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