1 // Copyright 2016 The Chromium Authors
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/huffman_trie/trie/trie_writer.h"
6
7 #include <algorithm>
8 #include <ostream>
9
10 #include "base/check.h"
11 #include "net/tools/huffman_trie/trie/trie_bit_buffer.h"
12
13 namespace net::huffman_trie {
14
15 namespace {
16
CompareReversedEntries(const std::unique_ptr<net::huffman_trie::ReversedEntry> & lhs,const std::unique_ptr<net::huffman_trie::ReversedEntry> & rhs)17 bool CompareReversedEntries(
18 const std::unique_ptr<net::huffman_trie::ReversedEntry>& lhs,
19 const std::unique_ptr<net::huffman_trie::ReversedEntry>& rhs) {
20 return lhs->reversed_name < rhs->reversed_name;
21 }
22
23 // Searches for the longest common prefix for all entries between |start| and
24 // |end|.
LongestCommonPrefix(ReversedEntries::const_iterator start,ReversedEntries::const_iterator end)25 std::vector<uint8_t> LongestCommonPrefix(ReversedEntries::const_iterator start,
26 ReversedEntries::const_iterator end) {
27 if (start == end) {
28 return std::vector<uint8_t>();
29 }
30
31 std::vector<uint8_t> prefix;
32 for (size_t i = 0;; ++i) {
33 if (i > (*start)->reversed_name.size()) {
34 break;
35 }
36
37 uint8_t candidate = (*start)->reversed_name.at(i);
38 if (candidate == kTerminalValue) {
39 break;
40 }
41
42 bool ok = true;
43 for (auto it = start + 1; it != end; ++it) {
44 if (i > (*it)->reversed_name.size() ||
45 (*it)->reversed_name.at(i) != candidate) {
46 ok = false;
47 break;
48 }
49 }
50
51 if (!ok) {
52 break;
53 }
54
55 prefix.push_back(candidate);
56 }
57
58 return prefix;
59 }
60
61 // Returns the reversed |hostname| as a vector of bytes. The reversed hostname
62 // will be terminated by |kTerminalValue|.
ReverseName(const std::string & hostname)63 std::vector<uint8_t> ReverseName(const std::string& hostname) {
64 size_t hostname_size = hostname.size();
65 std::vector<uint8_t> reversed_name(hostname_size + 1);
66
67 for (size_t i = 0; i < hostname_size; ++i) {
68 reversed_name[i] = hostname[hostname_size - i - 1];
69 }
70
71 reversed_name[reversed_name.size() - 1] = kTerminalValue;
72 return reversed_name;
73 }
74
75 // Removes the first |length| characters from all entries between |start| and
76 // |end|.
RemovePrefix(size_t length,ReversedEntries::iterator start,ReversedEntries::iterator end)77 void RemovePrefix(size_t length,
78 ReversedEntries::iterator start,
79 ReversedEntries::iterator end) {
80 for (auto it = start; it != end; ++it) {
81 (*it)->reversed_name.erase((*it)->reversed_name.begin(),
82 (*it)->reversed_name.begin() + length);
83 }
84 }
85
86 } // namespace
87
ReversedEntry(std::vector<uint8_t> reversed_name,const TrieEntry * entry)88 ReversedEntry::ReversedEntry(std::vector<uint8_t> reversed_name,
89 const TrieEntry* entry)
90 : reversed_name(reversed_name), entry(entry) {}
91
92 ReversedEntry::~ReversedEntry() = default;
93
TrieWriter(const huffman_trie::HuffmanRepresentationTable & huffman_table,huffman_trie::HuffmanBuilder * huffman_builder)94 TrieWriter::TrieWriter(
95 const huffman_trie::HuffmanRepresentationTable& huffman_table,
96 huffman_trie::HuffmanBuilder* huffman_builder)
97 : huffman_table_(huffman_table), huffman_builder_(huffman_builder) {}
98
99 TrieWriter::~TrieWriter() = default;
100
WriteEntries(const TrieEntries & entries,uint32_t * root_position)101 bool TrieWriter::WriteEntries(const TrieEntries& entries,
102 uint32_t* root_position) {
103 if (entries.empty())
104 return false;
105
106 ReversedEntries reversed_entries;
107 for (auto* const entry : entries) {
108 auto reversed_entry =
109 std::make_unique<ReversedEntry>(ReverseName(entry->name()), entry);
110 reversed_entries.push_back(std::move(reversed_entry));
111 }
112
113 std::stable_sort(reversed_entries.begin(), reversed_entries.end(),
114 CompareReversedEntries);
115
116 return WriteDispatchTables(reversed_entries.begin(), reversed_entries.end(),
117 root_position);
118 }
119
WriteDispatchTables(ReversedEntries::iterator start,ReversedEntries::iterator end,uint32_t * position)120 bool TrieWriter::WriteDispatchTables(ReversedEntries::iterator start,
121 ReversedEntries::iterator end,
122 uint32_t* position) {
123 DCHECK(start != end) << "No entries passed to WriteDispatchTables";
124
125 TrieBitBuffer writer;
126
127 std::vector<uint8_t> prefix = LongestCommonPrefix(start, end);
128 writer.WriteSize(prefix.size());
129
130 if (prefix.size()) {
131 for (uint8_t c : prefix) {
132 writer.WriteChar(c, huffman_table_, huffman_builder_);
133 }
134 }
135
136 RemovePrefix(prefix.size(), start, end);
137 int32_t last_position = -1;
138
139 while (start != end) {
140 uint8_t candidate = (*start)->reversed_name.at(0);
141 auto sub_entries_end = start + 1;
142
143 for (; sub_entries_end != end; sub_entries_end++) {
144 if ((*sub_entries_end)->reversed_name.at(0) != candidate) {
145 break;
146 }
147 }
148
149 writer.WriteChar(candidate, huffman_table_, huffman_builder_);
150
151 if (candidate == kTerminalValue) {
152 if (sub_entries_end - start != 1) {
153 return false;
154 }
155 if (!(*start)->entry->WriteEntry(&writer)) {
156 return false;
157 }
158 } else {
159 RemovePrefix(1, start, sub_entries_end);
160 uint32_t table_position;
161 if (!WriteDispatchTables(start, sub_entries_end, &table_position)) {
162 return false;
163 }
164
165 writer.WritePosition(table_position, &last_position);
166 }
167
168 start = sub_entries_end;
169 }
170
171 writer.WriteChar(kEndOfTableValue, huffman_table_, huffman_builder_);
172
173 *position = buffer_.position();
174 writer.Flush();
175 writer.WriteToBitWriter(&buffer_);
176 return true;
177 }
178
position() const179 uint32_t TrieWriter::position() const {
180 return buffer_.position();
181 }
182
Flush()183 void TrieWriter::Flush() {
184 buffer_.Flush();
185 }
186
187 } // namespace net::huffman_trie
188