Potrzebuję wyjaśnienia instrukcji montażu K & R fahr-to-cels przykład

Question

Utknąłem nauki podstawowe podstawy języka asemblera z Fahrenheita do przykładu Celsius z K & R książka. Oto kod C, które mam na myśli:

#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; 
    } 
} 

Wraz z GCC 4.4.7 (GNU/Linux x86-64) pojawia się po demontażu:

$ 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. 

Co nie jest oczywiste dla mnie jest ten fragment:

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) 

to znaczy, że wszystko rozumiem do:

lea -0xa0(%rax),%ecx 

jak to jest odjęcie 160 z %eax rejestru, który przechowuje 5*fahr, jak:

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

więc po %ecx (jak również kompletnych %rcx) przechowuje 5*fahr - 160. Jednak nie wiem jak to jest dzielić przez 9 wtedy. Wydaje się, że niektóre sztuczki, takie jak "pomnóż przez odwrotność", aby uniknąć podziału, ale nie rozumiem, jak to działa.

Answer 1

Podsumowując, co zostało powiedziane w komentarzach: 0x38e38e39 jest 954437177 w postaci dziesiętnej, czyli dokładnie (2^33 + 1)/9. Więc, kod zespół działa w ten sposób (mam wymienić (5 * fahr - 160) z X dla jasności):

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) */ 

to gdzie zaczyna się zabawa. edx:eax oznacza 1-operand imul najpierw wypełniając jego operand (edx w tym przypadku) 32 bity, a następnie umieszczając pozostałe dolne bity w eax.

Skutecznie, otrzymujemy 64-bitowy wynik w dwóch rejestrach! Wygląda to mniej więcej tak:

edx to 32 najmniej znaczące bity z (X * ((2^33 + 1)/9)) >> 32.

eax jest (X * ((2^33 + 1)/9)) % 2^32 (ale to będzie wyrzucić wkrótce)

Następnie mamy te rzeczy na kształt:

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 */ 

Więc teraz ecx jest 32 najmniej znaczących bitów (X * ((2^33 + 1)/9)) >> 33 i eax jest X >> 31 , czyli 32 "bit znaku" -s z X (który jest 32-bitową liczbą całkowitą ze znakiem), które są równe 0, jeśli X jest nieujemne i -1 i f X jest ujemna.

EDIT: szczegółowe opracowanie na specjalnym przypadku negatywnej X

teraz trochę o tym, co dzieje się z liczb ujemnych. Ważną częścią o numerze ecx jest to, że w rzeczywistości jest 32 najbardziej znaczącymi bitami X * ((2^33 + 1)/9).

Mam nadzieję, że pamiętasz, że w systemie binarnym zanegowanie liczby oznacza odwrócenie wszystkich jej bitów, a następnie dodanie do niej 1. A kiedy dodamy 1, odwracamy lsb na 1, jeśli było to 0, w przeciwnym razie odwrócimy go i wszystkie bity po nim 'dopóki nie znajdziemy pierwszego 0, a następnie również odwrócimy.

Więc co się dzieje, gdy staramy się negować (X * ((2^33 + 1)/9)) (lub równoważnie, co dostajemy, gdy wykonujemy obliczenia z -X, zważywszy X pozytywny dla tego przykładu)? Oczywiście najpierw odwracamy wszystkie bity, a następnie dodajemy do niego 1. Ale dla tego ostatniego (dodanie do niego 1), aby wpłynąć na 32 najbardziej znaczące bity liczby, 32 najmniej znaczące bity musiałyby być równe 0xFFFFFFFF. I (zaufaj mi na tym) nie ma 32-bitowej liczby całkowitej, która po pomnożeniu przez 0x38e38e39 daje taki wynik.

Tak skutecznie, podczas gdy (-X * ((2^33 + 1)/9)) == -(X * ((2^33 + 1)/9)), różni się od 32 najbardziej znaczących bitów: ((-X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF != -(((X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF).

Zamiast tego 32 najbardziej znaczące bity z (-X * ((2^33 + 1)/9)) są równe bitowej negacji 32 najbardziej znaczących bitów (X * ((2^33 + 1)/9)): ((-X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF != ~(((X * ((2^33 + 1)/9)) >> 33) & 0xFFFFFFFF).

Tl; dr negatywnego X postępowania: wartość ecx do -X będzie równa negację logiczną wartości ecx do X. Nie chcemy tego. Tak, aby uzyskać poprawne wyniki dla ujemnych X, będziemy musieli dodać 1 do ecx (lub, równoważnie, odejmowanie -1):

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

Potem przychodzi ostatnia część:

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

I "Bardzo mi przykro, jeśli coś wymieszałem, mam problem z utrzymaniem mojej głowy wokół ASM napisanej w składni GAS, ale mam nadzieję, że rozumiesz ten pomysł.

Tl; dr: trick tutaj jest mnożenie przez odwrotność pomnożona przez dużą liczbę, odrzucając wiele z arytmetycznego przesunięcia, a następnie zaokrąglenie wyniku do zera, jeśli jest ujemna.

Po co wszystkie kłopoty?

W rezultacie wprowadziliśmy podział na 10 cykli (biorąc pod uwagę, że imul trwa tylko jeden cykl). Biorąc pod uwagę, że idiv może zająć prawie dwa razy więcej cykli (od 11 do 18, jak wspomniał Hans Passant w this, odpowiedź na podobne pytanie), to podejście może przynieść ogromną przewagę wydajności.