DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (3391eef42443)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Math operations that implement wraparound semantics on overflow or underflow.
 *
 * While in some cases (but not all of them!) plain old C++ operators and casts
 * will behave just like these functions, there are three reasons you should use
 * these functions:
 *
 *   1) These functions make *explicit* the desire for and dependence upon
 *      wraparound semantics, just as Rust's i32::wrapping_add and similar
 *      functions explicitly produce wraparound in Rust.
 *   2) They implement this functionality *safely*, without invoking signed
 *      integer overflow that has undefined behavior in C++.
 *   3) They play nice with compiler-based integer-overflow sanitizers (see
 *      build/autoconf/sanitize.m4), that in appropriately configured builds
 *      verify at runtime that integral arithmetic doesn't overflow.
 */

#ifndef mozilla_WrappingOperations_h
#define mozilla_WrappingOperations_h

#include "mozilla/Attributes.h"
#include "mozilla/TypeTraits.h"

#include <limits.h>

namespace mozilla {

namespace detail {

template <typename UnsignedType>
struct WrapToSignedHelper {
  static_assert(mozilla::IsUnsigned<UnsignedType>::value,
                "WrapToSigned must be passed an unsigned type");

  using SignedType = typename mozilla::MakeSigned<UnsignedType>::Type;

  static constexpr SignedType MaxValue =
      (UnsignedType(1) << (CHAR_BIT * sizeof(SignedType) - 1)) - 1;
  static constexpr SignedType MinValue = -MaxValue - 1;

  static constexpr UnsignedType MinValueUnsigned =
      static_cast<UnsignedType>(MinValue);
  static constexpr UnsignedType MaxValueUnsigned =
      static_cast<UnsignedType>(MaxValue);

  // Overflow-correctness was proven in bug 1432646 and is explained in the
  // comment below.  This function is very hot, both at compile time and
  // runtime, so disable all overflow checking in it.
  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  MOZ_NO_SANITIZE_SIGNED_OVERFLOW static constexpr SignedType compute(
      UnsignedType aValue) {
    // This algorithm was originally provided here:
    // https://stackoverflow.com/questions/13150449/efficient-unsigned-to-signed-cast-avoiding-implementation-defined-behavior
    //
    // If the value is in the non-negative signed range, just cast.
    //
    // If the value will be negative, compute its delta from the first number
    // past the max signed integer, then add that to the minimum signed value.
    //
    // At the low end: if |u| is the maximum signed value plus one, then it has
    // the same mathematical value as |MinValue| cast to unsigned form.  The
    // delta is zero, so the signed form of |u| is |MinValue| -- exactly the
    // result of adding zero delta to |MinValue|.
    //
    // At the high end: if |u| is the maximum *unsigned* value, then it has all
    // bits set.  |MinValue| cast to unsigned form is purely the high bit set.
    // So the delta is all bits but high set -- exactly |MaxValue|.  And as
    // |MinValue = -MaxValue - 1|, we have |MaxValue + (-MaxValue - 1)| to
    // equal -1.
    //
    // Thus the delta below is in signed range, the corresponding cast is safe,
    // and this computation produces values spanning [MinValue, 0): exactly the
    // desired range of all negative signed integers.
    return (aValue <= MaxValueUnsigned)
               ? static_cast<SignedType>(aValue)
               : static_cast<SignedType>(aValue - MinValueUnsigned) + MinValue;
  }
};

}  // namespace detail

/**
 * Convert an unsigned value to signed, if necessary wrapping around.
 *
 * This is the behavior normal C++ casting will perform in most implementations
 * these days -- but this function makes explicit that such conversion is
 * happening.
 */
template <typename UnsignedType>
constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
WrapToSigned(UnsignedType aValue) {
  return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
}

namespace detail {

template <typename T>
constexpr T ToResult(typename MakeUnsigned<T>::Type aUnsigned) {
  // We could *always* return WrapToSigned and rely on unsigned conversion to
  // undo the wrapping when |T| is unsigned, but this seems clearer.
  return IsSigned<T>::value ? WrapToSigned(aUnsigned) : aUnsigned;
}

template <typename T>
struct WrappingAddHelper {
 private:
  using UnsignedT = typename MakeUnsigned<T>::Type;

