DO NOT COMMIT: Implement HPACK (draft 03)

net/spdy/http2_encoding_context.cc

Index: net/spdy/http2_encoding_context.cc
diff --git a/net/spdy/http2_encoding_context.cc b/net/spdy/http2_encoding_context.cc
new file mode 100644
index 0000000000000000000000000000000000000000..993c924ed07aaddab66f7d65542f98afc5f578f0
--- /dev/null
+++ b/net/spdy/http2_encoding_context.cc
@@ -0,0 +1,379 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "net/spdy/http2_encoding_context.h"
+
+#include "base/logging.h"
+
+namespace net {
+
+const uint8 kIndexOpcode = 0x1;
+const uint8 kIndexN = 7;
+
+const uint8 kLiteralNoIndexOpcode = 0x3;
+const uint8 kLiteralNoIndexN= 5;
+
+const uint8 kLiteralIncrementalOpcode = 0x2;
+const uint8 kLiteralIncrementalN = 5;
+
+const uint8 kLiteralSubstitutionOpcode = 0x0;
+const uint8 kLiteralSubstitutionN = 6;
+
+const uint32 kUntouched = kuint32max;
+
+namespace {
+
+const char* kPreDefinedRequestHeaderTable[][2] = {
+  { ":scheme",             "http"  },  // 0
+  { ":scheme",             "https" },  // 1
+  { ":host",               ""      },  // 2
+  { ":path",               "/"     },  // 3
+  { ":method",             "GET"   },  // 4
+  { "accept",              ""      },  // 5
+  { "accept-charset",      ""      },  // 6
+  { "accept-encoding",     ""      },  // 7
+  { "accept-language",     ""      },  // 8
+  { "cookie",              ""      },  // 9
+  { "if-modified-since",   ""      },  // 10
+  { "user-agent",          ""      },  // 11
+  { "referer",             ""      },  // 12
+  { "authorization",       ""      },  // 13
+  { "allow",               ""      },  // 14
+  { "cache-control",       ""      },  // 15
+  { "connection",          ""      },  // 16
+  { "content-length",      ""      },  // 17
+  { "content-type",        ""      },  // 18
+  { "date",                ""      },  // 19
+  { "expect",              ""      },  // 20
+  { "from",                ""      },  // 21
+  { "if-match",            ""      },  // 22
+  { "if-none-match",       ""      },  // 23
+  { "if-range",            ""      },  // 24
+  { "if-unmodified-since", ""      },  // 25
+  { "max-forwards",        ""      },  // 26
+  { "proxy-authorization", ""      },  // 27
+  { "range",               ""      },  // 28
+  { "via",                 ""      }   // 29
+};
+
+const char* kPreDefinedResponseHeaderTable[][2] = {
+  { ":status",                     "200" },  // 0
+  { "age",                         ""    },  // 1
+  { "cache-control",               ""    },  // 2
+  { "content-length",              ""    },  // 3
+  { "content-type",                ""    },  // 4
+  { "date",                        ""    },  // 5
+  { "etag",                        ""    },  // 6
+  { "expires",                     ""    },  // 7
+  { "last-modified",               ""    },  // 8
+  { "server",                      ""    },  // 9
+  { "set-cookie",                  ""    },  // 10
+  { "vary",                        ""    },  // 11
+  { "via",                         ""    },  // 12
+  { "access-control-allow-origin", ""    },  // 13
+  { "accept-ranges",               ""    },  // 14
+  { "allow",                       ""    },  // 15
+  { "connection",                  ""    },  // 16
+  { "content-disposition",         ""    },  // 17
+  { "content-encoding",            ""    },  // 18
+  { "content-language",            ""    },  // 19
+  { "content-location",            ""    },  // 20
+  { "content-range",               ""    },  // 21
+  { "link",                        ""    },  // 22
+  { "location",                    ""    },  // 23
+  { "proxy-authenticate",          ""    },  // 24
+  { "refresh",                     ""    },  // 25
+  { "retry-after",                 ""    },  // 26
+  { "strict-transport-security",   ""    },  // 27
+  { "transfer-encoding",           ""    },  // 28
+  { "www-authenticate",            ""    },  // 29
+};
+
+}  // namespace
+
+bool IsValidHeaderName(const std::string& str) {
+  size_t start = (str.empty() || str[0] != ':') ? 0 : 1;
+
+  if (start == str.size())
+    return false;
+
+  for (size_t i = start; i < str.size(); ++i) {
+    switch (str[i]) {
+      case '!':
+      case '#':
+      case '$':
+      case '%':
+      case '&':
+      case '\'':
+
+      case '*':
+      case '+':
+      case '-':
+      case '.':
+      case '^':
+      case '_':
+
+      case '`':
+      case '|':
+      case '~':
+        break;
+
+      default:
+        if (str[i] >= '0' && str[i] <= '9')
+          break;
+
+        if (str[i] >= 'a' && str[i] <= 'z')
+          break;
+
+        return false;
+    }
+  }
+
+  return true;
+}
+
+bool IsValidHeaderValue(const std::string& str) {
+  return true;
+}
+
+bool StringsEqualConstantTime(const std::string& str1,
+                              const std::string& str2) {
+  size_t size = str1.size();
+  if (str2.size() != size)
+    return false;
+
+  uint8 x = 0;
+  for (size_t i = 0; i < size; ++i) {
+    x |= str1[i] ^ str2[i];
+  }
+  return x == 0;
+}
+
+HeaderTableEntry::HeaderTableEntry()
+    : referenced(false),
+      touch_count(kUntouched) {}
+
+HeaderTableEntry::HeaderTableEntry(const std::string& name,
+                                   const std::string& value)
+    : name(name),
+      value(value),
+      referenced(false),
+      touch_count(kUntouched) {}
+
+bool HeaderTableEntry::Equals(const HeaderTableEntry& other) const {
+  return
+      StringsEqualConstantTime(name, other.name) &&
+      StringsEqualConstantTime(value, other.value) &&
+      (referenced == other.referenced) &&
+      (touch_count == other.touch_count);
+}
+
+size_t HeaderTableEntry::Size() const {
+  return name.size() + value.size() + 32;
+}
+
+HeaderTable::HeaderTable() : size_(0), max_size_(4096) {}
+
+HeaderTable::~HeaderTable() {}
+
+size_t HeaderTable::GetEntryCount() const {
+  return entries_.size();
+}
+
+void HeaderTable::SetMaxSize(size_t max_size) {
+  max_size_ = max_size;
+  while (size_ > max_size_) {
+    RemoveFirstEntry();
+  }
+}
+
+const HeaderTableEntry* HeaderTable::GetEntry(int32 index) const {
+  DCHECK_GE(index, 0);
+  DCHECK_LT(static_cast<size_t>(index), entries_.size());
+  return &entries_[index];
+}
+
+HeaderTableEntry* HeaderTable::GetMutableEntry(int32 index) {
+  DCHECK_GE(index, 0);
+  DCHECK_LT(static_cast<size_t>(index), entries_.size());
+  return &entries_[index];
+}
+
+void HeaderTable::TryAppendEntry(
+    const HeaderTableEntry& entry,
+    int32* index,
+    std::vector<uint32>* removed_referenced_indices) {
+  DCHECK(IsValidHeaderName(entry.name));
+  DCHECK(IsValidHeaderValue(entry.value));
+
+  *index = -1;
+  removed_referenced_indices->clear();
+
+  size_t size_delta = entry.Size();
+  size_t num_to_shift = 0;
+  size_t size_after_shift = size_;
+  while ((num_to_shift < entries_.size()) &&
+         (size_after_shift + size_delta) > max_size_) {
+    size_after_shift -= entries_[num_to_shift].Size();
+    ++num_to_shift;
+  }
+
+  for (size_t i = 0; i < num_to_shift; ++i) {
+    if (entries_[i].referenced) {
+      removed_referenced_indices->push_back(i);
+    }
+  }
+
+  entries_.erase(entries_.begin(), entries_.begin() + num_to_shift);
+  size_ = size_after_shift;
+  if ((size_ + size_delta) <= max_size_) {
+    size_ += size_delta;
+    *index = entries_.size();
+    entries_.push_back(entry);
+  }
+}
+
+void HeaderTable::TryReplaceEntry(
+    uint32 substituted_index,
+    const HeaderTableEntry& entry,
+    int32* index,
+    std::vector<uint32>* removed_referenced_indices) {
+  DCHECK(IsValidHeaderName(entry.name));
+  DCHECK(IsValidHeaderValue(entry.value));
+
+  *index = substituted_index;
+  removed_referenced_indices->clear();
+
+  size_t size_delta = entry.Size() - GetEntry(*index)->Size();
+  size_t num_to_shift = 0;
+  size_t size_after_shift = size_;
+  while ((num_to_shift < entries_.size()) &&
+         (size_after_shift + size_delta) > max_size_) {
+    size_after_shift -= entries_[num_to_shift].Size();
+    ++num_to_shift;
+    if (num_to_shift >= static_cast<size_t>(*index)) {
+      size_delta = entry.Size();
+    }
+  }
+
+  for (size_t i = 0; i < num_to_shift; ++i) {
+    if (entries_[i].referenced) {
+      removed_referenced_indices->push_back(i);
+    }
+  }
+
+  entries_.erase(entries_.begin(), entries_.begin() + num_to_shift);
+  *index -= num_to_shift;
+  size_ = size_after_shift;
+  if ((size_ + size_delta) <= max_size_) {
+    size_ += size_delta;
+    if (*index >= 0) {
+      entries_[*index] = entry;
+    } else {
+      *index = 0;
+      entries_.push_front(entry);
+    }
+  } else {
+    *index = -1;
+  }
+}
+
+void HeaderTable::RemoveFirstEntry() {
+  DCHECK(!entries_.empty());
+  size_ -= entries_.front().Size();
+  entries_.pop_front();
+}
+
+EncodingContext::EncodingContext(Http2Direction direction) {
+  const char* (*initial_header_table)[2] = NULL;
+  size_t initial_header_table_size = 0;
+  switch (direction) {
+    case HTTP2_REQUEST:
+      initial_header_table = kPreDefinedRequestHeaderTable;
+      initial_header_table_size = arraysize(kPreDefinedRequestHeaderTable);
+    case HTTP2_RESPONSE:
+      initial_header_table = kPreDefinedResponseHeaderTable;
+      initial_header_table_size = arraysize(kPreDefinedResponseHeaderTable);
+  }
+  DCHECK(initial_header_table);
+  DCHECK_GT(initial_header_table_size, 0u);
+
+  for (size_t i = 0; i < initial_header_table_size; ++i) {
+    int32 index = 0;
+    std::vector<uint32> removed_referenced_indices;
+    header_table_.TryAppendEntry(
+        HeaderTableEntry(initial_header_table[i][0],
+                         initial_header_table[i][1]),
+        &index,
+        &removed_referenced_indices);
+    DCHECK_GE(index, 0);
+    DCHECK(removed_referenced_indices.empty());
+  }
+}
+
+EncodingContext::~EncodingContext() {}
+
+size_t EncodingContext::GetEntryCount() const {
+  return header_table_.GetEntryCount();
+}
+
+bool EncodingContext::IsReferenced(uint32 index) const {
+  return header_table_.GetEntry(index)->referenced;
+}
+
+bool EncodingContext::GetIndexedHeaderName(uint32 index,
+                                           std::string* name) const {
+  *name = header_table_.GetEntry(index)->name;
+  return true;
+}
+
+bool EncodingContext::GetIndexedHeaderValue(uint32 index,
+                                            std::string* value) const {
+  *value = header_table_.GetEntry(index)->value;
+  return true;
+}
+
+void EncodingContext::ProcessIndexedHeader(uint32 index) {
+  HeaderTableEntry* entry = header_table_.GetMutableEntry(index);
+  entry->referenced = !entry->referenced;
+}
+
+void EncodingContext::ProcessLiteralHeaderWithIncrementalIndexing(
+    const std::string& name,
+    const std::string& value,
+    int32* index,
+    std::vector<uint32>* removed_referenced_indices) {
+  header_table_.TryAppendEntry(HeaderTableEntry(name, value),
+                               index, removed_referenced_indices);
+  if (*index >= 0) {
+    header_table_.GetMutableEntry(*index)->referenced = true;
+  }
+}
+
+void EncodingContext::ProcessLiteralHeaderWithSubstitutionIndexing(
+    const std::string& name,
+    uint32 substituted_index,
+    const std::string& value,
+    int32* index,
+    std::vector<uint32>* removed_referenced_indices) {
+  header_table_.TryReplaceEntry(substituted_index,
+                                HeaderTableEntry(name, value),
+                                index, removed_referenced_indices);
+  if (*index >= 0) {
+    header_table_.GetMutableEntry(*index)->referenced = true;
+  }
+}
+
+void EncodingContext::AddTouches(uint32 index, uint32 touch_count) {
+  HeaderTableEntry* entry = header_table_.GetMutableEntry(index);
+  if (entry->touch_count == kUntouched)
+    entry->touch_count = 0;
+  entry->touch_count += touch_count;
+}
+
+HeaderTableEntry* EncodingContext::GetMutableEntry(int32 index) {
+  return header_table_.GetMutableEntry(index);
+}
+
+}  // namespace net