summaryrefslogtreecommitdiff
path: root/third_party/numerics/safe_math_impl.h
blob: 4bf59e64e07c6ce6edde7deee2e2014bc623749c (plain)
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
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef SAFE_MATH_IMPL_H_
#define SAFE_MATH_IMPL_H_

#include <stdint.h>

#include <cmath>
#include <cstdlib>
#include <limits>

#include "../macros.h"
#include "../template_util.h"
#include "safe_conversions.h"

namespace base {
namespace internal {

// Everything from here up to the floating point operations is portable C++,
// but it may not be fast. This code could be split based on
// platform/architecture and replaced with potentially faster implementations.

// Integer promotion templates used by the portable checked integer arithmetic.
template <size_t Size, bool IsSigned>
struct IntegerForSizeAndSign;
template <>
struct IntegerForSizeAndSign<1, true> {
  typedef int8_t type;
};
template <>
struct IntegerForSizeAndSign<1, false> {
  typedef uint8_t type;
};
template <>
struct IntegerForSizeAndSign<2, true> {
  typedef int16_t type;
};
template <>
struct IntegerForSizeAndSign<2, false> {
  typedef uint16_t type;
};
template <>
struct IntegerForSizeAndSign<4, true> {
  typedef int32_t type;
};
template <>
struct IntegerForSizeAndSign<4, false> {
  typedef uint32_t type;
};
template <>
struct IntegerForSizeAndSign<8, true> {
  typedef int64_t type;
};
template <>
struct IntegerForSizeAndSign<8, false> {
  typedef uint64_t type;
};

// WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
// support 128-bit math, then the ArithmeticPromotion template below will need
// to be updated (or more likely replaced with a decltype expression).

template <typename Integer>
struct UnsignedIntegerForSize {
  typedef typename enable_if<
      std::numeric_limits<Integer>::is_integer,
      typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
};

template <typename Integer>
struct SignedIntegerForSize {
  typedef typename enable_if<
      std::numeric_limits<Integer>::is_integer,
      typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
};

template <typename Integer>
struct TwiceWiderInteger {
  typedef typename enable_if<
      std::numeric_limits<Integer>::is_integer,
      typename IntegerForSizeAndSign<
          sizeof(Integer) * 2,
          std::numeric_limits<Integer>::is_signed>::type>::type type;
};

template <typename Integer>
struct PositionOfSignBit {
  static const typename enable_if<std::numeric_limits<Integer>::is_integer,
                                  size_t>::type value = 8 * sizeof(Integer) - 1;
};

// Helper templates for integer manipulations.

template <typename T>
bool HasSignBit(T x) {
  // Cast to unsigned since right shift on signed is undefined.
  return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >>
            PositionOfSignBit<T>::value);
}

// This wrapper undoes the standard integer promotions.
template <typename T>
T BinaryComplement(T x) {
  return ~x;
}

// Here are the actual portable checked integer math implementations.
// TODO(jschuh): Break this code out from the enable_if pattern and find a clean
// way to coalesce things into the CheckedNumericState specializations below.

template <typename T>
typename enable_if<std::numeric_limits<T>::is_integer, T>::type
CheckedAdd(T x, T y, RangeConstraint* validity) {
  // Since the value of x+y is undefined if we have a signed type, we compute
  // it using the unsigned type of the same size.
  typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
  UnsignedDst ux = static_cast<UnsignedDst>(x);
  UnsignedDst uy = static_cast<UnsignedDst>(y);
  UnsignedDst uresult = ux + uy;
  // Addition is valid if the sign of (x + y) is equal to either that of x or
  // that of y.
  if (std::numeric_limits<T>::is_signed) {
    if (HasSignBit(BinaryComplement((uresult ^ ux) & (uresult ^ uy))))
      *validity = RANGE_VALID;
    else  // Direction of wrap is inverse of result sign.
      *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;

  } else {  // Unsigned is either valid or overflow.
    *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
  }
  return static_cast<T>(uresult);
}

template <typename T>
typename enable_if<std::numeric_limits<T>::is_integer, T>::type
CheckedSub(T x, T y, RangeConstraint* validity) {
  // Since the value of x+y is undefined if we have a signed type, we compute
  // it using the unsigned type of the same size.
  typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
  UnsignedDst ux = static_cast<UnsignedDst>(x);
  UnsignedDst uy = static_cast<UnsignedDst>(y);
  UnsignedDst uresult = ux - uy;
  // Subtraction is valid if either x and y have same sign, or (x-y) and x have
  // the same sign.
  if (std::numeric_limits<T>::is_signed) {
    if (HasSignBit(BinaryComplement((uresult ^ ux) & (ux ^ uy))))
      *validity = RANGE_VALID;
    else  // Direction of wrap is inverse of result sign.
      *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;

  } else {  // Unsigned is either valid or underflow.
    *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
  }
  return static_cast<T>(uresult);
}

// Integer multiplication is a bit complicated. In the fast case we just
// we just promote to a twice wider type, and range check the result. In the
// slow case we need to manually check that the result won't be truncated by
// checking with division against the appropriate bound.
template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
    T>::type
CheckedMul(T x, T y, RangeConstraint* validity) {
  typedef typename TwiceWiderInteger<T>::type IntermediateType;
  IntermediateType tmp =
      static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
  *validity = DstRangeRelationToSrcRange<T>(tmp);
  return static_cast<T>(tmp);
}

template <typename T>
typename enable_if<std::numeric_limits<T>::is_integer&& std::numeric_limits<
                       T>::is_signed&&(sizeof(T) * 2 > sizeof(uintmax_t)),
                   T>::type
CheckedMul(T x, T y, RangeConstraint* validity) {
  // if either side is zero then the result will be zero.
  if (!(x || y)) {
    return RANGE_VALID;

  } else if (x > 0) {
    if (y > 0)
      *validity =
          x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
    else
      *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
                                                         : RANGE_UNDERFLOW;

  } else {
    if (y > 0)
      *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
                                                         : RANGE_UNDERFLOW;
    else
      *validity =
          y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
  }

  return x * y;
}

template <typename T>
typename enable_if<std::numeric_limits<T>::is_integer &&
                       !std::numeric_limits<T>::is_signed &&
                       (sizeof(T) * 2 > sizeof(uintmax_t)),
                   T>::type
CheckedMul(T x, T y, RangeConstraint* validity) {
  *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
                  ? RANGE_VALID
                  : RANGE_OVERFLOW;
  return x * y;
}

// Division just requires a check for an invalid negation on signed min/-1.
template <typename T>
T CheckedDiv(
    T x,
    T y,
    RangeConstraint* validity,
    typename enable_if<std::numeric_limits<T>::is_integer, int>::type = 0) {
  if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() &&
      y == static_cast<T>(-1)) {
    *validity = RANGE_OVERFLOW;
    return std::numeric_limits<T>::min();
  }

