Zack Williams | e940c7a | 2019-08-21 14:25:39 -0700 | [diff] [blame] | 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 | "io" |
| 9 | ) |
| 10 | |
| 11 | const ( |
| 12 | uint32Max = ^uint32(0) |
| 13 | initialHeaderTableSize = 4096 |
| 14 | ) |
| 15 | |
| 16 | type Encoder struct { |
| 17 | dynTab dynamicTable |
| 18 | // minSize is the minimum table size set by |
| 19 | // SetMaxDynamicTableSize after the previous Header Table Size |
| 20 | // Update. |
| 21 | minSize uint32 |
| 22 | // maxSizeLimit is the maximum table size this encoder |
| 23 | // supports. This will protect the encoder from too large |
| 24 | // size. |
| 25 | maxSizeLimit uint32 |
| 26 | // tableSizeUpdate indicates whether "Header Table Size |
| 27 | // Update" is required. |
| 28 | tableSizeUpdate bool |
| 29 | w io.Writer |
| 30 | buf []byte |
| 31 | } |
| 32 | |
| 33 | // NewEncoder returns a new Encoder which performs HPACK encoding. An |
| 34 | // encoded data is written to w. |
| 35 | func NewEncoder(w io.Writer) *Encoder { |
| 36 | e := &Encoder{ |
| 37 | minSize: uint32Max, |
| 38 | maxSizeLimit: initialHeaderTableSize, |
| 39 | tableSizeUpdate: false, |
| 40 | w: w, |
| 41 | } |
| 42 | e.dynTab.table.init() |
| 43 | e.dynTab.setMaxSize(initialHeaderTableSize) |
| 44 | return e |
| 45 | } |
| 46 | |
| 47 | // WriteField encodes f into a single Write to e's underlying Writer. |
| 48 | // This function may also produce bytes for "Header Table Size Update" |
| 49 | // if necessary. If produced, it is done before encoding f. |
| 50 | func (e *Encoder) WriteField(f HeaderField) error { |
| 51 | e.buf = e.buf[:0] |
| 52 | |
| 53 | if e.tableSizeUpdate { |
| 54 | e.tableSizeUpdate = false |
| 55 | if e.minSize < e.dynTab.maxSize { |
| 56 | e.buf = appendTableSize(e.buf, e.minSize) |
| 57 | } |
| 58 | e.minSize = uint32Max |
| 59 | e.buf = appendTableSize(e.buf, e.dynTab.maxSize) |
| 60 | } |
| 61 | |
| 62 | idx, nameValueMatch := e.searchTable(f) |
| 63 | if nameValueMatch { |
| 64 | e.buf = appendIndexed(e.buf, idx) |
| 65 | } else { |
| 66 | indexing := e.shouldIndex(f) |
| 67 | if indexing { |
| 68 | e.dynTab.add(f) |
| 69 | } |
| 70 | |
| 71 | if idx == 0 { |
| 72 | e.buf = appendNewName(e.buf, f, indexing) |
| 73 | } else { |
| 74 | e.buf = appendIndexedName(e.buf, f, idx, indexing) |
| 75 | } |
| 76 | } |
| 77 | n, err := e.w.Write(e.buf) |
| 78 | if err == nil && n != len(e.buf) { |
| 79 | err = io.ErrShortWrite |
| 80 | } |
| 81 | return err |
| 82 | } |
| 83 | |
| 84 | // searchTable searches f in both stable and dynamic header tables. |
| 85 | // The static header table is searched first. Only when there is no |
| 86 | // exact match for both name and value, the dynamic header table is |
| 87 | // then searched. If there is no match, i is 0. If both name and value |
| 88 | // match, i is the matched index and nameValueMatch becomes true. If |
| 89 | // only name matches, i points to that index and nameValueMatch |
| 90 | // becomes false. |
| 91 | func (e *Encoder) searchTable(f HeaderField) (i uint64, nameValueMatch bool) { |
| 92 | i, nameValueMatch = staticTable.search(f) |
| 93 | if nameValueMatch { |
| 94 | return i, true |
| 95 | } |
| 96 | |
| 97 | j, nameValueMatch := e.dynTab.table.search(f) |
| 98 | if nameValueMatch || (i == 0 && j != 0) { |
| 99 | return j + uint64(staticTable.len()), nameValueMatch |
| 100 | } |
| 101 | |
| 102 | return i, false |
| 103 | } |
| 104 | |
| 105 | // SetMaxDynamicTableSize changes the dynamic header table size to v. |
| 106 | // The actual size is bounded by the value passed to |
| 107 | // SetMaxDynamicTableSizeLimit. |
| 108 | func (e *Encoder) SetMaxDynamicTableSize(v uint32) { |
| 109 | if v > e.maxSizeLimit { |
| 110 | v = e.maxSizeLimit |
| 111 | } |
| 112 | if v < e.minSize { |
| 113 | e.minSize = v |
| 114 | } |
| 115 | e.tableSizeUpdate = true |
| 116 | e.dynTab.setMaxSize(v) |
| 117 | } |
| 118 | |
| 119 | // SetMaxDynamicTableSizeLimit changes the maximum value that can be |
| 120 | // specified in SetMaxDynamicTableSize to v. By default, it is set to |
| 121 | // 4096, which is the same size of the default dynamic header table |
| 122 | // size described in HPACK specification. If the current maximum |
| 123 | // dynamic header table size is strictly greater than v, "Header Table |
| 124 | // Size Update" will be done in the next WriteField call and the |
| 125 | // maximum dynamic header table size is truncated to v. |
| 126 | func (e *Encoder) SetMaxDynamicTableSizeLimit(v uint32) { |
| 127 | e.maxSizeLimit = v |
| 128 | if e.dynTab.maxSize > v { |
| 129 | e.tableSizeUpdate = true |
| 130 | e.dynTab.setMaxSize(v) |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | // shouldIndex reports whether f should be indexed. |
| 135 | func (e *Encoder) shouldIndex(f HeaderField) bool { |
| 136 | return !f.Sensitive && f.Size() <= e.dynTab.maxSize |
| 137 | } |
| 138 | |
| 139 | // appendIndexed appends index i, as encoded in "Indexed Header Field" |
| 140 | // representation, to dst and returns the extended buffer. |
| 141 | func appendIndexed(dst []byte, i uint64) []byte { |
| 142 | first := len(dst) |
| 143 | dst = appendVarInt(dst, 7, i) |
| 144 | dst[first] |= 0x80 |
| 145 | return dst |
| 146 | } |
| 147 | |
| 148 | // appendNewName appends f, as encoded in one of "Literal Header field |
| 149 | // - New Name" representation variants, to dst and returns the |
| 150 | // extended buffer. |
| 151 | // |
| 152 | // If f.Sensitive is true, "Never Indexed" representation is used. If |
divyadesai | 1900913 | 2020-03-04 12:58:08 +0000 | [diff] [blame] | 153 | // f.Sensitive is false and indexing is true, "Incremental Indexing" |
Zack Williams | e940c7a | 2019-08-21 14:25:39 -0700 | [diff] [blame] | 154 | // representation is used. |
| 155 | func appendNewName(dst []byte, f HeaderField, indexing bool) []byte { |
| 156 | dst = append(dst, encodeTypeByte(indexing, f.Sensitive)) |
| 157 | dst = appendHpackString(dst, f.Name) |
| 158 | return appendHpackString(dst, f.Value) |
| 159 | } |
| 160 | |
| 161 | // appendIndexedName appends f and index i referring indexed name |
| 162 | // entry, as encoded in one of "Literal Header field - Indexed Name" |
| 163 | // representation variants, to dst and returns the extended buffer. |
| 164 | // |
| 165 | // If f.Sensitive is true, "Never Indexed" representation is used. If |
| 166 | // f.Sensitive is false and indexing is true, "Incremental Indexing" |
| 167 | // representation is used. |
| 168 | func appendIndexedName(dst []byte, f HeaderField, i uint64, indexing bool) []byte { |
| 169 | first := len(dst) |
| 170 | var n byte |
| 171 | if indexing { |
| 172 | n = 6 |
| 173 | } else { |
| 174 | n = 4 |
| 175 | } |
| 176 | dst = appendVarInt(dst, n, i) |
| 177 | dst[first] |= encodeTypeByte(indexing, f.Sensitive) |
| 178 | return appendHpackString(dst, f.Value) |
| 179 | } |
| 180 | |
| 181 | // appendTableSize appends v, as encoded in "Header Table Size Update" |
| 182 | // representation, to dst and returns the extended buffer. |
| 183 | func appendTableSize(dst []byte, v uint32) []byte { |
| 184 | first := len(dst) |
| 185 | dst = appendVarInt(dst, 5, uint64(v)) |
| 186 | dst[first] |= 0x20 |
| 187 | return dst |
| 188 | } |
| 189 | |
| 190 | // appendVarInt appends i, as encoded in variable integer form using n |
| 191 | // bit prefix, to dst and returns the extended buffer. |
| 192 | // |
| 193 | // See |
| 194 | // http://http2.github.io/http2-spec/compression.html#integer.representation |
| 195 | func appendVarInt(dst []byte, n byte, i uint64) []byte { |
| 196 | k := uint64((1 << n) - 1) |
| 197 | if i < k { |
| 198 | return append(dst, byte(i)) |
| 199 | } |
| 200 | dst = append(dst, byte(k)) |
| 201 | i -= k |
| 202 | for ; i >= 128; i >>= 7 { |
| 203 | dst = append(dst, byte(0x80|(i&0x7f))) |
| 204 | } |
| 205 | return append(dst, byte(i)) |
| 206 | } |
| 207 | |
| 208 | // appendHpackString appends s, as encoded in "String Literal" |
| 209 | // representation, to dst and returns the extended buffer. |
| 210 | // |
| 211 | // s will be encoded in Huffman codes only when it produces strictly |
| 212 | // shorter byte string. |
| 213 | func appendHpackString(dst []byte, s string) []byte { |
| 214 | huffmanLength := HuffmanEncodeLength(s) |
| 215 | if huffmanLength < uint64(len(s)) { |
| 216 | first := len(dst) |
| 217 | dst = appendVarInt(dst, 7, huffmanLength) |
| 218 | dst = AppendHuffmanString(dst, s) |
| 219 | dst[first] |= 0x80 |
| 220 | } else { |
| 221 | dst = appendVarInt(dst, 7, uint64(len(s))) |
| 222 | dst = append(dst, s...) |
| 223 | } |
| 224 | return dst |
| 225 | } |
| 226 | |
| 227 | // encodeTypeByte returns type byte. If sensitive is true, type byte |
| 228 | // for "Never Indexed" representation is returned. If sensitive is |
| 229 | // false and indexing is true, type byte for "Incremental Indexing" |
| 230 | // representation is returned. Otherwise, type byte for "Without |
| 231 | // Indexing" is returned. |
| 232 | func encodeTypeByte(indexing, sensitive bool) byte { |
| 233 | if sensitive { |
| 234 | return 0x10 |
| 235 | } |
| 236 | if indexing { |
| 237 | return 0x40 |
| 238 | } |
| 239 | return 0 |
| 240 | } |