2010-07-02 Zhenyao Mo <zmo@google.com>
[WebKit.git] / WebCore / html / canvas / CheckedInt.h
1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
3 /* ***** BEGIN LICENSE BLOCK *****
4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5  *
6  * The contents of this file are subject to the Mozilla Public License Version
7  * 1.1 (the "License"); you may not use this file except in compliance with
8  * the License. You may obtain a copy of the License at
9  * http://www.mozilla.org/MPL/
10  *
11  * Software distributed under the License is distributed on an "AS IS" basis,
12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13  * for the specific language governing rights and limitations under the
14  * License.
15  *
16  * The Original Code is Mozilla code.
17  *
18  * The Initial Developer of the Original Code is the Mozilla Corporation.
19  * Portions created by the Initial Developer are Copyright (C) 2009
20  * the Initial Developer. All Rights Reserved.
21  *
22  * Contributor(s):
23  *  Benoit Jacob <bjacob@mozilla.com>
24  *  Jeff Muizelaar <jmuizelaar@mozilla.com>
25  *
26  * Alternatively, the contents of this file may be used under the terms of
27  * either the GNU General Public License Version 2 or later (the "GPL"), or
28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29  * in which case the provisions of the GPL or the LGPL are applicable instead
30  * of those above. If you wish to allow use of your version of this file only
31  * under the terms of either the GPL or the LGPL, and not to allow others to
32  * use your version of this file under the terms of the MPL, indicate your
33  * decision by deleting the provisions above and replace them with the notice
34  * and other provisions required by the GPL or the LGPL. If you do not delete
35  * the provisions above, a recipient may use your version of this file under
36  * the terms of any one of the MPL, the GPL or the LGPL.
37  *
38  * ***** END LICENSE BLOCK ***** */
39
40 // Necessary modifications are made to the original CheckedInt.h file to remove
41 // dependencies on prtypes.
42 // Also, change define Mozilla_CheckedInt_h to CheckedInt_h, change namespace
43 // from mozilla to WebCore for easier usage.
44
45 #ifndef CheckedInt_h
46 #define CheckedInt_h
47
48 #include <climits>
49
50 namespace WebCore {
51
52 namespace CheckedInt_internal {
53
54 /* we don't want to use std::numeric_limits here because int... types may not support it,
55  * depending on the platform, e.g. on certain platform they use nonstandard built-in types
56  */
57
58 /*** Step 1: manually record information for all the types that we want to support
59  ***/
60
61 struct unsupported_type {};
62
63 template<typename T> struct integer_type_manually_recorded_info
64 {
65     enum { is_supported = 0 };
66     typedef unsupported_type twice_bigger_type;
67 };
68
69
70 #define CHECKEDINT_REGISTER_SUPPORTED_TYPE(T,_twice_bigger_type)  \
71 template<> struct integer_type_manually_recorded_info<T>       \
72 {                                                              \
73     enum { is_supported = 1 };                                 \
74     typedef _twice_bigger_type twice_bigger_type;              \
75     static void TYPE_NOT_SUPPORTED_BY_CheckedInt() {}             \
76 };
77
78 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int8_t,   int16_t)
79 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint8_t,  uint16_t)
80 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int16_t,  int32_t)
81 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint16_t, uint32_t)
82 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int32_t,  int64_t)
83 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint32_t, uint64_t)
84 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int64_t,  unsupported_type)
85 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint64_t, unsupported_type)
86
87
88 /*** Step 2: record some info about a given integer type,
89  ***         including whether it is supported, whether a twice bigger integer type
90  ***         is supported, what that twice bigger type is, and some stuff as found
91  ***         in std::numeric_limits (which we don't use because int.. types may
92  ***         not support it, if they are defined directly from compiler built-in types).
93  ***/
94
95 template<typename T> struct is_unsupported_type { enum { answer = 0 }; };
96 template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; };
97
98 template<typename T> struct integer_traits
99 {
100     typedef typename integer_type_manually_recorded_info<T>::twice_bigger_type twice_bigger_type;
101
102     enum {
103         is_supported = integer_type_manually_recorded_info<T>::is_supported,
104         twice_bigger_type_is_supported
105             = is_unsupported_type<
106                   typename integer_type_manually_recorded_info<T>::twice_bigger_type
107               >::answer ? 0 : 1,
108         size = sizeof(T),
109         position_of_sign_bit = CHAR_BIT * size - 1,
110         is_signed = (T(-1) > T(0)) ? 0 : 1
111     };
112
113     static T min()
114     {
115         // bitwise ops may return a larger type, that's why we cast explicitly to T
116         return is_signed ? T(T(1) << position_of_sign_bit) : T(0);
117     }
118
119     static T max()
120     {
121         return ~min();
122     }
123 };
124
125 /*** Step 3: Implement the actual validity checks --- ideas taken from IntegerLib, code different.
126  ***/
127
128 // bitwise ops may return a larger type, so it's good to use these inline helpers guaranteeing that
129 // the result is really of type T
130
131 template<typename T> inline T has_sign_bit(T x)
132 {
133     return x >> integer_traits<T>::position_of_sign_bit;
134 }
135
136 template<typename T> inline T binary_complement(T x)
137 {
138     return ~x;
139 }
140
141 template<typename T, typename U,
142          bool is_T_signed = integer_traits<T>::is_signed,
143          bool is_U_signed = integer_traits<U>::is_signed>
144 struct is_in_range_impl {};
145
146 template<typename T, typename U>
147 struct is_in_range_impl<T, U, true, true>
148 {
149     static T run(U x)
150     {
151         return (x <= integer_traits<T>::max()) &
152                (x >= integer_traits<T>::min());
153     }
154 };
155
156 template<typename T, typename U>
157 struct is_in_range_impl<T, U, false, false>
158 {
159     static T run(U x)
160     {
161         return x <= integer_traits<T>::max();
162     }
163 };
164
165 template<typename T, typename U>
166 struct is_in_range_impl<T, U, true, false>
167 {
168     static T run(U x)
169     {
170         if (sizeof(T) > sizeof(U))
171             return 1;
172         else
173             return x <= U(integer_traits<T>::max());
174     }
175 };
176
177 template<typename T, typename U>
178 struct is_in_range_impl<T, U, false, true>
179 {
180     static T run(U x)
181     {
182         if (sizeof(T) >= sizeof(U))
183             return x >= 0;
184         else
185             return x >= 0 && x <= U(integer_traits<T>::max());
186     }
187 };
188
189 template<typename T, typename U> inline T is_in_range(U x)
190 {
191     return is_in_range_impl<T, U>::run(x);
192 }
193
194 template<typename T> inline T is_add_valid(T x, T y, T result)
195 {
196     return integer_traits<T>::is_signed ?
197                         // addition is valid if the sign of x+y is equal to either that of x or that of y.
198                         // Beware! These bitwise operations can return a larger integer type, if T was a
199                         // small type like int8, so we explicitly cast to T.
200                         has_sign_bit(binary_complement(T((result^x) & (result^y))))
201                     :
202                         binary_complement(x) >= y;
203 }
204
205 template<typename T> inline T is_sub_valid(T x, T y, T result)
206 {
207     return integer_traits<T>::is_signed ?
208                         // substraction is valid if either x and y have same sign, or x-y and x have same sign
209                         has_sign_bit(binary_complement(T((result^x) & (x^y))))
210                     :
211                         x >= y;
212 }
213
214 template<typename T,
215          bool is_signed =  integer_traits<T>::is_signed,
216          bool twice_bigger_type_is_supported = integer_traits<T>::twice_bigger_type_is_supported>
217 struct is_mul_valid_impl {};
218
219 template<typename T>
220 struct is_mul_valid_impl<T, true, true>
221 {
222     static T run(T x, T y)
223     {
224         typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type;
225         twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y);
226         return is_in_range<T>(product);
227     }
228 };
229
230 template<typename T>
231 struct is_mul_valid_impl<T, false, true>
232 {
233     static T run(T x, T y)
234     {
235         typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type;
236         twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y);
237         return is_in_range<T>(product);
238     }
239 };
240
241 template<typename T>
242 struct is_mul_valid_impl<T, true, false>
243 {
244     static T run(T x, T y)
245     {
246         const T max_value = integer_traits<T>::max();
247         const T min_value = integer_traits<T>::min();
248
249         if (x == 0 || y == 0) return true;
250
251         if (x > 0) {
252             if (y > 0)
253                 return x <= max_value / y;
254             else
255                 return y >= min_value / x;
256         } else {
257             if (y > 0)
258                 return x >= min_value / y;
259             else
260                 return y >= max_value / x;
261         }
262     }
263 };
264
265 template<typename T>
266 struct is_mul_valid_impl<T, false, false>
267 {
268     static T run(T x, T y)
269     {
270         const T max_value = integer_traits<T>::max();
271         if (x == 0 || y == 0) return true;
272         return x <= max_value / y;
273     }
274 };
275
276 template<typename T> inline T is_mul_valid(T x, T y, T /*result not used*/)
277 {
278     return is_mul_valid_impl<T>::run(x, y);
279 }
280
281 template<typename T> inline T is_div_valid(T x, T y)
282 {
283     return integer_traits<T>::is_signed ?
284                         // keep in mind that min/-1 is invalid because abs(min)>max
285                         y != 0 && (x != integer_traits<T>::min() || y != T(-1))
286                     :
287                         y != 0;
288 }
289
290 } // end namespace CheckedInt_internal
291
292
293 /*** Step 4: Now define the CheckedInt class.
294  ***/
295
296 /** \class CheckedInt
297   * \brief Integer wrapper class checking for integer overflow and other errors
298   * \param T the integer type to wrap. Can be any of int8_t, uint8_t, int16_t, uint16_t,
299   *          int32_t, uint32_t, int64_t, uint64_t.
300   *
301   * This class implements guarded integer arithmetic. Do a computation, then check that
302   * valid() returns true, you then have a guarantee that no problem, such as integer overflow,
303   * happened during this computation.
304   *
305   * The arithmetic operators in this class are guaranteed not to crash your app
306   * in case of a division by zero.
307   *
308   * For example, suppose that you want to implement a function that computes (x+y)/z,
309   * that doesn't crash if z==0, and that reports on error (divide by zero or integer overflow).
310   * You could code it as follows:
311     \code
312     bool compute_x_plus_y_over_z(int32_t x, int32_t y, int32_t z, int32_t *result)
313     {
314         CheckedInt<int32_t> checked_result = (CheckedInt<int32_t>(x) + y) / z;
315         *result = checked_result.value();
316         return checked_result.valid();
317     }
318     \endcode
319   *
320   * Implicit conversion from plain integers to checked integers is allowed. The plain integer
321   * is checked to be in range before being casted to the destination type. This means that the following
322   * lines all compile, and the resulting CheckedInts are correctly detected as valid or invalid:
323   * \code
324     CheckedInt<uint8_t> x(1);   // 1 is of type int, is found to be in range for uint8_t, x is valid
325     CheckedInt<uint8_t> x(-1);  // -1 is of type int, is found not to be in range for uint8_t, x is invalid
326     CheckedInt<int8_t> x(-1);   // -1 is of type int, is found to be in range for int8_t, x is valid
327     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
328     CheckedInt<int32_t> x(uint32_t(123456789)); // 3123456789 is of type uint32_t, is found not to be in range
329                                              // for int32_t, x is invalid
330   * \endcode
331   * Implicit conversion from
332   * checked integers to plain integers is not allowed. As shown in the
333   * above example, to get the value of a checked integer as a normal integer, call value().
334   *
335   * Arithmetic operations between checked and plain integers is allowed; the result type
336   * is the type of the checked integer.
337   *
338   * Safe integers of different types cannot be used in the same arithmetic expression.
339   */
340 template<typename T>
341 class CheckedInt
342 {
343 protected:
344     T mValue;
345     T mIsValid; // stored as a T to limit the number of integer conversions when
346                 // evaluating nested arithmetic expressions.
347
348     template<typename U>
349     CheckedInt(const U& value, bool isValid) : mValue(value), mIsValid(isValid)
350     {
351         CheckedInt_internal::integer_type_manually_recorded_info<T>
352             ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
353     }
354
355 public:
356     /** Constructs a checked integer with given \a value. The checked integer is initialized as valid or invalid
357       * depending on whether the \a value is in range.
358       *
359       * This constructor is not explicit. Instead, the type of its argument is a separate template parameter,
360       * ensuring that no conversion is performed before this constructor is actually called.
361       * As explained in the above documentation for class CheckedInt, this constructor checks that its argument is
362       * valid.
363       */
364     template<typename U>
365     CheckedInt(const U& value)
366         : mValue(value),
367           mIsValid(CheckedInt_internal::is_in_range<T>(value))
368     {
369         CheckedInt_internal::integer_type_manually_recorded_info<T>
370             ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
371     }
372
373     /** Constructs a valid checked integer with uninitialized value */
374     CheckedInt() : mIsValid(1)
375     {
376         CheckedInt_internal::integer_type_manually_recorded_info<T>
377             ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
378     }
379
380     /** \returns the actual value */
381     T value() const { return mValue; }
382
383     /** \returns true if the checked integer is valid, i.e. is not the result
384       * of an invalid operation or of an operation involving an invalid checked integer
385       */
386     bool valid() const { return mIsValid; }
387
388     /** \returns the sum. Checks for overflow. */
389     template<typename U> friend CheckedInt<U> operator +(const CheckedInt<U>& lhs, const CheckedInt<U>& rhs);
390     /** Adds. Checks for overflow. \returns self reference */
391     template<typename U> CheckedInt& operator +=(const U &rhs);
392     /** \returns the difference. Checks for overflow. */
393     template<typename U> friend CheckedInt<U> operator -(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
394     /** Substracts. Checks for overflow. \returns self reference */
395     template<typename U> CheckedInt& operator -=(const U &rhs);
396     /** \returns the product. Checks for overflow. */
397     template<typename U> friend CheckedInt<U> operator *(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
398     /** Multiplies. Checks for overflow. \returns self reference */
399     template<typename U> CheckedInt& operator *=(const U &rhs);
400     /** \returns the quotient. Checks for overflow and for divide-by-zero. */
401     template<typename U> friend CheckedInt<U> operator /(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs);
402     /** Divides. Checks for overflow and for divide-by-zero. \returns self reference */
403     template<typename U> CheckedInt& operator /=(const U &rhs);
404
405     /** \returns the opposite value. Checks for overflow. */
406     CheckedInt operator -() const
407     {
408         T result = -value();
409         /* give the compiler a good chance to perform RVO */
410         return CheckedInt(result,
411                        mIsValid & CheckedInt_internal::is_sub_valid(T(0), value(), result));
412     }
413
414     /** \returns true if the left and right hand sides are valid and have the same value. */
415     bool operator ==(const CheckedInt& other) const
416     {
417         return bool(mIsValid & other.mIsValid & T(value() == other.value()));
418     }
419
420 private:
421     /** operator!= is disabled. Indeed: (a!=b) should be the same as !(a==b) but that
422       * would mean that if a or b is invalid, (a!=b) is always true, which is very tricky.
423       */
424     template<typename U>
425     bool operator !=(const U& other) const { return !(*this == other); }
426 };
427
428 #define CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)               \
429 template<typename T>                                          \
430 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs) \
431 {                                                             \
432     T x = lhs.value();                                        \
433     T y = rhs.value();                                        \
434     T result = x OP y;                                        \
435     T is_op_valid                                             \
436         = CheckedInt_internal::is_##NAME##_valid(x, y, result);  \
437     /* give the compiler a good chance to perform RVO */      \
438     return CheckedInt<T>(result,                                 \
439                       lhs.mIsValid &                          \
440                       rhs.mIsValid &                          \
441                       is_op_valid);                           \
442 }
443
444 CHECKEDINT_BASIC_BINARY_OPERATOR(add, +)
445 CHECKEDINT_BASIC_BINARY_OPERATOR(sub, -)
446 CHECKEDINT_BASIC_BINARY_OPERATOR(mul, *)
447
448 // division can't be implemented by CHECKEDINT_BASIC_BINARY_OPERATOR
449 // because if rhs == 0, we are not allowed to even try to compute the quotient.
450 template<typename T>
451 inline CheckedInt<T> operator /(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs)
452 {
453     T x = lhs.value();
454     T y = rhs.value();
455     T is_op_valid = CheckedInt_internal::is_div_valid(x, y);
456     T result = is_op_valid ? (x / y) : 0;
457     /* give the compiler a good chance to perform RVO */
458     return CheckedInt<T>(result,
459                       lhs.mIsValid &
460                       rhs.mIsValid &
461                       is_op_valid);
462 }
463
464 // implement cast_to_CheckedInt<T>(x), making sure that
465 //  - it allows x to be either a CheckedInt<T> or any integer type that can be casted to T
466 //  - if x is already a CheckedInt<T>, we just return a reference to it, instead of copying it (optimization)
467
468 template<typename T, typename U>
469 struct cast_to_CheckedInt_impl
470 {
471     typedef CheckedInt<T> return_type;
472     static CheckedInt<T> run(const U& u) { return u; }
473 };
474
475 template<typename T>
476 struct cast_to_CheckedInt_impl<T, CheckedInt<T> >
477 {
478     typedef const CheckedInt<T>& return_type;
479     static const CheckedInt<T>& run(const CheckedInt<T>& u) { return u; }
480 };
481
482 template<typename T, typename U>
483 inline typename cast_to_CheckedInt_impl<T, U>::return_type
484 cast_to_CheckedInt(const U& u)
485 {
486     return cast_to_CheckedInt_impl<T, U>::run(u);
487 }
488
489 #define CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP) \
490 template<typename T>                                          \
491 template<typename U>                                          \
492 CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(const U &rhs)    \
493 {                                                             \
494     *this = *this OP cast_to_CheckedInt<T>(rhs);                 \
495     return *this;                                             \
496 }                                                             \
497 template<typename T, typename U>                              \
498 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const U &rhs) \
499 {                                                             \
500     return lhs OP cast_to_CheckedInt<T>(rhs);                    \
501 }                                                             \
502 template<typename T, typename U>                              \
503 inline CheckedInt<T> operator OP(const U & lhs, const CheckedInt<T> &rhs) \
504 {                                                             \
505     return cast_to_CheckedInt<T>(lhs) OP rhs;                    \
506 }
507
508 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=)
509 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=)
510 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=)
511 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=)
512
513 template<typename T, typename U>
514 inline bool operator ==(const CheckedInt<T> &lhs, const U &rhs)
515 {
516     return lhs == cast_to_CheckedInt<T>(rhs);
517 }
518
519 template<typename T, typename U>
520 inline bool operator ==(const U & lhs, const CheckedInt<T> &rhs)
521 {
522     return cast_to_CheckedInt<T>(lhs) == rhs;
523 }
524
525 } // end namespace WebCore
526
527 #endif /* CheckedInt_h */