1 // Copyright 2016 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/http2/hpack/varint/hpack_varint_decoder.h"
6
7 #include "absl/strings/str_cat.h"
8
9 namespace http2 {
10
Start(uint8_t prefix_value,uint8_t prefix_length,DecodeBuffer * db)11 DecodeStatus HpackVarintDecoder::Start(uint8_t prefix_value,
12 uint8_t prefix_length,
13 DecodeBuffer* db) {
14 QUICHE_DCHECK_LE(3u, prefix_length);
15 QUICHE_DCHECK_LE(prefix_length, 8u);
16
17 // |prefix_mask| defines the sequence of low-order bits of the first byte
18 // that encode the prefix of the value. It is also the marker in those bits
19 // of the first byte indicating that at least one extension byte is needed.
20 const uint8_t prefix_mask = (1 << prefix_length) - 1;
21
22 // Ignore the bits that aren't a part of the prefix of the varint.
23 value_ = prefix_value & prefix_mask;
24
25 if (value_ < prefix_mask) {
26 MarkDone();
27 return DecodeStatus::kDecodeDone;
28 }
29
30 offset_ = 0;
31 return Resume(db);
32 }
33
StartExtended(uint8_t prefix_length,DecodeBuffer * db)34 DecodeStatus HpackVarintDecoder::StartExtended(uint8_t prefix_length,
35 DecodeBuffer* db) {
36 QUICHE_DCHECK_LE(3u, prefix_length);
37 QUICHE_DCHECK_LE(prefix_length, 8u);
38
39 value_ = (1 << prefix_length) - 1;
40 offset_ = 0;
41 return Resume(db);
42 }
43
Resume(DecodeBuffer * db)44 DecodeStatus HpackVarintDecoder::Resume(DecodeBuffer* db) {
45 // There can be at most 10 continuation bytes. Offset is zero for the
46 // first one and increases by 7 for each subsequent one.
47 const uint8_t kMaxOffset = 63;
48 CheckNotDone();
49
50 // Process most extension bytes without the need for overflow checking.
51 while (offset_ < kMaxOffset) {
52 if (db->Empty()) {
53 return DecodeStatus::kDecodeInProgress;
54 }
55
56 uint8_t byte = db->DecodeUInt8();
57 uint64_t summand = byte & 0x7f;
58
59 // Shifting a 7 bit value to the left by at most 56 places can never
60 // overflow on uint64_t.
61 QUICHE_DCHECK_LE(offset_, 56);
62 QUICHE_DCHECK_LE(summand, std::numeric_limits<uint64_t>::max() >> offset_);
63
64 summand <<= offset_;
65
66 // At this point,
67 // |value_| is at most (2^prefix_length - 1) + (2^49 - 1), and
68 // |summand| is at most 255 << 56 (which is smaller than 2^63),
69 // so adding them can never overflow on uint64_t.
70 QUICHE_DCHECK_LE(value_, std::numeric_limits<uint64_t>::max() - summand);
71
72 value_ += summand;
73
74 // Decoding ends if continuation flag is not set.
75 if ((byte & 0x80) == 0) {
76 MarkDone();
77 return DecodeStatus::kDecodeDone;
78 }
79
80 offset_ += 7;
81 }
82
83 if (db->Empty()) {
84 return DecodeStatus::kDecodeInProgress;
85 }
86
87 QUICHE_DCHECK_EQ(kMaxOffset, offset_);
88
89 uint8_t byte = db->DecodeUInt8();
90 // No more extension bytes are allowed after this.
91 if ((byte & 0x80) == 0) {
92 uint64_t summand = byte & 0x7f;
93 // Check for overflow in left shift.
94 if (summand <= std::numeric_limits<uint64_t>::max() >> offset_) {
95 summand <<= offset_;
96 // Check for overflow in addition.
97 if (value_ <= std::numeric_limits<uint64_t>::max() - summand) {
98 value_ += summand;
99 MarkDone();
100 return DecodeStatus::kDecodeDone;
101 }
102 }
103 }
104
105 // Signal error if value is too large or there are too many extension bytes.
106 QUICHE_DLOG(WARNING)
107 << "Variable length int encoding is too large or too long. "
108 << DebugString();
109 MarkDone();
110 return DecodeStatus::kDecodeError;
111 }
112
value() const113 uint64_t HpackVarintDecoder::value() const {
114 CheckDone();
115 return value_;
116 }
117
set_value(uint64_t v)118 void HpackVarintDecoder::set_value(uint64_t v) {
119 MarkDone();
120 value_ = v;
121 }
122
DebugString() const123 std::string HpackVarintDecoder::DebugString() const {
124 return absl::StrCat("HpackVarintDecoder(value=", value_, ", offset=", offset_,
125 ")");
126 }
127
StartForTest(uint8_t prefix_value,uint8_t prefix_length,DecodeBuffer * db)128 DecodeStatus HpackVarintDecoder::StartForTest(uint8_t prefix_value,
129 uint8_t prefix_length,
130 DecodeBuffer* db) {
131 return Start(prefix_value, prefix_length, db);
132 }
133
StartExtendedForTest(uint8_t prefix_length,DecodeBuffer * db)134 DecodeStatus HpackVarintDecoder::StartExtendedForTest(uint8_t prefix_length,
135 DecodeBuffer* db) {
136 return StartExtended(prefix_length, db);
137 }
138
ResumeForTest(DecodeBuffer * db)139 DecodeStatus HpackVarintDecoder::ResumeForTest(DecodeBuffer* db) {
140 return Resume(db);
141 }
142
143 } // namespace http2
144