tables.go (7719B)
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 staticTable. 100 // 101 // See Section 2.3.3. 102 func (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. 116 func (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 127 var 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 386 var 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 }