VC CRT庫中的strlen算法

VC中CRT庫的strlen算法淺析

最近在看《老碼識途》一書時论巍，看到其對于C運行時庫中的strlen函數的講解，詳細解釋了匯編實現的加速算法。為了加深理解又從網上參考了一些博文【揭秘VC CRT庫Intel模塊】-- strlen名惩，在仔細研究则吟，并融入自己的理解后舷丹，將其做一個記錄涮毫。

1.strlen的c語言實現

??首先，我們應該知道在C/C++中呢铆，0(并非字符“0”)標識著一個字符串的結束晦鞋，因此計算字符串的長度 length = 第一個0的位置 - 首字符的位置。如果讓我們自己寫一個strlen的算法，我們很容易就能寫出類似下面這個形式的函數悠垛。

size_t __cdecl strlen ( const char * str)
{
        const char *eos = str;
        while( *eos++ ) ;          //不為0就加1线定，查看下個字符是否為0
        return( eos - str - 1 );    //因為*eos = 0后，++操作使其移到下個字符确买，所以這里需要減1.
}

??在VS2017中斤讥，將上述代碼反匯編后，其匯編如下所示拇惋。針對每條語句我已經做了注釋周偎，可以看到剛好與c語言的邏輯吻合。

    const char *eos = str;
00BF42A8 8B 45 08             mov         eax,dword ptr [str] ;str指向的是字符串的首地址撑帖，將其指向的首地址賦值給eax
00BF42AB 89 45 F8             mov         dword ptr [eos],eax ;最終將字符串首地址保存局部變量eos指向的棧空間
    while (*eos++);          
00BF42AE 8B 45 F8             mov         eax,dword ptr [eos]  ;將eos指向的地址取出澳眷，賦值給eax
00BF42B1 8A 08                mov         cl,byte ptr [eax]  ;從eax指向的地址處胡嘿，取一個字符賦值給cl
00BF42B3 88 8D 33 FF FF FF    mov         byte ptr [ebp-0CDh],cl  ;將該字符保存在ebp-oxcdh的棧空間
00BF42B9 8B 55 F8             mov         edx,dword ptr [eos]  ;將eos指向的地址取出钳踊，賦值給ebx
00BF42BC 83 C2 01             add         edx,1  ;加1衷敌，指向下一個字符
00BF42BF 89 55 F8             mov         dword ptr [eos],edx  ;保存回eos指向的棧空間
00BF42C2 0F BE 85 33 FF FF FF movsx       eax,byte ptr [ebp-0CDh]  ;取回之前保存的字符
00BF42C9 85 C0                test        eax,eax  ;字符與自身做與操作
00BF42CB 74 02                je          strlen+4Fh (0BF42CFh)  ;如果該字符為0拓瞪，說明到了字符結尾缴罗，跳轉到return
00BF42CD EB DF                jmp         strlen+2Eh (0BF42AEh)  ;如果不等0，循環(huán)祭埂，繼續(xù)判斷下一個字符
    return(eos - str - 1);    
00BF42CF 8B 45 F8             mov         eax,dword ptr [eos]  
00BF42D2 2B 45 08             sub         eax,dword ptr [str]  ;eos處指向的地址-str首地址
00BF42D5 83 E8 01             sub         eax,1 ;再減1面氓，返回結果保存在eax中

2.CRT庫中strlen的匯編高效實現

??然而，因為strlen作為一個相當常用的函數蛆橡，如果其實現的算法速度更快舌界，那么其對整個系統(tǒng)的性能提升是比較可觀的。因此在CRT庫中泰演，針對strlen函數呻拌，實現了一個更為高效的匯編實現的算法，我本機是win10 + vs2017環(huán)境睦焕，在路徑 C:\Program Files (x86)\Windows Kits\10\Source\10.0.17763.0\ucrt\string\i386 中找到了strlen.asm的實現藐握，其主要代碼如下:

string  equ     [esp + 4]
        mov     ecx,string              ; ecx -> string
        test    ecx,3                   ; test if string is aligned on 32 bits
        je      short main_loop

str_misaligned:
        ; simple byte loop until string is aligned
        mov     al,byte ptr [ecx]
        add     ecx,1
        test    al,al
        je      short byte_3
        test    ecx,3
        jne     short str_misaligned
        add     eax,dword ptr 0         ; 5 byte nop to align label below
        align   16                      ; should be redundant

