mfbt/WrappingOperations.h

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