  *validity = RANGE_VALID;
  return x / y;
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
    T>::type
CheckedMod(T x, T y, RangeConstraint* validity) {
  *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
  return x % y;
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
    T>::type
CheckedMod(T x, T y, RangeConstraint* validity) {
  *validity = RANGE_VALID;
  return x % y;
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
    T>::type
CheckedNeg(T value, RangeConstraint* validity) {
  *validity =
      value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
  // The negation of signed min is min, so catch that one.
  return -value;
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
    T>::type
CheckedNeg(T value, RangeConstraint* validity) {
  // The only legal unsigned negation is zero.
  *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
  return static_cast<T>(
      -static_cast<typename SignedIntegerForSize<T>::type>(value));
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer&& std::numeric_limits<T>::is_signed,
    T>::type
CheckedAbs(T value, RangeConstraint* validity) {
  *validity =
      value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
  return std::abs(value);
}

template <typename T>
typename enable_if<
    std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
    T>::type
CheckedAbs(T value, RangeConstraint* validity) {
  // Absolute value of a positive is just its identiy.
  *validity = RANGE_VALID;
  return value;
}

// These are the floating point stubs that the compiler needs to see. Only the
// negation operation is ever called.
#define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                        \
  template <typename T>                                          \
  typename enable_if<std::numeric_limits<T>::is_iec559, T>::type \
  Checked##NAME(T, T, RangeConstraint*) {                        \
    NOTREACHED();                                                \
    return 0;                                                    \
  }

BASE_FLOAT_ARITHMETIC_STUBS(Add)
BASE_FLOAT_ARITHMETIC_STUBS(Sub)
BASE_FLOAT_ARITHMETIC_STUBS(Mul)
BASE_FLOAT_ARITHMETIC_STUBS(Div)
BASE_FLOAT_ARITHMETIC_STUBS(Mod)

#undef BASE_FLOAT_ARITHMETIC_STUBS

template <typename T>
typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
    T value,
    RangeConstraint*) {
  return -value;
}

template <typename T>
typename enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
    T value,
    RangeConstraint*) {
  return std::abs(value);
}

// Floats carry around their validity state with them, but integers do not. So,
// we wrap the underlying value in a specialization in order to hide that detail
// and expose an interface via accessors.
enum NumericRepresentation {
  NUMERIC_INTEGER,
  NUMERIC_FLOATING,
  NUMERIC_UNKNOWN
};

template <typename NumericType>
struct GetNumericRepresentation {
  static const NumericRepresentation value =
      std::numeric_limits<NumericType>::is_integer
          ? NUMERIC_INTEGER
          : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
                                                         : NUMERIC_UNKNOWN);
};

template <typename T, NumericRepresentation type =
                          GetNumericRepresentation<T>::value>
class CheckedNumericState {};

// Integrals require quite a bit of additional housekeeping to manage state.
template <typename T>
class CheckedNumericState<T, NUMERIC_INTEGER> {
 private:
  T value_;
  RangeConstraint validity_;

