Add static domain security state generator tool.

net/tools/domain_security_preload_generator/huffman/huffman_frequency_tracker.cc

+// 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.
+
+#include "net/tools/domain_security_preload_generator/huffman/huffman_frequency_tracker.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+#include "net/tools/domain_security_preload_generator/huffman/huffman_node.h"
+
+namespace net {
+
+namespace {
+
+bool CompareNodes(const std::unique_ptr<net::HuffmanNode>& lhs,
+                  const std::unique_ptr<net::HuffmanNode>& rhs) {
+  return lhs->count() < rhs->count();
+}
+
+}  // namespace
+
+HuffmanFrequencyTracker::HuffmanFrequencyTracker() {}
+
+HuffmanFrequencyTracker::~HuffmanFrequencyTracker() {}
+
+void HuffmanFrequencyTracker::RecordUsage(uint8_t character) {
+  counts_[character] += 1;
+}
+
+HuffmanRepresentationTable
+HuffmanFrequencyTracker::ToHuffmanRepresentationTable() {
+  HuffmanRepresentationTable table;
+  std::unique_ptr<HuffmanNode> node(BuildTree());
+
+  TreeToHuffmanRepresentationTable(node.get(), 0, 0, &table);
+  return table;
+}
+
+void HuffmanFrequencyTracker::TreeToHuffmanRepresentationTable(
+    HuffmanNode* node,
+    uint32_t bits,
+    uint32_t number_of_bits,
+    HuffmanRepresentationTable* table) {
+  if (node->IsLeaf()) {
+    HuffmanRepresentation item;
+    item.bits = bits;
+    item.number_of_bits = number_of_bits;
+
+    table->insert(HuffmanRepresentationPair(node->value(), item));
+  } else {
+    uint32_t new_bits = bits << 1;
+    TreeToHuffmanRepresentationTable(node->left().get(), new_bits,
+                                     number_of_bits + 1, table);
+    TreeToHuffmanRepresentationTable(node->right().get(), new_bits | 1,
+                                     number_of_bits + 1, table);
+  }
+}
+
+std::vector<uint8_t> HuffmanFrequencyTracker::AsVector() {
+  std::vector<uint8_t> bytes;
+  std::unique_ptr<HuffmanNode> node(BuildTree());
+  WriteToVector(node.get(), &bytes);
+  return bytes;
+}
+
+uint32_t HuffmanFrequencyTracker::WriteToVector(HuffmanNode* node,
+                                                std::vector<uint8_t>* vector) {
+  uint8_t left_value;
+  uint8_t right_value;
+  uint32_t child_position;
+
+  if (node->left()->IsLeaf()) {
+    left_value = 128 | node->left()->value();
+  } else {
+    child_position = WriteToVector(node->left().get(), vector);
+    CHECK(child_position < 512) << "huffman tree too large";
+    left_value = child_position / 2;
+  }
+
+  if (node->right()->IsLeaf()) {
+    right_value = 128 | node->right()->value();
+  } else {
+    child_position = WriteToVector(node->right().get(), vector);
+    CHECK(child_position < 512) << "huffman tree to large";
+    right_value = child_position / 2;
+  }
+
+  uint32_t position = vector->size();
+  vector->push_back(left_value);
+  vector->push_back(right_value);
+  return position;
+}
+
+std::unique_ptr<HuffmanNode> HuffmanFrequencyTracker::BuildTree() {
+  std::vector<std::unique_ptr<HuffmanNode>> nodes;
+  nodes.reserve(counts_.size());
+
+  for (const auto& item : counts_) {
+    if (item.second > 0) {
+      std::unique_ptr<HuffmanNode> node(
+          new HuffmanNode(item.first, item.second, nullptr, nullptr));
+      nodes.push_back(std::move(node));
+    }
+  }
+
+  if (nodes.size() < 2) {
+    return std::move(nodes[0]);
+  }
+
+  std::stable_sort(nodes.begin(), nodes.end(), CompareNodes);
+
+  while (nodes.size() > 1) {
+    std::unique_ptr<HuffmanNode> a = std::move(nodes[0]);
+    std::unique_ptr<HuffmanNode> b = std::move(nodes[1]);
+
+    std::unique_ptr<HuffmanNode> parent(new HuffmanNode(
+        0, a->count() + b->count(), std::move(a), std::move(b)));
+
+    nodes.erase(nodes.begin());
+    nodes[0] = std::move(parent);
+
+    std::stable_sort(nodes.begin(), nodes.end(), CompareNodes);
+  }
+
+  return std::move(nodes[0]);
+}
+
+}  // namespace net