The Tor Browser / file revision

 /* -*- 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/. */

 /* Provides checked integers, detecting integer overflow and divide-by-0. */

 #ifndef mozilla_CheckedInt_h

 #define mozilla_CheckedInt_h

 #include <stdint.h>

 #include "mozilla/Assertions.h"

 #include "mozilla/IntegerTypeTraits.h"

 namespace mozilla {

 template<typename T> class CheckedInt;

 namespace detail {

 /*

  * Step 1: manually record supported types

  *

  * What's nontrivial here is that there are different families of integer

  * types: basic integer types and stdint types. It is merrily undefined which

  * types from one family may be just typedefs for a type from another family.

  *

  * For example, on GCC 4.6, aside from the basic integer types, the only other

  * type that isn't just a typedef for some of them, is int8_t.

  */

 struct UnsupportedType {};

 template<typename IntegerType>

 struct IsSupportedPass2

 {

     static const bool value = false;

 };

 template<typename IntegerType>

 struct IsSupported

 {

     static const bool value = IsSupportedPass2<IntegerType>::value;

 };

 template<>

 struct IsSupported<int8_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<uint8_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<int16_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<uint16_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<int32_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<uint32_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<int64_t>

 { static const bool value = true; };

 template<>

 struct IsSupported<uint64_t>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<char>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<signed char>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<unsigned char>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<short>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<unsigned short>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<int>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<unsigned int>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<long>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<unsigned long>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<long long>

 { static const bool value = true; };

 template<>

 struct IsSupportedPass2<unsigned long long>

 { static const bool value = true; };

 /*

  * Step 2: Implement the actual validity checks.

  *

  * Ideas taken from IntegerLib, code different.

  */

 template<typename IntegerType, size_t Size = sizeof(IntegerType)>

 struct TwiceBiggerType

 {

     typedef typename detail::StdintTypeForSizeAndSignedness<

                        sizeof(IntegerType) * 2,

                        IsSigned<IntegerType>::value

                      >::Type Type;

 };

 template<typename IntegerType>

 struct TwiceBiggerType<IntegerType, 8>

 {

     typedef UnsupportedType Type;

 };

 template<typename T>

 inline bool

 HasSignBit(T x)

 {

   // In C++, right bit shifts on negative values is undefined by the standard.

   // Notice that signed-to-unsigned conversions are always well-defined in the

   // standard, as the value congruent modulo 2**n as expected. By contrast,

   // unsigned-to-signed is only well-defined if the value is representable.

   return bool(typename MakeUnsigned<T>::Type(x) >> PositionOfSignBit<T>::value);

 }

 // Bitwise ops may return a larger type, so it's good to use this inline

 // helper guaranteeing that the result is really of type T.

 template<typename T>

 inline T

 BinaryComplement(T x)

 {

   return ~x;

 }

 template<typename T,

          typename U,

          bool IsTSigned = IsSigned<T>::value,

          bool IsUSigned = IsSigned<U>::value>

 struct DoesRangeContainRange

 {

 };

 template<typename T, typename U, bool Signedness>

 struct DoesRangeContainRange<T, U, Signedness, Signedness>

 {

     static const bool value = sizeof(T) >= sizeof(U);

 };

 template<typename T, typename U>

 struct DoesRangeContainRange<T, U, true, false>

 {

     static const bool value = sizeof(T) > sizeof(U);

 };

 template<typename T, typename U>

 struct DoesRangeContainRange<T, U, false, true>

 {

     static const bool value = false;

 };

 template<typename T,

          typename U,

          bool IsTSigned = IsSigned<T>::value,

          bool IsUSigned = IsSigned<U>::value,

          bool DoesTRangeContainURange = DoesRangeContainRange<T, U>::value>

 struct IsInRangeImpl {};

 template<typename T, typename U, bool IsTSigned, bool IsUSigned>

 struct IsInRangeImpl<T, U, IsTSigned, IsUSigned, true>

 {

     static bool run(U)

     {

        return true;

     }

 };

 template<typename T, typename U>

 struct IsInRangeImpl<T, U, true, true, false>

 {

     static bool run(U x)

     {

       return x <= MaxValue<T>::value && x >= MinValue<T>::value;

     }

 };

 template<typename T, typename U>

 struct IsInRangeImpl<T, U, false, false, false>

 {

     static bool run(U x)

     {

       return x <= MaxValue<T>::value;

     }

 };

 template<typename T, typename U>

 struct IsInRangeImpl<T, U, true, false, false>

 {

     static bool run(U x)

     {

       return sizeof(T) > sizeof(U) || x <= U(MaxValue<T>::value);

     }

 };

 template<typename T, typename U>

 struct IsInRangeImpl<T, U, false, true, false>

 {

     static bool run(U x)

     {

       return sizeof(T) >= sizeof(U)

              ? x >= 0

              : x >= 0 && x <= U(MaxValue<T>::value);

     }

 };

 template<typename T, typename U>

 inline bool

 IsInRange(U x)

 {

   return IsInRangeImpl<T, U>::run(x);

 }

 template<typename T>

 inline bool

 IsAddValid(T x, T y)

 {

   // Addition is valid if the sign of x+y is equal to either that of x or that

   // of y. 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.

   // Beware! These bitwise operations can return a larger integer type,

   // if T was a small type like int8_t, so we explicitly cast to T.

   typename MakeUnsigned<T>::Type ux = x;

   typename MakeUnsigned<T>::Type uy = y;

   typename MakeUnsigned<T>::Type result = ux + uy;

   return IsSigned<T>::value

          ? HasSignBit(BinaryComplement(T((result ^ x) & (result ^ y))))

          : BinaryComplement(x) >= y;

 }

 template<typename T>

 inline bool

 IsSubValid(T x, T y)

 {

   // Subtraction is valid if either x and y have same sign, or x-y and x have

   // same sign. 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.

   typename MakeUnsigned<T>::Type ux = x;

   typename MakeUnsigned<T>::Type uy = y;

   typename MakeUnsigned<T>::Type result = ux - uy;

   return IsSigned<T>::value

          ? HasSignBit(BinaryComplement(T((result ^ x) & (x ^ y))))

          : x >= y;

 }

 template<typename T,

          bool IsTSigned = IsSigned<T>::value,

          bool TwiceBiggerTypeIsSupported =

            IsSupported<typename TwiceBiggerType<T>::Type>::value>

 struct IsMulValidImpl {};

 template<typename T, bool IsTSigned>

 struct IsMulValidImpl<T, IsTSigned, true>

 {

     static bool run(T x, T y)

     {

       typedef typename TwiceBiggerType<T>::Type TwiceBiggerType;

       TwiceBiggerType product = TwiceBiggerType(x) * TwiceBiggerType(y);

       return IsInRange<T>(product);

     }

 };

 template<typename T>

 struct IsMulValidImpl<T, true, false>

 {

     static bool run(T x, T y)

     {

       const T max = MaxValue<T>::value;

       const T min = MinValue<T>::value;

       if (x == 0 || y == 0)

         return true;

       if (x > 0) {

         return y > 0

                ? x <= max / y

                : y >= min / x;

       }

       // If we reach this point, we know that x < 0.

       return y > 0

              ? x >= min / y

              : y >= max / x;

     }

 };

 template<typename T>

 struct IsMulValidImpl<T, false, false>

 {

     static bool run(T x, T y)

     {

       return y == 0 ||  x <= MaxValue<T>::value / y;

     }

 };

 template<typename T>

 inline bool

 IsMulValid(T x, T y)

 {

   return IsMulValidImpl<T>::run(x, y);

 }

 template<typename T>

 inline bool

 IsDivValid(T x, T y)

 {

   // Keep in mind that in the signed case, min/-1 is invalid because abs(min)>max.

   return y != 0 &&

          !(IsSigned<T>::value && x == MinValue<T>::value && y == T(-1));

 }

 template<typename T, bool IsTSigned = IsSigned<T>::value>

 struct IsModValidImpl;

 template<typename T>

 inline bool

 IsModValid(T x, T y)

 {

   return IsModValidImpl<T>::run(x, y);

 }

 /*

  * Mod is pretty simple.

  * For now, let's just use the ANSI C definition:

  * If x or y are negative, the results are implementation defined.

  *   Consider these invalid.

  * Undefined for y=0.

  * The result will never exceed either x or y.

  *

  * Checking that x>=0 is a warning when T is unsigned.

  */

 template<typename T>

 struct IsModValidImpl<T, false> {

   static inline bool run(T x, T y) {

     return y >= 1;

   }

 };

 template<typename T>

 struct IsModValidImpl<T, true> {

   static inline bool run(T x, T y) {

     if (x < 0)

       return false;

     return y >= 1;

   }

 };

 template<typename T, bool IsSigned = IsSigned<T>::value>

 struct NegateImpl;

 template<typename T>

 struct NegateImpl<T, false>

 {

     static CheckedInt<T> negate(const CheckedInt<T>& val)

     {

       // Handle negation separately for signed/unsigned, for simpler code and to

       // avoid an MSVC warning negating an unsigned value.

       return CheckedInt<T>(0, val.isValid() && val.mValue == 0);

     }

 };

 template<typename T>

 struct NegateImpl<T, true>

 {

     static CheckedInt<T> negate(const CheckedInt<T>& val)

     {

       // Watch out for the min-value, which (with twos-complement) can't be

       // negated as -min-value is then (max-value + 1).

       if (!val.isValid() || val.mValue == MinValue<T>::value)

         return CheckedInt<T>(val.mValue, false);

       return CheckedInt<T>(-val.mValue, true);

     }

 };

 } // namespace detail

 /*

  * Step 3: Now define the CheckedInt class.

  */

 /**

  * @class CheckedInt

  * @brief Integer wrapper class checking for integer overflow and other errors

  * @param T the integer type to wrap. Can be any type among the following:

  *            - any basic integer type such as |int|

  *            - any stdint type such as |int8_t|

  *

  * This class implements guarded integer arithmetic. Do a computation, check

  * that isValid() returns true, you then have a guarantee that no problem, such

  * as integer overflow, happened during this computation, and you can call

  * value() to get the plain integer value.

  *

  * The arithmetic operators in this class are guaranteed not to raise a signal

  * (e.g. in case of a division by zero).

  *

  * For example, suppose that you want to implement a function that computes

  * (x+y)/z, that doesn't crash if z==0, and that reports on error (divide by

  * zero or integer overflow). You could code it as follows:

    @code

    bool computeXPlusYOverZ(int x, int y, int z, int *result)

    {

        CheckedInt<int> checkedResult = (CheckedInt<int>(x) + y) / z;

        if (checkedResult.isValid()) {

            *result = checkedResult.value();

            return true;

        } else {

            return false;

        }

    }

    @endcode

  *

  * Implicit conversion from plain integers to checked integers is allowed. The

  * plain integer is checked to be in range before being casted to the

  * destination type. This means that the following lines all compile, and the

  * resulting CheckedInts are correctly detected as valid or invalid:

  * @code

    // 1 is of type int, is found to be in range for uint8_t, x is valid

    CheckedInt<uint8_t> x(1);

    // -1 is of type int, is found not to be in range for uint8_t, x is invalid

    CheckedInt<uint8_t> x(-1);

    // -1 is of type int, is found to be in range for int8_t, x is valid

    CheckedInt<int8_t> x(-1);

    // 1000 is of type int16_t, is found not to be in range for int8_t,

    // x is invalid

    CheckedInt<int8_t> x(int16_t(1000));

    // 3123456789 is of type uint32_t, is found not to be in range for int32_t,

    // x is invalid

    CheckedInt<int32_t> x(uint32_t(3123456789));

  * @endcode

  * Implicit conversion from

  * checked integers to plain integers is not allowed. As shown in the

  * above example, to get the value of a checked integer as a normal integer,

  * call value().

  *

  * Arithmetic operations between checked and plain integers is allowed; the

  * result type is the type of the checked integer.

  *

  * Checked integers of different types cannot be used in the same arithmetic

  * expression.

  *

  * There are convenience typedefs for all stdint types, of the following form

  * (these are just 2 examples):

    @code

    typedef CheckedInt<int32_t> CheckedInt32;

    typedef CheckedInt<uint16_t> CheckedUint16;

    @endcode

  */

 template<typename T>

 class CheckedInt

 {

   protected:

     T mValue;

     bool mIsValid;

     template<typename U>

     CheckedInt(U aValue, bool aIsValid) : mValue(aValue), mIsValid(aIsValid)

     {

       static_assert(detail::IsSupported<T>::value &&

                     detail::IsSupported<U>::value,

                     "This type is not supported by CheckedInt");

     }

     friend struct detail::NegateImpl<T>;

   public:

     /**

      * Constructs a checked integer with given @a value. The checked integer is

      * initialized as valid or invalid depending on whether the @a value

      * is in range.

      *

      * This constructor is not explicit. Instead, the type of its argument is a

      * separate template parameter, ensuring that no conversion is performed

      * before this constructor is actually called. As explained in the above

      * documentation for class CheckedInt, this constructor checks that its

      * argument is valid.

      */

     template<typename U>

     CheckedInt(U aValue)

       : mValue(T(aValue)),

         mIsValid(detail::IsInRange<T>(aValue))

     {

       static_assert(detail::IsSupported<T>::value &&

                     detail::IsSupported<U>::value,

                     "This type is not supported by CheckedInt");

     }

     template<typename U>

     friend class CheckedInt;

     template<typename U>

     CheckedInt<U> toChecked() const

     {

       CheckedInt<U> ret(mValue);

       ret.mIsValid = ret.mIsValid && mIsValid;

       return ret;

     }

     /** Constructs a valid checked integer with initial value 0 */

     CheckedInt() : mValue(0), mIsValid(true)

     {

       static_assert(detail::IsSupported<T>::value,

                     "This type is not supported by CheckedInt");

     }

     /** @returns the actual value */

     T value() const

     {

       MOZ_ASSERT(mIsValid, "Invalid checked integer (division by zero or integer overflow)");

       return mValue;

     }

     /**

      * @returns true if the checked integer is valid, i.e. is not the result

      * of an invalid operation or of an operation involving an invalid checked

      * integer

      */

     bool isValid() const

     {

       return mIsValid;

     }

     template<typename U>

     friend CheckedInt<U> operator +(const CheckedInt<U>& lhs,

                                     const CheckedInt<U>& rhs);

     template<typename U>

     CheckedInt& operator +=(U rhs);

     template<typename U>

     friend CheckedInt<U> operator -(const CheckedInt<U>& lhs,

                                     const CheckedInt<U>& rhs);

     template<typename U>

     CheckedInt& operator -=(U rhs);

     template<typename U>

     friend CheckedInt<U> operator *(const CheckedInt<U>& lhs,

                                     const CheckedInt<U>& rhs);

     template<typename U>

     CheckedInt& operator *=(U rhs);

     template<typename U>

     friend CheckedInt<U> operator /(const CheckedInt<U>& lhs,

                                     const CheckedInt<U>& rhs);

     template<typename U>

     CheckedInt& operator /=(U rhs);

     template<typename U>

     friend CheckedInt<U> operator %(const CheckedInt<U>& lhs,

                                     const CheckedInt<U>& rhs);

     template<typename U>

     CheckedInt& operator %=(U rhs);

     CheckedInt operator -() const

     {

       return detail::NegateImpl<T>::negate(*this);

     }

     /**

      * @returns true if the left and right hand sides are valid

      * and have the same value.

      *

      * Note that these semantics are the reason why we don't offer

      * a operator!=. Indeed, we'd want to have a!=b be equivalent to !(a==b)

      * but that would mean that whenever a or b is invalid, a!=b

      * is always true, which would be very confusing.

      *

      * For similar reasons, operators <, >, <=, >= would be very tricky to

      * specify, so we just avoid offering them.

      *

      * Notice that these == semantics are made more reasonable by these facts:

      *  1. a==b implies equality at the raw data level

      *     (the converse is false, as a==b is never true among invalids)

      *  2. This is similar to the behavior of IEEE floats, where a==b

      *     means that a and b have the same value *and* neither is NaN.

      */

     bool operator ==(const CheckedInt& other) const

     {

       return mIsValid && other.mIsValid && mValue == other.mValue;

     }

     /** prefix ++ */

     CheckedInt& operator++()

     {

       *this += 1;

       return *this;

     }

     /** postfix ++ */

     CheckedInt operator++(int)

     {

       CheckedInt tmp = *this;

       *this += 1;

       return tmp;

     }

     /** prefix -- */

     CheckedInt& operator--()

     {

       *this -= 1;

       return *this;

     }

     /** postfix -- */

     CheckedInt operator--(int)

     {

       CheckedInt tmp = *this;

       *this -= 1;

       return tmp;

     }

   private:

     /**

      * The !=, <, <=, >, >= operators are disabled:

      * see the comment on operator==.

      */

     template<typename U>

     bool operator !=(U other) const MOZ_DELETE;

     template<typename U>

     bool operator <(U other) const MOZ_DELETE;

     template<typename U>

     bool operator <=(U other) const MOZ_DELETE;

     template<typename U>

     bool operator >(U other) const MOZ_DELETE;

     template<typename U>

     bool operator >=(U other) const MOZ_DELETE;

 };

 #define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)                \

 template<typename T>                                                  \

 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \

                                  const CheckedInt<T> &rhs)            \

 {                                                                     \

   if (!detail::Is##NAME##Valid(lhs.mValue, rhs.mValue))               \

     return CheckedInt<T>(0, false);                                   \

                                                                       \

   return CheckedInt<T>(lhs.mValue OP rhs.mValue,                      \

                        lhs.mIsValid && rhs.mIsValid);                 \

 }

 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Add, +)

 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Sub, -)

 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Mul, *)

 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Div, /)

 MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(Mod, %)

 #undef MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR

 // Implement castToCheckedInt<T>(x), making sure that

 //  - it allows x to be either a CheckedInt<T> or any integer type

 //    that can be casted to T

 //  - if x is already a CheckedInt<T>, we just return a reference to it,

 //    instead of copying it (optimization)

 namespace detail {

 template<typename T, typename U>

 struct CastToCheckedIntImpl

 {

     typedef CheckedInt<T> ReturnType;

     static CheckedInt<T> run(U u) { return u; }

 };

 template<typename T>

 struct CastToCheckedIntImpl<T, CheckedInt<T> >

 {

     typedef const CheckedInt<T>& ReturnType;

     static const CheckedInt<T>& run(const CheckedInt<T>& u) { return u; }

 };

 } // namespace detail

 template<typename T, typename U>

 inline typename detail::CastToCheckedIntImpl<T, U>::ReturnType

 castToCheckedInt(U u)

 {

   static_assert(detail::IsSupported<T>::value &&

                 detail::IsSupported<U>::value,

                 "This type is not supported by CheckedInt");

   return detail::CastToCheckedIntImpl<T, U>::run(u);

 }

 #define MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP)  \

 template<typename T>                                              \

 template<typename U>                                              \

 CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(U rhs)         \

 {                                                                 \

   *this = *this OP castToCheckedInt<T>(rhs);                      \

   return *this;                                                   \

 }                                                                 \

 template<typename T, typename U>                                  \

 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, U rhs) \

 {                                                                 \

   return lhs OP castToCheckedInt<T>(rhs);                         \

 }                                                                 \

 template<typename T, typename U>                                  \

 inline CheckedInt<T> operator OP(U lhs, const CheckedInt<T> &rhs) \

 {                                                                 \

   return castToCheckedInt<T>(lhs) OP rhs;                         \

 }

 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=)

 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=)

 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=)

 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=)

 MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(%, %=)

 #undef MOZ_CHECKEDINT_CONVENIENCE_BINARY_OPERATORS

 template<typename T, typename U>

 inline bool

 operator ==(const CheckedInt<T> &lhs, U rhs)

 {

   return lhs == castToCheckedInt<T>(rhs);

 }

 template<typename T, typename U>

 inline bool

 operator ==(U  lhs, const CheckedInt<T> &rhs)

 {

   return castToCheckedInt<T>(lhs) == rhs;

 }

 // Convenience typedefs.

 typedef CheckedInt<int8_t>   CheckedInt8;

 typedef CheckedInt<uint8_t>  CheckedUint8;

 typedef CheckedInt<int16_t>  CheckedInt16;

 typedef CheckedInt<uint16_t> CheckedUint16;

 typedef CheckedInt<int32_t>  CheckedInt32;

 typedef CheckedInt<uint32_t> CheckedUint32;

 typedef CheckedInt<int64_t>  CheckedInt64;

 typedef CheckedInt<uint64_t> CheckedUint64;

 } // namespace mozilla

 #endif /* mozilla_CheckedInt_h */