Binary Bomb Phase4求解求助：func4递归分析与输入错误排查

问题描述 #

我在破解Binary Bomb的Phase4时遇到瓶颈，追踪代码后仍有困惑。已知该阶段要求输入两个数字（格式如1 2），且第一个输入必须≤14（对应指令地址40106a）。我推导的输入为3 1，但验证失败，推导过程如下：
当第一个输入为3时，程序调用func4(3, 0, 14)，首先计算中点为(0+14)//2=7，因3<7，递归调用func4(3, 0, 6)；新参数下中点为(0+6)//2=3，与输入值相等后退出递归。

汇编代码 #

func4 汇编 #

000000000040100b <func4>:
  40100b:   48 83 ec 08             sub    $0x8,%rsp
  40100f:   89 d1                   mov    %edx,%ecx
  401011:   29 f1                   sub    %esi,%ecx
  401013:   89 c8                   mov    %ecx,%eax
  401015:   c1 e8 1f                shr    $0x1f,%eax
  401018:   01 c8                   add    %ecx,%eax
  40101a:   d1 f8                   sar    %eax
  40101c:   01 f0                   add    %esi,%eax
  40101e:   39 f8                   cmp    %edi,%eax
  401020:   7f 0c                   jg     40102e <func4+0x23>
  401022:   7c 18                   jl     40103c <func4+0x31>
  401024:   b8 00 00 00 00          mov    $0x0,%eax
  401029:   48 83 c4 08             add    $0x8,%rsp
  40102d:   c3                      retq   
  40102e:   8d 50 ff                lea    -0x1(%rax),%edx
  401031:   e8 d5 ff ff ff          callq  40100b <func4>
  401036:   8d 44 00 01             lea    0x1(%rax,%rax,1),%eax
  40103a:   eb ed                   jmp    401029 <func4+0x1e>
  40103c:   8d 70 01                lea    0x1(%rax),%esi
  40103f:   e8 c7 ff ff ff          callq  40100b <func4>
  401044:   01 c0                   add    %eax,%eax
  401046:   eb e1                   jmp    401029 <func4+0x1e>

phase4 汇编 #

0000000000401048 <phase_4>:
  401048:   48 83 ec 18             sub    $0x18,%rsp
  40104c:   48 8d 4c 24 08          lea    0x8(%rsp),%rcx
  401051:   48 8d 54 24 0c          lea    0xc(%rsp),%rdx
  401056:   be 1e 27 40 00          mov    $0x40271e,%esi
  40105b:   b8 00 00 00 00          mov    $0x0,%eax
  401060:   e8 cb fb ff ff          callq  400c30 <__isoc99_sscanf@plt>
  401065:   83 f8 02                cmp    $0x2,%eax
  401068:   75 07                   jne    401071 <phase_4+0x29>
  40106a:   83 7c 24 0c 0e          cmpl   $0xe,0xc(%rsp)
  40106f:   76 05                   jbe    401076 <phase_4+0x2e>
  401071:   e8 5e 06 00 00          callq  4016d4 <explode_bomb>
  401076:   ba 0e 00 00 00          mov    $0xe,%edx
  40107b:   be 00 00 00 00          mov    $0x0,%esi
  401080:   8b 7c 24 0c             mov    0xc(%rsp),%edi
  401084:   e8 82 ff ff ff          callq  40100b <func4>
  401089:   83 f8 01                cmp    $0x1,%eax
  40108c:   75 07                   jne    401095 <phase_4+0x4d>
  40108e:   83 7c 24 08 01          cmpl   $0x1,0x8(%rsp)
  401093:   74 05                   je     40109a <phase_4+0x52>
  401095:   e8 3a 06 00 00          callq  4016d4 <explode_bomb>
  40109a:   48 83 c4 18             add    $0x18,%rsp
  40109e:   c3                      retq   

逻辑拆解与错误分析 #

func4 伪代码转换 #

先将func4的汇编转为C伪代码，明确其递归逻辑：

int func4(int x, int low, int high) {
    // 计算有符号数中点，避免溢出
    int diff = high - low;
    int mid = low + ((diff + (diff >> 31)) >> 1);
    if (mid > x) {
        int res = func4(x, low, mid - 1);
        return 2 * res + 1;
    } else if (mid < x) {
        int res = func4(x, mid + 1, high);
        return 2 * res;
    } else {
        return 0;
    }
}

phase4 核心要求 #

phase4的验证逻辑可总结为：

1. 必须输入两个整数，否则触发炸弹；
2. 第一个输入的整数必须≤14，否则触发炸弹；
3. 调用func4(第一个输入, 0, 14)的返回值必须等于1，否则触发炸弹；
4. 第二个输入的整数必须等于1，否则触发炸弹。

推导修正 #

你的推导遗漏了func4的返回值计算逻辑：当递归子调用返回0时，上层调用会执行2*res +1的计算，因此func4(3, 0, 14)的最终返回值是1，完全满足phase4的要求。

输入3 1本身是正确的，验证失败可能是以下原因：

• 输入时搞反了两个数字的顺序（比如输入1 3）；
• 使用了非空格的分隔符（比如逗号、制表符，而程序要求空格分隔）；
• 输入时存在拼写错误（比如输入3 2或3 l）。

另外，唯一满足func4(x,0,14)=1的x值就是3，因此正确输入只能是3 1。

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