Add static domain security state generator tool.

net/tools/domain_security_preload_generator/huffman/huffman_frequency_tracker.h

+// Copyright (c) 2016 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.
+
+#ifndef NET_TOOLS_DOMAIN_SECURITY_PRELOAD_GENERATOR_HUFFMAN_FREQUENCY_TRACKER_H_
+#define NET_TOOLS_DOMAIN_SECURITY_PRELOAD_GENERATOR_HUFFMAN_FREQUENCY_TRACKER_H_
+
+#include <stdint.h>
+
+#include <map>
+#include <memory>
+#include <vector>
+
+namespace net {
+
+class HuffmanNode;

[agl, 2016/12/06 18:51:36]

HPACK is full of Huffman code too and I worry that we might evolve into an ODR
violation. I think it would be worth putting at least this Huffman code in a
namespace. Maybe "transport_security_state"?

[martijnc, 2016/12/07 22:37:54]

I moved most of the code into a "transport_security_state" namespace, most of it
is very specific to this anyway.

Would you prefer a different name for this tool as well? I opted for
"domain_security_preload_generator" because that's the component this is under
in the bug tracker.

"transport_security_state_generator" might be clearer since the other code is
named similarly, as was the old script.

+
+struct HuffmanRepresentation {
+  uint32_t bits;
+  uint32_t number_of_bits;
+};
+
+// A HuffmanRepresentationTable maps the original characters to their Huffman
+// representation. The Huffman representation consists of the number of bits
+// needed to represent the character and the actual bits.
+using HuffmanRepresentationTable = std::map<uint8_t, HuffmanRepresentation>;
+using HuffmanRepresentationPair = std::pair<uint8_t, HuffmanRepresentation>;
+
+// This class tracks the number of times each character is used and calculates
+// a space efficient way to represent all tracked characters by constructing a
+// Huffman tree based on the number of times each character is seen.
+class HuffmanFrequencyTracker {
+ public:
+  HuffmanFrequencyTracker();
+  ~HuffmanFrequencyTracker();
+
+  // Will increase the count for |character| by one indicating it has been used.
+  void RecordUsage(uint8_t character);
+
+  // Returns a HuffmanRepresentationTable based on the usage data collected
+  // through RecordUsage().
+  HuffmanRepresentationTable ToHuffmanRepresentationTable();

[agl, 2016/12/06 18:51:36]

"HuffmanRepresentation" in the name seems like a bit of a sutter. Also this is
called ToFoo, while just below is AsFoo. I think they should both have the same
prefix.

[martijnc, 2016/12/07 22:37:54]

Both done.

+
+  // Outputs the Huffman representation as a vector of uint8_t's in a format
+  // Chromium can use to reconstruct the tree.
+  //
+  // The nodes of the tree are pairs of uint8s. The last node in the array is
+  // the root of the tree. Each pair is two uint8_t values, the first is "left"
+  // and the second is "right". If a uint8_t value has the MSB set then it
+  // represents a literal leaf value. Otherwise it's a pointer to the n'th
+  // element of the array.
+  std::vector<uint8_t> AsVector();
+
+ private:
+  // Determines the Huffman representation of the characters under |node| and
+  // inserts them into |table|. |bits| and |number_of_bits| are used as a
+  // prefix.
+  void TreeToHuffmanRepresentationTable(HuffmanNode* node,
+                                        uint32_t bits,
+                                        uint32_t number_of_bits,
+                                        HuffmanRepresentationTable* table);
+
+  // Converts the tree under |node| into a byte representation in |vector|. See
+  // AsVector() for more information on the format.
+  uint32_t WriteToVector(HuffmanNode* node, std::vector<uint8_t>* vector);
+
+  // Constructs a Huffman tree based on |counts_|.
+  std::unique_ptr<HuffmanNode> BuildTree();
+
+  // Holds usage information for the traced characters. Maps the character to
+  // the number of these its usage has been recorded through RecordUsage().

[agl, 2016/12/06 18:51:36]

s/these/times/

[martijnc, 2016/12/07 22:37:54]

Done.

+  std::map<uint8_t, uint32_t> counts_;
+};
+
+}  // namespace net
+
+#endif  // NET_TOOLS_DOMAIN_SECURITY_PRELOAD_GENERATOR_HUFFMAN_FREQUENCY_TRACKER_H_