Come funziona questo pezzo di assemblaggio?

Question

Recentemente ho avuto bisogno di eseguire il debug di un programma a livello di assembly. Non ho molta esperienza con gli assemblatori, quindi ho pensato di scrivere alcuni semplici programmi in C e un singolo passo attraverso di loro al fine di ottenere una sensazione per il linguaggio prima di iniziare il debugging del codice di altri popoli. Comunque, io davvero non capisco che cosa gcc in queste due linee (compilato con -O0 -ggdb):

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

dove MAX_SIZE è #defined essere 5 e i è una variabile locale (memorizzato in 0x8 (% ebp), credo). Secondo gdb, questo diventa:

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 

Dal 0x804963c è l'indirizzo di elementi, posso vedere come la prima riga di codice C funziona. Inoltre, 0x8049634 è l'indirizzo di coda, quindi suppongo che la coda + 33 e la coda + 38 siano equivalenti a% ecx = tail + 1 ... ma non ho idea di cosa succederà dopo. Chi avrebbe mai pensato che un semplice modulo potesse essere così complicato?

Answer 1

È un modo per evitare di dover eseguire un'istruzione di divisione più costosa. Sono stato anche abbastanza perplesso la prima volta che ho incontrato questo. La cosa divertente è che la ricerca dei numeri magici usati per questo trucco (in questo caso 0x66666667) dà spesso risultati che spiegano questo trucco. (Credo che al momento fosse l'unica cosa concreta che dovevo continuare perché non avevo le fonti.)

Una ricerca rapida mi ha fornito questo post sul blog: http://blog.dkbza.org/2007/09/reverse-engineering-compiler-produced.html Ha alcuni link utili nella parte inferiore (incluso un link indiretto a un documento su questo trucco).