diff options
Diffstat (limited to 'third_party/libwebrtc/rtc_base/numerics')
42 files changed, 5122 insertions, 0 deletions
diff --git a/third_party/libwebrtc/rtc_base/numerics/divide_round.h b/third_party/libwebrtc/rtc_base/numerics/divide_round.h new file mode 100644 index 0000000000..90c67fca3c --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/divide_round.h @@ -0,0 +1,60 @@ +/* + * Copyright 2019 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_DIVIDE_ROUND_H_ +#define RTC_BASE_NUMERICS_DIVIDE_ROUND_H_ + +#include <type_traits> + +#include "rtc_base/checks.h" +#include "rtc_base/numerics/safe_compare.h" + +namespace webrtc { + +template <typename Dividend, typename Divisor> +inline auto constexpr DivideRoundUp(Dividend dividend, Divisor divisor) { + static_assert(std::is_integral<Dividend>(), ""); + static_assert(std::is_integral<Divisor>(), ""); + RTC_DCHECK_GE(dividend, 0); + RTC_DCHECK_GT(divisor, 0); + + auto quotient = dividend / divisor; + auto remainder = dividend % divisor; + return quotient + (remainder > 0 ? 1 : 0); +} + +template <typename Dividend, typename Divisor> +inline auto constexpr DivideRoundToNearest(Dividend dividend, Divisor divisor) { + static_assert(std::is_integral<Dividend>(), ""); + static_assert(std::is_integral<Divisor>(), ""); + RTC_DCHECK_GT(divisor, 0); + + if (dividend < Dividend{0}) { + auto half_of_divisor = divisor / 2; + auto quotient = dividend / divisor; + auto remainder = dividend % divisor; + if (rtc::SafeGt(-remainder, half_of_divisor)) { + --quotient; + } + return quotient; + } + + auto half_of_divisor = (divisor - 1) / 2; + auto quotient = dividend / divisor; + auto remainder = dividend % divisor; + if (rtc::SafeGt(remainder, half_of_divisor)) { + ++quotient; + } + return quotient; +} + +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_DIVIDE_ROUND_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/divide_round_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/divide_round_unittest.cc new file mode 100644 index 0000000000..00548e1cb2 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/divide_round_unittest.cc @@ -0,0 +1,178 @@ +/* + * Copyright 2019 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/divide_round.h" + +#include <limits> + +#include "test/gtest.h" + +namespace webrtc { +namespace { + +TEST(DivideRoundUpTest, CanBeUsedAsConstexpr) { + static_assert(DivideRoundUp(5, 1) == 5, ""); + static_assert(DivideRoundUp(5, 2) == 3, ""); +} + +TEST(DivideRoundUpTest, ReturnsZeroForZeroDividend) { + EXPECT_EQ(DivideRoundUp(uint8_t{0}, 1), 0); + EXPECT_EQ(DivideRoundUp(uint8_t{0}, 3), 0); + EXPECT_EQ(DivideRoundUp(int{0}, 1), 0); + EXPECT_EQ(DivideRoundUp(int{0}, 3), 0); +} + +TEST(DivideRoundUpTest, WorksForMaxDividend) { + EXPECT_EQ(DivideRoundUp(uint8_t{255}, 2), 128); + EXPECT_EQ(DivideRoundUp(std::numeric_limits<int>::max(), 2), + std::numeric_limits<int>::max() / 2 + + (std::numeric_limits<int>::max() % 2)); +} + +TEST(DivideRoundToNearestTest, CanBeUsedAsConstexpr) { + static constexpr int kOne = DivideRoundToNearest(5, 4); + static constexpr int kTwo = DivideRoundToNearest(7, 4); + static_assert(kOne == 1); + static_assert(kTwo == 2); + static_assert(DivideRoundToNearest(-5, 4) == -1); + static_assert(DivideRoundToNearest(-7, 4) == -2); +} + +TEST(DivideRoundToNearestTest, DivideByOddNumber) { + EXPECT_EQ(DivideRoundToNearest(-5, 3), -2); + EXPECT_EQ(DivideRoundToNearest(-4, 3), -1); + EXPECT_EQ(DivideRoundToNearest(-3, 3), -1); + EXPECT_EQ(DivideRoundToNearest(-2, 3), -1); + EXPECT_EQ(DivideRoundToNearest(-1, 3), 0); + EXPECT_EQ(DivideRoundToNearest(0, 3), 0); + EXPECT_EQ(DivideRoundToNearest(1, 3), 0); + EXPECT_EQ(DivideRoundToNearest(2, 3), 1); + EXPECT_EQ(DivideRoundToNearest(3, 3), 1); + EXPECT_EQ(DivideRoundToNearest(4, 3), 1); + EXPECT_EQ(DivideRoundToNearest(5, 3), 2); + EXPECT_EQ(DivideRoundToNearest(6, 3), 2); +} + +TEST(DivideRoundToNearestTest, DivideByEvenNumberTieRoundsUp) { + EXPECT_EQ(DivideRoundToNearest(-7, 4), -2); + EXPECT_EQ(DivideRoundToNearest(-6, 4), -1); + EXPECT_EQ(DivideRoundToNearest(-5, 4), -1); + EXPECT_EQ(DivideRoundToNearest(-4, 4), -1); + EXPECT_EQ(DivideRoundToNearest(-3, 4), -1); + EXPECT_EQ(DivideRoundToNearest(-2, 4), 0); + EXPECT_EQ(DivideRoundToNearest(-1, 4), 0); + EXPECT_EQ(DivideRoundToNearest(0, 4), 0); + EXPECT_EQ(DivideRoundToNearest(1, 4), 0); + EXPECT_EQ(DivideRoundToNearest(2, 4), 1); + EXPECT_EQ(DivideRoundToNearest(3, 4), 1); + EXPECT_EQ(DivideRoundToNearest(4, 4), 1); + EXPECT_EQ(DivideRoundToNearest(5, 4), 1); + EXPECT_EQ(DivideRoundToNearest(6, 4), 2); + EXPECT_EQ(DivideRoundToNearest(7, 4), 2); +} + +TEST(DivideRoundToNearestTest, LargeDivisor) { + EXPECT_EQ(DivideRoundToNearest(std::numeric_limits<int>::max() - 1, + std::numeric_limits<int>::max()), + 1); + EXPECT_EQ(DivideRoundToNearest(std::numeric_limits<int>::min(), + std::numeric_limits<int>::max()), + -1); +} + +TEST(DivideRoundToNearestTest, DivideSmallTypeByLargeType) { + uint8_t small = 0xff; + uint16_t large = 0xffff; + EXPECT_EQ(DivideRoundToNearest(small, large), 0); +} + +using IntegerTypes = ::testing::Types<int8_t, + int16_t, + int32_t, + int64_t, + uint8_t, + uint16_t, + uint32_t, + uint64_t>; +template <typename T> +class DivideRoundTypedTest : public ::testing::Test {}; +TYPED_TEST_SUITE(DivideRoundTypedTest, IntegerTypes); + +TYPED_TEST(DivideRoundTypedTest, RoundToNearestPreservesType) { + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int8_t{3})), + decltype(TypeParam{100} / int8_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int16_t{3})), + decltype(TypeParam{100} / int16_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int32_t{3})), + decltype(TypeParam{100} / int32_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, int64_t{3})), + decltype(TypeParam{100} / int64_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint8_t{3})), + decltype(TypeParam{100} / uint8_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint16_t{3})), + decltype(TypeParam{100} / uint16_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint32_t{3})), + decltype(TypeParam{100} / uint32_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundToNearest(TypeParam{100}, uint64_t{3})), + decltype(TypeParam{100} / uint64_t{3})>::value, + ""); +} + +TYPED_TEST(DivideRoundTypedTest, RoundUpPreservesType) { + static_assert(std::is_same<decltype(DivideRoundUp(TypeParam{100}, int8_t{3})), + decltype(TypeParam{100} / int8_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, int16_t{3})), + decltype(TypeParam{100} / int16_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, int32_t{3})), + decltype(TypeParam{100} / int32_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, int64_t{3})), + decltype(TypeParam{100} / int64_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint8_t{3})), + decltype(TypeParam{100} / uint8_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint16_t{3})), + decltype(TypeParam{100} / uint16_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint32_t{3})), + decltype(TypeParam{100} / uint32_t{3})>::value, + ""); + static_assert( + std::is_same<decltype(DivideRoundUp(TypeParam{100}, uint64_t{3})), + decltype(TypeParam{100} / uint64_t{3})>::value, + ""); +} + +} // namespace +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.cc b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.cc new file mode 100644 index 0000000000..b426fdeed7 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.cc @@ -0,0 +1,82 @@ +/* + * Copyright 2019 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/event_based_exponential_moving_average.h" + +#include <cmath> + +#include "rtc_base/checks.h" + +namespace { + +// For a normal distributed value, the 95% double sided confidence interval is +// is 1.96 * stddev. +constexpr double ninetyfive_percent_confidence = 1.96; + +} // namespace + +namespace rtc { + +// `half_time` specifies how much weight will be given to old samples, +// a sample gets exponentially less weight so that it's 50% +// after `half_time` time units has passed. +EventBasedExponentialMovingAverage::EventBasedExponentialMovingAverage( + int half_time) { + SetHalfTime(half_time); +} + +void EventBasedExponentialMovingAverage::SetHalfTime(int half_time) { + tau_ = static_cast<double>(half_time) / log(2); + Reset(); +} + +void EventBasedExponentialMovingAverage::Reset() { + value_ = std::nan("uninit"); + sample_variance_ = std::numeric_limits<double>::infinity(); + estimator_variance_ = 1; + last_observation_timestamp_.reset(); +} + +void EventBasedExponentialMovingAverage::AddSample(int64_t now, int sample) { + if (!last_observation_timestamp_.has_value()) { + value_ = sample; + } else { + // TODO(webrtc:11140): This should really be > (e.g not >=) + // but some pesky tests run with simulated clock and let + // samples arrive simultaneously! + RTC_DCHECK(now >= *last_observation_timestamp_); + // Variance gets computed after second sample. + int64_t age = now - *last_observation_timestamp_; + double e = exp(-age / tau_); + double alpha = e / (1 + e); + double one_minus_alpha = 1 - alpha; + double sample_diff = sample - value_; + value_ = one_minus_alpha * value_ + alpha * sample; + estimator_variance_ = + (one_minus_alpha * one_minus_alpha) * estimator_variance_ + + (alpha * alpha); + if (sample_variance_ == std::numeric_limits<double>::infinity()) { + // First variance. + sample_variance_ = sample_diff * sample_diff; + } else { + double new_variance = one_minus_alpha * sample_variance_ + + alpha * sample_diff * sample_diff; + sample_variance_ = new_variance; + } + } + last_observation_timestamp_ = now; +} + +double EventBasedExponentialMovingAverage::GetConfidenceInterval() const { + return ninetyfive_percent_confidence * + sqrt(sample_variance_ * estimator_variance_); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.h b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.h new file mode 100644 index 0000000000..a59fff7241 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average.h @@ -0,0 +1,70 @@ +/* + * Copyright 2019 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_EVENT_BASED_EXPONENTIAL_MOVING_AVERAGE_H_ +#define RTC_BASE_NUMERICS_EVENT_BASED_EXPONENTIAL_MOVING_AVERAGE_H_ + +#include <cmath> +#include <cstdint> +#include <limits> +#include "absl/types/optional.h" + +namespace rtc { + +/** + * This class implements exponential moving average for time series + * estimating both value, variance and variance of estimator based on + * https://en.wikipedia.org/w/index.php?title=Moving_average§ion=9#Application_to_measuring_computer_performance + * with the additions from nisse@ added to + * https://en.wikipedia.org/wiki/Talk:Moving_average. + * + * A sample gets exponentially less weight so that it's 50% + * after `half_time` time units. + */ +class EventBasedExponentialMovingAverage { + public: + // `half_time` specifies how much weight will be given to old samples, + // see example above. + explicit EventBasedExponentialMovingAverage(int half_time); + + void AddSample(int64_t now, int value); + + double GetAverage() const { return value_; } + double GetVariance() const { return sample_variance_; } + + // Compute 95% confidence interval assuming that + // - variance of samples are normal distributed. + // - variance of estimator is normal distributed. + // + // The returned values specifies the distance from the average, + // i.e if X = GetAverage(), m = GetConfidenceInterval() + // then a there is 95% likelihood that the observed variables is inside + // [ X +/- m ]. + double GetConfidenceInterval() const; + + // Reset + void Reset(); + + // Update the half_time. + // NOTE: resets estimate too. + void SetHalfTime(int half_time); + + private: + double tau_; + double value_ = std::nan("uninit"); + double sample_variance_ = std::numeric_limits<double>::infinity(); + // This is the ratio between variance of the estimate and variance of samples. + double estimator_variance_ = 1; + absl::optional<int64_t> last_observation_timestamp_; +}; + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_EVENT_BASED_EXPONENTIAL_MOVING_AVERAGE_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average_unittest.cc new file mode 100644 index 0000000000..967be41213 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/event_based_exponential_moving_average_unittest.cc @@ -0,0 +1,227 @@ +/* + * Copyright 2019 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/event_based_exponential_moving_average.h" + +#include <cmath> + +#include "test/gtest.h" + +namespace { + +constexpr int kHalfTime = 500; +constexpr double kError = 0.1; + +} // namespace + +namespace rtc { + +TEST(EventBasedExponentialMovingAverageTest, NoValue) { + EventBasedExponentialMovingAverage average(kHalfTime); + + EXPECT_TRUE(std::isnan(average.GetAverage())); + EXPECT_EQ(std::numeric_limits<double>::infinity(), average.GetVariance()); + EXPECT_EQ(std::numeric_limits<double>::infinity(), + average.GetConfidenceInterval()); +} + +TEST(EventBasedExponentialMovingAverageTest, FirstValue) { + EventBasedExponentialMovingAverage average(kHalfTime); + + int64_t time = 23; + constexpr int value = 1000; + average.AddSample(time, value); + EXPECT_NEAR(value, average.GetAverage(), kError); + EXPECT_EQ(std::numeric_limits<double>::infinity(), average.GetVariance()); + EXPECT_EQ(std::numeric_limits<double>::infinity(), + average.GetConfidenceInterval()); +} + +TEST(EventBasedExponentialMovingAverageTest, Half) { + EventBasedExponentialMovingAverage average(kHalfTime); + + int64_t time = 23; + constexpr int value = 1000; + average.AddSample(time, value); + average.AddSample(time + kHalfTime, 0); + EXPECT_NEAR(666.7, average.GetAverage(), kError); + EXPECT_NEAR(1000000, average.GetVariance(), kError); + EXPECT_NEAR(1460.9, average.GetConfidenceInterval(), kError); +} + +TEST(EventBasedExponentialMovingAverageTest, Same) { + EventBasedExponentialMovingAverage average(kHalfTime); + + int64_t time = 23; + constexpr int value = 1000; + average.AddSample(time, value); + average.AddSample(time + kHalfTime, value); + EXPECT_NEAR(value, average.GetAverage(), kError); + EXPECT_NEAR(0, average.GetVariance(), kError); + EXPECT_NEAR(0, average.GetConfidenceInterval(), kError); +} + +TEST(EventBasedExponentialMovingAverageTest, Almost100) { + EventBasedExponentialMovingAverage average(kHalfTime); + + int64_t time = 23; + constexpr int value = 100; + average.AddSample(time + 0 * kHalfTime, value - 10); + average.AddSample(time + 1 * kHalfTime, value + 10); + average.AddSample(time + 2 * kHalfTime, value - 15); + average.AddSample(time + 3 * kHalfTime, value + 15); + EXPECT_NEAR(100.2, average.GetAverage(), kError); + EXPECT_NEAR(372.6, average.GetVariance(), kError); + EXPECT_NEAR(19.7, average.GetConfidenceInterval(), kError); // 100 +/- 20 + + average.AddSample(time + 4 * kHalfTime, value); + average.AddSample(time + 5 * kHalfTime, value); + average.AddSample(time + 6 * kHalfTime, value); + average.AddSample(time + 7 * kHalfTime, value); + EXPECT_NEAR(100.0, average.GetAverage(), kError); + EXPECT_NEAR(73.6, average.GetVariance(), kError); + EXPECT_NEAR(7.6, average.GetConfidenceInterval(), kError); // 100 +/- 7 +} + +// Test that getting a value at X and another at X+1 +// is almost the same as getting another at X and a value at X+1. +TEST(EventBasedExponentialMovingAverageTest, AlmostSameTime) { + int64_t time = 23; + constexpr int value = 100; + + { + EventBasedExponentialMovingAverage average(kHalfTime); + average.AddSample(time + 0, value); + average.AddSample(time + 1, 0); + EXPECT_NEAR(50, average.GetAverage(), kError); + EXPECT_NEAR(10000, average.GetVariance(), kError); + EXPECT_NEAR(138.6, average.GetConfidenceInterval(), + kError); // 50 +/- 138.6 + } + + { + EventBasedExponentialMovingAverage average(kHalfTime); + average.AddSample(time + 0, 0); + average.AddSample(time + 1, 100); + EXPECT_NEAR(50, average.GetAverage(), kError); + EXPECT_NEAR(10000, average.GetVariance(), kError); + EXPECT_NEAR(138.6, average.GetConfidenceInterval(), + kError); // 50 +/- 138.6 + } +} + +// This test shows behavior of estimator with a half_time of 100. +// It is unclear if these set of observations are representative +// of any real world scenarios. +TEST(EventBasedExponentialMovingAverageTest, NonUniformSamplesHalftime100) { + int64_t time = 23; + constexpr int value = 100; + + { + // The observations at 100 and 101, are significantly close in + // time that the estimator returns approx. the average. + EventBasedExponentialMovingAverage average(100); + average.AddSample(time + 0, value); + average.AddSample(time + 100, value); + average.AddSample(time + 101, 0); + EXPECT_NEAR(50.2, average.GetAverage(), kError); + EXPECT_NEAR(86.2, average.GetConfidenceInterval(), kError); // 50 +/- 86 + } + + { + EventBasedExponentialMovingAverage average(100); + average.AddSample(time + 0, value); + average.AddSample(time + 1, value); + average.AddSample(time + 100, 0); + EXPECT_NEAR(66.5, average.GetAverage(), kError); + EXPECT_NEAR(65.4, average.GetConfidenceInterval(), kError); // 66 +/- 65 + } + + { + EventBasedExponentialMovingAverage average(100); + for (int i = 0; i < 10; i++) { + average.AddSample(time + i, value); + } + average.AddSample(time + 100, 0); + EXPECT_NEAR(65.3, average.GetAverage(), kError); + EXPECT_NEAR(59.1, average.GetConfidenceInterval(), kError); // 55 +/- 59 + } + + { + EventBasedExponentialMovingAverage average(100); + average.AddSample(time + 0, 100); + for (int i = 90; i <= 100; i++) { + average.AddSample(time + i, 0); + } + EXPECT_NEAR(0.05, average.GetAverage(), kError); + EXPECT_NEAR(4.9, average.GetConfidenceInterval(), kError); // 0 +/- 5 + } +} + +TEST(EventBasedExponentialMovingAverageTest, Reset) { + constexpr int64_t time = 23; + constexpr int value = 100; + + EventBasedExponentialMovingAverage average(100); + EXPECT_TRUE(std::isnan(average.GetAverage())); + EXPECT_EQ(std::numeric_limits<double>::infinity(), average.GetVariance()); + EXPECT_EQ(std::numeric_limits<double>::infinity(), + average.GetConfidenceInterval()); + + average.AddSample(time + 0, value); + average.AddSample(time + 100, value); + average.AddSample(time + 101, 0); + EXPECT_FALSE(std::isnan(average.GetAverage())); + + average.Reset(); + EXPECT_TRUE(std::isnan(average.GetAverage())); + EXPECT_EQ(std::numeric_limits<double>::infinity(), average.GetVariance()); + EXPECT_EQ(std::numeric_limits<double>::infinity(), + average.GetConfidenceInterval()); +} + +// Test that SetHalfTime modifies behavior and resets average. +TEST(EventBasedExponentialMovingAverageTest, SetHalfTime) { + constexpr int64_t time = 23; + constexpr int value = 100; + + EventBasedExponentialMovingAverage average(100); + + average.AddSample(time + 0, value); + average.AddSample(time + 100, 0); + EXPECT_NEAR(66.7, average.GetAverage(), kError); + + average.SetHalfTime(1000); + EXPECT_TRUE(std::isnan(average.GetAverage())); + EXPECT_EQ(std::numeric_limits<double>::infinity(), average.GetVariance()); + EXPECT_EQ(std::numeric_limits<double>::infinity(), + average.GetConfidenceInterval()); + + average.AddSample(time + 0, value); + average.AddSample(time + 100, 0); + EXPECT_NEAR(51.7, average.GetAverage(), kError); +} + +TEST(EventBasedExponentialMovingAverageTest, SimultaneousSamples) { + constexpr int64_t time = 23; + constexpr int value = 100; + + EventBasedExponentialMovingAverage average(100); + + average.AddSample(time, value); + // This should really NOT be supported, + // i.e 2 samples with same timestamp. + // But there are tests running with simulated clock + // that produce this. + // TODO(webrtc:11140) : Fix those tests and remove this! + average.AddSample(time, value); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.cc b/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.cc new file mode 100644 index 0000000000..d7b7293918 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.cc @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2019 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/event_rate_counter.h" + +#include <algorithm> + +namespace webrtc { + +void EventRateCounter::AddEvent(Timestamp event_time) { + if (first_time_.IsFinite()) + interval_.AddSample(event_time - last_time_); + first_time_ = std::min(first_time_, event_time); + last_time_ = std::max(last_time_, event_time); + event_count_++; +} + +void EventRateCounter::AddEvents(EventRateCounter other) { + first_time_ = std::min(first_time_, other.first_time_); + last_time_ = std::max(last_time_, other.last_time_); + event_count_ += other.event_count_; + interval_.AddSamples(other.interval_); +} + +bool EventRateCounter::IsEmpty() const { + return first_time_ == last_time_; +} + +double EventRateCounter::Rate() const { + if (event_count_ == 0) + return 0; + if (event_count_ == 1) + return NAN; + return (event_count_ - 1) / (last_time_ - first_time_).seconds<double>(); +} + +TimeDelta EventRateCounter::TotalDuration() const { + if (first_time_.IsInfinite()) { + return TimeDelta::Zero(); + } + return last_time_ - first_time_; +} +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.h b/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.h new file mode 100644 index 0000000000..60ec3ba416 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/event_rate_counter.h @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2019 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_EVENT_RATE_COUNTER_H_ +#define RTC_BASE_NUMERICS_EVENT_RATE_COUNTER_H_ + +#include "rtc_base/numerics/sample_stats.h" + +namespace webrtc { + +// Calculates statistics based on events. For example for computing frame rates. +// Note that it doesn't provide any running statistics or reset funcitonality, +// so it's mostly useful for end of call statistics. +class EventRateCounter { + public: + // Adds an event based on it's `event_time` for correct updates of the + // interval statistics, each event must be added past the previous events. + void AddEvent(Timestamp event_time); + // Adds the events from `other`. Note that the interval stats won't be + // recalculated, only merged, so this is not equivalent to if the events would + // have been added to the same counter from the start. + void AddEvents(EventRateCounter other); + bool IsEmpty() const; + // Average number of events per second. Defaults to 0 for no events and NAN + // for one event. + double Rate() const; + SampleStats<TimeDelta>& interval() { return interval_; } + TimeDelta TotalDuration() const; + int Count() const { return event_count_; } + + private: + Timestamp first_time_ = Timestamp::PlusInfinity(); + Timestamp last_time_ = Timestamp::MinusInfinity(); + int64_t event_count_ = 0; + SampleStats<TimeDelta> interval_; +}; +} // namespace webrtc +#endif // RTC_BASE_NUMERICS_EVENT_RATE_COUNTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/exp_filter.cc b/third_party/libwebrtc/rtc_base/numerics/exp_filter.cc new file mode 100644 index 0000000000..a58250abc4 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/exp_filter.cc @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2011 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/exp_filter.h" + +#include <cmath> + +namespace rtc { + +const float ExpFilter::kValueUndefined = -1.0f; + +void ExpFilter::Reset(float alpha) { + alpha_ = alpha; + filtered_ = kValueUndefined; +} + +float ExpFilter::Apply(float exp, float sample) { + if (filtered_ == kValueUndefined) { + // Initialize filtered value. + filtered_ = sample; + } else if (exp == 1.0) { + filtered_ = alpha_ * filtered_ + (1 - alpha_) * sample; + } else { + float alpha = std::pow(alpha_, exp); + filtered_ = alpha * filtered_ + (1 - alpha) * sample; + } + if (max_ != kValueUndefined && filtered_ > max_) { + filtered_ = max_; + } + return filtered_; +} + +void ExpFilter::UpdateBase(float alpha) { + alpha_ = alpha; +} +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/exp_filter.h b/third_party/libwebrtc/rtc_base/numerics/exp_filter.h new file mode 100644 index 0000000000..6bded80d02 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/exp_filter.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2011 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_EXP_FILTER_H_ +#define RTC_BASE_NUMERICS_EXP_FILTER_H_ + +namespace rtc { + +// This class can be used, for example, for smoothing the result of bandwidth +// estimation and packet loss estimation. + +class ExpFilter { + public: + static const float kValueUndefined; + + explicit ExpFilter(float alpha, float max = kValueUndefined) : max_(max) { + Reset(alpha); + } + + // Resets the filter to its initial state, and resets filter factor base to + // the given value `alpha`. + void Reset(float alpha); + + // Applies the filter with a given exponent on the provided sample: + // y(k) = min(alpha_^ exp * y(k-1) + (1 - alpha_^ exp) * sample, max_). + float Apply(float exp, float sample); + + // Returns current filtered value. + float filtered() const { return filtered_; } + + // Changes the filter factor base to the given value `alpha`. + void UpdateBase(float alpha); + + private: + float alpha_; // Filter factor base. + float filtered_; // Current filter output. + const float max_; +}; +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_EXP_FILTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/exp_filter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/exp_filter_unittest.cc new file mode 100644 index 0000000000..f5b436f1b9 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/exp_filter_unittest.cc @@ -0,0 +1,72 @@ +/* + * Copyright 2014 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/exp_filter.h" + +#include <cmath> + +#include "test/gtest.h" + +namespace rtc { + +TEST(ExpFilterTest, FirstTimeOutputEqualInput) { + // No max value defined. + ExpFilter filter = ExpFilter(0.9f); + filter.Apply(100.0f, 10.0f); + + // First time, first argument no effect. + double value = 10.0f; + EXPECT_FLOAT_EQ(value, filter.filtered()); +} + +TEST(ExpFilterTest, SecondTime) { + float value; + + ExpFilter filter = ExpFilter(0.9f); + filter.Apply(100.0f, 10.0f); + + // First time, first argument no effect. + value = 10.0f; + + filter.Apply(10.0f, 20.0f); + float alpha = std::pow(0.9f, 10.0f); + value = alpha * value + (1.0f - alpha) * 20.0f; + EXPECT_FLOAT_EQ(value, filter.filtered()); +} + +TEST(ExpFilterTest, Reset) { + ExpFilter filter = ExpFilter(0.9f); + filter.Apply(100.0f, 10.0f); + + filter.Reset(0.8f); + filter.Apply(100.0f, 1.0f); + + // Become first time after a reset. + double value = 1.0f; + EXPECT_FLOAT_EQ(value, filter.filtered()); +} + +TEST(ExpfilterTest, OutputLimitedByMax) { + double value; + + // Max value defined. + ExpFilter filter = ExpFilter(0.9f, 1.0f); + filter.Apply(100.0f, 10.0f); + + // Limited to max value. + value = 1.0f; + EXPECT_EQ(value, filter.filtered()); + + filter.Apply(1.0f, 0.0f); + value = 0.9f * value; + EXPECT_FLOAT_EQ(value, filter.filtered()); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.cc b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.cc new file mode 100644 index 0000000000..29d2341c85 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.cc @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2017 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/histogram_percentile_counter.h" + +#include <algorithm> +#include <cmath> + +#include "rtc_base/checks.h" + +namespace rtc { +HistogramPercentileCounter::HistogramPercentileCounter( + uint32_t long_tail_boundary) + : histogram_low_(size_t{long_tail_boundary}), + long_tail_boundary_(long_tail_boundary), + total_elements_(0), + total_elements_low_(0) {} + +HistogramPercentileCounter::~HistogramPercentileCounter() = default; + +void HistogramPercentileCounter::Add(const HistogramPercentileCounter& other) { + for (uint32_t value = 0; value < other.long_tail_boundary_; ++value) { + Add(value, other.histogram_low_[value]); + } + for (const auto& it : histogram_high_) { + Add(it.first, it.second); + } +} + +void HistogramPercentileCounter::Add(uint32_t value, size_t count) { + if (value < long_tail_boundary_) { + histogram_low_[value] += count; + total_elements_low_ += count; + } else { + histogram_high_[value] += count; + } + total_elements_ += count; +} + +void HistogramPercentileCounter::Add(uint32_t value) { + Add(value, 1); +} + +absl::optional<uint32_t> HistogramPercentileCounter::GetPercentile( + float fraction) { + RTC_CHECK_LE(fraction, 1.0); + RTC_CHECK_GE(fraction, 0.0); + if (total_elements_ == 0) + return absl::nullopt; + size_t elements_to_skip = static_cast<size_t>( + std::max(0.0f, std::ceil(total_elements_ * fraction) - 1)); + if (elements_to_skip >= total_elements_) + elements_to_skip = total_elements_ - 1; + if (elements_to_skip < total_elements_low_) { + for (uint32_t value = 0; value < long_tail_boundary_; ++value) { + if (elements_to_skip < histogram_low_[value]) + return value; + elements_to_skip -= histogram_low_[value]; + } + } else { + elements_to_skip -= total_elements_low_; + for (const auto& it : histogram_high_) { + if (elements_to_skip < it.second) + return it.first; + elements_to_skip -= it.second; + } + } + RTC_DCHECK_NOTREACHED(); + return absl::nullopt; +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.h b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.h new file mode 100644 index 0000000000..4787f2ef98 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter.h @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2017 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_HISTOGRAM_PERCENTILE_COUNTER_H_ +#define RTC_BASE_NUMERICS_HISTOGRAM_PERCENTILE_COUNTER_H_ + +#include <stddef.h> +#include <stdint.h> + +#include <map> +#include <vector> + +#include "absl/types/optional.h" + +namespace rtc { +// Calculates percentiles on the stream of data. Use `Add` methods to add new +// values. Use `GetPercentile` to get percentile of the currently added values. +class HistogramPercentileCounter { + public: + // Values below `long_tail_boundary` are stored as the histogram in an array. + // Values above - in a map. + explicit HistogramPercentileCounter(uint32_t long_tail_boundary); + ~HistogramPercentileCounter(); + void Add(uint32_t value); + void Add(uint32_t value, size_t count); + void Add(const HistogramPercentileCounter& other); + // Argument should be from 0 to 1. + absl::optional<uint32_t> GetPercentile(float fraction); + + private: + std::vector<size_t> histogram_low_; + std::map<uint32_t, size_t> histogram_high_; + const uint32_t long_tail_boundary_; + size_t total_elements_; + size_t total_elements_low_; +}; +} // namespace rtc +#endif // RTC_BASE_NUMERICS_HISTOGRAM_PERCENTILE_COUNTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc new file mode 100644 index 0000000000..fc36b59208 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc @@ -0,0 +1,44 @@ +/* + * Copyright 2017 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/histogram_percentile_counter.h" + +#include <cstdint> +#include <utility> +#include <vector> + +#include "test/gtest.h" + +TEST(HistogramPercentileCounterTest, ReturnsCorrectPercentiles) { + rtc::HistogramPercentileCounter counter(10); + const std::vector<int> kTestValues = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, + 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; + + EXPECT_FALSE(counter.GetPercentile(0.5f)); + // Pairs of {fraction, percentile value} computed by hand + // for `kTestValues`. + const std::vector<std::pair<float, uint32_t>> kTestPercentiles = { + {0.0f, 1}, {0.01f, 1}, {0.5f, 10}, {0.9f, 18}, + {0.95f, 19}, {0.99f, 20}, {1.0f, 20}}; + for (int value : kTestValues) { + counter.Add(value); + } + for (const auto& test_percentile : kTestPercentiles) { + EXPECT_EQ(test_percentile.second, + counter.GetPercentile(test_percentile.first).value_or(0)); + } +} + +TEST(HistogramPercentileCounterTest, HandlesEmptySequence) { + rtc::HistogramPercentileCounter counter(10); + EXPECT_FALSE(counter.GetPercentile(0.5f)); + counter.Add(1u); + EXPECT_TRUE(counter.GetPercentile(0.5f)); +} diff --git a/third_party/libwebrtc/rtc_base/numerics/math_utils.h b/third_party/libwebrtc/rtc_base/numerics/math_utils.h new file mode 100644 index 0000000000..5482cec6e5 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/math_utils.h @@ -0,0 +1,75 @@ +/* + * Copyright 2005 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 API_NUMERICS_MATH_UTILS_H_ +#define API_NUMERICS_MATH_UTILS_H_ + +#include <limits> +#include <type_traits> + +#include "rtc_base/checks.h" + +namespace webrtc { +namespace webrtc_impl { +// Given two numbers `x` and `y` such that x >= y, computes the difference +// x - y without causing undefined behavior due to signed overflow. +template <typename T> +typename std::make_unsigned<T>::type unsigned_difference(T x, T y) { + static_assert( + std::is_signed<T>::value, + "Function unsigned_difference is only meaningful for signed types."); + RTC_DCHECK_GE(x, y); + typedef typename std::make_unsigned<T>::type unsigned_type; + // int -> unsigned conversion repeatedly adds UINT_MAX + 1 until the number + // can be represented as an unsigned. Since we know that the actual + // difference x - y can be represented as an unsigned, it is sufficient to + // compute the difference modulo UINT_MAX + 1, i.e using unsigned arithmetic. + return static_cast<unsigned_type>(x) - static_cast<unsigned_type>(y); +} + +// Provide neutral element with respect to min(). +// Typically used as an initial value for running minimum. +template <typename T, + typename std::enable_if<std::numeric_limits<T>::has_infinity>::type* = + nullptr> +constexpr T infinity_or_max() { + return std::numeric_limits<T>::infinity(); +} + +template <typename T, + typename std::enable_if< + !std::numeric_limits<T>::has_infinity>::type* = nullptr> +constexpr T infinity_or_max() { + // Fallback to max(). + return std::numeric_limits<T>::max(); +} + +// Provide neutral element with respect to max(). +// Typically used as an initial value for running maximum. +template <typename T, + typename std::enable_if<std::numeric_limits<T>::has_infinity>::type* = + nullptr> +constexpr T minus_infinity_or_min() { + static_assert(std::is_signed<T>::value, "Unsupported. Please open a bug."); + return -std::numeric_limits<T>::infinity(); +} + +template <typename T, + typename std::enable_if< + !std::numeric_limits<T>::has_infinity>::type* = nullptr> +constexpr T minus_infinity_or_min() { + // Fallback to min(). + return std::numeric_limits<T>::min(); +} + +} // namespace webrtc_impl +} // namespace webrtc + +#endif // API_NUMERICS_MATH_UTILS_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/mod_ops.h b/third_party/libwebrtc/rtc_base/numerics/mod_ops.h new file mode 100644 index 0000000000..65618b4876 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/mod_ops.h @@ -0,0 +1,142 @@ +/* + * Copyright (c) 2016 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_MOD_OPS_H_ +#define RTC_BASE_NUMERICS_MOD_OPS_H_ + +#include <algorithm> +#include <type_traits> + +#include "rtc_base/checks.h" + +namespace webrtc { + +template <unsigned long M> // NOLINT +inline unsigned long Add(unsigned long a, unsigned long b) { // NOLINT + RTC_DCHECK_LT(a, M); + unsigned long t = M - b % M; // NOLINT + unsigned long res = a - t; // NOLINT + if (t > a) + return res + M; + return res; +} + +template <unsigned long M> // NOLINT +inline unsigned long Subtract(unsigned long a, unsigned long b) { // NOLINT + RTC_DCHECK_LT(a, M); + unsigned long sub = b % M; // NOLINT + if (a < sub) + return M - (sub - a); + return a - sub; +} + +// Calculates the forward difference between two wrapping numbers. +// +// Example: +// uint8_t x = 253; +// uint8_t y = 2; +// +// ForwardDiff(x, y) == 5 +// +// 252 253 254 255 0 1 2 3 +// ################################################# +// | | x | | | | | y | | +// ################################################# +// |----->----->----->----->-----> +// +// ForwardDiff(y, x) == 251 +// +// 252 253 254 255 0 1 2 3 +// ################################################# +// | | x | | | | | y | | +// ################################################# +// -->-----> |----->--- +// +// If M > 0 then wrapping occurs at M, if M == 0 then wrapping occurs at the +// largest value representable by T. +template <typename T, T M> +inline typename std::enable_if<(M > 0), T>::type ForwardDiff(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + RTC_DCHECK_LT(a, M); + RTC_DCHECK_LT(b, M); + return a <= b ? b - a : M - (a - b); +} + +template <typename T, T M> +inline typename std::enable_if<(M == 0), T>::type ForwardDiff(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + return b - a; +} + +template <typename T> +inline T ForwardDiff(T a, T b) { + return ForwardDiff<T, 0>(a, b); +} + +// Calculates the reverse difference between two wrapping numbers. +// +// Example: +// uint8_t x = 253; +// uint8_t y = 2; +// +// ReverseDiff(y, x) == 5 +// +// 252 253 254 255 0 1 2 3 +// ################################################# +// | | x | | | | | y | | +// ################################################# +// <-----<-----<-----<-----<-----| +// +// ReverseDiff(x, y) == 251 +// +// 252 253 254 255 0 1 2 3 +// ################################################# +// | | x | | | | | y | | +// ################################################# +// ---<-----| |<-----<-- +// +// If M > 0 then wrapping occurs at M, if M == 0 then wrapping occurs at the +// largest value representable by T. +template <typename T, T M> +inline typename std::enable_if<(M > 0), T>::type ReverseDiff(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + RTC_DCHECK_LT(a, M); + RTC_DCHECK_LT(b, M); + return b <= a ? a - b : M - (b - a); +} + +template <typename T, T M> +inline typename std::enable_if<(M == 0), T>::type ReverseDiff(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + return a - b; +} + +template <typename T> +inline T ReverseDiff(T a, T b) { + return ReverseDiff<T, 0>(a, b); +} + +// Calculates the minimum distance between to wrapping numbers. +// +// The minimum distance is defined as min(ForwardDiff(a, b), ReverseDiff(a, b)) +template <typename T, T M = 0> +inline T MinDiff(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + return std::min(ForwardDiff<T, M>(a, b), ReverseDiff<T, M>(a, b)); +} + +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_MOD_OPS_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/mod_ops_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/mod_ops_unittest.cc new file mode 100644 index 0000000000..3bd20345a7 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/mod_ops_unittest.cc @@ -0,0 +1,159 @@ +/* + * Copyright (c) 2016 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/mod_ops.h" + +#include <stdint.h> + +#include "test/gtest.h" + +namespace webrtc { +class TestModOps : public ::testing::Test { + protected: + // Can't use std::numeric_limits<unsigned long>::max() since + // MSVC doesn't support constexpr. + static const unsigned long ulmax = ~0ul; // NOLINT +}; + +TEST_F(TestModOps, Add) { + const int D = 100; + ASSERT_EQ(1u, Add<D>(0, 1)); + ASSERT_EQ(0u, Add<D>(0, D)); + for (int i = 0; i < D; ++i) + ASSERT_EQ(0u, Add<D>(i, D - i)); + + int t = 37; + uint8_t a = t; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(a, static_cast<uint8_t>(t)); + t = Add<256>(t, 1); + ++a; + } +} + +TEST_F(TestModOps, AddLarge) { + const unsigned long D = ulmax - 10ul; // NOLINT + unsigned long l = D - 1ul; // NOLINT + ASSERT_EQ(D - 2ul, Add<D>(l, l)); + ASSERT_EQ(9ul, Add<D>(l, ulmax)); + ASSERT_EQ(10ul, Add<D>(0ul, ulmax)); +} + +TEST_F(TestModOps, Subtract) { + const int D = 100; + ASSERT_EQ(99u, Subtract<D>(0, 1)); + ASSERT_EQ(0u, Subtract<D>(0, D)); + for (int i = 0; i < D; ++i) + ASSERT_EQ(0u, Subtract<D>(i, D + i)); + + int t = 37; + uint8_t a = t; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(a, static_cast<uint8_t>(t)); + t = Subtract<256>(t, 1); + --a; + } +} + +TEST_F(TestModOps, SubtractLarge) { + // NOLINTNEXTLINE + const unsigned long D = ulmax - 10ul; // NOLINT + unsigned long l = D - 1ul; // NOLINT + ASSERT_EQ(0ul, Subtract<D>(l, l)); + ASSERT_EQ(D - 11ul, Subtract<D>(l, ulmax)); + ASSERT_EQ(D - 10ul, Subtract<D>(0ul, ulmax)); +} + +TEST_F(TestModOps, ForwardDiff) { + ASSERT_EQ(0u, ForwardDiff(4711u, 4711u)); + + uint8_t x = 0; + uint8_t y = 255; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(255u, ForwardDiff(x, y)); + ++x; + ++y; + } + + int yi = 255; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(255u, ForwardDiff<uint8_t>(x, yi)); + ++x; + ++yi; + } +} + +TEST_F(TestModOps, ForwardDiffWithDivisor) { + ASSERT_EQ(122, (ForwardDiff<uint8_t, 123>(0, 122))); + ASSERT_EQ(0, (ForwardDiff<uint8_t, 123>(122, 122))); + ASSERT_EQ(122, (ForwardDiff<uint8_t, 123>(1, 0))); + ASSERT_EQ(0, (ForwardDiff<uint8_t, 123>(0, 0))); + ASSERT_EQ(1, (ForwardDiff<uint8_t, 123>(122, 0))); +} + +TEST_F(TestModOps, ReverseDiff) { + ASSERT_EQ(0u, ReverseDiff(4711u, 4711u)); + + uint8_t x = 0; + uint8_t y = 255; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(1u, ReverseDiff(x, y)); + ++x; + ++y; + } + + int yi = 255; + for (int i = 0; i < 256; ++i) { + ASSERT_EQ(1u, ReverseDiff<uint8_t>(x, yi)); + ++x; + ++yi; + } +} + +TEST_F(TestModOps, ReverseDiffWithDivisor) { + ASSERT_EQ(1, (ReverseDiff<uint8_t, 123>(0, 122))); + ASSERT_EQ(0, (ReverseDiff<uint8_t, 123>(122, 122))); + ASSERT_EQ(1, (ReverseDiff<uint8_t, 123>(1, 0))); + ASSERT_EQ(0, (ReverseDiff<uint8_t, 123>(0, 0))); + ASSERT_EQ(122, (ReverseDiff<uint8_t, 123>(122, 0))); +} + +TEST_F(TestModOps, MinDiff) { + for (uint16_t i = 0; i < 256; ++i) { + ASSERT_EQ(0, MinDiff<uint8_t>(i, i)); + ASSERT_EQ(1, MinDiff<uint8_t>(i - 1, i)); + ASSERT_EQ(1, MinDiff<uint8_t>(i + 1, i)); + } + + for (uint8_t i = 0; i < 128; ++i) + ASSERT_EQ(i, MinDiff<uint8_t>(0, i)); + + for (uint8_t i = 0; i < 128; ++i) + ASSERT_EQ(128 - i, MinDiff<uint8_t>(0, 128 + i)); +} + +TEST_F(TestModOps, MinDiffWitDivisor) { + ASSERT_EQ(5u, (MinDiff<uint8_t, 11>(0, 5))); + ASSERT_EQ(5u, (MinDiff<uint8_t, 11>(0, 6))); + ASSERT_EQ(5u, (MinDiff<uint8_t, 11>(5, 0))); + ASSERT_EQ(5u, (MinDiff<uint8_t, 11>(6, 0))); + + const uint16_t D = 4711; + + for (uint16_t i = 0; i < D / 2; ++i) + ASSERT_EQ(i, (MinDiff<uint16_t, D>(0, i))); + + ASSERT_EQ(D / 2, (MinDiff<uint16_t, D>(0, D / 2))); + + for (uint16_t i = 0; i < D / 2; ++i) + ASSERT_EQ(D / 2 - i, (MinDiff<uint16_t, D>(0, D / 2 - i))); +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_average.cc b/third_party/libwebrtc/rtc_base/numerics/moving_average.cc new file mode 100644 index 0000000000..c825839227 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_average.cc @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2018 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/moving_average.h" + +#include <algorithm> + +#include "rtc_base/checks.h" + +namespace rtc { + +MovingAverage::MovingAverage(size_t window_size) : history_(window_size, 0) { + // Limit window size to avoid overflow. + RTC_DCHECK_LE(window_size, (int64_t{1} << 32) - 1); +} +MovingAverage::~MovingAverage() = default; + +void MovingAverage::AddSample(int sample) { + count_++; + size_t index = count_ % history_.size(); + if (count_ > history_.size()) + sum_ -= history_[index]; + sum_ += sample; + history_[index] = sample; +} + +absl::optional<int> MovingAverage::GetAverageRoundedDown() const { + if (count_ == 0) + return absl::nullopt; + return sum_ / Size(); +} + +absl::optional<int> MovingAverage::GetAverageRoundedToClosest() const { + if (count_ == 0) + return absl::nullopt; + return (sum_ + Size() / 2) / Size(); +} + +absl::optional<double> MovingAverage::GetUnroundedAverage() const { + if (count_ == 0) + return absl::nullopt; + return sum_ / static_cast<double>(Size()); +} + +void MovingAverage::Reset() { + count_ = 0; + sum_ = 0; +} + +size_t MovingAverage::Size() const { + return std::min(count_, history_.size()); +} +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_average.h b/third_party/libwebrtc/rtc_base/numerics/moving_average.h new file mode 100644 index 0000000000..41ce60348e --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_average.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2018 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_MOVING_AVERAGE_H_ +#define RTC_BASE_NUMERICS_MOVING_AVERAGE_H_ + +#include <stddef.h> +#include <stdint.h> + +#include <vector> + +#include "absl/types/optional.h" + +namespace rtc { + +// Calculates average over fixed size window. If there are less than window +// size elements, calculates average of all inserted so far elements. +// +class MovingAverage { + public: + // Maximum supported window size is 2^32 - 1. + explicit MovingAverage(size_t window_size); + ~MovingAverage(); + // MovingAverage is neither copyable nor movable. + MovingAverage(const MovingAverage&) = delete; + MovingAverage& operator=(const MovingAverage&) = delete; + + // Adds new sample. If the window is full, the oldest element is pushed out. + void AddSample(int sample); + + // Returns rounded down average of last `window_size` elements or all + // elements if there are not enough of them. Returns nullopt if there were + // no elements added. + absl::optional<int> GetAverageRoundedDown() const; + + // Same as above but rounded to the closest integer. + absl::optional<int> GetAverageRoundedToClosest() const; + + // Returns unrounded average over the window. + absl::optional<double> GetUnroundedAverage() const; + + // Resets to the initial state before any elements were added. + void Reset(); + + // Returns number of elements in the window. + size_t Size() const; + + private: + // Total number of samples added to the class since last reset. + size_t count_ = 0; + // Sum of the samples in the moving window. + int64_t sum_ = 0; + // Circular buffer for all the samples in the moving window. + // Size is always `window_size` + std::vector<int> history_; +}; + +} // namespace rtc +#endif // RTC_BASE_NUMERICS_MOVING_AVERAGE_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_average_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/moving_average_unittest.cc new file mode 100644 index 0000000000..9bc9a1aef8 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_average_unittest.cc @@ -0,0 +1,87 @@ +/* + * Copyright (c) 2018 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/moving_average.h" + +#include "test/gtest.h" + +namespace test { + +TEST(MovingAverageTest, EmptyAverage) { + rtc::MovingAverage moving_average(1); + EXPECT_EQ(0u, moving_average.Size()); + EXPECT_EQ(absl::nullopt, moving_average.GetAverageRoundedDown()); +} + +// Test single value. +TEST(MovingAverageTest, OneElement) { + rtc::MovingAverage moving_average(1); + moving_average.AddSample(3); + EXPECT_EQ(1u, moving_average.Size()); + EXPECT_EQ(3, *moving_average.GetAverageRoundedDown()); +} + +TEST(MovingAverageTest, GetAverage) { + rtc::MovingAverage moving_average(1024); + moving_average.AddSample(1); + moving_average.AddSample(1); + moving_average.AddSample(3); + moving_average.AddSample(3); + EXPECT_EQ(*moving_average.GetAverageRoundedDown(), 2); + EXPECT_EQ(*moving_average.GetAverageRoundedToClosest(), 2); +} + +TEST(MovingAverageTest, GetAverageRoundedDownRounds) { + rtc::MovingAverage moving_average(1024); + moving_average.AddSample(1); + moving_average.AddSample(2); + moving_average.AddSample(2); + moving_average.AddSample(2); + EXPECT_EQ(*moving_average.GetAverageRoundedDown(), 1); +} + +TEST(MovingAverageTest, GetAverageRoundedToClosestRounds) { + rtc::MovingAverage moving_average(1024); + moving_average.AddSample(1); + moving_average.AddSample(2); + moving_average.AddSample(2); + moving_average.AddSample(2); + EXPECT_EQ(*moving_average.GetAverageRoundedToClosest(), 2); +} + +TEST(MovingAverageTest, Reset) { + rtc::MovingAverage moving_average(5); + moving_average.AddSample(1); + EXPECT_EQ(1, *moving_average.GetAverageRoundedDown()); + EXPECT_EQ(1, *moving_average.GetAverageRoundedToClosest()); + + moving_average.Reset(); + + EXPECT_FALSE(moving_average.GetAverageRoundedDown()); + moving_average.AddSample(10); + EXPECT_EQ(10, *moving_average.GetAverageRoundedDown()); + EXPECT_EQ(10, *moving_average.GetAverageRoundedToClosest()); +} + +TEST(MovingAverageTest, ManySamples) { + rtc::MovingAverage moving_average(10); + for (int i = 1; i < 11; i++) { + moving_average.AddSample(i); + } + EXPECT_EQ(*moving_average.GetAverageRoundedDown(), 5); + EXPECT_EQ(*moving_average.GetAverageRoundedToClosest(), 6); + for (int i = 1; i < 2001; i++) { + moving_average.AddSample(i); + } + EXPECT_EQ(*moving_average.GetAverageRoundedDown(), 1995); + EXPECT_EQ(*moving_average.GetAverageRoundedToClosest(), 1996); +} + +} // namespace test diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_max_counter.h b/third_party/libwebrtc/rtc_base/numerics/moving_max_counter.h new file mode 100644 index 0000000000..5eb45d392b --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_max_counter.h @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2017 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_MOVING_MAX_COUNTER_H_ +#define RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_ + +#include <stdint.h> + +#include <deque> +#include <limits> +#include <utility> + +#include "absl/types/optional.h" +#include "rtc_base/checks.h" + +namespace rtc { + +// Implements moving max: can add samples to it and calculate maximum over some +// fixed moving window. +// +// Window size is configured at constructor. +// Samples can be added with `Add()` and max over current window is returned by +// `MovingMax`. `current_time_ms` in successive calls to Add and MovingMax +// should never decrease as if it's a wallclock time. +template <class T> +class MovingMaxCounter { + public: + explicit MovingMaxCounter(int64_t window_length_ms); + + MovingMaxCounter(const MovingMaxCounter&) = delete; + MovingMaxCounter& operator=(const MovingMaxCounter&) = delete; + + // Advances the current time, and adds a new sample. The new current time must + // be at least as large as the old current time. + void Add(const T& sample, int64_t current_time_ms); + // Advances the current time, and returns the maximum sample in the time + // window ending at the current time. The new current time must be at least as + // large as the old current time. + absl::optional<T> Max(int64_t current_time_ms); + void Reset(); + + private: + // Throws out obsolete samples. + void RollWindow(int64_t new_time_ms); + const int64_t window_length_ms_; + // This deque stores (timestamp, sample) pairs in chronological order; new + // pairs are only ever added at the end. However, because they can't affect + // the Max() calculation, pairs older than window_length_ms_ are discarded, + // and if an older pair has a sample that's smaller than that of a younger + // pair, the older pair is discarded. As a result, the sequence of timestamps + // is strictly increasing, and the sequence of samples is strictly decreasing. + std::deque<std::pair<int64_t, T>> samples_; +#if RTC_DCHECK_IS_ON + int64_t last_call_time_ms_ = std::numeric_limits<int64_t>::min(); +#endif +}; + +template <class T> +MovingMaxCounter<T>::MovingMaxCounter(int64_t window_length_ms) + : window_length_ms_(window_length_ms) {} + +template <class T> +void MovingMaxCounter<T>::Add(const T& sample, int64_t current_time_ms) { + RollWindow(current_time_ms); + // Remove samples that will never be maximum in any window: newly added sample + // will always be in all windows the previous samples are. Thus, smaller or + // equal samples could be removed. This will maintain the invariant - deque + // contains strictly decreasing sequence of values. + while (!samples_.empty() && samples_.back().second <= sample) { + samples_.pop_back(); + } + // Add the new sample but only if there's no existing sample at the same time. + // Due to checks above, the already existing element will be larger, so the + // new sample will never be the maximum in any window. + if (samples_.empty() || samples_.back().first < current_time_ms) { + samples_.emplace_back(std::make_pair(current_time_ms, sample)); + } +} + +template <class T> +absl::optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) { + RollWindow(current_time_ms); + absl::optional<T> res; + if (!samples_.empty()) { + res.emplace(samples_.front().second); + } + return res; +} + +template <class T> +void MovingMaxCounter<T>::Reset() { + samples_.clear(); +} + +template <class T> +void MovingMaxCounter<T>::RollWindow(int64_t new_time_ms) { +#if RTC_DCHECK_IS_ON + RTC_DCHECK_GE(new_time_ms, last_call_time_ms_); + last_call_time_ms_ = new_time_ms; +#endif + const int64_t window_begin_ms = new_time_ms - window_length_ms_; + auto it = samples_.begin(); + while (it != samples_.end() && it->first < window_begin_ms) { + ++it; + } + samples_.erase(samples_.begin(), it); +} + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_MOVING_MAX_COUNTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_max_counter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/moving_max_counter_unittest.cc new file mode 100644 index 0000000000..0e3195f467 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_max_counter_unittest.cc @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2017 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/moving_max_counter.h" + +#include "test/gtest.h" + +TEST(MovingMaxCounter, ReportsMaximumInTheWindow) { + rtc::MovingMaxCounter<int> counter(100); + counter.Add(1, 1); + EXPECT_EQ(counter.Max(1), 1); + counter.Add(2, 30); + EXPECT_EQ(counter.Max(30), 2); + counter.Add(100, 60); + EXPECT_EQ(counter.Max(60), 100); + counter.Add(4, 70); + EXPECT_EQ(counter.Max(70), 100); + counter.Add(5, 90); + EXPECT_EQ(counter.Max(90), 100); +} + +TEST(MovingMaxCounter, IgnoresOldElements) { + rtc::MovingMaxCounter<int> counter(100); + counter.Add(1, 1); + counter.Add(2, 30); + counter.Add(100, 60); + counter.Add(4, 70); + counter.Add(5, 90); + EXPECT_EQ(counter.Max(160), 100); + // 100 is now out of the window. Next maximum is 5. + EXPECT_EQ(counter.Max(161), 5); +} + +TEST(MovingMaxCounter, HandlesEmptyWindow) { + rtc::MovingMaxCounter<int> counter(100); + counter.Add(123, 1); + EXPECT_TRUE(counter.Max(101).has_value()); + EXPECT_FALSE(counter.Max(102).has_value()); +} + +TEST(MovingMaxCounter, HandlesSamplesWithEqualTimestamps) { + rtc::MovingMaxCounter<int> counter(100); + counter.Add(2, 30); + EXPECT_EQ(counter.Max(30), 2); + counter.Add(5, 30); + EXPECT_EQ(counter.Max(30), 5); + counter.Add(4, 30); + EXPECT_EQ(counter.Max(30), 5); + counter.Add(1, 90); + EXPECT_EQ(counter.Max(150), 1); +} diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter.h b/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter.h new file mode 100644 index 0000000000..d68814a25b --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter.h @@ -0,0 +1,103 @@ +/* + * Copyright (c) 2017 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_MOVING_PERCENTILE_FILTER_H_ +#define RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_ + +#include <stddef.h> + +#include <cstddef> +#include <list> + +#include "rtc_base/checks.h" +#include "rtc_base/numerics/percentile_filter.h" + +namespace webrtc { + +// Class to efficiently get moving percentile filter from a stream of samples. +template <typename T> +class MovingPercentileFilter { + public: + // Construct filter. `percentile` defines what percentile to track and + // `window_size` is how many latest samples are stored for finding the + // percentile. `percentile` must be between 0.0 and 1.0 (inclusive) and + // `window_size` must be greater than 0. + MovingPercentileFilter(float percentile, size_t window_size); + + MovingPercentileFilter(const MovingPercentileFilter&) = delete; + MovingPercentileFilter& operator=(const MovingPercentileFilter&) = delete; + + // Insert a new sample. + void Insert(const T& value); + + // Removes all samples; + void Reset(); + + // Get percentile over the latest window. + T GetFilteredValue() const; + + // The number of samples that are currently stored. + size_t GetNumberOfSamplesStored() const; + + private: + PercentileFilter<T> percentile_filter_; + std::list<T> samples_; + size_t samples_stored_; + const size_t window_size_; +}; + +// Convenience type for the common median case. +template <typename T> +class MovingMedianFilter : public MovingPercentileFilter<T> { + public: + explicit MovingMedianFilter(size_t window_size) + : MovingPercentileFilter<T>(0.5f, window_size) {} +}; + +template <typename T> +MovingPercentileFilter<T>::MovingPercentileFilter(float percentile, + size_t window_size) + : percentile_filter_(percentile), + samples_stored_(0), + window_size_(window_size) { + RTC_CHECK_GT(window_size, 0); +} + +template <typename T> +void MovingPercentileFilter<T>::Insert(const T& value) { + percentile_filter_.Insert(value); + samples_.emplace_back(value); + ++samples_stored_; + if (samples_stored_ > window_size_) { + percentile_filter_.Erase(samples_.front()); + samples_.pop_front(); + --samples_stored_; + } +} + +template <typename T> +T MovingPercentileFilter<T>::GetFilteredValue() const { + return percentile_filter_.GetPercentileValue(); +} + +template <typename T> +void MovingPercentileFilter<T>::Reset() { + percentile_filter_.Reset(); + samples_.clear(); + samples_stored_ = 0; +} + +template <typename T> +size_t MovingPercentileFilter<T>::GetNumberOfSamplesStored() const { + return samples_stored_; +} + +} // namespace webrtc +#endif // RTC_BASE_NUMERICS_MOVING_PERCENTILE_FILTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter_unittest.cc new file mode 100644 index 0000000000..30c0ebb23d --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/moving_percentile_filter_unittest.cc @@ -0,0 +1,86 @@ +/* + * Copyright 2017 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/moving_percentile_filter.h" + +#include <stdint.h> + +#include <algorithm> + +#include "test/gtest.h" + +namespace webrtc { + +// 25th percentile can be exactly found with a window of length 4. +TEST(MovingPercentileFilter, Percentile25ReturnsMovingPercentile25WithWindow4) { + MovingPercentileFilter<int> perc25(0.25f, 4); + const int64_t kSamples[10] = {1, 2, 3, 4, 4, 4, 5, 6, 7, 8}; + const int64_t kExpectedFilteredValues[10] = {1, 1, 1, 1, 2, 3, 4, 4, 4, 5}; + for (size_t i = 0; i < 10; ++i) { + perc25.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], perc25.GetFilteredValue()); + EXPECT_EQ(std::min<size_t>(i + 1, 4), perc25.GetNumberOfSamplesStored()); + } +} + +// 90th percentile becomes the 67th percentile with a window of length 4. +TEST(MovingPercentileFilter, Percentile90ReturnsMovingPercentile67WithWindow4) { + MovingPercentileFilter<int> perc67(0.67f, 4); + MovingPercentileFilter<int> perc90(0.9f, 4); + const int64_t kSamples[8] = {1, 10, 1, 9, 1, 10, 1, 8}; + const int64_t kExpectedFilteredValues[9] = {1, 1, 1, 9, 9, 9, 9, 8}; + for (size_t i = 0; i < 8; ++i) { + perc67.Insert(kSamples[i]); + perc90.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], perc67.GetFilteredValue()); + EXPECT_EQ(kExpectedFilteredValues[i], perc90.GetFilteredValue()); + } +} + +TEST(MovingMedianFilterTest, ProcessesNoSamples) { + MovingMedianFilter<int> filter(2); + EXPECT_EQ(0, filter.GetFilteredValue()); + EXPECT_EQ(0u, filter.GetNumberOfSamplesStored()); +} + +TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow5) { + MovingMedianFilter<int> filter(5); + const int64_t kSamples[5] = {1, 5, 2, 3, 4}; + const int64_t kExpectedFilteredValues[5] = {1, 1, 2, 2, 3}; + for (size_t i = 0; i < 5; ++i) { + filter.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue()); + EXPECT_EQ(i + 1, filter.GetNumberOfSamplesStored()); + } +} + +TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow3) { + MovingMedianFilter<int> filter(3); + const int64_t kSamples[5] = {1, 5, 2, 3, 4}; + const int64_t kExpectedFilteredValues[5] = {1, 1, 2, 3, 3}; + for (int i = 0; i < 5; ++i) { + filter.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue()); + EXPECT_EQ(std::min<size_t>(i + 1, 3), filter.GetNumberOfSamplesStored()); + } +} + +TEST(MovingMedianFilterTest, ReturnsMovingMedianWindow1) { + MovingMedianFilter<int> filter(1); + const int64_t kSamples[5] = {1, 5, 2, 3, 4}; + const int64_t kExpectedFilteredValues[5] = {1, 5, 2, 3, 4}; + for (int i = 0; i < 5; ++i) { + filter.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue()); + EXPECT_EQ(1u, filter.GetNumberOfSamplesStored()); + } +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/percentile_filter.h b/third_party/libwebrtc/rtc_base/numerics/percentile_filter.h new file mode 100644 index 0000000000..2a18c1aa73 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/percentile_filter.h @@ -0,0 +1,124 @@ +/* + * Copyright (c) 2016 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_PERCENTILE_FILTER_H_ +#define RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_ + +#include <stdint.h> + +#include <iterator> +#include <set> + +#include "rtc_base/checks.h" + +namespace webrtc { + +// Class to efficiently get the percentile value from a group of observations. +// The percentile is the value below which a given percentage of the +// observations fall. +template <typename T> +class PercentileFilter { + public: + // Construct filter. `percentile` should be between 0 and 1. + explicit PercentileFilter(float percentile); + + // Insert one observation. The complexity of this operation is logarithmic in + // the size of the container. + void Insert(const T& value); + + // Remove one observation or return false if `value` doesn't exist in the + // container. The complexity of this operation is logarithmic in the size of + // the container. + bool Erase(const T& value); + + // Get the percentile value. The complexity of this operation is constant. + T GetPercentileValue() const; + + // Removes all the stored observations. + void Reset(); + + private: + // Update iterator and index to point at target percentile value. + void UpdatePercentileIterator(); + + const float percentile_; + std::multiset<T> set_; + // Maintain iterator and index of current target percentile value. + typename std::multiset<T>::iterator percentile_it_; + int64_t percentile_index_; +}; + +template <typename T> +PercentileFilter<T>::PercentileFilter(float percentile) + : percentile_(percentile), + percentile_it_(set_.begin()), + percentile_index_(0) { + RTC_CHECK_GE(percentile, 0.0f); + RTC_CHECK_LE(percentile, 1.0f); +} + +template <typename T> +void PercentileFilter<T>::Insert(const T& value) { + // Insert element at the upper bound. + set_.insert(value); + if (set_.size() == 1u) { + // First element inserted - initialize percentile iterator and index. + percentile_it_ = set_.begin(); + percentile_index_ = 0; + } else if (value < *percentile_it_) { + // If new element is before us, increment `percentile_index_`. + ++percentile_index_; + } + UpdatePercentileIterator(); +} + +template <typename T> +bool PercentileFilter<T>::Erase(const T& value) { + typename std::multiset<T>::const_iterator it = set_.lower_bound(value); + // Ignore erase operation if the element is not present in the current set. + if (it == set_.end() || *it != value) + return false; + if (it == percentile_it_) { + // If same iterator, update to the following element. Index is not + // affected. + percentile_it_ = set_.erase(it); + } else { + set_.erase(it); + // If erased element was before us, decrement `percentile_index_`. + if (value <= *percentile_it_) + --percentile_index_; + } + UpdatePercentileIterator(); + return true; +} + +template <typename T> +void PercentileFilter<T>::UpdatePercentileIterator() { + if (set_.empty()) + return; + const int64_t index = static_cast<int64_t>(percentile_ * (set_.size() - 1)); + std::advance(percentile_it_, index - percentile_index_); + percentile_index_ = index; +} + +template <typename T> +T PercentileFilter<T>::GetPercentileValue() const { + return set_.empty() ? 0 : *percentile_it_; +} + +template <typename T> +void PercentileFilter<T>::Reset() { + set_.clear(); + percentile_it_ = set_.begin(); + percentile_index_ = 0; +} +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_PERCENTILE_FILTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/percentile_filter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/percentile_filter_unittest.cc new file mode 100644 index 0000000000..d6baa32001 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/percentile_filter_unittest.cc @@ -0,0 +1,142 @@ +/* + * Copyright 2016 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/percentile_filter.h" + +#include <stdlib.h> + +#include <array> +#include <climits> +#include <cstdint> +#include <random> + +#include "absl/algorithm/container.h" +#include "test/gtest.h" + +namespace webrtc { + +class PercentileFilterTest : public ::testing::TestWithParam<float> { + public: + PercentileFilterTest() : filter_(GetParam()) { + // Make sure the tests are deterministic by seeding with a constant. + srand(42); + } + + PercentileFilterTest(const PercentileFilterTest&) = delete; + PercentileFilterTest& operator=(const PercentileFilterTest&) = delete; + + protected: + PercentileFilter<int64_t> filter_; +}; + +INSTANTIATE_TEST_SUITE_P(PercentileFilterTests, + PercentileFilterTest, + ::testing::Values(0.0f, 0.1f, 0.5f, 0.9f, 1.0f)); + +TEST(PercentileFilterTest, MinFilter) { + PercentileFilter<int64_t> filter(0.0f); + filter.Insert(4); + EXPECT_EQ(4, filter.GetPercentileValue()); + filter.Insert(3); + EXPECT_EQ(3, filter.GetPercentileValue()); +} + +TEST(PercentileFilterTest, MaxFilter) { + PercentileFilter<int64_t> filter(1.0f); + filter.Insert(3); + EXPECT_EQ(3, filter.GetPercentileValue()); + filter.Insert(4); + EXPECT_EQ(4, filter.GetPercentileValue()); +} + +TEST(PercentileFilterTest, MedianFilterDouble) { + PercentileFilter<double> filter(0.5f); + filter.Insert(2.71828); + filter.Insert(3.14159); + filter.Insert(1.41421); + EXPECT_EQ(2.71828, filter.GetPercentileValue()); +} + +TEST(PercentileFilterTest, MedianFilterInt) { + PercentileFilter<int> filter(0.5f); + filter.Insert(INT_MIN); + filter.Insert(1); + filter.Insert(2); + EXPECT_EQ(1, filter.GetPercentileValue()); + filter.Insert(INT_MAX); + filter.Erase(INT_MIN); + EXPECT_EQ(2, filter.GetPercentileValue()); +} + +TEST(PercentileFilterTest, MedianFilterUnsigned) { + PercentileFilter<unsigned> filter(0.5f); + filter.Insert(UINT_MAX); + filter.Insert(2u); + filter.Insert(1u); + EXPECT_EQ(2u, filter.GetPercentileValue()); + filter.Insert(0u); + filter.Erase(UINT_MAX); + EXPECT_EQ(1u, filter.GetPercentileValue()); +} + +TEST_P(PercentileFilterTest, EmptyFilter) { + EXPECT_EQ(0, filter_.GetPercentileValue()); + filter_.Insert(3); + bool success = filter_.Erase(3); + EXPECT_TRUE(success); + EXPECT_EQ(0, filter_.GetPercentileValue()); +} + +TEST_P(PercentileFilterTest, EraseNonExistingElement) { + bool success = filter_.Erase(3); + EXPECT_FALSE(success); + EXPECT_EQ(0, filter_.GetPercentileValue()); + filter_.Insert(4); + success = filter_.Erase(3); + EXPECT_FALSE(success); + EXPECT_EQ(4, filter_.GetPercentileValue()); +} + +TEST_P(PercentileFilterTest, DuplicateElements) { + filter_.Insert(3); + filter_.Insert(3); + filter_.Erase(3); + EXPECT_EQ(3, filter_.GetPercentileValue()); +} + +TEST_P(PercentileFilterTest, InsertAndEraseTenValuesInRandomOrder) { + std::array<int64_t, 10> zero_to_nine = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + // The percentile value of the ten values above. + const int64_t expected_value = static_cast<int64_t>(GetParam() * 9); + + // Insert two sets of `zero_to_nine` in random order. + for (int i = 0; i < 2; ++i) { + absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()())); + for (int64_t value : zero_to_nine) + filter_.Insert(value); + // After inserting a full set of `zero_to_nine`, the percentile should + // stay constant. + EXPECT_EQ(expected_value, filter_.GetPercentileValue()); + } + + // Insert and erase sets of `zero_to_nine` in random order a few times. + for (int i = 0; i < 3; ++i) { + absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()())); + for (int64_t value : zero_to_nine) + filter_.Erase(value); + EXPECT_EQ(expected_value, filter_.GetPercentileValue()); + absl::c_shuffle(zero_to_nine, std::mt19937(std::random_device()())); + for (int64_t value : zero_to_nine) + filter_.Insert(value); + EXPECT_EQ(expected_value, filter_.GetPercentileValue()); + } +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/running_statistics.h b/third_party/libwebrtc/rtc_base/numerics/running_statistics.h new file mode 100644 index 0000000000..bbcc7e2a73 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/running_statistics.h @@ -0,0 +1,161 @@ +/* + * Copyright (c) 2019 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 API_NUMERICS_RUNNING_STATISTICS_H_ +#define API_NUMERICS_RUNNING_STATISTICS_H_ + +#include <algorithm> +#include <cmath> +#include <limits> + +#include "absl/types/optional.h" +#include "rtc_base/checks.h" +#include "rtc_base/numerics/math_utils.h" + +namespace webrtc { +namespace webrtc_impl { + +// tl;dr: Robust and efficient online computation of statistics, +// using Welford's method for variance. [1] +// +// This should be your go-to class if you ever need to compute +// min, max, mean, variance and standard deviation. +// If you need to get percentiles, please use webrtc::SamplesStatsCounter. +// +// Please note RemoveSample() won't affect min and max. +// If you want a full-fledged moving window over N last samples, +// please use webrtc::RollingAccumulator. +// +// The measures return absl::nullopt if no samples were fed (Size() == 0), +// otherwise the returned optional is guaranteed to contain a value. +// +// [1] +// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm + +// The type T is a scalar which must be convertible to double. +// Rationale: we often need greater precision for measures +// than for the samples themselves. +template <typename T> +class RunningStatistics { + public: + // Update stats //////////////////////////////////////////// + + // Add a value participating in the statistics in O(1) time. + void AddSample(T sample) { + max_ = std::max(max_, sample); + min_ = std::min(min_, sample); + ++size_; + // Welford's incremental update. + const double delta = sample - mean_; + mean_ += delta / size_; + const double delta2 = sample - mean_; + cumul_ += delta * delta2; + } + + // Remove a previously added value in O(1) time. + // Nb: This doesn't affect min or max. + // Calling RemoveSample when Size()==0 is incorrect. + void RemoveSample(T sample) { + RTC_DCHECK_GT(Size(), 0); + // In production, just saturate at 0. + if (Size() == 0) { + return; + } + // Since samples order doesn't matter, this is the + // exact reciprocal of Welford's incremental update. + --size_; + const double delta = sample - mean_; + mean_ -= delta / size_; + const double delta2 = sample - mean_; + cumul_ -= delta * delta2; + } + + // Merge other stats, as if samples were added one by one, but in O(1). + void MergeStatistics(const RunningStatistics<T>& other) { + if (other.size_ == 0) { + return; + } + max_ = std::max(max_, other.max_); + min_ = std::min(min_, other.min_); + const int64_t new_size = size_ + other.size_; + const double new_mean = + (mean_ * size_ + other.mean_ * other.size_) / new_size; + // Each cumulant must be corrected. + // * from: sum((x_i - mean_)²) + // * to: sum((x_i - new_mean)²) + auto delta = [new_mean](const RunningStatistics<T>& stats) { + return stats.size_ * (new_mean * (new_mean - 2 * stats.mean_) + + stats.mean_ * stats.mean_); + }; + cumul_ = cumul_ + delta(*this) + other.cumul_ + delta(other); + mean_ = new_mean; + size_ = new_size; + } + + // Get Measures //////////////////////////////////////////// + + // Returns number of samples involved via AddSample() or MergeStatistics(), + // minus number of times RemoveSample() was called. + int64_t Size() const { return size_; } + + // Returns minimum among all seen samples, in O(1) time. + // This isn't affected by RemoveSample(). + absl::optional<T> GetMin() const { + if (size_ == 0) { + return absl::nullopt; + } + return min_; + } + + // Returns maximum among all seen samples, in O(1) time. + // This isn't affected by RemoveSample(). + absl::optional<T> GetMax() const { + if (size_ == 0) { + return absl::nullopt; + } + return max_; + } + + // Returns mean in O(1) time. + absl::optional<double> GetMean() const { + if (size_ == 0) { + return absl::nullopt; + } + return mean_; + } + + // Returns unbiased sample variance in O(1) time. + absl::optional<double> GetVariance() const { + if (size_ == 0) { + return absl::nullopt; + } + return cumul_ / size_; + } + + // Returns unbiased standard deviation in O(1) time. + absl::optional<double> GetStandardDeviation() const { + if (size_ == 0) { + return absl::nullopt; + } + return std::sqrt(*GetVariance()); + } + + private: + int64_t size_ = 0; // Samples seen. + T min_ = infinity_or_max<T>(); + T max_ = minus_infinity_or_min<T>(); + double mean_ = 0; + double cumul_ = 0; // Variance * size_, sometimes noted m2. +}; + +} // namespace webrtc_impl +} // namespace webrtc + +#endif // API_NUMERICS_RUNNING_STATISTICS_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/running_statistics_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/running_statistics_unittest.cc new file mode 100644 index 0000000000..d593f3fc5a --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/running_statistics_unittest.cc @@ -0,0 +1,196 @@ +/* + * Copyright (c) 2016 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/running_statistics.h" + +#include <math.h> + +#include <random> +#include <vector> + +#include "absl/algorithm/container.h" +#include "test/gtest.h" + +// Tests were copied from samples_stats_counter_unittest.cc. + +namespace webrtc { +namespace webrtc_impl { +namespace { + +RunningStatistics<double> CreateStatsFilledWithIntsFrom1ToN(int n) { + std::vector<double> data; + for (int i = 1; i <= n; i++) { + data.push_back(i); + } + absl::c_shuffle(data, std::mt19937(std::random_device()())); + + RunningStatistics<double> stats; + for (double v : data) { + stats.AddSample(v); + } + return stats; +} + +// Add n samples drawn from uniform distribution in [a;b]. +RunningStatistics<double> CreateStatsFromUniformDistribution(int n, + double a, + double b) { + std::mt19937 gen{std::random_device()()}; + std::uniform_real_distribution<> dis(a, b); + + RunningStatistics<double> stats; + for (int i = 1; i <= n; i++) { + stats.AddSample(dis(gen)); + } + return stats; +} + +class RunningStatisticsTest : public ::testing::TestWithParam<int> {}; + +constexpr int SIZE_FOR_MERGE = 5; + +TEST(RunningStatistics, FullSimpleTest) { + auto stats = CreateStatsFilledWithIntsFrom1ToN(100); + + EXPECT_DOUBLE_EQ(*stats.GetMin(), 1.0); + EXPECT_DOUBLE_EQ(*stats.GetMax(), 100.0); + // EXPECT_DOUBLE_EQ is too strict (max 4 ULP) for this one. + ASSERT_NEAR(*stats.GetMean(), 50.5, 1e-10); +} + +TEST(RunningStatistics, VarianceAndDeviation) { + RunningStatistics<int> stats; + stats.AddSample(2); + stats.AddSample(2); + stats.AddSample(-1); + stats.AddSample(5); + + EXPECT_DOUBLE_EQ(*stats.GetMean(), 2.0); + EXPECT_DOUBLE_EQ(*stats.GetVariance(), 4.5); + EXPECT_DOUBLE_EQ(*stats.GetStandardDeviation(), sqrt(4.5)); +} + +TEST(RunningStatistics, RemoveSample) { + // We check that adding then removing sample is no-op, + // or so (due to loss of precision). + RunningStatistics<int> stats; + stats.AddSample(2); + stats.AddSample(2); + stats.AddSample(-1); + stats.AddSample(5); + + constexpr int iterations = 1e5; + for (int i = 0; i < iterations; ++i) { + stats.AddSample(i); + stats.RemoveSample(i); + + EXPECT_NEAR(*stats.GetMean(), 2.0, 1e-8); + EXPECT_NEAR(*stats.GetVariance(), 4.5, 1e-3); + EXPECT_NEAR(*stats.GetStandardDeviation(), sqrt(4.5), 1e-4); + } +} + +TEST(RunningStatistics, RemoveSamplesSequence) { + // We check that adding then removing a sequence of samples is no-op, + // or so (due to loss of precision). + RunningStatistics<int> stats; + stats.AddSample(2); + stats.AddSample(2); + stats.AddSample(-1); + stats.AddSample(5); + + constexpr int iterations = 1e4; + for (int i = 0; i < iterations; ++i) { + stats.AddSample(i); + } + for (int i = 0; i < iterations; ++i) { + stats.RemoveSample(i); + } + + EXPECT_NEAR(*stats.GetMean(), 2.0, 1e-7); + EXPECT_NEAR(*stats.GetVariance(), 4.5, 1e-3); + EXPECT_NEAR(*stats.GetStandardDeviation(), sqrt(4.5), 1e-4); +} + +TEST(RunningStatistics, VarianceFromUniformDistribution) { + // Check variance converge to 1/12 for [0;1) uniform distribution. + // Acts as a sanity check for NumericStabilityForVariance test. + auto stats = CreateStatsFromUniformDistribution(1e6, 0, 1); + + EXPECT_NEAR(*stats.GetVariance(), 1. / 12, 1e-3); +} + +TEST(RunningStatistics, NumericStabilityForVariance) { + // Same test as VarianceFromUniformDistribution, + // except the range is shifted to [1e9;1e9+1). + // Variance should also converge to 1/12. + // NB: Although we lose precision for the samples themselves, the fractional + // part still enjoys 22 bits of mantissa and errors should even out, + // so that couldn't explain a mismatch. + auto stats = CreateStatsFromUniformDistribution(1e6, 1e9, 1e9 + 1); + + EXPECT_NEAR(*stats.GetVariance(), 1. / 12, 1e-3); +} + +TEST(RunningStatistics, MinRemainsUnchangedAfterRemove) { + // We don't want to recompute min (that's RollingAccumulator's role), + // check we get the overall min. + RunningStatistics<int> stats; + stats.AddSample(1); + stats.AddSample(2); + stats.RemoveSample(1); + EXPECT_EQ(stats.GetMin(), 1); +} + +TEST(RunningStatistics, MaxRemainsUnchangedAfterRemove) { + // We don't want to recompute max (that's RollingAccumulator's role), + // check we get the overall max. + RunningStatistics<int> stats; + stats.AddSample(1); + stats.AddSample(2); + stats.RemoveSample(2); + EXPECT_EQ(stats.GetMax(), 2); +} + +TEST_P(RunningStatisticsTest, MergeStatistics) { + int data[SIZE_FOR_MERGE] = {2, 2, -1, 5, 10}; + // Split the data in different partitions. + // We have 6 distinct tests: + // * Empty merged with full sequence. + // * 1 sample merged with 4 last. + // * 2 samples merged with 3 last. + // [...] + // * Full merged with empty sequence. + // All must lead to the same result. + // I miss QuickCheck so much. + RunningStatistics<int> stats0, stats1; + for (int i = 0; i < GetParam(); ++i) { + stats0.AddSample(data[i]); + } + for (int i = GetParam(); i < SIZE_FOR_MERGE; ++i) { + stats1.AddSample(data[i]); + } + stats0.MergeStatistics(stats1); + + EXPECT_EQ(stats0.Size(), SIZE_FOR_MERGE); + EXPECT_DOUBLE_EQ(*stats0.GetMin(), -1); + EXPECT_DOUBLE_EQ(*stats0.GetMax(), 10); + EXPECT_DOUBLE_EQ(*stats0.GetMean(), 3.6); + EXPECT_DOUBLE_EQ(*stats0.GetVariance(), 13.84); + EXPECT_DOUBLE_EQ(*stats0.GetStandardDeviation(), sqrt(13.84)); +} + +INSTANTIATE_TEST_SUITE_P(RunningStatisticsTests, + RunningStatisticsTest, + ::testing::Range(0, SIZE_FOR_MERGE + 1)); + +} // namespace +} // namespace webrtc_impl +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_compare.h b/third_party/libwebrtc/rtc_base/numerics/safe_compare.h new file mode 100644 index 0000000000..85f0a30e83 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_compare.h @@ -0,0 +1,176 @@ +/* + * Copyright 2016 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. + */ + +// This file defines six constexpr functions: +// +// rtc::SafeEq // == +// rtc::SafeNe // != +// rtc::SafeLt // < +// rtc::SafeLe // <= +// rtc::SafeGt // > +// rtc::SafeGe // >= +// +// They each accept two arguments of arbitrary types, and in almost all cases, +// they simply call the appropriate comparison operator. However, if both +// arguments are integers, they don't compare them using C++'s quirky rules, +// but instead adhere to the true mathematical definitions. It is as if the +// arguments were first converted to infinite-range signed integers, and then +// compared, although of course nothing expensive like that actually takes +// place. In practice, for signed/signed and unsigned/unsigned comparisons and +// some mixed-signed comparisons with a compile-time constant, the overhead is +// zero; in the remaining cases, it is just a few machine instructions (no +// branches). + +#ifndef RTC_BASE_NUMERICS_SAFE_COMPARE_H_ +#define RTC_BASE_NUMERICS_SAFE_COMPARE_H_ + +#include <stddef.h> +#include <stdint.h> + +#include <type_traits> +#include <utility> + +#include "rtc_base/type_traits.h" + +namespace rtc { + +namespace safe_cmp_impl { + +template <size_t N> +struct LargerIntImpl : std::false_type {}; +template <> +struct LargerIntImpl<sizeof(int8_t)> : std::true_type { + using type = int16_t; +}; +template <> +struct LargerIntImpl<sizeof(int16_t)> : std::true_type { + using type = int32_t; +}; +template <> +struct LargerIntImpl<sizeof(int32_t)> : std::true_type { + using type = int64_t; +}; + +// LargerInt<T1, T2>::value is true iff there's a signed type that's larger +// than T1 (and no larger than the larger of T2 and int*, for performance +// reasons); and if there is such a type, LargerInt<T1, T2>::type is an alias +// for it. +template <typename T1, typename T2> +struct LargerInt + : LargerIntImpl<sizeof(T1) < sizeof(T2) || sizeof(T1) < sizeof(int*) + ? sizeof(T1) + : 0> {}; + +template <typename T> +constexpr typename std::make_unsigned<T>::type MakeUnsigned(T a) { + return static_cast<typename std::make_unsigned<T>::type>(a); +} + +// Overload for when both T1 and T2 have the same signedness. +template <typename Op, + typename T1, + typename T2, + typename std::enable_if<std::is_signed<T1>::value == + std::is_signed<T2>::value>::type* = nullptr> +constexpr bool Cmp(T1 a, T2 b) { + return Op::Op(a, b); +} + +// Overload for signed - unsigned comparison that can be promoted to a bigger +// signed type. +template <typename Op, + typename T1, + typename T2, + typename std::enable_if<std::is_signed<T1>::value && + std::is_unsigned<T2>::value && + LargerInt<T2, T1>::value>::type* = nullptr> +constexpr bool Cmp(T1 a, T2 b) { + return Op::Op(a, static_cast<typename LargerInt<T2, T1>::type>(b)); +} + +// Overload for unsigned - signed comparison that can be promoted to a bigger +// signed type. +template <typename Op, + typename T1, + typename T2, + typename std::enable_if<std::is_unsigned<T1>::value && + std::is_signed<T2>::value && + LargerInt<T1, T2>::value>::type* = nullptr> +constexpr bool Cmp(T1 a, T2 b) { + return Op::Op(static_cast<typename LargerInt<T1, T2>::type>(a), b); +} + +// Overload for signed - unsigned comparison that can't be promoted to a bigger +// signed type. +template <typename Op, + typename T1, + typename T2, + typename std::enable_if<std::is_signed<T1>::value && + std::is_unsigned<T2>::value && + !LargerInt<T2, T1>::value>::type* = nullptr> +constexpr bool Cmp(T1 a, T2 b) { + return a < 0 ? Op::Op(-1, 0) : Op::Op(safe_cmp_impl::MakeUnsigned(a), b); +} + +// Overload for unsigned - signed comparison that can't be promoted to a bigger +// signed type. +template <typename Op, + typename T1, + typename T2, + typename std::enable_if<std::is_unsigned<T1>::value && + std::is_signed<T2>::value && + !LargerInt<T1, T2>::value>::type* = nullptr> +constexpr bool Cmp(T1 a, T2 b) { + return b < 0 ? Op::Op(0, -1) : Op::Op(a, safe_cmp_impl::MakeUnsigned(b)); +} + +#define RTC_SAFECMP_MAKE_OP(name, op) \ + struct name { \ + template <typename T1, typename T2> \ + static constexpr bool Op(T1 a, T2 b) { \ + return a op b; \ + } \ + }; +RTC_SAFECMP_MAKE_OP(EqOp, ==) +RTC_SAFECMP_MAKE_OP(NeOp, !=) +RTC_SAFECMP_MAKE_OP(LtOp, <) +RTC_SAFECMP_MAKE_OP(LeOp, <=) +RTC_SAFECMP_MAKE_OP(GtOp, >) +RTC_SAFECMP_MAKE_OP(GeOp, >=) +#undef RTC_SAFECMP_MAKE_OP + +} // namespace safe_cmp_impl + +#define RTC_SAFECMP_MAKE_FUN(name) \ + template <typename T1, typename T2> \ + constexpr \ + typename std::enable_if<IsIntlike<T1>::value && IsIntlike<T2>::value, \ + bool>::type Safe##name(T1 a, T2 b) { \ + /* Unary plus here turns enums into real integral types. */ \ + return safe_cmp_impl::Cmp<safe_cmp_impl::name##Op>(+a, +b); \ + } \ + template <typename T1, typename T2> \ + constexpr \ + typename std::enable_if<!IsIntlike<T1>::value || !IsIntlike<T2>::value, \ + bool>::type Safe##name(const T1& a, \ + const T2& b) { \ + return safe_cmp_impl::name##Op::Op(a, b); \ + } +RTC_SAFECMP_MAKE_FUN(Eq) +RTC_SAFECMP_MAKE_FUN(Ne) +RTC_SAFECMP_MAKE_FUN(Lt) +RTC_SAFECMP_MAKE_FUN(Le) +RTC_SAFECMP_MAKE_FUN(Gt) +RTC_SAFECMP_MAKE_FUN(Ge) +#undef RTC_SAFECMP_MAKE_FUN + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_SAFE_COMPARE_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_compare_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/safe_compare_unittest.cc new file mode 100644 index 0000000000..92bde686ba --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_compare_unittest.cc @@ -0,0 +1,395 @@ +/* + * Copyright 2016 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/safe_compare.h" + +#include <limits> + +#include "test/gtest.h" + +namespace rtc { + +namespace { + +constexpr std::uintmax_t umax = std::numeric_limits<std::uintmax_t>::max(); +constexpr std::intmax_t imin = std::numeric_limits<std::intmax_t>::min(); +constexpr std::intmax_t m1 = -1; + +// m1 and umax have the same representation because we use 2's complement +// arithmetic, so naive casting will confuse them. +static_assert(static_cast<std::uintmax_t>(m1) == umax, ""); +static_assert(m1 == static_cast<std::intmax_t>(umax), ""); + +static const std::pair<int, int> p1(1, 1); +static const std::pair<int, int> p2(1, 2); + +} // namespace + +// clang-format off + +// These functions aren't used in the tests, but it's useful to look at the +// compiler output for them, and verify that (1) the same-signedness *Safe +// functions result in exactly the same code as their *Ref counterparts, and +// that (2) the mixed-signedness *Safe functions have just a few extra +// arithmetic and logic instructions (but no extra control flow instructions). +bool TestLessThanRef( int a, int b) { return a < b; } +bool TestLessThanRef( unsigned a, unsigned b) { return a < b; } +bool TestLessThanSafe( int a, int b) { return SafeLt(a, b); } +bool TestLessThanSafe(unsigned a, unsigned b) { return SafeLt(a, b); } +bool TestLessThanSafe(unsigned a, int b) { return SafeLt(a, b); } +bool TestLessThanSafe( int a, unsigned b) { return SafeLt(a, b); } + +// For these, we expect the *Ref and *Safe functions to result in identical +// code, except for the ones that compare a signed variable with an unsigned +// constant; in that case, the *Ref function does an unsigned comparison (fast +// but incorrect) and the *Safe function spends a few extra instructions on +// doing it right. +bool TestLessThan17Ref( int a) { return a < 17; } +bool TestLessThan17Ref( unsigned a) { return a < 17; } +bool TestLessThan17uRef( int a) { return static_cast<unsigned>(a) < 17u; } +bool TestLessThan17uRef( unsigned a) { return a < 17u; } +bool TestLessThan17Safe( int a) { return SafeLt(a, 17); } +bool TestLessThan17Safe( unsigned a) { return SafeLt(a, 17); } +bool TestLessThan17uSafe( int a) { return SafeLt(a, 17u); } +bool TestLessThan17uSafe(unsigned a) { return SafeLt(a, 17u); } + +// Cases where we can't convert to a larger signed type. +bool TestLessThanMax( intmax_t a, uintmax_t b) { return SafeLt(a, b); } +bool TestLessThanMax(uintmax_t a, intmax_t b) { return SafeLt(a, b); } +bool TestLessThanMax17u( intmax_t a) { return SafeLt(a, uintmax_t{17}); } +bool TestLessThanMax17( uintmax_t a) { return SafeLt(a, intmax_t{17}); } + +// Cases where the compiler should be able to compute the result at compile +// time. +bool TestLessThanConst1() { return SafeLt( -1, 1); } +bool TestLessThanConst2() { return SafeLt( m1, umax); } +bool TestLessThanConst3() { return SafeLt(umax, imin); } +bool TestLessThanConst4(unsigned a) { return SafeLt( a, -1); } +bool TestLessThanConst5(unsigned a) { return SafeLt(-1, a); } +bool TestLessThanConst6(unsigned a) { return SafeLt( a, a); } + +// clang-format on + +TEST(SafeCmpTest, Eq) { + static_assert(!SafeEq(-1, 2), ""); + static_assert(!SafeEq(-1, 2u), ""); + static_assert(!SafeEq(2, -1), ""); + static_assert(!SafeEq(2u, -1), ""); + + static_assert(!SafeEq(1, 2), ""); + static_assert(!SafeEq(1, 2u), ""); + static_assert(!SafeEq(1u, 2), ""); + static_assert(!SafeEq(1u, 2u), ""); + static_assert(!SafeEq(2, 1), ""); + static_assert(!SafeEq(2, 1u), ""); + static_assert(!SafeEq(2u, 1), ""); + static_assert(!SafeEq(2u, 1u), ""); + + static_assert(SafeEq(2, 2), ""); + static_assert(SafeEq(2, 2u), ""); + static_assert(SafeEq(2u, 2), ""); + static_assert(SafeEq(2u, 2u), ""); + + static_assert(SafeEq(imin, imin), ""); + static_assert(!SafeEq(imin, umax), ""); + static_assert(!SafeEq(umax, imin), ""); + static_assert(SafeEq(umax, umax), ""); + + static_assert(SafeEq(m1, m1), ""); + static_assert(!SafeEq(m1, umax), ""); + static_assert(!SafeEq(umax, m1), ""); + static_assert(SafeEq(umax, umax), ""); + + static_assert(!SafeEq(1, 2), ""); + static_assert(!SafeEq(1, 2.0), ""); + static_assert(!SafeEq(1.0, 2), ""); + static_assert(!SafeEq(1.0, 2.0), ""); + static_assert(!SafeEq(2, 1), ""); + static_assert(!SafeEq(2, 1.0), ""); + static_assert(!SafeEq(2.0, 1), ""); + static_assert(!SafeEq(2.0, 1.0), ""); + + static_assert(SafeEq(2, 2), ""); + static_assert(SafeEq(2, 2.0), ""); + static_assert(SafeEq(2.0, 2), ""); + static_assert(SafeEq(2.0, 2.0), ""); + + EXPECT_TRUE(SafeEq(p1, p1)); + EXPECT_FALSE(SafeEq(p1, p2)); + EXPECT_FALSE(SafeEq(p2, p1)); + EXPECT_TRUE(SafeEq(p2, p2)); +} + +TEST(SafeCmpTest, Ne) { + static_assert(SafeNe(-1, 2), ""); + static_assert(SafeNe(-1, 2u), ""); + static_assert(SafeNe(2, -1), ""); + static_assert(SafeNe(2u, -1), ""); + + static_assert(SafeNe(1, 2), ""); + static_assert(SafeNe(1, 2u), ""); + static_assert(SafeNe(1u, 2), ""); + static_assert(SafeNe(1u, 2u), ""); + static_assert(SafeNe(2, 1), ""); + static_assert(SafeNe(2, 1u), ""); + static_assert(SafeNe(2u, 1), ""); + static_assert(SafeNe(2u, 1u), ""); + + static_assert(!SafeNe(2, 2), ""); + static_assert(!SafeNe(2, 2u), ""); + static_assert(!SafeNe(2u, 2), ""); + static_assert(!SafeNe(2u, 2u), ""); + + static_assert(!SafeNe(imin, imin), ""); + static_assert(SafeNe(imin, umax), ""); + static_assert(SafeNe(umax, imin), ""); + static_assert(!SafeNe(umax, umax), ""); + + static_assert(!SafeNe(m1, m1), ""); + static_assert(SafeNe(m1, umax), ""); + static_assert(SafeNe(umax, m1), ""); + static_assert(!SafeNe(umax, umax), ""); + + static_assert(SafeNe(1, 2), ""); + static_assert(SafeNe(1, 2.0), ""); + static_assert(SafeNe(1.0, 2), ""); + static_assert(SafeNe(1.0, 2.0), ""); + static_assert(SafeNe(2, 1), ""); + static_assert(SafeNe(2, 1.0), ""); + static_assert(SafeNe(2.0, 1), ""); + static_assert(SafeNe(2.0, 1.0), ""); + + static_assert(!SafeNe(2, 2), ""); + static_assert(!SafeNe(2, 2.0), ""); + static_assert(!SafeNe(2.0, 2), ""); + static_assert(!SafeNe(2.0, 2.0), ""); + + EXPECT_FALSE(SafeNe(p1, p1)); + EXPECT_TRUE(SafeNe(p1, p2)); + EXPECT_TRUE(SafeNe(p2, p1)); + EXPECT_FALSE(SafeNe(p2, p2)); +} + +TEST(SafeCmpTest, Lt) { + static_assert(SafeLt(-1, 2), ""); + static_assert(SafeLt(-1, 2u), ""); + static_assert(!SafeLt(2, -1), ""); + static_assert(!SafeLt(2u, -1), ""); + + static_assert(SafeLt(1, 2), ""); + static_assert(SafeLt(1, 2u), ""); + static_assert(SafeLt(1u, 2), ""); + static_assert(SafeLt(1u, 2u), ""); + static_assert(!SafeLt(2, 1), ""); + static_assert(!SafeLt(2, 1u), ""); + static_assert(!SafeLt(2u, 1), ""); + static_assert(!SafeLt(2u, 1u), ""); + + static_assert(!SafeLt(2, 2), ""); + static_assert(!SafeLt(2, 2u), ""); + static_assert(!SafeLt(2u, 2), ""); + static_assert(!SafeLt(2u, 2u), ""); + + static_assert(!SafeLt(imin, imin), ""); + static_assert(SafeLt(imin, umax), ""); + static_assert(!SafeLt(umax, imin), ""); + static_assert(!SafeLt(umax, umax), ""); + + static_assert(!SafeLt(m1, m1), ""); + static_assert(SafeLt(m1, umax), ""); + static_assert(!SafeLt(umax, m1), ""); + static_assert(!SafeLt(umax, umax), ""); + + static_assert(SafeLt(1, 2), ""); + static_assert(SafeLt(1, 2.0), ""); + static_assert(SafeLt(1.0, 2), ""); + static_assert(SafeLt(1.0, 2.0), ""); + static_assert(!SafeLt(2, 1), ""); + static_assert(!SafeLt(2, 1.0), ""); + static_assert(!SafeLt(2.0, 1), ""); + static_assert(!SafeLt(2.0, 1.0), ""); + + static_assert(!SafeLt(2, 2), ""); + static_assert(!SafeLt(2, 2.0), ""); + static_assert(!SafeLt(2.0, 2), ""); + static_assert(!SafeLt(2.0, 2.0), ""); + + EXPECT_FALSE(SafeLt(p1, p1)); + EXPECT_TRUE(SafeLt(p1, p2)); + EXPECT_FALSE(SafeLt(p2, p1)); + EXPECT_FALSE(SafeLt(p2, p2)); +} + +TEST(SafeCmpTest, Le) { + static_assert(SafeLe(-1, 2), ""); + static_assert(SafeLe(-1, 2u), ""); + static_assert(!SafeLe(2, -1), ""); + static_assert(!SafeLe(2u, -1), ""); + + static_assert(SafeLe(1, 2), ""); + static_assert(SafeLe(1, 2u), ""); + static_assert(SafeLe(1u, 2), ""); + static_assert(SafeLe(1u, 2u), ""); + static_assert(!SafeLe(2, 1), ""); + static_assert(!SafeLe(2, 1u), ""); + static_assert(!SafeLe(2u, 1), ""); + static_assert(!SafeLe(2u, 1u), ""); + + static_assert(SafeLe(2, 2), ""); + static_assert(SafeLe(2, 2u), ""); + static_assert(SafeLe(2u, 2), ""); + static_assert(SafeLe(2u, 2u), ""); + + static_assert(SafeLe(imin, imin), ""); + static_assert(SafeLe(imin, umax), ""); + static_assert(!SafeLe(umax, imin), ""); + static_assert(SafeLe(umax, umax), ""); + + static_assert(SafeLe(m1, m1), ""); + static_assert(SafeLe(m1, umax), ""); + static_assert(!SafeLe(umax, m1), ""); + static_assert(SafeLe(umax, umax), ""); + + static_assert(SafeLe(1, 2), ""); + static_assert(SafeLe(1, 2.0), ""); + static_assert(SafeLe(1.0, 2), ""); + static_assert(SafeLe(1.0, 2.0), ""); + static_assert(!SafeLe(2, 1), ""); + static_assert(!SafeLe(2, 1.0), ""); + static_assert(!SafeLe(2.0, 1), ""); + static_assert(!SafeLe(2.0, 1.0), ""); + + static_assert(SafeLe(2, 2), ""); + static_assert(SafeLe(2, 2.0), ""); + static_assert(SafeLe(2.0, 2), ""); + static_assert(SafeLe(2.0, 2.0), ""); + + EXPECT_TRUE(SafeLe(p1, p1)); + EXPECT_TRUE(SafeLe(p1, p2)); + EXPECT_FALSE(SafeLe(p2, p1)); + EXPECT_TRUE(SafeLe(p2, p2)); +} + +TEST(SafeCmpTest, Gt) { + static_assert(!SafeGt(-1, 2), ""); + static_assert(!SafeGt(-1, 2u), ""); + static_assert(SafeGt(2, -1), ""); + static_assert(SafeGt(2u, -1), ""); + + static_assert(!SafeGt(1, 2), ""); + static_assert(!SafeGt(1, 2u), ""); + static_assert(!SafeGt(1u, 2), ""); + static_assert(!SafeGt(1u, 2u), ""); + static_assert(SafeGt(2, 1), ""); + static_assert(SafeGt(2, 1u), ""); + static_assert(SafeGt(2u, 1), ""); + static_assert(SafeGt(2u, 1u), ""); + + static_assert(!SafeGt(2, 2), ""); + static_assert(!SafeGt(2, 2u), ""); + static_assert(!SafeGt(2u, 2), ""); + static_assert(!SafeGt(2u, 2u), ""); + + static_assert(!SafeGt(imin, imin), ""); + static_assert(!SafeGt(imin, umax), ""); + static_assert(SafeGt(umax, imin), ""); + static_assert(!SafeGt(umax, umax), ""); + + static_assert(!SafeGt(m1, m1), ""); + static_assert(!SafeGt(m1, umax), ""); + static_assert(SafeGt(umax, m1), ""); + static_assert(!SafeGt(umax, umax), ""); + + static_assert(!SafeGt(1, 2), ""); + static_assert(!SafeGt(1, 2.0), ""); + static_assert(!SafeGt(1.0, 2), ""); + static_assert(!SafeGt(1.0, 2.0), ""); + static_assert(SafeGt(2, 1), ""); + static_assert(SafeGt(2, 1.0), ""); + static_assert(SafeGt(2.0, 1), ""); + static_assert(SafeGt(2.0, 1.0), ""); + + static_assert(!SafeGt(2, 2), ""); + static_assert(!SafeGt(2, 2.0), ""); + static_assert(!SafeGt(2.0, 2), ""); + static_assert(!SafeGt(2.0, 2.0), ""); + + EXPECT_FALSE(SafeGt(p1, p1)); + EXPECT_FALSE(SafeGt(p1, p2)); + EXPECT_TRUE(SafeGt(p2, p1)); + EXPECT_FALSE(SafeGt(p2, p2)); +} + +TEST(SafeCmpTest, Ge) { + static_assert(!SafeGe(-1, 2), ""); + static_assert(!SafeGe(-1, 2u), ""); + static_assert(SafeGe(2, -1), ""); + static_assert(SafeGe(2u, -1), ""); + + static_assert(!SafeGe(1, 2), ""); + static_assert(!SafeGe(1, 2u), ""); + static_assert(!SafeGe(1u, 2), ""); + static_assert(!SafeGe(1u, 2u), ""); + static_assert(SafeGe(2, 1), ""); + static_assert(SafeGe(2, 1u), ""); + static_assert(SafeGe(2u, 1), ""); + static_assert(SafeGe(2u, 1u), ""); + + static_assert(SafeGe(2, 2), ""); + static_assert(SafeGe(2, 2u), ""); + static_assert(SafeGe(2u, 2), ""); + static_assert(SafeGe(2u, 2u), ""); + + static_assert(SafeGe(imin, imin), ""); + static_assert(!SafeGe(imin, umax), ""); + static_assert(SafeGe(umax, imin), ""); + static_assert(SafeGe(umax, umax), ""); + + static_assert(SafeGe(m1, m1), ""); + static_assert(!SafeGe(m1, umax), ""); + static_assert(SafeGe(umax, m1), ""); + static_assert(SafeGe(umax, umax), ""); + + static_assert(!SafeGe(1, 2), ""); + static_assert(!SafeGe(1, 2.0), ""); + static_assert(!SafeGe(1.0, 2), ""); + static_assert(!SafeGe(1.0, 2.0), ""); + static_assert(SafeGe(2, 1), ""); + static_assert(SafeGe(2, 1.0), ""); + static_assert(SafeGe(2.0, 1), ""); + static_assert(SafeGe(2.0, 1.0), ""); + + static_assert(SafeGe(2, 2), ""); + static_assert(SafeGe(2, 2.0), ""); + static_assert(SafeGe(2.0, 2), ""); + static_assert(SafeGe(2.0, 2.0), ""); + + EXPECT_TRUE(SafeGe(p1, p1)); + EXPECT_FALSE(SafeGe(p1, p2)); + EXPECT_TRUE(SafeGe(p2, p1)); + EXPECT_TRUE(SafeGe(p2, p2)); +} + +TEST(SafeCmpTest, Enum) { + enum E1 { e1 = 13 }; + enum { e2 = 13 }; + enum E3 : unsigned { e3 = 13 }; + enum : unsigned { e4 = 13 }; + static_assert(SafeEq(13, e1), ""); + static_assert(SafeEq(13u, e1), ""); + static_assert(SafeEq(13, e2), ""); + static_assert(SafeEq(13u, e2), ""); + static_assert(SafeEq(13, e3), ""); + static_assert(SafeEq(13u, e3), ""); + static_assert(SafeEq(13, e4), ""); + static_assert(SafeEq(13u, e4), ""); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_conversions.h b/third_party/libwebrtc/rtc_base/numerics/safe_conversions.h new file mode 100644 index 0000000000..e00219cbd7 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_conversions.h @@ -0,0 +1,74 @@ +/* + * Copyright 2014 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. + */ + +// Borrowed from Chromium's src/base/numerics/safe_conversions.h. + +#ifndef RTC_BASE_NUMERICS_SAFE_CONVERSIONS_H_ +#define RTC_BASE_NUMERICS_SAFE_CONVERSIONS_H_ + +#include <limits> + +#include "rtc_base/checks.h" +#include "rtc_base/numerics/safe_conversions_impl.h" + +namespace rtc { + +// Convenience function that returns true if the supplied value is in range +// for the destination type. +template <typename Dst, typename Src> +inline constexpr bool IsValueInRangeForNumericType(Src value) { + return internal::RangeCheck<Dst>(value) == internal::TYPE_VALID; +} + +// checked_cast<> and dchecked_cast<> are analogous to static_cast<> for +// numeric types, except that they [D]CHECK that the specified numeric +// conversion will not overflow or underflow. NaN source will always trigger +// the [D]CHECK. +template <typename Dst, typename Src> +inline constexpr Dst checked_cast(Src value) { + RTC_CHECK(IsValueInRangeForNumericType<Dst>(value)); + return static_cast<Dst>(value); +} +template <typename Dst, typename Src> +inline constexpr Dst dchecked_cast(Src value) { + RTC_DCHECK(IsValueInRangeForNumericType<Dst>(value)); + return static_cast<Dst>(value); +} + +// saturated_cast<> is analogous to static_cast<> for numeric types, except +// that the specified numeric conversion will saturate rather than overflow or +// underflow. NaN assignment to an integral will trigger a RTC_CHECK condition. +template <typename Dst, typename Src> +inline constexpr Dst saturated_cast(Src value) { + // Optimization for floating point values, which already saturate. + if (std::numeric_limits<Dst>::is_iec559) + return static_cast<Dst>(value); + + switch (internal::RangeCheck<Dst>(value)) { + case internal::TYPE_VALID: + return static_cast<Dst>(value); + + case internal::TYPE_UNDERFLOW: + return std::numeric_limits<Dst>::min(); + + case internal::TYPE_OVERFLOW: + return std::numeric_limits<Dst>::max(); + + // Should fail only on attempting to assign NaN to a saturated integer. + case internal::TYPE_INVALID: + RTC_CHECK_NOTREACHED(); + } + + RTC_CHECK_NOTREACHED(); +} + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_SAFE_CONVERSIONS_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_conversions_impl.h b/third_party/libwebrtc/rtc_base/numerics/safe_conversions_impl.h new file mode 100644 index 0000000000..e924ce3256 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_conversions_impl.h @@ -0,0 +1,177 @@ +/* + * Copyright 2014 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. + */ + +// Borrowed from Chromium's src/base/numerics/safe_conversions_impl.h. + +#ifndef RTC_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ +#define RTC_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ + +#include <limits> + +namespace rtc { +namespace internal { + +enum DstSign { DST_UNSIGNED, DST_SIGNED }; + +enum SrcSign { SRC_UNSIGNED, SRC_SIGNED }; + +enum DstRange { OVERLAPS_RANGE, CONTAINS_RANGE }; + +// Helper templates to statically determine if our destination type can contain +// all values represented by the source type. + +template <typename Dst, + typename Src, + DstSign IsDstSigned = + std::numeric_limits<Dst>::is_signed ? DST_SIGNED : DST_UNSIGNED, + SrcSign IsSrcSigned = + std::numeric_limits<Src>::is_signed ? SRC_SIGNED : SRC_UNSIGNED> +struct StaticRangeCheck {}; + +template <typename Dst, typename Src> +struct StaticRangeCheck<Dst, Src, DST_SIGNED, SRC_SIGNED> { + typedef std::numeric_limits<Dst> DstLimits; + typedef std::numeric_limits<Src> SrcLimits; + // Compare based on max_exponent, which we must compute for integrals. + static const size_t kDstMaxExponent = + DstLimits::is_iec559 ? DstLimits::max_exponent : (sizeof(Dst) * 8 - 1); + static const size_t kSrcMaxExponent = + SrcLimits::is_iec559 ? SrcLimits::max_exponent : (sizeof(Src) * 8 - 1); + static const DstRange value = + kDstMaxExponent >= kSrcMaxExponent ? CONTAINS_RANGE : OVERLAPS_RANGE; +}; + +template <typename Dst, typename Src> +struct StaticRangeCheck<Dst, Src, DST_UNSIGNED, SRC_UNSIGNED> { + static const DstRange value = + sizeof(Dst) >= sizeof(Src) ? CONTAINS_RANGE : OVERLAPS_RANGE; +}; + +template <typename Dst, typename Src> +struct StaticRangeCheck<Dst, Src, DST_SIGNED, SRC_UNSIGNED> { + typedef std::numeric_limits<Dst> DstLimits; + typedef std::numeric_limits<Src> SrcLimits; + // Compare based on max_exponent, which we must compute for integrals. + static const size_t kDstMaxExponent = + DstLimits::is_iec559 ? DstLimits::max_exponent : (sizeof(Dst) * 8 - 1); + static const size_t kSrcMaxExponent = sizeof(Src) * 8; + static const DstRange value = + kDstMaxExponent >= kSrcMaxExponent ? CONTAINS_RANGE : OVERLAPS_RANGE; +}; + +template <typename Dst, typename Src> +struct StaticRangeCheck<Dst, Src, DST_UNSIGNED, SRC_SIGNED> { + static const DstRange value = OVERLAPS_RANGE; +}; + +enum RangeCheckResult { + TYPE_VALID = 0, // Value can be represented by the destination type. + TYPE_UNDERFLOW = 1, // Value would overflow. + TYPE_OVERFLOW = 2, // Value would underflow. + TYPE_INVALID = 3 // Source value is invalid (i.e. NaN). +}; + +// This macro creates a RangeCheckResult from an upper and lower bound +// check by taking advantage of the fact that only NaN can be out of range in +// both directions at once. +#define BASE_NUMERIC_RANGE_CHECK_RESULT(is_in_upper_bound, is_in_lower_bound) \ + RangeCheckResult(((is_in_upper_bound) ? 0 : TYPE_OVERFLOW) | \ + ((is_in_lower_bound) ? 0 : TYPE_UNDERFLOW)) + +template <typename Dst, + typename Src, + DstSign IsDstSigned = + std::numeric_limits<Dst>::is_signed ? DST_SIGNED : DST_UNSIGNED, + SrcSign IsSrcSigned = + std::numeric_limits<Src>::is_signed ? SRC_SIGNED : SRC_UNSIGNED, + DstRange IsSrcRangeContained = StaticRangeCheck<Dst, Src>::value> +struct RangeCheckImpl {}; + +// The following templates are for ranges that must be verified at runtime. We +// split it into checks based on signedness to avoid confusing casts and +// compiler warnings on signed an unsigned comparisons. + +// Dst range always contains the result: nothing to check. +template <typename Dst, typename Src, DstSign IsDstSigned, SrcSign IsSrcSigned> +struct RangeCheckImpl<Dst, Src, IsDstSigned, IsSrcSigned, CONTAINS_RANGE> { + static constexpr RangeCheckResult Check(Src value) { return TYPE_VALID; } +}; + +// Signed to signed narrowing. +template <typename Dst, typename Src> +struct RangeCheckImpl<Dst, Src, DST_SIGNED, SRC_SIGNED, OVERLAPS_RANGE> { + static constexpr RangeCheckResult Check(Src value) { + typedef std::numeric_limits<Dst> DstLimits; + return DstLimits::is_iec559 + ? BASE_NUMERIC_RANGE_CHECK_RESULT( + value <= static_cast<Src>(DstLimits::max()), + value >= static_cast<Src>(DstLimits::max() * -1)) + : BASE_NUMERIC_RANGE_CHECK_RESULT( + value <= static_cast<Src>(DstLimits::max()), + value >= static_cast<Src>(DstLimits::min())); + } +}; + +// Unsigned to unsigned narrowing. +template <typename Dst, typename Src> +struct RangeCheckImpl<Dst, Src, DST_UNSIGNED, SRC_UNSIGNED, OVERLAPS_RANGE> { + static constexpr RangeCheckResult Check(Src value) { + typedef std::numeric_limits<Dst> DstLimits; + return BASE_NUMERIC_RANGE_CHECK_RESULT( + value <= static_cast<Src>(DstLimits::max()), true); + } +}; + +// Unsigned to signed. +template <typename Dst, typename Src> +struct RangeCheckImpl<Dst, Src, DST_SIGNED, SRC_UNSIGNED, OVERLAPS_RANGE> { + static constexpr RangeCheckResult Check(Src value) { + typedef std::numeric_limits<Dst> DstLimits; + return sizeof(Dst) > sizeof(Src) + ? TYPE_VALID + : BASE_NUMERIC_RANGE_CHECK_RESULT( + value <= static_cast<Src>(DstLimits::max()), true); + } +}; + +// Signed to unsigned. +template <typename Dst, typename Src> +struct RangeCheckImpl<Dst, Src, DST_UNSIGNED, SRC_SIGNED, OVERLAPS_RANGE> { + typedef std::numeric_limits<Dst> DstLimits; + typedef std::numeric_limits<Src> SrcLimits; + // Compare based on max_exponent, which we must compute for integrals. + static constexpr size_t DstMaxExponent() { return sizeof(Dst) * 8; } + static constexpr size_t SrcMaxExponent() { + return SrcLimits::is_iec559 ? SrcLimits::max_exponent + : (sizeof(Src) * 8 - 1); + } + static constexpr RangeCheckResult Check(Src value) { + return (DstMaxExponent() >= SrcMaxExponent()) + ? BASE_NUMERIC_RANGE_CHECK_RESULT(true, + value >= static_cast<Src>(0)) + : BASE_NUMERIC_RANGE_CHECK_RESULT( + value <= static_cast<Src>(DstLimits::max()), + value >= static_cast<Src>(0)); + } +}; + +template <typename Dst, typename Src> +inline constexpr RangeCheckResult RangeCheck(Src value) { + static_assert(std::numeric_limits<Src>::is_specialized, + "argument must be numeric"); + static_assert(std::numeric_limits<Dst>::is_specialized, + "result must be numeric"); + return RangeCheckImpl<Dst, Src>::Check(value); +} + +} // namespace internal +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_SAFE_CONVERSIONS_IMPL_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_minmax.h b/third_party/libwebrtc/rtc_base/numerics/safe_minmax.h new file mode 100644 index 0000000000..6c41dfd617 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_minmax.h @@ -0,0 +1,335 @@ +/* + * Copyright 2017 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. + */ + +// Minimum and maximum +// =================== +// +// rtc::SafeMin(x, y) +// rtc::SafeMax(x, y) +// +// (These are both constexpr.) +// +// Accept two arguments of either any two integral or any two floating-point +// types, and return the smaller and larger value, respectively, with no +// truncation or wrap-around. If only one of the input types is statically +// guaranteed to be able to represent the result, the return type is that type; +// if either one would do, the result type is the smaller type. (One of these +// two cases always applies.) +// +// * The case with one floating-point and one integral type is not allowed, +// because the floating-point type will have greater range, but may not +// have sufficient precision to represent the integer value exactly.) +// +// Clamp (a.k.a. constrain to a given interval) +// ============================================ +// +// rtc::SafeClamp(x, a, b) +// +// Accepts three arguments of any mix of integral types or any mix of +// floating-point types, and returns the value in the closed interval [a, b] +// that is closest to x (that is, if x < a it returns a; if x > b it returns b; +// and if a <= x <= b it returns x). As for SafeMin() and SafeMax(), there is +// no truncation or wrap-around. The result type +// +// 1. is statically guaranteed to be able to represent the result; +// +// 2. is no larger than the largest of the three argument types; and +// +// 3. has the same signedness as the type of the first argument, if this is +// possible without violating the First or Second Law. +// +// There is always at least one type that meets criteria 1 and 2. If more than +// one type meets these criteria equally well, the result type is one of the +// types that is smallest. Note that unlike SafeMin() and SafeMax(), +// SafeClamp() will sometimes pick a return type that isn't the type of any of +// its arguments. +// +// * In this context, a type A is smaller than a type B if it has a smaller +// range; that is, if A::max() - A::min() < B::max() - B::min(). For +// example, int8_t < int16_t == uint16_t < int32_t, and all integral types +// are smaller than all floating-point types.) +// +// * As for SafeMin and SafeMax, mixing integer and floating-point arguments +// is not allowed, because floating-point types have greater range than +// integer types, but do not have sufficient precision to represent the +// values of most integer types exactly. +// +// Requesting a specific return type +// ================================= +// +// All three functions allow callers to explicitly specify the return type as a +// template parameter, overriding the default return type. E.g. +// +// rtc::SafeMin<int>(x, y) // returns an int +// +// If the requested type is statically guaranteed to be able to represent the +// result, then everything's fine, and the return type is as requested. But if +// the requested type is too small, a static_assert is triggered. + +#ifndef RTC_BASE_NUMERICS_SAFE_MINMAX_H_ +#define RTC_BASE_NUMERICS_SAFE_MINMAX_H_ + +#include <limits> +#include <type_traits> + +#include "rtc_base/checks.h" +#include "rtc_base/numerics/safe_compare.h" +#include "rtc_base/type_traits.h" + +namespace rtc { + +namespace safe_minmax_impl { + +// Make the range of a type available via something other than a constexpr +// function, to work around MSVC limitations. See +// https://blogs.msdn.microsoft.com/vcblog/2015/12/02/partial-support-for-expression-sfinae-in-vs-2015-update-1/ +template <typename T> +struct Limits { + static constexpr T lowest = std::numeric_limits<T>::lowest(); + static constexpr T max = std::numeric_limits<T>::max(); +}; + +template <typename T, bool is_enum = std::is_enum<T>::value> +struct UnderlyingType; + +template <typename T> +struct UnderlyingType<T, false> { + using type = T; +}; + +template <typename T> +struct UnderlyingType<T, true> { + using type = typename std::underlying_type<T>::type; +}; + +// Given two types T1 and T2, find types that can hold the smallest (in +// ::min_t) and the largest (in ::max_t) of the two values. +template <typename T1, + typename T2, + bool int1 = IsIntlike<T1>::value, + bool int2 = IsIntlike<T2>::value> +struct MType { + static_assert(int1 == int2, + "You may not mix integral and floating-point arguments"); +}; + +// Specialization for when neither type is integral (and therefore presumably +// floating-point). +template <typename T1, typename T2> +struct MType<T1, T2, false, false> { + using min_t = typename std::common_type<T1, T2>::type; + static_assert(std::is_same<min_t, T1>::value || + std::is_same<min_t, T2>::value, + ""); + + using max_t = typename std::common_type<T1, T2>::type; + static_assert(std::is_same<max_t, T1>::value || + std::is_same<max_t, T2>::value, + ""); +}; + +// Specialization for when both types are integral. +template <typename T1, typename T2> +struct MType<T1, T2, true, true> { + // The type with the lowest minimum value. In case of a tie, the type with + // the lowest maximum value. In case that too is a tie, the types have the + // same range, and we arbitrarily pick T1. + using min_t = typename std::conditional< + SafeLt(Limits<T1>::lowest, Limits<T2>::lowest), + T1, + typename std::conditional< + SafeGt(Limits<T1>::lowest, Limits<T2>::lowest), + T2, + typename std::conditional<SafeLe(Limits<T1>::max, Limits<T2>::max), + T1, + T2>::type>::type>::type; + static_assert(std::is_same<min_t, T1>::value || + std::is_same<min_t, T2>::value, + ""); + + // The type with the highest maximum value. In case of a tie, the types have + // the same range (because in C++, integer types with the same maximum also + // have the same minimum). + static_assert(SafeNe(Limits<T1>::max, Limits<T2>::max) || + SafeEq(Limits<T1>::lowest, Limits<T2>::lowest), + "integer types with the same max should have the same min"); + using max_t = typename std:: + conditional<SafeGe(Limits<T1>::max, Limits<T2>::max), T1, T2>::type; + static_assert(std::is_same<max_t, T1>::value || + std::is_same<max_t, T2>::value, + ""); +}; + +// A dummy type that we pass around at compile time but never actually use. +// Declared but not defined. +struct DefaultType; + +// ::type is A, except we fall back to B if A is DefaultType. We static_assert +// that the chosen type can hold all values that B can hold. +template <typename A, typename B> +struct TypeOr { + using type = typename std:: + conditional<std::is_same<A, DefaultType>::value, B, A>::type; + static_assert(SafeLe(Limits<type>::lowest, Limits<B>::lowest) && + SafeGe(Limits<type>::max, Limits<B>::max), + "The specified type isn't large enough"); + static_assert(IsIntlike<type>::value == IsIntlike<B>::value && + std::is_floating_point<type>::value == + std::is_floating_point<type>::value, + "float<->int conversions not allowed"); +}; + +} // namespace safe_minmax_impl + +template < + typename R = safe_minmax_impl::DefaultType, + typename T1 = safe_minmax_impl::DefaultType, + typename T2 = safe_minmax_impl::DefaultType, + typename R2 = typename safe_minmax_impl::TypeOr< + R, + typename safe_minmax_impl::MType< + typename safe_minmax_impl::UnderlyingType<T1>::type, + typename safe_minmax_impl::UnderlyingType<T2>::type>::min_t>::type> +constexpr R2 SafeMin(T1 a, T2 b) { + static_assert(IsIntlike<T1>::value || std::is_floating_point<T1>::value, + "The first argument must be integral or floating-point"); + static_assert(IsIntlike<T2>::value || std::is_floating_point<T2>::value, + "The second argument must be integral or floating-point"); + return SafeLt(a, b) ? static_cast<R2>(a) : static_cast<R2>(b); +} + +template < + typename R = safe_minmax_impl::DefaultType, + typename T1 = safe_minmax_impl::DefaultType, + typename T2 = safe_minmax_impl::DefaultType, + typename R2 = typename safe_minmax_impl::TypeOr< + R, + typename safe_minmax_impl::MType< + typename safe_minmax_impl::UnderlyingType<T1>::type, + typename safe_minmax_impl::UnderlyingType<T2>::type>::max_t>::type> +constexpr R2 SafeMax(T1 a, T2 b) { + static_assert(IsIntlike<T1>::value || std::is_floating_point<T1>::value, + "The first argument must be integral or floating-point"); + static_assert(IsIntlike<T2>::value || std::is_floating_point<T2>::value, + "The second argument must be integral or floating-point"); + return SafeGt(a, b) ? static_cast<R2>(a) : static_cast<R2>(b); +} + +namespace safe_minmax_impl { + +// Given three types T, L, and H, let ::type be a suitable return value for +// SafeClamp(T, L, H). See the docs at the top of this file for details. +template <typename T, + typename L, + typename H, + bool int1 = IsIntlike<T>::value, + bool int2 = IsIntlike<L>::value, + bool int3 = IsIntlike<H>::value> +struct ClampType { + static_assert(int1 == int2 && int1 == int3, + "You may not mix integral and floating-point arguments"); +}; + +// Specialization for when all three types are floating-point. +template <typename T, typename L, typename H> +struct ClampType<T, L, H, false, false, false> { + using type = typename std::common_type<T, L, H>::type; +}; + +// Specialization for when all three types are integral. +template <typename T, typename L, typename H> +struct ClampType<T, L, H, true, true, true> { + private: + // Range of the return value. The return type must be able to represent this + // full range. + static constexpr auto r_min = + SafeMax(Limits<L>::lowest, SafeMin(Limits<H>::lowest, Limits<T>::lowest)); + static constexpr auto r_max = + SafeMin(Limits<H>::max, SafeMax(Limits<L>::max, Limits<T>::max)); + + // Is the given type an acceptable return type? (That is, can it represent + // all possible return values, and is it no larger than the largest of the + // input types?) + template <typename A> + struct AcceptableType { + private: + static constexpr bool not_too_large = sizeof(A) <= sizeof(L) || + sizeof(A) <= sizeof(H) || + sizeof(A) <= sizeof(T); + static constexpr bool range_contained = + SafeLe(Limits<A>::lowest, r_min) && SafeLe(r_max, Limits<A>::max); + + public: + static constexpr bool value = not_too_large && range_contained; + }; + + using best_signed_type = typename std::conditional< + AcceptableType<int8_t>::value, + int8_t, + typename std::conditional< + AcceptableType<int16_t>::value, + int16_t, + typename std::conditional<AcceptableType<int32_t>::value, + int32_t, + int64_t>::type>::type>::type; + + using best_unsigned_type = typename std::conditional< + AcceptableType<uint8_t>::value, + uint8_t, + typename std::conditional< + AcceptableType<uint16_t>::value, + uint16_t, + typename std::conditional<AcceptableType<uint32_t>::value, + uint32_t, + uint64_t>::type>::type>::type; + + public: + // Pick the best type, preferring the same signedness as T but falling back + // to the other one if necessary. + using type = typename std::conditional< + std::is_signed<T>::value, + typename std::conditional<AcceptableType<best_signed_type>::value, + best_signed_type, + best_unsigned_type>::type, + typename std::conditional<AcceptableType<best_unsigned_type>::value, + best_unsigned_type, + best_signed_type>::type>::type; + static_assert(AcceptableType<type>::value, ""); +}; + +} // namespace safe_minmax_impl + +template < + typename R = safe_minmax_impl::DefaultType, + typename T = safe_minmax_impl::DefaultType, + typename L = safe_minmax_impl::DefaultType, + typename H = safe_minmax_impl::DefaultType, + typename R2 = typename safe_minmax_impl::TypeOr< + R, + typename safe_minmax_impl::ClampType< + typename safe_minmax_impl::UnderlyingType<T>::type, + typename safe_minmax_impl::UnderlyingType<L>::type, + typename safe_minmax_impl::UnderlyingType<H>::type>::type>::type> +R2 SafeClamp(T x, L min, H max) { + static_assert(IsIntlike<H>::value || std::is_floating_point<H>::value, + "The first argument must be integral or floating-point"); + static_assert(IsIntlike<T>::value || std::is_floating_point<T>::value, + "The second argument must be integral or floating-point"); + static_assert(IsIntlike<L>::value || std::is_floating_point<L>::value, + "The third argument must be integral or floating-point"); + RTC_DCHECK_LE(min, max); + return SafeLe(x, min) + ? static_cast<R2>(min) + : SafeGe(x, max) ? static_cast<R2>(max) : static_cast<R2>(x); +} + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_SAFE_MINMAX_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/safe_minmax_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/safe_minmax_unittest.cc new file mode 100644 index 0000000000..c52b3f93dc --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/safe_minmax_unittest.cc @@ -0,0 +1,345 @@ +/* + * Copyright 2017 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/safe_minmax.h" + +#include <algorithm> +#include <limits> + +#include "test/gtest.h" + +namespace rtc { + +namespace { + +// Functions that check that SafeMin(), SafeMax(), and SafeClamp() return the +// specified type. The functions that end in "R" use an explicitly given return +// type. + +template <typename T1, typename T2, typename Tmin, typename Tmax> +constexpr bool TypeCheckMinMax() { + return std::is_same<decltype(SafeMin(std::declval<T1>(), std::declval<T2>())), + Tmin>::value && + std::is_same<decltype(SafeMax(std::declval<T1>(), std::declval<T2>())), + Tmax>::value; +} + +template <typename T1, typename T2, typename R> +constexpr bool TypeCheckMinR() { + return std::is_same< + decltype(SafeMin<R>(std::declval<T1>(), std::declval<T2>())), R>::value; +} + +template <typename T1, typename T2, typename R> +constexpr bool TypeCheckMaxR() { + return std::is_same< + decltype(SafeMax<R>(std::declval<T1>(), std::declval<T2>())), R>::value; +} + +template <typename T, typename L, typename H, typename R> +constexpr bool TypeCheckClamp() { + return std::is_same<decltype(SafeClamp(std::declval<T>(), std::declval<L>(), + std::declval<H>())), + R>::value; +} + +template <typename T, typename L, typename H, typename R> +constexpr bool TypeCheckClampR() { + return std::is_same<decltype(SafeClamp<R>(std::declval<T>(), + std::declval<L>(), + std::declval<H>())), + R>::value; +} + +// clang-format off + +// SafeMin/SafeMax: Check that all combinations of signed/unsigned 8/64 bits +// give the correct default result type. +static_assert(TypeCheckMinMax< int8_t, int8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckMinMax< int8_t, uint8_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckMinMax< int8_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckMinMax< int8_t, uint64_t, int8_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax< uint8_t, int8_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckMinMax< uint8_t, uint8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckMinMax< uint8_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckMinMax< uint8_t, uint64_t, uint8_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax< int64_t, int8_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckMinMax< int64_t, uint8_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckMinMax< int64_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckMinMax< int64_t, uint64_t, int64_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax<uint64_t, int8_t, int8_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax<uint64_t, uint8_t, uint8_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax<uint64_t, int64_t, int64_t, uint64_t>(), ""); +static_assert(TypeCheckMinMax<uint64_t, uint64_t, uint64_t, uint64_t>(), ""); + +// SafeClamp: Check that all combinations of signed/unsigned 8/64 bits give the +// correct result type. +static_assert(TypeCheckClamp< int8_t, int8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int8_t, uint8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int8_t, int64_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int8_t, uint64_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint8_t, int64_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint8_t, uint64_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int64_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int64_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int8_t, int64_t, uint64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint64_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint64_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int8_t, uint64_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int8_t, int64_t, int16_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int8_t, uint64_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint8_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint8_t, int64_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint8_t, uint64_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int64_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int64_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, int64_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint64_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint64_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint64_t, int64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp< uint8_t, uint64_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int8_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int8_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int8_t, uint64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint8_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint8_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint8_t, uint64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int64_t, int8_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int64_t, uint8_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, int64_t, uint64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint64_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint64_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp< int64_t, uint64_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int8_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int8_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int8_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint8_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint8_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint8_t, int64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint8_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int64_t, int8_t, int8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int64_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int64_t, int64_t, int64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, int64_t, uint64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint64_t, int8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint64_t, uint8_t, uint8_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint64_t, int64_t, uint64_t>(), ""); +static_assert(TypeCheckClamp<uint64_t, uint64_t, uint64_t, uint64_t>(), ""); + +enum DefaultE { kFoo = -17 }; +enum UInt8E : uint8_t { kBar = 17 }; + +// SafeMin/SafeMax: Check that we can use enum types. +static_assert(TypeCheckMinMax<unsigned, unsigned, unsigned, unsigned>(), ""); +static_assert(TypeCheckMinMax<unsigned, DefaultE, int, unsigned>(), ""); +static_assert(TypeCheckMinMax<unsigned, UInt8E, uint8_t, unsigned>(), ""); +static_assert(TypeCheckMinMax<DefaultE, unsigned, int, unsigned>(), ""); +static_assert(TypeCheckMinMax<DefaultE, DefaultE, int, int>(), ""); +static_assert(TypeCheckMinMax<DefaultE, UInt8E, int, int>(), ""); +static_assert(TypeCheckMinMax< UInt8E, unsigned, uint8_t, unsigned>(), ""); +static_assert(TypeCheckMinMax< UInt8E, DefaultE, int, int>(), ""); +static_assert(TypeCheckMinMax< UInt8E, UInt8E, uint8_t, uint8_t>(), ""); + +// SafeClamp: Check that we can use enum types. +static_assert(TypeCheckClamp<unsigned, unsigned, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp<unsigned, unsigned, DefaultE, unsigned>(), ""); +static_assert(TypeCheckClamp<unsigned, unsigned, UInt8E, uint8_t>(), ""); +static_assert(TypeCheckClamp<unsigned, DefaultE, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp<unsigned, DefaultE, DefaultE, int>(), ""); +static_assert(TypeCheckClamp<unsigned, DefaultE, UInt8E, uint8_t>(), ""); +static_assert(TypeCheckClamp<unsigned, UInt8E, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp<unsigned, UInt8E, DefaultE, unsigned>(), ""); +static_assert(TypeCheckClamp<unsigned, UInt8E, UInt8E, uint8_t>(), ""); +static_assert(TypeCheckClamp<DefaultE, unsigned, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp<DefaultE, unsigned, DefaultE, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, unsigned, UInt8E, int16_t>(), ""); +static_assert(TypeCheckClamp<DefaultE, DefaultE, unsigned, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, DefaultE, DefaultE, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, DefaultE, UInt8E, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, UInt8E, unsigned, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, UInt8E, DefaultE, int>(), ""); +static_assert(TypeCheckClamp<DefaultE, UInt8E, UInt8E, int16_t>(), ""); +static_assert(TypeCheckClamp< UInt8E, unsigned, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp< UInt8E, unsigned, DefaultE, unsigned>(), ""); +static_assert(TypeCheckClamp< UInt8E, unsigned, UInt8E, uint8_t>(), ""); +static_assert(TypeCheckClamp< UInt8E, DefaultE, unsigned, unsigned>(), ""); +static_assert(TypeCheckClamp< UInt8E, DefaultE, DefaultE, int>(), ""); +static_assert(TypeCheckClamp< UInt8E, DefaultE, UInt8E, uint8_t>(), ""); +static_assert(TypeCheckClamp< UInt8E, UInt8E, unsigned, uint8_t>(), ""); +static_assert(TypeCheckClamp< UInt8E, UInt8E, DefaultE, uint8_t>(), ""); +static_assert(TypeCheckClamp< UInt8E, UInt8E, UInt8E, uint8_t>(), ""); + +using ld = long double; + +// SafeMin/SafeMax: Check that all floating-point combinations give the +// correct result type. +static_assert(TypeCheckMinMax< float, float, float, float>(), ""); +static_assert(TypeCheckMinMax< float, double, double, double>(), ""); +static_assert(TypeCheckMinMax< float, ld, ld, ld>(), ""); +static_assert(TypeCheckMinMax<double, float, double, double>(), ""); +static_assert(TypeCheckMinMax<double, double, double, double>(), ""); +static_assert(TypeCheckMinMax<double, ld, ld, ld>(), ""); +static_assert(TypeCheckMinMax< ld, float, ld, ld>(), ""); +static_assert(TypeCheckMinMax< ld, double, ld, ld>(), ""); +static_assert(TypeCheckMinMax< ld, ld, ld, ld>(), ""); + +// SafeClamp: Check that all floating-point combinations give the correct +// result type. +static_assert(TypeCheckClamp< float, float, float, float>(), ""); +static_assert(TypeCheckClamp< float, float, double, double>(), ""); +static_assert(TypeCheckClamp< float, float, ld, ld>(), ""); +static_assert(TypeCheckClamp< float, double, float, double>(), ""); +static_assert(TypeCheckClamp< float, double, double, double>(), ""); +static_assert(TypeCheckClamp< float, double, ld, ld>(), ""); +static_assert(TypeCheckClamp< float, ld, float, ld>(), ""); +static_assert(TypeCheckClamp< float, ld, double, ld>(), ""); +static_assert(TypeCheckClamp< float, ld, ld, ld>(), ""); +static_assert(TypeCheckClamp<double, float, float, double>(), ""); +static_assert(TypeCheckClamp<double, float, double, double>(), ""); +static_assert(TypeCheckClamp<double, float, ld, ld>(), ""); +static_assert(TypeCheckClamp<double, double, float, double>(), ""); +static_assert(TypeCheckClamp<double, double, double, double>(), ""); +static_assert(TypeCheckClamp<double, double, ld, ld>(), ""); +static_assert(TypeCheckClamp<double, ld, float, ld>(), ""); +static_assert(TypeCheckClamp<double, ld, double, ld>(), ""); +static_assert(TypeCheckClamp<double, ld, ld, ld>(), ""); +static_assert(TypeCheckClamp< ld, float, float, ld>(), ""); +static_assert(TypeCheckClamp< ld, float, double, ld>(), ""); +static_assert(TypeCheckClamp< ld, float, ld, ld>(), ""); +static_assert(TypeCheckClamp< ld, double, float, ld>(), ""); +static_assert(TypeCheckClamp< ld, double, double, ld>(), ""); +static_assert(TypeCheckClamp< ld, double, ld, ld>(), ""); +static_assert(TypeCheckClamp< ld, ld, float, ld>(), ""); +static_assert(TypeCheckClamp< ld, ld, double, ld>(), ""); +static_assert(TypeCheckClamp< ld, ld, ld, ld>(), ""); + +// clang-format on + +// SafeMin/SafeMax: Check some cases of explicitly specified return type. The +// commented-out lines give compilation errors due to the requested return type +// being too small or requiring an int<->float conversion. +static_assert(TypeCheckMinR<int8_t, int8_t, int16_t>(), ""); +// static_assert(TypeCheckMinR<int8_t, int8_t, float>(), ""); +static_assert(TypeCheckMinR<uint32_t, uint64_t, uint32_t>(), ""); +// static_assert(TypeCheckMaxR<uint64_t, float, float>(), ""); +// static_assert(TypeCheckMaxR<uint64_t, double, float>(), ""); +static_assert(TypeCheckMaxR<uint32_t, int32_t, uint32_t>(), ""); +// static_assert(TypeCheckMaxR<uint32_t, int32_t, int32_t>(), ""); + +// SafeClamp: Check some cases of explicitly specified return type. The +// commented-out lines give compilation errors due to the requested return type +// being too small. +static_assert(TypeCheckClampR<int16_t, int8_t, uint8_t, int16_t>(), ""); +static_assert(TypeCheckClampR<int16_t, int8_t, uint8_t, int32_t>(), ""); +// static_assert(TypeCheckClampR<int16_t, int8_t, uint8_t, uint32_t>(), ""); + +template <typename T1, typename T2, typename Tmin, typename Tmax> +constexpr bool CheckMinMax(T1 a, T2 b, Tmin min, Tmax max) { + return TypeCheckMinMax<T1, T2, Tmin, Tmax>() && SafeMin(a, b) == min && + SafeMax(a, b) == max; +} + +template <typename T, typename L, typename H, typename R> +bool CheckClamp(T x, L min, H max, R clamped) { + return TypeCheckClamp<T, L, H, R>() && SafeClamp(x, min, max) == clamped; +} + +// SafeMin/SafeMax: Check a few values. +static_assert(CheckMinMax(int8_t{1}, int8_t{-1}, int8_t{-1}, int8_t{1}), ""); +static_assert(CheckMinMax(uint8_t{1}, int8_t{-1}, int8_t{-1}, uint8_t{1}), ""); +static_assert(CheckMinMax(uint8_t{5}, uint64_t{2}, uint8_t{2}, uint64_t{5}), + ""); +static_assert(CheckMinMax(std::numeric_limits<int32_t>::min(), + std::numeric_limits<uint32_t>::max(), + std::numeric_limits<int32_t>::min(), + std::numeric_limits<uint32_t>::max()), + ""); +static_assert(CheckMinMax(std::numeric_limits<int32_t>::min(), + std::numeric_limits<uint16_t>::max(), + std::numeric_limits<int32_t>::min(), + int32_t{std::numeric_limits<uint16_t>::max()}), + ""); +// static_assert(CheckMinMax(1.f, 2, 1.f, 2.f), ""); +static_assert(CheckMinMax(1.f, 0.0, 0.0, 1.0), ""); + +// SafeClamp: Check a few values. +TEST(SafeMinmaxTest, Clamp) { + EXPECT_TRUE(CheckClamp(int32_t{-1000000}, std::numeric_limits<int16_t>::min(), + std::numeric_limits<int16_t>::max(), + std::numeric_limits<int16_t>::min())); + EXPECT_TRUE(CheckClamp(uint32_t{1000000}, std::numeric_limits<int16_t>::min(), + std::numeric_limits<int16_t>::max(), + std::numeric_limits<int16_t>::max())); + EXPECT_TRUE(CheckClamp(3.f, -1.0, 1.f, 1.0)); + EXPECT_TRUE(CheckClamp(3.0, -1.f, 1.f, 1.0)); +} + +} // namespace + +// These functions aren't used in the tests, but it's useful to look at the +// compiler output for them, and verify that (1) the same-signedness Test*Safe +// functions result in exactly the same code as their Test*Ref counterparts, +// and that (2) the mixed-signedness Test*Safe functions have just a few extra +// arithmetic and logic instructions (but no extra control flow instructions). + +// clang-format off +int32_t TestMinRef( int32_t a, int32_t b) { return std::min(a, b); } +uint32_t TestMinRef( uint32_t a, uint32_t b) { return std::min(a, b); } +int32_t TestMinSafe( int32_t a, int32_t b) { return SafeMin(a, b); } +int32_t TestMinSafe( int32_t a, uint32_t b) { return SafeMin(a, b); } +int32_t TestMinSafe(uint32_t a, int32_t b) { return SafeMin(a, b); } +uint32_t TestMinSafe(uint32_t a, uint32_t b) { return SafeMin(a, b); } +// clang-format on + +int32_t TestClampRef(int32_t x, int32_t a, int32_t b) { + return std::max(a, std::min(x, b)); +} +uint32_t TestClampRef(uint32_t x, uint32_t a, uint32_t b) { + return std::max(a, std::min(x, b)); +} +int32_t TestClampSafe(int32_t x, int32_t a, int32_t b) { + return SafeClamp(x, a, b); +} +int32_t TestClampSafe(int32_t x, int32_t a, uint32_t b) { + return SafeClamp(x, a, b); +} +int32_t TestClampSafe(int32_t x, uint32_t a, int32_t b) { + return SafeClamp(x, a, b); +} +uint32_t TestClampSafe(int32_t x, uint32_t a, uint32_t b) { + return SafeClamp(x, a, b); +} +int32_t TestClampSafe(uint32_t x, int32_t a, int32_t b) { + return SafeClamp(x, a, b); +} +uint32_t TestClampSafe(uint32_t x, int32_t a, uint32_t b) { + return SafeClamp(x, a, b); +} +int32_t TestClampSafe(uint32_t x, uint32_t a, int32_t b) { + return SafeClamp(x, a, b); +} +uint32_t TestClampSafe(uint32_t x, uint32_t a, uint32_t b) { + return SafeClamp(x, a, b); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/sample_counter.cc b/third_party/libwebrtc/rtc_base/numerics/sample_counter.cc new file mode 100644 index 0000000000..16a8e25098 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sample_counter.cc @@ -0,0 +1,109 @@ +/* + * Copyright (c) 2018 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/sample_counter.h" + +#include <limits> + +#include "rtc_base/checks.h" +#include "rtc_base/numerics/safe_conversions.h" + +namespace rtc { + +SampleCounter::SampleCounter() = default; +SampleCounter::~SampleCounter() = default; + +void SampleCounter::Add(int sample) { + if (sum_ > 0) { + RTC_DCHECK_LE(sample, std::numeric_limits<int64_t>::max() - sum_); + } else { + RTC_DCHECK_GE(sample, std::numeric_limits<int64_t>::min() - sum_); + } + sum_ += sample; + ++num_samples_; + if (!max_ || sample > *max_) { + max_ = sample; + } +} + +void SampleCounter::Add(const SampleCounter& other) { + if (sum_ > 0) { + RTC_DCHECK_LE(other.sum_, std::numeric_limits<int64_t>::max() - sum_); + } else { + RTC_DCHECK_GE(other.sum_, std::numeric_limits<int64_t>::min() - sum_); + } + sum_ += other.sum_; + RTC_DCHECK_LE(other.num_samples_, + std::numeric_limits<int64_t>::max() - num_samples_); + num_samples_ += other.num_samples_; + if (other.max_ && (!max_ || *max_ < *other.max_)) + max_ = other.max_; +} + +absl::optional<int> SampleCounter::Avg(int64_t min_required_samples) const { + RTC_DCHECK_GT(min_required_samples, 0); + if (num_samples_ < min_required_samples) + return absl::nullopt; + return rtc::dchecked_cast<int>(sum_ / num_samples_); +} + +absl::optional<int> SampleCounter::Max() const { + return max_; +} + +absl::optional<int64_t> SampleCounter::Sum(int64_t min_required_samples) const { + RTC_DCHECK_GT(min_required_samples, 0); + if (num_samples_ < min_required_samples) + return absl::nullopt; + return sum_; +} + +int64_t SampleCounter::NumSamples() const { + return num_samples_; +} + +void SampleCounter::Reset() { + *this = {}; +} + +SampleCounterWithVariance::SampleCounterWithVariance() = default; +SampleCounterWithVariance::~SampleCounterWithVariance() = default; + +absl::optional<int64_t> SampleCounterWithVariance::Variance( + int64_t min_required_samples) const { + RTC_DCHECK_GT(min_required_samples, 0); + if (num_samples_ < min_required_samples) + return absl::nullopt; + // E[(x-mean)^2] = E[x^2] - mean^2 + int64_t mean = sum_ / num_samples_; + return sum_squared_ / num_samples_ - mean * mean; +} + +void SampleCounterWithVariance::Add(int sample) { + SampleCounter::Add(sample); + // Prevent overflow in squaring. + RTC_DCHECK_GT(sample, std::numeric_limits<int32_t>::min()); + RTC_DCHECK_LE(int64_t{sample} * sample, + std::numeric_limits<int64_t>::max() - sum_squared_); + sum_squared_ += int64_t{sample} * sample; +} + +void SampleCounterWithVariance::Add(const SampleCounterWithVariance& other) { + SampleCounter::Add(other); + RTC_DCHECK_LE(other.sum_squared_, + std::numeric_limits<int64_t>::max() - sum_squared_); + sum_squared_ += other.sum_squared_; +} + +void SampleCounterWithVariance::Reset() { + *this = {}; +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/sample_counter.h b/third_party/libwebrtc/rtc_base/numerics/sample_counter.h new file mode 100644 index 0000000000..717a1afbcf --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sample_counter.h @@ -0,0 +1,58 @@ +/* + * Copyright (c) 2018 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_SAMPLE_COUNTER_H_ +#define RTC_BASE_NUMERICS_SAMPLE_COUNTER_H_ + +#include <stdint.h> + +#include "absl/types/optional.h" + +namespace rtc { + +// Simple utility class for counting basic statistics (max./avg./variance) on +// stream of samples. +class SampleCounter { + public: + SampleCounter(); + ~SampleCounter(); + void Add(int sample); + absl::optional<int> Avg(int64_t min_required_samples) const; + absl::optional<int> Max() const; + absl::optional<int64_t> Sum(int64_t min_required_samples) const; + int64_t NumSamples() const; + void Reset(); + // Adds all the samples from the `other` SampleCounter as if they were all + // individually added using `Add(int)` method. + void Add(const SampleCounter& other); + + protected: + int64_t sum_ = 0; + int64_t num_samples_ = 0; + absl::optional<int> max_; +}; + +class SampleCounterWithVariance : public SampleCounter { + public: + SampleCounterWithVariance(); + ~SampleCounterWithVariance(); + void Add(int sample); + absl::optional<int64_t> Variance(int64_t min_required_samples) const; + void Reset(); + // Adds all the samples from the `other` SampleCounter as if they were all + // individually added using `Add(int)` method. + void Add(const SampleCounterWithVariance& other); + + private: + int64_t sum_squared_ = 0; +}; + +} // namespace rtc +#endif // RTC_BASE_NUMERICS_SAMPLE_COUNTER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/sample_counter_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/sample_counter_unittest.cc new file mode 100644 index 0000000000..14b0573de9 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sample_counter_unittest.cc @@ -0,0 +1,80 @@ +/* + * Copyright 2018 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/sample_counter.h" + +#include <initializer_list> + +#include "test/gmock.h" +#include "test/gtest.h" + +using ::testing::Eq; + +namespace rtc { + +TEST(SampleCounterTest, ProcessesNoSamples) { + constexpr int kMinSamples = 1; + SampleCounter counter; + EXPECT_THAT(counter.Avg(kMinSamples), Eq(absl::nullopt)); + EXPECT_THAT(counter.Max(), Eq(absl::nullopt)); +} + +TEST(SampleCounterTest, NotEnoughSamples) { + constexpr int kMinSamples = 6; + SampleCounter counter; + for (int value : {1, 2, 3, 4, 5}) { + counter.Add(value); + } + EXPECT_THAT(counter.Avg(kMinSamples), Eq(absl::nullopt)); + EXPECT_THAT(counter.Sum(kMinSamples), Eq(absl::nullopt)); + EXPECT_THAT(counter.Max(), Eq(5)); +} + +TEST(SampleCounterTest, EnoughSamples) { + constexpr int kMinSamples = 5; + SampleCounter counter; + for (int value : {1, 2, 3, 4, 5}) { + counter.Add(value); + } + EXPECT_THAT(counter.Avg(kMinSamples), Eq(3)); + EXPECT_THAT(counter.Sum(kMinSamples), Eq(15)); + EXPECT_THAT(counter.Max(), Eq(5)); +} + +TEST(SampleCounterTest, ComputesVariance) { + constexpr int kMinSamples = 5; + SampleCounterWithVariance counter; + for (int value : {1, 2, 3, 4, 5}) { + counter.Add(value); + } + EXPECT_THAT(counter.Variance(kMinSamples), Eq(2)); +} + +TEST(SampleCounterTest, AggregatesTwoCounters) { + constexpr int kMinSamples = 5; + SampleCounterWithVariance counter1; + for (int value : {1, 2, 3}) { + counter1.Add(value); + } + SampleCounterWithVariance counter2; + for (int value : {4, 5}) { + counter2.Add(value); + } + // Before aggregation there is not enough samples. + EXPECT_THAT(counter1.Avg(kMinSamples), Eq(absl::nullopt)); + EXPECT_THAT(counter1.Variance(kMinSamples), Eq(absl::nullopt)); + // Aggregate counter2 in counter1. + counter1.Add(counter2); + EXPECT_THAT(counter1.Avg(kMinSamples), Eq(3)); + EXPECT_THAT(counter1.Max(), Eq(5)); + EXPECT_THAT(counter1.Variance(kMinSamples), Eq(2)); +} + +} // namespace rtc diff --git a/third_party/libwebrtc/rtc_base/numerics/sample_stats.cc b/third_party/libwebrtc/rtc_base/numerics/sample_stats.cc new file mode 100644 index 0000000000..6000b2b88f --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sample_stats.cc @@ -0,0 +1,152 @@ +/* + * Copyright (c) 2019 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/sample_stats.h" + +namespace webrtc { + +double SampleStats<double>::Max() { + if (IsEmpty()) + return INFINITY; + return GetMax(); +} + +double SampleStats<double>::Mean() { + if (IsEmpty()) + return 0; + return GetAverage(); +} + +double SampleStats<double>::Median() { + return Quantile(0.5); +} + +double SampleStats<double>::Quantile(double quantile) { + if (IsEmpty()) + return 0; + return GetPercentile(quantile); +} + +double SampleStats<double>::Min() { + if (IsEmpty()) + return -INFINITY; + return GetMin(); +} + +double SampleStats<double>::Variance() { + if (IsEmpty()) + return 0; + return GetVariance(); +} + +double SampleStats<double>::StandardDeviation() { + return sqrt(Variance()); +} + +int SampleStats<double>::Count() { + return static_cast<int>(GetSamples().size()); +} + +void SampleStats<TimeDelta>::AddSample(TimeDelta delta) { + RTC_DCHECK(delta.IsFinite()); + stats_.AddSample(delta.seconds<double>()); +} + +void SampleStats<TimeDelta>::AddSampleMs(double delta_ms) { + AddSample(TimeDelta::Millis(delta_ms)); +} +void SampleStats<TimeDelta>::AddSamples(const SampleStats<TimeDelta>& other) { + stats_.AddSamples(other.stats_); +} + +bool SampleStats<TimeDelta>::IsEmpty() { + return stats_.IsEmpty(); +} + +TimeDelta SampleStats<TimeDelta>::Max() { + return TimeDelta::Seconds(stats_.Max()); +} + +TimeDelta SampleStats<TimeDelta>::Mean() { + return TimeDelta::Seconds(stats_.Mean()); +} + +TimeDelta SampleStats<TimeDelta>::Median() { + return Quantile(0.5); +} + +TimeDelta SampleStats<TimeDelta>::Quantile(double quantile) { + return TimeDelta::Seconds(stats_.Quantile(quantile)); +} + +TimeDelta SampleStats<TimeDelta>::Min() { + return TimeDelta::Seconds(stats_.Min()); +} + +TimeDelta SampleStats<TimeDelta>::Variance() { + return TimeDelta::Seconds(stats_.Variance()); +} + +TimeDelta SampleStats<TimeDelta>::StandardDeviation() { + return TimeDelta::Seconds(stats_.StandardDeviation()); +} + +int SampleStats<TimeDelta>::Count() { + return stats_.Count(); +} + +void SampleStats<DataRate>::AddSample(DataRate sample) { + stats_.AddSample(sample.bps<double>()); +} + +void SampleStats<DataRate>::AddSampleBps(double rate_bps) { + stats_.AddSample(rate_bps); +} + +void SampleStats<DataRate>::AddSamples(const SampleStats<DataRate>& other) { + stats_.AddSamples(other.stats_); +} + +bool SampleStats<DataRate>::IsEmpty() { + return stats_.IsEmpty(); +} + +DataRate SampleStats<DataRate>::Max() { + return DataRate::BitsPerSec(stats_.Max()); +} + +DataRate SampleStats<DataRate>::Mean() { + return DataRate::BitsPerSec(stats_.Mean()); +} + +DataRate SampleStats<DataRate>::Median() { + return Quantile(0.5); +} + +DataRate SampleStats<DataRate>::Quantile(double quantile) { + return DataRate::BitsPerSec(stats_.Quantile(quantile)); +} + +DataRate SampleStats<DataRate>::Min() { + return DataRate::BitsPerSec(stats_.Min()); +} + +DataRate SampleStats<DataRate>::Variance() { + return DataRate::BitsPerSec(stats_.Variance()); +} + +DataRate SampleStats<DataRate>::StandardDeviation() { + return DataRate::BitsPerSec(stats_.StandardDeviation()); +} + +int SampleStats<DataRate>::Count() { + return stats_.Count(); +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/sample_stats.h b/third_party/libwebrtc/rtc_base/numerics/sample_stats.h new file mode 100644 index 0000000000..39af1c6a37 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sample_stats.h @@ -0,0 +1,77 @@ +/* + * Copyright (c) 2019 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_SAMPLE_STATS_H_ +#define RTC_BASE_NUMERICS_SAMPLE_STATS_H_ + +#include "api/numerics/samples_stats_counter.h" +#include "api/units/data_rate.h" +#include "api/units/time_delta.h" +#include "api/units/timestamp.h" + +namespace webrtc { +template <typename T> +class SampleStats; + +// TODO(srte): Merge this implementation with SamplesStatsCounter. +template <> +class SampleStats<double> : public SamplesStatsCounter { + public: + double Max(); + double Mean(); + double Median(); + double Quantile(double quantile); + double Min(); + double Variance(); + double StandardDeviation(); + int Count(); +}; + +template <> +class SampleStats<TimeDelta> { + public: + void AddSample(TimeDelta delta); + void AddSampleMs(double delta_ms); + void AddSamples(const SampleStats<TimeDelta>& other); + bool IsEmpty(); + TimeDelta Max(); + TimeDelta Mean(); + TimeDelta Median(); + TimeDelta Quantile(double quantile); + TimeDelta Min(); + TimeDelta Variance(); + TimeDelta StandardDeviation(); + int Count(); + + private: + SampleStats<double> stats_; +}; + +template <> +class SampleStats<DataRate> { + public: + void AddSample(DataRate rate); + void AddSampleBps(double rate_bps); + void AddSamples(const SampleStats<DataRate>& other); + bool IsEmpty(); + DataRate Max(); + DataRate Mean(); + DataRate Median(); + DataRate Quantile(double quantile); + DataRate Min(); + DataRate Variance(); + DataRate StandardDeviation(); + int Count(); + + private: + SampleStats<double> stats_; +}; +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_SAMPLE_STATS_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper.h b/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper.h new file mode 100644 index 0000000000..d741b5c910 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper.h @@ -0,0 +1,80 @@ +/* + * Copyright (c) 2022 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_SEQUENCE_NUMBER_UNWRAPPER_H_ +#define RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UNWRAPPER_H_ + +#include <stdint.h> + +#include <limits> + +#include "absl/types/optional.h" +#include "rtc_base/numerics/sequence_number_util.h" + +namespace webrtc { + +// A sequence number unwrapper where the first unwrapped value equals the +// first value being unwrapped. +template <typename T, T M = 0> +class SeqNumUnwrapper { + static_assert( + std::is_unsigned<T>::value && + std::numeric_limits<T>::max() < std::numeric_limits<int64_t>::max(), + "Type unwrapped must be an unsigned integer smaller than int64_t."); + + public: + // Unwraps `value` and updates the internal state of the unwrapper. + int64_t Unwrap(T value) { + if (!last_value_) { + last_unwrapped_ = {value}; + } else { + last_unwrapped_ += Delta(*last_value_, value); + } + + last_value_ = value; + return last_unwrapped_; + } + + // Returns the `value` without updating the internal state of the unwrapper. + int64_t PeekUnwrap(T value) const { + if (!last_value_) { + return value; + } + return last_unwrapped_ + Delta(*last_value_, value); + } + + // Resets the unwrapper to its initial state. Unwrapped sequence numbers will + // being at 0 after resetting. + void Reset() { + last_unwrapped_ = 0; + last_value_.reset(); + } + + private: + static int64_t Delta(T last_value, T new_value) { + constexpr int64_t kBackwardAdjustment = + M == 0 ? int64_t{std::numeric_limits<T>::max()} + 1 : M; + int64_t result = ForwardDiff<T, M>(last_value, new_value); + if (!AheadOrAt<T, M>(new_value, last_value)) { + result -= kBackwardAdjustment; + } + return result; + } + + int64_t last_unwrapped_ = 0; + absl::optional<T> last_value_; +}; + +using RtpTimestampUnwrapper = SeqNumUnwrapper<uint32_t>; +using RtpSequenceNumberUnwrapper = SeqNumUnwrapper<uint16_t>; + +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UNWRAPPER_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper_unittest.cc new file mode 100644 index 0000000000..fcd903bab4 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sequence_number_unwrapper_unittest.cc @@ -0,0 +1,146 @@ +/* + * Copyright (c) 2022 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/sequence_number_unwrapper.h" + +#include <cstdint> + +#include "test/gtest.h" + +namespace webrtc { + +TEST(SeqNumUnwrapper, PreserveStartValue) { + SeqNumUnwrapper<uint8_t> unwrapper; + EXPECT_EQ(123, unwrapper.Unwrap(123)); +} + +TEST(SeqNumUnwrapper, ForwardWrap) { + SeqNumUnwrapper<uint8_t> unwrapper; + EXPECT_EQ(255, unwrapper.Unwrap(255)); + EXPECT_EQ(256, unwrapper.Unwrap(0)); +} + +TEST(SeqNumUnwrapper, ForwardWrapWithDivisor) { + SeqNumUnwrapper<uint8_t, 33> unwrapper; + EXPECT_EQ(30, unwrapper.Unwrap(30)); + EXPECT_EQ(36, unwrapper.Unwrap(3)); +} + +TEST(SeqNumUnwrapper, BackWardWrap) { + SeqNumUnwrapper<uint8_t> unwrapper; + EXPECT_EQ(0, unwrapper.Unwrap(0)); + EXPECT_EQ(-2, unwrapper.Unwrap(254)); +} + +TEST(SeqNumUnwrapper, BackWardWrapWithDivisor) { + SeqNumUnwrapper<uint8_t, 33> unwrapper; + EXPECT_EQ(0, unwrapper.Unwrap(0)); + EXPECT_EQ(-2, unwrapper.Unwrap(31)); +} + +TEST(SeqNumUnwrapper, Unwrap) { + SeqNumUnwrapper<uint16_t> unwrapper; + const uint16_t kMax = std::numeric_limits<uint16_t>::max(); + const uint16_t kMaxDist = kMax / 2 + 1; + + EXPECT_EQ(0, unwrapper.Unwrap(0)); + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(0, unwrapper.Unwrap(0)); + + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(kMax, unwrapper.Unwrap(kMax)); + EXPECT_EQ(kMax + 1, unwrapper.Unwrap(0)); + EXPECT_EQ(kMax, unwrapper.Unwrap(kMax)); + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(0, unwrapper.Unwrap(0)); +} + +TEST(SeqNumUnwrapper, UnwrapOddDivisor) { + SeqNumUnwrapper<uint8_t, 11> unwrapper; + + EXPECT_EQ(10, unwrapper.Unwrap(10)); + EXPECT_EQ(11, unwrapper.Unwrap(0)); + EXPECT_EQ(16, unwrapper.Unwrap(5)); + EXPECT_EQ(21, unwrapper.Unwrap(10)); + EXPECT_EQ(22, unwrapper.Unwrap(0)); + EXPECT_EQ(17, unwrapper.Unwrap(6)); + EXPECT_EQ(12, unwrapper.Unwrap(1)); + EXPECT_EQ(7, unwrapper.Unwrap(7)); + EXPECT_EQ(2, unwrapper.Unwrap(2)); + EXPECT_EQ(0, unwrapper.Unwrap(0)); +} + +TEST(SeqNumUnwrapper, ManyForwardWraps) { + const int kLargeNumber = 4711; + const int kMaxStep = kLargeNumber / 2; + const int kNumWraps = 100; + SeqNumUnwrapper<uint16_t, kLargeNumber> unwrapper; + + uint16_t next_unwrap = 0; + int64_t expected = 0; + for (int i = 0; i < kNumWraps * 2 + 1; ++i) { + EXPECT_EQ(expected, unwrapper.Unwrap(next_unwrap)); + expected += kMaxStep; + next_unwrap = (next_unwrap + kMaxStep) % kLargeNumber; + } +} + +TEST(SeqNumUnwrapper, ManyBackwardWraps) { + const int kLargeNumber = 4711; + const int kMaxStep = kLargeNumber / 2; + const int kNumWraps = 100; + SeqNumUnwrapper<uint16_t, kLargeNumber> unwrapper; + + uint16_t next_unwrap = 0; + int64_t expected = 0; + for (uint16_t i = 0; i < kNumWraps * 2 + 1; ++i) { + EXPECT_EQ(expected, unwrapper.Unwrap(next_unwrap)); + expected -= kMaxStep; + next_unwrap = (next_unwrap + kMaxStep + 1) % kLargeNumber; + } +} + +TEST(SeqNumUnwrapper, Reset) { + const uint16_t kMax = std::numeric_limits<uint16_t>::max(); + const uint16_t kMaxStep = kMax / 2; + SeqNumUnwrapper<uint16_t> unwrapper; + EXPECT_EQ(10, unwrapper.Unwrap(10)); + EXPECT_EQ(kMaxStep + 10, unwrapper.Unwrap(kMaxStep + 10)); + + EXPECT_EQ(kMax + 3, unwrapper.PeekUnwrap(2)); + unwrapper.Reset(); + // After Reset() the range is reset back to the start. + EXPECT_EQ(2, unwrapper.PeekUnwrap(2)); +} + +TEST(SeqNumUnwrapper, PeekUnwrap) { + const uint16_t kMax = std::numeric_limits<uint16_t>::max(); + const uint16_t kMaxStep = kMax / 2; + const uint16_t kMaxDist = kMaxStep + 1; + SeqNumUnwrapper<uint16_t> unwrapper; + // No previous unwraps, so PeekUnwrap(x) == x. + EXPECT_EQ(10, unwrapper.PeekUnwrap(10)); + EXPECT_EQ(kMaxDist + 10, unwrapper.PeekUnwrap(kMaxDist + 10)); + + EXPECT_EQ(10, unwrapper.Unwrap(10)); + EXPECT_EQ(12, unwrapper.PeekUnwrap(12)); + // State should not have updated, so kMaxDist + 12 should be negative. + EXPECT_EQ(-kMaxDist + 12, unwrapper.Unwrap(kMaxDist + 12)); + + // Test PeekUnwrap after around. + unwrapper.Reset(); + EXPECT_EQ(kMaxStep, unwrapper.Unwrap(kMaxStep)); + EXPECT_EQ(2 * kMaxStep, unwrapper.Unwrap(2 * kMaxStep)); + EXPECT_EQ(kMax + 1, unwrapper.PeekUnwrap(0)); + // Wrap back to last range. + EXPECT_EQ(kMax - 3, unwrapper.PeekUnwrap(kMax - 3)); +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/rtc_base/numerics/sequence_number_util.h b/third_party/libwebrtc/rtc_base/numerics/sequence_number_util.h new file mode 100644 index 0000000000..702b82fa2b --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sequence_number_util.h @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2016 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_SEQUENCE_NUMBER_UTIL_H_ +#define RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_ + +#include <stdint.h> + +#include <limits> +#include <type_traits> + +#include "rtc_base/numerics/mod_ops.h" + +namespace webrtc { + +// Test if the sequence number `a` is ahead or at sequence number `b`. +// +// If `M` is an even number and the two sequence numbers are at max distance +// from each other, then the sequence number with the highest value is +// considered to be ahead. +template <typename T, T M> +inline typename std::enable_if<(M > 0), bool>::type AheadOrAt(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + const T maxDist = M / 2; + if (!(M & 1) && MinDiff<T, M>(a, b) == maxDist) + return b < a; + return ForwardDiff<T, M>(b, a) <= maxDist; +} + +template <typename T, T M> +inline typename std::enable_if<(M == 0), bool>::type AheadOrAt(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + const T maxDist = std::numeric_limits<T>::max() / 2 + T(1); + if (a - b == maxDist) + return b < a; + return ForwardDiff(b, a) < maxDist; +} + +template <typename T> +inline bool AheadOrAt(T a, T b) { + return AheadOrAt<T, 0>(a, b); +} + +// Test if the sequence number `a` is ahead of sequence number `b`. +// +// If `M` is an even number and the two sequence numbers are at max distance +// from each other, then the sequence number with the highest value is +// considered to be ahead. +template <typename T, T M = 0> +inline bool AheadOf(T a, T b) { + static_assert(std::is_unsigned<T>::value, + "Type must be an unsigned integer."); + return a != b && AheadOrAt<T, M>(a, b); +} + +// Comparator used to compare sequence numbers in a continuous fashion. +// +// WARNING! If used to sort sequence numbers of length M then the interval +// covered by the sequence numbers may not be larger than floor(M/2). +template <typename T, T M = 0> +struct AscendingSeqNumComp { + bool operator()(T a, T b) const { return AheadOf<T, M>(a, b); } +}; + +// Comparator used to compare sequence numbers in a continuous fashion. +// +// WARNING! If used to sort sequence numbers of length M then the interval +// covered by the sequence numbers may not be larger than floor(M/2). +template <typename T, T M = 0> +struct DescendingSeqNumComp { + bool operator()(T a, T b) const { return AheadOf<T, M>(b, a); } +}; + +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_ diff --git a/third_party/libwebrtc/rtc_base/numerics/sequence_number_util_unittest.cc b/third_party/libwebrtc/rtc_base/numerics/sequence_number_util_unittest.cc new file mode 100644 index 0000000000..d44127bfa5 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/sequence_number_util_unittest.cc @@ -0,0 +1,215 @@ +/* + * Copyright (c) 2016 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/sequence_number_util.h" + +#include <cstdint> +#include <iterator> +#include <set> + +#include "test/gtest.h" + +namespace webrtc { +class TestSeqNumUtil : public ::testing::Test { + protected: + // Can't use std::numeric_limits<unsigned long>::max() since + // MSVC doesn't support constexpr. + static const unsigned long ulmax = ~0ul; // NOLINT +}; + +TEST_F(TestSeqNumUtil, AheadOrAt) { + uint8_t x = 0; + uint8_t y = 0; + ASSERT_TRUE(AheadOrAt(x, y)); + ++x; + ASSERT_TRUE(AheadOrAt(x, y)); + ASSERT_FALSE(AheadOrAt(y, x)); + for (int i = 0; i < 256; ++i) { + ASSERT_TRUE(AheadOrAt(x, y)); + ++x; + ++y; + } + + x = 128; + y = 0; + ASSERT_TRUE(AheadOrAt(x, y)); + ASSERT_FALSE(AheadOrAt(y, x)); + + x = 129; + ASSERT_FALSE(AheadOrAt(x, y)); + ASSERT_TRUE(AheadOrAt(y, x)); + ASSERT_TRUE(AheadOrAt<uint16_t>(x, y)); + ASSERT_FALSE(AheadOrAt<uint16_t>(y, x)); +} + +TEST_F(TestSeqNumUtil, AheadOrAtWithDivisor) { + ASSERT_TRUE((AheadOrAt<uint8_t, 11>(5, 0))); + ASSERT_FALSE((AheadOrAt<uint8_t, 11>(6, 0))); + ASSERT_FALSE((AheadOrAt<uint8_t, 11>(0, 5))); + ASSERT_TRUE((AheadOrAt<uint8_t, 11>(0, 6))); + + ASSERT_TRUE((AheadOrAt<uint8_t, 10>(5, 0))); + ASSERT_FALSE((AheadOrAt<uint8_t, 10>(6, 0))); + ASSERT_FALSE((AheadOrAt<uint8_t, 10>(0, 5))); + ASSERT_TRUE((AheadOrAt<uint8_t, 10>(0, 6))); + + const uint8_t D = 211; + uint8_t x = 0; + for (int i = 0; i < D; ++i) { + uint8_t next_x = Add<D>(x, 1); + ASSERT_TRUE((AheadOrAt<uint8_t, D>(i, i))); + ASSERT_TRUE((AheadOrAt<uint8_t, D>(next_x, i))); + ASSERT_FALSE((AheadOrAt<uint8_t, D>(i, next_x))); + x = next_x; + } +} + +TEST_F(TestSeqNumUtil, AheadOf) { + uint8_t x = 0; + uint8_t y = 0; + ASSERT_FALSE(AheadOf(x, y)); + ++x; + ASSERT_TRUE(AheadOf(x, y)); + ASSERT_FALSE(AheadOf(y, x)); + for (int i = 0; i < 256; ++i) { + ASSERT_TRUE(AheadOf(x, y)); + ++x; + ++y; + } + + x = 128; + y = 0; + for (int i = 0; i < 128; ++i) { + ASSERT_TRUE(AheadOf(x, y)); + ASSERT_FALSE(AheadOf(y, x)); + x++; + y++; + } + + for (int i = 0; i < 128; ++i) { + ASSERT_FALSE(AheadOf(x, y)); + ASSERT_TRUE(AheadOf(y, x)); + x++; + y++; + } + + x = 129; + y = 0; + ASSERT_FALSE(AheadOf(x, y)); + ASSERT_TRUE(AheadOf(y, x)); + ASSERT_TRUE(AheadOf<uint16_t>(x, y)); + ASSERT_FALSE(AheadOf<uint16_t>(y, x)); +} + +TEST_F(TestSeqNumUtil, AheadOfWithDivisor) { + ASSERT_TRUE((AheadOf<uint8_t, 11>(5, 0))); + ASSERT_FALSE((AheadOf<uint8_t, 11>(6, 0))); + ASSERT_FALSE((AheadOf<uint8_t, 11>(0, 5))); + ASSERT_TRUE((AheadOf<uint8_t, 11>(0, 6))); + + ASSERT_TRUE((AheadOf<uint8_t, 10>(5, 0))); + ASSERT_FALSE((AheadOf<uint8_t, 10>(6, 0))); + ASSERT_FALSE((AheadOf<uint8_t, 10>(0, 5))); + ASSERT_TRUE((AheadOf<uint8_t, 10>(0, 6))); + + const uint8_t D = 211; + uint8_t x = 0; + for (int i = 0; i < D; ++i) { + uint8_t next_x = Add<D>(x, 1); + ASSERT_FALSE((AheadOf<uint8_t, D>(i, i))); + ASSERT_TRUE((AheadOf<uint8_t, D>(next_x, i))); + ASSERT_FALSE((AheadOf<uint8_t, D>(i, next_x))); + x = next_x; + } +} + +TEST_F(TestSeqNumUtil, ForwardDiffWithDivisor) { + const uint8_t kDivisor = 211; + + for (uint8_t i = 0; i < kDivisor - 1; ++i) { + ASSERT_EQ(0, (ForwardDiff<uint8_t, kDivisor>(i, i))); + ASSERT_EQ(1, (ForwardDiff<uint8_t, kDivisor>(i, i + 1))); + ASSERT_EQ(kDivisor - 1, (ForwardDiff<uint8_t, kDivisor>(i + 1, i))); + } + + for (uint8_t i = 1; i < kDivisor; ++i) { + ASSERT_EQ(i, (ForwardDiff<uint8_t, kDivisor>(0, i))); + ASSERT_EQ(kDivisor - i, (ForwardDiff<uint8_t, kDivisor>(i, 0))); + } +} + +TEST_F(TestSeqNumUtil, ReverseDiffWithDivisor) { + const uint8_t kDivisor = 241; + + for (uint8_t i = 0; i < kDivisor - 1; ++i) { + ASSERT_EQ(0, (ReverseDiff<uint8_t, kDivisor>(i, i))); + ASSERT_EQ(kDivisor - 1, (ReverseDiff<uint8_t, kDivisor>(i, i + 1))); + ASSERT_EQ(1, (ReverseDiff<uint8_t, kDivisor>(i + 1, i))); + } + + for (uint8_t i = 1; i < kDivisor; ++i) { + ASSERT_EQ(kDivisor - i, (ReverseDiff<uint8_t, kDivisor>(0, i))); + ASSERT_EQ(i, (ReverseDiff<uint8_t, kDivisor>(i, 0))); + } +} + +TEST_F(TestSeqNumUtil, SeqNumComparator) { + std::set<uint8_t, AscendingSeqNumComp<uint8_t>> seq_nums_asc; + std::set<uint8_t, DescendingSeqNumComp<uint8_t>> seq_nums_desc; + + uint8_t x = 0; + for (int i = 0; i < 128; ++i) { + seq_nums_asc.insert(x); + seq_nums_desc.insert(x); + ASSERT_EQ(x, *seq_nums_asc.begin()); + ASSERT_EQ(x, *seq_nums_desc.rbegin()); + ++x; + } + + seq_nums_asc.clear(); + seq_nums_desc.clear(); + x = 199; + for (int i = 0; i < 128; ++i) { + seq_nums_asc.insert(x); + seq_nums_desc.insert(x); + ASSERT_EQ(x, *seq_nums_asc.begin()); + ASSERT_EQ(x, *seq_nums_desc.rbegin()); + ++x; + } +} + +TEST_F(TestSeqNumUtil, SeqNumComparatorWithDivisor) { + const uint8_t D = 223; + + std::set<uint8_t, AscendingSeqNumComp<uint8_t, D>> seq_nums_asc; + std::set<uint8_t, DescendingSeqNumComp<uint8_t, D>> seq_nums_desc; + + uint8_t x = 0; + for (int i = 0; i < D / 2; ++i) { + seq_nums_asc.insert(x); + seq_nums_desc.insert(x); + ASSERT_EQ(x, *seq_nums_asc.begin()); + ASSERT_EQ(x, *seq_nums_desc.rbegin()); + x = Add<D>(x, 1); + } + + seq_nums_asc.clear(); + seq_nums_desc.clear(); + x = 200; + for (int i = 0; i < D / 2; ++i) { + seq_nums_asc.insert(x); + seq_nums_desc.insert(x); + ASSERT_EQ(x, *seq_nums_asc.begin()); + ASSERT_EQ(x, *seq_nums_desc.rbegin()); + x = Add<D>(x, 1); + } +} + +} // namespace webrtc |