除法优化识别以及还原方法
除数为无符号2的幂
快速识别
? x >> n(无符号右移)
快速还原
? \(\frac{x}{2^n}\)由于n=4,所以例子中的除法是\(\frac{x}{16}\)
除数为无符号非2的幂
快速识别
\(\frac{x}{c}=x*M>>n\)，且使用无符号乘法时
快速还原
\(c = \frac{2^n}{M}\)
本例中\(n=33,M=0xAAAAAAAB\)
\[c = \frac{2^{33}}{0xAAAAAAAB} = 2.9999999996507540345598531381041? \]向上取整为3，所以这里的除法是\(\frac{x}{3}\)
通用还原
由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}\)所以\(\frac{2^n}{c} = M\)
\[c =\frac{2^n}{M} = \frac{2^{33}}{0xAAAAAAAB} = 2.9999999996507540345598531381041? \]向上取整为3，所以这里的除法是\(\frac{x}{3}\)
除数为无符号非2的幂第二种
快速识别
\(\frac{x}{c} = \{[x-(x*M >> 32) >> n1] + x * M >> 32\} >> n2\),且使用无符号乘法时
快速还原
\[M = \frac{2^{n}}{c}-2^{32},n = n1 +n2+32 \]\[c =\frac{2^n}{M+2^{32}} \]在本例中\(n = n1 +n2 +32 = 1 + 2 + 32 = 35,M = 0x24924925\)
\[c =\frac{2^n}{M+2^{32}} = \frac{2^{35}}{0x24924925+2^{32}} = 6.9999999993888195604619552997935? \]向上取整为7，所以这里的除法是\(\frac{x}{7}\)
通用还原
上面的代码所为用下面的数学公式表达
\[\frac{\frac{x-\frac{x*M}{2^{32}}}{2}+\frac{x*M}{2^{32}}}{2^2} = x*\frac{2^{32}+M}{2^{35}} \]由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}\)所以\(\frac{2^n}{c}=2^{32}+M\)
\[c =\frac{2^n}{M+2^{32}} = \frac{2^{35}}{0x24924925+2^{32}} = 6.9999999993888195604619552997935? \]向上取整为7，所以这里的除法是\(\frac{x}{7}\)
除数为有符号2的幂
快速识别
如果\(x\ge0,则\frac{x}{2^n} = x >> n\),如果\(x<0,则\frac{x}{2^n} = [x+(2^n-1)] >> n\)
快速还原
\(c = 2^n = 2^3 = 8\),所以这里的除法是\(\frac{x}{8}\)
通用还原
由于sar是向下取整，而\(\frac{x}{c}\)为负数需要向上取整，所以需要加上\(2^n -1\)，为什么是加上\(2^n -1\)呢，因为 \(2^n = c\),而\(\frac{x}{c}\)余数的最小值为\(-\frac{c-1}{c}\),所以加上\(c-1\)就能起到加1的效果，加一后取下整，等于原来的值取上整。
除数为有符号非2的幂第一种
快速识别
如果\(x\ge0,则\frac{x}{c} = x *M >> n ,如果x<0,则\frac{x}{c} = [x *M >> n] + 1\)
快速还原
\[c = \frac{2^n}{M} = \frac{2^{33}}{38E38E39} = 8.9999999989522621036795594143123? \]向上取整为9，所以这里的除法是\(\frac{x}{9}\)
通用还原
由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}所以\frac{2^n}{c} = M\)
\[c =\frac{2^n}{M} = \frac{2^{33}}{38E38E39} = 8.9999999989522621036795594143123? \]向上取整为9，所以这里的除法是\(\frac{x}{3}\)
除数为有符号非2的幂第二种
快速识别
如果\(x\ge0,则\frac{x}{c} = [x *M + x*2^{32}]>> n ,如果x<0,则\frac{x}{c} =\{ [x *M + x*2^{32}]>> n\} + 1\)
快速还原
\[c = \frac{2^n}{M} = \frac{2^{35}}{0x88888889} = 14.999999996944097802665530336711? \]向上取整为9，所以这里的除法是\(\frac{x}{15}\)
通用还原
上面的代码所为用下面的数学公式表达
\[\frac{x*M+x*2^{32}}{2^{35}}=x*(M+2^{32})*\frac{1}{2^{35}} \]由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}\)所以\(\frac{2^n}{c}=2^{32}+M\)
\[c =\frac{2^n}{M+2^{32}} = \frac{2^{35}}{88888889+2^{32}} =\frac{2^{35}}{0x88888889}=14.999999996944097802665530336711? \]注：上面的88888889是有符号数
向上取整为9，所以这里的除法是\(\frac{x}{15}\)
除数为有符号负2幂
快速识别
如果\(x\ge0,则\frac{x}{c} = -(x >> n),如果x<0,则\frac{x}{2^n} = -\{[x+(2^n-1)] >> n\}\)
快速还原
\[c = - 2^n = - 2^ 2 = -4 \]通用还原
仔细观察，这里无非就是将除数为2的幂取负而已，只要把除数为2的幂的除数求出来，再取负就行
除数为有符号非负2的幂的第一种
快速识别
如果\(x\ge0,则\frac{x}{c} = x *M >> n ,如果x<0,则\frac{x}{c} = [x *M >> n] + 1\)，但此时注意 这里的M是个负数，这一点是用来区分除数为有符号非2的幂的第一种的优化的
快速还原
\[c =\frac{2^n}{M} = \frac{2^{33}}{99999999} = -\frac{2^{33}}{66666667} = -\lceil4.9999999982537701732058415050132?\rceil = -5 \]所以这里的除法是\(\frac{x}{-5}\)
通用还原
由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}所以\frac{2^n}{c} = M\)
\[c =\frac{2^n}{M} = \frac{2^{33}}{99999999} = -\frac{2^{33}}{66666667} = -\lceil4.9999999982537701732058415050132?\rceil = -5 \]所以这里的除法是\(\frac{x}{-5}\)
除数为有符号非负2的幂的第一种Gcc版
快速识别
如果\(x\ge0,则\frac{x}{c} = -（x *M >> n） ,如果x<0,则\frac{x}{c} = -[（x *M >> n） + 1]\)
快速还原
\[-c =\frac{2^n}{M} = \frac{2^{33}}{66666667} = \lceil4.9999999982537701732058415050132?\rceil = 5 \]\(c = -5 所以这里的除法是\frac{x}{-5}\)
通用还原
上面的代码所为用下面的数学公式表达
\[-\frac{x*M}{2^n} = x*-M*\frac{1}{2^n} \]由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}所以\frac{2^n}{c} = -M\)
\[c =\frac{2^n}{-M} = \frac{2^{33}}{99999999} = -\frac{2^{33}}{66666667} = -\lceil4.9999999982537701732058415050132?\rceil = -5 \]所以这里的除法是\(\frac{x}{-5}\)
除数为有符号非负2的幂的第二种
快速识别
如果\(x\ge0,则\frac{x}{c} = (x *M -X*2^{32})>> n ,如果x<0,则\frac{x}{c} = [(x *M -X*2^{32})>> n] + 1\)
快速还原
\[c =\frac{2^n}{M-2^{32}} = \frac{2^{34}}{6DB6DB6D-2^{32}} = \frac{2^{34}}{FFFFFFFF6DB6DB6D}= -\frac{2^{34}}{92492493}=-\lceil6.9999999979627318686215638099758?\rceil = -7 \]$c = -7 \(所以这里的除法是\)\frac{x}{-7}$
通用还原
上面的代码所为用下面的数学公式表达
\[\frac{x*M-x*2^{32}}{2^n} = x*(M-2^{32})*\frac{1}{2^n} \]由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}所以\frac{2^n}{c} = M-2^{32}\)
\[c =\frac{2^n}{M-2^{32}} = \frac{2^{34}}{6DB6DB6D-2^{32}} = \frac{2^{34}}{FFFFFFFF6DB6DB6D}= -\frac{2^{34}}{92492493}=-\lceil6.9999999979627318686215638099758?\rceil = -7 \]所以这里的除法是\(\frac{x}{-7}\)
除数为有符号非负2的幂的第二种Gcc版
快速识别
如果\(x\ge0,则\frac{x}{c} = -[(x *M+x*2^{32}) >> n] ,如果x<0,则\frac{x}{c} = -\{[(x *M+x*2^{32}) >> n] + 1\}\)
快速还原
\[-c =\frac{2^n}{M+2^{32}} = \frac{2^{34}}{92492493+2^{32}} = \frac{2^{34}}{0x92492493}=\lceil6.9999999979627318686215638099758?\rceil = 7 \]\(c = -7所以这里的除法是\frac{x}{-7}\)
通用还原
上面的代码所为用下面的数学公式表达
\[-\frac{x*M+x*2^{32}}{2^n} = x*(-M-2^{32})*\frac{1}{2^n} \]由于\(\frac{x}{c} = x * \frac{2^n}{c}*\frac{1}{2^n}所以\frac{2^n}{c} = -M-2^{32}\)
\[c =\frac{2^n}{-M-2^{32}} = \frac{2^{34}}{6DB6DB6D-2^{32}} = \frac{2^{34}}{FFFFFFFF6DB6DB6D} =-\frac{2^{34}}{0x92492493}= -\lceil6.9999999979627318686215638099758\rceil = -7 \]所以这里的除法是\(\frac{x}{-7}\)
至此除法优化完毕，一共有11中优化，除了2的幂(包括无符号)和-2的幂这三种，其他都是\(\frac{x}{c} = x*\frac{2^n}{c}*\frac{1}{2^n}\)的变种优化，通过比对代码和公式，即可还原
参考资料：c++汇编与逆向分析技术解密