blob: 2a4ea922cf94891670d2db44b94fbae43c2895f2 [file] [log] [blame]
/*
* 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/audio_processing/agc/clipping_predictor_evaluator.h"
#include <algorithm>
#include "rtc_base/checks.h"
#include "rtc_base/logging.h"
namespace webrtc {
namespace {
// Returns the index of the oldest item in the ring buffer for a non-empty
// ring buffer with give `size`, `tail` index and `capacity`.
int OldestExpectedDetectionIndex(int size, int tail, int capacity) {
RTC_DCHECK_GT(size, 0);
return tail - size + (tail < size ? capacity : 0);
}
} // namespace
ClippingPredictorEvaluator::ClippingPredictorEvaluator(int history_size)
: history_size_(history_size),
ring_buffer_capacity_(history_size + 1),
ring_buffer_(ring_buffer_capacity_),
true_positives_(0),
true_negatives_(0),
false_positives_(0),
false_negatives_(0) {
RTC_DCHECK_GT(history_size_, 0);
Reset();
}
ClippingPredictorEvaluator::~ClippingPredictorEvaluator() = default;
absl::optional<int> ClippingPredictorEvaluator::Observe(
bool clipping_detected,
bool clipping_predicted) {
RTC_DCHECK_GE(ring_buffer_size_, 0);
RTC_DCHECK_LE(ring_buffer_size_, ring_buffer_capacity_);
RTC_DCHECK_GE(ring_buffer_tail_, 0);
RTC_DCHECK_LT(ring_buffer_tail_, ring_buffer_capacity_);
DecreaseTimesToLive();
if (clipping_predicted) {
// TODO(bugs.webrtc.org/12874): Use designated initializers one fixed.
Push(/*expected_detection=*/{/*ttl=*/history_size_, /*detected=*/false});
}
// Clipping is expected if there are expected detections regardless of
// whether all the expected detections have been previously matched - i.e.,
// `ExpectedDetection::detected` is true.
const bool clipping_expected = ring_buffer_size_ > 0;
absl::optional<int> prediction_interval;
if (clipping_expected && clipping_detected) {
prediction_interval = FindEarliestPredictionInterval();
// Add a true positive for each unexpired expected detection.
const int num_modified_items = MarkExpectedDetectionAsDetected();
true_positives_ += num_modified_items;
RTC_DCHECK(prediction_interval.has_value() || num_modified_items == 0);
RTC_DCHECK(!prediction_interval.has_value() || num_modified_items > 0);
} else if (clipping_expected && !clipping_detected) {
// Add a false positive if there is one expected detection that has expired
// and that has never been matched before. Note that there is at most one
// unmatched expired detection.
if (HasExpiredUnmatchedExpectedDetection()) {
false_positives_++;
}
} else if (!clipping_expected && clipping_detected) {
false_negatives_++;
} else {
RTC_DCHECK(!clipping_expected && !clipping_detected);
true_negatives_++;
}
return prediction_interval;
}
void ClippingPredictorEvaluator::Reset() {
// Empty the ring buffer of expected detections.
ring_buffer_tail_ = 0;
ring_buffer_size_ = 0;
}
// Cost: O(1).
void ClippingPredictorEvaluator::Push(ExpectedDetection value) {
ring_buffer_[ring_buffer_tail_] = value;
ring_buffer_tail_++;
if (ring_buffer_tail_ == ring_buffer_capacity_) {
ring_buffer_tail_ = 0;
}
ring_buffer_size_ = std::min(ring_buffer_capacity_, ring_buffer_size_ + 1);
}
// Cost: O(N).
void ClippingPredictorEvaluator::DecreaseTimesToLive() {
bool expired_found = false;
for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_;
++i) {
int index = i >= 0 ? i : ring_buffer_capacity_ + i;
RTC_DCHECK_GE(index, 0);
RTC_DCHECK_LT(index, ring_buffer_.size());
RTC_DCHECK_GE(ring_buffer_[index].ttl, 0);
if (ring_buffer_[index].ttl == 0) {
RTC_DCHECK(!expired_found)
<< "There must be at most one expired item in the ring buffer.";
expired_found = true;
RTC_DCHECK_EQ(index, OldestExpectedDetectionIndex(ring_buffer_size_,
ring_buffer_tail_,
ring_buffer_capacity_))
<< "The expired item must be the oldest in the ring buffer.";
}
ring_buffer_[index].ttl--;
}
if (expired_found) {
ring_buffer_size_--;
}
}
// Cost: O(N).
absl::optional<int> ClippingPredictorEvaluator::FindEarliestPredictionInterval()
const {
absl::optional<int> prediction_interval;
for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_;
++i) {
int index = i >= 0 ? i : ring_buffer_capacity_ + i;
RTC_DCHECK_GE(index, 0);
RTC_DCHECK_LT(index, ring_buffer_.size());
if (!ring_buffer_[index].detected) {
prediction_interval = std::max(prediction_interval.value_or(0),
history_size_ - ring_buffer_[index].ttl);
}
}
return prediction_interval;
}
// Cost: O(N).
int ClippingPredictorEvaluator::MarkExpectedDetectionAsDetected() {
int num_modified_items = 0;
for (int i = ring_buffer_tail_ - ring_buffer_size_; i < ring_buffer_tail_;
++i) {
int index = i >= 0 ? i : ring_buffer_capacity_ + i;
RTC_DCHECK_GE(index, 0);
RTC_DCHECK_LT(index, ring_buffer_.size());
if (!ring_buffer_[index].detected) {
num_modified_items++;
}
ring_buffer_[index].detected = true;
}
return num_modified_items;
}
// Cost: O(1).
bool ClippingPredictorEvaluator::HasExpiredUnmatchedExpectedDetection() const {
if (ring_buffer_size_ == 0) {
return false;
}
// If an expired item, that is `ttl` equal to 0, exists, it must be the
// oldest.
const int oldest_index = OldestExpectedDetectionIndex(
ring_buffer_size_, ring_buffer_tail_, ring_buffer_capacity_);
RTC_DCHECK_GE(oldest_index, 0);
RTC_DCHECK_LT(oldest_index, ring_buffer_.size());
return ring_buffer_[oldest_index].ttl == 0 &&
!ring_buffer_[oldest_index].detected;
}
} // namespace webrtc