Move sequence_number_utils.h to rtc_base/
Bug: webrtc:8440
Change-Id: I36e70da6ce70b95db7d3fce8b0013bff5c795bfc
Reviewed-on: https://webrtc-review.googlesource.com/14860
Reviewed-by: Karl Wiberg <kwiberg@webrtc.org>
Reviewed-by: Åsa Persson <asapersson@webrtc.org>
Reviewed-by: Philip Eliasson <philipel@webrtc.org>
Commit-Queue: Björn Terelius <terelius@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#20429}diff --git a/rtc_base/BUILD.gn b/rtc_base/BUILD.gn
index 8490a60..775fd14 100644
--- a/rtc_base/BUILD.gn
+++ b/rtc_base/BUILD.gn
@@ -403,9 +403,11 @@
"numerics/exp_filter.cc",
"numerics/exp_filter.h",
"numerics/percentile_filter.h",
+ "numerics/sequence_number_util.h",
]
deps = [
":rtc_base_approved",
+ "../api:optional",
]
}
@@ -996,6 +998,7 @@
sources = [
"numerics/exp_filter_unittest.cc",
"numerics/percentile_filter_unittest.cc",
+ "numerics/sequence_number_util_unittest.cc",
]
deps = [
":rtc_base_approved",
diff --git a/rtc_base/numerics/sequence_number_util.h b/rtc_base/numerics/sequence_number_util.h
new file mode 100644
index 0000000..9dbd812
--- /dev/null
+++ b/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/mod_ops.h"
+#include "rtc_base/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/rtc_base/numerics/sequence_number_util_unittest.cc b/rtc_base/numerics/sequence_number_util_unittest.cc
new file mode 100644
index 0000000..beb2b52
--- /dev/null
+++ b/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