--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/html/canvas/CheckedInt.h Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,527 @@
+/* -*- 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 ***** */
+
+// Necessary modifications are made to the original CheckedInt.h file to remove
+// dependencies on prtypes.
+// Also, change define Mozilla_CheckedInt_h to CheckedInt_h, change namespace
+// from mozilla to WebCore for easier usage.
+
+#ifndef CheckedInt_h
+#define CheckedInt_h
+
+#include <climits>
+
+namespace WebCore {
+
+namespace CheckedInt_internal {
+
+/* we don't want to use std::numeric_limits here because int... 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(int8_t, int16_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint8_t, uint16_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(int16_t, int32_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint16_t, uint32_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(int32_t, int64_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint32_t, uint64_t)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(int64_t, unsupported_type)
+CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint64_t, 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 int.. 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 int8_t, uint8_t, int16_t, uint16_t,
+ * int32_t, uint32_t, int64_t, uint64_t.
+ *
+ * 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
+ bool compute_x_plus_y_over_z(int32_t x, int32_t y, int32_t z, int32_t *result)
+ {
+ CheckedInt<int32_t> checked_result = (CheckedInt<int32_t>(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<uint8_t> x(1); // 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<int8_t> x(-1); // -1 is of type int, is found to be in range for int8_t, x is valid
+ CheckedInt<int8_t> x(int16_t(1000)); // 1000 is of type int16_t, is found not to be in range for int8_t, x is invalid
+ CheckedInt<int32_t> x(uint32_t(123456789)); // 3123456789 is of type uint32_t, is found not to be in range
+ // for int32_t, 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, bool 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 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 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. */
+ bool operator ==(const CheckedInt& other) const
+ {
+ return bool(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>
+ bool 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 bool operator ==(const CheckedInt<T> &lhs, const U &rhs)
+{
+ return lhs == cast_to_CheckedInt<T>(rhs);
+}
+
+template<typename T, typename U>
+inline bool operator ==(const U & lhs, const CheckedInt<T> &rhs)
+{
+ return cast_to_CheckedInt<T>(lhs) == rhs;
+}
+
+} // end namespace WebCore
+
+#endif /* CheckedInt_h */