x86_64 中的除法、模运算和冒泡排序
2026-07-08T17:46:33+08:00
用高级语言（例如 C）写出来的算法，在查看源代码时会显得非常直白。然而，编译器会把它们在汇编层面转换成一些相当神秘的模式。为了提升我们的逆向工程能力，我们需要学习这些模式，这样才能快速识别它们。这篇博客会列举一些例子，它们都是我今天在解一道 CTF 题时遇到的。
整数之间的有符号除法
先看这段代码：
#include <stdio.h>
int div(int a)
{
return a / 42;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
把它编译一下，然后打开你心爱的 iaito 或 radare2，看看汇编。我们不需要关心 main()，所以直接进入 sym.div，就能看到类似这样的内容：
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 sar eax, 0x1f
0x00001167 sub edx, eax
0x00001169 mov eax, edx
0x0000116b pop rbp
0x0000116c ret
这里看不到 idiv 指令。相反，我们能看到 0x00001156 处有一条 imul 指令，后面跟着一条 shr 指令和一条 sar 指令。之后，结果会出现在 edx 寄存器里。
但如果我们换一个数字，会发生什么？试试看。编译下面这段：
#include <stdio.h>
int div(int a)
{
return a / 6;
}
int main()
{
int a;
scanf("%d", &a);
a = div(a);
printf("%d", a);
return 0;
}
我们会得到一段类似的反汇编：
33: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x2aaaaaab
0x0000115d shr rdx, 0x20
0x00001161 sar eax, 0x1f
0x00001164 sub edx, eax
0x00001166 mov eax, edx
0x00001168 pop rbp
0x00001169 ret
如果我们使用负数，会发生什么？把 6 换成 -7，我们会得到类似的结果：
36: div (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0xffffffff92492493
0x0000115d shr rdx, 0x20
0x00001161 add edx, eax
0x00001163 sar edx, 2
0x00001166 sar eax, 0x1f
0x00001169 sub eax, edx
0x0000116b pop rbp
0x0000116c ret
如果我们不使用常量，会发生什么？编译下面这段：
#include <stdio.h>
int div(int a, int b)
{
return a / b;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
a = div(a, b);
printf("%d", a);
return 0;
}
之后，我们终于会看到不同的东西：
19: div (int64_t arg1, signed int64_t arg2);
`- args(rdi, rsi) vars(2:sp[0xc..0x10])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov dword [var_8h], esi ; arg2
0x00001153 mov eax, dword [var_4h]
0x00001156 cdq
0x00001157 idiv dword [var_8h]
0x0000115a pop rbp
0x0000115b ret
x86_64 CPU 确实支持除法，但代价很高。因此，如果除数已经以常量形式给出，编译器就会在编译时替我们做这种优化。它会根据除数计算出一个魔数乘数，并把除法转换成乘法和位移的组合。有一篇论文对这个算法作了进一步解释。
不过，如果这个常量只在运行时才知道，这种优化就帮不上忙了，因此它会直接使用除法指令。
取模运算
现在编译这段：
#include <stdio.h>
int mymod(int a)
{
return a % 42;
}
int main()
{
int a;
scanf("%d", &a);
a = mymod(a);
printf("%d", a);
return 0;
}
我们会得到 mymod() 的反汇编：
45: mymod (int64_t arg1);
`- args(rdi) vars(1:sp[0xc..0xc])
0x00001149 push rbp
0x0000114a mov rbp, rsp
0x0000114d mov dword [var_4h], edi ; arg1
0x00001150 mov eax, dword [var_4h]
0x00001153 movsxd rdx, eax
0x00001156 imul rdx, rdx, 0x30c30c31
0x0000115d shr rdx, 0x20
0x00001161 sar edx, 3
0x00001164 mov ecx, eax
0x00001166 sar ecx, 0x1f
0x00001169 sub edx, ecx
0x0000116b imul ecx, edx, 0x2a
0x0000116e sub eax, ecx
0x00001170 mov edx, eax
0x00001172 mov eax, edx
0x00001174 pop rbp
0x00001175 ret
从 0x00001150 到 0x00001161 的指令使用了上面提到的魔数乘数来实现除法。然后它会把被除数复制一份到 ecx，再对它进行 31 位算术右移。如果被除数是非负数，ecx 就是 0；否则，它就是 -1。
这样做是为了从被除数中计算出一个 bias，因为除法总是向零截断。我们用商来计算取模：对于正数，模 = 被除数 - 除数 * 商；对于负数，模 = 被除数 - 除数 * （商 + 1）。
冒泡排序
最后编译这段：
#include <stdio.h>
void bubble(int *arr, int n)
{
for (int i1 = 0; i1 < n - 1; i1++)
{
for (int i2 = 0; i1 + i2 < n - 1; i2++)
{
if (arr[i1] > arr[i2])
{
int tmp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = tmp;
}
}
}
}
int main()
{
int a[42];
for (int i1 = 0; i1 < 42; i1++)
a[i1] = 42 - i1;
bubble(a, 42);
for (int i1 = 0; i1 < 42; i1++)
printf("%d", a[i1]);
return 0;
}
这次看看 iaito 生成的 sym.bubble 图：
我们可以看到，0x00001144 处设置了一个计数器。0x00001209 这个块里有一次比较。如果计数器还没有达到阈值，就会继续执行。0x00001150 处又设置了一个计数器。0x0000115c 这个块里会比较两个相邻的数字。如果前者更大，就会在 0x0000118c 这个块里执行交换。
结论
这只是逆向工程过程中可能遇到的几种模式示例。随着我们做得越来越多，我们会积累越来越多的经验，也就能够更快地识别反汇编中的更多模式。
