philipel | 5ab4c6d | 2016-03-08 03:36:15 -0800 | [diff] [blame] | 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 | |
Karl Wiberg | 65c3922 | 2017-11-22 12:25:14 +0100 | [diff] [blame] | 11 | #ifndef RTC_BASE_NUMERICS_MOD_OPS_H_ |
| 12 | #define RTC_BASE_NUMERICS_MOD_OPS_H_ |
philipel | 5ab4c6d | 2016-03-08 03:36:15 -0800 | [diff] [blame] | 13 | |
Karl Wiberg | 65c3922 | 2017-11-22 12:25:14 +0100 | [diff] [blame] | 14 | #include <algorithm> |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 15 | #include <type_traits> |
philipel | 5ab4c6d | 2016-03-08 03:36:15 -0800 | [diff] [blame] | 16 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 17 | #include "rtc_base/checks.h" |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 18 | |
| 19 | namespace webrtc { |
| 20 | |
| 21 | template <unsigned long M> // NOLINT |
| 22 | inline unsigned long Add(unsigned long a, unsigned long b) { // NOLINT |
| 23 | RTC_DCHECK_LT(a, M); |
| 24 | unsigned long t = M - b % M; // NOLINT |
| 25 | unsigned long res = a - t; // NOLINT |
| 26 | if (t > a) |
| 27 | return res + M; |
| 28 | return res; |
| 29 | } |
| 30 | |
| 31 | template <unsigned long M> // NOLINT |
| 32 | inline unsigned long Subtract(unsigned long a, unsigned long b) { // NOLINT |
| 33 | RTC_DCHECK_LT(a, M); |
| 34 | unsigned long sub = b % M; // NOLINT |
| 35 | if (a < sub) |
| 36 | return M - (sub - a); |
| 37 | return a - sub; |
| 38 | } |
| 39 | |
| 40 | // Calculates the forward difference between two wrapping numbers. |
| 41 | // |
| 42 | // Example: |
| 43 | // uint8_t x = 253; |
| 44 | // uint8_t y = 2; |
| 45 | // |
| 46 | // ForwardDiff(x, y) == 5 |
| 47 | // |
| 48 | // 252 253 254 255 0 1 2 3 |
| 49 | // ################################################# |
| 50 | // | | x | | | | | y | | |
| 51 | // ################################################# |
| 52 | // |----->----->----->----->-----> |
| 53 | // |
| 54 | // ForwardDiff(y, x) == 251 |
| 55 | // |
| 56 | // 252 253 254 255 0 1 2 3 |
| 57 | // ################################################# |
| 58 | // | | x | | | | | y | | |
| 59 | // ################################################# |
| 60 | // -->-----> |----->--- |
| 61 | // |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 62 | // If M > 0 then wrapping occurs at M, if M == 0 then wrapping occurs at the |
| 63 | // largest value representable by T. |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 64 | template <typename T, T M> |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 65 | inline typename std::enable_if<(M > 0), T>::type ForwardDiff(T a, T b) { |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 66 | static_assert(std::is_unsigned<T>::value, |
| 67 | "Type must be an unsigned integer."); |
| 68 | RTC_DCHECK_LT(a, M); |
| 69 | RTC_DCHECK_LT(b, M); |
| 70 | return a <= b ? b - a : M - (a - b); |
| 71 | } |
| 72 | |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 73 | template <typename T, T M> |
| 74 | inline typename std::enable_if<(M == 0), T>::type ForwardDiff(T a, T b) { |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 75 | static_assert(std::is_unsigned<T>::value, |
| 76 | "Type must be an unsigned integer."); |
| 77 | return b - a; |
| 78 | } |
| 79 | |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 80 | template <typename T> |
| 81 | inline T ForwardDiff(T a, T b) { |
| 82 | return ForwardDiff<T, 0>(a, b); |
| 83 | } |
| 84 | |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 85 | // Calculates the reverse difference between two wrapping numbers. |
| 86 | // |
| 87 | // Example: |
| 88 | // uint8_t x = 253; |
| 89 | // uint8_t y = 2; |
| 90 | // |
| 91 | // ReverseDiff(y, x) == 5 |
| 92 | // |
| 93 | // 252 253 254 255 0 1 2 3 |
| 94 | // ################################################# |
| 95 | // | | x | | | | | y | | |
| 96 | // ################################################# |
| 97 | // <-----<-----<-----<-----<-----| |
| 98 | // |
| 99 | // ReverseDiff(x, y) == 251 |
| 100 | // |
| 101 | // 252 253 254 255 0 1 2 3 |
| 102 | // ################################################# |
| 103 | // | | x | | | | | y | | |
| 104 | // ################################################# |
| 105 | // ---<-----| |<-----<-- |
| 106 | // |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 107 | // If M > 0 then wrapping occurs at M, if M == 0 then wrapping occurs at the |
| 108 | // largest value representable by T. |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 109 | template <typename T, T M> |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 110 | inline typename std::enable_if<(M > 0), T>::type ReverseDiff(T a, T b) { |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 111 | static_assert(std::is_unsigned<T>::value, |
| 112 | "Type must be an unsigned integer."); |
| 113 | RTC_DCHECK_LT(a, M); |
| 114 | RTC_DCHECK_LT(b, M); |
| 115 | return b <= a ? a - b : M - (b - a); |
| 116 | } |
| 117 | |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 118 | template <typename T, T M> |
| 119 | inline typename std::enable_if<(M == 0), T>::type ReverseDiff(T a, T b) { |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 120 | static_assert(std::is_unsigned<T>::value, |
| 121 | "Type must be an unsigned integer."); |
| 122 | return a - b; |
| 123 | } |
| 124 | |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 125 | template <typename T> |
| 126 | inline T ReverseDiff(T a, T b) { |
| 127 | return ReverseDiff<T, 0>(a, b); |
| 128 | } |
| 129 | |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 130 | // Calculates the minimum distance between to wrapping numbers. |
| 131 | // |
| 132 | // The minimum distance is defined as min(ForwardDiff(a, b), ReverseDiff(a, b)) |
philipel | 7956c0f | 2017-07-26 07:48:15 -0700 | [diff] [blame] | 133 | template <typename T, T M = 0> |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 134 | inline T MinDiff(T a, T b) { |
| 135 | static_assert(std::is_unsigned<T>::value, |
| 136 | "Type must be an unsigned integer."); |
| 137 | return std::min(ForwardDiff<T, M>(a, b), ReverseDiff<T, M>(a, b)); |
| 138 | } |
| 139 | |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 140 | } // namespace webrtc |
philipel | 5ab4c6d | 2016-03-08 03:36:15 -0800 | [diff] [blame] | 141 | |
Karl Wiberg | 65c3922 | 2017-11-22 12:25:14 +0100 | [diff] [blame] | 142 | #endif // RTC_BASE_NUMERICS_MOD_OPS_H_ |