19

受此问题启发，来自 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指向空终止符。然后z2-z产生字符串长度。

为什么不使用strlen()这部分并像这样重写：

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

为什么使用循环+减法而不是strlen()？循环+减法能做什么strlen()不能做什么？

4

2 回答 2

7

我无法告诉您他们必须重新实现它的原因，以及为什么他们选择intifsize_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 Fundamental Types , 4. 中说：

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

...

41)：这意味着无符号算术不会溢出，因为不能由得到的无符号整数类型表示的结果以比得到的无符号整数类型可以表示的最大值大一的数字为模减少

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

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

到目前为止溢出。

至于减去两个指向数组元素的指针，5.7 加法运算符，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 标准，我们将在 C99 附件 E 中看到 的最小最大值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 16 = 1073741823 10来防止未定义行为。

我不确定他们为什么选择这个值，因为在大多数机器上，只有最重要的位告诉 signness。与标准相比，选择 minimum 可能是有意义的INT_MAX，但是 1073741823 在不了解更多细节的情况下确实有点奇怪（尽管它当然完美地完成了他们函数上方的评论所说的：截断到 30 位并防止溢出）。



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

并像这样重写它：

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

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

顺便说一句，如下面的参考资料所示，(int)(strlen(z))如果 ptrdiff_t > 的最大值可能会产生未定义的行为INT_MAX，所以(int)(0x3fffffff & strlen(z))会更好。

于 2011-07-27T11:22:27.463 回答
1

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

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

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

于 2011-07-28T01:15:25.747 回答