深圳网站设计兴田德润信任高,网站建设唯特和凡科哪个好,今天大事件新闻,分类wordpresshttps://blog.delphij.net/2012/04/freebsd-strlen3.html 与 Pascal 等语言不同#xff0c;C 的字符串并不保存串的长度#xff0c;而是在字符串末尾以 nul 字符#xff08;\0#xff09;来表示字符串结束。这个设计决策是上世纪 60 年代作出的#xff0c;有都市传说是为了…https://blog.delphij.net/2012/04/freebsd-strlen3.html 与 Pascal 等语言不同C 的字符串并不保存串的长度而是在字符串末尾以 nul 字符\0来表示字符串结束。这个设计决策是上世纪 60 年代作出的有都市传说是为了省几个字节的空间不过我个人认为也可能是因为汇编里面到处都是判断是否碰到了 0 的操作。不管怎么说这个设计令 strlen 变成了一个 O(n) 的操作。 早期的 BSD Unix 采用的 strlen 是非常简单的循环比较每一个字符是不是 nul。1993年J.T. Conklin 为 i386 系统撰写了一个汇编的版本这个版本的核心用的是 REP SCASB实际上和 C 版本的算法是一样的不知道为什么 C 编译器不能写出同样的代码。 为了配合 x86_64 平台后来又有了一个新的汇编版本这个版本的核心算法是按字匹配找到包含 nul 字符的字之后再在其中用原始的算法找到 nul 字符。 我在 2009 年根据这个 x86_64 版本的汇编的思路重写了一个 C 的版本并在 2010 年做了一次最终的变动形成了目前的版本。这个版本的大致流程如下 判断第一个字中是否存在 nul如果存在扫描查找其中有效位置的 nul 字符 按字扫描剩余的字符串如果发现字中带 nul则扫描并返回其位置。 实现细节 整个算法中比较难理解的是判断字中是否带 nul 字符。具体的方法是计算两个中间变量 a (x - 0x01010101) b (~x 0x80808080) 计算 a b 0 这里的 0x01010101 和 0x80808080 可以进一步扩展。第一步如果每个字节都 0x7f只要那个字节不是 0做差必然得到一个 0x80 的结果换言之最高位是0如果有字节 0x81做差必然得到一个 0x80 的结果。对于等于 0x80 的情况我们会得到 0x7f但这并不重要。 注意到此处任何一个字节的最高 bit 是 1 的话则必然是前面两种情况之一要么这个字节是 0要么它 0x81。如果不考虑后一种情况我们直接把结果 0x80808080 即可然而由于需要考虑后一种情况我们接着计算 ~x 0x80808080。若某一字节 0x80则对应的结果将是那个位置上的一个 0x80。 将两个结果做逻辑与若结果非 0 则说明至少有一个字节是 nul。 这里说起来的过程很复杂但事实上计算机计算这些要比一个一个去判断每个字节是否为 0 要快。这里有几方面的原因 按字长做操作令 CPU 无需模拟按字节为长度操作的情况后者是比较耗时的 前两步操作分别计算a, b可以并发执行 最后一步操作可以直接在两个寄存器之间进行且是速度较快的与运算 在实际的实现中还有一些其他的技巧。 第一个技巧是从第一个小节就开始用字长的操作。一般来说内存分配器在分配内存时是以字边界开始的因此通常 strlen() 的操作的指针都是对齐的。不过即使不是这个指针往前退到第一个整字位置例如字长8指针 0x9则退回 0x8开始的一个整字必然是在同一个内存页上因此这个访问不会越界。如果在这个整字中有 nul 字符我们只需从指针开始处扫描到第一个整字结尾的地方即可知道是不是真的找到了字符串的末尾。 由于整个字已经在处理器缓存中后续的循环也不会太慢。 第二个技巧与此类似我们一直都用整字的操作。如果字的起始地址在内存页中则终止地址也必然在同一个内存页中。这个访问同样也不会发生意外越界尽管在分配内存时可能出现类似分配了 4 个字节但访问了 8 个字节的情况。换言之如果程序原先不会发生越界异常则现在也不会。 这个版本的 strlen 源代码可以在 这里 找到。 转载于:https://www.cnblogs.com/marryZhan/archive/2012/05/23/2797292.html
