還記得初學C的時候，對于字符串操作一類函數(shù)的記憶顯得尤為深刻，各種考試會考strlen、strlen等函數(shù)的實現(xiàn)，到了畢業(yè)找工作，很多公司的筆試題里，也包含有strlen、strcpy等函數(shù)的實現(xiàn)?？梢娮址僮黝惡瘮?shù)是受到了老師和公司出題者的青睞啊。那么本文就來研究一下strlen這個函數(shù)吧！

可能你這時已經(jīng)在BS我了，心想就這么個東西，還需要研究的么。我能瞬間完成，于是你寫下了這段代碼：

[cpp]view plaincopy

intstrlen(constchar*str)

{

intlength=0;

while(*str++)

++length;

return(length);

}

哇！你還真快，真的瞬間寫下了這個簡潔精煉的strlen，不錯，你的C語言考題過關(guān)了，公司筆試也過了，值得恭喜。但是，似乎這么快就解決了問題，那本文要怎么進行下去呢？那就先分析一下你瞬間秒殺出來的這個strlen吧，她簡直太完美了，和MS的工程師們寫得如出一轍，總體看下來也就幾行代碼完事，那么，為啥這么幾行就能解決問題？還有沒有更優(yōu)的方案？你靈機一動，又瞬間想出一種：

[cpp]view plaincopy

intstrlen(constchar*str)

{

constchar*ptr=str;

while(*str++)

;

return(str-ptr-1);

}

所謂代碼簡短不一定就是最優(yōu)的，當然這里不能扯到軟件工程里去了，我們可以看出這兩種實現(xiàn)，str++是逐字節(jié)向后移動的，時間復雜度都是O(n)，所以這個strlen可以很簡單的完成，那么更優(yōu)的方案是什么呢？試想，如果能夠幾個字節(jié)一跳，不是能夠更快的完成求長度，不就降低了復雜度？先拭目以待吧。

本系列是為了剖析crt庫中intel模塊下的那些函數(shù)的，那么我們?nèi)フ艺夷抢锩嬗袥]有strlen的實現(xiàn)，呀！居然找到了，它就位于VC/crt/src/intel/strlen.asm里。打開看看，咦，有點暈。不過最亮眼的就是，在前面的注釋里，MS的工程師們寫了個“注釋版”的strlen，與你前面實現(xiàn)的strlen簡直是一摸一樣的?？墒牵亲⑨尠娴?，不會編譯進程序運行。那么繼續(xù)看下面的匯編實現(xiàn)，代碼如下：

[cpp]view plaincopy

CODESEG

publicstrlen

strlenproc\

buf:ptrbyte

OPTIONPROLOGUE:NONE,EPILOGUE:NONE

.FPO(0,1,0,0,0,0)

stringequ[esp+4]

movecx,string;ecx->string

testecx,3;testifstringisalignedon32bits

jeshortmain_loop

str_misaligned:

;simplebyteloopuntilstringisaligned

moval,byteptr[ecx]

addecx,1

testal,al

jeshortbyte_3

testecx,3

jneshortstr_misaligned

addeax,dwordptr0;5bytenoptoalignlabelbelow

align16;shouldberedundant

main_loop:

moveax,dwordptr[ecx];read4bytes

movedx,7efefeffh

addedx,eax

xoreax,-1

xoreax,edx

addecx,4

testeax,81010100h

jeshortmain_loop

;foundzerobyteintheloop

moveax,[ecx-4]

testal,al;isitbyte0

jeshortbyte_0

testah,ah;isitbyte1

jeshortbyte_1

testeax,00ff0000h;isitbyte2

jeshortbyte_2

testeax,0ff000000h;isitbyte3

jeshortbyte_3

jmpshortmain_loop;takenifbits24-30areclearandbit

;31isset

byte_3:

leaeax,[ecx-1]

movecx,string

subeax,ecx

ret

byte_2:

leaeax,[ecx-2]

movecx,string

subeax,ecx

ret

byte_1:

leaeax,[ecx-3]

movecx,string

subeax,ecx

ret

byte_0:

leaeax,[ecx-4]

movecx,string

subeax,ecx

ret

strlenendp

end

只看主體部分的匯編代碼，我們進行逐句研究。

首先，是聲明了strlen的公共符號，以及strlen的函數(shù)參數(shù)等聲明，OPTION一句代碼是為了讓匯編程序不生成開始代碼和結(jié)束代碼（這個可以查閱相關(guān)文獻資料，這里不進行詳細解釋），下一句.FPO，是與堆棧指針省略（FramePointOmission）相關(guān)的，在MSDN里面的解釋如下：

