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
|
/* -*- 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
* without performing C++ undefined behavior or tripping up compiler-based
* integer-overflow sanitizers.
*/
#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>
inline constexpr typename detail::WrapToSignedHelper<UnsignedType>::SignedType
WrapToSigned(UnsignedType aValue)
{
return detail::WrapToSignedHelper<UnsignedType>::compute(aValue);
}
namespace detail {
template<typename T>
struct WrappingMultiplyHelper
{
private:
using UnsignedT = typename MakeUnsigned<T>::Type;
MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
static UnsignedT
multiply(UnsignedT aX, UnsignedT aY)
{
// |mozilla::WrappingMultiply| isn't constexpr because MSVC warns about well-
// defined unsigned integer overflows that may happen here.
// https://msdn.microsoft.com/en-us/library/4kze989h.aspx And constexpr
// seems to cause the warning to be emitted at |WrappingMultiply| call *sites*
// instead of here, so these #pragmas are ineffective.
//
// https://stackoverflow.com/questions/37658794/integer-constant-overflow-warning-in-constexpr
//
// If/when MSVC fix this bug, we should make these functions constexpr.
// Begin with |1U| to ensure the overall operation chain is never promoted
// to signed integer operations that might have *signed* integer overflow.
return static_cast<UnsignedT>(1U * aX * aY);
}
static T
toResult(UnsignedT aX, UnsignedT aY)
{
// We could always return WrapToSigned and rely on unsigned conversion
// undoing the wrapping when |T| is unsigned, but this seems clearer.
return IsSigned<T>::value
? WrapToSigned(multiply(aX, aY))
: multiply(aX, aY);
}
public:
MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
static T compute(T aX, T aY)
{
return toResult(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. This function:
*
* 1) makes explicit the desire for and dependence upon wraparound semantics,
* 2) provides wraparound semantics *safely* with no signed integer overflow
* that would have undefined behavior, and
* 3) won't trip up {,un}signed-integer overflow sanitizers (see
* build/autoconf/sanitize.m4) at runtime.
*
* 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).
*
* Use this function for any unsigned multiplication that can wrap (instead of
* normal C++ multiplication) to play nice with the sanitizers. But it's
* especially important to use it for uint16_t multiplication: in most compilers
* for uint16_t*uint16_t some operand values will trigger signed integer
* overflow with undefined behavior! http://kqueue.org/blog/2013/09/17/cltq/
* has the grody details. Other than that one weird case, WrappingMultiply on
* unsigned types is the same as C++ multiplication.
*
* For N-bit signed integer types, this is equivalent to multiplying the two
* numbers wrapped to unsigned, taking the product mod 2**N, then wrapping that
* number 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 is no ready equivalent to this operation in C++, as applying C++
* multiplication to signed integer types in ways that trigger overflow has
* undefined behavior. However, it's how multiplication *tends* to behave with
* most compilers in most situations, even though it's emphatically not required
* to do so.
*/
template<typename T>
inline T
WrappingMultiply(T aX, T aY)
{
return detail::WrappingMultiplyHelper<T>::compute(aX, aY);
}
} /* namespace mozilla */
#endif /* mozilla_WrappingOperations_h */
|
