1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// Copyright 2016 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.
#ifndef QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_
#define QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_
// HpackHuffmanDecoder is an incremental decoder of strings that have been
// encoded using the Huffman table defined in the HPACK spec.
// By incremental, we mean that the HpackHuffmanDecoder::Decode method does
// not require the entire string to be provided, and can instead decode the
// string as fragments of it become available (e.g. as HPACK block fragments
// are received for decoding by HpackEntryDecoder).
#include <stddef.h>
#include <cstdint>
#include <iosfwd>
#include <string>
#include "absl/strings/string_view.h"
#include "quiche/common/platform/api/quiche_export.h"
namespace http2 {
// HuffmanAccumulator is used to store bits during decoding, e.g. next N bits
// that have not yet been decoded, but have been extracted from the encoded
// string). An advantage of using a uint64 for the accumulator
// is that it has room for the bits of the longest code plus the bits of a full
// byte; that means that when adding more bits to the accumulator, it can always
// be done in whole bytes. For example, if we currently have 26 bits in the
// accumulator, and need more to decode the current symbol, we can add a whole
// byte to the accumulator, and not have to do juggling with adding 6 bits (to
// reach 30), and then keep track of the last two bits we've not been able to
// add to the accumulator.
typedef uint64_t HuffmanAccumulator;
typedef size_t HuffmanAccumulatorBitCount;
// HuffmanBitBuffer stores the leading edge of bits to be decoded. The high
// order bit of accumulator_ is the next bit to be decoded.
class QUICHE_EXPORT_PRIVATE HuffmanBitBuffer {
public:
HuffmanBitBuffer();
// Prepare for decoding a new Huffman encoded string.
void Reset();
// Add as many whole bytes to the accumulator (accumulator_) as possible,
// returning the number of bytes added.
size_t AppendBytes(absl::string_view input);
// Get the bits of the accumulator.
HuffmanAccumulator value() const { return accumulator_; }
// Number of bits of the encoded string that are in the accumulator
// (accumulator_).
HuffmanAccumulatorBitCount count() const { return count_; }
// Are there no bits in the accumulator?
bool IsEmpty() const { return count_ == 0; }
// Number of additional bits that can be added to the accumulator.
HuffmanAccumulatorBitCount free_count() const;
// Consume the leading |code_length| bits of the accumulator.
void ConsumeBits(HuffmanAccumulatorBitCount code_length);
// Are the contents valid for the end of a Huffman encoded string? The RFC
// states that EOS (end-of-string) symbol must not be explicitly encoded in
// the bit stream, but any unused bits in the final byte must be set to the
// prefix of the EOS symbol, which is all 1 bits. So there can be at most 7
// such bits.
// Returns true if the bit buffer is empty, or contains at most 7 bits, all
// of them 1. Otherwise returns false.
bool InputProperlyTerminated() const;
std::string DebugString() const;
private:
HuffmanAccumulator accumulator_;
HuffmanAccumulatorBitCount count_;
};
inline std::ostream& operator<<(std::ostream& out, const HuffmanBitBuffer& v) {
return out << v.DebugString();
}
class QUICHE_EXPORT_PRIVATE HpackHuffmanDecoder {
public:
HpackHuffmanDecoder();
~HpackHuffmanDecoder();
// Prepare for decoding a new Huffman encoded string.
void Reset() { bit_buffer_.Reset(); }
// Decode the portion of a HPACK Huffman encoded string that is in |input|,
// appending the decoded symbols into |*output|, stopping when more bits are
// needed to determine the next symbol, which/ means that the input has been
// drained, and also that the bit_buffer_ is empty or that the bits that are
// in it are not a whole symbol.
// If |input| is the start of a string, the caller must first call Reset.
// If |input| includes the end of the encoded string, the caller must call
// InputProperlyTerminated after Decode has returned true in order to
// determine if the encoded string was properly terminated.
// Returns false if something went wrong (e.g. the encoding contains the code
// EOS symbol). Otherwise returns true, in which case input has been fully
// decoded or buffered; in particular, if the low-order bit of the final byte
// of the input is not the last bit of an encoded symbol, then bit_buffer_
// will contain the leading bits of the code for that symbol, but not the
// final bits of that code.
// Note that output should be empty, but that it is not cleared by Decode().
bool Decode(absl::string_view input, std::string* output);
// Is what remains in the bit_buffer_ valid at the end of an encoded string?
// Call after passing the the final portion of a Huffman string to Decode,
// and getting true as the result.
bool InputProperlyTerminated() const {
return bit_buffer_.InputProperlyTerminated();
}
std::string DebugString() const;
private:
HuffmanBitBuffer bit_buffer_;
};
inline std::ostream& operator<<(std::ostream& out,
const HpackHuffmanDecoder& v) {
return out << v.DebugString();
}
} // namespace http2
#endif // QUICHE_HTTP2_HPACK_HUFFMAN_HPACK_HUFFMAN_DECODER_H_
|
