Home | History | Annotate | Download | only in spdy 
      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
    217