strlen

之前只有一篇关于较早版本的 strlen(3) 实现的笔记，这里补上我在2010年做的新增改进。

背景与历史

与Pascal等语言不同，C语言的字符串并不显式保存长度，而是在字符串末尾以NUL字符（'\0'）标记结束。这个设计决策是上世纪60年代做出的，坊间传闻是为了节省几个字节的存储空间，不过我个人认为也可能是因为早期汇编指令中充满了测试零值的操作。无论缘由如何，这一设计直接导致strlen必须遍历整个字符串，成为一个$O(n)$操作。

早期的BSD Unix采用的strlen实现十分简单粗暴，即通过循环逐字节比较是否为NUL。1993年，J.T. Conklin为i386架构撰写了汇编优化版本，其核心利用了rep scasb指令，在算法逻辑上与C版本逐字节扫描并无二致（彼时C编译器尚无法自动生成这类指令）。

为了配合x86_64平台，后来又引入了新的汇编版本。该版本的核心思想升级为按机器字（word）匹配：先以字为单位快速推进，定位到包含NUL字符的字之后，再在该字内部按原始逐字节算法精确定位NUL的位置。

我在2009年根据这个x86_64汇编思路重写了一个纯C语言版本，并在2010年完成了最终调整，形成了当前版本。算法整体流程如下：

• 首字检测：判断首个机器字中是否存在NUL；若存在，则自起始有效位置扫描查找其中的NUL字符；
• 按字遍历：按机器字宽度主循环扫描剩余字符串，一旦发现当前字包含NUL，则精确定位并返回总长度。

I have taken some time to rewrite memchr(3) to utilize similiar algorithm as my strlen(3) did. Two different formular, however, would have a roughly 1/3 difference.

Currently I have taken an approach that when memchr(3) is trying to match a pattern of 8-bit, then consider the string as 8-bit, which uses the first formular which is expected to have uniform O(n) time complexity by reducing unnecessary branches.

This approach, however, might be bogus since if you find 7-bit character within a 8-bit string, in that case, memchr(3) would perform poorly, if there are a lot of characters having their MSB as 1.