Add WindowedMinFilter to rtc_base/numerics
The filter returns the min value within a fixed size window.
Bug: webrtc:447037083
Change-Id: If42ff0e19af8b4a6aaf8f4addc11e326b4244e43
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/411760
Reviewed-by: Danil Chapovalov <danilchap@webrtc.org>
Reviewed-by: Harald Alvestrand <hta@webrtc.org>
Commit-Queue: Per Kjellander <perkj@webrtc.org>
Cr-Commit-Position: refs/heads/main@{#45741}
diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index ce7896b..49245ac 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -737,6 +737,11 @@
]
}
+rtc_library("windowed_min_filter") {
+ sources = [ "numerics/windowed_min_filter.h" ]
+ deps = [ ":checks" ]
+}
+
rtc_library("rtc_numerics") {
sources = [
"numerics/event_based_exponential_moving_average.cc",
@@ -2220,13 +2225,17 @@
"numerics/running_statistics_unittest.cc",
"numerics/sequence_number_unwrapper_unittest.cc",
"numerics/sequence_number_util_unittest.cc",
+ "numerics/windowed_min_filter_unittest.cc",
]
deps = [
":mod_ops",
":rtc_numerics",
":timeutils",
+ ":windowed_min_filter",
+ "../api/units:time_delta",
"../test:test_main",
"../test:test_support",
+ "//testing/gtest",
"//third_party/abseil-cpp/absl/algorithm:container",
]
}
diff --git a/rtc_base/numerics/windowed_min_filter.h b/rtc_base/numerics/windowed_min_filter.h
new file mode 100644
index 0000000..42f4fc1
--- /dev/null
+++ b/rtc_base/numerics/windowed_min_filter.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright (c) 2025 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.
+ */
+
+#ifndef RTC_BASE_NUMERICS_WINDOWED_MIN_FILTER_H_
+#define RTC_BASE_NUMERICS_WINDOWED_MIN_FILTER_H_
+
+#include <deque>
+
+#include "rtc_base/checks.h"
+
+namespace webrtc {
+
+template <typename V>
+class WindowedMinFilter {
+ public:
+ explicit WindowedMinFilter(int window_length) : max_size_(window_length) {
+ RTC_DCHECK_GT(window_length, 1);
+ }
+
+ void Insert(V value) {
+ if (!min_values_.empty()) {
+ if (min_values_.front().index == index_) {
+ // Min value is too old.
+ min_values_.pop_front();
+ }
+
+ // If value <= min_values_.front().value, value is the minimum value and
+ // we can forget all other. The alternative had been to always
+ // check the back value, but then we would also have to check for
+ // empty.
+ if (min_values_.front().value >= value) {
+ min_values_.clear();
+ } else {
+ while (min_values_.back().value >= value) {
+ min_values_.pop_back();
+ }
+ }
+ }
+ RTC_DCHECK_LT(min_values_.size(), max_size_);
+ min_values_.push_back({.value = value, .index = index_});
+ index_ = (index_ + 1) % max_size_;
+ }
+
+ // Returns the min value within the window. If no value has been inserted,
+ // returns the default value of V.
+ V GetMin() const {
+ if (min_values_.empty()) {
+ return V();
+ }
+ return min_values_.front().value;
+ }
+
+ void Reset() {
+ min_values_.clear();
+ index_ = 0;
+ }
+
+ private:
+ const int max_size_;
+ struct ValueAndIndex {
+ V value;
+ int index;
+ };
+
+ int index_ = 0;
+ std::deque<ValueAndIndex> min_values_;
+};
+
+} // namespace webrtc
+
+#endif // RTC_BASE_NUMERICS_WINDOWED_MIN_FILTER_H_
diff --git a/rtc_base/numerics/windowed_min_filter_unittest.cc b/rtc_base/numerics/windowed_min_filter_unittest.cc
new file mode 100644
index 0000000..ce6d8ae
--- /dev/null
+++ b/rtc_base/numerics/windowed_min_filter_unittest.cc
@@ -0,0 +1,93 @@
+/*
+ * Copyright (c) 2025 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 "rtc_base/numerics/windowed_min_filter.h"
+
+#include <string>
+
+#include "api/units/time_delta.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+namespace {
+
+TEST(WindowedMinFilterTest, EmptyFilterReturnZero) {
+ WindowedMinFilter<TimeDelta> filter(/*window_length=*/3);
+ EXPECT_EQ(filter.GetMin(), TimeDelta::Zero());
+}
+
+TEST(WindowedMinFilterTest, EmptyFilterReturnEmptyString) {
+ WindowedMinFilter<std::string> filter(/*window_length=*/3);
+ EXPECT_EQ(filter.GetMin(), "");
+}
+
+TEST(WindowedMinFilterTest, GetMinReturnsMin) {
+ WindowedMinFilter<int> filter(/*window_length=*/3);
+
+ filter.Insert(30);
+ EXPECT_EQ(filter.GetMin(), 30);
+ filter.Insert(20);
+ EXPECT_EQ(filter.GetMin(), 20);
+ filter.Insert(10);
+ EXPECT_EQ(filter.GetMin(), 10);
+}
+
+TEST(WindowedMinFilterTest, GetMinReturnsMinNotSortedInput) {
+ WindowedMinFilter<int> filter(/*window_length=*/4);
+
+ filter.Insert(0);
+ filter.Insert(30);
+ EXPECT_EQ(filter.GetMin(), 0);
+ filter.Insert(10);
+ EXPECT_EQ(filter.GetMin(), 0);
+ filter.Insert(40);
+ EXPECT_EQ(filter.GetMin(), 0);
+ filter.Insert(40);
+ EXPECT_EQ(filter.GetMin(), 10);
+}
+
+TEST(WindowedMinFilterTest, GetMinReturnsMinWithStringsNotSorted) {
+ WindowedMinFilter<std::string> filter(/*window_length=*/3);
+
+ filter.Insert("bbb");
+ EXPECT_EQ(filter.GetMin(), "bbb");
+ filter.Insert("ccc");
+ EXPECT_EQ(filter.GetMin(), "bbb");
+ filter.Insert("aaa");
+ EXPECT_EQ(filter.GetMin(), "aaa");
+}
+
+TEST(WindowedMinFilterTest, GetMinReturnsMinInWindow) {
+ WindowedMinFilter<int> filter(/*window_length=*/3);
+
+ filter.Insert(10);
+ filter.Insert(20);
+ filter.Insert(30);
+ EXPECT_EQ(filter.GetMin(), 10);
+ filter.Insert(40);
+ EXPECT_EQ(filter.GetMin(), 20);
+ filter.Insert(50);
+ EXPECT_EQ(filter.GetMin(), 30);
+}
+
+TEST(WindowedMinFilterTest, RestartAfterReset) {
+ WindowedMinFilter<int> filter(/*window_length=*/3);
+
+ filter.Insert(10);
+ filter.Insert(20);
+ ASSERT_EQ(filter.GetMin(), 10);
+ filter.Reset();
+ EXPECT_EQ(filter.GetMin(), 0);
+ filter.Insert(30);
+ EXPECT_EQ(filter.GetMin(), 30);
+}
+
+} // namespace
+} // namespace webrtc
diff --git a/test/fuzzers/BUILD.gn b/test/fuzzers/BUILD.gn
index e7a254c..5611c78 100644
--- a/test/fuzzers/BUILD.gn
+++ b/test/fuzzers/BUILD.gn
@@ -829,6 +829,15 @@
]
}
+webrtc_fuzzer_test("windowed_min_filter_fuzzer") {
+ sources = [ "windowed_min_filter_fuzzer.cc" ]
+ deps = [
+ "../../rtc_base:checks",
+ "../../rtc_base:windowed_min_filter",
+ "//third_party/abseil-cpp/absl/algorithm:container",
+ ]
+}
+
group("fuzzers") {
testonly = true
deps = [
@@ -889,6 +898,7 @@
":vp9_replay_fuzzer",
":webrtc_base64_decode_fuzzer",
":webrtc_base64_encode_fuzzer",
+ ":windowed_min_filter_fuzzer",
]
if (rtc_use_h265) {
deps += [
diff --git a/test/fuzzers/windowed_min_filter_fuzzer.cc b/test/fuzzers/windowed_min_filter_fuzzer.cc
new file mode 100644
index 0000000..a79f6bc
--- /dev/null
+++ b/test/fuzzers/windowed_min_filter_fuzzer.cc
@@ -0,0 +1,47 @@
+/*
+ * Copyright (c) 2025 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 <deque>
+#include "absl/algorithm/container.h"
+#include "rtc_base/numerics/windowed_min_filter.h"
+#include "rtc_base/checks.h"
+#include "test/fuzzers/fuzz_data_helper.h"
+
+namespace webrtc {
+
+void FuzzOneInput(const uint8_t* data, size_t size) {
+ class ReferenceFilter {
+ public:
+ explicit ReferenceFilter(int window_length) : max_size_(window_length) {}
+ void Insert(int value) {
+ buffer_.push_back(value);
+ if (buffer_.size() > max_size_) {
+ buffer_.pop_front();
+ }
+ }
+ int GetMin() const { return *absl::c_min_element(buffer_); }
+
+ private:
+ const size_t max_size_;
+ std::deque<int> buffer_;
+ };
+
+ ReferenceFilter reference_filter(/*window_length=*/10);
+ WindowedMinFilter<int> filter(/*window_length=*/10);
+ test::FuzzDataHelper fuzz_data(MakeArrayView(data, size));
+
+ while (fuzz_data.CanReadBytes(sizeof(int))) {
+ int value = fuzz_data.Read<int>();
+ reference_filter.Insert(value);
+ filter.Insert(value);
+ RTC_CHECK_EQ(filter.GetMin(), reference_filter.GetMin());
+ }
+}
+} // namespace webrtc
