1 // Copyright (c) 2019 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 "quiche/quic/core/qpack/qpack_required_insert_count.h"
6
7 #include "absl/base/macros.h"
8 #include "quiche/quic/platform/api/quic_test.h"
9
10 namespace quic {
11 namespace test {
12 namespace {
13
TEST(QpackRequiredInsertCountTest,QpackEncodeRequiredInsertCount)14 TEST(QpackRequiredInsertCountTest, QpackEncodeRequiredInsertCount) {
15 EXPECT_EQ(0u, QpackEncodeRequiredInsertCount(0, 0));
16 EXPECT_EQ(0u, QpackEncodeRequiredInsertCount(0, 8));
17 EXPECT_EQ(0u, QpackEncodeRequiredInsertCount(0, 1024));
18
19 EXPECT_EQ(2u, QpackEncodeRequiredInsertCount(1, 8));
20 EXPECT_EQ(5u, QpackEncodeRequiredInsertCount(20, 8));
21 EXPECT_EQ(7u, QpackEncodeRequiredInsertCount(106, 10));
22 }
23
24 // For testing valid decodings, the Encoded Required Insert Count is calculated
25 // from Required Insert Count, so that there is an expected value to compare
26 // the decoded value against, and so that intricate inequalities can be
27 // documented.
28 struct {
29 uint64_t required_insert_count;
30 uint64_t max_entries;
31 uint64_t total_number_of_inserts;
32 } kTestData[] = {
33 // Maximum dynamic table capacity is zero.
34 {0, 0, 0},
35 // No dynamic entries in header.
36 {0, 100, 0},
37 {0, 100, 500},
38 // Required Insert Count has not wrapped around yet, no entries evicted.
39 {15, 100, 25},
40 {20, 100, 10},
41 // Required Insert Count has not wrapped around yet, some entries evicted.
42 {90, 100, 110},
43 // Required Insert Count has wrapped around.
44 {234, 100, 180},
45 // Required Insert Count has wrapped around many times.
46 {5678, 100, 5701},
47 // Lowest and highest possible Required Insert Count values
48 // for given MaxEntries and total number of insertions.
49 {401, 100, 500},
50 {600, 100, 500}};
51
TEST(QpackRequiredInsertCountTest,QpackDecodeRequiredInsertCount)52 TEST(QpackRequiredInsertCountTest, QpackDecodeRequiredInsertCount) {
53 for (size_t i = 0; i < ABSL_ARRAYSIZE(kTestData); ++i) {
54 const uint64_t required_insert_count = kTestData[i].required_insert_count;
55 const uint64_t max_entries = kTestData[i].max_entries;
56 const uint64_t total_number_of_inserts =
57 kTestData[i].total_number_of_inserts;
58
59 if (required_insert_count != 0) {
60 // Dynamic entries cannot be referenced if dynamic table capacity is zero.
61 ASSERT_LT(0u, max_entries) << i;
62 // Entry |total_number_of_inserts - 1 - max_entries| and earlier entries
63 // are evicted. Entry |required_insert_count - 1| is referenced. No
64 // evicted entry can be referenced.
65 ASSERT_LT(total_number_of_inserts, required_insert_count + max_entries)
66 << i;
67 // Entry |required_insert_count - 1 - max_entries| and earlier entries are
68 // evicted, entry |total_number_of_inserts - 1| is the last acknowledged
69 // entry. Every evicted entry must be acknowledged.
70 ASSERT_LE(required_insert_count, total_number_of_inserts + max_entries)
71 << i;
72 }
73
74 uint64_t encoded_required_insert_count =
75 QpackEncodeRequiredInsertCount(required_insert_count, max_entries);
76
77 // Initialize to a value different from the expected output to confirm that
78 // QpackDecodeRequiredInsertCount() modifies the value of
79 // |decoded_required_insert_count|.
80 uint64_t decoded_required_insert_count = required_insert_count + 1;
81 EXPECT_TRUE(QpackDecodeRequiredInsertCount(
82 encoded_required_insert_count, max_entries, total_number_of_inserts,
83 &decoded_required_insert_count))
84 << i;
85
86 EXPECT_EQ(decoded_required_insert_count, required_insert_count) << i;
87 }
88 }
89
90 // Failures are tested with hardcoded values for encoded required insert count,
91 // to provide test coverage for values that would never be produced by a well
92 // behaved encoding function.
93 struct {
94 uint64_t encoded_required_insert_count;
95 uint64_t max_entries;
96 uint64_t total_number_of_inserts;
97 } kInvalidTestData[] = {
98 // Maximum dynamic table capacity is zero, yet header block
99 // claims to have a reference to a dynamic table entry.
100 {1, 0, 0},
101 {9, 0, 0},
102 // Examples from
103 // https://github.com/quicwg/base-drafts/issues/2112#issue-389626872.
104 {1, 10, 2},
105 {18, 10, 2},
106 // Encoded Required Insert Count value too small or too large
107 // for given MaxEntries and total number of insertions.
108 {400, 100, 500},
109 {601, 100, 500}};
110
TEST(QpackRequiredInsertCountTest,DecodeRequiredInsertCountError)111 TEST(QpackRequiredInsertCountTest, DecodeRequiredInsertCountError) {
112 for (size_t i = 0; i < ABSL_ARRAYSIZE(kInvalidTestData); ++i) {
113 uint64_t decoded_required_insert_count = 0;
114 EXPECT_FALSE(QpackDecodeRequiredInsertCount(
115 kInvalidTestData[i].encoded_required_insert_count,
116 kInvalidTestData[i].max_entries,
117 kInvalidTestData[i].total_number_of_inserts,
118 &decoded_required_insert_count))
119 << i;
120 }
121 }
122
123 } // namespace
124 } // namespace test
125 } // namespace quic
126