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). 7import sys 8 9 10def char_cmp(x, y): 11 rv = cmp(x["nbits"], y["nbits"]) 12 if not rv: 13 rv = cmp(x["bpat"], y["bpat"]) 14 if not rv: 15 rv = cmp(x["ascii"], y["ascii"]) 16 return rv 17 18 19characters = [] 20 21for line in sys.stdin: 22 line = line.rstrip() 23 obracket = line.rfind("[") 24 nbits = int(line[obracket + 1 : -1]) 25 26 oparen = line.find(" (") 27 ascii = int(line[oparen + 2 : oparen + 5].strip()) 28 29 bar = line.find("|", oparen) 30 space = line.find(" ", bar) 31 bpat = line[bar + 1 : space].strip().rstrip("|") 32 33 characters.append({"ascii": ascii, "nbits": nbits, "bpat": bpat}) 34 35characters.sort(cmp=char_cmp) 36raw_entries = [] 37for c in characters: 38 raw_entries.append((c["ascii"], c["bpat"])) 39 40 41class DefaultList(list): 42 def __init__(self, default=None): 43 self.__default = default 44 45 def __ensure_size(self, sz): 46 while sz > len(self): 47 self.append(self.__default) 48 49 def __getitem__(self, idx): 50 self.__ensure_size(idx + 1) 51 rv = super(DefaultList, self).__getitem__(idx) 52 return rv 53 54 def __setitem__(self, idx, val): 55 self.__ensure_size(idx + 1) 56 super(DefaultList, self).__setitem__(idx, val) 57 58 59def expand_to_8bit(bstr): 60 while len(bstr) < 8: 61 bstr += "0" 62 return int(bstr, 2) 63 64 65table = DefaultList() 66for r in raw_entries: 67 ascii, bpat = r 68 ascii = int(ascii) 69 bstrs = bpat.split("|") 70 curr_table = table 71 while len(bstrs) > 1: 72 idx = expand_to_8bit(bstrs[0]) 73 if curr_table[idx] is None: 74 curr_table[idx] = DefaultList() 75 curr_table = curr_table[idx] 76 bstrs.pop(0) 77 78 idx = expand_to_8bit(bstrs[0]) 79 curr_table[idx] = { 80 "prefix_len": len(bstrs[0]), 81 "mask": int(bstrs[0], 2), 82 "value": ascii, 83 } 84 85 86def output_table(table, name_suffix=""): 87 max_prefix_len = 0 88 for i, t in enumerate(table): 89 if isinstance(t, dict): 90 if t["prefix_len"] > max_prefix_len: 91 max_prefix_len = t["prefix_len"] 92 elif t is not None: 93 output_table(t, "%s_%s" % (name_suffix, i)) 94 95 tablename = "HuffmanIncoming%s" % (name_suffix if name_suffix else "Root",) 96 entriestable = tablename.replace("HuffmanIncoming", "HuffmanIncomingEntries") 97 nexttable = tablename.replace("HuffmanIncoming", "HuffmanIncomingNextTables") 98 sys.stdout.write("static const HuffmanIncomingEntry %s[] = {\n" % (entriestable,)) 99 prefix_len = 0 100 value = 0 101 i = 0 102 while i < 256: 103 t = table[i] 104 if isinstance(t, dict): 105 value = t["value"] 106 prefix_len = t["prefix_len"] 107 elif t is not None: 108 break 109 110 sys.stdout.write(" { %s, %s }" % (value, prefix_len)) 111 sys.stdout.write(",\n") 112 i += 1 113 114 indexOfFirstNextTable = i 115 if i < 256: 116 sys.stdout.write("};\n") 117 sys.stdout.write("\n") 118 sys.stdout.write("static const HuffmanIncomingTable* %s[] = {\n" % (nexttable,)) 119 while i < 256: 120 subtable = "%s_%s" % (name_suffix, i) 121 ptr = "&HuffmanIncoming%s" % (subtable,) 122 sys.stdout.write(" %s" % (ptr)) 123 sys.stdout.write(",\n") 124 i += 1 125 else: 126 nexttable = "nullptr" 127 128 sys.stdout.write("};\n") 129 sys.stdout.write("\n") 130 sys.stdout.write("static const HuffmanIncomingTable %s = {\n" % (tablename,)) 131 sys.stdout.write(" %s,\n" % (entriestable,)) 132 sys.stdout.write(" %s,\n" % (nexttable,)) 133 sys.stdout.write(" %s,\n" % (indexOfFirstNextTable,)) 134 sys.stdout.write(" %s\n" % (max_prefix_len,)) 135 sys.stdout.write("};\n") 136 sys.stdout.write("\n") 137 138 139sys.stdout.write( 140 """/* 141 * THIS FILE IS AUTO-GENERATED. DO NOT EDIT! 142 */ 143#ifndef mozilla__net__Http2HuffmanIncoming_h 144#define mozilla__net__Http2HuffmanIncoming_h 145 146namespace mozilla { 147namespace net { 148 149struct HuffmanIncomingTable; 150 151struct HuffmanIncomingEntry { 152 uint16_t mValue:9; // 9 bits so it can hold 0..256 153 uint16_t mPrefixLen:7; // only holds 1..8 154}; 155 156// The data members are public only so they can be statically constructed. All 157// accesses should be done through the functions. 158struct HuffmanIncomingTable { 159 // The normal entries, for indices in the range 0..(mNumEntries-1). 160 const HuffmanIncomingEntry* const mEntries; 161 162 // The next tables, for indices in the range mNumEntries..255. Must be 163 // |nullptr| if mIndexOfFirstNextTable is 256. 164 const HuffmanIncomingTable** const mNextTables; 165 166 // The index of the first next table (equal to the number of entries in 167 // mEntries). This cannot be a uint8_t because it can have the value 256, 168 // in which case there are no next tables and mNextTables must be |nullptr|. 169 const uint16_t mIndexOfFirstNextTable; 170 171 const uint8_t mPrefixLen; 172 173 bool IndexHasANextTable(uint8_t aIndex) const 174 { 175 return aIndex >= mIndexOfFirstNextTable; 176 } 177 178 const HuffmanIncomingEntry* Entry(uint8_t aIndex) const 179 { 180 MOZ_ASSERT(aIndex < mIndexOfFirstNextTable); 181 return &mEntries[aIndex]; 182 } 183 184 const HuffmanIncomingTable* NextTable(uint8_t aIndex) const 185 { 186 MOZ_ASSERT(aIndex >= mIndexOfFirstNextTable); 187 return mNextTables[aIndex - mIndexOfFirstNextTable]; 188 } 189}; 190 191""" 192) 193 194output_table(table) 195 196sys.stdout.write( 197 """} // namespace net 198} // namespace mozilla 199 200#endif // mozilla__net__Http2HuffmanIncoming_h 201""" 202) 203