no bug - Bumping Firefox l10n changesets r=release a=l10n-bump DONTBUILD CLOSED TREE
[gecko.git] / mfbt / WrappingOperations.h
blobbd67ac34f18897dc47d1861b70f95020720adaa1
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/. */
7 /*
8 * Math operations that implement wraparound semantics on overflow or underflow.
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:
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.
24 #ifndef mozilla_WrappingOperations_h
25 #define mozilla_WrappingOperations_h
27 #include "mozilla/Attributes.h"
29 #include <limits.h>
30 #include <type_traits>
32 namespace mozilla {
34 namespace detail {
36 template <typename UnsignedType>
37 struct WrapToSignedHelper {
38 static_assert(std::is_unsigned_v<UnsignedType>,
39 "WrapToSigned must be passed an unsigned type");
41 using SignedType = std::make_signed_t<UnsignedType>;
43 static constexpr SignedType MaxValue =
44 (UnsignedType(1) << (CHAR_BIT * sizeof(SignedType) - 1)) - 1;
45 static constexpr SignedType MinValue = -MaxValue - 1;
47 static constexpr UnsignedType MinValueUnsigned =
48 static_cast<UnsignedType>(MinValue);
49 static constexpr UnsignedType MaxValueUnsigned =
50 static_cast<UnsignedType>(MaxValue);
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
61 // If the value is in the non-negative signed range, just cast.
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.
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|.
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.
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;
86 } // namespace detail
88 /**
89 * Convert an unsigned value to signed, if necessary wrapping around.
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.
95 template <typename UnsignedType>
96 constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
97 WrapToSigned(UnsignedType aValue) {
98 return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
101 namespace detail {
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;
110 template <typename T>
111 struct WrappingAddHelper {
112 private:
113 using UnsignedT = std::make_unsigned_t<T>;
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));
122 } // namespace detail
125 * Add two integers of the same type and return the result converted to that
126 * type using wraparound semantics, without triggering overflow sanitizers.
128 * For N-bit unsigned integer types, this is equivalent to adding the two
129 * numbers, then taking the result mod 2**N:
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).
134 * Unsigned WrappingAdd acts exactly like C++ unsigned addition.
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:
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).
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.
151 template <typename T>
152 constexpr T WrappingAdd(T aX, T aY) {
153 return detail::WrappingAddHelper<T>::compute(aX, aY);
156 namespace detail {
158 template <typename T>
159 struct WrappingSubtractHelper {
160 private:
161 using UnsignedT = std::make_unsigned_t<T>;
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));
170 } // namespace detail
173 * Subtract two integers of the same type and return the result converted to
174 * that type using wraparound semantics, without triggering overflow sanitizers.
176 * For N-bit unsigned integer types, this is equivalent to subtracting the two
177 * numbers, then taking the result mod 2**N:
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).
182 * Unsigned WrappingSubtract acts exactly like C++ unsigned subtraction.
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:
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).
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.
197 template <typename T>
198 constexpr T WrappingSubtract(T aX, T aY) {
199 return detail::WrappingSubtractHelper<T>::compute(aX, aY);
202 namespace detail {
204 template <typename T>
205 struct WrappingMultiplyHelper {
206 private:
207 using UnsignedT = std::make_unsigned_t<T>;
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)));
219 } // namespace detail
222 * Multiply two integers of the same type and return the result converted to
223 * that type using wraparound semantics, without triggering overflow sanitizers.
225 * For N-bit unsigned integer types, this is equivalent to multiplying the two
226 * numbers, then taking the result mod 2**N:
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).
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.
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:
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).
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.
255 template <typename T>
256 constexpr T WrappingMultiply(T aX, T aY) {
257 return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
260 } /* namespace mozilla */
262 #endif /* mozilla_WrappingOperations_h */