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 "net/third_party/quiche/src/http2/decoder/decode_buffer.h" 19 #include "net/third_party/quiche/src/http2/decoder/decode_status.h" 20 #include "net/third_party/quiche/src/http2/hpack/varint/hpack_varint_decoder.h" 21 #include "net/third_party/quiche/src/http2/platform/api/http2_logging.h" 22 #include "net/third_party/quiche/src/http2/platform/api/http2_macros.h" 23 #include "net/third_party/quiche/src/common/platform/api/quiche_export.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_PRIVATE 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 HTTP2_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 HTTP2_FALLTHROUGH; 100 101 case kDecodingString: 102 HTTP2_DVLOG(2) << "kDecodingString: db->Remaining=" << db->Remaining() 103 << " remaining_=" << remaining_; 104 return DecodeString(db, cb); 105 106 case kResumeDecodingLength: 107 HTTP2_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, 128 Listener* cb, 129 DecodeStatus* status) { 130 if (db->Empty()) { 131 *status = DecodeStatus::kDecodeInProgress; 132 state_ = kStartDecodingLength; 133 return false; 134 } 135 uint8_t h_and_prefix = db->DecodeUInt8(); 136 huffman_encoded_ = (h_and_prefix & 0x80) == 0x80; 137 *status = length_decoder_.Start(h_and_prefix, 7, db); 138 if (*status == DecodeStatus::kDecodeDone) { 139 OnStringStart(cb, status); 140 return true; 141 } 142 // Set the state to cover the DecodeStatus::kDecodeInProgress case. 143 // Won't be needed if the status is kDecodeError. 144 state_ = kResumeDecodingLength; 145 return false; 146 } 147 148 // Returns true if the length is fully decoded and the listener wants the 149 // decoding to continue, false otherwise; status is set to the status from 150 // the varint decoder; state_ is updated when fully decoded. 151 // If the length is not fully decoded, case state_ is set appropriately 152 // for the next call to Resume. 153 template <class Listener> ResumeDecodingLength(DecodeBuffer * db,Listener * cb,DecodeStatus * status)154 bool ResumeDecodingLength(DecodeBuffer* db, 155 Listener* cb, 156 DecodeStatus* status) { 157 DCHECK_EQ(state_, kResumeDecodingLength); 158 *status = length_decoder_.Resume(db); 159 if (*status == DecodeStatus::kDecodeDone) { 160 state_ = kDecodingString; 161 OnStringStart(cb, status); 162 return true; 163 } 164 return false; 165 } 166 167 // Returns true if the listener wants the decoding to continue, and 168 // false otherwise, in which case status set. 169 template <class Listener> OnStringStart(Listener * cb,DecodeStatus *)170 void OnStringStart(Listener* cb, DecodeStatus* /*status*/) { 171 // TODO(vasilvv): fail explicitly in case of truncation. 172 remaining_ = static_cast<size_t>(length_decoder_.value()); 173 // Make callback so consumer knows what is coming. 174 cb->OnStringStart(huffman_encoded_, remaining_); 175 } 176 177 // Passes the available portion of the string to the listener, and signals 178 // the end of the string when it is reached. Returns kDecodeDone or 179 // kDecodeInProgress as appropriate. 180 template <class Listener> DecodeString(DecodeBuffer * db,Listener * cb)181 DecodeStatus DecodeString(DecodeBuffer* db, Listener* cb) { 182 size_t len = std::min(remaining_, db->Remaining()); 183 if (len > 0) { 184 cb->OnStringData(db->cursor(), len); 185 db->AdvanceCursor(len); 186 remaining_ -= len; 187 } 188 if (remaining_ == 0) { 189 cb->OnStringEnd(); 190 return DecodeStatus::kDecodeDone; 191 } 192 state_ = kDecodingString; 193 return DecodeStatus::kDecodeInProgress; 194 } 195 196 HpackVarintDecoder length_decoder_; 197 198 // These fields are initialized just to keep ASAN happy about reading 199 // them from DebugString(). 200 size_t remaining_ = 0; 201 StringDecoderState state_ = kStartDecodingLength; 202 bool huffman_encoded_ = false; 203 }; 204 205 QUICHE_EXPORT_PRIVATE std::ostream& operator<<(std::ostream& out, 206 const HpackStringDecoder& v); 207 208 } // namespace http2 209 #endif // QUICHE_HTTP2_HPACK_DECODER_HPACK_STRING_DECODER_H_ 210