2018年5月

Welcome to my fiendish little bomb.
You have 6 phases with which to blow yourself up. Have a nice day!

bomblab分6个phase,每个phase有一个函数,没有函数的源代码,只能通过阅读函数的汇编代码得出恰当的输入。一次错误的输入会引爆炸弹。不过只要在explode_bomb打一个断点就可以了。

gdb调试汇编命令:
- disassemble 反汇编函数func,输出函数汇编代码。简称disas
- b 在函数func处打断点
- b *+ 在函数func汇编代码中+num处打断点
- cl 清除函数func的所有断点
- ni/si 在汇编代码中逐步执行
- p $ 打印寄存器reg当前的值 e.g.:p $rax
- x/<n/f/u> 输出地址addr后的信息,
n:一个数字,表示输出数量
f:输出格式(s:字符串,x:十六进制,d:十进制...)
u:输出每个数所占位数(b:单字节,h:双字节,w:四字节,g:八字节),默认四字节
addr:一个内存地址
e.g. x/8xg $rsp+0x20

特殊寄存器:
rsp:stack ptr,指向系统栈中当前函数栈底位置
rax:函数返回值寄存器
rdi:传入第一个参数
rsi:传入第二个参数
rdx:传入第三个参数
rcx:传入第四个参数

phase_1

   0x0000000000400ee0 <+0>: sub    $0x8,%rsp
   0x0000000000400ee4 <+4>: mov    $0x402400,%esi
   0x0000000000400ee9 <+9>: callq  0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    callq  0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    retq 

<+4>行给esi赋了一个蜜汁内存地址0x402400,然后调用string_not_equal
x/s $0x402400 得到"Border relations with Canada have never been better."
就是答案了。

phase_2

   0x0000000000400efc <+0>:   push   %rbp
   0x0000000000400efd <+1>:   push   %rbx
   0x0000000000400efe <+2>:   sub    $0x28,%rsp
   0x0000000000400f02 <+6>:   mov    %rsp,%rsi
   0x0000000000400f05 <+9>:   callq  0x40145c <read_six_numbers>
   0x0000000000400f0a <+14>:  cmpl   $0x1,(%rsp)
   0x0000000000400f0e <+18>:  je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:  callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:  jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:  mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:  add    %eax,%eax
   0x0000000000400f1c <+32>:  cmp    %eax,(%rbx)
   0x0000000000400f1e <+34>:  je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:  callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:  add    $0x4,%rbx
   0x0000000000400f29 <+45>:  cmp    %rbp,%rbx
   0x0000000000400f2c <+48>:  jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:  jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:  lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:  lea    0x18(%rsp),%rbp
   0x0000000000400f3a <+62>:  jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:  add    $0x28,%rsp
   0x0000000000400f40 <+68>:  pop    %rbx
   0x0000000000400f41 <+69>:  pop    %rbp
   0x0000000000400f42 <+70>:  retq   

<+9>调用read_six_numbers
<+18>要求第一个数必须为1
然后是一个循环,要求后一个数是前一个数的二倍
因此答案为 1 2 4 8 16 32

phase_3

   0x0000000000400f43 <+0>:   sub    $0x18,%rsp
   0x0000000000400f47 <+4>:   lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:   lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:  mov    $0x4025cf,%esi
   0x0000000000400f56 <+19>:  mov    $0x0,%eax
   0x0000000000400f5b <+24>:  callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000400f60 <+29>:  cmp    $0x1,%eax
   0x0000000000400f63 <+32>:  jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:  callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:  cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:  ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:  mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:  jmpq   *0x402470(,%rax,8)
   0x0000000000400f7c <+57>:  mov    $0xcf,%eax
   0x0000000000400f81 <+62>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:  mov    $0x2c3,%eax
   0x0000000000400f88 <+69>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:  mov    $0x100,%eax
   0x0000000000400f8f <+76>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:  mov    $0x185,%eax
   0x0000000000400f96 <+83>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:  mov    $0xce,%eax
   0x0000000000400f9d <+90>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:  mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:  mov    $0x147,%eax
   0x0000000000400fab <+104>: jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>: callq  0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>: mov    $0x0,%eax
   0x0000000000400fb7 <+116>: jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>: mov    $0x137,%eax
   0x0000000000400fbe <+123>: cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>: je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>: callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>: add    $0x18,%rsp
   0x0000000000400fcd <+138>: retq  

