¿Cómo funciona esta pieza de montaje?

Question

Recientemente tuve que depurar un programa en el nivel de ensamblaje. No tengo mucha experiencia como ensamblador, así que pensé que escribiría algunos programas simples de C y un solo paso a través de ellos para tener una idea del idioma antes de comenzar a depurar el código de otras personas. Sin embargo, realmente no entiendo lo que gcc hecho de estas dos líneas (compilado con -O0 -ggdb):

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

donde se MAX_SIZE #defined ser 5 e i es una variable local (almacenado en 0x8 (% ebp), supongo). De acuerdo con el BGF, esto se convierte en:

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 

Desde 0x804963c es la dirección de los envíos, puedo ver cómo la primera línea de código C funciona. Además, 0x8049634 es la dirección de cola, así que supongo que cola + 33 y cola + 38 son equivalentes a% ecx = cola + 1 ... pero no tengo idea de lo que está sucediendo después. ¿Quién hubiera pensado que un módulo simple podría ser tan complicado?

Answer 1

Es una forma de evitar tener que hacer una instrucción de división más costosa. La primera vez que me encontré con esto también me sorprendió bastante. Lo divertido es que la búsqueda de los números mágicos que se utilizan para este truco (en este caso 0x66666667) a menudo da resultados que explican este truco. (Creo que en ese momento era lo único concreto que tenía que seguir porque no tenía las fuentes.)

Una búsqueda rápida me dio esta publicación en el blog: http://blog.dkbza.org/2007/09/reverse-engineering-compiler-produced.html Tiene algunos enlaces útiles en la parte inferior (incluyendo un enlace indirecto a un documento sobre este truco).