strstr的各种实现–从strlen的实现谈起___pi_strcmp+0x8c

如果不看glibc的代码，那么也许你永远也不知道什么叫境界，仅仅认为简单的可读性强的代码就是最好的代码的人也一定停留在应届毕业生的水平，程序很大意义上是给机器看的而不是给人看的，人看程序很大意义上是维护和经验学习，本文从简单的几个标准c的库函数来分析一下函数实现算法设计的重要性，首先谈谈strlen的实现，然后谈一下strstr的实现，最后实现一个我自己的strstr。先从strlen开始吧，一般而言，strlen的显而易见的实现就是傻傻的呆呆的一个一个字符的扫描，同时递加计数器，待到扫描到0的时候返回计数器的值就是字符串的长度，这种算法绝对简单，相同思想的别的算法可以实现的短小精悍，起码能唬过面试官，必要的时候能让女朋友更加崇拜你，但是高手并不仅仅满足于代码本身的美，而是喜于挖掘更深层次的东西，考虑每次扫描一个字符，然后判断它是否为0，时间将大大消耗在一个个判断和慢速的推进，如果字符串很长，那么时间将会消耗得很大，因此显然的想法就是将推进步伐加大，然后判断这一大步中是否包含有字符0，一次迈一大步节省了总的步数，但是判断一大步是否包含0成了瓶颈，步伐越大判断越难，难道又要在一大步中一个个字符扫描吗？如果那样最终的步进并没有变得高效，因此在判断“是否包含0”的时候必须用另一种时间复杂度为O(1)的算法来解决，这就是位运算，于是glibc的天才实现就是一次步进一个32位的word，然后用一个巧妙的位运算来解析出有没有0包含其中，实际上如果机器本身实现了更长的数据类型则完全可以使用这种更长的类型来实现更长的步进，在32位的x86机器上，32字节的长度就够长了，直接获得了底层的高效支持，来看一下代码：

size_t strlen ( const char *str )

{

const char *char_ptr;

const unsigned long int *longword_ptr;

unsigned long int longword, magic_bits, himagic, lomagic;

for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr)

if (*char_ptr == '/0') //这个for主要是想看看第一个4字节对齐过程中是否会结束操作，如果结束则直接返回实际结束的位置和开始位置的差

return char_ptr - str;

longword_ptr = (unsigned long int *) char_ptr;

//himagic：10000000 10000000 10000000 10000000

//lomagic：00000001 00000001 00000001 00000001

himagic = 0x80808080L;

lomagic = 0x01010101L;

...

if (sizeof (longword) > 8)

abort ();

for (;;)

{

longword = *longword_ptr++;

//仔细看看下面的这个判断，longword - lomagic的结果，如果longword中有一个字节全0，那么在其减去lomagic之后，对应的该字节的最高位将会成为1，和himagic与操作之后结果就会不为0，然后就剩下判断了，该操作正确的前提是所有的字符都是ascii字符，也就是其最高位开始都是0，这个位运算是很显然的，另外除了这个技巧之外还有一个类似的算法如下：

unsigned long magic = 0x7efefeffL; (01111110 11111110 11111110 11111111)

unsigned long longword = XXXX;

unsigned long r1 = longword + magic; (如果有一个字符不是0，那么经过这个加法后，比此字符更高的一位的最低位的0将会成为1)

unsigned long r2 = (r1 ^ ~longword) ; (这个操作将会加法后的结果中和原来的longword相比没有改变的位全部置为1，只要magic对应每个字节的最低位被进位，那么加和和原来的数据的该位必不相同，如果原始位为1，那么由于进位加上magic的变成1的相应位后就会成为0，如果原始位为0，那么加上magic后将成为1)

unsigned long r3 = r2 & ~magic; (magic的反码的每个字节的最低位为1其余为0，和r2相与之后如果不为0，就说明有全是0的字节)

if( r3 != 0 ) ... (完毕，这个算法稍显复杂，但是更加具有技巧性，由此可见位运算是多么强大)

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

{

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;

...//不考虑的情况

}

}

}

欣赏完了strlen的实现，我不禁想赞叹其作者的聪明才智，其实不是作者很聪明，而是只要对c语言位运算有深刻理解的程序员都应该能做出来，在此基础之上，我们返璞归真的看一下ststr的实现，strstr其本质就是在既有字符串中匹配字串，完全可以应用上述算法，于是我自己实现了一个算法完全按照上述strlen的算法，在引出这个属于我自己的算法之前还是从最基本的BSD的libc实现的strstr开始吧：

char * strstr1(const char * s, const char * find)

{

char c, sc;

size_t len;

if ((c = *find++) != 0)

{

len = strlen(find);

do

{

do

{

if ((sc = *s++) == 0) //按照字节推进，到达源字符串末尾时直接返回NULL

return (NULL);

} while (sc != c);

} while (strncmp(s, find, len) != 0); //比对从此位置开始的len长度的所有字符，strncmp是一个复杂的操作，因此注定此函数效率不高，但是很清晰。

s--;

}

return ((char *)s);

}

下面看看windows的CRT的实现吧，比BSD好了那么一点，说实话这个算法是非常不错的，就我个人测试得出的结果，它的效率除了在某种情况下低于glibc的之外，其它的情况下是最高的：

char * strstr2 ( const char * str1, const char * str2)

{

char *cp = (char *) str1;

char *s1, *s2;

if ( !*str2 )

return((char *)str1);

while (*cp) //该算法以str2为基准在str1逐字节匹配

{

s1 = cp;

s2 = (char *) str2;

while ( *s1 && *s2 && !(*s1-*s2) )

s1++, s2++;

if (!*s2) //如果s2在和s1比较中提前结束，那么说明匹配成功

return(cp);

cp++;

}

return(NULL);

}