main_loop:
        mov     eax,dword ptr [ecx]     ; read 4 bytes
        mov     edx,7efefeffh
        add     edx,eax
        xor     eax,-1
        xor     eax,edx
        add     ecx,4
        test    eax,81010100h
        je      short main_loop
        ; found zero byte in the loop
        mov     eax,[ecx - 4]
        test    al,al                   ; is it byte 0
        je      short byte_0
        test    ah,ah                   ; is it byte 1
        je      short byte_1
        test    eax,00ff0000h           ; is it byte 2
        je      short byte_2
        test    eax,0ff000000h          ; is it byte 3
        je      short byte_3
        jmp     short main_loop         ; taken if bits 24-30 are clear and bit 31 is set

byte_3:
        lea     eax,[ecx - 1]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_2:
        lea     eax,[ecx - 2]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_1:
        lea     eax,[ecx - 3]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_0:
        lea     eax,[ecx - 4]
        mov     ecx,string
        sub     eax,ecx
        ret

??上述源碼中，根據開發(fā)人員已經有的注釋垃喊，我們可以了解其整體框架猾普，下面我們對其進行詳細的解釋。

string  equ     [esp + 4]               ; 字符串地址
        mov     ecx,string              ; ecx -> string
        test    ecx,3                   ; test if string is aligned on 32 bits缔御，判斷地址是否4字節(jié)對齊
        je      short main_loop

??上述代碼主要是判斷字符串地址是否4字節(jié)(32bits)對齊抬闷，如果對齊直接跳到main_loop主循環(huán)，否則先進行地址對齊。這里是通過test ecx,3進行判斷笤成，3的二進制表達為 011B评架，如果 ecx & 011B > 0, 說明ecx低兩位不為0，也就說明ecx所保存的地址沒有4字節(jié)對齊炕泳，即不能整除4纵诞。

str_misaligned:
        ; simple byte loop until string is aligned
        mov     al,byte ptr [ecx]    ; 從ecx指向的內存取一個字符存放在al中
        add     ecx,1                ; ecx指向下一個字符
        test    al,al                ; 測試所取的字符是否為0
        je      short byte_3         ; 如果為0，跳轉到byte_3代碼塊
        test    ecx,3                ; 再次測試地址是否4字節(jié)對齊
        jne     short str_misaligned ; 不對齊則繼續(xù)循環(huán)
        add     eax,dword ptr 0      ; 5 byte nop to align label below
        align   16                   ; should be redundant

??先從ecx指向的內存空間讀取一個字符培遵，存入al寄存器浙芙。然后將ecx指向下一個字符，判斷al是否等于0籽腕，如果為0說明到達字符結尾嗡呼，跳轉到byte_3(后面介紹)運行，否則繼續(xù)皇耗。然后再測試更新后的ecx是否4字節(jié)對齊南窗，如果沒有則繼續(xù)循環(huán)(最多循環(huán)3次)。后面兩條指令郎楼，根據其注釋万伤，看起來像填充符號。【揭秘VC CRT庫Intel模塊】-- strlen一文的博主解釋最后這兩條指令是為了16字節(jié)對齊呜袁，即使得main_loop的地址16字節(jié)對齊敌买。
??下面開始進入main_loop的介紹，由于此段代碼相比之前更長一點阶界，我們先將其分解詳細解釋虹钮，對于代碼前半部分。

mov     eax,dword ptr [ecx]     ; read 4 bytes荐操，一次讀四個字節(jié)芜抒，比我們前一半版每次讀一個字節(jié)快！
        mov     edx,7efefeffh ; 將7efefeffh賦值給edx, 0x7efefeffh = 01111110 11111110 11111110 11111111B
        add     edx,eax ; 將讀取的四個字符加到edx
        xor     eax,-1 ; 將eax取反托启，eax 異或 -1 = 將eax取反宅倒，因為-1的補碼表示為0xffffffffh
        xor     eax,edx ; eax 異或 edx
        add     ecx,4 ; ecx加4，指向下4個字符
        test    eax,81010100h ; 測試四個hole是否存在1
        je      short main_loop ; 如果不存在1屯耸，則四個字符不存在0拐迁，沒到字符串結尾，繼續(xù)循環(huán)

??首先第一給指令疗绣，給edx賦值0x7efefeffh, 其二進制表示為：

01111110\ 11111110\ 11111110\ 11111111

??將這個數的二進制分為4組线召，對應四個字符。這個數有一個特點多矮，對于其中每個為0的位置缓淹，如果再加上某個數后哈打，該位置沒有進位，那么該位置之后的低bits中(8個一組)讯壶，一定存在為0的字符料仗。后面量xor指令則是為了獲取該位置是否有進位，這里我簡單說一下我的理解伏蚊。