 public:
  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  static constexpr T compute(T aX, T aY) {
    return ToResult<T>(static_cast<UnsignedT>(aX) + static_cast<UnsignedT>(aY));
  }
};

}  // namespace detail

/**
 * Add two integers of the same type and return the result converted to that
 * type using wraparound semantics, without triggering overflow sanitizers.
 *
 * For N-bit unsigned integer types, this is equivalent to adding the two
 * numbers, then taking the result mod 2**N:
 *
 *   WrappingAdd(uint32_t(42), uint32_t(17)) is 59 (59 mod 2**32);
 *   WrappingAdd(uint8_t(240), uint8_t(20)) is 4 (260 mod 2**8).
 *
 * Unsigned WrappingAdd acts exactly like C++ unsigned addition.
 *
 * For N-bit signed integer types, this is equivalent to adding the two numbers
 * wrapped to unsigned, then wrapping the sum mod 2**N to the signed range:
 *
 *   WrappingAdd(int16_t(32767), int16_t(3)) is
 *     -32766 ((32770 mod 2**16) - 2**16);
 *   WrappingAdd(int8_t(-128), int8_t(-128)) is
 *     0 (256 mod 2**8);
 *   WrappingAdd(int32_t(-42), int32_t(-17)) is
 *     -59 ((8589934533 mod 2**32) - 2**32).
 *
 * There's no equivalent to this operation in C++, as C++ signed addition that
 * overflows has undefined behavior.  But it's how such addition *tends* to
 * behave with most compilers, unless an optimization or similar -- quite
 * permissibly -- triggers different behavior.
 */
template <typename T>
constexpr T WrappingAdd(T aX, T aY) {
  return detail::WrappingAddHelper<T>::compute(aX, aY);
}

namespace detail {

template <typename T>
struct WrappingSubtractHelper {
 private:
  using UnsignedT = typename MakeUnsigned<T>::Type;

 public:
  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  static constexpr T compute(T aX, T aY) {
    return ToResult<T>(static_cast<UnsignedT>(aX) - static_cast<UnsignedT>(aY));
  }
};

}  // namespace detail

/**
 * Subtract two integers of the same type and return the result converted to
 * that type using wraparound semantics, without triggering overflow sanitizers.
 *
 * For N-bit unsigned integer types, this is equivalent to subtracting the two
 * numbers, then taking the result mod 2**N:
 *
 *   WrappingSubtract(uint32_t(42), uint32_t(17)) is 29 (29 mod 2**32);
 *   WrappingSubtract(uint8_t(5), uint8_t(20)) is 241 (-15 mod 2**8).
 *
 * Unsigned WrappingSubtract acts exactly like C++ unsigned subtraction.
 *
 * For N-bit signed integer types, this is equivalent to subtracting the two
 * numbers wrapped to unsigned, then wrapping the difference mod 2**N to the
 * signed range:
 *
 *   WrappingSubtract(int16_t(32767), int16_t(-5)) is -32764 ((32772 mod 2**16)
 * - 2**16); WrappingSubtract(int8_t(-128), int8_t(127)) is 1 (-255 mod 2**8);
 *   WrappingSubtract(int32_t(-17), int32_t(-42)) is 25 (25 mod 2**32).
 *
 * There's no equivalent to this operation in C++, as C++ signed subtraction
 * that overflows has undefined behavior.  But it's how such subtraction *tends*
 * to behave with most compilers, unless an optimization or similar -- quite
 * permissibly -- triggers different behavior.
 */
template <typename T>
constexpr T WrappingSubtract(T aX, T aY) {
  return detail::WrappingSubtractHelper<T>::compute(aX, aY);
}

namespace detail {

template <typename T>
struct WrappingMultiplyHelper {
 private:
  using UnsignedT = typename MakeUnsigned<T>::Type;

