hpack_huffman_table.cc

// 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/spdy/hpack_huffman_table.h"

#include <algorithm>
#include <cmath>

#include "base/logging.h"
#include "net/spdy/hpack_input_stream.h"
#include "net/spdy/hpack_output_stream.h"

namespace net {

using base::StringPiece;
using std::string;

namespace {

// How many bits to index in the root decode table.
const uint8 kDecodeTableRootBits = 9;
// Maximum number of bits to index in successive decode tables.
const uint8 kDecodeTableBranchBits = 6;

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::DecodeEntry::DecodeEntry()
  : next_table_index(0), length(0), symbol_id(0) {
}
HpackHuffmanTable::DecodeEntry::DecodeEntry(uint8 next_table_index,
                                            uint8 length,
                                            uint16 symbol_id)
  : next_table_index(next_table_index), length(length), symbol_id(symbol_id) {
}
size_t HpackHuffmanTable::DecodeTable::size() const {
  return size_t(1) << indexed_length;
}

HpackHuffmanTable::HpackHuffmanTable() {}

HpackHuffmanTable::~HpackHuffmanTable() {}

bool HpackHuffmanTable::Initialize(const HpackHuffmanSymbol* input_symbols,
                                   size_t symbol_count) {
  CHECK(!IsInitialized());

  std::vector<Symbol> symbols(symbol_count);
  // Validate symbol id sequence, and copy into |symbols|.
  for (size_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 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>(symbols.back().code >> 24);

  BuildDecodeTables(symbols);
  // 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);
  }
}

void HpackHuffmanTable::BuildDecodeTables(const std::vector<Symbol>& symbols) {
  AddDecodeTable(0, kDecodeTableRootBits);
  // We wish to maximize the flatness of the DecodeTable hierarchy (subject to
  // the |kDecodeTableBranchBits| constraint), and to minimize the size of
  // child tables. To achieve this, we iterate in order of descending code
  // length. This ensures that child tables are visited with their longest
  // entry first, and that the child can therefore be minimally sized to hold
  // that entry without fear of introducing unneccesary branches later.
  for (std::vector<Symbol>::const_reverse_iterator it = symbols.rbegin();
       it != symbols.rend(); ++it) {
    uint8 table_index = 0;
    while (true) {
      const DecodeTable table = decode_tables_[table_index];

      // Mask and shift the portion of the code being indexed into low bits.
      uint32 index = (it->code << table.prefix_length);
      index = index >> (32 - table.indexed_length);

      CHECK_LT(index, table.size());
      DecodeEntry entry = Entry(table, index);

      uint8 total_indexed = table.prefix_length + table.indexed_length;
      if (total_indexed >= it->length) {
        // We're writing a terminal entry.
        entry.length = it->length;
        entry.symbol_id = it->id;
        entry.next_table_index = table_index;
        SetEntry(table, index, entry);
        break;
      }

      if (entry.length == 0) {
        // First visit to this placeholder. We need to create a new table.
        CHECK_EQ(entry.next_table_index, 0);
        entry.length = it->length;
        entry.next_table_index = AddDecodeTable(
            total_indexed,  // Becomes the new table prefix.
            std::min<uint8>(kDecodeTableBranchBits,
                            entry.length - total_indexed));
        SetEntry(table, index, entry);
      }
      CHECK_NE(entry.next_table_index, table_index);
      table_index = entry.next_table_index;
    }
  }
  // Fill shorter table entries into the additional entry spots they map to.
  for (size_t i = 0; i != decode_tables_.size(); i++) {
    const DecodeTable& table = decode_tables_[i];
    uint8 total_indexed = table.prefix_length + table.indexed_length;

    size_t j = 0;
    while (j != table.size()) {
      const DecodeEntry& entry = Entry(table, j);
      if (entry.length != 0 && entry.length < total_indexed) {
        // The difference between entry & table bit counts tells us how
        // many additional entries map to this one.
        size_t fill_count = 1 << (total_indexed - entry.length);
        CHECK_LE(j + fill_count, table.size());

        for (size_t k = 1; k != fill_count; k++) {
          CHECK_EQ(Entry(table, j + k).length, 0);
          SetEntry(table, j + k, entry);
        }
        j += fill_count;
      } else {
        j++;
      }
    }
  }
}

uint8 HpackHuffmanTable::AddDecodeTable(uint8 prefix, uint8 indexed) {
  CHECK_LT(decode_tables_.size(), 255u);
  {
    DecodeTable table;
    table.prefix_length = prefix;
    table.indexed_length = indexed;
    table.entries_offset = decode_entries_.size();
    decode_tables_.push_back(table);
  }
  decode_entries_.resize(decode_entries_.size() + (size_t(1) << indexed));
  return static_cast<uint8>(decode_tables_.size() - 1);
}

const HpackHuffmanTable::DecodeEntry& HpackHuffmanTable::Entry(
    const DecodeTable& table,
    uint32 index) const {
  DCHECK_LT(index, table.size());
  DCHECK_LT(table.entries_offset + index, decode_entries_.size());
  return decode_entries_[table.entries_offset + index];
}

void HpackHuffmanTable::SetEntry(const DecodeTable& table,
                                 uint32 index,
                                 const DecodeEntry& entry) {
  CHECK_LT(index, table.size());
  CHECK_LT(table.entries_offset + index, decode_entries_.size());
  decode_entries_[table.entries_offset + index] = entry;
}

bool HpackHuffmanTable::IsInitialized() const {
  return !code_by_id_.empty();
}

void HpackHuffmanTable::EncodeString(StringPiece in,
                                     HpackOutputStream* out) const {
  size_t bit_remnant = 0;
  for (size_t i = 0; i != in.size(); i++) {
    uint16 symbol_id = static_cast<uint8>(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 code = code_by_id_[symbol_id] >> (32 - length);

    bit_remnant = (bit_remnant + length) % 8;

    if (length > 24) {
      out->AppendBits(static_cast<uint8>(code >> 24), length - 24);
      length = 24;
    }
    if (length > 16) {
      out->AppendBits(static_cast<uint8>(code >> 16), length - 16);
      length = 16;
    }
    if (length > 8) {
      out->AppendBits(static_cast<uint8>(code >> 8), length - 8);
      length = 8;
    }
    out->AppendBits(static_cast<uint8>(code), length);
  }
  if (bit_remnant != 0) {
    // Pad current byte as required.
    out->AppendBits(pad_bits_ >> bit_remnant, 8 - bit_remnant);
  }
}

size_t HpackHuffmanTable::EncodedSize(StringPiece in) const {
  size_t bit_count = 0;
  for (size_t i = 0; i != in.size(); i++) {
    uint16 symbol_id = static_cast<uint8>(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;
}

bool HpackHuffmanTable::DecodeString(HpackInputStream* in,
                                     size_t out_capacity,
                                     string* out) const {
  // Number of decode iterations required for a 32-bit code.
  const int kDecodeIterations = static_cast<int>(
      std::ceil((32.f - kDecodeTableRootBits) / kDecodeTableBranchBits));

  out->clear();

  // Current input, stored in the high |bits_available| bits of |bits|.
  uint32 bits = 0;
  size_t bits_available = 0;
  bool peeked_success = in->PeekBits(&bits_available, &bits);

  while (true) {
    const DecodeTable* table = &decode_tables_[0];
    uint32 index = bits >> (32 - kDecodeTableRootBits);

    for (int i = 0; i != kDecodeIterations; i++) {
      DCHECK_LT(index, table->size());
      DCHECK_LT(Entry(*table, index).next_table_index, decode_tables_.size());

      table = &decode_tables_[Entry(*table, index).next_table_index];
      // Mask and shift the portion of the code being indexed into low bits.
      index = (bits << table->prefix_length) >> (32 - table->indexed_length);
    }
    const DecodeEntry& entry = Entry(*table, index);

    if (entry.length > bits_available) {
      if (!peeked_success) {
        // Unable to read enough input for a match. If only a portion of
        // the last byte remains, this is a successful EOF condition.
        in->ConsumeByteRemainder();
        return !in->HasMoreData();
      }
    } else if (entry.length == 0) {
      // The input is an invalid prefix, larger than any prefix in the table.
      return false;
    } else {
      if (out->size() == out_capacity) {
        // This code would cause us to overflow |out_capacity|.
        return false;
      }
      if (entry.symbol_id < 256) {
        // Assume symbols >= 256 are used for padding.
        out->push_back(static_cast<char>(entry.symbol_id));
      }

      in->ConsumeBits(entry.length);
      bits = bits << entry.length;
      bits_available -= entry.length;
    }
    peeked_success = in->PeekBits(&bits_available, &bits);
  }
  NOTREACHED();
  return false;
}

}  // namespace net