反汇编strlen函数

0. 本文结构概述

1. strlen库函数实现原理
2. 公式分析(变换形式)
3. 计算步骤分析（有些繁琐，后续会修改优化）
4. C语言实现该函数
5. 汇编语言实现该函数

1. strlen库函数实现原理

使用VS2019进行反汇编，发现字符串操作的库函数，多数都是汇编实现的(没有看完所有的)。按照我预想的strlen函数计算字符串长度，就是一位一位的判断是否为'\0'，然而库函数是4位比较。简要步骤如下所示：

• 步骤1：判断地址是否为 4字节对齐
  为什么要判断4字节对齐呢？ 【CPU一次能取多少内存需要看总线的位数，如果是32位，一次读取4个字节，而且CPU不能跨内存区间访问。也就是说如果内存地址为编号为0x00000003-0x00000007，想取这4个地址内的数据，CPU要取两次。这样的效率太低了，所以需要等地址为4字节对齐时，再以4字节取出判断。】

  • 1.1 公式：addr & 0x11 == 0
  • 1.2 若结果为0，说明 addr 能被4整除，addr 是4字节对齐的，直接进入步骤2
  • 1.3 若不为0，需要按位判断是否为 '\0'，然后再次进行 1.1 步骤

• 步骤2：通过运算判断此4字节中是否有 '\0'

  • 公式：

    a  = 值 + 0x7efefeff
    值 = 值 ^ 0xffffffff
    值 = 值 ^ a
    值 = 值 & 0x81010100
    ----> 结果为0 ----> 每一位都非0
    ----> 结果非0 ----> 某一位为0
    

• 步骤3：若该4字节中存在 '\0' ，则按位判断是否为 '\0'

• 步骤4：返回值：eax = 字符串首地址 - 当前位 (首地址为低地址)

• 流程图如下所示：
  

2. 公式分析(变换形式)

1. 想要变换形式，需要对这个公式表示认同，以此达到共识
   值 ^ 0xffffffff == 0xffffffff - 值

2. 将如下公式变成一个表达式

a  = 值 + 0x7efefeff
值 = 值 ^ 0xffffffff
值 = 值 ^ a
值 = 值 & 0x81010100
----> 结果为0 ----> 每一位都非0
----> 结果非0 ----> 某一位为0

• 表达式：结果 = ((值 + 0x7efefeff) ^ (0xffffffff - 值)) & 0x81010100

3. 将表达式写成表格形式

3. 计算步骤分析（有些繁琐，后续会修改优化）

• 第1字节是否为0，都不影响当前字节计算结果的最低位等于0。
• 第2、3、4字节的最低位满足以下条件
  • 若第1字节不为0，肯定会发生进位，那么第2字节的运算公式就发生了改变：(fe + c + 1) ^ (ff - c) = (ff + c) ^ (ff - c) = xxxx xxx0，此时第2字节的运算公式和第1字节一致，那么第2字节的计算结果的最低位也一定等于0
  • 若第1字节为0，那么第2字节的运算公式为：(fe + c) ^ (ff - c) = xxxx xxx1
• 第4字节中，若第4字节等于0，那么分两种情况
  • 第3位进位：(7e + 0 + 1) ^ (ff - 0) = 7f ^ ff = 1000 0000，高位等于1
  • 第3位不进位：(7e + 0) ^ (ff - 0) = 7e ^ ff = 1000 0001，高位与低位都等于1
• 第4字节中，若第4字节大于0，同样分两种情况
  • 第3位进位：(7e + 1 + 1) ^ (ff - 1) = 80 ^ fe = 0111 1110，高位与低位都等于0
  • 第3位不进位分两种情况
    • 第4字节等于1：(7e + 1 + 0) ^ (ff - 1) = 7f ^ fe = 1000 0001，高位与低位都等于1，因为我们要用第4字节判断第3和第4字节的进位情况，当我们第4字节等于1时，无法确定这个1是第3字节进位得来的，还是第4字节本身就为1，但是结果符合我们的判断依据，他们都等于1，最终的与运算结果必然是非0的。
    • 第4字节大于1：(7e + 2 + 0) ^ (ff - 2) = 7f ^ fe = 0111 1101，高位等于0，低位等于1，从大于1开始，高位持续等于0，低位一直等于1

4. C语言实现该函数

int myStrlen(char buf[])
{
	int* p = buf;
	int len = 0;
	while (1)
	{
		int tmp = ((*p + 0x8efefeff) ^ (~(*p))) & 0x81010100;
		if (!tmp)
		{
			p++;
			continue;
		}
		else
		{
			len = (char*)p - buf;
			if (!(*p & 0xff))
			{
				len +=  0;
				break;
			}
			else if (!(*p & 0xff00))
			{
				len += 1;
				break;
			}
			else if (!(*p & 0xff0000))
			{
				len += 2;
				break;
			}
			else if (!(*p & 0xff000000))
			{
				len += 3;
				break;
			}
		}
	}
	return len;
}

5. 汇编语言实现该函数

int __declspec(naked)asm_strlen(char* buf)
{
	__asm
	{
		push ebp
		mov ebp, esp
		push ecx
		push edx
		push [ebp + 8]

		mov ecx, [ebp + 8]
		test ecx, 3
		je asm_strlen@main_loop

	asm_strlen@misligned:
		mov al, byte ptr[ecx]
		add ecx, 1
		test al, al
		je byte_0
		test ecx, 3
		jne asm_strlen@misligned

	asm_strlen@main_loop:
		mov eax, dword ptr[ecx]
		add ecx, 4
		mov edx, eax
		add edx, 0x7efefeff
		xor eax, 0xffffffff
		xor eax, edx
		test eax, 0x81010100
		je asm_strlen@main_loop

		mov eax, dword ptr[ecx - 4]
		test al, al
		je asm_strlen@byte_0
		test ah, ah
		je asm_strlen@byte_1
		test eax, 0x00ff0000
		je asm_strlen@byte_2
		test eax, 0xff000000
		je asm_strlen@byte_3

	asm_strlen@byte_3:
		lea eax, [ecx - 1]
		pop ecx
		sub eax, ecx
		jmp asm_strlen@end

	asm_strlen@byte_2:
		lea eax, [ecx - 2]
		pop ecx
		sub eax, ecx
		jmp asm_strlen@end

	asm_strlen@byte_1:
		lea eax, [ecx - 3]
		pop ecx
		sub eax, ecx
		jmp asm_strlen@end

	asm_strlen@byte_0:
		lea eax, [ecx - 4]
		pop ecx
		sub eax, ecx
		jmp asm_strlen@end

	asm_strlen@end:
		pop edx
		pop ecx
		pop ebp
		ret
	}
}