| // Copyright 2014 The Go Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style | |
| // license that can be found in the LICENSE file. | |
| package hpack | |
| import ( | |
| "fmt" | |
| ) | |
| // headerFieldTable implements a list of HeaderFields. | |
| // This is used to implement the static and dynamic tables. | |
| type headerFieldTable struct { | |
| // For static tables, entries are never evicted. | |
| // | |
| // For dynamic tables, entries are evicted from ents[0] and added to the end. | |
| // Each entry has a unique id that starts at one and increments for each | |
| // entry that is added. This unique id is stable across evictions, meaning | |
| // it can be used as a pointer to a specific entry. As in hpack, unique ids | |
| // are 1-based. The unique id for ents[k] is k + evictCount + 1. | |
| // | |
| // Zero is not a valid unique id. | |
| // | |
| // evictCount should not overflow in any remotely practical situation. In | |
| // practice, we will have one dynamic table per HTTP/2 connection. If we | |
| // assume a very powerful server that handles 1M QPS per connection and each | |
| // request adds (then evicts) 100 entries from the table, it would still take | |
| // 2M years for evictCount to overflow. | |
| ents []HeaderField | |
| evictCount uint64 | |
| // byName maps a HeaderField name to the unique id of the newest entry with | |
| // the same name. See above for a definition of "unique id". | |
| byName map[string]uint64 | |
| // byNameValue maps a HeaderField name/value pair to the unique id of the newest | |
| // entry with the same name and value. See above for a definition of "unique id". | |
| byNameValue map[pairNameValue]uint64 | |
| } | |
| type pairNameValue struct { | |
| name, value string | |
| } | |
| func (t *headerFieldTable) init() { | |
| t.byName = make(map[string]uint64) | |
| t.byNameValue = make(map[pairNameValue]uint64) | |
| } | |
| // len reports the number of entries in the table. | |
| func (t *headerFieldTable) len() int { | |
| return len(t.ents) | |
| } | |
| // addEntry adds a new entry. | |
| func (t *headerFieldTable) addEntry(f HeaderField) { | |
| id := uint64(t.len()) + t.evictCount + 1 | |
| t.byName[f.Name] = id | |
| t.byNameValue[pairNameValue{f.Name, f.Value}] = id | |
| t.ents = append(t.ents, f) | |
| } | |
| // evictOldest evicts the n oldest entries in the table. | |
| func (t *headerFieldTable) evictOldest(n int) { | |
| if n > t.len() { | |
| panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len())) | |
| } | |
| for k := 0; k < n; k++ { | |
| f := t.ents[k] | |
| id := t.evictCount + uint64(k) + 1 | |
| if t.byName[f.Name] == id { | |
| delete(t.byName, f.Name) | |
| } | |
| if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id { | |
| delete(t.byNameValue, p) | |
| } | |
| } | |
| copy(t.ents, t.ents[n:]) | |
| for k := t.len() - n; k < t.len(); k++ { | |
| t.ents[k] = HeaderField{} // so strings can be garbage collected | |
| } | |
| t.ents = t.ents[:t.len()-n] | |
| if t.evictCount+uint64(n) < t.evictCount { | |
| panic("evictCount overflow") | |
| } | |
| t.evictCount += uint64(n) | |
| } | |
| // search finds f in the table. If there is no match, i is 0. | |
| // If both name and value match, i is the matched index and nameValueMatch | |
| // becomes true. If only name matches, i points to that index and | |
| // nameValueMatch becomes false. | |
| // | |
| // The returned index is a 1-based HPACK index. For dynamic tables, HPACK says | |
| // that index 1 should be the newest entry, but t.ents[0] is the oldest entry, | |
| // meaning t.ents is reversed for dynamic tables. Hence, when t is a dynamic | |
| // table, the return value i actually refers to the entry t.ents[t.len()-i]. | |
| // | |
| // All tables are assumed to be a dynamic tables except for the global | |
| // staticTable pointer. | |
| // | |
| // See Section 2.3.3. | |
| func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) { | |
| if !f.Sensitive { | |
| if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 { | |
| return t.idToIndex(id), true | |
| } | |
| } | |
| if id := t.byName[f.Name]; id != 0 { | |
| return t.idToIndex(id), false | |
| } | |
| return 0, false | |
| } | |
| // idToIndex converts a unique id to an HPACK index. | |
| // See Section 2.3.3. | |
| func (t *headerFieldTable) idToIndex(id uint64) uint64 { | |
| if id <= t.evictCount { | |
| panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount)) | |
| } | |
| k := id - t.evictCount - 1 // convert id to an index t.ents[k] | |
| if t != staticTable { | |
| return uint64(t.len()) - k // dynamic table | |
| } | |
| return k + 1 | |
| } | |
| // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#appendix-B | |
| var staticTable = newStaticTable() | |
| var staticTableEntries = [...]HeaderField{ | |
| {Name: ":authority"}, | |
| {Name: ":method", Value: "GET"}, | |
| {Name: ":method", Value: "POST"}, | |
| {Name: ":path", Value: "/"}, | |
| {Name: ":path", Value: "/index.html"}, | |
| {Name: ":scheme", Value: "http"}, | |
| {Name: ":scheme", Value: "https"}, | |
| {Name: ":status", Value: "200"}, | |
| {Name: ":status", Value: "204"}, | |
| {Name: ":status", Value: "206"}, | |
| {Name: ":status", Value: "304"}, | |
| {Name: ":status", Value: "400"}, | |
| {Name: ":status", Value: "404"}, | |
| {Name: ":status", Value: "500"}, | |
| {Name: "accept-charset"}, | |
| {Name: "accept-encoding", Value: "gzip, deflate"}, | |
| {Name: "accept-language"}, | |
| {Name: "accept-ranges"}, | |
| {Name: "accept"}, | |
| {Name: "access-control-allow-origin"}, | |
| {Name: "age"}, | |
| {Name: "allow"}, | |
| {Name: "authorization"}, | |
| {Name: "cache-control"}, | |
| {Name: "content-disposition"}, | |
| {Name: "content-encoding"}, | |
| {Name: "content-language"}, | |
| {Name: "content-length"}, | |
| {Name: "content-location"}, | |
| {Name: "content-range"}, | |
| {Name: "content-type"}, | |
| {Name: "cookie"}, | |
| {Name: "date"}, | |
| {Name: "etag"}, | |
| {Name: "expect"}, | |
| {Name: "expires"}, | |
| {Name: "from"}, | |
| {Name: "host"}, | |
| {Name: "if-match"}, | |
| {Name: "if-modified-since"}, | |
| {Name: "if-none-match"}, | |
| {Name: "if-range"}, | |
| {Name: "if-unmodified-since"}, | |
| {Name: "last-modified"}, | |
| {Name: "link"}, | |
| {Name: "location"}, | |
| {Name: "max-forwards"}, | |
| {Name: "proxy-authenticate"}, | |
| {Name: "proxy-authorization"}, | |
| {Name: "range"}, | |
| {Name: "referer"}, | |
| {Name: "refresh"}, | |
| {Name: "retry-after"}, | |
| {Name: "server"}, | |
| {Name: "set-cookie"}, | |
| {Name: "strict-transport-security"}, | |
| {Name: "transfer-encoding"}, | |
| {Name: "user-agent"}, | |
| {Name: "vary"}, | |
| {Name: "via"}, | |
| {Name: "www-authenticate"}, | |
| } | |
| func newStaticTable() *headerFieldTable { | |
| t := &headerFieldTable{} | |
| t.init() | |
| for _, e := range staticTableEntries[:] { | |
| t.addEntry(e) | |
| } | |
| return t | |
| } | |
| var huffmanCodes = [256]uint32{ | |
| 0x1ff8, | |
| 0x7fffd8, | |
| 0xfffffe2, | |
| 0xfffffe3, | |
| 0xfffffe4, | |
| 0xfffffe5, | |
| 0xfffffe6, | |
| 0xfffffe7, | |
| 0xfffffe8, | |
| 0xffffea, | |
| 0x3ffffffc, | |
| 0xfffffe9, | |
| 0xfffffea, | |
| 0x3ffffffd, | |
| 0xfffffeb, | |
| 0xfffffec, | |
| 0xfffffed, | |
| 0xfffffee, | |
| 0xfffffef, | |
| 0xffffff0, | |
| 0xffffff1, | |
| 0xffffff2, | |
| 0x3ffffffe, | |
| 0xffffff3, | |
| 0xffffff4, | |
| 0xffffff5, | |
| 0xffffff6, | |
| 0xffffff7, | |
| 0xffffff8, | |
| 0xffffff9, | |
| 0xffffffa, | |
| 0xffffffb, | |
| 0x14, | |
| 0x3f8, | |
| 0x3f9, | |
| 0xffa, | |
| 0x1ff9, | |
| 0x15, | |
| 0xf8, | |
| 0x7fa, | |
| 0x3fa, | |
| 0x3fb, | |
| 0xf9, | |
| 0x7fb, | |
| 0xfa, | |
| 0x16, | |
| 0x17, | |
| 0x18, | |
| 0x0, | |
| 0x1, | |
| 0x2, | |
| 0x19, | |
| 0x1a, | |
| 0x1b, | |
| 0x1c, | |
| 0x1d, | |
| 0x1e, | |
| 0x1f, | |
| 0x5c, | |
| 0xfb, | |
| 0x7ffc, | |
| 0x20, | |
| 0xffb, | |
| 0x3fc, | |
| 0x1ffa, | |
| 0x21, | |
| 0x5d, | |
| 0x5e, | |
| 0x5f, | |
| 0x60, | |
| 0x61, | |
| 0x62, | |
| 0x63, | |
| 0x64, | |
| 0x65, | |
| 0x66, | |
| 0x67, | |
| 0x68, | |
| 0x69, | |
| 0x6a, | |
| 0x6b, | |
| 0x6c, | |
| 0x6d, | |
| 0x6e, | |
| 0x6f, | |
| 0x70, | |
| 0x71, | |
| 0x72, | |
| 0xfc, | |
| 0x73, | |
| 0xfd, | |
| 0x1ffb, | |
| 0x7fff0, | |
| 0x1ffc, | |
| 0x3ffc, | |
| 0x22, | |
| 0x7ffd, | |
| 0x3, | |
| 0x23, | |
| 0x4, | |
| 0x24, | |
| 0x5, | |
| 0x25, | |
| 0x26, | |
| 0x27, | |
| 0x6, | |
| 0x74, | |
| 0x75, | |
| 0x28, | |
| 0x29, | |
| 0x2a, | |
| 0x7, | |
| 0x2b, | |
| 0x76, | |
| 0x2c, | |
| 0x8, | |
| 0x9, | |
| 0x2d, | |
| 0x77, | |
| 0x78, | |
| 0x79, | |
| 0x7a, | |
| 0x7b, | |
| 0x7ffe, | |
| 0x7fc, | |
| 0x3ffd, | |
| 0x1ffd, | |
| 0xffffffc, | |
| 0xfffe6, | |
| 0x3fffd2, | |
| 0xfffe7, | |
| 0xfffe8, | |
| 0x3fffd3, | |
| 0x3fffd4, | |
| 0x3fffd5, | |
| 0x7fffd9, | |
| 0x3fffd6, | |
| 0x7fffda, | |
| 0x7fffdb, | |
| 0x7fffdc, | |
| 0x7fffdd, | |
| 0x7fffde, | |
| 0xffffeb, | |
| 0x7fffdf, | |
| 0xffffec, | |
| 0xffffed, | |
| 0x3fffd7, | |
| 0x7fffe0, | |
| 0xffffee, | |
| 0x7fffe1, | |
| 0x7fffe2, | |
| 0x7fffe3, | |
| 0x7fffe4, | |
| 0x1fffdc, | |
| 0x3fffd8, | |
| 0x7fffe5, | |
| 0x3fffd9, | |
| 0x7fffe6, | |
| 0x7fffe7, | |
| 0xffffef, | |
| 0x3fffda, | |
| 0x1fffdd, | |
| 0xfffe9, | |
| 0x3fffdb, | |
| 0x3fffdc, | |
| 0x7fffe8, | |
| 0x7fffe9, | |
| 0x1fffde, | |
| 0x7fffea, | |
| 0x3fffdd, | |
| 0x3fffde, | |
| 0xfffff0, | |
| 0x1fffdf, | |
| 0x3fffdf, | |
| 0x7fffeb, | |
| 0x7fffec, | |
| 0x1fffe0, | |
| 0x1fffe1, | |
| 0x3fffe0, | |
| 0x1fffe2, | |
| 0x7fffed, | |
| 0x3fffe1, | |
| 0x7fffee, | |
| 0x7fffef, | |
| 0xfffea, | |
| 0x3fffe2, | |
| 0x3fffe3, | |
| 0x3fffe4, | |
| 0x7ffff0, | |
| 0x3fffe5, | |
| 0x3fffe6, | |
| 0x7ffff1, | |
| 0x3ffffe0, | |
| 0x3ffffe1, | |
| 0xfffeb, | |
| 0x7fff1, | |
| 0x3fffe7, | |
| 0x7ffff2, | |
| 0x3fffe8, | |
| 0x1ffffec, | |
| 0x3ffffe2, | |
| 0x3ffffe3, | |
| 0x3ffffe4, | |
| 0x7ffffde, | |
| 0x7ffffdf, | |
| 0x3ffffe5, | |
| 0xfffff1, | |
| 0x1ffffed, | |
| 0x7fff2, | |
| 0x1fffe3, | |
| 0x3ffffe6, | |
| 0x7ffffe0, | |
| 0x7ffffe1, | |
| 0x3ffffe7, | |
| 0x7ffffe2, | |
| 0xfffff2, | |
| 0x1fffe4, | |
| 0x1fffe5, | |
| 0x3ffffe8, | |
| 0x3ffffe9, | |
| 0xffffffd, | |
| 0x7ffffe3, | |
| 0x7ffffe4, | |
| 0x7ffffe5, | |
| 0xfffec, | |
| 0xfffff3, | |
| 0xfffed, | |
| 0x1fffe6, | |
| 0x3fffe9, | |
| 0x1fffe7, | |
| 0x1fffe8, | |
| 0x7ffff3, | |
| 0x3fffea, | |
| 0x3fffeb, | |
| 0x1ffffee, | |
| 0x1ffffef, | |
| 0xfffff4, | |
| 0xfffff5, | |
| 0x3ffffea, | |
| 0x7ffff4, | |
| 0x3ffffeb, | |
| 0x7ffffe6, | |
| 0x3ffffec, | |
| 0x3ffffed, | |
| 0x7ffffe7, | |
| 0x7ffffe8, | |
| 0x7ffffe9, | |
| 0x7ffffea, | |
| 0x7ffffeb, | |
| 0xffffffe, | |
| 0x7ffffec, | |
| 0x7ffffed, | |
| 0x7ffffee, | |
| 0x7ffffef, | |
| 0x7fffff0, | |
| 0x3ffffee, | |
| } | |
| var huffmanCodeLen = [256]uint8{ | |
| 13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28, | |
| 28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28, | |
| 6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6, | |
| 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10, | |
| 13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
| 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6, | |
| 15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5, | |
| 6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28, | |
| 20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23, | |
| 24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24, | |
| 22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23, | |
| 21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23, | |
| 26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25, | |
| 19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27, | |
| 20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23, | |
| 26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26, | |
| } |