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，循环，继续判断下一个字符
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作为一个相当常用的函数，如果其实现的算法速度更快，那么其对整个系统的性能提升是比较可观的。因此在CRT库中，针对strlen函数，实现了一个更为高效的汇编实现的算法，我本机是win10 + vs2017环境，在路径 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
上述源码中，根据开发人员已经有的注释，我们可以了解其整体框架，下面我们对其进行详细的解释。
string equ [esp + 4] ; 字符串地址
mov ecx,string ; ecx -> string
test ecx,3 ; test if string is aligned on 32 bits，判断地址是否4字节对齐
je short main_loop
上述代码主要是判断字符串地址是否4字节(32bits)对齐，如果对齐直接跳到main_loop主循环，否则先进行地址对齐。这里是通过test ecx,3进行判断，3的二进制表达为 011B，如果 ecx & 011B > 0, 说明ecx低两位不为0，也就说明ecx所保存的地址没有4字节对齐，即不能整除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字节对齐
jne short str_misaligned ; 不对齐则继续循环
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(后面介绍)运行，否则继续。然后再测试更新后的ecx是否4字节对齐，如果没有则继续循环(最多循环3次)。后面两条指令，根据其注释，看起来像填充符号。【揭秘VC CRT库Intel模块】-- strlen一文的博主解释最后这两条指令是为了16字节对齐，即使得main_loop的地址16字节对齐。
下面开始进入main_loop的介绍，由于此段代码相比之前更长一点，我们先将其分解详细解释，对于代码前半部分。
mov eax,dword ptr [ecx] ; read 4 bytes，一次读四个字节，比我们前一半版每次读一个字节快！
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，没到字符串结尾，继续循环
首先第一给指令，给edx赋值0x7efefeffh, 其二进制表示为：
对于二进制中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种情况分析，我们可以发现一旦在 0 的位置不存在进位，经过上述add和两个xor操作后，eax在该位置保存的值就为1，最后用test eax，81010100h，来取这些0位置的值。其中0x81010100h的二进制为：
最后通过je指令来判断，是否0位置是否存在没有进位的点，如果不存在，说明没到字符串末尾，继续循环，否则进入后面的字符末尾判断代码段。
发现取得的四个字符中存在编码为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]处的一个字节
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] 的原因是因为在循环中ecx已经指向下一个四字节
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库中的汇编版本进行长度统计，循环1000000次，计时后结果如下：
crt的strlen函数属于intrinsic函数，所谓intrinsic函数，可以称作为内部函数，这与inline函数有点类似，但是不是inline之意。
因此，可以猜想CRT的strlen函数没有太多的调用函数进栈和出栈时间耗费，因此我们再一次实现了一个内联汇编版本的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;
}
4.总结
从上面的介绍了我们已经大致了解了CRT库中的strlen算法的具体实现，同时也实现了我们的版本并与其进行对比，论证了其高效的性能。当然，我们这里只是窥得了CRT库的冰山一角，相信其中还有更多优秀高效的算法值得我们去学习。利用《老码识途》所推崇的 “猜测 -> 实证 -> 构建” 思维实践方法，拨开底层的神秘面纱！
参考
- 韩宏,李林，《老“码”识途：从机器码到框架的系统观逆向修炼之路》
- masefee，【揭秘VC CRT库Intel模块】-- strlen
