net/spdy/hpack_huffman_table.cc - platform/external/chromium_org - Git at Google

 // 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
	// 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