DO NOT COMMIT: Implement HPACK (draft 03)

net/spdy/http2_decompressor.cc

Index: net/spdy/http2_decompressor.cc
diff --git a/net/spdy/http2_decompressor.cc b/net/spdy/http2_decompressor.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c431f6e878ad074d3e8a7cbef3e8f24482876731
--- /dev/null
+++ b/net/spdy/http2_decompressor.cc
@@ -0,0 +1,272 @@
+// 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_decompressor.h"
+
+#include <cstddef>
+
+#include "base/logging.h"
+
+namespace net {
+
+namespace {
+
+class Http2Decoder {
+ public:
+  Http2Decoder(const char* buffer,
+               size_t buffer_size,
+               EncodingContext* encoding_context,
+               SpdyNameValueBlock* out);
+
+  bool HasMoreData() const;
+
+  void EmitHeader(const std::string& name, const std::string& value);
+
+  bool ProcessNextHeaderRepresentation();
+
+ private:
+  bool PeekNextOctet(uint8* next_octet);
+
+  bool DecodeNextOctet(uint8* next_octet);
+
+  bool DecodeNextInteger(uint8 N, uint32* I);
+
+  bool DecodeNextOctetSequence(std::string* str);
+
+  bool DecodeNextName(uint8 N, std::string* next_name);
+
+  bool DecodeNextValue(std::string* next_value);
+
+  const char* const buffer_;
+  const size_t buffer_size_;
+  EncodingContext* const encoding_context_;
+  SpdyNameValueBlock* out_;
+  size_t i_;
+
+  DISALLOW_COPY_AND_ASSIGN(Http2Decoder);
+};
+
+Http2Decoder::Http2Decoder(const char* buffer,
+                           size_t buffer_size,
+                           EncodingContext* encoding_context,
+                           SpdyNameValueBlock* out)
+    : buffer_(buffer),
+      buffer_size_(buffer_size),
+      encoding_context_(encoding_context),
+      out_(out),
+      i_(0) {}
+
+bool Http2Decoder::HasMoreData() const {
+  return i_ < buffer_size_;
+}
+
+void Http2Decoder::EmitHeader(const std::string& name,
+                              const std::string& value) {
+  VLOG(1) << "Emitting " << name << " " << value;
+  if (out_->find(name) == out_->end()) {
+    (*out_)[name] = value;
+  } else {
+    std::string new_value = (*out_)[name];
+    new_value.append(1, '\0');  // +=() doesn't append 0's
+    new_value += value;
+    (*out_)[name] = new_value;
+  }
+}
+
+bool Http2Decoder::ProcessNextHeaderRepresentation() {
+  uint8 next_octet = 0;
+  if (!PeekNextOctet(&next_octet))
+    return false;
+
+  if ((next_octet >> kIndexN) == kIndexOpcode) {
+    uint32 index = 0;
+    DecodeNextInteger(7, &index);
+    encoding_context_->ProcessIndexedHeader(index);
+    if (!encoding_context_->IsReferenced(index)) {
+      return true;
+    }
+    encoding_context_->AddTouches(index, 0);
+    std::string name;
+    if (!encoding_context_->GetIndexedHeaderName(index, &name)) {
+      return false;
+    }
+    std::string value;
+    if (!encoding_context_->GetIndexedHeaderValue(index, &value)) {
+      return false;
+    }
+    EmitHeader(name, value);
+    return true;
+  }
+
+  if ((next_octet >> kLiteralNoIndexN) == kLiteralNoIndexOpcode) {
+    std::string name;
+    if (!DecodeNextName(kLiteralNoIndexN, &name))
+      return false;
+    std::string value;
+    if (!DecodeNextValue(&value))
+      return false;
+    EmitHeader(name, value);
+    return true;
+  }
+
+  if ((next_octet >> kLiteralIncrementalN) == kLiteralIncrementalOpcode) {
+    std::string name;
+    if (!DecodeNextName(kLiteralIncrementalN, &name))
+      return false;
+    std::string value;
+    if (!DecodeNextValue(&value))
+      return false;
+    int32 index = 0;
+    std::vector<uint32> removed_referenced_indices;
+    encoding_context_->ProcessLiteralHeaderWithIncrementalIndexing(
+        name, value, &index, &removed_referenced_indices);
+    if (index >= 0) {
+      encoding_context_->AddTouches(index, 0);
+    }
+    EmitHeader(name, value);
+    return true;
+  }
+
+  if ((next_octet >> kLiteralSubstitutionN) == kLiteralSubstitutionOpcode) {
+    std::string name;
+    if (!DecodeNextName(kLiteralSubstitutionN, &name))
+      return false;
+    uint32 substituted_index = 0;
+    if (!DecodeNextInteger(0, &substituted_index))
+      return false;
+    std::string value;
+    if (!DecodeNextValue(&value))
+      return false;
+    int32 index = 0;
+    std::vector<uint32> removed_referenced_indices;
+    encoding_context_->ProcessLiteralHeaderWithSubstitutionIndexing(
+        name, substituted_index, value, &index, &removed_referenced_indices);
+    if (index >= 0) {
+      encoding_context_->AddTouches(index, 0);
+    }
+    EmitHeader(name, value);
+    return true;
+  }
+
+  LOG(ERROR) << "Invalid opcode 0x" << std::hex << static_cast<int>(next_octet);
+  return false;
+}
+
+bool Http2Decoder::PeekNextOctet(uint8* next_octet) {
+  if (!HasMoreData()) {
+    LOG(ERROR) << "HasMoreData returned false in PeekNextOctet";
+    return false;
+  }
+
+  *next_octet = buffer_[i_];
+  return true;
+}
+
+bool Http2Decoder::DecodeNextOctet(uint8* next_octet) {
+  if (!PeekNextOctet(next_octet))
+    return false;
+
+  ++i_;
+  return true;
+}
+
+bool Http2Decoder::DecodeNextInteger(uint8 N, uint32* I) {
+  *I = 0;
+  bool has_more = true;
+  uint8 shift = N;
+
+  if (N > 0) {
+    uint8 next_marker = (1 << N) - 1;
+    uint8 next_octet = 0;
+    if (!DecodeNextOctet(&next_octet))
+      return false;
+    *I = next_octet & next_marker;
+    has_more = (*I == next_marker);
+  }
+
+  while (has_more) {
+    uint8 next_octet = 0;
+    if (!DecodeNextOctet(&next_octet))
+      return false;
+    has_more = (next_octet & 0x80) != 0;
+    *I += (next_octet % 128) << shift;
+    shift += 7;
+  }
+
+  return true;
+}
+
+bool Http2Decoder::DecodeNextOctetSequence(std::string* str) {
+  uint32 size = 0;
+  if (!DecodeNextInteger(0, &size)) {
+    return false;
+  }
+  if ((i_ + size) > buffer_size_) {
+    LOG(ERROR) << "Invalid size " << size;
+    return false;
+  }
+  str->assign(buffer_ + i_, size);
+  i_ += size;
+  return true;
+}
+
+bool Http2Decoder::DecodeNextName(uint8 N, std::string* next_name) {
+  uint32 index_plus_one_or_zero = 0;
+  if (!DecodeNextInteger(N, &index_plus_one_or_zero))
+    return false;
+  if (index_plus_one_or_zero == 0) {
+    if (!DecodeNextOctetSequence(next_name))
+      return false;
+  } else {
+    uint32 index = index_plus_one_or_zero - 1;
+    if (!encoding_context_->GetIndexedHeaderName(index, next_name)) {
+      LOG(ERROR) << "Invalid index " << index;
+      return false;
+    }
+  }
+  if (!IsValidHeaderName(*next_name)) {
+    LOG(ERROR) << "Invalid name " << *next_name;
+    return false;
+  }
+  return true;
+}
+
+bool Http2Decoder::DecodeNextValue(std::string* next_value) {
+  if (!DecodeNextOctetSequence(next_value))
+    return false;
+  if (!IsValidHeaderValue(*next_value)) {
+    LOG(ERROR) << "Invalid value " << *next_value;
+    return false;
+  }
+  return true;
+}
+
+}  // namespace
+
+Http2Decompressor::Http2Decompressor() : encoding_context_(HTTP2_REQUEST) {}
+
+Http2Decompressor::~Http2Decompressor() {}
+
+bool Http2Decompressor::DecodeNameValueBlock(const char* data, size_t len,
+                                             SpdyNameValueBlock* out) {
+  Http2Decoder decoder(data, len, &encoding_context_, out);
+  while (decoder.HasMoreData()) {
+    if (!decoder.ProcessNextHeaderRepresentation()) {
+      LOG(INFO) << "Error processing next header representation";
+      return false;
+    }
+  }
+
+  for (size_t i = 0; i < encoding_context_.GetEntryCount(); ++i) {
+    HeaderTableEntry* entry = encoding_context_.GetMutableEntry(i);
+    if (entry->referenced && (entry->touch_count == kUntouched)) {
+      decoder.EmitHeader(entry->name, entry->value);
+    }
+    entry->touch_count = kUntouched;
+  }
+
+  return true;
+}
+
+}  // namespace net