<+14>蜜汁内存地址0x4025cf
x/s 0x4025cf得到 "%d %d"
sscanf第二个参数,即输入格式为2个整数
eax为成功赋值参数个数
<+32>强制eax>1,即传入两个参数
可以发现传入的第一个参数地址为$rsp+0x8,第二个参数地址为$rsp+0xc
<+44>要求第一个参数小于等于7
<+50>跳转*(0x402470+8rax),此时rax为第一个参数的值
看一下内存0x402470后的值

(gdb) x/8xg 0x402470
0x402470:   0x0000000000400f7c  0x0000000000400fb9
0x402480:   0x0000000000400f83  0x0000000000400f8a
0x402490:   0x0000000000400f91  0x0000000000400f98
0x4024a0:   0x0000000000400f9f  0x0000000000400fa6

即对于每个rax,会跳转到一个位置,以第一个参数为7为例:
会跳转到0x400fa6,然后比较第二个参数与0x147是否相等
因此7 327 (0x147=327)为一组解,理论上应该有八组解

phase_4

   0x000000000040100c <+0>: sub    $0x18,%rsp
   0x0000000000401010 <+4>: lea    0xc(%rsp),%rcx
   0x0000000000401015 <+9>: lea    0x8(%rsp),%rdx
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx
   0x000000000040103f <+51>:    mov    $0x0,%esi
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi
   0x0000000000401048 <+60>:    callq  0x400fce <func4>
   0x000000000040104d <+65>:    test   %eax,%eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    retq  

