JonathanSalwan / Triton

Triton is a dynamic binary analysis library. Build your own program analysis tools, automate your reverse engineering, perform software verification or just emulate code.
https://triton-library.github.io
Apache License 2.0
3.4k stars 524 forks source link

Reduce AstNode hash collisions #1224

Closed ndrewh closed 1 year ago

ndrewh commented 1 year ago

Rationale

Disclaimer: I am not a mathematician

Here is the existing hash2n: https://github.com/JonathanSalwan/Triton/blob/48de90d395a626c6247f0d71abd6cac1290daf62/src/libtriton/ast/ast.cpp#L3465-L3470

Problem:

>>> def hash2n(h, n):
...     mask = (1 << 512)-1
...     for i in range(n):
...         h = (h*h) & mask
...     return h
...
>>> hex(hash2n(0x234567634254235abcdef347429930357493234568, 6))
'0xe5e18ae21077c93b662e1178fad20e6f28cb5ec2729268fd1fdcee1eba6a4aa98d0ba763cc453901000000000000000000000000000000000000000000000000'
>>> hex(hash2n(0x234567634254235abcdef347429930357493234568, 8))
'0x0'
>>> hex(hash2n(0x234567634254235abcdef347429930357493234569, 6))
'0x51c42032b604df2f5518592a48f2c8a77f8514bad777283e7e8c56c8855115221358021fdc912b71bc7bf2344f908b2d0e6ddab534f3bd1e0bf69fb856e9201'