strlen的一个实现，估计1/3人看不明白

远非那么简单，不是简单的
while(*s!='

远非那么简单，不是简单的
while(*s!='\0') {
s++;
len++;
}

size_t

strlen (str)

     const char *str;

{

  const char *char_ptr;

  const unsigned long int *longword_ptr;

  unsigned long int longword, himagic, lomagic;



  /* Handle the first few characters by reading one character at a time.

     Do this until CHAR_PTR is aligned on a longword boundary.  */

  for (char_ptr = str; ((unsigned long int) char_ptr

            & (sizeof (longword) - 1)) != 0;

       ++char_ptr)

    if (*char_ptr == '\0')

      return char_ptr - str;



  /* All these elucidatory comments refer to 4-byte longwords,

     but the theory applies equally well to 8-byte longwords.  */



  longword_ptr = (unsigned long int *) char_ptr;



  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits

     the "holes."  Note that there is a hole just to the left of

     each byte, with an extra at the end:



     bits:  01111110 11111110 11111110 11111111

     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD



     The 1-bits make sure that carries propagate to the next 0-bit.

     The 0-bits provide holes for carries to fall into.  */

  himagic = 0x80808080L;

  lomagic = 0x01010101L;

  if (sizeof (longword) > 4)

    {   

      /* 64-bit version of the magic.  */

      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */

      himagic = ((himagic << 16) << 16) | himagic;

      lomagic = ((lomagic << 16) << 16) | lomagic;

    }   

  if (sizeof (longword) > 8)

    abort ();



  /* Instead of the traditional loop which tests each character,

     we will test a longword at a time.  The tricky part is testing

     if *any of the four* bytes in the longword in question are zero.  */

  for (;;)

    {

      longword = *longword_ptr++;



      if (((longword - lomagic) & ~longword & himagic) != 0)

    {

      /* Which of the bytes was the zero?  If none of them were, it was

         a misfire; continue the search.  */



      const char *cp = (const char *) (longword_ptr - 1);



      if (cp[0] == 0)

        return cp - str;

      if (cp[1] == 0)

        return cp - str + 1;

      if (cp[2] == 0)

        return cp - str + 2;

      if (cp[3] == 0)

        return cp - str + 3;

      if (sizeof (longword) > 4)

        {

          if (cp[4] == 0)

        return cp - str + 4;

          if (cp[5] == 0)

        return cp - str + 5;

          if (cp[6] == 0)

        return cp - str + 6;

          if (cp[7] == 0)

        return cp - str + 7;

        }

    }

    }

}

38 个解决方案

#1

1/3人看不懂是个缺点，现在还是蛮有人会献丑的啊

#2

基础C语言标准库stdio的源码？

#3

gcc用的便是这个实现，性能应该不错

#4

引用 2 楼 sxjkk 的回复:

基础C语言标准库stdio的源码？

string.h 的源码

#5

我应该属于那1/3了

#6

哗众取宠的人还是有滴，简单的东西复杂化，有一套啊

#7

估计无非是把逐字节比较改成逐4字节比较，这样对于长字符串速度可以提高接近4倍

#8

引用 6 楼 hkf314 的回复:

哗众取宠的人还是有滴，简单的东西复杂化，有一套啊

这么能说哗众取宠呢，这些都是底层的函数实现啊，我们平常用的最普通的printf函数具体实现恐怕也很长

用printf函数打印是简单，但是写printf函数实现的人不简单

#9

引用 8 楼 sxjkk 的回复:

引用 6 楼 hkf314 的回复:
哗众取宠的人还是有滴，简单的东西复杂化，有一套啊

这么能说哗众取宠呢，这些都是底层的函数实现啊，我们平常用的最普通的printf函数具体实现恐怕也很长

用printf函数打印是简单，但是写printf函数实现的人不简单

printf超过2500行代码，实现绝非想象中的几百行

#10

引用 8 楼 sxjkk 的回复:

引用 6 楼 hkf314 的回复:
哗众取宠的人还是有滴，简单的东西复杂化，有一套啊

这么能说哗众取宠呢，这些都是底层的函数实现啊，我们平常用的最普通的printf函数具体实现恐怕也很长

用printf函数打印是简单，但是写printf函数实现的人不简单

应该说写api的人不简单，printf没几行，全是调用

#11

引用 7 楼 arong1234 的回复:

估计无非是把逐字节比较改成逐4字节比较，这样对于长字符串速度可以提高接近4倍

巧妙之处就在于如何保证这4个字节里没有'\0'

#12

1.怎么不使用编译开关？
可以去掉无谓的判断
如if (sizeof (longword) > 8)等等
虽然可能会被编译器优化掉

2.longword = *longword_ptr++;
看来看去，都觉得会越界

char_ptr = str;
longword_ptr = (unsigned long int *) char_ptr;

假如str的长度为2
这时能取到 sizeof(unsigned long int)字节么？

#13

楼上的不妨琢磨一下下面两句……
if (((longword - lomagic) & ~longword & himagic) != 0)

const char *cp = (const char *) (longword_ptr - 1);

#14

引用 12 楼 stjay 的回复:

2.longword = *longword_ptr++;
看来看去，都觉得会越界

char_ptr = str;
longword_ptr = (unsigned long int *) char_ptr;

假如str的长度为2
这时能取到 sizeof(unsigned long int)字节么？

再加条件char_ptr=0x00010000（只要是sizeof(longword)整数倍）
可跳过
for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

3.怎样在未知大小的内存空间里，能够每次取sizeof (unsigned long int)字节

4.const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
一旦这样unsigned long int*和char*互转
又得考虑大小端储存问题，即是移植性问题

#15

唉，居然这么复杂，看着有点头大了。

#16

吃完晚饭来写代码分析

#17

挨个判断字符是否为0，遇到0则退出，代码很简洁，也不算性能低。只是有点不足，在字长是4字节或者8字节的计算机上，每次只
读取一个字节，有些浪费计算机的能力，如果每次都读取4字节或者8字节，总的读取次数就大大减少，在读取4字节或者8字节的时
候，如果地址不在边界上，机器就要分两次才能读取完成，这样性能将会降低，弱化优化效果，所以前几个字符必须单独处理，然后
从字长边界地址开始，每次读取4字节或者8字节。

新的方式：

    * 开头的几字节单独处理
    * 中间部分4字节或者8字节处理
    * 最后几字节单独处理

看上去很好，但是还有一个问题，4字节或者8字节读取的时候，如何保证有全0的字节存在，因为0是用来表示字符串的结尾的。
判断连续的几个字节中是否存在全0的字节，成了优化的关键。我们不能一个字节一个字节判断，因为优化的思想就是一次读取
多个字节，减少总的读取次数，单独判断每一个字节的话，就失去优化的效果了。

怎么办呢，当然首先考虑位运算了。

    * 一个纯0的字节有什么特点? 很明显，每一位都是0，按位取反后每一位都是1。
    * 一个全0的字节还有什么特点? 这个字节减1，必然要从更高字节借1，借1后，该字节的最高位必然是1。

似乎有些眉目了，以4字节整数n为例，我们只要把每个字节分别减去1，如果有纯0的字节存在，必然会有借位，借位之后会在
字节最高位留下一个1。只要判断每个字节的最高位是否存在1就可以了，然而，这里还有一个问题，就是这个4字节整数里，
某些字节本来最高位可能就含有1，所以必须排除掉这些字节。

解决方案：

    * 将n的每一个字节分别减1，并取出最高位，得到x，如果存在借位，该字节最高位就是1
    * 将n的每一个字节按位取反并取出最高位，得到y，y中某字节最高位为1，表示它在n里是0
    * 将x和y按位与运算，若不等于0，说明n至少有1字节原本最高位不是1，后来变成1了，就是借位

若n中存在全0字节，则 x&y 一定不为0，因为借位的那个字节最高位会被置为1
若n中不存在全0字节，则不会产生借位，x&y 等于0。
x&y ==  (n-0x01010101) & ~n & 0x80808080

glibc中strcat的实现，基于以上结论，就不难理解了。glibc还考虑了字长是8字节的情况。

#18

原创  strlen 的高效实现  收藏

处理字符串的时候，经常需要获得字符串的长度，C标准库提供了strlen这个函数，实现一个普通的版本并不
困难，大致上跟下面的代码类似。

view plaincopy to clipboardprint?

   1. unsigned int strlen(const char *s)
   2. {
   3.     char *e = s;
   4.     while (*e)
   5.         e++;
   6.     return (e-s);
   7. }

unsigned int strlen(const char *s) { char *e = s; while (*e) e++; return (e-s); }

挨个判断字符是否为0，遇到0则退出，代码很简洁，也不算性能低。只是有点不足，在字长是4字节或者8字节
的计算机上，每次只读取一个字节，有些浪费计算机的能力，如果每次都读取4字节或者8字节，总的读取次数
就大大减少，在读取4字节或者8字节的时候，如果地址不在边界上，机器就要分两次才能读取完成，这样性能
将会降低，弱化优化效果，所以前几个字符必须单独处理，然后从字长边界地址开始，每次读取4字节或者8字
节。

新的方式：

    * 开头的几字节单独处理
    * 中间部分4字节或者8字节处理
    * 最后几字节单独处理

看上去很好，但是还有一个问题，4字节或者8字节读取的时候，如何保证有全0的字节存在，因为0是用来表示
字符串的结尾的。判断连续的几个字节中是否存在全0的字节，成了优化的关键。我们不能一个字节一个字节判
断，因为优化的思想就是一次读取多个字节，减少总的读取次数，单独判断每一个字节的话，就失去优化的效
果了。

怎么办呢，当然首先考虑位运算了。

    * 一个纯0的字节有什么特点? 很明显，每一位都是0，按位取反后每一位都是1。
    * 一个全0的字节还有什么特点? 这个字节减1，必然要从更高字节借1，借1后，该字节的最高位必然是1。

似乎有些眉目了，以4字节整数n为例，我们只要把每个字节分别减去1，如果有纯0的字节存在，必然会有借位，
借位之后会在字节最高位留下一个1。只要判断每个字节的最高位是否存在1就可以了，然而，这里还有一个问
题，就是这个4字节整数里，某些字节本来最高位可能就含有1，所以必须排除掉这些字节。

解决方案：

    * 将n的每一个字节分别减1，并取出最高位，得到x，如果存在借位，该字节最高位就是1
    * 将n的每一个字节按位取反并取出最高位，得到y，y中某字节最高位为1，表示它在n里是0
    * 将x和y按位与运算，若不等于0，说明n至少有1字节原本最高位不是1，后来变成1了，就是借位

若n中存在全0字节，则 x&y 一定不为0，因为借位的那个字节最高位会被置为1
若n中不存在全0字节，则不会产生借位，x&y 等于0。
x&y ==  (n-0x01010101) & ~n & 0x80808080

#19

#20

#21

来学习了

#22

看不懂。。。汗。。。。

#23

主要是考虑了一些宽字符的情况，所以这么复杂。
我没看明白，也没怎么细看……
这些东西，除非用到，否则没必要研究吧，因为并不是多巧妙，只是问题本身很复杂。

#24

高人

#25

mark

#26

纯粹路过；

#27

都是强人呀！

#28

学习。。。。。。。。

#29

good

#30

该回复于2009-11-16 08:58:25被版主删除

#31

如果要看懂这样经过优化的代码，就一定要对CPU的硬件结构有一定的了解，纯从软件的角度确实会觉得复杂了。

#32

一般的代码，不需要这么复杂吧！！

#33

库里面大多是通过汇编来实现的，x86种直接有对应的求长度的指令，速度比你这方法快不是一个等量级的

#34

引用 33 楼 cangyingzhijia 的回复:

库里面大多是通过汇编来实现的，x86种直接有对应的求长度的指令，速度比你这方法快不是一个等量级的

这个是比较通用的算法，具体到某个平台上，未必是最优，但至少达到了比较好的性能。
如果考虑到平台的特异性，那就得针对不同的平台，用不同的汇编了。
就像memcpy，最快的是DMA，但未必所有的平台都支持DMA。

#35

路过。。。

#36

1/3

#37

我靠，我看不懂！~~~

#38

很强大呀！

') {
s++; s++;