 public:
  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  static constexpr T compute(T aX, T aY) {
    // Begin with |1U| to ensure the overall operation chain is never promoted
    // to signed integer operations that might have *signed* integer overflow.
    return ToResult<T>(static_cast<UnsignedT>(1U * static_cast<UnsignedT>(aX) *
                                              static_cast<UnsignedT>(aY)));
  }
};

}  // namespace detail

/**
 * Multiply two integers of the same type and return the result converted to
 * that type using wraparound semantics, without triggering overflow sanitizers.
 *
 * For N-bit unsigned integer types, this is equivalent to multiplying the two
 * numbers, then taking the result mod 2**N:
 *
 *   WrappingMultiply(uint32_t(42), uint32_t(17)) is 714 (714 mod 2**32);
 *   WrappingMultiply(uint8_t(16), uint8_t(24)) is 128 (384 mod 2**8);
 *   WrappingMultiply(uint16_t(3), uint16_t(32768)) is 32768 (98304 mod 2*16).
 *
 * Unsigned WrappingMultiply is *not* identical to C++ multiplication: with most
 * compilers, in rare cases uint16_t*uint16_t can invoke *signed* integer
 * overflow having undefined behavior!  http://kqueue.org/blog/2013/09/17/cltq/
 * has the grody details.  (Some compilers do this for uint32_t, not uint16_t.)
 * So it's especially important to use WrappingMultiply for wraparound math with
 * uint16_t.  That quirk aside, this function acts like you *thought* C++
 * unsigned multiplication always worked.
 *
 * For N-bit signed integer types, this is equivalent to multiplying the two
 * numbers wrapped to unsigned, then wrapping the product mod 2**N to the signed
 * range:
 *
 *   WrappingMultiply(int16_t(-456), int16_t(123)) is
 *     9448 ((-56088 mod 2**16) + 2**16);
 *   WrappingMultiply(int32_t(-7), int32_t(-9)) is 63 (63 mod 2**32);
 *   WrappingMultiply(int8_t(16), int8_t(24)) is -128 ((384 mod 2**8) - 2**8);
 *   WrappingMultiply(int8_t(16), int8_t(255)) is -16 ((4080 mod 2**8) - 2**8).
 *
 * There's no equivalent to this operation in C++, as C++ signed
 * multiplication that overflows has undefined behavior.  But it's how such
 * multiplication *tends* to behave with most compilers, unless an optimization
 * or similar -- quite permissibly -- triggers different behavior.
 */
template <typename T>
constexpr T WrappingMultiply(T aX, T aY) {
  return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
}

// The |mozilla::Wrapping*| functions are constexpr. Unfortunately, MSVC warns
// about well-defined unsigned integer overflows that may occur within the
// constexpr math.
//
//   https://msdn.microsoft.com/en-us/library/4kze989h.aspx (C4307)
//   https://developercommunity.visualstudio.com/content/problem/211134/unsigned-integer-overflows-in-constexpr-functionsa.html
//   (bug report)
//
// So we need a way to suppress these warnings. Unfortunately, the warnings are
// issued at the very top of the `constexpr` chain, which is often some
// distance from the triggering Wrapping*() operation. So we can't suppress
// them within this file. Instead, callers have to do it with these macros.
//
// If/when MSVC fix this bug, we should remove these macros.
#ifdef _MSC_VER
#  define MOZ_PUSH_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING \
    __pragma(warning(push)) __pragma(warning(disable : 4307))
#  define MOZ_POP_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING \
    __pragma(warning(pop))
#else
#  define MOZ_PUSH_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING
#  define MOZ_POP_DISABLE_INTEGRAL_CONSTANT_OVERFLOW_WARNING
#endif

} /* namespace mozilla */

#endif /* mozilla_WrappingOperations_h */