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 #ifndef QUICHE_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ 6 #define QUICHE_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ 7 8 // HpackStringDecoder decodes strings encoded per the HPACK spec; this does 9 // not mean decompressing Huffman encoded strings, just identifying the length, 10 // encoding and contents for a listener. 11 12 #include <stddef.h> 13 14 #include <algorithm> 15 #include <cstdint> 16 #include <string> 17 18 #include "absl/base/macros.h" 19 #include "quiche/http2/decoder/decode_buffer.h" 20 #include "quiche/http2/decoder/decode_status.h" 21 #include "quiche/http2/hpack/varint/hpack_varint_decoder.h" 22 #include "quiche/common/platform/api/quiche_export.h" 23 #include "quiche/common/platform/api/quiche_logging.h" 24 25 namespace http2 { 26 27 // Decodes a single string in an HPACK header entry. The high order bit of 28 // the first byte of the length is the H (Huffman) bit indicating whether 29 // the value is Huffman encoded, and the remainder of the byte is the first 30 // 7 bits of an HPACK varint. 31 // 32 // Call Start() to begin decoding; if it returns kDecodeInProgress, then call 33 // Resume() when more input is available, repeating until kDecodeInProgress is 34 // not returned. If kDecodeDone or kDecodeError is returned, then Resume() must 35 // not be called until Start() has been called to start decoding a new string. 36 class QUICHE_EXPORT HpackStringDecoder { 37 public: 38 enum StringDecoderState { 39 kStartDecodingLength, 40 kDecodingString, 41 kResumeDecodingLength, 42 }; 43 44 template <class Listener> Start(DecodeBuffer * db,Listener * cb)45 DecodeStatus Start(DecodeBuffer* db, Listener* cb) { 46 // Fast decode path is used if the string is under 127 bytes and the 47 // entire length of the string is in the decode buffer. More than 83% of 48 // string lengths are encoded in just one byte. 49 if (db->HasData() && (*db->cursor() & 0x7f) != 0x7f) { 50 // The string is short. 51 uint8_t h_and_prefix = db->DecodeUInt8(); 52 uint8_t length = h_and_prefix & 0x7f; 53 bool huffman_encoded = (h_and_prefix & 0x80) == 0x80; 54 cb->OnStringStart(huffman_encoded, length); 55 if (length <= db->Remaining()) { 56 // Yeah, we've got the whole thing in the decode buffer. 57 // Ideally this will be the common case. Note that we don't 58 // update any of the member variables in this path. 59 cb->OnStringData(db->cursor(), length); 60 db->AdvanceCursor(length); 61 cb->OnStringEnd(); 62 return DecodeStatus::kDecodeDone; 63 } 64 // Not all in the buffer. 65 huffman_encoded_ = huffman_encoded; 66 remaining_ = length; 67 // Call Resume to decode the string body, which is only partially 68 // in the decode buffer (or not at all). 69 state_ = kDecodingString; 70 return Resume(db, cb); 71 } 72 // Call Resume to decode the string length, which is either not in 73 // the decode buffer, or spans multiple bytes. 74 state_ = kStartDecodingLength; 75 return Resume(db, cb); 76 } 77 78 template <class Listener> Resume(DecodeBuffer * db,Listener * cb)79 DecodeStatus Resume(DecodeBuffer* db, Listener* cb) { 80 DecodeStatus status; 81 while (true) { 82 switch (state_) { 83 case kStartDecodingLength: 84 QUICHE_DVLOG(2) << "kStartDecodingLength: db->Remaining=" 85 << db->Remaining(); 86 if (!StartDecodingLength(db, cb, &status)) { 87 // The length is split across decode buffers. 88 return status; 89 } 90 // We've finished decoding the length, which spanned one or more 91 // bytes. Approximately 17% of strings have a length that is greater 92 // than 126 bytes, and thus the length is encoded in more than one 93 // byte, and so doesn't get the benefit of the optimization in 94 // Start() for single byte lengths. But, we still expect that most 95 // of such strings will be contained entirely in a single decode 96 // buffer, and hence this fall through skips another trip through the 97 // switch above and more importantly skips setting the state_ variable 98 // again in those cases where we don't need it. 99 ABSL_FALLTHROUGH_INTENDED; 100 101 case kDecodingString: 102 QUICHE_DVLOG(2) << "kDecodingString: db->Remaining=" 103 << db->Remaining() << " remaining_=" << remaining_; 104 return DecodeString(db, cb); 105 106 case kResumeDecodingLength: 107 QUICHE_DVLOG(2) << "kResumeDecodingLength: db->Remaining=" 108 << db->Remaining(); 109 if (!ResumeDecodingLength(db, cb, &status)) { 110 return status; 111 } 112 } 113 } 114 } 115 116 std::string DebugString() const; 117 118 private: 119 static std::string StateToString(StringDecoderState v); 120 121 // Returns true if the length is fully decoded and the listener wants the 122 // decoding to continue, false otherwise; status is set to the status from 123 // the varint decoder. 124 // If the length is not fully decoded, case state_ is set appropriately 125 // for the next call to Resume. 126 template <class Listener> StartDecodingLength(DecodeBuffer * db,Listener * cb,DecodeStatus * status)127 bool StartDecodingLength(DecodeBuffer* db, Listener* cb, 128 DecodeStatus* status) { 129 if (db->Empty()) { 130 *status = DecodeStatus::kDecodeInProgress; 131 state_ = kStartDecodingLength; 132 return false; 133 } 134 uint8_t h_and_prefix = db->DecodeUInt8(); 135 huffman_encoded_ = (h_and_prefix & 0x80) == 0x80; 136 *status = length_decoder_.Start(h_and_prefix, 7, db); 137 if (*status == DecodeStatus::kDecodeDone) { 138 OnStringStart(cb, status); 139 return true; 140 } 141 // Set the state to cover the DecodeStatus::kDecodeInProgress case. 142 // Won't be needed if the status is kDecodeError. 143 state_ = kResumeDecodingLength; 144 return false; 145 } 146 147 // Returns true if the length is fully decoded and the listener wants the 148 // decoding to continue, false otherwise; status is set to the status from 149 // the varint decoder; state_ is updated when fully decoded. 150 // If the length is not fully decoded, case state_ is set appropriately 151 // for the next call to Resume. 152 template <class Listener> ResumeDecodingLength(DecodeBuffer * db,Listener * cb,DecodeStatus * status)153 bool ResumeDecodingLength(DecodeBuffer* db, Listener* cb, 154 DecodeStatus* status) { 155 QUICHE_DCHECK_EQ(state_, kResumeDecodingLength); 156 *status = length_decoder_.Resume(db); 157 if (*status == DecodeStatus::kDecodeDone) { 158 state_ = kDecodingString; 159 OnStringStart(cb, status); 160 return true; 161 } 162 return false; 163 } 164 165 // Returns true if the listener wants the decoding to continue, and 166 // false otherwise, in which case status set. 167 template <class Listener> OnStringStart(Listener * cb,DecodeStatus *)168 void OnStringStart(Listener* cb, DecodeStatus* /*status*/) { 169 // TODO(vasilvv): fail explicitly in case of truncation. 170 remaining_ = static_cast<size_t>(length_decoder_.value()); 171 // Make callback so consumer knows what is coming. 172 cb->OnStringStart(huffman_encoded_, remaining_); 173 } 174 175 // Passes the available portion of the string to the listener, and signals 176 // the end of the string when it is reached. Returns kDecodeDone or 177 // kDecodeInProgress as appropriate. 178 template <class Listener> DecodeString(DecodeBuffer * db,Listener * cb)179 DecodeStatus DecodeString(DecodeBuffer* db, Listener* cb) { 180 size_t len = std::min(remaining_, db->Remaining()); 181 if (len > 0) { 182 cb->OnStringData(db->cursor(), len); 183 db->AdvanceCursor(len); 184 remaining_ -= len; 185 } 186 if (remaining_ == 0) { 187 cb->OnStringEnd(); 188 return DecodeStatus::kDecodeDone; 189 } 190 state_ = kDecodingString; 191 return DecodeStatus::kDecodeInProgress; 192 } 193 194 HpackVarintDecoder length_decoder_; 195 196 // These fields are initialized just to keep ASAN happy about reading 197 // them from DebugString(). 198 size_t remaining_ = 0; 199 StringDecoderState state_ = kStartDecodingLength; 200 bool huffman_encoded_ = false; 201 }; 202 203 QUICHE_EXPORT std::ostream& operator<<(std::ostream& out, 204 const HpackStringDecoder& v); 205 206 } // namespace http2 207 #endif // QUICHE_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ 208