| OLD | NEW |
| 1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "net/spdy/hpack_encoder.h" | 5 #include "net/spdy/hpack_encoder.h" |
| 6 | 6 |
| 7 #include <algorithm> | 7 #include <algorithm> |
| 8 | 8 |
| 9 #include "base/logging.h" | 9 #include "base/logging.h" |
| 10 #include "net/spdy/hpack_header_table.h" | 10 #include "net/spdy/hpack_header_table.h" |
| (...skipping 15 matching lines...) Expand all Loading... |
| 26 // Set on a entries added to the reference set during this encoding. | 26 // Set on a entries added to the reference set during this encoding. |
| 27 const uint8 kReferencedThisEncoding = 3; | 27 const uint8 kReferencedThisEncoding = 3; |
| 28 | 28 |
| 29 } // namespace | 29 } // namespace |
| 30 | 30 |
| 31 HpackEncoder::HpackEncoder(const HpackHuffmanTable& table) | 31 HpackEncoder::HpackEncoder(const HpackHuffmanTable& table) |
| 32 : output_stream_(), | 32 : output_stream_(), |
| 33 allow_huffman_compression_(true), | 33 allow_huffman_compression_(true), |
| 34 huffman_table_(table), | 34 huffman_table_(table), |
| 35 char_counts_(NULL), | 35 char_counts_(NULL), |
| 36 total_char_counts_(NULL) {} | 36 total_char_counts_(NULL) { |
| 37 } |
| 37 | 38 |
| 38 HpackEncoder::~HpackEncoder() {} | 39 HpackEncoder::~HpackEncoder() { |
| 40 } |
| 39 | 41 |
| 40 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set, | 42 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set, |
| 41 string* output) { | 43 string* output) { |
| 42 // Walk the set of entries to encode, which are not already implied by the | 44 // Walk the set of entries to encode, which are not already implied by the |
| 43 // header table's reference set. They must be explicitly emitted. | 45 // header table's reference set. They must be explicitly emitted. |
| 44 Representations explicit_set(DetermineEncodingDelta(header_set)); | 46 Representations explicit_set(DetermineEncodingDelta(header_set)); |
| 45 for (Representations::const_iterator it = explicit_set.begin(); | 47 for (Representations::const_iterator it = explicit_set.begin(); |
| 46 it != explicit_set.end(); ++it) { | 48 it != explicit_set.end(); |
| 49 ++it) { |
| 47 // Try to find an exact match. Note that dynamic entries are preferred | 50 // Try to find an exact match. Note that dynamic entries are preferred |
| 48 // by the header table index. | 51 // by the header table index. |
| 49 HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second); | 52 HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second); |
| 50 if (entry != NULL && !entry->IsStatic()) { | 53 if (entry != NULL && !entry->IsStatic()) { |
| 51 // Already in the dynamic table. Simply toggle on. | 54 // Already in the dynamic table. Simply toggle on. |
| 52 CHECK_EQ(kNoState, entry->state()); | 55 CHECK_EQ(kNoState, entry->state()); |
| 53 EmitDynamicIndex(entry); | 56 EmitDynamicIndex(entry); |
| 54 continue; | 57 continue; |
| 55 } | 58 } |
| 56 | 59 |
| (...skipping 17 matching lines...) Expand all Loading... |
| 74 } | 77 } |
| 75 } | 78 } |
| 76 if (entry != NULL) { | 79 if (entry != NULL) { |
| 77 EmitStaticIndex(entry); | 80 EmitStaticIndex(entry); |
| 78 } else { | 81 } else { |
| 79 EmitIndexedLiteral(*it); | 82 EmitIndexedLiteral(*it); |
| 80 } | 83 } |
| 81 } | 84 } |
| 82 // Walk the reference set, toggling off as needed and clearing encoding state. | 85 // Walk the reference set, toggling off as needed and clearing encoding state. |
| 83 for (HpackEntry::OrderedSet::const_iterator it = | 86 for (HpackEntry::OrderedSet::const_iterator it = |
| 84 header_table_.reference_set().begin(); | 87 header_table_.reference_set().begin(); |
| 85 it != header_table_.reference_set().end();) { | 88 it != header_table_.reference_set().end();) { |
| 86 HpackEntry* entry = *(it++); // Step to prevent invalidation. | 89 HpackEntry* entry = *(it++); // Step to prevent invalidation. |
| 87 CHECK_NE(kNoState, entry->state()); | 90 CHECK_NE(kNoState, entry->state()); |
| 88 | 91 |
| 89 if (entry->state() == kReferencedExplicitOff) { | 92 if (entry->state() == kReferencedExplicitOff) { |
| 90 // Explicitly toggle off. | 93 // Explicitly toggle off. |
| 91 EmitDynamicIndex(entry); | 94 EmitDynamicIndex(entry); |
| 92 } | 95 } |
| 93 entry->set_state(kNoState); | 96 entry->set_state(kNoState); |
| 94 } | 97 } |
| 95 output_stream_.TakeString(output); | 98 output_stream_.TakeString(output); |
| 96 return true; | 99 return true; |
| 97 } | 100 } |
| 98 | 101 |
| 99 bool HpackEncoder::EncodeHeaderSetWithoutCompression( | 102 bool HpackEncoder::EncodeHeaderSetWithoutCompression( |
| 100 const std::map<string, string>& header_set, | 103 const std::map<string, string>& header_set, |
| 101 string* output) { | 104 string* output) { |
| 102 | |
| 103 allow_huffman_compression_ = false; | 105 allow_huffman_compression_ = false; |
| 104 for (std::map<string, string>::const_iterator it = header_set.begin(); | 106 for (std::map<string, string>::const_iterator it = header_set.begin(); |
| 105 it != header_set.end(); ++it) { | 107 it != header_set.end(); |
| 108 ++it) { |
| 106 // Note that cookies are not crumbled in this case. | 109 // Note that cookies are not crumbled in this case. |
| 107 EmitNonIndexedLiteral(*it); | 110 EmitNonIndexedLiteral(*it); |
| 108 } | 111 } |
| 109 allow_huffman_compression_ = true; | 112 allow_huffman_compression_ = true; |
| 110 output_stream_.TakeString(output); | 113 output_stream_.TakeString(output); |
| 111 return true; | 114 return true; |
| 112 } | 115 } |
| 113 | 116 |
| 114 void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) { | 117 void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) { |
| 115 DCHECK(!entry->IsStatic()); | 118 DCHECK(!entry->IsStatic()); |
| 116 output_stream_.AppendPrefix(kIndexedOpcode); | 119 output_stream_.AppendPrefix(kIndexedOpcode); |
| 117 output_stream_.AppendUint32(entry->Index()); | 120 output_stream_.AppendUint32(entry->Index()); |
| 118 | 121 |
| 119 entry->set_state(kNoState); | 122 entry->set_state(kNoState); |
| 120 if (header_table_.Toggle(entry)) { | 123 if (header_table_.Toggle(entry)) { |
| 121 // Was added to the reference set. | 124 // Was added to the reference set. |
| 122 entry->set_state(kReferencedThisEncoding); | 125 entry->set_state(kReferencedThisEncoding); |
| 123 } | 126 } |
| 124 } | 127 } |
| 125 | 128 |
| 126 void HpackEncoder::EmitStaticIndex(HpackEntry* entry) { | 129 void HpackEncoder::EmitStaticIndex(HpackEntry* entry) { |
| 127 DCHECK(entry->IsStatic()); | 130 DCHECK(entry->IsStatic()); |
| 128 output_stream_.AppendPrefix(kIndexedOpcode); | 131 output_stream_.AppendPrefix(kIndexedOpcode); |
| 129 output_stream_.AppendUint32(entry->Index()); | 132 output_stream_.AppendUint32(entry->Index()); |
| 130 | 133 |
| 131 HpackEntry* new_entry = header_table_.TryAddEntry(entry->name(), | 134 HpackEntry* new_entry = |
| 132 entry->value()); | 135 header_table_.TryAddEntry(entry->name(), entry->value()); |
| 133 if (new_entry) { | 136 if (new_entry) { |
| 134 // This is a static entry: no need to pin. | 137 // This is a static entry: no need to pin. |
| 135 header_table_.Toggle(new_entry); | 138 header_table_.Toggle(new_entry); |
| 136 new_entry->set_state(kReferencedThisEncoding); | 139 new_entry->set_state(kReferencedThisEncoding); |
| 137 } | 140 } |
| 138 } | 141 } |
| 139 | 142 |
| 140 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) { | 143 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) { |
| 141 output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode); | 144 output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode); |
| 142 EmitLiteral(representation); | 145 EmitLiteral(representation); |
| 143 | 146 |
| 144 HpackEntry* new_entry = header_table_.TryAddEntry(representation.first, | 147 HpackEntry* new_entry = |
| 145 representation.second); | 148 header_table_.TryAddEntry(representation.first, representation.second); |
| 146 if (new_entry) { | 149 if (new_entry) { |
| 147 header_table_.Toggle(new_entry); | 150 header_table_.Toggle(new_entry); |
| 148 new_entry->set_state(kReferencedThisEncoding); | 151 new_entry->set_state(kReferencedThisEncoding); |
| 149 } | 152 } |
| 150 } | 153 } |
| 151 | 154 |
| 152 void HpackEncoder::EmitNonIndexedLiteral( | 155 void HpackEncoder::EmitNonIndexedLiteral(const Representation& representation) { |
| 153 const Representation& representation) { | |
| 154 output_stream_.AppendPrefix(kLiteralNoIndexOpcode); | 156 output_stream_.AppendPrefix(kLiteralNoIndexOpcode); |
| 155 output_stream_.AppendUint32(0); | 157 output_stream_.AppendUint32(0); |
| 156 EmitString(representation.first); | 158 EmitString(representation.first); |
| 157 EmitString(representation.second); | 159 EmitString(representation.second); |
| 158 } | 160 } |
| 159 | 161 |
| 160 void HpackEncoder::EmitLiteral(const Representation& representation) { | 162 void HpackEncoder::EmitLiteral(const Representation& representation) { |
| 161 const HpackEntry* name_entry = header_table_.GetByName(representation.first); | 163 const HpackEntry* name_entry = header_table_.GetByName(representation.first); |
| 162 if (name_entry != NULL) { | 164 if (name_entry != NULL) { |
| 163 output_stream_.AppendUint32(name_entry->Index()); | 165 output_stream_.AppendUint32(name_entry->Index()); |
| 164 } else { | 166 } else { |
| 165 output_stream_.AppendUint32(0); | 167 output_stream_.AppendUint32(0); |
| 166 EmitString(representation.first); | 168 EmitString(representation.first); |
| 167 } | 169 } |
| 168 EmitString(representation.second); | 170 EmitString(representation.second); |
| 169 } | 171 } |
| 170 | 172 |
| 171 void HpackEncoder::EmitString(StringPiece str) { | 173 void HpackEncoder::EmitString(StringPiece str) { |
| 172 size_t encoded_size = (!allow_huffman_compression_ ? str.size() | 174 size_t encoded_size = |
| 173 : huffman_table_.EncodedSize(str)); | 175 (!allow_huffman_compression_ ? str.size() |
| 176 : huffman_table_.EncodedSize(str)); |
| 174 if (encoded_size < str.size()) { | 177 if (encoded_size < str.size()) { |
| 175 output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded); | 178 output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded); |
| 176 output_stream_.AppendUint32(encoded_size); | 179 output_stream_.AppendUint32(encoded_size); |
| 177 huffman_table_.EncodeString(str, &output_stream_); | 180 huffman_table_.EncodeString(str, &output_stream_); |
| 178 } else { | 181 } else { |
| 179 output_stream_.AppendPrefix(kStringLiteralIdentityEncoded); | 182 output_stream_.AppendPrefix(kStringLiteralIdentityEncoded); |
| 180 output_stream_.AppendUint32(str.size()); | 183 output_stream_.AppendUint32(str.size()); |
| 181 output_stream_.AppendBytes(str); | 184 output_stream_.AppendBytes(str); |
| 182 } | 185 } |
| 183 UpdateCharacterCounts(str); | 186 UpdateCharacterCounts(str); |
| 184 } | 187 } |
| 185 | 188 |
| 186 // static | 189 // static |
| 187 HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta( | 190 HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta( |
| 188 const std::map<string, string>& header_set) { | 191 const std::map<string, string>& header_set) { |
| 189 // Flatten & crumble headers into an ordered list of representations. | 192 // Flatten & crumble headers into an ordered list of representations. |
| 190 Representations full_set; | 193 Representations full_set; |
| 191 for (std::map<string, string>::const_iterator it = header_set.begin(); | 194 for (std::map<string, string>::const_iterator it = header_set.begin(); |
| 192 it != header_set.end(); ++it) { | 195 it != header_set.end(); |
| 196 ++it) { |
| 193 if (it->first == "cookie") { | 197 if (it->first == "cookie") { |
| 194 // |CookieToCrumbs()| produces ordered crumbs. | 198 // |CookieToCrumbs()| produces ordered crumbs. |
| 195 CookieToCrumbs(*it, &full_set); | 199 CookieToCrumbs(*it, &full_set); |
| 196 } else { | 200 } else { |
| 197 // Note std::map guarantees representations are ordered. | 201 // Note std::map guarantees representations are ordered. |
| 198 full_set.push_back(make_pair( | 202 full_set.push_back( |
| 199 StringPiece(it->first), StringPiece(it->second))); | 203 make_pair(StringPiece(it->first), StringPiece(it->second))); |
| 200 } | 204 } |
| 201 } | 205 } |
| 202 // Perform a linear merge of ordered representations with the (also ordered) | 206 // Perform a linear merge of ordered representations with the (also ordered) |
| 203 // reference set. Mark each referenced entry with current membership state, | 207 // reference set. Mark each referenced entry with current membership state, |
| 204 // and gather representations which must be explicitly emitted. | 208 // and gather representations which must be explicitly emitted. |
| 205 Representations::const_iterator r_it = full_set.begin(); | 209 Representations::const_iterator r_it = full_set.begin(); |
| 206 HpackEntry::OrderedSet::const_iterator s_it = | 210 HpackEntry::OrderedSet::const_iterator s_it = |
| 207 header_table_.reference_set().begin(); | 211 header_table_.reference_set().begin(); |
| 208 | 212 |
| 209 Representations explicit_set; | 213 Representations explicit_set; |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 260 Representations* out) { | 264 Representations* out) { |
| 261 size_t prior_size = out->size(); | 265 size_t prior_size = out->size(); |
| 262 | 266 |
| 263 // See Section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 | 267 // See Section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2 |
| 264 // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 | 268 // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11 |
| 265 // Cookie values are split into individually-encoded HPACK representations. | 269 // Cookie values are split into individually-encoded HPACK representations. |
| 266 for (size_t pos = 0;;) { | 270 for (size_t pos = 0;;) { |
| 267 size_t end = cookie.second.find(";", pos); | 271 size_t end = cookie.second.find(";", pos); |
| 268 | 272 |
| 269 if (end == StringPiece::npos) { | 273 if (end == StringPiece::npos) { |
| 270 out->push_back(make_pair( | 274 out->push_back(make_pair(cookie.first, cookie.second.substr(pos))); |
| 271 cookie.first, | |
| 272 cookie.second.substr(pos))); | |
| 273 break; | 275 break; |
| 274 } | 276 } |
| 275 out->push_back(make_pair( | 277 out->push_back( |
| 276 cookie.first, | 278 make_pair(cookie.first, cookie.second.substr(pos, end - pos))); |
| 277 cookie.second.substr(pos, end - pos))); | |
| 278 | 279 |
| 279 // Consume next space if present. | 280 // Consume next space if present. |
| 280 pos = end + 1; | 281 pos = end + 1; |
| 281 if (pos != cookie.second.size() && cookie.second[pos] == ' ') { | 282 if (pos != cookie.second.size() && cookie.second[pos] == ' ') { |
| 282 pos++; | 283 pos++; |
| 283 } | 284 } |
| 284 } | 285 } |
| 285 // Sort crumbs and remove duplicates. | 286 // Sort crumbs and remove duplicates. |
| 286 std::sort(out->begin() + prior_size, out->end()); | 287 std::sort(out->begin() + prior_size, out->end()); |
| 287 out->erase(std::unique(out->begin() + prior_size, out->end()), | 288 out->erase(std::unique(out->begin() + prior_size, out->end()), out->end()); |
| 288 out->end()); | |
| 289 } | 289 } |
| 290 | 290 |
| 291 } // namespace net | 291 } // namespace net |
| OLD | NEW |