diff options
Diffstat (limited to 'vendor/golang.org/x/net/http2/hpack/tables.go')
-rw-r--r-- | vendor/golang.org/x/net/http2/hpack/tables.go | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/vendor/golang.org/x/net/http2/hpack/tables.go b/vendor/golang.org/x/net/http2/hpack/tables.go new file mode 100644 index 0000000..a66cfbe --- /dev/null +++ b/vendor/golang.org/x/net/http2/hpack/tables.go | |||
@@ -0,0 +1,479 @@ | |||
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 | |||
5 | package hpack | ||
6 | |||
7 | import ( | ||
8 | "fmt" | ||
9 | ) | ||
10 | |||
11 | // headerFieldTable implements a list of HeaderFields. | ||
12 | // This is used to implement the static and dynamic tables. | ||
13 | type 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 | |||
41 | type pairNameValue struct { | ||
42 | name, value string | ||
43 | } | ||
44 | |||
45 | func (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. | ||
51 | func (t *headerFieldTable) len() int { | ||
52 | return len(t.ents) | ||
53 | } | ||
54 | |||
55 | // addEntry adds a new entry. | ||
56 | func (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. | ||
64 | func (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. | ||
103 | func (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. | ||
117 | func (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 | ||
129 | var staticTable = newStaticTable() | ||
130 | var 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 | |||
194 | func newStaticTable() *headerFieldTable { | ||
195 | t := &headerFieldTable{} | ||
196 | t.init() | ||
197 | for _, e := range staticTableEntries[:] { | ||
198 | t.addEntry(e) | ||
199 | } | ||
200 | return t | ||
201 | } | ||
202 | |||
203 | var 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 | |||
462 | var 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 | } | ||