Source file src/pkg/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	}
   480	

View as plain text