b=555798; add CheckedInt class; r=jmuizelaar, r=vladimir
authorBenoit Jacob <bjacob@mozilla.com>
Wed, 30 Jun 2010 11:53:41 -0400
changeset 46445 c6b9defb1972b4ec3dd0e174686dfcda4da37635
parent 46444 f2b92415cef33d8f4124db18e50aae5d72e24707
child 46446 d5d4a04727a41b6fba56e2d5b978fe638ade3cb1
push id14191
push userbjacob@mozilla.com
push dateWed, 30 Jun 2010 15:54:52 +0000
treeherdermozilla-central@c6b9defb1972 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjmuizelaar, vladimir
bugs555798
milestone2.0b2pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
b=555798; add CheckedInt class; r=jmuizelaar, r=vladimir
xpcom/ds/CheckedInt.h
xpcom/ds/Makefile.in
xpcom/tests/Makefile.in
xpcom/tests/TestCheckedInt.cpp
new file mode 100644
--- /dev/null
+++ b/xpcom/ds/CheckedInt.h
@@ -0,0 +1,524 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et cindent: */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla code.
+ *
+ * The Initial Developer of the Original Code is the Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Benoit Jacob <bjacob@mozilla.com>
+ *  Jeff Muizelaar <jmuizelaar@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef mozilla_CheckedInt_h
+#define mozilla_CheckedInt_h
+
+#include "prtypes.h"
+
+#include <climits>
+
+namespace mozilla {
+
+namespace CheckedInt_internal {
+
+/* we don't want to use std::numeric_limits here because PRInt... types may not support it,
+ * depending on the platform, e.g. on certain platform they use nonstandard built-in types
+ */
+
+/*** Step 1: manually record information for all the types that we want to support
+ ***/
+
+struct unsupported_type {};
+
+template<typename T> struct integer_type_manually_recorded_info
+{
+    enum { is_supported = 0 };
+    typedef unsupported_type twice_bigger_type;
+};
+
+
+#define CHECKEDINT_REGISTER_SUPPORTED_TYPE(T,_twice_bigger_type)  \
+template<> struct integer_type_manually_recorded_info<T>       \
+{                                                              \
+    enum { is_supported = 1 };                                 \
+    typedef _twice_bigger_type twice_bigger_type;              \
+    static void TYPE_NOT_SUPPORTED_BY_CheckedInt() {}             \
+};
+
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt8,   PRInt16)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint8,  PRUint16)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt16,  PRInt32)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint16, PRUint32)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt32,  PRInt64)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint32, PRUint64)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt64,  unsupported_type)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint64, unsupported_type)
+
+
+/*** Step 2: record some info about a given integer type,
+ ***         including whether it is supported, whether a twice bigger integer type
+ ***         is supported, what that twice bigger type is, and some stuff as found
+ ***         in std::numeric_limits (which we don't use because PRInt.. types may
+ ***         not support it, if they are defined directly from compiler built-in types).
+ ***/
+
+template<typename T> struct is_unsupported_type { enum { answer = 0 }; };
+template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; };
+
+template<typename T> struct integer_traits
+{
+    typedef typename integer_type_manually_recorded_info<T>::twice_bigger_type twice_bigger_type;
+
+    enum {
+        is_supported = integer_type_manually_recorded_info<T>::is_supported,
+        twice_bigger_type_is_supported
+            = is_unsupported_type<
+                  typename integer_type_manually_recorded_info<T>::twice_bigger_type
+              >::answer ? 0 : 1,
+        size = sizeof(T),
+        position_of_sign_bit = CHAR_BIT * size - 1,
+        is_signed = (T(-1) > T(0)) ? 0 : 1
+    };
+
+    static T min()
+    {
+        // bitwise ops may return a larger type, that's why we cast explicitly to T
+        return is_signed ? T(T(1) << position_of_sign_bit) : T(0);
+    }
+
+    static T max()
+    {
+        return ~min();
+    }
+};
+
+/*** Step 3: Implement the actual validity checks --- ideas taken from IntegerLib, code different.
+ ***/
+
+// bitwise ops may return a larger type, so it's good to use these inline helpers guaranteeing that
+// the result is really of type T
+
+template<typename T> inline T has_sign_bit(T x)
+{
+    return x >> integer_traits<T>::position_of_sign_bit;
+}
+
+template<typename T> inline T binary_complement(T x)
+{
+    return ~x;
+}
+
+template<typename T, typename U,
+         bool is_T_signed = integer_traits<T>::is_signed,
+         bool is_U_signed = integer_traits<U>::is_signed>
+struct is_in_range_impl {};
+
+template<typename T, typename U>
+struct is_in_range_impl<T, U, true, true>
+{
+    static T run(U x)
+    {
+        return (x <= integer_traits<T>::max()) &
+               (x >= integer_traits<T>::min());
+    }
+};
+
+template<typename T, typename U>
+struct is_in_range_impl<T, U, false, false>
+{
+    static T run(U x)
+    {
+        return x <= integer_traits<T>::max();
+    }
+};
+
+template<typename T, typename U>
+struct is_in_range_impl<T, U, true, false>
+{
+    static T run(U x)
+    {
+        if (sizeof(T) > sizeof(U))
+            return 1;
+        else
+            return x <= U(integer_traits<T>::max());
+    }
+};
+
+template<typename T, typename U>
+struct is_in_range_impl<T, U, false, true>
+{
+    static T run(U x)
+    {
+        if (sizeof(T) >= sizeof(U))
+            return x >= 0;
+        else
+            return x >= 0 && x <= U(integer_traits<T>::max());
+    }
+};
+
+template<typename T, typename U> inline T is_in_range(U x)
+{
+    return is_in_range_impl<T, U>::run(x);
+}
+
+template<typename T> inline T is_add_valid(T x, T y, T result)
+{
+    return integer_traits<T>::is_signed ?
+                        // addition is valid if the sign of x+y is equal to either that of x or that of y.
+                        // Beware! These bitwise operations can return a larger integer type, if T was a
+                        // small type like int8, so we explicitly cast to T.
+                        has_sign_bit(binary_complement(T((result^x) & (result^y))))
+                    :
+                        binary_complement(x) >= y;
+}
+
+template<typename T> inline T is_sub_valid(T x, T y, T result)
+{
+    return integer_traits<T>::is_signed ?
+                        // substraction is valid if either x and y have same sign, or x-y and x have same sign
+                        has_sign_bit(binary_complement(T((result^x) & (x^y))))
+                    :
+                        x >= y;
+}
+
+template<typename T,
+         bool is_signed =  integer_traits<T>::is_signed,
+         bool twice_bigger_type_is_supported = integer_traits<T>::twice_bigger_type_is_supported>
+struct is_mul_valid_impl {};
+
+template<typename T>
+struct is_mul_valid_impl<T, true, true>
+{
+    static T run(T x, T y)
+    {
+        typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type;
+        twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y);
+        return is_in_range<T>(product);
+    }
+};
+
+template<typename T>
+struct is_mul_valid_impl<T, false, true>
+{
+    static T run(T x, T y)
+    {
+        typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type;
+        twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y);
+        return is_in_range<T>(product);
+    }
+};
+
+template<typename T>
+struct is_mul_valid_impl<T, true, false>
+{
+    static T run(T x, T y)
+    {
+        const T max_value = integer_traits<T>::max();
+        const T min_value = integer_traits<T>::min();
+
+        if (x == 0 || y == 0) return true;
+
+        if (x > 0) {
+            if (y > 0)
+                return x <= max_value / y;
+            else
+                return y >= min_value / x;
+        } else {
+            if (y > 0)
+                return x >= min_value / y;
+            else
+                return y >= max_value / x;
+        }
+    }
+};
+
+template<typename T>
+struct is_mul_valid_impl<T, false, false>
+{
+    static T run(T x, T y)
+    {
+        const T max_value = integer_traits<T>::max();
+        if (x == 0 || y == 0) return true;
+        return x <= max_value / y;
+    }
+};
+
+template<typename T> inline T is_mul_valid(T x, T y, T /*result not used*/)
+{
+    return is_mul_valid_impl<T>::run(x, y);
+}
+
+template<typename T> inline T is_div_valid(T x, T y)
+{
+    return integer_traits<T>::is_signed ?
+                        // keep in mind that min/-1 is invalid because abs(min)>max
+                        y != 0 && (x != integer_traits<T>::min() || y != T(-1))
+                    :
+                        y != 0;
+}
+
+} // end namespace CheckedInt_internal
+
+
+/*** Step 4: 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 of PRInt8, PRUint8, PRInt16, PRUint16,
+  *          PRInt32, PRUint32, PRInt64, PRUint64.
+  *
+  * This class implements guarded integer arithmetic. Do a computation, then check that
+  * valid() returns true, you then have a guarantee that no problem, such as integer overflow,
+  * happened during this computation.
+  *
+  * The arithmetic operators in this class are guaranteed not to crash your app
+  * 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
+    PRBool compute_x_plus_y_over_z(PRInt32 x, PRInt32 y, PRInt32 z, PRInt32 *result)
+    {
+        CheckedInt<PRInt32> checked_result = (CheckedInt<PRInt32>(x) + y) / z;
+        *result = checked_result.value();
+        return checked_result.valid();
+    }
+    \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
+    CheckedInt<PRUint8> x(1);   // 1 is of type int, is found to be in range for PRUint8, x is valid
+    CheckedInt<PRUint8> x(-1);  // -1 is of type int, is found not to be in range for PRUint8, x is invalid
+    CheckedInt<PRInt8> x(-1);   // -1 is of type int, is found to be in range for PRInt8, x is valid
+    CheckedInt<PRInt8> x(PRInt16(1000)); // 1000 is of type PRInt16, is found not to be in range for PRInt8, x is invalid
+    CheckedInt<PRInt32> x(PRUint32(123456789)); // 3123456789 is of type PRUint32, is found not to be in range
+                                             // for PRInt32, x is invalid
+  * \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.
+  *
+  * Safe integers of different types cannot be used in the same arithmetic expression.
+  */
+template<typename T>
+class CheckedInt
+{
+protected:
+    T mValue;
+    T mIsValid; // stored as a T to limit the number of integer conversions when
+                // evaluating nested arithmetic expressions.
+
+    template<typename U>
+    CheckedInt(const U& value, PRBool isValid) : mValue(value), mIsValid(isValid)
+    {
+        CheckedInt_internal::integer_type_manually_recorded_info<T>
+            ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
+    }
+
+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(const U& value)
+        : mValue(value),
+          mIsValid(CheckedInt_internal::is_in_range<T>(value))
+    {
+        CheckedInt_internal::integer_type_manually_recorded_info<T>
+            ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
+    }
+
+    /** Constructs a valid checked integer with uninitialized value */
+    CheckedInt() : mIsValid(1)
+    {
+        CheckedInt_internal::integer_type_manually_recorded_info<T>
+            ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
+    }
+
+    /** \returns the actual value */
+    T value() const { return mValue; }
+
+    /** \returns PR_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
+      */
+    PRBool valid() const { return mIsValid; }
+
+    /** \returns the sum. Checks for overflow. */
+    template<typename U> friend CheckedInt<U> operator +(const CheckedInt<U>& lhs, const CheckedInt<U>& rhs);
+    /** Adds. Checks for overflow. \returns self reference */
+    template<typename U> CheckedInt& operator +=(const U &rhs);
+    /** \returns the difference. Checks for overflow. */
+    template<typename U> friend CheckedInt<U> operator -(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
+    /** Substracts. Checks for overflow. \returns self reference */
+    template<typename U> CheckedInt& operator -=(const U &rhs);
+    /** \returns the product. Checks for overflow. */
+    template<typename U> friend CheckedInt<U> operator *(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
+    /** Multiplies. Checks for overflow. \returns self reference */
+    template<typename U> CheckedInt& operator *=(const U &rhs);
+    /** \returns the quotient. Checks for overflow and for divide-by-zero. */
+    template<typename U> friend CheckedInt<U> operator /(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
+    /** Divides. Checks for overflow and for divide-by-zero. \returns self reference */
+    template<typename U> CheckedInt& operator /=(const U &rhs);
+
+    /** \returns the opposite value. Checks for overflow. */
+    CheckedInt operator -() const
+    {
+        T result = -value();
+        /* give the compiler a good chance to perform RVO */
+        return CheckedInt(result,
+                       mIsValid & CheckedInt_internal::is_sub_valid(T(0), value(), result));
+    }
+
+    /** \returns true if the left and right hand sides are valid and have the same value. */
+    PRBool operator ==(const CheckedInt& other) const
+    {
+        return PRBool(mIsValid & other.mIsValid & T(value() == other.value()));
+    }
+
+private:
+    /** operator!= is disabled. Indeed: (a!=b) should be the same as !(a==b) but that
+      * would mean that if a or b is invalid, (a!=b) is always true, which is very tricky.
+      */
+    template<typename U>
+    PRBool operator !=(const U& other) const { return !(*this == other); }
+};
+
+#define CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)               \
+template<typename T>                                          \
+inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs) \
+{                                                             \
+    T x = lhs.value();                                        \
+    T y = rhs.value();                                        \
+    T result = x OP y;                                        \
+    T is_op_valid                                             \
+        = CheckedInt_internal::is_##NAME##_valid(x, y, result);  \
+    /* give the compiler a good chance to perform RVO */      \
+    return CheckedInt<T>(result,                                 \
+                      lhs.mIsValid &                          \
+                      rhs.mIsValid &                          \
+                      is_op_valid);                           \
+}
+
+CHECKEDINT_BASIC_BINARY_OPERATOR(add, +)
+CHECKEDINT_BASIC_BINARY_OPERATOR(sub, -)
+CHECKEDINT_BASIC_BINARY_OPERATOR(mul, *)
+
+// division can't be implemented by CHECKEDINT_BASIC_BINARY_OPERATOR
+// because if rhs == 0, we are not allowed to even try to compute the quotient.
+template<typename T>
+inline CheckedInt<T> operator /(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs)
+{
+    T x = lhs.value();
+    T y = rhs.value();
+    T is_op_valid = CheckedInt_internal::is_div_valid(x, y);
+    T result = is_op_valid ? (x / y) : 0;
+    /* give the compiler a good chance to perform RVO */
+    return CheckedInt<T>(result,
+                      lhs.mIsValid &
+                      rhs.mIsValid &
+                      is_op_valid);
+}
+
+// implement cast_to_CheckedInt<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)
+
+template<typename T, typename U>
+struct cast_to_CheckedInt_impl
+{
+    typedef CheckedInt<T> return_type;
+    static CheckedInt<T> run(const U& u) { return u; }
+};
+
+template<typename T>
+struct cast_to_CheckedInt_impl<T, CheckedInt<T> >
+{
+    typedef const CheckedInt<T>& return_type;
+    static const CheckedInt<T>& run(const CheckedInt<T>& u) { return u; }
+};
+
+template<typename T, typename U>
+inline typename cast_to_CheckedInt_impl<T, U>::return_type
+cast_to_CheckedInt(const U& u)
+{
+    return cast_to_CheckedInt_impl<T, U>::run(u);
+}
+
+#define CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP) \
+template<typename T>                                          \
+template<typename U>                                          \
+CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(const U &rhs)    \
+{                                                             \
+    *this = *this OP cast_to_CheckedInt<T>(rhs);                 \
+    return *this;                                             \
+}                                                             \
+template<typename T, typename U>                              \
+inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const U &rhs) \
+{                                                             \
+    return lhs OP cast_to_CheckedInt<T>(rhs);                    \
+}                                                             \
+template<typename T, typename U>                              \
+inline CheckedInt<T> operator OP(const U & lhs, const CheckedInt<T> &rhs) \
+{                                                             \
+    return cast_to_CheckedInt<T>(lhs) OP rhs;                    \
+}
+
+CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=)
+CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=)
+CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=)
+CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=)
+
+template<typename T, typename U>
+inline PRBool operator ==(const CheckedInt<T> &lhs, const U &rhs)
+{
+    return lhs == cast_to_CheckedInt<T>(rhs);
+}
+
+template<typename T, typename U>
+inline PRBool operator ==(const U & lhs, const CheckedInt<T> &rhs)
+{
+    return cast_to_CheckedInt<T>(lhs) == rhs;
+}
+
+} // end namespace mozilla
+
+#endif /* mozilla_CheckedInt_h */
--- a/xpcom/ds/Makefile.in
+++ b/xpcom/ds/Makefile.in
@@ -109,16 +109,17 @@ EXPORTS		= \
 		nsSupportsArray.h \
 		nsSupportsPrimitives.h \
 		nsTime.h \
 		nsVariant.h \
 		nsStringEnumerator.h \
 		nsHashPropertyBag.h \
 		nsWhitespaceTokenizer.h \
 		nsCharSeparatedTokenizer.h \
