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