forked from python-pillow/Pillow
/
make_hash.py
66 lines (55 loc) · 1.24 KB
/
make_hash.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# brute-force search for access descriptor hash table
modes = [
"1",
"L",
"LA",
"La",
"I",
"I;16",
"I;16L",
"I;16B",
"I;32L",
"I;32B",
"F",
"P",
"PA",
"RGB",
"RGBA",
"RGBa",
"RGBX",
"CMYK",
"YCbCr",
"LAB",
"HSV",
]
def hash(s, i):
# djb2 hash: multiply by 33 and xor character
for c in s:
i = (((i << 5) + i) ^ ord(c)) & 0xFFFFFFFF
return i
def check(size, i0):
h = [None] * size
for m in modes:
i = hash(m, i0)
i = i % size
if h[i]:
return 0
h[i] = m
return h
min_start = 0
# 1) find the smallest table size with no collisions
for min_size in range(len(modes), 16384):
if check(min_size, 0):
print(len(modes), "modes fit in", min_size, "slots")
break
# 2) see if we can do better with a different initial value
for i0 in range(65556):
for size in range(1, min_size):
if check(size, i0):
if size < min_size:
print(len(modes), "modes fit in", size, "slots with start", i0)
min_size = size
min_start = i0
print()
print("#define ACCESS_TABLE_SIZE", min_size)
print("#define ACCESS_TABLE_HASH", min_start)