1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/netwerk/protocol/http/make_incoming_tables.py Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,147 @@
1.4 +# This script exists to auto-generate Http2HuffmanIncoming.h from the table
1.5 +# contained in the HPACK spec. It's pretty simple to run:
1.6 +# python make_incoming_tables.py < http2_huffman_table.txt > Http2HuffmanIncoming.h
1.7 +# where huff_incoming.txt is copy/pasted text from the latest version of the
1.8 +# HPACK spec, with all non-relevant lines removed (the most recent version
1.9 +# of huff_incoming.txt also lives in this directory as an example).
1.10 +import sys
1.11 +
1.12 +def char_cmp(x, y):
1.13 + rv = cmp(x['nbits'], y['nbits'])
1.14 + if not rv:
1.15 + rv = cmp(x['bpat'], y['bpat'])
1.16 + if not rv:
1.17 + rv = cmp(x['ascii'], y['ascii'])
1.18 + return rv
1.19 +
1.20 +characters = []
1.21 +
1.22 +for line in sys.stdin:
1.23 + line = line.rstrip()
1.24 + obracket = line.rfind('[')
1.25 + nbits = int(line[obracket + 1:-1])
1.26 +
1.27 + ascii = int(line[10:13].strip())
1.28 +
1.29 + bar = line.find('|', 9)
1.30 + obracket = line.find('[', bar)
1.31 + bpat = line[bar + 1:obracket - 1].strip().rstrip('|')
1.32 +
1.33 + characters.append({'ascii': ascii, 'nbits': nbits, 'bpat': bpat})
1.34 +
1.35 +characters.sort(cmp=char_cmp)
1.36 +raw_entries = []
1.37 +for c in characters:
1.38 + raw_entries.append((c['ascii'], c['bpat']))
1.39 +
1.40 +class DefaultList(list):
1.41 + def __init__(self, default=None):
1.42 + self.__default = default
1.43 +
1.44 + def __ensure_size(self, sz):
1.45 + while sz > len(self):
1.46 + self.append(self.__default)
1.47 +
1.48 + def __getitem__(self, idx):
1.49 + self.__ensure_size(idx + 1)
1.50 + rv = super(DefaultList, self).__getitem__(idx)
1.51 + return rv
1.52 +
1.53 + def __setitem__(self, idx, val):
1.54 + self.__ensure_size(idx + 1)
1.55 + super(DefaultList, self).__setitem__(idx, val)
1.56 +
1.57 +def expand_to_8bit(bstr):
1.58 + while len(bstr) < 8:
1.59 + bstr += '0'
1.60 + return int(bstr, 2)
1.61 +
1.62 +table = DefaultList()
1.63 +for r in raw_entries:
1.64 + ascii, bpat = r
1.65 + ascii = int(ascii)
1.66 + bstrs = bpat.split('|')
1.67 + curr_table = table
1.68 + while len(bstrs) > 1:
1.69 + idx = expand_to_8bit(bstrs[0])
1.70 + if curr_table[idx] is None:
1.71 + curr_table[idx] = DefaultList()
1.72 + curr_table = curr_table[idx]
1.73 + bstrs.pop(0)
1.74 +
1.75 + idx = expand_to_8bit(bstrs[0])
1.76 + curr_table[idx] = {'prefix_len': len(bstrs[0]),
1.77 + 'mask': int(bstrs[0], 2),
1.78 + 'value': ascii}
1.79 +
1.80 +
1.81 +def output_table(table, name_suffix=''):
1.82 + max_prefix_len = 0
1.83 + for i, t in enumerate(table):
1.84 + if isinstance(t, dict):
1.85 + if t['prefix_len'] > max_prefix_len:
1.86 + max_prefix_len = t['prefix_len']
1.87 + elif t is not None:
1.88 + output_table(t, '%s_%s' % (name_suffix, i))
1.89 +
1.90 + tablename = 'HuffmanIncoming%s' % (name_suffix if name_suffix else 'Root',)
1.91 + entriestable = tablename.replace('HuffmanIncoming', 'HuffmanIncomingEntries')
1.92 + sys.stdout.write('static HuffmanIncomingEntry %s[] = {\n' % (entriestable,))
1.93 + prefix_len = 0
1.94 + value = 0
1.95 + ptr = 'nullptr'
1.96 + for i in range(256):
1.97 + t = table[i]
1.98 + if isinstance(t, dict):
1.99 + prefix_len = t['prefix_len']
1.100 + value = t['value']
1.101 + ptr = 'nullptr'
1.102 + elif t is not None:
1.103 + prefix_len = 0
1.104 + value = 0
1.105 + subtable = '%s_%s' % (name_suffix, i)
1.106 + ptr = '&HuffmanIncoming%s' % (subtable,)
1.107 + sys.stdout.write(' { %s, %s, %s }' %
1.108 + (ptr, value, prefix_len))
1.109 + if i < 255:
1.110 + sys.stdout.write(',')
1.111 + sys.stdout.write('\n')
1.112 + sys.stdout.write('};\n')
1.113 + sys.stdout.write('\n')
1.114 + sys.stdout.write('static HuffmanIncomingTable %s = {\n' % (tablename,))
1.115 + sys.stdout.write(' %s,\n' % (entriestable,))
1.116 + sys.stdout.write(' %s\n' % (max_prefix_len,))
1.117 + sys.stdout.write('};\n')
1.118 + sys.stdout.write('\n')
1.119 +
1.120 +sys.stdout.write('''/*
1.121 + * THIS FILE IS AUTO-GENERATED. DO NOT EDIT!
1.122 + */
1.123 +#ifndef mozilla__net__Http2HuffmanIncoming_h
1.124 +#define mozilla__net__Http2HuffmanIncoming_h
1.125 +
1.126 +namespace mozilla {
1.127 +namespace net {
1.128 +
1.129 +struct HuffmanIncomingTable;
1.130 +
1.131 +struct HuffmanIncomingEntry {
1.132 + HuffmanIncomingTable *mPtr;
1.133 + uint16_t mValue;
1.134 + uint8_t mPrefixLen;
1.135 +};
1.136 +
1.137 +struct HuffmanIncomingTable {
1.138 + HuffmanIncomingEntry *mEntries;
1.139 + uint8_t mPrefixLen;
1.140 +};
1.141 +
1.142 +''')
1.143 +
1.144 +output_table(table)
1.145 +
1.146 +sys.stdout.write('''} // namespace net
1.147 +} // namespace mozilla
1.148 +
1.149 +#endif // mozilla__net__Http2HuffmanIncoming_h
1.150 +''')
