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
computeWrapToSignedHelper56   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
WrapToSigned(UnsignedType aValue)97 WrapToSigned(UnsignedType aValue) {
98   return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
99 }
100 
101 namespace detail {
102 
103 template <typename T>
ToResult(std::make_unsigned_t<T> aUnsigned)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
computeWrappingAddHelper117   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>
WrappingAdd(T aX,T aY)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
computeWrappingSubtractHelper165   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>
WrappingSubtract(T aX,T aY)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
computeWrappingMultiplyHelper211   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>
WrappingMultiply(T aX,T aY)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 */
263