1 /*
2 * Copyright (c) 2021 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 #include "modules/remote_bitrate_estimator/packet_arrival_map.h"
11
12 #include "test/gmock.h"
13 #include "test/gtest.h"
14
15 namespace webrtc {
16 namespace {
17
TEST(PacketArrivalMapTest,IsConsistentWhenEmpty)18 TEST(PacketArrivalMapTest, IsConsistentWhenEmpty) {
19 PacketArrivalTimeMap map;
20
21 EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
22 EXPECT_FALSE(map.has_received(0));
23 EXPECT_EQ(map.clamp(-5), 0);
24 EXPECT_EQ(map.clamp(5), 0);
25 }
26
TEST(PacketArrivalMapTest,InsertsFirstItemIntoMap)27 TEST(PacketArrivalMapTest, InsertsFirstItemIntoMap) {
28 PacketArrivalTimeMap map;
29
30 map.AddPacket(42, Timestamp::Millis(10));
31 EXPECT_EQ(map.begin_sequence_number(), 42);
32 EXPECT_EQ(map.end_sequence_number(), 43);
33
34 EXPECT_FALSE(map.has_received(41));
35 EXPECT_TRUE(map.has_received(42));
36 EXPECT_FALSE(map.has_received(44));
37
38 EXPECT_EQ(map.clamp(-100), 42);
39 EXPECT_EQ(map.clamp(42), 42);
40 EXPECT_EQ(map.clamp(100), 43);
41 }
42
TEST(PacketArrivalMapTest,InsertsWithGaps)43 TEST(PacketArrivalMapTest, InsertsWithGaps) {
44 PacketArrivalTimeMap map;
45
46 map.AddPacket(42, Timestamp::Zero());
47 map.AddPacket(45, Timestamp::Millis(11));
48 EXPECT_EQ(map.begin_sequence_number(), 42);
49 EXPECT_EQ(map.end_sequence_number(), 46);
50
51 EXPECT_FALSE(map.has_received(41));
52 EXPECT_TRUE(map.has_received(42));
53 EXPECT_FALSE(map.has_received(43));
54 EXPECT_FALSE(map.has_received(44));
55 EXPECT_TRUE(map.has_received(45));
56 EXPECT_FALSE(map.has_received(46));
57
58 EXPECT_EQ(map.get(42), Timestamp::Zero());
59 EXPECT_LT(map.get(43), Timestamp::Zero());
60 EXPECT_LT(map.get(44), Timestamp::Zero());
61 EXPECT_EQ(map.get(45), Timestamp::Millis(11));
62
63 EXPECT_EQ(map.clamp(-100), 42);
64 EXPECT_EQ(map.clamp(44), 44);
65 EXPECT_EQ(map.clamp(100), 46);
66 }
67
TEST(PacketArrivalMapTest,FindNextAtOrAfterWithGaps)68 TEST(PacketArrivalMapTest, FindNextAtOrAfterWithGaps) {
69 PacketArrivalTimeMap map;
70
71 map.AddPacket(42, Timestamp::Zero());
72 map.AddPacket(45, Timestamp::Millis(11));
73 EXPECT_EQ(map.begin_sequence_number(), 42);
74 EXPECT_EQ(map.end_sequence_number(), 46);
75
76 PacketArrivalTimeMap::PacketArrivalTime packet = map.FindNextAtOrAfter(42);
77 EXPECT_EQ(packet.arrival_time, Timestamp::Zero());
78 EXPECT_EQ(packet.sequence_number, 42);
79
80 packet = map.FindNextAtOrAfter(43);
81 EXPECT_EQ(packet.arrival_time, Timestamp::Millis(11));
82 EXPECT_EQ(packet.sequence_number, 45);
83 }
84
TEST(PacketArrivalMapTest,InsertsWithinBuffer)85 TEST(PacketArrivalMapTest, InsertsWithinBuffer) {
86 PacketArrivalTimeMap map;
87
88 map.AddPacket(42, Timestamp::Millis(10));
89 map.AddPacket(45, Timestamp::Millis(11));
90
91 map.AddPacket(43, Timestamp::Millis(12));
92 map.AddPacket(44, Timestamp::Millis(13));
93
94 EXPECT_EQ(map.begin_sequence_number(), 42);
95 EXPECT_EQ(map.end_sequence_number(), 46);
96
97 EXPECT_FALSE(map.has_received(41));
98 EXPECT_TRUE(map.has_received(42));
99 EXPECT_TRUE(map.has_received(43));
100 EXPECT_TRUE(map.has_received(44));
101 EXPECT_TRUE(map.has_received(45));
102 EXPECT_FALSE(map.has_received(46));
103
104 EXPECT_EQ(map.get(42), Timestamp::Millis(10));
105 EXPECT_EQ(map.get(43), Timestamp::Millis(12));
106 EXPECT_EQ(map.get(44), Timestamp::Millis(13));
107 EXPECT_EQ(map.get(45), Timestamp::Millis(11));
108 }
109
TEST(PacketArrivalMapTest,GrowsBufferAndRemoveOld)110 TEST(PacketArrivalMapTest, GrowsBufferAndRemoveOld) {
111 PacketArrivalTimeMap map;
112
113 constexpr int64_t kLargeSeq = 42 + PacketArrivalTimeMap::kMaxNumberOfPackets;
114 map.AddPacket(42, Timestamp::Millis(10));
115 map.AddPacket(43, Timestamp::Millis(11));
116 map.AddPacket(44, Timestamp::Millis(12));
117 map.AddPacket(45, Timestamp::Millis(13));
118 map.AddPacket(kLargeSeq, Timestamp::Millis(12));
119
120 EXPECT_EQ(map.begin_sequence_number(), 43);
121 EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
122 EXPECT_EQ(map.end_sequence_number() - map.begin_sequence_number(),
123 PacketArrivalTimeMap::kMaxNumberOfPackets);
124
125 EXPECT_FALSE(map.has_received(41));
126 EXPECT_FALSE(map.has_received(42));
127 EXPECT_TRUE(map.has_received(43));
128 EXPECT_TRUE(map.has_received(44));
129 EXPECT_TRUE(map.has_received(45));
130 EXPECT_FALSE(map.has_received(46));
131 EXPECT_TRUE(map.has_received(kLargeSeq));
132 EXPECT_FALSE(map.has_received(kLargeSeq + 1));
133 }
134
TEST(PacketArrivalMapTest,GrowsBufferAndRemoveOldTrimsBeginning)135 TEST(PacketArrivalMapTest, GrowsBufferAndRemoveOldTrimsBeginning) {
136 PacketArrivalTimeMap map;
137
138 constexpr int64_t kLargeSeq = 42 + PacketArrivalTimeMap::kMaxNumberOfPackets;
139 map.AddPacket(42, Timestamp::Millis(10));
140 // Missing: 43, 44
141 map.AddPacket(45, Timestamp::Millis(13));
142 map.AddPacket(kLargeSeq, Timestamp::Millis(12));
143
144 EXPECT_EQ(map.begin_sequence_number(), 45);
145 EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
146
147 EXPECT_FALSE(map.has_received(44));
148 EXPECT_TRUE(map.has_received(45));
149 EXPECT_FALSE(map.has_received(46));
150 EXPECT_TRUE(map.has_received(kLargeSeq));
151 EXPECT_FALSE(map.has_received(kLargeSeq + 1));
152 }
153
TEST(PacketArrivalMapTest,SequenceNumberJumpsDeletesAll)154 TEST(PacketArrivalMapTest, SequenceNumberJumpsDeletesAll) {
155 PacketArrivalTimeMap map;
156
157 constexpr int64_t kLargeSeq =
158 42 + 2 * PacketArrivalTimeMap::kMaxNumberOfPackets;
159 map.AddPacket(42, Timestamp::Millis(10));
160 map.AddPacket(kLargeSeq, Timestamp::Millis(12));
161
162 EXPECT_EQ(map.begin_sequence_number(), kLargeSeq);
163 EXPECT_EQ(map.end_sequence_number(), kLargeSeq + 1);
164
165 EXPECT_FALSE(map.has_received(42));
166 EXPECT_TRUE(map.has_received(kLargeSeq));
167 EXPECT_FALSE(map.has_received(kLargeSeq + 1));
168 }
169
TEST(PacketArrivalMapTest,ExpandsBeforeBeginning)170 TEST(PacketArrivalMapTest, ExpandsBeforeBeginning) {
171 PacketArrivalTimeMap map;
172
173 map.AddPacket(42, Timestamp::Millis(10));
174 map.AddPacket(-1000, Timestamp::Millis(13));
175
176 EXPECT_EQ(map.begin_sequence_number(), -1000);
177 EXPECT_EQ(map.end_sequence_number(), 43);
178
179 EXPECT_FALSE(map.has_received(-1001));
180 EXPECT_TRUE(map.has_received(-1000));
181 EXPECT_FALSE(map.has_received(-999));
182 EXPECT_TRUE(map.has_received(42));
183 EXPECT_FALSE(map.has_received(43));
184 }
185
TEST(PacketArrivalMapTest,ExpandingBeforeBeginningKeepsReceived)186 TEST(PacketArrivalMapTest, ExpandingBeforeBeginningKeepsReceived) {
187 PacketArrivalTimeMap map;
188
189 map.AddPacket(42, Timestamp::Millis(10));
190 constexpr int64_t kSmallSeq =
191 static_cast<int64_t>(42) - 2 * PacketArrivalTimeMap::kMaxNumberOfPackets;
192 map.AddPacket(kSmallSeq, Timestamp::Millis(13));
193
194 EXPECT_EQ(map.begin_sequence_number(), 42);
195 EXPECT_EQ(map.end_sequence_number(), 43);
196 }
197
TEST(PacketArrivalMapTest,ErasesToRemoveElements)198 TEST(PacketArrivalMapTest, ErasesToRemoveElements) {
199 PacketArrivalTimeMap map;
200
201 map.AddPacket(42, Timestamp::Millis(10));
202 map.AddPacket(43, Timestamp::Millis(11));
203 map.AddPacket(44, Timestamp::Millis(12));
204 map.AddPacket(45, Timestamp::Millis(13));
205
206 map.EraseTo(44);
207
208 EXPECT_EQ(map.begin_sequence_number(), 44);
209 EXPECT_EQ(map.end_sequence_number(), 46);
210
211 EXPECT_FALSE(map.has_received(43));
212 EXPECT_TRUE(map.has_received(44));
213 EXPECT_TRUE(map.has_received(45));
214 EXPECT_FALSE(map.has_received(46));
215 }
216
TEST(PacketArrivalMapTest,ErasesInEmptyMap)217 TEST(PacketArrivalMapTest, ErasesInEmptyMap) {
218 PacketArrivalTimeMap map;
219
220 EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
221
222 map.EraseTo(map.end_sequence_number());
223 EXPECT_EQ(map.begin_sequence_number(), map.end_sequence_number());
224 }
225
TEST(PacketArrivalMapTest,IsTolerantToWrongArgumentsForErase)226 TEST(PacketArrivalMapTest, IsTolerantToWrongArgumentsForErase) {
227 PacketArrivalTimeMap map;
228
229 map.AddPacket(42, Timestamp::Millis(10));
230 map.AddPacket(43, Timestamp::Millis(11));
231
232 map.EraseTo(1);
233
234 EXPECT_EQ(map.begin_sequence_number(), 42);
235 EXPECT_EQ(map.end_sequence_number(), 44);
236
237 map.EraseTo(100);
238
239 EXPECT_EQ(map.begin_sequence_number(), 44);
240 EXPECT_EQ(map.end_sequence_number(), 44);
241 }
242
TEST(PacketArrivalMapTest,EraseAllRemembersBeginningSeqNbr)243 TEST(PacketArrivalMapTest, EraseAllRemembersBeginningSeqNbr) {
244 PacketArrivalTimeMap map;
245
246 map.AddPacket(42, Timestamp::Millis(10));
247 map.AddPacket(43, Timestamp::Millis(11));
248 map.AddPacket(44, Timestamp::Millis(12));
249 map.AddPacket(45, Timestamp::Millis(13));
250
251 map.EraseTo(46);
252
253 map.AddPacket(50, Timestamp::Millis(10));
254
255 EXPECT_EQ(map.begin_sequence_number(), 46);
256 EXPECT_EQ(map.end_sequence_number(), 51);
257
258 EXPECT_FALSE(map.has_received(45));
259 EXPECT_FALSE(map.has_received(46));
260 EXPECT_FALSE(map.has_received(47));
261 EXPECT_FALSE(map.has_received(48));
262 EXPECT_FALSE(map.has_received(49));
263 EXPECT_TRUE(map.has_received(50));
264 EXPECT_FALSE(map.has_received(51));
265 }
266
TEST(PacketArrivalMapTest,EraseToMissingSequenceNumber)267 TEST(PacketArrivalMapTest, EraseToMissingSequenceNumber) {
268 PacketArrivalTimeMap map;
269
270 map.AddPacket(37, Timestamp::Millis(10));
271 map.AddPacket(39, Timestamp::Millis(11));
272 map.AddPacket(40, Timestamp::Millis(12));
273 map.AddPacket(41, Timestamp::Millis(13));
274
275 map.EraseTo(38);
276
277 map.AddPacket(42, Timestamp::Millis(40));
278
279 EXPECT_EQ(map.begin_sequence_number(), 38);
280 EXPECT_EQ(map.end_sequence_number(), 43);
281
282 EXPECT_FALSE(map.has_received(37));
283 EXPECT_FALSE(map.has_received(38));
284 EXPECT_TRUE(map.has_received(39));
285 EXPECT_TRUE(map.has_received(40));
286 EXPECT_TRUE(map.has_received(41));
287 EXPECT_TRUE(map.has_received(42));
288 }
289
290 } // namespace
291 } // namespace webrtc
292