net/spdy/hpack_encoder.cc

   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
   3 // found in the LICENSE file.
   4
   5 #include "net/spdy/hpack_encoder.h"
   6
   7 #include <algorithm>
   8
   9 #include "base/logging.h"
  10 #include "net/spdy/hpack_header_table.h"
  11 #include "net/spdy/hpack_huffman_table.h"
  12 #include "net/spdy/hpack_output_stream.h"
  13
  14 namespace net {
  15
  16 using base::StringPiece;
  17 using std::string;
  18
  19 HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
  20     : output_stream_(),
  21       allow_huffman_compression_(true),
  22       huffman_table_(table),
  23       char_counts_(NULL),
  24       total_char_counts_(NULL) {}
  25
  26 HpackEncoder::~HpackEncoder() {}
  27
  28 bool HpackEncoder::EncodeHeaderSet(const SpdyHeaderBlock& header_set,
  29                                    string* output) {
  30   // Separate header set into pseudo-headers and regular headers.
  31   Representations pseudo_headers;
  32   Representations regular_headers;
  33   for (const auto& header : header_set) {
  34     if (header.first == "cookie") {
  35       // Note that there can only be one "cookie" header, because header_set is
  36       // a map.
  37       CookieToCrumbs(header, &regular_headers);
  38     } else if (header.first[0] == kPseudoHeaderPrefix) {
  39       DecomposeRepresentation(header, &pseudo_headers);
  40     } else {
  41       DecomposeRepresentation(header, &regular_headers);
  42     }
  43   }
  44
  45   // Encode pseudo-headers.
  46   for (const auto& header : pseudo_headers) {
  47     const HpackEntry* entry =
  48         header_table_.GetByNameAndValue(header.first, header.second);
  49     if (entry != NULL) {
  50       EmitIndex(entry);
  51     } else {
  52       if (header.first == ":authority") {
  53         // :authority is always present and rarely changes, and has moderate
  54         // length, therefore it makes a lot of sense to index (insert in the
  55         // header table).
  56         EmitIndexedLiteral(header);
  57       } else {
  58         // Most common pseudo-header fields are represented in the static table,
  59         // while uncommon ones are small, so do not index them.
  60         EmitNonIndexedLiteral(header);
  61       }
  62     }
  63   }
  64
  65   // Encode regular headers.
  66   for (const auto& header : regular_headers) {
  67     const HpackEntry* entry =
  68         header_table_.GetByNameAndValue(header.first, header.second);
  69     if (entry != NULL) {
  70       EmitIndex(entry);
  71     } else {
  72       EmitIndexedLiteral(header);
  73     }
  74   }
  75
  76   output_stream_.TakeString(output);
  77   return true;
  78 }
  79
  80 bool HpackEncoder::EncodeHeaderSetWithoutCompression(
  81     const SpdyHeaderBlock& header_set,
  82     string* output) {
  83   allow_huffman_compression_ = false;
  84   for (const auto& header : header_set) {
  85     // Note that cookies are not crumbled in this case.
  86     EmitNonIndexedLiteral(header);
  87   }
  88   allow_huffman_compression_ = true;
  89   output_stream_.TakeString(output);
  90   return true;
  91 }
  92
  93 void HpackEncoder::EmitIndex(const HpackEntry* entry) {
  94   output_stream_.AppendPrefix(kIndexedOpcode);
  95   output_stream_.AppendUint32(header_table_.IndexOf(entry));
  96 }
  97
  98 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
  99   output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
 100   EmitLiteral(representation);
 101   header_table_.TryAddEntry(representation.first, representation.second);
 102 }
 103
 104 void HpackEncoder::EmitNonIndexedLiteral(
 105     const Representation& representation) {
 106   output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
 107   output_stream_.AppendUint32(0);
 108   EmitString(representation.first);
 109   EmitString(representation.second);
 110 }
 111
 112 void HpackEncoder::EmitLiteral(const Representation& representation) {
 113   const HpackEntry* name_entry = header_table_.GetByName(representation.first);
 114   if (name_entry != NULL) {
 115     output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
 116   } else {
 117     output_stream_.AppendUint32(0);
 118     EmitString(representation.first);
 119   }
 120   EmitString(representation.second);
 121 }
 122
 123 void HpackEncoder::EmitString(StringPiece str) {
 124   size_t encoded_size = (!allow_huffman_compression_ ? str.size()
 125                          : huffman_table_.EncodedSize(str));
 126   if (encoded_size < str.size()) {
 127     output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
 128     output_stream_.AppendUint32(encoded_size);
 129     huffman_table_.EncodeString(str, &output_stream_);
 130   } else {
 131     output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
 132     output_stream_.AppendUint32(str.size());
 133     output_stream_.AppendBytes(str);
 134   }
 135   UpdateCharacterCounts(str);
 136 }
 137
 138 void HpackEncoder::SetCharCountsStorage(std::vector<size_t>* char_counts,
 139                                         size_t* total_char_counts) {
 140   CHECK_LE(256u, char_counts->size());
 141   char_counts_ = char_counts;
 142   total_char_counts_ = total_char_counts;
 143 }
 144
 145 void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
 146   if (char_counts_ == NULL || total_char_counts_ == NULL) {
 147     return;
 148   }
 149   for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) {
 150     ++(*char_counts_)[static_cast<uint8>(*it)];
 151   }
 152   (*total_char_counts_) += str.size();
 153 }
 154
 155 // static
 156 void HpackEncoder::CookieToCrumbs(const Representation& cookie,
 157                                   Representations* out) {
 158   size_t prior_size = out->size();
 159
 160   // See Section 8.1.2.5. "Compressing the Cookie Header Field" in the HTTP/2
 161   // specification at https://tools.ietf.org/html/draft-ietf-httpbis-http2-14.
 162   // Cookie values are split into individually-encoded HPACK representations.
 163   for (size_t pos = 0;;) {
 164     size_t end = cookie.second.find(";", pos);
 165
 166     if (end == StringPiece::npos) {
 167       out->push_back(std::make_pair(cookie.first, cookie.second.substr(pos)));
 168       break;
 169     }
 170     out->push_back(
 171         std::make_pair(cookie.first, cookie.second.substr(pos, end - pos)));
 172
 173     // Consume next space if present.
 174     pos = end + 1;
 175     if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
 176       pos++;
 177     }
 178   }
 179   // Sort crumbs and remove duplicates.
 180   std::sort(out->begin() + prior_size, out->end());
 181   out->erase(std::unique(out->begin() + prior_size, out->end()),
 182              out->end());
 183 }
 184
 185 // static
 186 void HpackEncoder::DecomposeRepresentation(const Representation& header_field,
 187                                            Representations* out) {
 188   size_t pos = 0;
 189   size_t end = 0;
 190   while (end != StringPiece::npos) {
 191     end = header_field.second.find('\0', pos);
 192     out->push_back(std::make_pair(header_field.first,
 193                                   header_field.second.substr(pos, end - pos)));
 194     pos = end + 1;
 195   }
 196 }
 197
 198 }  // namespace net