phf.py (1208B)
1 import random 2 # inputs = ["GET", "HEAD", "POST", "PUT", "DELETE", 3 # "CONNECT", "OPTIONS", "TRACE"] 4 5 # int_inputs = [int.from_bytes(bytes(i, 'ascii'), 'little') for i in inputs] 6 7 # answers = list(range(8)) 8 9 inps = [random.randrange(2**32) for i in range(100000)] 10 11 def is_phf(h, inputs): 12 return len({h(x) for x in inputs}) == len(inputs) 13 14 def colls(h, inputs): 15 return len({h(x) for x in inputs}) 16 17 # print(next(m for m in range(9, 2**32) if is_phf(lambda x: x % m, int_inputs))) 18 19 def h(x, c): 20 m = (x * c) % 2**32 21 return m 22 23 # out = [0]*8 24 # idxs = list(h(x, 0x1b8b6e6d) for x in int_inputs) 25 26 # for i, idx in enumerate(idxs): 27 # out[idx] = answers[i] 28 29 # print([inputs[i] for i in out]) 30 # print(list(out[h(x, 0x1b8b6e6d)] for x in int_inputs)) 31 32 best = float('-inf') 33 while best < len(inps): 34 c = random.randrange(2**32) 35 # max_idx = max(h(x, c) for x in int_inputs) 36 cls = colls(lambda x: h(x, c), inps) 37 if cls > best: 38 print(cls, hex(c)) 39 best = cls 40 41 42 43 # for i in inputs: 44 # print(i, " ") 45 # for c in i[::-1]: 46 # print(hex(ord(c))[2:], end=" ") 47 # print(" ") 48 # print(int.from_bytes(bytes(i, 'ascii'), 'little')) 49 # print("\n")