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