4.窥孔优化(以除法还原示例)

窥孔优化是反编译器一个很重要的还原技术。而且这个技术没有捷径可言，大部分情况，都是特定规则的集合。

这一章将以最经典的“整数除法”为例，展示编译器和反编译器的对于整数除法的优化与还原技术。

编译器对乘法与除法优化

对于很多算数表达式，为了提升效率编译器会进行等价的替换。

典型案例之一就是使用左移替代2的倍数的乘法：

//源码示例，这里a为无符号整数
a = a * 4

//编译器优化后
a = a << 2

这一优化就是”窥孔优化“的一种，因为在现代CPU中除法和乘法运算是十分昂贵的，尤其是除法。（据说以前除法比加法慢50倍以上，比乘法慢10倍以上，直到Intel的Cannon Lake架构出现，Cannon Lake将64位整数除法的最大延时从96个周期降为了18个周期。这样除法就只比加法慢20倍，比乘法慢5倍）

实际的情况比想象中更加的复杂，单说加减乘除就有各种优化方法，下面是几个常见的典型除法类的优化示例：

无符号除法优化 https://godbolt.org/z/acm19_div3

//除法优化示例，这里edi为无符号整数
edi = edi / 3

//优化后编译成汇编 即 edi = (edi * 0xaaaaaaab) >> 33
mov eax, edi          ; eax = edi
mov edi, 2863311531   ; edi = 0xaaaaaaab
imul rax, rdi         ; rax = rax * 0xaaaaaaab
shr rax, 33           ; rax >>= 33

2.有符号除法优化

//除法优化示例，这里edi为有符号整数
edi  = edi / 2;

//优化后编译成汇编 即 edi =  (edi + (edi >> 33)) >> 1
//其中所有的右移都为有符号右移
mov     eax, edi         ; eax = edi
shr     eax, 31          ; eax = eax >> 31
add     eax, edi         ; eax = eax + edi
sar     eax              ; eax = eax >> 1

3.无符号取余优化

//取余优化示例，这里edi为无符号整数
edi % 3 == 0

//优化后编译成汇编
imul edi, edi, -1431655765    ; edi = edi * 0xaaaaaaab
cmp edi, 1431655765           ; compare with 0x55555555
setbe al                      ; return 1 if edi <= 0x55555555

在GCC中，有专门的规则实现这一类优化，叫做match.pd的文件专门描述这一类优化。他是一种类LISP规则语言，反正我是看不懂，可以看上面的注释，看看具体实现了哪种优化。

gcc/gcc/match.pd at master · gcc-mirror/gccGitHub

反编译器的反窥孔优化：

为了将优化后的算式“反向优化”为人类可理解的算法，反编译器和编译器一样，都有这一类的匹配规则，称之为“反窥孔优化”。但是，编译器的窥孔优化不一定是绝对能还原的，所以

我这里以Ghidra为例（IDA不开源，有空再研究这玩意咋实现），Ghidra提供了一些列的规则处理这种特殊情况

https://www.lockshaw.io/static/ghidra/decompiler/doc/classRule.html#details

其中的除法优化示例：RuleDivOpt 类，他会将优化后乘法+右移的功能反编译成除法

公式为：

sub( (zext(V)*c)>>n, 0) => V / (2^n/(c-1))
sub( (sext(V)*c)s>>n, 0) => V s/ (2^n/(c-1))

看上面这个公式不太直观。还是举个例子后模拟ghidra的运算方法

# 源码
unsigned divideByFive(unsigned x)
{
    return x / 5;
}
# 编译器优化后的汇编实现
mov     eax, edi
mov     edi, 3435973837
imul    rax, rdi
shr     rax, 34

参考汇编，代入公式 ( 2^n / (c-1) ) 其中 n=34, c=3435973837

Python 3.10.6
>>> n=34
>>> c=3435973837
>>> ( 2**n // (c-1) )
5

换成整数，约为5，因此可以反编译优化为 x / 5

反窥孔优化简单汇总

下面简单汇总了一些反窥孔优化的项目，都是从ghidra抄的

其中 V、W、X代表变量

c、d代表常量


-V => V * -1
V + -W ==> V - W
((V + c) + d) => V + (c+d)
((V * c) * d) => V * (c*d)
((V + (W + c)) + d) => (W + (c+d)) + V
V + 0xff... => V - 0x00...
(V << W) & d => (V & (W >> c)) << c
(V & c) & d => V & (c & d)
(V >> X) | (W >> X) => (V | W) >> X
!!V => V
!(V == W) => V != W
!(V < W) => W <= V
!(V <= W) => W < V
!(V != W) => V == W
V ^^ W => V != W
V * c + V * d => V * (c + d)
sub( (zext(V)*c)>>n, 0) => V / (2^n/(c-1))
sub( (sext(V)*c)s>>n, 0) => V s/ (2^n/(c-1))
sub(ext(V)*c,b)>>d + V -> sub( (ext(V)*(c+2^n))>>n,0)
W+((V-W)>>1) =>sub( (zext(V)*(c+2^n))>>(n+1), 0)
(V << c) << d => V << (c+d)
(V << c) >> c => V & 0xff
sub( concat(V,W), 0) => W
sub( concat(V,W), c) => V
sub( concat(V,W), c) => sub(V,c)
V * -1 == c => V == -c
V + c == d => V == (d-c)
~V == c => V == ~c
((V + c) + W) & 0xfff0 => (V + (c & 0xfff0)) + W