1 /*
2 * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #ifndef RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_
12 #define RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_
13
14 #include <stdint.h>
15
16 #include <limits>
17 #include <type_traits>
18
19 #include "absl/types/optional.h"
20 #include "rtc_base/checks.h"
21 #include "rtc_base/numerics/mod_ops.h"
22
23 namespace webrtc {
24
25 // Test if the sequence number |a| is ahead or at sequence number |b|.
26 //
27 // If |M| is an even number and the two sequence numbers are at max distance
28 // from each other, then the sequence number with the highest value is
29 // considered to be ahead.
30 template <typename T, T M>
AheadOrAt(T a,T b)31 inline typename std::enable_if<(M > 0), bool>::type AheadOrAt(T a, T b) {
32 static_assert(std::is_unsigned<T>::value,
33 "Type must be an unsigned integer.");
34 const T maxDist = M / 2;
35 if (!(M & 1) && MinDiff<T, M>(a, b) == maxDist)
36 return b < a;
37 return ForwardDiff<T, M>(b, a) <= maxDist;
38 }
39
40 template <typename T, T M>
AheadOrAt(T a,T b)41 inline typename std::enable_if<(M == 0), bool>::type AheadOrAt(T a, T b) {
42 static_assert(std::is_unsigned<T>::value,
43 "Type must be an unsigned integer.");
44 const T maxDist = std::numeric_limits<T>::max() / 2 + T(1);
45 if (a - b == maxDist)
46 return b < a;
47 return ForwardDiff(b, a) < maxDist;
48 }
49
50 template <typename T>
AheadOrAt(T a,T b)51 inline bool AheadOrAt(T a, T b) {
52 return AheadOrAt<T, 0>(a, b);
53 }
54
55 // Test if the sequence number |a| is ahead of sequence number |b|.
56 //
57 // If |M| is an even number and the two sequence numbers are at max distance
58 // from each other, then the sequence number with the highest value is
59 // considered to be ahead.
60 template <typename T, T M = 0>
AheadOf(T a,T b)61 inline bool AheadOf(T a, T b) {
62 static_assert(std::is_unsigned<T>::value,
63 "Type must be an unsigned integer.");
64 return a != b && AheadOrAt<T, M>(a, b);
65 }
66
67 // Comparator used to compare sequence numbers in a continuous fashion.
68 //
69 // WARNING! If used to sort sequence numbers of length M then the interval
70 // covered by the sequence numbers may not be larger than floor(M/2).
71 template <typename T, T M = 0>
72 struct AscendingSeqNumComp {
operatorAscendingSeqNumComp73 bool operator()(T a, T b) const { return AheadOf<T, M>(a, b); }
74 };
75
76 // Comparator used to compare sequence numbers in a continuous fashion.
77 //
78 // WARNING! If used to sort sequence numbers of length M then the interval
79 // covered by the sequence numbers may not be larger than floor(M/2).
80 template <typename T, T M = 0>
81 struct DescendingSeqNumComp {
operatorDescendingSeqNumComp82 bool operator()(T a, T b) const { return AheadOf<T, M>(b, a); }
83 };
84
85 // A sequence number unwrapper where the first unwrapped value equals the
86 // first value being unwrapped.
87 template <typename T, T M = 0>
88 class SeqNumUnwrapper {
89 static_assert(
90 std::is_unsigned<T>::value &&
91 std::numeric_limits<T>::max() < std::numeric_limits<int64_t>::max(),
92 "Type unwrapped must be an unsigned integer smaller than int64_t.");
93
94 public:
Unwrap(T value)95 int64_t Unwrap(T value) {
96 if (!last_value_) {
97 last_unwrapped_ = {value};
98 } else {
99 last_unwrapped_ += ForwardDiff<T, M>(*last_value_, value);
100
101 if (!AheadOrAt<T, M>(value, *last_value_)) {
102 constexpr int64_t kBackwardAdjustment =
103 M == 0 ? int64_t{std::numeric_limits<T>::max()} + 1 : M;
104 last_unwrapped_ -= kBackwardAdjustment;
105 }
106 }
107
108 last_value_ = value;
109 return last_unwrapped_;
110 }
111
112 private:
113 int64_t last_unwrapped_ = 0;
114 absl::optional<T> last_value_;
115 };
116
117 } // namespace webrtc
118
119 #endif // RTC_BASE_NUMERICS_SEQUENCE_NUMBER_UTIL_H_
120