diff -r ffa851df0825 -r 2fb8b9db1c86 symbian-qemu-0.9.1-12/python-2.6.1/Tools/unicode/makeunicodedata.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/symbian-qemu-0.9.1-12/python-2.6.1/Tools/unicode/makeunicodedata.py Fri Jul 31 15:01:17 2009 +0100 @@ -0,0 +1,963 @@ +# +# (re)generate unicode property and type databases +# +# this script converts a unicode 3.2 database file to +# Modules/unicodedata_db.h, Modules/unicodename_db.h, +# and Objects/unicodetype_db.h +# +# history: +# 2000-09-24 fl created (based on bits and pieces from unidb) +# 2000-09-25 fl merged tim's splitbin fixes, separate decomposition table +# 2000-09-25 fl added character type table +# 2000-09-26 fl added LINEBREAK, DECIMAL, and DIGIT flags/fields (2.0) +# 2000-11-03 fl expand first/last ranges +# 2001-01-19 fl added character name tables (2.1) +# 2001-01-21 fl added decomp compression; dynamic phrasebook threshold +# 2002-09-11 wd use string methods +# 2002-10-18 mvl update to Unicode 3.2 +# 2002-10-22 mvl generate NFC tables +# 2002-11-24 mvl expand all ranges, sort names version-independently +# 2002-11-25 mvl add UNIDATA_VERSION +# 2004-05-29 perky add east asian width information +# 2006-03-10 mvl update to Unicode 4.1; add UCD 3.2 delta +# +# written by Fredrik Lundh (fredrik@pythonware.com) +# + +import sys + +SCRIPT = sys.argv[0] +VERSION = "2.6" + +# The Unicode Database +UNIDATA_VERSION = "5.1.0" +UNICODE_DATA = "UnicodeData%s.txt" +COMPOSITION_EXCLUSIONS = "CompositionExclusions%s.txt" +EASTASIAN_WIDTH = "EastAsianWidth%s.txt" + +old_versions = ["3.2.0"] + +CATEGORY_NAMES = [ "Cn", "Lu", "Ll", "Lt", "Mn", "Mc", "Me", "Nd", + "Nl", "No", "Zs", "Zl", "Zp", "Cc", "Cf", "Cs", "Co", "Cn", "Lm", + "Lo", "Pc", "Pd", "Ps", "Pe", "Pi", "Pf", "Po", "Sm", "Sc", "Sk", + "So" ] + +BIDIRECTIONAL_NAMES = [ "", "L", "LRE", "LRO", "R", "AL", "RLE", "RLO", + "PDF", "EN", "ES", "ET", "AN", "CS", "NSM", "BN", "B", "S", "WS", + "ON" ] + +EASTASIANWIDTH_NAMES = [ "F", "H", "W", "Na", "A", "N" ] + +# note: should match definitions in Objects/unicodectype.c +ALPHA_MASK = 0x01 +DECIMAL_MASK = 0x02 +DIGIT_MASK = 0x04 +LOWER_MASK = 0x08 +LINEBREAK_MASK = 0x10 +SPACE_MASK = 0x20 +TITLE_MASK = 0x40 +UPPER_MASK = 0x80 +NODELTA_MASK = 0x100 + +def maketables(trace=0): + + print "--- Reading", UNICODE_DATA % "", "..." + + version = "" + unicode = UnicodeData(UNICODE_DATA % version, + COMPOSITION_EXCLUSIONS % version, + EASTASIAN_WIDTH % version) + + print len(filter(None, unicode.table)), "characters" + + for version in old_versions: + print "--- Reading", UNICODE_DATA % ("-"+version), "..." + old_unicode = UnicodeData(UNICODE_DATA % ("-"+version), + COMPOSITION_EXCLUSIONS % ("-"+version), + EASTASIAN_WIDTH % ("-"+version)) + print len(filter(None, old_unicode.table)), "characters" + merge_old_version(version, unicode, old_unicode) + + makeunicodename(unicode, trace) + makeunicodedata(unicode, trace) + makeunicodetype(unicode, trace) + +# -------------------------------------------------------------------- +# unicode character properties + +def makeunicodedata(unicode, trace): + + dummy = (0, 0, 0, 0, 0) + table = [dummy] + cache = {0: dummy} + index = [0] * len(unicode.chars) + + FILE = "Modules/unicodedata_db.h" + + print "--- Preparing", FILE, "..." + + # 1) database properties + + for char in unicode.chars: + record = unicode.table[char] + if record: + # extract database properties + category = CATEGORY_NAMES.index(record[2]) + combining = int(record[3]) + bidirectional = BIDIRECTIONAL_NAMES.index(record[4]) + mirrored = record[9] == "Y" + eastasianwidth = EASTASIANWIDTH_NAMES.index(record[15]) + item = ( + category, combining, bidirectional, mirrored, eastasianwidth + ) + # add entry to index and item tables + i = cache.get(item) + if i is None: + cache[item] = i = len(table) + table.append(item) + index[char] = i + + # 2) decomposition data + + decomp_data = [0] + decomp_prefix = [""] + decomp_index = [0] * len(unicode.chars) + decomp_size = 0 + + comp_pairs = [] + comp_first = [None] * len(unicode.chars) + comp_last = [None] * len(unicode.chars) + + for char in unicode.chars: + record = unicode.table[char] + if record: + if record[5]: + decomp = record[5].split() + if len(decomp) > 19: + raise Exception, "character %x has a decomposition too large for nfd_nfkd" % char + # prefix + if decomp[0][0] == "<": + prefix = decomp.pop(0) + else: + prefix = "" + try: + i = decomp_prefix.index(prefix) + except ValueError: + i = len(decomp_prefix) + decomp_prefix.append(prefix) + prefix = i + assert prefix < 256 + # content + decomp = [prefix + (len(decomp)<<8)] +\ + map(lambda s: int(s, 16), decomp) + # Collect NFC pairs + if not prefix and len(decomp) == 3 and \ + char not in unicode.exclusions and \ + unicode.table[decomp[1]][3] == "0": + p, l, r = decomp + comp_first[l] = 1 + comp_last[r] = 1 + comp_pairs.append((l,r,char)) + try: + i = decomp_data.index(decomp) + except ValueError: + i = len(decomp_data) + decomp_data.extend(decomp) + decomp_size = decomp_size + len(decomp) * 2 + else: + i = 0 + decomp_index[char] = i + + f = l = 0 + comp_first_ranges = [] + comp_last_ranges = [] + prev_f = prev_l = None + for i in unicode.chars: + if comp_first[i] is not None: + comp_first[i] = f + f += 1 + if prev_f is None: + prev_f = (i,i) + elif prev_f[1]+1 == i: + prev_f = prev_f[0],i + else: + comp_first_ranges.append(prev_f) + prev_f = (i,i) + if comp_last[i] is not None: + comp_last[i] = l + l += 1 + if prev_l is None: + prev_l = (i,i) + elif prev_l[1]+1 == i: + prev_l = prev_l[0],i + else: + comp_last_ranges.append(prev_l) + prev_l = (i,i) + comp_first_ranges.append(prev_f) + comp_last_ranges.append(prev_l) + total_first = f + total_last = l + + comp_data = [0]*(total_first*total_last) + for f,l,char in comp_pairs: + f = comp_first[f] + l = comp_last[l] + comp_data[f*total_last+l] = char + + print len(table), "unique properties" + print len(decomp_prefix), "unique decomposition prefixes" + print len(decomp_data), "unique decomposition entries:", + print decomp_size, "bytes" + print total_first, "first characters in NFC" + print total_last, "last characters in NFC" + print len(comp_pairs), "NFC pairs" + + print "--- Writing", FILE, "..." + + fp = open(FILE, "w") + print >>fp, "/* this file was generated by %s %s */" % (SCRIPT, VERSION) + print >>fp + print >>fp, '#define UNIDATA_VERSION "%s"' % UNIDATA_VERSION + print >>fp, "/* a list of unique database records */" + print >>fp, \ + "const _PyUnicode_DatabaseRecord _PyUnicode_Database_Records[] = {" + for item in table: + print >>fp, " {%d, %d, %d, %d, %d}," % item + print >>fp, "};" + print >>fp + + print >>fp, "/* Reindexing of NFC first characters. */" + print >>fp, "#define TOTAL_FIRST",total_first + print >>fp, "#define TOTAL_LAST",total_last + print >>fp, "struct reindex{int start;short count,index;};" + print >>fp, "static struct reindex nfc_first[] = {" + for start,end in comp_first_ranges: + print >>fp," { %d, %d, %d}," % (start,end-start,comp_first[start]) + print >>fp," {0,0,0}" + print >>fp,"};\n" + print >>fp, "static struct reindex nfc_last[] = {" + for start,end in comp_last_ranges: + print >>fp," { %d, %d, %d}," % (start,end-start,comp_last[start]) + print >>fp," {0,0,0}" + print >>fp,"};\n" + + # FIXME: the following tables could be made static, and + # the support code moved into unicodedatabase.c + + print >>fp, "/* string literals */" + print >>fp, "const char *_PyUnicode_CategoryNames[] = {" + for name in CATEGORY_NAMES: + print >>fp, " \"%s\"," % name + print >>fp, " NULL" + print >>fp, "};" + + print >>fp, "const char *_PyUnicode_BidirectionalNames[] = {" + for name in BIDIRECTIONAL_NAMES: + print >>fp, " \"%s\"," % name + print >>fp, " NULL" + print >>fp, "};" + + print >>fp, "const char *_PyUnicode_EastAsianWidthNames[] = {" + for name in EASTASIANWIDTH_NAMES: + print >>fp, " \"%s\"," % name + print >>fp, " NULL" + print >>fp, "};" + + print >>fp, "static const char *decomp_prefix[] = {" + for name in decomp_prefix: + print >>fp, " \"%s\"," % name + print >>fp, " NULL" + print >>fp, "};" + + # split record index table + index1, index2, shift = splitbins(index, trace) + + print >>fp, "/* index tables for the database records */" + print >>fp, "#define SHIFT", shift + Array("index1", index1).dump(fp, trace) + Array("index2", index2).dump(fp, trace) + + # split decomposition index table + index1, index2, shift = splitbins(decomp_index, trace) + + print >>fp, "/* decomposition data */" + Array("decomp_data", decomp_data).dump(fp, trace) + + print >>fp, "/* index tables for the decomposition data */" + print >>fp, "#define DECOMP_SHIFT", shift + Array("decomp_index1", index1).dump(fp, trace) + Array("decomp_index2", index2).dump(fp, trace) + + index, index2, shift = splitbins(comp_data, trace) + print >>fp, "/* NFC pairs */" + print >>fp, "#define COMP_SHIFT", shift + Array("comp_index", index).dump(fp, trace) + Array("comp_data", index2).dump(fp, trace) + + # Generate delta tables for old versions + for version, table, normalization in unicode.changed: + cversion = version.replace(".","_") + records = [table[0]] + cache = {table[0]:0} + index = [0] * len(table) + for i, record in enumerate(table): + try: + index[i] = cache[record] + except KeyError: + index[i] = cache[record] = len(records) + records.append(record) + index1, index2, shift = splitbins(index, trace) + print >>fp, "static const change_record change_records_%s[] = {" % cversion + for record in records: + print >>fp, "\t{ %s }," % ", ".join(map(str,record)) + print >>fp, "};" + Array("changes_%s_index" % cversion, index1).dump(fp, trace) + Array("changes_%s_data" % cversion, index2).dump(fp, trace) + print >>fp, "static const change_record* get_change_%s(Py_UCS4 n)" % cversion + print >>fp, "{" + print >>fp, "\tint index;" + print >>fp, "\tif (n >= 0x110000) index = 0;" + print >>fp, "\telse {" + print >>fp, "\t\tindex = changes_%s_index[n>>%d];" % (cversion, shift) + print >>fp, "\t\tindex = changes_%s_data[(index<<%d)+(n & %d)];" % \ + (cversion, shift, ((1<>fp, "\t}" + print >>fp, "\treturn change_records_%s+index;" % cversion + print >>fp, "}\n" + print >>fp, "static Py_UCS4 normalization_%s(Py_UCS4 n)" % cversion + print >>fp, "{" + print >>fp, "\tswitch(n) {" + for k, v in normalization: + print >>fp, "\tcase %s: return 0x%s;" % (hex(k), v) + print >>fp, "\tdefault: return 0;" + print >>fp, "\t}\n}\n" + + fp.close() + +# -------------------------------------------------------------------- +# unicode character type tables + +def makeunicodetype(unicode, trace): + + FILE = "Objects/unicodetype_db.h" + + print "--- Preparing", FILE, "..." + + # extract unicode types + dummy = (0, 0, 0, 0, 0, 0) + table = [dummy] + cache = {0: dummy} + index = [0] * len(unicode.chars) + + for char in unicode.chars: + record = unicode.table[char] + if record: + # extract database properties + category = record[2] + bidirectional = record[4] + flags = 0 + delta = True + if category in ["Lm", "Lt", "Lu", "Ll", "Lo"]: + flags |= ALPHA_MASK + if category == "Ll": + flags |= LOWER_MASK + if category == "Zl" or bidirectional == "B": + flags |= LINEBREAK_MASK + if category == "Zs" or bidirectional in ("WS", "B", "S"): + flags |= SPACE_MASK + if category == "Lt": + flags |= TITLE_MASK + if category == "Lu": + flags |= UPPER_MASK + # use delta predictor for upper/lower/title if it fits + if record[12]: + upper = int(record[12], 16) - char + if -32768 <= upper <= 32767 and delta: + upper = upper & 0xffff + else: + upper += char + delta = False + else: + upper = 0 + if record[13]: + lower = int(record[13], 16) - char + if -32768 <= lower <= 32767 and delta: + lower = lower & 0xffff + else: + lower += char + delta = False + else: + lower = 0 + if record[14]: + title = int(record[14], 16) - char + if -32768 <= lower <= 32767 and delta: + title = title & 0xffff + else: + title += char + delta = False + else: + title = 0 + if not delta: + flags |= NODELTA_MASK + # decimal digit, integer digit + decimal = 0 + if record[6]: + flags |= DECIMAL_MASK + decimal = int(record[6]) + digit = 0 + if record[7]: + flags |= DIGIT_MASK + digit = int(record[7]) + item = ( + upper, lower, title, decimal, digit, flags + ) + # add entry to index and item tables + i = cache.get(item) + if i is None: + cache[item] = i = len(table) + table.append(item) + index[char] = i + + print len(table), "unique character type entries" + + print "--- Writing", FILE, "..." + + fp = open(FILE, "w") + print >>fp, "/* this file was generated by %s %s */" % (SCRIPT, VERSION) + print >>fp + print >>fp, "/* a list of unique character type descriptors */" + print >>fp, "const _PyUnicode_TypeRecord _PyUnicode_TypeRecords[] = {" + for item in table: + print >>fp, " {%d, %d, %d, %d, %d, %d}," % item + print >>fp, "};" + print >>fp + + # split decomposition index table + index1, index2, shift = splitbins(index, trace) + + print >>fp, "/* type indexes */" + print >>fp, "#define SHIFT", shift + Array("index1", index1).dump(fp, trace) + Array("index2", index2).dump(fp, trace) + + fp.close() + +# -------------------------------------------------------------------- +# unicode name database + +def makeunicodename(unicode, trace): + + FILE = "Modules/unicodename_db.h" + + print "--- Preparing", FILE, "..." + + # collect names + names = [None] * len(unicode.chars) + + for char in unicode.chars: + record = unicode.table[char] + if record: + name = record[1].strip() + if name and name[0] != "<": + names[char] = name + chr(0) + + print len(filter(lambda n: n is not None, names)), "distinct names" + + # collect unique words from names (note that we differ between + # words inside a sentence, and words ending a sentence. the + # latter includes the trailing null byte. + + words = {} + n = b = 0 + for char in unicode.chars: + name = names[char] + if name: + w = name.split() + b = b + len(name) + n = n + len(w) + for w in w: + l = words.get(w) + if l: + l.append(None) + else: + words[w] = [len(words)] + + print n, "words in text;", b, "bytes" + + wordlist = words.items() + + # sort on falling frequency, then by name + def cmpwords((aword, alist),(bword, blist)): + r = -cmp(len(alist),len(blist)) + if r: + return r + return cmp(aword, bword) + wordlist.sort(cmpwords) + + # figure out how many phrasebook escapes we need + escapes = 0 + while escapes * 256 < len(wordlist): + escapes = escapes + 1 + print escapes, "escapes" + + short = 256 - escapes + + assert short > 0 + + print short, "short indexes in lexicon" + + # statistics + n = 0 + for i in range(short): + n = n + len(wordlist[i][1]) + print n, "short indexes in phrasebook" + + # pick the most commonly used words, and sort the rest on falling + # length (to maximize overlap) + + wordlist, wordtail = wordlist[:short], wordlist[short:] + wordtail.sort(lambda a, b: len(b[0])-len(a[0])) + wordlist.extend(wordtail) + + # generate lexicon from words + + lexicon_offset = [0] + lexicon = "" + words = {} + + # build a lexicon string + offset = 0 + for w, x in wordlist: + # encoding: bit 7 indicates last character in word (chr(128) + # indicates the last character in an entire string) + ww = w[:-1] + chr(ord(w[-1])+128) + # reuse string tails, when possible + o = lexicon.find(ww) + if o < 0: + o = offset + lexicon = lexicon + ww + offset = offset + len(w) + words[w] = len(lexicon_offset) + lexicon_offset.append(o) + + lexicon = map(ord, lexicon) + + # generate phrasebook from names and lexicon + phrasebook = [0] + phrasebook_offset = [0] * len(unicode.chars) + for char in unicode.chars: + name = names[char] + if name: + w = name.split() + phrasebook_offset[char] = len(phrasebook) + for w in w: + i = words[w] + if i < short: + phrasebook.append(i) + else: + # store as two bytes + phrasebook.append((i>>8) + short) + phrasebook.append(i&255) + + assert getsize(phrasebook) == 1 + + # + # unicode name hash table + + # extract names + data = [] + for char in unicode.chars: + record = unicode.table[char] + if record: + name = record[1].strip() + if name and name[0] != "<": + data.append((name, char)) + + # the magic number 47 was chosen to minimize the number of + # collisions on the current data set. if you like, change it + # and see what happens... + + codehash = Hash("code", data, 47) + + print "--- Writing", FILE, "..." + + fp = open(FILE, "w") + print >>fp, "/* this file was generated by %s %s */" % (SCRIPT, VERSION) + print >>fp + print >>fp, "#define NAME_MAXLEN", 256 + print >>fp + print >>fp, "/* lexicon */" + Array("lexicon", lexicon).dump(fp, trace) + Array("lexicon_offset", lexicon_offset).dump(fp, trace) + + # split decomposition index table + offset1, offset2, shift = splitbins(phrasebook_offset, trace) + + print >>fp, "/* code->name phrasebook */" + print >>fp, "#define phrasebook_shift", shift + print >>fp, "#define phrasebook_short", short + + Array("phrasebook", phrasebook).dump(fp, trace) + Array("phrasebook_offset1", offset1).dump(fp, trace) + Array("phrasebook_offset2", offset2).dump(fp, trace) + + print >>fp, "/* name->code dictionary */" + codehash.dump(fp, trace) + + fp.close() + + +def merge_old_version(version, new, old): + # Changes to exclusion file not implemented yet + if old.exclusions != new.exclusions: + raise NotImplementedError, "exclusions differ" + + # In these change records, 0xFF means "no change" + bidir_changes = [0xFF]*0x110000 + category_changes = [0xFF]*0x110000 + decimal_changes = [0xFF]*0x110000 + mirrored_changes = [0xFF]*0x110000 + # In numeric data, 0 means "no change", + # -1 means "did not have a numeric value + numeric_changes = [0] * 0x110000 + # normalization_changes is a list of key-value pairs + normalization_changes = [] + for i in range(0x110000): + if new.table[i] is None: + # Characters unassigned in the new version ought to + # be unassigned in the old one + assert old.table[i] is None + continue + # check characters unassigned in the old version + if old.table[i] is None: + # category 0 is "unassigned" + category_changes[i] = 0 + continue + # check characters that differ + if old.table[i] != new.table[i]: + for k in range(len(old.table[i])): + if old.table[i][k] != new.table[i][k]: + value = old.table[i][k] + if k == 2: + #print "CATEGORY",hex(i), old.table[i][k], new.table[i][k] + category_changes[i] = CATEGORY_NAMES.index(value) + elif k == 4: + #print "BIDIR",hex(i), old.table[i][k], new.table[i][k] + bidir_changes[i] = BIDIRECTIONAL_NAMES.index(value) + elif k == 5: + #print "DECOMP",hex(i), old.table[i][k], new.table[i][k] + # We assume that all normalization changes are in 1:1 mappings + assert " " not in value + normalization_changes.append((i, value)) + elif k == 6: + #print "DECIMAL",hex(i), old.table[i][k], new.table[i][k] + # we only support changes where the old value is a single digit + assert value in "0123456789" + decimal_changes[i] = int(value) + elif k == 8: + # print "NUMERIC",hex(i), `old.table[i][k]`, new.table[i][k] + # Since 0 encodes "no change", the old value is better not 0 + assert value != "0" and value != "-1" + if not value: + numeric_changes[i] = -1 + else: + assert re.match("^[0-9]+$", value) + numeric_changes[i] = int(value) + elif k == 9: + if value == 'Y': + mirrored_changes[i] = '1' + else: + mirrored_changes[i] = '0' + elif k == 11: + # change to ISO comment, ignore + pass + elif k == 12: + # change to simple uppercase mapping; ignore + pass + elif k == 13: + # change to simple lowercase mapping; ignore + pass + elif k == 14: + # change to simple titlecase mapping; ignore + pass + else: + class Difference(Exception):pass + raise Difference, (hex(i), k, old.table[i], new.table[i]) + new.changed.append((version, zip(bidir_changes, category_changes, + decimal_changes, mirrored_changes, + numeric_changes), + normalization_changes)) + + +# -------------------------------------------------------------------- +# the following support code is taken from the unidb utilities +# Copyright (c) 1999-2000 by Secret Labs AB + +# load a unicode-data file from disk + +import sys + +class UnicodeData: + + def __init__(self, filename, exclusions, eastasianwidth, expand=1): + self.changed = [] + file = open(filename) + table = [None] * 0x110000 + while 1: + s = file.readline() + if not s: + break + s = s.strip().split(";") + char = int(s[0], 16) + table[char] = s + + # expand first-last ranges + if expand: + field = None + for i in range(0, 0x110000): + s = table[i] + if s: + if s[1][-6:] == "First>": + s[1] = "" + field = s + elif s[1][-5:] == "Last>": + s[1] = "" + field = None + elif field: + f2 = field[:] + f2[0] = "%X" % i + table[i] = f2 + + # public attributes + self.filename = filename + self.table = table + self.chars = range(0x110000) # unicode 3.2 + + file = open(exclusions) + self.exclusions = {} + for s in file: + s = s.strip() + if not s: + continue + if s[0] == '#': + continue + char = int(s.split()[0],16) + self.exclusions[char] = 1 + + widths = [None] * 0x110000 + for s in open(eastasianwidth): + s = s.strip() + if not s: + continue + if s[0] == '#': + continue + s = s.split()[0].split(';') + if '..' in s[0]: + first, last = [int(c, 16) for c in s[0].split('..')] + chars = range(first, last+1) + else: + chars = [int(s[0], 16)] + for char in chars: + widths[char] = s[1] + for i in range(0, 0x110000): + if table[i] is not None: + table[i].append(widths[i]) + + def uselatin1(self): + # restrict character range to ISO Latin 1 + self.chars = range(256) + +# hash table tools + +# this is a straight-forward reimplementation of Python's built-in +# dictionary type, using a static data structure, and a custom string +# hash algorithm. + +def myhash(s, magic): + h = 0 + for c in map(ord, s.upper()): + h = (h * magic) + c + ix = h & 0xff000000L + if ix: + h = (h ^ ((ix>>24) & 0xff)) & 0x00ffffff + return h + +SIZES = [ + (4,3), (8,3), (16,3), (32,5), (64,3), (128,3), (256,29), (512,17), + (1024,9), (2048,5), (4096,83), (8192,27), (16384,43), (32768,3), + (65536,45), (131072,9), (262144,39), (524288,39), (1048576,9), + (2097152,5), (4194304,3), (8388608,33), (16777216,27) +] + +class Hash: + def __init__(self, name, data, magic): + # turn a (key, value) list into a static hash table structure + + # determine table size + for size, poly in SIZES: + if size > len(data): + poly = size + poly + break + else: + raise AssertionError, "ran out of polynominals" + + print size, "slots in hash table" + + table = [None] * size + + mask = size-1 + + n = 0 + + hash = myhash + + # initialize hash table + for key, value in data: + h = hash(key, magic) + i = (~h) & mask + v = table[i] + if v is None: + table[i] = value + continue + incr = (h ^ (h >> 3)) & mask; + if not incr: + incr = mask + while 1: + n = n + 1 + i = (i + incr) & mask + v = table[i] + if v is None: + table[i] = value + break + incr = incr << 1 + if incr > mask: + incr = incr ^ poly + + print n, "collisions" + self.collisions = n + + for i in range(len(table)): + if table[i] is None: + table[i] = 0 + + self.data = Array(name + "_hash", table) + self.magic = magic + self.name = name + self.size = size + self.poly = poly + + def dump(self, file, trace): + # write data to file, as a C array + self.data.dump(file, trace) + file.write("#define %s_magic %d\n" % (self.name, self.magic)) + file.write("#define %s_size %d\n" % (self.name, self.size)) + file.write("#define %s_poly %d\n" % (self.name, self.poly)) + +# stuff to deal with arrays of unsigned integers + +class Array: + + def __init__(self, name, data): + self.name = name + self.data = data + + def dump(self, file, trace=0): + # write data to file, as a C array + size = getsize(self.data) + if trace: + print >>sys.stderr, self.name+":", size*len(self.data), "bytes" + file.write("static ") + if size == 1: + file.write("unsigned char") + elif size == 2: + file.write("unsigned short") + else: + file.write("unsigned int") + file.write(" " + self.name + "[] = {\n") + if self.data: + s = " " + for item in self.data: + i = str(item) + ", " + if len(s) + len(i) > 78: + file.write(s + "\n") + s = " " + i + else: + s = s + i + if s.strip(): + file.write(s + "\n") + file.write("};\n\n") + +def getsize(data): + # return smallest possible integer size for the given array + maxdata = max(data) + if maxdata < 256: + return 1 + elif maxdata < 65536: + return 2 + else: + return 4 + +def splitbins(t, trace=0): + """t, trace=0 -> (t1, t2, shift). Split a table to save space. + + t is a sequence of ints. This function can be useful to save space if + many of the ints are the same. t1 and t2 are lists of ints, and shift + is an int, chosen to minimize the combined size of t1 and t2 (in C + code), and where for each i in range(len(t)), + t[i] == t2[(t1[i >> shift] << shift) + (i & mask)] + where mask is a bitmask isolating the last "shift" bits. + + If optional arg trace is non-zero (default zero), progress info + is printed to sys.stderr. The higher the value, the more info + you'll get. + """ + + import sys + if trace: + def dump(t1, t2, shift, bytes): + print >>sys.stderr, "%d+%d bins at shift %d; %d bytes" % ( + len(t1), len(t2), shift, bytes) + print >>sys.stderr, "Size of original table:", len(t)*getsize(t), \ + "bytes" + n = len(t)-1 # last valid index + maxshift = 0 # the most we can shift n and still have something left + if n > 0: + while n >> 1: + n >>= 1 + maxshift += 1 + del n + bytes = sys.maxint # smallest total size so far + t = tuple(t) # so slices can be dict keys + for shift in range(maxshift + 1): + t1 = [] + t2 = [] + size = 2**shift + bincache = {} + for i in range(0, len(t), size): + bin = t[i:i+size] + index = bincache.get(bin) + if index is None: + index = len(t2) + bincache[bin] = index + t2.extend(bin) + t1.append(index >> shift) + # determine memory size + b = len(t1)*getsize(t1) + len(t2)*getsize(t2) + if trace > 1: + dump(t1, t2, shift, b) + if b < bytes: + best = t1, t2, shift + bytes = b + t1, t2, shift = best + if trace: + print >>sys.stderr, "Best:", + dump(t1, t2, shift, bytes) + if __debug__: + # exhaustively verify that the decomposition is correct + mask = ~((~0) << shift) # i.e., low-bit mask of shift bits + for i in xrange(len(t)): + assert t[i] == t2[(t1[i >> shift] << shift) + (i & mask)] + return best + +if __name__ == "__main__": + maketables(1)