Moved sequence number specific operations from mod_ops.h
to sequence_number_util.h
Also in this CL:
- Implemented a MinDiff function which finds the smallest diff of two
wrapping numbers.
- Implemented comparators for sequence numbers.
BUG=
R=mflodman@webrtc.org, tommi@webrtc.org, torbjorng@webrtc.org
Review URL: https://codereview.webrtc.org/1814753002 .
Cr-Commit-Position: refs/heads/master@{#12083}
diff --git a/webrtc/modules/video_coding/histogram.cc b/webrtc/modules/video_coding/histogram.cc
index e07d50b..f2aa6ea 100644
--- a/webrtc/modules/video_coding/histogram.cc
+++ b/webrtc/modules/video_coding/histogram.cc
@@ -12,7 +12,7 @@
#include <algorithm>
-#include "webrtc/base/mod_ops.h"
+#include "webrtc/modules/video_coding/sequence_number_util.h"
namespace webrtc {
namespace video_coding {
diff --git a/webrtc/modules/video_coding/nack_module.cc b/webrtc/modules/video_coding/nack_module.cc
index 80f8496..1b12afe 100644
--- a/webrtc/modules/video_coding/nack_module.cc
+++ b/webrtc/modules/video_coding/nack_module.cc
@@ -15,7 +15,6 @@
#include "webrtc/base/checks.h"
#include "webrtc/base/logging.h"
-#include "webrtc/base/mod_ops.h"
#include "webrtc/modules/utility/include/process_thread.h"
namespace webrtc {
diff --git a/webrtc/modules/video_coding/nack_module.h b/webrtc/modules/video_coding/nack_module.h
index 8e0a79b..7163a8e 100644
--- a/webrtc/modules/video_coding/nack_module.h
+++ b/webrtc/modules/video_coding/nack_module.h
@@ -16,12 +16,12 @@
#include <set>
#include "webrtc/base/criticalsection.h"
-#include "webrtc/base/mod_ops.h"
#include "webrtc/base/thread_annotations.h"
#include "webrtc/modules/include/module.h"
#include "webrtc/modules/video_coding/include/video_coding_defines.h"
#include "webrtc/modules/video_coding/packet.h"
#include "webrtc/modules/video_coding/histogram.h"
+#include "webrtc/modules/video_coding/sequence_number_util.h"
#include "webrtc/system_wrappers/include/clock.h"
namespace webrtc {
diff --git a/webrtc/modules/video_coding/nack_module_unittest.cc b/webrtc/modules/video_coding/nack_module_unittest.cc
index fab03ce..3870742 100644
--- a/webrtc/modules/video_coding/nack_module_unittest.cc
+++ b/webrtc/modules/video_coding/nack_module_unittest.cc
@@ -15,7 +15,6 @@
#include "webrtc/modules/video_coding/include/video_coding_defines.h"
#include "webrtc/modules/video_coding/nack_module.h"
#include "webrtc/system_wrappers/include/clock.h"
-#include "webrtc/base/mod_ops.h"
namespace webrtc {
class TestNackModule : public ::testing::Test,
diff --git a/webrtc/modules/video_coding/sequence_number_util.h b/webrtc/modules/video_coding/sequence_number_util.h
new file mode 100644
index 0000000..828e68a
--- /dev/null
+++ b/webrtc/modules/video_coding/sequence_number_util.h
@@ -0,0 +1,110 @@
+/*
+ * 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 WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_
+#define WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_
+
+#include <limits>
+#include <type_traits>
+
+#include "webrtc/base/mod_ops.h"
+
+namespace webrtc {
+
+// Test if the sequence number |a| is ahead or at sequence number |b|.
+//
+// If |M| is an even number and the two sequence numbers are at max distance
+// from each other, then the sequence number with the highest value is
+// considered to be ahead.
+template <typename T, T M>
+inline bool 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>
+inline bool 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;
+}
+
+// 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>
+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);
+}
+
+template <typename T>
+inline bool AheadOf(T a, T b) {
+ static_assert(std::is_unsigned<T>::value,
+ "Type must be an unsigned integer.");
+ return a != b && AheadOrAt(a, b);
+}
+
+namespace internal {
+
+template <typename T, typename M>
+struct SeqNumComp;
+
+template <typename T, T M>
+struct SeqNumComp<T, std::integral_constant<T, M>> {
+ bool operator()(T a, T b) const { return AheadOf<T, M>(a, b); }
+};
+
+template <typename T>
+struct SeqNumComp<T, std::integral_constant<T, T(0)>> {
+ bool operator()(T a, T b) const { return AheadOf<T>(a, b); }
+};
+
+} // namespace internal
+
+// 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
+ : private internal::SeqNumComp<T, std::integral_constant<T, M>> {
+ bool operator()(T a, T b) const {
+ return internal::SeqNumComp<T, std::integral_constant<T, M>>::operator()(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
+ : private internal::SeqNumComp<T, std::integral_constant<T, M>> {
+ bool operator()(T a, T b) const {
+ return internal::SeqNumComp<T, std::integral_constant<T, M>>::operator()(b,
+ a);
+ }
+};
+
+} // namespace webrtc
+
+#endif // WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_
diff --git a/webrtc/modules/video_coding/sequence_number_util_unittest.cc b/webrtc/modules/video_coding/sequence_number_util_unittest.cc
new file mode 100644
index 0000000..8028efd
--- /dev/null
+++ b/webrtc/modules/video_coding/sequence_number_util_unittest.cc
@@ -0,0 +1,212 @@
+/*
+ * 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 "testing/gtest/include/gtest/gtest.h"
+#include "webrtc/modules/video_coding/sequence_number_util.h"
+
+namespace webrtc {
+class TestSeqNumUtil : public ::testing::Test {
+ protected:
+ // Can't use std::numeric_limits<unsigned long>::max() since
+ // MSVC doesn't support constexpr.
+ static const unsigned long ulmax = ~0ul; // NOLINT
+};
+
+TEST_F(TestSeqNumUtil, AheadOrAt) {
+ uint8_t x = 0;
+ uint8_t y = 0;
+ ASSERT_TRUE(AheadOrAt(x, y));
+ ++x;
+ ASSERT_TRUE(AheadOrAt(x, y));
+ ASSERT_FALSE(AheadOrAt(y, x));
+ for (int i = 0; i < 256; ++i) {
+ ASSERT_TRUE(AheadOrAt(x, y));
+ ++x;
+ ++y;
+ }
+
+ x = 128;
+ y = 0;
+ ASSERT_TRUE(AheadOrAt(x, y));
+ ASSERT_FALSE(AheadOrAt(y, x));
+
+ x = 129;
+ ASSERT_FALSE(AheadOrAt(x, y));
+ ASSERT_TRUE(AheadOrAt(y, x));
+ ASSERT_TRUE(AheadOrAt<uint16_t>(x, y));
+ ASSERT_FALSE(AheadOrAt<uint16_t>(y, x));
+}
+
+TEST_F(TestSeqNumUtil, AheadOrAtWithDivisor) {
+ ASSERT_TRUE((AheadOrAt<uint8_t, 11>(5, 0)));
+ ASSERT_FALSE((AheadOrAt<uint8_t, 11>(6, 0)));
+ ASSERT_FALSE((AheadOrAt<uint8_t, 11>(0, 5)));
+ ASSERT_TRUE((AheadOrAt<uint8_t, 11>(0, 6)));
+
+ ASSERT_TRUE((AheadOrAt<uint8_t, 10>(5, 0)));
+ ASSERT_FALSE((AheadOrAt<uint8_t, 10>(6, 0)));
+ ASSERT_FALSE((AheadOrAt<uint8_t, 10>(0, 5)));
+ ASSERT_TRUE((AheadOrAt<uint8_t, 10>(0, 6)));
+
+ const uint8_t D = 211;
+ uint8_t x = 0;
+ for (int i = 0; i < D; ++i) {
+ uint8_t next_x = Add<D>(x, 1);
+ ASSERT_TRUE((AheadOrAt<uint8_t, D>(i, i)));
+ ASSERT_TRUE((AheadOrAt<uint8_t, D>(next_x, i)));
+ ASSERT_FALSE((AheadOrAt<uint8_t, D>(i, next_x)));
+ x = next_x;
+ }
+}
+
+TEST_F(TestSeqNumUtil, AheadOf) {
+ uint8_t x = 0;
+ uint8_t y = 0;
+ ASSERT_FALSE(AheadOf(x, y));
+ ++x;
+ ASSERT_TRUE(AheadOf(x, y));
+ ASSERT_FALSE(AheadOf(y, x));
+ for (int i = 0; i < 256; ++i) {
+ ASSERT_TRUE(AheadOf(x, y));
+ ++x;
+ ++y;
+ }
+
+ x = 128;
+ y = 0;
+ for (int i = 0; i < 128; ++i) {
+ ASSERT_TRUE(AheadOf(x, y));
+ ASSERT_FALSE(AheadOf(y, x));
+ x++;
+ y++;
+ }
+
+ for (int i = 0; i < 128; ++i) {
+ ASSERT_FALSE(AheadOf(x, y));
+ ASSERT_TRUE(AheadOf(y, x));
+ x++;
+ y++;
+ }
+
+ x = 129;
+ y = 0;
+ ASSERT_FALSE(AheadOf(x, y));
+ ASSERT_TRUE(AheadOf(y, x));
+ ASSERT_TRUE(AheadOf<uint16_t>(x, y));
+ ASSERT_FALSE(AheadOf<uint16_t>(y, x));
+}
+
+TEST_F(TestSeqNumUtil, AheadOfWithDivisor) {
+ ASSERT_TRUE((AheadOf<uint8_t, 11>(5, 0)));
+ ASSERT_FALSE((AheadOf<uint8_t, 11>(6, 0)));
+ ASSERT_FALSE((AheadOf<uint8_t, 11>(0, 5)));
+ ASSERT_TRUE((AheadOf<uint8_t, 11>(0, 6)));
+
+ ASSERT_TRUE((AheadOf<uint8_t, 10>(5, 0)));
+ ASSERT_FALSE((AheadOf<uint8_t, 10>(6, 0)));
+ ASSERT_FALSE((AheadOf<uint8_t, 10>(0, 5)));
+ ASSERT_TRUE((AheadOf<uint8_t, 10>(0, 6)));
+
+ const uint8_t D = 211;
+ uint8_t x = 0;
+ for (int i = 0; i < D; ++i) {
+ uint8_t next_x = Add<D>(x, 1);
+ ASSERT_FALSE((AheadOf<uint8_t, D>(i, i)));
+ ASSERT_TRUE((AheadOf<uint8_t, D>(next_x, i)));
+ ASSERT_FALSE((AheadOf<uint8_t, D>(i, next_x)));
+ x = next_x;
+ }
+}
+
+TEST_F(TestSeqNumUtil, ForwardDiffWithDivisor) {
+ const uint8_t kDivisor = 211;
+
+ for (uint8_t i = 0; i < kDivisor - 1; ++i) {
+ ASSERT_EQ(0, (ForwardDiff<uint8_t, kDivisor>(i, i)));
+ ASSERT_EQ(1, (ForwardDiff<uint8_t, kDivisor>(i, i + 1)));
+ ASSERT_EQ(kDivisor - 1, (ForwardDiff<uint8_t, kDivisor>(i + 1, i)));
+ }
+
+ for (uint8_t i = 1; i < kDivisor; ++i) {
+ ASSERT_EQ(i, (ForwardDiff<uint8_t, kDivisor>(0, i)));
+ ASSERT_EQ(kDivisor - i, (ForwardDiff<uint8_t, kDivisor>(i, 0)));
+ }
+}
+
+TEST_F(TestSeqNumUtil, ReverseDiffWithDivisor) {
+ const uint8_t kDivisor = 241;
+
+ for (uint8_t i = 0; i < kDivisor - 1; ++i) {
+ ASSERT_EQ(0, (ReverseDiff<uint8_t, kDivisor>(i, i)));
+ ASSERT_EQ(kDivisor - 1, (ReverseDiff<uint8_t, kDivisor>(i, i + 1)));
+ ASSERT_EQ(1, (ReverseDiff<uint8_t, kDivisor>(i + 1, i)));
+ }
+
+ for (uint8_t i = 1; i < kDivisor; ++i) {
+ ASSERT_EQ(kDivisor - i, (ReverseDiff<uint8_t, kDivisor>(0, i)));
+ ASSERT_EQ(i, (ReverseDiff<uint8_t, kDivisor>(i, 0)));
+ }
+}
+
+TEST_F(TestSeqNumUtil, SeqNumComparator) {
+ std::set<uint8_t, AscendingSeqNumComp<uint8_t>> seq_nums_asc;
+ std::set<uint8_t, DescendingSeqNumComp<uint8_t>> seq_nums_desc;
+
+ uint8_t x = 0;
+ for (int i = 0; i < 128; ++i) {
+ seq_nums_asc.insert(x);
+ seq_nums_desc.insert(x);
+ ASSERT_EQ(x, *seq_nums_asc.begin());
+ ASSERT_EQ(x, *seq_nums_desc.rbegin());
+ ++x;
+ }
+
+ seq_nums_asc.clear();
+ seq_nums_desc.clear();
+ x = 199;
+ for (int i = 0; i < 128; ++i) {
+ seq_nums_asc.insert(x);
+ seq_nums_desc.insert(x);
+ ASSERT_EQ(x, *seq_nums_asc.begin());
+ ASSERT_EQ(x, *seq_nums_desc.rbegin());
+ ++x;
+ }
+}
+
+TEST_F(TestSeqNumUtil, SeqNumComparatorWithDivisor) {
+ const uint8_t D = 223;
+
+ std::set<uint8_t, AscendingSeqNumComp<uint8_t, D>> seq_nums_asc;
+ std::set<uint8_t, DescendingSeqNumComp<uint8_t, D>> seq_nums_desc;
+
+ uint8_t x = 0;
+ for (int i = 0; i < D / 2; ++i) {
+ seq_nums_asc.insert(x);
+ seq_nums_desc.insert(x);
+ ASSERT_EQ(x, *seq_nums_asc.begin());
+ ASSERT_EQ(x, *seq_nums_desc.rbegin());
+ x = Add<D>(x, 1);
+ }
+
+ seq_nums_asc.clear();
+ seq_nums_desc.clear();
+ x = 200;
+ for (int i = 0; i < D / 2; ++i) {
+ seq_nums_asc.insert(x);
+ seq_nums_desc.insert(x);
+ ASSERT_EQ(x, *seq_nums_asc.begin());
+ ASSERT_EQ(x, *seq_nums_desc.rbegin());
+ x = Add<D>(x, 1);
+ }
+}
+
+} // namespace webrtc