Project import generated by Copybara.
PiperOrigin-RevId: 229942388
Change-Id: Ib5a23c152c95ed4294cece9f902227c21ce531ef
diff --git a/spdy/core/hpack/hpack_huffman_table.cc b/spdy/core/hpack/hpack_huffman_table.cc
new file mode 100644
index 0000000..c917767
--- /dev/null
+++ b/spdy/core/hpack/hpack_huffman_table.cc
@@ -0,0 +1,151 @@
+// 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/third_party/quiche/src/spdy/core/hpack/hpack_huffman_table.h"
+
+#include <algorithm>
+#include <cmath>
+#include <limits>
+#include <memory>
+
+#include "base/logging.h"
+#include "net/third_party/quiche/src/spdy/core/hpack/hpack_output_stream.h"
+#include "net/third_party/quiche/src/spdy/platform/api/spdy_estimate_memory_usage.h"
+
+namespace spdy {
+
+namespace {
+
+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::HpackHuffmanTable() : pad_bits_(0), failed_symbol_id_(0) {}
+
+HpackHuffmanTable::~HpackHuffmanTable() = default;
+
+bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols,
+ size_t symbol_count) {
+ CHECK(!IsInitialized());
+ DCHECK_LE(symbol_count, std::numeric_limits<uint16_t>::max());
+
+ std::vector<Symbol> symbols(symbol_count);
+ // Validate symbol id sequence, and copy into |symbols|.
+ for (uint16_t 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_t 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_t>(symbols.back().code >> 24);
+
+ // 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);
+ }
+}
+
+bool HpackHuffmanTable::IsInitialized() const {
+ return !code_by_id_.empty();
+}
+
+void HpackHuffmanTable::EncodeString(SpdyStringPiece in,
+ HpackOutputStream* out) const {
+ size_t bit_remnant = 0;
+ for (size_t i = 0; i != in.size(); i++) {
+ uint16_t symbol_id = static_cast<uint8_t>(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_t code = code_by_id_[symbol_id] >> (32 - length);
+
+ bit_remnant = (bit_remnant + length) % 8;
+
+ if (length > 24) {
+ out->AppendBits(static_cast<uint8_t>(code >> 24), length - 24);
+ length = 24;
+ }
+ if (length > 16) {
+ out->AppendBits(static_cast<uint8_t>(code >> 16), length - 16);
+ length = 16;
+ }
+ if (length > 8) {
+ out->AppendBits(static_cast<uint8_t>(code >> 8), length - 8);
+ length = 8;
+ }
+ out->AppendBits(static_cast<uint8_t>(code), length);
+ }
+ if (bit_remnant != 0) {
+ // Pad current byte as required.
+ out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant);
+ }
+}
+
+size_t HpackHuffmanTable::EncodedSize(SpdyStringPiece in) const {
+ size_t bit_count = 0;
+ for (size_t i = 0; i != in.size(); i++) {
+ uint16_t symbol_id = static_cast<uint8_t>(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;
+}
+
+size_t HpackHuffmanTable::EstimateMemoryUsage() const {
+ return SpdyEstimateMemoryUsage(code_by_id_) +
+ SpdyEstimateMemoryUsage(length_by_id_);
+}
+
+} // namespace spdy
