除数为无符号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‬ \]

向上取整为3，所以这里的除法是\(\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++汇编与逆向分析技术解密