一丶除法简介
除法,在汇编中是 DIV 指令 跟 IDIV指令,跟乘法一样.指令周期时间长.所以也必须进行优化.
但是除法的优化有很多原理.也就是很复杂. 逆向工作人员.也要搞清楚除法才算是真正的入了逆向的的小门.
除法搞不定.以后代码还原.等等.自己根本还原不了.有人说 可以使用IDA静态分析工具. F5插件. 我可以告诉你
F5搞不定除法的.会给你还原的乱七八糟.还不如看汇编.所以这也是我们必须搞定的.
二丶简介除法原理
除法原理是由数学上来决定的.也就是说.优化是按照数学公式来定的.这也早就了.不管你是VC6.0写的程序
还是VS2017等更高版本写的程序.都不会有很大变化.原因是.这种优化已经是最优的优化了.除非数学上有很大
变动.(不可能的.如果有就是数学界的一大震动)否则不会改变的.还有一种情况就是.CPU越来越好.优化的时候
使用了新指令了. 新指令进行优化.不过占很小一部分.因为如果都是新指令优化.那么这个程序就没法兼容以前系统了
1.搞明白数学中的向上取整 向下取整. 以及程序中的向零取整.
首先画出一个坐标系,如下:
-∞ 0 +∞
<-------------*------------------>
向下取整:
向下取整就是往负无穷方向接近 x的数值. 不大于x的最大整数. 例如x为3.5 那么往负无穷接近,不大于
3.5的最大整数是多少. 是3.
-3.5向下取整就是-4 向上取整就是-3
在C语言中是 floor函数. 向下取整也称为地板取整
向上取整:
向上取整就是往正无穷接近 x的数值. 不小于x的最大整数. 例如3.5 向上取整就是4
向上取整在C语言中是ceil()函数.也成为天花板取整
向零取整:
向零取整就很简单了.可以理解为 正数是向下取整, 负数是向上取整.反正靠近0就可以.
向零取整是计算机整数除法规定的.计算机会使用这种除法.也称为截断除法.
疑问?
为什么要学习取整.虽说取整很简单.原因是在计算机中.除法都是向零取整的除法.
例如我们上面说过的向下取整. 假设: a为被除数 b为除数 那么
公式: ⌊-a/b⌋ ≠ -⌊a/b⌋
我们可以带入计算:
-7 / 2 = -3.5 向下取整 = -4
-⌊7/2⌋ = -3 首先计算出 7 / 2 = 3.5 向下取整则是3 外面有个负号 所以是-3
向上取整问题:
向上取整是一样的.结果也是不一样.
公式: ⌈-a/b⌉ ≠ -⌈a/b⌉
一样代入
⌈-7/2⌉ = -3
-⌈7/2⌉ = -4
向零取整:
计算机中的除法就是整数除法,就是向零取整.
[-a / b] = [a / -b] = -[a / b]
我们可以代入公式:
[-7 / 2] = -3
[7 / -2] = -3
-[7 / 2] = -3
所以三个公式是一样的.
所以必须要了解取整.
2.除法的扩展知识
除法的扩展知识:
在整数的除法中,只有能整除和不能整除的两种情况则会产生余数.
设 a = 被除数 b = 除数 c = 商 r = 余数
那么可以得到下面的公式:
除法原型:
a / b = c .... r
6 / 4 = 1 ...2
-
|r| < |b| : 余数的绝对值,绝对会小于除数的. 比如 6 / 4 = 1 .... 2 那么 余数2 不关是正数还是负数,绝对都是绝对会小于除数的,也就是4
-
a = q * b + r : 求被除数,被除数是商*除数+余数
-
b = (a - r)/c : 求除数,除数等于 被除数-余数 / 商
-
q = (a - r)/b : 求商: 被除数 - 余数 / 除数
-
r = a - (q * b) : 求余数 被除数 - (商 * 除数)
三丶除法的代码还原.
有了以上的公式支撑.那么我们则可以进行除法的代码还原的学习了.
1.除数为2的一次方
高级代码:
int main(int argc, char* argv[])
{
int nValue = 10;
scanf("%d",&nValue); //防止变量nValue优化成常量. 所以不让他优化
int nTemp = nValue / 2; //常量是2的一次方 重要代码
scanf("%d",&nTemp);//防止优化
return 0;
}
Debug下的汇编
.text:00401280 mov eax, [ebp+var_4]
.text:00401283 cdq
.text:00401284 sub eax, edx 重要代码
.text:00401286 sar eax, 1
其实如果是2的1次方,Debug跟Release下.都会产生代码定式.
代码定式:
mov reg,[ebp - ?]; 获得被除数 reg存放的是被除数的值
cdq 符号扩展. 被除数是负数,那么 扩展符号位之后 edx = 0xFFFFFFFF 也就是-1 否则就是0
sub eax,edx 调整符号位,被除数是正数,那么此条语句执行完相当于没制定. 被除数是负数. 则会形成 (被除数 - 1) 因为是负数.所以被除数是补码形式存在
sar eax,1 sar相当于向下取整. sar是有符号右移,右移一位就是 / 2
代码定式可以进行总结:
mov eax,[ebp - ?]
cdq
sub eax,edx
sar eax, B
还原方法:
除数的还原 = 2^b次方
被除数的还原: = 被除数就是eax 如果是补码,则是负数. 且cdq之后 edx肯定是 0xFF... 也就是-1
还原原理:
设a 是被除数
设b 是除数
则有下面公式:
b > 0 则有下面公式
b < 0 则有下面的公式
关于证明我就不说了.具体可以看下 钱林松的 <<C++反汇编与逆向分析技术揭秘>>这本书.
有了以上公式,那么上面的汇编代码则能看明白了.
假设:
7 / 2 = 3..1 这个是数学上的公式.
7 / 2 = 3 这个是计算机中的整数除法.向零取整.
根据以上公式, b > 0. b是除数. 也就是2, 它的大于0的. 所以我们使用第一条公式.
向下取整(a / b) = 向上取整 ( (a - b + 1) / b); 或者使用
向上取整(a / b) = 向下取整 ((a + b -1) / b);
带入公式可以得出:
向上取整((7 - 2 + 1) / 2) = 3; 结果就是对的.
向下取整((7 + 2 - 1) / 2) = 3; 结果也是对的.
那么汇编定力我们就能看明白.
mov eax,[ebp - ?]
cdq
sub eax,edx 调整商,被除数是负数.那么商也是负数.
sar eax, n 向下取整
代入公式:
向下取整((eax + eax - edx(-1 or 0)) / 2^n)
b > 0,那么使用第一条公式即可. 被除数是正数. 那么edx就是0
向下取整((10 + 2^n - 0) / 2^1)
= (10 + 2 - 0) / 2
= 12 / 2
= 6
= 向下取整(6)
= 5 商
所以不懂公式,那么直接进行最笨的方法,记下来.怎么还原即可.
总结:
除数为2的一次方
汇编定式:
mov eax,[ebp - ?]
cdq
sub eax,edx
sar eax, n
还原方法: a + b - 1 (-1 or 0)
向下取整(eax + 2^n - edx) / 2^n) 根据公式还原.
不使用公式:
除数: 2^n
被除数: eax
商:
被除数为正:
eax / 2^n
被除数为负数:
(eax -1) / 2^n次方.
一定注意.当被除数为 负数的时候才会使用 公式:
a/b = (a + b - 1)/b
如果被除数是正数
a/b = a >> n 例如: a = 4 b = 2; 那么就是 4/2 = 4 >> 1位. 其实n其实就是b平方表现形式. b^n
a/b = a >> b 5 / 2 = 5 >> 1(b^n 取n的值)
2.除数为2的幂
高级代码:
int main(int argc, char* argv[])
{
int nValue = 16;
scanf("%d",&nValue);// 防止优化.核心代码不是这个
int nTemp = nValue / 8; //核心代码 一会观看反汇编
scanf("%d",&nTemp); //防止优化
return 0;
}
Debug下的汇编跟Release汇编一样,Release有流水线优化代码.去掉则会跟Debug下汇编一样.
产生以下汇编代码
.text:00401040 mov eax, [ebp+var_4] 获得被除数
.text:00401043 cdq 符号扩展 eax,edx 被除数为正, edx = 0, 否则 edx = -1
.text:00401044 and edx, 7 位与运算.被除数为正数,此条指令没用,因为edx = 0. 0 & 7还是0 被除数为负数 edx结果为7
.text:00401047 add eax, edx (eax + edx)/2^n edx = 0 则被除数是0 edx = -1 则被除数是负数. 且公式会有改变 (eax + 7) / 2^n
.text:00401049 sar eax, 3
我们观看这个代码可以产生代码定式:
.text:00401040 mov eax, [ebp+var_4]
.text:00401043 cdq
.text:00401044 and edx, b^n - 1
.text:00401047 add eax, edx
.text:00401049 sar eax, n
除数的还原: (2^n - 1) == b 那么被除数就是2^n次方
主要是还原除数.
被除数就是eax,判断正负看是否是补码就可以.
原理同上.这里也是一个无条件分支.
解析:
当 a(eax) > 0的时候. 且 b > 0 的时候 带入公式 a / b = a >> n n = b的幂数.
当 a(eax) <0 的时候 且b > 0的时候. 有公式 a/b = (a +b - 1)/b 向下取整
所以仔细看汇编代码.
cdq 根据 a的值 扩展到edx中. a>0 则 edx = 0; a < 0 则edx = -1
从cdq开始就开始做无条件分支了
如果 eax(a) < 0
那么执行的汇编就为
mov eax, [ebp+var_4]
cdq
and edx,b^n-1 === edx = b - 1
add eax,edx ===> eax + edx === eax + b - 1
sar eax,1 ===> eax + edx == (eax + b - 1) / b
如果是正数 那么就好办了. 直接公式 a / b = a >> n
执行的汇编为
mov eax,[xxx]
....
.... 为负数才会执行的代码.不写了.写了执行也跟没执行一样. 所以就是两句代码.
....
sar eax,1
四丶除法第一讲总结
今天主要就是讲了两个除法的还原.除法很多.但是鉴于篇幅.一个博客只更新两个.便于以后复习,也便于
自己的理解.
1.除数是2的一次方
mov eax,[ebp - ?]
cdq
sub eax,edx
sar eax, n
除数进行还原: 2^n
被除数: eax eax是补码,则商为负,则 sub eax,edx会执行. 被除数为负数 edx = -1 正数为0
sub eax,edx也是判断被除数是否为正负数.而进行的无分支优化.
除法原理:
b > 0 也就是除数大于0
使用公式:
如果代入公式则是: 向下取整((eax + 2^n - edx) / 2^n) 或者使用 向上取整((a - 2^n + edx) / 2^n);
b < 0 则有下面的公式
2.除数为2的幂总结:
代码定式:
.text:00401040 mov eax, [ebp+var_4]
.text:00401043 cdq
.text:00401044 and edx, b
.text:00401047 add eax, edx
.text:00401049 sar eax, n
除数的还原: 如果: (2^n - 1) == b 那么被除数就是2^n次方
主要是还原除数.
被除数就是eax,判断正负看是否是补码就可以.
eax == 正数 且 b > 0的时候 执行的公式就是 a/b = (a + b - 1) / b
eax == 负数 且 b > 0的时候 执行的公式就是 a/b = a > n
所以汇编代码还原的逆向.还是要根据数学定理来还原.一定核心数学定理就是如下.此博客只是讲解了第一种数学定理
,汇编根据数学的表现形式
b > 0 则有下面公式
b < 0 则有下面的公式