net/spdy/hpack_encoder.cc - chromium/src.git - Git at Google

 // Copyright 2014 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/hpack_encoder.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 {

 using base::StringPiece;
 using std::string;

 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),
       char_counts_(NULL),
       total_char_counts_(NULL) {}

 HpackEncoder::~HpackEncoder() {}

 bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
                                    string* output) {
   // 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 {
       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);
   return true;
 }

 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);
   }
   UpdateCharacterCounts(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") {
       // |CookieToCrumbs()| produces ordered crumbs.
       CookieToCrumbs(*it, &full_set);
     } 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::SetCharCountsStorage(std::vector<size_t>* char_counts,
                                         size_t* total_char_counts) {
   CHECK_LE(256u, char_counts->size());
   char_counts_ = char_counts;
   total_char_counts_ = total_char_counts;
 }

 void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
   if (char_counts_ == NULL || total_char_counts_ == NULL) {
     return;
   }
   for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) {
     ++(*char_counts_)[static_cast<uint8>(*it)];
   }
   (*total_char_counts_) += str.size();
 }

 // static
 void HpackEncoder::CookieToCrumbs(const Representation& cookie,
                                   Representations* out) {
   size_t prior_size = out->size();

   // 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.second.find(";", pos);

     if (end == StringPiece::npos) {
       out->push_back(make_pair(
           cookie.first,
           cookie.second.substr(pos)));
       break;
     }
     out->push_back(make_pair(
         cookie.first,
         cookie.second.substr(pos, end - pos)));

     // Consume next space if present.
     pos = end + 1;
     if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
       pos++;
     }
   }
   // Sort crumbs and remove duplicates.
   std::sort(out->begin() + prior_size, out->end());
   out->erase(std::unique(out->begin() + prior_size, out->end()),
              out->end());
 }

 }  // namespace net
	// Copyright 2014 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/hpack_encoder.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 {

	using base::StringPiece;
	using std::string;

	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),
	char_counts_(NULL),
	total_char_counts_(NULL) {}

	HpackEncoder::~HpackEncoder() {}

	bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
	string* output) {
	// 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 {
	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);
	return true;
	}

	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);
	}
	UpdateCharacterCounts(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") {
	// \|CookieToCrumbs()\| produces ordered crumbs.
	CookieToCrumbs(*it, &full_set);
	} 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::SetCharCountsStorage(std::vector<size_t>* char_counts,
	size_t* total_char_counts) {
	CHECK_LE(256u, char_counts->size());
	char_counts_ = char_counts;
	total_char_counts_ = total_char_counts;
	}

	void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
	if (char_counts_ == NULL \|\| total_char_counts_ == NULL) {
	return;
	}
	for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) {
	++(char_counts_)[static_cast<uint8>(it)];
	}
	(*total_char_counts_) += str.size();
	}

	// static
	void HpackEncoder::CookieToCrumbs(const Representation& cookie,
	Representations* out) {
	size_t prior_size = out->size();

	// 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.second.find(";", pos);

	if (end == StringPiece::npos) {
	out->push_back(make_pair(
	cookie.first,
	cookie.second.substr(pos)));
	break;
	}
	out->push_back(make_pair(
	cookie.first,
	cookie.second.substr(pos, end - pos)));

	// Consume next space if present.
	pos = end + 1;
	if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
	pos++;
	}
	}
	// Sort crumbs and remove duplicates.
	std::sort(out->begin() + prior_size, out->end());
	out->erase(std::unique(out->begin() + prior_size, out->end()),
	out->end());
	}

	} // namespace net