diff options
Diffstat (limited to 'third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc')
-rw-r--r-- | third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc | 164 |
1 files changed, 164 insertions, 0 deletions
diff --git a/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc new file mode 100644 index 0000000000..182297d303 --- /dev/null +++ b/third_party/libwebrtc/modules/remote_bitrate_estimator/packet_arrival_map.cc @@ -0,0 +1,164 @@ +/* + * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ +#include "modules/remote_bitrate_estimator/packet_arrival_map.h" + +#include <algorithm> +#include <cstdint> + +#include "api/units/timestamp.h" +#include "rtc_base/checks.h" + +namespace webrtc { + +void PacketArrivalTimeMap::AddPacket(int64_t sequence_number, + Timestamp arrival_time) { + RTC_DCHECK_GE(arrival_time, Timestamp::Zero()); + if (!has_seen_packet()) { + // First packet. + Reallocate(kMinCapacity); + begin_sequence_number_ = sequence_number; + end_sequence_number_ = sequence_number + 1; + arrival_times_[Index(sequence_number)] = arrival_time; + return; + } + + if (sequence_number >= begin_sequence_number() && + sequence_number < end_sequence_number()) { + // The packet is within the buffer - no need to expand it. + arrival_times_[Index(sequence_number)] = arrival_time; + return; + } + + if (sequence_number < begin_sequence_number()) { + // The packet goes before the current buffer. Expand to add packet, but only + // if it fits within kMaxNumberOfPackets. + int64_t new_size = end_sequence_number() - sequence_number; + if (new_size > kMaxNumberOfPackets) { + // Don't expand the buffer further, as that would remove newly received + // packets. + return; + } + AdjustToSize(new_size); + + arrival_times_[Index(sequence_number)] = arrival_time; + SetNotReceived(sequence_number + 1, begin_sequence_number_); + begin_sequence_number_ = sequence_number; + return; + } + + // The packet goes after the buffer. + RTC_DCHECK_GE(sequence_number, end_sequence_number_); + int64_t new_end_sequence_number = sequence_number + 1; + + if (new_end_sequence_number >= end_sequence_number_ + kMaxNumberOfPackets) { + // All old packets have to be removed. + begin_sequence_number_ = sequence_number; + end_sequence_number_ = new_end_sequence_number; + arrival_times_[Index(sequence_number)] = arrival_time; + return; + } + + if (begin_sequence_number_ < new_end_sequence_number - kMaxNumberOfPackets) { + // Remove oldest entries + begin_sequence_number_ = new_end_sequence_number - kMaxNumberOfPackets; + RTC_DCHECK_GT(end_sequence_number_, begin_sequence_number_); + } + + AdjustToSize(new_end_sequence_number - begin_sequence_number_); + + // Packets can be received out-of-order. If this isn't the next expected + // packet, add enough placeholders to fill the gap. + SetNotReceived(end_sequence_number_, sequence_number); + end_sequence_number_ = new_end_sequence_number; + arrival_times_[Index(sequence_number)] = arrival_time; +} + +void PacketArrivalTimeMap::SetNotReceived( + int64_t begin_sequence_number_inclusive, + int64_t end_sequence_number_exclusive) { + static constexpr Timestamp value = Timestamp::MinusInfinity(); + + int begin_index = Index(begin_sequence_number_inclusive); + int end_index = Index(end_sequence_number_exclusive); + + if (begin_index <= end_index) { + // Entries to clear are in single block: + // [......{-----}....] + std::fill(arrival_times_.get() + begin_index, + arrival_times_.get() + end_index, value); + } else { + // Entries to clear span across arrival_times_ border: + // [--}..........{---] + std::fill(arrival_times_.get() + begin_index, + arrival_times_.get() + capacity(), value); + std::fill(arrival_times_.get(), arrival_times_.get() + end_index, value); + } +} + +void PacketArrivalTimeMap::RemoveOldPackets(int64_t sequence_number, + Timestamp arrival_time_limit) { + int64_t check_to = std::min(sequence_number, end_sequence_number_); + while (begin_sequence_number_ < check_to && + arrival_times_[Index(begin_sequence_number_)] <= arrival_time_limit) { + ++begin_sequence_number_; + } + AdjustToSize(end_sequence_number_ - begin_sequence_number_); +} + +void PacketArrivalTimeMap::EraseTo(int64_t sequence_number) { + if (sequence_number < begin_sequence_number_) { + return; + } + if (sequence_number >= end_sequence_number_) { + // Erase all. + begin_sequence_number_ = end_sequence_number_; + return; + } + // Remove some. + begin_sequence_number_ = sequence_number; + AdjustToSize(end_sequence_number_ - begin_sequence_number_); +} + +void PacketArrivalTimeMap::AdjustToSize(int new_size) { + if (new_size > capacity()) { + int new_capacity = capacity(); + while (new_capacity < new_size) + new_capacity *= 2; + Reallocate(new_capacity); + } + if (capacity() > std::max(kMinCapacity, 4 * new_size)) { + int new_capacity = capacity(); + while (new_capacity > 2 * std::max(new_size, kMinCapacity)) { + new_capacity /= 2; + } + Reallocate(new_capacity); + } + RTC_DCHECK_LE(new_size, capacity()); +} + +void PacketArrivalTimeMap::Reallocate(int new_capacity) { + int new_capacity_minus_1 = new_capacity - 1; + // Check capacity is a power of 2. + RTC_DCHECK_EQ(new_capacity & new_capacity_minus_1, 0); + // Create uninitialized memory. + // All valid entries should be set by `AddPacket` before use. + void* raw = operator new[](new_capacity * sizeof(Timestamp)); + Timestamp* new_buffer = static_cast<Timestamp*>(raw); + + for (int64_t sequence_number = begin_sequence_number_; + sequence_number < end_sequence_number_; ++sequence_number) { + new_buffer[sequence_number & new_capacity_minus_1] = + arrival_times_[sequence_number & capacity_minus_1_]; + } + arrival_times_.reset(new_buffer); + capacity_minus_1_ = new_capacity_minus_1; +} + +} // namespace webrtc |