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