# Chapter 14 Division by 9 下面是一個非常簡單的函數 ``` #!bash int f(int a) { return a/9; }; ``` ## 14.1 x86 以一種十分容易預測的方式編譯的 ``` #!bash _a$ = 8 ; size = 4 _f PROC push ebp mov ebp, esp mov eax, DWORD PTR _a$[ebp] cdq ; sign extend EAX to EDX:EAX mov ecx, 9 idiv ecx pop ebp ret 0 _f ENDP ``` IDIV 有符號數除法指令 64位的被除數分存在兩個寄存器EDX:EAX,除數放在單個寄存器ECX中。運算結束后，商放在EAX，余數放在EDX。f（）函數的返回值將包含在eax寄存器中，也就是說，在進行除法運算之后，值不會再放到其他位置，它已經在合適的地方了。正因為IDIV指令要求被除數分存在EDX：EAX里，所以需要在做除法前用CDQ指令將EAX中的值擴展成64位有符號數，就像MOVSX指令(13.1.1)所做的一樣。如果我們切換到優化模式（/0x），我們會得到 清單14.2:MSVC優化模式 ``` #!bash _a$ = 8 ; size = 4 _f PROC mov ecx, DWORD PTR _a$[esp-4] mov eax, 954437177 ; 38e38e39H imul ecx sar edx, 1 mov eax, edx shr eax, 31 ; 0000001fH add eax, edx ret 0 _f ENDP ``` 這里將除法優化為乘法。乘法運算要快得多。使用這種技巧可以得到更高效的代碼。 在編譯器優化中，這也稱為“strength reduction” GCC4.4.1甚至在沒有打開優化模式的情況下生成了和在MSVC下打開優化模式的生成的幾乎一樣的代碼。 清單14.3 GCC 4.4.1 非優化模式 ``` #!bash public f f procnear arg_0 = dword ptr 8 push ebp mov ebp, esp mov ecx, [ebp+arg_0] mov edx, 954437177 ; 38E38E39h mov eax, ecx imul edx sar edx, 1 mov eax, ecx sar eax, 1Fh mov ecx, edx sub ecx, eax mov eax, ecx pop ebp retn f endp ``` ## 14.2 ARM ARM處理器，就像其他的“純”RISC處理器一樣，缺少除法指令，缺少32位常數乘法的單條指令。利用一個技巧，通過加法，減法，移位是可以實現除法的。 這里有一個32位數被10（20，3.3常量除法）除的例子，輸出商和余數。 ``` #!bash ; takes argument in a1 ; returns quotient in a1, remainder in a2 ; cycles could be saved if only divide or remainder is required SUB a2, a1, #10 ; keep (x-10) for later SUB a1, a1, a1, lsr #2 ADD a1, a1, a1, lsr #4 ADD a1, a1, a1, lsr #8 ADD a1, a1, a1, lsr #16 MOV a1, a1, lsr #3 ADD a3, a1, a1, asl #2 SUBS a2, a2, a3, asl #1 ; calc (x-10) - (x/10)*10 ADDPL a1, a1, #1 ; fix-up quotient ADDMI a2, a2, #10 ; fix-up remainder MOV pc, lr ``` ### 14.2.1 Xcode優化模式（LLVM）+ARM模式 ``` #!bash __text:00002C58 39 1E 08 E3 E3 18 43 E3 MOV R1, 0x38E38E39 __text:00002C60 10 F1 50 E7 SMMUL R0, R0, R1 __text:00002C64 C0 10 A0 E1 MOV R1, R0,ASR#1 __text:00002C68 A0 0F 81 E0 ADD R0, R1, R0,LSR#31 __text:00002C6C 1E FF 2F E1 BX LR ``` 運行原理 這里的代碼和優化模式的MSVC和GCC生成的基本相同。顯然，LLVM在產生常量上使用相同的算法。 善于觀察的讀者可能會問，MOV指令是如何將32位數值寫入寄存器中的，因為這在ARM模式下是不可能的。實際上是可能的，但是，就像我們看到的，與標準指令每條有四個字節不同的是，這里的每條指令有8個字節，其實這是兩條指令。第一條指令將值0x8E39裝入寄存器的低十六位，第二條指令是MOVT,它將0x383E裝入寄存器的高16位。IDA知道這些順序，并且為了精簡緊湊，將它精簡轉換成一條偽代碼。 SMMUL (Signed Most Significant Word Multiply)實現兩個32位有符號數的乘法，并且將高32位的部分放在r0中，棄掉結果的低32位部分。 ``` “MOV R1,R0,ASR#1“指令算數右移一位。 “ADD R0,R1,LSR#31” R0=R1+R0>>32 ``` 事實上，在ARM模式下，并沒有單獨的移位指令。相反，像（MOV,ADD,SUB,RSB）3 這樣的數據處理指令，第二個操作數需要被移位。ASR表示算數右移，LSR表示邏輯右移。 ### 14.2.2 優化 Xcode(LLVM)+thumb-2 模式 ``` #!bash MOV R1, 0x38E38E39 SMMUL.W R0, R0, R1 ASRS R1, R0, #1 ADD.W R0, R1, R0,LSR#31 BX LR ``` 在thumb模式下有些單獨的移位指令，這個例子中使用了ASRS（算數右移） ### 14.2.3 Xcode非優化模式（LLVM） keil模式 非優化模式 LLVM不生成我們之前看到的那樣的代碼，它插入了一個調用庫函數的`call __divsi3` 關于keil：通常插入一個調用庫函數的`call __aeabi_idivmod` ## 14.3 工作原理 下面展示的是怎樣用乘法來優化除法，其中借助了2^n的階乘  M是一個magic系數 M的計算過程  因此這些代碼片段通常具有這樣的形式  n可以是任意數，可能是32（那么這樣運算結果的高位部分從EX或者RDX寄存器中獲取），可能是31（這種情況下乘法結果的高位部分結果右移） n的選取是為了減少錯誤。 當進行有符號數除法運算，乘法結果的符號也會被放到輸出結果中。 下面來看看不同之處。 ``` #!bash int f3_32_signed(int a) { return a/3; }; unsigned int f3_32_unsigned(unsigned int a) { return a/3; }; ``` 在無符號版本的函數中，magic系數是0xAAAAAAAB，乘法結果被2^3*3除。 在有符號版本的函數中，magic系數是0x55555556，乘法結果被2^32除。 符號來自于乘法結果：高32位的結果右移31位（將符號位放在EAX中最不重要的位置）。如果最后結果為負，則會設置為1。 清單14.4：MSVC 2012/OX ``` #!bash _f3_32_unsigned PROC mov eax, -1431655765 ; aaaaaaabH mul DWORD PTR _a$[esp-4] ; unsigned multiply shr edx, 1 mov eax, edx ret 0 _f3_32_unsigned ENDP _f3_32_signed PROC mov eax, 1431655766 ; 55555556H imul DWORD PTR _a$[esp-4] ; signed multiply mov eax, edx shr eax, 31 ; 0000001fH add eax, edx ; add 1 if sign is negative ret 0 _f3_32_signed ENDP ``` ## 14.4 得到除數 ### 14.4.1 變形＃1 通常，代碼具有這樣一種形式 ``` #!bash mov eax, MAGICAL CONSTANT imul input value sar edx, SHIFTING COEFFICIENT ; signed division by 2^x using arithmetic shift right mov eax, edx shr eax, 31 add eax, edx ``` 我們將32位的magic系數表示為M，移位表示為C，除數表示為D 我們得到的除法是  舉個例子 清單14.5：優化模式 MSVC2012 ``` #!bash mov eax, 2021161081 ; 78787879H imul DWORD PTR _a$[esp-4] sar edx, 3 mov eax, edx shr eax, 31 ; 0000001fH add eax, edx ``` 即  比32位的數字大，為了方便，于是我們使用用Wolfram Mathematica軟件。 ``` In[1]:=N[2^(32+3)/2021161081] Out[1]:=17. ``` 因此例子中的代碼得到結果是17。 對于64位除法來說，原理是一樣的，但是應該使用2^64來代替2^32。 ``` #!bash uint64_t f1234(uint64_t a) { return a/1234; }; ``` 清單14.7：MSVC2012/Ox ``` #!bash f1234 PROC mov rax, 7653754429286296943 ; 6a37991a23aead6fH mul rcx shr rdx, 9 mov rax, rdx ret 0 f1234 ENDP ``` 清單14.8：Wolfram Mathematica ``` In[1]:=N[2^(64+9)/16^^6a37991a23aead6f] Out[1]:=1234. ``` ### 14.4.2 變形＃2 忽略算數移位的變形也是存在的 ``` #!bash mov eax, 55555556h ; 1431655766 imul ecx mov eax, edx shr eax, 1Fh ``` 更加簡潔  在這個例子中  再用一次Wolfram Mathematica ``` In[1]:=N[2^32/16^^55555556] Out[1]:=3. ``` 得到的除數是3