| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "net/spdy/hpack_huffman_table.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <cmath> | |
| 9 | |
| 10 #include "base/logging.h" | |
| 11 #include "base/numerics/safe_conversions.h" | |
| 12 #include "net/spdy/hpack_input_stream.h" | |
| 13 #include "net/spdy/hpack_output_stream.h" | |
| 14 | |
| 15 namespace net { | |
| 16 | |
| 17 using base::StringPiece; | |
| 18 using std::string; | |
| 19 | |
| 20 namespace { | |
| 21 | |
| 22 // How many bits to index in the root decode table. | |
| 23 const uint8 kDecodeTableRootBits = 9; | |
| 24 // Maximum number of bits to index in successive decode tables. | |
| 25 const uint8 kDecodeTableBranchBits = 6; | |
| 26 | |
| 27 bool SymbolLengthAndIdCompare(const HpackHuffmanSymbol& a, | |
| 28 const HpackHuffmanSymbol& b) { | |
| 29 if (a.length == b.length) { | |
| 30 return a.id < b.id; | |
| 31 } | |
| 32 return a.length < b.length; | |
| 33 } | |
| 34 bool SymbolIdCompare(const HpackHuffmanSymbol& a, | |
| 35 const HpackHuffmanSymbol& b) { | |
| 36 return a.id < b.id; | |
| 37 } | |
| 38 | |
| 39 } // namespace | |
| 40 | |
| 41 HpackHuffmanTable::DecodeEntry::DecodeEntry() | |
| 42 : next_table_index(0), length(0), symbol_id(0) { | |
| 43 } | |
| 44 HpackHuffmanTable::DecodeEntry::DecodeEntry(uint8 next_table_index, | |
| 45 uint8 length, | |
| 46 uint16 symbol_id) | |
| 47 : next_table_index(next_table_index), length(length), symbol_id(symbol_id) { | |
| 48 } | |
| 49 size_t HpackHuffmanTable::DecodeTable::size() const { | |
| 50 return size_t(1) << indexed_length; | |
| 51 } | |
| 52 | |
| 53 HpackHuffmanTable::HpackHuffmanTable() {} | |
| 54 | |
| 55 HpackHuffmanTable::~HpackHuffmanTable() {} | |
| 56 | |
| 57 bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols, | |
| 58 size_t symbol_count) { | |
| 59 CHECK(!IsInitialized()); | |
| 60 DCHECK(base::IsValueInRangeForNumericType<uint16>(symbol_count)); | |
| 61 | |
| 62 std::vector<Symbol> symbols(symbol_count); | |
| 63 // Validate symbol id sequence, and copy into |symbols|. | |
| 64 for (uint16 i = 0; i < symbol_count; i++) { | |
| 65 if (i != input_symbols[i].id) { | |
| 66 failed_symbol_id_ = i; | |
| 67 return false; | |
| 68 } | |
| 69 symbols[i] = input_symbols[i]; | |
| 70 } | |
| 71 // Order on length and ID ascending, to verify symbol codes are canonical. | |
| 72 std::sort(symbols.begin(), symbols.end(), SymbolLengthAndIdCompare); | |
| 73 if (symbols[0].code != 0) { | |
| 74 failed_symbol_id_ = 0; | |
| 75 return false; | |
| 76 } | |
| 77 for (size_t i = 1; i != symbols.size(); i++) { | |
| 78 unsigned code_shift = 32 - symbols[i-1].length; | |
| 79 uint32 code = symbols[i-1].code + (1 << code_shift); | |
| 80 | |
| 81 if (code != symbols[i].code) { | |
| 82 failed_symbol_id_ = symbols[i].id; | |
| 83 return false; | |
| 84 } | |
| 85 if (code < symbols[i-1].code) { | |
| 86 // An integer overflow occurred. This implies the input | |
| 87 // lengths do not represent a valid Huffman code. | |
| 88 failed_symbol_id_ = symbols[i].id; | |
| 89 return false; | |
| 90 } | |
| 91 } | |
| 92 if (symbols.back().length < 8) { | |
| 93 // At least one code (such as an EOS symbol) must be 8 bits or longer. | |
| 94 // Without this, some inputs will not be encodable in a whole number | |
| 95 // of bytes. | |
| 96 return false; | |
| 97 } | |
| 98 pad_bits_ = static_cast<uint8>(symbols.back().code >> 24); | |
| 99 | |
| 100 BuildDecodeTables(symbols); | |
| 101 // Order on symbol ID ascending. | |
| 102 std::sort(symbols.begin(), symbols.end(), SymbolIdCompare); | |
| 103 BuildEncodeTable(symbols); | |
| 104 return true; | |
| 105 } | |
| 106 | |
| 107 void HpackHuffmanTable::BuildEncodeTable(const std::vector<Symbol>& symbols) { | |
| 108 for (size_t i = 0; i != symbols.size(); i++) { | |
| 109 const Symbol& symbol = symbols[i]; | |
| 110 CHECK_EQ(i, symbol.id); | |
| 111 code_by_id_.push_back(symbol.code); | |
| 112 length_by_id_.push_back(symbol.length); | |
| 113 } | |
| 114 } | |
| 115 | |
| 116 void HpackHuffmanTable::BuildDecodeTables(const std::vector<Symbol>& symbols) { | |
| 117 AddDecodeTable(0, kDecodeTableRootBits); | |
| 118 // We wish to maximize the flatness of the DecodeTable hierarchy (subject to | |
| 119 // the |kDecodeTableBranchBits| constraint), and to minimize the size of | |
| 120 // child tables. To achieve this, we iterate in order of descending code | |
| 121 // length. This ensures that child tables are visited with their longest | |
| 122 // entry first, and that the child can therefore be minimally sized to hold | |
| 123 // that entry without fear of introducing unneccesary branches later. | |
| 124 for (std::vector<Symbol>::const_reverse_iterator it = symbols.rbegin(); | |
| 125 it != symbols.rend(); ++it) { | |
| 126 uint8 table_index = 0; | |
| 127 while (true) { | |
| 128 const DecodeTable table = decode_tables_[table_index]; | |
| 129 | |
| 130 // Mask and shift the portion of the code being indexed into low bits. | |
| 131 uint32 index = (it->code << table.prefix_length); | |
| 132 index = index >> (32 - table.indexed_length); | |
| 133 | |
| 134 CHECK_LT(index, table.size()); | |
| 135 DecodeEntry entry = Entry(table, index); | |
| 136 | |
| 137 uint8 total_indexed = table.prefix_length + table.indexed_length; | |
| 138 if (total_indexed >= it->length) { | |
| 139 // We're writing a terminal entry. | |
| 140 entry.length = it->length; | |
| 141 entry.symbol_id = it->id; | |
| 142 entry.next_table_index = table_index; | |
| 143 SetEntry(table, index, entry); | |
| 144 break; | |
| 145 } | |
| 146 | |
| 147 if (entry.length == 0) { | |
| 148 // First visit to this placeholder. We need to create a new table. | |
| 149 CHECK_EQ(entry.next_table_index, 0); | |
| 150 entry.length = it->length; | |
| 151 entry.next_table_index = AddDecodeTable( | |
| 152 total_indexed, // Becomes the new table prefix. | |
| 153 std::min<uint8>(kDecodeTableBranchBits, | |
| 154 entry.length - total_indexed)); | |
| 155 SetEntry(table, index, entry); | |
| 156 } | |
| 157 CHECK_NE(entry.next_table_index, table_index); | |
| 158 table_index = entry.next_table_index; | |
| 159 } | |
| 160 } | |
| 161 // Fill shorter table entries into the additional entry spots they map to. | |
| 162 for (size_t i = 0; i != decode_tables_.size(); i++) { | |
| 163 const DecodeTable& table = decode_tables_[i]; | |
| 164 uint8 total_indexed = table.prefix_length + table.indexed_length; | |
| 165 | |
| 166 size_t j = 0; | |
| 167 while (j != table.size()) { | |
| 168 const DecodeEntry& entry = Entry(table, j); | |
| 169 if (entry.length != 0 && entry.length < total_indexed) { | |
| 170 // The difference between entry & table bit counts tells us how | |
| 171 // many additional entries map to this one. | |
| 172 size_t fill_count = 1 << (total_indexed - entry.length); | |
| 173 CHECK_LE(j + fill_count, table.size()); | |
| 174 | |
| 175 for (size_t k = 1; k != fill_count; k++) { | |
| 176 CHECK_EQ(Entry(table, j + k).length, 0); | |
| 177 SetEntry(table, j + k, entry); | |
| 178 } | |
| 179 j += fill_count; | |
| 180 } else { | |
| 181 j++; | |
| 182 } | |
| 183 } | |
| 184 } | |
| 185 } | |
| 186 | |
| 187 uint8 HpackHuffmanTable::AddDecodeTable(uint8 prefix, uint8 indexed) { | |
| 188 CHECK_LT(decode_tables_.size(), 255u); | |
| 189 { | |
| 190 DecodeTable table; | |
| 191 table.prefix_length = prefix; | |
| 192 table.indexed_length = indexed; | |
| 193 table.entries_offset = decode_entries_.size(); | |
| 194 decode_tables_.push_back(table); | |
| 195 } | |
| 196 decode_entries_.resize(decode_entries_.size() + (size_t(1) << indexed)); | |
| 197 return static_cast<uint8>(decode_tables_.size() - 1); | |
| 198 } | |
| 199 | |
| 200 const HpackHuffmanTable::DecodeEntry& HpackHuffmanTable::Entry( | |
| 201 const DecodeTable& table, | |
| 202 uint32 index) const { | |
| 203 DCHECK_LT(index, table.size()); | |
| 204 DCHECK_LT(table.entries_offset + index, decode_entries_.size()); | |
| 205 return decode_entries_[table.entries_offset + index]; | |
| 206 } | |
| 207 | |
| 208 void HpackHuffmanTable::SetEntry(const DecodeTable& table, | |
| 209 uint32 index, | |
| 210 const DecodeEntry& entry) { | |
| 211 CHECK_LT(index, table.size()); | |
| 212 CHECK_LT(table.entries_offset + index, decode_entries_.size()); | |
| 213 decode_entries_[table.entries_offset + index] = entry; | |
| 214 } | |
| 215 | |
| 216 bool HpackHuffmanTable::IsInitialized() const { | |
| 217 return !code_by_id_.empty(); | |
| 218 } | |
| 219 | |
| 220 void HpackHuffmanTable::EncodeString(StringPiece in, | |
| 221 HpackOutputStream* out) const { | |
| 222 size_t bit_remnant = 0; | |
| 223 for (size_t i = 0; i != in.size(); i++) { | |
| 224 uint16 symbol_id = static_cast<uint8>(in[i]); | |
| 225 CHECK_GT(code_by_id_.size(), symbol_id); | |
| 226 | |
| 227 // Load, and shift code to low bits. | |
| 228 unsigned length = length_by_id_[symbol_id]; | |
| 229 uint32 code = code_by_id_[symbol_id] >> (32 - length); | |
| 230 | |
| 231 bit_remnant = (bit_remnant + length) % 8; | |
| 232 | |
| 233 if (length > 24) { | |
| 234 out->AppendBits(static_cast<uint8>(code >> 24), length - 24); | |
| 235 length = 24; | |
| 236 } | |
| 237 if (length > 16) { | |
| 238 out->AppendBits(static_cast<uint8>(code >> 16), length - 16); | |
| 239 length = 16; | |
| 240 } | |
| 241 if (length > 8) { | |
| 242 out->AppendBits(static_cast<uint8>(code >> 8), length - 8); | |
| 243 length = 8; | |
| 244 } | |
| 245 out->AppendBits(static_cast<uint8>(code), length); | |
| 246 } | |
| 247 if (bit_remnant != 0) { | |
| 248 // Pad current byte as required. | |
| 249 out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant); | |
| 250 } | |
| 251 } | |
| 252 | |
| 253 size_t HpackHuffmanTable::EncodedSize(StringPiece in) const { | |
| 254 size_t bit_count = 0; | |
| 255 for (size_t i = 0; i != in.size(); i++) { | |
| 256 uint16 symbol_id = static_cast<uint8>(in[i]); | |
| 257 CHECK_GT(code_by_id_.size(), symbol_id); | |
| 258 | |
| 259 bit_count += length_by_id_[symbol_id]; | |
| 260 } | |
| 261 if (bit_count % 8 != 0) { | |
| 262 bit_count += 8 - bit_count % 8; | |
| 263 } | |
| 264 return bit_count / 8; | |
| 265 } | |
| 266 | |
| 267 bool HpackHuffmanTable::DecodeString(HpackInputStream* in, | |
| 268 size_t out_capacity, | |
| 269 string* out) const { | |
| 270 // Number of decode iterations required for a 32-bit code. | |
| 271 const int kDecodeIterations = static_cast<int>( | |
| 272 std::ceil((32.f - kDecodeTableRootBits) / kDecodeTableBranchBits)); | |
| 273 | |
| 274 out->clear(); | |
| 275 | |
| 276 // Current input, stored in the high |bits_available| bits of |bits|. | |
| 277 uint32 bits = 0; | |
| 278 size_t bits_available = 0; | |
| 279 bool peeked_success = in->PeekBits(&bits_available, &bits); | |
| 280 | |
| 281 while (true) { | |
| 282 const DecodeTable* table = &decode_tables_[0]; | |
| 283 uint32 index = bits >> (32 - kDecodeTableRootBits); | |
| 284 | |
| 285 for (int i = 0; i != kDecodeIterations; i++) { | |
| 286 DCHECK_LT(index, table->size()); | |
| 287 DCHECK_LT(Entry(*table, index).next_table_index, decode_tables_.size()); | |
| 288 | |
| 289 table = &decode_tables_[Entry(*table, index).next_table_index]; | |
| 290 // Mask and shift the portion of the code being indexed into low bits. | |
| 291 index = (bits << table->prefix_length) >> (32 - table->indexed_length); | |
| 292 } | |
| 293 const DecodeEntry& entry = Entry(*table, index); | |
| 294 | |
| 295 if (entry.length > bits_available) { | |
| 296 if (!peeked_success) { | |
| 297 // Unable to read enough input for a match. If only a portion of | |
| 298 // the last byte remains, this is a successful EOF condition. | |
| 299 in->ConsumeByteRemainder(); | |
| 300 return !in->HasMoreData(); | |
| 301 } | |
| 302 } else if (entry.length == 0) { | |
| 303 // The input is an invalid prefix, larger than any prefix in the table. | |
| 304 return false; | |
| 305 } else { | |
| 306 if (out->size() == out_capacity) { | |
| 307 // This code would cause us to overflow |out_capacity|. | |
| 308 return false; | |
| 309 } | |
| 310 if (entry.symbol_id < 256) { | |
| 311 // Assume symbols >= 256 are used for padding. | |
| 312 out->push_back(static_cast<char>(entry.symbol_id)); | |
| 313 } | |
| 314 | |
| 315 in->ConsumeBits(entry.length); | |
| 316 bits = bits << entry.length; | |
| 317 bits_available -= entry.length; | |
| 318 } | |
| 319 peeked_success = in->PeekBits(&bits_available, &bits); | |
| 320 } | |
| 321 NOTREACHED(); | |
| 322 return false; | |
| 323 } | |
| 324 | |
| 325 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 992733002:
Remove //net (except for Android test stuff) and sdch (Closed)
Base URL: git@github.com:domokit/mojo.git@master