Skip to content

Latest commit

 

History

History
112 lines (85 loc) · 4.77 KB

201603311247.txt.md

File metadata and controls

112 lines (85 loc) · 4.77 KB
Raw

标题: 逆向工程中面对并理解编译器对除法的优化

http://scz.617.cn/misc/201603311247.txt

参看:

Understanding of MSVS C++ compiler optimizations - Hans Passant [2014-07-08] http://stackoverflow.com/questions/24628899/understanding-of-msvs-c-compiler-optimizations

这是我看过的最简洁的解答:

Processors are not very good at dividing, an idiv can take between 11 and 18 cycles. As opposed to shifts and multiplies, they usually only take a single cycle.

So the optimizer replaced your division by a multiplication using fixed-point math, taking advantage of a 32-bit multiply producing a 64-bit result into edx:eax. Back-of-the-envelope:

n / 100 = n * 0.32 / 32 = n * (0.32 * pow(2,32)) / 32 / pow(2,32)

Those divisions are very cheap, just a right-shift. And the multiplier becomes:

0.32 * pow(2,32) = 1374389534.72 ~= 1374389535 = 0x51EB851F (向上取整)

n / 10 = n * 0.4 / 4 = n * (0.4 * pow(2,32)) / 4 / pow(2,32) 0.4 * pow(2,32) = 1717986918.4 ~= 1717986919 = 0x66666667 (向上取整)

n / 5 = n * 2 / 10 = n * (2 * 0.4 * pow(2,32)) / 4 / pow(2,32) 2 * 0.4 * pow(2,32) = 3435973836.8 ~= 3435973837 = 0xCCCCCCCD (向上取整)

n / 3 = n * (2/3) / 2 = n * ((2/3) * pow(2,32)) / 2 / pow(2,32) (2/3) * pow(2,32) ~= 2863311530.667 ~= 2863311531 = 0xAAAAAAAB (向上取整)

n / 7 = n * (4/7) / 4 (4/7) * pow(2,32) ~= 2454267026.2857 ~= 2454267026 = 0x92492492 (向下取整)

有多种优化方式，比如:

n / 10 = n * 0.4 / 4 = n * (0.4 * pow(2,32)) / 4 / pow(2,32) n / 10 = n / 5 / 2 = n * (0.8 * pow(2,32)) / 8 / pow(2,32)

n / 5 = n * 2 / 10 = n * (0.8 * pow(2,32)) / 4 / pow(2,32) n / 5 = n / 10 * 2 = n * (0.4 * pow(2,32)) / 2 / pow(2,32)

n / 7 = n * (4/7) / 4 n / 7 = n * (2/7) / 2 n / 7 = n * (1/7) / 1

保底的优化:

n / c = n * (1/c) / 1 = n * ((1/c) * pow(2,32)) / pow(2,32) magic = (1/c) * pow(2,32)

一般形式:

假设c不是2的幂，b为小于c的2的幂

n / c = n * (b/c) / b = n * ((b/c) * pow(2,32)) / b / pow(2,32) magic = (b/c) * pow(2,32)

前面只是介绍了编译器对除法优化的基本原理，并不是严格的数学推导。这里涉及一 个如何取整的问题，前述例子中4/7的情形是向下取整。前文没有解释如何取整，理 解其本质需要一些初等代数的知识，下文讲解得比较细:

快速立即除法的乘法实现(通用算法) - HAM [2009-10-31] http://blog.csdn.net/concreteham/article/details/4750740

如果拿0x51EB851F做关键字进行百度搜索，能找到一些从汇编角度讲解这种优化的中 文文章，其中有一篇被四处转载的，还做什么误差分析，我的建议是只看上文即可。

有一些现成的程序，在指定除数的情况下给出优化结果:

http://win32assembly.programminghorizon.com/files/magicnumber.zip http://www.masmforum.com/archive2012/6717_MagicNumber64.zip

推荐后者，比如指定除数125，得到:

mov eax,X mov edx,010624DD3h mul edx shr edx,03h ; edx = quotient

这是编译器对除法的优化，一般人这辈子都不需要关心这种优化。但是，对于逆向工 程来说，可能必须面对并理解这种优化，现有F5无法将优化结果还原成人类可读方式。

话说回来，从功利性实践角度讲，不理解优化原理也无所谓，在逆向输出中看到神密 常量，放狗搜之即可，一般秒中。

罗列这种神密常量没有意义，尤其同一除数存在多种优化方式的情况下，下面这些仅 仅是便于查找:

0xAAAAAAAB 3 2/3 0xCCCCCCCD 5 4/5 0x92492492 7 4/7 0x49249249 7 2/7 0x24924925 7 1/7 0x38E38E39 9 0x66666667 10 4/10 0x51EB851F 100 32/100 0x10624DD3 1000