對于二進制中0的位置是否存在進位立轧，有以下4種情況，我們首先假定array為進位值(0 或者 1), x 為 eax寄存器中該位置的值(0 or 1躏吊，因為指令是add edx氛改，eax)，res為該位置的結果比伏。

array=0胜卤，x=0;
add指令  ->  res = array + x = 0
xor指令   ->   x = x xor -1 = !x = 1
xor指令   ->  res = res xor x = 1
最后eax保存在該位置的值為1，那么就說明該位置之前的字符存在0赁项，所以相加后沒有進位瑰艘。
array=1, x=0;
add指令  ->  res = array + x = 1
xor指令   ->   x = x xor -1 = !x = 1
xor指令   ->  res = res xor x = 0
最后eax保存在該位置的值為0，那么就說明該位置之前的字符不存在0肤舞。
array=0, x=1;
add指令  ->  res = array + x = 1
xor指令   ->   x = x xor -1 = !x = 0
xor指令   ->  res = res xor x = 1
最后eax保存在該位置的值為1，那么就說明該位置之前的字符存在0均蜜，所以相加后沒有進位李剖。
array=1, x=1;
add指令  ->  res = array + x = 0 (只保留1bit)
xor指令   ->   x = x xor -1 = !x = 0
xor指令   ->  res = res xor x = 0
最后eax保存在該位置的值為0，那么就說明該位置之前的字符不存在0囤耳。
??從上面的4種情況分析篙顺，我們可以發(fā)現一旦在 0 的位置不存在進位，經過上述add和兩個xor操作后充择，eax在該位置保存的值就為1德玫，最后用test eax，81010100h椎麦，來取這些0位置的值宰僧。其中0x81010100h的二進制為：
$10000001\ 00000001\ 00000001\ 00000000$

最后通過je指令來判斷，是否0位置是否存在沒有進位的點观挎，如果不存在琴儿，說明沒到字符串末尾，繼續(xù)循環(huán)嘁捷，否則進入后面的字符末尾判斷代碼段造成。

??發(fā)現取得的四個字符中存在編碼為0的字符時，進入下面的邏輯段判斷具體哪個字符編碼為0雄嚣，即為字符串的結尾晒屎。這段代碼主要判斷哪個字符編碼為0，以確定字符串的結尾，需要格外注意的是大小端存儲的問題鼓鲁，列如字符四個字符存儲在內存中時為 [0x65h 0x66h 0x67h 0x68h]蕴轨。但是，當我們以dword的形式讀入到寄存器比如eax中時坐桩，由于是小端存儲尺棋，那么從左到右它將被轉換為 [0x68h 0x67h 0x66h 0x65h]，因此 al 保存的應該是0x65h绵跷，所以其內存地址應該是ecx-4膘螟，即跳轉到byte_0運行。下面的代碼我注釋了前幾行碾局，后面幾行十分類似荆残，這里就不贅述了。

; found zero byte in the loop
        mov     eax,[ecx - 4]  ;由于前面ecx加了4净当，這里減去4再取回之前的4個字符(注意大小端存放)
        test    al,al          ; 由于是小端存放内斯，則al處存放的字符應該是[ecx-4]處的一個字節(jié)
        je      short byte_0 ; 當al為字符結尾時，跳轉到byte_0
        test    ah,ah                   ; is it byte 1
        je      short byte_1
        test    eax,00ff0000h           ; is it byte 2
        je      short byte_2
        test    eax,0ff000000h          ; is it byte 3
        je      short byte_3
        jmp     short main_loop         ; taken if bits 24-30 are clear and bit 31 is set
; 這個jmp指令有點不理解像啼，如果按之前的分析俘闯，是一定存在編碼為0的字符的，所以不可能運行到這條指令
; 這里猜測其可能是為了避免四個字符中高位字符編碼 = 128這種情況忽冻，
; 這種情況下, 31bit處的0也沒有進位真朗，但是其不存在編碼為0的字符。

??現在僧诚，代碼運行到最后的收尾階段了遮婶，即用編碼為0的地址減去字符串首地址計算字符串長度，代碼相對比較簡單湖笨，就不多加描述了旗扑。

