← Back to branch summary

~ubuntu-branches/ubuntu/wily/python-imaging/wily

« back to all changes in this revision

Viewing changes to Tests/make_hash.py

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2013-01-31 20:49:20 UTC
  • mfrom: (1.1.4)
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130131204920-7tnuhqhlsqdza4c2
Rewrite build dependencies to allow cross builds.

Show diffs side-by-side

added added

removed removed

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