+		CheckedInt.h \
 		$(NULL)			
 
 XPIDLSRCS	= \
 		nsIAtom.idl \
 		nsIAtomService.idl \
 		nsICollection.idl \
 		nsIEnumerator.idl \
 		nsIINIParser.idl \
--- a/xpcom/tests/Makefile.in
+++ b/xpcom/tests/Makefile.in
@@ -96,16 +96,17 @@ CPP_UNIT_TESTS = \
                  TestHashtables.cpp \
                  TestID.cpp \
                  TestObserverArray.cpp \
                  TestObserverService.cpp \
                  TestPipe.cpp \
                  TestRefPtr.cpp \
                  TestServMgr.cpp \
                  TestTextFormatter.cpp \
+                 TestCheckedInt.cpp \
                  $(NULL)
 
 ifndef MOZ_ENABLE_LIBXUL
 CPP_UNIT_TESTS += \
                   TestArray.cpp \
                   TestCRT.cpp \
                   TestDeque.cpp \
                   TestEncoding.cpp \
new file mode 100644
--- /dev/null
+++ b/xpcom/tests/TestCheckedInt.cpp
@@ -0,0 +1,455 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim:set ts=2 sw=2 sts=2 et cindent: */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla code.
+ *
+ * The Initial Developer of the Original Code is the Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2009
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *  Benoit Jacob <bjacob@mozilla.com>
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+
+#include "CheckedInt.h"
+#include <iostream>
+
+namespace CheckedInt_test {
+
+using namespace mozilla::CheckedInt_internal;
+using mozilla::CheckedInt;
+
+int g_tests_passed = 0;
+int g_tests_failed = 0;
+
+void verify_impl_function(bool x, bool expected,
+                          const char* file, int line,
+                          int T_size, bool T_is_signed)
+{
+    if (x == expected) {
+        g_tests_passed++;
+    } else {
+        g_tests_failed++;
+        std::cerr << "Test failed at " << file << ":" << line;
+        std::cerr << " with T a ";
+        if(T_is_signed)
+            std::cerr << "signed";
+        else
+            std::cerr << "unsigned";
+        std::cerr << " " << CHAR_BIT*T_size << "-bit integer type" << std::endl;
+    }
+}
+
+#define VERIFY_IMPL(x, expected) \
+    verify_impl_function((x), (expected), __FILE__, __LINE__, sizeof(T), integer_traits<T>::is_signed)
+
+#define VERIFY(x)            VERIFY_IMPL(x, true)
+#define VERIFY_IS_FALSE(x)   VERIFY_IMPL(x, false)
+#define VERIFY_IS_VALID(x)   VERIFY_IMPL((x).valid(), PR_TRUE)
+#define VERIFY_IS_INVALID(x) VERIFY_IMPL((x).valid(), PR_FALSE)
+#define VERIFY_IS_VALID_IF(x,condition) VERIFY_IMPL((x).valid(), (condition))
+
+template<typename T, unsigned int size = sizeof(T)>
+struct test_twice_bigger_type
+{
+    static void run()
+    {
+        VERIFY(integer_traits<T>::twice_bigger_type_is_supported);
+        VERIFY(sizeof(typename integer_traits<T>::twice_bigger_type)
+                    == 2 * sizeof(T));
+        VERIFY(bool(integer_traits<
+                    typename integer_traits<T>::twice_bigger_type
+                >::is_signed) == bool(integer_traits<T>::is_signed));
+    }
+};
+
+template<typename T>
+struct test_twice_bigger_type<T, 8>
+{
+    static void run()
+    {
+        VERIFY_IS_FALSE(integer_traits<T>::twice_bigger_type_is_supported);
+    }
+};
+
+
+template<typename T>
+void test()
+{
+    static bool already_run = false;
+    if (already_run) {
+        g_tests_failed++;
+        std::cerr << "You already tested this type. Copy/paste typo??" << std::endl;
+        return;
+    }
+    already_run = true;
+
+    VERIFY(integer_traits<T>::is_supported);
+    VERIFY(integer_traits<T>::size == sizeof(T));
+    enum{ is_signed = integer_traits<T>::is_signed };
+    VERIFY(bool(is_signed) == !bool(T(-1) > T(0)));
+
+    test_twice_bigger_type<T>::run();
+
+    CheckedInt<T> max_value(integer_traits<T>::max());
+    CheckedInt<T> min_value(integer_traits<T>::min());
+
+    // check min() and max(), since they are custom implementations and a mistake there
+    // could potentially NOT be caught by any other tests... while making everything wrong!
+
+    T bit = 1;
+    for(unsigned int i = 0; i < sizeof(T) * CHAR_BIT - 1; i++)
+    {
+        VERIFY((min_value.value() & bit) == 0);
+        bit <<= 1;
+    }
+    VERIFY((min_value.value() & bit) == (is_signed ? bit : T(0)));
+    VERIFY(max_value.value() == T(~(min_value.value())));
+
+    CheckedInt<T> zero(0);
+    CheckedInt<T> one(1);
+    CheckedInt<T> two(2);
+    CheckedInt<T> three(3);
+    CheckedInt<T> four(4);
+
+    /* addition / substraction checks */
+
+    VERIFY_IS_VALID(zero+zero);
+    VERIFY(zero+zero == zero);
+    VERIFY_IS_FALSE(zero+zero == one); // check that == doesn't always return true
+    VERIFY_IS_VALID(zero+one);
+    VERIFY(zero+one == one);
+    VERIFY_IS_VALID(one+one);
+    VERIFY(one+one == two);
+
+    CheckedInt<T> max_value_minus_one = max_value - one;
+    CheckedInt<T> max_value_minus_two = max_value - two;
+    VERIFY_IS_VALID(max_value_minus_one);
+    VERIFY_IS_VALID(max_value_minus_two);
+    VERIFY_IS_VALID(max_value_minus_one + one);
+    VERIFY_IS_VALID(max_value_minus_two + one);
+    VERIFY_IS_VALID(max_value_minus_two + two);
+    VERIFY(max_value_minus_one + one == max_value);
+    VERIFY(max_value_minus_two + one == max_value_minus_one);
+    VERIFY(max_value_minus_two + two == max_value);
+
+    VERIFY_IS_VALID(max_value + zero);
+    VERIFY_IS_VALID(max_value - zero);
+    VERIFY_IS_INVALID(max_value + one);
+    VERIFY_IS_INVALID(max_value + two);
+    VERIFY_IS_INVALID(max_value + max_value_minus_one);
+    VERIFY_IS_INVALID(max_value + max_value);
+
+    CheckedInt<T> min_value_plus_one = min_value + one;
+    CheckedInt<T> min_value_plus_two = min_value + two;
+    VERIFY_IS_VALID(min_value_plus_one);
+    VERIFY_IS_VALID(min_value_plus_two);
+    VERIFY_IS_VALID(min_value_plus_one - one);
+    VERIFY_IS_VALID(min_value_plus_two - one);
+    VERIFY_IS_VALID(min_value_plus_two - two);
+    VERIFY(min_value_plus_one - one == min_value);
+    VERIFY(min_value_plus_two - one == min_value_plus_one);
+    VERIFY(min_value_plus_two - two == min_value);
+
+    CheckedInt<T> min_value_minus_one = min_value - one;
+    VERIFY_IS_VALID(min_value + zero);
+    VERIFY_IS_VALID(min_value - zero);
+    VERIFY_IS_INVALID(min_value - one);
+    VERIFY_IS_INVALID(min_value - two);
+    VERIFY_IS_INVALID(min_value - min_value_minus_one);
+    VERIFY_IS_VALID(min_value - min_value);
+
+    CheckedInt<T> max_value_over_two = max_value / two;
+    VERIFY_IS_VALID(max_value_over_two + max_value_over_two);
+    VERIFY_IS_VALID(max_value_over_two + one);
+    VERIFY((max_value_over_two + one) - one == max_value_over_two);
+    VERIFY_IS_VALID(max_value_over_two - max_value_over_two);
+    VERIFY(max_value_over_two - max_value_over_two == zero);
+
+    CheckedInt<T> min_value_over_two = min_value / two;
+    VERIFY_IS_VALID(min_value_over_two + min_value_over_two);
+    VERIFY_IS_VALID(min_value_over_two + one);
+    VERIFY((min_value_over_two + one) - one == min_value_over_two);
+    VERIFY_IS_VALID(min_value_over_two - min_value_over_two);
+    VERIFY(min_value_over_two - min_value_over_two == zero);
+
+    VERIFY_IS_INVALID(min_value - one);
+    VERIFY_IS_INVALID(min_value - two);
+
+    if (is_signed) {
+        VERIFY_IS_INVALID(min_value + min_value);
+        VERIFY_IS_INVALID(min_value_over_two + min_value_over_two + min_value_over_two);
+        VERIFY_IS_INVALID(zero - min_value + min_value);
+        VERIFY_IS_INVALID(one - min_value + min_value);
+    }
+
+    /* unary operator- checks */
+
+    CheckedInt<T> neg_one = -one;
+    CheckedInt<T> neg_two = -two;
+
+    if (is_signed) {
+        VERIFY_IS_VALID(-max_value);
+        VERIFY_IS_VALID(-max_value - one);
+        VERIFY_IS_VALID(neg_one);
+        VERIFY_IS_VALID(-max_value + neg_one);
+        VERIFY_IS_VALID(neg_one + one);
+        VERIFY(neg_one + one == zero);
+        VERIFY_IS_VALID(neg_two);
+        VERIFY_IS_VALID(neg_one + neg_one);
+        VERIFY(neg_one + neg_one == neg_two);
+    } else {
+        VERIFY_IS_INVALID(neg_one);
+    }
+
+    /* multiplication checks */
+
+    VERIFY_IS_VALID(zero*zero);
+    VERIFY(zero*zero == zero);
+    VERIFY_IS_VALID(zero*one);
+    VERIFY(zero*one == zero);
+    VERIFY_IS_VALID(one*zero);
+    VERIFY(one*zero == zero);
+    VERIFY_IS_VALID(one*one);
+    VERIFY(one*one == one);
+    VERIFY_IS_VALID(one*three);
+    VERIFY(one*three == three);
+    VERIFY_IS_VALID(two*two);
+    VERIFY(two*two == four);
+
+    VERIFY_IS_INVALID(max_value * max_value);
+    VERIFY_IS_INVALID(max_value_over_two * max_value);
+    VERIFY_IS_INVALID(max_value_over_two * max_value_over_two);
+
+    CheckedInt<T> max_value_approx_sqrt(T(T(1) << (CHAR_BIT*sizeof(T)/2)));
+
+    VERIFY_IS_VALID(max_value_approx_sqrt);
+    VERIFY_IS_VALID(max_value_approx_sqrt * two);
+    VERIFY_IS_INVALID(max_value_approx_sqrt * max_value_approx_sqrt);
+    VERIFY_IS_INVALID(max_value_approx_sqrt * max_value_approx_sqrt * max_value_approx_sqrt);
+
+    if (is_signed) {
+        VERIFY_IS_INVALID(min_value * min_value);
+        VERIFY_IS_INVALID(min_value_over_two * min_value);
+        VERIFY_IS_INVALID(min_value_over_two * min_value_over_two);
+
+        CheckedInt<T> min_value_approx_sqrt = -max_value_approx_sqrt;
+
+        VERIFY_IS_VALID(min_value_approx_sqrt);
+        VERIFY_IS_VALID(min_value_approx_sqrt * two);
+        VERIFY_IS_INVALID(min_value_approx_sqrt * max_value_approx_sqrt);
+        VERIFY_IS_INVALID(min_value_approx_sqrt * min_value_approx_sqrt);
+    }
+
+    // make sure to check all 4 paths in signed multiplication validity check.
+    // test positive * positive
+    VERIFY_IS_VALID(max_value * one);
+    VERIFY(max_value * one == max_value);
+    VERIFY_IS_INVALID(max_value * two);
+    VERIFY_IS_VALID(max_value_over_two * two);
+    VERIFY((max_value_over_two + max_value_over_two) == (max_value_over_two * two));
+
+    if (is_signed) {
+        // test positive * negative
+        VERIFY_IS_VALID(max_value * neg_one);
+        VERIFY_IS_VALID(-max_value);
+        VERIFY(max_value * neg_one == -max_value);
+        VERIFY_IS_VALID(one * min_value);
+        VERIFY_IS_INVALID(max_value * neg_two);
+        VERIFY_IS_VALID(max_value_over_two * neg_two);
+        VERIFY_IS_VALID(two * min_value_over_two);
+        VERIFY_IS_VALID((max_value_over_two + one) * neg_two);
+        VERIFY_IS_INVALID((max_value_over_two + two) * neg_two);
+        VERIFY_IS_INVALID(two * (min_value_over_two - one));
+
+        // test negative * positive
+        VERIFY_IS_VALID(min_value * one);
+        VERIFY_IS_VALID(min_value_plus_one * one);
+        VERIFY_IS_INVALID(min_value * two);
+        VERIFY_IS_VALID(min_value_over_two * two);
+        VERIFY(min_value_over_two * two == min_value);
+        VERIFY_IS_INVALID((min_value_over_two - one) * neg_two);
+        VERIFY_IS_INVALID(neg_two * max_value);
+        VERIFY_IS_VALID(min_value_over_two * two);
+        VERIFY(min_value_over_two * two == min_value);
+        VERIFY_IS_VALID(neg_two * max_value_over_two);
+        VERIFY_IS_INVALID((min_value_over_two - one) * two);
+        VERIFY_IS_VALID(neg_two * (max_value_over_two + one));
+        VERIFY_IS_INVALID(neg_two * (max_value_over_two + two));
+
+        // test negative * negative
+        VERIFY_IS_INVALID(min_value * neg_one);
+        VERIFY_IS_VALID(min_value_plus_one * neg_one);
+        VERIFY(min_value_plus_one * neg_one == max_value);
+        VERIFY_IS_INVALID(min_value * neg_two);
+        VERIFY_IS_INVALID(min_value_over_two * neg_two);
+        VERIFY_IS_INVALID(neg_one * min_value);
+        VERIFY_IS_VALID(neg_one * min_value_plus_one);
+        VERIFY(neg_one * min_value_plus_one == max_value);
+        VERIFY_IS_INVALID(neg_two * min_value);
+        VERIFY_IS_INVALID(neg_two * min_value_over_two);
+    }
+
+    /* division checks */
+
+    VERIFY_IS_VALID(one / one);
+    VERIFY(one / one == one);
+    VERIFY_IS_VALID(three / three);
+    VERIFY(three / three == one);
+    VERIFY_IS_VALID(four / two);
+    VERIFY(four / two == two);
+    VERIFY((four*three)/four == three);
+
+    // check that div by zero is invalid
+    VERIFY_IS_INVALID(zero / zero);
+    VERIFY_IS_INVALID(one / zero);
+    VERIFY_IS_INVALID(two / zero);
+    VERIFY_IS_INVALID(neg_one / zero);
+    VERIFY_IS_INVALID(max_value / zero);
+    VERIFY_IS_INVALID(min_value / zero);
+
+    if (is_signed) {
+        // check that min_value / -1 is invalid
+        VERIFY_IS_INVALID(min_value / neg_one);
+
+        // check that the test for div by -1 isn't banning other numerators than min_value
+        VERIFY_IS_VALID(one / neg_one);
+        VERIFY_IS_VALID(zero / neg_one);
+        VERIFY_IS_VALID(neg_one / neg_one);
+        VERIFY_IS_VALID(max_value / neg_one);
+    }
+
+    /* check that invalidity is correctly preserved by arithmetic ops */
+
+    CheckedInt<T> some_invalid = max_value + max_value;
+    VERIFY_IS_INVALID(some_invalid + zero);
+    VERIFY_IS_INVALID(some_invalid - zero);
+    VERIFY_IS_INVALID(zero + some_invalid);
+    VERIFY_IS_INVALID(zero - some_invalid);
+    VERIFY_IS_INVALID(-some_invalid);
+    VERIFY_IS_INVALID(some_invalid * zero);
+    VERIFY_IS_INVALID(some_invalid * one);
+    VERIFY_IS_INVALID(zero * some_invalid);
+    VERIFY_IS_INVALID(one * some_invalid);
+    VERIFY_IS_INVALID(some_invalid / zero);
+    VERIFY_IS_INVALID(some_invalid / one);
+    VERIFY_IS_INVALID(zero / some_invalid);
+    VERIFY_IS_INVALID(one / some_invalid);
+    VERIFY_IS_INVALID(some_invalid + some_invalid);
+    VERIFY_IS_INVALID(some_invalid - some_invalid);
+    VERIFY_IS_INVALID(some_invalid * some_invalid);
+    VERIFY_IS_INVALID(some_invalid / some_invalid);
+
+    /* check that mixing checked integers with plain integers in expressions is allowed */
+
+    VERIFY(one + T(2) == three);
+    VERIFY(2 + one == three);
+    {
+        CheckedInt<T> x = one;
+        x += 2;
+        VERIFY(x == three);
+    }
+    VERIFY(two - 1 == one);
+    VERIFY(2 - one == one);
+    {
+        CheckedInt<T> x = two;
+        x -= 1;
+        VERIFY(x == one);
+    }
+    VERIFY(one * 2 == two);
+    VERIFY(2 * one == two);
+    {
+        CheckedInt<T> x = one;
+        x *= 2;
+        VERIFY(x == two);
+    }
+    VERIFY(four / 2 == two);
+    VERIFY(4 / two == two);
+    {
+        CheckedInt<T> x = four;
+        x /= 2;
+        VERIFY(x == two);
+    }
+
+    VERIFY(one == 1);
+    VERIFY(1 == one);
+    VERIFY_IS_FALSE(two == 1);
+    VERIFY_IS_FALSE(1 == two);
+    VERIFY_IS_FALSE(some_invalid == 1);
+    VERIFY_IS_FALSE(1 == some_invalid);
+
+    /* Check that construction of CheckedInt from an integer value of a mismatched type is checked */
+
+    #define VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(U) \
+    { \
+        bool is_U_signed = integer_traits<U>::is_signed; \
+        VERIFY_IS_VALID(CheckedInt<T>(U(0))); \
+        VERIFY_IS_VALID(CheckedInt<T>(U(1))); \
+        VERIFY_IS_VALID(CheckedInt<T>(U(100))); \
+        if (is_U_signed) \
+            VERIFY_IS_VALID_IF(CheckedInt<T>(U(-1)), is_signed); \
+        if (sizeof(U) > sizeof(T)) \
+            VERIFY_IS_INVALID(CheckedInt<T>(U(integer_traits<T>::max())+1)); \
+        VERIFY_IS_VALID_IF(CheckedInt<T>(integer_traits<U>::max()), \
+            (sizeof(T) > sizeof(U) || ((sizeof(T) == sizeof(U)) && (is_U_signed || !is_signed)))); \
+        VERIFY_IS_VALID_IF(CheckedInt<T>(integer_traits<U>::min()), \
+            is_U_signed == false ? 1 : \
+            bool(is_signed) == false ? 0 : \
+            sizeof(T) >= sizeof(U)); \
+    }
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRInt8)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRUint8)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRInt16)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRUint16)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRInt32)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRUint32)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRInt64)
+    VERIFY_CONSTRUCTION_FROM_INTEGER_TYPE(PRUint64)
+}
+
+} // end namespace CheckedInt_test
+
+int main()
+{
+    CheckedInt_test::test<PRInt8>();
+    CheckedInt_test::test<PRUint8>();
+    CheckedInt_test::test<PRInt16>();
+    CheckedInt_test::test<PRUint16>();
+    CheckedInt_test::test<PRInt32>();
+    CheckedInt_test::test<PRUint32>();
+    CheckedInt_test::test<PRInt64>();
+    CheckedInt_test::test<PRUint64>();
+
+    std::cerr << CheckedInt_test::g_tests_failed << " tests failed, "
+              << CheckedInt_test::g_tests_passed << " tests passed out of "
+              << CheckedInt_test::g_tests_failed + CheckedInt_test::g_tests_passed
+              << " tests." << std::endl;
+
+    return CheckedInt_test::g_tests_failed > 0;
+}