WrappingOperations.h (10407B)
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 3 /* This Source Code Form is subject to the terms of the Mozilla Public 4 * License, v. 2.0. If a copy of the MPL was not distributed with this 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 6 7 /* 8 * Math operations that implement wraparound semantics on overflow or underflow. 9 * 10 * While in some cases (but not all of them!) plain old C++ operators and casts 11 * will behave just like these functions, there are three reasons you should use 12 * these functions: 13 * 14 * 1) These functions make *explicit* the desire for and dependence upon 15 * wraparound semantics, just as Rust's i32::wrapping_add and similar 16 * functions explicitly produce wraparound in Rust. 17 * 2) They implement this functionality *safely*, without invoking signed 18 * integer overflow that has undefined behavior in C++. 19 * 3) They play nice with compiler-based integer-overflow sanitizers (see 20 * build/moz.configure/toolchain.configure), that in appropriately 21 * configured builds verify at runtime that integral arithmetic doesn't 22 * overflow. 23 */ 24 25 #ifndef mozilla_WrappingOperations_h 26 #define mozilla_WrappingOperations_h 27 28 #include "mozilla/Attributes.h" 29 30 #include <limits.h> 31 #include <type_traits> 32 33 namespace mozilla { 34 35 namespace detail { 36 37 template <typename UnsignedType> 38 struct WrapToSignedHelper { 39 static_assert(std::is_unsigned_v<UnsignedType>, 40 "WrapToSigned must be passed an unsigned type"); 41 42 using SignedType = std::make_signed_t<UnsignedType>; 43 44 static constexpr SignedType MaxValue = 45 (UnsignedType(1) << (CHAR_BIT * sizeof(SignedType) - 1)) - 1; 46 static constexpr SignedType MinValue = -MaxValue - 1; 47 48 static constexpr UnsignedType MinValueUnsigned = 49 static_cast<UnsignedType>(MinValue); 50 static constexpr UnsignedType MaxValueUnsigned = 51 static_cast<UnsignedType>(MaxValue); 52 53 // Overflow-correctness was proven in bug 1432646 and is explained in the 54 // comment below. This function is very hot, both at compile time and 55 // runtime, so disable all overflow checking in it. 56 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW 57 MOZ_NO_SANITIZE_SIGNED_OVERFLOW static constexpr SignedType compute( 58 UnsignedType aValue) { 59 // This algorithm was originally provided here: 60 // https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior 61 // 62 // If the value is in the non-negative signed range, just cast. 63 // 64 // If the value will be negative, compute its delta from the first number 65 // past the max signed integer, then add that to the minimum signed value. 66 // 67 // At the low end: if |u| is the maximum signed value plus one, then it has 68 // the same mathematical value as |MinValue| cast to unsigned form. The 69 // delta is zero, so the signed form of |u| is |MinValue| -- exactly the 70 // result of adding zero delta to |MinValue|. 71 // 72 // At the high end: if |u| is the maximum *unsigned* value, then it has all 73 // bits set. |MinValue| cast to unsigned form is purely the high bit set. 74 // So the delta is all bits but high set -- exactly |MaxValue|. And as 75 // |MinValue = -MaxValue - 1|, we have |MaxValue + (-MaxValue - 1)| to 76 // equal -1. 77 // 78 // Thus the delta below is in signed range, the corresponding cast is safe, 79 // and this computation produces values spanning [MinValue, 0): exactly the 80 // desired range of all negative signed integers. 81 return (aValue <= MaxValueUnsigned) 82 ? static_cast<SignedType>(aValue) 83 : static_cast<SignedType>(aValue - MinValueUnsigned) + MinValue; 84 } 85 }; 86 87 } // namespace detail 88 89 /** 90 * Convert an unsigned value to signed, if necessary wrapping around. 91 * 92 * This is the behavior normal C++ casting will perform in most implementations 93 * these days -- but this function makes explicit that such conversion is 94 * happening. 95 */ 96 template <typename UnsignedType> 97 constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType 98 WrapToSigned(UnsignedType aValue) { 99 return detail::WrapToSignedHelper<UnsignedType>::compute(aValue); 100 } 101 102 namespace detail { 103 104 template <typename T> 105 constexpr T ToResult(std::make_unsigned_t<T> aUnsigned) { 106 // We could *always* return WrapToSigned and rely on unsigned conversion to 107 // undo the wrapping when |T| is unsigned, but this seems clearer. 108 return std::is_signed_v<T> ? WrapToSigned(aUnsigned) : aUnsigned; 109 } 110 111 template <typename T> 112 struct WrappingAddHelper { 113 private: 114 using UnsignedT = std::make_unsigned_t<T>; 115 116 public: 117 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW 118 static constexpr T compute(T aX, T aY) { 119 return ToResult<T>(static_cast<UnsignedT>(aX) + static_cast<UnsignedT>(aY)); 120 } 121 }; 122 123 } // namespace detail 124 125 /** 126 * Add two integers of the same type and return the result converted to that 127 * type using wraparound semantics, without triggering overflow sanitizers. 128 * 129 * For N-bit unsigned integer types, this is equivalent to adding the two 130 * numbers, then taking the result mod 2**N: 131 * 132 * WrappingAdd(uint32_t(42), uint32_t(17)) is 59 (59 mod 2**32); 133 * WrappingAdd(uint8_t(240), uint8_t(20)) is 4 (260 mod 2**8). 134 * 135 * Unsigned WrappingAdd acts exactly like C++ unsigned addition. 136 * 137 * For N-bit signed integer types, this is equivalent to adding the two numbers 138 * wrapped to unsigned, then wrapping the sum mod 2**N to the signed range: 139 * 140 * WrappingAdd(int16_t(32767), int16_t(3)) is 141 * -32766 ((32770 mod 2**16) - 2**16); 142 * WrappingAdd(int8_t(-128), int8_t(-128)) is 143 * 0 (256 mod 2**8); 144 * WrappingAdd(int32_t(-42), int32_t(-17)) is 145 * -59 ((8589934533 mod 2**32) - 2**32). 146 * 147 * There's no equivalent to this operation in C++, as C++ signed addition that 148 * overflows has undefined behavior. But it's how such addition *tends* to 149 * behave with most compilers, unless an optimization or similar -- quite 150 * permissibly -- triggers different behavior. 151 */ 152 template <typename T> 153 constexpr T WrappingAdd(T aX, T aY) { 154 return detail::WrappingAddHelper<T>::compute(aX, aY); 155 } 156 157 namespace detail { 158 159 template <typename T> 160 struct WrappingSubtractHelper { 161 private: 162 using UnsignedT = std::make_unsigned_t<T>; 163 164 public: 165 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW 166 static constexpr T compute(T aX, T aY) { 167 return ToResult<T>(static_cast<UnsignedT>(aX) - static_cast<UnsignedT>(aY)); 168 } 169 }; 170 171 } // namespace detail 172 173 /** 174 * Subtract two integers of the same type and return the result converted to 175 * that type using wraparound semantics, without triggering overflow sanitizers. 176 * 177 * For N-bit unsigned integer types, this is equivalent to subtracting the two 178 * numbers, then taking the result mod 2**N: 179 * 180 * WrappingSubtract(uint32_t(42), uint32_t(17)) is 29 (29 mod 2**32); 181 * WrappingSubtract(uint8_t(5), uint8_t(20)) is 241 (-15 mod 2**8). 182 * 183 * Unsigned WrappingSubtract acts exactly like C++ unsigned subtraction. 184 * 185 * For N-bit signed integer types, this is equivalent to subtracting the two 186 * numbers wrapped to unsigned, then wrapping the difference mod 2**N to the 187 * signed range: 188 * 189 * WrappingSubtract(int16_t(32767), int16_t(-5)) is -32764 ((32772 mod 2**16) 190 * - 2**16); WrappingSubtract(int8_t(-128), int8_t(127)) is 1 (-255 mod 2**8); 191 * WrappingSubtract(int32_t(-17), int32_t(-42)) is 25 (25 mod 2**32). 192 * 193 * There's no equivalent to this operation in C++, as C++ signed subtraction 194 * that overflows has undefined behavior. But it's how such subtraction *tends* 195 * to behave with most compilers, unless an optimization or similar -- quite 196 * permissibly -- triggers different behavior. 197 */ 198 template <typename T> 199 constexpr T WrappingSubtract(T aX, T aY) { 200 return detail::WrappingSubtractHelper<T>::compute(aX, aY); 201 } 202 203 namespace detail { 204 205 template <typename T> 206 struct WrappingMultiplyHelper { 207 private: 208 using UnsignedT = std::make_unsigned_t<T>; 209 210 public: 211 MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW 212 static constexpr T compute(T aX, T aY) { 213 // Begin with |1U| to ensure the overall operation chain is never promoted 214 // to signed integer operations that might have *signed* integer overflow. 215 return ToResult<T>(static_cast<UnsignedT>(1U * static_cast<UnsignedT>(aX) * 216 static_cast<UnsignedT>(aY))); 217 } 218 }; 219 220 } // namespace detail 221 222 /** 223 * Multiply two integers of the same type and return the result converted to 224 * that type using wraparound semantics, without triggering overflow sanitizers. 225 * 226 * For N-bit unsigned integer types, this is equivalent to multiplying the two 227 * numbers, then taking the result mod 2**N: 228 * 229 * WrappingMultiply(uint32_t(42), uint32_t(17)) is 714 (714 mod 2**32); 230 * WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8); 231 * WrappingMultiply(uint16_t(3), uint16_t(32768)) is 32768 (98304 mod 2*16). 232 * 233 * Unsigned WrappingMultiply is *not* identical to C++ multiplication: with most 234 * compilers, in rare cases uint16_t*uint16_t can invoke *signed* integer 235 * overflow having undefined behavior! http://kqueue.org/blog/2013/09/17/cltq/ 236 * has the grody details. (Some compilers do this for uint32_t, not uint16_t.) 237 * So it's especially important to use WrappingMultiply for wraparound math with 238 * uint16_t. That quirk aside, this function acts like you *thought* C++ 239 * unsigned multiplication always worked. 240 * 241 * For N-bit signed integer types, this is equivalent to multiplying the two 242 * numbers wrapped to unsigned, then wrapping the product mod 2**N to the signed 243 * range: 244 * 245 * WrappingMultiply(int16_t(-456), int16_t(123)) is 246 * 9448 ((-56088 mod 2**16) + 2**16); 247 * WrappingMultiply(int32_t(-7), int32_t(-9)) is 63 (63 mod 2**32); 248 * WrappingMultiply(int8_t(16), int8_t(24)) is -128 ((384 mod 2**8) - 2**8); 249 * WrappingMultiply(int8_t(16), int8_t(255)) is -16 ((4080 mod 2**8) - 2**8). 250 * 251 * There's no equivalent to this operation in C++, as C++ signed 252 * multiplication that overflows has undefined behavior. But it's how such 253 * multiplication *tends* to behave with most compilers, unless an optimization 254 * or similar -- quite permissibly -- triggers different behavior. 255 */ 256 template <typename T> 257 constexpr T WrappingMultiply(T aX, T aY) { 258 return detail::WrappingMultiplyHelper<T>::compute(aX, aY); 259 } 260 261 } /* namespace mozilla */ 262 263 #endif /* mozilla_WrappingOperations_h */