diff options
Diffstat (limited to 'third_party/libwebrtc/webrtc/rtc_base/numerics')
23 files changed, 3178 insertions, 0 deletions
diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/exp_filter.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/exp_filter.cc new file mode 100644 index 0000000000..0c6fb006f6 --- /dev/null +++ b/third_party/libwebrtc/webrtc/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 <math.h> + +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 = 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/webrtc/rtc_base/numerics/exp_filter.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/exp_filter.h new file mode 100644 index 0000000000..4be9a0a778 --- /dev/null +++ b/third_party/libwebrtc/webrtc/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/webrtc/rtc_base/numerics/exp_filter_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/exp_filter_unittest.cc new file mode 100644 index 0000000000..412dc77099 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/exp_filter_unittest.cc @@ -0,0 +1,71 @@ +/* + * 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 <math.h> + +#include "rtc_base/numerics/exp_filter.h" +#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) { + double 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); + double alpha = 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/webrtc/rtc_base/numerics/histogram_percentile_counter.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter.cc new file mode 100644 index 0000000000..87ebd53d47 --- /dev/null +++ b/third_party/libwebrtc/webrtc/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); +} + +rtc::Optional<uint32_t> HistogramPercentileCounter::GetPercentile( + float fraction) { + RTC_CHECK_LE(fraction, 1.0); + RTC_CHECK_GE(fraction, 0.0); + if (total_elements_ == 0) + return rtc::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_NOTREACHED(); + return rtc::nullopt; +} + +} // namespace rtc diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter.h new file mode 100644 index 0000000000..4ad2e5377d --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter.h @@ -0,0 +1,43 @@ +/* + * 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 <stdint.h> +#include <map> +#include <vector> + +#include "api/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. + rtc::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/webrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc new file mode 100644 index 0000000000..a004dbaaea --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/histogram_percentile_counter_unittest.cc @@ -0,0 +1,43 @@ +/* + * 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 <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/webrtc/rtc_base/numerics/mathutils.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/mathutils.h new file mode 100644 index 0000000000..5036c8fecb --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/mathutils.h @@ -0,0 +1,39 @@ +/* + * 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 RTC_BASE_NUMERICS_MATHUTILS_H_ +#define RTC_BASE_NUMERICS_MATHUTILS_H_ + +#include <math.h> +#include <type_traits> + +#include "rtc_base/checks.h" + +#ifndef M_PI +#define M_PI 3.14159265359f +#endif + +// 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); +} + +#endif // RTC_BASE_NUMERICS_MATHUTILS_H_ diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/mod_ops.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/mod_ops.h new file mode 100644 index 0000000000..90d3ed804f --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/mod_ops.h @@ -0,0 +1,143 @@ +/* + * 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 <limits> +#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/webrtc/rtc_base/numerics/mod_ops_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/mod_ops_unittest.cc new file mode 100644 index 0000000000..7b03e65de6 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/mod_ops_unittest.cc @@ -0,0 +1,156 @@ +/* + * 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 "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/webrtc/rtc_base/numerics/moving_max_counter.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_max_counter.h new file mode 100644 index 0000000000..4595cf3551 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_max_counter.h @@ -0,0 +1,116 @@ +/* + * 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 "api/optional.h" +#include "rtc_base/checks.h" +#include "rtc_base/constructormagic.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); + // 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. + rtc::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 + RTC_DISALLOW_COPY_AND_ASSIGN(MovingMaxCounter); +}; + +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> +rtc::Optional<T> MovingMaxCounter<T>::Max(int64_t current_time_ms) { + RollWindow(current_time_ms); + rtc::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/webrtc/rtc_base/numerics/moving_max_counter_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_max_counter_unittest.cc new file mode 100644 index 0000000000..4e74d6d4d2 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_max_counter_unittest.cc @@ -0,0 +1,57 @@ +/* + * 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/webrtc/rtc_base/numerics/moving_median_filter.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_median_filter.h new file mode 100644 index 0000000000..b5c5fcea9e --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_median_filter.h @@ -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. + */ + +#ifndef RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_ +#define RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_ + +#include <list> + +#include "rtc_base/checks.h" +#include "rtc_base/constructormagic.h" +#include "rtc_base/numerics/percentile_filter.h" + +namespace webrtc { + +// Class to efficiently get moving median filter from a stream of samples. +template <typename T> +class MovingMedianFilter { + public: + // Construct filter. |window_size| is how many latest samples are stored and + // used to take median. |window_size| must be positive. + explicit MovingMedianFilter(size_t window_size); + + // Insert a new sample. + void Insert(const T& value); + + // Removes all samples; + void Reset(); + + // Get median over the latest window. + T GetFilteredValue() const; + + private: + PercentileFilter<T> percentile_filter_; + std::list<T> samples_; + size_t samples_stored_; + const size_t window_size_; + + RTC_DISALLOW_COPY_AND_ASSIGN(MovingMedianFilter); +}; + +template <typename T> +MovingMedianFilter<T>::MovingMedianFilter(size_t window_size) + : percentile_filter_(0.5f), samples_stored_(0), window_size_(window_size) { + RTC_CHECK_GT(window_size, 0); +} + +template <typename T> +void MovingMedianFilter<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 MovingMedianFilter<T>::GetFilteredValue() const { + return percentile_filter_.GetPercentileValue(); +} + +template <typename T> +void MovingMedianFilter<T>::Reset() { + percentile_filter_.Reset(); + samples_.clear(); + samples_stored_ = 0; +} + +} // namespace webrtc +#endif // RTC_BASE_NUMERICS_MOVING_MEDIAN_FILTER_H_ diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_median_filter_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_median_filter_unittest.cc new file mode 100644 index 0000000000..5a6eb3da87 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/moving_median_filter_unittest.cc @@ -0,0 +1,51 @@ +/* + * 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_median_filter.h" +#include "test/gtest.h" + +namespace webrtc { + +TEST(MovingMedianFilterTest, ProcessesNoSamples) { + MovingMedianFilter<int> filter(2); + EXPECT_EQ(0, filter.GetFilteredValue()); +} + +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 (int i = 0; i < 5; ++i) { + filter.Insert(kSamples[i]); + EXPECT_EQ(kExpectedFilteredValues[i], filter.GetFilteredValue()); + } +} + +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()); + } +} + +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()); + } +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/percentile_filter.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/percentile_filter.h new file mode 100644 index 0000000000..cba44639b7 --- /dev/null +++ b/third_party/libwebrtc/webrtc/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/webrtc/rtc_base/numerics/percentile_filter_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/percentile_filter_unittest.cc new file mode 100644 index 0000000000..b7aff43010 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/percentile_filter_unittest.cc @@ -0,0 +1,138 @@ +/* + * 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 <algorithm> +#include <climits> + +#include "rtc_base/constructormagic.h" +#include "rtc_base/numerics/percentile_filter.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); + } + + protected: + PercentileFilter<int64_t> filter_; + + private: + RTC_DISALLOW_COPY_AND_ASSIGN(PercentileFilterTest); +}; + +INSTANTIATE_TEST_CASE_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) { + int64_t zero_to_nine[10] = {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) { + std::random_shuffle(zero_to_nine, zero_to_nine + 10); + 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) { + std::random_shuffle(zero_to_nine, zero_to_nine + 10); + for (int64_t value : zero_to_nine) + filter_.Erase(value); + EXPECT_EQ(expected_value, filter_.GetPercentileValue()); + + std::random_shuffle(zero_to_nine, zero_to_nine + 10); + for (int64_t value : zero_to_nine) + filter_.Insert(value); + EXPECT_EQ(expected_value, filter_.GetPercentileValue()); + } +} + +} // namespace webrtc diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_compare.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_compare.h new file mode 100644 index 0000000000..85f0a30e83 --- /dev/null +++ b/third_party/libwebrtc/webrtc/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/webrtc/rtc_base/numerics/safe_compare_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_compare_unittest.cc new file mode 100644 index 0000000000..e7a251f88a --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_compare_unittest.cc @@ -0,0 +1,394 @@ +/* + * 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 <limits> + +#include "rtc_base/numerics/safe_compare.h" +#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/webrtc/rtc_base/numerics/safe_conversions.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_conversions.h new file mode 100644 index 0000000000..58efcaa746 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_conversions.h @@ -0,0 +1,76 @@ +/* + * 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 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 Dst checked_cast(Src value) { + RTC_CHECK(IsValueInRangeForNumericType<Dst>(value)); + return static_cast<Dst>(value); +} +template <typename Dst, typename Src> +inline 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 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: + FATAL(); + return std::numeric_limits<Dst>::max(); + } + + FATAL(); + return static_cast<Dst>(value); +} + +} // namespace rtc + +#endif // RTC_BASE_NUMERICS_SAFE_CONVERSIONS_H_ diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_conversions_impl.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_conversions_impl.h new file mode 100644 index 0000000000..9b4f1c6483 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_conversions_impl.h @@ -0,0 +1,175 @@ +/* + * 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 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 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 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 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> { + static RangeCheckResult Check(Src value) { + 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 = sizeof(Dst) * 8; + static const size_t kSrcMaxExponent = + SrcLimits::is_iec559 ? SrcLimits::max_exponent : (sizeof(Src) * 8 - 1); + return (kDstMaxExponent >= kSrcMaxExponent) + ? 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 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/webrtc/rtc_base/numerics/safe_minmax.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_minmax.h new file mode 100644 index 0000000000..8d00afbebd --- /dev/null +++ b/third_party/libwebrtc/webrtc/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 third 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/webrtc/rtc_base/numerics/safe_minmax_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_minmax_unittest.cc new file mode 100644 index 0000000000..72d23b66f4 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/safe_minmax_unittest.cc @@ -0,0 +1,344 @@ +/* + * 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 <algorithm> +#include <limits> + +#include "rtc_base/numerics/safe_minmax.h" +#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/webrtc/rtc_base/numerics/sequence_number_util.h b/third_party/libwebrtc/webrtc/rtc_base/numerics/sequence_number_util.h new file mode 100644 index 0000000000..9e4b8446f5 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/sequence_number_util.h @@ -0,0 +1,128 @@ +/* + * 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 <limits> +#include <type_traits> + +#include "api/optional.h" +#include "rtc_base/numerics/mod_ops.h" +#include "rtc_base/numerics/safe_compare.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); } +}; + +// A sequencer number unwrapper where the start value of the unwrapped sequence +// can be set. The unwrapped value is not allowed to wrap. +template <typename T, T M = 0> +class SeqNumUnwrapper { + // Use '<' instead of rtc::SafeLt to avoid crbug.com/753488 + static_assert( + std::is_unsigned<T>::value && + std::numeric_limits<T>::max() < std::numeric_limits<uint64_t>::max(), + "Type unwrapped must be an unsigned integer smaller than uint64_t."); + + public: + // We want a default value that is close to 2^62 for a two reasons. Firstly, + // we can unwrap wrapping numbers in either direction, and secondly, the + // unwrapped numbers can be stored in either int64_t or uint64_t. We also want + // the default value to be human readable, which makes a power of 10 suitable. + static constexpr uint64_t kDefaultStartValue = 1000000000000000000UL; + + SeqNumUnwrapper() : last_unwrapped_(kDefaultStartValue) {} + explicit SeqNumUnwrapper(uint64_t start_at) : last_unwrapped_(start_at) {} + + uint64_t Unwrap(T value) { + if (!last_value_) + last_value_.emplace(value); + + uint64_t unwrapped = 0; + if (AheadOrAt<T, M>(value, *last_value_)) { + unwrapped = last_unwrapped_ + ForwardDiff<T, M>(*last_value_, value); + RTC_CHECK_GE(unwrapped, last_unwrapped_); + } else { + unwrapped = last_unwrapped_ - ReverseDiff<T, M>(*last_value_, value); + RTC_CHECK_LT(unwrapped, last_unwrapped_); + } + + *last_value_ = value; + last_unwrapped_ = unwrapped; + return last_unwrapped_; + } + + private: + uint64_t last_unwrapped_; + rtc::Optional<T> last_value_; +}; + +} // namespace webrtc + +#endif // RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_ diff --git a/third_party/libwebrtc/webrtc/rtc_base/numerics/sequence_number_util_unittest.cc b/third_party/libwebrtc/webrtc/rtc_base/numerics/sequence_number_util_unittest.cc new file mode 100644 index 0000000000..beb2b52a47 --- /dev/null +++ b/third_party/libwebrtc/webrtc/rtc_base/numerics/sequence_number_util_unittest.cc @@ -0,0 +1,320 @@ +/* + * 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 <set> + +#include "rtc_base/numerics/sequence_number_util.h" +#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); + } +} + +#if GTEST_HAS_DEATH_TEST +#if !defined(WEBRTC_ANDROID) +TEST(SeqNumUnwrapper, NoBackWardWrap) { + SeqNumUnwrapper<uint8_t> unwrapper(0); + EXPECT_EQ(0U, unwrapper.Unwrap(0)); + + // The unwrapped sequence is not allowed to wrap, if that happens the + // SeqNumUnwrapper should have been constructed with a higher start value. + EXPECT_DEATH(unwrapper.Unwrap(255), ""); +} + +TEST(SeqNumUnwrapper, NoForwardWrap) { + SeqNumUnwrapper<uint32_t> unwrapper(std::numeric_limits<uint64_t>::max()); + EXPECT_EQ(std::numeric_limits<uint64_t>::max(), unwrapper.Unwrap(0)); + + // The unwrapped sequence is not allowed to wrap, if that happens the + // SeqNumUnwrapper should have been constructed with a lower start value. + EXPECT_DEATH(unwrapper.Unwrap(1), ""); +} +#endif +#endif + +TEST(SeqNumUnwrapper, ForwardWrap) { + SeqNumUnwrapper<uint8_t> unwrapper(0); + EXPECT_EQ(0U, unwrapper.Unwrap(255)); + EXPECT_EQ(1U, unwrapper.Unwrap(0)); +} + +TEST(SeqNumUnwrapper, ForwardWrapWithDivisor) { + SeqNumUnwrapper<uint8_t, 33> unwrapper(0); + EXPECT_EQ(0U, unwrapper.Unwrap(30)); + EXPECT_EQ(6U, unwrapper.Unwrap(3)); +} + +TEST(SeqNumUnwrapper, BackWardWrap) { + SeqNumUnwrapper<uint8_t> unwrapper(10); + EXPECT_EQ(10U, unwrapper.Unwrap(0)); + EXPECT_EQ(8U, unwrapper.Unwrap(254)); +} + +TEST(SeqNumUnwrapper, BackWardWrapWithDivisor) { + SeqNumUnwrapper<uint8_t, 33> unwrapper(10); + EXPECT_EQ(10U, unwrapper.Unwrap(0)); + EXPECT_EQ(8U, unwrapper.Unwrap(31)); +} + +TEST(SeqNumUnwrapper, Unwrap) { + SeqNumUnwrapper<uint16_t> unwrapper(0); + const uint16_t kMax = std::numeric_limits<uint16_t>::max(); + const uint16_t kMaxDist = kMax / 2 + 1; + + EXPECT_EQ(0U, unwrapper.Unwrap(0)); + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(0U, unwrapper.Unwrap(0)); + + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(kMax, unwrapper.Unwrap(kMax)); + EXPECT_EQ(kMax + 1U, unwrapper.Unwrap(0)); + EXPECT_EQ(kMax, unwrapper.Unwrap(kMax)); + EXPECT_EQ(kMaxDist, unwrapper.Unwrap(kMaxDist)); + EXPECT_EQ(0U, unwrapper.Unwrap(0)); +} + +TEST(SeqNumUnwrapper, UnwrapOddDivisor) { + SeqNumUnwrapper<uint8_t, 11> unwrapper(10); + + EXPECT_EQ(10U, unwrapper.Unwrap(10)); + EXPECT_EQ(11U, unwrapper.Unwrap(0)); + EXPECT_EQ(16U, unwrapper.Unwrap(5)); + EXPECT_EQ(21U, unwrapper.Unwrap(10)); + EXPECT_EQ(22U, unwrapper.Unwrap(0)); + EXPECT_EQ(17U, unwrapper.Unwrap(6)); + EXPECT_EQ(12U, unwrapper.Unwrap(1)); + EXPECT_EQ(7U, unwrapper.Unwrap(7)); + EXPECT_EQ(2U, unwrapper.Unwrap(2)); + EXPECT_EQ(0U, 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; + uint64_t expected = decltype(unwrapper)::kDefaultStartValue; + 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(kLargeNumber * kNumWraps); + + uint16_t next_unwrap = 0; + uint64_t expected = kLargeNumber * kNumWraps; + 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; + } +} + +} // namespace webrtc |