C++逆向：除法的常规优化及其识别与还原

C/C++逆向

2901

2021-08-20

本文涉及到的是除法的一般优化方法，其中特殊情况暂时不列举，涉及的知识点包括除以2的幂以及除以非2的幂的常规情况
…

具体知识点包括：

被除数是无符号数，除以2的幂
被除数是有符号数，除以2的幂
被除数是无符号数，除以非2的幂
被除数是有符号数，除以非2的幂的常规情况，即：MagicNum没有进位和不为负数的情况

在学习的时候，需要对照着看，使用的工具是VC6.0和IDA 6.1。使用的是VC6.0的原因是其编译器对于除法优化更加激进一些，也更加不好识别一些，而VS2019等IDE的MSVC编译器已经将部分优化直接替换为了除法等指令，原因可能是因为现在的硬件对于除法指令的硬件优化更加好一些，已经在可接受范围内了，所以本文采用的是VC6.0的编译器进行练习。

需要注意的是

在编译时需要选择的是Release版本，而不能是Debug版本，开启的选项是速度优先优化选项，而不是体积优先。
在写例子的时候，需要注意传播优化、折叠优化等优化方式带来的影响

无符号数除以2的幂

示例01 - 除数为2

int main(int argc, char* argv[])
{
	printf("%d", (unsigned int)argc / 2);
	return 0;
}

对其反汇编进行整理，得到反汇编为：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main proc near

arg_0           = dword ptr  4

	mov     eax, [esp+arg_0]
	shr     eax, 1
	push    eax
	push    offset s->D     ; "%d"
	call    printf
	add     esp, 8
	xor     eax, eax
	retn

_main endp

发现其使用的是shr reg, 1 ，使用无符号右移指令来替代除法指令，其指令周期更短，运算更快。

示例02 - 除数为2的幂

int main(int argc, char* argv[])
{
	printf("%d", (unsigned int)argc / 8);
	return 0;
}

反汇编结果：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

	mov     eax, [esp+arg_0]
	shr     eax, 3		   ; 还是使用的是无符号右移指令
	push    eax
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn
				
_main           endp

可以发现，其使用的还是无符号右移指令，右移的次数为幂次

总结

对于被除数是无符号数，而除数是2的幂的情况下，MSVC使用的是无符号右移指令，定式为：

mov reg, x		; x为被除数
shr reg, N		; N为2的幂次

还原时直接可以通过 $2^N$ 得到除数

有符号数除以2的幂

示例01 - 除数为2

int main(int argc, char* argv[])
{
	printf("%d", argc / 2);
	return 0;
}

观察其反汇编：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

	mov     eax, [esp+arg_0]
	cdq
	sub     eax, edx
	sar     eax, 1
	push    eax
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn

_main           endp

可以发现其计算方法并不是简单的将无符号右移指令shr 变为sar：

mov     eax, [esp+arg_0]
cdq
sub     eax, edx
sar     eax, 1

它在做什么呢？需要一行一行看。首先它将eax进行符号扩展，变为edx, eax的形式，edx保存的是有符号数arg0 的符号位。如果arg0为正数，则edx的值为0；如果arg0为负数，则edx的值为0xFFFF,FFFF，也就是-1。紧接着它用了减法操作，如果上述运算结果edx为0，则相当于该操作是无效操作；如果是-1，则相当于将被除数做了一个加一的操作。最后才做了一个带符号的右移运算，得到最终的除法运算结果。

将运算的每一步都搞清楚了好像也没明白它为什么这么做？他其实是将分支操作给转变成了无分支的操作了。在C/C++中，它的取整操作是向0取整的，也就是说，对于正数，它是向下取整；而对于负数，它是向上取整的。举个例子，3.5取整是3，-3.5取整就是-3，即：取更靠近0的整数。在这里就出现问题了，对于数学意义上来讲，-3.5的取整应该是-4，所以为了符合C/C++的向0取整约定，需要做调整，那么如何做调整呢，只需要将负数部分的向下取整变为上整即可，也就是说：-3.5 + 1 = -2.5，然后再取下整，就是-3。与向0取整的结果是一致的。

