diff options
Diffstat (limited to 'Source/WebCore/html/canvas/CheckedInt.h')
| -rw-r--r-- | Source/WebCore/html/canvas/CheckedInt.h | 527 |
1 files changed, 527 insertions, 0 deletions
diff --git a/Source/WebCore/html/canvas/CheckedInt.h b/Source/WebCore/html/canvas/CheckedInt.h new file mode 100644 index 0000000..861e8e6 --- /dev/null +++ b/Source/WebCore/html/canvas/CheckedInt.h @@ -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 */ |