|
|
|---|---|
|
|
|
|
|
先附上参考资料：
1. Concrete Mathematics - Ronald L. Graham 2. The Art of Computer Programming - Donald E. Knuth 3. divcnst-pldi94.pdf (感谢forgot提供) 4. The Solver Web Online Help - ? (a8fK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4c8Z5k6i4y4G2L8s2k6W2M7W2)9J5k6h3W2@1i4K6u0r3e0h3q4F1N6h3q4D9K9g2)9J5c8V1k6S2j5%4c8G2N6s2g2E0i4K6u0r3M7$3!0#2M7X3y4W2i4K6u0r3x3o6l9I4i4K6u0W2K9s2c8E0 感谢bughoho提供) 由于本人没学会如何将word中的数学公式转换为论坛格式，故以下讨论用抓图表达。   
|
|
|
以下数学相关的定义和推导，若已掌握或者暂无兴趣，可跳过本节阅读其后的讨论，在后面的讨论中，涉及到的定义和推导将会以编号形式指出，感兴趣的读者可以回到本节考察相关推论和证明。
    
|
|
|
3. VC++6.0对整数除法的优化和论证
A. VC++6.0 对除以整型常量的各类处理 整数除法运算对应汇编指令分有符号idiv、无符号div。除法是指令中执行周期较长的，因此其效率也是较低的，所以编译器会尽量将除法指令用其它运算指令代替。C++中的除法和数学中的除法不同。在C++中除法运算不保留余数，有专门提求取余数的运算“%”也称之为取模运算。而且对于整数除法，C++的规则是仅仅保留整数部分，小数部分完全舍弃。 如果除数是变量，则只能使用除法指令。但是如果除数为常量，便有了优化的余地，根据除数值的相关特性，编译器有对应的处理方式。 在本节我们讨论编译其对除数为2的次方、非2次方、负数等各类情景的处理方式，我们假定整型为4字节补码形式。 见代码中实例演示。 各类型除法转换——Debug调试版 // C++源码说明：除法运算
// 变量定义
int nVarOne = argc;
int nVarTwo = argc;
// 两变量做除法
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);
// 变量除以常量，常量2的1次方
printf("nVarOne / 2 = %d", nVarOne / 2);
// 变量除以非二次方数
printf("nVarTwo / 7 = %d", nVarTwo / 7);
// 变量对非二次方数取模
printf("nVarTwo % 7 = %d", nVarTwo % 7);
// 变量除以常量，常量为2的3次方
printf("nVarOne / 8 = %d", nVarOne / 8);// C++源码于对应汇编代码讲解
// C++源码对比，变量定义
int nVarOne = argc;
0040B7E8 mov eax,dword ptr [ebp+8]
0040B7EB mov dword ptr [ebp-4],eax
// C++源码对比，变量定义
37: int nVarTwo = argc;
0040B7EE mov ecx,dword ptr [ebp+8]
0040B7F1 mov dword ptr [ebp-8],ecx
// 除法运算转换特性
// C++源码对比，变量 / 变量
printf("nVarOne / nVarTwo = %d", nVarOne / nVarTwo);
; 取出被除数放入eax中
0040B7F4 mov eax,dword ptr [ebp-4]
; 扩展高位
0040B7F7 cdq
; 两变量相除，直接使用有符号除法指令idiv
0040B7F8 idiv eax,dword ptr [ebp-8]
; eax保存商值，作为参数压栈，调用函数printf，此函数讲解略
0040B7FB push eax
0040B7FC push offset string "nVarOne / nVarTwo = %d" (00420034)
0040B801 call printf (0040b750)
0040B806 add esp,8// C++源码对比，变量 / 常量（常量值为2）
printf("nVarOne / 2 = %d", nVarOne / 2);
0040B809 mov eax,dword ptr [ebp-4]
0040B80C cdq
; 自身减去扩展高位
0040B80D sub eax,edx
; 和乘法运算类似，乘法是左移，对应的除法为右移
0040B80F sar eax,1
; printf 函数说明略…… // C++源码对比，变量 / 常量（常量值为2的3次方）
printf("nVarOne / 8 = %d", nVarOne / 8);
; 取出被除数放入eax
0040B851 mov eax,dword ptr [ebp-4]
; 扩展eax高位到edx，eax中为负数则edx为0xFFFFFFFF
0040B854 cdq
; 如果eax为负数，则0xFFFFFFFF & 0x00000007 <==> 0x00000007 反之为0
0040B855 and edx,7
; 使用eax加edx，如eax为负数则加7，反之加0
0040B858 add eax,edx
; 将eax右移3位
0040B85A sar eax,3
; printf 函数说明略……没有打开O2的时候下，以上代码中只有除数为2 的次方值的前提下，才进行了优化处理。我们先从最为较简单的除以常量2的优化开始分析。  
|
|
|
 
