Project import generated by Copybara.
PiperOrigin-RevId: 229942388
Change-Id: Ib5a23c152c95ed4294cece9f902227c21ce531ef
diff --git a/spdy/core/hpack/hpack_constants.cc b/spdy/core/hpack/hpack_constants.cc
new file mode 100644
index 0000000..9c1498a
--- /dev/null
+++ b/spdy/core/hpack/hpack_constants.cc
@@ -0,0 +1,386 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+
+#include <cstddef>
+#include <memory>
+#include <vector>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h"
+
+namespace spdy {
+
+// Produced by applying the python program [1] with tables provided by [2]
+// (inserted into the source of the python program) and copy-paste them into
+// this file.
+//
+// [1] net/tools/build_hpack_constants.py in Chromium
+// [2] http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08
+
+// HpackHuffmanSymbol entries are initialized as {code, length, id}.
+// Codes are specified in the |length| most-significant bits of |code|.
+const std::vector<HpackHuffmanSymbol>& HpackHuffmanCodeVector() {
+ static const auto* kHpackHuffmanCode = new std::vector<HpackHuffmanSymbol>{
+ {0xffc00000ul, 13, 0}, // 11111111|11000
+ {0xffffb000ul, 23, 1}, // 11111111|11111111|1011000
+ {0xfffffe20ul, 28, 2}, // 11111111|11111111|11111110|0010
+ {0xfffffe30ul, 28, 3}, // 11111111|11111111|11111110|0011
+ {0xfffffe40ul, 28, 4}, // 11111111|11111111|11111110|0100
+ {0xfffffe50ul, 28, 5}, // 11111111|11111111|11111110|0101
+ {0xfffffe60ul, 28, 6}, // 11111111|11111111|11111110|0110
+ {0xfffffe70ul, 28, 7}, // 11111111|11111111|11111110|0111
+ {0xfffffe80ul, 28, 8}, // 11111111|11111111|11111110|1000
+ {0xffffea00ul, 24, 9}, // 11111111|11111111|11101010
+ {0xfffffff0ul, 30, 10}, // 11111111|11111111|11111111|111100
+ {0xfffffe90ul, 28, 11}, // 11111111|11111111|11111110|1001
+ {0xfffffea0ul, 28, 12}, // 11111111|11111111|11111110|1010
+ {0xfffffff4ul, 30, 13}, // 11111111|11111111|11111111|111101
+ {0xfffffeb0ul, 28, 14}, // 11111111|11111111|11111110|1011
+ {0xfffffec0ul, 28, 15}, // 11111111|11111111|11111110|1100
+ {0xfffffed0ul, 28, 16}, // 11111111|11111111|11111110|1101
+ {0xfffffee0ul, 28, 17}, // 11111111|11111111|11111110|1110
+ {0xfffffef0ul, 28, 18}, // 11111111|11111111|11111110|1111
+ {0xffffff00ul, 28, 19}, // 11111111|11111111|11111111|0000
+ {0xffffff10ul, 28, 20}, // 11111111|11111111|11111111|0001
+ {0xffffff20ul, 28, 21}, // 11111111|11111111|11111111|0010
+ {0xfffffff8ul, 30, 22}, // 11111111|11111111|11111111|111110
+ {0xffffff30ul, 28, 23}, // 11111111|11111111|11111111|0011
+ {0xffffff40ul, 28, 24}, // 11111111|11111111|11111111|0100
+ {0xffffff50ul, 28, 25}, // 11111111|11111111|11111111|0101
+ {0xffffff60ul, 28, 26}, // 11111111|11111111|11111111|0110
+ {0xffffff70ul, 28, 27}, // 11111111|11111111|11111111|0111
+ {0xffffff80ul, 28, 28}, // 11111111|11111111|11111111|1000
+ {0xffffff90ul, 28, 29}, // 11111111|11111111|11111111|1001
+ {0xffffffa0ul, 28, 30}, // 11111111|11111111|11111111|1010
+ {0xffffffb0ul, 28, 31}, // 11111111|11111111|11111111|1011
+ {0x50000000ul, 6, 32}, // ' ' 010100
+ {0xfe000000ul, 10, 33}, // '!' 11111110|00
+ {0xfe400000ul, 10, 34}, // '"' 11111110|01
+ {0xffa00000ul, 12, 35}, // '#' 11111111|1010
+ {0xffc80000ul, 13, 36}, // '$' 11111111|11001
+ {0x54000000ul, 6, 37}, // '%' 010101
+ {0xf8000000ul, 8, 38}, // '&' 11111000
+ {0xff400000ul, 11, 39}, // ''' 11111111|010
+ {0xfe800000ul, 10, 40}, // '(' 11111110|10
+ {0xfec00000ul, 10, 41}, // ')' 11111110|11
+ {0xf9000000ul, 8, 42}, // '*' 11111001
+ {0xff600000ul, 11, 43}, // '+' 11111111|011
+ {0xfa000000ul, 8, 44}, // ',' 11111010
+ {0x58000000ul, 6, 45}, // '-' 010110
+ {0x5c000000ul, 6, 46}, // '.' 010111
+ {0x60000000ul, 6, 47}, // '/' 011000
+ {0x00000000ul, 5, 48}, // '0' 00000
+ {0x08000000ul, 5, 49}, // '1' 00001
+ {0x10000000ul, 5, 50}, // '2' 00010
+ {0x64000000ul, 6, 51}, // '3' 011001
+ {0x68000000ul, 6, 52}, // '4' 011010
+ {0x6c000000ul, 6, 53}, // '5' 011011
+ {0x70000000ul, 6, 54}, // '6' 011100
+ {0x74000000ul, 6, 55}, // '7' 011101
+ {0x78000000ul, 6, 56}, // '8' 011110
+ {0x7c000000ul, 6, 57}, // '9' 011111
+ {0xb8000000ul, 7, 58}, // ':' 1011100
+ {0xfb000000ul, 8, 59}, // ';' 11111011
+ {0xfff80000ul, 15, 60}, // '<' 11111111|1111100
+ {0x80000000ul, 6, 61}, // '=' 100000
+ {0xffb00000ul, 12, 62}, // '>' 11111111|1011
+ {0xff000000ul, 10, 63}, // '?' 11111111|00
+ {0xffd00000ul, 13, 64}, // '@' 11111111|11010
+ {0x84000000ul, 6, 65}, // 'A' 100001
+ {0xba000000ul, 7, 66}, // 'B' 1011101
+ {0xbc000000ul, 7, 67}, // 'C' 1011110
+ {0xbe000000ul, 7, 68}, // 'D' 1011111
+ {0xc0000000ul, 7, 69}, // 'E' 1100000
+ {0xc2000000ul, 7, 70}, // 'F' 1100001
+ {0xc4000000ul, 7, 71}, // 'G' 1100010
+ {0xc6000000ul, 7, 72}, // 'H' 1100011
+ {0xc8000000ul, 7, 73}, // 'I' 1100100
+ {0xca000000ul, 7, 74}, // 'J' 1100101
+ {0xcc000000ul, 7, 75}, // 'K' 1100110
+ {0xce000000ul, 7, 76}, // 'L' 1100111
+ {0xd0000000ul, 7, 77}, // 'M' 1101000
+ {0xd2000000ul, 7, 78}, // 'N' 1101001
+ {0xd4000000ul, 7, 79}, // 'O' 1101010
+ {0xd6000000ul, 7, 80}, // 'P' 1101011
+ {0xd8000000ul, 7, 81}, // 'Q' 1101100
+ {0xda000000ul, 7, 82}, // 'R' 1101101
+ {0xdc000000ul, 7, 83}, // 'S' 1101110
+ {0xde000000ul, 7, 84}, // 'T' 1101111
+ {0xe0000000ul, 7, 85}, // 'U' 1110000
+ {0xe2000000ul, 7, 86}, // 'V' 1110001
+ {0xe4000000ul, 7, 87}, // 'W' 1110010
+ {0xfc000000ul, 8, 88}, // 'X' 11111100
+ {0xe6000000ul, 7, 89}, // 'Y' 1110011
+ {0xfd000000ul, 8, 90}, // 'Z' 11111101
+ {0xffd80000ul, 13, 91}, // '[' 11111111|11011
+ {0xfffe0000ul, 19, 92}, // '\' 11111111|11111110|000
+ {0xffe00000ul, 13, 93}, // ']' 11111111|11100
+ {0xfff00000ul, 14, 94}, // '^' 11111111|111100
+ {0x88000000ul, 6, 95}, // '_' 100010
+ {0xfffa0000ul, 15, 96}, // '`' 11111111|1111101
+ {0x18000000ul, 5, 97}, // 'a' 00011
+ {0x8c000000ul, 6, 98}, // 'b' 100011
+ {0x20000000ul, 5, 99}, // 'c' 00100
+ {0x90000000ul, 6, 100}, // 'd' 100100
+ {0x28000000ul, 5, 101}, // 'e' 00101
+ {0x94000000ul, 6, 102}, // 'f' 100101
+ {0x98000000ul, 6, 103}, // 'g' 100110
+ {0x9c000000ul, 6, 104}, // 'h' 100111
+ {0x30000000ul, 5, 105}, // 'i' 00110
+ {0xe8000000ul, 7, 106}, // 'j' 1110100
+ {0xea000000ul, 7, 107}, // 'k' 1110101
+ {0xa0000000ul, 6, 108}, // 'l' 101000
+ {0xa4000000ul, 6, 109}, // 'm' 101001
+ {0xa8000000ul, 6, 110}, // 'n' 101010
+ {0x38000000ul, 5, 111}, // 'o' 00111
+ {0xac000000ul, 6, 112}, // 'p' 101011
+ {0xec000000ul, 7, 113}, // 'q' 1110110
+ {0xb0000000ul, 6, 114}, // 'r' 101100
+ {0x40000000ul, 5, 115}, // 's' 01000
+ {0x48000000ul, 5, 116}, // 't' 01001
+ {0xb4000000ul, 6, 117}, // 'u' 101101
+ {0xee000000ul, 7, 118}, // 'v' 1110111
+ {0xf0000000ul, 7, 119}, // 'w' 1111000
+ {0xf2000000ul, 7, 120}, // 'x' 1111001
+ {0xf4000000ul, 7, 121}, // 'y' 1111010
+ {0xf6000000ul, 7, 122}, // 'z' 1111011
+ {0xfffc0000ul, 15, 123}, // '{' 11111111|1111110
+ {0xff800000ul, 11, 124}, // '|' 11111111|100
+ {0xfff40000ul, 14, 125}, // '}' 11111111|111101
+ {0xffe80000ul, 13, 126}, // '~' 11111111|11101
+ {0xffffffc0ul, 28, 127}, // 11111111|11111111|11111111|1100
+ {0xfffe6000ul, 20, 128}, // 11111111|11111110|0110
+ {0xffff4800ul, 22, 129}, // 11111111|11111111|010010
+ {0xfffe7000ul, 20, 130}, // 11111111|11111110|0111
+ {0xfffe8000ul, 20, 131}, // 11111111|11111110|1000
+ {0xffff4c00ul, 22, 132}, // 11111111|11111111|010011
+ {0xffff5000ul, 22, 133}, // 11111111|11111111|010100
+ {0xffff5400ul, 22, 134}, // 11111111|11111111|010101
+ {0xffffb200ul, 23, 135}, // 11111111|11111111|1011001
+ {0xffff5800ul, 22, 136}, // 11111111|11111111|010110
+ {0xffffb400ul, 23, 137}, // 11111111|11111111|1011010
+ {0xffffb600ul, 23, 138}, // 11111111|11111111|1011011
+ {0xffffb800ul, 23, 139}, // 11111111|11111111|1011100
+ {0xffffba00ul, 23, 140}, // 11111111|11111111|1011101
+ {0xffffbc00ul, 23, 141}, // 11111111|11111111|1011110
+ {0xffffeb00ul, 24, 142}, // 11111111|11111111|11101011
+ {0xffffbe00ul, 23, 143}, // 11111111|11111111|1011111
+ {0xffffec00ul, 24, 144}, // 11111111|11111111|11101100
+ {0xffffed00ul, 24, 145}, // 11111111|11111111|11101101
+ {0xffff5c00ul, 22, 146}, // 11111111|11111111|010111
+ {0xffffc000ul, 23, 147}, // 11111111|11111111|1100000
+ {0xffffee00ul, 24, 148}, // 11111111|11111111|11101110
+ {0xffffc200ul, 23, 149}, // 11111111|11111111|1100001
+ {0xffffc400ul, 23, 150}, // 11111111|11111111|1100010
+ {0xffffc600ul, 23, 151}, // 11111111|11111111|1100011
+ {0xffffc800ul, 23, 152}, // 11111111|11111111|1100100
+ {0xfffee000ul, 21, 153}, // 11111111|11111110|11100
+ {0xffff6000ul, 22, 154}, // 11111111|11111111|011000
+ {0xffffca00ul, 23, 155}, // 11111111|11111111|1100101
+ {0xffff6400ul, 22, 156}, // 11111111|11111111|011001
+ {0xffffcc00ul, 23, 157}, // 11111111|11111111|1100110
+ {0xffffce00ul, 23, 158}, // 11111111|11111111|1100111
+ {0xffffef00ul, 24, 159}, // 11111111|11111111|11101111
+ {0xffff6800ul, 22, 160}, // 11111111|11111111|011010
+ {0xfffee800ul, 21, 161}, // 11111111|11111110|11101
+ {0xfffe9000ul, 20, 162}, // 11111111|11111110|1001
+ {0xffff6c00ul, 22, 163}, // 11111111|11111111|011011
+ {0xffff7000ul, 22, 164}, // 11111111|11111111|011100
+ {0xffffd000ul, 23, 165}, // 11111111|11111111|1101000
+ {0xffffd200ul, 23, 166}, // 11111111|11111111|1101001
+ {0xfffef000ul, 21, 167}, // 11111111|11111110|11110
+ {0xffffd400ul, 23, 168}, // 11111111|11111111|1101010
+ {0xffff7400ul, 22, 169}, // 11111111|11111111|011101
+ {0xffff7800ul, 22, 170}, // 11111111|11111111|011110
+ {0xfffff000ul, 24, 171}, // 11111111|11111111|11110000
+ {0xfffef800ul, 21, 172}, // 11111111|11111110|11111
+ {0xffff7c00ul, 22, 173}, // 11111111|11111111|011111
+ {0xffffd600ul, 23, 174}, // 11111111|11111111|1101011
+ {0xffffd800ul, 23, 175}, // 11111111|11111111|1101100
+ {0xffff0000ul, 21, 176}, // 11111111|11111111|00000
+ {0xffff0800ul, 21, 177}, // 11111111|11111111|00001
+ {0xffff8000ul, 22, 178}, // 11111111|11111111|100000
+ {0xffff1000ul, 21, 179}, // 11111111|11111111|00010
+ {0xffffda00ul, 23, 180}, // 11111111|11111111|1101101
+ {0xffff8400ul, 22, 181}, // 11111111|11111111|100001
+ {0xffffdc00ul, 23, 182}, // 11111111|11111111|1101110
+ {0xffffde00ul, 23, 183}, // 11111111|11111111|1101111
+ {0xfffea000ul, 20, 184}, // 11111111|11111110|1010
+ {0xffff8800ul, 22, 185}, // 11111111|11111111|100010
+ {0xffff8c00ul, 22, 186}, // 11111111|11111111|100011
+ {0xffff9000ul, 22, 187}, // 11111111|11111111|100100
+ {0xffffe000ul, 23, 188}, // 11111111|11111111|1110000
+ {0xffff9400ul, 22, 189}, // 11111111|11111111|100101
+ {0xffff9800ul, 22, 190}, // 11111111|11111111|100110
+ {0xffffe200ul, 23, 191}, // 11111111|11111111|1110001
+ {0xfffff800ul, 26, 192}, // 11111111|11111111|11111000|00
+ {0xfffff840ul, 26, 193}, // 11111111|11111111|11111000|01
+ {0xfffeb000ul, 20, 194}, // 11111111|11111110|1011
+ {0xfffe2000ul, 19, 195}, // 11111111|11111110|001
+ {0xffff9c00ul, 22, 196}, // 11111111|11111111|100111
+ {0xffffe400ul, 23, 197}, // 11111111|11111111|1110010
+ {0xffffa000ul, 22, 198}, // 11111111|11111111|101000
+ {0xfffff600ul, 25, 199}, // 11111111|11111111|11110110|0
+ {0xfffff880ul, 26, 200}, // 11111111|11111111|11111000|10
+ {0xfffff8c0ul, 26, 201}, // 11111111|11111111|11111000|11
+ {0xfffff900ul, 26, 202}, // 11111111|11111111|11111001|00
+ {0xfffffbc0ul, 27, 203}, // 11111111|11111111|11111011|110
+ {0xfffffbe0ul, 27, 204}, // 11111111|11111111|11111011|111
+ {0xfffff940ul, 26, 205}, // 11111111|11111111|11111001|01
+ {0xfffff100ul, 24, 206}, // 11111111|11111111|11110001
+ {0xfffff680ul, 25, 207}, // 11111111|11111111|11110110|1
+ {0xfffe4000ul, 19, 208}, // 11111111|11111110|010
+ {0xffff1800ul, 21, 209}, // 11111111|11111111|00011
+ {0xfffff980ul, 26, 210}, // 11111111|11111111|11111001|10
+ {0xfffffc00ul, 27, 211}, // 11111111|11111111|11111100|000
+ {0xfffffc20ul, 27, 212}, // 11111111|11111111|11111100|001
+ {0xfffff9c0ul, 26, 213}, // 11111111|11111111|11111001|11
+ {0xfffffc40ul, 27, 214}, // 11111111|11111111|11111100|010
+ {0xfffff200ul, 24, 215}, // 11111111|11111111|11110010
+ {0xffff2000ul, 21, 216}, // 11111111|11111111|00100
+ {0xffff2800ul, 21, 217}, // 11111111|11111111|00101
+ {0xfffffa00ul, 26, 218}, // 11111111|11111111|11111010|00
+ {0xfffffa40ul, 26, 219}, // 11111111|11111111|11111010|01
+ {0xffffffd0ul, 28, 220}, // 11111111|11111111|11111111|1101
+ {0xfffffc60ul, 27, 221}, // 11111111|11111111|11111100|011
+ {0xfffffc80ul, 27, 222}, // 11111111|11111111|11111100|100
+ {0xfffffca0ul, 27, 223}, // 11111111|11111111|11111100|101
+ {0xfffec000ul, 20, 224}, // 11111111|11111110|1100
+ {0xfffff300ul, 24, 225}, // 11111111|11111111|11110011
+ {0xfffed000ul, 20, 226}, // 11111111|11111110|1101
+ {0xffff3000ul, 21, 227}, // 11111111|11111111|00110
+ {0xffffa400ul, 22, 228}, // 11111111|11111111|101001
+ {0xffff3800ul, 21, 229}, // 11111111|11111111|00111
+ {0xffff4000ul, 21, 230}, // 11111111|11111111|01000
+ {0xffffe600ul, 23, 231}, // 11111111|11111111|1110011
+ {0xffffa800ul, 22, 232}, // 11111111|11111111|101010
+ {0xffffac00ul, 22, 233}, // 11111111|11111111|101011
+ {0xfffff700ul, 25, 234}, // 11111111|11111111|11110111|0
+ {0xfffff780ul, 25, 235}, // 11111111|11111111|11110111|1
+ {0xfffff400ul, 24, 236}, // 11111111|11111111|11110100
+ {0xfffff500ul, 24, 237}, // 11111111|11111111|11110101
+ {0xfffffa80ul, 26, 238}, // 11111111|11111111|11111010|10
+ {0xffffe800ul, 23, 239}, // 11111111|11111111|1110100
+ {0xfffffac0ul, 26, 240}, // 11111111|11111111|11111010|11
+ {0xfffffcc0ul, 27, 241}, // 11111111|11111111|11111100|110
+ {0xfffffb00ul, 26, 242}, // 11111111|11111111|11111011|00
+ {0xfffffb40ul, 26, 243}, // 11111111|11111111|11111011|01
+ {0xfffffce0ul, 27, 244}, // 11111111|11111111|11111100|111
+ {0xfffffd00ul, 27, 245}, // 11111111|11111111|11111101|000
+ {0xfffffd20ul, 27, 246}, // 11111111|11111111|11111101|001
+ {0xfffffd40ul, 27, 247}, // 11111111|11111111|11111101|010
+ {0xfffffd60ul, 27, 248}, // 11111111|11111111|11111101|011
+ {0xffffffe0ul, 28, 249}, // 11111111|11111111|11111111|1110
+ {0xfffffd80ul, 27, 250}, // 11111111|11111111|11111101|100
+ {0xfffffda0ul, 27, 251}, // 11111111|11111111|11111101|101
+ {0xfffffdc0ul, 27, 252}, // 11111111|11111111|11111101|110
+ {0xfffffde0ul, 27, 253}, // 11111111|11111111|11111101|111
+ {0xfffffe00ul, 27, 254}, // 11111111|11111111|11111110|000
+ {0xfffffb80ul, 26, 255}, // 11111111|11111111|11111011|10
+ {0xfffffffcul, 30, 256}, // EOS 11111111|11111111|11111111|111111
+ };
+ return *kHpackHuffmanCode;
+}
+
+// The "constructor" for a HpackStaticEntry that computes the lengths at
+// compile time.
+#define STATIC_ENTRY(name, value) \
+ { name, SPDY_ARRAYSIZE(name) - 1, value, SPDY_ARRAYSIZE(value) - 1 }
+
+const std::vector<HpackStaticEntry>& HpackStaticTableVector() {
+ static const auto* kHpackStaticTable = new std::vector<HpackStaticEntry>{
+ STATIC_ENTRY(":authority", ""), // 1
+ STATIC_ENTRY(":method", "GET"), // 2
+ STATIC_ENTRY(":method", "POST"), // 3
+ STATIC_ENTRY(":path", "/"), // 4
+ STATIC_ENTRY(":path", "/index.html"), // 5
+ STATIC_ENTRY(":scheme", "http"), // 6
+ STATIC_ENTRY(":scheme", "https"), // 7
+ STATIC_ENTRY(":status", "200"), // 8
+ STATIC_ENTRY(":status", "204"), // 9
+ STATIC_ENTRY(":status", "206"), // 10
+ STATIC_ENTRY(":status", "304"), // 11
+ STATIC_ENTRY(":status", "400"), // 12
+ STATIC_ENTRY(":status", "404"), // 13
+ STATIC_ENTRY(":status", "500"), // 14
+ STATIC_ENTRY("accept-charset", ""), // 15
+ STATIC_ENTRY("accept-encoding", "gzip, deflate"), // 16
+ STATIC_ENTRY("accept-language", ""), // 17
+ STATIC_ENTRY("accept-ranges", ""), // 18
+ STATIC_ENTRY("accept", ""), // 19
+ STATIC_ENTRY("access-control-allow-origin", ""), // 20
+ STATIC_ENTRY("age", ""), // 21
+ STATIC_ENTRY("allow", ""), // 22
+ STATIC_ENTRY("authorization", ""), // 23
+ STATIC_ENTRY("cache-control", ""), // 24
+ STATIC_ENTRY("content-disposition", ""), // 25
+ STATIC_ENTRY("content-encoding", ""), // 26
+ STATIC_ENTRY("content-language", ""), // 27
+ STATIC_ENTRY("content-length", ""), // 28
+ STATIC_ENTRY("content-location", ""), // 29
+ STATIC_ENTRY("content-range", ""), // 30
+ STATIC_ENTRY("content-type", ""), // 31
+ STATIC_ENTRY("cookie", ""), // 32
+ STATIC_ENTRY("date", ""), // 33
+ STATIC_ENTRY("etag", ""), // 34
+ STATIC_ENTRY("expect", ""), // 35
+ STATIC_ENTRY("expires", ""), // 36
+ STATIC_ENTRY("from", ""), // 37
+ STATIC_ENTRY("host", ""), // 38
+ STATIC_ENTRY("if-match", ""), // 39
+ STATIC_ENTRY("if-modified-since", ""), // 40
+ STATIC_ENTRY("if-none-match", ""), // 41
+ STATIC_ENTRY("if-range", ""), // 42
+ STATIC_ENTRY("if-unmodified-since", ""), // 43
+ STATIC_ENTRY("last-modified", ""), // 44
+ STATIC_ENTRY("link", ""), // 45
+ STATIC_ENTRY("location", ""), // 46
+ STATIC_ENTRY("max-forwards", ""), // 47
+ STATIC_ENTRY("proxy-authenticate", ""), // 48
+ STATIC_ENTRY("proxy-authorization", ""), // 49
+ STATIC_ENTRY("range", ""), // 50
+ STATIC_ENTRY("referer", ""), // 51
+ STATIC_ENTRY("refresh", ""), // 52
+ STATIC_ENTRY("retry-after", ""), // 53
+ STATIC_ENTRY("server", ""), // 54
+ STATIC_ENTRY("set-cookie", ""), // 55
+ STATIC_ENTRY("strict-transport-security", ""), // 56
+ STATIC_ENTRY("transfer-encoding", ""), // 57
+ STATIC_ENTRY("user-agent", ""), // 58
+ STATIC_ENTRY("vary", ""), // 59
+ STATIC_ENTRY("via", ""), // 60
+ STATIC_ENTRY("www-authenticate", ""), // 61
+ };
+ return *kHpackStaticTable;
+}
+
+#undef STATIC_ENTRY
+
+const HpackHuffmanTable& ObtainHpackHuffmanTable() {
+ static const HpackHuffmanTable* const shared_huffman_table = []() {
+ auto* table = new HpackHuffmanTable();
+ CHECK(table->Initialize(HpackHuffmanCodeVector().data(),
+ HpackHuffmanCodeVector().size()));
+ CHECK(table->IsInitialized());
+ return table;
+ }();
+ return *shared_huffman_table;
+}
+
+const HpackStaticTable& ObtainHpackStaticTable() {
+ static const HpackStaticTable* const shared_static_table = []() {
+ auto* table = new HpackStaticTable();
+ table->Initialize(HpackStaticTableVector().data(),
+ HpackStaticTableVector().size());
+ CHECK(table->IsInitialized());
+ return table;
+ }();
+ return *shared_static_table;
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_constants.h b/spdy/core/hpack/hpack_constants.h
new file mode 100644
index 0000000..3f4026b
--- /dev/null
+++ b/spdy/core/hpack/hpack_constants.h
@@ -0,0 +1,95 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+
+// All section references below are to
+// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08
+
+namespace spdy {
+
+// An HpackPrefix signifies |bits| stored in the top |bit_size| bits
+// of an octet.
+struct HpackPrefix {
+ uint8_t bits;
+ size_t bit_size;
+};
+
+// Represents a symbol and its Huffman code (stored in most-significant bits).
+struct HpackHuffmanSymbol {
+ uint32_t code;
+ uint8_t length;
+ uint16_t id;
+};
+
+// An entry in the static table. Must be a POD in order to avoid static
+// initializers, i.e. no user-defined constructors or destructors.
+struct HpackStaticEntry {
+ const char* const name;
+ const size_t name_len;
+ const char* const value;
+ const size_t value_len;
+};
+
+class HpackHuffmanTable;
+class HpackStaticTable;
+
+// Defined in RFC 7540, 6.5.2.
+const uint32_t kDefaultHeaderTableSizeSetting = 4096;
+
+// RFC 7541, 5.2: Flag for a string literal that is stored unmodified (i.e.,
+// without Huffman encoding).
+const HpackPrefix kStringLiteralIdentityEncoded = {0x0, 1};
+
+// RFC 7541, 5.2: Flag for a Huffman-coded string literal.
+const HpackPrefix kStringLiteralHuffmanEncoded = {0x1, 1};
+
+// RFC 7541, 6.1: Opcode for an indexed header field.
+const HpackPrefix kIndexedOpcode = {0b1, 1};
+
+// RFC 7541, 6.2.1: Opcode for a literal header field with incremental indexing.
+const HpackPrefix kLiteralIncrementalIndexOpcode = {0b01, 2};
+
+// RFC 7541, 6.2.2: Opcode for a literal header field without indexing.
+const HpackPrefix kLiteralNoIndexOpcode = {0b0000, 4};
+
+// RFC 7541, 6.2.3: Opcode for a literal header field which is never indexed.
+// Currently unused.
+// const HpackPrefix kLiteralNeverIndexOpcode = {0b0001, 4};
+
+// RFC 7541, 6.3: Opcode for maximum header table size update. Begins a
+// varint-encoded table size with a 5-bit prefix.
+const HpackPrefix kHeaderTableSizeUpdateOpcode = {0b001, 3};
+
+// Symbol code table from RFC 7541, "Appendix C. Huffman Code".
+SPDY_EXPORT_PRIVATE const std::vector<HpackHuffmanSymbol>&
+HpackHuffmanCodeVector();
+
+// Static table from RFC 7541, "Appendix B. Static Table Definition".
+SPDY_EXPORT_PRIVATE const std::vector<HpackStaticEntry>&
+HpackStaticTableVector();
+
+// Returns a HpackHuffmanTable instance initialized with |kHpackHuffmanCode|.
+// The instance is read-only, has static lifetime, and is safe to share amoung
+// threads. This function is thread-safe.
+SPDY_EXPORT_PRIVATE const HpackHuffmanTable& ObtainHpackHuffmanTable();
+
+// Returns a HpackStaticTable instance initialized with |kHpackStaticTable|.
+// The instance is read-only, has static lifetime, and is safe to share amoung
+// threads. This function is thread-safe.
+SPDY_EXPORT_PRIVATE const HpackStaticTable& ObtainHpackStaticTable();
+
+// Pseudo-headers start with a colon. (HTTP2 8.1.2.1., HPACK 3.1.)
+const char kPseudoHeaderPrefix = ':';
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_CONSTANTS_H_
diff --git a/spdy/core/hpack/hpack_decoder_adapter.cc b/spdy/core/hpack/hpack_decoder_adapter.cc
new file mode 100644
index 0000000..309af39
--- /dev/null
+++ b/spdy/core/hpack/hpack_decoder_adapter.cc
@@ -0,0 +1,201 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h"
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/http2/decoder/decode_buffer.h"
+#include "net/third_party/quiche/src/http2/decoder/decode_status.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+
+using ::http2::DecodeBuffer;
+using ::http2::HpackEntryType;
+using ::http2::HpackString;
+
+namespace spdy {
+namespace {
+const size_t kMaxDecodeBufferSizeBytes = 32 * 1024; // 32 KB
+} // namespace
+
+HpackDecoderAdapter::HpackDecoderAdapter()
+ : hpack_decoder_(&listener_adapter_, kMaxDecodeBufferSizeBytes),
+ max_decode_buffer_size_bytes_(kMaxDecodeBufferSizeBytes),
+ header_block_started_(false) {}
+
+HpackDecoderAdapter::~HpackDecoderAdapter() = default;
+
+void HpackDecoderAdapter::ApplyHeaderTableSizeSetting(size_t size_setting) {
+ DVLOG(2) << "HpackDecoderAdapter::ApplyHeaderTableSizeSetting";
+ hpack_decoder_.ApplyHeaderTableSizeSetting(size_setting);
+}
+
+void HpackDecoderAdapter::HandleControlFrameHeadersStart(
+ SpdyHeadersHandlerInterface* handler) {
+ DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersStart";
+ DCHECK(!header_block_started_);
+ listener_adapter_.set_handler(handler);
+}
+
+bool HpackDecoderAdapter::HandleControlFrameHeadersData(
+ const char* headers_data,
+ size_t headers_data_length) {
+ DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersData: len="
+ << headers_data_length;
+ if (!header_block_started_) {
+ // Initialize the decoding process here rather than in
+ // HandleControlFrameHeadersStart because that method is not always called.
+ header_block_started_ = true;
+ if (!hpack_decoder_.StartDecodingBlock()) {
+ header_block_started_ = false;
+ return false;
+ }
+ }
+
+ // Sometimes we get a call with headers_data==nullptr and
+ // headers_data_length==0, in which case we need to avoid creating
+ // a DecodeBuffer, which would otherwise complain.
+ if (headers_data_length > 0) {
+ DCHECK_NE(headers_data, nullptr);
+ if (headers_data_length > max_decode_buffer_size_bytes_) {
+ DVLOG(1) << "max_decode_buffer_size_bytes_ < headers_data_length: "
+ << max_decode_buffer_size_bytes_ << " < " << headers_data_length;
+ return false;
+ }
+ listener_adapter_.AddToTotalHpackBytes(headers_data_length);
+ http2::DecodeBuffer db(headers_data, headers_data_length);
+ bool ok = hpack_decoder_.DecodeFragment(&db);
+ DCHECK(!ok || db.Empty()) << "Remaining=" << db.Remaining();
+ return ok;
+ }
+ return true;
+}
+
+bool HpackDecoderAdapter::HandleControlFrameHeadersComplete(
+ size_t* compressed_len) {
+ DVLOG(2) << "HpackDecoderAdapter::HandleControlFrameHeadersComplete";
+ if (compressed_len != nullptr) {
+ *compressed_len = listener_adapter_.total_hpack_bytes();
+ }
+ if (!hpack_decoder_.EndDecodingBlock()) {
+ DVLOG(3) << "EndDecodingBlock returned false";
+ return false;
+ }
+ header_block_started_ = false;
+ return true;
+}
+
+const SpdyHeaderBlock& HpackDecoderAdapter::decoded_block() const {
+ return listener_adapter_.decoded_block();
+}
+
+void HpackDecoderAdapter::SetHeaderTableDebugVisitor(
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) {
+ DVLOG(2) << "HpackDecoderAdapter::SetHeaderTableDebugVisitor";
+ if (visitor != nullptr) {
+ listener_adapter_.SetHeaderTableDebugVisitor(std::move(visitor));
+ hpack_decoder_.set_tables_debug_listener(&listener_adapter_);
+ } else {
+ hpack_decoder_.set_tables_debug_listener(nullptr);
+ listener_adapter_.SetHeaderTableDebugVisitor(nullptr);
+ }
+}
+
+void HpackDecoderAdapter::set_max_decode_buffer_size_bytes(
+ size_t max_decode_buffer_size_bytes) {
+ DVLOG(2) << "HpackDecoderAdapter::set_max_decode_buffer_size_bytes";
+ max_decode_buffer_size_bytes_ = max_decode_buffer_size_bytes;
+ hpack_decoder_.set_max_string_size_bytes(max_decode_buffer_size_bytes);
+}
+
+size_t HpackDecoderAdapter::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(hpack_decoder_);
+}
+
+HpackDecoderAdapter::ListenerAdapter::ListenerAdapter() : handler_(nullptr) {}
+HpackDecoderAdapter::ListenerAdapter::~ListenerAdapter() = default;
+
+void HpackDecoderAdapter::ListenerAdapter::set_handler(
+ SpdyHeadersHandlerInterface* handler) {
+ handler_ = handler;
+}
+
+void HpackDecoderAdapter::ListenerAdapter::SetHeaderTableDebugVisitor(
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) {
+ visitor_ = std::move(visitor);
+}
+
+void HpackDecoderAdapter::ListenerAdapter::OnHeaderListStart() {
+ DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeaderListStart";
+ total_hpack_bytes_ = 0;
+ total_uncompressed_bytes_ = 0;
+ decoded_block_.clear();
+ if (handler_ != nullptr) {
+ handler_->OnHeaderBlockStart();
+ }
+}
+
+void HpackDecoderAdapter::ListenerAdapter::OnHeader(HpackEntryType entry_type,
+ const HpackString& name,
+ const HpackString& value) {
+ DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeader:\n name: " << name
+ << "\n value: " << value;
+ total_uncompressed_bytes_ += name.size() + value.size();
+ if (handler_ == nullptr) {
+ DVLOG(3) << "Adding to decoded_block";
+ decoded_block_.AppendValueOrAddHeader(name.ToStringPiece(),
+ value.ToStringPiece());
+ } else {
+ DVLOG(3) << "Passing to handler";
+ handler_->OnHeader(name.ToStringPiece(), value.ToStringPiece());
+ }
+}
+
+void HpackDecoderAdapter::ListenerAdapter::OnHeaderListEnd() {
+ DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnHeaderListEnd";
+ // We don't clear the SpdyHeaderBlock here to allow access to it until the
+ // next HPACK block is decoded.
+ if (handler_ != nullptr) {
+ handler_->OnHeaderBlockEnd(total_uncompressed_bytes_, total_hpack_bytes_);
+ handler_ = nullptr;
+ }
+}
+
+void HpackDecoderAdapter::ListenerAdapter::OnHeaderErrorDetected(
+ SpdyStringPiece error_message) {
+ VLOG(1) << error_message;
+}
+
+int64_t HpackDecoderAdapter::ListenerAdapter::OnEntryInserted(
+ const http2::HpackStringPair& sp,
+ size_t insert_count) {
+ DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnEntryInserted: " << sp
+ << ", insert_count=" << insert_count;
+ if (visitor_ == nullptr) {
+ return 0;
+ }
+ HpackEntry entry(sp.name.ToStringPiece(), sp.value.ToStringPiece(),
+ /*is_static*/ false, insert_count);
+ int64_t time_added = visitor_->OnNewEntry(entry);
+ DVLOG(2)
+ << "HpackDecoderAdapter::ListenerAdapter::OnEntryInserted: time_added="
+ << time_added;
+ return time_added;
+}
+
+void HpackDecoderAdapter::ListenerAdapter::OnUseEntry(
+ const http2::HpackStringPair& sp,
+ size_t insert_count,
+ int64_t time_added) {
+ DVLOG(2) << "HpackDecoderAdapter::ListenerAdapter::OnUseEntry: " << sp
+ << ", insert_count=" << insert_count
+ << ", time_added=" << time_added;
+ if (visitor_ != nullptr) {
+ HpackEntry entry(sp.name.ToStringPiece(), sp.value.ToStringPiece(),
+ /*is_static*/ false, insert_count);
+ entry.set_time_added(time_added);
+ visitor_->OnUseEntry(entry);
+ }
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_decoder_adapter.h b/spdy/core/hpack/hpack_decoder_adapter.h
new file mode 100644
index 0000000..b497fe7
--- /dev/null
+++ b/spdy/core/hpack/hpack_decoder_adapter.h
@@ -0,0 +1,159 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_
+
+// HpackDecoderAdapter uses http2::HpackDecoder to decode HPACK blocks into
+// HTTP/2 header lists as outlined in http://tools.ietf.org/html/rfc7541.
+
+#include <stddef.h>
+
+#include <cstdint>
+#include <memory>
+
+#include "base/macros.h"
+#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder.h"
+#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_listener.h"
+#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_tables.h"
+#include "net/third_party/quiche/src/http2/hpack/hpack_string.h"
+#include "net/third_party/quiche/src/http2/hpack/http2_hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_header_block.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_headers_handler_interface.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+namespace spdy {
+namespace test {
+class HpackDecoderAdapterPeer;
+} // namespace test
+
+class SPDY_EXPORT_PRIVATE HpackDecoderAdapter {
+ public:
+ friend test::HpackDecoderAdapterPeer;
+ HpackDecoderAdapter();
+ HpackDecoderAdapter(const HpackDecoderAdapter&) = delete;
+ HpackDecoderAdapter& operator=(const HpackDecoderAdapter&) = delete;
+ ~HpackDecoderAdapter();
+
+ // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE.
+ void ApplyHeaderTableSizeSetting(size_t size_setting);
+
+ // If a SpdyHeadersHandlerInterface is provided, the decoder will emit
+ // headers to it rather than accumulating them in a SpdyHeaderBlock.
+ // Does not take ownership of the handler, but does use the pointer until
+ // the current HPACK block is completely decoded.
+ void HandleControlFrameHeadersStart(SpdyHeadersHandlerInterface* handler);
+
+ // Called as HPACK block fragments arrive. Returns false if an error occurred
+ // while decoding the block. Does not take ownership of headers_data.
+ bool HandleControlFrameHeadersData(const char* headers_data,
+ size_t headers_data_length);
+
+ // Called after a HPACK block has been completely delivered via
+ // HandleControlFrameHeadersData(). Returns false if an error occurred.
+ // |compressed_len| if non-null will be set to the size of the encoded
+ // buffered block that was accumulated in HandleControlFrameHeadersData(),
+ // to support subsequent calculation of compression percentage.
+ // Discards the handler supplied at the start of decoding the block.
+ // TODO(jamessynge): Determine if compressed_len is needed; it is used to
+ // produce UUMA stat Net.SpdyHpackDecompressionPercentage, but only for
+ // deprecated SPDY3.
+ bool HandleControlFrameHeadersComplete(size_t* compressed_len);
+
+ // Accessor for the most recently decoded headers block. Valid until the next
+ // call to HandleControlFrameHeadersData().
+ // TODO(birenroy): Remove this method when all users of HpackDecoder specify
+ // a SpdyHeadersHandlerInterface.
+ const SpdyHeaderBlock& decoded_block() const;
+
+ void SetHeaderTableDebugVisitor(
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor);
+
+ // Set how much encoded data this decoder is willing to buffer.
+ // TODO(jamessynge): Resolve definition of this value, as it is currently
+ // too tied to a single implementation. We probably want to limit one or more
+ // of these: individual name or value strings, header entries, the entire
+ // header list, or the HPACK block; we probably shouldn't care about the size
+ // of individual transport buffers.
+ void set_max_decode_buffer_size_bytes(size_t max_decode_buffer_size_bytes);
+
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ class SPDY_EXPORT_PRIVATE ListenerAdapter
+ : public http2::HpackDecoderListener,
+ public http2::HpackDecoderTablesDebugListener {
+ public:
+ ListenerAdapter();
+ ~ListenerAdapter() override;
+
+ // If a SpdyHeadersHandlerInterface is provided, the decoder will emit
+ // headers to it rather than accumulating them in a SpdyHeaderBlock.
+ // Does not take ownership of the handler, but does use the pointer until
+ // the current HPACK block is completely decoded.
+ void set_handler(SpdyHeadersHandlerInterface* handler);
+ const SpdyHeaderBlock& decoded_block() const { return decoded_block_; }
+
+ void SetHeaderTableDebugVisitor(
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor);
+
+ // Override the HpackDecoderListener methods:
+ void OnHeaderListStart() override;
+ void OnHeader(http2::HpackEntryType entry_type,
+ const http2::HpackString& name,
+ const http2::HpackString& value) override;
+ void OnHeaderListEnd() override;
+ void OnHeaderErrorDetected(SpdyStringPiece error_message) override;
+
+ // Override the HpackDecoderTablesDebugListener methods:
+ int64_t OnEntryInserted(const http2::HpackStringPair& entry,
+ size_t insert_count) override;
+ void OnUseEntry(const http2::HpackStringPair& entry,
+ size_t insert_count,
+ int64_t insert_time) override;
+
+ void AddToTotalHpackBytes(size_t delta) { total_hpack_bytes_ += delta; }
+ size_t total_hpack_bytes() const { return total_hpack_bytes_; }
+
+ private:
+ // If the caller doesn't provide a handler, the header list is stored in
+ // this SpdyHeaderBlock.
+ SpdyHeaderBlock decoded_block_;
+
+ // If non-NULL, handles decoded headers. Not owned.
+ SpdyHeadersHandlerInterface* handler_;
+
+ // Total bytes that have been received as input (i.e. HPACK encoded)
+ // in the current HPACK block.
+ size_t total_hpack_bytes_;
+
+ // Total bytes of the name and value strings in the current HPACK block.
+ size_t total_uncompressed_bytes_;
+
+ // visitor_ is used by a QUIC experiment regarding HPACK; remove
+ // when the experiment is done.
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor_;
+ };
+
+ // Converts calls to HpackDecoderListener into calls to
+ // SpdyHeadersHandlerInterface.
+ ListenerAdapter listener_adapter_;
+
+ // The actual decoder.
+ http2::HpackDecoder hpack_decoder_;
+
+ // How much encoded data this decoder is willing to buffer.
+ size_t max_decode_buffer_size_bytes_;
+
+ // Flag to keep track of having seen the header block start. Needed at the
+ // moment because HandleControlFrameHeadersStart won't be called if a handler
+ // is not being provided by the caller.
+ bool header_block_started_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_DECODER_ADAPTER_H_
diff --git a/spdy/core/hpack/hpack_decoder_adapter_test.cc b/spdy/core/hpack/hpack_decoder_adapter_test.cc
new file mode 100644
index 0000000..765c2ea
--- /dev/null
+++ b/spdy/core/hpack/hpack_decoder_adapter_test.cc
@@ -0,0 +1,1097 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h"
+
+// Tests of HpackDecoderAdapter.
+
+#include <stdint.h>
+
+#include <tuple>
+#include <utility>
+#include <vector>
+
+#include "base/logging.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_state.h"
+#include "net/third_party/quiche/src/http2/hpack/decoder/hpack_decoder_tables.h"
+#include "net/third_party/quiche/src/http2/hpack/tools/hpack_block_builder.h"
+#include "net/third_party/quiche/src/http2/test_tools/http2_random.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_test_utils.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+
+using ::http2::HpackEntryType;
+using ::http2::HpackString;
+using ::http2::HpackStringPair;
+using ::http2::test::HpackBlockBuilder;
+using ::http2::test::HpackDecoderPeer;
+using ::testing::ElementsAre;
+using ::testing::Pair;
+
+namespace http2 {
+namespace test {
+
+class HpackDecoderStatePeer {
+ public:
+ static HpackDecoderTables* GetDecoderTables(HpackDecoderState* state) {
+ return &state->decoder_tables_;
+ }
+};
+
+class HpackDecoderPeer {
+ public:
+ static HpackDecoderState* GetDecoderState(HpackDecoder* decoder) {
+ return &decoder->decoder_state_;
+ }
+ static HpackDecoderTables* GetDecoderTables(HpackDecoder* decoder) {
+ return HpackDecoderStatePeer::GetDecoderTables(GetDecoderState(decoder));
+ }
+};
+
+} // namespace test
+} // namespace http2
+
+namespace spdy {
+namespace test {
+
+class HpackDecoderAdapterPeer {
+ public:
+ explicit HpackDecoderAdapterPeer(HpackDecoderAdapter* decoder)
+ : decoder_(decoder) {}
+
+ void HandleHeaderRepresentation(SpdyStringPiece name, SpdyStringPiece value) {
+ decoder_->listener_adapter_.OnHeader(HpackEntryType::kIndexedLiteralHeader,
+ HpackString(name), HpackString(value));
+ }
+
+ http2::HpackDecoderTables* GetDecoderTables() {
+ return HpackDecoderPeer::GetDecoderTables(&decoder_->hpack_decoder_);
+ }
+
+ const HpackStringPair* GetTableEntry(uint32_t index) {
+ return GetDecoderTables()->Lookup(index);
+ }
+
+ size_t current_header_table_size() {
+ return GetDecoderTables()->current_header_table_size();
+ }
+
+ size_t header_table_size_limit() {
+ return GetDecoderTables()->header_table_size_limit();
+ }
+
+ void set_header_table_size_limit(size_t size) {
+ return GetDecoderTables()->DynamicTableSizeUpdate(size);
+ }
+
+ private:
+ HpackDecoderAdapter* decoder_;
+};
+
+class HpackEncoderPeer {
+ public:
+ static void CookieToCrumbs(const HpackEncoder::Representation& cookie,
+ HpackEncoder::Representations* crumbs_out) {
+ HpackEncoder::CookieToCrumbs(cookie, crumbs_out);
+ }
+};
+
+namespace {
+
+const bool kNoCheckDecodedSize = false;
+const char* kCookieKey = "cookie";
+
+// Is HandleControlFrameHeadersStart to be called, and with what value?
+enum StartChoice { START_WITH_HANDLER, START_WITHOUT_HANDLER, NO_START };
+
+class HpackDecoderAdapterTest
+ : public ::testing::TestWithParam<std::tuple<StartChoice, bool>> {
+ protected:
+ HpackDecoderAdapterTest() : decoder_(), decoder_peer_(&decoder_) {}
+
+ void SetUp() override {
+ std::tie(start_choice_, randomly_split_input_buffer_) = GetParam();
+ }
+
+ void HandleControlFrameHeadersStart() {
+ bytes_passed_in_ = 0;
+ switch (start_choice_) {
+ case START_WITH_HANDLER:
+ decoder_.HandleControlFrameHeadersStart(&handler_);
+ break;
+ case START_WITHOUT_HANDLER:
+ decoder_.HandleControlFrameHeadersStart(nullptr);
+ break;
+ case NO_START:
+ break;
+ }
+ }
+
+ bool HandleControlFrameHeadersData(SpdyStringPiece str) {
+ VLOG(3) << "HandleControlFrameHeadersData:\n" << SpdyHexDump(str);
+ bytes_passed_in_ += str.size();
+ return decoder_.HandleControlFrameHeadersData(str.data(), str.size());
+ }
+
+ bool HandleControlFrameHeadersComplete(size_t* size) {
+ bool rc = decoder_.HandleControlFrameHeadersComplete(size);
+ if (size != nullptr) {
+ EXPECT_EQ(*size, bytes_passed_in_);
+ }
+ return rc;
+ }
+
+ bool DecodeHeaderBlock(SpdyStringPiece str, bool check_decoded_size = true) {
+ // Don't call this again if HandleControlFrameHeadersData failed previously.
+ EXPECT_FALSE(decode_has_failed_);
+ HandleControlFrameHeadersStart();
+ if (randomly_split_input_buffer_) {
+ do {
+ // Decode some fragment of the remaining bytes.
+ size_t bytes = str.size();
+ if (!str.empty()) {
+ bytes = random_.Uniform(str.size()) + 1;
+ }
+ EXPECT_LE(bytes, str.size());
+ if (!HandleControlFrameHeadersData(str.substr(0, bytes))) {
+ decode_has_failed_ = true;
+ return false;
+ }
+ str.remove_prefix(bytes);
+ } while (!str.empty());
+ } else if (!HandleControlFrameHeadersData(str)) {
+ decode_has_failed_ = true;
+ return false;
+ }
+ // Want to get out the number of compressed bytes that were decoded,
+ // so pass in a pointer if no handler.
+ size_t total_hpack_bytes = 0;
+ if (start_choice_ == START_WITH_HANDLER) {
+ if (!HandleControlFrameHeadersComplete(nullptr)) {
+ decode_has_failed_ = true;
+ return false;
+ }
+ total_hpack_bytes = handler_.compressed_header_bytes_parsed();
+ } else {
+ if (!HandleControlFrameHeadersComplete(&total_hpack_bytes)) {
+ decode_has_failed_ = true;
+ return false;
+ }
+ }
+ EXPECT_EQ(total_hpack_bytes, bytes_passed_in_);
+ if (check_decoded_size && start_choice_ == START_WITH_HANDLER) {
+ EXPECT_EQ(handler_.header_bytes_parsed(), SizeOfHeaders(decoded_block()));
+ }
+ return true;
+ }
+
+ bool EncodeAndDecodeDynamicTableSizeUpdates(size_t first, size_t second) {
+ HpackBlockBuilder hbb;
+ hbb.AppendDynamicTableSizeUpdate(first);
+ if (second != first) {
+ hbb.AppendDynamicTableSizeUpdate(second);
+ }
+ return DecodeHeaderBlock(hbb.buffer());
+ }
+
+ const SpdyHeaderBlock& decoded_block() const {
+ if (start_choice_ == START_WITH_HANDLER) {
+ return handler_.decoded_block();
+ } else {
+ return decoder_.decoded_block();
+ }
+ }
+
+ static size_t SizeOfHeaders(const SpdyHeaderBlock& headers) {
+ size_t size = 0;
+ for (const auto& kv : headers) {
+ if (kv.first == kCookieKey) {
+ HpackEncoder::Representations crumbs;
+ HpackEncoderPeer::CookieToCrumbs(kv, &crumbs);
+ for (const auto& crumb : crumbs) {
+ size += crumb.first.size() + crumb.second.size();
+ }
+ } else {
+ size += kv.first.size() + kv.second.size();
+ }
+ }
+ return size;
+ }
+
+ const SpdyHeaderBlock& DecodeBlockExpectingSuccess(SpdyStringPiece str) {
+ EXPECT_TRUE(DecodeHeaderBlock(str));
+ return decoded_block();
+ }
+
+ void expectEntry(size_t index,
+ size_t size,
+ const SpdyString& name,
+ const SpdyString& value) {
+ const HpackStringPair* entry = decoder_peer_.GetTableEntry(index);
+ EXPECT_EQ(name, entry->name) << "index " << index;
+ EXPECT_EQ(value, entry->value);
+ EXPECT_EQ(size, entry->size());
+ }
+
+ SpdyHeaderBlock MakeHeaderBlock(
+ const std::vector<std::pair<SpdyString, SpdyString>>& headers) {
+ SpdyHeaderBlock result;
+ for (const auto& kv : headers) {
+ result.AppendValueOrAddHeader(kv.first, kv.second);
+ }
+ return result;
+ }
+
+ http2::test::Http2Random random_;
+ HpackDecoderAdapter decoder_;
+ test::HpackDecoderAdapterPeer decoder_peer_;
+ TestHeadersHandler handler_;
+ StartChoice start_choice_;
+ bool randomly_split_input_buffer_;
+ bool decode_has_failed_ = false;
+ size_t bytes_passed_in_;
+};
+
+INSTANTIATE_TEST_CASE_P(
+ NoHandler,
+ HpackDecoderAdapterTest,
+ ::testing::Combine(::testing::Values(START_WITHOUT_HANDLER, NO_START),
+ ::testing::Bool()));
+
+INSTANTIATE_TEST_CASE_P(
+ WithHandler,
+ HpackDecoderAdapterTest,
+ ::testing::Combine(::testing::Values(START_WITH_HANDLER),
+ ::testing::Bool()));
+
+TEST_P(HpackDecoderAdapterTest,
+ AddHeaderDataWithHandleControlFrameHeadersData) {
+ // The hpack decode buffer size is limited in size. This test verifies that
+ // adding encoded data under that limit is accepted, and data that exceeds the
+ // limit is rejected.
+ HandleControlFrameHeadersStart();
+ const size_t kMaxBufferSizeBytes = 50;
+ const SpdyString a_value = SpdyString(49, 'x');
+ decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes);
+ HpackBlockBuilder hbb;
+ hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader,
+ false, "a", false, a_value);
+ const SpdyString& s = hbb.buffer();
+ EXPECT_GT(s.size(), kMaxBufferSizeBytes);
+
+ // Any one in input buffer must not exceed kMaxBufferSizeBytes.
+ EXPECT_TRUE(HandleControlFrameHeadersData(s.substr(0, s.size() / 2)));
+ EXPECT_TRUE(HandleControlFrameHeadersData(s.substr(s.size() / 2)));
+
+ EXPECT_FALSE(HandleControlFrameHeadersData(s));
+ SpdyHeaderBlock expected_block = MakeHeaderBlock({{"a", a_value}});
+ EXPECT_EQ(expected_block, decoded_block());
+}
+
+TEST_P(HpackDecoderAdapterTest, NameTooLong) {
+ // Verify that a name longer than the allowed size generates an error.
+ const size_t kMaxBufferSizeBytes = 50;
+ const SpdyString name = SpdyString(2 * kMaxBufferSizeBytes, 'x');
+ const SpdyString value = "abc";
+
+ decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes);
+
+ HpackBlockBuilder hbb;
+ hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader,
+ false, name, false, value);
+
+ const size_t fragment_size = (3 * kMaxBufferSizeBytes) / 2;
+ const SpdyString fragment = hbb.buffer().substr(0, fragment_size);
+
+ HandleControlFrameHeadersStart();
+ EXPECT_FALSE(HandleControlFrameHeadersData(fragment));
+}
+
+TEST_P(HpackDecoderAdapterTest, HeaderTooLongToBuffer) {
+ // Verify that a header longer than the allowed size generates an error if
+ // it isn't all in one input buffer.
+ const SpdyString name = "some-key";
+ const SpdyString value = "some-value";
+ const size_t kMaxBufferSizeBytes = name.size() + value.size() - 2;
+ decoder_.set_max_decode_buffer_size_bytes(kMaxBufferSizeBytes);
+
+ HpackBlockBuilder hbb;
+ hbb.AppendLiteralNameAndValue(HpackEntryType::kNeverIndexedLiteralHeader,
+ false, name, false, value);
+ const size_t fragment_size = hbb.size() - 1;
+ const SpdyString fragment = hbb.buffer().substr(0, fragment_size);
+
+ HandleControlFrameHeadersStart();
+ EXPECT_FALSE(HandleControlFrameHeadersData(fragment));
+}
+
+// Decode with incomplete data in buffer.
+TEST_P(HpackDecoderAdapterTest, DecodeWithIncompleteData) {
+ HandleControlFrameHeadersStart();
+
+ // No need to wait for more data.
+ EXPECT_TRUE(HandleControlFrameHeadersData("\x82\x85\x82"));
+ std::vector<std::pair<SpdyString, SpdyString>> expected_headers = {
+ {":method", "GET"}, {":path", "/index.html"}, {":method", "GET"}};
+
+ SpdyHeaderBlock expected_block1 = MakeHeaderBlock(expected_headers);
+ EXPECT_EQ(expected_block1, decoded_block());
+
+ // Full and partial headers, won't add partial to the headers.
+ EXPECT_TRUE(
+ HandleControlFrameHeadersData("\x40\x03goo"
+ "\x03gar\xbe\x40\x04spam"));
+ expected_headers.push_back({"goo", "gar"});
+ expected_headers.push_back({"goo", "gar"});
+
+ SpdyHeaderBlock expected_block2 = MakeHeaderBlock(expected_headers);
+ EXPECT_EQ(expected_block2, decoded_block());
+
+ // Add the needed data.
+ EXPECT_TRUE(HandleControlFrameHeadersData("\x04gggs"));
+
+ size_t size = 0;
+ EXPECT_TRUE(HandleControlFrameHeadersComplete(&size));
+ EXPECT_EQ(24u, size);
+
+ expected_headers.push_back({"spam", "gggs"});
+
+ SpdyHeaderBlock expected_block3 = MakeHeaderBlock(expected_headers);
+ EXPECT_EQ(expected_block3, decoded_block());
+}
+
+TEST_P(HpackDecoderAdapterTest, HandleHeaderRepresentation) {
+ // Make sure the decoder is properly initialized.
+ HandleControlFrameHeadersStart();
+ HandleControlFrameHeadersData("");
+
+ // All cookie crumbs are joined.
+ decoder_peer_.HandleHeaderRepresentation("cookie", " part 1");
+ decoder_peer_.HandleHeaderRepresentation("cookie", "part 2 ");
+ decoder_peer_.HandleHeaderRepresentation("cookie", "part3");
+
+ // Already-delimited headers are passed through.
+ decoder_peer_.HandleHeaderRepresentation("passed-through",
+ SpdyString("foo\0baz", 7));
+
+ // Other headers are joined on \0. Case matters.
+ decoder_peer_.HandleHeaderRepresentation("joined", "not joined");
+ decoder_peer_.HandleHeaderRepresentation("joineD", "value 1");
+ decoder_peer_.HandleHeaderRepresentation("joineD", "value 2");
+
+ // Empty headers remain empty.
+ decoder_peer_.HandleHeaderRepresentation("empty", "");
+
+ // Joined empty headers work as expected.
+ decoder_peer_.HandleHeaderRepresentation("empty-joined", "");
+ decoder_peer_.HandleHeaderRepresentation("empty-joined", "foo");
+ decoder_peer_.HandleHeaderRepresentation("empty-joined", "");
+ decoder_peer_.HandleHeaderRepresentation("empty-joined", "");
+
+ // Non-contiguous cookie crumb.
+ decoder_peer_.HandleHeaderRepresentation("cookie", " fin!");
+
+ // Finish and emit all headers.
+ decoder_.HandleControlFrameHeadersComplete(nullptr);
+
+ // Resulting decoded headers are in the same order as the inputs.
+ EXPECT_THAT(
+ decoded_block(),
+ ElementsAre(Pair("cookie", " part 1; part 2 ; part3; fin!"),
+ Pair("passed-through", SpdyStringPiece("foo\0baz", 7)),
+ Pair("joined", "not joined"),
+ Pair("joineD", SpdyStringPiece("value 1\0value 2", 15)),
+ Pair("empty", ""),
+ Pair("empty-joined", SpdyStringPiece("\0foo\0\0", 6))));
+}
+
+// Decoding indexed static table field should work.
+TEST_P(HpackDecoderAdapterTest, IndexedHeaderStatic) {
+ // Reference static table entries #2 and #5.
+ const SpdyHeaderBlock& header_set1 = DecodeBlockExpectingSuccess("\x82\x85");
+ SpdyHeaderBlock expected_header_set1;
+ expected_header_set1[":method"] = "GET";
+ expected_header_set1[":path"] = "/index.html";
+ EXPECT_EQ(expected_header_set1, header_set1);
+
+ // Reference static table entry #2.
+ const SpdyHeaderBlock& header_set2 = DecodeBlockExpectingSuccess("\x82");
+ SpdyHeaderBlock expected_header_set2;
+ expected_header_set2[":method"] = "GET";
+ EXPECT_EQ(expected_header_set2, header_set2);
+}
+
+TEST_P(HpackDecoderAdapterTest, IndexedHeaderDynamic) {
+ // First header block: add an entry to header table.
+ const SpdyHeaderBlock& header_set1 = DecodeBlockExpectingSuccess(
+ "\x40\x03"
+ "foo"
+ "\x03"
+ "bar");
+ SpdyHeaderBlock expected_header_set1;
+ expected_header_set1["foo"] = "bar";
+ EXPECT_EQ(expected_header_set1, header_set1);
+
+ // Second header block: add another entry to header table.
+ const SpdyHeaderBlock& header_set2 = DecodeBlockExpectingSuccess(
+ "\xbe\x40\x04"
+ "spam"
+ "\x04"
+ "eggs");
+ SpdyHeaderBlock expected_header_set2;
+ expected_header_set2["foo"] = "bar";
+ expected_header_set2["spam"] = "eggs";
+ EXPECT_EQ(expected_header_set2, header_set2);
+
+ // Third header block: refer to most recently added entry.
+ const SpdyHeaderBlock& header_set3 = DecodeBlockExpectingSuccess("\xbe");
+ SpdyHeaderBlock expected_header_set3;
+ expected_header_set3["spam"] = "eggs";
+ EXPECT_EQ(expected_header_set3, header_set3);
+}
+
+// Test a too-large indexed header.
+TEST_P(HpackDecoderAdapterTest, InvalidIndexedHeader) {
+ // High-bit set, and a prefix of one more than the number of static entries.
+ EXPECT_FALSE(DecodeHeaderBlock("\xbe"));
+}
+
+TEST_P(HpackDecoderAdapterTest, ContextUpdateMaximumSize) {
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting,
+ decoder_peer_.header_table_size_limit());
+ SpdyString input;
+ {
+ // Maximum-size update with size 126. Succeeds.
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(126);
+
+ output_stream.TakeString(&input);
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(126u, decoder_peer_.header_table_size_limit());
+ }
+ {
+ // Maximum-size update with kDefaultHeaderTableSizeSetting. Succeeds.
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(kDefaultHeaderTableSizeSetting);
+
+ output_stream.TakeString(&input);
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting,
+ decoder_peer_.header_table_size_limit());
+ }
+ {
+ // Maximum-size update with kDefaultHeaderTableSizeSetting + 1. Fails.
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(kDefaultHeaderTableSizeSetting + 1);
+
+ output_stream.TakeString(&input);
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting,
+ decoder_peer_.header_table_size_limit());
+ }
+}
+
+// Two HeaderTableSizeUpdates may appear at the beginning of the block
+TEST_P(HpackDecoderAdapterTest, TwoTableSizeUpdates) {
+ SpdyString input;
+ {
+ // Should accept two table size updates, update to second one
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(0);
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(122);
+
+ output_stream.TakeString(&input);
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(122u, decoder_peer_.header_table_size_limit());
+ }
+}
+
+// Three HeaderTableSizeUpdates should result in an error
+TEST_P(HpackDecoderAdapterTest, ThreeTableSizeUpdatesError) {
+ SpdyString input;
+ {
+ // Should reject three table size updates, update to second one
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(5);
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(10);
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(15);
+
+ output_stream.TakeString(&input);
+
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(10u, decoder_peer_.header_table_size_limit());
+ }
+}
+
+// HeaderTableSizeUpdates may only appear at the beginning of the block
+// Any other updates should result in an error
+TEST_P(HpackDecoderAdapterTest, TableSizeUpdateSecondError) {
+ SpdyString input;
+ {
+ // Should reject a table size update appearing after a different entry
+ // The table size should remain as the default
+ HpackOutputStream output_stream;
+ output_stream.AppendBytes("\x82\x85");
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(123);
+
+ output_stream.TakeString(&input);
+
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting,
+ decoder_peer_.header_table_size_limit());
+ }
+}
+
+// HeaderTableSizeUpdates may only appear at the beginning of the block
+// Any other updates should result in an error
+TEST_P(HpackDecoderAdapterTest, TableSizeUpdateFirstThirdError) {
+ SpdyString input;
+ {
+ // Should reject the second table size update
+ // if a different entry appears after the first update
+ // The table size should update to the first but not the second
+ HpackOutputStream output_stream;
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(60);
+ output_stream.AppendBytes("\x82\x85");
+ output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream.AppendUint32(125);
+
+ output_stream.TakeString(&input);
+
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece(input)));
+ EXPECT_EQ(60u, decoder_peer_.header_table_size_limit());
+ }
+}
+
+// Decoding two valid encoded literal headers with no indexing should
+// work.
+TEST_P(HpackDecoderAdapterTest, LiteralHeaderNoIndexing) {
+ // First header with indexed name, second header with string literal
+ // name.
+ const char input[] = "\x04\x0c/sample/path\x00\x06:path2\x0e/sample/path/2";
+ const SpdyHeaderBlock& header_set = DecodeBlockExpectingSuccess(
+ SpdyStringPiece(input, SPDY_ARRAYSIZE(input) - 1));
+
+ SpdyHeaderBlock expected_header_set;
+ expected_header_set[":path"] = "/sample/path";
+ expected_header_set[":path2"] = "/sample/path/2";
+ EXPECT_EQ(expected_header_set, header_set);
+}
+
+// Decoding two valid encoded literal headers with incremental
+// indexing and string literal names should work.
+TEST_P(HpackDecoderAdapterTest, LiteralHeaderIncrementalIndexing) {
+ const char input[] = "\x44\x0c/sample/path\x40\x06:path2\x0e/sample/path/2";
+ const SpdyHeaderBlock& header_set = DecodeBlockExpectingSuccess(
+ SpdyStringPiece(input, SPDY_ARRAYSIZE(input) - 1));
+
+ SpdyHeaderBlock expected_header_set;
+ expected_header_set[":path"] = "/sample/path";
+ expected_header_set[":path2"] = "/sample/path/2";
+ EXPECT_EQ(expected_header_set, header_set);
+}
+
+TEST_P(HpackDecoderAdapterTest, LiteralHeaderWithIndexingInvalidNameIndex) {
+ decoder_.ApplyHeaderTableSizeSetting(0);
+ EXPECT_TRUE(EncodeAndDecodeDynamicTableSizeUpdates(0, 0));
+
+ // Name is the last static index. Works.
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x7d\x03ooo")));
+ // Name is one beyond the last static index. Fails.
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x7e\x03ooo")));
+}
+
+TEST_P(HpackDecoderAdapterTest, LiteralHeaderNoIndexingInvalidNameIndex) {
+ // Name is the last static index. Works.
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x0f\x2e\x03ooo")));
+ // Name is one beyond the last static index. Fails.
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x0f\x2f\x03ooo")));
+}
+
+TEST_P(HpackDecoderAdapterTest, LiteralHeaderNeverIndexedInvalidNameIndex) {
+ // Name is the last static index. Works.
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyStringPiece("\x1f\x2e\x03ooo")));
+ // Name is one beyond the last static index. Fails.
+ EXPECT_FALSE(DecodeHeaderBlock(SpdyStringPiece("\x1f\x2f\x03ooo")));
+}
+
+TEST_P(HpackDecoderAdapterTest, TruncatedIndex) {
+ // Indexed Header, varint for index requires multiple bytes,
+ // but only one provided.
+ EXPECT_FALSE(DecodeHeaderBlock("\xff"));
+}
+
+TEST_P(HpackDecoderAdapterTest, TruncatedHuffmanLiteral) {
+ // Literal value, Huffman encoded, but with the last byte missing (i.e.
+ // drop the final ff shown below).
+ //
+ // 41 | == Literal indexed ==
+ // | Indexed name (idx = 1)
+ // | :authority
+ // 8c | Literal value (len = 12)
+ // | Huffman encoded:
+ // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k.....
+ // | Decoded:
+ // | www.example.com
+ // | -> :authority: www.example.com
+
+ SpdyString first = SpdyHexDecode("418cf1e3c2e5f23a6ba0ab90f4ff");
+ EXPECT_TRUE(DecodeHeaderBlock(first));
+ first.pop_back();
+ EXPECT_FALSE(DecodeHeaderBlock(first));
+}
+
+TEST_P(HpackDecoderAdapterTest, HuffmanEOSError) {
+ // Literal value, Huffman encoded, but with an additional ff byte at the end
+ // of the string, i.e. an EOS that is longer than permitted.
+ //
+ // 41 | == Literal indexed ==
+ // | Indexed name (idx = 1)
+ // | :authority
+ // 8d | Literal value (len = 13)
+ // | Huffman encoded:
+ // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k.....
+ // | Decoded:
+ // | www.example.com
+ // | -> :authority: www.example.com
+
+ SpdyString first = SpdyHexDecode("418cf1e3c2e5f23a6ba0ab90f4ff");
+ EXPECT_TRUE(DecodeHeaderBlock(first));
+ first = SpdyHexDecode("418df1e3c2e5f23a6ba0ab90f4ffff");
+ EXPECT_FALSE(DecodeHeaderBlock(first));
+}
+
+// Round-tripping the header set from RFC 7541 C.3.1 should work.
+// http://httpwg.org/specs/rfc7541.html#rfc.section.C.3.1
+TEST_P(HpackDecoderAdapterTest, BasicC31) {
+ HpackEncoder encoder(ObtainHpackHuffmanTable());
+
+ SpdyHeaderBlock expected_header_set;
+ expected_header_set[":method"] = "GET";
+ expected_header_set[":scheme"] = "http";
+ expected_header_set[":path"] = "/";
+ expected_header_set[":authority"] = "www.example.com";
+
+ SpdyString encoded_header_set;
+ EXPECT_TRUE(
+ encoder.EncodeHeaderSet(expected_header_set, &encoded_header_set));
+
+ EXPECT_TRUE(DecodeHeaderBlock(encoded_header_set));
+ EXPECT_EQ(expected_header_set, decoded_block());
+}
+
+// RFC 7541, Section C.4: Request Examples with Huffman Coding
+// http://httpwg.org/specs/rfc7541.html#rfc.section.C.4
+TEST_P(HpackDecoderAdapterTest, SectionC4RequestHuffmanExamples) {
+ // TODO(jamessynge): Use http2/hpack/tools/hpack_example.h to parse the
+ // example directly, instead of having it as a comment.
+ //
+ // 82 | == Indexed - Add ==
+ // | idx = 2
+ // | -> :method: GET
+ // 86 | == Indexed - Add ==
+ // | idx = 6
+ // | -> :scheme: http
+ // 84 | == Indexed - Add ==
+ // | idx = 4
+ // | -> :path: /
+ // 41 | == Literal indexed ==
+ // | Indexed name (idx = 1)
+ // | :authority
+ // 8c | Literal value (len = 12)
+ // | Huffman encoded:
+ // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k.....
+ // | Decoded:
+ // | www.example.com
+ // | -> :authority: www.example.com
+ SpdyString first = SpdyHexDecode("828684418cf1e3c2e5f23a6ba0ab90f4ff");
+ const SpdyHeaderBlock& first_header_set = DecodeBlockExpectingSuccess(first);
+
+ EXPECT_THAT(first_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":method", "GET"),
+ Pair(":scheme", "http"),
+ Pair(":path", "/"),
+ Pair(":authority", "www.example.com")));
+ // clang-format on
+
+ expectEntry(62, 57, ":authority", "www.example.com");
+ EXPECT_EQ(57u, decoder_peer_.current_header_table_size());
+
+ // 82 | == Indexed - Add ==
+ // | idx = 2
+ // | -> :method: GET
+ // 86 | == Indexed - Add ==
+ // | idx = 6
+ // | -> :scheme: http
+ // 84 | == Indexed - Add ==
+ // | idx = 4
+ // | -> :path: /
+ // be | == Indexed - Add ==
+ // | idx = 62
+ // | -> :authority: www.example.com
+ // 58 | == Literal indexed ==
+ // | Indexed name (idx = 24)
+ // | cache-control
+ // 86 | Literal value (len = 8)
+ // | Huffman encoded:
+ // a8eb 1064 9cbf | ...d..
+ // | Decoded:
+ // | no-cache
+ // | -> cache-control: no-cache
+
+ SpdyString second = SpdyHexDecode("828684be5886a8eb10649cbf");
+ const SpdyHeaderBlock& second_header_set =
+ DecodeBlockExpectingSuccess(second);
+
+ EXPECT_THAT(second_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":method", "GET"),
+ Pair(":scheme", "http"),
+ Pair(":path", "/"),
+ Pair(":authority", "www.example.com"),
+ Pair("cache-control", "no-cache")));
+ // clang-format on
+
+ expectEntry(62, 53, "cache-control", "no-cache");
+ expectEntry(63, 57, ":authority", "www.example.com");
+ EXPECT_EQ(110u, decoder_peer_.current_header_table_size());
+
+ // 82 | == Indexed - Add ==
+ // | idx = 2
+ // | -> :method: GET
+ // 87 | == Indexed - Add ==
+ // | idx = 7
+ // | -> :scheme: https
+ // 85 | == Indexed - Add ==
+ // | idx = 5
+ // | -> :path: /index.html
+ // bf | == Indexed - Add ==
+ // | idx = 63
+ // | -> :authority: www.example.com
+ // 40 | == Literal indexed ==
+ // 88 | Literal name (len = 10)
+ // | Huffman encoded:
+ // 25a8 49e9 5ba9 7d7f | %.I.[.}.
+ // | Decoded:
+ // | custom-key
+ // 89 | Literal value (len = 12)
+ // | Huffman encoded:
+ // 25a8 49e9 5bb8 e8b4 bf | %.I.[....
+ // | Decoded:
+ // | custom-value
+ // | -> custom-key: custom-value
+ SpdyString third =
+ SpdyHexDecode("828785bf408825a849e95ba97d7f8925a849e95bb8e8b4bf");
+ const SpdyHeaderBlock& third_header_set = DecodeBlockExpectingSuccess(third);
+
+ EXPECT_THAT(
+ third_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":method", "GET"),
+ Pair(":scheme", "https"),
+ Pair(":path", "/index.html"),
+ Pair(":authority", "www.example.com"),
+ Pair("custom-key", "custom-value")));
+ // clang-format on
+
+ expectEntry(62, 54, "custom-key", "custom-value");
+ expectEntry(63, 53, "cache-control", "no-cache");
+ expectEntry(64, 57, ":authority", "www.example.com");
+ EXPECT_EQ(164u, decoder_peer_.current_header_table_size());
+}
+
+// RFC 7541, Section C.6: Response Examples with Huffman Coding
+// http://httpwg.org/specs/rfc7541.html#rfc.section.C.6
+TEST_P(HpackDecoderAdapterTest, SectionC6ResponseHuffmanExamples) {
+ // The example is based on a maximum dynamic table size of 256,
+ // which allows for testing dynamic table evictions.
+ decoder_peer_.set_header_table_size_limit(256);
+
+ // 48 | == Literal indexed ==
+ // | Indexed name (idx = 8)
+ // | :status
+ // 82 | Literal value (len = 3)
+ // | Huffman encoded:
+ // 6402 | d.
+ // | Decoded:
+ // | 302
+ // | -> :status: 302
+ // 58 | == Literal indexed ==
+ // | Indexed name (idx = 24)
+ // | cache-control
+ // 85 | Literal value (len = 7)
+ // | Huffman encoded:
+ // aec3 771a 4b | ..w.K
+ // | Decoded:
+ // | private
+ // | -> cache-control: private
+ // 61 | == Literal indexed ==
+ // | Indexed name (idx = 33)
+ // | date
+ // 96 | Literal value (len = 29)
+ // | Huffman encoded:
+ // d07a be94 1054 d444 a820 0595 040b 8166 | .z...T.D. .....f
+ // e082 a62d 1bff | ...-..
+ // | Decoded:
+ // | Mon, 21 Oct 2013 20:13:21
+ // | GMT
+ // | -> date: Mon, 21 Oct 2013
+ // | 20:13:21 GMT
+ // 6e | == Literal indexed ==
+ // | Indexed name (idx = 46)
+ // | location
+ // 91 | Literal value (len = 23)
+ // | Huffman encoded:
+ // 9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 | .)...c.........C
+ // d3 | .
+ // | Decoded:
+ // | https://www.example.com
+ // | -> location: https://www.e
+ // | xample.com
+
+ SpdyString first = SpdyHexDecode(
+ "488264025885aec3771a4b6196d07abe"
+ "941054d444a8200595040b8166e082a6"
+ "2d1bff6e919d29ad171863c78f0b97c8"
+ "e9ae82ae43d3");
+ const SpdyHeaderBlock& first_header_set = DecodeBlockExpectingSuccess(first);
+
+ EXPECT_THAT(first_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":status", "302"),
+ Pair("cache-control", "private"),
+ Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
+ Pair("location", "https://www.example.com")));
+ // clang-format on
+
+ expectEntry(62, 63, "location", "https://www.example.com");
+ expectEntry(63, 65, "date", "Mon, 21 Oct 2013 20:13:21 GMT");
+ expectEntry(64, 52, "cache-control", "private");
+ expectEntry(65, 42, ":status", "302");
+ EXPECT_EQ(222u, decoder_peer_.current_header_table_size());
+
+ // 48 | == Literal indexed ==
+ // | Indexed name (idx = 8)
+ // | :status
+ // 83 | Literal value (len = 3)
+ // | Huffman encoded:
+ // 640e ff | d..
+ // | Decoded:
+ // | 307
+ // | - evict: :status: 302
+ // | -> :status: 307
+ // c1 | == Indexed - Add ==
+ // | idx = 65
+ // | -> cache-control: private
+ // c0 | == Indexed - Add ==
+ // | idx = 64
+ // | -> date: Mon, 21 Oct 2013
+ // | 20:13:21 GMT
+ // bf | == Indexed - Add ==
+ // | idx = 63
+ // | -> location:
+ // | https://www.example.com
+ SpdyString second = SpdyHexDecode("4883640effc1c0bf");
+ const SpdyHeaderBlock& second_header_set =
+ DecodeBlockExpectingSuccess(second);
+
+ EXPECT_THAT(second_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":status", "307"),
+ Pair("cache-control", "private"),
+ Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
+ Pair("location", "https://www.example.com")));
+ // clang-format on
+
+ expectEntry(62, 42, ":status", "307");
+ expectEntry(63, 63, "location", "https://www.example.com");
+ expectEntry(64, 65, "date", "Mon, 21 Oct 2013 20:13:21 GMT");
+ expectEntry(65, 52, "cache-control", "private");
+ EXPECT_EQ(222u, decoder_peer_.current_header_table_size());
+
+ // 88 | == Indexed - Add ==
+ // | idx = 8
+ // | -> :status: 200
+ // c1 | == Indexed - Add ==
+ // | idx = 65
+ // | -> cache-control: private
+ // 61 | == Literal indexed ==
+ // | Indexed name (idx = 33)
+ // | date
+ // 96 | Literal value (len = 22)
+ // | Huffman encoded:
+ // d07a be94 1054 d444 a820 0595 040b 8166 | .z...T.D. .....f
+ // e084 a62d 1bff | ...-..
+ // | Decoded:
+ // | Mon, 21 Oct 2013 20:13:22
+ // | GMT
+ // | - evict: cache-control:
+ // | private
+ // | -> date: Mon, 21 Oct 2013
+ // | 20:13:22 GMT
+ // c0 | == Indexed - Add ==
+ // | idx = 64
+ // | -> location:
+ // | https://www.example.com
+ // 5a | == Literal indexed ==
+ // | Indexed name (idx = 26)
+ // | content-encoding
+ // 83 | Literal value (len = 3)
+ // | Huffman encoded:
+ // 9bd9 ab | ...
+ // | Decoded:
+ // | gzip
+ // | - evict: date: Mon, 21 Oct
+ // | 2013 20:13:21 GMT
+ // | -> content-encoding: gzip
+ // 77 | == Literal indexed ==
+ // | Indexed name (idx = 55)
+ // | set-cookie
+ // ad | Literal value (len = 45)
+ // | Huffman encoded:
+ // 94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 | .........5...[9`
+ // d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 | ..'..6r..'..)...
+ // 3160 65c0 03ed 4ee5 b106 3d50 07 | 1`e...N...=P.
+ // | Decoded:
+ // | foo=ASDJKHQKBZXOQWEOPIUAXQ
+ // | WEOIU; max-age=3600; versi
+ // | on=1
+ // | - evict: location:
+ // | https://www.example.com
+ // | - evict: :status: 307
+ // | -> set-cookie: foo=ASDJKHQ
+ // | KBZXOQWEOPIUAXQWEOIU;
+ // | max-age=3600; version=1
+ SpdyString third = SpdyHexDecode(
+ "88c16196d07abe941054d444a8200595"
+ "040b8166e084a62d1bffc05a839bd9ab"
+ "77ad94e7821dd7f2e6c7b335dfdfcd5b"
+ "3960d5af27087f3672c1ab270fb5291f"
+ "9587316065c003ed4ee5b1063d5007");
+ const SpdyHeaderBlock& third_header_set = DecodeBlockExpectingSuccess(third);
+
+ EXPECT_THAT(third_header_set,
+ ElementsAre(
+ // clang-format off
+ Pair(":status", "200"),
+ Pair("cache-control", "private"),
+ Pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"),
+ Pair("location", "https://www.example.com"),
+ Pair("content-encoding", "gzip"),
+ Pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;"
+ " max-age=3600; version=1")));
+ // clang-format on
+
+ expectEntry(62, 98, "set-cookie",
+ "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;"
+ " max-age=3600; version=1");
+ expectEntry(63, 52, "content-encoding", "gzip");
+ expectEntry(64, 65, "date", "Mon, 21 Oct 2013 20:13:22 GMT");
+ EXPECT_EQ(215u, decoder_peer_.current_header_table_size());
+}
+
+// Regression test: Found that entries with dynamic indexed names and literal
+// values caused "use after free" MSAN failures if the name was evicted as it
+// was being re-used.
+TEST_P(HpackDecoderAdapterTest, ReuseNameOfEvictedEntry) {
+ // Each entry is measured as 32 bytes plus the sum of the lengths of the name
+ // and the value. Set the size big enough for at most one entry, and a fairly
+ // small one at that (31 ASCII characters).
+ decoder_.ApplyHeaderTableSizeSetting(63);
+
+ HpackBlockBuilder hbb;
+ hbb.AppendDynamicTableSizeUpdate(0);
+ hbb.AppendDynamicTableSizeUpdate(63);
+
+ const SpdyStringPiece name("some-name");
+ const SpdyStringPiece value1("some-value");
+ const SpdyStringPiece value2("another-value");
+ const SpdyStringPiece value3("yet-another-value");
+
+ // Add an entry that will become the first in the dynamic table, entry 62.
+ hbb.AppendLiteralNameAndValue(HpackEntryType::kIndexedLiteralHeader, false,
+ name, false, value1);
+
+ // Confirm that entry has been added by re-using it.
+ hbb.AppendIndexedHeader(62);
+
+ // Add another entry referring to the name of the first. This will evict the
+ // first.
+ hbb.AppendNameIndexAndLiteralValue(HpackEntryType::kIndexedLiteralHeader, 62,
+ false, value2);
+
+ // Confirm that entry has been added by re-using it.
+ hbb.AppendIndexedHeader(62);
+
+ // Add another entry referring to the name of the second. This will evict the
+ // second.
+ hbb.AppendNameIndexAndLiteralValue(HpackEntryType::kIndexedLiteralHeader, 62,
+ false, value3);
+
+ // Confirm that entry has been added by re-using it.
+ hbb.AppendIndexedHeader(62);
+
+ // Can't have DecodeHeaderBlock do the default check for size of the decoded
+ // data because SpdyHeaderBlock will join multiple headers with the same
+ // name into a single entry, thus we won't see repeated occurrences of the
+ // name, instead seeing separators between values.
+ EXPECT_TRUE(DecodeHeaderBlock(hbb.buffer(), kNoCheckDecodedSize));
+
+ SpdyHeaderBlock expected_header_set;
+ expected_header_set.AppendValueOrAddHeader(name, value1);
+ expected_header_set.AppendValueOrAddHeader(name, value1);
+ expected_header_set.AppendValueOrAddHeader(name, value2);
+ expected_header_set.AppendValueOrAddHeader(name, value2);
+ expected_header_set.AppendValueOrAddHeader(name, value3);
+ expected_header_set.AppendValueOrAddHeader(name, value3);
+
+ // SpdyHeaderBlock stores these 6 strings as '\0' separated values.
+ // Make sure that is what happened.
+ SpdyString joined_values = expected_header_set[name].as_string();
+ EXPECT_EQ(joined_values.size(),
+ 2 * value1.size() + 2 * value2.size() + 2 * value3.size() + 5);
+
+ EXPECT_EQ(expected_header_set, decoded_block());
+
+ if (start_choice_ == START_WITH_HANDLER) {
+ EXPECT_EQ(handler_.header_bytes_parsed(),
+ 6 * name.size() + 2 * value1.size() + 2 * value2.size() +
+ 2 * value3.size());
+ }
+}
+
+// Regression test for https://crbug.com/747395.
+TEST_P(HpackDecoderAdapterTest, Cookies) {
+ SpdyHeaderBlock expected_header_set;
+ expected_header_set["cookie"] = "foo; bar";
+
+ EXPECT_TRUE(DecodeHeaderBlock(SpdyHexDecode("608294e76003626172")));
+ EXPECT_EQ(expected_header_set, decoded_block());
+}
+
+} // namespace
+} // namespace test
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_encoder.cc b/spdy/core/hpack/hpack_encoder.cc
new file mode 100644
index 0000000..a9981b9
--- /dev/null
+++ b/spdy/core/hpack/hpack_encoder.cc
@@ -0,0 +1,365 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_ptr_util.h"
+
+namespace spdy {
+
+class HpackEncoder::RepresentationIterator {
+ public:
+ // |pseudo_headers| and |regular_headers| must outlive the iterator.
+ RepresentationIterator(const Representations& pseudo_headers,
+ const Representations& regular_headers)
+ : pseudo_begin_(pseudo_headers.begin()),
+ pseudo_end_(pseudo_headers.end()),
+ regular_begin_(regular_headers.begin()),
+ regular_end_(regular_headers.end()) {}
+
+ // |headers| must outlive the iterator.
+ explicit RepresentationIterator(const Representations& headers)
+ : pseudo_begin_(headers.begin()),
+ pseudo_end_(headers.end()),
+ regular_begin_(headers.end()),
+ regular_end_(headers.end()) {}
+
+ bool HasNext() {
+ return pseudo_begin_ != pseudo_end_ || regular_begin_ != regular_end_;
+ }
+
+ const Representation Next() {
+ if (pseudo_begin_ != pseudo_end_) {
+ return *pseudo_begin_++;
+ } else {
+ return *regular_begin_++;
+ }
+ }
+
+ private:
+ Representations::const_iterator pseudo_begin_;
+ Representations::const_iterator pseudo_end_;
+ Representations::const_iterator regular_begin_;
+ Representations::const_iterator regular_end_;
+};
+
+namespace {
+
+// The default header listener.
+void NoOpListener(SpdyStringPiece /*name*/, SpdyStringPiece /*value*/) {}
+
+// The default HPACK indexing policy.
+bool DefaultPolicy(SpdyStringPiece name, SpdyStringPiece /* value */) {
+ if (name.empty()) {
+ return false;
+ }
+ // :authority is always present and rarely changes, and has moderate
+ // length, therefore it makes a lot of sense to index (insert in the
+ // dynamic table).
+ if (name[0] == kPseudoHeaderPrefix) {
+ return name == ":authority";
+ }
+ return true;
+}
+
+} // namespace
+
+HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
+ : output_stream_(),
+ huffman_table_(table),
+ min_table_size_setting_received_(std::numeric_limits<size_t>::max()),
+ listener_(NoOpListener),
+ should_index_(DefaultPolicy),
+ enable_compression_(true),
+ should_emit_table_size_(false) {}
+
+HpackEncoder::~HpackEncoder() = default;
+
+bool HpackEncoder::EncodeHeaderSet(const SpdyHeaderBlock& header_set,
+ SpdyString* output) {
+ // Separate header set into pseudo-headers and regular headers.
+ Representations pseudo_headers;
+ Representations regular_headers;
+ bool found_cookie = false;
+ for (const auto& header : header_set) {
+ if (!found_cookie && header.first == "cookie") {
+ // Note that there can only be one "cookie" header, because header_set is
+ // a map.
+ found_cookie = true;
+ CookieToCrumbs(header, ®ular_headers);
+ } else if (!header.first.empty() &&
+ header.first[0] == kPseudoHeaderPrefix) {
+ DecomposeRepresentation(header, &pseudo_headers);
+ } else {
+ DecomposeRepresentation(header, ®ular_headers);
+ }
+ }
+
+ {
+ RepresentationIterator iter(pseudo_headers, regular_headers);
+ EncodeRepresentations(&iter, output);
+ }
+ return true;
+}
+
+void HpackEncoder::ApplyHeaderTableSizeSetting(size_t size_setting) {
+ if (size_setting == header_table_.settings_size_bound()) {
+ return;
+ }
+ if (size_setting < header_table_.settings_size_bound()) {
+ min_table_size_setting_received_ =
+ std::min(size_setting, min_table_size_setting_received_);
+ }
+ header_table_.SetSettingsHeaderTableSize(size_setting);
+ should_emit_table_size_ = true;
+}
+
+size_t HpackEncoder::EstimateMemoryUsage() const {
+ // |huffman_table_| is a singleton. It's accounted for in spdy_session_pool.cc
+ return SpdyEstimateMemoryUsage(header_table_) +
+ SpdyEstimateMemoryUsage(output_stream_);
+}
+
+void HpackEncoder::EncodeRepresentations(RepresentationIterator* iter,
+ SpdyString* output) {
+ MaybeEmitTableSize();
+ while (iter->HasNext()) {
+ const auto header = iter->Next();
+ listener_(header.first, header.second);
+ if (enable_compression_) {
+ const HpackEntry* entry =
+ header_table_.GetByNameAndValue(header.first, header.second);
+ if (entry != nullptr) {
+ EmitIndex(entry);
+ } else if (should_index_(header.first, header.second)) {
+ EmitIndexedLiteral(header);
+ } else {
+ EmitNonIndexedLiteral(header);
+ }
+ } else {
+ EmitNonIndexedLiteral(header);
+ }
+ }
+
+ output_stream_.TakeString(output);
+}
+
+void HpackEncoder::EmitIndex(const HpackEntry* entry) {
+ DVLOG(2) << "Emitting index " << header_table_.IndexOf(entry);
+ output_stream_.AppendPrefix(kIndexedOpcode);
+ output_stream_.AppendUint32(header_table_.IndexOf(entry));
+}
+
+void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
+ DVLOG(2) << "Emitting indexed literal: (" << representation.first << ", "
+ << representation.second << ")";
+ output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
+ EmitLiteral(representation);
+ header_table_.TryAddEntry(representation.first, representation.second);
+}
+
+void HpackEncoder::EmitNonIndexedLiteral(const Representation& representation) {
+ DVLOG(2) << "Emitting nonindexed literal: (" << representation.first << ", "
+ << representation.second << ")";
+ output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
+ output_stream_.AppendUint32(0);
+ EmitString(representation.first);
+ EmitString(representation.second);
+}
+
+void HpackEncoder::EmitLiteral(const Representation& representation) {
+ const HpackEntry* name_entry = header_table_.GetByName(representation.first);
+ if (name_entry != nullptr) {
+ output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
+ } else {
+ output_stream_.AppendUint32(0);
+ EmitString(representation.first);
+ }
+ EmitString(representation.second);
+}
+
+void HpackEncoder::EmitString(SpdyStringPiece str) {
+ size_t encoded_size =
+ enable_compression_ ? huffman_table_.EncodedSize(str) : str.size();
+ if (encoded_size < str.size()) {
+ DVLOG(2) << "Emitted Huffman-encoded string of length " << encoded_size;
+ output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
+ output_stream_.AppendUint32(encoded_size);
+ huffman_table_.EncodeString(str, &output_stream_);
+ } else {
+ DVLOG(2) << "Emitted literal string of length " << str.size();
+ output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
+ output_stream_.AppendUint32(str.size());
+ output_stream_.AppendBytes(str);
+ }
+}
+
+void HpackEncoder::MaybeEmitTableSize() {
+ if (!should_emit_table_size_) {
+ return;
+ }
+ const size_t current_size = CurrentHeaderTableSizeSetting();
+ DVLOG(1) << "MaybeEmitTableSize current_size=" << current_size;
+ DVLOG(1) << "MaybeEmitTableSize min_table_size_setting_received_="
+ << min_table_size_setting_received_;
+ if (min_table_size_setting_received_ < current_size) {
+ output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream_.AppendUint32(min_table_size_setting_received_);
+ }
+ output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ output_stream_.AppendUint32(current_size);
+ min_table_size_setting_received_ = std::numeric_limits<size_t>::max();
+ should_emit_table_size_ = false;
+}
+
+// static
+void HpackEncoder::CookieToCrumbs(const Representation& cookie,
+ Representations* out) {
+ // See Section 8.1.2.5. "Compressing the Cookie Header Field" in the HTTP/2
+ // specification at https://tools.ietf.org/html/draft-ietf-httpbis-http2-14.
+ // Cookie values are split into individually-encoded HPACK representations.
+ SpdyStringPiece cookie_value = cookie.second;
+ // Consume leading and trailing whitespace if present.
+ SpdyStringPiece::size_type first = cookie_value.find_first_not_of(" \t");
+ SpdyStringPiece::size_type last = cookie_value.find_last_not_of(" \t");
+ if (first == SpdyStringPiece::npos) {
+ cookie_value = SpdyStringPiece();
+ } else {
+ cookie_value = cookie_value.substr(first, (last - first) + 1);
+ }
+ for (size_t pos = 0;;) {
+ size_t end = cookie_value.find(";", pos);
+
+ if (end == SpdyStringPiece::npos) {
+ out->push_back(std::make_pair(cookie.first, cookie_value.substr(pos)));
+ break;
+ }
+ out->push_back(
+ std::make_pair(cookie.first, cookie_value.substr(pos, end - pos)));
+
+ // Consume next space if present.
+ pos = end + 1;
+ if (pos != cookie_value.size() && cookie_value[pos] == ' ') {
+ pos++;
+ }
+ }
+}
+
+// static
+void HpackEncoder::DecomposeRepresentation(const Representation& header_field,
+ Representations* out) {
+ size_t pos = 0;
+ size_t end = 0;
+ while (end != SpdyStringPiece::npos) {
+ end = header_field.second.find('\0', pos);
+ out->push_back(std::make_pair(
+ header_field.first,
+ header_field.second.substr(
+ pos, end == SpdyStringPiece::npos ? end : end - pos)));
+ pos = end + 1;
+ }
+}
+
+// static
+void HpackEncoder::GatherRepresentation(const Representation& header_field,
+ Representations* out) {
+ out->push_back(std::make_pair(header_field.first, header_field.second));
+}
+
+// Iteratively encodes a SpdyHeaderBlock.
+class HpackEncoder::Encoderator : public ProgressiveEncoder {
+ public:
+ Encoderator(const SpdyHeaderBlock& header_set, HpackEncoder* encoder);
+
+ // Encoderator is neither copyable nor movable.
+ Encoderator(const Encoderator&) = delete;
+ Encoderator& operator=(const Encoderator&) = delete;
+
+ // Returns true iff more remains to encode.
+ bool HasNext() const override { return has_next_; }
+
+ // Encodes up to max_encoded_bytes of the current header block into the
+ // given output string.
+ void Next(size_t max_encoded_bytes, SpdyString* output) override;
+
+ private:
+ HpackEncoder* encoder_;
+ std::unique_ptr<RepresentationIterator> header_it_;
+ Representations pseudo_headers_;
+ Representations regular_headers_;
+ bool has_next_;
+};
+
+HpackEncoder::Encoderator::Encoderator(const SpdyHeaderBlock& header_set,
+ HpackEncoder* encoder)
+ : encoder_(encoder), has_next_(true) {
+ // Separate header set into pseudo-headers and regular headers.
+ const bool use_compression = encoder_->enable_compression_;
+ bool found_cookie = false;
+ for (const auto& header : header_set) {
+ if (!found_cookie && header.first == "cookie") {
+ // Note that there can only be one "cookie" header, because header_set
+ // is a map.
+ found_cookie = true;
+ CookieToCrumbs(header, ®ular_headers_);
+ } else if (!header.first.empty() &&
+ header.first[0] == kPseudoHeaderPrefix) {
+ use_compression ? DecomposeRepresentation(header, &pseudo_headers_)
+ : GatherRepresentation(header, &pseudo_headers_);
+ } else {
+ use_compression ? DecomposeRepresentation(header, ®ular_headers_)
+ : GatherRepresentation(header, ®ular_headers_);
+ }
+ }
+ header_it_ =
+ SpdyMakeUnique<RepresentationIterator>(pseudo_headers_, regular_headers_);
+
+ encoder_->MaybeEmitTableSize();
+}
+
+void HpackEncoder::Encoderator::Next(size_t max_encoded_bytes,
+ SpdyString* output) {
+ SPDY_BUG_IF(!has_next_)
+ << "Encoderator::Next called with nothing left to encode.";
+ const bool use_compression = encoder_->enable_compression_;
+
+ // Encode up to max_encoded_bytes of headers.
+ while (header_it_->HasNext() &&
+ encoder_->output_stream_.size() <= max_encoded_bytes) {
+ const Representation header = header_it_->Next();
+ encoder_->listener_(header.first, header.second);
+ if (use_compression) {
+ const HpackEntry* entry = encoder_->header_table_.GetByNameAndValue(
+ header.first, header.second);
+ if (entry != nullptr) {
+ encoder_->EmitIndex(entry);
+ } else if (encoder_->should_index_(header.first, header.second)) {
+ encoder_->EmitIndexedLiteral(header);
+ } else {
+ encoder_->EmitNonIndexedLiteral(header);
+ }
+ } else {
+ encoder_->EmitNonIndexedLiteral(header);
+ }
+ }
+
+ has_next_ = encoder_->output_stream_.size() > max_encoded_bytes;
+ encoder_->output_stream_.BoundedTakeString(max_encoded_bytes, output);
+}
+
+std::unique_ptr<HpackEncoder::ProgressiveEncoder> HpackEncoder::EncodeHeaderSet(
+ const SpdyHeaderBlock& header_set) {
+ return SpdyMakeUnique<Encoderator>(header_set, this);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_encoder.h b/spdy/core/hpack/hpack_encoder.h
new file mode 100644
index 0000000..486d536
--- /dev/null
+++ b/spdy/core/hpack/hpack_encoder.h
@@ -0,0 +1,152 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_
+
+#include <stddef.h>
+
+#include <functional>
+#include <map>
+#include <memory>
+#include <utility>
+#include <vector>
+
+#include "base/macros.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_protocol.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+// An HpackEncoder encodes header sets as outlined in
+// http://tools.ietf.org/html/rfc7541.
+
+namespace spdy {
+
+class HpackHuffmanTable;
+
+namespace test {
+class HpackEncoderPeer;
+} // namespace test
+
+class SPDY_EXPORT_PRIVATE HpackEncoder {
+ public:
+ using Representation = std::pair<SpdyStringPiece, SpdyStringPiece>;
+ using Representations = std::vector<Representation>;
+
+ // Callers may provide a HeaderListener to be informed of header name-value
+ // pairs processed by this encoder.
+ using HeaderListener = std::function<void(SpdyStringPiece, SpdyStringPiece)>;
+
+ // An indexing policy should return true if the provided header name-value
+ // pair should be inserted into the HPACK dynamic table.
+ using IndexingPolicy = std::function<bool(SpdyStringPiece, SpdyStringPiece)>;
+
+ // |table| is an initialized HPACK Huffman table, having an
+ // externally-managed lifetime which spans beyond HpackEncoder.
+ explicit HpackEncoder(const HpackHuffmanTable& table);
+ HpackEncoder(const HpackEncoder&) = delete;
+ HpackEncoder& operator=(const HpackEncoder&) = delete;
+ ~HpackEncoder();
+
+ // Encodes the given header set into the given string. Returns
+ // whether or not the encoding was successful.
+ bool EncodeHeaderSet(const SpdyHeaderBlock& header_set, SpdyString* output);
+
+ class SPDY_EXPORT_PRIVATE ProgressiveEncoder {
+ public:
+ virtual ~ProgressiveEncoder() {}
+
+ // Returns true iff more remains to encode.
+ virtual bool HasNext() const = 0;
+
+ // Encodes up to max_encoded_bytes of the current header block into the
+ // given output string.
+ virtual void Next(size_t max_encoded_bytes, SpdyString* output) = 0;
+ };
+
+ // Returns a ProgressiveEncoder which must be outlived by both the given
+ // SpdyHeaderBlock and this object.
+ std::unique_ptr<ProgressiveEncoder> EncodeHeaderSet(
+ const SpdyHeaderBlock& header_set);
+
+ // Called upon a change to SETTINGS_HEADER_TABLE_SIZE. Specifically, this
+ // is to be called after receiving (and sending an acknowledgement for) a
+ // SETTINGS_HEADER_TABLE_SIZE update from the remote decoding endpoint.
+ void ApplyHeaderTableSizeSetting(size_t size_setting);
+
+ size_t CurrentHeaderTableSizeSetting() const {
+ return header_table_.settings_size_bound();
+ }
+
+ // This HpackEncoder will use |policy| to determine whether to insert header
+ // name-value pairs into the dynamic table.
+ void SetIndexingPolicy(IndexingPolicy policy) { should_index_ = policy; }
+
+ // |listener| will be invoked for each header name-value pair processed by
+ // this encoder.
+ void SetHeaderListener(HeaderListener listener) { listener_ = listener; }
+
+ void SetHeaderTableDebugVisitor(
+ std::unique_ptr<HpackHeaderTable::DebugVisitorInterface> visitor) {
+ header_table_.set_debug_visitor(std::move(visitor));
+ }
+
+ void DisableCompression() { enable_compression_ = false; }
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ friend class test::HpackEncoderPeer;
+
+ class RepresentationIterator;
+ class Encoderator;
+
+ // Encodes a sequence of header name-value pairs as a single header block.
+ void EncodeRepresentations(RepresentationIterator* iter, SpdyString* output);
+
+ // Emits a static/dynamic indexed representation (Section 7.1).
+ void EmitIndex(const HpackEntry* entry);
+
+ // Emits a literal representation (Section 7.2).
+ void EmitIndexedLiteral(const Representation& representation);
+ void EmitNonIndexedLiteral(const Representation& representation);
+ void EmitLiteral(const Representation& representation);
+
+ // Emits a Huffman or identity string (whichever is smaller).
+ void EmitString(SpdyStringPiece str);
+
+ // Emits the current dynamic table size if the table size was recently
+ // updated and we have not yet emitted it (Section 6.3).
+ void MaybeEmitTableSize();
+
+ // Crumbles a cookie header into ";" delimited crumbs.
+ static void CookieToCrumbs(const Representation& cookie,
+ Representations* crumbs_out);
+
+ // Crumbles other header field values at \0 delimiters.
+ static void DecomposeRepresentation(const Representation& header_field,
+ Representations* out);
+
+ // Gathers headers without crumbling. Used when compression is not enabled.
+ static void GatherRepresentation(const Representation& header_field,
+ Representations* out);
+
+ HpackHeaderTable header_table_;
+ HpackOutputStream output_stream_;
+
+ const HpackHuffmanTable& huffman_table_;
+ size_t min_table_size_setting_received_;
+ HeaderListener listener_;
+ IndexingPolicy should_index_;
+ bool enable_compression_;
+ bool should_emit_table_size_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_ENCODER_H_
diff --git a/spdy/core/hpack/hpack_encoder_test.cc b/spdy/core/hpack/hpack_encoder_test.cc
new file mode 100644
index 0000000..8ead1c2
--- /dev/null
+++ b/spdy/core/hpack/hpack_encoder_test.cc
@@ -0,0 +1,586 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h"
+
+#include <cstdint>
+#include <map>
+
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/http2/test_tools/http2_random.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_unsafe_arena.h"
+
+namespace spdy {
+
+namespace test {
+
+class HpackHeaderTablePeer {
+ public:
+ explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {}
+
+ HpackHeaderTable::EntryTable* dynamic_entries() {
+ return &table_->dynamic_entries_;
+ }
+
+ private:
+ HpackHeaderTable* table_;
+};
+
+class HpackEncoderPeer {
+ public:
+ typedef HpackEncoder::Representation Representation;
+ typedef HpackEncoder::Representations Representations;
+
+ explicit HpackEncoderPeer(HpackEncoder* encoder) : encoder_(encoder) {}
+
+ bool compression_enabled() const { return encoder_->enable_compression_; }
+ HpackHeaderTable* table() { return &encoder_->header_table_; }
+ HpackHeaderTablePeer table_peer() { return HpackHeaderTablePeer(table()); }
+ const HpackHuffmanTable& huffman_table() const {
+ return encoder_->huffman_table_;
+ }
+ void EmitString(SpdyStringPiece str) { encoder_->EmitString(str); }
+ void TakeString(SpdyString* out) { encoder_->output_stream_.TakeString(out); }
+ static void CookieToCrumbs(SpdyStringPiece cookie,
+ std::vector<SpdyStringPiece>* out) {
+ Representations tmp;
+ HpackEncoder::CookieToCrumbs(std::make_pair("", cookie), &tmp);
+
+ out->clear();
+ for (size_t i = 0; i != tmp.size(); ++i) {
+ out->push_back(tmp[i].second);
+ }
+ }
+ static void DecomposeRepresentation(SpdyStringPiece value,
+ std::vector<SpdyStringPiece>* out) {
+ Representations tmp;
+ HpackEncoder::DecomposeRepresentation(std::make_pair("foobar", value),
+ &tmp);
+
+ out->clear();
+ for (size_t i = 0; i != tmp.size(); ++i) {
+ out->push_back(tmp[i].second);
+ }
+ }
+
+ // TODO(dahollings): Remove or clean up these methods when deprecating
+ // non-incremental encoding path.
+ static bool EncodeHeaderSet(HpackEncoder* encoder,
+ const SpdyHeaderBlock& header_set,
+ SpdyString* output,
+ bool use_incremental) {
+ if (use_incremental) {
+ return EncodeIncremental(encoder, header_set, output);
+ } else {
+ return encoder->EncodeHeaderSet(header_set, output);
+ }
+ }
+
+ static bool EncodeIncremental(HpackEncoder* encoder,
+ const SpdyHeaderBlock& header_set,
+ SpdyString* output) {
+ std::unique_ptr<HpackEncoder::ProgressiveEncoder> encoderator =
+ encoder->EncodeHeaderSet(header_set);
+ SpdyString output_buffer;
+ http2::test::Http2Random random;
+ encoderator->Next(random.UniformInRange(0, 16), &output_buffer);
+ while (encoderator->HasNext()) {
+ SpdyString second_buffer;
+ encoderator->Next(random.UniformInRange(0, 16), &second_buffer);
+ output_buffer.append(second_buffer);
+ }
+ *output = std::move(output_buffer);
+ return true;
+ }
+
+ private:
+ HpackEncoder* encoder_;
+};
+
+} // namespace test
+
+namespace {
+
+using testing::ElementsAre;
+using testing::Pair;
+
+class HpackEncoderTest : public ::testing::TestWithParam<bool> {
+ protected:
+ typedef test::HpackEncoderPeer::Representations Representations;
+
+ HpackEncoderTest()
+ : encoder_(ObtainHpackHuffmanTable()),
+ peer_(&encoder_),
+ static_(peer_.table()->GetByIndex(1)),
+ headers_storage_(1024 /* block size */) {}
+
+ void SetUp() override {
+ use_incremental_ = GetParam();
+
+ // Populate dynamic entries into the table fixture. For simplicity each
+ // entry has name.size() + value.size() == 10.
+ key_1_ = peer_.table()->TryAddEntry("key1", "value1");
+ key_2_ = peer_.table()->TryAddEntry("key2", "value2");
+ cookie_a_ = peer_.table()->TryAddEntry("cookie", "a=bb");
+ cookie_c_ = peer_.table()->TryAddEntry("cookie", "c=dd");
+
+ // No further insertions may occur without evictions.
+ peer_.table()->SetMaxSize(peer_.table()->size());
+ }
+
+ void SaveHeaders(SpdyStringPiece name, SpdyStringPiece value) {
+ SpdyStringPiece n(headers_storage_.Memdup(name.data(), name.size()),
+ name.size());
+ SpdyStringPiece v(headers_storage_.Memdup(value.data(), value.size()),
+ value.size());
+ headers_observed_.push_back(std::make_pair(n, v));
+ }
+
+ void ExpectIndex(size_t index) {
+ expected_.AppendPrefix(kIndexedOpcode);
+ expected_.AppendUint32(index);
+ }
+ void ExpectIndexedLiteral(const HpackEntry* key_entry,
+ SpdyStringPiece value) {
+ expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
+ expected_.AppendUint32(IndexOf(key_entry));
+ ExpectString(&expected_, value);
+ }
+ void ExpectIndexedLiteral(SpdyStringPiece name, SpdyStringPiece value) {
+ expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
+ expected_.AppendUint32(0);
+ ExpectString(&expected_, name);
+ ExpectString(&expected_, value);
+ }
+ void ExpectNonIndexedLiteral(SpdyStringPiece name, SpdyStringPiece value) {
+ expected_.AppendPrefix(kLiteralNoIndexOpcode);
+ expected_.AppendUint32(0);
+ ExpectString(&expected_, name);
+ ExpectString(&expected_, value);
+ }
+ void ExpectString(HpackOutputStream* stream, SpdyStringPiece str) {
+ const HpackHuffmanTable& huffman_table = peer_.huffman_table();
+ size_t encoded_size = peer_.compression_enabled()
+ ? huffman_table.EncodedSize(str)
+ : str.size();
+ if (encoded_size < str.size()) {
+ expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
+ expected_.AppendUint32(encoded_size);
+ huffman_table.EncodeString(str, stream);
+ } else {
+ expected_.AppendPrefix(kStringLiteralIdentityEncoded);
+ expected_.AppendUint32(str.size());
+ expected_.AppendBytes(str);
+ }
+ }
+ void ExpectHeaderTableSizeUpdate(uint32_t size) {
+ expected_.AppendPrefix(kHeaderTableSizeUpdateOpcode);
+ expected_.AppendUint32(size);
+ }
+ void CompareWithExpectedEncoding(const SpdyHeaderBlock& header_set) {
+ SpdyString expected_out, actual_out;
+ expected_.TakeString(&expected_out);
+ EXPECT_TRUE(test::HpackEncoderPeer::EncodeHeaderSet(
+ &encoder_, header_set, &actual_out, use_incremental_));
+ EXPECT_EQ(expected_out, actual_out);
+ }
+ size_t IndexOf(const HpackEntry* entry) {
+ return peer_.table()->IndexOf(entry);
+ }
+
+ HpackEncoder encoder_;
+ test::HpackEncoderPeer peer_;
+
+ const HpackEntry* static_;
+ const HpackEntry* key_1_;
+ const HpackEntry* key_2_;
+ const HpackEntry* cookie_a_;
+ const HpackEntry* cookie_c_;
+
+ SpdyUnsafeArena headers_storage_;
+ std::vector<std::pair<SpdyStringPiece, SpdyStringPiece>> headers_observed_;
+
+ HpackOutputStream expected_;
+ bool use_incremental_;
+};
+
+INSTANTIATE_TEST_CASE_P(HpackEncoderTests, HpackEncoderTest, ::testing::Bool());
+
+TEST_P(HpackEncoderTest, SingleDynamicIndex) {
+ encoder_.SetHeaderListener(
+ [this](SpdyStringPiece name, SpdyStringPiece value) {
+ this->SaveHeaders(name, value);
+ });
+
+ ExpectIndex(IndexOf(key_2_));
+
+ SpdyHeaderBlock headers;
+ headers[key_2_->name()] = key_2_->value();
+ CompareWithExpectedEncoding(headers);
+ EXPECT_THAT(headers_observed_,
+ ElementsAre(Pair(key_2_->name(), key_2_->value())));
+}
+
+TEST_P(HpackEncoderTest, SingleStaticIndex) {
+ ExpectIndex(IndexOf(static_));
+
+ SpdyHeaderBlock headers;
+ headers[static_->name()] = static_->value();
+ CompareWithExpectedEncoding(headers);
+}
+
+TEST_P(HpackEncoderTest, SingleStaticIndexTooLarge) {
+ peer_.table()->SetMaxSize(1); // Also evicts all fixtures.
+ ExpectIndex(IndexOf(static_));
+
+ SpdyHeaderBlock headers;
+ headers[static_->name()] = static_->value();
+ CompareWithExpectedEncoding(headers);
+
+ EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
+}
+
+TEST_P(HpackEncoderTest, SingleLiteralWithIndexName) {
+ ExpectIndexedLiteral(key_2_, "value3");
+
+ SpdyHeaderBlock headers;
+ headers[key_2_->name()] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ // A new entry was inserted and added to the reference set.
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), key_2_->name());
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+TEST_P(HpackEncoderTest, SingleLiteralWithLiteralName) {
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), "key3");
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+TEST_P(HpackEncoderTest, SingleLiteralTooLarge) {
+ peer_.table()->SetMaxSize(1); // Also evicts all fixtures.
+
+ ExpectIndexedLiteral("key3", "value3");
+
+ // A header overflowing the header table is still emitted.
+ // The header table is empty.
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ EXPECT_EQ(0u, peer_.table_peer().dynamic_entries()->size());
+}
+
+TEST_P(HpackEncoderTest, EmitThanEvict) {
+ // |key_1_| is toggled and placed into the reference set,
+ // and then immediately evicted by "key3".
+ ExpectIndex(IndexOf(key_1_));
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers[key_1_->name()] = key_1_->value();
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+}
+
+TEST_P(HpackEncoderTest, CookieHeaderIsCrumbled) {
+ ExpectIndex(IndexOf(cookie_a_));
+ ExpectIndex(IndexOf(cookie_c_));
+ ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
+
+ SpdyHeaderBlock headers;
+ headers["cookie"] = "a=bb; c=dd; e=ff";
+ CompareWithExpectedEncoding(headers);
+}
+
+TEST_P(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) {
+ // Compactable string. Uses Huffman coding.
+ peer_.EmitString("feedbeef");
+ expected_.AppendPrefix(kStringLiteralHuffmanEncoded);
+ expected_.AppendUint32(6);
+ expected_.AppendBytes("\x94\xA5\x92\x32\x96_");
+
+ // Non-compactable. Uses identity coding.
+ peer_.EmitString("@@@@@@");
+ expected_.AppendPrefix(kStringLiteralIdentityEncoded);
+ expected_.AppendUint32(6);
+ expected_.AppendBytes("@@@@@@");
+
+ SpdyString expected_out, actual_out;
+ expected_.TakeString(&expected_out);
+ peer_.TakeString(&actual_out);
+ EXPECT_EQ(expected_out, actual_out);
+}
+
+TEST_P(HpackEncoderTest, EncodingWithoutCompression) {
+ encoder_.SetHeaderListener(
+ [this](SpdyStringPiece name, SpdyStringPiece value) {
+ this->SaveHeaders(name, value);
+ });
+ encoder_.DisableCompression();
+
+ ExpectNonIndexedLiteral(":path", "/index.html");
+ ExpectNonIndexedLiteral("cookie", "foo=bar");
+ ExpectNonIndexedLiteral("cookie", "baz=bing");
+ ExpectNonIndexedLiteral("hello", "goodbye");
+
+ SpdyHeaderBlock headers;
+ headers[":path"] = "/index.html";
+ headers["cookie"] = "foo=bar; baz=bing";
+ headers["hello"] = "goodbye";
+
+ CompareWithExpectedEncoding(headers);
+
+ EXPECT_THAT(
+ headers_observed_,
+ ElementsAre(Pair(":path", "/index.html"), Pair("cookie", "foo=bar"),
+ Pair("cookie", "baz=bing"), Pair("hello", "goodbye")));
+}
+
+TEST_P(HpackEncoderTest, MultipleEncodingPasses) {
+ encoder_.SetHeaderListener(
+ [this](SpdyStringPiece name, SpdyStringPiece value) {
+ this->SaveHeaders(name, value);
+ });
+
+ // Pass 1.
+ {
+ SpdyHeaderBlock headers;
+ headers["key1"] = "value1";
+ headers["cookie"] = "a=bb";
+
+ ExpectIndex(IndexOf(key_1_));
+ ExpectIndex(IndexOf(cookie_a_));
+ CompareWithExpectedEncoding(headers);
+ }
+ // Header table is:
+ // 65: key1: value1
+ // 64: key2: value2
+ // 63: cookie: a=bb
+ // 62: cookie: c=dd
+ // Pass 2.
+ {
+ SpdyHeaderBlock headers;
+ headers["key2"] = "value2";
+ headers["cookie"] = "c=dd; e=ff";
+
+ // "key2: value2"
+ ExpectIndex(64);
+ // "cookie: c=dd"
+ ExpectIndex(62);
+ // This cookie evicts |key1| from the dynamic table.
+ ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff");
+
+ CompareWithExpectedEncoding(headers);
+ }
+ // Header table is:
+ // 65: key2: value2
+ // 64: cookie: a=bb
+ // 63: cookie: c=dd
+ // 62: cookie: e=ff
+ // Pass 3.
+ {
+ SpdyHeaderBlock headers;
+ headers["key2"] = "value2";
+ headers["cookie"] = "a=bb; b=cc; c=dd";
+
+ // "key2: value2"
+ ExpectIndex(65);
+ // "cookie: a=bb"
+ ExpectIndex(64);
+ // This cookie evicts |key2| from the dynamic table.
+ ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "b=cc");
+ // "cookie: c=dd"
+ ExpectIndex(64);
+
+ CompareWithExpectedEncoding(headers);
+ }
+
+ // clang-format off
+ EXPECT_THAT(headers_observed_,
+ ElementsAre(Pair("key1", "value1"),
+ Pair("cookie", "a=bb"),
+ Pair("key2", "value2"),
+ Pair("cookie", "c=dd"),
+ Pair("cookie", "e=ff"),
+ Pair("key2", "value2"),
+ Pair("cookie", "a=bb"),
+ Pair("cookie", "b=cc"),
+ Pair("cookie", "c=dd")));
+ // clang-format on
+}
+
+TEST_P(HpackEncoderTest, PseudoHeadersFirst) {
+ SpdyHeaderBlock headers;
+ // A pseudo-header that should not be indexed.
+ headers[":path"] = "/spam/eggs.html";
+ // A pseudo-header to be indexed.
+ headers[":authority"] = "www.example.com";
+ // A regular header which precedes ":" alphabetically, should still be encoded
+ // after pseudo-headers.
+ headers["-foo"] = "bar";
+ headers["foo"] = "bar";
+ headers["cookie"] = "c=dd";
+
+ // Headers are indexed in the order in which they were added.
+ // This entry pushes "cookie: a=bb" back to 63.
+ ExpectNonIndexedLiteral(":path", "/spam/eggs.html");
+ ExpectIndexedLiteral(peer_.table()->GetByName(":authority"),
+ "www.example.com");
+ ExpectIndexedLiteral("-foo", "bar");
+ ExpectIndexedLiteral("foo", "bar");
+ ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "c=dd");
+ CompareWithExpectedEncoding(headers);
+}
+
+TEST_P(HpackEncoderTest, CookieToCrumbs) {
+ test::HpackEncoderPeer peer(nullptr);
+ std::vector<SpdyStringPiece> out;
+
+ // Leading and trailing whitespace is consumed. A space after ';' is consumed.
+ // All other spaces remain. ';' at beginning and end of string produce empty
+ // crumbs.
+ // See section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
+ // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
+ peer.CookieToCrumbs(" foo=1;bar=2 ; bar=3; bing=4; ", &out);
+ EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3", " bing=4", ""));
+
+ peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out);
+ EXPECT_THAT(out, ElementsAre("", "", "foo = bar ", "", "", "baz =bing"));
+
+ peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out);
+ EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar", "baz=bing"));
+
+ peer.CookieToCrumbs("baz=bing", &out);
+ EXPECT_THAT(out, ElementsAre("baz=bing"));
+
+ peer.CookieToCrumbs("", &out);
+ EXPECT_THAT(out, ElementsAre(""));
+
+ peer.CookieToCrumbs("foo;bar; baz;baz;bing;", &out);
+ EXPECT_THAT(out, ElementsAre("foo", "bar", "baz", "baz", "bing", ""));
+
+ peer.CookieToCrumbs(" \t foo=1;bar=2 ; bar=3;\t ", &out);
+ EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3", ""));
+
+ peer.CookieToCrumbs(" \t foo=1;bar=2 ; bar=3 \t ", &out);
+ EXPECT_THAT(out, ElementsAre("foo=1", "bar=2 ", "bar=3"));
+}
+
+TEST_P(HpackEncoderTest, DecomposeRepresentation) {
+ test::HpackEncoderPeer peer(nullptr);
+ std::vector<SpdyStringPiece> out;
+
+ peer.DecomposeRepresentation("", &out);
+ EXPECT_THAT(out, ElementsAre(""));
+
+ peer.DecomposeRepresentation("foobar", &out);
+ EXPECT_THAT(out, ElementsAre("foobar"));
+
+ peer.DecomposeRepresentation(SpdyStringPiece("foo\0bar", 7), &out);
+ EXPECT_THAT(out, ElementsAre("foo", "bar"));
+
+ peer.DecomposeRepresentation(SpdyStringPiece("\0foo\0bar", 8), &out);
+ EXPECT_THAT(out, ElementsAre("", "foo", "bar"));
+
+ peer.DecomposeRepresentation(SpdyStringPiece("foo\0bar\0", 8), &out);
+ EXPECT_THAT(out, ElementsAre("foo", "bar", ""));
+
+ peer.DecomposeRepresentation(SpdyStringPiece("\0foo\0bar\0", 9), &out);
+ EXPECT_THAT(out, ElementsAre("", "foo", "bar", ""));
+}
+
+// Test that encoded headers do not have \0-delimited multiple values, as this
+// became disallowed in HTTP/2 draft-14.
+TEST_P(HpackEncoderTest, CrumbleNullByteDelimitedValue) {
+ SpdyHeaderBlock headers;
+ // A header field to be crumbled: "spam: foo\0bar".
+ headers["spam"] = SpdyString("foo\0bar", 7);
+
+ ExpectIndexedLiteral("spam", "foo");
+ expected_.AppendPrefix(kLiteralIncrementalIndexOpcode);
+ expected_.AppendUint32(62);
+ expected_.AppendPrefix(kStringLiteralIdentityEncoded);
+ expected_.AppendUint32(3);
+ expected_.AppendBytes("bar");
+ CompareWithExpectedEncoding(headers);
+}
+
+TEST_P(HpackEncoderTest, HeaderTableSizeUpdate) {
+ encoder_.ApplyHeaderTableSizeSetting(1024);
+ ExpectHeaderTableSizeUpdate(1024);
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), "key3");
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+TEST_P(HpackEncoderTest, HeaderTableSizeUpdateWithMin) {
+ const size_t starting_size = peer_.table()->settings_size_bound();
+ encoder_.ApplyHeaderTableSizeSetting(starting_size - 2);
+ encoder_.ApplyHeaderTableSizeSetting(starting_size - 1);
+ // We must encode the low watermark, so the peer knows to evict entries
+ // if necessary.
+ ExpectHeaderTableSizeUpdate(starting_size - 2);
+ ExpectHeaderTableSizeUpdate(starting_size - 1);
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), "key3");
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+TEST_P(HpackEncoderTest, HeaderTableSizeUpdateWithExistingSize) {
+ encoder_.ApplyHeaderTableSizeSetting(peer_.table()->settings_size_bound());
+ // No encoded size update.
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), "key3");
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+TEST_P(HpackEncoderTest, HeaderTableSizeUpdatesWithGreaterSize) {
+ const size_t starting_size = peer_.table()->settings_size_bound();
+ encoder_.ApplyHeaderTableSizeSetting(starting_size + 1);
+ encoder_.ApplyHeaderTableSizeSetting(starting_size + 2);
+ // Only a single size update to the final size.
+ ExpectHeaderTableSizeUpdate(starting_size + 2);
+ ExpectIndexedLiteral("key3", "value3");
+
+ SpdyHeaderBlock headers;
+ headers["key3"] = "value3";
+ CompareWithExpectedEncoding(headers);
+
+ HpackEntry* new_entry = &peer_.table_peer().dynamic_entries()->front();
+ EXPECT_EQ(new_entry->name(), "key3");
+ EXPECT_EQ(new_entry->value(), "value3");
+}
+
+} // namespace
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_entry.cc b/spdy/core/hpack/hpack_entry.cc
new file mode 100644
index 0000000..90d53e6
--- /dev/null
+++ b/spdy/core/hpack/hpack_entry.cc
@@ -0,0 +1,89 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+
+namespace spdy {
+
+const size_t HpackEntry::kSizeOverhead = 32;
+
+HpackEntry::HpackEntry(SpdyStringPiece name,
+ SpdyStringPiece value,
+ bool is_static,
+ size_t insertion_index)
+ : name_(name.data(), name.size()),
+ value_(value.data(), value.size()),
+ name_ref_(name_),
+ value_ref_(value_),
+ insertion_index_(insertion_index),
+ type_(is_static ? STATIC : DYNAMIC),
+ time_added_(0) {}
+
+HpackEntry::HpackEntry(SpdyStringPiece name, SpdyStringPiece value)
+ : name_ref_(name),
+ value_ref_(value),
+ insertion_index_(0),
+ type_(LOOKUP),
+ time_added_(0) {}
+
+HpackEntry::HpackEntry() : insertion_index_(0), type_(LOOKUP), time_added_(0) {}
+
+HpackEntry::HpackEntry(const HpackEntry& other)
+ : insertion_index_(other.insertion_index_),
+ type_(other.type_),
+ time_added_(0) {
+ if (type_ == LOOKUP) {
+ name_ref_ = other.name_ref_;
+ value_ref_ = other.value_ref_;
+ } else {
+ name_ = other.name_;
+ value_ = other.value_;
+ name_ref_ = SpdyStringPiece(name_.data(), name_.size());
+ value_ref_ = SpdyStringPiece(value_.data(), value_.size());
+ }
+}
+
+HpackEntry& HpackEntry::operator=(const HpackEntry& other) {
+ insertion_index_ = other.insertion_index_;
+ type_ = other.type_;
+ if (type_ == LOOKUP) {
+ name_.clear();
+ value_.clear();
+ name_ref_ = other.name_ref_;
+ value_ref_ = other.value_ref_;
+ return *this;
+ }
+ name_ = other.name_;
+ value_ = other.value_;
+ name_ref_ = SpdyStringPiece(name_.data(), name_.size());
+ value_ref_ = SpdyStringPiece(value_.data(), value_.size());
+ return *this;
+}
+
+HpackEntry::~HpackEntry() = default;
+
+// static
+size_t HpackEntry::Size(SpdyStringPiece name, SpdyStringPiece value) {
+ return name.size() + value.size() + kSizeOverhead;
+}
+size_t HpackEntry::Size() const {
+ return Size(name(), value());
+}
+
+SpdyString HpackEntry::GetDebugString() const {
+ return SpdyStrCat(
+ "{ name: \"", name_ref_, "\", value: \"", value_ref_,
+ "\", index: ", insertion_index_, " ",
+ (IsStatic() ? " static" : (IsLookup() ? " lookup" : " dynamic")), " }");
+}
+
+size_t HpackEntry::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(name_) + SpdyEstimateMemoryUsage(value_);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_entry.h b/spdy/core/hpack/hpack_entry.h
new file mode 100644
index 0000000..28dee47
--- /dev/null
+++ b/spdy/core/hpack/hpack_entry.h
@@ -0,0 +1,110 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_
+
+#include <cstddef>
+#include <cstdint>
+
+#include "base/macros.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+// All section references below are to
+// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08
+
+namespace spdy {
+
+// A structure for an entry in the static table (3.3.1)
+// and the header table (3.3.2).
+class SPDY_EXPORT_PRIVATE HpackEntry {
+ public:
+ // The constant amount added to name().size() and value().size() to
+ // get the size of an HpackEntry as defined in 5.1.
+ static const size_t kSizeOverhead;
+
+ // Creates an entry. Preconditions:
+ // - |is_static| captures whether this entry is a member of the static
+ // or dynamic header table.
+ // - |insertion_index| is this entry's index in the total set of entries ever
+ // inserted into the header table (including static entries).
+ //
+ // The combination of |is_static| and |insertion_index| allows an
+ // HpackEntryTable to determine the index of an HpackEntry in O(1) time.
+ // Copies |name| and |value|.
+ HpackEntry(SpdyStringPiece name,
+ SpdyStringPiece value,
+ bool is_static,
+ size_t insertion_index);
+
+ // Create a 'lookup' entry (only) suitable for querying a HpackEntrySet. The
+ // instance InsertionIndex() always returns 0 and IsLookup() returns true.
+ // The memory backing |name| and |value| must outlive this object.
+ HpackEntry(SpdyStringPiece name, SpdyStringPiece value);
+
+ HpackEntry(const HpackEntry& other);
+ HpackEntry& operator=(const HpackEntry& other);
+
+ // Creates an entry with empty name and value. Only defined so that
+ // entries can be stored in STL containers.
+ HpackEntry();
+
+ ~HpackEntry();
+
+ SpdyStringPiece name() const { return name_ref_; }
+ SpdyStringPiece value() const { return value_ref_; }
+
+ // Returns whether this entry is a member of the static (as opposed to
+ // dynamic) table.
+ bool IsStatic() const { return type_ == STATIC; }
+
+ // Returns whether this entry is a lookup-only entry.
+ bool IsLookup() const { return type_ == LOOKUP; }
+
+ // Used to compute the entry's index in the header table.
+ size_t InsertionIndex() const { return insertion_index_; }
+
+ // Returns the size of an entry as defined in 5.1.
+ static size_t Size(SpdyStringPiece name, SpdyStringPiece value);
+ size_t Size() const;
+
+ SpdyString GetDebugString() const;
+
+ int64_t time_added() const { return time_added_; }
+ void set_time_added(int64_t now) { time_added_ = now; }
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ enum EntryType {
+ LOOKUP,
+ DYNAMIC,
+ STATIC,
+ };
+
+ // These members are not used for LOOKUP entries.
+ SpdyString name_;
+ SpdyString value_;
+
+ // These members are always valid. For DYNAMIC and STATIC entries, they
+ // always point to |name_| and |value_|.
+ SpdyStringPiece name_ref_;
+ SpdyStringPiece value_ref_;
+
+ // The entry's index in the total set of entries ever inserted into the header
+ // table.
+ size_t insertion_index_;
+
+ EntryType type_;
+
+ // For HpackHeaderTable::DebugVisitorInterface
+ int64_t time_added_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_ENTRY_H_
diff --git a/spdy/core/hpack/hpack_entry_test.cc b/spdy/core/hpack/hpack_entry_test.cc
new file mode 100644
index 0000000..507c851
--- /dev/null
+++ b/spdy/core/hpack/hpack_entry_test.cc
@@ -0,0 +1,122 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace spdy {
+
+namespace {
+
+class HpackEntryTest : public ::testing::Test {
+ protected:
+ HpackEntryTest()
+ : name_("header-name"),
+ value_("header value"),
+ total_insertions_(0),
+ table_size_(0) {}
+
+ // These builders maintain the same external table invariants that a "real"
+ // table (ie HpackHeaderTable) would.
+ HpackEntry StaticEntry() {
+ return HpackEntry(name_, value_, true, total_insertions_++);
+ }
+ HpackEntry DynamicEntry() {
+ ++table_size_;
+ size_t index = total_insertions_++;
+ return HpackEntry(name_, value_, false, index);
+ }
+ void DropEntry() { --table_size_; }
+
+ size_t IndexOf(const HpackEntry& entry) const {
+ if (entry.IsStatic()) {
+ return 1 + entry.InsertionIndex() + table_size_;
+ } else {
+ return total_insertions_ - entry.InsertionIndex();
+ }
+ }
+
+ size_t Size() {
+ return name_.size() + value_.size() + HpackEntry::kSizeOverhead;
+ }
+
+ SpdyString name_, value_;
+
+ private:
+ // Referenced by HpackEntry instances.
+ size_t total_insertions_;
+ size_t table_size_;
+};
+
+TEST_F(HpackEntryTest, StaticConstructor) {
+ HpackEntry entry(StaticEntry());
+
+ EXPECT_EQ(name_, entry.name());
+ EXPECT_EQ(value_, entry.value());
+ EXPECT_TRUE(entry.IsStatic());
+ EXPECT_EQ(1u, IndexOf(entry));
+ EXPECT_EQ(Size(), entry.Size());
+}
+
+TEST_F(HpackEntryTest, DynamicConstructor) {
+ HpackEntry entry(DynamicEntry());
+
+ EXPECT_EQ(name_, entry.name());
+ EXPECT_EQ(value_, entry.value());
+ EXPECT_FALSE(entry.IsStatic());
+ EXPECT_EQ(1u, IndexOf(entry));
+ EXPECT_EQ(Size(), entry.Size());
+}
+
+TEST_F(HpackEntryTest, LookupConstructor) {
+ HpackEntry entry(name_, value_);
+
+ EXPECT_EQ(name_, entry.name());
+ EXPECT_EQ(value_, entry.value());
+ EXPECT_FALSE(entry.IsStatic());
+ EXPECT_EQ(0u, IndexOf(entry));
+ EXPECT_EQ(Size(), entry.Size());
+}
+
+TEST_F(HpackEntryTest, DefaultConstructor) {
+ HpackEntry entry;
+
+ EXPECT_TRUE(entry.name().empty());
+ EXPECT_TRUE(entry.value().empty());
+ EXPECT_EQ(HpackEntry::kSizeOverhead, entry.Size());
+}
+
+TEST_F(HpackEntryTest, IndexUpdate) {
+ HpackEntry static1(StaticEntry());
+ HpackEntry static2(StaticEntry());
+
+ EXPECT_EQ(1u, IndexOf(static1));
+ EXPECT_EQ(2u, IndexOf(static2));
+
+ HpackEntry dynamic1(DynamicEntry());
+ HpackEntry dynamic2(DynamicEntry());
+
+ EXPECT_EQ(1u, IndexOf(dynamic2));
+ EXPECT_EQ(2u, IndexOf(dynamic1));
+ EXPECT_EQ(3u, IndexOf(static1));
+ EXPECT_EQ(4u, IndexOf(static2));
+
+ DropEntry(); // Drops |dynamic1|.
+
+ EXPECT_EQ(1u, IndexOf(dynamic2));
+ EXPECT_EQ(2u, IndexOf(static1));
+ EXPECT_EQ(3u, IndexOf(static2));
+
+ HpackEntry dynamic3(DynamicEntry());
+
+ EXPECT_EQ(1u, IndexOf(dynamic3));
+ EXPECT_EQ(2u, IndexOf(dynamic2));
+ EXPECT_EQ(3u, IndexOf(static1));
+ EXPECT_EQ(4u, IndexOf(static2));
+}
+
+} // namespace
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table.cc b/spdy/core/hpack/hpack_header_table.cc
new file mode 100644
index 0000000..dbe565f
--- /dev/null
+++ b/spdy/core/hpack/hpack_header_table.cc
@@ -0,0 +1,274 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+
+namespace spdy {
+
+size_t HpackHeaderTable::EntryHasher::operator()(
+ const HpackEntry* entry) const {
+ return SpdyHashStringPair(entry->name(), entry->value());
+}
+
+bool HpackHeaderTable::EntriesEq::operator()(const HpackEntry* lhs,
+ const HpackEntry* rhs) const {
+ if (lhs == nullptr) {
+ return rhs == nullptr;
+ }
+ if (rhs == nullptr) {
+ return false;
+ }
+ return lhs->name() == rhs->name() && lhs->value() == rhs->value();
+}
+
+HpackHeaderTable::HpackHeaderTable()
+ : static_entries_(ObtainHpackStaticTable().GetStaticEntries()),
+ static_index_(ObtainHpackStaticTable().GetStaticIndex()),
+ static_name_index_(ObtainHpackStaticTable().GetStaticNameIndex()),
+ settings_size_bound_(kDefaultHeaderTableSizeSetting),
+ size_(0),
+ max_size_(kDefaultHeaderTableSizeSetting),
+ total_insertions_(static_entries_.size()) {}
+
+HpackHeaderTable::~HpackHeaderTable() = default;
+
+const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) {
+ if (index == 0) {
+ return nullptr;
+ }
+ index -= 1;
+ if (index < static_entries_.size()) {
+ return &static_entries_[index];
+ }
+ index -= static_entries_.size();
+ if (index < dynamic_entries_.size()) {
+ const HpackEntry* result = &dynamic_entries_[index];
+ if (debug_visitor_ != nullptr) {
+ debug_visitor_->OnUseEntry(*result);
+ }
+ return result;
+ }
+ return nullptr;
+}
+
+const HpackEntry* HpackHeaderTable::GetByName(SpdyStringPiece name) {
+ {
+ auto it = static_name_index_.find(name);
+ if (it != static_name_index_.end()) {
+ return it->second;
+ }
+ }
+ {
+ NameToEntryMap::const_iterator it = dynamic_name_index_.find(name);
+ if (it != dynamic_name_index_.end()) {
+ const HpackEntry* result = it->second;
+ if (debug_visitor_ != nullptr) {
+ debug_visitor_->OnUseEntry(*result);
+ }
+ return result;
+ }
+ }
+ return nullptr;
+}
+
+const HpackEntry* HpackHeaderTable::GetByNameAndValue(SpdyStringPiece name,
+ SpdyStringPiece value) {
+ HpackEntry query(name, value);
+ {
+ auto it = static_index_.find(&query);
+ if (it != static_index_.end()) {
+ return *it;
+ }
+ }
+ {
+ auto it = dynamic_index_.find(&query);
+ if (it != dynamic_index_.end()) {
+ const HpackEntry* result = *it;
+ if (debug_visitor_ != nullptr) {
+ debug_visitor_->OnUseEntry(*result);
+ }
+ return result;
+ }
+ }
+ return nullptr;
+}
+
+size_t HpackHeaderTable::IndexOf(const HpackEntry* entry) const {
+ if (entry->IsLookup()) {
+ return 0;
+ } else if (entry->IsStatic()) {
+ return 1 + entry->InsertionIndex();
+ } else {
+ return total_insertions_ - entry->InsertionIndex() + static_entries_.size();
+ }
+}
+
+void HpackHeaderTable::SetMaxSize(size_t max_size) {
+ CHECK_LE(max_size, settings_size_bound_);
+
+ max_size_ = max_size;
+ if (size_ > max_size_) {
+ Evict(EvictionCountToReclaim(size_ - max_size_));
+ CHECK_LE(size_, max_size_);
+ }
+}
+
+void HpackHeaderTable::SetSettingsHeaderTableSize(size_t settings_size) {
+ settings_size_bound_ = settings_size;
+ SetMaxSize(settings_size_bound_);
+}
+
+void HpackHeaderTable::EvictionSet(SpdyStringPiece name,
+ SpdyStringPiece value,
+ EntryTable::iterator* begin_out,
+ EntryTable::iterator* end_out) {
+ size_t eviction_count = EvictionCountForEntry(name, value);
+ *begin_out = dynamic_entries_.end() - eviction_count;
+ *end_out = dynamic_entries_.end();
+}
+
+size_t HpackHeaderTable::EvictionCountForEntry(SpdyStringPiece name,
+ SpdyStringPiece value) const {
+ size_t available_size = max_size_ - size_;
+ size_t entry_size = HpackEntry::Size(name, value);
+
+ if (entry_size <= available_size) {
+ // No evictions are required.
+ return 0;
+ }
+ return EvictionCountToReclaim(entry_size - available_size);
+}
+
+size_t HpackHeaderTable::EvictionCountToReclaim(size_t reclaim_size) const {
+ size_t count = 0;
+ for (auto it = dynamic_entries_.rbegin();
+ it != dynamic_entries_.rend() && reclaim_size != 0; ++it, ++count) {
+ reclaim_size -= std::min(reclaim_size, it->Size());
+ }
+ return count;
+}
+
+void HpackHeaderTable::Evict(size_t count) {
+ for (size_t i = 0; i != count; ++i) {
+ CHECK(!dynamic_entries_.empty());
+ HpackEntry* entry = &dynamic_entries_.back();
+
+ size_ -= entry->Size();
+ auto it = dynamic_index_.find(entry);
+ DCHECK(it != dynamic_index_.end());
+ // Only remove an entry from the index if its insertion index matches;
+ // otherwise, the index refers to another entry with the same name and
+ // value.
+ if ((*it)->InsertionIndex() == entry->InsertionIndex()) {
+ dynamic_index_.erase(it);
+ }
+ auto name_it = dynamic_name_index_.find(entry->name());
+ DCHECK(name_it != dynamic_name_index_.end());
+ // Only remove an entry from the literal index if its insertion index
+ /// matches; otherwise, the index refers to another entry with the same
+ // name.
+ if (name_it->second->InsertionIndex() == entry->InsertionIndex()) {
+ dynamic_name_index_.erase(name_it);
+ }
+ dynamic_entries_.pop_back();
+ }
+}
+
+const HpackEntry* HpackHeaderTable::TryAddEntry(SpdyStringPiece name,
+ SpdyStringPiece value) {
+ Evict(EvictionCountForEntry(name, value));
+
+ size_t entry_size = HpackEntry::Size(name, value);
+ if (entry_size > (max_size_ - size_)) {
+ // Entire table has been emptied, but there's still insufficient room.
+ DCHECK(dynamic_entries_.empty());
+ DCHECK_EQ(0u, size_);
+ return nullptr;
+ }
+ dynamic_entries_.push_front(HpackEntry(name, value,
+ false, // is_static
+ total_insertions_));
+ HpackEntry* new_entry = &dynamic_entries_.front();
+ auto index_result = dynamic_index_.insert(new_entry);
+ if (!index_result.second) {
+ // An entry with the same name and value already exists in the dynamic
+ // index. We should replace it with the newly added entry.
+ DVLOG(1) << "Found existing entry: "
+ << (*index_result.first)->GetDebugString()
+ << " replacing with: " << new_entry->GetDebugString();
+ DCHECK_GT(new_entry->InsertionIndex(),
+ (*index_result.first)->InsertionIndex());
+ dynamic_index_.erase(index_result.first);
+ CHECK(dynamic_index_.insert(new_entry).second);
+ }
+
+ auto name_result =
+ dynamic_name_index_.insert(std::make_pair(new_entry->name(), new_entry));
+ if (!name_result.second) {
+ // An entry with the same name already exists in the dynamic index. We
+ // should replace it with the newly added entry.
+ DVLOG(1) << "Found existing entry: "
+ << name_result.first->second->GetDebugString()
+ << " replacing with: " << new_entry->GetDebugString();
+ DCHECK_GT(new_entry->InsertionIndex(),
+ name_result.first->second->InsertionIndex());
+ dynamic_name_index_.erase(name_result.first);
+ auto insert_result = dynamic_name_index_.insert(
+ std::make_pair(new_entry->name(), new_entry));
+ CHECK(insert_result.second);
+ }
+
+ size_ += entry_size;
+ ++total_insertions_;
+ if (debug_visitor_ != nullptr) {
+ // Call |debug_visitor_->OnNewEntry()| to get the current time.
+ HpackEntry& entry = dynamic_entries_.front();
+ entry.set_time_added(debug_visitor_->OnNewEntry(entry));
+ DVLOG(2) << "HpackHeaderTable::OnNewEntry: name=" << entry.name()
+ << ", value=" << entry.value()
+ << ", insert_index=" << entry.InsertionIndex()
+ << ", time_added=" << entry.time_added();
+ }
+
+ return &dynamic_entries_.front();
+}
+
+void HpackHeaderTable::DebugLogTableState() const {
+ DVLOG(2) << "Dynamic table:";
+ for (auto it = dynamic_entries_.begin(); it != dynamic_entries_.end(); ++it) {
+ DVLOG(2) << " " << it->GetDebugString();
+ }
+ DVLOG(2) << "Full Static Index:";
+ for (const auto* entry : static_index_) {
+ DVLOG(2) << " " << entry->GetDebugString();
+ }
+ DVLOG(2) << "Full Static Name Index:";
+ for (const auto it : static_name_index_) {
+ DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString();
+ }
+ DVLOG(2) << "Full Dynamic Index:";
+ for (const auto* entry : dynamic_index_) {
+ DVLOG(2) << " " << entry->GetDebugString();
+ }
+ DVLOG(2) << "Full Dynamic Name Index:";
+ for (const auto it : dynamic_name_index_) {
+ DVLOG(2) << " " << it.first << ": " << it.second->GetDebugString();
+ }
+}
+
+size_t HpackHeaderTable::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(dynamic_entries_) +
+ SpdyEstimateMemoryUsage(dynamic_index_) +
+ SpdyEstimateMemoryUsage(dynamic_name_index_);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_header_table.h b/spdy/core/hpack/hpack_header_table.h
new file mode 100644
index 0000000..e85edb7
--- /dev/null
+++ b/spdy/core/hpack/hpack_header_table.h
@@ -0,0 +1,180 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <deque>
+#include <memory>
+
+#include "base/macros.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_containers.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_macros.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+// All section references below are to http://tools.ietf.org/html/rfc7541.
+
+namespace spdy {
+
+namespace test {
+class HpackHeaderTablePeer;
+} // namespace test
+
+// A data structure for the static table (2.3.1) and the dynamic table (2.3.2).
+class SPDY_EXPORT_PRIVATE HpackHeaderTable {
+ public:
+ friend class test::HpackHeaderTablePeer;
+
+ // Debug visitor my be used to extract debug/internal information
+ // about the HpackHeaderTable as it operates.
+ //
+ // Most HpackHeaderTable implementations do not need to bother with
+ // this interface at all.
+ class DebugVisitorInterface {
+ public:
+ virtual ~DebugVisitorInterface() {}
+
+ // |OnNewEntry()| and |OnUseEntry()| can be used together to
+ // gather data about the distribution of time intervals between
+ // creation and reference of entries in the dynamic table. The
+ // data is desired to sanity check a proposed extension to HPACK
+ // for QUIC that would eliminate inter-stream head of line
+ // blocking (due to standard HPACK). The visitor should return
+ // the current time from |OnNewEntry()|, which will be passed
+ // to |OnUseEntry()| each time that particular entry is used to
+ // emit an indexed representation.
+ virtual int64_t OnNewEntry(const HpackEntry& entry) = 0;
+ virtual void OnUseEntry(const HpackEntry& entry) = 0;
+ };
+
+ // HpackHeaderTable takes advantage of the deque property that references
+ // remain valid, so long as insertions & deletions are at the head & tail.
+ // This precludes the use of base::circular_deque.
+ //
+ // If this changes (we want to change to circular_deque or we start to drop
+ // entries from the middle of the table), this should to be a std::list, in
+ // which case |*_index_| can be trivially extended to map to list iterators.
+ using EntryTable = std::deque<HpackEntry>;
+
+ struct SPDY_EXPORT_PRIVATE EntryHasher {
+ size_t operator()(const HpackEntry* entry) const;
+ };
+ struct SPDY_EXPORT_PRIVATE EntriesEq {
+ bool operator()(const HpackEntry* lhs, const HpackEntry* rhs) const;
+ };
+ using UnorderedEntrySet = SpdyHashSet<HpackEntry*, EntryHasher, EntriesEq>;
+ using NameToEntryMap =
+ SpdyHashMap<SpdyStringPiece, const HpackEntry*, SpdyStringPieceHash>;
+
+ HpackHeaderTable();
+ HpackHeaderTable(const HpackHeaderTable&) = delete;
+ HpackHeaderTable& operator=(const HpackHeaderTable&) = delete;
+
+ ~HpackHeaderTable();
+
+ // Last-acknowledged value of SETTINGS_HEADER_TABLE_SIZE.
+ size_t settings_size_bound() const { return settings_size_bound_; }
+
+ // Current and maximum estimated byte size of the table, as described in
+ // 4.1. Notably, this is /not/ the number of entries in the table.
+ size_t size() const { return size_; }
+ size_t max_size() const { return max_size_; }
+
+ // Returns the entry matching the index, or NULL.
+ const HpackEntry* GetByIndex(size_t index);
+
+ // Returns the lowest-value entry having |name|, or NULL.
+ const HpackEntry* GetByName(SpdyStringPiece name);
+
+ // Returns the lowest-index matching entry, or NULL.
+ const HpackEntry* GetByNameAndValue(SpdyStringPiece name,
+ SpdyStringPiece value);
+
+ // Returns the index of an entry within this header table.
+ size_t IndexOf(const HpackEntry* entry) const;
+
+ // Sets the maximum size of the header table, evicting entries if
+ // necessary as described in 5.2.
+ void SetMaxSize(size_t max_size);
+
+ // Sets the SETTINGS_HEADER_TABLE_SIZE bound of the table. Will call
+ // SetMaxSize() as needed to preserve max_size() <= settings_size_bound().
+ void SetSettingsHeaderTableSize(size_t settings_size);
+
+ // Determine the set of entries which would be evicted by the insertion
+ // of |name| & |value| into the table, as per section 4.4. No eviction
+ // actually occurs. The set is returned via range [begin_out, end_out).
+ void EvictionSet(SpdyStringPiece name,
+ SpdyStringPiece value,
+ EntryTable::iterator* begin_out,
+ EntryTable::iterator* end_out);
+
+ // Adds an entry for the representation, evicting entries as needed. |name|
+ // and |value| must not be owned by an entry which could be evicted. The
+ // added HpackEntry is returned, or NULL is returned if all entries were
+ // evicted and the empty table is of insufficent size for the representation.
+ const HpackEntry* TryAddEntry(SpdyStringPiece name, SpdyStringPiece value);
+
+ void DebugLogTableState() const SPDY_UNUSED;
+
+ void set_debug_visitor(std::unique_ptr<DebugVisitorInterface> visitor) {
+ debug_visitor_ = std::move(visitor);
+ }
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ // Returns number of evictions required to enter |name| & |value|.
+ size_t EvictionCountForEntry(SpdyStringPiece name,
+ SpdyStringPiece value) const;
+
+ // Returns number of evictions required to reclaim |reclaim_size| table size.
+ size_t EvictionCountToReclaim(size_t reclaim_size) const;
+
+ // Evicts |count| oldest entries from the table.
+ void Evict(size_t count);
+
+ // |static_entries_|, |static_index_|, and |static_name_index_| are owned by
+ // HpackStaticTable singleton.
+
+ // Tracks HpackEntries by index.
+ const EntryTable& static_entries_;
+ EntryTable dynamic_entries_;
+
+ // Tracks the unique HpackEntry for a given header name and value.
+ const UnorderedEntrySet& static_index_;
+
+ // Tracks the first static entry for each name in the static table.
+ const NameToEntryMap& static_name_index_;
+
+ // Tracks the most recently inserted HpackEntry for a given header name and
+ // value.
+ UnorderedEntrySet dynamic_index_;
+
+ // Tracks the most recently inserted HpackEntry for a given header name.
+ NameToEntryMap dynamic_name_index_;
+
+ // Last acknowledged value for SETTINGS_HEADER_TABLE_SIZE.
+ size_t settings_size_bound_;
+
+ // Estimated current and maximum byte size of the table.
+ // |max_size_| <= |settings_size_bound_|
+ size_t size_;
+ size_t max_size_;
+
+ // Total number of table insertions which have occurred. Referenced by
+ // IndexOf() for determination of an HpackEntry's table index.
+ size_t total_insertions_;
+
+ std::unique_ptr<DebugVisitorInterface> debug_visitor_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_HEADER_TABLE_H_
diff --git a/spdy/core/hpack/hpack_header_table_test.cc b/spdy/core/hpack/hpack_header_table_test.cc
new file mode 100644
index 0000000..b032aba
--- /dev/null
+++ b/spdy/core/hpack/hpack_header_table_test.cc
@@ -0,0 +1,446 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <set>
+#include <vector>
+
+#include "base/macros.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+
+namespace spdy {
+
+using std::distance;
+
+namespace test {
+
+class HpackHeaderTablePeer {
+ public:
+ explicit HpackHeaderTablePeer(HpackHeaderTable* table) : table_(table) {}
+
+ const HpackHeaderTable::EntryTable& dynamic_entries() {
+ return table_->dynamic_entries_;
+ }
+ const HpackHeaderTable::EntryTable& static_entries() {
+ return table_->static_entries_;
+ }
+ size_t index_size() {
+ return table_->static_index_.size() + table_->dynamic_index_.size();
+ }
+ std::vector<HpackEntry*> EvictionSet(SpdyStringPiece name,
+ SpdyStringPiece value) {
+ HpackHeaderTable::EntryTable::iterator begin, end;
+ table_->EvictionSet(name, value, &begin, &end);
+ std::vector<HpackEntry*> result;
+ for (; begin != end; ++begin) {
+ result.push_back(&(*begin));
+ }
+ return result;
+ }
+ size_t total_insertions() { return table_->total_insertions_; }
+ size_t dynamic_entries_count() { return table_->dynamic_entries_.size(); }
+ size_t EvictionCountForEntry(SpdyStringPiece name, SpdyStringPiece value) {
+ return table_->EvictionCountForEntry(name, value);
+ }
+ size_t EvictionCountToReclaim(size_t reclaim_size) {
+ return table_->EvictionCountToReclaim(reclaim_size);
+ }
+ void Evict(size_t count) { return table_->Evict(count); }
+
+ void AddDynamicEntry(SpdyStringPiece name, SpdyStringPiece value) {
+ table_->dynamic_entries_.push_back(
+ HpackEntry(name, value, false, table_->total_insertions_++));
+ }
+
+ private:
+ HpackHeaderTable* table_;
+};
+
+} // namespace test
+
+namespace {
+
+class HpackHeaderTableTest : public ::testing::Test {
+ protected:
+ typedef std::vector<HpackEntry> HpackEntryVector;
+
+ HpackHeaderTableTest() : table_(), peer_(&table_) {}
+
+ // Returns an entry whose Size() is equal to the given one.
+ static HpackEntry MakeEntryOfSize(uint32_t size) {
+ EXPECT_GE(size, HpackEntry::kSizeOverhead);
+ SpdyString name((size - HpackEntry::kSizeOverhead) / 2, 'n');
+ SpdyString value(size - HpackEntry::kSizeOverhead - name.size(), 'v');
+ HpackEntry entry(name, value, false, 0);
+ EXPECT_EQ(size, entry.Size());
+ return entry;
+ }
+
+ // Returns a vector of entries whose total size is equal to the given
+ // one.
+ static HpackEntryVector MakeEntriesOfTotalSize(uint32_t total_size) {
+ EXPECT_GE(total_size, HpackEntry::kSizeOverhead);
+ uint32_t entry_size = HpackEntry::kSizeOverhead;
+ uint32_t remaining_size = total_size;
+ HpackEntryVector entries;
+ while (remaining_size > 0) {
+ EXPECT_LE(entry_size, remaining_size);
+ entries.push_back(MakeEntryOfSize(entry_size));
+ remaining_size -= entry_size;
+ entry_size = std::min(remaining_size, entry_size + 32);
+ }
+ return entries;
+ }
+
+ // Adds the given vector of entries to the given header table,
+ // expecting no eviction to happen.
+ void AddEntriesExpectNoEviction(const HpackEntryVector& entries) {
+ for (auto it = entries.begin(); it != entries.end(); ++it) {
+ HpackHeaderTable::EntryTable::iterator begin, end;
+
+ table_.EvictionSet(it->name(), it->value(), &begin, &end);
+ EXPECT_EQ(0, distance(begin, end));
+
+ const HpackEntry* entry = table_.TryAddEntry(it->name(), it->value());
+ EXPECT_NE(entry, static_cast<HpackEntry*>(nullptr));
+ }
+
+ for (size_t i = 0; i != entries.size(); ++i) {
+ // Static table has 61 entries, dynamic entries follow those.
+ size_t index = 61 + entries.size() - i;
+ const HpackEntry* entry = table_.GetByIndex(index);
+ EXPECT_EQ(entries[i].name(), entry->name());
+ EXPECT_EQ(entries[i].value(), entry->value());
+ EXPECT_EQ(index, table_.IndexOf(entry));
+ }
+ }
+
+ HpackEntry DynamicEntry(const SpdyString& name, const SpdyString& value) {
+ peer_.AddDynamicEntry(name, value);
+ return peer_.dynamic_entries().back();
+ }
+
+ HpackHeaderTable table_;
+ test::HpackHeaderTablePeer peer_;
+};
+
+TEST_F(HpackHeaderTableTest, StaticTableInitialization) {
+ EXPECT_EQ(0u, table_.size());
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.max_size());
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
+
+ EXPECT_EQ(0u, peer_.dynamic_entries_count());
+ EXPECT_EQ(peer_.static_entries().size(), peer_.total_insertions());
+
+ // Static entries have been populated and inserted into the table & index.
+ EXPECT_NE(0u, peer_.static_entries().size());
+ EXPECT_EQ(peer_.index_size(), peer_.static_entries().size());
+ for (size_t i = 0; i != peer_.static_entries().size(); ++i) {
+ const HpackEntry* entry = &peer_.static_entries()[i];
+
+ EXPECT_TRUE(entry->IsStatic());
+ EXPECT_EQ(entry, table_.GetByIndex(i + 1));
+ EXPECT_EQ(entry, table_.GetByNameAndValue(entry->name(), entry->value()));
+ }
+}
+
+TEST_F(HpackHeaderTableTest, BasicDynamicEntryInsertionAndEviction) {
+ size_t static_count = peer_.total_insertions();
+ const HpackEntry* first_static_entry = table_.GetByIndex(1);
+
+ EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
+
+ const HpackEntry* entry = table_.TryAddEntry("header-key", "Header Value");
+ EXPECT_EQ("header-key", entry->name());
+ EXPECT_EQ("Header Value", entry->value());
+ EXPECT_FALSE(entry->IsStatic());
+
+ // Table counts were updated appropriately.
+ EXPECT_EQ(entry->Size(), table_.size());
+ EXPECT_EQ(1u, peer_.dynamic_entries_count());
+ EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
+ EXPECT_EQ(static_count + 1, peer_.total_insertions());
+ EXPECT_EQ(static_count + 1, peer_.index_size());
+
+ // Index() of entries reflects the insertion.
+ EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
+ // Static table has 61 entries.
+ EXPECT_EQ(62u, table_.IndexOf(entry));
+ EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
+ EXPECT_EQ(entry, table_.GetByIndex(62));
+
+ // Evict |entry|. Table counts are again updated appropriately.
+ peer_.Evict(1);
+ EXPECT_EQ(0u, table_.size());
+ EXPECT_EQ(0u, peer_.dynamic_entries_count());
+ EXPECT_EQ(peer_.dynamic_entries().size(), peer_.dynamic_entries_count());
+ EXPECT_EQ(static_count + 1, peer_.total_insertions());
+ EXPECT_EQ(static_count, peer_.index_size());
+
+ // Index() of |first_static_entry| reflects the eviction.
+ EXPECT_EQ(1u, table_.IndexOf(first_static_entry));
+ EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
+}
+
+TEST_F(HpackHeaderTableTest, EntryIndexing) {
+ const HpackEntry* first_static_entry = table_.GetByIndex(1);
+
+ // Static entries are queryable by name & value.
+ EXPECT_EQ(first_static_entry, table_.GetByName(first_static_entry->name()));
+ EXPECT_EQ(first_static_entry,
+ table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
+
+ // Create a mix of entries which duplicate names, and names & values of both
+ // dynamic and static entries.
+ const HpackEntry* entry1 = table_.TryAddEntry(first_static_entry->name(),
+ first_static_entry->value());
+ const HpackEntry* entry2 =
+ table_.TryAddEntry(first_static_entry->name(), "Value Four");
+ const HpackEntry* entry3 = table_.TryAddEntry("key-1", "Value One");
+ const HpackEntry* entry4 = table_.TryAddEntry("key-2", "Value Three");
+ const HpackEntry* entry5 = table_.TryAddEntry("key-1", "Value Two");
+ const HpackEntry* entry6 = table_.TryAddEntry("key-2", "Value Three");
+ const HpackEntry* entry7 = table_.TryAddEntry("key-2", "Value Four");
+
+ // Entries are queryable under their current index.
+ EXPECT_EQ(entry7, table_.GetByIndex(62));
+ EXPECT_EQ(entry6, table_.GetByIndex(63));
+ EXPECT_EQ(entry5, table_.GetByIndex(64));
+ EXPECT_EQ(entry4, table_.GetByIndex(65));
+ EXPECT_EQ(entry3, table_.GetByIndex(66));
+ EXPECT_EQ(entry2, table_.GetByIndex(67));
+ EXPECT_EQ(entry1, table_.GetByIndex(68));
+ EXPECT_EQ(first_static_entry, table_.GetByIndex(1));
+
+ // Querying by name returns the most recently added matching entry.
+ EXPECT_EQ(entry5, table_.GetByName("key-1"));
+ EXPECT_EQ(entry7, table_.GetByName("key-2"));
+ EXPECT_EQ(entry2->name(),
+ table_.GetByName(first_static_entry->name())->name());
+ EXPECT_EQ(nullptr, table_.GetByName("not-present"));
+
+ // Querying by name & value returns the lowest-index matching entry among
+ // static entries, and the highest-index one among dynamic entries.
+ EXPECT_EQ(entry3, table_.GetByNameAndValue("key-1", "Value One"));
+ EXPECT_EQ(entry5, table_.GetByNameAndValue("key-1", "Value Two"));
+ EXPECT_EQ(entry6, table_.GetByNameAndValue("key-2", "Value Three"));
+ EXPECT_EQ(entry7, table_.GetByNameAndValue("key-2", "Value Four"));
+ EXPECT_EQ(first_static_entry,
+ table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
+ EXPECT_EQ(entry2,
+ table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
+ EXPECT_EQ(nullptr, table_.GetByNameAndValue("key-1", "Not Present"));
+ EXPECT_EQ(nullptr, table_.GetByNameAndValue("not-present", "Value One"));
+
+ // Evict |entry1|. Queries for its name & value now return the static entry.
+ // |entry2| remains queryable.
+ peer_.Evict(1);
+ EXPECT_EQ(first_static_entry,
+ table_.GetByNameAndValue(first_static_entry->name(),
+ first_static_entry->value()));
+ EXPECT_EQ(entry2,
+ table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
+
+ // Evict |entry2|. Queries by its name & value are not found.
+ peer_.Evict(1);
+ EXPECT_EQ(nullptr,
+ table_.GetByNameAndValue(first_static_entry->name(), "Value Four"));
+}
+
+TEST_F(HpackHeaderTableTest, SetSizes) {
+ SpdyString key = "key", value = "value";
+ const HpackEntry* entry1 = table_.TryAddEntry(key, value);
+ const HpackEntry* entry2 = table_.TryAddEntry(key, value);
+ const HpackEntry* entry3 = table_.TryAddEntry(key, value);
+
+ // Set exactly large enough. No Evictions.
+ size_t max_size = entry1->Size() + entry2->Size() + entry3->Size();
+ table_.SetMaxSize(max_size);
+ EXPECT_EQ(3u, peer_.dynamic_entries().size());
+
+ // Set just too small. One eviction.
+ max_size = entry1->Size() + entry2->Size() + entry3->Size() - 1;
+ table_.SetMaxSize(max_size);
+ EXPECT_EQ(2u, peer_.dynamic_entries().size());
+
+ // Changing SETTINGS_HEADER_TABLE_SIZE.
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound());
+ // In production, the size passed to SetSettingsHeaderTableSize is never
+ // larger than table_.settings_size_bound().
+ table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting * 3 + 1);
+ EXPECT_EQ(kDefaultHeaderTableSizeSetting * 3 + 1, table_.max_size());
+
+ // SETTINGS_HEADER_TABLE_SIZE upper-bounds |table_.max_size()|,
+ // and will force evictions.
+ max_size = entry3->Size() - 1;
+ table_.SetSettingsHeaderTableSize(max_size);
+ EXPECT_EQ(max_size, table_.max_size());
+ EXPECT_EQ(max_size, table_.settings_size_bound());
+ EXPECT_EQ(0u, peer_.dynamic_entries().size());
+}
+
+TEST_F(HpackHeaderTableTest, EvictionCountForEntry) {
+ SpdyString key = "key", value = "value";
+ const HpackEntry* entry1 = table_.TryAddEntry(key, value);
+ const HpackEntry* entry2 = table_.TryAddEntry(key, value);
+ size_t entry3_size = HpackEntry::Size(key, value);
+
+ // Just enough capacity for third entry.
+ table_.SetMaxSize(entry1->Size() + entry2->Size() + entry3_size);
+ EXPECT_EQ(0u, peer_.EvictionCountForEntry(key, value));
+ EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value + "x"));
+
+ // No extra capacity. Third entry would force evictions.
+ table_.SetMaxSize(entry1->Size() + entry2->Size());
+ EXPECT_EQ(1u, peer_.EvictionCountForEntry(key, value));
+ EXPECT_EQ(2u, peer_.EvictionCountForEntry(key, value + "x"));
+}
+
+TEST_F(HpackHeaderTableTest, EvictionCountToReclaim) {
+ SpdyString key = "key", value = "value";
+ const HpackEntry* entry1 = table_.TryAddEntry(key, value);
+ const HpackEntry* entry2 = table_.TryAddEntry(key, value);
+
+ EXPECT_EQ(1u, peer_.EvictionCountToReclaim(1));
+ EXPECT_EQ(1u, peer_.EvictionCountToReclaim(entry1->Size()));
+ EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + 1));
+ EXPECT_EQ(2u, peer_.EvictionCountToReclaim(entry1->Size() + entry2->Size()));
+}
+
+// Fill a header table with entries. Make sure the entries are in
+// reverse order in the header table.
+TEST_F(HpackHeaderTableTest, TryAddEntryBasic) {
+ EXPECT_EQ(0u, table_.size());
+ EXPECT_EQ(table_.settings_size_bound(), table_.max_size());
+
+ HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
+
+ // Most of the checks are in AddEntriesExpectNoEviction().
+ AddEntriesExpectNoEviction(entries);
+ EXPECT_EQ(table_.max_size(), table_.size());
+ EXPECT_EQ(table_.settings_size_bound(), table_.size());
+}
+
+// Fill a header table with entries, and then ramp the table's max
+// size down to evict an entry one at a time. Make sure the eviction
+// happens as expected.
+TEST_F(HpackHeaderTableTest, SetMaxSize) {
+ HpackEntryVector entries =
+ MakeEntriesOfTotalSize(kDefaultHeaderTableSizeSetting / 2);
+ AddEntriesExpectNoEviction(entries);
+
+ for (auto it = entries.begin(); it != entries.end(); ++it) {
+ size_t expected_count = distance(it, entries.end());
+ EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
+
+ table_.SetMaxSize(table_.size() + 1);
+ EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
+
+ table_.SetMaxSize(table_.size());
+ EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
+
+ --expected_count;
+ table_.SetMaxSize(table_.size() - 1);
+ EXPECT_EQ(expected_count, peer_.dynamic_entries().size());
+ }
+ EXPECT_EQ(0u, table_.size());
+}
+
+// Fill a header table with entries, and then add an entry just big
+// enough to cause eviction of all but one entry. Make sure the
+// eviction happens as expected and the long entry is inserted into
+// the table.
+TEST_F(HpackHeaderTableTest, TryAddEntryEviction) {
+ HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
+ AddEntriesExpectNoEviction(entries);
+
+ const HpackEntry* survivor_entry = table_.GetByIndex(61 + 1);
+ HpackEntry long_entry =
+ MakeEntryOfSize(table_.max_size() - survivor_entry->Size());
+
+ // All dynamic entries but the first are to be evicted.
+ EXPECT_EQ(peer_.dynamic_entries().size() - 1,
+ peer_.EvictionSet(long_entry.name(), long_entry.value()).size());
+
+ const HpackEntry* new_entry =
+ table_.TryAddEntry(long_entry.name(), long_entry.value());
+ EXPECT_EQ(62u, table_.IndexOf(new_entry));
+ EXPECT_EQ(2u, peer_.dynamic_entries().size());
+ EXPECT_EQ(table_.GetByIndex(63), survivor_entry);
+ EXPECT_EQ(table_.GetByIndex(62), new_entry);
+}
+
+// Fill a header table with entries, and then add an entry bigger than
+// the entire table. Make sure no entry remains in the table.
+TEST_F(HpackHeaderTableTest, TryAddTooLargeEntry) {
+ HpackEntryVector entries = MakeEntriesOfTotalSize(table_.max_size());
+ AddEntriesExpectNoEviction(entries);
+
+ const HpackEntry long_entry = MakeEntryOfSize(table_.max_size() + 1);
+
+ // All entries are to be evicted.
+ EXPECT_EQ(peer_.dynamic_entries().size(),
+ peer_.EvictionSet(long_entry.name(), long_entry.value()).size());
+
+ const HpackEntry* new_entry =
+ table_.TryAddEntry(long_entry.name(), long_entry.value());
+ EXPECT_EQ(new_entry, static_cast<HpackEntry*>(nullptr));
+ EXPECT_EQ(0u, peer_.dynamic_entries().size());
+}
+
+TEST_F(HpackHeaderTableTest, EntryNamesDiffer) {
+ HpackEntry entry1("header", "value");
+ HpackEntry entry2("HEADER", "value");
+
+ HpackHeaderTable::EntryHasher hasher;
+ EXPECT_NE(hasher(&entry1), hasher(&entry2));
+
+ HpackHeaderTable::EntriesEq eq;
+ EXPECT_FALSE(eq(&entry1, &entry2));
+}
+
+TEST_F(HpackHeaderTableTest, EntryValuesDiffer) {
+ HpackEntry entry1("header", "value");
+ HpackEntry entry2("header", "VALUE");
+
+ HpackHeaderTable::EntryHasher hasher;
+ EXPECT_NE(hasher(&entry1), hasher(&entry2));
+
+ HpackHeaderTable::EntriesEq eq;
+ EXPECT_FALSE(eq(&entry1, &entry2));
+}
+
+TEST_F(HpackHeaderTableTest, EntriesEqual) {
+ HpackEntry entry1(DynamicEntry("name", "value"));
+ HpackEntry entry2(DynamicEntry("name", "value"));
+
+ HpackHeaderTable::EntryHasher hasher;
+ EXPECT_EQ(hasher(&entry1), hasher(&entry2));
+
+ HpackHeaderTable::EntriesEq eq;
+ EXPECT_TRUE(eq(&entry1, &entry2));
+}
+
+TEST_F(HpackHeaderTableTest, StaticAndDynamicEntriesEqual) {
+ HpackEntry entry1("name", "value");
+ HpackEntry entry2(DynamicEntry("name", "value"));
+
+ HpackHeaderTable::EntryHasher hasher;
+ EXPECT_EQ(hasher(&entry1), hasher(&entry2));
+
+ HpackHeaderTable::EntriesEq eq;
+ EXPECT_TRUE(eq(&entry1, &entry2));
+}
+
+} // namespace
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_huffman_table.cc b/spdy/core/hpack/hpack_huffman_table.cc
new file mode 100644
index 0000000..c917767
--- /dev/null
+++ b/spdy/core/hpack/hpack_huffman_table.cc
@@ -0,0 +1,151 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+
+#include <algorithm>
+#include <cmath>
+#include <limits>
+#include <memory>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+
+namespace spdy {
+
+namespace {
+
+bool SymbolLengthAndIdCompare(const HpackHuffmanSymbol& a,
+ const HpackHuffmanSymbol& b) {
+ if (a.length == b.length) {
+ return a.id < b.id;
+ }
+ return a.length < b.length;
+}
+bool SymbolIdCompare(const HpackHuffmanSymbol& a, const HpackHuffmanSymbol& b) {
+ return a.id < b.id;
+}
+
+} // namespace
+
+HpackHuffmanTable::HpackHuffmanTable() : pad_bits_(0), failed_symbol_id_(0) {}
+
+HpackHuffmanTable::~HpackHuffmanTable() = default;
+
+bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols,
+ size_t symbol_count) {
+ CHECK(!IsInitialized());
+ DCHECK_LE(symbol_count, std::numeric_limits<uint16_t>::max());
+
+ std::vector<Symbol> symbols(symbol_count);
+ // Validate symbol id sequence, and copy into |symbols|.
+ for (uint16_t i = 0; i < symbol_count; i++) {
+ if (i != input_symbols[i].id) {
+ failed_symbol_id_ = i;
+ return false;
+ }
+ symbols[i] = input_symbols[i];
+ }
+ // Order on length and ID ascending, to verify symbol codes are canonical.
+ std::sort(symbols.begin(), symbols.end(), SymbolLengthAndIdCompare);
+ if (symbols[0].code != 0) {
+ failed_symbol_id_ = 0;
+ return false;
+ }
+ for (size_t i = 1; i != symbols.size(); i++) {
+ unsigned code_shift = 32 - symbols[i - 1].length;
+ uint32_t code = symbols[i - 1].code + (1 << code_shift);
+
+ if (code != symbols[i].code) {
+ failed_symbol_id_ = symbols[i].id;
+ return false;
+ }
+ if (code < symbols[i - 1].code) {
+ // An integer overflow occurred. This implies the input
+ // lengths do not represent a valid Huffman code.
+ failed_symbol_id_ = symbols[i].id;
+ return false;
+ }
+ }
+ if (symbols.back().length < 8) {
+ // At least one code (such as an EOS symbol) must be 8 bits or longer.
+ // Without this, some inputs will not be encodable in a whole number
+ // of bytes.
+ return false;
+ }
+ pad_bits_ = static_cast<uint8_t>(symbols.back().code >> 24);
+
+ // Order on symbol ID ascending.
+ std::sort(symbols.begin(), symbols.end(), SymbolIdCompare);
+ BuildEncodeTable(symbols);
+ return true;
+}
+
+void HpackHuffmanTable::BuildEncodeTable(const std::vector<Symbol>& symbols) {
+ for (size_t i = 0; i != symbols.size(); i++) {
+ const Symbol& symbol = symbols[i];
+ CHECK_EQ(i, symbol.id);
+ code_by_id_.push_back(symbol.code);
+ length_by_id_.push_back(symbol.length);
+ }
+}
+
+bool HpackHuffmanTable::IsInitialized() const {
+ return !code_by_id_.empty();
+}
+
+void HpackHuffmanTable::EncodeString(SpdyStringPiece in,
+ HpackOutputStream* out) const {
+ size_t bit_remnant = 0;
+ for (size_t i = 0; i != in.size(); i++) {
+ uint16_t symbol_id = static_cast<uint8_t>(in[i]);
+ CHECK_GT(code_by_id_.size(), symbol_id);
+
+ // Load, and shift code to low bits.
+ unsigned length = length_by_id_[symbol_id];
+ uint32_t code = code_by_id_[symbol_id] >> (32 - length);
+
+ bit_remnant = (bit_remnant + length) % 8;
+
+ if (length > 24) {
+ out->AppendBits(static_cast<uint8_t>(code >> 24), length - 24);
+ length = 24;
+ }
+ if (length > 16) {
+ out->AppendBits(static_cast<uint8_t>(code >> 16), length - 16);
+ length = 16;
+ }
+ if (length > 8) {
+ out->AppendBits(static_cast<uint8_t>(code >> 8), length - 8);
+ length = 8;
+ }
+ out->AppendBits(static_cast<uint8_t>(code), length);
+ }
+ if (bit_remnant != 0) {
+ // Pad current byte as required.
+ out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant);
+ }
+}
+
+size_t HpackHuffmanTable::EncodedSize(SpdyStringPiece in) const {
+ size_t bit_count = 0;
+ for (size_t i = 0; i != in.size(); i++) {
+ uint16_t symbol_id = static_cast<uint8_t>(in[i]);
+ CHECK_GT(code_by_id_.size(), symbol_id);
+
+ bit_count += length_by_id_[symbol_id];
+ }
+ if (bit_count % 8 != 0) {
+ bit_count += 8 - bit_count % 8;
+ }
+ return bit_count / 8;
+}
+
+size_t HpackHuffmanTable::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(code_by_id_) +
+ SpdyEstimateMemoryUsage(length_by_id_);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_huffman_table.h b/spdy/core/hpack/hpack_huffman_table.h
new file mode 100644
index 0000000..80d9e52
--- /dev/null
+++ b/spdy/core/hpack/hpack_huffman_table.h
@@ -0,0 +1,76 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_
+
+#include <cstddef>
+#include <cstdint>
+#include <vector>
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+namespace spdy {
+
+namespace test {
+class HpackHuffmanTablePeer;
+} // namespace test
+
+class HpackOutputStream;
+
+// HpackHuffmanTable encodes string literals using a constructed canonical
+// Huffman code. Once initialized, an instance is read only and may be accessed
+// only through its const interface.
+class SPDY_EXPORT_PRIVATE HpackHuffmanTable {
+ public:
+ friend class test::HpackHuffmanTablePeer;
+
+ typedef HpackHuffmanSymbol Symbol;
+
+ HpackHuffmanTable();
+ ~HpackHuffmanTable();
+
+ // Prepares HpackHuffmanTable to encode the canonical Huffman code as
+ // determined by the given symbols. Must be called exactly once.
+ // Returns false if the input symbols define an invalid coding, and true
+ // otherwise. Symbols must be presented in ascending ID order with no gaps,
+ // and |symbol_count| must fit in a uint16_t.
+ bool Initialize(const Symbol* input_symbols, size_t symbol_count);
+
+ // Returns whether Initialize() has been successfully called.
+ bool IsInitialized() const;
+
+ // Encodes the input string to the output stream using the table's Huffman
+ // context.
+ void EncodeString(SpdyStringPiece in, HpackOutputStream* out) const;
+
+ // Returns the encoded size of the input string.
+ size_t EncodedSize(SpdyStringPiece in) const;
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ // Expects symbols ordered on ID ascending.
+ void BuildEncodeTable(const std::vector<Symbol>& symbols);
+
+ // Symbol code and code length, in ascending symbol ID order.
+ // Codes are stored in the most-significant bits of the word.
+ std::vector<uint32_t> code_by_id_;
+ std::vector<uint8_t> length_by_id_;
+
+ // The first 8 bits of the longest code. Applied when generating padding bits.
+ uint8_t pad_bits_;
+
+ // If initialization fails, preserve the symbol ID which failed validation
+ // for examination in tests.
+ uint16_t failed_symbol_id_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_HUFFMAN_TABLE_H_
diff --git a/spdy/core/hpack/hpack_huffman_table_test.cc b/spdy/core/hpack/hpack_huffman_table_test.cc
new file mode 100644
index 0000000..f30926c
--- /dev/null
+++ b/spdy/core/hpack/hpack_huffman_table_test.cc
@@ -0,0 +1,309 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+
+#include <utility>
+
+#include "base/macros.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/http2/hpack/huffman/hpack_huffman_decoder.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_arraysize.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_utils.h"
+
+namespace spdy {
+
+namespace test {
+
+class HpackHuffmanTablePeer {
+ public:
+ explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table)
+ : table_(table) {}
+
+ const std::vector<uint32_t>& code_by_id() const { return table_.code_by_id_; }
+ const std::vector<uint8_t>& length_by_id() const {
+ return table_.length_by_id_;
+ }
+ uint8_t pad_bits() const { return table_.pad_bits_; }
+ uint16_t failed_symbol_id() const { return table_.failed_symbol_id_; }
+
+ private:
+ const HpackHuffmanTable& table_;
+};
+
+namespace {
+
+// Tests of the ability to encode some canonical Huffman code,
+// not just the one defined in the RFC 7541.
+class GenericHuffmanTableTest : public ::testing::Test {
+ protected:
+ GenericHuffmanTableTest() : table_(), peer_(table_) {}
+
+ SpdyString EncodeString(SpdyStringPiece input) {
+ SpdyString result;
+ HpackOutputStream output_stream;
+ table_.EncodeString(input, &output_stream);
+
+ output_stream.TakeString(&result);
+ // Verify EncodedSize() agrees with EncodeString().
+ EXPECT_EQ(result.size(), table_.EncodedSize(input));
+ return result;
+ }
+
+ HpackHuffmanTable table_;
+ HpackHuffmanTablePeer peer_;
+};
+
+TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) {
+ {
+ // Verify eight symbols can be encoded with 3 bits per symbol.
+ HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 3, 0},
+ {0b00100000000000000000000000000000, 3, 1},
+ {0b01000000000000000000000000000000, 3, 2},
+ {0b01100000000000000000000000000000, 3, 3},
+ {0b10000000000000000000000000000000, 3, 4},
+ {0b10100000000000000000000000000000, 3, 5},
+ {0b11000000000000000000000000000000, 3, 6},
+ {0b11100000000000000000000000000000, 8, 7}};
+ HpackHuffmanTable table;
+ EXPECT_TRUE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ }
+ {
+ // But using 2 bits with one symbol overflows the code.
+ HpackHuffmanSymbol code[] = {
+ {0b01000000000000000000000000000000, 3, 0},
+ {0b01100000000000000000000000000000, 3, 1},
+ {0b00000000000000000000000000000000, 2, 2},
+ {0b10000000000000000000000000000000, 3, 3},
+ {0b10100000000000000000000000000000, 3, 4},
+ {0b11000000000000000000000000000000, 3, 5},
+ {0b11100000000000000000000000000000, 3, 6},
+ {0b00000000000000000000000000000000, 8, 7}}; // Overflow.
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id());
+ }
+ {
+ // Verify four symbols can be encoded with incremental bits per symbol.
+ HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0},
+ {0b10000000000000000000000000000000, 2, 1},
+ {0b11000000000000000000000000000000, 3, 2},
+ {0b11100000000000000000000000000000, 8, 3}};
+ HpackHuffmanTable table;
+ EXPECT_TRUE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ }
+ {
+ // But repeating a length overflows the code.
+ HpackHuffmanSymbol code[] = {
+ {0b00000000000000000000000000000000, 1, 0},
+ {0b10000000000000000000000000000000, 2, 1},
+ {0b11000000000000000000000000000000, 2, 2},
+ {0b00000000000000000000000000000000, 8, 3}}; // Overflow.
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id());
+ }
+ {
+ // Symbol IDs must be assigned sequentially with no gaps.
+ HpackHuffmanSymbol code[] = {
+ {0b00000000000000000000000000000000, 1, 0},
+ {0b10000000000000000000000000000000, 2, 1},
+ {0b11000000000000000000000000000000, 3, 1}, // Repeat.
+ {0b11100000000000000000000000000000, 8, 3}};
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id());
+ }
+ {
+ // Canonical codes must begin with zero.
+ HpackHuffmanSymbol code[] = {{0b10000000000000000000000000000000, 4, 0},
+ {0b10010000000000000000000000000000, 4, 1},
+ {0b10100000000000000000000000000000, 4, 2},
+ {0b10110000000000000000000000000000, 8, 3}};
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id());
+ }
+ {
+ // Codes must match the expected canonical sequence.
+ HpackHuffmanSymbol code[] = {
+ {0b00000000000000000000000000000000, 2, 0},
+ {0b01000000000000000000000000000000, 2, 1},
+ {0b11000000000000000000000000000000, 2, 2}, // Code not canonical.
+ {0b10000000000000000000000000000000, 8, 3}};
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id());
+ }
+ {
+ // At least one code must have a length of 8 bits (to ensure pad-ability).
+ HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0},
+ {0b10000000000000000000000000000000, 2, 1},
+ {0b11000000000000000000000000000000, 3, 2},
+ {0b11100000000000000000000000000000, 7, 3}};
+ HpackHuffmanTable table;
+ EXPECT_FALSE(table.Initialize(code, SPDY_ARRAYSIZE(code)));
+ }
+}
+
+TEST_F(GenericHuffmanTableTest, ValidateInternalsWithSmallCode) {
+ HpackHuffmanSymbol code[] = {
+ {0b01100000000000000000000000000000, 4, 0}, // 3rd.
+ {0b01110000000000000000000000000000, 4, 1}, // 4th.
+ {0b00000000000000000000000000000000, 2, 2}, // 1st assigned code.
+ {0b01000000000000000000000000000000, 3, 3}, // 2nd.
+ {0b10000000000000000000000000000000, 5, 4}, // 5th.
+ {0b10001000000000000000000000000000, 5, 5}, // 6th.
+ {0b10011000000000000000000000000000, 8, 6}, // 8th.
+ {0b10010000000000000000000000000000, 5, 7}}; // 7th.
+ EXPECT_TRUE(table_.Initialize(code, SPDY_ARRAYSIZE(code)));
+
+ ASSERT_EQ(SPDY_ARRAYSIZE(code), peer_.code_by_id().size());
+ ASSERT_EQ(SPDY_ARRAYSIZE(code), peer_.length_by_id().size());
+ for (size_t i = 0; i < SPDY_ARRAYSIZE(code); ++i) {
+ EXPECT_EQ(code[i].code, peer_.code_by_id()[i]);
+ EXPECT_EQ(code[i].length, peer_.length_by_id()[i]);
+ }
+
+ EXPECT_EQ(0b10011000, peer_.pad_bits());
+
+ char input_storage[] = {2, 3, 2, 7, 4};
+ SpdyStringPiece input(input_storage, SPDY_ARRAYSIZE(input_storage));
+ // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100.
+ char expect_storage[] = {0b00010001, 0b00101000, 0b01001100};
+ SpdyStringPiece expect(expect_storage, SPDY_ARRAYSIZE(expect_storage));
+ EXPECT_EQ(expect, EncodeString(input));
+}
+
+// Tests of the ability to encode the HPACK Huffman Code, defined in:
+// https://httpwg.github.io/specs/rfc7541.html#huffman.code
+class HpackHuffmanTableTest : public GenericHuffmanTableTest {
+ protected:
+ void SetUp() override {
+ EXPECT_TRUE(table_.Initialize(HpackHuffmanCodeVector().data(),
+ HpackHuffmanCodeVector().size()));
+ EXPECT_TRUE(table_.IsInitialized());
+ }
+
+ // Use http2::HpackHuffmanDecoder for roundtrip tests.
+ void DecodeString(const SpdyString& encoded, SpdyString* out) {
+ http2::HpackHuffmanDecoder decoder;
+ out->clear();
+ EXPECT_TRUE(decoder.Decode(encoded, out));
+ }
+};
+
+TEST_F(HpackHuffmanTableTest, InitializeHpackCode) {
+ EXPECT_EQ(peer_.pad_bits(), 0b11111111); // First 8 bits of EOS.
+}
+
+TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
+ SpdyString buffer;
+ SpdyString test_table[] = {
+ SpdyHexDecode("f1e3c2e5f23a6ba0ab90f4ff"),
+ "www.example.com",
+ SpdyHexDecode("a8eb10649cbf"),
+ "no-cache",
+ SpdyHexDecode("25a849e95ba97d7f"),
+ "custom-key",
+ SpdyHexDecode("25a849e95bb8e8b4bf"),
+ "custom-value",
+ };
+ // Round-trip each test example.
+ for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); i += 2) {
+ const SpdyString& encodedFixture(test_table[i]);
+ const SpdyString& decodedFixture(test_table[i + 1]);
+ DecodeString(encodedFixture, &buffer);
+ EXPECT_EQ(decodedFixture, buffer);
+ buffer = EncodeString(decodedFixture);
+ EXPECT_EQ(encodedFixture, buffer);
+ }
+}
+
+TEST_F(HpackHuffmanTableTest, SpecResponseExamples) {
+ SpdyString buffer;
+ SpdyString test_table[] = {
+ SpdyHexDecode("6402"),
+ "302",
+ SpdyHexDecode("aec3771a4b"),
+ "private",
+ SpdyHexDecode("d07abe941054d444a8200595040b8166"
+ "e082a62d1bff"),
+ "Mon, 21 Oct 2013 20:13:21 GMT",
+ SpdyHexDecode("9d29ad171863c78f0b97c8e9ae82ae43"
+ "d3"),
+ "https://www.example.com",
+ SpdyHexDecode("94e7821dd7f2e6c7b335dfdfcd5b3960"
+ "d5af27087f3672c1ab270fb5291f9587"
+ "316065c003ed4ee5b1063d5007"),
+ "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
+ };
+ // Round-trip each test example.
+ for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); i += 2) {
+ const SpdyString& encodedFixture(test_table[i]);
+ const SpdyString& decodedFixture(test_table[i + 1]);
+ DecodeString(encodedFixture, &buffer);
+ EXPECT_EQ(decodedFixture, buffer);
+ buffer = EncodeString(decodedFixture);
+ EXPECT_EQ(encodedFixture, buffer);
+ }
+}
+
+TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) {
+ for (size_t i = 0; i != 256; i++) {
+ char c = static_cast<char>(i);
+ char storage[3] = {c, c, c};
+ SpdyStringPiece input(storage, SPDY_ARRAYSIZE(storage));
+ SpdyString buffer_in = EncodeString(input);
+ SpdyString buffer_out;
+ DecodeString(buffer_in, &buffer_out);
+ EXPECT_EQ(input, buffer_out);
+ }
+}
+
+TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) {
+ char storage[512];
+ for (size_t i = 0; i != 256; i++) {
+ storage[i] = static_cast<char>(i);
+ storage[511 - i] = static_cast<char>(i);
+ }
+ SpdyStringPiece input(storage, SPDY_ARRAYSIZE(storage));
+ SpdyString buffer_in = EncodeString(input);
+ SpdyString buffer_out;
+ DecodeString(buffer_in, &buffer_out);
+ EXPECT_EQ(input, buffer_out);
+}
+
+TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) {
+ SpdyString test_table[] = {
+ "",
+ "Mon, 21 Oct 2013 20:13:21 GMT",
+ "https://www.example.com",
+ "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
+ SpdyString(1, '\0'),
+ SpdyString("foo\0bar", 7),
+ SpdyString(256, '\0'),
+ };
+ for (size_t i = 0; i != 256; ++i) {
+ // Expand last |test_table| entry to cover all codes.
+ test_table[SPDY_ARRAYSIZE(test_table) - 1][i] = static_cast<char>(i);
+ }
+
+ HpackOutputStream output_stream;
+ SpdyString encoding;
+ for (size_t i = 0; i != SPDY_ARRAYSIZE(test_table); ++i) {
+ table_.EncodeString(test_table[i], &output_stream);
+ output_stream.TakeString(&encoding);
+ EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i]));
+ }
+}
+
+} // namespace
+
+} // namespace test
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_output_stream.cc b/spdy/core/hpack/hpack_output_stream.cc
new file mode 100644
index 0000000..30b5662
--- /dev/null
+++ b/spdy/core/hpack/hpack_output_stream.cc
@@ -0,0 +1,97 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+
+#include <utility>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+
+namespace spdy {
+
+HpackOutputStream::HpackOutputStream() : bit_offset_(0) {}
+
+HpackOutputStream::~HpackOutputStream() = default;
+
+void HpackOutputStream::AppendBits(uint8_t bits, size_t bit_size) {
+ DCHECK_GT(bit_size, 0u);
+ DCHECK_LE(bit_size, 8u);
+ DCHECK_EQ(bits >> bit_size, 0);
+ size_t new_bit_offset = bit_offset_ + bit_size;
+ if (bit_offset_ == 0) {
+ // Buffer ends on a byte boundary.
+ DCHECK_LE(bit_size, 8u);
+ buffer_.append(1, bits << (8 - bit_size));
+ } else if (new_bit_offset <= 8) {
+ // Buffer does not end on a byte boundary but the given bits fit
+ // in the remainder of the last byte.
+ buffer_.back() |= bits << (8 - new_bit_offset);
+ } else {
+ // Buffer does not end on a byte boundary and the given bits do
+ // not fit in the remainder of the last byte.
+ buffer_.back() |= bits >> (new_bit_offset - 8);
+ buffer_.append(1, bits << (16 - new_bit_offset));
+ }
+ bit_offset_ = new_bit_offset % 8;
+}
+
+void HpackOutputStream::AppendPrefix(HpackPrefix prefix) {
+ AppendBits(prefix.bits, prefix.bit_size);
+}
+
+void HpackOutputStream::AppendBytes(SpdyStringPiece buffer) {
+ DCHECK_EQ(bit_offset_, 0u);
+ buffer_.append(buffer.data(), buffer.size());
+}
+
+void HpackOutputStream::AppendUint32(uint32_t I) {
+ // The algorithm below is adapted from the pseudocode in 6.1.
+ size_t N = 8 - bit_offset_;
+ uint8_t max_first_byte = static_cast<uint8_t>((1 << N) - 1);
+ if (I < max_first_byte) {
+ AppendBits(static_cast<uint8_t>(I), N);
+ } else {
+ AppendBits(max_first_byte, N);
+ I -= max_first_byte;
+ while ((I & ~0x7f) != 0) {
+ buffer_.append(1, (I & 0x7f) | 0x80);
+ I >>= 7;
+ }
+ AppendBits(static_cast<uint8_t>(I), 8);
+ }
+}
+
+void HpackOutputStream::TakeString(SpdyString* output) {
+ // This must hold, since all public functions cause the buffer to
+ // end on a byte boundary.
+ DCHECK_EQ(bit_offset_, 0u);
+ buffer_.swap(*output);
+ buffer_.clear();
+ bit_offset_ = 0;
+}
+
+void HpackOutputStream::BoundedTakeString(size_t max_size, SpdyString* output) {
+ if (buffer_.size() > max_size) {
+ // Save off overflow bytes to temporary string (causes a copy).
+ SpdyString overflow(buffer_.data() + max_size, buffer_.size() - max_size);
+
+ // Resize buffer down to the given limit.
+ buffer_.resize(max_size);
+
+ // Give buffer to output string.
+ *output = std::move(buffer_);
+
+ // Reset to contain overflow.
+ buffer_ = std::move(overflow);
+ } else {
+ TakeString(output);
+ }
+}
+
+size_t HpackOutputStream::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(buffer_);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_output_stream.h b/spdy/core/hpack/hpack_output_stream.h
new file mode 100644
index 0000000..450803f
--- /dev/null
+++ b/spdy/core/hpack/hpack_output_stream.h
@@ -0,0 +1,76 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_
+
+#include <cstdint>
+#include <map>
+
+#include "base/macros.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+// All section references below are to
+// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08
+
+namespace spdy {
+
+// An HpackOutputStream handles all the low-level details of encoding
+// header fields.
+class SPDY_EXPORT_PRIVATE HpackOutputStream {
+ public:
+ HpackOutputStream();
+ HpackOutputStream(const HpackOutputStream&) = delete;
+ HpackOutputStream& operator=(const HpackOutputStream&) = delete;
+ ~HpackOutputStream();
+
+ // Appends the lower |bit_size| bits of |bits| to the internal buffer.
+ //
+ // |bit_size| must be > 0 and <= 8. |bits| must not have any bits
+ // set other than the lower |bit_size| bits.
+ void AppendBits(uint8_t bits, size_t bit_size);
+
+ // Simply forwards to AppendBits(prefix.bits, prefix.bit-size).
+ void AppendPrefix(HpackPrefix prefix);
+
+ // Directly appends |buffer|.
+ void AppendBytes(SpdyStringPiece buffer);
+
+ // Appends the given integer using the representation described in
+ // 6.1. If the internal buffer ends on a byte boundary, the prefix
+ // length N is taken to be 8; otherwise, it is taken to be the
+ // number of bits to the next byte boundary.
+ //
+ // It is guaranteed that the internal buffer will end on a byte
+ // boundary after this function is called.
+ void AppendUint32(uint32_t I);
+
+ // Swaps the internal buffer with |output|, then resets state.
+ void TakeString(SpdyString* output);
+
+ // Gives up to |max_size| bytes of the internal buffer to |output|. Resets
+ // internal state with the overflow.
+ void BoundedTakeString(size_t max_size, SpdyString* output);
+
+ // Size in bytes of stream's internal buffer.
+ size_t size() const { return buffer_.size(); }
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ // The internal bit buffer.
+ SpdyString buffer_;
+
+ // If 0, the buffer ends on a byte boundary. If non-zero, the buffer
+ // ends on the nth most significant bit. Guaranteed to be < 8.
+ size_t bit_offset_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_OUTPUT_STREAM_H_
diff --git a/spdy/core/hpack/hpack_output_stream_test.cc b/spdy/core/hpack/hpack_output_stream_test.cc
new file mode 100644
index 0000000..823c41b
--- /dev/null
+++ b/spdy/core/hpack/hpack_output_stream_test.cc
@@ -0,0 +1,276 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+
+#include <cstddef>
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace spdy {
+
+namespace {
+
+// Make sure that AppendBits() appends bits starting from the most
+// significant bit, and that it can handle crossing a byte boundary.
+TEST(HpackOutputStreamTest, AppendBits) {
+ HpackOutputStream output_stream;
+ SpdyString expected_str;
+
+ output_stream.AppendBits(0x1, 1);
+ expected_str.append(1, 0x00);
+ expected_str.back() |= (0x1 << 7);
+
+ output_stream.AppendBits(0x0, 1);
+
+ output_stream.AppendBits(0x3, 2);
+ *expected_str.rbegin() |= (0x3 << 4);
+
+ output_stream.AppendBits(0x0, 2);
+
+ // Byte-crossing append.
+ output_stream.AppendBits(0x7, 3);
+ *expected_str.rbegin() |= (0x7 >> 1);
+ expected_str.append(1, 0x00);
+ expected_str.back() |= (0x7 << 7);
+
+ output_stream.AppendBits(0x0, 7);
+
+ SpdyString str;
+ output_stream.TakeString(&str);
+ EXPECT_EQ(expected_str, str);
+}
+
+// Utility function to return I as a string encoded with an N-bit
+// prefix.
+SpdyString EncodeUint32(uint8_t N, uint32_t I) {
+ HpackOutputStream output_stream;
+ if (N < 8) {
+ output_stream.AppendBits(0x00, 8 - N);
+ }
+ output_stream.AppendUint32(I);
+ SpdyString str;
+ output_stream.TakeString(&str);
+ return str;
+}
+
+// The {Number}ByteIntegersEightBitPrefix tests below test that
+// certain integers are encoded correctly with an 8-bit prefix in
+// exactly {Number} bytes.
+
+TEST(HpackOutputStreamTest, OneByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(8, 0x00));
+ EXPECT_EQ("\x7f", EncodeUint32(8, 0x7f));
+ // Maximum.
+ EXPECT_EQ("\xfe", EncodeUint32(8, 0xfe));
+}
+
+TEST(HpackOutputStreamTest, TwoByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ(SpdyString("\xff\x00", 2), EncodeUint32(8, 0xff));
+ EXPECT_EQ("\xff\x01", EncodeUint32(8, 0x0100));
+ // Maximum.
+ EXPECT_EQ("\xff\x7f", EncodeUint32(8, 0x017e));
+}
+
+TEST(HpackOutputStreamTest, ThreeByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ("\xff\x80\x01", EncodeUint32(8, 0x017f));
+ EXPECT_EQ("\xff\x80\x1e", EncodeUint32(8, 0x0fff));
+ // Maximum.
+ EXPECT_EQ("\xff\xff\x7f", EncodeUint32(8, 0x40fe));
+}
+
+TEST(HpackOutputStreamTest, FourByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ("\xff\x80\x80\x01", EncodeUint32(8, 0x40ff));
+ EXPECT_EQ("\xff\x80\xfe\x03", EncodeUint32(8, 0xffff));
+ // Maximum.
+ EXPECT_EQ("\xff\xff\xff\x7f", EncodeUint32(8, 0x002000fe));
+}
+
+TEST(HpackOutputStreamTest, FiveByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ("\xff\x80\x80\x80\x01", EncodeUint32(8, 0x002000ff));
+ EXPECT_EQ("\xff\x80\xfe\xff\x07", EncodeUint32(8, 0x00ffffff));
+ // Maximum.
+ EXPECT_EQ("\xff\xff\xff\xff\x7f", EncodeUint32(8, 0x100000fe));
+}
+
+TEST(HpackOutputStreamTest, SixByteIntegersEightBitPrefix) {
+ // Minimum.
+ EXPECT_EQ("\xff\x80\x80\x80\x80\x01", EncodeUint32(8, 0x100000ff));
+ // Maximum.
+ EXPECT_EQ("\xff\x80\xfe\xff\xff\x0f", EncodeUint32(8, 0xffffffff));
+}
+
+// The {Number}ByteIntegersOneToSevenBitPrefix tests below test that
+// certain integers are encoded correctly with an N-bit prefix in
+// exactly {Number} bytes for N in {1, 2, ..., 7}.
+
+TEST(HpackOutputStreamTest, OneByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(7, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(6, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(5, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(4, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(3, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(2, 0x00));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(1, 0x00));
+
+ // Maximums.
+ EXPECT_EQ("\x7e", EncodeUint32(7, 0x7e));
+ EXPECT_EQ("\x3e", EncodeUint32(6, 0x3e));
+ EXPECT_EQ("\x1e", EncodeUint32(5, 0x1e));
+ EXPECT_EQ("\x0e", EncodeUint32(4, 0x0e));
+ EXPECT_EQ("\x06", EncodeUint32(3, 0x06));
+ EXPECT_EQ("\x02", EncodeUint32(2, 0x02));
+ EXPECT_EQ(SpdyString("\x00", 1), EncodeUint32(1, 0x00));
+}
+
+TEST(HpackOutputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ(SpdyString("\x7f\x00", 2), EncodeUint32(7, 0x7f));
+ EXPECT_EQ(SpdyString("\x3f\x00", 2), EncodeUint32(6, 0x3f));
+ EXPECT_EQ(SpdyString("\x1f\x00", 2), EncodeUint32(5, 0x1f));
+ EXPECT_EQ(SpdyString("\x0f\x00", 2), EncodeUint32(4, 0x0f));
+ EXPECT_EQ(SpdyString("\x07\x00", 2), EncodeUint32(3, 0x07));
+ EXPECT_EQ(SpdyString("\x03\x00", 2), EncodeUint32(2, 0x03));
+ EXPECT_EQ(SpdyString("\x01\x00", 2), EncodeUint32(1, 0x01));
+
+ // Maximums.
+ EXPECT_EQ("\x7f\x7f", EncodeUint32(7, 0xfe));
+ EXPECT_EQ("\x3f\x7f", EncodeUint32(6, 0xbe));
+ EXPECT_EQ("\x1f\x7f", EncodeUint32(5, 0x9e));
+ EXPECT_EQ("\x0f\x7f", EncodeUint32(4, 0x8e));
+ EXPECT_EQ("\x07\x7f", EncodeUint32(3, 0x86));
+ EXPECT_EQ("\x03\x7f", EncodeUint32(2, 0x82));
+ EXPECT_EQ("\x01\x7f", EncodeUint32(1, 0x80));
+}
+
+TEST(HpackOutputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ("\x7f\x80\x01", EncodeUint32(7, 0xff));
+ EXPECT_EQ("\x3f\x80\x01", EncodeUint32(6, 0xbf));
+ EXPECT_EQ("\x1f\x80\x01", EncodeUint32(5, 0x9f));
+ EXPECT_EQ("\x0f\x80\x01", EncodeUint32(4, 0x8f));
+ EXPECT_EQ("\x07\x80\x01", EncodeUint32(3, 0x87));
+ EXPECT_EQ("\x03\x80\x01", EncodeUint32(2, 0x83));
+ EXPECT_EQ("\x01\x80\x01", EncodeUint32(1, 0x81));
+
+ // Maximums.
+ EXPECT_EQ("\x7f\xff\x7f", EncodeUint32(7, 0x407e));
+ EXPECT_EQ("\x3f\xff\x7f", EncodeUint32(6, 0x403e));
+ EXPECT_EQ("\x1f\xff\x7f", EncodeUint32(5, 0x401e));
+ EXPECT_EQ("\x0f\xff\x7f", EncodeUint32(4, 0x400e));
+ EXPECT_EQ("\x07\xff\x7f", EncodeUint32(3, 0x4006));
+ EXPECT_EQ("\x03\xff\x7f", EncodeUint32(2, 0x4002));
+ EXPECT_EQ("\x01\xff\x7f", EncodeUint32(1, 0x4000));
+}
+
+TEST(HpackOutputStreamTest, FourByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ("\x7f\x80\x80\x01", EncodeUint32(7, 0x407f));
+ EXPECT_EQ("\x3f\x80\x80\x01", EncodeUint32(6, 0x403f));
+ EXPECT_EQ("\x1f\x80\x80\x01", EncodeUint32(5, 0x401f));
+ EXPECT_EQ("\x0f\x80\x80\x01", EncodeUint32(4, 0x400f));
+ EXPECT_EQ("\x07\x80\x80\x01", EncodeUint32(3, 0x4007));
+ EXPECT_EQ("\x03\x80\x80\x01", EncodeUint32(2, 0x4003));
+ EXPECT_EQ("\x01\x80\x80\x01", EncodeUint32(1, 0x4001));
+
+ // Maximums.
+ EXPECT_EQ("\x7f\xff\xff\x7f", EncodeUint32(7, 0x20007e));
+ EXPECT_EQ("\x3f\xff\xff\x7f", EncodeUint32(6, 0x20003e));
+ EXPECT_EQ("\x1f\xff\xff\x7f", EncodeUint32(5, 0x20001e));
+ EXPECT_EQ("\x0f\xff\xff\x7f", EncodeUint32(4, 0x20000e));
+ EXPECT_EQ("\x07\xff\xff\x7f", EncodeUint32(3, 0x200006));
+ EXPECT_EQ("\x03\xff\xff\x7f", EncodeUint32(2, 0x200002));
+ EXPECT_EQ("\x01\xff\xff\x7f", EncodeUint32(1, 0x200000));
+}
+
+TEST(HpackOutputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ("\x7f\x80\x80\x80\x01", EncodeUint32(7, 0x20007f));
+ EXPECT_EQ("\x3f\x80\x80\x80\x01", EncodeUint32(6, 0x20003f));
+ EXPECT_EQ("\x1f\x80\x80\x80\x01", EncodeUint32(5, 0x20001f));
+ EXPECT_EQ("\x0f\x80\x80\x80\x01", EncodeUint32(4, 0x20000f));
+ EXPECT_EQ("\x07\x80\x80\x80\x01", EncodeUint32(3, 0x200007));
+ EXPECT_EQ("\x03\x80\x80\x80\x01", EncodeUint32(2, 0x200003));
+ EXPECT_EQ("\x01\x80\x80\x80\x01", EncodeUint32(1, 0x200001));
+
+ // Maximums.
+ EXPECT_EQ("\x7f\xff\xff\xff\x7f", EncodeUint32(7, 0x1000007e));
+ EXPECT_EQ("\x3f\xff\xff\xff\x7f", EncodeUint32(6, 0x1000003e));
+ EXPECT_EQ("\x1f\xff\xff\xff\x7f", EncodeUint32(5, 0x1000001e));
+ EXPECT_EQ("\x0f\xff\xff\xff\x7f", EncodeUint32(4, 0x1000000e));
+ EXPECT_EQ("\x07\xff\xff\xff\x7f", EncodeUint32(3, 0x10000006));
+ EXPECT_EQ("\x03\xff\xff\xff\x7f", EncodeUint32(2, 0x10000002));
+ EXPECT_EQ("\x01\xff\xff\xff\x7f", EncodeUint32(1, 0x10000000));
+}
+
+TEST(HpackOutputStreamTest, SixByteIntegersOneToSevenBitPrefixes) {
+ // Minimums.
+ EXPECT_EQ("\x7f\x80\x80\x80\x80\x01", EncodeUint32(7, 0x1000007f));
+ EXPECT_EQ("\x3f\x80\x80\x80\x80\x01", EncodeUint32(6, 0x1000003f));
+ EXPECT_EQ("\x1f\x80\x80\x80\x80\x01", EncodeUint32(5, 0x1000001f));
+ EXPECT_EQ("\x0f\x80\x80\x80\x80\x01", EncodeUint32(4, 0x1000000f));
+ EXPECT_EQ("\x07\x80\x80\x80\x80\x01", EncodeUint32(3, 0x10000007));
+ EXPECT_EQ("\x03\x80\x80\x80\x80\x01", EncodeUint32(2, 0x10000003));
+ EXPECT_EQ("\x01\x80\x80\x80\x80\x01", EncodeUint32(1, 0x10000001));
+
+ // Maximums.
+ EXPECT_EQ("\x7f\x80\xff\xff\xff\x0f", EncodeUint32(7, 0xffffffff));
+ EXPECT_EQ("\x3f\xc0\xff\xff\xff\x0f", EncodeUint32(6, 0xffffffff));
+ EXPECT_EQ("\x1f\xe0\xff\xff\xff\x0f", EncodeUint32(5, 0xffffffff));
+ EXPECT_EQ("\x0f\xf0\xff\xff\xff\x0f", EncodeUint32(4, 0xffffffff));
+ EXPECT_EQ("\x07\xf8\xff\xff\xff\x0f", EncodeUint32(3, 0xffffffff));
+ EXPECT_EQ("\x03\xfc\xff\xff\xff\x0f", EncodeUint32(2, 0xffffffff));
+ EXPECT_EQ("\x01\xfe\xff\xff\xff\x0f", EncodeUint32(1, 0xffffffff));
+}
+
+// Test that encoding an integer with an N-bit prefix preserves the
+// upper (8-N) bits of the first byte.
+TEST(HpackOutputStreamTest, AppendUint32PreservesUpperBits) {
+ HpackOutputStream output_stream;
+ output_stream.AppendBits(0x7f, 7);
+ output_stream.AppendUint32(0x01);
+ SpdyString str;
+ output_stream.TakeString(&str);
+ EXPECT_EQ(SpdyString("\xff\x00", 2), str);
+}
+
+TEST(HpackOutputStreamTest, AppendBytes) {
+ HpackOutputStream output_stream;
+
+ output_stream.AppendBytes("buffer1");
+ output_stream.AppendBytes("buffer2");
+
+ SpdyString str;
+ output_stream.TakeString(&str);
+ EXPECT_EQ("buffer1buffer2", str);
+}
+
+TEST(HpackOutputStreamTest, BoundedTakeString) {
+ HpackOutputStream output_stream;
+
+ output_stream.AppendBytes("buffer12");
+ output_stream.AppendBytes("buffer456");
+
+ SpdyString str;
+ output_stream.BoundedTakeString(9, &str);
+ EXPECT_EQ("buffer12b", str);
+
+ output_stream.AppendBits(0x7f, 7);
+ output_stream.AppendUint32(0x11);
+ output_stream.BoundedTakeString(9, &str);
+ EXPECT_EQ("uffer456\xff", str);
+
+ output_stream.BoundedTakeString(9, &str);
+ EXPECT_EQ("\x10", str);
+}
+
+} // namespace
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_round_trip_test.cc b/spdy/core/hpack/hpack_round_trip_test.cc
new file mode 100644
index 0000000..4b3a848
--- /dev/null
+++ b/spdy/core/hpack/hpack_round_trip_test.cc
@@ -0,0 +1,227 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <cmath>
+#include <cstdint>
+#include <ctime>
+#include <vector>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/http2/test_tools/http2_random.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_decoder_adapter.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_encoder.h"
+#include "net/third_party/quiche/src/spdy/core/spdy_test_utils.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string.h"
+
+namespace spdy {
+namespace test {
+
+namespace {
+
+// Supports testing with the input split at every byte boundary.
+enum InputSizeParam { ALL_INPUT, ONE_BYTE, ZERO_THEN_ONE_BYTE };
+
+class HpackRoundTripTest : public ::testing::TestWithParam<InputSizeParam> {
+ protected:
+ HpackRoundTripTest() : encoder_(ObtainHpackHuffmanTable()), decoder_() {}
+
+ void SetUp() override {
+ // Use a small table size to tickle eviction handling.
+ encoder_.ApplyHeaderTableSizeSetting(256);
+ decoder_.ApplyHeaderTableSizeSetting(256);
+ }
+
+ bool RoundTrip(const SpdyHeaderBlock& header_set) {
+ SpdyString encoded;
+ encoder_.EncodeHeaderSet(header_set, &encoded);
+
+ bool success = true;
+ if (GetParam() == ALL_INPUT) {
+ // Pass all the input to the decoder at once.
+ success = decoder_.HandleControlFrameHeadersData(encoded.data(),
+ encoded.size());
+ } else if (GetParam() == ONE_BYTE) {
+ // Pass the input to the decoder one byte at a time.
+ const char* data = encoded.data();
+ for (size_t ndx = 0; ndx < encoded.size() && success; ++ndx) {
+ success = decoder_.HandleControlFrameHeadersData(data + ndx, 1);
+ }
+ } else if (GetParam() == ZERO_THEN_ONE_BYTE) {
+ // Pass the input to the decoder one byte at a time, but before each
+ // byte pass an empty buffer.
+ const char* data = encoded.data();
+ for (size_t ndx = 0; ndx < encoded.size() && success; ++ndx) {
+ success = (decoder_.HandleControlFrameHeadersData(data + ndx, 0) &&
+ decoder_.HandleControlFrameHeadersData(data + ndx, 1));
+ }
+ } else {
+ ADD_FAILURE() << "Unknown param: " << GetParam();
+ }
+
+ if (success) {
+ success = decoder_.HandleControlFrameHeadersComplete(nullptr);
+ }
+
+ EXPECT_EQ(header_set, decoder_.decoded_block());
+ return success;
+ }
+
+ size_t SampleExponential(size_t mean, size_t sanity_bound) {
+ return std::min<size_t>(-std::log(random_.RandDouble()) * mean,
+ sanity_bound);
+ }
+
+ http2::test::Http2Random random_;
+ HpackEncoder encoder_;
+ HpackDecoderAdapter decoder_;
+};
+
+INSTANTIATE_TEST_CASE_P(Tests,
+ HpackRoundTripTest,
+ ::testing::Values(ALL_INPUT,
+ ONE_BYTE,
+ ZERO_THEN_ONE_BYTE));
+
+TEST_P(HpackRoundTripTest, ResponseFixtures) {
+ {
+ SpdyHeaderBlock headers;
+ headers[":status"] = "302";
+ headers["cache-control"] = "private";
+ headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT";
+ headers["location"] = "https://www.example.com";
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+ {
+ SpdyHeaderBlock headers;
+ headers[":status"] = "200";
+ headers["cache-control"] = "private";
+ headers["date"] = "Mon, 21 Oct 2013 20:13:21 GMT";
+ headers["location"] = "https://www.example.com";
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+ {
+ SpdyHeaderBlock headers;
+ headers[":status"] = "200";
+ headers["cache-control"] = "private";
+ headers["content-encoding"] = "gzip";
+ headers["date"] = "Mon, 21 Oct 2013 20:13:22 GMT";
+ headers["location"] = "https://www.example.com";
+ headers["set-cookie"] =
+ "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;"
+ " max-age=3600; version=1";
+ headers["multivalue"] = SpdyString("foo\0bar", 7);
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+}
+
+TEST_P(HpackRoundTripTest, RequestFixtures) {
+ {
+ SpdyHeaderBlock headers;
+ headers[":authority"] = "www.example.com";
+ headers[":method"] = "GET";
+ headers[":path"] = "/";
+ headers[":scheme"] = "http";
+ headers["cookie"] = "baz=bing; foo=bar";
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+ {
+ SpdyHeaderBlock headers;
+ headers[":authority"] = "www.example.com";
+ headers[":method"] = "GET";
+ headers[":path"] = "/";
+ headers[":scheme"] = "http";
+ headers["cache-control"] = "no-cache";
+ headers["cookie"] = "foo=bar; spam=eggs";
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+ {
+ SpdyHeaderBlock headers;
+ headers[":authority"] = "www.example.com";
+ headers[":method"] = "GET";
+ headers[":path"] = "/index.html";
+ headers[":scheme"] = "https";
+ headers["custom-key"] = "custom-value";
+ headers["cookie"] = "baz=bing; fizzle=fazzle; garbage";
+ headers["multivalue"] = SpdyString("foo\0bar", 7);
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+}
+
+TEST_P(HpackRoundTripTest, RandomizedExamples) {
+ // Grow vectors of names & values, which are seeded with fixtures and then
+ // expanded with dynamically generated data. Samples are taken using the
+ // exponential distribution.
+ std::vector<SpdyString> pseudo_header_names, random_header_names;
+ pseudo_header_names.push_back(":authority");
+ pseudo_header_names.push_back(":path");
+ pseudo_header_names.push_back(":status");
+
+ // TODO(jgraettinger): Enable "cookie" as a name fixture. Crumbs may be
+ // reconstructed in any order, which breaks the simple validation used here.
+
+ std::vector<SpdyString> values;
+ values.push_back("/");
+ values.push_back("/index.html");
+ values.push_back("200");
+ values.push_back("404");
+ values.push_back("");
+ values.push_back("baz=bing; foo=bar; garbage");
+ values.push_back("baz=bing; fizzle=fazzle; garbage");
+
+ for (size_t i = 0; i != 2000; ++i) {
+ SpdyHeaderBlock headers;
+
+ // Choose a random number of headers to add, and of these a random subset
+ // will be HTTP/2 pseudo headers.
+ size_t header_count = 1 + SampleExponential(7, 50);
+ size_t pseudo_header_count =
+ std::min(header_count, 1 + SampleExponential(7, 50));
+ EXPECT_LE(pseudo_header_count, header_count);
+ for (size_t j = 0; j != header_count; ++j) {
+ SpdyString name, value;
+ // Pseudo headers must be added before regular headers.
+ if (j < pseudo_header_count) {
+ // Choose one of the defined pseudo headers at random.
+ size_t name_index = random_.Uniform(pseudo_header_names.size());
+ name = pseudo_header_names[name_index];
+ } else {
+ // Randomly reuse an existing header name, or generate a new one.
+ size_t name_index = SampleExponential(20, 200);
+ if (name_index >= random_header_names.size()) {
+ name = random_.RandString(1 + SampleExponential(5, 30));
+ // A regular header cannot begin with the pseudo header prefix ":".
+ if (name[0] == ':') {
+ name[0] = 'x';
+ }
+ random_header_names.push_back(name);
+ } else {
+ name = random_header_names[name_index];
+ }
+ }
+
+ // Randomly reuse an existing value, or generate a new one.
+ size_t value_index = SampleExponential(20, 200);
+ if (value_index >= values.size()) {
+ SpdyString newvalue = random_.RandString(1 + SampleExponential(15, 75));
+ // Currently order is not preserved in the encoder. In particular,
+ // when a value is decomposed at \0 delimiters, its parts might get
+ // encoded out of order if some but not all of them already exist in
+ // the header table. For now, avoid \0 bytes in values.
+ std::replace(newvalue.begin(), newvalue.end(), '\x00', '\x01');
+ values.push_back(newvalue);
+ value = values.back();
+ } else {
+ value = values[value_index];
+ }
+ headers[name] = value;
+ }
+ EXPECT_TRUE(RoundTrip(headers));
+ }
+}
+
+} // namespace
+
+} // namespace test
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_static_table.cc b/spdy/core/hpack/hpack_static_table.cc
new file mode 100644
index 0000000..14e282e
--- /dev/null
+++ b/spdy/core/hpack/hpack_static_table.cc
@@ -0,0 +1,50 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h"
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_entry.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+namespace spdy {
+
+HpackStaticTable::HpackStaticTable() = default;
+
+HpackStaticTable::~HpackStaticTable() = default;
+
+void HpackStaticTable::Initialize(const HpackStaticEntry* static_entry_table,
+ size_t static_entry_count) {
+ CHECK(!IsInitialized());
+
+ int total_insertions = 0;
+ for (const HpackStaticEntry* it = static_entry_table;
+ it != static_entry_table + static_entry_count; ++it) {
+ static_entries_.push_back(
+ HpackEntry(SpdyStringPiece(it->name, it->name_len),
+ SpdyStringPiece(it->value, it->value_len),
+ true, // is_static
+ total_insertions));
+ HpackEntry* entry = &static_entries_.back();
+ CHECK(static_index_.insert(entry).second);
+ // Multiple static entries may have the same name, so inserts may fail.
+ static_name_index_.insert(std::make_pair(entry->name(), entry));
+
+ ++total_insertions;
+ }
+}
+
+bool HpackStaticTable::IsInitialized() const {
+ return !static_entries_.empty();
+}
+
+size_t HpackStaticTable::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(static_entries_) +
+ SpdyEstimateMemoryUsage(static_index_) +
+ SpdyEstimateMemoryUsage(static_name_index_);
+}
+
+} // namespace spdy
diff --git a/spdy/core/hpack/hpack_static_table.h b/spdy/core/hpack/hpack_static_table.h
new file mode 100644
index 0000000..f354a12
--- /dev/null
+++ b/spdy/core/hpack/hpack_static_table.h
@@ -0,0 +1,54 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_
+#define QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_header_table.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_export.h"
+
+namespace spdy {
+
+struct HpackStaticEntry;
+
+// HpackStaticTable provides |static_entries_| and |static_index_| for HPACK
+// encoding and decoding contexts. Once initialized, an instance is read only
+// and may be accessed only through its const interface. Such an instance may
+// be shared accross multiple HPACK contexts.
+class SPDY_EXPORT_PRIVATE HpackStaticTable {
+ public:
+ HpackStaticTable();
+ ~HpackStaticTable();
+
+ // Prepares HpackStaticTable by filling up static_entries_ and static_index_
+ // from an array of struct HpackStaticEntry. Must be called exactly once.
+ void Initialize(const HpackStaticEntry* static_entry_table,
+ size_t static_entry_count);
+
+ // Returns whether Initialize() has been called.
+ bool IsInitialized() const;
+
+ // Accessors.
+ const HpackHeaderTable::EntryTable& GetStaticEntries() const {
+ return static_entries_;
+ }
+ const HpackHeaderTable::UnorderedEntrySet& GetStaticIndex() const {
+ return static_index_;
+ }
+ const HpackHeaderTable::NameToEntryMap& GetStaticNameIndex() const {
+ return static_name_index_;
+ }
+
+ // Returns the estimate of dynamically allocated memory in bytes.
+ size_t EstimateMemoryUsage() const;
+
+ private:
+ HpackHeaderTable::EntryTable static_entries_;
+ HpackHeaderTable::UnorderedEntrySet static_index_;
+ HpackHeaderTable::NameToEntryMap static_name_index_;
+};
+
+} // namespace spdy
+
+#endif // QUICHE_SPDY_CORE_HPACK_HPACK_STATIC_TABLE_H_
diff --git a/spdy/core/hpack/hpack_static_table_test.cc b/spdy/core/hpack/hpack_static_table_test.cc
new file mode 100644
index 0000000..4550be0
--- /dev/null
+++ b/spdy/core/hpack/hpack_static_table_test.cc
@@ -0,0 +1,60 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_static_table.h"
+
+#include <set>
+#include <vector>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_constants.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_string_piece.h"
+
+namespace spdy {
+
+namespace test {
+
+namespace {
+
+class HpackStaticTableTest : public ::testing::Test {
+ protected:
+ HpackStaticTableTest() : table_() {}
+
+ HpackStaticTable table_;
+};
+
+// Check that an initialized instance has the right number of entries.
+TEST_F(HpackStaticTableTest, Initialize) {
+ EXPECT_FALSE(table_.IsInitialized());
+ table_.Initialize(HpackStaticTableVector().data(),
+ HpackStaticTableVector().size());
+ EXPECT_TRUE(table_.IsInitialized());
+
+ HpackHeaderTable::EntryTable static_entries = table_.GetStaticEntries();
+ EXPECT_EQ(HpackStaticTableVector().size(), static_entries.size());
+
+ HpackHeaderTable::UnorderedEntrySet static_index = table_.GetStaticIndex();
+ EXPECT_EQ(HpackStaticTableVector().size(), static_index.size());
+
+ HpackHeaderTable::NameToEntryMap static_name_index =
+ table_.GetStaticNameIndex();
+ std::set<SpdyStringPiece> names;
+ for (auto* entry : static_index) {
+ names.insert(entry->name());
+ }
+ EXPECT_EQ(names.size(), static_name_index.size());
+}
+
+// Test that ObtainHpackStaticTable returns the same instance every time.
+TEST_F(HpackStaticTableTest, IsSingleton) {
+ const HpackStaticTable* static_table_one = &ObtainHpackStaticTable();
+ const HpackStaticTable* static_table_two = &ObtainHpackStaticTable();
+ EXPECT_EQ(static_table_one, static_table_two);
+}
+
+} // namespace
+
+} // namespace test
+
+} // namespace spdy
