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

2024-01-07

灵感来自这个问题 https://stackoverflow.com/q/6842130/57428关于 SQLite3 中的以下代码：

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

伴随着提交消息 http://www.sqlite.org/src/timeline?c=2008-12-10%2019:26:22说这个功能有帮助int溢出。

我对这部分特别感兴趣：

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

对我来说这个循环前进z2 until z2指向空终止符。然后z2-z产生字符串长度。

为什么不使用strlen()对于这部分并重写如下：

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

为什么用循环+减法而不是strlen()？循环+减法可以做什么strlen() can't?

我无法告诉你为什么他们必须重新实施它，以及为什么他们选择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.:

Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2ⁿ where n is the number of bits in the value representation of that particular size of integer. 41)

...

⁴¹⁾: This implies that unsigned arithmetic does not overflow because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting unsigned integer type

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

如果在计算表达式期间，结果未在数学上定义或不在其类型的可表示值范围内，则行为未定义，除非此类表达式是常量表达式（5.19），在这种情况下程序是格式错误的。 [注：大多数现有的 C++ 实现都会忽略整数溢出。除以零的处理、使用零除数形成余数以及所有浮点例外情况因机器而异，通常可以通过库函数进行调整。 ]

到目前为止溢出。

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

当两个指向同一数组对象的元素的指针相减时，结果是两个数组元素的下标之差。结果的类型是实现定义的有符号整型；该类型应与标头 (18.1) 中定义为 ptrdiff_t 的类型相同。 [...]

看着18.1:

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

那么让我们看看 C 标准（不过我只有 C99 的副本），7.17 通用定义:

用于 size_t 和 ptrdiff_t 的类型不应具有整数转换等级大于signed long int 除非实现支持对象大到足以使这一点成为必要。

不作进一步保证ptrdiff_t。然后，附录 E（仍在 ISO/IEC 9899:TC2 中）给出了最小震级对于有符号长整型，但不是最大值：

#define LONG_MAX +2147483647

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

#define INT_MAX +32767

关于截断部分的总结

通常，ptrdiff_t不大于signed long，不小于32位。
int只是定义为至少 16 位长。
因此，两个指针相减可能会得到不适合的结果int您的平台。
我们从上面记得，对于有符号类型，不适合的结果会产生未定义的行为。
strlen30确实对指针减结果应用按位或：

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

That prevents undefiend behaviour by truncation of the pointer-subtraction result to a maximum value of 3FFFFFFF₁₆ = 1073741823₁₀.

我不确定他们为什么选择这个值，因为在大多数机器上，只有最高有效位表示符号性 http://en.wikipedia.org/wiki/Signed_number_representations#One.27s_complement。相对于标准，选择最小值可能是有意义的INT_MAX，但是 1073741823 在不了解更多细节的情况下确实有点奇怪（尽管它当然完美地实现了其函数上面的注释：截断为 30 位并防止溢出）。

“为什么这部分不使用 strlen()”

并像这样重写：

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

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

顺便说一句，从上面的参考文献中可以看出，(int)(strlen(z))如果 ptrdiff_t > 的最大值，可能会产生未定义的行为INT_MAX, so (int)(0x3fffffff & strlen(z))会更好。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)