1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
4 * You can obtain one at http://mozilla.org/MPL/2.0/. */
6 /* Provides checked integers, detecting integer overflow and divide-by-0. */
8 #ifndef mozilla_CheckedInt_h_
9 #define mozilla_CheckedInt_h_
12 * Build options. Comment out these #defines to disable the corresponding
13 * optional feature. Disabling features may be useful for code using
14 * CheckedInt outside of Mozilla (e.g. WebKit)
17 // Enable usage of MOZ_STATIC_ASSERT to check for unsupported types.
18 // If disabled, static asserts are replaced by regular assert().
19 #define MOZ_CHECKEDINT_ENABLE_MOZ_ASSERTS
22 * End of build options
26 #ifdef MOZ_CHECKEDINT_ENABLE_MOZ_ASSERTS
27 # include "mozilla/Assertions.h"
29 # ifndef MOZ_STATIC_ASSERT
31 # define MOZ_STATIC_ASSERT(cond, reason) assert((cond) && reason)
32 # define MOZ_ASSERT(cond, reason) assert((cond) && reason)
36 #include "mozilla/StandardInteger.h"
46 * Step 1: manually record supported types
48 * What's nontrivial here is that there are different families of integer
49 * types: basic integer types and stdint types. It is merrily undefined which
50 * types from one family may be just typedefs for a type from another family.
52 * For example, on GCC 4.6, aside from the basic integer types, the only other
53 * type that isn't just a typedef for some of them, is int8_t.
56 struct UnsupportedType
{};
58 template<typename IntegerType
>
59 struct IsSupportedPass2
61 static const bool value
= false;
64 template<typename IntegerType
>
67 static const bool value
= IsSupportedPass2
<IntegerType
>::value
;
71 struct IsSupported
<int8_t>
72 { static const bool value
= true; };
75 struct IsSupported
<uint8_t>
76 { static const bool value
= true; };
79 struct IsSupported
<int16_t>
80 { static const bool value
= true; };
83 struct IsSupported
<uint16_t>
84 { static const bool value
= true; };
87 struct IsSupported
<int32_t>
88 { static const bool value
= true; };
91 struct IsSupported
<uint32_t>
92 { static const bool value
= true; };
95 struct IsSupported
<int64_t>
96 { static const bool value
= true; };
99 struct IsSupported
<uint64_t>
100 { static const bool value
= true; };
104 struct IsSupportedPass2
<char>
105 { static const bool value
= true; };
108 struct IsSupportedPass2
<unsigned char>
109 { static const bool value
= true; };
112 struct IsSupportedPass2
<short>
113 { static const bool value
= true; };
116 struct IsSupportedPass2
<unsigned short>
117 { static const bool value
= true; };
120 struct IsSupportedPass2
<int>
121 { static const bool value
= true; };
124 struct IsSupportedPass2
<unsigned int>
125 { static const bool value
= true; };
128 struct IsSupportedPass2
<long>
129 { static const bool value
= true; };
132 struct IsSupportedPass2
<unsigned long>
133 { static const bool value
= true; };
137 * Step 2: some integer-traits kind of stuff.
140 template<size_t Size
, bool Signedness
>
141 struct StdintTypeForSizeAndSignedness
145 struct StdintTypeForSizeAndSignedness
<1, true>
146 { typedef int8_t Type
; };
149 struct StdintTypeForSizeAndSignedness
<1, false>
150 { typedef uint8_t Type
; };
153 struct StdintTypeForSizeAndSignedness
<2, true>
154 { typedef int16_t Type
; };
157 struct StdintTypeForSizeAndSignedness
<2, false>
158 { typedef uint16_t Type
; };
161 struct StdintTypeForSizeAndSignedness
<4, true>
162 { typedef int32_t Type
; };
165 struct StdintTypeForSizeAndSignedness
<4, false>
166 { typedef uint32_t Type
; };
169 struct StdintTypeForSizeAndSignedness
<8, true>
170 { typedef int64_t Type
; };
173 struct StdintTypeForSizeAndSignedness
<8, false>
174 { typedef uint64_t Type
; };
176 template<typename IntegerType
>
179 typedef typename StdintTypeForSizeAndSignedness
<sizeof(IntegerType
),
183 template<typename IntegerType
>
186 static const bool value
= IntegerType(-1) <= IntegerType(0);
189 template<typename IntegerType
, size_t Size
= sizeof(IntegerType
)>
190 struct TwiceBiggerType
192 typedef typename StdintTypeForSizeAndSignedness
<
193 sizeof(IntegerType
) * 2,
194 IsSigned
<IntegerType
>::value
198 template<typename IntegerType
>
199 struct TwiceBiggerType
<IntegerType
, 8>
201 typedef UnsupportedType Type
;
204 template<typename IntegerType
>
205 struct PositionOfSignBit
207 static const size_t value
= CHAR_BIT
* sizeof(IntegerType
) - 1;
210 template<typename IntegerType
>
214 typedef typename UnsignedType
<IntegerType
>::Type UnsignedIntegerType
;
215 static const size_t PosOfSignBit
= PositionOfSignBit
<IntegerType
>::value
;
218 // Bitwise ops may return a larger type, that's why we cast explicitly.
219 // In C++, left bit shifts on signed values is undefined by the standard
220 // unless the shifted value is representable.
221 // Notice that signed-to-unsigned conversions are always well-defined in
222 // the standard as the value congruent to 2**n, as expected. By contrast,
223 // unsigned-to-signed is only well-defined if the value is representable.
224 static const IntegerType value
=
225 IsSigned
<IntegerType
>::value
226 ? IntegerType(UnsignedIntegerType(1) << PosOfSignBit
)
230 template<typename IntegerType
>
233 // Tricksy, but covered by the unit test.
234 // Relies heavily on the type of MinValue<IntegerType>::value
235 // being IntegerType.
236 static const IntegerType value
= ~MinValue
<IntegerType
>::value
;
240 * Step 3: Implement the actual validity checks.
242 * Ideas taken from IntegerLib, code different.
249 // In C++, right bit shifts on negative values is undefined by the standard.
250 // Notice that signed-to-unsigned conversions are always well-defined in the
251 // standard, as the value congruent modulo 2**n as expected. By contrast,
252 // unsigned-to-signed is only well-defined if the value is representable.
253 return bool(typename UnsignedType
<T
>::Type(x
)
254 >> PositionOfSignBit
<T
>::value
);
257 // Bitwise ops may return a larger type, so it's good to use this inline
258 // helper guaranteeing that the result is really of type T.
261 BinaryComplement(T x
)
268 bool IsTSigned
= IsSigned
<T
>::value
,
269 bool IsUSigned
= IsSigned
<U
>::value
>
270 struct DoesRangeContainRange
274 template<typename T
, typename U
, bool Signedness
>
275 struct DoesRangeContainRange
<T
, U
, Signedness
, Signedness
>
277 static const bool value
= sizeof(T
) >= sizeof(U
);
280 template<typename T
, typename U
>
281 struct DoesRangeContainRange
<T
, U
, true, false>
283 static const bool value
= sizeof(T
) > sizeof(U
);
286 template<typename T
, typename U
>
287 struct DoesRangeContainRange
<T
, U
, false, true>
289 static const bool value
= false;
294 bool IsTSigned
= IsSigned
<T
>::value
,
295 bool IsUSigned
= IsSigned
<U
>::value
,
296 bool DoesTRangeContainURange
= DoesRangeContainRange
<T
, U
>::value
>
297 struct IsInRangeImpl
{};
299 template<typename T
, typename U
, bool IsTSigned
, bool IsUSigned
>
300 struct IsInRangeImpl
<T
, U
, IsTSigned
, IsUSigned
, true>
308 template<typename T
, typename U
>
309 struct IsInRangeImpl
<T
, U
, true, true, false>
313 return x
<= MaxValue
<T
>::value
&& x
>= MinValue
<T
>::value
;
317 template<typename T
, typename U
>
318 struct IsInRangeImpl
<T
, U
, false, false, false>
322 return x
<= MaxValue
<T
>::value
;
326 template<typename T
, typename U
>
327 struct IsInRangeImpl
<T
, U
, true, false, false>
331 return sizeof(T
) > sizeof(U
) || x
<= U(MaxValue
<T
>::value
);
335 template<typename T
, typename U
>
336 struct IsInRangeImpl
<T
, U
, false, true, false>
340 return sizeof(T
) >= sizeof(U
)
342 : x
>= 0 && x
<= U(MaxValue
<T
>::value
);
346 template<typename T
, typename U
>
350 return IsInRangeImpl
<T
, U
>::run(x
);
357 // Addition is valid if the sign of x+y is equal to either that of x or that
358 // of y. Since the value of x+y is undefined if we have a signed type, we
359 // compute it using the unsigned type of the same size.
360 // Beware! These bitwise operations can return a larger integer type,
361 // if T was a small type like int8_t, so we explicitly cast to T.
363 typename UnsignedType
<T
>::Type ux
= x
;
364 typename UnsignedType
<T
>::Type uy
= y
;
365 typename UnsignedType
<T
>::Type result
= ux
+ uy
;
366 return IsSigned
<T
>::value
367 ? HasSignBit(BinaryComplement(T((result
^ x
) & (result
^ y
))))
368 : BinaryComplement(x
) >= y
;
375 // Subtraction is valid if either x and y have same sign, or x-y and x have
376 // same sign. Since the value of x-y is undefined if we have a signed type,
377 // we compute it using the unsigned type of the same size.
378 typename UnsignedType
<T
>::Type ux
= x
;
379 typename UnsignedType
<T
>::Type uy
= y
;
380 typename UnsignedType
<T
>::Type result
= ux
- uy
;
382 return IsSigned
<T
>::value
383 ? HasSignBit(BinaryComplement(T((result
^ x
) & (x
^ y
))))
388 bool IsSigned
= IsSigned
<T
>::value
,
389 bool TwiceBiggerTypeIsSupported
=
390 IsSupported
<typename TwiceBiggerType
<T
>::Type
>::value
>
391 struct IsMulValidImpl
{};
393 template<typename T
, bool IsSigned
>
394 struct IsMulValidImpl
<T
, IsSigned
, true>
396 static bool run(T x
, T y
)
398 typedef typename TwiceBiggerType
<T
>::Type TwiceBiggerType
;
399 TwiceBiggerType product
= TwiceBiggerType(x
) * TwiceBiggerType(y
);
400 return IsInRange
<T
>(product
);
405 struct IsMulValidImpl
<T
, true, false>
407 static bool run(T x
, T y
)
409 const T max
= MaxValue
<T
>::value
;
410 const T min
= MinValue
<T
>::value
;
412 if (x
== 0 || y
== 0)
421 // If we reach this point, we know that x < 0.
429 struct IsMulValidImpl
<T
, false, false>
431 static bool run(T x
, T y
)
433 return y
== 0 || x
<= MaxValue
<T
>::value
/ y
;
441 return IsMulValidImpl
<T
>::run(x
, y
);
448 // Keep in mind that in the signed case, min/-1 is invalid because abs(min)>max.
450 !(IsSigned
<T
>::value
&& x
== MinValue
<T
>::value
&& y
== T(-1));
453 // This is just to shut up msvc warnings about negating unsigned ints.
454 template<typename T
, bool IsSigned
= IsSigned
<T
>::value
>
455 struct OppositeIfSignedImpl
457 static T
run(T x
) { return -x
; }
460 struct OppositeIfSignedImpl
<T
, false>
462 static T
run(T x
) { return x
; }
466 OppositeIfSigned(T x
)
468 return OppositeIfSignedImpl
<T
>::run(x
);
471 } // namespace detail
475 * Step 4: Now define the CheckedInt class.
480 * @brief Integer wrapper class checking for integer overflow and other errors
481 * @param T the integer type to wrap. Can be any type among the following:
482 * - any basic integer type such as |int|
483 * - any stdint type such as |int8_t|
485 * This class implements guarded integer arithmetic. Do a computation, check
486 * that isValid() returns true, you then have a guarantee that no problem, such
487 * as integer overflow, happened during this computation, and you can call
488 * value() to get the plain integer value.
490 * The arithmetic operators in this class are guaranteed not to raise a signal
491 * (e.g. in case of a division by zero).
493 * For example, suppose that you want to implement a function that computes
494 * (x+y)/z, that doesn't crash if z==0, and that reports on error (divide by
495 * zero or integer overflow). You could code it as follows:
497 bool computeXPlusYOverZ(int x, int y, int z, int *result)
499 CheckedInt<int> checkedResult = (CheckedInt<int>(x) + y) / z;
500 if (checkedResult.isValid()) {
501 *result = checkedResult.value();
509 * Implicit conversion from plain integers to checked integers is allowed. The
510 * plain integer is checked to be in range before being casted to the
511 * destination type. This means that the following lines all compile, and the
512 * resulting CheckedInts are correctly detected as valid or invalid:
514 // 1 is of type int, is found to be in range for uint8_t, x is valid
515 CheckedInt<uint8_t> x(1);
516 // -1 is of type int, is found not to be in range for uint8_t, x is invalid
517 CheckedInt<uint8_t> x(-1);
518 // -1 is of type int, is found to be in range for int8_t, x is valid
519 CheckedInt<int8_t> x(-1);
520 // 1000 is of type int16_t, is found not to be in range for int8_t,
522 CheckedInt<int8_t> x(int16_t(1000));
523 // 3123456789 is of type uint32_t, is found not to be in range for int32_t,
525 CheckedInt<int32_t> x(uint32_t(3123456789));
527 * Implicit conversion from
528 * checked integers to plain integers is not allowed. As shown in the
529 * above example, to get the value of a checked integer as a normal integer,
532 * Arithmetic operations between checked and plain integers is allowed; the
533 * result type is the type of the checked integer.
535 * Checked integers of different types cannot be used in the same arithmetic
538 * There are convenience typedefs for all stdint types, of the following form
539 * (these are just 2 examples):
541 typedef CheckedInt<int32_t> CheckedInt32;
542 typedef CheckedInt<uint16_t> CheckedUint16;
553 CheckedInt(U value
, bool isValid
) : mValue(value
), mIsValid(isValid
)
555 MOZ_STATIC_ASSERT(detail::IsSupported
<T
>::value
,
556 "This type is not supported by CheckedInt");
561 * Constructs a checked integer with given @a value. The checked integer is
562 * initialized as valid or invalid depending on whether the @a value
565 * This constructor is not explicit. Instead, the type of its argument is a
566 * separate template parameter, ensuring that no conversion is performed
567 * before this constructor is actually called. As explained in the above
568 * documentation for class CheckedInt, this constructor checks that its
574 mIsValid(detail::IsInRange
<T
>(value
))
576 MOZ_STATIC_ASSERT(detail::IsSupported
<T
>::value
,
577 "This type is not supported by CheckedInt");
580 /** Constructs a valid checked integer with initial value 0 */
581 CheckedInt() : mValue(0), mIsValid(true)
583 MOZ_STATIC_ASSERT(detail::IsSupported
<T
>::value
,
584 "This type is not supported by CheckedInt");
587 /** @returns the actual value */
590 MOZ_ASSERT(mIsValid
, "Invalid checked integer (division by zero or integer overflow)");
595 * @returns true if the checked integer is valid, i.e. is not the result
596 * of an invalid operation or of an operation involving an invalid checked
605 friend CheckedInt
<U
> operator +(const CheckedInt
<U
>& lhs
,
606 const CheckedInt
<U
>& rhs
);
608 CheckedInt
& operator +=(U rhs
);
610 friend CheckedInt
<U
> operator -(const CheckedInt
<U
>& lhs
,
611 const CheckedInt
<U
> &rhs
);
613 CheckedInt
& operator -=(U rhs
);
615 friend CheckedInt
<U
> operator *(const CheckedInt
<U
>& lhs
,
616 const CheckedInt
<U
> &rhs
);
618 CheckedInt
& operator *=(U rhs
);
620 friend CheckedInt
<U
> operator /(const CheckedInt
<U
>& lhs
,
621 const CheckedInt
<U
> &rhs
);
623 CheckedInt
& operator /=(U rhs
);
625 CheckedInt
operator -() const
627 // Circumvent msvc warning about - applied to unsigned int.
628 // if we're unsigned, the only valid case anyway is 0
629 // in which case - is a no-op.
630 T result
= detail::OppositeIfSigned(mValue
);
631 /* Help the compiler perform RVO (return value optimization). */
632 return CheckedInt(result
,
633 mIsValid
&& detail::IsSubValid(T(0),
638 * @returns true if the left and right hand sides are valid
639 * and have the same value.
641 * Note that these semantics are the reason why we don't offer
642 * a operator!=. Indeed, we'd want to have a!=b be equivalent to !(a==b)
643 * but that would mean that whenever a or b is invalid, a!=b
644 * is always true, which would be very confusing.
646 * For similar reasons, operators <, >, <=, >= would be very tricky to
647 * specify, so we just avoid offering them.
649 * Notice that these == semantics are made more reasonable by these facts:
650 * 1. a==b implies equality at the raw data level
651 * (the converse is false, as a==b is never true among invalids)
652 * 2. This is similar to the behavior of IEEE floats, where a==b
653 * means that a and b have the same value *and* neither is NaN.
655 bool operator ==(const CheckedInt
& other
) const
657 return mIsValid
&& other
.mIsValid
&& mValue
== other
.mValue
;
661 CheckedInt
& operator++()
668 CheckedInt
operator++(int)
670 CheckedInt tmp
= *this;
676 CheckedInt
& operator--()
683 CheckedInt
operator--(int)
685 CheckedInt tmp
= *this;
692 * The !=, <, <=, >, >= operators are disabled:
693 * see the comment on operator==.
696 bool operator !=(U other
) const MOZ_DELETE
;
698 bool operator <(U other
) const MOZ_DELETE
;
700 bool operator <=(U other
) const MOZ_DELETE
;
702 bool operator >(U other
) const MOZ_DELETE
;
704 bool operator >=(U other
) const MOZ_DELETE
;
707 #define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP) \
708 template<typename T> \
709 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, \
710 const CheckedInt<T> &rhs) \
712 if (!detail::Is##NAME##Valid(lhs.mValue, rhs.mValue)) \
713 return CheckedInt<T>(0, false); \
715 return CheckedInt<T>(lhs.mValue OP rhs.mValue, \
716 lhs.mIsValid && rhs.mIsValid); \
719 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Add
, +)
720 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Sub
, -)
721 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Mul
, *)
722 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Div
, /)
724 #undef MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR
726 // Implement castToCheckedInt<T>(x), making sure that
727 // - it allows x to be either a CheckedInt<T> or any integer type
728 // that can be casted to T
729 // - if x is already a CheckedInt<T>, we just return a reference to it,
730 // instead of copying it (optimization)
734 template<typename T
, typename U
>
735 struct CastToCheckedIntImpl
737 typedef CheckedInt
<T
> ReturnType
;
738 static CheckedInt
<T
> run(U u
) { return u
; }
742 struct CastToCheckedIntImpl
<T
, CheckedInt
<T
> >
744 typedef const CheckedInt
<T
>& ReturnType
;
745 static const CheckedInt
<T
>& run(const CheckedInt
<T
>& u
) { return u
; }
748 } // namespace detail
750 template<typename T
, typename U
>
751 inline typename
detail::CastToCheckedIntImpl
<T
, U
>::ReturnType
752 castToCheckedInt(U u
)
754 return detail::CastToCheckedIntImpl
<T
, U
>::run(u
);
757 #define MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP) \
758 template<typename T> \
759 template<typename U> \
760 CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(U rhs) \
762 *this = *this OP castToCheckedInt<T>(rhs); \
765 template<typename T, typename U> \
766 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, U rhs) \
768 return lhs OP castToCheckedInt<T>(rhs); \
770 template<typename T, typename U> \
771 inline CheckedInt<T> operator OP(U lhs, const CheckedInt<T> &rhs) \
773 return castToCheckedInt<T>(lhs) OP rhs; \
776 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=)
777 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=)
778 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=)
779 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=)
781 #undef MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS
783 template<typename T
, typename U
>
785 operator ==(const CheckedInt
<T
> &lhs
, U rhs
)
787 return lhs
== castToCheckedInt
<T
>(rhs
);
790 template<typename T
, typename U
>
792 operator ==(U lhs
, const CheckedInt
<T
> &rhs
)
794 return castToCheckedInt
<T
>(lhs
) == rhs
;
797 // Convenience typedefs.
798 typedef CheckedInt
<int8_t> CheckedInt8
;
799 typedef CheckedInt
<uint8_t> CheckedUint8
;
800 typedef CheckedInt
<int16_t> CheckedInt16
;
801 typedef CheckedInt
<uint16_t> CheckedUint16
;
802 typedef CheckedInt
<int32_t> CheckedInt32
;
803 typedef CheckedInt
<uint32_t> CheckedUint32
;
804 typedef CheckedInt
<int64_t> CheckedInt64
;
805 typedef CheckedInt
<uint64_t> CheckedUint64
;
807 } // namespace mozilla
809 #endif /* mozilla_CheckedInt_h_ */