OLD | NEW |
---|---|
1 // Copyright (c) 2016 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/tools/transport_security_state_generator/huffman/huffman_builder.h " | 5 #include "net/tools/transport_security_state_generator/huffman/huffman_builder.h " |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 | 8 |
9 #include "base/logging.h" | 9 #include "base/logging.h" |
10 #include "base/memory/ptr_util.h" | |
10 | 11 |
11 namespace net { | 12 namespace net { |
12 | 13 |
13 namespace transport_security_state { | 14 namespace transport_security_state { |
14 | 15 |
15 namespace { | 16 namespace { |
16 | 17 |
17 class HuffmanNode { | 18 class HuffmanNode { |
18 public: | 19 public: |
19 HuffmanNode(uint8_t value, | 20 HuffmanNode(uint8_t value, |
(...skipping 27 matching lines...) Expand all Loading... | |
47 return lhs->count() < rhs->count(); | 48 return lhs->count() < rhs->count(); |
48 } | 49 } |
49 | 50 |
50 } // namespace | 51 } // namespace |
51 | 52 |
52 HuffmanBuilder::HuffmanBuilder() {} | 53 HuffmanBuilder::HuffmanBuilder() {} |
53 | 54 |
54 HuffmanBuilder::~HuffmanBuilder() {} | 55 HuffmanBuilder::~HuffmanBuilder() {} |
55 | 56 |
56 void HuffmanBuilder::RecordUsage(uint8_t character) { | 57 void HuffmanBuilder::RecordUsage(uint8_t character) { |
57 counts_[character] += 1; | 58 DCHECK(character < 128); |
59 counts_[character & 127] += 1; | |
58 } | 60 } |
59 | 61 |
60 HuffmanRepresentationTable HuffmanBuilder::ToTable() { | 62 HuffmanRepresentationTable HuffmanBuilder::ToTable() { |
61 HuffmanRepresentationTable table; | 63 HuffmanRepresentationTable table; |
62 std::unique_ptr<HuffmanNode> node(BuildTree()); | 64 std::unique_ptr<HuffmanNode> node(BuildTree()); |
63 | 65 |
64 TreeToTable(node.get(), 0, 0, &table); | 66 TreeToTable(node.get(), 0, 0, &table); |
65 return table; | 67 return table; |
66 } | 68 } |
67 | 69 |
(...skipping 24 matching lines...) Expand all Loading... | |
92 uint32_t HuffmanBuilder::WriteToVector(HuffmanNode* node, | 94 uint32_t HuffmanBuilder::WriteToVector(HuffmanNode* node, |
93 std::vector<uint8_t>* vector) { | 95 std::vector<uint8_t>* vector) { |
94 uint8_t left_value; | 96 uint8_t left_value; |
95 uint8_t right_value; | 97 uint8_t right_value; |
96 uint32_t child_position; | 98 uint32_t child_position; |
97 | 99 |
98 if (node->left()->IsLeaf()) { | 100 if (node->left()->IsLeaf()) { |
99 left_value = 128 | node->left()->value(); | 101 left_value = 128 | node->left()->value(); |
100 } else { | 102 } else { |
101 child_position = WriteToVector(node->left().get(), vector); | 103 child_position = WriteToVector(node->left().get(), vector); |
102 CHECK(child_position < 512) << "huffman tree too large"; | 104 DCHECK(child_position < 512) << "huffman tree too large"; |
103 left_value = child_position / 2; | 105 left_value = child_position / 2; |
104 } | 106 } |
105 | 107 |
106 if (node->right()->IsLeaf()) { | 108 if (node->right()->IsLeaf()) { |
107 right_value = 128 | node->right()->value(); | 109 right_value = 128 | node->right()->value(); |
108 } else { | 110 } else { |
109 child_position = WriteToVector(node->right().get(), vector); | 111 child_position = WriteToVector(node->right().get(), vector); |
110 CHECK(child_position < 512) << "huffman tree to large"; | 112 DCHECK(child_position < 512) << "huffman tree to large"; |
111 right_value = child_position / 2; | 113 right_value = child_position / 2; |
112 } | 114 } |
113 | 115 |
114 uint32_t position = static_cast<uint32_t>(vector->size()); | 116 uint32_t position = static_cast<uint32_t>(vector->size()); |
115 vector->push_back(left_value); | 117 vector->push_back(left_value); |
116 vector->push_back(right_value); | 118 vector->push_back(right_value); |
117 return position; | 119 return position; |
118 } | 120 } |
119 | 121 |
120 std::unique_ptr<HuffmanNode> HuffmanBuilder::BuildTree() { | 122 std::unique_ptr<HuffmanNode> HuffmanBuilder::BuildTree() { |
121 std::vector<std::unique_ptr<HuffmanNode>> nodes; | 123 std::vector<std::unique_ptr<HuffmanNode>> nodes; |
122 nodes.reserve(counts_.size()); | 124 nodes.reserve(counts_.size()); |
123 | 125 |
124 for (const auto& item : counts_) { | 126 for (const auto& item : counts_) { |
125 if (item.second > 0) { | 127 nodes.push_back(base::MakeUnique<HuffmanNode>(item.first, item.second, |
martijnc
2017/02/08 20:58:21
This condition is always true because if the value
| |
126 std::unique_ptr<HuffmanNode> node( | 128 nullptr, nullptr)); |
127 new HuffmanNode(item.first, item.second, nullptr, nullptr)); | |
128 nodes.push_back(std::move(node)); | |
129 } | |
130 } | 129 } |
131 | 130 |
132 if (nodes.size() < 2) { | 131 // At least 2 nodes are required for everything to work properly. Add |
martijnc
2017/02/08 20:58:21
ToVector() expects at least 2 nodes.
| |
133 return std::move(nodes[0]); | 132 // arbitrary nodes to fill the tree. |
133 for (uint8_t i = 0; nodes.size() < 2 && i < 2; ++i) { | |
134 for (const auto& node : nodes) { | |
135 if (node->value() == i) { | |
136 break; | |
137 } | |
138 } | |
139 | |
140 nodes.push_back(base::MakeUnique<HuffmanNode>(i, 0, nullptr, nullptr)); | |
134 } | 141 } |
135 | 142 |
136 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); | 143 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); |
137 | 144 |
138 while (nodes.size() > 1) { | 145 while (nodes.size() > 1) { |
139 std::unique_ptr<HuffmanNode> a = std::move(nodes[0]); | 146 std::unique_ptr<HuffmanNode> a = std::move(nodes[0]); |
140 std::unique_ptr<HuffmanNode> b = std::move(nodes[1]); | 147 std::unique_ptr<HuffmanNode> b = std::move(nodes[1]); |
141 | 148 |
142 uint32_t count_a = a->count(); | 149 uint32_t count_a = a->count(); |
143 uint32_t count_b = b->count(); | 150 uint32_t count_b = b->count(); |
144 | 151 |
145 std::unique_ptr<HuffmanNode> parent( | 152 std::unique_ptr<HuffmanNode> parent( |
146 new HuffmanNode(0, count_a + count_b, std::move(a), std::move(b))); | 153 new HuffmanNode(0, count_a + count_b, std::move(a), std::move(b))); |
147 | 154 |
148 nodes.erase(nodes.begin()); | 155 nodes.erase(nodes.begin()); |
149 nodes[0] = std::move(parent); | 156 nodes[0] = std::move(parent); |
150 | 157 |
151 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); | 158 std::stable_sort(nodes.begin(), nodes.end(), CompareNodes); |
152 } | 159 } |
153 | 160 |
154 return std::move(nodes[0]); | 161 return std::move(nodes[0]); |
155 } | 162 } |
156 | 163 |
157 } // namespace transport_security_state | 164 } // namespace transport_security_state |
158 | 165 |
159 } // namespace net | 166 } // namespace net |
OLD | NEW |