1// Copyright 2014 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package hpack
6
7import (
8	"fmt"
9)
10
11// headerFieldTable implements a list of HeaderFields.
12// This is used to implement the static and dynamic tables.
13type headerFieldTable struct {
14	// For static tables, entries are never evicted.
15	//
16	// For dynamic tables, entries are evicted from ents[0] and added to the end.
17	// Each entry has a unique id that starts at one and increments for each
18	// entry that is added. This unique id is stable across evictions, meaning
19	// it can be used as a pointer to a specific entry. As in hpack, unique ids
20	// are 1-based. The unique id for ents[k] is k + evictCount + 1.
21	//
22	// Zero is not a valid unique id.
23	//
24	// evictCount should not overflow in any remotely practical situation. In
25	// practice, we will have one dynamic table per HTTP/2 connection. If we
26	// assume a very powerful server that handles 1M QPS per connection and each
27	// request adds (then evicts) 100 entries from the table, it would still take
28	// 2M years for evictCount to overflow.
29	ents       []HeaderField
30	evictCount uint64
31
32	// byName maps a HeaderField name to the unique id of the newest entry with
33	// the same name. See above for a definition of "unique id".
34	byName map[string]uint64
35
36	// byNameValue maps a HeaderField name/value pair to the unique id of the newest
37	// entry with the same name and value. See above for a definition of "unique id".
38	byNameValue map[pairNameValue]uint64
39}
40
41type pairNameValue struct {
42	name, value string
43}
44
45func (t *headerFieldTable) init() {
46	t.byName = make(map[string]uint64)
47	t.byNameValue = make(map[pairNameValue]uint64)
48}
49
50// len reports the number of entries in the table.
51func (t *headerFieldTable) len() int {
52	return len(t.ents)
53}
54
55// addEntry adds a new entry.
56func (t *headerFieldTable) addEntry(f HeaderField) {
57	id := uint64(t.len()) + t.evictCount + 1
58	t.byName[f.Name] = id
59	t.byNameValue[pairNameValue{f.Name, f.Value}] = id
60	t.ents = append(t.ents, f)
61}
62
63// evictOldest evicts the n oldest entries in the table.
64func (t *headerFieldTable) evictOldest(n int) {
65	if n > t.len() {
66		panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))
67	}
68	for k := 0; k < n; k++ {
69		f := t.ents[k]
70		id := t.evictCount + uint64(k) + 1
71		if t.byName[f.Name] == id {
72			delete(t.byName, f.Name)
73		}
74		if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
75			delete(t.byNameValue, p)
76		}
77	}
78	copy(t.ents, t.ents[n:])
79	for k := t.len() - n; k < t.len(); k++ {
80		t.ents[k] = HeaderField{} // so strings can be garbage collected
81	}
82	t.ents = t.ents[:t.len()-n]
83	if t.evictCount+uint64(n) < t.evictCount {
84		panic("evictCount overflow")
85	}
86	t.evictCount += uint64(n)
87}
88
89// search finds f in the table. If there is no match, i is 0.
90// If both name and value match, i is the matched index and nameValueMatch
91// becomes true. If only name matches, i points to that index and
92// nameValueMatch becomes false.
93//
94// The returned index is a 1-based HPACK index. For dynamic tables, HPACK says
95// that index 1 should be the newest entry, but t.ents[0] is the oldest entry,
96// meaning t.ents is reversed for dynamic tables. Hence, when t is a dynamic
97// table, the return value i actually refers to the entry t.ents[t.len()-i].
98//
99// All tables are assumed to be a dynamic tables except for the global staticTable.
100//
101// See Section 2.3.3.
102func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
103	if !f.Sensitive {
104		if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
105			return t.idToIndex(id), true
106		}
107	}
108	if id := t.byName[f.Name]; id != 0 {
109		return t.idToIndex(id), false
110	}
111	return 0, false
112}
113
114// idToIndex converts a unique id to an HPACK index.
115// See Section 2.3.3.
116func (t *headerFieldTable) idToIndex(id uint64) uint64 {
117	if id <= t.evictCount {
118		panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
119	}
120	k := id - t.evictCount - 1 // convert id to an index t.ents[k]
121	if t != staticTable {
122		return uint64(t.len()) - k // dynamic table
123	}
124	return k + 1
125}
126
127var huffmanCodes = [256]uint32{
128	0x1ff8,
129	0x7fffd8,
130	0xfffffe2,
131	0xfffffe3,
132	0xfffffe4,
133	0xfffffe5,
134	0xfffffe6,
135	0xfffffe7,
136	0xfffffe8,
137	0xffffea,
138	0x3ffffffc,
139	0xfffffe9,
140	0xfffffea,
141	0x3ffffffd,
142	0xfffffeb,
143	0xfffffec,
144	0xfffffed,
145	0xfffffee,
146	0xfffffef,
147	0xffffff0,
148	0xffffff1,
149	0xffffff2,
150	0x3ffffffe,
151	0xffffff3,
152	0xffffff4,
153	0xffffff5,
154	0xffffff6,
155	0xffffff7,
156	0xffffff8,
157	0xffffff9,
158	0xffffffa,
159	0xffffffb,
160	0x14,
161	0x3f8,
162	0x3f9,
163	0xffa,
164	0x1ff9,
165	0x15,
166	0xf8,
167	0x7fa,
168	0x3fa,
169	0x3fb,
170	0xf9,
171	0x7fb,
172	0xfa,
173	0x16,
174	0x17,
175	0x18,
176	0x0,
177	0x1,
178	0x2,
179	0x19,
180	0x1a,
181	0x1b,
182	0x1c,
183	0x1d,
184	0x1e,
185	0x1f,
186	0x5c,
187	0xfb,
188	0x7ffc,
189	0x20,
190	0xffb,
191	0x3fc,
192	0x1ffa,
193	0x21,
194	0x5d,
195	0x5e,
196	0x5f,
197	0x60,
198	0x61,
199	0x62,
200	0x63,
201	0x64,
202	0x65,
203	0x66,
204	0x67,
205	0x68,
206	0x69,
207	0x6a,
208	0x6b,
209	0x6c,
210	0x6d,
211	0x6e,
212	0x6f,
213	0x70,
214	0x71,
215	0x72,
216	0xfc,
217	0x73,
218	0xfd,
219	0x1ffb,
220	0x7fff0,
221	0x1ffc,
222	0x3ffc,
223	0x22,
224	0x7ffd,
225	0x3,
226	0x23,
227	0x4,
228	0x24,
229	0x5,
230	0x25,
231	0x26,
232	0x27,
233	0x6,
234	0x74,
235	0x75,
236	0x28,
237	0x29,
238	0x2a,
239	0x7,
240	0x2b,
241	0x76,
242	0x2c,
243	0x8,
244	0x9,
245	0x2d,
246	0x77,
247	0x78,
248	0x79,
249	0x7a,
250	0x7b,
251	0x7ffe,
252	0x7fc,
253	0x3ffd,
254	0x1ffd,
255	0xffffffc,
256	0xfffe6,
257	0x3fffd2,
258	0xfffe7,
259	0xfffe8,
260	0x3fffd3,
261	0x3fffd4,
262	0x3fffd5,
263	0x7fffd9,
264	0x3fffd6,
265	0x7fffda,
266	0x7fffdb,
267	0x7fffdc,
268	0x7fffdd,
269	0x7fffde,
270	0xffffeb,
271	0x7fffdf,
272	0xffffec,
273	0xffffed,
274	0x3fffd7,
275	0x7fffe0,
276	0xffffee,
277	0x7fffe1,
278	0x7fffe2,
279	0x7fffe3,
280	0x7fffe4,
281	0x1fffdc,
282	0x3fffd8,
283	0x7fffe5,
284	0x3fffd9,
285	0x7fffe6,
286	0x7fffe7,
287	0xffffef,
288	0x3fffda,
289	0x1fffdd,
290	0xfffe9,
291	0x3fffdb,
292	0x3fffdc,
293	0x7fffe8,
294	0x7fffe9,
295	0x1fffde,
296	0x7fffea,
297	0x3fffdd,
298	0x3fffde,
299	0xfffff0,
300	0x1fffdf,
301	0x3fffdf,
302	0x7fffeb,
303	0x7fffec,
304	0x1fffe0,
305	0x1fffe1,
306	0x3fffe0,
307	0x1fffe2,
308	0x7fffed,
309	0x3fffe1,
310	0x7fffee,
311	0x7fffef,
312	0xfffea,
313	0x3fffe2,
314	0x3fffe3,
315	0x3fffe4,
316	0x7ffff0,
317	0x3fffe5,
318	0x3fffe6,
319	0x7ffff1,
320	0x3ffffe0,
321	0x3ffffe1,
322	0xfffeb,
323	0x7fff1,
324	0x3fffe7,
325	0x7ffff2,
326	0x3fffe8,
327	0x1ffffec,
328	0x3ffffe2,
329	0x3ffffe3,
330	0x3ffffe4,
331	0x7ffffde,
332	0x7ffffdf,
333	0x3ffffe5,
334	0xfffff1,
335	0x1ffffed,
336	0x7fff2,
337	0x1fffe3,
338	0x3ffffe6,
339	0x7ffffe0,
340	0x7ffffe1,
341	0x3ffffe7,
342	0x7ffffe2,
343	0xfffff2,
344	0x1fffe4,
345	0x1fffe5,
346	0x3ffffe8,
347	0x3ffffe9,
348	0xffffffd,
349	0x7ffffe3,
350	0x7ffffe4,
351	0x7ffffe5,
352	0xfffec,
353	0xfffff3,
354	0xfffed,
355	0x1fffe6,
356	0x3fffe9,
357	0x1fffe7,
358	0x1fffe8,
359	0x7ffff3,
360	0x3fffea,
361	0x3fffeb,
362	0x1ffffee,
363	0x1ffffef,
364	0xfffff4,
365	0xfffff5,
366	0x3ffffea,
367	0x7ffff4,
368	0x3ffffeb,
369	0x7ffffe6,
370	0x3ffffec,
371	0x3ffffed,
372	0x7ffffe7,
373	0x7ffffe8,
374	0x7ffffe9,
375	0x7ffffea,
376	0x7ffffeb,
377	0xffffffe,
378	0x7ffffec,
379	0x7ffffed,
380	0x7ffffee,
381	0x7ffffef,
382	0x7fffff0,
383	0x3ffffee,
384}
385
386var huffmanCodeLen = [256]uint8{
387	13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28,
388	28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28,
389	6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6,
390	5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10,
391	13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
392	7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6,
393	15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5,
394	6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28,
395	20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23,
396	24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24,
397	22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23,
398	21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23,
399	26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25,
400	19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27,
401	20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23,
402	26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26,
403}
404