| // 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/quic/core/qpack/qpack_progressive_decoder.h" |
| |
| #include "base/logging.h" |
| #include "net/third_party/quiche/src/quic/core/qpack/qpack_constants.h" |
| #include "net/third_party/quiche/src/quic/core/qpack/qpack_header_table.h" |
| #include "net/third_party/quiche/src/quic/platform/api/quic_ptr_util.h" |
| |
| namespace quic { |
| |
| QpackProgressiveDecoder::QpackProgressiveDecoder( |
| QuicStreamId stream_id, |
| QpackHeaderTable* header_table, |
| QpackDecoderStreamSender* decoder_stream_sender, |
| HeadersHandlerInterface* handler) |
| : stream_id_(stream_id), |
| prefix_decoder_( |
| QuicMakeUnique<QpackInstructionDecoder>(QpackPrefixLanguage(), this)), |
| instruction_decoder_(QpackRequestStreamLanguage(), this), |
| header_table_(header_table), |
| decoder_stream_sender_(decoder_stream_sender), |
| handler_(handler), |
| largest_reference_(0), |
| base_index_(0), |
| largest_reference_seen_(0), |
| prefix_decoded_(false), |
| decoding_(true), |
| error_detected_(false) {} |
| |
| // static |
| bool QpackProgressiveDecoder::DecodeLargestReference( |
| uint64_t wire_largest_reference, |
| uint64_t max_entries, |
| uint64_t total_number_of_inserts, |
| uint64_t* largest_reference) { |
| if (wire_largest_reference == 0) { |
| *largest_reference = 0; |
| return true; |
| } |
| |
| // |max_entries| is calculated by dividing an unsigned 64-bit integer by 32, |
| // precluding all calculations in this method from overflowing. |
| DCHECK_LE(max_entries, std::numeric_limits<uint64_t>::max() / 32); |
| |
| if (wire_largest_reference > 2 * max_entries) { |
| return false; |
| } |
| |
| *largest_reference = wire_largest_reference - 1; |
| DCHECK_LT(*largest_reference, std::numeric_limits<uint64_t>::max() / 16); |
| |
| uint64_t current_wrapped = total_number_of_inserts % (2 * max_entries); |
| DCHECK_LT(current_wrapped, std::numeric_limits<uint64_t>::max() / 16); |
| |
| if (current_wrapped >= *largest_reference + max_entries) { |
| // Largest Reference wrapped around 1 extra time. |
| *largest_reference += 2 * max_entries; |
| } else if (current_wrapped + max_entries < *largest_reference) { |
| // Decoder wrapped around 1 extra time. |
| current_wrapped += 2 * max_entries; |
| } |
| |
| if (*largest_reference > |
| std::numeric_limits<uint64_t>::max() - total_number_of_inserts) { |
| return false; |
| } |
| |
| *largest_reference += total_number_of_inserts; |
| |
| // Prevent underflow, but also disallow invalid value 0 for Largest Reference. |
| if (current_wrapped >= *largest_reference) { |
| return false; |
| } |
| |
| *largest_reference -= current_wrapped; |
| |
| return true; |
| } |
| |
| void QpackProgressiveDecoder::Decode(QuicStringPiece data) { |
| DCHECK(decoding_); |
| |
| if (data.empty() || error_detected_) { |
| return; |
| } |
| |
| // Decode prefix byte by byte until the first (and only) instruction is |
| // decoded. |
| while (!prefix_decoded_) { |
| prefix_decoder_->Decode(data.substr(0, 1)); |
| data = data.substr(1); |
| if (data.empty()) { |
| return; |
| } |
| } |
| |
| instruction_decoder_.Decode(data); |
| } |
| |
| void QpackProgressiveDecoder::EndHeaderBlock() { |
| DCHECK(decoding_); |
| decoding_ = false; |
| |
| if (error_detected_) { |
| return; |
| } |
| |
| if (!instruction_decoder_.AtInstructionBoundary()) { |
| OnError("Incomplete header block."); |
| return; |
| } |
| |
| if (!prefix_decoded_) { |
| OnError("Incomplete header data prefix."); |
| return; |
| } |
| |
| if (largest_reference_ != largest_reference_seen_) { |
| OnError("Largest Reference too large."); |
| return; |
| } |
| |
| decoder_stream_sender_->SendHeaderAcknowledgement(stream_id_); |
| handler_->OnDecodingCompleted(); |
| } |
| |
| bool QpackProgressiveDecoder::OnInstructionDecoded( |
| const QpackInstruction* instruction) { |
| if (instruction == QpackIndexedHeaderFieldInstruction()) { |
| return DoIndexedHeaderFieldInstruction(); |
| } |
| if (instruction == QpackIndexedHeaderFieldPostBaseInstruction()) { |
| return DoIndexedHeaderFieldPostBaseInstruction(); |
| } |
| if (instruction == QpackLiteralHeaderFieldNameReferenceInstruction()) { |
| return DoLiteralHeaderFieldNameReferenceInstruction(); |
| } |
| if (instruction == QpackLiteralHeaderFieldPostBaseInstruction()) { |
| return DoLiteralHeaderFieldPostBaseInstruction(); |
| } |
| if (instruction == QpackLiteralHeaderFieldInstruction()) { |
| return DoLiteralHeaderFieldInstruction(); |
| } |
| DCHECK_EQ(instruction, QpackPrefixInstruction()); |
| return DoPrefixInstruction(); |
| } |
| |
| void QpackProgressiveDecoder::OnError(QuicStringPiece error_message) { |
| DCHECK(!error_detected_); |
| |
| error_detected_ = true; |
| handler_->OnDecodingErrorDetected(error_message); |
| } |
| |
| bool QpackProgressiveDecoder::DoIndexedHeaderFieldInstruction() { |
| if (!instruction_decoder_.s_bit()) { |
| uint64_t absolute_index; |
| if (!RequestStreamRelativeIndexToAbsoluteIndex( |
| instruction_decoder_.varint(), &absolute_index)) { |
| OnError("Invalid relative index."); |
| return false; |
| } |
| |
| if (absolute_index > largest_reference_) { |
| OnError("Index larger than Largest Reference."); |
| return false; |
| } |
| |
| largest_reference_seen_ = std::max(largest_reference_seen_, absolute_index); |
| |
| DCHECK_NE(0u, absolute_index); |
| const uint64_t real_index = absolute_index - 1; |
| auto entry = |
| header_table_->LookupEntry(/* is_static = */ false, real_index); |
| if (!entry) { |
| OnError("Dynamic table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), entry->value()); |
| return true; |
| } |
| |
| auto entry = header_table_->LookupEntry(/* is_static = */ true, |
| instruction_decoder_.varint()); |
| if (!entry) { |
| OnError("Static table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), entry->value()); |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DoIndexedHeaderFieldPostBaseInstruction() { |
| uint64_t absolute_index; |
| if (!PostBaseIndexToAbsoluteIndex(instruction_decoder_.varint(), |
| &absolute_index)) { |
| OnError("Invalid post-base index."); |
| return false; |
| } |
| |
| if (absolute_index > largest_reference_) { |
| OnError("Index larger than Largest Reference."); |
| return false; |
| } |
| |
| largest_reference_seen_ = std::max(largest_reference_seen_, absolute_index); |
| |
| DCHECK_NE(0u, absolute_index); |
| const uint64_t real_index = absolute_index - 1; |
| auto entry = header_table_->LookupEntry(/* is_static = */ false, real_index); |
| if (!entry) { |
| OnError("Dynamic table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), entry->value()); |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DoLiteralHeaderFieldNameReferenceInstruction() { |
| if (!instruction_decoder_.s_bit()) { |
| uint64_t absolute_index; |
| if (!RequestStreamRelativeIndexToAbsoluteIndex( |
| instruction_decoder_.varint(), &absolute_index)) { |
| OnError("Invalid relative index."); |
| return false; |
| } |
| |
| if (absolute_index > largest_reference_) { |
| OnError("Index larger than Largest Reference."); |
| return false; |
| } |
| |
| largest_reference_seen_ = std::max(largest_reference_seen_, absolute_index); |
| |
| DCHECK_NE(0u, absolute_index); |
| const uint64_t real_index = absolute_index - 1; |
| auto entry = |
| header_table_->LookupEntry(/* is_static = */ false, real_index); |
| if (!entry) { |
| OnError("Dynamic table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), instruction_decoder_.value()); |
| return true; |
| } |
| |
| auto entry = header_table_->LookupEntry(/* is_static = */ true, |
| instruction_decoder_.varint()); |
| if (!entry) { |
| OnError("Static table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), instruction_decoder_.value()); |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DoLiteralHeaderFieldPostBaseInstruction() { |
| uint64_t absolute_index; |
| if (!PostBaseIndexToAbsoluteIndex(instruction_decoder_.varint(), |
| &absolute_index)) { |
| OnError("Invalid post-base index."); |
| return false; |
| } |
| |
| if (absolute_index > largest_reference_) { |
| OnError("Index larger than Largest Reference."); |
| return false; |
| } |
| |
| largest_reference_seen_ = std::max(largest_reference_seen_, absolute_index); |
| |
| DCHECK_NE(0u, absolute_index); |
| const uint64_t real_index = absolute_index - 1; |
| auto entry = header_table_->LookupEntry(/* is_static = */ false, real_index); |
| if (!entry) { |
| OnError("Dynamic table entry not found."); |
| return false; |
| } |
| |
| handler_->OnHeaderDecoded(entry->name(), instruction_decoder_.value()); |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DoLiteralHeaderFieldInstruction() { |
| handler_->OnHeaderDecoded(instruction_decoder_.name(), |
| instruction_decoder_.value()); |
| |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DoPrefixInstruction() { |
| DCHECK(!prefix_decoded_); |
| |
| if (!DecodeLargestReference( |
| prefix_decoder_->varint(), header_table_->max_entries(), |
| header_table_->inserted_entry_count(), &largest_reference_)) { |
| OnError("Error decoding Largest Reference."); |
| return false; |
| } |
| |
| const bool sign = prefix_decoder_->s_bit(); |
| const uint64_t delta_base_index = prefix_decoder_->varint2(); |
| if (!DeltaBaseIndexToBaseIndex(sign, delta_base_index, &base_index_)) { |
| OnError("Error calculating Base Index."); |
| return false; |
| } |
| |
| prefix_decoded_ = true; |
| |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::DeltaBaseIndexToBaseIndex( |
| bool sign, |
| uint64_t delta_base_index, |
| uint64_t* base_index) { |
| if (sign) { |
| if (delta_base_index == std::numeric_limits<uint64_t>::max() || |
| largest_reference_ < delta_base_index + 1) { |
| return false; |
| } |
| *base_index = largest_reference_ - delta_base_index - 1; |
| return true; |
| } |
| |
| if (delta_base_index > |
| std::numeric_limits<uint64_t>::max() - largest_reference_) { |
| return false; |
| } |
| *base_index = largest_reference_ + delta_base_index; |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::RequestStreamRelativeIndexToAbsoluteIndex( |
| uint64_t relative_index, |
| uint64_t* absolute_index) const { |
| if (relative_index == std::numeric_limits<uint64_t>::max() || |
| relative_index + 1 > base_index_) { |
| return false; |
| } |
| |
| *absolute_index = base_index_ - relative_index; |
| return true; |
| } |
| |
| bool QpackProgressiveDecoder::PostBaseIndexToAbsoluteIndex( |
| uint64_t post_base_index, |
| uint64_t* absolute_index) const { |
| if (post_base_index >= std::numeric_limits<uint64_t>::max() - base_index_) { |
| return false; |
| } |
| |
| *absolute_index = base_index_ + post_base_index + 1; |
| return true; |
| } |
| |
| } // namespace quic |