FPO (cdwLocals, cdwParams, cbProlog, cbRegs, fUseBP, cbFrame)

cdwLocals：Number of local variables, an unsigned 32 bit value.

cdwParams：Size of the parameters, an unsigned 16 bit value.

cbProlog：Number of bytes in the function prolog code, an unsigned 8 bit value.

cbRegs：Number of bytes in the function prolog code, an unsigned 8 bit value.

fUseBP：Indicates whether the EBP register has been allocated. either 0 or 1.

cbFrame：Indicates the frame type.在這里只需要關(guān)注第二個參數(shù)，它為1，表示有一個參數(shù)。strlen本身也就是一個參數(shù)。其他參數(shù)，看上面的英文注釋應該很簡單了，這里不作解釋。你也可以點擊這里查閱。

繼續(xù)向下，關(guān)注這三句：

[cpp]view plaincopy

stringequ[esp+4]

movecx,string;ecx->string

testecx,3;testifstringisalignedon32bits

jeshortmain_loop

第一句，esp+4這個就簡單了，在《【動態(tài)分配棧內(nèi)存】之a(chǎn)lloca內(nèi)幕》一文中有詳細的解釋，這里只做簡單解釋，esp+4正是strlen參數(shù)的地址，這個地址屬于棧內(nèi)存空間，再[esp+4]取值，則得到strlen參數(shù)指向的地址（strlen的參數(shù)為const char*）。假如代碼是這樣的：

[cpp]view plaincopy

charszName[]="masefee";

strlen(szName);

那么，上面的[esp+4]所得的地址值就是szName數(shù)組的首地址。前面的string equ [esp+4]并不會產(chǎn)生任何代碼，string只相當于是一個宏定義（至于為什么需要這個string，到后面就知道了，你要相信，這一切都是有理有據(jù)的，這也正是研究的樂趣之一），于是mov ecx,string就等價于mov ecx,[esp+4]，這句是直接將參數(shù)指向的地址值賦值給ecx寄存器，ecx此刻就是字符串的首地址了。再下一句，test ecx,3，這句是測試ecx存放的這個地址值是不是4字節(jié)（32bits）對齊的，如果是，則跳轉(zhuǎn)到main_loop進行執(zhí)行，否則，則繼續(xù)向下。我們先看未對齊的情況，自然就是緊接著的str_misaligned節(jié)：

[cpp]view plaincopy

str_misaligned:

moval,byteptr[ecx]

addecx,1

testal,al

jeshortbyte_3

testecx,3

jneshortstr_misaligned

addeax,dwordptr0;5bytenoptoalignlabelbelow

align16;shouldberedundant

先不看這段代碼，我們先推斷一下，前面說到了不對齊的情況，一般對于操作系統(tǒng)來說，對于內(nèi)存的分配總是會對齊的，所以這里strlen一進來就檢查是否對齊，那么不對齊的情況是什么時候呢？如下：

[cpp]view plaincopy

charszName[]="masefee";

char*p=szName;

p++;//使p向后移動一個字節(jié)，本身假設以4字節(jié)對齊，移動之后就不再4字節(jié)對齊了

strlen(p);

當然，這里是我故意寫成這樣的，在實際中還有其他的情況，例如一個結(jié)構(gòu)體里面有一個字符串，這個結(jié)構(gòu)體是一字節(jié)對齊的，字符串的位置不確定時，那么字符串的首地址也就可能不是4字節(jié)對齊的。繼續(xù)前面的推斷，如果不對齊時，就會先讓其對齊，然后再繼續(xù)求長度，如果在讓其重新對齊的過程中，發(fā)現(xiàn)了結(jié)束符則停止，立刻返回長度。好了，推斷完畢。再看上面的匯編代碼，果然是這樣干的。

先是向ecx指向的內(nèi)存里取一個字節(jié)到al里，然后ecx加1向后移動一個字節(jié)，再判斷al是否為0，如果為0則跳轉(zhuǎn)到byte_3節(jié)，否則繼續(xù)測試ecx當前的地址值是否已經(jīng)對齊，未對齊則繼續(xù)取一個字節(jié)的值，再加ecx，直到對齊或者碰到結(jié)束符。當沒有碰到結(jié)束符且ecx存放的地址值已經(jīng)對齊時，下面一句add eax,dword ptr 0，后面有注釋，表明這句代碼無實際意義。align 16和前面的add共同作用是為了將代碼以16字節(jié)對齊，后面的main_loop就是16字節(jié)對齊開始的地址了（又一次感受到了MS工程師們的聰明之處，考慮很周到）。

接下來該進入到main_loop了，很明顯這是主循環(huán)的意思，也是strlen的核心。這里用了很巧妙的算法，先分析前半部分代碼：

