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 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  }
   404
View as plain text