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 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 // 45 // 3. has the same signedness as the type of the first argument, if this is 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 76 #ifndef RTC_BASE_NUMERICS_SAFE_MINMAX_H_ 77 #define RTC_BASE_NUMERICS_SAFE_MINMAX_H_ 78 79 #include <limits> 80 #include <type_traits> 81 82 #include "rtc_base/checks.h" 83 #include "rtc_base/numerics/safe_compare.h" 84 #include "rtc_base/type_traits.h" 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 334 335 #endif // RTC_BASE_NUMERICS_SAFE_MINMAX_H_ 336