今天逆向某个程序的时候发现了下面的代码:
注意 movabs 那条指令将一个很奇怪的 64 位立即数赋值给了 rbp,后面又有 mul 指令,可以推测出它是用乘法、加减法和位运算模拟除法或取模指令(可以参考RE4B里面除以9的那章)。
这里我没找到任何线索,于是用 Python 模拟了一下:
然后打出输入为200之内的结果:
发现其实这个函数就是 r64%53.
这个的实现原理是什么呢?
刚刚再细看了一下,0x35就是53,所以最后两个操作是商 rax 乘 53,然后被除数 r64 减去 rax*53 得到余数,剩下的问题就是前面除以 53 是怎么做的,原理和 RE4B 里面讲的应该一样。
不过有点奇怪的就是移位因子的选择问题,怎样选择移位因子才能保证没有误差?
代码:
| 0x180000595 4c8b01 mov r8, qword [rcx]
| 0x180000598 48bd53138cb7. movabs rbp, 0x3521cfb2b78c1353
| 0x1800005a2 488bf2 mov rsi, rdx
| 0x1800005a5 4c334108 xor r8, qword [rcx + 8]
| 0x1800005a9 488bc5 mov rax, rbp
| 0x1800005ac 4c8d25cd0b00. lea r12, [0x180001180]
| 0x1800005b3 488bf9 mov rdi, rcx
| 0x1800005b6 49f7e0 mul r8
| 0x1800005b9 498bc0 mov rax, r8
| 0x1800005bc 482bc2 sub rax, rdx
| 0x1800005bf 48d1e8 shr rax, 1
| 0x1800005c2 4803c2 add rax, rdx
| 0x1800005c5 48c1e805 shr rax, 5
| 0x1800005c9 486bc035 imul rax, rax, 0x35
| 0x1800005cd 4c2bc0 sub r8, rax
| 0x1800005d0 4b8b5cc418 mov rbx, qword [r12 + r8*8 + 0x18]
注意 movabs 那条指令将一个很奇怪的 64 位立即数赋值给了 rbp,后面又有 mul 指令,可以推测出它是用乘法、加减法和位运算模拟除法或取模指令(可以参考RE4B里面除以9的那章)。
这里我没找到任何线索,于是用 Python 模拟了一下:
代码:
def fn(r64):
rdx = ((r64 * 0x3521cfb2b78c1353) >> 64)
rax = r64 - rdx
rax = rax >> 1
rax = rax + rdx
rax = rax >> 5
rax = rax * 0x35
return r64 - rax
然后打出输入为200之内的结果:
代码:
for i in range(200):
print(fn(i))
发现其实这个函数就是 r64%53.
这个的实现原理是什么呢?
刚刚再细看了一下,0x35就是53,所以最后两个操作是商 rax 乘 53,然后被除数 r64 减去 rax*53 得到余数,剩下的问题就是前面除以 53 是怎么做的,原理和 RE4B 里面讲的应该一样。
不过有点奇怪的就是移位因子的选择问题,怎样选择移位因子才能保证没有误差?