strlen源碼剖析快速确定字元串結束符位置
整理分别來自于下面的文章。
http://code.google.com/p/strstrsse/source/browse/trunk/
http://www.cppblog.com/djxzh/archive/2008/10/27/65245.aspx
http://www.cppblog.com/ant/archive/2007/10/12/32886.html
學習高效程式設計的有效途徑之一就是閱讀高手寫的源代碼，CRT(C/C++ Runtime Library)作為底層的函數庫，實作必然高效。恰好手中就有glibc和VC的CRT源代碼，于是挑了一個相對簡單的函數strlen研究了一下，并對各種實作作了簡單的效率測試。
strlen的函數原形如下：
size_t strlen(const char *str);
strlen傳回str中字元的個數，其中str為一個以'\0'結尾的字元串(a null-terminated string)。
1. 簡單實作
如果不管效率，最簡單的實作隻需要4行代碼：
1 size_t strlen_a(const char *str) {
2 size_t length = 0;
3 while (*str++)
4 ++length;
5 return length;
6 }
也許可以稍加改進如下：
1 size_t strlen_b(const char *str) {
2 const char *cp = str;
3 while (*cp++)
4 ;
5 return (cp - str - 1);
6 }
2. 高效實作
很顯然，标準庫的實作肯定不會如此簡單，上面的strlen_a以及strlen_b都是一次判斷一個字元直到發現'\0'為止，這是非常低效的。比較高效的實作如下(在這裡WORD表示計算機中的一個字，不是WORD類型)：
(1) 一次判斷一個字元直到記憶體對齊，如果在記憶體對齊之前就遇到'\0'則直接return，否則到(2)；
(2) 一次讀入并判斷一個WORD，如果此WORD中沒有為0的位元組，則繼續下一個WORD，否則到(3)；
(3) 到這裡則說明WORD中至少有一個位元組為0，剩下的就是找出第一個為0的位元組的位置然後return。
NOTE：
資料對齊(data alignment)，是指資料所在的記憶體位址必須是該資料長度的整數倍，這樣CPU的存取速度最快。比如在32位的計算機中，一個WORD為4 byte，則WORD資料的起始位址能被4整除的時候CPU的存取效率比較高。CPU的優化規則大概如下：對于n位元組(n = 2,4,8...)的元素，它的首位址能被n整除才能獲得最好的性能。
為了便于下面的讨論，這裡假設所用的計算機為32位，即一個WORD為4個位元組。下面給出在32位計算機上的C語言實作(假設unsigned long為4個位元組)：
1 typedef unsigned long ulong;
3 size_t strlen_c(const char *str)
4 {
5 const char *char_ptr;
6 const ulong *longword_ptr;
7 register ulong longword, magic_bits;
9 for (char_ptr = str; ((ulong)char_ptr & (sizeof(ulong) - 1)) != 0; ++char_ptr) {
12 if (*char_ptr == '\0')
13 return char_ptr - str;
14 }
16 longword_ptr = (ulong*)char_ptr;
17 magic_bits = 0x7efefeffL;
[S1] 20 while (1) {
22 longword = *longword_ptr++;
24 if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0) {
25 const char *cp = (const char*)(longword_ptr - 1);
27 if (cp[0] == 0)
29 return cp - str;
30 if (cp[1] == 0)
31 return cp - str + 1;
32 if (cp[2] == 0)
33 return cp - str + 2;
34 if (cp[3] == 0)
35 return cp - str + 3;
36 }
37 }
38 }
3. 源碼剖析
上面給出的C語言實作雖然不算特别複雜，但也值得花點時間來弄清楚，先看9-14行：
for (char_ptr = str; ((ulong)char_ptr & (sizeof(ulong) - 1)) != 0; ++char_ptr) {
if (*char_ptr == '\0')
return char_ptr - str;
}
上面的代碼實作了資料對齊，如果在對齊之前就遇到'\0'則可以直接return char_ptr - str;
第16行将longword_ptr指向資料對齊後的首位址
longword_ptr = (ulong*)char_ptr;
第18行給magic_bits指派(在後面會解釋這個值的意義)
magic_bits = 0x7efefeffL;
第22行讀入一個WORD到longword并将longword_ptr指向下一個WORD
longword = *longword_ptr++;
第24行的if語句是整個算法的核心，該語句判斷22行讀入的WORD中是否有為0的位元組
if ((((longword + magic_bits) ^ ~longword) & ~magic_bits) != 0)
if語句中的計算可以分為如下3步：
(1) longword + magic_bits
其中magic_bits的二進制表示如下：
b3 b2 b1 b0
31------------------------------->0
magic_bits: 01111110 11111110 11111110 11111111
magic_bits中的31,24,16,8這些bits都為0(零)，我們把這幾個bits稱為holes，注意在每個byte的左邊都有一個hole。
(2)檢測0位元組：
如果longword 中有一個位元組的所有bit都為0，則進行加法後，從這個位元組的右邊的位元組傳遞來的進位都會落到這個位元組的最低位所在的hole上，而從這個位元組的最高位則永遠不會産生向左邊位元組的hole的進位。則這個位元組左邊的hole在進行加法後不會改變，由此可以檢測出0位元組；
相反，如果longword中所有位元組都不為0，則每個位元組中至少有1位為1，進行加法後所有的hole都會被改變。
為了便于了解，請看下面的例子：
b3 b2 b1 b0
31------------------------------->0
longword: XXXXXXXX XXXXXXXX 00000000 XXXXXXXX
+ magic_bits: 01111110 11111110 11111110 11111111
上面longword中的b1為0，X可能為0也可能為1。因為b1的所有bit都為0，而從b0傳遞過來的進位隻可能是0或1，很顯然b1永遠也不會産生進位，是以加法後longword的第16 bit這個hole不會變。
(2) ^ ~longword
這一步取出加法後longword中所有未改變的bit。
使特定位的值取反 (mask中特定位置1，其它位為0 s=s^mask)
(3) & ~magic_bits
最後取出longword中未改變的hole，如果有任何hole未改變則說明longword中有為0的位元組。
（按位與運算：取某數中指定位 (mask中特定位置1，其它位為0，s=s&mask)）
根據上面的描述，如果longword中有為0的位元組，則if中的表達式結果為非0，否則為0。
NOTE：
如果b3為10000000，則進行加法後第31 bit這個hole不會變，這說明我們無法檢測出b3為10000000的所有WORD。值得慶幸的是用于strlen的字元串都是ASCII标準字元，其值在0-127之間，這意味着每一個位元組的第一個bit都為0。是以上面的算法是安全的。
一旦檢測出longword中有為0的位元組，後面的代碼隻需要找到第一個為0的位元組并傳回相應的長度就OK：
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;
4. 另一種實作
1 size_t strlen_d(const char *str) {
2
3 const char *char_ptr;
4 const ulong *longword_ptr;
5 register ulong longword, himagic, lomagic;
6
7 for (char_ptr = str; ((ulong)char_ptr
8 & (sizeof(ulong) - 1)) != 0;
9 ++char_ptr) {
10 if (*char_ptr == '\0')
11 return char_ptr - str;
12 }
13
14 longword_ptr = (ulong*)char_ptr;
15
16 himagic = 0x80808080L;
17 lomagic = 0x01010101L;
18
19 while (1) {
20
21 longword = *longword_ptr++;
22
23 if (((longword - lomagic) & himagic) != 0) {
24
25 const char *cp = (const char*)(longword_ptr - 1);
26
27 if (cp[0] == 0)
28 return cp - str;
29 if (cp[1] == 0)
30 return cp - str + 1;
31 if (cp[2] == 0)
32 return cp - str + 2;
33 if (cp[3] == 0)
34 return cp - str + 3;
35 }
36 }
37 }
上面的代碼與strlen_c基本一樣，不同的是：
magic_bits換成了himagic和lomagic
himagic = 0x80808080L;
lomagic = 0x01010101L;
以及 if語句變得比較簡單了
if (((longword - lomagic) & himagic) != 0)
if語句中的計算可以分為如下2步：
(1) longword - lomagic
himagic和lomagic的二進制表示如下：
b3 b2 b1 b0
31------------------------------->0
himagic: 10000000 10000000 10000000 10000000
lomagic: 00000001 00000001 00000001 00000001
在這種方法中假設所有字元都是ASCII标準字元，其值在0-127之間，是以longword總是如下形式：
b3 b2 b1 b0
31------------------------------->0
longword: 0XXXXXXX 0XXXXXXX 0XXXXXXX 0XXXXXXX
檢測0位元組：
如果longword 中有一個位元組的所有bit都為0，則進行減法後，這個位元組的最高位一定會從0變為1；相反，如果longword中所有位元組都不為0，則每個位元組中至少有1位為1，進行減法後這個位元組的最高位依然為0。
(2) & himagic
這一步取出每個位元組最高位的1，如果有任意位元組最高位為1則說明longword中有為0的位元組。
根據上面的描述，如果longword中有為0的位元組，則if中的表達式結果為非0，否則為0。
5. 彙編實作
VC CRT的彙編實作與前面strlen_c算法類似
1 page ,132
2 title strlen - return the length of a null-terminated string
3 ;***
4 ;strlen.asm - contains strlen() routine
5 ;
6 ; Copyright (c) Microsoft Corporation. All rights reserved.
7 ;
8 ;Purpose:
9 ; strlen returns the length of a null-terminated string,
10 ; not including the null byte itself.
11 ;
12 ;*******************************************************************************
13
14 .xlist
15 include cruntime.inc
16 .list
17
18 page
19 ;***
20 ;strlen - return the length of a null-terminated string
21 ;
22 ;Purpose:
23 ; Finds the length in bytes of the given string, not including
24 ; the final null character.
25 ;
26 ; Algorithm:
27 ; int strlen (const char * str)
28 ; {
29 ; int length = 0;
30 ;
31 ; while( *str++ )
32 ; ++length;
33 ;
34 ; return( length );
35 ; }
36 ;
37 ;Entry:
38 ; const char * str - string whose length is to be computed
39 ;
40 ;Exit:
41 ; EAX = length of the string "str", exclusive of the final null byte
42 ;
43 ;Uses:
44 ; EAX, ECX, EDX
45 ;
46 ;Exceptions:
47 ;
48 ;*******************************************************************************
49
50 CODESEG
51
52 public strlen
53
54 strlen proc \
55 buf:ptr byte
56
57 OPTION PROLOGUE:NONE, EPILOGUE:NONE
58
59 .FPO ( 0, 1, 0, 0, 0, 0 )
60
61 string equ [esp + 4]
62
63 mov ecx,string ; ecx -> string
64 test ecx,3 ; test if string is aligned on 32 bits
65 je short main_loop
66
67 str_misaligned:
68 ; simple byte loop until string is aligned
69 mov al,byte ptr [ecx]
70 add ecx,1
71 test al,al
72 je short byte_3
73 test ecx,3
74 jne short str_misaligned
75
76 add eax,dword ptr 0 ; 5 byte nop to align label below
77
78 align 16 ; should be redundant
79
80 main_loop:
81 mov eax,dword ptr [ecx] ; read 4 bytes
82 mov edx,7efefeffh
83 add edx,eax
84 xor eax,-1
85 xor eax,edx
86 add ecx,4
87 test eax,81010100h
88 je short main_loop
89 ; found zero byte in the loop
90 mov eax,[ecx - 4]
91 test al,al ; is it byte 0
92 je short byte_0
93 test ah,ah ; is it byte 1
94 je short byte_1
95 test eax,00ff0000h ; is it byte 2
96 je short byte_2
97 test eax,0ff000000h ; is it byte 3
98 je short byte_3
99 jmp short main_loop ; taken if bits 24-30 are clear and bit
100 ; 31 is set
101
102 byte_3:
103 lea eax,[ecx - 1]
104 mov ecx,string
105 sub eax,ecx
106 ret
107 byte_2:
108 lea eax,[ecx - 2]
109 mov ecx,string
110 sub eax,ecx
111 ret
112 byte_1:
113 lea eax,[ecx - 3]
114 mov ecx,string
115 sub eax,ecx
116 ret
117 byte_0:
118 lea eax,[ecx - 4]
119 mov ecx,string
120 sub eax,ecx
121 ret
122
123 strlen endp
124
125 end
6. 測試結果
為了對上述各種實作的效率有一個大概的認識，我在VC8和GCC下分别進行了測試，測試時均采用預設優化方式。下面是在GCC下運作幾百萬次後的結果(在VC8下的運作結果與此相似)：
strlen_a
--------------------------------------------------
1: 515 ticks 0.515 seconds
2: 375 ticks 0.375 seconds
3: 375 ticks 0.375 seconds
4: 375 ticks 0.375 seconds
5: 375 ticks 0.375 seconds
total: 2015 ticks 2.015 seconds
average: 403 ticks 0.403 seconds
--------------------------------------------------
strlen_b
--------------------------------------------------
1: 360 ticks 0.36 seconds
2: 390 ticks 0.39 seconds
3: 375 ticks 0.375 seconds
4: 360 ticks 0.36 seconds
5: 375 ticks 0.375 seconds
total: 1860 ticks 1.86 seconds
average: 372 ticks 0.372 seconds
--------------------------------------------------
strlen_c
--------------------------------------------------
1: 187 ticks 0.187 seconds
2: 172 ticks 0.172 seconds
3: 187 ticks 0.187 seconds
4: 187 ticks 0.187 seconds
5: 188 ticks 0.188 seconds
total: 921 ticks 0.921 seconds
average: 184 ticks 0.1842 seconds
--------------------------------------------------
strlen_d
--------------------------------------------------
1: 172 ticks 0.172 seconds
2: 187 ticks 0.187 seconds
3: 172 ticks 0.172 seconds
4: 187 ticks 0.187 seconds
5: 188 ticks 0.188 seconds
total: 906 ticks 0.906 seconds
average: 181 ticks 0.1812 seconds
--------------------------------------------------
strlen
--------------------------------------------------
1: 187 ticks 0.187 seconds
2: 172 ticks 0.172 seconds
3: 188 ticks 0.188 seconds
4: 172 ticks 0.172 seconds
5: 187 ticks 0.187 seconds
total: 906 ticks 0.906 seconds
average: 181 ticks 0.1812 seconds
--------------------------------------------------
posted on 2007-10-12 13:19螞蟻終結者閱讀(14436)評論(34) 編輯 收藏引用所屬分類:The Annotated CRT Sources
(2) ^ ~longword
這一步取出加法後longword中所有未改變的bit。
======================================
這個什麼意思？ 回複 更多評論
# re: strlen源碼剖析 2007-09-27 08:19 螞蟻終結者
可能我說的不夠清楚，看下面的例子：
b3 b2 b1 b0
31------------------------------->0
longword: 00001001 00011000 00000000 00001100
+ magic_bits: 01111110 11111110 11111110 11111111
sum: 10001000 0001011011111111 00001011
^ ~longword: 11110110 1110011111111111 11110011
a: 01111110 1111000100000000 11111000
& ~magic_bits: 10000001 00000001 00000001 00000000
result: 00000000 0000000100000000 00000000
sum = longword + magic_bits;
a = sum ^ ~longword;
即用sum與longword逐位比較，如果有某個位相同，就說這個位在加法後未改變，這樣在a中為1的位就是未改變的。
result = a & ~magic_bits;
得到未改變的hole位，從上例可以看出第16 bit這個hole加法後未改變，這樣就檢測出了0位元組。
# re: strlen源碼剖析 2007-09-27 08:52 Yong Sun
隻能檢測0~127，是個問題，最好能相容0~255，有部分制表符和擴充字元位于這個區域。 回複 更多評論
# re: strlen源碼剖析 2007-09-27 09:06 螞蟻終結者
實際上0~255都能檢測出來的：
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;
如果上面的語句執行完還沒有return，則會繼續下一次循環，這樣還是能檢測到在if語句中漏掉的128~255，隻不過效率上會有所損失。如果要檢測0~255之間的字元，strlen_c比strlen_d要好。因為strlen_c隻會漏掉這樣的WORD：
10000000 XXXXXXXX XXXXXXXX XXXXXXXX
回複 更多評論
# re: strlen源碼剖析 2007-09-27 09:23 k120
為了便于下面的讨論，這裡假設所用的計算機為32位，即一個WORD為4個位元組?呵呵,筆誤吧?
回複 更多評論
# re: strlen源碼剖析 2007-09-27 09:35 螞蟻終結者
Sorry，我不該用WORD這個單詞。我說的WORD在這裡表示計算機中的一個字長，不是一般為2個位元組的WORD類型。
回複 更多評論
# re: strlen源碼剖析 2007-09-27 10:32 Yong Sun
另外，是否有endian的問題呢？ 回複 更多評論
# re: strlen源碼剖析 2007-09-27 10:39 Yong Sun
想了想，應該沒有，呵呵 回複 更多評論
# re: strlen源碼剖析 2007-09-27 11:16 螞蟻終結者
c語言的版本不會有endian的問題，如果用彙編就需要注意了。
假設有4個連續的位元組abcd，現在要找出其中的第一個0位元組：
1. 在PowerPC這種big-endian的計算機上，将這4個位元組讀到寄存器中依然是
abcd，從左到右找到最左邊的0位元組就OK了。
2. 在X86這種little-endian的計算機上，将這4個位元組讀到寄存器中就會變成
dcba，這就需要從右到左找到最右邊的0位元組。
可以看出，上面VC的彙編實作是針對X86計算機的。
回複 更多評論
# re: strlen源碼剖析 2007-09-27 12:51 ∑x
如果能做到這樣的分析，還有什麼能學不會?! 回複 更多評論
# re: strlen源碼剖析 2007-10-12 16:36 Minidx全文檢索
幾天前看過的文章怎麼又跑前面來了？！ 回複 更多評論
# re: strlen源碼剖析 2007-11-02 13:04 really green
for (char_ptr = str; ((ulong)char_ptr
& (sizeof(ulong) - 1)) != 0 ;
++ char_ptr) {
if (*char_ptr == '\0' )
return char_ptr - str;
}
我比較菜，這裡就看不明白：
((ulong)char_ptr& (sizeof(ulong) - 1)) != 0 ;
(ulong)char_ptr 這個轉換把一個 char *轉成 ulong會發生什麼事情？ 回複 更多評論
# re: strlen源碼剖析 2007-11-02 19:28 really green
想了想這個問題問得挺幼稚，我了解 (ulong)char_ptr應該得到一個ulong的值，這個值就是指針char_ptr的值。
回複 更多評論
# re: strlen源碼剖析 2007-11-04 09:35 螞蟻終結者
you gotta it! 回複 更多評論
# re: strlen源碼剖析 2007-12-04 05:39 福福
如果有中文字元，這個是不是有問題
if (((longword - lomagic) & himagic) != 0) 回複 更多評論
# re: strlen源碼剖析 2007-12-05 19:39 螞蟻終結者
中文字元應該用wcslen才對，strlen是用來處理單位元組字元串的。
較長的描述請看MSDN：
However, strlen interprets the string as a single-byte character string, so its return value is always equal to the number of bytes, even if the string contains multibyte characters. wcslen is a wide-character version of strlen; the argument of wcslen is a wide-character string and the count of characters is in wide (two-byte) characters.
回複 更多評論
# re: strlen源碼剖析 2007-12-27 14:01 Fox
幾年沒動過彙編了，看了代碼，有種耳目一新的感覺～～～～～～～～ 回複 更多評論
# re: strlen源碼剖析 2007-12-31 17:44 Sunky
感謝部落客的精彩剖析。
感覺到我不會的東西太多了
由此堅定了我看GNU C的決心
謝謝 回複 更多評論
# re: strlen源碼剖析 2008-09-07 16:11 star
部落客的文章允許轉載麼？
昨天看glibc裡的注釋覺得雲裡霧裡
今天看了部落客的文章，突然覺得豁然開朗啊 ;-)
還有想問一個問題 glibc裡是這樣處理64位的
if (sizeof (longword) > 4)
{
magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
himagic = ((himagic << 16) << 16) | himagic;
lomagic = ((lomagic << 16) << 16) | lomagic;
}
為什麼不一次就移32位呢？ 回複 更多評論
# re: strlen源碼剖析 2008-09-07 19:54 螞蟻終結者
@star
歡迎轉載，轉載當然是沒有問題的，畢竟寫文章就是能讓更多的人看到！
為什麼不一次就移32位呢？
我也不太清楚，可能就其中注釋所說：
隻是為了避免warn吧呵呵！ 回複 更多評論
# re: strlen源碼剖析 2008-11-07 11:42 test
似乎CRT庫的這種寫法有點越界通路的意思，呵呵。 回複 更多評論
# re: strlen源碼剖析 2009-03-18 17:08 123
@福福
strlen算法在進行中文時不會出問題，關鍵點在後面的if(cp[?]==0)。
不過進行中文時效率會跟最簡單的strlen一樣。 回複 更多評論
# re: strlen源碼剖析 2009-04-29 14:32 uestc
分析得很清楚，寫得也很詳細，贊一個。 回複 更多評論
# re: strlen源碼剖析 2009-06-05 14:06 宋兵乙
for (char_ptr = str; ((ulong)char_ptr
& (sizeof(ulong) - 1)) != 0 ;
++ char_ptr) {
if (*char_ptr == '\0' )
return char_ptr - str;
}
如上的代碼我看不懂了，我的分析如下，麻煩各位高手指出錯誤。
sizeof(ulong)-1等于3，也就是二進制的0000 0011，于是想要跳出for循環，隻需char_ptr的最後兩位是0即可。而每次for循環時，char_ptr執行了++操作，由于char_ptr是指向char的指針，是以每次++應該是增加一個char的長度就是8。表現在二進制上就是倒數第4位增加1，而後兩位是不會變化的。故得出結論若char_ptr的初始值不滿足最後兩位是0，那for就永遠是死循環了。
求各位指出上述論證錯誤在哪。另外，我沒明白此例中記憶體對齊到滿足哪種條件才能提高代碼效率。 回複 更多評論
# re: strlen源碼剖析 2009-06-08 11:51 螞蟻終結者
@宋兵乙
“由于char_ptr是指向char的指針，是以每次++應該是增加一個char的長度就是8”
看來你對指針運算還不太了解，建議好好複習一下指針部分。
授人魚不如授人漁呵呵 回複 更多評論
# re: strlen源碼剖析 2009-10-29 11:31 似水之心
學習，謝謝分享 回複 更多評論
# re: strlen源碼剖析 2010-07-31 20:38 hoodlum1980
不錯。我今天反彙編看到strlen的彙編代碼一直覺得很奇怪，
沒搞懂這幾句話在幹什麼。。。看了這篇文章很有幫助。
[S1] 01111110 11111110 11111110 11111111
![筆試面試題目：滑動視窗(二)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)