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