同理可以发现仍然需要两个输入数
<+34>说明第一个参数小于0xe
<+69>要求第二个参数为0(所以要他何用
<+60>调用函数func4,传入三个参数,分别为0xe,0x0,phase_4的第一个参数
<+67>要求func4返回值为0
然后看一下func4长什么样:
其实把第一个参数从0试到0xe也行

   0x0000000000400fce <+0>: sub    $0x8,%rsp
   0x0000000000400fd2 <+4>: mov    %edx,%eax
   0x0000000000400fd4 <+6>: sub    %esi,%eax
   0x0000000000400fd6 <+8>: mov    %eax,%ecx
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
   0x0000000000400fdb <+13>:    add    %ecx,%eax
   0x0000000000400fdd <+15>:    sar    %eax
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx
   0x0000000000400fe9 <+27>:    callq  0x400fce <func4>
   0x0000000000400fee <+32>:    add    %eax,%eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi
   0x0000000000400ffe <+48>:    callq  0x400fce <func4>
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    retq   

看起来是一个奇怪的递归函数,不过不要慌,我们只需要让这个函数返回0就行了
然后可以发现,只要rdi=7就可以跳过那坨递归直接返回一个0。。。
所以 7 0 就行了。
其实答案不止7一个

phase_5

=> 0x0000000000401062 <+0>:   push   %rbx
   0x0000000000401063 <+1>:   sub    $0x20,%rsp
   0x0000000000401067 <+5>:   mov    %rdi,%rbx
   0x000000000040106a <+8>:   mov    %fs:0x28,%rax
   0x0000000000401073 <+17>:  mov    %rax,0x18(%rsp)
   0x0000000000401078 <+22>:  xor    %eax,%eax
   0x000000000040107a <+24>:  callq  0x40131b <string_length>
   0x000000000040107f <+29>:  cmp    $0x6,%eax
   0x0000000000401082 <+32>:  je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:  callq  0x40143a <explode_bomb>
   0x0000000000401089 <+39>:  jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:  movzbl (%rbx,%rax,1),%ecx
   0x000000000040108f <+45>:  mov    %cl,(%rsp)
   0x0000000000401092 <+48>:  mov    (%rsp),%rdx
   0x0000000000401096 <+52>:  and    $0xf,%edx
   0x0000000000401099 <+55>:  movzbl 0x4024b0(%rdx),%edx
   0x00000000004010a0 <+62>:  mov    %dl,0x10(%rsp,%rax,1)
   0x00000000004010a4 <+66>:  add    $0x1,%rax
   0x00000000004010a8 <+70>:  cmp    $0x6,%rax
   0x00000000004010ac <+74>:  jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:  movb   $0x0,0x16(%rsp)
   0x00000000004010b3 <+81>:  mov    $0x40245e,%esi
   0x00000000004010b8 <+86>:  lea    0x10(%rsp),%rdi
   0x00000000004010bd <+91>:  callq  0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:  test   %eax,%eax
   0x00000000004010c4 <+98>:  je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>: callq  0x40143a <explode_bomb>
   0x00000000004010cb <+105>: nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>: jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>: mov    $0x0,%eax
   0x00000000004010d7 <+117>: jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>: mov    0x18(%rsp),%rax
   0x00000000004010de <+124>: xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>: je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>: callq  0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>: add    $0x20,%rsp
   0x00000000004010f2 <+144>: pop    %rbx
   0x00000000004010f3 <+145>: retq  

<+32> 说明输入是一个长度为6的字符串。
然后进入一个循环<+41>~<+74>
枚举输入的字符,取其&$0xf后的数edx,然后把edx+0x4024b的值赋到$rsp+0x10+i(i为1到6的循环变量)
看一下0x4024b有啥

(gdb) x/s 0x4024b0
0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

其实只有前面一段"maduiersnfotvbyl"有用
然后<+76>~<+98>
比较字符串$rsp+0x10和0x40245e是否相等

(gdb) x/s 0x40245e
0x40245e:   "flyers"

也就是说我们需要通过凑出一个"flyers"
输入字符串每一个字符ascii的后四个bit对应"maduiersnfotvbyl"的下标,凑出一个"flyers"
一个可行解是"9?>567"

phase_6

这个phase跟前面画风不太一样啊。。。

   0x00000000004010f4 <+0>:   push   %r14
   0x00000000004010f6 <+2>:   push   %r13
   0x00000000004010f8 <+4>:   push   %r12
   0x00000000004010fa <+6>:   push   %rbp
   0x00000000004010fb <+7>:   push   %rbx
   0x00000000004010fc <+8>:   sub    $0x50,%rsp
   0x0000000000401100 <+12>:  mov    %rsp,%r13
   0x0000000000401103 <+15>:  mov    %rsp,%rsi
   0x0000000000401106 <+18>:  callq  0x40145c <read_six_numbers>
   0x000000000040110b <+23>:  mov    %rsp,%r14
   0x000000000040110e <+26>:  mov    $0x0,%r12d
   0x0000000000401114 <+32>:  mov    %r13,%rbp
   0x0000000000401117 <+35>:  mov    0x0(%r13),%eax
   0x000000000040111b <+39>:  sub    $0x1,%eax
   0x000000000040111e <+42>:  cmp    $0x5,%eax
   0x0000000000401121 <+45>:  jbe    0x401128 <phase_6+52>
   0x0000000000401123 <+47>:  callq  0x40143a <explode_bomb>
   0x0000000000401128 <+52>:  add    $0x1,%r12d
   0x000000000040112c <+56>:  cmp    $0x6,%r12d
   0x0000000000401130 <+60>:  je     0x401153 <phase_6+95>
   0x0000000000401132 <+62>:  mov    %r12d,%ebx
   0x0000000000401135 <+65>:  movslq %ebx,%rax
   0x0000000000401138 <+68>:  mov    (%rsp,%rax,4),%eax
   0x000000000040113b <+71>:  cmp    %eax,0x0(%rbp)
   0x000000000040113e <+74>:  jne    0x401145 <phase_6+81>
   0x0000000000401140 <+76>:  callq  0x40143a <explode_bomb>
   0x0000000000401145 <+81>:  add    $0x1,%ebx
   0x0000000000401148 <+84>:  cmp    $0x5,%ebx
   0x000000000040114b <+87>:  jle    0x401135 <phase_6+65>
   0x000000000040114d <+89>:  add    $0x4,%r13
   0x0000000000401151 <+93>:  jmp    0x401114 <phase_6+32>
   0x0000000000401153 <+95>:  lea    0x18(%rsp),%rsi
   0x0000000000401158 <+100>: mov    %r14,%rax
   0x000000000040115b <+103>: mov    $0x7,%ecx
   0x0000000000401160 <+108>: mov    %ecx,%edx
   0x0000000000401162 <+110>: sub    (%rax),%edx
   0x0000000000401164 <+112>: mov    %edx,(%rax)
   0x0000000000401166 <+114>: add    $0x4,%rax
   0x000000000040116a <+118>: cmp    %rsi,%rax
   0x000000000040116d <+121>: jne    0x401160 <phase_6+108>
   0x000000000040116f <+123>: mov    $0x0,%esi
   0x0000000000401174 <+128>: jmp    0x401197 <phase_6+163>
   0x0000000000401176 <+130>: mov    0x8(%rdx),%rdx
   0x000000000040117a <+134>: add    $0x1,%eax
   0x000000000040117d <+137>: cmp    %ecx,%eax
   0x000000000040117f <+139>: jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>: jmp    0x401188 <phase_6+148>
   0x0000000000401183 <+143>: mov    $0x6032d0,%edx
   0x0000000000401188 <+148>: mov    %rdx,0x20(%rsp,%rsi,2)
   0x000000000040118d <+153>: add    $0x4,%rsi
   0x0000000000401191 <+157>: cmp    $0x18,%rsi
   0x0000000000401195 <+161>: je     0x4011ab <phase_6+183>
   0x0000000000401197 <+163>: mov    (%rsp,%rsi,1),%ecx
   0x000000000040119a <+166>: cmp    $0x1,%ecx
   0x000000000040119d <+169>: jle    0x401183 <phase_6+143>
   0x000000000040119f <+171>: mov    $0x1,%eax
   0x00000000004011a4 <+176>: mov    $0x6032d0,%edx
   0x00000000004011a9 <+181>: jmp    0x401176 <phase_6+130>
   0x00000000004011ab <+183>: mov    0x20(%rsp),%rbx
   0x00000000004011b0 <+188>: lea    0x28(%rsp),%rax
   0x00000000004011b5 <+193>: lea    0x50(%rsp),%rsi
   0x00000000004011ba <+198>: mov    %rbx,%rcx
   0x00000000004011bd <+201>: mov    (%rax),%rdx
   0x00000000004011c0 <+204>: mov    %rdx,0x8(%rcx)
   0x00000000004011c4 <+208>: add    $0x8,%rax
   0x00000000004011c8 <+212>: cmp    %rsi,%rax
   0x00000000004011cb <+215>: je     0x4011d2 <phase_6+222>
   0x00000000004011cd <+217>: mov    %rdx,%rcx
   0x00000000004011d0 <+220>: jmp    0x4011bd <phase_6+201>
   0x00000000004011d2 <+222>: movq   $0x0,0x8(%rdx)
   0x00000000004011da <+230>: mov    $0x5,%ebp
   0x00000000004011df <+235>: mov    0x8(%rbx),%rax
   0x00000000004011e3 <+239>: mov    (%rax),%eax
   0x00000000004011e5 <+241>: cmp    %eax,(%rbx)
   0x00000000004011e7 <+243>: jge    0x4011ee <phase_6+250>
   0x00000000004011e9 <+245>: callq  0x40143a <explode_bomb>
   0x00000000004011ee <+250>: mov    0x8(%rbx),%rbx
   0x00000000004011f2 <+254>: sub    $0x1,%ebp
   0x00000000004011f5 <+257>: jne    0x4011df <phase_6+235>
   0x00000000004011f7 <+259>: add    $0x50,%rsp
   0x00000000004011fb <+263>: pop    %rbx
   0x00000000004011fc <+264>: pop    %rbp
   0x00000000004011fd <+265>: pop    %r12
   0x00000000004011ff <+267>: pop    %r13
   0x0000000000401201 <+269>: pop    %r14
   0x0000000000401203 <+271>: retq  

一个巨长的汇编代码,各种跳转。。。
不过努力分析一波可以发现这其实是一坨循环组成的
可以发现输入是6个数
<+32>~<+95>判断输入是不是一个1到6的排列

<+108>~<+121>把排列的所有数变成7-x(强行增加难度

<+128>~<+183>这段比较蛋疼,用力看一下,里面有一个蜜汁内存地址0x6032d0
里面是长这样的:

(gdb) x/12xg 0x6032d0
0x6032d0 <node1>:   0x000000010000014c  0x00000000006032e0
0x6032e0 <node2>:   0x00000002000000a8  0x00000000006032f0
0x6032f0 <node3>:   0x000000030000039c  0x0000000000603300
0x603300 <node4>:   0x00000004000002b3  0x0000000000603310
0x603310 <node5>:   0x00000005000001dd  0x0000000000603320
0x603320 <node6>:   0x00000006000001bb  0x0000000000000000

然后这段代码相当于把排列做了一个映射

1->0x00000000006032e0
2->0x00000000006032f0
3->0x0000000000603300
4->0x0000000000603310
5->0x0000000000603320
6->0x0000000000000000

然后接到原排列后面

<+201>~<+222>
其实最后两段是最蛋疼的
这一段相当于搞了一个类似链表的东西
把内存0x6032d0到0x6032e0这段做了一个轮换
(这段可以分成6组,每组由两个8位的数构成,一组中的第一个存一个数值,第二个存一个地址,对其中第二个做一个轮换)

<+235>~<+257>
这段是按上面那个链表的顺序访问访问每组,要求每组的第一个元素后四位递减顺序出现

0x000000010000014c->14c 
0x00000002000000a8->0a8 
0x000000030000039c->39c 
0x00000004000002b3->2b3 
0x00000005000001dd->1dd 
0x00000006000001bb->1bb 

然后就可以确定这个初始的排列了。。。

好像还有个隐藏关卡?
以后再说吧
强行完结撒花

好像几百年没更博了。。。

最近在学cmu的csapp,没有学号不能在cmu上交
不过可以下官方的自学lab

datalab断断续续搞了两三天QAQ
就不贴官方要求了

1.bitAnd

用 ~,| 实现按位与

int bitAnd(int x, int y) {
    return ~((~x)|(~y));
}

2.getByte

获得第n个byte

int getByte(int x, int n) {
    return (x>>(n<<3))&0xff;
}

3.logicalShift

逻辑右移n位
把最高的n-1位置0

int logicalShift(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    return (x>>n)&v2;
}

4.bitCount

计算所有位中1的个数,限制40个ops
开始确实没想到可以用类似分治一次搞多位。
就是每次把连续$$2^k$$个bit的和计算出来放在原来的位置
这个东西可以所有位一起搞

int bitCount(int x) {

    int t0 = 0x55|(0x55<<8);
    int v0 = t0|(t0<<16);
    int x0 = (x&v0)+((x>>1)&v0);

    int t1 = 0x33|(0x33<<8);
    int v1 = t1|(t1<<16);
    int x1 = (x0&v1)+((x0>>2)&v1);

    int t2 = 0xf|(0xf<<8);
    int v2 = t2|(t2<<16);
    int x2 = (x1&v2)+((x1>>4)&v2);

    int v3 = 0xff|(0xff<<16);
    int x3 = (x2&v3)+((x2>>8)&v3);

    int v4 = 0xff|(0xff<<8);
    int x4 = (x3&v4)+((x3>>16)&v4);

    return x4;
}

5.bang

不用!实现!
把所有位或到第一位就好了,每次折半

int bang(int x) {
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return (~x)&1;
}

6.tmin

最小的two's complement number -2147483648

int tmin(void) {
    return 1 << 31;
}

7.fitsBits

数x是否可以被表示成n个bit的数
就是判断最高32-n+1位是否相同
因为要实现logicalshift写的极丑,还特判了n=32

int fitsBits(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    x ^= x >> 31;
    return (n>>5&1)|(!((x << 1 >> n)&v2));
}

8.divpwr2

$$x/2^k$$向0取整
负数的话判断一下前n位有没有东西,如果有就+1

int divpwr2(int x, int n) {
    int v1 = x>>31&1;
    int v2 = !!((x>>n<<n)^x);
    return (x>>n)+(v1&v2);
}

9.negate

返回-x

int negate(int x) {
    return ~x + 1;
}

10.isPositive

返回x是否大于0
判0或负数

int isPositive(int x) {
    return !((!(x&~(1<<31)))|(x>>31));
}

11.isLessOrEqual

比较x是否小于等于y
首先比较符号是否相同
符号不同返回x为负
符号相同返回y-x非负

int isLessOrEqual(int x, int y) {
    int v2 = (x>>31)&1;
    int v1 = v2^((y>>31)&1);
    int v3 = y+((~x)+1);
    int v4 = !((v3>>31)&1);
    return (v1&v2)|((!v1)&v4);
}

12.ilog2

返回最高位位置(log下取整)
优雅的二分

int ilog2(int x) {
    int ret = 0;
    int t1 = 0;

    t1 = !(x>>16);
    ret = (!t1)<<4;
    x = x>>(16^(t1<<4));

    t1 = !(x>>8);
    ret |= (!t1)<<3;
    x = x>>(8^(t1<<3));

    t1 = !(x>>4);
    ret |= (!t1)<<2;
    x = x>>(4^(t1<<2));

    t1 = !(x>>2);
    ret |= (!t1)<<1;
    x = x>>(2^(t1<<1));

    return ret|(x>>1);
}

13.float_neg

为啥到这函数名就变下划线了啊啊啊啊
传入一个unsigned表示一个float格式的数,返回-x
判一下nan,把符号位反过来

unsigned float_neg(unsigned uf) {
    unsigned v = uf;
    unsigned frac = 0;
    unsigned exp = 0;
    unsigned s = 0;
    unsigned nf = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;
    nf = uf^0x80000000;
    if(exp == 0xff && frac)
        return uf;
    return nf;
}

14.float_i2f

把int转成float
首先特判掉0和-2147483648(雾)
然后记一下符号位,转成正数
然后如果不到23位就补到23位,如果超了的话emmm,round to nearest even了解一下~~~

unsigned float_i2f(int x) {
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned tx = x;
    unsigned num = 0;
    unsigned pre = 0;
    if(!tx) return 0u;
    if(tx == 0x80000000) return 0xcf000000;
    if(tx&0x80000000)
        s = 0x80000000, tx = -tx;
    exp = 150;
    while(tx < 0x800000)
        tx <<= 1,exp--;
    while(tx >= 0x1000000)
    {
        pre = tx & 1;
        num += pre;
        tx >>= 1; exp++;
    }
    if( pre && (num + (tx&1) >= 2))
    {
        tx++;
        if(tx >= 0x1000000)
            tx >>= 1, exp++;
    } 
    frac = tx^0x800000;
    return frac | (exp<<23) | s;
}

15.float_twice

传入一个unsigned表示一个float格式的数,返回2x
判掉nan和inf
再判一下2x会不会到inf
再判一下是不是normalized的
再判一下会不会到normalized

unsigned float_twice(unsigned uf) {
    unsigned v = uf;
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned exp1 = 0;
    unsigned frac1 = 0;
    unsigned s1 = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;

    exp1 = exp;
    frac1 = frac;
    s1 = s;

    if(exp == 0xff)
        return uf;

    if(exp == 0xfe)
        exp1 = 0xff, frac1 = 0;
    else if(exp == 0)
    {
        if((frac >> 23) & 1)
        {
            frac1 ^= 1<<23;
            exp1 = 1;
        }
        frac1 <<= 1;
    }
    else exp1++;

    return frac1 | (exp1<<23) | (s1<<31);
}