michael@0: # This script exists to auto-generate Http2HuffmanIncoming.h from the table
michael@0: # contained in the HPACK spec. It's pretty simple to run:
michael@0: #   python make_incoming_tables.py < http2_huffman_table.txt > Http2HuffmanIncoming.h
michael@0: # where huff_incoming.txt is copy/pasted text from the latest version of the
michael@0: # HPACK spec, with all non-relevant lines removed (the most recent version
michael@0: # of huff_incoming.txt also lives in this directory as an example).
michael@0: import sys
michael@0: 
michael@0: def char_cmp(x, y):
michael@0:     rv = cmp(x['nbits'], y['nbits'])
michael@0:     if not rv:
michael@0:         rv = cmp(x['bpat'], y['bpat'])
michael@0:     if not rv:
michael@0:         rv = cmp(x['ascii'], y['ascii'])
michael@0:     return rv
michael@0: 
michael@0: characters = []
michael@0: 
michael@0: for line in sys.stdin:
michael@0:     line = line.rstrip()
michael@0:     obracket = line.rfind('[')
michael@0:     nbits = int(line[obracket + 1:-1])
michael@0: 
michael@0:     ascii = int(line[10:13].strip())
michael@0: 
michael@0:     bar = line.find('|', 9)
michael@0:     obracket = line.find('[', bar)
michael@0:     bpat = line[bar + 1:obracket - 1].strip().rstrip('|')
michael@0: 
michael@0:     characters.append({'ascii': ascii, 'nbits': nbits, 'bpat': bpat})
michael@0: 
michael@0: characters.sort(cmp=char_cmp)
michael@0: raw_entries = []
michael@0: for c in characters:
michael@0:     raw_entries.append((c['ascii'], c['bpat']))
michael@0: 
michael@0: class DefaultList(list):
michael@0:     def __init__(self, default=None):
michael@0:         self.__default = default
michael@0: 
michael@0:     def __ensure_size(self, sz):
michael@0:         while sz > len(self):
michael@0:             self.append(self.__default)
michael@0: 
michael@0:     def __getitem__(self, idx):
michael@0:         self.__ensure_size(idx + 1)
michael@0:         rv = super(DefaultList, self).__getitem__(idx)
michael@0:         return rv
michael@0: 
michael@0:     def __setitem__(self, idx, val):
michael@0:         self.__ensure_size(idx + 1)
michael@0:         super(DefaultList, self).__setitem__(idx, val)
michael@0: 
michael@0: def expand_to_8bit(bstr):
michael@0:     while len(bstr) < 8:
michael@0:         bstr += '0'
michael@0:     return int(bstr, 2)
michael@0: 
michael@0: table = DefaultList()
michael@0: for r in raw_entries:
michael@0:     ascii, bpat = r
michael@0:     ascii = int(ascii)
michael@0:     bstrs = bpat.split('|')
michael@0:     curr_table = table
michael@0:     while len(bstrs) > 1:
michael@0:         idx = expand_to_8bit(bstrs[0])
michael@0:         if curr_table[idx] is None:
michael@0:             curr_table[idx] = DefaultList()
michael@0:         curr_table = curr_table[idx]
michael@0:         bstrs.pop(0)
michael@0: 
michael@0:     idx = expand_to_8bit(bstrs[0])
michael@0:     curr_table[idx] = {'prefix_len': len(bstrs[0]),
michael@0:                         'mask': int(bstrs[0], 2),
michael@0:                         'value': ascii}
michael@0: 
michael@0: 
michael@0: def output_table(table, name_suffix=''):
michael@0:     max_prefix_len = 0
michael@0:     for i, t in enumerate(table):
michael@0:         if isinstance(t, dict):
michael@0:             if t['prefix_len'] > max_prefix_len:
michael@0:                 max_prefix_len = t['prefix_len']
michael@0:         elif t is not None:
michael@0:             output_table(t, '%s_%s' % (name_suffix, i))
michael@0: 
michael@0:     tablename = 'HuffmanIncoming%s' % (name_suffix if name_suffix else 'Root',)
michael@0:     entriestable = tablename.replace('HuffmanIncoming', 'HuffmanIncomingEntries')
michael@0:     sys.stdout.write('static HuffmanIncomingEntry %s[] = {\n' % (entriestable,))
michael@0:     prefix_len = 0
michael@0:     value = 0
michael@0:     ptr = 'nullptr'
michael@0:     for i in range(256):
michael@0:         t = table[i]
michael@0:         if isinstance(t, dict):
michael@0:             prefix_len = t['prefix_len']
michael@0:             value = t['value']
michael@0:             ptr = 'nullptr'
michael@0:         elif t is not None:
michael@0:             prefix_len = 0
michael@0:             value = 0
michael@0:             subtable = '%s_%s' % (name_suffix, i)
michael@0:             ptr = '&HuffmanIncoming%s' % (subtable,)
michael@0:         sys.stdout.write('  { %s, %s, %s }' %
michael@0:                          (ptr, value, prefix_len))
michael@0:         if i < 255:
michael@0:             sys.stdout.write(',')
michael@0:         sys.stdout.write('\n')
michael@0:     sys.stdout.write('};\n')
michael@0:     sys.stdout.write('\n')
michael@0:     sys.stdout.write('static HuffmanIncomingTable %s = {\n' % (tablename,))
michael@0:     sys.stdout.write('  %s,\n' % (entriestable,))
michael@0:     sys.stdout.write('  %s\n' % (max_prefix_len,))
michael@0:     sys.stdout.write('};\n')
michael@0:     sys.stdout.write('\n')
michael@0: 
michael@0: sys.stdout.write('''/*
michael@0:  * THIS FILE IS AUTO-GENERATED. DO NOT EDIT!
michael@0:  */
michael@0: #ifndef mozilla__net__Http2HuffmanIncoming_h
michael@0: #define mozilla__net__Http2HuffmanIncoming_h
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace net {
michael@0: 
michael@0: struct HuffmanIncomingTable;
michael@0: 
michael@0: struct HuffmanIncomingEntry {
michael@0:   HuffmanIncomingTable *mPtr;
michael@0:   uint16_t mValue;
michael@0:   uint8_t mPrefixLen;
michael@0: };
michael@0: 
michael@0: struct HuffmanIncomingTable {
michael@0:   HuffmanIncomingEntry *mEntries;
michael@0:   uint8_t mPrefixLen;
michael@0: };
michael@0: 
michael@0: ''')
michael@0: 
michael@0: output_table(table)
michael@0: 
michael@0: sys.stdout.write('''} // namespace net
michael@0: } // namespace mozilla
michael@0: 
michael@0: #endif // mozilla__net__Http2HuffmanIncoming_h
michael@0: ''')