blob: 9f561eedf46d7e03d4776e38715868985acdbd01 [file] [log] [blame] [edit]
// Copyright (c) 2018 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/http2/hpack/huffman/hpack_huffman_encoder.h"
#include "base/logging.h"
#include "net/third_party/quiche/src/http2/hpack/huffman/huffman_spec_tables.h"
// TODO(jamessynge): Remove use of binary literals, that is a C++ 14 feature.
namespace http2 {
size_t ExactHuffmanSize(Http2StringPiece plain) {
size_t bits = 0;
for (const uint8_t c : plain) {
bits += HuffmanSpecTables::kCodeLengths[c];
}
return (bits + 7) / 8;
}
size_t BoundedHuffmanSize(Http2StringPiece plain) {
// TODO(jamessynge): Determine whether we should set the min size for Huffman
// encoding much higher (i.e. if less than N, then the savings isn't worth
// the cost of encoding and decoding). Of course, we need to decide on a
// value function, which might be throughput on a full load test, or a
// microbenchmark of the time to encode and then decode a HEADERS frame,
// possibly with the cost of crypto included (i.e. crypto is going to have
// a fairly constant per-byte cost, so reducing the number of bytes in-transit
// reduces the number that must be encrypted and later decrypted).
if (plain.size() < 3) {
// Huffman encoded string can't be smaller than the plain size for very
// short strings.
return plain.size();
}
// TODO(jamessynge): Measure whether this can be done more efficiently with
// nested loops (e.g. make exact measurement of 8 bytes, then check if min
// remaining is too long).
// Compute the number of bits in an encoding that is shorter than the plain
// string (i.e. the number of bits in a string 1 byte shorter than plain),
// and use this as the limit of the size of the encoding.
const size_t limit_bits = (plain.size() - 1) * 8;
// The shortest code length in the Huffman table of the HPACK spec has 5 bits
// (e.g. for 0, 1, a and e).
const size_t min_code_length = 5;
// We can therefore say that all plain text bytes whose code length we've not
// yet looked up will take at least 5 bits.
size_t min_bits_remaining = plain.size() * min_code_length;
size_t bits = 0;
for (const uint8_t c : plain) {
bits += HuffmanSpecTables::kCodeLengths[c];
min_bits_remaining -= min_code_length;
// If our minimum estimate of the total number of bits won't yield an
// encoding shorter the plain text, let's bail.
const size_t minimum_bits_total = bits + min_bits_remaining;
if (minimum_bits_total > limit_bits) {
bits += min_bits_remaining;
break;
}
}
return (bits + 7) / 8;
}
void HuffmanEncode(Http2StringPiece plain, Http2String* huffman) {
DCHECK(huffman != nullptr);
huffman->clear(); // Note that this doesn't release memory.
uint64_t bit_buffer = 0; // High-bit is next bit to output. Not clear if that
// is more performant than having the low-bit be the
// last to be output.
size_t bits_unused = 64; // Number of bits available for the next code.
for (uint8_t c : plain) {
size_t code_length = HuffmanSpecTables::kCodeLengths[c];
if (bits_unused < code_length) {
// There isn't enough room in bit_buffer for the code of c.
// Flush until bits_unused > 56 (i.e. 64 - 8).
do {
char h = static_cast<char>(bit_buffer >> 56);
bit_buffer <<= 8;
bits_unused += 8;
// Perhaps would be more efficient if we populated an array of chars,
// so we don't have to call push_back each time. Reconsider if used
// for production.
huffman->push_back(h);
} while (bits_unused <= 56);
}
uint64_t code = HuffmanSpecTables::kRightCodes[c];
size_t shift_by = bits_unused - code_length;
bit_buffer |= (code << shift_by);
bits_unused -= code_length;
}
// bit_buffer contains (64-bits_unused) bits that still need to be flushed.
// Output whole bytes until we don't have any whole bytes left.
size_t bits_used = 64 - bits_unused;
while (bits_used >= 8) {
char h = static_cast<char>(bit_buffer >> 56);
bit_buffer <<= 8;
bits_used -= 8;
huffman->push_back(h);
}
if (bits_used > 0) {
// We have less than a byte left to output. The spec calls for padding out
// the final byte with the leading bits of the EOS symbol (30 1-bits).
constexpr uint64_t leading_eos_bits = 0b11111111;
bit_buffer |= (leading_eos_bits << (56 - bits_used));
char h = static_cast<char>(bit_buffer >> 56);
huffman->push_back(h);
}
}
} // namespace http2