Add unittests for different transport security state generator components.

net/tools/transport_security_state_generator/huffman/huffman_builder_unittest.cc

+// Copyright 2017 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/transport_security_state_generator/huffman/huffman_builder.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace net {
+
+namespace transport_security_state {
+
+// Test that there are no Huffman representations that are a prefix for another.
+TEST(HuffmanBuilderTest, NoPrefixCollision) {
+  HuffmanBuilder builder;
+  HuffmanRepresentationTable encoding;
+  for (uint8_t i = 0; i <= 127; i++) {
+    // Make sure some values have identical counts.

[Ryan Sleevi, 2017/03/30 15:03:32]

Doesn't this make _most_ values have identical counts?

Or am I mentally parsing wrong?

[martijnc, 2017/03/30 19:02:22]

The intention is to make the values have an identical count to other values -
but not identical to all other values. But like you said, *all* values will have
a count that is identical to at least some other values.

Rephrased the comment in an attempt to clarify.

+    for (uint8_t j = 0; j <= i % 32; j++) {
+      builder.RecordUsage(i);
+    }
+  }
+
+  encoding = builder.ToTable();
+  for (uint8_t i = 0; i <= 127; i++) {
+    // There should never exist a representation that is a prefix for, or
+    // identical to, another.
+    uint32_t mask = 0;
+    for (uint32_t k = 0; k <= encoding[i].number_of_bits; k++) {
+      mask = (mask << 1) | 1;
+    }
+    mask = mask << (32 - encoding[i].number_of_bits);
+
+    for (uint8_t j = 0; j <= 127; j++) {
+      if (i == j) {
+        continue;
+      }
+
+      uint32_t aligned_i = encoding[i].bits
+                           << (32 - encoding[i].number_of_bits);
+      uint32_t aligned_j = encoding[j].bits
+                           << (32 - encoding[j].number_of_bits);
+      EXPECT_NE(aligned_i, aligned_j & mask);
+    }
+  }
+}
+
+// Test that all recorded characters get a representation and that no other
+// representations are created.
+// Note: There is an exception for encodings with less than 2 unique inputs.
+TEST(HuffmanBuilderTest, NoMissingInputs) {
+  HuffmanBuilder builder;
+  HuffmanRepresentationTable encoding;
+  for (uint8_t i = 0; i <= 63; i++) {

[Ryan Sleevi, 2017/03/30 15:03:32]

Why 63 (vs 127 above)? The i*2 means you'll skip 127 - desired or not?

[martijnc, 2017/03/30 19:02:22]

Yes, this intentionally skips over every odd value. Restructured this a bit so
that it (hopefully) is a little clearer.

+    for (uint8_t j = 0; j <= i % 5; j++) {
+      builder.RecordUsage(i * 2);
+    }
+  }
+
+  encoding = builder.ToTable();
+  for (uint8_t i = 0; i <= 126; i++) {
+    if (i % 2) {
+      EXPECT_EQ(encoding.find(i), encoding.cend());
+    } else {
+      EXPECT_NE(encoding.find(i), encoding.cend());
+    }
+  }
+}
+
+// Test that the representations have optimal order by checking that characters
+// with higher counts get shorter (or equal length) representations than those
+// with lower counts.
+TEST(HuffmanBuilderTest, OptimalCodeOrder) {
+  HuffmanBuilder builder;
+  HuffmanRepresentationTable encoding;
+  for (uint8_t i = 0; i <= 127; i++) {
+    for (uint8_t j = 0; j <= (i + 1); j++) {
+      builder.RecordUsage(i);
+    }
+  }
+
+  encoding = builder.ToTable();
+  for (uint8_t i = 0; i <= 127; i++) {
+    // The representation for |i| should be longer or have the same length as
+    // all following representations because they have a higher frequency and
+    // therefor should never get a longer representation.
+    for (uint8_t j = i; j <= 127; j++) {
+      // A representation for the values should exist in the table.
+      ASSERT_NE(encoding.find(i), encoding.cend());
+      ASSERT_NE(encoding.find(j), encoding.cend());
+
+      EXPECT_GE(encoding[i].number_of_bits, encoding[j].number_of_bits);
+    }
+  }
+}
+
+// Test that the ToVector() creates a byte vector that represents the expected
+// Huffman Tree.
+TEST(HuffmanBuilderTest, ToVector) {
+  // Build a small tree.
+  HuffmanBuilder builder;
+  builder.RecordUsage('a');
+  builder.RecordUsage('b');
+  builder.RecordUsage('b');
+  builder.RecordUsage('c');
+  builder.RecordUsage('c');
+  builder.RecordUsage('d');
+  builder.RecordUsage('d');
+  builder.RecordUsage('d');
+  builder.RecordUsage('e');
+  builder.RecordUsage('e');
+  builder.RecordUsage('e');
+
+  std::vector<uint8_t> output = builder.ToVector();
+
+  // This represents 4 elements (4 groups of 2 uint8_t's) which, when decoded,
+  // yields the expected Huffman Tree:
+  //                     root (element 3)
+  //                     /              \
+  //            element 1                element 2
+  //            /       \                /       \
+  //         0xE3 (c)   element 0     0xE4 (e)   0xE5 (f)
+  //                    /       \
+  //                 0xE1 (a)   0xE2 (b)
+  EXPECT_THAT(output, testing::ElementsAre(0xE1, 0xE2, 0xE3, 0x0, 0xE4, 0xE5,
+                                           0x1, 0x2));

[Ryan Sleevi, 2017/03/30 15:03:32]

Sleevi stupidity - why 0x1/0x2?

[martijnc, 2017/03/30 19:02:22]

Every pair of uint8_t's represents a node in the tree. There are 4 nodes;

Node 0: 0xE1 & 0xE2
Node 1: 0xE3 & 0x0
Node 2: 0xE4 & 0xE5
Node 3: 0x1 & 0x2

The last node (last 2 values in the vector) is always the root.

The first value (0x1) is the left child and the second value (0x2) is the right
child of the root. Because the MSBs are not set, these values "point" to other
nodes. The actual value indicates which node they point to. The left child
points to node 1 and the right child points to node 2.

The left child of node 1 (0xE3) has its MSB set which means it is a leaf. The
right child has its MSB not set which means it is a pointer to another node
(node 0).

The MSBs for both values in node 2 are set indicating that both children are
leafs. The leaf values are obtained by ignoring the MSB (0xE4 & 0x7F = 0x64).

Both children of node 0 are leafs.

Fixed the labels in the tree, the ascii values for node 2 were incorrect. Also
replaced 'elements' with 'nodes' in the comment.

+}
+
+// The ToVector() logic requires at least 2 unique inputs to construct the
+// vector. Test that nodes are appended when there are less than 2 unique
+// inputs.
+TEST(HuffmanBuilderTest, ToVectorSingle) {
+  // Build a single element tree. Another element should be added automatically.
+  HuffmanBuilder builder;
+  builder.RecordUsage('a');
+
+  std::vector<uint8_t> output = builder.ToVector();
+
+  // This represents 1 elements (1 group of 2 uint8_t's) which, when decoded,
+  // yields the expected Huffman Tree:
+  //                     root (element 1)
+  //                     /              \
+  //             0x80 (\0)              0xE1 (a)
+  //
+  // Note: the node \0 node was appended to the tree.
+  EXPECT_THAT(output, testing::ElementsAre(0x80, 0xE1));
+}
+
+}  // transport_security_state
+
+}  // namespace net