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