kwiberg | 7885d3f | 2017-04-25 12:35:07 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2017 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 | |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 11 | // Minimum and maximum |
| 12 | // =================== |
| 13 | // |
| 14 | // rtc::SafeMin(x, y) |
| 15 | // rtc::SafeMax(x, y) |
| 16 | // |
| 17 | // (These are both constexpr.) |
| 18 | // |
| 19 | // Accept two arguments of either any two integral or any two floating-point |
| 20 | // types, and return the smaller and larger value, respectively, with no |
| 21 | // truncation or wrap-around. If only one of the input types is statically |
| 22 | // guaranteed to be able to represent the result, the return type is that type; |
| 23 | // if either one would do, the result type is the smaller type. (One of these |
| 24 | // two cases always applies.) |
| 25 | // |
| 26 | // * The case with one floating-point and one integral type is not allowed, |
| 27 | // because the floating-point type will have greater range, but may not |
| 28 | // have sufficient precision to represent the integer value exactly.) |
| 29 | // |
| 30 | // Clamp (a.k.a. constrain to a given interval) |
| 31 | // ============================================ |
| 32 | // |
| 33 | // rtc::SafeClamp(x, a, b) |
| 34 | // |
| 35 | // Accepts three arguments of any mix of integral types or any mix of |
| 36 | // floating-point types, and returns the value in the closed interval [a, b] |
| 37 | // that is closest to x (that is, if x < a it returns a; if x > b it returns b; |
| 38 | // and if a <= x <= b it returns x). As for SafeMin() and SafeMax(), there is |
| 39 | // no truncation or wrap-around. The result type |
| 40 | // |
| 41 | // 1. is statically guaranteed to be able to represent the result; |
| 42 | // |
| 43 | // 2. is no larger than the largest of the three argument types; and |
| 44 | // |
Karl Wiberg | 15df2ef | 2019-01-30 10:56:33 +0100 | [diff] [blame] | 45 | // 3. has the same signedness as the type of the first argument, if this is |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 46 | // possible without violating the First or Second Law. |
| 47 | // |
| 48 | // There is always at least one type that meets criteria 1 and 2. If more than |
| 49 | // one type meets these criteria equally well, the result type is one of the |
| 50 | // types that is smallest. Note that unlike SafeMin() and SafeMax(), |
| 51 | // SafeClamp() will sometimes pick a return type that isn't the type of any of |
| 52 | // its arguments. |
| 53 | // |
| 54 | // * In this context, a type A is smaller than a type B if it has a smaller |
| 55 | // range; that is, if A::max() - A::min() < B::max() - B::min(). For |
| 56 | // example, int8_t < int16_t == uint16_t < int32_t, and all integral types |
| 57 | // are smaller than all floating-point types.) |
| 58 | // |
| 59 | // * As for SafeMin and SafeMax, mixing integer and floating-point arguments |
| 60 | // is not allowed, because floating-point types have greater range than |
| 61 | // integer types, but do not have sufficient precision to represent the |
| 62 | // values of most integer types exactly. |
| 63 | // |
| 64 | // Requesting a specific return type |
| 65 | // ================================= |
| 66 | // |
| 67 | // All three functions allow callers to explicitly specify the return type as a |
| 68 | // template parameter, overriding the default return type. E.g. |
| 69 | // |
| 70 | // rtc::SafeMin<int>(x, y) // returns an int |
| 71 | // |
| 72 | // If the requested type is statically guaranteed to be able to represent the |
| 73 | // result, then everything's fine, and the return type is as requested. But if |
| 74 | // the requested type is too small, a static_assert is triggered. |
| 75 | |
Karl Wiberg | e40468b | 2017-11-22 10:42:26 +0100 | [diff] [blame] | 76 | #ifndef RTC_BASE_NUMERICS_SAFE_MINMAX_H_ |
| 77 | #define RTC_BASE_NUMERICS_SAFE_MINMAX_H_ |
kwiberg | 7885d3f | 2017-04-25 12:35:07 -0700 | [diff] [blame] | 78 | |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 79 | #include <limits> |
| 80 | #include <type_traits> |
| 81 | |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 82 | #include "rtc_base/checks.h" |
Karl Wiberg | e40468b | 2017-11-22 10:42:26 +0100 | [diff] [blame] | 83 | #include "rtc_base/numerics/safe_compare.h" |
Mirko Bonadei | 92ea95e | 2017-09-15 06:47:31 +0200 | [diff] [blame] | 84 | #include "rtc_base/type_traits.h" |
Henrik Kjellander | ec78f1c | 2017-06-29 07:52:50 +0200 | [diff] [blame] | 85 | |
| 86 | namespace rtc { |
| 87 | |
| 88 | namespace safe_minmax_impl { |
| 89 | |
| 90 | // Make the range of a type available via something other than a constexpr |
| 91 | // function, to work around MSVC limitations. See |
| 92 | // https://blogs.msdn.microsoft.com/vcblog/2015/12/02/partial-support-for-expression-sfinae-in-vs-2015-update-1/ |
| 93 | template <typename T> |
| 94 | struct Limits { |
| 95 | static constexpr T lowest = std::numeric_limits<T>::lowest(); |
| 96 | static constexpr T max = std::numeric_limits<T>::max(); |
| 97 | }; |
| 98 | |
| 99 | template <typename T, bool is_enum = std::is_enum<T>::value> |
| 100 | struct UnderlyingType; |
| 101 | |
| 102 | template <typename T> |
| 103 | struct UnderlyingType<T, false> { |
| 104 | using type = T; |
| 105 | }; |
| 106 | |
| 107 | template <typename T> |
| 108 | struct UnderlyingType<T, true> { |
| 109 | using type = typename std::underlying_type<T>::type; |
| 110 | }; |
| 111 | |
| 112 | // Given two types T1 and T2, find types that can hold the smallest (in |
| 113 | // ::min_t) and the largest (in ::max_t) of the two values. |
| 114 | template <typename T1, |
| 115 | typename T2, |
| 116 | bool int1 = IsIntlike<T1>::value, |
| 117 | bool int2 = IsIntlike<T2>::value> |
| 118 | struct MType { |
| 119 | static_assert(int1 == int2, |
| 120 | "You may not mix integral and floating-point arguments"); |
| 121 | }; |
| 122 | |
| 123 | // Specialization for when neither type is integral (and therefore presumably |
| 124 | // floating-point). |
| 125 | template <typename T1, typename T2> |
| 126 | struct MType<T1, T2, false, false> { |
| 127 | using min_t = typename std::common_type<T1, T2>::type; |
| 128 | static_assert(std::is_same<min_t, T1>::value || |
| 129 | std::is_same<min_t, T2>::value, |
| 130 | ""); |
| 131 | |
| 132 | using max_t = typename std::common_type<T1, T2>::type; |
| 133 | static_assert(std::is_same<max_t, T1>::value || |
| 134 | std::is_same<max_t, T2>::value, |
| 135 | ""); |
| 136 | }; |
| 137 | |
| 138 | // Specialization for when both types are integral. |
| 139 | template <typename T1, typename T2> |
| 140 | struct MType<T1, T2, true, true> { |
| 141 | // The type with the lowest minimum value. In case of a tie, the type with |
| 142 | // the lowest maximum value. In case that too is a tie, the types have the |
| 143 | // same range, and we arbitrarily pick T1. |
| 144 | using min_t = typename std::conditional< |
| 145 | SafeLt(Limits<T1>::lowest, Limits<T2>::lowest), |
| 146 | T1, |
| 147 | typename std::conditional< |
| 148 | SafeGt(Limits<T1>::lowest, Limits<T2>::lowest), |
| 149 | T2, |
| 150 | typename std::conditional<SafeLe(Limits<T1>::max, Limits<T2>::max), |
| 151 | T1, |
| 152 | T2>::type>::type>::type; |
| 153 | static_assert(std::is_same<min_t, T1>::value || |
| 154 | std::is_same<min_t, T2>::value, |
| 155 | ""); |
| 156 | |
| 157 | // The type with the highest maximum value. In case of a tie, the types have |
| 158 | // the same range (because in C++, integer types with the same maximum also |
| 159 | // have the same minimum). |
| 160 | static_assert(SafeNe(Limits<T1>::max, Limits<T2>::max) || |
| 161 | SafeEq(Limits<T1>::lowest, Limits<T2>::lowest), |
| 162 | "integer types with the same max should have the same min"); |
| 163 | using max_t = typename std:: |
| 164 | conditional<SafeGe(Limits<T1>::max, Limits<T2>::max), T1, T2>::type; |
| 165 | static_assert(std::is_same<max_t, T1>::value || |
| 166 | std::is_same<max_t, T2>::value, |
| 167 | ""); |
| 168 | }; |
| 169 | |
| 170 | // A dummy type that we pass around at compile time but never actually use. |
| 171 | // Declared but not defined. |
| 172 | struct DefaultType; |
| 173 | |
| 174 | // ::type is A, except we fall back to B if A is DefaultType. We static_assert |
| 175 | // that the chosen type can hold all values that B can hold. |
| 176 | template <typename A, typename B> |
| 177 | struct TypeOr { |
| 178 | using type = typename std:: |
| 179 | conditional<std::is_same<A, DefaultType>::value, B, A>::type; |
| 180 | static_assert(SafeLe(Limits<type>::lowest, Limits<B>::lowest) && |
| 181 | SafeGe(Limits<type>::max, Limits<B>::max), |
| 182 | "The specified type isn't large enough"); |
| 183 | static_assert(IsIntlike<type>::value == IsIntlike<B>::value && |
| 184 | std::is_floating_point<type>::value == |
| 185 | std::is_floating_point<type>::value, |
| 186 | "float<->int conversions not allowed"); |
| 187 | }; |
| 188 | |
| 189 | } // namespace safe_minmax_impl |
| 190 | |
| 191 | template < |
| 192 | typename R = safe_minmax_impl::DefaultType, |
| 193 | typename T1 = safe_minmax_impl::DefaultType, |
| 194 | typename T2 = safe_minmax_impl::DefaultType, |
| 195 | typename R2 = typename safe_minmax_impl::TypeOr< |
| 196 | R, |
| 197 | typename safe_minmax_impl::MType< |
| 198 | typename safe_minmax_impl::UnderlyingType<T1>::type, |
| 199 | typename safe_minmax_impl::UnderlyingType<T2>::type>::min_t>::type> |
| 200 | constexpr R2 SafeMin(T1 a, T2 b) { |
| 201 | static_assert(IsIntlike<T1>::value || std::is_floating_point<T1>::value, |
| 202 | "The first argument must be integral or floating-point"); |
| 203 | static_assert(IsIntlike<T2>::value || std::is_floating_point<T2>::value, |
| 204 | "The second argument must be integral or floating-point"); |
| 205 | return SafeLt(a, b) ? static_cast<R2>(a) : static_cast<R2>(b); |
| 206 | } |
| 207 | |
| 208 | template < |
| 209 | typename R = safe_minmax_impl::DefaultType, |
| 210 | typename T1 = safe_minmax_impl::DefaultType, |
| 211 | typename T2 = safe_minmax_impl::DefaultType, |
| 212 | typename R2 = typename safe_minmax_impl::TypeOr< |
| 213 | R, |
| 214 | typename safe_minmax_impl::MType< |
| 215 | typename safe_minmax_impl::UnderlyingType<T1>::type, |
| 216 | typename safe_minmax_impl::UnderlyingType<T2>::type>::max_t>::type> |
| 217 | constexpr R2 SafeMax(T1 a, T2 b) { |
| 218 | static_assert(IsIntlike<T1>::value || std::is_floating_point<T1>::value, |
| 219 | "The first argument must be integral or floating-point"); |
| 220 | static_assert(IsIntlike<T2>::value || std::is_floating_point<T2>::value, |
| 221 | "The second argument must be integral or floating-point"); |
| 222 | return SafeGt(a, b) ? static_cast<R2>(a) : static_cast<R2>(b); |
| 223 | } |
| 224 | |
| 225 | namespace safe_minmax_impl { |
| 226 | |
| 227 | // Given three types T, L, and H, let ::type be a suitable return value for |
| 228 | // SafeClamp(T, L, H). See the docs at the top of this file for details. |
| 229 | template <typename T, |
| 230 | typename L, |
| 231 | typename H, |
| 232 | bool int1 = IsIntlike<T>::value, |
| 233 | bool int2 = IsIntlike<L>::value, |
| 234 | bool int3 = IsIntlike<H>::value> |
| 235 | struct ClampType { |
| 236 | static_assert(int1 == int2 && int1 == int3, |
| 237 | "You may not mix integral and floating-point arguments"); |
| 238 | }; |
| 239 | |
| 240 | // Specialization for when all three types are floating-point. |
| 241 | template <typename T, typename L, typename H> |
| 242 | struct ClampType<T, L, H, false, false, false> { |
| 243 | using type = typename std::common_type<T, L, H>::type; |
| 244 | }; |
| 245 | |
| 246 | // Specialization for when all three types are integral. |
| 247 | template <typename T, typename L, typename H> |
| 248 | struct ClampType<T, L, H, true, true, true> { |
| 249 | private: |
| 250 | // Range of the return value. The return type must be able to represent this |
| 251 | // full range. |
| 252 | static constexpr auto r_min = |
| 253 | SafeMax(Limits<L>::lowest, SafeMin(Limits<H>::lowest, Limits<T>::lowest)); |
| 254 | static constexpr auto r_max = |
| 255 | SafeMin(Limits<H>::max, SafeMax(Limits<L>::max, Limits<T>::max)); |
| 256 | |
| 257 | // Is the given type an acceptable return type? (That is, can it represent |
| 258 | // all possible return values, and is it no larger than the largest of the |
| 259 | // input types?) |
| 260 | template <typename A> |
| 261 | struct AcceptableType { |
| 262 | private: |
| 263 | static constexpr bool not_too_large = sizeof(A) <= sizeof(L) || |
| 264 | sizeof(A) <= sizeof(H) || |
| 265 | sizeof(A) <= sizeof(T); |
| 266 | static constexpr bool range_contained = |
| 267 | SafeLe(Limits<A>::lowest, r_min) && SafeLe(r_max, Limits<A>::max); |
| 268 | |
| 269 | public: |
| 270 | static constexpr bool value = not_too_large && range_contained; |
| 271 | }; |
| 272 | |
| 273 | using best_signed_type = typename std::conditional< |
| 274 | AcceptableType<int8_t>::value, |
| 275 | int8_t, |
| 276 | typename std::conditional< |
| 277 | AcceptableType<int16_t>::value, |
| 278 | int16_t, |
| 279 | typename std::conditional<AcceptableType<int32_t>::value, |
| 280 | int32_t, |
| 281 | int64_t>::type>::type>::type; |
| 282 | |
| 283 | using best_unsigned_type = typename std::conditional< |
| 284 | AcceptableType<uint8_t>::value, |
| 285 | uint8_t, |
| 286 | typename std::conditional< |
| 287 | AcceptableType<uint16_t>::value, |
| 288 | uint16_t, |
| 289 | typename std::conditional<AcceptableType<uint32_t>::value, |
| 290 | uint32_t, |
| 291 | uint64_t>::type>::type>::type; |
| 292 | |
| 293 | public: |
| 294 | // Pick the best type, preferring the same signedness as T but falling back |
| 295 | // to the other one if necessary. |
| 296 | using type = typename std::conditional< |
| 297 | std::is_signed<T>::value, |
| 298 | typename std::conditional<AcceptableType<best_signed_type>::value, |
| 299 | best_signed_type, |
| 300 | best_unsigned_type>::type, |
| 301 | typename std::conditional<AcceptableType<best_unsigned_type>::value, |
| 302 | best_unsigned_type, |
| 303 | best_signed_type>::type>::type; |
| 304 | static_assert(AcceptableType<type>::value, ""); |
| 305 | }; |
| 306 | |
| 307 | } // namespace safe_minmax_impl |
| 308 | |
| 309 | template < |
| 310 | typename R = safe_minmax_impl::DefaultType, |
| 311 | typename T = safe_minmax_impl::DefaultType, |
| 312 | typename L = safe_minmax_impl::DefaultType, |
| 313 | typename H = safe_minmax_impl::DefaultType, |
| 314 | typename R2 = typename safe_minmax_impl::TypeOr< |
| 315 | R, |
| 316 | typename safe_minmax_impl::ClampType< |
| 317 | typename safe_minmax_impl::UnderlyingType<T>::type, |
| 318 | typename safe_minmax_impl::UnderlyingType<L>::type, |
| 319 | typename safe_minmax_impl::UnderlyingType<H>::type>::type>::type> |
| 320 | R2 SafeClamp(T x, L min, H max) { |
| 321 | static_assert(IsIntlike<H>::value || std::is_floating_point<H>::value, |
| 322 | "The first argument must be integral or floating-point"); |
| 323 | static_assert(IsIntlike<T>::value || std::is_floating_point<T>::value, |
| 324 | "The second argument must be integral or floating-point"); |
| 325 | static_assert(IsIntlike<L>::value || std::is_floating_point<L>::value, |
| 326 | "The third argument must be integral or floating-point"); |
| 327 | RTC_DCHECK_LE(min, max); |
| 328 | return SafeLe(x, min) |
| 329 | ? static_cast<R2>(min) |
| 330 | : SafeGe(x, max) ? static_cast<R2>(max) : static_cast<R2>(x); |
| 331 | } |
| 332 | |
| 333 | } // namespace rtc |
kwiberg | 7885d3f | 2017-04-25 12:35:07 -0700 | [diff] [blame] | 334 | |
Karl Wiberg | e40468b | 2017-11-22 10:42:26 +0100 | [diff] [blame] | 335 | #endif // RTC_BASE_NUMERICS_SAFE_MINMAX_H_ |