下面的strstr3是glibc的算法，我看了好长时间都没有看懂，我就不解释代码的意义了，该代码体现了一种境界，这种境界不是一般的人所能达到的，代码已经不仅仅是让一般人读的了，代码的读者是和机器合为一体的人才能读懂的：

typedef unsigned chartype;

char * strstr3( char *phaystack, char *pneedle)

{

unsigned char *haystack, *needle;

chartype b;

unsigned char *rneedle;

haystack = ( unsigned char *) phaystack;

if ((b = *(needle = ( unsigned char *) pneedle)))

{

//printf("un is:%d/n",b);

chartype c;

haystack--; /* possible ANSI violation */

{

chartype a;

do

if (!(a = *++haystack))

goto ret0;

while (a != b);

}

if (!(c = *++needle))

goto foundneedle;

++needle;

goto jin;

for (;;)

{

{

chartype a;

if (0)

jin:{

if ((a = *++haystack) == c)

goto crest;

}

else

a = *++haystack;

do

{

for (; a != b; a = *++haystack)

{

if (!a)

goto ret0;

if ((a = *++haystack) == b)

break;

if (!a)

goto ret0;

}

}while ((a = *++haystack) != c);

}

crest:

{

chartype a;

{

const unsigned char *rhaystack;

if (*(rhaystack = haystack-- + 1) == (a = *(rneedle = needle)))

do

{

if (!a)

goto foundneedle;

if (*++rhaystack != (a = *++needle))

break;

if (!a)

goto foundneedle;

}while (*++rhaystack == (a = *++needle));

needle = rneedle; /* took the register-poor aproach */

}

if (!a)

break;

}

}

}

foundneedle:

return (char *) haystack;

ret0:

return 0;

}

最后看看我的版本，我所实现的这个strstr函数有个特点，它只在一定的情况下才能体现高效性能，就是在大容量字符串匹配的情况下，因为这个算法和glibc的strlen一样，是按照4个字节的步伐向前推进的，因此一旦找到匹配的字符创，那么后面的匹配将会非常快，经过我的测试，这个实现在大量字符匹配时会很高效：

char * strstr4( const char *str, const char * find)

{

unsigned long *long_ptr_src,*long_ptr_find;

unsigned long magic1 = 0x80808080L, magic2 = 0x01010101L;

long_ptr_src = (unsigned long*)str;

long_ptr_find = (unsigned long*)find;

while (1)

{

unsigned long tmp = *long_ptr_src^*long_ptr_find;

if(tmp == 0)

{

long_ptr_src++;

long_ptr_find++;

continue;

}

else

{

if ((((*long_ptr_src - magic2) & magic1) == 0)&&(((*long_ptr_find - magic2) & magic1) != 0))

{

char *cp = (char*)(long_ptr_find);

char * tt = (char *)(long_ptr_src);

if (cp[0] == 0 ||(cp[1] == 0 &&tt[0] == cp[0])||

(cp[2] == 0 && tt[0] == cp[0]&& tt[1] == cp[1])||

(cp[3] == 0 &&tt[0] == cp[0]&& tt[1] == cp[1]&& tt[2]==cp[2]))

return tt - (cp-find);

return NULL;

}

if (((*long_ptr_src - magic2) & magic1) != 0)

{

return NULL;

}//差一种两个字符串均到尾部的情况需要讨论，比较复杂

int mp = 1;

while (!(tmp & 0xFF000000))

{

mp++;

tmp <<= 8;

}

char * tmpchar = (char *)long_ptr_src;

tmpchar += mp;

long_ptr_src = (unsigned long*)tmpchar;

long_ptr_find = (unsigned long*)find;

}

}

}

以下是测试程序：

char *a1 = (char *)malloc(512);

memset(a1,0,512);

strcpy(a1,"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()_+~QWERTYUIOPasdfghjklzxcvbnmzaqwsxcderfvbgtyhnujmkiol,./;'p[]");

char *a2 = (char *)malloc(512);

memset(a2,0,512);

strcpy(a2,"defghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()_+~QWERTYUIO");//jklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()_+~QWERTYUIOPasdfghjklzxcvbnmzaqwsxcderfvbgtyhnujmkiol,");

unsigned long c1 = GetCycleCount();

char *a3 = strstrX(a1,a2);

unsigned long c2 = GetCycleCount();

unsigned long delta = c2 - c1;

最后，有一个问题值得思考，然后看看这个strstr4算法中存在的问题，就是这个strstr实现的过程和rsync算法很相似，其实也是一种权衡，在时间和空间之间的权衡。strstr4的实现思想其实和CRT的实现strstr2是一致的，只是加入了glibc的strlen实现中所用到的算法，strstr4算法的好处在于如果需要匹配的字符串很长，那么将会很高效，但是如果在源字符串很长的索引处才匹配成功，那么时间将大量花费在：

int mp = 1;

while (!(tmp & 0xFF000000))

{

mp++;

tmp <<= 8;

}

char * tmpchar = (char *)long_ptr_src;

tmpchar += mp;

long_ptr_src = (unsigned long*)tmpchar;

其实看看这个计算的结果，看似很有技巧性，实际上很多情况下的结果都是执行tmpchar+=1的操作，这个和strstr2中的cp++是一致的，不幸的是耗费了更多的时间在移位和判断上，再一个就是这个算法是根本错误的，比如一个字符串是aaaaooooo，匹配字符串是aaaooo，如果按照strstr4的理解那么就是将源字符串的匹配指针一下子移动到o处重新开始匹配，这是错误的，因此修改为strstr2的方式，那样的话效率将会大大提高：

char * tmpchar = (char *)long_ptr_src;

tmpchar ++;

long_ptr_src = (unsigned long*)tmpchar;