在上述描述的下整转上整其实有一个数学定理，本文并不打算将所用到的定理一一列出，而是举例子和描述出最终结果，以将笔者所理解的描述出来，证明我自己已经懂了即可。

示例02 - 除数为2的幂

int main(int argc, char* argv[])
{
	printf("%d", argc / 8);
	return 0;
}

反汇编结果：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

	mov     eax, [esp+arg_0]
	cdq
	and     edx, 7		   ; 在上述基础上又多出了这么一个操作
	add     eax, edx
	sar     eax, 3
	push    eax
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn

_main           endp

根据示例01的分析，这个也应该是有分支转为无分支的操作（因为分支操作打乱了流水线优化，所以速度会变慢）。但是其又多了一句and edx, 7的运算，这句运算是做什么用的呢？

mov     eax, [esp+arg_0]
cdq
and     edx, 7		   ; 在上述基础上又多出了这么一个操作
add     eax, edx		   ; 加一操作也变为了加0或者加7了
sar     eax, 3

设a是被除数，b是除数，q是商，r是余数，则有： $a = qb + r$ ，可以得到： $\frac{a}{b} = q + \frac{r}{b}$ ，当 $a < 0, b > 0$ 时，有： $\lceil \frac{a}{b} \rceil= \lceil q + \frac{r}{b}\rceil$ ，而 $\lceil q + \frac{r}{b}\rceil = q + \lceil \frac{r}{b} \rceil$ ，且 $|r| < b$ , $|r| + 1 \le b$ ，故有：

\lceil \frac{a}{b} \rceil - \lfloor \frac{a + b - 1}{b} \rfloor = q + \lceil \frac{r}{b} \rceil - q - \lfloor \frac{r + b - 1}{b} \rfloor = \lceil \frac{r}{b} \rceil - \lfloor \frac{r - 1}{b} \rfloor -1

\lceil \frac{r}{b} \rceil - \lfloor \frac{r - 1}{b} \rfloor = 1,when \space r < 0

\lceil \frac{r}{b} \rceil - \lfloor \frac{r - 1}{b} \rfloor = 1,when \space r = 0

\lceil \frac{r}{b} \rceil - \lfloor \frac{r - 1}{b} \rfloor = 1,when \space r > 0

\Rightarrow \lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor

对于上述证明的通俗理解是：由于r是余数，其结果可能不为0，那么使其上整转为下整运算，分子需要加的最大整数就应该是b - 1，因为再加1，就变为了1，则当余数为0时，会影响其结果，导致计算后结果上整值和下整值不正确，因此为了保证其结果不管在什么时候都能相等，调整因子最大为b - 1

总结

对于这种的代码定式可以统一为示例02的定式，原因是示例1的为示例2的特殊情况：

mov reg, x
cdq
and edx, 2^N - 1
add reg, edx
sar reg, N

识别时需要先统计一共右移了几次，然后再判断其用来做与运算的值是否是 $2^N - 1$ ，如果是，则可以认为是被除数为有符号数而除数是2的幂的情况，还原时直接将除数还原为 $2^N$

当除数是负的2的幂的时候，只需要在最后面添加一句neg reg即可得到结果。

无符号数除以非2的幂

示例

int main(int argc, char* argv[])
{
	printf("%d", (unsigned int)argc / 5);
	return 0;
}

反汇编结果为：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

	mov     eax, 0CCCCCCCDh	; 多出来一个大数
	mul     [esp+arg_0]
	shr     edx, 2
	push    edx				; 乘法运算后取高32位
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn

_main           endp

上述反汇编结果用到的其实就是一个除法转乘法的运算，前提是除数必须是一个常量，可以在编译期间内计算出来的，原因是下列公式：

