| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2016 The Chromium Authors. All rights reserved. | |
| 2 // Use of this source code is governed by a BSD-style license that can be | |
| 3 // found in the LICENSE file. | |
| 4 | |
| 5 #include "net/tools/domain_security_preload_generator/huffman/huffman_frequency_
tracker.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 | |
| 9 #include "base/logging.h" | |
| 10 | |
| 11 namespace net { | |
| 12 | |
| 13 namespace transport_security_state { | |
| 14 | |
| 15 namespace { | |
| 16 | |
| 17 class HuffmanNode { | |
| 18 public: | |
| 19 HuffmanNode(uint8_t value, | |
| 20 uint32_t count, | |
| 21 std::unique_ptr<HuffmanNode> left, | |
| 22 std::unique_ptr<HuffmanNode> right) | |
| 23 : value_(value), | |
| 24 count_(count), | |
| 25 left_(std::move(left)), | |
| 26 right_(std::move(right)) {} | |
| 27 ~HuffmanNode() {} | |
| 28 | |
| 29 bool IsLeaf() const { | |
| 30 return left_.get() == nullptr && right_.get() == nullptr; | |
| 31 } | |
| 32 | |
| 33 uint8_t value() const { return value_; } | |
| 34 uint32_t count() const { return count_; } | |
| 35 const std::unique_ptr<HuffmanNode>& left() const { return left_; } | |
| 36 const std::unique_ptr<HuffmanNode>& right() const { return right_; } | |
| 37 | |
| 38 private: | |
| 39 uint8_t value_; | |
| 40 uint32_t count_; | |
| 41 std::unique_ptr<HuffmanNode> left_; | |
| 42 std::unique_ptr<HuffmanNode> right_; | |
| 43 }; | |
| 44 | |
| 45 bool CompareNodes(const std::unique_ptr<HuffmanNode>& lhs, | |
| 46 const std::unique_ptr<HuffmanNode>& rhs) { | |
| 47 return lhs->count() < rhs->count(); | |
| 48 } | |
| 49 | |
| 50 } // namespace | |
| 51 | |
| 52 HuffmanFrequencyTracker::HuffmanFrequencyTracker() {} | |
| 53 | |
| 54 HuffmanFrequencyTracker::~HuffmanFrequencyTracker() {} | |
| 55 | |
| 56 void HuffmanFrequencyTracker::RecordUsage(uint8_t character) { | |
| 57 counts_[character] += 1; | |
| 58 } | |
| 59 | |
| 60 HuffmanRepresentationTable HuffmanFrequencyTracker::ToTable() { | |
| 61 HuffmanRepresentationTable table; | |
| 62 std::unique_ptr<HuffmanNode> node(BuildTree()); | |
| 63 | |
| 64 TreeToTable(node.get(), 0, 0, &table); | |
| 65 return table; | |
| 66 } | |
| 67 | |
| 68 void HuffmanFrequencyTracker::TreeToTable(HuffmanNode* node, | |
| 69 uint32_t bits, | |
| 70 uint32_t number_of_bits, | |
| 71 HuffmanRepresentationTable* table) { | |
| 72 if (node->IsLeaf()) { | |
| 73 HuffmanRepresentation item; | |
| 74 item.bits = bits; | |
| 75 item.number_of_bits = number_of_bits; | |
| 76 | |
| 77 table->insert(HuffmanRepresentationPair(node->value(), item)); | |
| 78 } else { | |
| 79 uint32_t new_bits = bits << 1; | |
| 80 TreeToTable(node->left().get(), new_bits, number_of_bits + 1, table); | |
| 81 TreeToTable(node->right().get(), new_bits | 1, number_of_bits + 1, table); | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 std::vector<uint8_t> HuffmanFrequencyTracker::ToVector() { | |
| 86 std::vector<uint8_t> bytes; | |
| 87 std::unique_ptr<HuffmanNode> node(BuildTree()); | |
| 88 WriteToVector(node.get(), &bytes); | |
| 89 return bytes; | |
| 90 } | |
| 91 | |
| 92 uint32_t HuffmanFrequencyTracker::WriteToVector(HuffmanNode* node, | |
| 93 std::vector<uint8_t>* vector) { | |
| 94 uint8_t left_value; | |
| 95 uint8_t right_value; | |
| 96 uint32_t child_position; | |
| 97 | |
| 98 if (node->left()->IsLeaf()) { | |
| 99 left_value = 128 | node->left()->value(); | |
| 100 } else { | |
| 101 child_position = WriteToVector(node->left().get(), vector); | |
| 102 CHECK(child_position < 512) << "huffman tree too large"; | |
| 103 left_value = child_position / 2; | |
| 104 } | |
| 105 | |
| 106 if (node->right()->IsLeaf()) { | |
| 107 right_value = 128 | node->right()->value(); | |
| 108 } else { | |
| 109 child_position = WriteToVector(node->right().get(), vector); | |
| 110 CHECK(child_position < 512) << "huffman tree to large"; | |
| 111 right_value = child_position / 2; | |
| 112 } | |
| 113 | |
| 114 uint32_t position = static_cast<uint32_t>(vector->size()); | |
| 115 vector->push_back(left_value); | |
| 116 vector->push_back(right_value); | |
| 117 return position; | |
| 118 } | |
| 119 | |
| 120 std::unique_ptr<HuffmanNode> HuffmanFrequencyTracker::BuildTree() { | |
| 121 std::vector<std::unique_ptr<HuffmanNode>> nodes; | |
| 122 nodes.reserve(counts_.size()); | |
| 123 | |
| 124 for (const auto& item : counts_) { | |
| 125 if (item.second > 0) { | |
| 126 std::unique_ptr<HuffmanNode> node( | |
| 127 new HuffmanNode(item.first, item.second, nullptr, nullptr)); | |
| 128 nodes.push_back(std::move(node)); | |
| 129 } | |
| 130 } | |
| 131 | |
| 132 if (nodes.size() < 2) { | |
| 133 return std::move(nodes[0]); | |
| 134 } | |
| 135 | |
| 136 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); | |
| 137 | |
| 138 while (nodes.size() > 1) { | |
| 139 std::unique_ptr<HuffmanNode> a = std::move(nodes[0]); | |
| 140 std::unique_ptr<HuffmanNode> b = std::move(nodes[1]); | |
| 141 | |
| 142 uint32_t count_a = a->count(); | |
| 143 uint32_t count_b = b->count(); | |
| 144 | |
| 145 std::unique_ptr<HuffmanNode> parent( | |
| 146 new HuffmanNode(0, count_a + count_b, std::move(a), std::move(b))); | |
| 147 | |
| 148 nodes.erase(nodes.begin()); | |
| 149 nodes[0] = std::move(parent); | |
| 150 | |
| 151 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); | |
| 152 } | |
| 153 | |
| 154 return std::move(nodes[0]); | |
| 155 } | |
| 156 | |
| 157 } // namespace transport_security_state | |
| 158 | |
| 159 } // namespace net | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2632073002:
Rename domain_security_preload_generator. (Closed)
