需要解釋K＆R fahr-to-cels的彙編指令示例

Question

我被卡在學習彙編語言的基礎知識中，用華氏溫度對K & R的攝氏例子進行了學習。下面是我所指的C代碼：

#include <stdio.h> 

main() 
{ 
    int fahr, celsius; 
    int lower, upper, step; 

    lower = 0; 
    upper = 300; 
    step = 20; 

    fahr = lower; 
    while (fahr <= upper) { 
     celsius = 5 * (fahr-32)/9; 
     printf("%d\t%d\n", fahr, celsius); 
     fahr = fahr + step; 
    } 
} 

隨着GCC 4.4.7（GNU/Linux的x86-64的），我獲得以下拆解：

$ gcc -O0 -g -ansi -pedantic l1-2a.c 
$ gdb -q a.out 
(gdb) disas /m main 
(gdb) disas /m main 
Dump of assembler code for function main: 
6 { 
    0x00000000004004c4 <+0>: push %rbp 
    0x00000000004004c5 <+1>: mov %rsp,%rbp 
    0x00000000004004c8 <+4>: sub $0x20,%rsp 

7  int fahr, celsius; 
8  int lower, upper, step; 
9 
10  lower = 0; 
    0x00000000004004cc <+8>: movl $0x0,-0xc(%rbp) 

11  upper = 300; 
    0x00000000004004d3 <+15>: movl $0x12c,-0x8(%rbp) 

12  step = 20; 
    0x00000000004004da <+22>: movl $0x14,-0x4(%rbp) 

13 
14  fahr = lower; 
    0x00000000004004e1 <+29>: mov -0xc(%rbp),%eax 
    0x00000000004004e4 <+32>: mov %eax,-0x14(%rbp) 

15  while (fahr <= upper) { 
    0x00000000004004e7 <+35>: jmp 0x400532 <main+110> 
    0x0000000000400532 <+110>: mov -0x14(%rbp),%eax 
    0x0000000000400535 <+113>: cmp -0x8(%rbp),%eax 
    0x0000000000400538 <+116>: jle 0x4004e9 <main+37> 

16   celsius = 5 * (fahr-32)/9; 
    0x00000000004004e9 <+37>: mov -0x14(%rbp),%edx 
    0x00000000004004ec <+40>: mov %edx,%eax 
    0x00000000004004ee <+42>: shl $0x2,%eax 
    0x00000000004004f1 <+45>: add %edx,%eax 
    0x00000000004004f3 <+47>: lea -0xa0(%rax),%ecx 
    0x00000000004004f9 <+53>: mov $0x38e38e39,%edx 
    0x00000000004004fe <+58>: mov %ecx,%eax 
    0x0000000000400500 <+60>: imul %edx 
    0x0000000000400502 <+62>: sar %edx 
    0x0000000000400504 <+64>: mov %ecx,%eax 
    0x0000000000400506 <+66>: sar $0x1f,%eax 
    0x0000000000400509 <+69>: mov %edx,%ecx 
    0x000000000040050b <+71>: sub %eax,%ecx 
    0x000000000040050d <+73>: mov %ecx,%eax 
    0x000000000040050f <+75>: mov %eax,-0x10(%rbp) 

17   printf("%d\t%d\n", fahr, celsius); 
    0x0000000000400512 <+78>: mov $0x400638,%eax 
    0x0000000000400517 <+83>: mov -0x10(%rbp),%edx 
    0x000000000040051a <+86>: mov -0x14(%rbp),%ecx 
    0x000000000040051d <+89>: mov %ecx,%esi 
    0x000000000040051f <+91>: mov %rax,%rdi 
    0x0000000000400522 <+94>: mov $0x0,%eax 
    0x0000000000400527 <+99>: callq 0x4003b8 <printf@plt> 

18   fahr = fahr + step; 
    0x000000000040052c <+104>: mov -0x4(%rbp),%eax 
    0x000000000040052f <+107>: add %eax,-0x14(%rbp) 

19  } 
20 } 
    0x000000000040053a <+118>: leaveq 
    0x000000000040053b <+119>: retq 

End of assembler dump. 

什麼是不明確的，我是這個片段：

16   celsius = 5 * (fahr-32)/9; 
    0x00000000004004e9 <+37>: mov -0x14(%rbp),%edx 
    0x00000000004004ec <+40>: mov %edx,%eax 
    0x00000000004004ee <+42>: shl $0x2,%eax 
    0x00000000004004f1 <+45>: add %edx,%eax 
    0x00000000004004f3 <+47>: lea -0xa0(%rax),%ecx 
    0x00000000004004f9 <+53>: mov $0x38e38e39,%edx 
    0x00000000004004fe <+58>: mov %ecx,%eax 
    0x0000000000400500 <+60>: imul %edx 
    0x0000000000400502 <+62>: sar %edx 
    0x0000000000400504 <+64>: mov %ecx,%eax 
    0x0000000000400506 <+66>: sar $0x1f,%eax 
    0x0000000000400509 <+69>: mov %edx,%ecx 
    0x000000000040050b <+71>: sub %eax,%ecx 
    0x000000000040050d <+73>: mov %ecx,%eax 
    0x000000000040050f <+75>: mov %eax,-0x10(%rbp) 

