反汇编二进制还原C程序：解析sar算术右移指令移位规则

sar %eax指令的运行逻辑解答 #

你对移位指令的规则记忆存在偏差，x86架构下的移位指令存在两类编码形式，并非所有移位操作都从%cl取移位量：

• 操作码以D0/D1开头的移位指令：属于固定移位1位的编码，执行时直接对目标操作数做1位对应移位操作，完全不需要读取%rcx/%cl的值。你看到的地址400ff1处的指令d1 f8 sar %eax就属于这类，操作码D1对应双字操作数移位1位，因此无论%cl是什么值，都会将%eax算术右移1位。
• 操作码以D2/D3开头的移位指令：才是可变移位量的编码，这类指令执行时才会读取%cl的低8位作为移位量。

这一段紧邻的指令是在实现有符号整数的正确二分中间值计算，避免负数右移时的向负无穷取整误差：

mov    %edx,%eax       # eax = high（第三个传入参数）
sub    %esi,%eax       # eax = high - low（区间长度）
mov    %eax,%ebx
shr    $0x1f,%ebx      # ebx = 区间长度的符号位，差为负时取1，非负取0
add    %ebx,%eax
sar    %eax            # 上述两步实现有符号数(high-low)/2向零取整
lea    (%rax,%rsi,1),%ebx  # ebx = low + (high-low)/2 = mid，即二分中间点

完整func4函数还原 #

结合调用片段的初始参数（low=0、high=0xe即14）和递归分支逻辑，该函数是基于二分查找路径的节点求和函数，三个参数分别为：第一个参数%edi是目标查找值x，第二个%esi是查找区间左边界low，第三个%edx是查找区间右边界high。
等价C代码如下：

int func4(int x, int low, int high) {
    int len = high - low;
    // 有符号数向零取整的除法，计算正确的二分中间点
    int mid = low + ((len + (len >> 31)) >> 1);
    if (mid > x) {
        // 目标值在左半区间，递归后累加当前mid值
        return mid + func4(x, low, mid - 1);
    }
    if (mid < x) {
        // 目标值在右半区间，递归后累加当前mid值
        return mid + func4(x, mid + 1, high);
    }
    // 命中目标点，直接返回mid
    return mid;
}

当传入初始参数low=0、high=14时，该函数会返回二分查找x过程中所有经过的中间节点值的总和。

内容的提问来源于stack exchange，提问作者arka