OLD | NEW |
(Empty) | |
| 1 // Copyright 2017 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/transport_security_state_generator/huffman/huffman_builder.h
" |
| 6 #include "testing/gmock/include/gmock/gmock.h" |
| 7 #include "testing/gtest/include/gtest/gtest.h" |
| 8 |
| 9 namespace net { |
| 10 |
| 11 namespace transport_security_state { |
| 12 |
| 13 namespace { |
| 14 |
| 15 // Test that there are no Huffman representations that are a prefix for another. |
| 16 TEST(HuffmanBuilderTest, NoPrefixCollision) { |
| 17 HuffmanBuilder builder; |
| 18 HuffmanRepresentationTable encoding; |
| 19 for (uint8_t i = 0; i <= 127; i++) { |
| 20 // Make sure all values have an identical count to at least some other |
| 21 // values. |
| 22 for (uint8_t j = 0; j <= i % 32; j++) { |
| 23 builder.RecordUsage(i); |
| 24 } |
| 25 } |
| 26 |
| 27 encoding = builder.ToTable(); |
| 28 for (uint8_t i = 0; i <= 127; i++) { |
| 29 // There should never exist a representation that is a prefix for, or |
| 30 // identical to, another. |
| 31 uint32_t mask = 0; |
| 32 for (uint32_t k = 0; k <= encoding[i].number_of_bits; k++) { |
| 33 mask = (mask << 1) | 1; |
| 34 } |
| 35 mask = mask << (32 - encoding[i].number_of_bits); |
| 36 |
| 37 for (uint8_t j = 0; j <= 127; j++) { |
| 38 if (i == j) { |
| 39 continue; |
| 40 } |
| 41 |
| 42 uint32_t aligned_i = encoding[i].bits |
| 43 << (32 - encoding[i].number_of_bits); |
| 44 uint32_t aligned_j = encoding[j].bits |
| 45 << (32 - encoding[j].number_of_bits); |
| 46 EXPECT_NE(aligned_i, aligned_j & mask); |
| 47 } |
| 48 } |
| 49 } |
| 50 |
| 51 // Test that all recorded characters get a representation and that no other |
| 52 // representations are created. |
| 53 // Note: There is an exception for encodings with less than 2 unique inputs. |
| 54 TEST(HuffmanBuilderTest, NoMissingInputs) { |
| 55 HuffmanBuilder builder; |
| 56 HuffmanRepresentationTable encoding; |
| 57 for (uint8_t i = 0; i <= 127; i++) { |
| 58 if (i % 2) { |
| 59 for (uint8_t j = 0; j <= i % 5; j++) { |
| 60 builder.RecordUsage(i); |
| 61 } |
| 62 } |
| 63 } |
| 64 |
| 65 encoding = builder.ToTable(); |
| 66 for (uint8_t i = 0; i <= 127; i++) { |
| 67 if (i % 2) { |
| 68 EXPECT_NE(encoding.find(i), encoding.cend()); |
| 69 } else { |
| 70 EXPECT_EQ(encoding.find(i), encoding.cend()); |
| 71 } |
| 72 } |
| 73 } |
| 74 |
| 75 // Test that the representations have optimal order by checking that characters |
| 76 // with higher counts get shorter (or equal length) representations than those |
| 77 // with lower counts. |
| 78 TEST(HuffmanBuilderTest, OptimalCodeOrder) { |
| 79 HuffmanBuilder builder; |
| 80 HuffmanRepresentationTable encoding; |
| 81 for (uint8_t i = 0; i <= 127; i++) { |
| 82 for (uint8_t j = 0; j <= (i + 1); j++) { |
| 83 builder.RecordUsage(i); |
| 84 } |
| 85 } |
| 86 |
| 87 encoding = builder.ToTable(); |
| 88 for (uint8_t i = 0; i <= 127; i++) { |
| 89 // The representation for |i| should be longer or have the same length as |
| 90 // all following representations because they have a higher frequency and |
| 91 // therefor should never get a longer representation. |
| 92 for (uint8_t j = i; j <= 127; j++) { |
| 93 // A representation for the values should exist in the table. |
| 94 ASSERT_NE(encoding.find(i), encoding.cend()); |
| 95 ASSERT_NE(encoding.find(j), encoding.cend()); |
| 96 |
| 97 EXPECT_GE(encoding[i].number_of_bits, encoding[j].number_of_bits); |
| 98 } |
| 99 } |
| 100 } |
| 101 |
| 102 // Test that the ToVector() creates a byte vector that represents the expected |
| 103 // Huffman Tree. |
| 104 TEST(HuffmanBuilderTest, ToVector) { |
| 105 // Build a small tree. |
| 106 HuffmanBuilder builder; |
| 107 builder.RecordUsage('a'); |
| 108 builder.RecordUsage('b'); |
| 109 builder.RecordUsage('b'); |
| 110 builder.RecordUsage('c'); |
| 111 builder.RecordUsage('c'); |
| 112 builder.RecordUsage('d'); |
| 113 builder.RecordUsage('d'); |
| 114 builder.RecordUsage('d'); |
| 115 builder.RecordUsage('e'); |
| 116 builder.RecordUsage('e'); |
| 117 builder.RecordUsage('e'); |
| 118 |
| 119 std::vector<uint8_t> output = builder.ToVector(); |
| 120 |
| 121 // This represents 4 nodes (4 groups of 2 uint8_t's) which, when decoded, |
| 122 // yields the expected Huffman Tree: |
| 123 // root (node 3) |
| 124 // / \ |
| 125 // node 1 node 2 |
| 126 // / \ / \ |
| 127 // 0xE3 (c) node 0 0xE4 (d) 0xE5 (e) |
| 128 // / \ |
| 129 // 0xE1 (a) 0xE2 (b) |
| 130 EXPECT_THAT(output, testing::ElementsAre(0xE1, 0xE2, 0xE3, 0x0, 0xE4, 0xE5, |
| 131 0x1, 0x2)); |
| 132 } |
| 133 |
| 134 // The ToVector() logic requires at least 2 unique inputs to construct the |
| 135 // vector. Test that nodes are appended when there are less than 2 unique |
| 136 // inputs. |
| 137 TEST(HuffmanBuilderTest, ToVectorSingle) { |
| 138 // Build a single element tree. Another element should be added automatically. |
| 139 HuffmanBuilder builder; |
| 140 builder.RecordUsage('a'); |
| 141 |
| 142 std::vector<uint8_t> output = builder.ToVector(); |
| 143 |
| 144 // This represents 1 node (1 group of 2 uint8_t's) which, when decoded, |
| 145 // yields the expected Huffman Tree: |
| 146 // root (node 0) |
| 147 // / \ |
| 148 // 0x80 (\0) 0xE1 (a) |
| 149 // |
| 150 // Note: the node \0 node was appended to the tree. |
| 151 EXPECT_THAT(output, testing::ElementsAre(0x80, 0xE1)); |
| 152 } |
| 153 |
| 154 } // namespace |
| 155 |
| 156 } // namespace transport_security_state |
| 157 |
| 158 } // namespace net |
OLD | NEW |