vendor/golang.org/x/net/http2/hpack/tables.go

   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 }