需要解释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

因为它是160从%eax寄存器中减去的,它持有5*fahr如下:

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代表1操作数imul首先填充其操作数(edx在本例中为32位),然后将剩余的低位写入eax.

实际上,我们在两个寄存器中获得了64位结果!它看起来像这样:

edx是32个最不重要的位(X * ((2^33 + 1) / 9)) >> 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是32个最低位显著(X * ((2^33 + 1) / 9)) >> 33和eax是X >> 31,即32"符号位"的-s X(这是有符号的32位整数),它是等于0如果X是非负的,并-1如果X是负的.

编辑:详细阐述负面的特殊情况 X

现在谈谈负数会发生什么.关键的一点ecx是它实际上是32个最重要的部分X * ((2^33 + 1) / 9).

我希望你记住,在二进制中,否定一个数字意味着反转它的所有位然后再添加1它.当我们添加时1,我们将lsb反转为1if 0,否则我们将它和它之后的所有位反转,直到我们找到第一个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).

相反,32个最高有效位(-X * ((2^33 + 1) / 9))等于32位最高有效位的按位否定(X * ((2^33 + 1) / 9)):((-X * ((2^33 + 1) / 9)) >> 33) & 0xFFFFFFFF != ~(((X * ((2^33 + 1) / 9)) >> 33) & 0xFFFFFFFF).

TL;博士负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语法编写,但我希望你理解这个想法.

Tl; dr:这里的技巧是乘以逆乘以一个大数,用算术移位丢弃大数,然后如果它是负数则将结果舍入为零.

为什么这么麻烦？

结果,我们将分区塞进了10个循环(考虑到也imul只需要一个循环).考虑到idiv(如由Hans帕桑特中提到的从11到18可能需要长达几乎两倍周期这个回答类似的问题),这种方法可以使一个巨大的性能优势.