为什么重新实现strlen作为循环+减法?
受到关于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()
不能?
为什么重新实现strlen作为循环+减法?
我怀疑真正的答案是程序员感觉像是这样,但另一个潜在的理由/合理化是循环是内联的(与strlen30
本身是否相关),而在许多系统上, strlen
是一个外联函数调用(例如Linux的/ GCC)。 如果绝大多数字符串是空的或短的(尽管对长字符串采用“特殊”处理),那么对于常见情况可能会产生轻微的性能提升。 仅仅这种可能性就足以让代码开心的程序员点击攻击。 对于更长的字符串,我希望库strlen
通常是最优的(允许它缺乏应用程序特定字符串长度的知识)。
有些系统甚至可能不会受益于这种内联,因为strlen
提供了自己的内联,或内联/外联混合,快速内联检查空,一个char,可能是两个char字符串然后调用。
我不能告诉你为什么他们必须重新实现它,以及为什么他们选择int
而不是size_t
作为返回类型。 但关于function:
/* ** 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的定律,其中n是该特定整数大小的值表示中的位数。 41)
…
41) :这意味着无符号算术不会溢出,因为无法由结果无符号整数类型表示的结果以比模式生成的无符号整数类型所表示的最大值大1的数量减少模数
该部分标准没有定义有符号整数的溢出行为。 如果我们看一下5.表达式 ,5:
如果在评估表达式期间,结果未在数学上定义或未在其类型的可表示值范围内,则行为未定义,除非此类表达式是常量表达式(5.19),在这种情况下程序生病-formed。 [注意:大多数现有的C ++实现忽略整数溢出。 除零处理,使用零除数形成余数,所有浮点exception因机器而异,通常可通过库函数调整。 ]
到目前为止溢出。
至于减去两个指向数组元素的指针, 5.7 Additive运算符 ,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中)给出了有符号long int的最小幅度 ,但不是最大值:
#define LONG_MAX +2147483647
现在int
的最大值是什么, sqlite - strlen30()
的返回类型sqlite - strlen30()
? 让我们跳过再次将我们转发到C标准的C ++引用,我们将在附件E的C99中看到int
的最小最大值:
#define INT_MAX +32767
关于截断部分的摘要
- 通常,
ptrdiff_t
不大于有signed long
ptrdiff_t
,它不小于32位。 -
int
被定义为至少16位长。 - 因此,减去两个指针可能会产生一个不适合您平台的
int
的结果。 - 我们从上面记得,对于签名类型,不适合的结果会产生未定义的行为。
-
strlen30
确实应用了bitwise或者指针 – 减法 – 结果:
| 32 bit | ptr_diff |10111101111110011110111110011111| // could be even larger & |00111111111111111111111111111111| // == 3FFFFFFF16 ---------------------------------- = |00111101111110011110111110011111| // truncated
这可以通过将指针减法结果截断为最大值3FFFFFFF 16 = 1073741823 10来防止不受欢迎的行为。
我不确定他们为什么选择这个值,因为在大多数机器上,只有最重要的一点才能说出签名 。 选择最小INT_MAX
可能比标准INT_MAX
,但1073741823确实有点奇怪而不知道更多细节(尽管它当然完全符合其function上面的注释:截断到30位并防止溢出)。
“为什么不在这部分使用strlen()”
并重写它像这样:
return 0x3fffffff & (int)(strlen(z));
我的猜测是他们想要避免潜在的间接性。 另一个优点可能是对标准库的依赖性较少,如果您编写非托管应用程序,这可能很有用。
顺便说一句,如上面的引用所示,如果ptrdiff_t> INT_MAX
的最大值,那么(int)(0x3fffffff & strlen(z))
(int)(strlen(z))
可能会产生未定义的行为,因此(int)(0x3fffffff & strlen(z))
会更好。