1 /*
2  *  Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
3  *
4  *  Use of this source code is governed by a BSD-style license
5  *  that can be found in the LICENSE file in the root of the source
6  *  tree. An additional intellectual property rights grant can be found
7  *  in the file PATENTS.  All contributing project authors may
8  *  be found in the AUTHORS file in the root of the source tree.
9  */
10 
11 #include "rtc_base/numerics/sequence_number_util.h"
12 
13 #include <cstdint>
14 #include <iterator>
15 #include <set>
16 
17 #include "test/gtest.h"
18 
19 namespace webrtc {
20 class TestSeqNumUtil : public ::testing::Test {
21  protected:
22   // Can't use std::numeric_limits<unsigned long>::max() since
23   // MSVC doesn't support constexpr.
24   static const unsigned long ulmax = ~0ul;  // NOLINT
25 };
26 
TEST_F(TestSeqNumUtil,AheadOrAt)27 TEST_F(TestSeqNumUtil, AheadOrAt) {
28   uint8_t x = 0;
29   uint8_t y = 0;
30   ASSERT_TRUE(AheadOrAt(x, y));
31   ++x;
32   ASSERT_TRUE(AheadOrAt(x, y));
33   ASSERT_FALSE(AheadOrAt(y, x));
34   for (int i = 0; i < 256; ++i) {
35     ASSERT_TRUE(AheadOrAt(x, y));
36     ++x;
37     ++y;
38   }
39 
40   x = 128;
41   y = 0;
42   ASSERT_TRUE(AheadOrAt(x, y));
43   ASSERT_FALSE(AheadOrAt(y, x));
44 
45   x = 129;
46   ASSERT_FALSE(AheadOrAt(x, y));
47   ASSERT_TRUE(AheadOrAt(y, x));
48   ASSERT_TRUE(AheadOrAt<uint16_t>(x, y));
49   ASSERT_FALSE(AheadOrAt<uint16_t>(y, x));
50 }
51 
TEST_F(TestSeqNumUtil,AheadOrAtWithDivisor)52 TEST_F(TestSeqNumUtil, AheadOrAtWithDivisor) {
53   ASSERT_TRUE((AheadOrAt<uint8_t, 11>(5, 0)));
54   ASSERT_FALSE((AheadOrAt<uint8_t, 11>(6, 0)));
55   ASSERT_FALSE((AheadOrAt<uint8_t, 11>(0, 5)));
56   ASSERT_TRUE((AheadOrAt<uint8_t, 11>(0, 6)));
57 
58   ASSERT_TRUE((AheadOrAt<uint8_t, 10>(5, 0)));
59   ASSERT_FALSE((AheadOrAt<uint8_t, 10>(6, 0)));
60   ASSERT_FALSE((AheadOrAt<uint8_t, 10>(0, 5)));
61   ASSERT_TRUE((AheadOrAt<uint8_t, 10>(0, 6)));
62 
63   const uint8_t D = 211;
64   uint8_t x = 0;
65   for (int i = 0; i < D; ++i) {
66     uint8_t next_x = Add<D>(x, 1);
67     ASSERT_TRUE((AheadOrAt<uint8_t, D>(i, i)));
68     ASSERT_TRUE((AheadOrAt<uint8_t, D>(next_x, i)));
69     ASSERT_FALSE((AheadOrAt<uint8_t, D>(i, next_x)));
70     x = next_x;
71   }
72 }
73 
TEST_F(TestSeqNumUtil,AheadOf)74 TEST_F(TestSeqNumUtil, AheadOf) {
75   uint8_t x = 0;
76   uint8_t y = 0;
77   ASSERT_FALSE(AheadOf(x, y));
78   ++x;
79   ASSERT_TRUE(AheadOf(x, y));
80   ASSERT_FALSE(AheadOf(y, x));
81   for (int i = 0; i < 256; ++i) {
82     ASSERT_TRUE(AheadOf(x, y));
83     ++x;
84     ++y;
85   }
86 
87   x = 128;
88   y = 0;
89   for (int i = 0; i < 128; ++i) {
90     ASSERT_TRUE(AheadOf(x, y));
91     ASSERT_FALSE(AheadOf(y, x));
92     x++;
93     y++;
94   }
95 
96   for (int i = 0; i < 128; ++i) {
97     ASSERT_FALSE(AheadOf(x, y));
98     ASSERT_TRUE(AheadOf(y, x));
99     x++;
100     y++;
101   }
102 
103   x = 129;
104   y = 0;
105   ASSERT_FALSE(AheadOf(x, y));
106   ASSERT_TRUE(AheadOf(y, x));
107   ASSERT_TRUE(AheadOf<uint16_t>(x, y));
108   ASSERT_FALSE(AheadOf<uint16_t>(y, x));
109 }
110 
TEST_F(TestSeqNumUtil,AheadOfWithDivisor)111 TEST_F(TestSeqNumUtil, AheadOfWithDivisor) {
112   ASSERT_TRUE((AheadOf<uint8_t, 11>(5, 0)));
113   ASSERT_FALSE((AheadOf<uint8_t, 11>(6, 0)));
114   ASSERT_FALSE((AheadOf<uint8_t, 11>(0, 5)));
115   ASSERT_TRUE((AheadOf<uint8_t, 11>(0, 6)));
116 
117   ASSERT_TRUE((AheadOf<uint8_t, 10>(5, 0)));
118   ASSERT_FALSE((AheadOf<uint8_t, 10>(6, 0)));
119   ASSERT_FALSE((AheadOf<uint8_t, 10>(0, 5)));
120   ASSERT_TRUE((AheadOf<uint8_t, 10>(0, 6)));
121 
122   const uint8_t D = 211;
123   uint8_t x = 0;
124   for (int i = 0; i < D; ++i) {
125     uint8_t next_x = Add<D>(x, 1);
126     ASSERT_FALSE((AheadOf<uint8_t, D>(i, i)));
127     ASSERT_TRUE((AheadOf<uint8_t, D>(next_x, i)));
128     ASSERT_FALSE((AheadOf<uint8_t, D>(i, next_x)));
129     x = next_x;
130   }
131 }
132 
TEST_F(TestSeqNumUtil,ForwardDiffWithDivisor)133 TEST_F(TestSeqNumUtil, ForwardDiffWithDivisor) {
134   const uint8_t kDivisor = 211;
135 
136   for (uint8_t i = 0; i < kDivisor - 1; ++i) {
137     ASSERT_EQ(0, (ForwardDiff<uint8_t, kDivisor>(i, i)));
138     ASSERT_EQ(1, (ForwardDiff<uint8_t, kDivisor>(i, i + 1)));
139     ASSERT_EQ(kDivisor - 1, (ForwardDiff<uint8_t, kDivisor>(i + 1, i)));
140   }
141 
142   for (uint8_t i = 1; i < kDivisor; ++i) {
143     ASSERT_EQ(i, (ForwardDiff<uint8_t, kDivisor>(0, i)));
144     ASSERT_EQ(kDivisor - i, (ForwardDiff<uint8_t, kDivisor>(i, 0)));
145   }
146 }
147 
TEST_F(TestSeqNumUtil,ReverseDiffWithDivisor)148 TEST_F(TestSeqNumUtil, ReverseDiffWithDivisor) {
149   const uint8_t kDivisor = 241;
150 
151   for (uint8_t i = 0; i < kDivisor - 1; ++i) {
152     ASSERT_EQ(0, (ReverseDiff<uint8_t, kDivisor>(i, i)));
153     ASSERT_EQ(kDivisor - 1, (ReverseDiff<uint8_t, kDivisor>(i, i + 1)));
154     ASSERT_EQ(1, (ReverseDiff<uint8_t, kDivisor>(i + 1, i)));
155   }
156 
157   for (uint8_t i = 1; i < kDivisor; ++i) {
158     ASSERT_EQ(kDivisor - i, (ReverseDiff<uint8_t, kDivisor>(0, i)));
159     ASSERT_EQ(i, (ReverseDiff<uint8_t, kDivisor>(i, 0)));
160   }
161 }
162 
TEST_F(TestSeqNumUtil,SeqNumComparator)163 TEST_F(TestSeqNumUtil, SeqNumComparator) {
164   std::set<uint8_t, AscendingSeqNumComp<uint8_t>> seq_nums_asc;
165   std::set<uint8_t, DescendingSeqNumComp<uint8_t>> seq_nums_desc;
166 
167   uint8_t x = 0;
168   for (int i = 0; i < 128; ++i) {
169     seq_nums_asc.insert(x);
170     seq_nums_desc.insert(x);
171     ASSERT_EQ(x, *seq_nums_asc.begin());
172     ASSERT_EQ(x, *seq_nums_desc.rbegin());
173     ++x;
174   }
175 
176   seq_nums_asc.clear();
177   seq_nums_desc.clear();
178   x = 199;
179   for (int i = 0; i < 128; ++i) {
180     seq_nums_asc.insert(x);
181     seq_nums_desc.insert(x);
182     ASSERT_EQ(x, *seq_nums_asc.begin());
183     ASSERT_EQ(x, *seq_nums_desc.rbegin());
184     ++x;
185   }
186 }
187 
TEST_F(TestSeqNumUtil,SeqNumComparatorWithDivisor)188 TEST_F(TestSeqNumUtil, SeqNumComparatorWithDivisor) {
189   const uint8_t D = 223;
190 
191   std::set<uint8_t, AscendingSeqNumComp<uint8_t, D>> seq_nums_asc;
192   std::set<uint8_t, DescendingSeqNumComp<uint8_t, D>> seq_nums_desc;
193 
194   uint8_t x = 0;
195   for (int i = 0; i < D / 2; ++i) {
196     seq_nums_asc.insert(x);
197     seq_nums_desc.insert(x);
198     ASSERT_EQ(x, *seq_nums_asc.begin());
199     ASSERT_EQ(x, *seq_nums_desc.rbegin());
200     x = Add<D>(x, 1);
201   }
202 
203   seq_nums_asc.clear();
204   seq_nums_desc.clear();
205   x = 200;
206   for (int i = 0; i < D / 2; ++i) {
207     seq_nums_asc.insert(x);
208     seq_nums_desc.insert(x);
209     ASSERT_EQ(x, *seq_nums_asc.begin());
210     ASSERT_EQ(x, *seq_nums_desc.rbegin());
211     x = Add<D>(x, 1);
212   }
213 }
214 
TEST(SeqNumUnwrapper,PreserveStartValue)215 TEST(SeqNumUnwrapper, PreserveStartValue) {
216   SeqNumUnwrapper<uint8_t> unwrapper;
217   EXPECT_EQ(123, unwrapper.Unwrap(123));
218 }
219 
TEST(SeqNumUnwrapper,ForwardWrap)220 TEST(SeqNumUnwrapper, ForwardWrap) {
221   SeqNumUnwrapper<uint8_t> unwrapper;
222   EXPECT_EQ(255, unwrapper.Unwrap(255));
223   EXPECT_EQ(256, unwrapper.Unwrap(0));
224 }
225 
TEST(SeqNumUnwrapper,ForwardWrapWithDivisor)226 TEST(SeqNumUnwrapper, ForwardWrapWithDivisor) {
227   SeqNumUnwrapper<uint8_t, 33> unwrapper;
228   EXPECT_EQ(30, unwrapper.Unwrap(30));
229   EXPECT_EQ(36, unwrapper.Unwrap(3));
230 }
231 
TEST(SeqNumUnwrapper,BackWardWrap)232 TEST(SeqNumUnwrapper, BackWardWrap) {
233   SeqNumUnwrapper<uint8_t> unwrapper;
234   EXPECT_EQ(0, unwrapper.Unwrap(0));
235   EXPECT_EQ(-2, unwrapper.Unwrap(254));
236 }
237 
TEST(SeqNumUnwrapper,BackWardWrapWithDivisor)238 TEST(SeqNumUnwrapper, BackWardWrapWithDivisor) {
239   SeqNumUnwrapper<uint8_t, 33> unwrapper;
240   EXPECT_EQ(0, unwrapper.Unwrap(0));
241   EXPECT_EQ(-2, unwrapper.Unwrap(31));
242 }
243 
TEST(SeqNumUnwrapper,Unwrap)244 TEST(SeqNumUnwrapper, Unwrap) {
245   SeqNumUnwrapper<uint16_t> unwrapper;
246   const uint16_t kMax = std::numeric_limits<uint16_t>::max();
247   const uint16_t kMaxDist = kMax / 2 + 1;
248 
249   EXPECT_EQ(0, unwrapper.Unwrap(0));
250   EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist));
251   EXPECT_EQ(0, unwrapper.Unwrap(0));
252 
253   EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist));
254   EXPECT_EQ(kMax, unwrapper.Unwrap(kMax));
255   EXPECT_EQ(kMax + 1, unwrapper.Unwrap(0));
256   EXPECT_EQ(kMax, unwrapper.Unwrap(kMax));
257   EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist));
258   EXPECT_EQ(0, unwrapper.Unwrap(0));
259 }
260 
TEST(SeqNumUnwrapper,UnwrapOddDivisor)261 TEST(SeqNumUnwrapper, UnwrapOddDivisor) {
262   SeqNumUnwrapper<uint8_t, 11> unwrapper;
263 
264   EXPECT_EQ(10, unwrapper.Unwrap(10));
265   EXPECT_EQ(11, unwrapper.Unwrap(0));
266   EXPECT_EQ(16, unwrapper.Unwrap(5));
267   EXPECT_EQ(21, unwrapper.Unwrap(10));
268   EXPECT_EQ(22, unwrapper.Unwrap(0));
269   EXPECT_EQ(17, unwrapper.Unwrap(6));
270   EXPECT_EQ(12, unwrapper.Unwrap(1));
271   EXPECT_EQ(7, unwrapper.Unwrap(7));
272   EXPECT_EQ(2, unwrapper.Unwrap(2));
273   EXPECT_EQ(0, unwrapper.Unwrap(0));
274 }
275 
TEST(SeqNumUnwrapper,ManyForwardWraps)276 TEST(SeqNumUnwrapper, ManyForwardWraps) {
277   const int kLargeNumber = 4711;
278   const int kMaxStep = kLargeNumber / 2;
279   const int kNumWraps = 100;
280   SeqNumUnwrapper<uint16_t, kLargeNumber> unwrapper;
281 
282   uint16_t next_unwrap = 0;
283   int64_t expected = 0;
284   for (int i = 0; i < kNumWraps * 2 + 1; ++i) {
285     EXPECT_EQ(expected, unwrapper.Unwrap(next_unwrap));
286     expected += kMaxStep;
287     next_unwrap = (next_unwrap + kMaxStep) % kLargeNumber;
288   }
289 }
290 
TEST(SeqNumUnwrapper,ManyBackwardWraps)291 TEST(SeqNumUnwrapper, ManyBackwardWraps) {
292   const int kLargeNumber = 4711;
293   const int kMaxStep = kLargeNumber / 2;
294   const int kNumWraps = 100;
295   SeqNumUnwrapper<uint16_t, kLargeNumber> unwrapper;
296 
297   uint16_t next_unwrap = 0;
298   int64_t expected = 0;
299   for (uint16_t i = 0; i < kNumWraps * 2 + 1; ++i) {
300     EXPECT_EQ(expected, unwrapper.Unwrap(next_unwrap));
301     expected -= kMaxStep;
302     next_unwrap = (next_unwrap + kMaxStep + 1) % kLargeNumber;
303   }
304 }
305 
306 }  // namespace webrtc
307