Implemented a new sequence number unwrapper in sequence_number_util.h.

webrtc/modules/video_coding/sequence_number_util.h

 /*
  *  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/rtc_base/mod_ops.h"
+#include "webrtc/rtc_base/optional.h"
+#include "webrtc/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 bool AheadOrAt(T a, T b) {
+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>
-inline bool AheadOrAt(T a, T b) {
+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, typename M = void>
+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>
+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);
 }
 
-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);
-  }
+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
-    : 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);
+struct DescendingSeqNumComp {
+  bool operator()(T a, T b) const { return AheadOf<T, M>(b, a); }
+};
+
+template <typename T, T M = 0>
+class SeqNumUnwrapper {

[terelius, 2017/07/10 21:20:23]

We already have an Unwrapper in webrtc/modules/include/module_common_types.h
Any chance we can use that instead?

[philipel, 2017/07/11 11:08:30]

I updated the CL description with the motivation as to why we reimplement this
functionality.

[terelius, 2017/07/11 12:38:17]

Not sure I agree with the reasons for reimplementing it. An unwrapper doesn't
seem specific to the video coding module, so to me it actually seems appropriate
to place it in modules_common_types.h
The implementation in that file isn't longer than this, and it already contains
similar helper functions like IsNewer. The initial unwrapping value is a good
point, but maybe this feature could be added to the existing class?

[philipel, 2017/07/11 12:49:06]

If that is the case then I guess we could move sequence_number_util.h to
modules/include (or maybe even to rtc_base?).

I also think that breaking module_common_types into separate files/classes is a
good thing, instead of being this large file with various functions, definitions
and classes.
The IsNewer and such functions can only handle numbers that wrap at 8/16/32
bits, but not at some other value. I expect to use this new unwrapper in the
RtpFrameReferenceFinder where for example picture ids can wrap at 15 bits.

+  static_assert(
+      std::is_unsigned<T>::value &&
+          rtc::SafeLt(std::numeric_limits<T>::max(),
+                      std::numeric_limits<uint64_t>::max()),
+      "Type unwrapped must be an unsigned integer smaller than uint64_t.");
+
+ public:
+  SeqNumUnwrapper() : last_unwrapped_(0) {}
+  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<uint64_t> last_value_;
 };
 
 }  // namespace webrtc
 
 #endif  // WEBRTC_MODULES_VIDEO_CODING_SEQUENCE_NUMBER_UTIL_H_