logo标签列表

为什么要使用“strlen30()”而不是“strlen()”？

csqlitestrlen
7

我已经阅读并思考了SQLite的源代码。

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

为什么要使用 strlen30() 而不是 strlen()（在 string.h 中）？
不幸的是，SQLite源代码只是说了显而易见的事情 - “计算一个字符串长度，该长度限制为可以存储在32位有符号整数的低30位中。”。 - Rafał Rawicki
也许sqlite的其他部分无法处理大于1073741823字节的字符串——假设它们更小是解决方案（我不相信这个）。 - pmg
3个回答
3

这个变更所附带的提交信息如下：

[793aaebd8024896c] check-in [c872d55493] 的一部分，从不使用 strlen()。使用我们自己内部的 sqlite3Strlen30()，它保证永远不会溢出整数。额外显式转换以避免烦人的警告消息。(CVS 6007) (用户：drh 分支：trunk)

4
提交信息太糟糕了。我想知道如何使用“&”进行裁剪可以解决整数溢出的问题？ - sharptooth
@jeff 谢谢你的回答！我想在你的回答中再次阅读源代码。如果英文有错误，我想道歉。 - hority
1
@hority 您的英语绝对没有问题，所以不需要道歉！ - Jeff Foster
@sharptooth：因为只有无符号整数具有明确定义的溢出行为。对于有符号整数，它的定义不明确。此外，两个char指针之间的差异是否具有与普通整数相同的字节大小也没有定义。提交消息清晰简洁，但确实缺少指向详细功能请求或类似内容的指针。 - Sebastian Mach
@phresnel：你能否详细解释一下这个问题？它非常有趣，但我不太理解。 - sharptooth
@sharptooth：我已经在 你的新问题 中尝试给出答案 :) - Sebastian Mach
2

(这是我在为什么要重新实现strlen作为循环减法的答案，但它已经关闭了)

我不能告诉你他们为什么不得不重新实现它，以及为什么他们选择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.中规定：

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

...

41）：这意味着无符号算术不会溢出，因为不能由结果无符号整数类型表示的结果将对可以由结果无符号整数类型表示的最大值加1取模。

标准没有为有符号整数定义溢出行为。如果我们看一下5.表达式，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中）给出了signed long int的最小值，但没有最大值：

#define LONG_MAX +2147483647

现在问题来了，sqlite-strlen30() 的返回类型int的最大值是多少？让我们跳过转到C标准的C++引用，看一下在 C99 中，附录 E 中 int 的最小最大值：

#define INT_MAX +32767



概述

  1. ptrdiff_t通常不大于signed long，而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

这样做是为了避免指针相减的结果被截断，最大值为3FFFFFFF16 = 107374182310，这样可以防止未定义的行为。

我不确定他们为什么选择了这个确切的值，因为在大多数机器上，只有最高有效位说明符号。也许选择最小的INT_MAX与标准相符合更有意义，但是没有更多的细节，1073741823看起来确实有点奇怪（尽管它完全按照函数上方的注释所说的那样：截取30位并防止溢出）。

感谢您如此详细的回答！我很高兴您解答了我的琐碎问题。我曾认为“溢出”可能是编程语言的永恒问题... - hority
1
我猜他们选择了这个上限是为了允许执行某些类型的整数运算而不会招致 UB 的愤怒，但我认为他们的逻辑有些错误，因为在一个对象小于 4G 的 64 位机器上，将 size_t 定义为 uint32_t 和 ptrdiff_t 定义为 int32_t 是合法的，并且在从一个 3G 对象的末尾减去指针到开头时可以做任何事情。 - supercat
1

CVS提交信息如下：

永远不要使用strlen()。使用我们自己的内部sqlite3Strlen30()，它保证永远不会溢出整数。额外的显式转换以避免烦人的警告消息。(CVS 6007)

我找不到关于这个提交的进一步参考或解释，也不知道他们在那个地方如何溢出。我相信这是某些静态代码分析工具报告的错误。

原因很简单 - 在32位系统上，size_t无法适应int。因此，它们会裁剪最高有效位。我看不出这如何有助于溢出 - 无论你是否称其为裁剪，它都是裁剪。 - sharptooth
20亿个符号其实已经足够了，不需要用到TB级别。 - sharptooth
@Rafał 非常感谢您的回答！我学到了在发布问题之前必须阅读CVS提交消息...谢谢!(^o^)/ - hority
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接