summaryrefslogtreecommitdiff
path: root/third_party/base/numerics/safe_math.h
blob: a0c41a467b904fb742bfc7f0fe0a098112a3378f (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
503
504
505
506
507
508
509
510
// 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 PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_
#define PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_

#include <stddef.h>

#include <limits>
#include <type_traits>

#include "third_party/base/numerics/safe_math_impl.h"

namespace pdfium {
namespace base {
namespace internal {

// CheckedNumeric<> implements all the logic and operators for detecting integer
// boundary conditions such as overflow, underflow, and invalid conversions.
// The CheckedNumeric type implicitly converts from floating point and integer
// data types, and contains overloads for basic arithmetic operations (i.e.: +,
// -, *, / for all types and %, <<, >>, &, |, ^ for integers). Type promotions
// are a slightly modified version of the standard C arithmetic rules with the
// two differences being that there is no default promotion to int and bitwise
// logical operations always return an unsigned of the wider type.
//
// You may also use one of the variadic convenience functions, which accept
// standard arithmetic or CheckedNumeric types, perform arithmetic operations,
// and return a CheckedNumeric result. The supported functions are:
//  CheckAdd() - Addition.
//  CheckSub() - Subtraction.
//  CheckMul() - Multiplication.
//  CheckDiv() - Division.
//  CheckMod() - Modulous (integer only).
//  CheckLsh() - Left integer shift (integer only).
//  CheckRsh() - Right integer shift (integer only).
//  CheckAnd() - Bitwise AND (integer only with unsigned result).
//  CheckOr()  - Bitwise OR (integer only with unsigned result).
//  CheckXor() - Bitwise XOR (integer only with unsigned result).
//  CheckMax() - Maximum of supplied arguments.
//  CheckMin() - Minimum of supplied arguments.
//
// The unary negation, increment, and decrement operators are supported, along
// with the following unary arithmetic methods, which return a new
// CheckedNumeric as a result of the operation:
//  Abs() - Absolute value.
//  UnsignedAbs() - Absolute value as an equal-width unsigned underlying type
//          (valid for only integral types).
//  Max() - Returns whichever is greater of the current instance or argument.
//          The underlying return type is whichever has the greatest magnitude.
//  Min() - Returns whichever is lowest of the current instance or argument.
//          The underlying return type is whichever has can represent the lowest
//          number in the smallest width (e.g. int8_t over unsigned, int over
//          int8_t, and float over int).
//
// The following methods convert from CheckedNumeric to standard numeric values:
//  AssignIfValid() - Assigns the underlying value to the supplied destination
//          pointer if the value is currently valid and within the range
//          supported by the destination type. Returns true on success.
//  ****************************************************************************
//  *  WARNING: All of the following functions return a StrictNumeric, which   *
//  *  is valid for comparison and assignment operations, but will trigger a   *
//  *  compile failure on attempts to assign to a type of insufficient range.  *
//  ****************************************************************************
//  IsValid() - Returns true if the underlying numeric value is valid (i.e. has
//          has not wrapped and is not the result of an invalid conversion).
//  ValueOrDie() - Returns the underlying value. If the state is not valid this
//          call will crash on a CHECK.
//  ValueOrDefault() - Returns the current value, or the supplied default if the
//          state is not valid (will not trigger a CHECK).
//
// The following wrapper functions can be used to avoid the template
// disambiguator syntax when converting a destination type.
//   IsValidForType<>() in place of: a.template IsValid<Dst>()
//   ValueOrDieForType<>() in place of: a.template ValueOrDie()
//   ValueOrDefaultForType<>() in place of: a.template ValueOrDefault(default)
//
// The following are general utility methods that are useful for converting
// between arithmetic types and CheckedNumeric types:
//  CheckedNumeric::Cast<Dst>() - Instance method returning a CheckedNumeric
//          derived from casting the current instance to a CheckedNumeric of
//          the supplied destination type.
//  MakeCheckedNum() - Creates a new CheckedNumeric from the underlying type of
//          the supplied arithmetic, CheckedNumeric, or StrictNumeric type.
//
// Comparison operations are explicitly not supported because they could result
// in a crash on an unexpected CHECK condition. You should use patterns like the
// following for comparisons:
//   CheckedNumeric<size_t> checked_size = untrusted_input_value;
//   checked_size += HEADER LENGTH;
//   if (checked_size.IsValid() && checked_size.ValueOrDie() < buffer_size)
//     Do stuff...

template <typename T>
class CheckedNumeric {
  static_assert(std::is_arithmetic<T>::value,
                "CheckedNumeric<T>: T must be a numeric type.");

 public:
  using type = T;

  constexpr CheckedNumeric() {}

  // Copy constructor.
  template <typename Src>
  constexpr CheckedNumeric(const CheckedNumeric<Src>& rhs)
      : state_(rhs.state_.value(), rhs.IsValid()) {}

  template <typename Src>
  friend class CheckedNumeric;

  // This is not an explicit constructor because we implicitly upgrade regular
  // numerics to CheckedNumerics to make them easier to use.
  template <typename Src>
  constexpr CheckedNumeric(Src value)  // NOLINT(runtime/explicit)
      : state_(value) {
    static_assert(std::is_arithmetic<Src>::value, "Argument must be numeric.");
  }

  // This is not an explicit constructor because we want a seamless conversion
  // from StrictNumeric types.
  template <typename Src>
  constexpr CheckedNumeric(
      StrictNumeric<Src> value)  // NOLINT(runtime/explicit)
      : state_(static_cast<Src>(value)) {}

  // IsValid() - The public API to test if a CheckedNumeric is currently valid.
  // A range checked destination type can be supplied using the Dst template
  // parameter.
  template <typename Dst = T>
  constexpr bool IsValid() const {
    return state_.is_valid() &&
           IsValueInRangeForNumericType<Dst>(state_.value());
  }

  // AssignIfValid(Dst) - Assigns the underlying value if it is currently valid
  // and is within the range supported by the destination type. Returns true if
  // successful and false otherwise.
  template <typename Dst>
  constexpr bool AssignIfValid(Dst* result) const {
    return IsValid<Dst>() ? ((*result = static_cast<Dst>(state_.value())), true)
                          : false;
  }

  // ValueOrDie() - The primary accessor for the underlying value. If the
  // current state is not valid it will CHECK and crash.
  // A range checked destination type can be supplied using the Dst template
  // parameter, which will trigger a CHECK if the value is not in bounds for
  // the destination.
  // The CHECK behavior can be overridden by supplying a handler as a
  // template parameter, for test code, etc. However, the handler cannot access
  // the underlying value, and it is not available through other means.
  template <typename Dst = T, class CheckHandler = CheckOnFailure>
  constexpr StrictNumeric<Dst> ValueOrDie() const {
    return IsValid<Dst>() ? static_cast<Dst>(state_.value())
                          : CheckHandler::template HandleFailure<Dst>();
  }

  // ValueOrDefault(T default_value) - A convenience method that returns the
  // current value if the state is valid, and the supplied default_value for
  // any other state.
  // A range checked destination type can be supplied using the Dst template
  // parameter. WARNING: This function may fail to compile or CHECK at runtime
  // if the supplied default_value is not within range of the destination type.
  template <typename Dst = T, typename Src>
  constexpr StrictNumeric<Dst> ValueOrDefault(const Src default_value) const {
    return IsValid<Dst>() ? static_cast<Dst>(state_.value())
                          : checked_cast<Dst>(default_value);
  }

  // Returns a checked numeric of the specified type, cast from the current
  // CheckedNumeric. If the current state is invalid or the destination cannot
  // represent the result then the returned CheckedNumeric will be invalid.
  template <typename Dst>
  constexpr CheckedNumeric<typename UnderlyingType<Dst>::type> Cast() const {
    return *this;
  }

  // This friend method is available solely for providing more detailed logging
  // in the the tests. Do not implement it in production code, because the
  // underlying values may change at any time.
  template <typename U>
  friend U GetNumericValueForTest(const CheckedNumeric<U>& src);

  // Prototypes for the supported arithmetic operator overloads.
  template <typename Src>
  CheckedNumeric& operator+=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator-=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator*=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator/=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator%=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator<<=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator>>=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator&=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator|=(const Src rhs);
  template <typename Src>
  CheckedNumeric& operator^=(const Src rhs);

  constexpr CheckedNumeric operator-() const {
    return CheckedNumeric<T>(
        NegateWrapper(state_.value()),
        IsValid() &&
            (!std::is_signed<T>::value || std::is_floating_point<T>::value ||
             NegateWrapper(state_.value()) !=
                 std::numeric_limits<T>::lowest()));
  }

  constexpr CheckedNumeric operator~() const {
    return CheckedNumeric<decltype(InvertWrapper(T()))>(
        InvertWrapper(state_.value()), IsValid());
  }

  constexpr CheckedNumeric Abs() const {
    return CheckedNumeric<T>(
        AbsWrapper(state_.value()),
        IsValid() &&
            (!std::is_signed<T>::value || std::is_floating_point<T>::value ||
             AbsWrapper(state_.value()) != std::numeric_limits<T>::lowest()));
  }

  template <typename U>
  constexpr CheckedNumeric<typename MathWrapper<CheckedMaxOp, T, U>::type> Max(
      const U rhs) const {
    using R = typename UnderlyingType<U>::type;
    using result_type = typename MathWrapper<CheckedMaxOp, T, U>::type;
    // TODO(jschuh): This can be converted to the MathOp version and remain
    // constexpr once we have C++14 support.
    return CheckedNumeric<result_type>(
        static_cast<result_type>(
            IsGreater<T, R>::Test(state_.value(), Wrapper<U>::value(rhs))
                ? state_.value()
                : Wrapper<U>::value(rhs)),
        state_.is_valid() && Wrapper<U>::is_valid(rhs));
  }

  template <typename U>
  constexpr CheckedNumeric<typename MathWrapper<CheckedMinOp, T, U>::type> Min(
      const U rhs) const {
    using R = typename UnderlyingType<U>::type;
    using result_type = typename MathWrapper<CheckedMinOp, T, U>::type;
    // TODO(jschuh): This can be converted to the MathOp version and remain
    // constexpr once we have C++14 support.
    return CheckedNumeric<result_type>(
        static_cast<result_type>(
            IsLess<T, R>::Test(state_.value(), Wrapper<U>::value(rhs))
                ? state_.value()
                : Wrapper<U>::value(rhs)),
        state_.is_valid() && Wrapper<U>::is_valid(rhs));
  }

  // This function is available only for integral types. It returns an unsigned
  // integer of the same width as the source type, containing the absolute value
  // of the source, and properly handling signed min.
  constexpr CheckedNumeric<typename UnsignedOrFloatForSize<T>::type>
  UnsignedAbs() const {
    return CheckedNumeric<typename UnsignedOrFloatForSize<T>::type>(
        SafeUnsignedAbs(state_.value()), state_.is_valid());
  }

  CheckedNumeric& operator++() {
    *this += 1;
    return *this;
  }

  CheckedNumeric operator++(int) {
    CheckedNumeric value = *this;
    *this += 1;
    return value;
  }

  CheckedNumeric& operator--() {
    *this -= 1;
    return *this;
  }

  CheckedNumeric operator--(int) {
    CheckedNumeric value = *this;
    *this -= 1;
    return value;
  }

  // These perform the actual math operations on the CheckedNumerics.
  // Binary arithmetic operations.
  template <template <typename, typename, typename> class M,
            typename L,
            typename R>
  static CheckedNumeric MathOp(const L lhs, const R rhs) {
    using Math = typename MathWrapper<M, L, R>::math;
    T result = 0;
    bool is_valid =
        Wrapper<L>::is_valid(lhs) && Wrapper<R>::is_valid(rhs) &&
        Math::Do(Wrapper<L>::value(lhs), Wrapper<R>::value(rhs), &result);
    return CheckedNumeric<T>(result, is_valid);
  };

  // Assignment arithmetic operations.
  template <template <typename, typename, typename> class M, typename R>
  CheckedNumeric& MathOp(const R rhs) {
    using Math = typename MathWrapper<M, T, R>::math;
    T result = 0;  // Using T as the destination saves a range check.
    bool is_valid = state_.is_valid() && Wrapper<R>::is_valid(rhs) &&
                    Math::Do(state_.value(), Wrapper<R>::value(rhs), &result);
    *this = CheckedNumeric<T>(result, is_valid);
    return *this;
  };

 private:
  CheckedNumericState<T> state_;

  template <typename Src>
  constexpr CheckedNumeric(Src value, bool is_valid)
      : state_(value, is_valid) {}

  // These wrappers allow us to handle state the same way for both
  // CheckedNumeric and POD arithmetic types.
  template <typename Src>
  struct Wrapper {
    static constexpr bool is_valid(Src) { return true; }
    static constexpr Src value(Src value) { return value; }
  };

  template <typename Src>
  struct Wrapper<CheckedNumeric<Src>> {
    static constexpr bool is_valid(const CheckedNumeric<Src> v) {
      return v.IsValid();
    }
    static constexpr Src value(const CheckedNumeric<Src> v) {
      return v.state_.value();
    }
  };

  template <typename Src>
  struct Wrapper<StrictNumeric<Src>> {
    static constexpr bool is_valid(const StrictNumeric<Src>) { return true; }
    static constexpr Src value(const StrictNumeric<Src> v) {
      return static_cast<Src>(v);
    }
  };
};

// Convenience functions to avoid the ugly template disambiguator syntax.
template <typename Dst, typename Src>
constexpr bool IsValidForType(const CheckedNumeric<Src> value) {
  return value.template IsValid<Dst>();
}

template <typename Dst, typename Src>
constexpr StrictNumeric<Dst> ValueOrDieForType(
    const CheckedNumeric<Src> value) {
  return value.template ValueOrDie<Dst>();
}

template <typename Dst, typename Src, typename Default>
constexpr StrictNumeric<Dst> ValueOrDefaultForType(
    const CheckedNumeric<Src> value,
    const Default default_value) {
  return value.template ValueOrDefault<Dst>(default_value);
}

// These variadic templates work out the return types.
// TODO(jschuh): Rip all this out once we have C++14 non-trailing auto support.
template <template <typename, typename, typename> class M,
          typename L,
          typename R,
          typename... Args>
struct ResultType;

template <template <typename, typename, typename> class M,
          typename L,
          typename R>
struct ResultType<M, L, R> {
  using type = typename MathWrapper<M, L, R>::type;
};

template <template <typename, typename, typename> class M,
          typename L,
          typename R,
          typename... Args>
struct ResultType {
  using type =
      typename ResultType<M, typename ResultType<M, L, R>::type, Args...>::type;
};

// Convience wrapper to return a new CheckedNumeric from the provided arithmetic
// or CheckedNumericType.
template <typename T>
constexpr CheckedNumeric<typename UnderlyingType<T>::type> MakeCheckedNum(
    const T value) {
  return value;
}

// These implement the variadic wrapper for the math operations.
template <template <typename, typename, typename> class M,
          typename L,
          typename R>
CheckedNumeric<typename MathWrapper<M, L, R>::type> ChkMathOp(const L lhs,
                                                              const R rhs) {
  using Math = typename MathWrapper<M, L, R>::math;
  return CheckedNumeric<typename Math::result_type>::template MathOp<M>(lhs,
                                                                        rhs);
}

// General purpose wrapper template for arithmetic operations.
template <template <typename, typename, typename> class M,
          typename L,
          typename R,
          typename... Args>
CheckedNumeric<typename ResultType<M, L, R, Args...>::type>
ChkMathOp(const L lhs, const R rhs, const Args... args) {
  auto tmp = ChkMathOp<M>(lhs, rhs);
  return tmp.IsValid() ? ChkMathOp<M>(tmp, args...)
                       : decltype(ChkMathOp<M>(tmp, args...))(tmp);
};

// The following macros are just boilerplate for the standard arithmetic
// operator overloads and variadic function templates. A macro isn't the nicest
// solution, but it beats rewriting these over and over again.
#define BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME)                                \
  template <typename L, typename R, typename... Args>                         \
  CheckedNumeric<typename ResultType<Checked##NAME##Op, L, R, Args...>::type> \
      Check##NAME(const L lhs, const R rhs, const Args... args) {             \
    return ChkMathOp<Checked##NAME##Op, L, R, Args...>(lhs, rhs, args...);    \
  }

#define BASE_NUMERIC_ARITHMETIC_OPERATORS(NAME, OP, COMPOUND_OP)               \
  /* Binary arithmetic operator for all CheckedNumeric operations. */          \
  template <typename L, typename R,                                            \
            typename std::enable_if<IsCheckedOp<L, R>::value>::type* =         \
                nullptr>                                                       \
  CheckedNumeric<typename MathWrapper<Checked##NAME##Op, L, R>::type>          \
  operator OP(const L lhs, const R rhs) {                                      \
    return decltype(lhs OP rhs)::template MathOp<Checked##NAME##Op>(lhs, rhs); \
  }                                                                            \
  /* Assignment arithmetic operator implementation from CheckedNumeric. */     \
  template <typename L>                                                        \
  template <typename R>                                                        \
  CheckedNumeric<L>& CheckedNumeric<L>::operator COMPOUND_OP(const R rhs) {    \
    return MathOp<Checked##NAME##Op>(rhs);                                     \
  }                                                                            \
  /* Variadic arithmetic functions that return CheckedNumeric. */              \
  BASE_NUMERIC_ARITHMETIC_VARIADIC(NAME)

BASE_NUMERIC_ARITHMETIC_OPERATORS(Add, +, +=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Sub, -, -=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Mul, *, *=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Div, /, /=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Mod, %, %=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Lsh, <<, <<=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Rsh, >>, >>=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(And, &, &=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Or, |, |=)
BASE_NUMERIC_ARITHMETIC_OPERATORS(Xor, ^, ^=)
BASE_NUMERIC_ARITHMETIC_VARIADIC(Max)
BASE_NUMERIC_ARITHMETIC_VARIADIC(Min)

#undef BASE_NUMERIC_ARITHMETIC_VARIADIC
#undef BASE_NUMERIC_ARITHMETIC_OPERATORS

// These are some extra StrictNumeric operators to support simple pointer
// arithmetic with our result types. Since wrapping on a pointer is always
// bad, we trigger the CHECK condition here.
template <typename L, typename R>
L* operator+(L* lhs, const StrictNumeric<R> rhs) {
  uintptr_t result = CheckAdd(reinterpret_cast<uintptr_t>(lhs),
                              CheckMul(sizeof(L), static_cast<R>(rhs)))
                         .template ValueOrDie<uintptr_t>();
  return reinterpret_cast<L*>(result);
}

template <typename L, typename R>
L* operator-(L* lhs, const StrictNumeric<R> rhs) {
  uintptr_t result = CheckSub(reinterpret_cast<uintptr_t>(lhs),
                              CheckMul(sizeof(L), static_cast<R>(rhs)))
                         .template ValueOrDie<uintptr_t>();
  return reinterpret_cast<L*>(result);
}

}  // namespace internal

using internal::CheckedNumeric;
using internal::IsValidForType;
using internal::ValueOrDieForType;
using internal::ValueOrDefaultForType;
using internal::MakeCheckedNum;
using internal::CheckMax;
using internal::CheckMin;
using internal::CheckAdd;
using internal::CheckSub;
using internal::CheckMul;
using internal::CheckDiv;
using internal::CheckMod;
using internal::CheckLsh;
using internal::CheckRsh;
using internal::CheckAnd;
using internal::CheckOr;
using internal::CheckXor;

}  // namespace base
}  // namespace pdfium

#endif  // PDFIUM_THIRD_PARTY_BASE_NUMERICS_SAFE_MATH_H_