[cpp]view plaincopy

moveax,dwordptr[ecx];read4bytes

movedx,7efefeffh

addedx,eax

xoreax,-1

xoreax,edx

addecx,4

testeax,81010100h

jeshortmain_loop

首先，第一句向ecx所指向的內(nèi)存里讀取了4個字節(jié)到eax中，很明顯是想4個字節(jié)處理一次。然后再看第二句，將edx賦值為0x7efefeff，這個數(shù)字看起來有什么規(guī)律，有什么用呢？來看看這個數(shù)字的二進制：

01111110 11111110 11111110 11111111 看看這個數(shù)字的二進制，我們注意到有4個紅色的0，他們都有一個特征，就是在每個字節(jié)的左邊，這有什么用？再聯(lián)想一下，在左邊，什么時候會被修改？很明顯，當右邊有進位時，會修改到這個0，或者這幾個0的位置與另外一個數(shù)相運算時會被改變。先不忙分析，先看下一句add edx,eax，這一句是將從ecx指向的內(nèi)存里取出來的4字節(jié)整數(shù)與0x7efefeff相加，奇怪了，這樣相加有什么意義呢？仔細一想，驚訝了，原理這樣相加就能知道這個4字節(jié)整數(shù)中哪個或哪幾個字節(jié)為0了。為0則達到了strlen的目的，strlen就是為了找到結(jié)束符，然后返回長度。 再看這個加法的過程，加法的目的就是為了讓上面4個紅色的0中某些0被改變，如果有哪個0沒有改變并且最高位的0未改變，那說明這4個字節(jié)中存在某個或某些字節(jié)為0。這幾個紅色的0可以被稱為是洞(hole)，而且也很形象。舉個例子：

byte3 byte2 byte1byte0

???????? 00000000 ???????? ???????? // eax

+ 01111110 11111110 11111110 11111111 // edx = 0x7efefeff 上面是假設兩個數(shù)相加，問號代表0或者1，但整個字節(jié)不全0，eax的byte2為全0，與edx的byte2相加，不管byte1和byte0怎么相加，最后進位都只能最多為1，那么byte3的最低位永遠不可能改變。以此類推，如果byte0為0，byte1的最低位永遠不可能改變，只有byte0有1位不為0，byte1的最低位都會收到進位，這也就是為什么edx的byte0為0xff了。所有byte都靠進位進行判斷，只要右邊沒有進位則必然存在byte為0。

繼續(xù)向下看，xor eax,-1則是將eax（從ecx指向的內(nèi)存里取得的4字節(jié)）取反。然后xor eax,edx，這句的意圖是取出執(zhí)行前面的加法之后的值（add edx,eax后edx的值）中未改變的那些位，繼續(xù)，add ecx,4則表示將ecx向后移動4個字節(jié)，方便下次進行運算。再之后，一句test eax,81010100h，這個0x81010100就是前面0x7efefeff取反，也就是幾個hole的位置為1。再與前面取出來的加法之后的值（add edx,eax后edx的值）中未改變的那些位相比較：如果結(jié)果為0，則表示加法之后的值（add edx,eax后edx的值）與原始值eax（取出來的原始字符串的4個字節(jié)）作比較，并且相對于0x7efefeff中的4個0（hold）的位置上，每一個0的位置（hole）都被改變了（或者相對于0x81010100中4個1（同樣是hold的位置）的位置上，每一個1的位置（hole）都被改變了）；如果不為0，同理比較，則發(fā)現(xiàn)有字節(jié)為0。由此看來，與0x81010100進行test就是為了判斷從字符串取出來的4個字節(jié)與0x7efefeff相加之后的值的那幾個hold的位置相對于原始的4個字節(jié)中的那幾個hole的位置里，哪些hole位置的位是被改變了的。如果每個hole的位置都改變了則test結(jié)果為0，表示沒有字節(jié)為0，否則，則表示有字節(jié)為0。

當發(fā)現(xiàn)有字節(jié)為0時，則應該對取出來的4字節(jié)進行逐字節(jié)判斷哪個字節(jié)為0了，如下：

[cpp]view plaincopy

moveax,[ecx-4]

testal,al;isitbyte0

jeshortbyte_0

testah,ah;isitbyte1

jeshortbyte_1

testeax,00ff0000h;isitbyte2

jeshortbyte_2

testeax,0ff000000h;isitbyte3

jeshortbyte_3

jmpshortmain_loop;takenifbits24-30areclearandbit

;31isset

