Add static domain security state generator tool.

net/tools/domain_security_preload_generator/trie/trie_writer.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_TRIE_TRIE_WRITER_H_
+#define NET_TOOLS_DOMAIN_SECURITY_PRELOAD_GENERATOR_TRIE_TRIE_WRITER_H_
+
+#include <string>
+#include <vector>
+
+#include "net/tools/domain_security_preload_generator/bit_writer.h"
+#include "net/tools/domain_security_preload_generator/domain_security_entry.h"
+#include "net/tools/domain_security_preload_generator/huffman/huffman_frequency_tracker.h"
+
+namespace net {
+
+class DomainSecurityEntry;
+class TrieBitBuffer;
+
+namespace {
+
+struct ReversedEntry {
+  ReversedEntry(std::vector<uint8_t> reversed_name,
+                const DomainSecurityEntry* entry);
+  ~ReversedEntry();
+
+  std::vector<uint8_t> reversed_name;
+  const DomainSecurityEntry* entry;
+};
+
+}  // namespace
+
+// Maps a name to an index. This is used to track the index of several values
+// in the C++ index. The index refers the the array index of the name
+// (e.g. pinsets) are outputted as an C++ array and the index for the pinset
+// is encoded in the trie.
+using NameIDMap = std::map<std::string, uint32_t>;
+using NameIDPair = std::pair<std::string, uint32_t>;
+using ReversedEntries = std::vector<std::unique_ptr<ReversedEntry>>;
+
+class TrieWriter {
+ public:
+  enum : uint8_t { kTerminalValue = 0, kEndOfTableValue = 127 };
+
+  TrieWriter(const HuffmanRepresentationTable& huffman_table,
+             const NameIDMap& domain_ids_map,
+             const NameIDMap& expect_ct_report_uri_map,
+             const NameIDMap& expect_staple_report_uri_map,
+             const NameIDMap& pinsets_map,
+             HuffmanFrequencyTracker* frequency_tracker);
+  ~TrieWriter();
+
+  // Construct a trie containing all |entries|. The output is written to
+  // |buffer_|. Returns the position of the trie root.
+  int WriteEntries(const DomainSecurityEntries& entries);
+
+  // Returns the position |buffer_| is currently at. The returned value is in
+  // bits.
+  uint32_t position() const;
+
+  // Close the BitWriter to ensure any buffered bits are written to the vector.
+  void close();
+
+  // Returns the trie bytes.
+  const std::vector<uint8_t>& bytes() const { return buffer_.bytes(); }
+
+ private:
+  int WriteDispatchTables(ReversedEntries::iterator start,
+                          ReversedEntries::iterator end,
+                          int depth);
+
+  // Serializes |*entry| and writes the output to |*writer|.
+  void WriteSecurityEntry(const DomainSecurityEntry* entry,
+                          TrieBitBuffer* writer);
+
+  // Removes the first |length| characters from all entries between |start| and
+  // |end|.
+  void RemovePrefix(size_t length,
+                    ReversedEntries::iterator start,
+                    ReversedEntries::iterator end);
+
+  // Searches for the longest common prefix for all entries between |start| and
+  // |end|.
+  std::vector<uint8_t> LongestCommonPrefix(ReversedEntries::iterator start,
+                                           ReversedEntries::iterator end) const;
+
+  // Returns the reversed |hostname| as a vector of bytes. The reversed hostname
+  // will be terminated by |kTerminalValue|.
+  std::vector<uint8_t> ReverseName(const std::string& hostname) const;
+
+  BitWriter buffer_;
+  const HuffmanRepresentationTable& huffman_table_;
+  const NameIDMap& domain_ids_map_;
+  const NameIDMap& expect_ct_report_uri_map_;
+  const NameIDMap& expect_staple_report_uri_map_;
+  const NameIDMap& pinsets_map_;
+  HuffmanFrequencyTracker* frequency_tracker_;
+};
+
+}  // namespace net
+
+#endif  // NET_TOOLS_DOMAIN_SECURITY_PRELOAD_GENERATOR_TRIE_TRIE_WRITER_H_