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
100// staticTable pointer.
101//
102// See Section 2.3.3.
103func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
104	if !f.Sensitive {
105		if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
106			return t.idToIndex(id), true
107		}
108	}
109	if id := t.byName[f.Name]; id != 0 {
110		return t.idToIndex(id), false
111	}
112	return 0, false
113}
114
115// idToIndex converts a unique id to an HPACK index.
116// See Section 2.3.3.
117func (t *headerFieldTable) idToIndex(id uint64) uint64 {
118	if id <= t.evictCount {
119		panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
120	}
121	k := id - t.evictCount - 1 // convert id to an index t.ents[k]
122	if t != staticTable {
123		return uint64(t.len()) - k // dynamic table
124	}
125	return k + 1
126}
127
128// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#appendix-B
129var staticTable = newStaticTable()
130var staticTableEntries = [...]HeaderField{
131	{Name: ":authority"},
132	{Name: ":method", Value: "GET"},
133	{Name: ":method", Value: "POST"},
134	{Name: ":path", Value: "/"},
135	{Name: ":path", Value: "/index.html"},
136	{Name: ":scheme", Value: "http"},
137	{Name: ":scheme", Value: "https"},
138	{Name: ":status", Value: "200"},
139	{Name: ":status", Value: "204"},
140	{Name: ":status", Value: "206"},
141	{Name: ":status", Value: "304"},
142	{Name: ":status", Value: "400"},
143	{Name: ":status", Value: "404"},
144	{Name: ":status", Value: "500"},
145	{Name: "accept-charset"},
146	{Name: "accept-encoding", Value: "gzip, deflate"},
147	{Name: "accept-language"},
148	{Name: "accept-ranges"},
149	{Name: "accept"},
150	{Name: "access-control-allow-origin"},
151	{Name: "age"},
152	{Name: "allow"},
153	{Name: "authorization"},
154	{Name: "cache-control"},
155	{Name: "content-disposition"},
156	{Name: "content-encoding"},
157	{Name: "content-language"},
158	{Name: "content-length"},
159	{Name: "content-location"},
160	{Name: "content-range"},
161	{Name: "content-type"},
162	{Name: "cookie"},
163	{Name: "date"},
164	{Name: "etag"},
165	{Name: "expect"},
166	{Name: "expires"},
167	{Name: "from"},
168	{Name: "host"},
169	{Name: "if-match"},
170	{Name: "if-modified-since"},
171	{Name: "if-none-match"},
172	{Name: "if-range"},
173	{Name: "if-unmodified-since"},
174	{Name: "last-modified"},
175	{Name: "link"},
176	{Name: "location"},
177	{Name: "max-forwards"},
178	{Name: "proxy-authenticate"},
179	{Name: "proxy-authorization"},
180	{Name: "range"},
181	{Name: "referer"},
182	{Name: "refresh"},
183	{Name: "retry-after"},
184	{Name: "server"},
185	{Name: "set-cookie"},
186	{Name: "strict-transport-security"},
187	{Name: "transfer-encoding"},
188	{Name: "user-agent"},
189	{Name: "vary"},
190	{Name: "via"},
191	{Name: "www-authenticate"},
192}
193
194func newStaticTable() *headerFieldTable {
195	t := &headerFieldTable{}
196	t.init()
197	for _, e := range staticTableEntries[:] {
198		t.addEntry(e)
199	}
200	return t
201}
202
203var huffmanCodes = [256]uint32{
204	0x1ff8,
205	0x7fffd8,
206	0xfffffe2,
207	0xfffffe3,
208	0xfffffe4,
209	0xfffffe5,
210	0xfffffe6,
211	0xfffffe7,
212	0xfffffe8,
213	0xffffea,
214	0x3ffffffc,
215	0xfffffe9,
216	0xfffffea,
217	0x3ffffffd,
218	0xfffffeb,
219	0xfffffec,
220	0xfffffed,
221	0xfffffee,
222	0xfffffef,
223	0xffffff0,
224	0xffffff1,
225	0xffffff2,
226	0x3ffffffe,
227	0xffffff3,
228	0xffffff4,
229	0xffffff5,
230	0xffffff6,
231	0xffffff7,
232	0xffffff8,
233	0xffffff9,
234	0xffffffa,
235	0xffffffb,
236	0x14,
237	0x3f8,
238	0x3f9,
239	0xffa,
240	0x1ff9,
241	0x15,
242	0xf8,
243	0x7fa,
244	0x3fa,
245	0x3fb,
246	0xf9,
247	0x7fb,
248	0xfa,
249	0x16,
250	0x17,
251	0x18,
252	0x0,
253	0x1,
254	0x2,
255	0x19,
256	0x1a,
257	0x1b,
258	0x1c,
259	0x1d,
260	0x1e,
261	0x1f,
262	0x5c,
263	0xfb,
264	0x7ffc,
265	0x20,
266	0xffb,
267	0x3fc,
268	0x1ffa,
269	0x21,
270	0x5d,
271	0x5e,
272	0x5f,
273	0x60,
274	0x61,
275	0x62,
276	0x63,
277	0x64,
278	0x65,
279	0x66,
280	0x67,
281	0x68,
282	0x69,
283	0x6a,
284	0x6b,
285	0x6c,
286	0x6d,
287	0x6e,
288	0x6f,
289	0x70,
290	0x71,
291	0x72,
292	0xfc,
293	0x73,
294	0xfd,
295	0x1ffb,
296	0x7fff0,
297	0x1ffc,
298	0x3ffc,
299	0x22,
300	0x7ffd,
301	0x3,
302	0x23,
303	0x4,
304	0x24,
305	0x5,
306	0x25,
307	0x26,
308	0x27,
309	0x6,
310	0x74,
311	0x75,
312	0x28,
313	0x29,
314	0x2a,
315	0x7,
316	0x2b,
317	0x76,
318	0x2c,
319	0x8,
320	0x9,
321	0x2d,
322	0x77,
323	0x78,
324	0x79,
325	0x7a,
326	0x7b,
327	0x7ffe,
328	0x7fc,
329	0x3ffd,
330	0x1ffd,
331	0xffffffc,
332	0xfffe6,
333	0x3fffd2,
334	0xfffe7,
335	0xfffe8,
336	0x3fffd3,
337	0x3fffd4,
338	0x3fffd5,
339	0x7fffd9,
340	0x3fffd6,
341	0x7fffda,
342	0x7fffdb,
343	0x7fffdc,
344	0x7fffdd,
345	0x7fffde,
346	0xffffeb,
347	0x7fffdf,
348	0xffffec,
349	0xffffed,
350	0x3fffd7,
351	0x7fffe0,
352	0xffffee,
353	0x7fffe1,
354	0x7fffe2,
355	0x7fffe3,
356	0x7fffe4,
357	0x1fffdc,
358	0x3fffd8,
359	0x7fffe5,
360	0x3fffd9,
361	0x7fffe6,
362	0x7fffe7,
363	0xffffef,
364	0x3fffda,
365	0x1fffdd,
366	0xfffe9,
367	0x3fffdb,
368	0x3fffdc,
369	0x7fffe8,
370	0x7fffe9,
371	0x1fffde,
372	0x7fffea,
373	0x3fffdd,
374	0x3fffde,
375	0xfffff0,
376	0x1fffdf,
377	0x3fffdf,
378	0x7fffeb,
379	0x7fffec,
380	0x1fffe0,
381	0x1fffe1,
382	0x3fffe0,
383	0x1fffe2,
384	0x7fffed,
385	0x3fffe1,
386	0x7fffee,
387	0x7fffef,
388	0xfffea,
389	0x3fffe2,
390	0x3fffe3,
391	0x3fffe4,
392	0x7ffff0,
393	0x3fffe5,
394	0x3fffe6,
395	0x7ffff1,
396	0x3ffffe0,
397	0x3ffffe1,
398	0xfffeb,
399	0x7fff1,
400	0x3fffe7,
401	0x7ffff2,
402	0x3fffe8,
403	0x1ffffec,
404	0x3ffffe2,
405	0x3ffffe3,
406	0x3ffffe4,
407	0x7ffffde,
408	0x7ffffdf,
409	0x3ffffe5,
410	0xfffff1,
411	0x1ffffed,
412	0x7fff2,
413	0x1fffe3,
414	0x3ffffe6,
415	0x7ffffe0,
416	0x7ffffe1,
417	0x3ffffe7,
418	0x7ffffe2,
419	0xfffff2,
420	0x1fffe4,
421	0x1fffe5,
422	0x3ffffe8,
423	0x3ffffe9,
424	0xffffffd,
425	0x7ffffe3,
426	0x7ffffe4,
427	0x7ffffe5,
428	0xfffec,
429	0xfffff3,
430	0xfffed,
431	0x1fffe6,
432	0x3fffe9,
433	0x1fffe7,
434	0x1fffe8,
435	0x7ffff3,
436	0x3fffea,
437	0x3fffeb,
438	0x1ffffee,
439	0x1ffffef,
440	0xfffff4,
441	0xfffff5,
442	0x3ffffea,
443	0x7ffff4,
444	0x3ffffeb,
445	0x7ffffe6,
446	0x3ffffec,
447	0x3ffffed,
448	0x7ffffe7,
449	0x7ffffe8,
450	0x7ffffe9,
451	0x7ffffea,
452	0x7ffffeb,
453	0xffffffe,
454	0x7ffffec,
455	0x7ffffed,
456	0x7ffffee,
457	0x7ffffef,
458	0x7fffff0,
459	0x3ffffee,
460}
461
462var huffmanCodeLen = [256]uint8{
463	13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28,
464	28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28,
465	6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6,
466	5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10,
467	13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
468	7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6,
469	15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5,
470	6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28,
471	20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23,
472	24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24,
473	22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23,
474	21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23,
475	26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25,
476	19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27,
477	20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23,
478	26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26,
479}
480