为什么重新实现strlen作为循环+减法？

Question

受到关于SQLite3中以下代码的这个问题的启发:

 static int strlen30(const char *z){
    const char *z2 = z;
    while( *z2 ){ z2++; }
    return 0x3fffffff & (int)(z2 - z);
 }

这附带一条提交消息,说这个函数有助于int溢出.

我对这部分特别感兴趣:

 const char *z2 = z;
 while( *z2 ){ z2++; }

对我来说,这个循环前进,z2直到z2指向null终止符.然后z2-z产生字符串长度.

为什么不使用strlen()这个部分并重写如下:

return 0x3fffffff & (int)(strlen(z));

为什么使用循环+减法代替strlen()？什么可以循环+减法做什么strlen()不可以？

Answer 1

我不能告诉你为什么他们必须重新实现它,以及为什么他们选择int如果size_t作为返回类型.但关于功能:

/*
 ** Compute a string length that is limited to what can be stored in
 ** lower 30 bits of a 32-bit signed integer.
 */
static int strlen30(const char *z){
    const char *z2 = z;
    while( *z2 ){ z2++; }
    return 0x3fffffff & (int)(z2 - z);
}

关于截断,类型,溢出的标准参考

标准(ISO/IEC 14882:2003(E))3.9.1基本类型,4:

声明无符号的无符号整数应遵守算术模2 ⁿ的定律,其中n是该特定整数大小的值表示中的位数.41)

...

⁴¹⁾:这意味着无符号算术不会溢出,因为无法通过结果无符号整数类型表示的结果以比模式生成的无符号整数类型所表示的最大值大1的数量减少模数

该部分标准没有定义有符号整数的溢出行为.如果我们看一下5.表达式,5:

如果在评估表达式期间,结果未在数学上定义或未在其类型的可表示值范围内,则行为未定义,除非此类表达式是常量表达式(5.19),在这种情况下程序生病-formed.[注意:大多数现有的C++实现忽略整数溢出.除零处理,使用零除数形成余数,所有浮点异常因机器而异,通常可通过库函数调整.]

到目前为止溢出.

至于减去两个指向数组元素的指针,5.7 Additive运算符,6:

当减去指向同一数组对象的元素的两个指针时,结果是两个数组元素的下标的差异.结果的类型是实现定义的有符号整数类型; 此类型应与标题(18.1)中定义为ptrdiff_t的类型相同.[...]

看18.1:

内容与标准C库头stddef.h相同

那么让我们看看C标准(虽然我只有C99的副本),7.17常见定义:

1. 用于size_t和ptrdiff_t的类型不应具有大于signed long int的整数转换等级,除非该实现支持足够大的对象以使其成为必要.

没有进一步的保证ptrdiff_t.然后,附件E(仍在ISO/IEC 9899:TC2中)给出了有符号long int 的最小幅度,但不是最大值:

#define LONG_MAX +2147483647

现在int返回类型的最大值是sqlite - strlen30()多少？让我们跳过再次将我们转发到C标准的C++引用,我们将在附件E的C99中看到,最小值为int:

#define INT_MAX +32767

有关截断部分的摘要

1. 通常,ptrdiff_t不大于signed long,不小于32位.
2. int 被定义为至少16位长.
3. 因此,减去两个指针可能会产生一个不适合 int您的平台的结果.
4. 我们从上面记得,对于签名类型,不适合的结果会产生未定义的行为.
5. strlen30 确实按位或​​按指针减去结果:

          | 32 bit                         |
ptr_diff  |10111101111110011110111110011111| // could be even larger
&         |00111111111111111111111111111111| // == 3FFFFFFF<sub>16</sub>
          ----------------------------------
=         |00111101111110011110111110011111| // truncated

这可以通过将指针减法结果截断为最大值3FFFFFFF ₁₆ = 1073741823 ₁₀来防止不受欢迎的行为.

我不确定他们为什么选择这个值,因为在大多数机器上,只有最重要的一点才能说出签名.选择最小值可能比标准更有意义INT_MAX,但1073741823确实有些奇怪而不知道更多细节(尽管它当然完全符合其功能上面的注释:截断到30位并防止溢出).

"为什么不在这部分使用strlen()"

并重写它像这样:

return 0x3fffffff & (int)(strlen(z));

我的猜测是他们想要避免潜在的间接性.另一个优点可能是对标准库的依赖性较少,如果您编写非托管应用程序,这可能很有用.

顺便提一下,如上所述,(int)(strlen(z))如果ptrdiff_t>的最大值,可能会产生未定义的行为INT_MAX,因此(int)(0x3fffffff & strlen(z))会更好.

Answer 2

为什么将 strlen 重新实现为循环+减法？

我怀疑真正的答案是程序员喜欢它，但另一个潜在的理由/合理化是循环是内联的（独立于它strlen30本身是否是），而在许多系统上strlen是外联函数调用（例如Linux/海湾合作委员会）。如果绝大多数字符串是空的或短的（尽管对长字符串进行了“特殊”处理），那么对于常见情况可能会产生轻微的性能提升。仅这种可能性就足以让喜欢编写代码的程序员敲击键盘。对于较长的字符串，我希望该库strlen通常是最佳的（考虑到它缺乏对应用程序特定字符串长度的了解）。

有些系统甚至可能无法从这种内联中受益，因为strlen它自己提供了这种内联，或者是内联/外联混合，可以快速内联检查空的、一个字符的、可能是两个字符的字符串，然后调用。