我的意思是，我明白了一切達：

lea -0xa0(%rax),%ecx 

因爲它是從%eax寄存器，其保持5*fahr從其減去160，如：

5 * (fahr-32)/9 <=> (5*fahr - 5*32)/9 <=> (5*fahr - 160)/9 

從而%ecx後（以及完整%rcx）存儲5*fahr - 160。然而，我不知道它如何除以9。這似乎是一些騙局，如「乘以逆」，以避免分裂，但我不知道它是如何工作的。

Answer 1

總結評論中說的內容：0x38e38e39是954437177十進制，這正好是(2^33 + 1)/9。所以，彙編代碼以這種方式工作（我把它換成(5 * fahr - 160)與X爲清楚起見）：

mov $0x38e38e39,%edx /* edx is now 0x38e38e39 == (2^33 + 1)/9 */ 
mov %ecx,%eax  /* eax is now X */ 
imul %edx    /* edx:eax is now eax * edx == X * ((2^33 + 1)/9) */ 

這是最有趣的部分開始的位置。 edx:eax代表第一個操作數imul，先填充其操作數（在這種情況下爲edx）32位，然後將其餘的低位置入eax。

實際上，我們在兩個寄存器中得到了64位結果！它看起來像這樣：

edx是(X * ((2^33 + 1)/9)) >> 32的32個最低有效位。

eax是(X * ((2^33 + 1)/9)) % 2^32（但是這馬上就會丟棄）

然後我們得到這個東西成形狀：

sar %edx    /* edx is now edx >> 1 == (X * ((2^33 + 1)/9)) >> 33 */ 
mov %ecx,%eax  /* eax is now X again */ 
sar $0x1f,%eax  /* eax is now X >> 0x1f == X >> 31 */ 
mov %edx,%ecx  /* ecx is now (X * ((2^33 + 1)/9)) >> 33 */ 

所以現在ecx是(X * ((2^33 + 1)/9)) >> 33 32個最低顯著位和eax是X >> 31 ，即X（它是一個有符號的32位整數）的32「符號位」-s，如果X是非負的，則它等於0，並且如果是-1i f X爲負數。

編輯：對負X

現在有點什麼負數發生特殊情況詳細的闡述。關於ecx的重要部分是它實際上是X * ((2^33 + 1)/9)的32個最高有效位。

正如我希望你記得，在二進制，否定數字意味着反轉所有的位，然後加入1它。當我們添加1時，如果它是0，我們將lsb反轉爲1，否則我們將它反轉並在它之後的所有位'直到我們找到第一個0，然後將其反轉。

所以，當我們試圖否定(X * ((2^33 + 1)/9))發生了什麼（或者等價地，我們怎麼得到，如果我們用-X進行計算，考慮X積極爲這個例子）？當然，首先我們反轉所有的位，然後我們加上1。但是對於後者（將其添加1）影響數字的32個最重要位，32個最低有效位將必須等於0xFFFFFFFF。並且（相信我這個）沒有32位整數，當乘以0x38e38e39時，得出這樣的結果。

如此有效，雖然(-X * ((2^33 + 1)/9)) == -(X * ((2^33 + 1)/9))，它與32位最高有效位不同：((-X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF != -(((X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF)。

而是，(-X * ((2^33 + 1)/9))的32個最高有效位等於(X * ((2^33 + 1)/9))的32個最高有效位的按位否定：((-X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF != ~(((X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF)。

鉈組成; dr爲負X情況：的ecx爲-X的值將等於的ecx爲X值的按位求反。我們不希望這樣。因此，要獲得的X負值正確的結果，我們必須添加1到ecx（或等價地，減-1）：

sub %eax,%ecx  /* ecx is now X/9 */ 

然後是最後一部分：

mov %ecx,%eax  /* eax is now X/9 */ 
mov %eax,-0x10(%rbp) /* Aaand mov the result into the variable "cels" */ 

我如果我混淆了某些東西，我會非常抱歉，我無法用GAS語法編寫自己的頭腦，但我希望你能理解這個想法。

T1; dr：這裏的技巧是將乘以大數的逆乘以大數，用算術移位捨棄大數，然後如果結果爲負數則將結果舍入爲零。

爲什麼所有的麻煩？

因此，我們將分成10個週期（考慮imul只需要一個週期）。考慮到idiv可能會花費幾乎兩倍的週期（從Hans Passant在this回答類似的問題中提到的11到18），這種方法可以產生巨大的性能優勢。