Wie funktioniert dieses Montageelement?

Question

Ich musste vor kurzem ein Programm auf Baugruppenebene debuggen. Ich habe nicht viel Assembler-Erfahrung, also dachte ich, ich würde ein paar einfache C-Programme schreiben und sie in einem Schritt durchgehen, um ein Gefühl für die Sprache zu bekommen, bevor ich anfangen würde, Code anderer Leute zu debuggen. Allerdings habe ich nicht bekommen, wirklich was gcc aus diesen beiden Linien (mit -ggdb -O0 kompiliert):

items[tail] = i; 
tail = (tail+1) % MAX_SIZE; 

wo MAX_SIZE #defined 5 zu sein und i ist eine lokale Variable (gespeichert in 0x8 (% ebp), schätze ich). Nach GDB wird daraus:

0x08048394 <queue+17>: mov 0x8049634,%edx 
0x0804839a <queue+23>: mov 0x8(%ebp),%eax 
0x0804839d <queue+26>: mov %eax,0x804963c(,%edx,4) 
0x080483a4 <queue+33>: mov 0x8049634,%eax 
0x080483a9 <queue+38>: lea 0x1(%eax),%ecx 
0x080483ac <queue+41>: movl $0x66666667,-0xc(%ebp) 
0x080483b3 <queue+48>: mov -0xc(%ebp),%eax 
0x080483b6 <queue+51>: imul %ecx 
0x080483b8 <queue+53>: sar %edx 
0x080483ba <queue+55>: mov %ecx,%eax 
0x080483bc <queue+57>: sar $0x1f,%eax 
0x080483bf <queue+60>: mov %edx,%ebx 
0x080483c1 <queue+62>: sub %eax,%ebx 
0x080483c3 <queue+64>: mov %ebx,-0x8(%ebp) 
0x080483c6 <queue+67>: mov -0x8(%ebp),%eax 
0x080483c9 <queue+70>: shl $0x2,%eax 
0x080483cc <queue+73>: add -0x8(%ebp),%eax 
0x080483cf <queue+76>: mov %ecx,%edx 
0x080483d1 <queue+78>: sub %eax,%edx 
0x080483d3 <queue+80>: mov %edx,-0x8(%ebp) 
0x080483d6 <queue+83>: mov -0x8(%ebp),%ebx 
0x080483d9 <queue+86>: mov %ebx,0x804963 

Da 0x804963c die Adresse der Elemente ist, kann ich sehen, wie die erste Zeile von C-Code arbeitet. Außerdem ist 0x8049634 die Adresse von Tail, also nehme ich an, dass Warteschlange + 33 und Warteschlange + 38 äquivalent zu% ecx = Tail + 1 sind ... aber ich habe keine Ahnung, was danach passiert. Wer hätte gedacht, dass ein einfacher Modulo so kompliziert sein könnte?

Answer 1

Es ist ein Weg zu vermeiden, eine teurere Division Anweisung zu tun. Ich war auch ziemlich ratlos, als ich das erste Mal ankam. Das Lustige ist, dass die Suche nach den magischen Zahlen, die für diesen Trick verwendet werden (in diesem Fall 0x66666667) oft Ergebnisse gibt, die diesen Trick erklären. (Ich glaube zu der Zeit war es das einzige konkrete Ding, das ich weitermachen musste, weil ich die Quellen nicht hatte.)

Eine schnelle Suche gab mir diesen Blog-Beitrag: http://blog.dkbza.org/2007/09/reverse-engineering-compiler-produced.html Es hat einige nützliche Links an der Unterseite (einschließlich eines indirekten Links zu einem Papier über diesen Trick).