c - 需要解释 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是 (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 个“符号位”-s (这是一个有符号的 32 位整数)，等于 0如果 X是非负的并且到 -1如果 X是否定的。

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

现在来谈谈负数会发生什么。关于 ecx的重要部分是它实际上是 X * ((2^33 + 1) / 9)的32个最高有效位.

我希望你记得，在二进制中，取反一个数字意味着反转它的所有位，然后加上 1到它。当我们添加 1 ，我们将 lsb 反转为 1如果是 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) .

相反， (-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) .

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 语法编写的 asm，但我希望你理解这个想法。

Tl;博士:这里的技巧是乘以大数的倒数，用算术移位丢弃大数，如果结果为负，则将结果四舍五入为零。

为什么这么麻烦？

结果，我们将除法填充为 10 个周期(考虑到 imul 也只需要一个周期)。考虑 idiv可能占用几乎两倍的周期(Hans Passant 在 this 对类似问题的回答中提到的从 11 到 18)，这种方法可以带来巨大的性能优势。