1 // Copyright 2018 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "quiche/quic/core/qpack/qpack_instruction_decoder.h"
6
7 #include <algorithm>
8 #include <utility>
9
10 #include "absl/strings/string_view.h"
11 #include "quiche/quic/platform/api/quic_bug_tracker.h"
12 #include "quiche/quic/platform/api/quic_logging.h"
13
14 namespace quic {
15
16 namespace {
17
18 // Maximum length of header name and header value. This limits the amount of
19 // memory the peer can make the decoder allocate when sending string literals.
20 const size_t kStringLiteralLengthLimit = 1024 * 1024;
21
22 } // namespace
23
QpackInstructionDecoder(const QpackLanguage * language,Delegate * delegate)24 QpackInstructionDecoder::QpackInstructionDecoder(const QpackLanguage* language,
25 Delegate* delegate)
26 : language_(language),
27 delegate_(delegate),
28 s_bit_(false),
29 varint_(0),
30 varint2_(0),
31 is_huffman_encoded_(false),
32 string_length_(0),
33 error_detected_(false),
34 state_(State::kStartInstruction) {}
35
Decode(absl::string_view data)36 bool QpackInstructionDecoder::Decode(absl::string_view data) {
37 QUICHE_DCHECK(!data.empty());
38 QUICHE_DCHECK(!error_detected_);
39
40 while (true) {
41 bool success = true;
42 size_t bytes_consumed = 0;
43
44 switch (state_) {
45 case State::kStartInstruction:
46 success = DoStartInstruction(data);
47 break;
48 case State::kStartField:
49 success = DoStartField();
50 break;
51 case State::kReadBit:
52 success = DoReadBit(data);
53 break;
54 case State::kVarintStart:
55 success = DoVarintStart(data, &bytes_consumed);
56 break;
57 case State::kVarintResume:
58 success = DoVarintResume(data, &bytes_consumed);
59 break;
60 case State::kVarintDone:
61 success = DoVarintDone();
62 break;
63 case State::kReadString:
64 success = DoReadString(data, &bytes_consumed);
65 break;
66 case State::kReadStringDone:
67 success = DoReadStringDone();
68 break;
69 }
70
71 if (!success) {
72 return false;
73 }
74
75 // |success| must be false if an error is detected.
76 QUICHE_DCHECK(!error_detected_);
77
78 QUICHE_DCHECK_LE(bytes_consumed, data.size());
79
80 data = absl::string_view(data.data() + bytes_consumed,
81 data.size() - bytes_consumed);
82
83 // Stop processing if no more data but next state would require it.
84 if (data.empty() && (state_ != State::kStartField) &&
85 (state_ != State::kVarintDone) && (state_ != State::kReadStringDone)) {
86 return true;
87 }
88 }
89 }
90
AtInstructionBoundary() const91 bool QpackInstructionDecoder::AtInstructionBoundary() const {
92 return state_ == State::kStartInstruction;
93 }
94
DoStartInstruction(absl::string_view data)95 bool QpackInstructionDecoder::DoStartInstruction(absl::string_view data) {
96 QUICHE_DCHECK(!data.empty());
97
98 instruction_ = LookupOpcode(data[0]);
99 field_ = instruction_->fields.begin();
100
101 state_ = State::kStartField;
102 return true;
103 }
104
DoStartField()105 bool QpackInstructionDecoder::DoStartField() {
106 if (field_ == instruction_->fields.end()) {
107 // Completed decoding this instruction.
108
109 if (!delegate_->OnInstructionDecoded(instruction_)) {
110 return false;
111 }
112
113 state_ = State::kStartInstruction;
114 return true;
115 }
116
117 switch (field_->type) {
118 case QpackInstructionFieldType::kSbit:
119 case QpackInstructionFieldType::kName:
120 case QpackInstructionFieldType::kValue:
121 state_ = State::kReadBit;
122 return true;
123 case QpackInstructionFieldType::kVarint:
124 case QpackInstructionFieldType::kVarint2:
125 state_ = State::kVarintStart;
126 return true;
127 default:
128 QUIC_BUG(quic_bug_10767_1) << "Invalid field type.";
129 return false;
130 }
131 }
132
DoReadBit(absl::string_view data)133 bool QpackInstructionDecoder::DoReadBit(absl::string_view data) {
134 QUICHE_DCHECK(!data.empty());
135
136 switch (field_->type) {
137 case QpackInstructionFieldType::kSbit: {
138 const uint8_t bitmask = field_->param;
139 s_bit_ = (data[0] & bitmask) == bitmask;
140
141 ++field_;
142 state_ = State::kStartField;
143
144 return true;
145 }
146 case QpackInstructionFieldType::kName:
147 case QpackInstructionFieldType::kValue: {
148 const uint8_t prefix_length = field_->param;
149 QUICHE_DCHECK_GE(7, prefix_length);
150 const uint8_t bitmask = 1 << prefix_length;
151 is_huffman_encoded_ = (data[0] & bitmask) == bitmask;
152
153 state_ = State::kVarintStart;
154
155 return true;
156 }
157 default:
158 QUIC_BUG(quic_bug_10767_2) << "Invalid field type.";
159 return false;
160 }
161 }
162
DoVarintStart(absl::string_view data,size_t * bytes_consumed)163 bool QpackInstructionDecoder::DoVarintStart(absl::string_view data,
164 size_t* bytes_consumed) {
165 QUICHE_DCHECK(!data.empty());
166 QUICHE_DCHECK(field_->type == QpackInstructionFieldType::kVarint ||
167 field_->type == QpackInstructionFieldType::kVarint2 ||
168 field_->type == QpackInstructionFieldType::kName ||
169 field_->type == QpackInstructionFieldType::kValue);
170
171 http2::DecodeBuffer buffer(data.data() + 1, data.size() - 1);
172 http2::DecodeStatus status =
173 varint_decoder_.Start(data[0], field_->param, &buffer);
174
175 *bytes_consumed = 1 + buffer.Offset();
176 switch (status) {
177 case http2::DecodeStatus::kDecodeDone:
178 state_ = State::kVarintDone;
179 return true;
180 case http2::DecodeStatus::kDecodeInProgress:
181 state_ = State::kVarintResume;
182 return true;
183 case http2::DecodeStatus::kDecodeError:
184 OnError(ErrorCode::INTEGER_TOO_LARGE, "Encoded integer too large.");
185 return false;
186 default:
187 QUIC_BUG(quic_bug_10767_3) << "Unknown decode status " << status;
188 return false;
189 }
190 }
191
DoVarintResume(absl::string_view data,size_t * bytes_consumed)192 bool QpackInstructionDecoder::DoVarintResume(absl::string_view data,
193 size_t* bytes_consumed) {
194 QUICHE_DCHECK(!data.empty());
195 QUICHE_DCHECK(field_->type == QpackInstructionFieldType::kVarint ||
196 field_->type == QpackInstructionFieldType::kVarint2 ||
197 field_->type == QpackInstructionFieldType::kName ||
198 field_->type == QpackInstructionFieldType::kValue);
199
200 http2::DecodeBuffer buffer(data);
201 http2::DecodeStatus status = varint_decoder_.Resume(&buffer);
202
203 *bytes_consumed = buffer.Offset();
204 switch (status) {
205 case http2::DecodeStatus::kDecodeDone:
206 state_ = State::kVarintDone;
207 return true;
208 case http2::DecodeStatus::kDecodeInProgress:
209 QUICHE_DCHECK_EQ(*bytes_consumed, data.size());
210 QUICHE_DCHECK(buffer.Empty());
211 return true;
212 case http2::DecodeStatus::kDecodeError:
213 OnError(ErrorCode::INTEGER_TOO_LARGE, "Encoded integer too large.");
214 return false;
215 default:
216 QUIC_BUG(quic_bug_10767_4) << "Unknown decode status " << status;
217 return false;
218 }
219 }
220
DoVarintDone()221 bool QpackInstructionDecoder::DoVarintDone() {
222 QUICHE_DCHECK(field_->type == QpackInstructionFieldType::kVarint ||
223 field_->type == QpackInstructionFieldType::kVarint2 ||
224 field_->type == QpackInstructionFieldType::kName ||
225 field_->type == QpackInstructionFieldType::kValue);
226
227 if (field_->type == QpackInstructionFieldType::kVarint) {
228 varint_ = varint_decoder_.value();
229
230 ++field_;
231 state_ = State::kStartField;
232 return true;
233 }
234
235 if (field_->type == QpackInstructionFieldType::kVarint2) {
236 varint2_ = varint_decoder_.value();
237
238 ++field_;
239 state_ = State::kStartField;
240 return true;
241 }
242
243 string_length_ = varint_decoder_.value();
244 if (string_length_ > kStringLiteralLengthLimit) {
245 OnError(ErrorCode::STRING_LITERAL_TOO_LONG, "String literal too long.");
246 return false;
247 }
248
249 std::string* const string =
250 (field_->type == QpackInstructionFieldType::kName) ? &name_ : &value_;
251 string->clear();
252
253 if (string_length_ == 0) {
254 ++field_;
255 state_ = State::kStartField;
256 return true;
257 }
258
259 string->reserve(string_length_);
260
261 state_ = State::kReadString;
262 return true;
263 }
264
DoReadString(absl::string_view data,size_t * bytes_consumed)265 bool QpackInstructionDecoder::DoReadString(absl::string_view data,
266 size_t* bytes_consumed) {
267 QUICHE_DCHECK(!data.empty());
268 QUICHE_DCHECK(field_->type == QpackInstructionFieldType::kName ||
269 field_->type == QpackInstructionFieldType::kValue);
270
271 std::string* const string =
272 (field_->type == QpackInstructionFieldType::kName) ? &name_ : &value_;
273 QUICHE_DCHECK_LT(string->size(), string_length_);
274
275 *bytes_consumed = std::min(string_length_ - string->size(), data.size());
276 string->append(data.data(), *bytes_consumed);
277
278 QUICHE_DCHECK_LE(string->size(), string_length_);
279 if (string->size() == string_length_) {
280 state_ = State::kReadStringDone;
281 }
282 return true;
283 }
284
DoReadStringDone()285 bool QpackInstructionDecoder::DoReadStringDone() {
286 QUICHE_DCHECK(field_->type == QpackInstructionFieldType::kName ||
287 field_->type == QpackInstructionFieldType::kValue);
288
289 std::string* const string =
290 (field_->type == QpackInstructionFieldType::kName) ? &name_ : &value_;
291 QUICHE_DCHECK_EQ(string->size(), string_length_);
292
293 if (is_huffman_encoded_) {
294 huffman_decoder_.Reset();
295 // HpackHuffmanDecoder::Decode() cannot perform in-place decoding.
296 std::string decoded_value;
297 huffman_decoder_.Decode(*string, &decoded_value);
298 if (!huffman_decoder_.InputProperlyTerminated()) {
299 OnError(ErrorCode::HUFFMAN_ENCODING_ERROR,
300 "Error in Huffman-encoded string.");
301 return false;
302 }
303 *string = std::move(decoded_value);
304 }
305
306 ++field_;
307 state_ = State::kStartField;
308 return true;
309 }
310
LookupOpcode(uint8_t byte) const311 const QpackInstruction* QpackInstructionDecoder::LookupOpcode(
312 uint8_t byte) const {
313 for (const auto* instruction : *language_) {
314 if ((byte & instruction->opcode.mask) == instruction->opcode.value) {
315 return instruction;
316 }
317 }
318 // |language_| should be defined such that instruction opcodes cover every
319 // possible input.
320 QUICHE_DCHECK(false);
321 return nullptr;
322 }
323
OnError(ErrorCode error_code,absl::string_view error_message)324 void QpackInstructionDecoder::OnError(ErrorCode error_code,
325 absl::string_view error_message) {
326 QUICHE_DCHECK(!error_detected_);
327
328 error_detected_ = true;
329 delegate_->OnInstructionDecodingError(error_code, error_message);
330 }
331
332 } // namespace quic
333