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