\frac{A}{C} = A \times \frac{1}{C} = A \times \frac{2^n}{C}\times \frac{1}{2^n} = A\times M \times \frac{1}{2^n} = A \times M >> n

需要除数C是一个常量。

还原时只需要做逆运算： $MagicNum = \frac{2^n}{Divisor} \to Divisor = \frac{2^n}{MagicNum}$

总结

无符号数除以非2的幂的代码定式为：

mov reg, MagicNum
mul x
shr edx, n			; 使用edx相当于已经先右移了32位了，最终总的移位次数应该为N = 32 + n

代码定式使用的是无符号数的运算指令，还原时需要统计一共右移了多少位，然后再使用逆运算还原出除数。

需要注意的是，编译器在计算魔数MagicNum（就是上面反汇编中的大数）时，是作为无符号数运算的。且由于除数C不是2的幂，编译器在计算MagicNum是要做取下整操作的，因此我们在还原除数的时候，需要取上整。

有符号数除以非2的幂

这篇是一般的常规情况，即：编译器得到的MagicNum无进位现象，无需正负数调整运算结果的情况。

示例01 - 除数为正数

int main(int argc, char* argv[])
{
	printf("%d", argc / 5);
	return 0;
}

反汇编结果为：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

                mov     ecx, [esp+arg_0]
	mov     eax, 66666667h		; 注意此时MagicNum是正数
	imul    ecx
	sar     edx, 1				; 采用的是有符号运算指令
	mov     eax, edx
	shr     eax, 1Fh
	add     edx, eax				; 运算结果下整转上整
	push    edx
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn

_main           endp

可以发现，MagicNum是正数，且对于负数的情况，会加1做下整转上整的操作。还原方法与无符号数除以非2的幂的情况一致。

示例02 - 除数为负数

int main(int argc, char* argv[])
{
	printf("%d", argc / -5);
	return 0;
}

反汇编结果为：

; int __cdecl main(int argc, const char **argv, const char **envp)
_main           proc near               ; CODE XREF: start+AFp

arg_0           = dword ptr  4

	mov     ecx, [esp+arg_0]
	mov     eax, 99999999h		; 注意此时是负数，是以补码的形式存放的
	imul    ecx
	sar     edx, 1
	mov     eax, edx
	shr     eax, 1Fh
	add     edx, eax
	push    edx
	push    offset s->D     ; "%d"
	call    printf

	add     esp, 8
	xor     eax, eax
	retn

_main           endp

此时MagicNum是负数，在还原的时候，需要先求出其真值，再还原

识别定式总结

下列总结暂时为不完全的，原因是还有一些特殊情况未被加进来：

在识别时，先观察是否有加1做调整的操作，如果有且运算指令使用的是有符号运算指令，则被除数是有符号数。
查看MagicNum是否是负数（大于等于0x8000,0000即为负数）。如果是负数，则除数是负数；否则除数是正数

附录

对于取整操作的几个有用的性质：

上下取整是相对于0点是对称的，因此对于实数x取上整/下整再取负要变取整方向。如：对 $\lfloor -x \rfloor$ ，其结果等于将符号提出，并变取整方向 $-\lceil x \rceil$ 。可以利用该性质将取整运算内的符号提出
当x为实数时，即：x不为整数时，下整和上整运算的结果相差1

#逆向 ⁶ #除法优化 ² #C++逆向 ⁸

C++逆向：除法的非常规优化及其识别与还原

最优化理论：凸优化中的对偶

digSelf

digSelf

C++逆向：除法的常规优化及其识别与还原

无符号数除以2的幂

示例01 - 除数为2

示例02 - 除数为2的幂

总结

有符号数除以2的幂

示例01 - 除数为2

示例02 - 除数为2的幂

总结

无符号数除以非2的幂

示例

总结

有符号数除以非2的幂

示例01 - 除数为正数

示例02 - 除数为负数

识别定式总结

附录

分享