Skip to content

Instantly share code, notes, and snippets.

@recuraki
Created February 21, 2021 04:37
Show Gist options
  • Save recuraki/c1d0236c302eb8c280d9bf5993488383 to your computer and use it in GitHub Desktop.
Save recuraki/c1d0236c302eb8c280d9bf5993488383 to your computer and use it in GitHub Desktop.
ハッシュ衝突をさせたい
"""
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
assert(keys != NULL);
const size_t mask = DK_MASK(keys);
size_t i = hash & mask;
Py_ssize_t ix = dictkeys_get_index(keys, i);
printf("find_empty_slot %lx %lx %lx\n", mask, i, ix);
printf("find_empty_slot inputhash %lx\n", hash);
for (size_t perturb = hash; ix >= 0;) {
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
printf("loopb key:%lx per:%lx i:%lx ix:%lx\n", keys, perturb,i , ix);
ix = dictkeys_get_index(keys, i);
printf("loopa key:%lx per:%lx i:%lx ix:%lx\n", keys, perturb,i , ix);
}
printf("find_empty_slot RES %lx %lx %lx\n", mask,i , ix);
return i;
}
"""
PERTURB_SHIFT = 5
used = dict()
vala = 10
valb = (10<<10)*5-1
nn = 5
data = []
datb = []
hash = vala
mask = 2**8 - 1
i = hash & mask
perturb = hash
magic = [2,52,460,511,867]
for loop in range(nn):
perturb >>= PERTURB_SHIFT
i = (i * 5 + perturb + 1) & mask
print(">", loop, hex(i))
data.append(hex(i))
print("-------------------")
res = []
for hashcore in range(10000000):
for hashdiff in range(1):
hash = (hashcore << 0) + hashdiff
datb = []
i = hash & mask
perturb = hash
for loop in range(nn):
perturb >>= PERTURB_SHIFT
i = (i * 5 + perturb + 1) & mask
#print(">", loop, hex(i))
datb.append(hex(i))
if data == datb:
print(hashcore, hashdiff)
print(hash,"\t", hex(hash), "{:040b}".format(hash),"{:010b}".format(hash<<30>>30 & 2**12-1))
res.append(hash)
print(res)
import sys
sys.exit(1)
print("-------------------")
res = []
for hashcore in range(10000):
hash = 2 ** 125 -1 + hashcore
datb = []
i = hash & mask
perturb = hash
for loop in range(nn):
perturb >>= PERTURB_SHIFT
i = (i * 5 + perturb + 1) & mask
#print(">", loop, hex(i))
datb.append(hex(i))
if data == datb:
print(hash,"\t", hex(hash), "{:040b}".format(hash),"{:010b}".format(hash<<30>>30 & 2**12-1))
res.append(hash)
#print(res)
d = dict()
print(res)
print("res")
print("--")
for i in range(len(res )- 1):
print(res[i+1] - res[i+0])
for x in res:
d[x] = True
print(d)
print("--")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment