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
|
# brute-force search for access descriptor hash table
import random
modes = [
"1",
"L", "LA",
"I", "I;16", "I;16L", "I;16B", "I;32L", "I;32B",
"F",
"P", "PA",
"RGB", "RGBA", "RGBa", "RGBX",
"CMYK",
"YCbCr",
]
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 check(min_size, min_start)
print("#define ACCESS_TABLE_SIZE", min_size)
print("#define ACCESS_TABLE_HASH", min_start)
# for m in modes:
# print m, "=>", hash(m, min_start) % min_size
|