如上，第一句[ecx-4]的原因是因為ecx在前面加了4，因此要減4重新去開始的4字節(jié)，然后逐字節(jié)判斷哪個字節(jié)為0，代碼很簡單，這里就不詳細說明了。這里如果發(fā)現(xiàn)了某個字節(jié)為0，則跳轉(zhuǎn)到相應的尾部節(jié)中，如下：

[cpp]view plaincopy

byte_3:

leaeax,[ecx-1]

movecx,string

subeax,ecx

ret

byte_2:

leaeax,[ecx-2]

movecx,string

subeax,ecx

ret

byte_1:

leaeax,[ecx-3]

movecx,string

subeax,ecx

ret

byte_0:

leaeax,[ecx-4]

movecx,string

subeax,ecx

ret

以byte_3為例，也就是取出來的四個字節(jié)中，第4個字節(jié)為0，前3個字節(jié)不為0，于是eax就應該等于ecx-1，然后將ecx重新賦值為字符串的首地址（到這里你應該明白了為啥要有string這個宏了吧）。最后sub eax,ecx則直接獲得了字符串的長度。然后ret返回到上層。整個strlen就結(jié)束了。

通過前面的分析，我們已經(jīng)知道了strlen的原理，并且更深刻領(lǐng)略了算法的美妙。我們可以將這個匯編版本的strlen翻譯成C語言版，如下：

[cpp]view plaincopy

size_tstrlen(constchar*str)

{

constchar*ptr=str;

for(;((int)ptr&0x03)!=0;++ptr)

{

if(*ptr=='\0')

returnptr-str;

}

unsignedint*ptr_d=(unsignedint*)ptr;

unsignedintmagic=0x7efefeff;

while(true)

{

unsignedintbits32=*ptr_d++;

if((((bits32+magic)^(bits32^-1))&~magic)!=0)//bits32^-1等價于~bits32

{

ptr=(constchar*)(ptr_d-1);

if(ptr[0]==0)

returnptr-str;

if(ptr[1]==0)

returnptr-str+1;

if(ptr[2]==0)

returnptr-str+2;

if(ptr[3]==0)

returnptr-str+3;

}

}

}

好了，strlen就差不多分析完了，最后面的C語言版本還可以變化，例如根據(jù)字符的編碼集，進行特殊化。不過一般是不需要的，通用一些更好。我做了一個測試，將本文開頭的C語言版本、最后的C語言版本以及crt的匯編版本的性能進行對比，求相同字符串的長度，求10000000次，開啟O2優(yōu)化，三者平均耗時為：

普通C語言版本：723毫秒

后面的翻譯C版本：315毫秒

CRT匯編版本：218毫秒 可見，后兩者的性能有一定的提升，這里需要說明一點，crt的strlen函數(shù)屬于intrinsic函數(shù)，所謂intrinsic函數(shù)，可以稱作為內(nèi)部函數(shù)，這與inline函數(shù)有點類似，但是不是inline之意。inline不是強制的，在編譯器編譯時也是有所區(qū)別的。intrinsic函數(shù)相當于是在編譯器在編譯時根據(jù)上下文等情況來確定是否將函數(shù)代碼進行匯編級內(nèi)聯(lián)，在內(nèi)聯(lián)的同時進行優(yōu)化，由此既省去了函數(shù)調(diào)用開銷，同時優(yōu)化也更直接明了。編譯器熟悉intrinsic函數(shù)的內(nèi)在功能，很多時候又稱為內(nèi)建函數(shù)，因此編譯器可以更好的整合及優(yōu)化，目的只有一個，在特定的環(huán)境下，選擇最優(yōu)的方案。就拿strlen來說，例如這樣一段代碼：

[cpp]view plaincopy

intmain(intargc,char**argv)

{

intlen=strlen(argv[0]);

printf("%d",len);

return0;

}

在debug下禁用優(yōu)化、release下禁用優(yōu)化或release下最小化大小(/O1)時，可以強制開啟intrinsic內(nèi)部函數(shù)選項(/Oi)，這樣開啟之后，上面的strlen函數(shù)將不再調(diào)用crt的匯編版本函數(shù)，而是直接內(nèi)嵌到main函數(shù)代碼里，如下（debug或release下禁用優(yōu)化并開啟內(nèi)部函數(shù)(/Oi)）：

[cpp]view plaincopy

intlen=strlen(argv[0]);

0042D8DEmoveax,dwordptr[argv]

0042D8E1movecx,dwordptr[eax]

0042D8E3movdwordptr[ebp-0D0h],ecx

0042D8E9movedx,dwordptr[ebp-0D0h]

0042D8EFaddedx,1

0042D8F2movdwordptr[ebp-0D4h],edx

