1 /*
2 * Copyright (c) 2019 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 "modules/rtp_rtcp/source/rtp_sequence_number_map.h"
12
13 #include <algorithm>
14 #include <iterator>
15 #include <limits>
16
17 #include "absl/algorithm/container.h"
18 #include "rtc_base/checks.h"
19 #include "rtc_base/logging.h"
20 #include "rtc_base/numerics/sequence_number_util.h"
21
22 namespace webrtc {
23
RtpSequenceNumberMap(size_t max_entries)24 RtpSequenceNumberMap::RtpSequenceNumberMap(size_t max_entries)
25 : max_entries_(max_entries) {
26 RTC_DCHECK_GT(max_entries_, 4); // See code paring down to |max_entries_|.
27 RTC_DCHECK_LE(max_entries_, 1 << 15);
28 }
29
30 RtpSequenceNumberMap::~RtpSequenceNumberMap() = default;
31
InsertPacket(uint16_t sequence_number,Info info)32 void RtpSequenceNumberMap::InsertPacket(uint16_t sequence_number, Info info) {
33 RTC_DCHECK(associations_.size() < 2 ||
34 AheadOf(associations_.back().sequence_number,
35 associations_.front().sequence_number));
36
37 if (associations_.empty()) {
38 associations_.emplace_back(sequence_number, info);
39 return;
40 }
41
42 if (AheadOrAt(sequence_number, associations_.front().sequence_number) &&
43 AheadOrAt(associations_.back().sequence_number, sequence_number)) {
44 // The sequence number has wrapped around and is within the range
45 // currently held by |associations_| - we should invalidate all entries.
46 RTC_LOG(LS_WARNING) << "Sequence number wrapped-around unexpectedly.";
47 associations_.clear();
48 associations_.emplace_back(sequence_number, info);
49 return;
50 }
51
52 std::deque<Association>::iterator erase_to = associations_.begin();
53
54 RTC_DCHECK_LE(associations_.size(), max_entries_);
55 if (associations_.size() == max_entries_) {
56 // Pare down the container so that inserting some additional elements
57 // would not exceed the maximum size.
58 const size_t new_size = 3 * max_entries_ / 4;
59 erase_to = std::next(erase_to, max_entries_ - new_size);
60 }
61
62 // It is guaranteed that |associations_| can be split into two partitions,
63 // either partition possibly empty, such that:
64 // * In the first partition, all elements are AheadOf the new element.
65 // This is the partition of the obsolete elements.
66 // * In the second partition, the new element is AheadOf all the elements.
67 // The elements of this partition may stay.
68 auto cmp = [](const Association& a, uint16_t sequence_number) {
69 return AheadOf(a.sequence_number, sequence_number);
70 };
71 RTC_DCHECK(erase_to != associations_.end());
72 erase_to =
73 std::lower_bound(erase_to, associations_.end(), sequence_number, cmp);
74 associations_.erase(associations_.begin(), erase_to);
75
76 associations_.emplace_back(sequence_number, info);
77
78 RTC_DCHECK(associations_.size() == 1 ||
79 AheadOf(associations_.back().sequence_number,
80 associations_.front().sequence_number));
81 }
82
InsertFrame(uint16_t first_sequence_number,size_t packet_count,uint32_t timestamp)83 void RtpSequenceNumberMap::InsertFrame(uint16_t first_sequence_number,
84 size_t packet_count,
85 uint32_t timestamp) {
86 RTC_DCHECK_GT(packet_count, 0);
87 RTC_DCHECK_LE(packet_count, std::numeric_limits<size_t>::max());
88
89 for (size_t i = 0; i < packet_count; ++i) {
90 const bool is_first = (i == 0);
91 const bool is_last = (i == packet_count - 1);
92 InsertPacket(static_cast<uint16_t>(first_sequence_number + i),
93 Info(timestamp, is_first, is_last));
94 }
95 }
96
Get(uint16_t sequence_number) const97 absl::optional<RtpSequenceNumberMap::Info> RtpSequenceNumberMap::Get(
98 uint16_t sequence_number) const {
99 // To make the binary search easier to understand, we use the fact that
100 // adding a constant offset to all elements, as well as to the searched
101 // element, does not change the relative ordering. This way, we can find
102 // an offset that would make all of the elements strictly ascending according
103 // to normal integer comparison.
104 // Finding such an offset is easy - the offset that would map the oldest
105 // element to 0 would serve this purpose.
106
107 if (associations_.empty()) {
108 return absl::nullopt;
109 }
110
111 const uint16_t offset =
112 static_cast<uint16_t>(0) - associations_.front().sequence_number;
113
114 auto cmp = [offset](const Association& a, uint16_t sequence_number) {
115 return static_cast<uint16_t>(a.sequence_number + offset) <
116 static_cast<uint16_t>(sequence_number + offset);
117 };
118 const auto elem = absl::c_lower_bound(associations_, sequence_number, cmp);
119
120 return elem != associations_.end() && elem->sequence_number == sequence_number
121 ? absl::optional<Info>(elem->info)
122 : absl::nullopt;
123 }
124
AssociationCountForTesting() const125 size_t RtpSequenceNumberMap::AssociationCountForTesting() const {
126 return associations_.size();
127 }
128
129 } // namespace webrtc
130