; 這里ecx減一個數再取值比如 lea eax，[ecx-1] 的原因是因為在循環(huán)中ecx已經指向下一個四字節(jié)
byte_3:
        lea     eax,[ecx - 1] ; = eax, [ecx- 4 + 3], 將字符串結尾地址保存在eax
        mov     ecx,string ; 將字符串首地址保存在ecx
        sub     eax,ecx  ; eax = eax-ecx 即為字符串長度慈省，返回結果保存在eax中
        ret
byte_2:
        lea     eax,[ecx - 2] ; = eax, [ecx- 4 + 2]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_1:
        lea     eax,[ecx - 3] ; = eax, [ecx- 4 + 1]
        mov     ecx,string
        sub     eax,ecx
        ret
byte_0:
        lea     eax,[ecx - 4] ; = eax, [ecx- 4 + 0]
        mov     ecx,string
        sub     eax,ecx
        ret

3.測試c語言版本和匯編版本的性能差

??為了測試一下c語言版本和CRT庫中的運行性能臀防，我先構造了一個長度為187的字符串，分別用上述c語言版本和CRT庫中的匯編版本進行長度統(tǒng)計辫呻，循環(huán)1000000次清钥，計時后結果如下：

圖1. 計時結果

我們可以看到兩者有十幾倍的性能差，這有點太夸張放闺。后面想到因為我們自己實現的c語言版本因為調用函數進棧和出棧也十分耗費時間祟昭，而根據【揭秘VC CRT庫Intel模塊】-- strlen博主介紹:

crt的strlen函數屬于intrinsic函數，所謂intrinsic函數怖侦，可以稱作為內部函數篡悟，這與inline函數有點類似谜叹，但是不是inline之意。

??因此搬葬，可以猜想CRT的strlen函數沒有太多的調用函數進棧和出棧時間耗費荷腊，因此我們再一次實現了一個內聯(lián)匯編版本的strlen，源代碼如下所示：

#include <stdio.h>
#include <string.h>
#include "mytime.h"
using namespace std;

int strlen2(const char* str) {
    const char *eos = str;
    while (*eos++);          //不為0就加1女仰，查看下個字符是否為0
    return(eos - str - 1);    //因為*eos = 0后，++操作使其移到下個字符抡锈，所以這里需要減1.
}

int main() {
    const char* test = "hello world, errorhkajhsdlkablsalbxgdulgauwlddgaklusgddajkkaljbjakb\
skjbalksdaksddagkavkj.ajbbhquigfpeuyweyfwcwvcbvj.cb;uh)((**&^^%$%$$^%#%UR&*&*\
GYGYKFFJTDRHCFTIFYVJVKIDUDW#WSxiyufyfvkuyu!";
    TimerClock *tc = new TimerClock();
    int COUNT = 1000000;
    int b = 0;
    tc->update();
    for (int i = 0; i < COUNT; ++i) {
        b= strlen(test);
    }
    cout << "crt庫：strlen  -> cost time:" << tc->getTimerMicroSec() << "us" << endl;
    cout << "length = " << b << endl;
    b = 0;
    tc->update();
    for (int i = 0; i < COUNT; ++i) {
        //b = strlen2(test);
        __asm {
            push eax
            push ecx
            xor ecx,ecx
            mov eax, dword ptr[test]
        _main_loop:
            mov cl,byte ptr [eax]
            add eax,1
            test ecx,ecx
            je _return
            jmp _main_loop
        _return:
            mov ecx, dword ptr[test]
            sub eax,ecx
            sub eax,1
            mov b,eax
            pop ecx
            pop eax
        }
    }
    cout << "c語言：strlen  -> cost time:" << tc->getTimerMicroSec() << "us" << endl;
    cout << "length = " << b << endl;
    getchar();
    return 1;
}

??其運行時間結果如下疾忍，可以看到還是CRT庫版本的strlen函數運行時間更短一罩，而且接近4倍，正好和其一次性取值的的byte數接近(CRT版本一次取4個字節(jié)锹杈，我們實現的版本一次取1個字節(jié))，這也正好論證了我們的猜想迈着。

圖2. 計時結果2

4.總結

??從上面的介紹了我們已經大致了解了CRT庫中的strlen算法的具體實現竭望，同時也實現了我們的版本并與其進行對比，論證了其高效的性能裕菠。當然咬清，我們這里只是窺得了CRT庫的冰山一角，相信其中還有更多優(yōu)秀高效的算法值得我們去學習奴潘。利用《老碼識途》所推崇的 “猜測 -> 實證 -> 構建” 思維實踐方法旧烧，撥開底層的神秘面紗！