OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/spdy/hpack_huffman_table.h" | 5 #include "net/spdy/hpack_huffman_table.h" |
6 | 6 |
7 #include <bitset> | 7 #include <bitset> |
8 #include <string> | 8 #include <string> |
9 | 9 |
10 #include "base/logging.h" | 10 #include "base/logging.h" |
(...skipping 12 matching lines...) Expand all Loading... |
23 namespace net { | 23 namespace net { |
24 | 24 |
25 namespace test { | 25 namespace test { |
26 | 26 |
27 typedef HpackHuffmanTable::DecodeEntry DecodeEntry; | 27 typedef HpackHuffmanTable::DecodeEntry DecodeEntry; |
28 typedef HpackHuffmanTable::DecodeTable DecodeTable; | 28 typedef HpackHuffmanTable::DecodeTable DecodeTable; |
29 | 29 |
30 class HpackHuffmanTablePeer { | 30 class HpackHuffmanTablePeer { |
31 public: | 31 public: |
32 explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table) | 32 explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table) |
33 : table_(table) { } | 33 : table_(table) {} |
34 | 34 |
35 const std::vector<uint32>& code_by_id() const { | 35 const std::vector<uint32>& code_by_id() const { return table_.code_by_id_; } |
36 return table_.code_by_id_; | |
37 } | |
38 const std::vector<uint8>& length_by_id() const { | 36 const std::vector<uint8>& length_by_id() const { |
39 return table_.length_by_id_; | 37 return table_.length_by_id_; |
40 } | 38 } |
41 const std::vector<DecodeTable>& decode_tables() const { | 39 const std::vector<DecodeTable>& decode_tables() const { |
42 return table_.decode_tables_; | 40 return table_.decode_tables_; |
43 } | 41 } |
44 char pad_bits() const { | 42 char pad_bits() const { |
45 // Cast to match signed-ness of bits8(). | 43 // Cast to match signed-ness of bits8(). |
46 return static_cast<char>(table_.pad_bits_); | 44 return static_cast<char>(table_.pad_bits_); |
47 } | 45 } |
48 uint16 failed_symbol_id() const { | 46 uint16 failed_symbol_id() const { return table_.failed_symbol_id_; } |
49 return table_.failed_symbol_id_; | |
50 } | |
51 std::vector<DecodeEntry> decode_entries(const DecodeTable& decode_table) { | 47 std::vector<DecodeEntry> decode_entries(const DecodeTable& decode_table) { |
52 std::vector<DecodeEntry>::const_iterator begin = | 48 std::vector<DecodeEntry>::const_iterator begin = |
53 table_.decode_entries_.begin() + decode_table.entries_offset; | 49 table_.decode_entries_.begin() + decode_table.entries_offset; |
54 return std::vector<DecodeEntry>(begin, begin + decode_table.size()); | 50 return std::vector<DecodeEntry>(begin, begin + decode_table.size()); |
55 } | 51 } |
56 void DumpDecodeTable(const DecodeTable& table) { | 52 void DumpDecodeTable(const DecodeTable& table) { |
57 std::vector<DecodeEntry> entries = decode_entries(table); | 53 std::vector<DecodeEntry> entries = decode_entries(table); |
58 LOG(INFO) << "Table size " << (1 << table.indexed_length) | 54 LOG(INFO) << "Table size " << (1 << table.indexed_length) << " prefix " |
59 << " prefix " << unsigned(table.prefix_length) | 55 << unsigned(table.prefix_length) << " indexed " |
60 << " indexed " << unsigned(table.indexed_length); | 56 << unsigned(table.indexed_length); |
61 size_t i = 0; | 57 size_t i = 0; |
62 while (i != table.size()) { | 58 while (i != table.size()) { |
63 const DecodeEntry& entry = entries[i]; | 59 const DecodeEntry& entry = entries[i]; |
64 LOG(INFO) << i << ":" | 60 LOG(INFO) << i << ":" |
65 << " next_table " << unsigned(entry.next_table_index) | 61 << " next_table " << unsigned(entry.next_table_index) |
66 << " length " << unsigned(entry.length) | 62 << " length " << unsigned(entry.length) << " symbol " |
67 << " symbol " << unsigned(entry.symbol_id); | 63 << unsigned(entry.symbol_id); |
68 size_t j = 1; | 64 size_t j = 1; |
69 for (; (i + j) != table.size(); j++) { | 65 for (; (i + j) != table.size(); j++) { |
70 const DecodeEntry& next = entries[i + j]; | 66 const DecodeEntry& next = entries[i + j]; |
71 if (next.next_table_index != entry.next_table_index || | 67 if (next.next_table_index != entry.next_table_index || |
72 next.length != entry.length || | 68 next.length != entry.length || next.symbol_id != entry.symbol_id) |
73 next.symbol_id != entry.symbol_id) | |
74 break; | 69 break; |
75 } | 70 } |
76 if (j > 1) { | 71 if (j > 1) { |
77 LOG(INFO) << " (repeats " << j << " times)"; | 72 LOG(INFO) << " (repeats " << j << " times)"; |
78 } | 73 } |
79 i += j; | 74 i += j; |
80 } | 75 } |
81 } | 76 } |
82 | 77 |
83 private: | 78 private: |
84 const HpackHuffmanTable& table_; | 79 const HpackHuffmanTable& table_; |
85 }; | 80 }; |
86 | 81 |
87 namespace { | 82 namespace { |
88 | 83 |
89 class HpackHuffmanTableTest : public ::testing::Test { | 84 class HpackHuffmanTableTest : public ::testing::Test { |
90 protected: | 85 protected: |
91 HpackHuffmanTableTest() | 86 HpackHuffmanTableTest() : table_(), peer_(table_) {} |
92 : table_(), | |
93 peer_(table_) {} | |
94 | 87 |
95 string EncodeString(StringPiece input) { | 88 string EncodeString(StringPiece input) { |
96 string result; | 89 string result; |
97 HpackOutputStream output_stream; | 90 HpackOutputStream output_stream; |
98 table_.EncodeString(input, &output_stream); | 91 table_.EncodeString(input, &output_stream); |
99 | 92 |
100 output_stream.TakeString(&result); | 93 output_stream.TakeString(&result); |
101 // Verify EncodedSize() agrees with EncodeString(). | 94 // Verify EncodedSize() agrees with EncodeString(). |
102 EXPECT_EQ(result.size(), table_.EncodedSize(input)); | 95 EXPECT_EQ(result.size(), table_.EncodedSize(input)); |
103 return result; | 96 return result; |
104 } | 97 } |
105 | 98 |
106 HpackHuffmanTable table_; | 99 HpackHuffmanTable table_; |
107 HpackHuffmanTablePeer peer_; | 100 HpackHuffmanTablePeer peer_; |
108 }; | 101 }; |
109 | 102 |
110 MATCHER(DecodeEntryEq, "") { | 103 MATCHER(DecodeEntryEq, "") { |
111 const DecodeEntry& lhs = std::tr1::get<0>(arg); | 104 const DecodeEntry& lhs = std::tr1::get<0>(arg); |
112 const DecodeEntry& rhs = std::tr1::get<1>(arg); | 105 const DecodeEntry& rhs = std::tr1::get<1>(arg); |
113 return lhs.next_table_index == rhs.next_table_index && | 106 return lhs.next_table_index == rhs.next_table_index && |
114 lhs.length == rhs.length && | 107 lhs.length == rhs.length && lhs.symbol_id == rhs.symbol_id; |
115 lhs.symbol_id == rhs.symbol_id; | |
116 } | 108 } |
117 | 109 |
118 uint32 bits32(const string& bitstring) { | 110 uint32 bits32(const string& bitstring) { |
119 return std::bitset<32>(bitstring).to_ulong(); | 111 return std::bitset<32>(bitstring).to_ulong(); |
120 } | 112 } |
121 char bits8(const string& bitstring) { | 113 char bits8(const string& bitstring) { |
122 return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); | 114 return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); |
123 } | 115 } |
124 | 116 |
125 TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { | 117 TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { |
126 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 118 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
127 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 119 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
128 EXPECT_TRUE(table_.IsInitialized()); | 120 EXPECT_TRUE(table_.IsInitialized()); |
129 EXPECT_EQ(peer_.pad_bits(), bits8("11111111")); // First 8 bits of EOS. | 121 EXPECT_EQ(peer_.pad_bits(), bits8("11111111")); // First 8 bits of EOS. |
130 } | 122 } |
131 | 123 |
132 TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) { | 124 TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) { |
133 { | 125 { |
134 // Verify eight symbols can be encoded with 3 bits per symbol. | 126 // Verify eight symbols can be encoded with 3 bits per symbol. |
135 HpackHuffmanSymbol code[] = { | 127 HpackHuffmanSymbol code[] = { |
136 {bits32("00000000000000000000000000000000"), 3, 0}, | 128 {bits32("00000000000000000000000000000000"), 3, 0}, |
137 {bits32("00100000000000000000000000000000"), 3, 1}, | 129 {bits32("00100000000000000000000000000000"), 3, 1}, |
138 {bits32("01000000000000000000000000000000"), 3, 2}, | 130 {bits32("01000000000000000000000000000000"), 3, 2}, |
139 {bits32("01100000000000000000000000000000"), 3, 3}, | 131 {bits32("01100000000000000000000000000000"), 3, 3}, |
140 {bits32("10000000000000000000000000000000"), 3, 4}, | 132 {bits32("10000000000000000000000000000000"), 3, 4}, |
141 {bits32("10100000000000000000000000000000"), 3, 5}, | 133 {bits32("10100000000000000000000000000000"), 3, 5}, |
142 {bits32("11000000000000000000000000000000"), 3, 6}, | 134 {bits32("11000000000000000000000000000000"), 3, 6}, |
143 {bits32("11100000000000000000000000000000"), 8, 7}}; | 135 {bits32("11100000000000000000000000000000"), 8, 7}}; |
144 HpackHuffmanTable table; | 136 HpackHuffmanTable table; |
145 EXPECT_TRUE(table.Initialize(code, arraysize(code))); | 137 EXPECT_TRUE(table.Initialize(code, arraysize(code))); |
146 } | 138 } |
147 { | 139 { |
148 // But using 2 bits with one symbol overflows the code. | 140 // But using 2 bits with one symbol overflows the code. |
149 HpackHuffmanSymbol code[] = { | 141 HpackHuffmanSymbol code[] = { |
150 {bits32("01000000000000000000000000000000"), 3, 0}, | 142 {bits32("01000000000000000000000000000000"), 3, 0}, |
151 {bits32("01100000000000000000000000000000"), 3, 1}, | 143 {bits32("01100000000000000000000000000000"), 3, 1}, |
152 {bits32("00000000000000000000000000000000"), 2, 2}, | 144 {bits32("00000000000000000000000000000000"), 2, 2}, |
153 {bits32("10000000000000000000000000000000"), 3, 3}, | 145 {bits32("10000000000000000000000000000000"), 3, 3}, |
154 {bits32("10100000000000000000000000000000"), 3, 4}, | 146 {bits32("10100000000000000000000000000000"), 3, 4}, |
155 {bits32("11000000000000000000000000000000"), 3, 5}, | 147 {bits32("11000000000000000000000000000000"), 3, 5}, |
156 {bits32("11100000000000000000000000000000"), 3, 6}, | 148 {bits32("11100000000000000000000000000000"), 3, 6}, |
157 {bits32("00000000000000000000000000000000"), 8, 7}}; // Overflow. | 149 {bits32("00000000000000000000000000000000"), 8, 7}}; // Overflow. |
158 HpackHuffmanTable table; | 150 HpackHuffmanTable table; |
159 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 151 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
160 EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id()); | 152 EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id()); |
161 } | 153 } |
162 { | 154 { |
163 // Verify four symbols can be encoded with incremental bits per symbol. | 155 // Verify four symbols can be encoded with incremental bits per symbol. |
164 HpackHuffmanSymbol code[] = { | 156 HpackHuffmanSymbol code[] = { |
165 {bits32("00000000000000000000000000000000"), 1, 0}, | 157 {bits32("00000000000000000000000000000000"), 1, 0}, |
166 {bits32("10000000000000000000000000000000"), 2, 1}, | 158 {bits32("10000000000000000000000000000000"), 2, 1}, |
167 {bits32("11000000000000000000000000000000"), 3, 2}, | 159 {bits32("11000000000000000000000000000000"), 3, 2}, |
168 {bits32("11100000000000000000000000000000"), 8, 3}}; | 160 {bits32("11100000000000000000000000000000"), 8, 3}}; |
169 HpackHuffmanTable table; | 161 HpackHuffmanTable table; |
170 EXPECT_TRUE(table.Initialize(code, arraysize(code))); | 162 EXPECT_TRUE(table.Initialize(code, arraysize(code))); |
171 } | 163 } |
172 { | 164 { |
173 // But repeating a length overflows the code. | 165 // But repeating a length overflows the code. |
174 HpackHuffmanSymbol code[] = { | 166 HpackHuffmanSymbol code[] = { |
175 {bits32("00000000000000000000000000000000"), 1, 0}, | 167 {bits32("00000000000000000000000000000000"), 1, 0}, |
176 {bits32("10000000000000000000000000000000"), 2, 1}, | 168 {bits32("10000000000000000000000000000000"), 2, 1}, |
177 {bits32("11000000000000000000000000000000"), 2, 2}, | 169 {bits32("11000000000000000000000000000000"), 2, 2}, |
178 {bits32("00000000000000000000000000000000"), 8, 3}}; // Overflow. | 170 {bits32("00000000000000000000000000000000"), 8, 3}}; // Overflow. |
179 HpackHuffmanTable table; | 171 HpackHuffmanTable table; |
180 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 172 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
181 EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id()); | 173 EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id()); |
182 } | 174 } |
183 { | 175 { |
184 // Symbol IDs must be assigned sequentially with no gaps. | 176 // Symbol IDs must be assigned sequentially with no gaps. |
185 HpackHuffmanSymbol code[] = { | 177 HpackHuffmanSymbol code[] = { |
186 {bits32("00000000000000000000000000000000"), 1, 0}, | 178 {bits32("00000000000000000000000000000000"), 1, 0}, |
187 {bits32("10000000000000000000000000000000"), 2, 1}, | 179 {bits32("10000000000000000000000000000000"), 2, 1}, |
188 {bits32("11000000000000000000000000000000"), 3, 1}, // Repeat. | 180 {bits32("11000000000000000000000000000000"), 3, 1}, // Repeat. |
189 {bits32("11100000000000000000000000000000"), 8, 3}}; | 181 {bits32("11100000000000000000000000000000"), 8, 3}}; |
190 HpackHuffmanTable table; | 182 HpackHuffmanTable table; |
191 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 183 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
192 EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); | 184 EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); |
193 } | 185 } |
194 { | 186 { |
195 // Canonical codes must begin with zero. | 187 // Canonical codes must begin with zero. |
196 HpackHuffmanSymbol code[] = { | 188 HpackHuffmanSymbol code[] = { |
197 {bits32("10000000000000000000000000000000"), 4, 0}, | 189 {bits32("10000000000000000000000000000000"), 4, 0}, |
198 {bits32("10010000000000000000000000000000"), 4, 1}, | 190 {bits32("10010000000000000000000000000000"), 4, 1}, |
199 {bits32("10100000000000000000000000000000"), 4, 2}, | 191 {bits32("10100000000000000000000000000000"), 4, 2}, |
200 {bits32("10110000000000000000000000000000"), 8, 3}}; | 192 {bits32("10110000000000000000000000000000"), 8, 3}}; |
201 HpackHuffmanTable table; | 193 HpackHuffmanTable table; |
202 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 194 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
203 EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id()); | 195 EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id()); |
204 } | 196 } |
205 { | 197 { |
206 // Codes must match the expected canonical sequence. | 198 // Codes must match the expected canonical sequence. |
207 HpackHuffmanSymbol code[] = { | 199 HpackHuffmanSymbol code[] = { |
208 {bits32("00000000000000000000000000000000"), 2, 0}, | 200 {bits32("00000000000000000000000000000000"), 2, 0}, |
209 {bits32("01000000000000000000000000000000"), 2, 1}, | 201 {bits32("01000000000000000000000000000000"), 2, 1}, |
210 {bits32("11000000000000000000000000000000"), 2, 2}, // Not canonical. | 202 {bits32("11000000000000000000000000000000"), 2, 2}, // Not canonical. |
211 {bits32("10000000000000000000000000000000"), 8, 3}}; | 203 {bits32("10000000000000000000000000000000"), 8, 3}}; |
212 HpackHuffmanTable table; | 204 HpackHuffmanTable table; |
213 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 205 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
214 EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); | 206 EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); |
215 } | 207 } |
216 { | 208 { |
217 // At least one code must have a length of 8 bits (to ensure pad-ability). | 209 // At least one code must have a length of 8 bits (to ensure pad-ability). |
218 HpackHuffmanSymbol code[] = { | 210 HpackHuffmanSymbol code[] = { |
219 {bits32("00000000000000000000000000000000"), 1, 0}, | 211 {bits32("00000000000000000000000000000000"), 1, 0}, |
220 {bits32("10000000000000000000000000000000"), 2, 1}, | 212 {bits32("10000000000000000000000000000000"), 2, 1}, |
221 {bits32("11000000000000000000000000000000"), 3, 2}, | 213 {bits32("11000000000000000000000000000000"), 3, 2}, |
222 {bits32("11100000000000000000000000000000"), 7, 3}}; | 214 {bits32("11100000000000000000000000000000"), 7, 3}}; |
223 HpackHuffmanTable table; | 215 HpackHuffmanTable table; |
224 EXPECT_FALSE(table.Initialize(code, arraysize(code))); | 216 EXPECT_FALSE(table.Initialize(code, arraysize(code))); |
225 } | 217 } |
226 } | 218 } |
227 | 219 |
228 TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { | 220 TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) { |
229 HpackHuffmanSymbol code[] = { | 221 HpackHuffmanSymbol code[] = { |
230 {bits32("01100000000000000000000000000000"), 4, 0}, // 3rd. | 222 {bits32("01100000000000000000000000000000"), 4, 0}, // 3rd. |
231 {bits32("01110000000000000000000000000000"), 4, 1}, // 4th. | 223 {bits32("01110000000000000000000000000000"), 4, 1}, // 4th. |
232 {bits32("00000000000000000000000000000000"), 2, 2}, // 1st assigned code. | 224 {bits32("00000000000000000000000000000000"), 2, 2}, // 1st assigned code. |
233 {bits32("01000000000000000000000000000000"), 3, 3}, // 2nd. | 225 {bits32("01000000000000000000000000000000"), 3, 3}, // 2nd. |
234 {bits32("10000000000000000000000000000000"), 5, 4}, // 5th. | 226 {bits32("10000000000000000000000000000000"), 5, 4}, // 5th. |
235 {bits32("10001000000000000000000000000000"), 5, 5}, // 6th. | 227 {bits32("10001000000000000000000000000000"), 5, 5}, // 6th. |
236 {bits32("10011000000000000000000000000000"), 8, 6}, // 8th. | 228 {bits32("10011000000000000000000000000000"), 8, 6}, // 8th. |
237 {bits32("10010000000000000000000000000000"), 5, 7}}; // 7th. | 229 {bits32("10010000000000000000000000000000"), 5, 7}}; // 7th. |
238 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); | 230 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); |
239 | 231 |
240 EXPECT_THAT(peer_.code_by_id(), ElementsAre( | 232 EXPECT_THAT(peer_.code_by_id(), |
241 bits32("01100000000000000000000000000000"), | 233 ElementsAre(bits32("01100000000000000000000000000000"), |
242 bits32("01110000000000000000000000000000"), | 234 bits32("01110000000000000000000000000000"), |
243 bits32("00000000000000000000000000000000"), | 235 bits32("00000000000000000000000000000000"), |
244 bits32("01000000000000000000000000000000"), | 236 bits32("01000000000000000000000000000000"), |
245 bits32("10000000000000000000000000000000"), | 237 bits32("10000000000000000000000000000000"), |
246 bits32("10001000000000000000000000000000"), | 238 bits32("10001000000000000000000000000000"), |
247 bits32("10011000000000000000000000000000"), | 239 bits32("10011000000000000000000000000000"), |
248 bits32("10010000000000000000000000000000"))); | 240 bits32("10010000000000000000000000000000"))); |
249 EXPECT_THAT(peer_.length_by_id(), ElementsAre( | 241 EXPECT_THAT(peer_.length_by_id(), ElementsAre(4, 4, 2, 3, 5, 5, 8, 5)); |
250 4, 4, 2, 3, 5, 5, 8, 5)); | |
251 | 242 |
252 EXPECT_EQ(1u, peer_.decode_tables().size()); | 243 EXPECT_EQ(1u, peer_.decode_tables().size()); |
253 { | 244 { |
254 std::vector<DecodeEntry> expected; | 245 std::vector<DecodeEntry> expected; |
255 expected.resize(128, DecodeEntry(0, 2, 2)); // Fills 128. | 246 expected.resize(128, DecodeEntry(0, 2, 2)); // Fills 128. |
256 expected.resize(192, DecodeEntry(0, 3, 3)); // Fills 64. | 247 expected.resize(192, DecodeEntry(0, 3, 3)); // Fills 64. |
257 expected.resize(224, DecodeEntry(0, 4, 0)); // Fills 32. | 248 expected.resize(224, DecodeEntry(0, 4, 0)); // Fills 32. |
258 expected.resize(256, DecodeEntry(0, 4, 1)); // Fills 32. | 249 expected.resize(256, DecodeEntry(0, 4, 1)); // Fills 32. |
259 expected.resize(272, DecodeEntry(0, 5, 4)); // Fills 16. | 250 expected.resize(272, DecodeEntry(0, 5, 4)); // Fills 16. |
260 expected.resize(288, DecodeEntry(0, 5, 5)); // Fills 16. | 251 expected.resize(288, DecodeEntry(0, 5, 5)); // Fills 16. |
261 expected.resize(304, DecodeEntry(0, 5, 7)); // Fills 16. | 252 expected.resize(304, DecodeEntry(0, 5, 7)); // Fills 16. |
262 expected.resize(306, DecodeEntry(0, 8, 6)); // Fills 2. | 253 expected.resize(306, DecodeEntry(0, 8, 6)); // Fills 2. |
263 expected.resize(512, DecodeEntry()); // Remainder is empty. | 254 expected.resize(512, DecodeEntry()); // Remainder is empty. |
264 | 255 |
265 EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]), | 256 EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]), |
266 Pointwise(DecodeEntryEq(), expected)); | 257 Pointwise(DecodeEntryEq(), expected)); |
267 } | 258 } |
268 EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); | 259 EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); |
269 | 260 |
270 char input_storage[] = {2, 3, 2, 7, 4}; | 261 char input_storage[] = {2, 3, 2, 7, 4}; |
271 StringPiece input(input_storage, arraysize(input_storage)); | 262 StringPiece input(input_storage, arraysize(input_storage)); |
272 // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. | 263 // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. |
273 char expect_storage[] = { | 264 char expect_storage[] = {bits8("00010001"), bits8("00101000"), |
274 bits8("00010001"), | 265 bits8("01001100")}; |
275 bits8("00101000"), | |
276 bits8("01001100")}; | |
277 StringPiece expect(expect_storage, arraysize(expect_storage)); | 266 StringPiece expect(expect_storage, arraysize(expect_storage)); |
278 | 267 |
279 string buffer_in = EncodeString(input); | 268 string buffer_in = EncodeString(input); |
280 EXPECT_EQ(expect, buffer_in); | 269 EXPECT_EQ(expect, buffer_in); |
281 | 270 |
282 string buffer_out; | 271 string buffer_out; |
283 HpackInputStream input_stream(kuint32max, buffer_in); | 272 HpackInputStream input_stream(kuint32max, buffer_in); |
284 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); | 273 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); |
285 EXPECT_EQ(buffer_out, input); | 274 EXPECT_EQ(buffer_out, input); |
286 } | 275 } |
287 | 276 |
288 TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { | 277 TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) { |
289 HpackHuffmanSymbol code[] = { | 278 HpackHuffmanSymbol code[] = { |
290 {bits32("00000000000000000000000000000000"), 6, 0}, | 279 {bits32("00000000000000000000000000000000"), 6, 0}, |
291 {bits32("00000100000000000000000000000000"), 6, 1}, | 280 {bits32("00000100000000000000000000000000"), 6, 1}, |
292 {bits32("00001000000000000000000000000000"), 11, 2}, | 281 {bits32("00001000000000000000000000000000"), 11, 2}, |
293 {bits32("00001000001000000000000000000000"), 11, 3}, | 282 {bits32("00001000001000000000000000000000"), 11, 3}, |
294 {bits32("00001000010000000000000000000000"), 12, 4}, | 283 {bits32("00001000010000000000000000000000"), 12, 4}, |
295 }; | 284 }; |
296 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); | 285 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); |
297 | 286 |
298 EXPECT_EQ(2u, peer_.decode_tables().size()); | 287 EXPECT_EQ(2u, peer_.decode_tables().size()); |
299 { | 288 { |
300 std::vector<DecodeEntry> expected; | 289 std::vector<DecodeEntry> expected; |
301 expected.resize(8, DecodeEntry(0, 6, 0)); // Fills 8. | 290 expected.resize(8, DecodeEntry(0, 6, 0)); // Fills 8. |
302 expected.resize(16, DecodeEntry(0, 6, 1)); // Fills 8. | 291 expected.resize(16, DecodeEntry(0, 6, 1)); // Fills 8. |
303 expected.resize(17, DecodeEntry(1, 12, 0)); // Pointer. Fills 1. | 292 expected.resize(17, DecodeEntry(1, 12, 0)); // Pointer. Fills 1. |
304 expected.resize(512, DecodeEntry()); // Remainder is empty. | 293 expected.resize(512, DecodeEntry()); // Remainder is empty. |
305 | 294 |
306 const DecodeTable& decode_table = peer_.decode_tables()[0]; | 295 const DecodeTable& decode_table = peer_.decode_tables()[0]; |
307 EXPECT_EQ(decode_table.prefix_length, 0); | 296 EXPECT_EQ(decode_table.prefix_length, 0); |
308 EXPECT_EQ(decode_table.indexed_length, 9); | 297 EXPECT_EQ(decode_table.indexed_length, 9); |
309 EXPECT_THAT(peer_.decode_entries(decode_table), | 298 EXPECT_THAT(peer_.decode_entries(decode_table), |
310 Pointwise(DecodeEntryEq(), expected)); | 299 Pointwise(DecodeEntryEq(), expected)); |
311 } | 300 } |
312 { | 301 { |
313 std::vector<DecodeEntry> expected; | 302 std::vector<DecodeEntry> expected; |
314 expected.resize(2, DecodeEntry(1, 11, 2)); // Fills 2. | 303 expected.resize(2, DecodeEntry(1, 11, 2)); // Fills 2. |
315 expected.resize(4, DecodeEntry(1, 11, 3)); // Fills 2. | 304 expected.resize(4, DecodeEntry(1, 11, 3)); // Fills 2. |
316 expected.resize(5, DecodeEntry(1, 12, 4)); // Fills 1. | 305 expected.resize(5, DecodeEntry(1, 12, 4)); // Fills 1. |
317 expected.resize(8, DecodeEntry()); // Remainder is empty. | 306 expected.resize(8, DecodeEntry()); // Remainder is empty. |
318 | 307 |
319 const DecodeTable& decode_table = peer_.decode_tables()[1]; | 308 const DecodeTable& decode_table = peer_.decode_tables()[1]; |
320 EXPECT_EQ(decode_table.prefix_length, 9); | 309 EXPECT_EQ(decode_table.prefix_length, 9); |
321 EXPECT_EQ(decode_table.indexed_length, 3); | 310 EXPECT_EQ(decode_table.indexed_length, 3); |
322 EXPECT_THAT(peer_.decode_entries(decode_table), | 311 EXPECT_THAT(peer_.decode_entries(decode_table), |
323 Pointwise(DecodeEntryEq(), expected)); | 312 Pointwise(DecodeEntryEq(), expected)); |
324 } | 313 } |
325 EXPECT_EQ(bits8("00001000"), peer_.pad_bits()); | 314 EXPECT_EQ(bits8("00001000"), peer_.pad_bits()); |
326 } | 315 } |
327 | 316 |
328 TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) { | 317 TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) { |
329 HpackHuffmanSymbol code[] = { | 318 HpackHuffmanSymbol code[] = { |
330 {bits32("01100000000000000000000000000000"), 4, 0}, | 319 {bits32("01100000000000000000000000000000"), 4, 0}, |
331 {bits32("01110000000000000000000000000000"), 4, 1}, | 320 {bits32("01110000000000000000000000000000"), 4, 1}, |
332 {bits32("00000000000000000000000000000000"), 2, 2}, | 321 {bits32("00000000000000000000000000000000"), 2, 2}, |
333 {bits32("01000000000000000000000000000000"), 3, 3}, | 322 {bits32("01000000000000000000000000000000"), 3, 3}, |
334 {bits32("10000000000000000000000000000000"), 5, 4}, | 323 {bits32("10000000000000000000000000000000"), 5, 4}, |
335 {bits32("10001000000000000000000000000000"), 5, 5}, | 324 {bits32("10001000000000000000000000000000"), 5, 5}, |
336 {bits32("10011000000000000000000000000000"), 6, 6}, | 325 {bits32("10011000000000000000000000000000"), 6, 6}, |
337 {bits32("10010000000000000000000000000000"), 5, 7}, | 326 {bits32("10010000000000000000000000000000"), 5, 7}, |
338 {bits32("10011100000000000000000000000000"), 16, 8}}; | 327 {bits32("10011100000000000000000000000000"), 16, 8}}; |
339 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); | 328 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); |
340 | 329 |
341 string buffer; | 330 string buffer; |
342 const size_t capacity = 4; | 331 const size_t capacity = 4; |
343 { | 332 { |
344 // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100. | 333 // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100. |
345 char input_storage[] = {bits8("00010001"), bits8("00110100")}; | 334 char input_storage[] = {bits8("00010001"), bits8("00110100")}; |
346 StringPiece input(input_storage, arraysize(input_storage)); | 335 StringPiece input(input_storage, arraysize(input_storage)); |
347 | 336 |
348 HpackInputStream input_stream(kuint32max, input); | 337 HpackInputStream input_stream(kuint32max, input); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
382 EXPECT_EQ(buffer, "\x06"); | 371 EXPECT_EQ(buffer, "\x06"); |
383 } | 372 } |
384 } | 373 } |
385 | 374 |
386 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { | 375 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { |
387 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 376 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
388 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 377 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
389 | 378 |
390 string buffer; | 379 string buffer; |
391 string test_table[] = { | 380 string test_table[] = { |
392 "\xdb\x6d\x88\x3e\x68\xd1\xcb\x12\x25\xba\x7f", | 381 "\xdb\x6d\x88\x3e\x68\xd1\xcb\x12\x25\xba\x7f", "www.example.com", |
393 "www.example.com", | 382 "\x63\x65\x4a\x13\x98\xff", "no-cache", |
394 "\x63\x65\x4a\x13\x98\xff", | 383 "\x4e\xb0\x8b\x74\x97\x90\xfa\x7f", "custom-key", |
395 "no-cache", | 384 "\x4e\xb0\x8b\x74\x97\x9a\x17\xa8\xff", "custom-value", |
396 "\x4e\xb0\x8b\x74\x97\x90\xfa\x7f", | |
397 "custom-key", | |
398 "\x4e\xb0\x8b\x74\x97\x9a\x17\xa8\xff", | |
399 "custom-value", | |
400 }; | 385 }; |
401 // Round-trip each test example. | 386 // Round-trip each test example. |
402 for (size_t i = 0; i != arraysize(test_table); i += 2) { | 387 for (size_t i = 0; i != arraysize(test_table); i += 2) { |
403 const string& encodedFixture(test_table[i]); | 388 const string& encodedFixture(test_table[i]); |
404 const string& decodedFixture(test_table[i+1]); | 389 const string& decodedFixture(test_table[i + 1]); |
405 HpackInputStream input_stream(kuint32max, encodedFixture); | 390 HpackInputStream input_stream(kuint32max, encodedFixture); |
406 | 391 |
407 EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(), | 392 EXPECT_TRUE( |
408 &buffer)); | 393 table_.DecodeString(&input_stream, decodedFixture.size(), &buffer)); |
409 EXPECT_EQ(decodedFixture, buffer); | 394 EXPECT_EQ(decodedFixture, buffer); |
410 buffer = EncodeString(decodedFixture); | 395 buffer = EncodeString(decodedFixture); |
411 EXPECT_EQ(encodedFixture, buffer); | 396 EXPECT_EQ(encodedFixture, buffer); |
412 } | 397 } |
413 } | 398 } |
414 | 399 |
415 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { | 400 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { |
416 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 401 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
417 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 402 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
418 | 403 |
419 string buffer; | 404 string buffer; |
420 string test_table[] = { | 405 string test_table[] = { |
421 "\x98\xa7", | 406 "\x98\xa7", "302", "\x73\xd5\xcd\x11\x1f", "private", |
422 "302", | 407 "\xef\x6b\x3a\x7a\x0e\x6e\x8f\xa2\x63\xd0\x72\x9a\x6e\x83\x97\xd8" |
423 "\x73\xd5\xcd\x11\x1f", | 408 "\x69\xbd\x87\x37\x47\xbb\xbf\xc7", |
424 "private", | 409 "Mon, 21 Oct 2013 20:13:21 GMT", |
425 "\xef\x6b\x3a\x7a\x0e\x6e\x8f\xa2\x63\xd0\x72\x9a\x6e\x83\x97\xd8" | 410 "\xce\x31\x74\x3d\x80\x1b\x6d\xb1\x07\xcd\x1a\x39\x62\x44\xb7\x4f", |
426 "\x69\xbd\x87\x37\x47\xbb\xbf\xc7", | 411 "https://www.example.com", |
427 "Mon, 21 Oct 2013 20:13:21 GMT", | 412 "\xc5\xad\xb7\x7f\x87\x6f\xc7\xfb\xf7\xfd\xbf\xbe\xbf\xf3\xf7\xf4" |
428 "\xce\x31\x74\x3d\x80\x1b\x6d\xb1\x07\xcd\x1a\x39\x62\x44\xb7\x4f", | 413 "\xfb\x7e\xbb\xbe\x9f\x5f\x87\xe3\x7f\xef\xed\xfa\xee\xfa\x7c\x3f" |
429 "https://www.example.com", | 414 "\x1d\x5d\x1a\x23\xce\x54\x64\x36\xcd\x49\x4b\xd5\xd1\xcc\x5f\x05" |
430 "\xc5\xad\xb7\x7f\x87\x6f\xc7\xfb\xf7\xfd\xbf\xbe\xbf\xf3\xf7\xf4" | 415 "\x35\x96\x9b", |
431 "\xfb\x7e\xbb\xbe\x9f\x5f\x87\xe3\x7f\xef\xed\xfa\xee\xfa\x7c\x3f" | 416 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
432 "\x1d\x5d\x1a\x23\xce\x54\x64\x36\xcd\x49\x4b\xd5\xd1\xcc\x5f\x05" | |
433 "\x35\x96\x9b", | |
434 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", | |
435 }; | 417 }; |
436 // Round-trip each test example. | 418 // Round-trip each test example. |
437 for (size_t i = 0; i != arraysize(test_table); i += 2) { | 419 for (size_t i = 0; i != arraysize(test_table); i += 2) { |
438 const string& encodedFixture(test_table[i]); | 420 const string& encodedFixture(test_table[i]); |
439 const string& decodedFixture(test_table[i+1]); | 421 const string& decodedFixture(test_table[i + 1]); |
440 HpackInputStream input_stream(kuint32max, encodedFixture); | 422 HpackInputStream input_stream(kuint32max, encodedFixture); |
441 | 423 |
442 EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(), | 424 EXPECT_TRUE( |
443 &buffer)); | 425 table_.DecodeString(&input_stream, decodedFixture.size(), &buffer)); |
444 EXPECT_EQ(decodedFixture, buffer); | 426 EXPECT_EQ(decodedFixture, buffer); |
445 buffer = EncodeString(decodedFixture); | 427 buffer = EncodeString(decodedFixture); |
446 EXPECT_EQ(encodedFixture, buffer); | 428 EXPECT_EQ(encodedFixture, buffer); |
447 } | 429 } |
448 } | 430 } |
449 | 431 |
450 TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) { | 432 TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) { |
451 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 433 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
452 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 434 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
453 | 435 |
454 for (size_t i = 0; i != 256; i++) { | 436 for (size_t i = 0; i != 256; i++) { |
455 char c = static_cast<char>(i); | 437 char c = static_cast<char>(i); |
456 char storage[3] = {c, c, c}; | 438 char storage[3] = {c, c, c}; |
457 StringPiece input(storage, arraysize(storage)); | 439 StringPiece input(storage, arraysize(storage)); |
458 | 440 |
459 string buffer_in = EncodeString(input); | 441 string buffer_in = EncodeString(input); |
460 string buffer_out; | 442 string buffer_out; |
461 | 443 |
462 HpackInputStream input_stream(kuint32max, buffer_in); | 444 HpackInputStream input_stream(kuint32max, buffer_in); |
463 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); | 445 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); |
464 EXPECT_EQ(input, buffer_out); | 446 EXPECT_EQ(input, buffer_out); |
465 } | 447 } |
466 } | 448 } |
467 | 449 |
468 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { | 450 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { |
469 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 451 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
470 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 452 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
471 | 453 |
472 | |
473 char storage[512]; | 454 char storage[512]; |
474 for (size_t i = 0; i != 256; i++) { | 455 for (size_t i = 0; i != 256; i++) { |
475 storage[i] = static_cast<char>(i); | 456 storage[i] = static_cast<char>(i); |
476 storage[511 - i] = static_cast<char>(i); | 457 storage[511 - i] = static_cast<char>(i); |
477 } | 458 } |
478 StringPiece input(storage, arraysize(storage)); | 459 StringPiece input(storage, arraysize(storage)); |
479 | 460 |
480 string buffer_in = EncodeString(input); | 461 string buffer_in = EncodeString(input); |
481 string buffer_out; | 462 string buffer_out; |
482 | 463 |
483 HpackInputStream input_stream(kuint32max, buffer_in); | 464 HpackInputStream input_stream(kuint32max, buffer_in); |
484 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); | 465 EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out)); |
485 EXPECT_EQ(input, buffer_out); | 466 EXPECT_EQ(input, buffer_out); |
486 } | 467 } |
487 | 468 |
488 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { | 469 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { |
489 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 470 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
490 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 471 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
491 | 472 |
492 string test_table[] = { | 473 string test_table[] = { |
493 "", | 474 "", |
494 "Mon, 21 Oct 2013 20:13:21 GMT", | 475 "Mon, 21 Oct 2013 20:13:21 GMT", |
495 "https://www.example.com", | 476 "https://www.example.com", |
496 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", | 477 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
497 string(1, '\0'), | 478 string(1, '\0'), |
498 string("foo\0bar", 7), | 479 string("foo\0bar", 7), |
499 string(256, '\0'), | 480 string(256, '\0'), |
500 }; | 481 }; |
501 for (size_t i = 0; i != 256; ++i) { | 482 for (size_t i = 0; i != 256; ++i) { |
502 // Expand last |test_table| entry to cover all codes. | 483 // Expand last |test_table| entry to cover all codes. |
503 test_table[arraysize(test_table)-1][i] = static_cast<char>(i); | 484 test_table[arraysize(test_table) - 1][i] = static_cast<char>(i); |
504 } | 485 } |
505 | 486 |
506 HpackOutputStream output_stream; | 487 HpackOutputStream output_stream; |
507 string encoding; | 488 string encoding; |
508 for (size_t i = 0; i != arraysize(test_table); ++i) { | 489 for (size_t i = 0; i != arraysize(test_table); ++i) { |
509 table_.EncodeString(test_table[i], &output_stream); | 490 table_.EncodeString(test_table[i], &output_stream); |
510 output_stream.TakeString(&encoding); | 491 output_stream.TakeString(&encoding); |
511 EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); | 492 EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); |
512 } | 493 } |
513 } | 494 } |
514 | 495 |
515 } // namespace | 496 } // namespace |
516 | 497 |
517 } // namespace test | 498 } // namespace test |
518 | 499 |
519 } // namespace net | 500 } // namespace net |
OLD | NEW |