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 namespace {
     20 
     21 const uint8 kNoState = 0;
     22 // Set on a referenced HpackEntry which is part of the current header set.
     23 const uint8 kReferencedImplicitOn = 1;
     24 // Set on a referenced HpackEntry which is not part of the current header set.
     25 const uint8 kReferencedExplicitOff = 2;
     26 // Set on a entries added to the reference set during this encoding.
     27 const uint8 kReferencedThisEncoding = 3;
     28 
     29 }  // namespace
     30 
     31 HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
     32     : output_stream_(),
     33       allow_huffman_compression_(true),
     34       huffman_table_(table),
     35       char_counts_(NULL),
     36       total_char_counts_(NULL) {}
     37 
     38 HpackEncoder::~HpackEncoder() {}
     39 
     40 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
     41                                    string* output) {
     42   // 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.
     44   Representations explicit_set(DetermineEncodingDelta(header_set));
     45   for (Representations::const_iterator it = explicit_set.begin();
     46        it != explicit_set.end(); ++it) {
     47     // Try to find an exact match. Note that dynamic entries are preferred
     48     // by the header table index.
     49     HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second);
     50     if (entry != NULL && !entry->IsStatic()) {
     51       // Already in the dynamic table. Simply toggle on.
     52       CHECK_EQ(kNoState, entry->state());
     53       EmitDynamicIndex(entry);
     54       continue;
     55     }
     56 
     57     // Walk the set of entries to be evicted by this insertion.
     58     HpackHeaderTable::EntryTable::iterator evict_begin, evict_end, evict_it;
     59     header_table_.EvictionSet(it->first, it->second, &evict_begin, &evict_end);
     60 
     61     for (evict_it = evict_begin; evict_it != evict_end; ++evict_it) {
     62       HpackEntry* evictee = &(*evict_it);
     63 
     64       if (evict_it->state() == kReferencedImplicitOn) {
     65         // Issue twice to explicitly emit.
     66         EmitDynamicIndex(evictee);
     67         EmitDynamicIndex(evictee);
     68       } else if (evictee->state() == kReferencedExplicitOff) {
     69         // Eviction saves us from having to explicitly toggle off.
     70         evictee->set_state(kNoState);
     71       } else if (evictee->state() == kReferencedThisEncoding) {
     72         // Already emitted. No action required.
     73         evictee->set_state(kNoState);
     74       }
     75     }
     76     if (entry != NULL) {
     77       EmitStaticIndex(entry);
     78     } else {
     79       EmitIndexedLiteral(*it);
     80     }
     81   }
     82   // Walk the reference set, toggling off as needed and clearing encoding state.
     83   for (HpackHeaderTable::OrderedEntrySet::const_iterator it =
     84            header_table_.reference_set().begin();
     85        it != header_table_.reference_set().end();) {
     86     HpackEntry* entry = *(it++);  // Step to prevent invalidation.
     87     CHECK_NE(kNoState, entry->state());
     88 
     89     if (entry->state() == kReferencedExplicitOff) {
     90       // Explicitly toggle off.
     91       EmitDynamicIndex(entry);
     92     }
     93     entry->set_state(kNoState);
     94   }
     95   output_stream_.TakeString(output);
     96   return true;
     97 }
     98 
     99 bool HpackEncoder::EncodeHeaderSetWithoutCompression(
    100     const std::map<string, string>& header_set,
    101     string* output) {
    102 
    103   allow_huffman_compression_ = false;
    104   for (std::map<string, string>::const_iterator it = header_set.begin();
    105        it != header_set.end(); ++it) {
    106     // Note that cookies are not crumbled in this case.
    107     EmitNonIndexedLiteral(*it);
    108   }
    109   allow_huffman_compression_ = true;
    110   output_stream_.TakeString(output);
    111   return true;
    112 }
    113 
    114 void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) {
    115   DCHECK(!entry->IsStatic());
    116   output_stream_.AppendPrefix(kIndexedOpcode);
    117   output_stream_.AppendUint32(header_table_.IndexOf(entry));
    118 
    119   entry->set_state(kNoState);
    120   if (header_table_.Toggle(entry)) {
    121     // Was added to the reference set.
    122     entry->set_state(kReferencedThisEncoding);
    123   }
    124 }
    125 
    126 void HpackEncoder::EmitStaticIndex(HpackEntry* entry) {
    127   DCHECK(entry->IsStatic());
    128   output_stream_.AppendPrefix(kIndexedOpcode);
    129   output_stream_.AppendUint32(header_table_.IndexOf(entry));
    130 
    131   HpackEntry* new_entry = header_table_.TryAddEntry(entry->name(),
    132                                                     entry->value());
    133   if (new_entry) {
    134     // This is a static entry: no need to pin.
    135     header_table_.Toggle(new_entry);
    136     new_entry->set_state(kReferencedThisEncoding);
    137   }
    138 }
    139 
    140 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
    141   output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
    142   EmitLiteral(representation);
    143 
    144   HpackEntry* new_entry = header_table_.TryAddEntry(representation.first,
    145                                                     representation.second);
    146   if (new_entry) {
    147     header_table_.Toggle(new_entry);
    148     new_entry->set_state(kReferencedThisEncoding);
    149   }
    150 }
    151 
    152 void HpackEncoder::EmitNonIndexedLiteral(
    153     const Representation& representation) {
    154   output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
    155   output_stream_.AppendUint32(0);
    156   EmitString(representation.first);
    157   EmitString(representation.second);
    158 }
    159 
    160 void HpackEncoder::EmitLiteral(const Representation& representation) {
    161   const HpackEntry* name_entry = header_table_.GetByName(representation.first);
    162   if (name_entry != NULL) {
    163     output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
    164   } else {
    165     output_stream_.AppendUint32(0);
    166     EmitString(representation.first);
    167   }
    168   EmitString(representation.second);
    169 }
    170 
    171 void HpackEncoder::EmitString(StringPiece str) {
    172   size_t encoded_size = (!allow_huffman_compression_ ? str.size()
    173                          : huffman_table_.EncodedSize(str));
    174   if (encoded_size < str.size()) {
    175     output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
    176     output_stream_.AppendUint32(encoded_size);
    177     huffman_table_.EncodeString(str, &output_stream_);
    178   } else {
    179     output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
    180     output_stream_.AppendUint32(str.size());
    181     output_stream_.AppendBytes(str);
    182   }
    183   UpdateCharacterCounts(str);
    184 }
    185 
    186 // static
    187 HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta(
    188     const std::map<string, string>& header_set) {
    189   // Flatten & crumble headers into an ordered list of representations.
    190   Representations full_set;
    191   for (std::map<string, string>::const_iterator it = header_set.begin();
    192        it != header_set.end(); ++it) {
    193     if (it->first == "cookie") {
    194       // |CookieToCrumbs()| produces ordered crumbs.
    195       CookieToCrumbs(*it, &full_set);
    196     } else {
    197       // Note std::map guarantees representations are ordered.
    198       full_set.push_back(make_pair(
    199           StringPiece(it->first), StringPiece(it->second)));
    200     }
    201   }
    202   // Perform a linear merge of ordered representations with the (also ordered)
    203   // reference set. Mark each referenced entry with current membership state,
    204   // and gather representations which must be explicitly emitted.
    205   Representations::const_iterator r_it = full_set.begin();
    206   HpackHeaderTable::OrderedEntrySet::const_iterator s_it =
    207       header_table_.reference_set().begin();
    208 
    209   Representations explicit_set;
    210   while (r_it != full_set.end() &&
    211          s_it != header_table_.reference_set().end()) {
    212     // Compare on name, then value.
    213     int result = r_it->first.compare((*s_it)->name());
    214     if (result == 0) {
    215       result = r_it->second.compare((*s_it)->value());
    216     }
    217 
    218     if (result < 0) {
    219       explicit_set.push_back(*r_it);
    220       ++r_it;
    221     } else if (result > 0) {
    222       (*s_it)->set_state(kReferencedExplicitOff);
    223       ++s_it;
    224     } else {
    225       (*s_it)->set_state(kReferencedImplicitOn);
    226       ++s_it;
    227       ++r_it;
    228     }
    229   }
    230   while (r_it != full_set.end()) {
    231     explicit_set.push_back(*r_it);
    232     ++r_it;
    233   }
    234   while (s_it != header_table_.reference_set().end()) {
    235     (*s_it)->set_state(kReferencedExplicitOff);
    236     ++s_it;
    237   }
    238   return explicit_set;
    239 }
    240 
    241 void HpackEncoder::SetCharCountsStorage(std::vector<size_t>* char_counts,
    242                                         size_t* total_char_counts) {
    243   CHECK_LE(256u, char_counts->size());
    244   char_counts_ = char_counts;
    245   total_char_counts_ = total_char_counts;
    246 }
    247 
    248 void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
    249   if (char_counts_ == NULL || total_char_counts_ == NULL) {
    250     return;
    251   }
    252   for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) {
    253     ++(*char_counts_)[static_cast<uint8>(*it)];
    254   }
    255   (*total_char_counts_) += str.size();
    256 }
    257 
    258 // static
    259 void HpackEncoder::CookieToCrumbs(const Representation& cookie,
    260                                   Representations* out) {
    261   size_t prior_size = out->size();
    262 
    263   // 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
    265   // Cookie values are split into individually-encoded HPACK representations.
    266   for (size_t pos = 0;;) {
    267     size_t end = cookie.second.find(";", pos);
    268 
    269     if (end == StringPiece::npos) {
    270       out->push_back(make_pair(
    271           cookie.first,
    272           cookie.second.substr(pos)));
    273       break;
    274     }
    275     out->push_back(make_pair(
    276         cookie.first,
    277         cookie.second.substr(pos, end - pos)));
    278 
    279     // Consume next space if present.
    280     pos = end + 1;
    281     if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
    282       pos++;
    283     }
    284   }
    285   // Sort crumbs and remove duplicates.
    286   std::sort(out->begin() + prior_size, out->end());
    287   out->erase(std::unique(out->begin() + prior_size, out->end()),
    288              out->end());
    289 }
    290 
    291 }  // namespace net
    292