3种移位:
逻辑右移 >>
逻辑左移 <<
算术右移 >> (针对有符号数,高位补符号)
计算机中的除法是整除 ,整除带来的问题就是取整
对于正数来说: 向下取整
对于负数来说: 向上取整
因此计算机除法是 向0取整
0011 2 >> 1 0001 => 1 向下取整
1101 -3 >> 1 1110 => -2 向下取整
从上面可以看出,右移是向下取整的
除法的优化
除法优化的前提是除数是常量
伪造出来的M 计算结果可能精度不够, 计算 除数是 精度 应该是小数点后 6个9再取整
计算除数:
根据 M值 来判断
\1. 正数 y = 2^n / M
\2. 负数 y = 2^n / (2^32 - M）
\3. 溢出 y = 2^n / (2^32 + M）
1. 除数为无符号2的幂/
在cpu中,移位的效率高于算术运算
对于无符号数来说因此右移可以取代除法,因为 2者的 取整方式一样,
x / 2^n = x >> n
2. 除数为有符号2的幂
当除数为正数时,跟上面的一致,当x位负数时,取整方向发生了改变,因此需要把向下取整转为向上取整
下整转上整方式:
- 结果 + 1
- 被除数 + 一个数 2^n - 1 (调大被除数,结果也会变大),
例如: -10 / 4 向上取整 = (-10 + 3) / 4 向下取整
x >= 0
x / 2^n = (x + 0) >> n
x < 0
x / 2^n = (x + 2^n-1) >> n
分支慢的原因是因为会断流水线
指令实现无分支 正数 + 0 ,负数 + 15
cdq 这条指令 只有 intel 的cpu才有,因此跨平台的不能用这条指令
方法1:
mov eax, esi
cdq
and edx, 0Fh
add eax, edx
sar eax, 4
方法2:
mov edx, eax
sar edx, 31
and edx, 15
add eax, edx
sar eax, 4
方法3:
mov edx, eax
sar edx, 31 //正数全0 ,负数全1
shr edx, 28 // 高位补0
add eax, edx
sar eax, 4
3. 除数为有符号-2的幂
x / - 2^n = - ( x / 2^n )
4. 无符号非2的幂1
编译器是先乘一个数,再来位移 ,这个数编译器会先算出来 Magic Numbe
x / y = ( x * M ) >> n
=>
y = 2^n / M
对于32位系统来说 n 是一个 大于 32 的值 ,64位系统来说就是 大于64的值
5. 有符号非2的幂1 M >= 0
当 x 小于0 需要把向下取整转成向上取整, 而 向上取整 = 向下取整 + 1
所以 此公式 就变成了 x >= 0 结果 +0 和 x< 0 结果 + 1 的问题
x >= 0
x / y = (x * M) >> n + 0
x < 0
x / y = ((x * M) >> n) + 1
=>
y = 2^n / M
这个公式是最常见的 ,基本占 70% ~ 80%
无分支实现 正数 +0 负数 +1
mov eax , edx
shr eax , 1Fh ;取符号位
add eax , edx
6. 有符号负非2的幂1 M < 0
此式跟上式的区别就是 Magic Numbe 的最高位是 1
x / -y = ( x * -M ) >> n + 0
=>
y = 2^n / (2^32 - M）
7. 有符号非2的幂2 M < 0
取 Magic Numbe 值较大,本来是正数 ,但是因为是有符号,在 乘 的时候被当成了负数 ,此时计算结果会变小(变成了负数), 因此需要加上 变小的差值
x >= 0
x / y = (((x * M) >> 32) + x >> n) + 0
x < 0
x / y = (((x * M) >> 32) + x >> n) + 1
=>
y = 2^n / M
8. 有符号负非2的幂2 M >= 0
求负数的时候,就会造成 M >=0 (对M求完补码溢出变正数) ,此时计算结果会变大, 因此需要减去 变大的差值
x >= 0
x / y = (((x * M) >> 32) - x >> n) + 0
x < 0
x / y = (((x * M) >> 32) - x >> n) + 1
=>
y = 2^n / (2^32 - M）
9. 无符号非2的幂2
因为是无符号 Magic Numbe 可能会是一个很大很大的数， 乘完之后结果放不下，因此需要 分2次乘 2此移
公式： mul sub shr add shr
x / y = (x - (x * M) >> 32) >> n1) + (x * M >> 32) >> n2
=》
y = 2^n / (2^32 + M）
总结
当我们碰到一个除法，首先判断 除数是不是 2的 幂 ，不满足就看第二个公式（4.，5，6），还不满足就看 + （7） - （9） ，还不满足就看是否满足 乘 减 移 加 移 （9）
int n1 = 0;
int n2 = 0;
int n3 = 0;
scanf_s("%d %d", &n1, &n2);
n3 = (n1 / 7) * (n2 / 8) + (n2 / 5);
printf("%d\n", n3);
反汇编代码：
lea eax, [ebp+var_8]
mov dword ptr [ebp+Arglist], 0
push eax
lea eax, [ebp+Arglist]
mov [ebp+var_8], 0
push eax ; Arglist
push offset aDD ; "%d %d"
call sub_401050
mov eax, [ebp+var_8]
cdq
and edx, 7
lea edi, [edx+eax]
mov eax, 92492493h
imul dword ptr [ebp+Arglist]
mov eax, 66666667h
sar edi, 3 ； edi = n2 / 8
add edx, dword ptr [ebp+Arglist]
sar edx, 2
mov ecx, edx
shr ecx, 1Fh
add ecx, edx ; ecx = n1/7
imul [ebp+var_8]
imul edi, ecx ; edi = (n2 / 8) * (n1/7)
mov eax, edx
shr eax, 1Fh
add edi, edx ; edi = (n2 / 8) (n1/7) + ( n2 M >> n )
add eax, edi ; eax = (n2 / 8) (n1/7) + ( n2 M >> n ) +1
push eax
push offset Format ; "%d\n"
call sub_401020
=> edi = (n2 / 8) (n1 / 7) +( n2 M >> 32 ) +1
=> (n2 / 8) * (n1 / 7) + ( ( n2 * M >> n ) +1 )
=> (n2 / 8) * ( n1 / 7 ) + ( n2 / 5 )
取模
一个数 % 该数进制的 n 次幂 = 取 该数的 低 n-1 位
1.有符号模2的幂1 (新公式)
x >= 0
x % 2^n = x & 2^n - 1
x < 0 ；把负数变正数 （先加一个数再减去该数）
x % 2^n = x + ( 2^n - 1 & 2^n - 1 ) - 2^n - 1
例如： -6 % 8 = - 6 + 7 & 7 - 7
无分支实现
mov eax, ecx
cdq
and edx, 2^n-1
add ecx, edx
and ecx, 2^n-1
sub ecx edx
2.模2的幂2 (旧公式)
jns 分支跳转
if (x > 0)
x & 2^n - 1
else
(x - 1) | ~(2^n - 1) + 1
上式无法实现无分支是因为 没有规律
3.模非2的幂
x % y = z
=》
z = x - ( x / y ) * y
识别操作数符号
跳转指令 Jxx A B (无符号) (L G) 有符号
乘法 除法 有符号(i) 无符号(无)
加法减法不区分符号 (补码 把减法转成了 加法)
补码能取代减法 是因为 膜
膜最早出现再手表中: 代表可表示数的极限值 例如手表是 12
例如 要表示 3点 - 2点 = 1点 =》 3点 + （ 12点 - 2点 ） = 1点
即 一个数 - 另一个数 = 一个数 + （ 膜 - 另一个数 ）
补码是为了迅速求出 膜 - 另一个数
IDA的使用
颜色条
表示整个软件的代码的分析结果
粉色： 表示导入表（这个节的代码不需要还原）
蓝色： 用户写的代码 （需要还原的代码）,IDA可能会把库函数识别成自己的代码
浅蓝色：库函数（静态链接进来的）（不需要还原）
灰色： 数据
浅黄色：数据 ：全局数据区
图视图
方便快速看分支
一个方格代表一个代码块
当代码量很大的时候，可能无法画出图视图
上面的图可以看作
if elseif 为了方便看清结构，可以转化成 if else 的嵌套，因为 if elseif 的图视图 结构比较复杂不便于理解
缩略图
快速了解代码结构
IDA调试
下断点： 选中行 F2 或者 F5 再 F2下断点
快捷键和 OD一样
雷达卡
发表于 2025-5-7 22:22:12
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