| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright 2016 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "net/spdy/hpack/hpack_huffman_decoder.h" | |
| 6 | |
| 7 #include <bitset> | |
| 8 #include <limits> | |
| 9 | |
| 10 #include "base/logging.h" | |
| 11 #include "base/macros.h" | |
| 12 #include "base/rand_util.h" | |
| 13 #include "net/spdy/hpack/hpack_constants.h" | |
| 14 #include "net/spdy/hpack/hpack_huffman_table.h" | |
| 15 #include "net/spdy/hpack/hpack_input_stream.h" | |
| 16 #include "net/spdy/hpack/hpack_output_stream.h" | |
| 17 #include "net/spdy/platform/api/spdy_string_piece.h" | |
| 18 #include "net/spdy/spdy_test_utils.h" | |
| 19 #include "testing/gtest/include/gtest/gtest.h" | |
| 20 | |
| 21 namespace net { | |
| 22 namespace test { | |
| 23 | |
| 24 namespace { | |
| 25 | |
| 26 uint32_t RandUint32() { | |
| 27 return static_cast<uint32_t>(base::RandUint64() & 0xffffffff); | |
| 28 } | |
| 29 | |
| 30 } // anonymous namespace | |
| 31 | |
| 32 // Bits(HuffmanWord) constructs a bitset<32>, which produces nicely formatted | |
| 33 // binary numbers when LOG'd. | |
| 34 typedef std::bitset<32> Bits; | |
| 35 | |
| 36 typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord; | |
| 37 typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength; | |
| 38 | |
| 39 class HpackHuffmanDecoderPeer { | |
| 40 public: | |
| 41 static HuffmanCodeLength CodeLengthOfPrefix(HuffmanWord value) { | |
| 42 return HpackHuffmanDecoder::CodeLengthOfPrefix(value); | |
| 43 } | |
| 44 | |
| 45 static HuffmanWord DecodeToCanonical(HuffmanCodeLength code_length, | |
| 46 HuffmanWord bits) { | |
| 47 return HpackHuffmanDecoder::DecodeToCanonical(code_length, bits); | |
| 48 } | |
| 49 | |
| 50 static char CanonicalToSource(HuffmanWord canonical) { | |
| 51 return HpackHuffmanDecoder::CanonicalToSource(canonical); | |
| 52 } | |
| 53 }; | |
| 54 | |
| 55 // Tests of the ability to decode the HPACK Huffman Code, defined in: | |
| 56 // https://httpwg.github.io/specs/rfc7541.html#huffman.code | |
| 57 class HpackHuffmanDecoderTest : public ::testing::Test { | |
| 58 protected: | |
| 59 HpackHuffmanDecoderTest() : table_(ObtainHpackHuffmanTable()) {} | |
| 60 | |
| 61 // Since kHpackHuffmanCode doesn't include the canonical symbol value, | |
| 62 // this helper helps us to decode directly to the source symbol, allowing | |
| 63 // for EOS. | |
| 64 uint16_t DecodeToSource(HuffmanCodeLength code_length, HuffmanWord bits) { | |
| 65 HuffmanWord canonical = | |
| 66 HpackHuffmanDecoderPeer::DecodeToCanonical(code_length, bits); | |
| 67 EXPECT_LE(canonical, 256u); | |
| 68 if (canonical == 256u) { | |
| 69 return canonical; | |
| 70 } | |
| 71 return static_cast<unsigned char>( | |
| 72 HpackHuffmanDecoderPeer::CanonicalToSource(canonical)); | |
| 73 } | |
| 74 | |
| 75 void EncodeString(SpdyStringPiece input, SpdyString* encoded) { | |
| 76 HpackOutputStream output_stream; | |
| 77 table_.EncodeString(input, &output_stream); | |
| 78 encoded->clear(); | |
| 79 output_stream.TakeString(encoded); | |
| 80 // Verify EncodedSize() agrees with EncodeString(). | |
| 81 EXPECT_EQ(encoded->size(), table_.EncodedSize(input)); | |
| 82 } | |
| 83 | |
| 84 SpdyString EncodeString(SpdyStringPiece input) { | |
| 85 SpdyString result; | |
| 86 EncodeString(input, &result); | |
| 87 return result; | |
| 88 } | |
| 89 | |
| 90 const HpackHuffmanTable& table_; | |
| 91 }; | |
| 92 | |
| 93 TEST_F(HpackHuffmanDecoderTest, CodeLengthOfPrefix) { | |
| 94 for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) { | |
| 95 // First confirm our assumption that the low order bits of entry.code | |
| 96 // (those not part of the high order entry.length bits) are zero. | |
| 97 uint32_t non_code_bits = 0xffffffff >> entry.length; | |
| 98 EXPECT_EQ(0u, entry.code & non_code_bits); | |
| 99 | |
| 100 // entry.code has a code length of entry.length. | |
| 101 EXPECT_EQ(entry.length, | |
| 102 HpackHuffmanDecoderPeer::CodeLengthOfPrefix(entry.code)) | |
| 103 << "Full code: " << Bits(entry.code) << "\n" | |
| 104 << " ID: " << entry.id; | |
| 105 | |
| 106 // Let's try again with all the low order bits set to 1. | |
| 107 uint32_t bits = entry.code | (0xffffffff >> entry.length); | |
| 108 EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits)) | |
| 109 << "Full code: " << Bits(entry.code) << "\n" | |
| 110 << " bits: " << Bits(bits) << "\n" | |
| 111 << " ID: " << entry.id; | |
| 112 | |
| 113 // Let's try again with random low order bits. | |
| 114 uint32_t rand = RandUint32() & (0xffffffff >> entry.length); | |
| 115 bits = entry.code | rand; | |
| 116 EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits)) | |
| 117 << "Full code: " << Bits(entry.code) << "\n" | |
| 118 << " rand: " << Bits(rand) << "\n" | |
| 119 << " bits: " << Bits(bits) << "\n" | |
| 120 << " ID: " << entry.id; | |
| 121 | |
| 122 // If fewer bits are available and low order bits are zero after left | |
| 123 // shifting (should be true), CodeLengthOfPrefix should never return | |
| 124 // a value that is <= the number of available bits. | |
| 125 for (uint8_t available = entry.length - 1; available > 0; --available) { | |
| 126 uint32_t mask = 0xffffffff; | |
| 127 uint32_t avail_mask = mask << (32 - available); | |
| 128 bits = entry.code & avail_mask; | |
| 129 EXPECT_LT(available, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits)) | |
| 130 << "Full code: " << Bits(entry.code) << "\n" | |
| 131 << "availMask: " << Bits(avail_mask) << "\n" | |
| 132 << " bits: " << Bits(bits) << "\n" | |
| 133 << " ID: " << entry.id; | |
| 134 } | |
| 135 } | |
| 136 } | |
| 137 | |
| 138 TEST_F(HpackHuffmanDecoderTest, DecodeToSource) { | |
| 139 for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) { | |
| 140 // Check that entry.code, which has all the low order bits set to 0, | |
| 141 // decodes to entry.id. | |
| 142 EXPECT_EQ(entry.id, DecodeToSource(entry.length, entry.code)) | |
| 143 << " Length: " << entry.length << "\n" | |
| 144 << "Full code: " << Bits(entry.code); | |
| 145 | |
| 146 // Let's try again with all the low order bits set to 1. | |
| 147 uint32_t bits = entry.code | (0xffffffff >> entry.length); | |
| 148 EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits)) | |
| 149 << " Length: " << entry.length << "\n" | |
| 150 << "Full code: " << Bits(entry.code) << "\n" | |
| 151 << " bits: " << Bits(bits); | |
| 152 | |
| 153 // Let's try again with random low order bits. | |
| 154 uint32_t rand = RandUint32() & (0xffffffff >> entry.length); | |
| 155 bits = entry.code | rand; | |
| 156 EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits)) | |
| 157 << " Length: " << entry.length << "\n" | |
| 158 << "Full code: " << Bits(entry.code) << "\n" | |
| 159 << " rand: " << Bits(rand) << "\n" | |
| 160 << " bits: " << Bits(bits); | |
| 161 } | |
| 162 } | |
| 163 | |
| 164 TEST_F(HpackHuffmanDecoderTest, SpecRequestExamples) { | |
| 165 SpdyString buffer; | |
| 166 SpdyString test_table[] = { | |
| 167 a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"), | |
| 168 "www.example.com", | |
| 169 a2b_hex("a8eb10649cbf"), | |
| 170 "no-cache", | |
| 171 a2b_hex("25a849e95ba97d7f"), | |
| 172 "custom-key", | |
| 173 a2b_hex("25a849e95bb8e8b4bf"), | |
| 174 "custom-value", | |
| 175 }; | |
| 176 // Round-trip each test example. | |
| 177 for (size_t i = 0; i != arraysize(test_table); i += 2) { | |
| 178 const SpdyString& encodedFixture(test_table[i]); | |
| 179 const SpdyString& decodedFixture(test_table[i + 1]); | |
| 180 HpackInputStream input_stream(encodedFixture); | |
| 181 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer)); | |
| 182 EXPECT_EQ(decodedFixture, buffer); | |
| 183 buffer = EncodeString(decodedFixture); | |
| 184 EXPECT_EQ(encodedFixture, buffer); | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 TEST_F(HpackHuffmanDecoderTest, SpecResponseExamples) { | |
| 189 SpdyString buffer; | |
| 190 // clang-format off | |
| 191 SpdyString test_table[] = { | |
| 192 a2b_hex("6402"), | |
| 193 "302", | |
| 194 a2b_hex("aec3771a4b"), | |
| 195 "private", | |
| 196 a2b_hex("d07abe941054d444a8200595040b8166" | |
| 197 "e082a62d1bff"), | |
| 198 "Mon, 21 Oct 2013 20:13:21 GMT", | |
| 199 a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43" | |
| 200 "d3"), | |
| 201 "https://www.example.com", | |
| 202 a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960" | |
| 203 "d5af27087f3672c1ab270fb5291f9587" | |
| 204 "316065c003ed4ee5b1063d5007"), | |
| 205 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", | |
| 206 }; | |
| 207 // clang-format on | |
| 208 // Round-trip each test example. | |
| 209 for (size_t i = 0; i != arraysize(test_table); i += 2) { | |
| 210 const SpdyString& encodedFixture(test_table[i]); | |
| 211 const SpdyString& decodedFixture(test_table[i + 1]); | |
| 212 HpackInputStream input_stream(encodedFixture); | |
| 213 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer)); | |
| 214 EXPECT_EQ(decodedFixture, buffer); | |
| 215 buffer = EncodeString(decodedFixture); | |
| 216 EXPECT_EQ(encodedFixture, buffer); | |
| 217 } | |
| 218 } | |
| 219 | |
| 220 TEST_F(HpackHuffmanDecoderTest, RoundTripIndividualSymbols) { | |
| 221 for (size_t i = 0; i != 256; i++) { | |
| 222 char c = static_cast<char>(i); | |
| 223 char storage[3] = {c, c, c}; | |
| 224 SpdyStringPiece input(storage, arraysize(storage)); | |
| 225 SpdyString buffer_in = EncodeString(input); | |
| 226 SpdyString buffer_out; | |
| 227 HpackInputStream input_stream(buffer_in); | |
| 228 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buffer_out)); | |
| 229 EXPECT_EQ(input, buffer_out); | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 // Creates 256 input strings, each with a unique byte value i used to sandwich | |
| 234 // all the other higher byte values. | |
| 235 TEST_F(HpackHuffmanDecoderTest, RoundTripSymbolSequences) { | |
| 236 SpdyString input; | |
| 237 SpdyString encoded; | |
| 238 SpdyString decoded; | |
| 239 for (size_t i = 0; i != 256; i++) { | |
| 240 input.clear(); | |
| 241 auto ic = static_cast<char>(i); | |
| 242 input.push_back(ic); | |
| 243 for (size_t j = i; j != 256; j++) { | |
| 244 input.push_back(static_cast<char>(j)); | |
| 245 input.push_back(ic); | |
| 246 } | |
| 247 EncodeString(input, &encoded); | |
| 248 HpackInputStream input_stream(encoded); | |
| 249 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &decoded)); | |
| 250 EXPECT_EQ(input, decoded); | |
| 251 } | |
| 252 } | |
| 253 | |
| 254 } // namespace test | |
| 255 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2832973003:
Split net/spdy into core and chromium subdirectories. (Closed)
