The Tor Browser / file comparison
comparison: netwerk/protocol/http/make_incoming_tables.py
netwerk/protocol/http/make_incoming_tables.py
- branch
- TOR_BUG_9701
- changeset 11
- deefc01c0e14
equal
deleted
inserted
replaced
| -1:000000000000 | 0:819f0a46cca0 |
|---|---|
| 1 # This script exists to auto-generate Http2HuffmanIncoming.h from the table | |
| 2 # contained in the HPACK spec. It's pretty simple to run: | |
| 3 # python make_incoming_tables.py < http2_huffman_table.txt > Http2HuffmanIncoming.h | |
| 4 # where huff_incoming.txt is copy/pasted text from the latest version of the | |
| 5 # HPACK spec, with all non-relevant lines removed (the most recent version | |
| 6 # of huff_incoming.txt also lives in this directory as an example). | |
| 7 import sys | |
| 8 | |
| 9 def char_cmp(x, y): | |
| 10 rv = cmp(x['nbits'], y['nbits']) | |
| 11 if not rv: | |
| 12 rv = cmp(x['bpat'], y['bpat']) | |
| 13 if not rv: | |
| 14 rv = cmp(x['ascii'], y['ascii']) | |
| 15 return rv | |
| 16 | |
| 17 characters = [] | |
| 18 | |
| 19 for line in sys.stdin: | |
| 20 line = line.rstrip() | |
| 21 obracket = line.rfind('[') | |
| 22 nbits = int(line[obracket + 1:-1]) | |
| 23 | |
| 24 ascii = int(line[10:13].strip()) | |
| 25 | |
| 26 bar = line.find('|', 9) | |
| 27 obracket = line.find('[', bar) | |
| 28 bpat = line[bar + 1:obracket - 1].strip().rstrip('|') | |
| 29 | |
| 30 characters.append({'ascii': ascii, 'nbits': nbits, 'bpat': bpat}) | |
| 31 | |
| 32 characters.sort(cmp=char_cmp) | |
| 33 raw_entries = [] | |
| 34 for c in characters: | |
| 35 raw_entries.append((c['ascii'], c['bpat'])) | |
| 36 | |
| 37 class DefaultList(list): | |
| 38 def __init__(self, default=None): | |
| 39 self.__default = default | |
| 40 | |
| 41 def __ensure_size(self, sz): | |
| 42 while sz > len(self): | |
| 43 self.append(self.__default) | |
| 44 | |
| 45 def __getitem__(self, idx): | |
| 46 self.__ensure_size(idx + 1) | |
| 47 rv = super(DefaultList, self).__getitem__(idx) | |
| 48 return rv | |
| 49 | |
| 50 def __setitem__(self, idx, val): | |
| 51 self.__ensure_size(idx + 1) | |
| 52 super(DefaultList, self).__setitem__(idx, val) | |
| 53 | |
| 54 def expand_to_8bit(bstr): | |
| 55 while len(bstr) < 8: | |
| 56 bstr += '0' | |
| 57 return int(bstr, 2) | |
| 58 | |
| 59 table = DefaultList() | |
| 60 for r in raw_entries: | |
| 61 ascii, bpat = r | |
| 62 ascii = int(ascii) | |
| 63 bstrs = bpat.split('|') | |
| 64 curr_table = table | |
| 65 while len(bstrs) > 1: | |
| 66 idx = expand_to_8bit(bstrs[0]) | |
| 67 if curr_table[idx] is None: | |
| 68 curr_table[idx] = DefaultList() | |
| 69 curr_table = curr_table[idx] | |
| 70 bstrs.pop(0) | |
| 71 | |
| 72 idx = expand_to_8bit(bstrs[0]) | |
| 73 curr_table[idx] = {'prefix_len': len(bstrs[0]), | |
| 74 'mask': int(bstrs[0], 2), | |
| 75 'value': ascii} | |
| 76 | |
| 77 | |
| 78 def output_table(table, name_suffix=''): | |
| 79 max_prefix_len = 0 | |
| 80 for i, t in enumerate(table): | |
| 81 if isinstance(t, dict): | |
| 82 if t['prefix_len'] > max_prefix_len: | |
| 83 max_prefix_len = t['prefix_len'] | |
| 84 elif t is not None: | |
| 85 output_table(t, '%s_%s' % (name_suffix, i)) | |
| 86 | |
| 87 tablename = 'HuffmanIncoming%s' % (name_suffix if name_suffix else 'Root',) | |
| 88 entriestable = tablename.replace('HuffmanIncoming', 'HuffmanIncomingEntries') | |
| 89 sys.stdout.write('static HuffmanIncomingEntry %s[] = {\n' % (entriestable,)) | |
| 90 prefix_len = 0 | |
| 91 value = 0 | |
| 92 ptr = 'nullptr' | |
| 93 for i in range(256): | |
| 94 t = table[i] | |
| 95 if isinstance(t, dict): | |
| 96 prefix_len = t['prefix_len'] | |
| 97 value = t['value'] | |
| 98 ptr = 'nullptr' | |
| 99 elif t is not None: | |
| 100 prefix_len = 0 | |
| 101 value = 0 | |
| 102 subtable = '%s_%s' % (name_suffix, i) | |
| 103 ptr = '&HuffmanIncoming%s' % (subtable,) | |
| 104 sys.stdout.write(' { %s, %s, %s }' % | |
| 105 (ptr, value, prefix_len)) | |
| 106 if i < 255: | |
| 107 sys.stdout.write(',') | |
| 108 sys.stdout.write('\n') | |
| 109 sys.stdout.write('};\n') | |
| 110 sys.stdout.write('\n') | |
| 111 sys.stdout.write('static HuffmanIncomingTable %s = {\n' % (tablename,)) | |
| 112 sys.stdout.write(' %s,\n' % (entriestable,)) | |
| 113 sys.stdout.write(' %s\n' % (max_prefix_len,)) | |
| 114 sys.stdout.write('};\n') | |
| 115 sys.stdout.write('\n') | |
| 116 | |
| 117 sys.stdout.write('''/* | |
| 118 * THIS FILE IS AUTO-GENERATED. DO NOT EDIT! | |
| 119 */ | |
| 120 #ifndef mozilla__net__Http2HuffmanIncoming_h | |
| 121 #define mozilla__net__Http2HuffmanIncoming_h | |
| 122 | |
| 123 namespace mozilla { | |
| 124 namespace net { | |
| 125 | |
| 126 struct HuffmanIncomingTable; | |
| 127 | |
| 128 struct HuffmanIncomingEntry { | |
| 129 HuffmanIncomingTable *mPtr; | |
| 130 uint16_t mValue; | |
| 131 uint8_t mPrefixLen; | |
| 132 }; | |
| 133 | |
| 134 struct HuffmanIncomingTable { | |
| 135 HuffmanIncomingEntry *mEntries; | |
| 136 uint8_t mPrefixLen; | |
| 137 }; | |
| 138 | |
| 139 ''') | |
| 140 | |
| 141 output_table(table) | |
| 142 | |
| 143 sys.stdout.write('''} // namespace net | |
| 144 } // namespace mozilla | |
| 145 | |
| 146 #endif // mozilla__net__Http2HuffmanIncoming_h | |
| 147 ''') |
