这段汇编代码是如何工作的？

Question

最近我需要在汇编层面调试一个程序。我并没有很多汇编经验，所以我想写一些简单的C程序，并逐步执行它们，以便在开始调试他人代码之前对该语言有所了解。然而，我真的不明白gcc对这两行代码的处理结果（使用-ggdb -O0编译）：

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

其中MAX_SIZE被定义为5，i是一个本地变量（存储在0x8（%ebp）中，我猜）。根据gdb，这变成：

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

由于0x804963c是items的地址，我能理解第一行C代码的作用。同样地，0x8049634是tail的地址，所以我猜queue+33和queue+38等价于%ecx = tail+1...但我不知道之后发生了什么。谁会想到一个简单的模运算会这么复杂呢？

- Benno

Answer 1

这是一种避免使用更昂贵的除法指令的方法，第一次遇到时我也感到困惑。有趣的是，搜索用于此技巧的神奇数字（在本例中为0x66666667）通常会得到解释此技巧的结果。（我相信当时这是我唯一可以依赖的具体信息，因为我没有源代码。）

通过快速搜索，我发现了这篇博客文章：http://blog.dkbza.org/2007/09/reverse-engineering-compiler-produced.html 它底部包含一些有用的链接（包括一个间接链接到关于此技巧的论文）。

- mweerden