diff options
Diffstat (limited to 'net/spdy/hpack')
30 files changed, 6013 insertions, 0 deletions
diff --git a/net/spdy/hpack/hpack_constants.cc b/net/spdy/hpack/hpack_constants.cc new file mode 100644 index 0000000..28385f9 --- /dev/null +++ b/net/spdy/hpack/hpack_constants.cc @@ -0,0 +1,415 @@ +// 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/spdy/hpack/hpack_constants.h" + +#include <vector> + +#include "base/logging.h" +#include "base/memory/scoped_ptr.h" +#include "base/memory/singleton.h" +#include "net/spdy/hpack/hpack_huffman_table.h" +#include "net/spdy/hpack/hpack_static_table.h" + +namespace net { + +namespace { + +// SharedHpackHuffmanTable is a Singleton wrapping a HpackHuffmanTable +// instance initialized with |kHpackHuffmanCode|. +struct SharedHpackHuffmanTable { + public: + SharedHpackHuffmanTable() { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + scoped_ptr<HpackHuffmanTable> mutable_table(new HpackHuffmanTable()); + CHECK(mutable_table->Initialize(&code[0], code.size())); + CHECK(mutable_table->IsInitialized()); + table.reset(mutable_table.release()); + } + + static SharedHpackHuffmanTable* GetInstance() { + return Singleton<SharedHpackHuffmanTable>::get(); + } + + scoped_ptr<const HpackHuffmanTable> table; +}; + +// SharedHpackStaticTable is a Singleton wrapping a HpackStaticTable +// instance initialized with |kHpackStaticTable|. +struct SharedHpackStaticTable { + public: + SharedHpackStaticTable() { + std::vector<HpackStaticEntry> static_table = HpackStaticTableVector(); + scoped_ptr<HpackStaticTable> mutable_table(new HpackStaticTable()); + mutable_table->Initialize(&static_table[0], static_table.size()); + CHECK(mutable_table->IsInitialized()); + table.reset(mutable_table.release()); + } + + static SharedHpackStaticTable* GetInstance() { + return Singleton<SharedHpackStaticTable>::get(); + } + + scoped_ptr<const HpackStaticTable> table; +}; + +} // namespace + +// 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 +// [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|. +std::vector<HpackHuffmanSymbol> HpackHuffmanCode() { + static const HpackHuffmanSymbol kHpackHuffmanCode[] = { + {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 std::vector<HpackHuffmanSymbol>( + kHpackHuffmanCode, kHpackHuffmanCode + arraysize(kHpackHuffmanCode)); +} + +// The "constructor" for a HpackStaticEntry that computes the lengths at +// compile time. +#define STATIC_ENTRY(name, value) \ + { name, arraysize(name) - 1, value, arraysize(value) - 1 } + +std::vector<HpackStaticEntry> HpackStaticTableVector() { + static const HpackStaticEntry kHpackStaticTable[] = { + 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 std::vector<HpackStaticEntry>( + kHpackStaticTable, kHpackStaticTable + arraysize(kHpackStaticTable)); +} + +#undef STATIC_ENTRY + +const HpackHuffmanTable& ObtainHpackHuffmanTable() { + return *SharedHpackHuffmanTable::GetInstance()->table; +} + +const HpackStaticTable& ObtainHpackStaticTable() { + return *SharedHpackStaticTable::GetInstance()->table; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_constants.h b/net/spdy/hpack/hpack_constants.h new file mode 100644 index 0000000..4110260 --- /dev/null +++ b/net/spdy/hpack/hpack_constants.h @@ -0,0 +1,99 @@ +// 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 NET_SPDY_HPACK_CONSTANTS_H_ +#define NET_SPDY_HPACK_CONSTANTS_H_ + +#include <vector> + +#include "base/basictypes.h" +#include "net/base/net_export.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +// An HpackPrefix signifies |bits| stored in the top |bit_size| bits +// of an octet. +struct HpackPrefix { + uint8 bits; + size_t bit_size; +}; + +// Represents a symbol and its Huffman code (stored in most-significant bits). +struct HpackHuffmanSymbol { + uint32 code; + uint8 length; + uint16 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; + +const uint32 kDefaultHeaderTableSizeSetting = 4096; + +// Largest string literal an HpackDecoder/HpackEncoder will attempt to process +// before returning an error. +const uint32 kDefaultMaxStringLiteralSize = 16 * 1024; + +// Maximum amount of encoded header buffer HpackDecoder will retain before +// returning an error. +// TODO(jgraettinger): Remove with SpdyHeadersHandlerInterface switch. +const uint32 kMaxDecodeBufferSize = 32 * 1024; + +// 6.2: Flag for a string literal that is stored unmodified (i.e., +// without Huffman encoding). +const HpackPrefix kStringLiteralIdentityEncoded = {0x0, 1}; + +// 6.2: Flag for a Huffman-coded string literal. +const HpackPrefix kStringLiteralHuffmanEncoded = {0x1, 1}; + +// 7.1: Opcode for an indexed header field. +const HpackPrefix kIndexedOpcode = {0x1, 1}; + +// 7.2.1: Opcode for a literal header field with incremental indexing. +const HpackPrefix kLiteralIncrementalIndexOpcode = {0x1, 2}; + +// 7.2.2: Opcode for a literal header field without indexing. +const HpackPrefix kLiteralNoIndexOpcode = {0x0, 4}; + +// 7.2.3: Opcode for a literal header field which is never indexed. +const HpackPrefix kLiteralNeverIndexOpcode = {0x1, 4}; + +// 7.3: Opcode for maximum header table size update. Begins a varint-encoded +// table size with a 5-bit prefix. +const HpackPrefix kHeaderTableSizeUpdateOpcode = {0x1, 3}; + +// Returns symbol code table from "Appendix C. Huffman Code". +NET_EXPORT_PRIVATE std::vector<HpackHuffmanSymbol> HpackHuffmanCode(); + +// Returns static table from "Appendix B. Static Table Definition". +NET_EXPORT_PRIVATE 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. +NET_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. +NET_EXPORT_PRIVATE const HpackStaticTable& ObtainHpackStaticTable(); + +// Pseudo-headers start with a colon. (HTTP2 8.1.2.1., HPACK 3.1.) +const char kPseudoHeaderPrefix = ':'; + +} // namespace net + +#endif // NET_SPDY_HPACK_CONSTANTS_H_ diff --git a/net/spdy/hpack/hpack_decoder.cc b/net/spdy/hpack/hpack_decoder.cc new file mode 100644 index 0000000..f82cb76 --- /dev/null +++ b/net/spdy/hpack/hpack_decoder.cc @@ -0,0 +1,221 @@ +// 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/spdy/hpack/hpack_decoder.h" + +#include <utility> + +#include "base/basictypes.h" +#include "base/logging.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_output_stream.h" + +namespace net { + +using base::StringPiece; +using std::string; + +namespace { + +const char kCookieKey[] = "cookie"; + +} // namespace + +HpackDecoder::HpackDecoder(const HpackHuffmanTable& table) + : max_string_literal_size_(kDefaultMaxStringLiteralSize), + regular_header_seen_(false), + huffman_table_(table) {} + +HpackDecoder::~HpackDecoder() {} + +bool HpackDecoder::HandleControlFrameHeadersData(SpdyStreamId id, + const char* headers_data, + size_t headers_data_length) { + decoded_block_.clear(); + + size_t new_size = headers_block_buffer_.size() + headers_data_length; + if (new_size > kMaxDecodeBufferSize) { + return false; + } + headers_block_buffer_.insert(headers_block_buffer_.end(), headers_data, + headers_data + headers_data_length); + return true; +} + +bool HpackDecoder::HandleControlFrameHeadersComplete(SpdyStreamId id, + size_t* compressed_len) { + HpackInputStream input_stream(max_string_literal_size_, + headers_block_buffer_); + regular_header_seen_ = false; + if (compressed_len) { + *compressed_len = headers_block_buffer_.size(); + } + while (input_stream.HasMoreData()) { + if (!DecodeNextOpcode(&input_stream)) { + headers_block_buffer_.clear(); + return false; + } + } + headers_block_buffer_.clear(); + + // Emit the Cookie header, if any crumbles were encountered. + if (!cookie_value_.empty()) { + decoded_block_[kCookieKey] = cookie_value_; + cookie_value_.clear(); + } + return true; +} + +bool HpackDecoder::HandleHeaderRepresentation(StringPiece name, + StringPiece value) { + typedef std::pair<SpdyHeaderBlock::iterator, bool> InsertResult; + + // Fail if pseudo-header follows regular header. + if (name.size() > 0) { + if (name[0] == kPseudoHeaderPrefix) { + if (regular_header_seen_) { + return false; + } + } else { + regular_header_seen_ = true; + } + } + + if (name == kCookieKey) { + if (cookie_value_.empty()) { + cookie_value_.assign(value.data(), value.size()); + } else { + cookie_value_ += "; "; + cookie_value_.insert(cookie_value_.end(), value.begin(), value.end()); + } + } else { + InsertResult result = decoded_block_.insert( + std::make_pair(name.as_string(), value.as_string())); + if (!result.second) { + result.first->second.push_back('\0'); + result.first->second.insert(result.first->second.end(), value.begin(), + value.end()); + } + } + return true; +} + +bool HpackDecoder::DecodeNextOpcode(HpackInputStream* input_stream) { + // Implements 7.1: Indexed Header Field Representation. + if (input_stream->MatchPrefixAndConsume(kIndexedOpcode)) { + return DecodeNextIndexedHeader(input_stream); + } + // Implements 7.2.1: Literal Header Field with Incremental Indexing. + if (input_stream->MatchPrefixAndConsume(kLiteralIncrementalIndexOpcode)) { + return DecodeNextLiteralHeader(input_stream, true); + } + // Implements 7.2.2: Literal Header Field without Indexing. + if (input_stream->MatchPrefixAndConsume(kLiteralNoIndexOpcode)) { + return DecodeNextLiteralHeader(input_stream, false); + } + // Implements 7.2.3: Literal Header Field never Indexed. + // TODO(jgraettinger): Preserve the never-indexed bit. + if (input_stream->MatchPrefixAndConsume(kLiteralNeverIndexOpcode)) { + return DecodeNextLiteralHeader(input_stream, false); + } + // Implements 7.3: Header Table Size Update. + if (input_stream->MatchPrefixAndConsume(kHeaderTableSizeUpdateOpcode)) { + return DecodeNextHeaderTableSizeUpdate(input_stream); + } + // Unrecognized opcode. + return false; +} + +bool HpackDecoder::DecodeNextHeaderTableSizeUpdate( + HpackInputStream* input_stream) { + uint32 size = 0; + if (!input_stream->DecodeNextUint32(&size)) { + return false; + } + if (size > header_table_.settings_size_bound()) { + return false; + } + header_table_.SetMaxSize(size); + return true; +} + +bool HpackDecoder::DecodeNextIndexedHeader(HpackInputStream* input_stream) { + uint32 index = 0; + if (!input_stream->DecodeNextUint32(&index)) { + return false; + } + + const HpackEntry* entry = header_table_.GetByIndex(index); + if (entry == NULL) { + return false; + } + + return HandleHeaderRepresentation(entry->name(), entry->value()); +} + +bool HpackDecoder::DecodeNextLiteralHeader(HpackInputStream* input_stream, + bool should_index) { + StringPiece name; + if (!DecodeNextName(input_stream, &name)) { + return false; + } + + StringPiece value; + if (!DecodeNextStringLiteral(input_stream, false, &value)) { + return false; + } + + if (!HandleHeaderRepresentation(name, value)) { + return false; + } + + if (!should_index) { + return true; + } + + ignore_result(header_table_.TryAddEntry(name, value)); + return true; +} + +bool HpackDecoder::DecodeNextName(HpackInputStream* input_stream, + StringPiece* next_name) { + uint32 index_or_zero = 0; + if (!input_stream->DecodeNextUint32(&index_or_zero)) { + return false; + } + + if (index_or_zero == 0) { + return DecodeNextStringLiteral(input_stream, true, next_name); + } + + const HpackEntry* entry = header_table_.GetByIndex(index_or_zero); + if (entry == NULL) { + return false; + } + if (entry->IsStatic()) { + *next_name = entry->name(); + } else { + // |entry| could be evicted as part of this insertion. Preemptively copy. + key_buffer_.assign(entry->name()); + *next_name = key_buffer_; + } + return true; +} + +bool HpackDecoder::DecodeNextStringLiteral(HpackInputStream* input_stream, + bool is_key, + StringPiece* output) { + if (input_stream->MatchPrefixAndConsume(kStringLiteralHuffmanEncoded)) { + string* buffer = is_key ? &key_buffer_ : &value_buffer_; + bool result = input_stream->DecodeNextHuffmanString(huffman_table_, buffer); + *output = StringPiece(*buffer); + return result; + } + if (input_stream->MatchPrefixAndConsume(kStringLiteralIdentityEncoded)) { + return input_stream->DecodeNextIdentityString(output); + } + return false; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_decoder.h b/net/spdy/hpack/hpack_decoder.h new file mode 100644 index 0000000..cf78b6d --- /dev/null +++ b/net/spdy/hpack/hpack_decoder.h @@ -0,0 +1,132 @@ +// 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 NET_SPDY_HPACK_DECODER_H_ +#define NET_SPDY_HPACK_DECODER_H_ + +#include <map> +#include <string> +#include <vector> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_header_table.h" +#include "net/spdy/hpack/hpack_input_stream.h" +#include "net/spdy/spdy_protocol.h" + +// An HpackDecoder decodes header sets as outlined in +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +class HpackHuffmanTable; + +namespace test { +class HpackDecoderPeer; +} // namespace test + +class NET_EXPORT_PRIVATE HpackDecoder { + public: + friend class test::HpackDecoderPeer; + + // |table| is an initialized HPACK Huffman table, having an + // externally-managed lifetime which spans beyond HpackDecoder. + explicit HpackDecoder(const HpackHuffmanTable& table); + ~HpackDecoder(); + + // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE. + void ApplyHeaderTableSizeSetting(size_t size_setting) { + header_table_.SetSettingsHeaderTableSize(size_setting); + } + + // Called as headers data arrives. Returns false if an error occurred. + // TODO(jgraettinger): A future version of this method will incrementally + // parse and deliver headers via SpdyHeadersHandlerInterface. For now, + // header data is buffered until HandleControlFrameHeadersComplete(). + bool HandleControlFrameHeadersData(SpdyStreamId stream_id, + const char* headers_data, + size_t headers_data_length); + + // Called after a headers 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. TODO(jgraettinger): A + // future version of this method will simply deliver the Cookie + // header (which has been incrementally reconstructed) and notify + // the visitor that the block is finished. For now, this method + // decodes the complete buffered block, and stores results to + // |decoded_block_|. + bool HandleControlFrameHeadersComplete(SpdyStreamId stream_id, + size_t* compressed_len); + + // Accessor for the most recently decoded headers block. Valid until the next + // call to HandleControlFrameHeadersData(). + // TODO(jgraettinger): This was added to facilitate re-encoding the block in + // SPDY3 format for delivery to the SpdyFramer visitor, and will be removed + // with the migration to SpdyHeadersHandlerInterface. + const SpdyHeaderBlock& decoded_block() { return decoded_block_; } + + private: + // Adds the header representation to |decoded_block_|, applying the + // following rules, as per sections 8.1.3.3 & 8.1.3.4 of the HTTP2 draft + // specification: + // - Multiple values of the Cookie header are joined, delmited by '; '. + // This reconstruction is required to properly handle Cookie crumbling. + // - Multiple values of other headers are joined and delimited by '\0'. + // Note that this may be too accomodating, as the sender's HTTP2 layer + // should have already joined and delimited these values. + // + // Returns false if a pseudo-header field follows a regular header one, which + // MUST be treated as malformed, as per sections 8.1.2.1. of the HTTP2 draft + // specification. + // + // TODO(jgraettinger): This method will eventually emit to the + // SpdyHeadersHandlerInterface visitor. + bool HandleHeaderRepresentation(base::StringPiece name, + base::StringPiece value); + + const uint32 max_string_literal_size_; + HpackHeaderTable header_table_; + + // Incrementally reconstructed cookie value. + std::string cookie_value_; + + // TODO(jgraettinger): Buffer for headers data, and storage for the last- + // processed headers block. Both will be removed with the switch to + // SpdyHeadersHandlerInterface. + std::string headers_block_buffer_; + SpdyHeaderBlock decoded_block_; + + // Flag to keep track of having seen a regular header field. + bool regular_header_seen_; + + // Huffman table to be applied to decoded Huffman literals, + // and scratch space for storing those decoded literals. + const HpackHuffmanTable& huffman_table_; + std::string key_buffer_, value_buffer_; + + // Handlers for decoding HPACK opcodes and header representations + // (or parts thereof). These methods return true on success and + // false on error. + bool DecodeNextOpcode(HpackInputStream* input_stream); + bool DecodeNextHeaderTableSizeUpdate(HpackInputStream* input_stream); + bool DecodeNextIndexedHeader(HpackInputStream* input_stream); + bool DecodeNextLiteralHeader(HpackInputStream* input_stream, + bool should_index); + bool DecodeNextName(HpackInputStream* input_stream, + base::StringPiece* next_name); + bool DecodeNextStringLiteral(HpackInputStream* input_stream, + bool is_header_key, // As distinct from a value. + base::StringPiece* output); + + DISALLOW_COPY_AND_ASSIGN(HpackDecoder); +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_DECODER_H_ diff --git a/net/spdy/hpack/hpack_decoder_test.cc b/net/spdy/hpack/hpack_decoder_test.cc new file mode 100644 index 0000000..b20a9b2 --- /dev/null +++ b/net/spdy/hpack/hpack_decoder_test.cc @@ -0,0 +1,672 @@ +// 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/spdy/hpack/hpack_decoder.h" + +#include <map> +#include <string> + +#include "base/basictypes.h" +#include "base/logging.h" +#include "base/strings/string_piece.h" +#include "net/spdy/hpack/hpack_encoder.h" +#include "net/spdy/hpack/hpack_input_stream.h" +#include "net/spdy/hpack/hpack_output_stream.h" +#include "net/spdy/spdy_test_utils.h" +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +namespace test { + +using base::StringPiece; +using std::string; + +class HpackDecoderPeer { + public: + explicit HpackDecoderPeer(HpackDecoder* decoder) : decoder_(decoder) {} + + void HandleHeaderRepresentation(StringPiece name, StringPiece value) { + decoder_->HandleHeaderRepresentation(name, value); + } + bool DecodeNextName(HpackInputStream* in, StringPiece* out) { + return decoder_->DecodeNextName(in, out); + } + HpackHeaderTable* header_table() { return &decoder_->header_table_; } + void set_cookie_value(string value) { decoder_->cookie_value_ = value; } + string cookie_value() { return decoder_->cookie_value_; } + const SpdyHeaderBlock& decoded_block() const { + return decoder_->decoded_block_; + } + const string& headers_block_buffer() const { + return decoder_->headers_block_buffer_; + } + + private: + HpackDecoder* decoder_; +}; + +} // namespace test + +namespace { + +using base::StringPiece; +using std::string; +using test::a2b_hex; + +using testing::ElementsAre; +using testing::Pair; + +const size_t kLiteralBound = 1024; + +class HpackDecoderTest : public ::testing::Test { + protected: + HpackDecoderTest() + : decoder_(ObtainHpackHuffmanTable()), decoder_peer_(&decoder_) {} + + bool DecodeHeaderBlock(StringPiece str) { + return decoder_.HandleControlFrameHeadersData(0, str.data(), str.size()) && + decoder_.HandleControlFrameHeadersComplete(0, nullptr); + } + + const SpdyHeaderBlock& decoded_block() const { + // TODO(jgraettinger): HpackDecoderTest should implement + // SpdyHeadersHandlerInterface, and collect headers for examination. + return decoder_peer_.decoded_block(); + } + + const SpdyHeaderBlock& DecodeBlockExpectingSuccess(StringPiece str) { + EXPECT_TRUE(DecodeHeaderBlock(str)); + return decoded_block(); + } + + void expectEntry(size_t index, + size_t size, + const string& name, + const string& value) { + const HpackEntry* entry = decoder_peer_.header_table()->GetByIndex(index); + EXPECT_EQ(name, entry->name()) << "index " << index; + EXPECT_EQ(value, entry->value()); + EXPECT_EQ(size, entry->Size()); + EXPECT_EQ(index, decoder_peer_.header_table()->IndexOf(entry)); + } + + HpackDecoder decoder_; + test::HpackDecoderPeer decoder_peer_; +}; + +TEST_F(HpackDecoderTest, HandleControlFrameHeadersData) { + // Strings under threshold are concatenated in the buffer. + EXPECT_TRUE( + decoder_.HandleControlFrameHeadersData(0, "small string one", 16)); + EXPECT_TRUE( + decoder_.HandleControlFrameHeadersData(0, "small string two", 16)); + // A string which would push the buffer over the threshold is refused. + EXPECT_FALSE(decoder_.HandleControlFrameHeadersData( + 0, "fails", kMaxDecodeBufferSize - 32 + 1)); + + EXPECT_EQ(decoder_peer_.headers_block_buffer(), + "small string onesmall string two"); +} + +TEST_F(HpackDecoderTest, HandleControlFrameHeadersComplete) { + decoder_peer_.set_cookie_value("foobar=baz"); + + // Incremental cookie buffer should be emitted and cleared. + decoder_.HandleControlFrameHeadersData(0, "\x82\x85", 2); + decoder_.HandleControlFrameHeadersComplete(0, nullptr); + + EXPECT_THAT(decoded_block(), + ElementsAre(Pair(":method", "GET"), Pair(":path", "/index.html"), + Pair("cookie", "foobar=baz"))); + EXPECT_EQ(decoder_peer_.cookie_value(), ""); +} + +TEST_F(HpackDecoderTest, HandleHeaderRepresentation) { + // 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", + string("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(0, nullptr); + + EXPECT_THAT(decoded_block(), + ElementsAre(Pair("cookie", " part 1; part 2 ; part3; fin!"), + Pair("empty", ""), + Pair("empty-joined", string("\0foo\0\0", 6)), + Pair("joineD", string("value 1\0value 2", 15)), + Pair("joined", "not joined"), + Pair("passed-through", string("foo\0baz", 7)))); +} + +// Decoding an encoded name with a valid string literal should work. +TEST_F(HpackDecoderTest, DecodeNextNameLiteral) { + HpackInputStream input_stream(kLiteralBound, StringPiece("\x00\x04name", 6)); + + StringPiece string_piece; + EXPECT_TRUE(decoder_peer_.DecodeNextName(&input_stream, &string_piece)); + EXPECT_EQ("name", string_piece); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +TEST_F(HpackDecoderTest, DecodeNextNameLiteralWithHuffmanEncoding) { + string input = a2b_hex("008825a849e95ba97d7f"); + HpackInputStream input_stream(kLiteralBound, input); + + StringPiece string_piece; + EXPECT_TRUE(decoder_peer_.DecodeNextName(&input_stream, &string_piece)); + EXPECT_EQ("custom-key", string_piece); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +// Decoding an encoded name with a valid index should work. +TEST_F(HpackDecoderTest, DecodeNextNameIndexed) { + HpackInputStream input_stream(kLiteralBound, "\x01"); + + StringPiece string_piece; + EXPECT_TRUE(decoder_peer_.DecodeNextName(&input_stream, &string_piece)); + EXPECT_EQ(":authority", string_piece); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +// Decoding an encoded name with an invalid index should fail. +TEST_F(HpackDecoderTest, DecodeNextNameInvalidIndex) { + // One more than the number of static table entries. + HpackInputStream input_stream(kLiteralBound, "\x3e"); + + StringPiece string_piece; + EXPECT_FALSE(decoder_peer_.DecodeNextName(&input_stream, &string_piece)); +} + +// Decoding indexed static table field should work. +TEST_F(HpackDecoderTest, IndexedHeaderStatic) { + // Reference static table entries #2 and #5. + 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. + SpdyHeaderBlock header_set2 = DecodeBlockExpectingSuccess("\x82"); + SpdyHeaderBlock expected_header_set2; + expected_header_set2[":method"] = "GET"; + EXPECT_EQ(expected_header_set2, header_set2); +} + +TEST_F(HpackDecoderTest, IndexedHeaderDynamic) { + // First header block: add an entry to header table. + 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. + 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. + 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_F(HpackDecoderTest, InvalidIndexedHeader) { + // High-bit set, and a prefix of one more than the number of static entries. + EXPECT_FALSE(DecodeHeaderBlock(StringPiece("\xbe", 1))); +} + +// Test that a header block with a pseudo-header field following a regular one +// is treated as malformed. (HTTP2 draft-14 8.1.2.1., HPACK draft-09 3.1.) + +TEST_F(HpackDecoderTest, InvalidPseudoHeaderPositionStatic) { + // Okay: ":path" (static entry 4) followed by "allow" (static entry 20). + EXPECT_TRUE(DecodeHeaderBlock(a2b_hex("8494"))); + // Malformed: "allow" (static entry 20) followed by ":path" (static entry 4). + EXPECT_FALSE(DecodeHeaderBlock(a2b_hex("9484"))); +} + +TEST_F(HpackDecoderTest, InvalidPseudoHeaderPositionLiteral) { + // Okay: literal ":bar" followed by literal "foo". + EXPECT_TRUE(DecodeHeaderBlock(a2b_hex("40043a626172004003666f6f00"))); + // Malformed: literal "foo" followed by literal ":bar". + EXPECT_FALSE(DecodeHeaderBlock(a2b_hex("4003666f6f0040043a62617200"))); +} + +TEST_F(HpackDecoderTest, ContextUpdateMaximumSize) { + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table()->max_size()); + string 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(StringPiece(input))); + EXPECT_EQ(126u, decoder_peer_.header_table()->max_size()); + } + { + // Maximum-size update with kDefaultHeaderTableSizeSetting. Succeeds. + HpackOutputStream output_stream; + output_stream.AppendPrefix(kHeaderTableSizeUpdateOpcode); + output_stream.AppendUint32(kDefaultHeaderTableSizeSetting); + + output_stream.TakeString(&input); + EXPECT_TRUE(DecodeHeaderBlock(StringPiece(input))); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table()->max_size()); + } + { + // 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(StringPiece(input))); + EXPECT_EQ(kDefaultHeaderTableSizeSetting, + decoder_peer_.header_table()->max_size()); + } +} + +// Decoding two valid encoded literal headers with no indexing should +// work. +TEST_F(HpackDecoderTest, 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"; + SpdyHeaderBlock header_set = + DecodeBlockExpectingSuccess(StringPiece(input, 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_F(HpackDecoderTest, LiteralHeaderIncrementalIndexing) { + const char input[] = "\x44\x0c/sample/path\x40\x06:path2\x0e/sample/path/2"; + SpdyHeaderBlock header_set = + DecodeBlockExpectingSuccess(StringPiece(input, 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_F(HpackDecoderTest, LiteralHeaderWithIndexingInvalidNameIndex) { + decoder_.ApplyHeaderTableSizeSetting(0); + + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(StringPiece("\x7d\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(StringPiece("\x7e\x03ooo"))); +} + +TEST_F(HpackDecoderTest, LiteralHeaderNoIndexingInvalidNameIndex) { + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(StringPiece("\x0f\x2e\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(StringPiece("\x0f\x2f\x03ooo"))); +} + +TEST_F(HpackDecoderTest, LiteralHeaderNeverIndexedInvalidNameIndex) { + // Name is the last static index. Works. + EXPECT_TRUE(DecodeHeaderBlock(StringPiece("\x1f\x2e\x03ooo"))); + // Name is one beyond the last static index. Fails. + EXPECT_FALSE(DecodeHeaderBlock(StringPiece("\x1f\x2f\x03ooo"))); +} + +// Round-tripping the header set from E.2.1 should work. +TEST_F(HpackDecoderTest, BasicE21) { + 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"; + + string 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()); +} + +TEST_F(HpackDecoderTest, SectionD4RequestHuffmanExamples) { + SpdyHeaderBlock header_set; + + // 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 = 15) + // | Huffman encoded: + // f1e3 c2e5 f23a 6ba0 ab90 f4ff | .....:k..... + // | Decoded: + // | www.example.com + // | -> :authority: www.example.com + string first = a2b_hex( + "828684418cf1e3c2e5f23a6ba0ab90f4" + "ff"); + header_set = DecodeBlockExpectingSuccess(first); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":authority", "www.example.com"), Pair(":method", "GET"), + Pair(":path", "/"), Pair(":scheme", "http"))); + + expectEntry(62, 57, ":authority", "www.example.com"); + EXPECT_EQ(57u, decoder_peer_.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 + + string second = a2b_hex("828684be5886a8eb10649cbf"); + header_set = DecodeBlockExpectingSuccess(second); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":authority", "www.example.com"), Pair(":method", "GET"), + Pair(":path", "/"), Pair(":scheme", "http"), + Pair("cache-control", "no-cache"))); + + expectEntry(62, 53, "cache-control", "no-cache"); + expectEntry(63, 57, ":authority", "www.example.com"); + EXPECT_EQ(110u, decoder_peer_.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 + string third = a2b_hex( + "828785bf408825a849e95ba97d7f89" + "25a849e95bb8e8b4bf"); + header_set = DecodeBlockExpectingSuccess(third); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":authority", "www.example.com"), Pair(":method", "GET"), + Pair(":path", "/index.html"), Pair(":scheme", "https"), + Pair("custom-key", "custom-value"))); + + 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_.header_table()->size()); +} + +TEST_F(HpackDecoderTest, SectionD6ResponseHuffmanExamples) { + SpdyHeaderBlock header_set; + decoder_.ApplyHeaderTableSizeSetting(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 + + string first = a2b_hex( + "488264025885aec3771a4b6196d07abe" + "941054d444a8200595040b8166e082a6" + "2d1bff6e919d29ad171863c78f0b97c8" + "e9ae82ae43d3"); + header_set = DecodeBlockExpectingSuccess(first); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":status", "302"), Pair("cache-control", "private"), + Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), + Pair("location", "https://www.example.com"))); + + 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_.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 + string second = a2b_hex("4883640effc1c0bf"); + header_set = DecodeBlockExpectingSuccess(second); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":status", "307"), Pair("cache-control", "private"), + Pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"), + Pair("location", "https://www.example.com"))); + + 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_.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 + string third = a2b_hex( + "88c16196d07abe941054d444a8200595" + "040b8166e084a62d1bffc05a839bd9ab" + "77ad94e7821dd7f2e6c7b335dfdfcd5b" + "3960d5af27087f3672c1ab270fb5291f" + "9587316065c003ed4ee5b1063d5007"); + header_set = DecodeBlockExpectingSuccess(third); + + EXPECT_THAT( + header_set, + ElementsAre(Pair(":status", "200"), Pair("cache-control", "private"), + Pair("content-encoding", "gzip"), + Pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"), + Pair("location", "https://www.example.com"), + Pair("set-cookie", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU;" + " max-age=3600; version=1"))); + + 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_.header_table()->size()); +} + +} // namespace + +} // namespace net diff --git a/net/spdy/hpack/hpack_encoder.cc b/net/spdy/hpack/hpack_encoder.cc new file mode 100644 index 0000000..4509127 --- /dev/null +++ b/net/spdy/hpack/hpack_encoder.cc @@ -0,0 +1,197 @@ +// 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/spdy/hpack/hpack_encoder.h" + +#include <algorithm> + +#include "base/logging.h" +#include "net/spdy/hpack/hpack_header_table.h" +#include "net/spdy/hpack/hpack_huffman_table.h" +#include "net/spdy/hpack/hpack_output_stream.h" + +namespace net { + +using base::StringPiece; +using std::string; + +HpackEncoder::HpackEncoder(const HpackHuffmanTable& table) + : output_stream_(), + allow_huffman_compression_(true), + huffman_table_(table), + char_counts_(NULL), + total_char_counts_(NULL) {} + +HpackEncoder::~HpackEncoder() {} + +bool HpackEncoder::EncodeHeaderSet(const SpdyHeaderBlock& header_set, + string* output) { + // Separate header set into pseudo-headers and regular headers. + Representations pseudo_headers; + Representations regular_headers; + for (const auto& header : header_set) { + if (header.first == "cookie") { + // Note that there can only be one "cookie" header, because header_set is + // a map. + CookieToCrumbs(header, ®ular_headers); + } else if (header.first[0] == kPseudoHeaderPrefix) { + DecomposeRepresentation(header, &pseudo_headers); + } else { + DecomposeRepresentation(header, ®ular_headers); + } + } + + // Encode pseudo-headers. + for (const auto& header : pseudo_headers) { + const HpackEntry* entry = + header_table_.GetByNameAndValue(header.first, header.second); + if (entry != NULL) { + EmitIndex(entry); + } else { + if (header.first == ":authority") { + // :authority is always present and rarely changes, and has moderate + // length, therefore it makes a lot of sense to index (insert in the + // header table). + EmitIndexedLiteral(header); + } else { + // Most common pseudo-header fields are represented in the static table, + // while uncommon ones are small, so do not index them. + EmitNonIndexedLiteral(header); + } + } + } + + // Encode regular headers. + for (const auto& header : regular_headers) { + const HpackEntry* entry = + header_table_.GetByNameAndValue(header.first, header.second); + if (entry != NULL) { + EmitIndex(entry); + } else { + EmitIndexedLiteral(header); + } + } + + output_stream_.TakeString(output); + return true; +} + +bool HpackEncoder::EncodeHeaderSetWithoutCompression( + const SpdyHeaderBlock& header_set, + string* output) { + allow_huffman_compression_ = false; + for (const auto& header : header_set) { + // Note that cookies are not crumbled in this case. + EmitNonIndexedLiteral(header); + } + allow_huffman_compression_ = true; + output_stream_.TakeString(output); + return true; +} + +void HpackEncoder::EmitIndex(const HpackEntry* entry) { + output_stream_.AppendPrefix(kIndexedOpcode); + output_stream_.AppendUint32(header_table_.IndexOf(entry)); +} + +void HpackEncoder::EmitIndexedLiteral(const Representation& representation) { + output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode); + EmitLiteral(representation); + header_table_.TryAddEntry(representation.first, representation.second); +} + +void HpackEncoder::EmitNonIndexedLiteral(const Representation& representation) { + 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 != NULL) { + output_stream_.AppendUint32(header_table_.IndexOf(name_entry)); + } else { + output_stream_.AppendUint32(0); + EmitString(representation.first); + } + EmitString(representation.second); +} + +void HpackEncoder::EmitString(StringPiece str) { + size_t encoded_size = + (!allow_huffman_compression_ ? str.size() + : huffman_table_.EncodedSize(str)); + if (encoded_size < str.size()) { + output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded); + output_stream_.AppendUint32(encoded_size); + huffman_table_.EncodeString(str, &output_stream_); + } else { + output_stream_.AppendPrefix(kStringLiteralIdentityEncoded); + output_stream_.AppendUint32(str.size()); + output_stream_.AppendBytes(str); + } + UpdateCharacterCounts(str); +} + +void HpackEncoder::SetCharCountsStorage(std::vector<size_t>* char_counts, + size_t* total_char_counts) { + CHECK_LE(256u, char_counts->size()); + char_counts_ = char_counts; + total_char_counts_ = total_char_counts; +} + +void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) { + if (char_counts_ == NULL || total_char_counts_ == NULL) { + return; + } + for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) { + ++(*char_counts_)[static_cast<uint8>(*it)]; + } + (*total_char_counts_) += str.size(); +} + +// static +void HpackEncoder::CookieToCrumbs(const Representation& cookie, + Representations* out) { + size_t prior_size = out->size(); + + // 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. + for (size_t pos = 0;;) { + size_t end = cookie.second.find(";", pos); + + if (end == StringPiece::npos) { + out->push_back(std::make_pair(cookie.first, cookie.second.substr(pos))); + break; + } + out->push_back( + std::make_pair(cookie.first, cookie.second.substr(pos, end - pos))); + + // Consume next space if present. + pos = end + 1; + if (pos != cookie.second.size() && cookie.second[pos] == ' ') { + pos++; + } + } + // Sort crumbs and remove duplicates. + std::sort(out->begin() + prior_size, out->end()); + out->erase(std::unique(out->begin() + prior_size, out->end()), out->end()); +} + +// static +void HpackEncoder::DecomposeRepresentation(const Representation& header_field, + Representations* out) { + size_t pos = 0; + size_t end = 0; + while (end != StringPiece::npos) { + end = header_field.second.find('\0', pos); + out->push_back(std::make_pair(header_field.first, + header_field.second.substr(pos, end - pos))); + pos = end + 1; + } +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_encoder.h b/net/spdy/hpack/hpack_encoder.h new file mode 100644 index 0000000..fc85603 --- /dev/null +++ b/net/spdy/hpack/hpack_encoder.h @@ -0,0 +1,103 @@ +// 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 NET_SPDY_HPACK_ENCODER_H_ +#define NET_SPDY_HPACK_ENCODER_H_ + +#include <map> +#include <string> +#include <utility> +#include <vector> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_header_table.h" +#include "net/spdy/hpack/hpack_output_stream.h" +#include "net/spdy/spdy_protocol.h" + +// An HpackEncoder encodes header sets as outlined in +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +class HpackHuffmanTable; + +namespace test { +class HpackEncoderPeer; +} // namespace test + +class NET_EXPORT_PRIVATE HpackEncoder { + public: + friend class test::HpackEncoderPeer; + + // |table| is an initialized HPACK Huffman table, having an + // externally-managed lifetime which spans beyond HpackEncoder. + explicit HpackEncoder(const HpackHuffmanTable& table); + ~HpackEncoder(); + + // Encodes the given header set into the given string. Returns + // whether or not the encoding was successful. + bool EncodeHeaderSet(const SpdyHeaderBlock& header_set, std::string* output); + + // Encodes the given header set into the given string. Only non-indexed + // literal representations are emitted, bypassing the header table. Huffman + // coding is also not used. Returns whether the encoding was successful. + bool EncodeHeaderSetWithoutCompression(const SpdyHeaderBlock& header_set, + std::string* output); + + // 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) { + header_table_.SetSettingsHeaderTableSize(size_setting); + } + + // Sets externally-owned storage for aggregating character counts of emitted + // literal representations. + void SetCharCountsStorage(std::vector<size_t>* char_counts, + size_t* total_char_counts); + + private: + typedef std::pair<base::StringPiece, base::StringPiece> Representation; + typedef std::vector<Representation> Representations; + + // 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(base::StringPiece str); + + void UpdateCharacterCounts(base::StringPiece str); + + // Crumbles a cookie header into sorted, de-duplicated 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); + + HpackHeaderTable header_table_; + HpackOutputStream output_stream_; + + bool allow_huffman_compression_; + const HpackHuffmanTable& huffman_table_; + + // Externally-owned, nullable storage for character counts of literals. + std::vector<size_t>* char_counts_; + size_t* total_char_counts_; + + DISALLOW_COPY_AND_ASSIGN(HpackEncoder); +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_ENCODER_H_ diff --git a/net/spdy/hpack/hpack_encoder_test.cc b/net/spdy/hpack/hpack_encoder_test.cc new file mode 100644 index 0000000..02867cc --- /dev/null +++ b/net/spdy/hpack/hpack_encoder_test.cc @@ -0,0 +1,458 @@ +// 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/spdy/hpack/hpack_encoder.h" + +#include <map> +#include <string> + +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +using base::StringPiece; +using std::string; +using testing::ElementsAre; + +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) {} + + HpackHeaderTable* table() { return &encoder_->header_table_; } + HpackHeaderTablePeer table_peer() { return HpackHeaderTablePeer(table()); } + void set_allow_huffman_compression(bool allow) { + encoder_->allow_huffman_compression_ = allow; + } + void EmitString(StringPiece str) { encoder_->EmitString(str); } + void TakeString(string* out) { encoder_->output_stream_.TakeString(out); } + void UpdateCharacterCounts(StringPiece str) { + encoder_->UpdateCharacterCounts(str); + } + static void CookieToCrumbs(StringPiece cookie, + std::vector<StringPiece>* 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(StringPiece value, + std::vector<StringPiece>* 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); + } + } + + private: + HpackEncoder* encoder_; +}; + +} // namespace test + +namespace { + +using std::map; +using testing::ElementsAre; + +class HpackEncoderTest : public ::testing::Test { + protected: + typedef test::HpackEncoderPeer::Representations Representations; + + HpackEncoderTest() + : encoder_(ObtainHpackHuffmanTable()), + peer_(&encoder_), + static_(peer_.table()->GetByIndex(1)) {} + + void SetUp() override { + // 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()); + + // Disable Huffman coding by default. Most tests don't care about it. + peer_.set_allow_huffman_compression(false); + } + + void ExpectIndex(size_t index) { + expected_.AppendPrefix(kIndexedOpcode); + expected_.AppendUint32(index); + } + void ExpectIndexedLiteral(const HpackEntry* key_entry, StringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(IndexOf(key_entry)); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void ExpectIndexedLiteral(StringPiece name, StringPiece value) { + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(0); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(name.size()); + expected_.AppendBytes(name); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void ExpectNonIndexedLiteral(StringPiece name, StringPiece value) { + expected_.AppendPrefix(kLiteralNoIndexOpcode); + expected_.AppendUint32(0); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(name.size()); + expected_.AppendBytes(name); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(value.size()); + expected_.AppendBytes(value); + } + void CompareWithExpectedEncoding(const SpdyHeaderBlock& header_set) { + string expected_out, actual_out; + expected_.TakeString(&expected_out); + EXPECT_TRUE(encoder_.EncodeHeaderSet(header_set, &actual_out)); + 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_; + + HpackOutputStream expected_; +}; + +TEST_F(HpackEncoderTest, SingleDynamicIndex) { + ExpectIndex(IndexOf(key_2_)); + + SpdyHeaderBlock headers; + headers[key_2_->name()] = key_2_->value(); + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, SingleStaticIndex) { + ExpectIndex(IndexOf(static_)); + + SpdyHeaderBlock headers; + headers[static_->name()] = static_->value(); + CompareWithExpectedEncoding(headers); +} + +TEST_F(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_F(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_F(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_F(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_F(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_F(HpackEncoderTest, CookieHeaderIsCrumbled) { + ExpectIndex(IndexOf(cookie_a_)); + ExpectIndex(IndexOf(cookie_c_)); + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); + + SpdyHeaderBlock headers; + headers["cookie"] = "e=ff; a=bb; c=dd"; + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, StringsDynamicallySelectHuffmanCoding) { + peer_.set_allow_huffman_compression(true); + + // 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("@@@@@@"); + + string expected_out, actual_out; + expected_.TakeString(&expected_out); + peer_.TakeString(&actual_out); + EXPECT_EQ(expected_out, actual_out); +} + +TEST_F(HpackEncoderTest, EncodingWithoutCompression) { + // Implementation should internally disable. + peer_.set_allow_huffman_compression(true); + + ExpectNonIndexedLiteral(":path", "/index.html"); + ExpectNonIndexedLiteral("cookie", "foo=bar; baz=bing"); + ExpectNonIndexedLiteral("hello", "goodbye"); + + SpdyHeaderBlock headers; + headers[":path"] = "/index.html"; + headers["cookie"] = "foo=bar; baz=bing"; + headers["hello"] = "goodbye"; + + string expected_out, actual_out; + expected_.TakeString(&expected_out); + encoder_.EncodeHeaderSetWithoutCompression(headers, &actual_out); + EXPECT_EQ(expected_out, actual_out); +} + +TEST_F(HpackEncoderTest, MultipleEncodingPasses) { + // Pass 1. + { + SpdyHeaderBlock headers; + headers["key1"] = "value1"; + headers["cookie"] = "a=bb"; + + ExpectIndex(IndexOf(cookie_a_)); + ExpectIndex(IndexOf(key_1_)); + 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"; + + ExpectIndex(IndexOf(cookie_c_)); + // This cookie evicts |key1| from the dynamic table. + ExpectIndexedLiteral(peer_.table()->GetByName("cookie"), "e=ff"); + // "key2: value2" + ExpectIndex(65); + + 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"; + + // "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); + // "key2: value2" + ExpectIndexedLiteral("key2", "value2"); + + CompareWithExpectedEncoding(headers); + } +} + +TEST_F(HpackEncoderTest, PseudoHeadersFirst) { + SpdyHeaderBlock headers; + // A pseudo-header to be indexed. + headers[":authority"] = "www.example.com"; + // A pseudo-header that should not be indexed. + headers[":path"] = "/spam/eggs.html"; + // A regular header which precedes ":" alphabetically, should still be encoded + // after pseudo-headers. + headers["-foo"] = "bar"; + headers["foo"] = "bar"; + headers["cookie"] = "c=dd"; + + // Pseudo-headers are encoded in alphabetical order. + // This entry pushes "cookie: a=bb" back to 63. + ExpectIndexedLiteral(peer_.table()->GetByName(":authority"), + "www.example.com"); + ExpectNonIndexedLiteral(":path", "/spam/eggs.html"); + // Regular headers are endoded in alphabetical order. + // This entry pushes "cookie: a=bb" back to 64. + ExpectIndexedLiteral("-foo", "bar"); + ExpectIndex(64); + ExpectIndexedLiteral("foo", "bar"); + CompareWithExpectedEncoding(headers); +} + +TEST_F(HpackEncoderTest, CookieToCrumbs) { + test::HpackEncoderPeer peer(NULL); + std::vector<StringPiece> out; + + // A space after ';' is consumed. All other spaces remain. ';' at beginning + // and end of string produce empty crumbs. Duplicate crumbs are removed. + // 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("", " bing=4", " foo=1", "bar=2 ", "bar=3")); + + peer.CookieToCrumbs(";;foo = bar ;; ;baz =bing", &out); + EXPECT_THAT(out, ElementsAre("", "baz =bing", "foo = bar ")); + + peer.CookieToCrumbs("baz=bing; foo=bar; baz=bing", &out); + EXPECT_THAT(out, ElementsAre("baz=bing", "foo=bar")); + + 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("", "bar", "baz", "bing", "foo")); +} + +TEST_F(HpackEncoderTest, UpdateCharacterCounts) { + std::vector<size_t> counts(256, 0); + size_t total_counts = 0; + encoder_.SetCharCountsStorage(&counts, &total_counts); + + char kTestString[] = + "foo\0\1\xff" + "boo"; + peer_.UpdateCharacterCounts( + StringPiece(kTestString, arraysize(kTestString) - 1)); + + std::vector<size_t> expect(256, 0); + expect[static_cast<uint8>('f')] = 1; + expect[static_cast<uint8>('o')] = 4; + expect[static_cast<uint8>('\0')] = 1; + expect[static_cast<uint8>('\1')] = 1; + expect[static_cast<uint8>('\xff')] = 1; + expect[static_cast<uint8>('b')] = 1; + + EXPECT_EQ(expect, counts); + EXPECT_EQ(9u, total_counts); +} + +TEST_F(HpackEncoderTest, DecomposeRepresentation) { + test::HpackEncoderPeer peer(NULL); + std::vector<StringPiece> out; + + peer.DecomposeRepresentation("", &out); + EXPECT_THAT(out, ElementsAre("")); + + peer.DecomposeRepresentation("foobar", &out); + EXPECT_THAT(out, ElementsAre("foobar")); + + peer.DecomposeRepresentation(StringPiece("foo\0bar", 7), &out); + EXPECT_THAT(out, ElementsAre("foo", "bar")); + + peer.DecomposeRepresentation(StringPiece("\0foo\0bar", 8), &out); + EXPECT_THAT(out, ElementsAre("", "foo", "bar")); + + peer.DecomposeRepresentation(StringPiece("foo\0bar\0", 8), &out); + EXPECT_THAT(out, ElementsAre("foo", "bar", "")); + + peer.DecomposeRepresentation(StringPiece("\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_F(HpackEncoderTest, CrumbleNullByteDelimitedValue) { + SpdyHeaderBlock headers; + // A header field to be crumbled: "spam: foo\0bar". + headers["spam"] = string("foo\0bar", 7); + + ExpectIndexedLiteral("spam", "foo"); + expected_.AppendPrefix(kLiteralIncrementalIndexOpcode); + expected_.AppendUint32(62); + expected_.AppendPrefix(kStringLiteralIdentityEncoded); + expected_.AppendUint32(3); + expected_.AppendBytes("bar"); + CompareWithExpectedEncoding(headers); +} + +} // namespace + +} // namespace net diff --git a/net/spdy/hpack/hpack_entry.cc b/net/spdy/hpack/hpack_entry.cc new file mode 100644 index 0000000..c4c51ba --- /dev/null +++ b/net/spdy/hpack/hpack_entry.cc @@ -0,0 +1,49 @@ +// 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/spdy/hpack/hpack_entry.h" + +#include "base/logging.h" +#include "base/strings/string_number_conversions.h" +#include "net/spdy/hpack/hpack_string_util.h" + +namespace net { + +using base::StringPiece; + +const size_t HpackEntry::kSizeOverhead = 32; + +HpackEntry::HpackEntry(StringPiece name, + StringPiece value, + bool is_static, + size_t insertion_index) + : name_(name.data(), name.size()), + value_(value.data(), value.size()), + insertion_index_(insertion_index), + type_(is_static ? STATIC : DYNAMIC) {} + +HpackEntry::HpackEntry(StringPiece name, StringPiece value) + : name_(name.data(), name.size()), + value_(value.data(), value.size()), + insertion_index_(0), + type_(LOOKUP) {} + +HpackEntry::HpackEntry() : insertion_index_(0), type_(LOOKUP) {} + +HpackEntry::~HpackEntry() {} + +// static +size_t HpackEntry::Size(StringPiece name, StringPiece value) { + return name.size() + value.size() + kSizeOverhead; +} +size_t HpackEntry::Size() const { + return Size(name(), value()); +} + +std::string HpackEntry::GetDebugString() const { + return "{ name: \"" + name_ + "\", value: \"" + value_ + "\", " + + (IsStatic() ? "static" : "dynamic") + " }"; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_entry.h b/net/spdy/hpack/hpack_entry.h new file mode 100644 index 0000000..887b515 --- /dev/null +++ b/net/spdy/hpack/hpack_entry.h @@ -0,0 +1,92 @@ +// 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 NET_SPDY_HPACK_ENTRY_H_ +#define NET_SPDY_HPACK_ENTRY_H_ + +#include <cstddef> +#include <set> +#include <string> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +// A structure for an entry in the static table (3.3.1) +// and the header table (3.3.2). +class NET_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. + HpackEntry(base::StringPiece name, + base::StringPiece 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. + HpackEntry(base::StringPiece name, base::StringPiece value); + + // Creates an entry with empty name and value. Only defined so that + // entries can be stored in STL containers. + HpackEntry(); + + ~HpackEntry(); + + const std::string& name() const { return name_; } + const std::string& value() const { return value_; } + + // 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(base::StringPiece name, base::StringPiece value); + size_t Size() const; + + std::string GetDebugString() const; + + private: + enum EntryType { + LOOKUP, + DYNAMIC, + STATIC, + }; + + // TODO(jgraettinger): Reduce copies, possibly via SpdyPinnableBufferPiece. + std::string name_; + std::string value_; + + // The entry's index in the total set of entries ever inserted into the header + // table. + size_t insertion_index_; + + EntryType type_; +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_ENTRY_H_ diff --git a/net/spdy/hpack/hpack_entry_test.cc b/net/spdy/hpack/hpack_entry_test.cc new file mode 100644 index 0000000..eb7de1c --- /dev/null +++ b/net/spdy/hpack/hpack_entry_test.cc @@ -0,0 +1,126 @@ +// 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/spdy/hpack/hpack_entry.h" + +#include <string> + +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +namespace { + +using std::string; + +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; + } + + string 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 net diff --git a/net/spdy/hpack/hpack_header_table.cc b/net/spdy/hpack/hpack_header_table.cc new file mode 100644 index 0000000..b80116e --- /dev/null +++ b/net/spdy/hpack/hpack_header_table.cc @@ -0,0 +1,206 @@ +// 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/spdy/hpack/hpack_header_table.h" + +#include <algorithm> + +#include "base/logging.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_static_table.h" +#include "net/spdy/hpack/hpack_string_util.h" + +namespace net { + +using base::StringPiece; + +bool HpackHeaderTable::EntryComparator::operator()( + const HpackEntry* lhs, + const HpackEntry* rhs) const { + int result = lhs->name().compare(rhs->name()); + if (result != 0) + return result < 0; + result = lhs->value().compare(rhs->value()); + if (result != 0) + return result < 0; + const size_t lhs_index = lhs->IsLookup() ? 0 : 1 + lhs->InsertionIndex(); + const size_t rhs_index = rhs->IsLookup() ? 0 : 1 + rhs->InsertionIndex(); + DCHECK(lhs == rhs || lhs_index != rhs_index) + << "lhs: (" << lhs->name() << ", " << rhs->value() << ") rhs: (" + << rhs->name() << ", " << rhs->value() << ")" + << " lhs index: " << lhs_index << " rhs index: " << rhs_index; + return lhs_index < rhs_index; +} + +HpackHeaderTable::HpackHeaderTable() + : static_entries_(ObtainHpackStaticTable().GetStaticEntries()), + static_index_(ObtainHpackStaticTable().GetStaticIndex()), + settings_size_bound_(kDefaultHeaderTableSizeSetting), + size_(0), + max_size_(kDefaultHeaderTableSizeSetting), + total_insertions_(static_entries_.size()) {} + +HpackHeaderTable::~HpackHeaderTable() {} + +const HpackEntry* HpackHeaderTable::GetByIndex(size_t index) { + if (index == 0) { + return NULL; + } + index -= 1; + if (index < static_entries_.size()) { + return &static_entries_[index]; + } + index -= static_entries_.size(); + if (index < dynamic_entries_.size()) { + return &dynamic_entries_[index]; + } + return NULL; +} + +const HpackEntry* HpackHeaderTable::GetByName(StringPiece name) { + HpackEntry query(name, ""); + { + OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query); + if (it != static_index_.end() && (*it)->name() == name) { + return *it; + } + } + { + OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query); + if (it != dynamic_index_.end() && (*it)->name() == name) { + return *it; + } + } + return NULL; +} + +const HpackEntry* HpackHeaderTable::GetByNameAndValue(StringPiece name, + StringPiece value) { + HpackEntry query(name, value); + { + OrderedEntrySet::const_iterator it = static_index_.lower_bound(&query); + if (it != static_index_.end() && (*it)->name() == name && + (*it)->value() == value) { + return *it; + } + } + { + OrderedEntrySet::const_iterator it = dynamic_index_.lower_bound(&query); + if (it != dynamic_index_.end() && (*it)->name() == name && + (*it)->value() == value) { + return *it; + } + } + return NULL; +} + +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; + if (settings_size_bound_ < max_size_) { + SetMaxSize(settings_size_bound_); + } +} + +void HpackHeaderTable::EvictionSet(StringPiece name, + StringPiece 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(StringPiece name, + StringPiece 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 (EntryTable::const_reverse_iterator 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(); + CHECK_EQ(1u, dynamic_index_.erase(entry)); + dynamic_entries_.pop_back(); + } +} + +const HpackEntry* HpackHeaderTable::TryAddEntry(StringPiece name, + StringPiece 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 NULL; + } + dynamic_entries_.push_front(HpackEntry(name, value, + false, // is_static + total_insertions_)); + CHECK(dynamic_index_.insert(&dynamic_entries_.front()).second); + + size_ += entry_size; + ++total_insertions_; + + return &dynamic_entries_.front(); +} + +void HpackHeaderTable::DebugLogTableState() const { + DVLOG(2) << "Dynamic table:"; + for (EntryTable::const_iterator it = dynamic_entries_.begin(); + it != dynamic_entries_.end(); ++it) { + DVLOG(2) << " " << it->GetDebugString(); + } + DVLOG(2) << "Full Static Index:"; + for (OrderedEntrySet::const_iterator it = static_index_.begin(); + it != static_index_.end(); ++it) { + DVLOG(2) << " " << (*it)->GetDebugString(); + } + DVLOG(2) << "Full Dynamic Index:"; + for (OrderedEntrySet::const_iterator it = dynamic_index_.begin(); + it != dynamic_index_.end(); ++it) { + DVLOG(2) << " " << (*it)->GetDebugString(); + } +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_header_table.h b/net/spdy/hpack/hpack_header_table.h new file mode 100644 index 0000000..57c41db --- /dev/null +++ b/net/spdy/hpack/hpack_header_table.h @@ -0,0 +1,133 @@ +// 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 NET_SPDY_HPACK_HEADER_TABLE_H_ +#define NET_SPDY_HPACK_HEADER_TABLE_H_ + +#include <cstddef> +#include <deque> +#include <set> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_entry.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +using base::StringPiece; + +namespace test { +class HpackHeaderTablePeer; +} // namespace test + +// A data structure for the static table (3.3.1) and the header table (3.3.2). +class NET_EXPORT_PRIVATE HpackHeaderTable { + public: + friend class test::HpackHeaderTablePeer; + + // HpackHeaderTable takes advantage of the deque property that references + // remain valid, so long as insertions & deletions are at the head & tail. + // If this changes (eg we start to drop entries from the middle of the table), + // this needs to be a std::list, in which case |*_index_| can be trivially + // extended to map to list iterators. + typedef std::deque<HpackEntry> EntryTable; + + // Implements a total ordering of HpackEntry on name(), value(), then index + // ascending. Note that index may change over the lifetime of an HpackEntry, + // but the relative index order of two entries will not. This comparator is + // composed with the 'lookup' HpackEntry constructor to allow for efficient + // lower-bounding of matching entries. + struct NET_EXPORT_PRIVATE EntryComparator { + bool operator()(const HpackEntry* lhs, const HpackEntry* rhs) const; + }; + typedef std::set<HpackEntry*, EntryComparator> OrderedEntrySet; + + HpackHeaderTable(); + + ~HpackHeaderTable(); + + // Last-aknowledged value of SETTINGS_HEADER_TABLE_SIZE. + size_t settings_size_bound() { return settings_size_bound_; } + + // Current and maximum estimated byte size of the table, as described in + // 5.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(StringPiece name); + + // Returns the lowest-index matching entry, or NULL. + const HpackEntry* GetByNameAndValue(StringPiece name, StringPiece 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 3.3.3. No eviction + // actually occurs. The set is returned via range [begin_out, end_out). + void EvictionSet(StringPiece name, + StringPiece 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(StringPiece name, StringPiece value); + + void DebugLogTableState() const; + + private: + // Returns number of evictions required to enter |name| & |value|. + size_t EvictionCountForEntry(StringPiece name, StringPiece 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_| and |static_index_| are owned by HpackStaticTable + // singleton. + const EntryTable& static_entries_; + EntryTable dynamic_entries_; + + const OrderedEntrySet& static_index_; + OrderedEntrySet dynamic_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_header_table_size_| + 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_; + + DISALLOW_COPY_AND_ASSIGN(HpackHeaderTable); +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_HEADER_TABLE_H_ diff --git a/net/spdy/hpack/hpack_header_table_test.cc b/net/spdy/hpack/hpack_header_table_test.cc new file mode 100644 index 0000000..dc73010 --- /dev/null +++ b/net/spdy/hpack/hpack_header_table_test.cc @@ -0,0 +1,444 @@ +// 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/spdy/hpack/hpack_header_table.h" + +#include <algorithm> +#include <set> +#include <string> +#include <vector> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_entry.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +using base::StringPiece; +using std::distance; +using std::string; + +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(StringPiece name, StringPiece 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(StringPiece name, StringPiece 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(StringPiece name, StringPiece 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 size) { + EXPECT_GE(size, HpackEntry::kSizeOverhead); + string name((size - HpackEntry::kSizeOverhead) / 2, 'n'); + string value(size - HpackEntry::kSizeOverhead - name.size(), 'v'); + HpackEntry entry(name, value); + 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 total_size) { + EXPECT_GE(total_size, HpackEntry::kSizeOverhead); + uint32 entry_size = HpackEntry::kSizeOverhead; + uint32 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 (HpackEntryVector::const_iterator 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*>(NULL)); + } + + 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(string name, string 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 lowest-value matching entry. + EXPECT_EQ(entry3, table_.GetByName("key-1")); + EXPECT_EQ(entry7, table_.GetByName("key-2")); + EXPECT_EQ(entry2->name(), + table_.GetByName(first_static_entry->name())->name()); + EXPECT_EQ(NULL, 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(entry4, 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(NULL, table_.GetByNameAndValue("key-1", "Not Present")); + EXPECT_EQ(NULL, 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(NULL, + table_.GetByNameAndValue(first_static_entry->name(), "Value Four")); +} + +TEST_F(HpackHeaderTableTest, SetSizes) { + string 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 doesn't affect table_.max_size(), + // iff SETTINGS_HEADER_TABLE_SIZE >= |max_size|. + EXPECT_EQ(kDefaultHeaderTableSizeSetting, table_.settings_size_bound()); + table_.SetSettingsHeaderTableSize(kDefaultHeaderTableSizeSetting * 2); + EXPECT_EQ(max_size, table_.max_size()); + table_.SetSettingsHeaderTableSize(max_size + 1); + EXPECT_EQ(max_size, table_.max_size()); + EXPECT_EQ(2u, peer_.dynamic_entries().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) { + string 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) { + string 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 (HpackEntryVector::iterator 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*>(NULL)); + EXPECT_EQ(0u, peer_.dynamic_entries().size()); +} + +TEST_F(HpackHeaderTableTest, ComparatorNameOrdering) { + HpackEntry entry1("header", "value"); + HpackEntry entry2("HEADER", "value"); + + HpackHeaderTable::EntryComparator comparator; + EXPECT_FALSE(comparator(&entry1, &entry2)); + EXPECT_TRUE(comparator(&entry2, &entry1)); +} + +TEST_F(HpackHeaderTableTest, ComparatorValueOrdering) { + HpackEntry entry1("header", "value"); + HpackEntry entry2("header", "VALUE"); + + HpackHeaderTable::EntryComparator comparator; + EXPECT_FALSE(comparator(&entry1, &entry2)); + EXPECT_TRUE(comparator(&entry2, &entry1)); +} + +TEST_F(HpackHeaderTableTest, ComparatorIndexOrdering) { + HpackHeaderTable::EntryComparator comparator; + HpackEntry entry1(DynamicEntry("name", "value")); + HpackEntry entry2(DynamicEntry("name", "value")); + + // |entry1| has lower insertion index than |entry2|. + EXPECT_TRUE(comparator(&entry1, &entry2)); + EXPECT_FALSE(comparator(&entry2, &entry1)); +} + +TEST_F(HpackHeaderTableTest, ComparatorEqualityOrdering) { + HpackEntry entry1("name", "value"); + HpackEntry entry2(DynamicEntry("name", "value")); + + HpackHeaderTable::EntryComparator comparator; + EXPECT_FALSE(comparator(&entry1, &entry1)); + EXPECT_FALSE(comparator(&entry2, &entry2)); +} + +} // namespace + +} // namespace net diff --git a/net/spdy/hpack/hpack_huffman_table.cc b/net/spdy/hpack/hpack_huffman_table.cc new file mode 100644 index 0000000..8815e60 --- /dev/null +++ b/net/spdy/hpack/hpack_huffman_table.cc @@ -0,0 +1,324 @@ +// 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/spdy/hpack/hpack_huffman_table.h" + +#include <algorithm> +#include <cmath> + +#include "base/logging.h" +#include "base/numerics/safe_conversions.h" +#include "net/spdy/hpack/hpack_input_stream.h" +#include "net/spdy/hpack/hpack_output_stream.h" + +namespace net { + +using base::StringPiece; +using std::string; + +namespace { + +// How many bits to index in the root decode table. +const uint8 kDecodeTableRootBits = 9; +// Maximum number of bits to index in successive decode tables. +const uint8 kDecodeTableBranchBits = 6; + +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::DecodeEntry::DecodeEntry() + : next_table_index(0), length(0), symbol_id(0) {} +HpackHuffmanTable::DecodeEntry::DecodeEntry(uint8 next_table_index, + uint8 length, + uint16 symbol_id) + : next_table_index(next_table_index), + length(length), + symbol_id(symbol_id) {} +size_t HpackHuffmanTable::DecodeTable::size() const { + return size_t(1) << indexed_length; +} + +HpackHuffmanTable::HpackHuffmanTable() {} + +HpackHuffmanTable::~HpackHuffmanTable() {} + +bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols, + size_t symbol_count) { + CHECK(!IsInitialized()); + DCHECK(base::IsValueInRangeForNumericType<uint16>(symbol_count)); + + std::vector<Symbol> symbols(symbol_count); + // Validate symbol id sequence, and copy into |symbols|. + for (uint16 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 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>(symbols.back().code >> 24); + + BuildDecodeTables(symbols); + // 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); + } +} + +void HpackHuffmanTable::BuildDecodeTables(const std::vector<Symbol>& symbols) { + AddDecodeTable(0, kDecodeTableRootBits); + // We wish to maximize the flatness of the DecodeTable hierarchy (subject to + // the |kDecodeTableBranchBits| constraint), and to minimize the size of + // child tables. To achieve this, we iterate in order of descending code + // length. This ensures that child tables are visited with their longest + // entry first, and that the child can therefore be minimally sized to hold + // that entry without fear of introducing unneccesary branches later. + for (std::vector<Symbol>::const_reverse_iterator it = symbols.rbegin(); + it != symbols.rend(); ++it) { + uint8 table_index = 0; + while (true) { + const DecodeTable table = decode_tables_[table_index]; + + // Mask and shift the portion of the code being indexed into low bits. + uint32 index = (it->code << table.prefix_length); + index = index >> (32 - table.indexed_length); + + CHECK_LT(index, table.size()); + DecodeEntry entry = Entry(table, index); + + uint8 total_indexed = table.prefix_length + table.indexed_length; + if (total_indexed >= it->length) { + // We're writing a terminal entry. + entry.length = it->length; + entry.symbol_id = it->id; + entry.next_table_index = table_index; + SetEntry(table, index, entry); + break; + } + + if (entry.length == 0) { + // First visit to this placeholder. We need to create a new table. + CHECK_EQ(entry.next_table_index, 0); + entry.length = it->length; + entry.next_table_index = + AddDecodeTable(total_indexed, // Becomes the new table prefix. + std::min<uint8>(kDecodeTableBranchBits, + entry.length - total_indexed)); + SetEntry(table, index, entry); + } + CHECK_NE(entry.next_table_index, table_index); + table_index = entry.next_table_index; + } + } + // Fill shorter table entries into the additional entry spots they map to. + for (size_t i = 0; i != decode_tables_.size(); i++) { + const DecodeTable& table = decode_tables_[i]; + uint8 total_indexed = table.prefix_length + table.indexed_length; + + size_t j = 0; + while (j != table.size()) { + const DecodeEntry& entry = Entry(table, j); + if (entry.length != 0 && entry.length < total_indexed) { + // The difference between entry & table bit counts tells us how + // many additional entries map to this one. + size_t fill_count = 1 << (total_indexed - entry.length); + CHECK_LE(j + fill_count, table.size()); + + for (size_t k = 1; k != fill_count; k++) { + CHECK_EQ(Entry(table, j + k).length, 0); + SetEntry(table, j + k, entry); + } + j += fill_count; + } else { + j++; + } + } + } +} + +uint8 HpackHuffmanTable::AddDecodeTable(uint8 prefix, uint8 indexed) { + CHECK_LT(decode_tables_.size(), 255u); + { + DecodeTable table; + table.prefix_length = prefix; + table.indexed_length = indexed; + table.entries_offset = decode_entries_.size(); + decode_tables_.push_back(table); + } + decode_entries_.resize(decode_entries_.size() + (size_t(1) << indexed)); + return static_cast<uint8>(decode_tables_.size() - 1); +} + +const HpackHuffmanTable::DecodeEntry& HpackHuffmanTable::Entry( + const DecodeTable& table, + uint32 index) const { + DCHECK_LT(index, table.size()); + DCHECK_LT(table.entries_offset + index, decode_entries_.size()); + return decode_entries_[table.entries_offset + index]; +} + +void HpackHuffmanTable::SetEntry(const DecodeTable& table, + uint32 index, + const DecodeEntry& entry) { + CHECK_LT(index, table.size()); + CHECK_LT(table.entries_offset + index, decode_entries_.size()); + decode_entries_[table.entries_offset + index] = entry; +} + +bool HpackHuffmanTable::IsInitialized() const { + return !code_by_id_.empty(); +} + +void HpackHuffmanTable::EncodeString(StringPiece in, + HpackOutputStream* out) const { + size_t bit_remnant = 0; + for (size_t i = 0; i != in.size(); i++) { + uint16 symbol_id = static_cast<uint8>(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 code = code_by_id_[symbol_id] >> (32 - length); + + bit_remnant = (bit_remnant + length) % 8; + + if (length > 24) { + out->AppendBits(static_cast<uint8>(code >> 24), length - 24); + length = 24; + } + if (length > 16) { + out->AppendBits(static_cast<uint8>(code >> 16), length - 16); + length = 16; + } + if (length > 8) { + out->AppendBits(static_cast<uint8>(code >> 8), length - 8); + length = 8; + } + out->AppendBits(static_cast<uint8>(code), length); + } + if (bit_remnant != 0) { + // Pad current byte as required. + out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant); + } +} + +size_t HpackHuffmanTable::EncodedSize(StringPiece in) const { + size_t bit_count = 0; + for (size_t i = 0; i != in.size(); i++) { + uint16 symbol_id = static_cast<uint8>(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; +} + +bool HpackHuffmanTable::DecodeString(HpackInputStream* in, + size_t out_capacity, + string* out) const { + // Number of decode iterations required for a 32-bit code. + const int kDecodeIterations = static_cast<int>( + std::ceil((32.f - kDecodeTableRootBits) / kDecodeTableBranchBits)); + + out->clear(); + + // Current input, stored in the high |bits_available| bits of |bits|. + uint32 bits = 0; + size_t bits_available = 0; + bool peeked_success = in->PeekBits(&bits_available, &bits); + + while (true) { + const DecodeTable* table = &decode_tables_[0]; + uint32 index = bits >> (32 - kDecodeTableRootBits); + + for (int i = 0; i != kDecodeIterations; i++) { + DCHECK_LT(index, table->size()); + DCHECK_LT(Entry(*table, index).next_table_index, decode_tables_.size()); + + table = &decode_tables_[Entry(*table, index).next_table_index]; + // Mask and shift the portion of the code being indexed into low bits. + index = (bits << table->prefix_length) >> (32 - table->indexed_length); + } + const DecodeEntry& entry = Entry(*table, index); + + if (entry.length > bits_available) { + if (!peeked_success) { + // Unable to read enough input for a match. If only a portion of + // the last byte remains, this is a successful EOF condition. + in->ConsumeByteRemainder(); + return !in->HasMoreData(); + } + } else if (entry.length == 0) { + // The input is an invalid prefix, larger than any prefix in the table. + return false; + } else { + if (out->size() == out_capacity) { + // This code would cause us to overflow |out_capacity|. + return false; + } + if (entry.symbol_id < 256) { + // Assume symbols >= 256 are used for padding. + out->push_back(static_cast<char>(entry.symbol_id)); + } + + in->ConsumeBits(entry.length); + bits = bits << entry.length; + bits_available -= entry.length; + } + peeked_success = in->PeekBits(&bits_available, &bits); + } + NOTREACHED(); + return false; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_huffman_table.h b/net/spdy/hpack/hpack_huffman_table.h new file mode 100644 index 0000000..1904a7b --- /dev/null +++ b/net/spdy/hpack/hpack_huffman_table.h @@ -0,0 +1,128 @@ +// 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 NET_SPDY_HPACK_HUFFMAN_TABLE_H_ +#define NET_SPDY_HPACK_HUFFMAN_TABLE_H_ + +#include <cstddef> +#include <string> +#include <vector> + +#include "base/basictypes.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_constants.h" + +namespace net { + +namespace test { +class HpackHuffmanTablePeer; +} // namespace test + +class HpackInputStream; +class HpackOutputStream; + +// HpackHuffmanTable encodes and decodes 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 NET_EXPORT_PRIVATE HpackHuffmanTable { + public: + friend class test::HpackHuffmanTablePeer; + + typedef HpackHuffmanSymbol Symbol; + + // DecodeTables are multilevel indexes on code prefixes. Each table indexes + // a portion of the prefix mapped to DecodeEntry, which in turn either + // captures a terminal symbol, or points to the next DecodeTable to consult + // with successive portions of the prefix. + struct NET_EXPORT_PRIVATE DecodeEntry { + DecodeEntry(); + DecodeEntry(uint8 next_table_index, uint8 length, uint16 symbol_id); + + // The next table to consult. If this is a terminal, + // |next_table_index| will be self-referential. + uint8 next_table_index; + // Bit-length of terminal code, if this is a terminal. Length of the + // longest code having this prefix, if non-terminal. + uint8 length; + // Set only for terminal entries. + uint16 symbol_id; + }; + struct NET_EXPORT_PRIVATE DecodeTable { + // Number of bits indexed by the chain leading to this table. + uint8 prefix_length; + // Number of additional prefix bits this table indexes. + uint8 indexed_length; + // Entries are represented as a length |size()| slice into + // |decode_entries_| beginning at |entries_offset|. + size_t entries_offset; + // Returns |1 << indexed_length|. + size_t size() const; + }; + + HpackHuffmanTable(); + ~HpackHuffmanTable(); + + // Prepares HpackHuffmanTable to encode & decode 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. + 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(base::StringPiece in, HpackOutputStream* out) const; + + // Returns the encoded size of the input string. + size_t EncodedSize(base::StringPiece in) const; + + // Decodes symbols from |in| into |out|. It is the caller's responsibility + // to ensure |out| has a reserved a sufficient buffer to hold decoded output. + // DecodeString() halts when |in| runs out of input, in which case true is + // returned. It also halts (returning false) if an invalid Huffman code + // prefix is read, or if |out_capacity| would otherwise be overflowed. + bool DecodeString(HpackInputStream* in, + size_t out_capacity, + std::string* out) const; + + private: + // Expects symbols ordered on length & ID ascending. + void BuildDecodeTables(const std::vector<Symbol>& symbols); + + // Expects symbols ordered on ID ascending. + void BuildEncodeTable(const std::vector<Symbol>& symbols); + + // Adds a new DecodeTable with the argument prefix & indexed length. + // Returns the new table index. + uint8 AddDecodeTable(uint8 prefix, uint8 indexed); + + const DecodeEntry& Entry(const DecodeTable& table, uint32 index) const; + + void SetEntry(const DecodeTable& table, + uint32 index, + const DecodeEntry& entry); + + std::vector<DecodeTable> decode_tables_; + std::vector<DecodeEntry> decode_entries_; + + // Symbol code and code length, in ascending symbol ID order. + // Codes are stored in the most-significant bits of the word. + std::vector<uint32> code_by_id_; + std::vector<uint8> length_by_id_; + + // The first 8 bits of the longest code. Applied when generating padding bits. + uint8 pad_bits_; + + // If initialization fails, preserve the symbol ID which failed validation + // for examination in tests. + uint16 failed_symbol_id_; +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_HUFFMAN_TABLE_H_ diff --git a/net/spdy/hpack/hpack_huffman_table_test.cc b/net/spdy/hpack/hpack_huffman_table_test.cc new file mode 100644 index 0000000..a48ccb4 --- /dev/null +++ b/net/spdy/hpack/hpack_huffman_table_test.cc @@ -0,0 +1,473 @@ +// 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/spdy/hpack/hpack_huffman_table.h" + +#include <bitset> +#include <string> + +#include "base/logging.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_input_stream.h" +#include "net/spdy/hpack/hpack_output_stream.h" +#include "net/spdy/spdy_test_utils.h" +#include "testing/gmock/include/gmock/gmock.h" +#include "testing/gtest/include/gtest/gtest.h" + +using base::StringPiece; +using std::string; +using testing::ElementsAreArray; +using testing::Pointwise; + +namespace net { + +namespace test { + +typedef HpackHuffmanTable::DecodeEntry DecodeEntry; +typedef HpackHuffmanTable::DecodeTable DecodeTable; + +class HpackHuffmanTablePeer { + public: + explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table) + : table_(table) {} + + const std::vector<uint32>& code_by_id() const { return table_.code_by_id_; } + const std::vector<uint8>& length_by_id() const { + return table_.length_by_id_; + } + const std::vector<DecodeTable>& decode_tables() const { + return table_.decode_tables_; + } + char pad_bits() const { + // Cast to match signed-ness of bits8(). + return static_cast<char>(table_.pad_bits_); + } + uint16 failed_symbol_id() const { return table_.failed_symbol_id_; } + std::vector<DecodeEntry> decode_entries(const DecodeTable& decode_table) { + std::vector<DecodeEntry>::const_iterator begin = + table_.decode_entries_.begin() + decode_table.entries_offset; + return std::vector<DecodeEntry>(begin, begin + decode_table.size()); + } + + private: + const HpackHuffmanTable& table_; +}; + +namespace { + +class HpackHuffmanTableTest : public ::testing::Test { + protected: + HpackHuffmanTableTest() : table_(), peer_(table_) {} + + string EncodeString(StringPiece input) { + string 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_; +}; + +MATCHER(DecodeEntryEq, "") { + const DecodeEntry& lhs = std::tr1::get<0>(arg); + const DecodeEntry& rhs = std::tr1::get<1>(arg); + return lhs.next_table_index == rhs.next_table_index && + lhs.length == rhs.length && lhs.symbol_id == rhs.symbol_id; +} + +uint32 bits32(const string& bitstring) { + return std::bitset<32>(bitstring).to_ulong(); +} +char bits8(const string& bitstring) { + return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); +} + +TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + EXPECT_TRUE(table_.IsInitialized()); + EXPECT_EQ(peer_.pad_bits(), bits8("11111111")); // First 8 bits of EOS. +} + +TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) { + { + // Verify eight symbols can be encoded with 3 bits per symbol. + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 3, 0}, + {bits32("00100000000000000000000000000000"), 3, 1}, + {bits32("01000000000000000000000000000000"), 3, 2}, + {bits32("01100000000000000000000000000000"), 3, 3}, + {bits32("10000000000000000000000000000000"), 3, 4}, + {bits32("10100000000000000000000000000000"), 3, 5}, + {bits32("11000000000000000000000000000000"), 3, 6}, + {bits32("11100000000000000000000000000000"), 8, 7}}; + HpackHuffmanTable table; + EXPECT_TRUE(table.Initialize(code, arraysize(code))); + } + { + // But using 2 bits with one symbol overflows the code. + HpackHuffmanSymbol code[] = { + {bits32("01000000000000000000000000000000"), 3, 0}, + {bits32("01100000000000000000000000000000"), 3, 1}, + {bits32("00000000000000000000000000000000"), 2, 2}, + {bits32("10000000000000000000000000000000"), 3, 3}, + {bits32("10100000000000000000000000000000"), 3, 4}, + {bits32("11000000000000000000000000000000"), 3, 5}, + {bits32("11100000000000000000000000000000"), 3, 6}, + {bits32("00000000000000000000000000000000"), 8, 7}}; // Overflow. + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, arraysize(code))); + EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Verify four symbols can be encoded with incremental bits per symbol. + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 1, 0}, + {bits32("10000000000000000000000000000000"), 2, 1}, + {bits32("11000000000000000000000000000000"), 3, 2}, + {bits32("11100000000000000000000000000000"), 8, 3}}; + HpackHuffmanTable table; + EXPECT_TRUE(table.Initialize(code, arraysize(code))); + } + { + // But repeating a length overflows the code. + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 1, 0}, + {bits32("10000000000000000000000000000000"), 2, 1}, + {bits32("11000000000000000000000000000000"), 2, 2}, + {bits32("00000000000000000000000000000000"), 8, 3}}; // Overflow. + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, arraysize(code))); + EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Symbol IDs must be assigned sequentially with no gaps. + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 1, 0}, + {bits32("10000000000000000000000000000000"), 2, 1}, + {bits32("11000000000000000000000000000000"), 3, 1}, // Repeat. + {bits32("11100000000000000000000000000000"), 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, arraysize(code))); + EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Canonical codes must begin with zero. + HpackHuffmanSymbol code[] = { + {bits32("10000000000000000000000000000000"), 4, 0}, + {bits32("10010000000000000000000000000000"), 4, 1}, + {bits32("10100000000000000000000000000000"), 4, 2}, + {bits32("10110000000000000000000000000000"), 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, arraysize(code))); + EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id()); + } + { + // Codes must match the expected canonical sequence. + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 2, 0}, + {bits32("01000000000000000000000000000000"), 2, 1}, + {bits32("11000000000000000000000000000000"), 2, 2}, // Not canonical. + {bits32("10000000000000000000000000000000"), 8, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, 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[] = { + {bits32("00000000000000000000000000000000"), 1, 0}, + {bits32("10000000000000000000000000000000"), 2, 1}, + {bits32("11000000000000000000000000000000"), 3, 2}, + {bits32("11100000000000000000000000000000"), 7, 3}}; + HpackHuffmanTable table; + EXPECT_FALSE(table.Initialize(code, arraysize(code))); + } +} + +TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { + HpackHuffmanSymbol code[] = { + {bits32("01100000000000000000000000000000"), 4, 0}, // 3rd. + {bits32("01110000000000000000000000000000"), 4, 1}, // 4th. + {bits32("00000000000000000000000000000000"), 2, 2}, // 1st assigned code. + {bits32("01000000000000000000000000000000"), 3, 3}, // 2nd. + {bits32("10000000000000000000000000000000"), 5, 4}, // 5th. + {bits32("10001000000000000000000000000000"), 5, 5}, // 6th. + {bits32("10011000000000000000000000000000"), 8, 6}, // 8th. + {bits32("10010000000000000000000000000000"), 5, 7}}; // 7th. + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); + ASSERT_EQ(arraysize(code), peer_.code_by_id().size()); + ASSERT_EQ(arraysize(code), peer_.length_by_id().size()); + for (size_t i = 0; i < 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(1u, peer_.decode_tables().size()); + { + std::vector<DecodeEntry> expected; + expected.resize(128, DecodeEntry(0, 2, 2)); // Fills 128. + expected.resize(192, DecodeEntry(0, 3, 3)); // Fills 64. + expected.resize(224, DecodeEntry(0, 4, 0)); // Fills 32. + expected.resize(256, DecodeEntry(0, 4, 1)); // Fills 32. + expected.resize(272, DecodeEntry(0, 5, 4)); // Fills 16. + expected.resize(288, DecodeEntry(0, 5, 5)); // Fills 16. + expected.resize(304, DecodeEntry(0, 5, 7)); // Fills 16. + expected.resize(306, DecodeEntry(0, 8, 6)); // Fills 2. + expected.resize(512, DecodeEntry()); // Remainder is empty. + + EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]), + Pointwise(DecodeEntryEq(), expected)); + } + EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); + + char input_storage[] = {2, 3, 2, 7, 4}; + StringPiece input(input_storage, arraysize(input_storage)); + // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. + char expect_storage[] = {bits8("00010001"), bits8("00101000"), + bits8("01001100")}; + StringPiece expect(expect_storage, arraysize(expect_storage)); + + string buffer_in = EncodeString(input); + EXPECT_EQ(expect, buffer_in); + + string buffer_out; + HpackInputStream input_stream(kuint32max, buffer_in); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_EQ(buffer_out, input); +} + +TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { + HpackHuffmanSymbol code[] = { + {bits32("00000000000000000000000000000000"), 6, 0}, + {bits32("00000100000000000000000000000000"), 6, 1}, + {bits32("00001000000000000000000000000000"), 11, 2}, + {bits32("00001000001000000000000000000000"), 11, 3}, + {bits32("00001000010000000000000000000000"), 12, 4}, + }; + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); + + EXPECT_EQ(2u, peer_.decode_tables().size()); + { + std::vector<DecodeEntry> expected; + expected.resize(8, DecodeEntry(0, 6, 0)); // Fills 8. + expected.resize(16, DecodeEntry(0, 6, 1)); // Fills 8. + expected.resize(17, DecodeEntry(1, 12, 0)); // Pointer. Fills 1. + expected.resize(512, DecodeEntry()); // Remainder is empty. + + const DecodeTable& decode_table = peer_.decode_tables()[0]; + EXPECT_EQ(decode_table.prefix_length, 0); + EXPECT_EQ(decode_table.indexed_length, 9); + EXPECT_THAT(peer_.decode_entries(decode_table), + Pointwise(DecodeEntryEq(), expected)); + } + { + std::vector<DecodeEntry> expected; + expected.resize(2, DecodeEntry(1, 11, 2)); // Fills 2. + expected.resize(4, DecodeEntry(1, 11, 3)); // Fills 2. + expected.resize(5, DecodeEntry(1, 12, 4)); // Fills 1. + expected.resize(8, DecodeEntry()); // Remainder is empty. + + const DecodeTable& decode_table = peer_.decode_tables()[1]; + EXPECT_EQ(decode_table.prefix_length, 9); + EXPECT_EQ(decode_table.indexed_length, 3); + EXPECT_THAT(peer_.decode_entries(decode_table), + Pointwise(DecodeEntryEq(), expected)); + } + EXPECT_EQ(bits8("00001000"), peer_.pad_bits()); +} + +TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) { + HpackHuffmanSymbol code[] = { + {bits32("01100000000000000000000000000000"), 4, 0}, + {bits32("01110000000000000000000000000000"), 4, 1}, + {bits32("00000000000000000000000000000000"), 2, 2}, + {bits32("01000000000000000000000000000000"), 3, 3}, + {bits32("10000000000000000000000000000000"), 5, 4}, + {bits32("10001000000000000000000000000000"), 5, 5}, + {bits32("10011000000000000000000000000000"), 6, 6}, + {bits32("10010000000000000000000000000000"), 5, 7}, + {bits32("10011100000000000000000000000000"), 16, 8}}; + EXPECT_TRUE(table_.Initialize(code, arraysize(code))); + + string buffer; + const size_t capacity = 4; + { + // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100. + char input_storage[] = {bits8("00010001"), bits8("00110100")}; + StringPiece input(input_storage, arraysize(input_storage)); + + HpackInputStream input_stream(kuint32max, input); + EXPECT_TRUE(table_.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_EQ(buffer, "\x02\x03\x02\x06"); + } + { + // Expect to fail on an invalid code prefix. + // (2) 00 (3) 010 (2) 00 (too-large) 101000 (pad) 100. + char input_storage[] = {bits8("00010001"), bits8("01000111")}; + StringPiece input(input_storage, arraysize(input_storage)); + + HpackInputStream input_stream(kuint32max, input); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_EQ(buffer, "\x02\x03\x02"); + } + { + // Repeat the shortest 0b00 code to overflow |buffer|. Expect to fail. + std::vector<char> input_storage(1 + capacity / 4, '\0'); + StringPiece input(&input_storage[0], input_storage.size()); + + HpackInputStream input_stream(kuint32max, input); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); + + std::vector<char> expected(capacity, '\x02'); + EXPECT_THAT(buffer, ElementsAreArray(expected)); + EXPECT_EQ(capacity, buffer.size()); + } + { + // Expect to fail if more than a byte of unconsumed input remains. + // (6) 100110 (8 truncated) 1001110000 + char input_storage[] = {bits8("10011010"), bits8("01110000")}; + StringPiece input(input_storage, arraysize(input_storage)); + + HpackInputStream input_stream(kuint32max, input); + EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer)); + EXPECT_EQ(buffer, "\x06"); + } +} + +TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + string buffer; + string test_table[] = { + a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"), + "www.example.com", + a2b_hex("a8eb10649cbf"), + "no-cache", + a2b_hex("25a849e95ba97d7f"), + "custom-key", + a2b_hex("25a849e95bb8e8b4bf"), + "custom-value", + }; + // Round-trip each test example. + for (size_t i = 0; i != arraysize(test_table); i += 2) { + const string& encodedFixture(test_table[i]); + const string& decodedFixture(test_table[i + 1]); + HpackInputStream input_stream(kuint32max, encodedFixture); + + EXPECT_TRUE( + table_.DecodeString(&input_stream, decodedFixture.size(), &buffer)); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); + } +} + +TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + string buffer; + string test_table[] = { + a2b_hex("6402"), "302", a2b_hex("aec3771a4b"), "private", + a2b_hex("d07abe941054d444a8200595040b8166" + "e082a62d1bff"), + "Mon, 21 Oct 2013 20:13:21 GMT", + a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43" + "d3"), + "https://www.example.com", a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960" + "d5af27087f3672c1ab270fb5291f9587" + "316065c003ed4ee5b1063d5007"), + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + }; + // Round-trip each test example. + for (size_t i = 0; i != arraysize(test_table); i += 2) { + const string& encodedFixture(test_table[i]); + const string& decodedFixture(test_table[i + 1]); + HpackInputStream input_stream(kuint32max, encodedFixture); + + EXPECT_TRUE( + table_.DecodeString(&input_stream, decodedFixture.size(), &buffer)); + EXPECT_EQ(decodedFixture, buffer); + buffer = EncodeString(decodedFixture); + EXPECT_EQ(encodedFixture, buffer); + } +} + +TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + for (size_t i = 0; i != 256; i++) { + char c = static_cast<char>(i); + char storage[3] = {c, c, c}; + StringPiece input(storage, arraysize(storage)); + + string buffer_in = EncodeString(input); + string buffer_out; + + HpackInputStream input_stream(kuint32max, buffer_in); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_EQ(input, buffer_out); + } +} + +TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + char storage[512]; + for (size_t i = 0; i != 256; i++) { + storage[i] = static_cast<char>(i); + storage[511 - i] = static_cast<char>(i); + } + StringPiece input(storage, arraysize(storage)); + + string buffer_in = EncodeString(input); + string buffer_out; + + HpackInputStream input_stream(kuint32max, buffer_in); + EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); + EXPECT_EQ(input, buffer_out); +} + +TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(table_.Initialize(&code[0], code.size())); + + string test_table[] = { + "", + "Mon, 21 Oct 2013 20:13:21 GMT", + "https://www.example.com", + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", + string(1, '\0'), + string("foo\0bar", 7), + string(256, '\0'), + }; + for (size_t i = 0; i != 256; ++i) { + // Expand last |test_table| entry to cover all codes. + test_table[arraysize(test_table) - 1][i] = static_cast<char>(i); + } + + HpackOutputStream output_stream; + string encoding; + for (size_t i = 0; i != 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 net diff --git a/net/spdy/hpack/hpack_input_stream.cc b/net/spdy/hpack/hpack_input_stream.cc new file mode 100644 index 0000000..255509e6 --- /dev/null +++ b/net/spdy/hpack/hpack_input_stream.cc @@ -0,0 +1,171 @@ +// 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/spdy/hpack/hpack_input_stream.h" + +#include <algorithm> + +#include "base/basictypes.h" +#include "base/logging.h" + +namespace net { + +using base::StringPiece; +using std::string; + +HpackInputStream::HpackInputStream(uint32 max_string_literal_size, + StringPiece buffer) + : max_string_literal_size_(max_string_literal_size), + buffer_(buffer), + bit_offset_(0) {} + +HpackInputStream::~HpackInputStream() {} + +bool HpackInputStream::HasMoreData() const { + return !buffer_.empty(); +} + +bool HpackInputStream::MatchPrefixAndConsume(HpackPrefix prefix) { + DCHECK_GT(prefix.bit_size, 0u); + DCHECK_LE(prefix.bit_size, 8u); + + uint32 peeked = 0; + size_t peeked_count = 0; + + if (!PeekBits(&peeked_count, &peeked)) + return false; + + if ((peeked >> (32 - prefix.bit_size)) == prefix.bits) { + ConsumeBits(prefix.bit_size); + return true; + } + return false; +} + +bool HpackInputStream::PeekNextOctet(uint8* next_octet) { + if ((bit_offset_ > 0) || buffer_.empty()) + return false; + + *next_octet = buffer_[0]; + return true; +} + +bool HpackInputStream::DecodeNextOctet(uint8* next_octet) { + if (!PeekNextOctet(next_octet)) + return false; + + buffer_.remove_prefix(1); + return true; +} + +bool HpackInputStream::DecodeNextUint32(uint32* I) { + size_t N = 8 - bit_offset_; + DCHECK_GT(N, 0u); + DCHECK_LE(N, 8u); + + bit_offset_ = 0; + + *I = 0; + + uint8 next_marker = (1 << N) - 1; + uint8 next_octet = 0; + if (!DecodeNextOctet(&next_octet)) + return false; + *I = next_octet & next_marker; + + bool has_more = (*I == next_marker); + size_t shift = 0; + while (has_more && (shift < 32)) { + uint8 next_octet = 0; + if (!DecodeNextOctet(&next_octet)) + return false; + has_more = (next_octet & 0x80) != 0; + next_octet &= 0x7f; + uint32 addend = next_octet << shift; + // Check for overflow. + if ((addend >> shift) != next_octet) { + return false; + } + *I += addend; + shift += 7; + } + + return !has_more; +} + +bool HpackInputStream::DecodeNextIdentityString(StringPiece* str) { + uint32 size = 0; + if (!DecodeNextUint32(&size)) + return false; + + if (size > max_string_literal_size_) + return false; + + if (size > buffer_.size()) + return false; + + *str = StringPiece(buffer_.data(), size); + buffer_.remove_prefix(size); + return true; +} + +bool HpackInputStream::DecodeNextHuffmanString(const HpackHuffmanTable& table, + string* str) { + uint32 encoded_size = 0; + if (!DecodeNextUint32(&encoded_size)) + return false; + + if (encoded_size > buffer_.size()) + return false; + + HpackInputStream bounded_reader(max_string_literal_size_, + StringPiece(buffer_.data(), encoded_size)); + buffer_.remove_prefix(encoded_size); + + // HpackHuffmanTable will not decode beyond |max_string_literal_size_|. + return table.DecodeString(&bounded_reader, max_string_literal_size_, str); +} + +bool HpackInputStream::PeekBits(size_t* peeked_count, uint32* out) { + size_t byte_offset = (bit_offset_ + *peeked_count) / 8; + size_t bit_offset = (bit_offset_ + *peeked_count) % 8; + + if (*peeked_count >= 32 || byte_offset >= buffer_.size()) { + return false; + } + // We'll read the minimum of the current byte remainder, + // and the remaining unfilled bits of |out|. + size_t bits_to_read = std::min(32 - *peeked_count, 8 - bit_offset); + + uint32 new_bits = static_cast<uint32>(buffer_[byte_offset]); + // Shift byte remainder to most-signifcant bits of |new_bits|. + // This drops the leading |bit_offset| bits of the byte. + new_bits = new_bits << (24 + bit_offset); + // Shift bits to the most-significant open bits of |out|. + new_bits = new_bits >> *peeked_count; + + CHECK_EQ(*out & new_bits, 0u); + *out |= new_bits; + + *peeked_count += bits_to_read; + return true; +} + +void HpackInputStream::ConsumeBits(size_t bit_count) { + size_t byte_count = (bit_offset_ + bit_count) / 8; + bit_offset_ = (bit_offset_ + bit_count) % 8; + CHECK_GE(buffer_.size(), byte_count); + if (bit_offset_ != 0) { + CHECK_GT(buffer_.size(), 0u); + } + buffer_.remove_prefix(byte_count); +} + +void HpackInputStream::ConsumeByteRemainder() { + if (bit_offset_ != 0) { + ConsumeBits(8 - bit_offset_); + } +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_input_stream.h b/net/spdy/hpack/hpack_input_stream.h new file mode 100644 index 0000000..c640223 --- /dev/null +++ b/net/spdy/hpack/hpack_input_stream.h @@ -0,0 +1,78 @@ +// 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 NET_SPDY_HPACK_INPUT_STREAM_H_ +#define NET_SPDY_HPACK_INPUT_STREAM_H_ + +#include <string> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_huffman_table.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +// An HpackInputStream handles all the low-level details of decoding +// header fields. +class NET_EXPORT_PRIVATE HpackInputStream { + public: + // |max_string_literal_size| is the largest that any one string + // literal (header name or header value) can be. + HpackInputStream(uint32 max_string_literal_size, base::StringPiece buffer); + ~HpackInputStream(); + + // Returns whether or not there is more data to process. + bool HasMoreData() const; + + // If the next bits of input match |prefix|, consumes them and returns true. + // Otherwise, consumes nothing and returns false. + bool MatchPrefixAndConsume(HpackPrefix prefix); + + // The Decode* functions return true and fill in their arguments if + // decoding was successful, or false if an error was encountered. + + bool DecodeNextUint32(uint32* I); + bool DecodeNextIdentityString(base::StringPiece* str); + bool DecodeNextHuffmanString(const HpackHuffmanTable& table, + std::string* str); + + // Stores input bits into the most-significant, unfilled bits of |out|. + // |peeked_count| is the number of filled bits in |out| which have been + // previously peeked. PeekBits() will fill some number of remaining bits, + // returning the new total number via |peeked_count|. Returns true if one + // or more additional bits could be peeked, and false otherwise. + bool PeekBits(size_t* peeked_count, uint32* out); + + // Consumes |count| bits of input. Generally paired with PeekBits(). + void ConsumeBits(size_t count); + + // If not currently on a byte boundary, consumes and discards + // remaining bits in the current byte. + void ConsumeByteRemainder(); + + // Accessors for testing. + + void SetBitOffsetForTest(size_t bit_offset) { bit_offset_ = bit_offset; } + + private: + const uint32 max_string_literal_size_; + base::StringPiece buffer_; + size_t bit_offset_; + + bool PeekNextOctet(uint8* next_octet); + + bool DecodeNextOctet(uint8* next_octet); + + DISALLOW_COPY_AND_ASSIGN(HpackInputStream); +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_INPUT_STREAM_H_ diff --git a/net/spdy/hpack/hpack_input_stream_test.cc b/net/spdy/hpack/hpack_input_stream_test.cc new file mode 100644 index 0000000..002c170 --- /dev/null +++ b/net/spdy/hpack/hpack_input_stream_test.cc @@ -0,0 +1,630 @@ +// 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/spdy/hpack/hpack_input_stream.h" + +#include <bitset> +#include <string> +#include <vector> + +#include "base/logging.h" +#include "base/strings/string_piece.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/spdy_test_utils.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +namespace { + +using base::StringPiece; +using std::string; +using test::a2b_hex; + +const size_t kLiteralBound = 1024; + +class HpackInputStreamTest : public ::testing::Test { + public: + void SetUp() override { + std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); + EXPECT_TRUE(huffman_table_.Initialize(&code[0], code.size())); + } + + protected: + HpackHuffmanTable huffman_table_; +}; + +// Hex representation of encoded length and Huffman string. +const char kEncodedHuffmanFixture[] = + "2d" // Length prefix. + "94e7821dd7f2e6c7b335dfdfcd5b3960" + "d5af27087f3672c1ab270fb5291f9587" + "316065c003ed4ee5b1063d5007"; + +const char kDecodedHuffmanFixture[] = + "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"; + +// Utility function to decode an assumed-valid uint32 with an N-bit +// prefix. +uint32 DecodeValidUint32(uint8 N, StringPiece str) { + EXPECT_GT(N, 0); + EXPECT_LE(N, 8); + HpackInputStream input_stream(kLiteralBound, str); + input_stream.SetBitOffsetForTest(8 - N); + uint32 I; + EXPECT_TRUE(input_stream.DecodeNextUint32(&I)); + return I; +} + +// Utility function to decode an assumed-invalid uint32 with an N-bit +// prefix. +void ExpectDecodeUint32Invalid(uint8 N, StringPiece str) { + EXPECT_GT(N, 0); + EXPECT_LE(N, 8); + HpackInputStream input_stream(kLiteralBound, str); + input_stream.SetBitOffsetForTest(8 - N); + uint32 I; + EXPECT_FALSE(input_stream.DecodeNextUint32(&I)); +} + +uint32 bits32(const string& bitstring) { + return std::bitset<32>(bitstring).to_ulong(); +} + +// The {Number}ByteIntegersEightBitPrefix tests below test that +// certain integers are decoded correctly with an 8-bit prefix in +// exactly {Number} bytes. + +TEST_F(HpackInputStreamTest, OneByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0x00u, DecodeValidUint32(8, string("\x00", 1))); + EXPECT_EQ(0x7fu, DecodeValidUint32(8, "\x7f")); + // Maximum. + EXPECT_EQ(0xfeu, DecodeValidUint32(8, "\xfe")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff"); +} + +TEST_F(HpackInputStreamTest, TwoByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0xffu, DecodeValidUint32(8, string("\xff\x00", 2))); + EXPECT_EQ(0x0100u, DecodeValidUint32(8, "\xff\x01")); + // Maximum. + EXPECT_EQ(0x017eu, DecodeValidUint32(8, "\xff\x7f")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff\x80"); + ExpectDecodeUint32Invalid(8, "\xff\xff"); +} + +TEST_F(HpackInputStreamTest, ThreeByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0x017fu, DecodeValidUint32(8, "\xff\x80\x01")); + EXPECT_EQ(0x0fffu, DecodeValidUint32(8, "\xff\x80\x1e")); + // Maximum. + EXPECT_EQ(0x40feu, DecodeValidUint32(8, "\xff\xff\x7f")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff\x80\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\x80"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, FourByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0x40ffu, DecodeValidUint32(8, "\xff\x80\x80\x01")); + EXPECT_EQ(0xffffu, DecodeValidUint32(8, "\xff\x80\xfe\x03")); + // Maximum. + EXPECT_EQ(0x002000feu, DecodeValidUint32(8, "\xff\xff\xff\x7f")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff\xff\x80\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, FiveByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0x002000ffu, DecodeValidUint32(8, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x00ffffffu, DecodeValidUint32(8, "\xff\x80\xfe\xff\x07")); + // Maximum. + EXPECT_EQ(0x100000feu, DecodeValidUint32(8, "\xff\xff\xff\xff\x7f")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\x80\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\x00"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, SixByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(0x100000ffu, DecodeValidUint32(8, "\xff\x80\x80\x80\x80\x01")); + // Maximum. + EXPECT_EQ(0xffffffffu, DecodeValidUint32(8, "\xff\x80\xfe\xff\xff\x0f")); + // Invalid. + ExpectDecodeUint32Invalid(8, "\xff\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(8, "\xff\x80\xfe\xff\xff\x10"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\xff\xff"); +} + +// There are no valid uint32 encodings that are greater than six +// bytes. +TEST_F(HpackInputStreamTest, SevenByteIntegersEightBitPrefix) { + ExpectDecodeUint32Invalid(8, "\xff\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(8, "\xff\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\xff\xff\xff"); +} + +// 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_F(HpackInputStreamTest, OneByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0x00u, DecodeValidUint32(7, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(7, string("\x80", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(6, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(6, string("\xc0", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(5, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(5, string("\xe0", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(4, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(4, string("\xf0", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(3, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(3, string("\xf8", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(2, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(2, string("\xfc", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(1, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(1, string("\xfe", 1))); + + // Maximums. + EXPECT_EQ(0x7eu, DecodeValidUint32(7, "\x7e")); + EXPECT_EQ(0x7eu, DecodeValidUint32(7, "\xfe")); + EXPECT_EQ(0x3eu, DecodeValidUint32(6, "\x3e")); + EXPECT_EQ(0x3eu, DecodeValidUint32(6, "\xfe")); + EXPECT_EQ(0x1eu, DecodeValidUint32(5, "\x1e")); + EXPECT_EQ(0x1eu, DecodeValidUint32(5, "\xfe")); + EXPECT_EQ(0x0eu, DecodeValidUint32(4, "\x0e")); + EXPECT_EQ(0x0eu, DecodeValidUint32(4, "\xfe")); + EXPECT_EQ(0x06u, DecodeValidUint32(3, "\x06")); + EXPECT_EQ(0x06u, DecodeValidUint32(3, "\xfe")); + EXPECT_EQ(0x02u, DecodeValidUint32(2, "\x02")); + EXPECT_EQ(0x02u, DecodeValidUint32(2, "\xfe")); + EXPECT_EQ(0x00u, DecodeValidUint32(1, string("\x00", 1))); + EXPECT_EQ(0x00u, DecodeValidUint32(1, string("\xfe", 1))); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f"); + ExpectDecodeUint32Invalid(7, "\xff"); + ExpectDecodeUint32Invalid(6, "\x3f"); + ExpectDecodeUint32Invalid(6, "\xff"); + ExpectDecodeUint32Invalid(5, "\x1f"); + ExpectDecodeUint32Invalid(5, "\xff"); + ExpectDecodeUint32Invalid(4, "\x0f"); + ExpectDecodeUint32Invalid(4, "\xff"); + ExpectDecodeUint32Invalid(3, "\x07"); + ExpectDecodeUint32Invalid(3, "\xff"); + ExpectDecodeUint32Invalid(2, "\x03"); + ExpectDecodeUint32Invalid(2, "\xff"); + ExpectDecodeUint32Invalid(1, "\x01"); + ExpectDecodeUint32Invalid(1, "\xff"); +} + +TEST_F(HpackInputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0x7fu, DecodeValidUint32(7, string("\x7f\x00", 2))); + EXPECT_EQ(0x7fu, DecodeValidUint32(7, string("\xff\x00", 2))); + EXPECT_EQ(0x3fu, DecodeValidUint32(6, string("\x3f\x00", 2))); + EXPECT_EQ(0x3fu, DecodeValidUint32(6, string("\xff\x00", 2))); + EXPECT_EQ(0x1fu, DecodeValidUint32(5, string("\x1f\x00", 2))); + EXPECT_EQ(0x1fu, DecodeValidUint32(5, string("\xff\x00", 2))); + EXPECT_EQ(0x0fu, DecodeValidUint32(4, string("\x0f\x00", 2))); + EXPECT_EQ(0x0fu, DecodeValidUint32(4, string("\xff\x00", 2))); + EXPECT_EQ(0x07u, DecodeValidUint32(3, string("\x07\x00", 2))); + EXPECT_EQ(0x07u, DecodeValidUint32(3, string("\xff\x00", 2))); + EXPECT_EQ(0x03u, DecodeValidUint32(2, string("\x03\x00", 2))); + EXPECT_EQ(0x03u, DecodeValidUint32(2, string("\xff\x00", 2))); + EXPECT_EQ(0x01u, DecodeValidUint32(1, string("\x01\x00", 2))); + EXPECT_EQ(0x01u, DecodeValidUint32(1, string("\xff\x00", 2))); + + // Maximums. + EXPECT_EQ(0xfeu, DecodeValidUint32(7, "\x7f\x7f")); + EXPECT_EQ(0xfeu, DecodeValidUint32(7, "\xff\x7f")); + EXPECT_EQ(0xbeu, DecodeValidUint32(6, "\x3f\x7f")); + EXPECT_EQ(0xbeu, DecodeValidUint32(6, "\xff\x7f")); + EXPECT_EQ(0x9eu, DecodeValidUint32(5, "\x1f\x7f")); + EXPECT_EQ(0x9eu, DecodeValidUint32(5, "\xff\x7f")); + EXPECT_EQ(0x8eu, DecodeValidUint32(4, "\x0f\x7f")); + EXPECT_EQ(0x8eu, DecodeValidUint32(4, "\xff\x7f")); + EXPECT_EQ(0x86u, DecodeValidUint32(3, "\x07\x7f")); + EXPECT_EQ(0x86u, DecodeValidUint32(3, "\xff\x7f")); + EXPECT_EQ(0x82u, DecodeValidUint32(2, "\x03\x7f")); + EXPECT_EQ(0x82u, DecodeValidUint32(2, "\xff\x7f")); + EXPECT_EQ(0x80u, DecodeValidUint32(1, "\x01\x7f")); + EXPECT_EQ(0x80u, DecodeValidUint32(1, "\xff\x7f")); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f\x80"); + ExpectDecodeUint32Invalid(7, "\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\x80"); + ExpectDecodeUint32Invalid(6, "\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\x80"); + ExpectDecodeUint32Invalid(5, "\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\x80"); + ExpectDecodeUint32Invalid(4, "\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\x80"); + ExpectDecodeUint32Invalid(3, "\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\x80"); + ExpectDecodeUint32Invalid(2, "\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\x80"); + ExpectDecodeUint32Invalid(1, "\xff\xff"); +} + +TEST_F(HpackInputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0xffu, DecodeValidUint32(7, "\x7f\x80\x01")); + EXPECT_EQ(0xffu, DecodeValidUint32(7, "\xff\x80\x01")); + EXPECT_EQ(0xbfu, DecodeValidUint32(6, "\x3f\x80\x01")); + EXPECT_EQ(0xbfu, DecodeValidUint32(6, "\xff\x80\x01")); + EXPECT_EQ(0x9fu, DecodeValidUint32(5, "\x1f\x80\x01")); + EXPECT_EQ(0x9fu, DecodeValidUint32(5, "\xff\x80\x01")); + EXPECT_EQ(0x8fu, DecodeValidUint32(4, "\x0f\x80\x01")); + EXPECT_EQ(0x8fu, DecodeValidUint32(4, "\xff\x80\x01")); + EXPECT_EQ(0x87u, DecodeValidUint32(3, "\x07\x80\x01")); + EXPECT_EQ(0x87u, DecodeValidUint32(3, "\xff\x80\x01")); + EXPECT_EQ(0x83u, DecodeValidUint32(2, "\x03\x80\x01")); + EXPECT_EQ(0x83u, DecodeValidUint32(2, "\xff\x80\x01")); + EXPECT_EQ(0x81u, DecodeValidUint32(1, "\x01\x80\x01")); + EXPECT_EQ(0x81u, DecodeValidUint32(1, "\xff\x80\x01")); + + // Maximums. + EXPECT_EQ(0x407eu, DecodeValidUint32(7, "\x7f\xff\x7f")); + EXPECT_EQ(0x407eu, DecodeValidUint32(7, "\xff\xff\x7f")); + EXPECT_EQ(0x403eu, DecodeValidUint32(6, "\x3f\xff\x7f")); + EXPECT_EQ(0x403eu, DecodeValidUint32(6, "\xff\xff\x7f")); + EXPECT_EQ(0x401eu, DecodeValidUint32(5, "\x1f\xff\x7f")); + EXPECT_EQ(0x401eu, DecodeValidUint32(5, "\xff\xff\x7f")); + EXPECT_EQ(0x400eu, DecodeValidUint32(4, "\x0f\xff\x7f")); + EXPECT_EQ(0x400eu, DecodeValidUint32(4, "\xff\xff\x7f")); + EXPECT_EQ(0x4006u, DecodeValidUint32(3, "\x07\xff\x7f")); + EXPECT_EQ(0x4006u, DecodeValidUint32(3, "\xff\xff\x7f")); + EXPECT_EQ(0x4002u, DecodeValidUint32(2, "\x03\xff\x7f")); + EXPECT_EQ(0x4002u, DecodeValidUint32(2, "\xff\xff\x7f")); + EXPECT_EQ(0x4000u, DecodeValidUint32(1, "\x01\xff\x7f")); + EXPECT_EQ(0x4000u, DecodeValidUint32(1, "\xff\xff\x7f")); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f\xff\x80"); + ExpectDecodeUint32Invalid(7, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\xff\x80"); + ExpectDecodeUint32Invalid(6, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\xff\x80"); + ExpectDecodeUint32Invalid(5, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\xff\x80"); + ExpectDecodeUint32Invalid(4, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\xff\x80"); + ExpectDecodeUint32Invalid(3, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\xff\x80"); + ExpectDecodeUint32Invalid(2, "\xff\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\xff\x80"); + ExpectDecodeUint32Invalid(1, "\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, FourByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0x407fu, DecodeValidUint32(7, "\x7f\x80\x80\x01")); + EXPECT_EQ(0x407fu, DecodeValidUint32(7, "\xff\x80\x80\x01")); + EXPECT_EQ(0x403fu, DecodeValidUint32(6, "\x3f\x80\x80\x01")); + EXPECT_EQ(0x403fu, DecodeValidUint32(6, "\xff\x80\x80\x01")); + EXPECT_EQ(0x401fu, DecodeValidUint32(5, "\x1f\x80\x80\x01")); + EXPECT_EQ(0x401fu, DecodeValidUint32(5, "\xff\x80\x80\x01")); + EXPECT_EQ(0x400fu, DecodeValidUint32(4, "\x0f\x80\x80\x01")); + EXPECT_EQ(0x400fu, DecodeValidUint32(4, "\xff\x80\x80\x01")); + EXPECT_EQ(0x4007u, DecodeValidUint32(3, "\x07\x80\x80\x01")); + EXPECT_EQ(0x4007u, DecodeValidUint32(3, "\xff\x80\x80\x01")); + EXPECT_EQ(0x4003u, DecodeValidUint32(2, "\x03\x80\x80\x01")); + EXPECT_EQ(0x4003u, DecodeValidUint32(2, "\xff\x80\x80\x01")); + EXPECT_EQ(0x4001u, DecodeValidUint32(1, "\x01\x80\x80\x01")); + EXPECT_EQ(0x4001u, DecodeValidUint32(1, "\xff\x80\x80\x01")); + + // Maximums. + EXPECT_EQ(0x20007eu, DecodeValidUint32(7, "\x7f\xff\xff\x7f")); + EXPECT_EQ(0x20007eu, DecodeValidUint32(7, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x20003eu, DecodeValidUint32(6, "\x3f\xff\xff\x7f")); + EXPECT_EQ(0x20003eu, DecodeValidUint32(6, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x20001eu, DecodeValidUint32(5, "\x1f\xff\xff\x7f")); + EXPECT_EQ(0x20001eu, DecodeValidUint32(5, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x20000eu, DecodeValidUint32(4, "\x0f\xff\xff\x7f")); + EXPECT_EQ(0x20000eu, DecodeValidUint32(4, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x200006u, DecodeValidUint32(3, "\x07\xff\xff\x7f")); + EXPECT_EQ(0x200006u, DecodeValidUint32(3, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x200002u, DecodeValidUint32(2, "\x03\xff\xff\x7f")); + EXPECT_EQ(0x200002u, DecodeValidUint32(2, "\xff\xff\xff\x7f")); + EXPECT_EQ(0x200000u, DecodeValidUint32(1, "\x01\xff\xff\x7f")); + EXPECT_EQ(0x200000u, DecodeValidUint32(1, "\xff\xff\xff\x7f")); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f\xff\xff\x80"); + ExpectDecodeUint32Invalid(7, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\xff\xff\x80"); + ExpectDecodeUint32Invalid(6, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\xff\xff\x80"); + ExpectDecodeUint32Invalid(5, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\xff\xff\x80"); + ExpectDecodeUint32Invalid(4, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\xff\xff\x80"); + ExpectDecodeUint32Invalid(3, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\xff\xff\x80"); + ExpectDecodeUint32Invalid(2, "\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\xff\xff\x80"); + ExpectDecodeUint32Invalid(1, "\xff\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0x20007fu, DecodeValidUint32(7, "\x7f\x80\x80\x80\x01")); + EXPECT_EQ(0x20007fu, DecodeValidUint32(7, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x20003fu, DecodeValidUint32(6, "\x3f\x80\x80\x80\x01")); + EXPECT_EQ(0x20003fu, DecodeValidUint32(6, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x20001fu, DecodeValidUint32(5, "\x1f\x80\x80\x80\x01")); + EXPECT_EQ(0x20001fu, DecodeValidUint32(5, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x20000fu, DecodeValidUint32(4, "\x0f\x80\x80\x80\x01")); + EXPECT_EQ(0x20000fu, DecodeValidUint32(4, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x200007u, DecodeValidUint32(3, "\x07\x80\x80\x80\x01")); + EXPECT_EQ(0x200007u, DecodeValidUint32(3, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x200003u, DecodeValidUint32(2, "\x03\x80\x80\x80\x01")); + EXPECT_EQ(0x200003u, DecodeValidUint32(2, "\xff\x80\x80\x80\x01")); + EXPECT_EQ(0x200001u, DecodeValidUint32(1, "\x01\x80\x80\x80\x01")); + EXPECT_EQ(0x200001u, DecodeValidUint32(1, "\xff\x80\x80\x80\x01")); + + // Maximums. + EXPECT_EQ(0x1000007eu, DecodeValidUint32(7, "\x7f\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000007eu, DecodeValidUint32(7, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000003eu, DecodeValidUint32(6, "\x3f\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000003eu, DecodeValidUint32(6, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000001eu, DecodeValidUint32(5, "\x1f\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000001eu, DecodeValidUint32(5, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000000eu, DecodeValidUint32(4, "\x0f\xff\xff\xff\x7f")); + EXPECT_EQ(0x1000000eu, DecodeValidUint32(4, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000006u, DecodeValidUint32(3, "\x07\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000006u, DecodeValidUint32(3, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000002u, DecodeValidUint32(2, "\x03\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000002u, DecodeValidUint32(2, "\xff\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000000u, DecodeValidUint32(1, "\x01\xff\xff\xff\x7f")); + EXPECT_EQ(0x10000000u, DecodeValidUint32(1, "\xff\xff\xff\xff\x7f")); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(7, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(6, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(5, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(4, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(3, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(2, "\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\xff\xff\xff\x80"); + ExpectDecodeUint32Invalid(1, "\xff\xff\xff\xff\xff"); +} + +TEST_F(HpackInputStreamTest, SixByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(0x1000007fu, DecodeValidUint32(7, "\x7f\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000007fu, DecodeValidUint32(7, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000003fu, DecodeValidUint32(6, "\x3f\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000003fu, DecodeValidUint32(6, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000001fu, DecodeValidUint32(5, "\x1f\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000001fu, DecodeValidUint32(5, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000000fu, DecodeValidUint32(4, "\x0f\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x1000000fu, DecodeValidUint32(4, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000007u, DecodeValidUint32(3, "\x07\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000007u, DecodeValidUint32(3, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000003u, DecodeValidUint32(2, "\x03\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000003u, DecodeValidUint32(2, "\xff\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000001u, DecodeValidUint32(1, "\x01\x80\x80\x80\x80\x01")); + EXPECT_EQ(0x10000001u, DecodeValidUint32(1, "\xff\x80\x80\x80\x80\x01")); + + // Maximums. + EXPECT_EQ(0xffffffffu, DecodeValidUint32(7, "\x7f\x80\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(7, "\xff\x80\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(6, "\x3f\xc0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(6, "\xff\xc0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(5, "\x1f\xe0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(5, "\xff\xe0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(4, "\x0f\xf0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(4, "\xff\xf0\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(3, "\x07\xf8\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(3, "\xff\xf8\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(2, "\x03\xfc\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(2, "\xff\xfc\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(1, "\x01\xfe\xff\xff\xff\x0f")); + EXPECT_EQ(0xffffffffu, DecodeValidUint32(1, "\xff\xfe\xff\xff\xff\x0f")); + + // Invalid. + ExpectDecodeUint32Invalid(7, "\x7f\x80\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(7, "\xff\x80\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\xc0\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(6, "\xff\xc0\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\xe0\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(5, "\xff\xe0\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\xf0\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(4, "\xff\xf0\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\xf8\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(3, "\xff\xf8\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\xfc\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(2, "\xff\xfc\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\xfe\xff\xff\xff\x10"); + ExpectDecodeUint32Invalid(1, "\xff\xfe\xff\xff\xff\xff"); +} + +// There are no valid uint32 encodings that are greater than six +// bytes. +TEST_F(HpackInputStreamTest, SevenByteIntegersOneToSevenBitPrefixes) { + ExpectDecodeUint32Invalid(7, "\x7f\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(7, "\x7f\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(7, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(6, "\x3f\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(6, "\x3f\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(6, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(5, "\x1f\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(5, "\x1f\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(5, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(4, "\x0f\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(4, "\x0f\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(4, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(3, "\x07\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(3, "\x07\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(3, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(2, "\x03\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(2, "\x03\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(2, "\xff\xff\xff\xff\xff\xff\xff"); + ExpectDecodeUint32Invalid(1, "\x01\x80\x80\x80\x80\x80\x00"); + ExpectDecodeUint32Invalid(1, "\x01\x80\x80\x80\x80\x80\x01"); + ExpectDecodeUint32Invalid(1, "\xff\xff\xff\xff\xff\xff\xff"); +} + +// Decoding a valid encoded string literal should work. +TEST_F(HpackInputStreamTest, DecodeNextIdentityString) { + HpackInputStream input_stream(kLiteralBound, "\x0estring literal"); + + EXPECT_TRUE(input_stream.HasMoreData()); + StringPiece string_piece; + EXPECT_TRUE(input_stream.DecodeNextIdentityString(&string_piece)); + EXPECT_EQ("string literal", string_piece); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +// Decoding an encoded string literal with size larger than +// |max_string_literal_size_| should fail. +TEST_F(HpackInputStreamTest, DecodeNextIdentityStringSizeLimit) { + HpackInputStream input_stream(13, "\x0estring literal"); + + EXPECT_TRUE(input_stream.HasMoreData()); + StringPiece string_piece; + EXPECT_FALSE(input_stream.DecodeNextIdentityString(&string_piece)); +} + +// Decoding an encoded string literal with size larger than the +// remainder of the buffer should fail. +TEST_F(HpackInputStreamTest, DecodeNextIdentityStringNotEnoughInput) { + // Set the length to be one more than it should be. + HpackInputStream input_stream(kLiteralBound, "\x0fstring literal"); + + EXPECT_TRUE(input_stream.HasMoreData()); + StringPiece string_piece; + EXPECT_FALSE(input_stream.DecodeNextIdentityString(&string_piece)); +} + +TEST_F(HpackInputStreamTest, DecodeNextHuffmanString) { + string output, input(a2b_hex(kEncodedHuffmanFixture)); + HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 1, input); + + EXPECT_TRUE(input_stream.HasMoreData()); + EXPECT_TRUE(input_stream.DecodeNextHuffmanString(huffman_table_, &output)); + EXPECT_EQ(kDecodedHuffmanFixture, output); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +TEST_F(HpackInputStreamTest, DecodeNextHuffmanStringSizeLimit) { + string output, input(a2b_hex(kEncodedHuffmanFixture)); + // Max string literal is one byte shorter than the decoded fixture. + HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 2, input); + + // Decoded string overflows the max string literal. + EXPECT_TRUE(input_stream.HasMoreData()); + EXPECT_FALSE(input_stream.DecodeNextHuffmanString(huffman_table_, &output)); +} + +TEST_F(HpackInputStreamTest, DecodeNextHuffmanStringNotEnoughInput) { + string output, input(a2b_hex(kEncodedHuffmanFixture)); + input[0]++; // Input prefix is one byte larger than available input. + HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 1, input); + + // Not enough buffer for declared encoded length. + EXPECT_TRUE(input_stream.HasMoreData()); + EXPECT_FALSE(input_stream.DecodeNextHuffmanString(huffman_table_, &output)); +} + +TEST_F(HpackInputStreamTest, PeekBitsAndConsume) { + HpackInputStream input_stream(kLiteralBound, "\xad\xab\xad\xab\xad"); + + uint32 bits = 0; + size_t peeked_count = 0; + + // Read 0xad. + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10101101000000000000000000000000"), bits); + EXPECT_EQ(8u, peeked_count); + + // Read 0xab. + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10101101101010110000000000000000"), bits); + EXPECT_EQ(16u, peeked_count); + + input_stream.ConsumeBits(5); + bits = bits << 5; + peeked_count -= 5; + EXPECT_EQ(bits32("10110101011000000000000000000000"), bits); + EXPECT_EQ(11u, peeked_count); + + // Read 0xad. + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10110101011101011010000000000000"), bits); + EXPECT_EQ(19u, peeked_count); + + // Read 0xab. + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10110101011101011011010101100000"), bits); + EXPECT_EQ(27u, peeked_count); + + // Read 0xa, and 1 bit of 0xd + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10110101011101011011010101110101"), bits); + EXPECT_EQ(32u, peeked_count); + + // |bits| is full, and doesn't change. + EXPECT_FALSE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10110101011101011011010101110101"), bits); + EXPECT_EQ(32u, peeked_count); + + input_stream.ConsumeBits(27); + bits = bits << 27; + peeked_count -= 27; + EXPECT_EQ(bits32("10101000000000000000000000000000"), bits); + EXPECT_EQ(5u, peeked_count); + + // Read remaining 3 bits of 0xd. + EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10101101000000000000000000000000"), bits); + EXPECT_EQ(8u, peeked_count); + + // EOF. + EXPECT_FALSE(input_stream.PeekBits(&peeked_count, &bits)); + EXPECT_EQ(bits32("10101101000000000000000000000000"), bits); + EXPECT_EQ(8u, peeked_count); + + input_stream.ConsumeBits(8); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +TEST_F(HpackInputStreamTest, ConsumeByteRemainder) { + HpackInputStream input_stream(kLiteralBound, "\xad\xab"); + // Does nothing. + input_stream.ConsumeByteRemainder(); + + // Consumes one byte. + input_stream.ConsumeBits(3); + input_stream.ConsumeByteRemainder(); + EXPECT_TRUE(input_stream.HasMoreData()); + + input_stream.ConsumeBits(6); + EXPECT_TRUE(input_stream.HasMoreData()); + input_stream.ConsumeByteRemainder(); + EXPECT_FALSE(input_stream.HasMoreData()); +} + +} // namespace + +} // namespace net diff --git a/net/spdy/hpack/hpack_output_stream.cc b/net/spdy/hpack/hpack_output_stream.cc new file mode 100644 index 0000000..d2342b1 --- /dev/null +++ b/net/spdy/hpack/hpack_output_stream.cc @@ -0,0 +1,75 @@ +// 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/spdy/hpack/hpack_output_stream.h" + +#include "base/logging.h" + +namespace net { + +using base::StringPiece; +using std::string; + +HpackOutputStream::HpackOutputStream() : bit_offset_(0) {} + +HpackOutputStream::~HpackOutputStream() {} + +void HpackOutputStream::AppendBits(uint8 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_.rbegin() |= 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_.rbegin() |= 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(StringPiece buffer) { + DCHECK_EQ(bit_offset_, 0u); + buffer_.append(buffer.data(), buffer.size()); +} + +void HpackOutputStream::AppendUint32(uint32 I) { + // The algorithm below is adapted from the pseudocode in 6.1. + size_t N = 8 - bit_offset_; + uint8 max_first_byte = static_cast<uint8>((1 << N) - 1); + if (I < max_first_byte) { + AppendBits(static_cast<uint8>(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>(I), 8); + } +} + +void HpackOutputStream::TakeString(string* 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; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_output_stream.h b/net/spdy/hpack/hpack_output_stream.h new file mode 100644 index 0000000..5063900 --- /dev/null +++ b/net/spdy/hpack/hpack_output_stream.h @@ -0,0 +1,66 @@ +// 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 NET_SPDY_HPACK_OUTPUT_STREAM_H_ +#define NET_SPDY_HPACK_OUTPUT_STREAM_H_ + +#include <map> +#include <string> + +#include "base/basictypes.h" +#include "base/macros.h" +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_constants.h" + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +namespace net { + +// An HpackOutputStream handles all the low-level details of encoding +// header fields. +class NET_EXPORT_PRIVATE HpackOutputStream { + public: + explicit HpackOutputStream(); + ~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 bits, size_t bit_size); + + // Simply forwards to AppendBits(prefix.bits, prefix.bit-size). + void AppendPrefix(HpackPrefix prefix); + + // Directly appends |buffer|. + void AppendBytes(base::StringPiece 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 I); + + // Swaps the interal buffer with |output|. + void TakeString(std::string* output); + + private: + // The internal bit buffer. + std::string buffer_; + + // If 0, the buffer ends on a byte boundary. If non-zero, the buffer + // ends on the most significant nth bit. Guaranteed to be < 8. + size_t bit_offset_; + + DISALLOW_COPY_AND_ASSIGN(HpackOutputStream); +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_OUTPUT_STREAM_H_ diff --git a/net/spdy/hpack/hpack_output_stream_test.cc b/net/spdy/hpack/hpack_output_stream_test.cc new file mode 100644 index 0000000..48b5dcc --- /dev/null +++ b/net/spdy/hpack/hpack_output_stream_test.cc @@ -0,0 +1,260 @@ +// 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/spdy/hpack/hpack_output_stream.h" + +#include <cstddef> + +#include "base/basictypes.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +namespace { + +using std::string; + +// 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; + string expected_str; + + output_stream.AppendBits(0x1, 1); + expected_str.append(1, 0x00); + *expected_str.rbegin() |= (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.rbegin() |= (0x7 << 7); + + output_stream.AppendBits(0x0, 7); + + string str; + output_stream.TakeString(&str); + EXPECT_EQ(expected_str, str); +} + +// Utility function to return I as a string encoded with an N-bit +// prefix. +string EncodeUint32(uint8 N, uint32 I) { + HpackOutputStream output_stream; + if (N < 8) { + output_stream.AppendBits(0x00, 8 - N); + } + output_stream.AppendUint32(I); + string 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(string("\x00", 1), EncodeUint32(8, 0x00)); + EXPECT_EQ("\x7f", EncodeUint32(8, 0x7f)); + // Maximum. + EXPECT_EQ("\xfe", EncodeUint32(8, 0xfe)); +} + +TEST(HpackOutputStreamTest, TwoByteIntegersEightBitPrefix) { + // Minimum. + EXPECT_EQ(string("\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(string("\x00", 1), EncodeUint32(7, 0x00)); + EXPECT_EQ(string("\x00", 1), EncodeUint32(6, 0x00)); + EXPECT_EQ(string("\x00", 1), EncodeUint32(5, 0x00)); + EXPECT_EQ(string("\x00", 1), EncodeUint32(4, 0x00)); + EXPECT_EQ(string("\x00", 1), EncodeUint32(3, 0x00)); + EXPECT_EQ(string("\x00", 1), EncodeUint32(2, 0x00)); + EXPECT_EQ(string("\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(string("\x00", 1), EncodeUint32(1, 0x00)); +} + +TEST(HpackOutputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) { + // Minimums. + EXPECT_EQ(string("\x7f\x00", 2), EncodeUint32(7, 0x7f)); + EXPECT_EQ(string("\x3f\x00", 2), EncodeUint32(6, 0x3f)); + EXPECT_EQ(string("\x1f\x00", 2), EncodeUint32(5, 0x1f)); + EXPECT_EQ(string("\x0f\x00", 2), EncodeUint32(4, 0x0f)); + EXPECT_EQ(string("\x07\x00", 2), EncodeUint32(3, 0x07)); + EXPECT_EQ(string("\x03\x00", 2), EncodeUint32(2, 0x03)); + EXPECT_EQ(string("\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); + string str; + output_stream.TakeString(&str); + EXPECT_EQ(string("\xff\x00", 2), str); +} + +TEST(HpackOutputStreamTest, AppendBytes) { + HpackOutputStream output_stream; + + output_stream.AppendBytes("buffer1"); + output_stream.AppendBytes("buffer2"); + + string str; + output_stream.TakeString(&str); + EXPECT_EQ("buffer1buffer2", str); +} + +} // namespace + +} // namespace net diff --git a/net/spdy/hpack/hpack_round_trip_test.cc b/net/spdy/hpack/hpack_round_trip_test.cc new file mode 100644 index 0000000..1dd2f6e --- /dev/null +++ b/net/spdy/hpack/hpack_round_trip_test.cc @@ -0,0 +1,182 @@ +// 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 <ctime> +#include <map> +#include <string> +#include <vector> + +#include "base/rand_util.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_decoder.h" +#include "net/spdy/hpack/hpack_encoder.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +using std::map; +using std::string; +using std::vector; + +namespace { + +class HpackRoundTripTest : public ::testing::Test { + protected: + HpackRoundTripTest() + : encoder_(ObtainHpackHuffmanTable()), + decoder_(ObtainHpackHuffmanTable()) {} + + void SetUp() override { + // Use a small table size to tickle eviction handling. + encoder_.ApplyHeaderTableSizeSetting(256); + decoder_.ApplyHeaderTableSizeSetting(256); + } + + bool RoundTrip(const SpdyHeaderBlock& header_set) { + string encoded; + encoder_.EncodeHeaderSet(header_set, &encoded); + + bool success = decoder_.HandleControlFrameHeadersData(1, encoded.data(), + encoded.size()); + success &= decoder_.HandleControlFrameHeadersComplete(1, 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(base::RandDouble()) * mean, sanity_bound); + } + + HpackEncoder encoder_; + HpackDecoder decoder_; +}; + +TEST_F(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"] = string("foo\0bar", 7); + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_F(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"] = string("foo\0bar", 7); + EXPECT_TRUE(RoundTrip(headers)); + } +} + +TEST_F(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. + vector<string> names; + names.push_back(":authority"); + names.push_back(":path"); + 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. + + vector<string> 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"); + + int seed = std::time(NULL); + LOG(INFO) << "Seeding with srand(" << seed << ")"; + srand(seed); + + for (size_t i = 0; i != 2000; ++i) { + SpdyHeaderBlock headers; + + size_t header_count = 1 + SampleExponential(7, 50); + for (size_t j = 0; j != header_count; ++j) { + size_t name_index = SampleExponential(20, 200); + size_t value_index = SampleExponential(20, 200); + + string name, value; + if (name_index >= names.size()) { + names.push_back(base::RandBytesAsString(1 + SampleExponential(5, 30))); + name = names.back(); + } else { + name = names[name_index]; + } + if (value_index >= values.size()) { + string newvalue = + base::RandBytesAsString(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 net diff --git a/net/spdy/hpack/hpack_static_table.cc b/net/spdy/hpack/hpack_static_table.cc new file mode 100644 index 0000000..8ee1d0b --- /dev/null +++ b/net/spdy/hpack/hpack_static_table.cc @@ -0,0 +1,38 @@ +// 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/spdy/hpack/hpack_static_table.h" + +#include "base/logging.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "net/spdy/hpack/hpack_entry.h" + +namespace net { + +HpackStaticTable::HpackStaticTable() {} + +HpackStaticTable::~HpackStaticTable() {} + +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(StringPiece(it->name, it->name_len), + StringPiece(it->value, it->value_len), + true, // is_static + total_insertions)); + CHECK(static_index_.insert(&static_entries_.back()).second); + + ++total_insertions; + } +} + +bool HpackStaticTable::IsInitialized() const { + return !static_entries_.empty(); +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_static_table.h b/net/spdy/hpack/hpack_static_table.h new file mode 100644 index 0000000..e7e0fd4 --- /dev/null +++ b/net/spdy/hpack/hpack_static_table.h @@ -0,0 +1,46 @@ +// 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 NET_SPDY_HPACK_STATIC_TABLE_H_ +#define NET_SPDY_HPACK_STATIC_TABLE_H_ + +#include "net/spdy/hpack/hpack_header_table.h" + +namespace net { + +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 NET_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::OrderedEntrySet& GetStaticIndex() const { + return static_index_; + } + + private: + HpackHeaderTable::EntryTable static_entries_; + HpackHeaderTable::OrderedEntrySet static_index_; +}; + +} // namespace net + +#endif // NET_SPDY_HPACK_STATIC_TABLE_H_ diff --git a/net/spdy/hpack/hpack_static_table_test.cc b/net/spdy/hpack/hpack_static_table_test.cc new file mode 100644 index 0000000..441668f --- /dev/null +++ b/net/spdy/hpack/hpack_static_table_test.cc @@ -0,0 +1,51 @@ +// 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/spdy/hpack/hpack_static_table.h" + +#include <vector> + +#include "net/base/net_export.h" +#include "net/spdy/hpack/hpack_constants.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +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()); + std::vector<HpackStaticEntry> static_table = HpackStaticTableVector(); + table_.Initialize(&static_table[0], static_table.size()); + EXPECT_TRUE(table_.IsInitialized()); + + HpackHeaderTable::EntryTable static_entries = table_.GetStaticEntries(); + EXPECT_EQ(static_table.size(), static_entries.size()); + + HpackHeaderTable::OrderedEntrySet static_index = table_.GetStaticIndex(); + EXPECT_EQ(static_table.size(), static_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 net diff --git a/net/spdy/hpack/hpack_string_util.cc b/net/spdy/hpack/hpack_string_util.cc new file mode 100644 index 0000000..3f59291 --- /dev/null +++ b/net/spdy/hpack/hpack_string_util.cc @@ -0,0 +1,24 @@ +// 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/spdy/hpack/hpack_string_util.h" + +#include "base/basictypes.h" + +namespace net { + +bool StringPiecesEqualConstantTime(base::StringPiece str1, + base::StringPiece str2) { + size_t size = str1.size(); + if (str2.size() != size) + return false; + + uint8 x = 0; + for (size_t i = 0; i < size; ++i) { + x |= str1[i] ^ str2[i]; + } + return x == 0; +} + +} // namespace net diff --git a/net/spdy/hpack/hpack_string_util.h b/net/spdy/hpack/hpack_string_util.h new file mode 100644 index 0000000..22ffb56 --- /dev/null +++ b/net/spdy/hpack/hpack_string_util.h @@ -0,0 +1,22 @@ +// 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 NET_SPDY_HPACK_STRING_UTIL_H_ +#define NET_SPDY_HPACK_STRING_UTIL_H_ + +#include "base/strings/string_piece.h" +#include "net/base/net_export.h" + +namespace net { + +// All section references below are to +// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-08 + +// A constant-time StringPiece comparison function. +bool NET_EXPORT_PRIVATE StringPiecesEqualConstantTime(base::StringPiece str1, + base::StringPiece str2); + +} // namespace net + +#endif // NET_SPDY_HPACK_STRING_UTIL_H_ diff --git a/net/spdy/hpack/hpack_string_util_test.cc b/net/spdy/hpack/hpack_string_util_test.cc new file mode 100644 index 0000000..e1576fc --- /dev/null +++ b/net/spdy/hpack/hpack_string_util_test.cc @@ -0,0 +1,98 @@ +// 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/spdy/hpack/hpack_string_util.h" + +#include <cstddef> +#include <cstring> + +#include "base/basictypes.h" +#include "base/logging.h" +#include "base/strings/string_piece.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace net { + +namespace { + +using std::string; + +// Make sure StringPiecesEqualConstantTime() behaves like the regular +// string equality operator. +TEST(HpackStringUtilTest, StringPiecesEqualConstantTime) { + EXPECT_TRUE(StringPiecesEqualConstantTime("foo", "foo")); + EXPECT_FALSE(StringPiecesEqualConstantTime("foo", "foox")); + EXPECT_FALSE(StringPiecesEqualConstantTime("foo", "bar")); +} + +// TODO(jgraettinger): Support this benchmark. +/* +enum BM_StringPieceEqualityType { + STRCMP_EQUAL, + STRCMP_FIRST_CHAR_DIFFERS, + STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL, + STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS, +}; + +void BM_StringPieceEquality(int iters, int size, int type_int) { + BM_StringPieceEqualityType type = + static_cast<BM_StringPieceEqualityType>(type_int); + string str_a(size, 'x'); + string str_b(size, 'x'); + int result = 0; + switch (type) { + case STRCMP_EQUAL: + for (int i = 0; i < iters; ++i) { + result |= std::strcmp(str_a.c_str(), str_b.c_str()); + } + CHECK_EQ(result, 0); + return; + + case STRCMP_FIRST_CHAR_DIFFERS: + str_b[0] = 'y'; + for (int i = 0; i < iters; ++i) { + result |= std::strcmp(str_a.c_str(), str_b.c_str()); + } + CHECK_LT(result, 0); + return; + + case STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL: + for (int i = 0; i < iters; ++i) { + result |= StringPiecesEqualConstantTime(str_a, str_b); + } + CHECK_EQ(result, 1); + return; + + case STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS: + str_b[0] = 'y'; + for (int i = 0; i < iters; ++i) { + result |= StringPiecesEqualConstantTime(str_a, str_b); + } + CHECK_EQ(result, 0); + return; + } + + DCHECK(false); +} + +// Results should resemble the table below, where 0 and 1 are clearly +// different (STRCMP), but 2 and 3 are roughly the same +// (STRING_PIECES_EQUAL_CONSTANT_TIME). +// +// DEBUG: Benchmark Time(ns) CPU(ns) Iterations +// ------------------------------------------------------------------- +// DEBUG: BM_StringPieceEquality/1M/0 77796 77141 7778 +// DEBUG: BM_StringPieceEquality/1M/1 10 10 70000000 +// DEBUG: BM_StringPieceEquality/1M/2 7729735 7700000 100 +// DEBUG: BM_StringPieceEquality/1M/3 7803051 7800000 100 +BENCHMARK(BM_StringPieceEquality) + ->ArgPair(1<<20, STRCMP_EQUAL) + ->ArgPair(1<<20, STRCMP_FIRST_CHAR_DIFFERS) + ->ArgPair(1<<20, STRING_PIECES_EQUAL_CONSTANT_TIME_EQUAL) + ->ArgPair(1<<20, STRING_PIECES_EQUAL_CONSTANT_TIME_FIRST_CHAR_DIFFERS); +*/ + +} // namespace + +} // namespace net |