能力值：
( LV3，RANK：20 )
|
-
-
6 楼
除法
两个操作数都是变量的情况无法优化, 只能用div/idiv
mov eax, dword ptr [ebp-4] ;将被除数放入eax
cdq ;将eax中的符号位扩展到edx, 即将edx:eax扩展成一个值与eax相同的64位有符号整数
idiv dword ptr [ebp-8] ;用除数去除edx:eax, 商保存在eax中, 余数在edx中
除数是2的幂
这种情况用sar优化. sar是算术右移, 即右移后左边空出来的位用符号位填充. sar相当于向下取整, 这在被除数非负时是符合要求的, 但是在被除数是负数时, 按照C的除法规则, 应该是向上取整的, 所以需要对被除数做一些调整. x<0 时, x/2^n 中的x应该被调整为 x+(2^n-1), 即把商+1, 这样再对商向下取整就符合要求了
;除2时
mov eax, dword ptr [ebp-4] ;将被除数放入eax
cdq ;将eax中的符号位扩展到edx, 即将edx:eax扩展成一个值与eax相同的64位有符号整数
sub eax, edx
;非负时, edx为0, 不改变eax; 为负数时, edx为-1, 相当于eax+1, 符合x+(2^1-1)
sar eax, 1 ;算术右移, 即左边空出来的位用符号位填充
;除数大于2时, 这里是8
mov eax, dword ptr [ebp-4] ;将被除数放入eax
cdq ;将eax中的符号位扩展到edx, 即将edx:eax扩展成一个值与eax相同的64位有符号整数
and edx, 7 ;除数非负时, edx为0, and后edx仍为0; 除数为负数时, edx为0xFFFFFFFF, and后为7
add eax, edx ;加上edx, 如果非负, edx为0, 对eax无影响; 如果为负数, 相当于eax+7, 符合x+(2^8-1)
sar eax, 3
除数不是2的幂
情况1
mov ecx, dword ptr [ebp-4] ;ecx中是被除数
mov eax, 38E38E39h
imul ecx ;x*c ,乘法结果放在edx:eax中
sar edx, 1 ;edx是乘法结果的高32位, 直接操纵它等价于乘积已经右移了32位, 因此这是乘积右移33位
mov eax, edx
shr eax, 1Fh ;右移31位, 目的是取符号位
add edx, eax ;至此, edx中就是除法的计算结果了
在这种情况下, 假设除数是o, 编译器会事先计算一个常量c=(2^n)/o, 然后对于被除数x, (x*c)>>n 就是除法的结果了. 对于n的取值, 编译器始终保证这是一个大于32的值, 这样在做乘法的时候可以提高效率.
套用公式, 上面的代码是在计算 (x*38E38E39h)>>33, 并且在结果上又加上了符号位的值, 之所以要加符号位, 是因为我们依然用的是向下取整的sar, 这在结果是非负数的时候是正确的, 但是在结果是负数时比正确值少1(比如 -3.5 本来应该取 -3 的, 它取成 -4 了), 所以结果再加上一个符号位的值就正确了.
;总结, 当遇到以下形式的语句时, 基本可判断为除法运算
mov eax, MagicNumber
imul 被除数
sar edx, a
mov eax, edx
shr eax, 1Fh
add edx, eax ;之后, 直接使用edx的值
;n=a+32, (2^n)/MagicNumber 的结果就是除数的近似值
情况2
mov ecx, dword ptr [ebp-4] ;ecx中是被除数
mov eax, 24924925h
mul ecx
sub ecx, edx
shr ecx, 1
add ecx, edx
shr ecx, 2 ;至此, ecx中是除法结果
这种情况会在编译器选定的魔数超过4字节大小时出现, 编译器会将魔数调整为2^(32+n)/o-2^32 .
化简整理上面的运算过程, 结果是 ecx * ((2^32+c) / 2^35), 如果把上面的魔数c的计算式代入的话, 还差一个n就能化简为 ecx/o 的形式了, 这个n就是ecx右移的位数, 这里是3位, 所以n=3. 代入魔数的计算式, o≈7. 验算一下, 2^35/7-2^32 正好等于魔数
;总结, 当遇到以下形式的语句时, 基本可判断为除法运算
mov reg, dword ptr [ebp-4] ;reg中是被除数
mov eax, MagicNumber
mul reg
sub reg, edx
shr reg, 1
add reg, edx
shr reg, a ;这句可能没有. 这里的a的值应该为n-1, 如果n为1, 这句没有. 至此, reg中是除法结果
;n=a+1, 除数的近似值为 (2^(32+n))/(2^32+MagicNumber)
情况3
mov esi, dword ptr [ebp-4] ;esi中是被除数
mov eax, 92492493h
imul esi
add edx, esi
sar edx, 2
mov eax, edx
shr eax, 1Fh ;负数调整+1
add edx, eax ;至此, edx中是除法结果
这种情况会在魔数大于0x80000000时出现. 魔数本应是一个无符号数, 但是参与了有符号运算, 这时符号位不计为值, 导致参与运算的实际值为 MagicNumber-2^32
;总结, 当遇到以下形式的语句时, 基本可判断为除法运算
mov reg, dword ptr [ebp-4] ;reg中是被除数
mov eax, MagicNumber ;MagicNumber大于7fffffffh
mul reg
add edx, reg
sar edx, a
mov reg, edx
shr reg, 1Fh
add edx, reg ;至此, edx是除法结果
;n=a+32, (2^n)/MagicNumber 的结果就是除数的近似值
除数为负的2的幂
mov eax, dword ptr [ebp-4] ;将被除数放入eax
cdq
and edx, 7
add eax, edx
sar eax, 3 ;上面是除数为2的幂时的运算
neg eax ;对结果取反
;这相当于把 n/(-o) 变成了 -(n/o)
除数为负的非2的幂
情况1
mov ecx, dword ptr [ebp-4] ;将被除数放入ecx
mov eax, 99999999h
imul ecx
sar edx, 1
mov eax, edx
shr eax, 1Fh
add edx, eax ;至此, edx中为除法结果
首先注意这和除数大于0且不为2的幂时的区别: 虽然魔数大于0x7fffffff, 但是imul和sar直接并没有调整语句, 此时基本可以判断这是除数为负数的情况.
此时的魔数实际上补码形式. 当除数o为正数时, 设魔数c=2^n/o; 当o为负数时, -c=2^32-2^n/|o| ==> |o|=2^n/(2^32-c)
;总结, 当遇到以下形式的语句时, 基本可判断为除法运算
mov reg, dword ptr [ebp-4] ;reg中是被除数
mov eax, MagicNumber ;MagicNumber大于7fffffffh且imul与sar之间没有调整语句
imul reg
sar edx, a
mov reg, edx
shr reg, 1Fh
add edx, reg ;至此, edx是除法结果
;n=a+32, -((2^n)/(2^32-MagicNumber)) 的结果就是除数的近似值
情况2
mov ecx, dword ptr [ebp-4] ;将被除数放入ecx
mov eax, 6DB6DB6Dh
imul ecx
sub edx, ecx
sar edx, 2
mov eax, edx
shr eax, 1Fh
add edx, eax ;至此, edx中为除法结果
上面的运算过程化简之后可得 ecx* ((eax-2^32)/2^34) = edx, 因为edx中是除法结果, 所以 ecx* ((eax-2^32)/2^34) = ecx/o . 可得 |o| = 2^n / (2^32 - c) = 2^34 / 92492493h ≈ 7
;总结, 当遇到以下形式的语句时, 基本可判断为除法运算
mov reg, dword ptr [ebp-4] ;reg中是被除数
mov eax, MagicNumber ;MagicNumber小于7fffffffh且imul与sar之间有调整语句sub
imul reg
sub edx, reg
sar edx, a
mov reg, edx
shr reg, 1Fh
add edx, reg ;至此, edx是除法结果
;n=a+32, -((2^n)/(2^32-MagicNumber)) 的结果就是除数的近似值
|
