了解这个 x86 汇编函数的作用，递归

Question

我这里有这个 Assembly 函数，运行多次尝试了解它的作用和模式。在理解它的模式方面，我遇到了障碍。在此感谢任何形式的指导。

   0x0000555555555cbe <+0>: push   %rbx
   0x0000555555555cbf <+1>: mov    %edx,%eax
   0x0000555555555cc1 <+3>: sub    %esi,%eax
   0x0000555555555cc3 <+5>: mov    %eax,%ebx
   0x0000555555555cc5 <+7>: shr    [=10=]x1f,%ebx
   0x0000555555555cc8 <+10>: add    %eax,%ebx
   0x0000555555555cca <+12>: sar    %ebx
   0x0000555555555ccc <+14>: add    %esi,%ebx
   0x0000555555555cce <+16>: cmp    %edi,%ebx
   0x0000555555555cd0 <+18>: jg     0x555555555cda <func4+28>
   0x0000555555555cd2 <+20>: cmp    %edi,%ebx
   0x0000555555555cd4 <+22>: jl     0x555555555ce6 <func4+40>
   0x0000555555555cd6 <+24>: mov    %ebx,%eax
   0x0000555555555cd8 <+26>: pop    %rbx
   0x0000555555555cd9 <+27>: retq  
   0x0000555555555cda <+28>: lea    -0x1(%rbx),%edx
   0x0000555555555cdd <+31>: callq  0x555555555cbe <func4>
   0x0000555555555ce2 <+36>: add    %eax,%ebx
   0x0000555555555ce4 <+38>: jmp    0x555555555cd6 <func4+24>
   0x0000555555555ce6 <+40>: lea    0x1(%rbx),%esi
   0x0000555555555ce9 <+43>: callq  0x555555555cbe <func4>
   0x0000555555555cee <+48>: add    %eax,%ebx
   0x0000555555555cf0 <+50>: jmp    0x555555555cd6 <func4+24>

如果我的输入是“6 1”，寄存器如下：

rax            0x2 2
rbx            0x7fffffffe0c8 140737488347336
rcx            0x0 0
rdx            0xe 14
rsi            0x0 0
rdi            0x6 6
rbp            0x555555557170 0x555555557170 <__libc_csu_init>
rsp            0x7fffffffdfb8 0x7fffffffdfb8
r8             0x0 0
r9             0x0 0
r10            0x7ffff7b82f20 140737349431072
r11            0x55555555763a 93824992245306
r12            0x5555555558f0 93824992237808
r13            0x7fffffffe0c0 140737488347328
r14            0x0 0
r15            0x0 0
rip            0x555555555cbe 0x555555555cbe <func4>
eflags         0x293 [ CF AF SF IF ]
cs             0x33 51
ss             0x2b 43
ds             0x0 0
es             0x0 0
fs             0x0 0
gs             0x0 0
k0             0x0 0
k1             0x0 0
k2             0x0 0
k3             0x0 0
k4             0x0 0
k5             0x0 0
k6             0x0 0
k7             0x0 0

我试过一步一步地按照代码进行操作，输入很多，但似乎无法理解此函数所遵循的模式。

RDX 似乎总是 14，无论输入如何。据我所知，有一个循环可以查看某个移位和减法的组合是否大于或小于原始输入。

这些是我尝试过的输入及其以下输出：

14, 1 = 45

13, 1 = 31

5, 1 = 15

6, 1 = 21

7, 1 = returns 7??

8, 1 = 35

Answer 1

我总是喜欢为我的程序集提供一个调用图，所以我在 Binary Ninja 中进行了组装：

（英特尔语法）

（at&t 语法）

就个人而言，我更喜欢 intel 语法，所以我会从现在开始使用它。我们可以看到 3 个寄存器在写入之前被读取，它们是 edi、esi 和 edx。这些也恰好是标准 x86 调用约定中的前 3 个参数寄存器，因此我们可以推断该函数有 3 个参数。这里有注释（要理解为什么移动 0x1f 会产生符号位，你必须先理解 two's complement）：

这是等效的 C 代码：

int func4(int a, int b, int c) {
    int num = (b + c + (c < b)) / 2;
    if (num > a) {
        return func4(a, b, num - 1) + num;
    } else if (num < a) {
        return func4(a, num + 1, c) + num;
    } else {
        return num;
    }
}

现在我们有了干净、可读的 C 代码，我们可以开始推断函数实际做了什么。 (b + c) / 2 是平均值，而 c < b 始终为 0 或 1，这意味着 num 变量必须非常接近平均值。事实上，如果 b 和 c 都是偶数或都是奇数，那么 num 就是平均值，因为可能的加法 1 通过整数除法向下取整并且不会改变价值。但是，如果 b 和 c 中只有一个是偶数，那么可能的加法实际上很重要。我们来看看两种情况：

b 小于 c，在这种情况下 c < b 的计算结果为 0，因此 num 只是平均值，由于整数除法而向下舍入.由于 b 小于 c，向下舍入是向 b.
b 大于 c，在这种情况下，c < b 的计算结果为 1，因此 num 将是平均值加一半，从而将其推高到下一个值。这意味着 num 是向上舍入的平均值，并且由于 b 大于 c，因此它向 b.

因此，b 本质上是 b 和 c 的平均值，但四舍五入为 b 的值。现在我们可以看看实际的递归情况。需要注意的一件事是 a 永远不会改变。事实上，函数永远不会终止，直到 b 和 c 的平均值达到 a。如果平均值大于 a，则将 c 降低为平均值减一以降低平均值，如果平均值小于 a，则 b增加到平均值加一以提高平均值。现在，这是假设 b < c。为什么？当 b > c 及其所有逻辑中断并进入无限递归时，此函数真的很讨厌，因为将 b 设置为平均值实际上减少 b而不是增加b，绝不允许平均值达到a。所以，最后，你有一些奇怪的二进制搜索，其中平均值开始高于或低于预期值，然后转到另一边，然后慢慢接近所需值，并且 returns 所有平均值的总和方式。这也是func4(7, 1, 14)返回7的原因：7是1和14的平均值，所以它立即返回。

了解这个 x86 汇编函数的作用，递归

Understanding what this x86 assembly function does, recursion

assembly

reverse-engineering

x86-64

cpu-registers