|
|
|
 
|
|
|
回顾代码清单中的关键部分：
…… ; 92492493h疑似 .text:004010AA mov eax, 92492493h ; 这里是流水线优化，esp和上次调用的call指令相关，和除法计算无关，可暂不理会。 .text:004010AF add esp, 8 ; 有符号乘法，用esi乘以eax，esi中保存被除数 .text:004010B2 imul esi ; 这里又多出一个诡异的加法 .text:004010B4 add edx, esi ; 右移2位，也可看作除4 .text:004010B6 sar edx, 2 ; 结果给eax .text:004010B9 mov eax, edx ; 负数调整加1 .text:004010BB shr eax, 1Fh .text:004010BE add edx, eax .text:004010C0 push edx .text:004010C1 push offset aNvartwo7D ; "nVarTwo / 7 = %d" .text:004010C6 call _printf ……   
|
|
|
123456
|
|
|
4. 除数为负的非二次方（上）
.text:00401000 _main proc near ; CODE XREF: start+AFp .text:00401000 arg_0= dword ptr 4 .text:00401000 mov ecx, [esp+arg_0] [B].text:00401004 mov eax, 99999999h[/B] .text:00401009 imul ecx .text:0040100B sar edx, 1 .text:0040100D mov eax, edx .text:0040100F shr eax, 1Fh .text:00401012 add edx, eax .text:00401014 push edx .text:00401015 push offset Format ; "%d\n" .text:0040101A call _printf .text:0040101F add esp, 8 .text:00401022 xor eax, eax .text:00401024 retn .text:00401024 _main endp 对于负除数求值过程中，有什么需要注意的呢？我们先看看除法转乘法的过程：  
|
|
|
5. 除数为负的非二次方（下）
上例中我们讨论了对于Magic Number大于0x7fffffff的处理，那么在什么情况下 Magic Number会小于等于0x7fffffff，而且这个时候应该怎么处理呢？请先阅读以下代码： .text:00401000 _main proc near ; CODE XREF: start+AFp .text:00401000 arg_0= dword ptr 4 .text:00401000 mov ecx, [esp+arg_0] .text:00401004 mov eax, 6DB6DB6Dh .text:00401009 imul ecx .text:0040100B sub edx, ecx .text:0040100D sar edx, 2 .text:00401010 mov eax, edx .text:00401012 shr eax, 1Fh .text:00401015 add edx, eax .text:00401017 push edx .text:00401018 push offset Format ; "%d" .text:0040101D call _printf .text:00401022 add esp, 8 .text:00401025 retn .text:00401025 _main endp 回忆前面除数等于+7的讨论，对于正除数，Magic Number大于0x7fffffff的处理：  
|
|
|
B. 除法优化的原则(上)
看到这里，大家应该注意到以上讨论并还原除数的结果是近似值，说明了我们的公式给出还不够严格，那么我们可以好好思考一下其值近似但不等的原因，先看看余数是多少。 回忆一下除法和余数的关系，根据（性质3），有： b =(a - r) / q  
|
|
|
 
|
|
|
|
|
|
 前两天上课讲的这么快就放上来了啊？不知道ImageBase是哪位童鞋啊？ 
|
|
|
|
|
|
座等学习
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
说明环境，方便读者测试
占楼学习 |
|
|
学习了
|