 public:
  template <typename Src, NumericRepresentation type>
  friend class CheckedNumericState;

  CheckedNumericState() : value_(0), validity_(RANGE_VALID) {}

  template <typename Src>
  CheckedNumericState(Src value, RangeConstraint validity)
      : value_(value),
        validity_(GetRangeConstraint(validity |
                                     DstRangeRelationToSrcRange<T>(value))) {
    COMPILE_ASSERT(std::numeric_limits<Src>::is_specialized,
                   argument_must_be_numeric);
  }

  // Copy constructor.
  template <typename Src>
  CheckedNumericState(const CheckedNumericState<Src>& rhs)
      : value_(static_cast<T>(rhs.value())),
        validity_(GetRangeConstraint(
            rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value()))) {}

  template <typename Src>
  explicit CheckedNumericState(
      Src value,
      typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
          0)
      : value_(static_cast<T>(value)),
        validity_(DstRangeRelationToSrcRange<T>(value)) {}

  RangeConstraint validity() const { return validity_; }
  T value() const { return value_; }
};

// Floating points maintain their own validity, but need translation wrappers.
template <typename T>
class CheckedNumericState<T, NUMERIC_FLOATING> {
 private:
  T value_;

 public:
  template <typename Src, NumericRepresentation type>
  friend class CheckedNumericState;

  CheckedNumericState() : value_(0.0) {}

  template <typename Src>
  CheckedNumericState(
      Src value,
      RangeConstraint validity,
      typename enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0) {
    switch (DstRangeRelationToSrcRange<T>(value)) {
      case RANGE_VALID:
        value_ = static_cast<T>(value);
        break;

      case RANGE_UNDERFLOW:
        value_ = -std::numeric_limits<T>::infinity();
        break;

      case RANGE_OVERFLOW:
        value_ = std::numeric_limits<T>::infinity();
        break;

      case RANGE_INVALID:
        value_ = std::numeric_limits<T>::quiet_NaN();
        break;

      default:
        NOTREACHED();
    }
  }

  template <typename Src>
  explicit CheckedNumericState(
      Src value,
      typename enable_if<std::numeric_limits<Src>::is_specialized, int>::type =
          0)
      : value_(static_cast<T>(value)) {}

  // Copy constructor.
  template <typename Src>
  CheckedNumericState(const CheckedNumericState<Src>& rhs)
      : value_(static_cast<T>(rhs.value())) {}

  RangeConstraint validity() const {
    return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
                              value_ >= -std::numeric_limits<T>::max());
  }
  T value() const { return value_; }
};

// For integers less than 128-bit and floats 32-bit or larger, we can distil
// C/C++ arithmetic promotions down to two simple rules:
// 1. The type with the larger maximum exponent always takes precedence.
// 2. The resulting type must be promoted to at least an int.
// The following template specializations implement that promotion logic.
enum ArithmeticPromotionCategory {
  LEFT_PROMOTION,
  RIGHT_PROMOTION,
  DEFAULT_PROMOTION
};

template <typename Lhs,
          typename Rhs = Lhs,
          ArithmeticPromotionCategory Promotion =
              (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
                  ? (MaxExponent<Lhs>::value > MaxExponent<int>::value
                         ? LEFT_PROMOTION
                         : DEFAULT_PROMOTION)
                  : (MaxExponent<Rhs>::value > MaxExponent<int>::value
                         ? RIGHT_PROMOTION
                         : DEFAULT_PROMOTION) >
struct ArithmeticPromotion;

template <typename Lhs, typename Rhs>
struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
  typedef Lhs type;
};

template <typename Lhs, typename Rhs>
struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
  typedef Rhs type;
};

template <typename Lhs, typename Rhs>
struct ArithmeticPromotion<Lhs, Rhs, DEFAULT_PROMOTION> {
  typedef int type;
};

// We can statically check if operations on the provided types can wrap, so we
// can skip the checked operations if they're not needed. So, for an integer we
// care if the destination type preserves the sign and is twice the width of
// the source.
template <typename T, typename Lhs, typename Rhs>
struct IsIntegerArithmeticSafe {
  static const bool value = !std::numeric_limits<T>::is_iec559 &&
                            StaticDstRangeRelationToSrcRange<T, Lhs>::value ==
                                NUMERIC_RANGE_CONTAINED &&
                            sizeof(T) >= (2 * sizeof(Lhs)) &&
                            StaticDstRangeRelationToSrcRange<T, Rhs>::value !=
                                NUMERIC_RANGE_CONTAINED &&
                            sizeof(T) >= (2 * sizeof(Rhs));
};

}  // namespace internal
}  // namespace base

#endif  // SAFE_MATH_IMPL_H_