了解这个 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    $0x1f,%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 = 返回 7??

8, 1 = 35

Answer 1

我总是喜欢我的程序集有一个调用图，所以我在 Binary Ninja 中组装了它：

（英特尔语法）

(at&t 语法)

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

这是等效的 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 的可能加法被整数除法四舍五入并且不会改变值。然而，如果只有一个bandc是偶数，那么可能的加法实际上很重要。我们将看两种情况：

1. b小于c，在这种情况下c < b将评估为 0，因此num只是平均值，由于整数除法而向下舍入。由于b小于c，向下舍入就是向 舍入b。
2. 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。所以，最后，你有一些奇怪的二分搜索，其中平均值要么高于或低于预期值，然后转到另一侧，然后慢慢接近所需值，并返回沿途所有平均值的总和。这也是为什么func4(7, 1, 14)返回7：7是平均的1，并14因此它立即返回。