0042D8F8moveax,dwordptr[ebp-0D0h]<------???

0042D8FEmovcl,byteptr[eax]|

0042D900movbyteptr[ebp-0D5h],cl|//逐字節(jié)計算

0042D906adddwordptr[ebp-0D0h],1|

0042D90Dcmpbyteptr[ebp-0D5h],0|

0042D914jnemain+38h(42D8F8h)//---------

0042D916movedx,dwordptr[ebp-0D0h]

0042D91Csubedx,dwordptr[ebp-0D4h]

0042D922movdwordptr[ebp-0DCh],edx

0042D928moveax,dwordptr[ebp-0DCh]

0042D92Emovdwordptr[len],eax

如果在release下開啟最小化大小(/O1)并開啟內(nèi)部函數(shù)(/Oi)時，編譯后代碼如下：

[cpp]view plaincopy

intlen=strlen(argv[0]);

00401000moveax,dwordptr[esp+8]

00401004moveax,dwordptr[eax]

00401006leaedx,[eax+1]

00401009movcl,byteptr[eax]<------??

0040100Binceax|//逐字節(jié)計算

0040100Ctestcl,cl|

0040100Ejnemain+9(401009h)-------

00401010subeax,edx

代碼簡潔多了，同樣沒有函數(shù)調(diào)用開銷（其實，你會驚訝的發(fā)現(xiàn)，這幾句代碼正是本文開篇第二個C語言版的strlen的反匯編代碼，當然是經(jīng)過優(yōu)化后的代碼，這里省去了調(diào)用開銷。其實，本文前面開頭的兩個strlen，在開啟較高優(yōu)化級別時，編譯器也會將這兩個函數(shù)進行優(yōu)化內(nèi)嵌，也就與intrinsic函數(shù)一致了。這說明一點，編譯器是人性化的，只要能夠滿足優(yōu)化的條件，就會果斷進行優(yōu)化）。在開啟最小化大小(/O1)優(yōu)化并開啟內(nèi)部函數(shù)(/Oi)優(yōu)化與release下開啟最大化速度(/O2)或完全優(yōu)化(/Ox)時，產(chǎn)生的代碼是一致的。與release下開啟最大化速度(/O2)或完全優(yōu)化(/Ox)時，就算你不開啟內(nèi)部函數(shù)(/Oi)優(yōu)化，編譯器同樣會將strlen處理掉產(chǎn)生上面的代碼。這個跟優(yōu)化的級別有關(guān)，級別高了，自然就會更全面的優(yōu)化，不管你是否強制設置一些東西。也算是一個人性化設計吧。 要開啟某函數(shù)進行內(nèi)部函數(shù)優(yōu)化，可以通過代碼來開啟，如下：

[cpp]view plaincopy

#pragmaintrinsic(strlen)

有開啟，自然也有關(guān)閉，如下：

[cpp]view plaincopy

#pragmafunction(strlen)

強制將strlen的優(yōu)化關(guān)閉，這樣就算你是最大化速度(/O2)或完全優(yōu)化(/Ox)，照樣會調(diào)用crt的strlen函數(shù)。這兩者的具體詳細說明，請查閱MSDN，或點擊這里。

關(guān)于這個intrinsic pragma，MSDN有詳細準確的解釋，還是英文原文更能體會其本意：

Theintrinsicpragma tells the compiler that a function has known behavior. The compiler may call the function and not replace the function call with inlineinstructions, if it will result in better performance. .........

Programs that use intrinsic functions are faster because they do not have the overhead of function calls but may be larger due to the additional code generated.

對了，不要試圖用這兩個東西來強制開啟或關(guān)閉一個普通函數(shù)的(/Oi)優(yōu)化，所謂intrinsic，當然是編譯器內(nèi)定的一些函數(shù)，也算是做了一些細節(jié)上優(yōu)化的可選擇性吧。如果你不信我的，那你肯定會得到一個警告：

warning C4163: “xxxxx”: 不可用作內(nèi)部函數(shù).

對于intrinsic的相關(guān)優(yōu)化，編譯器處理得比較靈活，這代表它并不是強制性的，如果開啟SSE，編譯器還會考慮SSE優(yōu)化，在原理上，知道有這么回事就是了，本文的重點在于如何去挖掘和思考諸多細節(jié)。至于具體的內(nèi)定的函數(shù)有哪些，以及有哪些詳細說明，請查閱MSDN，或者點擊前面的鏈接。這里就不再累述了，已經(jīng)寫了這么長了。。

與此同時再一次感嘆MS的工程師們，細節(jié)做得很好。這也值得國內(nèi)IT行業(yè)浮躁環(huán)境下的coder們深思。