HPACK: Implement delta encoding.

net/spdy/hpack_encoder.cc

Index: net/spdy/hpack_encoder.cc
diff --git a/net/spdy/hpack_encoder.cc b/net/spdy/hpack_encoder.cc
index c9f6506529d992a8d0d587832195b3eed045e727..81d33ad171d38aaaaee3058cb3df5593b20f230c 100644
--- a/net/spdy/hpack_encoder.cc
+++ b/net/spdy/hpack_encoder.cc
@@ -4,7 +4,11 @@
 
 #include "net/spdy/hpack_encoder.h"
 
-#include "base/strings/string_util.h"
+#include <algorithm>
+
+#include "base/logging.h"
+#include "net/spdy/hpack_header_table.h"
+#include "net/spdy/hpack_huffman_table.h"
 #include "net/spdy/hpack_output_stream.h"
 
 namespace net {
@@ -12,61 +16,249 @@ namespace net {
 using base::StringPiece;
 using std::string;
 
-HpackEncoder::HpackEncoder()
-    : max_string_literal_size_(kDefaultMaxStringLiteralSize) {}
+namespace {
+
+const uint8 kNoState = 0;
+// Set on a referenced HpackEntry which is part of the current header set.
+const uint8 kReferencedImplicitOn = 1;
+// Set on a referenced HpackEntry which is not part of the current header set.
+const uint8 kReferencedExplicitOff = 2;
+// Set on a entries added to the reference set during this encoding.
+const uint8 kReferencedThisEncoding = 3;
+
+}  // namespace
+
+HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
+    : output_stream_(),
+      allow_huffman_compression_(true),
+      huffman_table_(table) {}
 
 HpackEncoder::~HpackEncoder() {}
 
 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
                                    string* output) {
-  // TOOD(jgraettinger): Do more sophisticated encoding.
-  HpackOutputStream output_stream;
-  for (std::map<string, string>::const_iterator it = header_set.begin();
-       it != header_set.end(); ++it) {
-    // TODO(jgraettinger): HTTP/2 requires strict lowercasing of headers,
-    // and the permissiveness here isn't wanted. Back this out in upstream.
-    if (LowerCaseEqualsASCII(it->first, "cookie")) {
-      std::vector<StringPiece> crumbs;
-      CookieToCrumbs(it->second, &crumbs);
-      for (size_t i = 0; i != crumbs.size(); i++) {
-        EmitNonIndexedLiteral(it->first, crumbs[i], &output_stream);
+  // Walk the set of entries to encode, which are not already implied by the
+  // header table's reference set. They must be explicitly emitted.
+  Representations explicit_set(DetermineEncodingDelta(header_set));
+  for (Representations::const_iterator it = explicit_set.begin();
+       it != explicit_set.end(); ++it) {
+    // Try to find an exact match. Note that dynamic entries are preferred
+    // by the header table index.
+    HpackEntry* entry = header_table_.GetByNameAndValue(it->first, it->second);
+    if (entry != NULL && !entry->IsStatic()) {
+      // Already in the dynamic table. Simply toggle on.
+      CHECK_EQ(kNoState, entry->state());
+      EmitDynamicIndex(entry);
+      continue;
+    }
+
+    // Walk the set of entries to be evicted by this insertion.
+    HpackHeaderTable::EntryTable::iterator evict_begin, evict_end, evict_it;
+    header_table_.EvictionSet(it->first, it->second, &evict_begin, &evict_end);
+
+    for (evict_it = evict_begin; evict_it != evict_end; ++evict_it) {
+      HpackEntry* evictee = &(*evict_it);
+
+      if (evict_it->state() == kReferencedImplicitOn) {
+        // Issue twice to explicitly emit.
+        EmitDynamicIndex(evictee);
+        EmitDynamicIndex(evictee);
+      } else if (evictee->state() == kReferencedExplicitOff) {
+        // Eviction saves us from having to explicitly toggle off.
+        evictee->set_state(kNoState);
+      } else if (evictee->state() == kReferencedThisEncoding) {
+        // Already emitted. No action required.
+        evictee->set_state(kNoState);
       }
+    }
+    if (entry != NULL) {
+      EmitStaticIndex(entry);
     } else {
-      EmitNonIndexedLiteral(it->first, it->second, &output_stream);
+      EmitIndexedLiteral(*it);
+    }
+  }
+  // Walk the reference set, toggling off as needed and clearing encoding state.
+  for (HpackEntry::OrderedSet::const_iterator it =
+          header_table_.reference_set().begin();
+       it != header_table_.reference_set().end();) {
+    HpackEntry* entry = *(it++);  // Step to prevent invalidation.
+    CHECK_NE(kNoState, entry->state());
+
+    if (entry->state() == kReferencedExplicitOff) {
+      // Explicitly toggle off.
+      EmitDynamicIndex(entry);
     }
+    entry->set_state(kNoState);
   }
-  output_stream.TakeString(output);
+  output_stream_.TakeString(output);
   return true;
 }
 
-void HpackEncoder::EmitNonIndexedLiteral(StringPiece name,
-                                         StringPiece value,
-                                         HpackOutputStream* output_stream) {
-  output_stream->AppendPrefix(kLiteralNoIndexOpcode);
-  output_stream->AppendUint32(0u);
-  output_stream->AppendPrefix(kStringLiteralIdentityEncoded);
-  output_stream->AppendUint32(name.size());
-  output_stream->AppendBytes(name);
-  output_stream->AppendPrefix(kStringLiteralIdentityEncoded);
-  output_stream->AppendUint32(value.size());
-  output_stream->AppendBytes(value);
+bool HpackEncoder::EncodeHeaderSetWithoutCompression(
+    const std::map<string, string>& header_set,
+    string* output) {
+
+  allow_huffman_compression_ = false;
+  for (std::map<string, string>::const_iterator it = header_set.begin();
+       it != header_set.end(); ++it) {
+    // Note that cookies are not crumbled in this case.
+    EmitNonIndexedLiteral(*it);
+  }
+  allow_huffman_compression_ = true;
+  output_stream_.TakeString(output);
+  return true;
+}
+
+void HpackEncoder::EmitDynamicIndex(HpackEntry* entry) {
+  DCHECK(!entry->IsStatic());
+  output_stream_.AppendPrefix(kIndexedOpcode);
+  output_stream_.AppendUint32(entry->Index());
+
+  entry->set_state(kNoState);
+  if (header_table_.Toggle(entry)) {
+    // Was added to the reference set.
+    entry->set_state(kReferencedThisEncoding);
+  }
+}
+
+void HpackEncoder::EmitStaticIndex(HpackEntry* entry) {
+  DCHECK(entry->IsStatic());
+  output_stream_.AppendPrefix(kIndexedOpcode);
+  output_stream_.AppendUint32(entry->Index());
+
+  HpackEntry* new_entry = header_table_.TryAddEntry(entry->name(),
+                                                    entry->value());
+  if (new_entry) {
+    // This is a static entry: no need to pin.
+    header_table_.Toggle(new_entry);
+    new_entry->set_state(kReferencedThisEncoding);
+  }
+}
+
+void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
+  output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
+  EmitLiteral(representation);
+
+  HpackEntry* new_entry = header_table_.TryAddEntry(representation.first,
+                                                    representation.second);
+  if (new_entry) {
+    header_table_.Toggle(new_entry);
+    new_entry->set_state(kReferencedThisEncoding);
+  }
+}
+
+void HpackEncoder::EmitNonIndexedLiteral(
+    const Representation& representation) {
+  output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
+  output_stream_.AppendUint32(0);
+  EmitString(representation.first);
+  EmitString(representation.second);
+}
+
+void HpackEncoder::EmitLiteral(const Representation& representation) {
+  const HpackEntry* name_entry = header_table_.GetByName(representation.first);
+  if (name_entry != NULL) {
+    output_stream_.AppendUint32(name_entry->Index());
+  } else {
+    output_stream_.AppendUint32(0);
+    EmitString(representation.first);
+  }
+  EmitString(representation.second);
+}
+
+void HpackEncoder::EmitString(StringPiece str) {
+  size_t encoded_size = (!allow_huffman_compression_ ? str.size()
+                         : huffman_table_.EncodedSize(str));
+  if (encoded_size < str.size()) {
+    output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
+    output_stream_.AppendUint32(encoded_size);
+    huffman_table_.EncodeString(str, &output_stream_);
+  } else {
+    output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
+    output_stream_.AppendUint32(str.size());
+    output_stream_.AppendBytes(str);
+  }
+}
+
+// static
+HpackEncoder::Representations HpackEncoder::DetermineEncodingDelta(
+    const std::map<string, string>& header_set) {
+  // Flatten & crumble headers into an ordered list of representations.
+  Representations full_set;
+  for (std::map<string, string>::const_iterator it = header_set.begin();
+       it != header_set.end(); ++it) {
+    if (it->first == "cookie") {
+      // Crumble cookie, and sort the result crumbs.
+      size_t sort_offset = full_set.size();
+      CookieToCrumbs(*it, &full_set);
+      std::sort(full_set.begin() + sort_offset, full_set.end());
+    } else {
+      // Note std::map guarantees representations are ordered.
+      full_set.push_back(make_pair(
+          StringPiece(it->first), StringPiece(it->second)));
+    }
+  }
+  // Perform a linear merge of ordered representations with the (also ordered)
+  // reference set. Mark each referenced entry with current membership state,
+  // and gather representations which must be explicitly emitted.
+  Representations::const_iterator r_it = full_set.begin();
+  HpackEntry::OrderedSet::const_iterator s_it =
+      header_table_.reference_set().begin();
+
+  Representations explicit_set;
+  while (r_it != full_set.end() &&
+         s_it != header_table_.reference_set().end()) {
+    // Compare on name, then value.
+    int result = r_it->first.compare((*s_it)->name());
+    if (result == 0) {
+      result = r_it->second.compare((*s_it)->value());
+    }
+
+    if (result < 0) {
+      explicit_set.push_back(*r_it);
+      ++r_it;
+    } else if (result > 0) {
+      (*s_it)->set_state(kReferencedExplicitOff);
+      ++s_it;
+    } else {
+      (*s_it)->set_state(kReferencedImplicitOn);
+      ++s_it;
+      ++r_it;
+    }
+  }
+  while (r_it != full_set.end()) {
+    explicit_set.push_back(*r_it);
+    ++r_it;
+  }
+  while (s_it != header_table_.reference_set().end()) {
+    (*s_it)->set_state(kReferencedExplicitOff);
+    ++s_it;
+  }
+  return explicit_set;
 }
 
-void HpackEncoder::CookieToCrumbs(StringPiece cookie,
-                                  std::vector<StringPiece>* out) {
-  out->clear();
+// static
+void HpackEncoder::CookieToCrumbs(const Representation& cookie,
+                                  Representations* out) {
+  // See Section 8.1.3.4 "Compressing the Cookie Header Field" in the HTTP/2
+  // specification at http://tools.ietf.org/html/draft-ietf-httpbis-http2-11
+  // Cookie values are split into individually-encoded HPACK representations.
   for (size_t pos = 0;;) {
-    size_t end = cookie.find(';', pos);
+    size_t end = cookie.second.find(";", pos);
 
     if (end == StringPiece::npos) {
-      out->push_back(cookie.substr(pos));
+      out->push_back(make_pair(
+          cookie.first,
+          cookie.second.substr(pos)));
       return;
     }
-    out->push_back(cookie.substr(pos, end - pos));
+    out->push_back(make_pair(
+        cookie.first,
+        cookie.second.substr(pos, end - pos)));
 
     // Consume next space if present.
     pos = end + 1;
-    if (pos != cookie.size() && cookie[pos] == ' ') {
+    if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
       pos++;
     }
   }