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
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/
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
16 * The Original Code is Mozilla code.
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.
23 * Benoit Jacob <bjacob@mozilla.com>
24 * Jeff Muizelaar <jmuizelaar@mozilla.com>
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.
38 * ***** END LICENSE BLOCK ***** */
40 #ifndef mozilla_CheckedInt_h
41 #define mozilla_CheckedInt_h
49 namespace CheckedInt_internal
{
51 /* we don't want to use std::numeric_limits here because PRInt... types may not support it,
52 * depending on the platform, e.g. on certain platforms they use nonstandard built-in types
55 /*** Step 1: manually record information for all the types that we want to support
58 struct unsupported_type
{};
60 template<typename T
> struct integer_type_manually_recorded_info
62 enum { is_supported
= 0 };
63 typedef unsupported_type twice_bigger_type
;
64 typedef unsupported_type unsigned_type
;
68 #define CHECKEDINT_REGISTER_SUPPORTED_TYPE(T,_twice_bigger_type,_unsigned_type) \
69 template<> struct integer_type_manually_recorded_info<T> \
71 enum { is_supported = 1 }; \
72 typedef _twice_bigger_type twice_bigger_type; \
73 typedef _unsigned_type unsigned_type; \
74 static void TYPE_NOT_SUPPORTED_BY_CheckedInt() {} \
77 // Type Twice Bigger Type Unsigned Type
78 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt8
, PRInt16
, PRUint8
)
79 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint8
, PRUint16
, PRUint8
)
80 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt16
, PRInt32
, PRUint16
)
81 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint16
, PRUint32
, PRUint16
)
82 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt32
, PRInt64
, PRUint32
)
83 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint32
, PRUint64
, PRUint32
)
84 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRInt64
, unsupported_type
, PRUint64
)
85 CHECKEDINT_REGISTER_SUPPORTED_TYPE(PRUint64
, unsupported_type
, PRUint64
)
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 PRInt.. types may
92 *** not support it, if they are defined directly from compiler built-in types).
93 *** We use function names min_value() and max_value() instead of min() and max()
94 *** because of stupid min/max macros in Windows headers.
97 template<typename T
> struct is_unsupported_type
{ enum { answer
= 0 }; };
98 template<> struct is_unsupported_type
<unsupported_type
> { enum { answer
= 1 }; };
100 template<typename T
> struct integer_traits
102 typedef typename integer_type_manually_recorded_info
<T
>::twice_bigger_type twice_bigger_type
;
103 typedef typename integer_type_manually_recorded_info
<T
>::unsigned_type unsigned_type
;
106 is_supported
= integer_type_manually_recorded_info
<T
>::is_supported
,
107 twice_bigger_type_is_supported
108 = is_unsupported_type
<
109 typename integer_type_manually_recorded_info
<T
>::twice_bigger_type
112 position_of_sign_bit
= CHAR_BIT
* size
- 1,
113 is_signed
= (T(-1) > T(0)) ? 0 : 1
118 // bitwise ops may return a larger type, that's why we cast explicitly to T
119 // in C++, left bit shifts on signed values is undefined by the standard unless the shifted value is representable.
120 // notice that signed-to-unsigned conversions are always well-defined in the standard,
121 // as the value congruent to 2^n as expected. By contrast, unsigned-to-signed is only well-defined if the value is
123 return is_signed
? T(unsigned_type(1) << position_of_sign_bit
) : T(0);
132 /*** Step 3: Implement the actual validity checks --- ideas taken from IntegerLib, code different.
135 // bitwise ops may return a larger type, so it's good to use these inline helpers guaranteeing that
136 // the result is really of type T
138 template<typename T
> inline T
has_sign_bit(T x
)
140 // in C++, right bit shifts on negative values is undefined by the standard.
141 // notice that signed-to-unsigned conversions are always well-defined in the standard,
142 // as the value congruent modulo 2^n as expected. By contrast, unsigned-to-signed is only well-defined if the value is
143 // representable. Here the unsigned-to-signed conversion is OK because the value (the result of the shift) is 0 or 1.
144 typedef typename integer_traits
<T
>::unsigned_type unsigned_T
;
145 return T(unsigned_T(x
) >> integer_traits
<T
>::position_of_sign_bit
);
148 template<typename T
> inline T
binary_complement(T x
)
153 template<typename T
, typename U
,
154 bool is_T_signed
= integer_traits
<T
>::is_signed
,
155 bool is_U_signed
= integer_traits
<U
>::is_signed
>
156 struct is_in_range_impl
{};
158 template<typename T
, typename U
>
159 struct is_in_range_impl
<T
, U
, true, true>
163 return (x
<= integer_traits
<T
>::max_value()) &&
164 (x
>= integer_traits
<T
>::min_value());
168 template<typename T
, typename U
>
169 struct is_in_range_impl
<T
, U
, false, false>
173 return x
<= integer_traits
<T
>::max_value();
177 template<typename T
, typename U
>
178 struct is_in_range_impl
<T
, U
, true, false>
182 if (sizeof(T
) > sizeof(U
))
185 return x
<= U(integer_traits
<T
>::max_value());
189 template<typename T
, typename U
>
190 struct is_in_range_impl
<T
, U
, false, true>
194 if (sizeof(T
) >= sizeof(U
))
197 return (x
>= 0) && (x
<= U(integer_traits
<T
>::max_value()));
201 template<typename T
, typename U
> inline T
is_in_range(U x
)
203 return is_in_range_impl
<T
, U
>::run(x
);
206 template<typename T
> inline T
is_add_valid(T x
, T y
, T result
)
208 return integer_traits
<T
>::is_signed
?
209 // addition is valid if the sign of x+y is equal to either that of x or that of y.
210 // Beware! These bitwise operations can return a larger integer type, if T was a
211 // small type like int8, so we explicitly cast to T.
212 has_sign_bit(binary_complement(T((result
^x
) & (result
^y
))))
214 binary_complement(x
) >= y
;
217 template<typename T
> inline T
is_sub_valid(T x
, T y
, T result
)
219 return integer_traits
<T
>::is_signed
?
220 // substraction is valid if either x and y have same sign, or x-y and x have same sign
221 has_sign_bit(binary_complement(T((result
^x
) & (x
^y
))))
227 bool is_signed
= integer_traits
<T
>::is_signed
,
228 bool twice_bigger_type_is_supported
= integer_traits
<T
>::twice_bigger_type_is_supported
>
229 struct is_mul_valid_impl
{};
231 template<typename T
, bool is_signed
>
232 struct is_mul_valid_impl
<T
, is_signed
, true>
234 static T
run(T x
, T y
)
236 typedef typename integer_traits
<T
>::twice_bigger_type twice_bigger_type
;
237 twice_bigger_type product
= twice_bigger_type(x
) * twice_bigger_type(y
);
238 return is_in_range
<T
>(product
);
243 struct is_mul_valid_impl
<T
, true, false>
245 static T
run(T x
, T y
)
247 const T max_value
= integer_traits
<T
>::max_value();
248 const T min_value
= integer_traits
<T
>::min_value();
250 if (x
== 0 || y
== 0) return true;
254 return x
<= max_value
/ y
;
256 return y
>= min_value
/ x
;
259 return x
>= min_value
/ y
;
261 return y
>= max_value
/ x
;
267 struct is_mul_valid_impl
<T
, false, false>
269 static T
run(T x
, T y
)
271 const T max_value
= integer_traits
<T
>::max_value();
272 if (x
== 0 || y
== 0) return true;
273 return x
<= max_value
/ y
;
277 template<typename T
> inline T
is_mul_valid(T x
, T y
, T
/*result not used*/)
279 return is_mul_valid_impl
<T
>::run(x
, y
);
282 template<typename T
> inline T
is_div_valid(T x
, T y
)
284 return integer_traits
<T
>::is_signed
?
285 // keep in mind that min/-1 is invalid because abs(min)>max
286 (y
!= 0) && (x
!= integer_traits
<T
>::min_value() || y
!= T(-1))
291 // this is just to shut up msvc warnings about negating unsigned ints.
292 template<typename T
, bool is_signed
= integer_traits
<T
>::is_signed
>
293 struct opposite_if_signed_impl
295 static T
run(T x
) { return -x
; }
298 struct opposite_if_signed_impl
<T
, false>
300 static T
run(T x
) { return x
; }
303 inline T
opposite_if_signed(T x
) { return opposite_if_signed_impl
<T
>::run(x
); }
307 } // end namespace CheckedInt_internal
310 /*** Step 4: Now define the CheckedInt class.
313 /** \class CheckedInt
314 * \brief Integer wrapper class checking for integer overflow and other errors
315 * \param T the integer type to wrap. Can be any of PRInt8, PRUint8, PRInt16, PRUint16,
316 * PRInt32, PRUint32, PRInt64, PRUint64.
318 * This class implements guarded integer arithmetic. Do a computation, check that
319 * valid() returns true, you then have a guarantee that no problem, such as integer overflow,
320 * happened during this computation.
322 * The arithmetic operators in this class are guaranteed not to crash your app
323 * in case of a division by zero.
325 * For example, suppose that you want to implement a function that computes (x+y)/z,
326 * that doesn't crash if z==0, and that reports on error (divide by zero or integer overflow).
327 * You could code it as follows:
329 PRBool compute_x_plus_y_over_z(PRInt32 x, PRInt32 y, PRInt32 z, PRInt32 *result)
331 CheckedInt<PRInt32> checked_result = (CheckedInt<PRInt32>(x) + y) / z;
332 *result = checked_result.value();
333 return checked_result.valid();
337 * Implicit conversion from plain integers to checked integers is allowed. The plain integer
338 * is checked to be in range before being casted to the destination type. This means that the following
339 * lines all compile, and the resulting CheckedInts are correctly detected as valid or invalid:
341 CheckedInt<PRUint8> x(1); // 1 is of type int, is found to be in range for PRUint8, x is valid
342 CheckedInt<PRUint8> x(-1); // -1 is of type int, is found not to be in range for PRUint8, x is invalid
343 CheckedInt<PRInt8> x(-1); // -1 is of type int, is found to be in range for PRInt8, x is valid
344 CheckedInt<PRInt8> x(PRInt16(1000)); // 1000 is of type PRInt16, is found not to be in range for PRInt8, x is invalid
345 CheckedInt<PRInt32> x(PRUint32(3123456789)); // 3123456789 is of type PRUint32, is found not to be in range
346 // for PRInt32, x is invalid
348 * Implicit conversion from
349 * checked integers to plain integers is not allowed. As shown in the
350 * above example, to get the value of a checked integer as a normal integer, call value().
352 * Arithmetic operations between checked and plain integers is allowed; the result type
353 * is the type of the checked integer.
355 * Checked integers of different types cannot be used in the same arithmetic expression.
357 * There are convenience typedefs for all PR integer types, of the following form (these are just 2 examples):
359 typedef CheckedInt<PRInt32> CheckedInt32;
360 typedef CheckedInt<PRUint16> CheckedUint16;
368 T mIsValid
; // stored as a T to limit the number of integer conversions when
369 // evaluating nested arithmetic expressions.
372 CheckedInt(U value
, T isValid
) : mValue(value
), mIsValid(isValid
)
374 CheckedInt_internal::integer_type_manually_recorded_info
<T
>
375 ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
379 /** Constructs a checked integer with given \a value. The checked integer is initialized as valid or invalid
380 * depending on whether the \a value is in range.
382 * This constructor is not explicit. Instead, the type of its argument is a separate template parameter,
383 * ensuring that no conversion is performed before this constructor is actually called.
384 * As explained in the above documentation for class CheckedInt, this constructor checks that its argument is
390 mIsValid(CheckedInt_internal::is_in_range
<T
>(value
))
392 CheckedInt_internal::integer_type_manually_recorded_info
<T
>
393 ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
396 /** Constructs a valid checked integer with initial value 0 */
397 CheckedInt() : mValue(0), mIsValid(1)
399 CheckedInt_internal::integer_type_manually_recorded_info
<T
>
400 ::TYPE_NOT_SUPPORTED_BY_CheckedInt();
403 /** \returns the actual value */
404 T
value() const { return mValue
; }
406 /** \returns PR_TRUE if the checked integer is valid, i.e. is not the result
407 * of an invalid operation or of an operation involving an invalid checked integer
411 return PRBool(mIsValid
);
414 /** \returns the sum. Checks for overflow. */
415 template<typename U
> friend CheckedInt
<U
> operator +(const CheckedInt
<U
>& lhs
, const CheckedInt
<U
>& rhs
);
416 /** Adds. Checks for overflow. \returns self reference */
417 template<typename U
> CheckedInt
& operator +=(U rhs
);
418 /** \returns the difference. Checks for overflow. */
419 template<typename U
> friend CheckedInt
<U
> operator -(const CheckedInt
<U
>& lhs
, const CheckedInt
<U
> &rhs
);
420 /** Substracts. Checks for overflow. \returns self reference */
421 template<typename U
> CheckedInt
& operator -=(U rhs
);
422 /** \returns the product. Checks for overflow. */
423 template<typename U
> friend CheckedInt
<U
> operator *(const CheckedInt
<U
>& lhs
, const CheckedInt
<U
> &rhs
);
424 /** Multiplies. Checks for overflow. \returns self reference */
425 template<typename U
> CheckedInt
& operator *=(U rhs
);
426 /** \returns the quotient. Checks for overflow and for divide-by-zero. */
427 template<typename U
> friend CheckedInt
<U
> operator /(const CheckedInt
<U
>& lhs
, const CheckedInt
<U
> &rhs
);
428 /** Divides. Checks for overflow and for divide-by-zero. \returns self reference */
429 template<typename U
> CheckedInt
& operator /=(U rhs
);
431 /** \returns the opposite value. Checks for overflow. */
432 CheckedInt
operator -() const
434 // circumvent msvc warning about - applied to unsigned int.
435 // if we're unsigned, the only valid case anyway is 0 in which case - is a no-op.
436 T result
= CheckedInt_internal::opposite_if_signed(value());
437 /* give the compiler a good chance to perform RVO */
438 return CheckedInt(result
,
439 mIsValid
& CheckedInt_internal::is_sub_valid(T(0), value(), result
));
442 /** \returns true if the left and right hand sides are valid and have the same value. */
443 PRBool
operator ==(const CheckedInt
& other
) const
445 return PRBool(mIsValid
& other
.mIsValid
& (value() == other
.mValue
));
449 CheckedInt
& operator++()
456 CheckedInt
operator++(int)
458 CheckedInt tmp
= *this;
464 CheckedInt
& operator--()
471 CheckedInt
operator--(int)
473 CheckedInt tmp
= *this;
479 /** operator!= is disabled. Indeed, (a!=b) should be the same as !(a==b) but that
480 * would mean that if a or b is invalid, (a!=b) is always true, which is very tricky.
483 PRBool
operator !=(U other
) const { return !(*this == other
); }
486 #define CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP) \
487 template<typename T> \
488 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs) \
494 = CheckedInt_internal::is_##NAME##_valid(x, y, result); \
495 /* give the compiler a good chance to perform RVO */ \
496 return CheckedInt<T>(result, \
497 lhs.mIsValid & rhs.mIsValid & is_op_valid); \
500 CHECKEDINT_BASIC_BINARY_OPERATOR(add
, +)
501 CHECKEDINT_BASIC_BINARY_OPERATOR(sub
, -)
502 CHECKEDINT_BASIC_BINARY_OPERATOR(mul
, *)
504 // division can't be implemented by CHECKEDINT_BASIC_BINARY_OPERATOR
505 // because if rhs == 0, we are not allowed to even try to compute the quotient.
507 inline CheckedInt
<T
> operator /(const CheckedInt
<T
> &lhs
, const CheckedInt
<T
> &rhs
)
511 T is_op_valid
= CheckedInt_internal::is_div_valid(x
, y
);
512 T result
= is_op_valid
? (x
/ y
) : 0;
513 /* give the compiler a good chance to perform RVO */
514 return CheckedInt
<T
>(result
,
515 lhs
.mIsValid
& rhs
.mIsValid
& is_op_valid
);
518 // implement cast_to_CheckedInt<T>(x), making sure that
519 // - it allows x to be either a CheckedInt<T> or any integer type that can be casted to T
520 // - if x is already a CheckedInt<T>, we just return a reference to it, instead of copying it (optimization)
522 template<typename T
, typename U
>
523 struct cast_to_CheckedInt_impl
525 typedef CheckedInt
<T
> return_type
;
526 static CheckedInt
<T
> run(U u
) { return u
; }
530 struct cast_to_CheckedInt_impl
<T
, CheckedInt
<T
> >
532 typedef const CheckedInt
<T
>& return_type
;
533 static const CheckedInt
<T
>& run(const CheckedInt
<T
>& u
) { return u
; }
536 template<typename T
, typename U
>
537 inline typename cast_to_CheckedInt_impl
<T
, U
>::return_type
538 cast_to_CheckedInt(U u
)
540 return cast_to_CheckedInt_impl
<T
, U
>::run(u
);
543 #define CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP) \
544 template<typename T> \
545 template<typename U> \
546 CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(U rhs) \
548 *this = *this OP cast_to_CheckedInt<T>(rhs); \
551 template<typename T, typename U> \
552 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, U rhs) \
554 return lhs OP cast_to_CheckedInt<T>(rhs); \
556 template<typename T, typename U> \
557 inline CheckedInt<T> operator OP(U lhs, const CheckedInt<T> &rhs) \
559 return cast_to_CheckedInt<T>(lhs) OP rhs; \
562 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=)
563 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=)
564 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=)
565 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=)
567 template<typename T
, typename U
>
568 inline PRBool
operator ==(const CheckedInt
<T
> &lhs
, U rhs
)
570 return lhs
== cast_to_CheckedInt
<T
>(rhs
);
573 template<typename T
, typename U
>
574 inline PRBool
operator ==(U lhs
, const CheckedInt
<T
> &rhs
)
576 return cast_to_CheckedInt
<T
>(lhs
) == rhs
;
579 // convenience typedefs.
580 // the use of a macro here helps make sure that we don't let a typo slip into some of these.
581 #define CHECKEDINT_MAKE_TYPEDEF(Type) \
582 typedef CheckedInt<PR##Type> Checked##Type;
584 CHECKEDINT_MAKE_TYPEDEF(Int8
)
585 CHECKEDINT_MAKE_TYPEDEF(Uint8
)
586 CHECKEDINT_MAKE_TYPEDEF(Int16
)
587 CHECKEDINT_MAKE_TYPEDEF(Uint16
)
588 CHECKEDINT_MAKE_TYPEDEF(Int32
)
589 CHECKEDINT_MAKE_TYPEDEF(Uint32
)
590 CHECKEDINT_MAKE_TYPEDEF(Int64
)
591 CHECKEDINT_MAKE_TYPEDEF(Uint64
)
593 } // end namespace mozilla
595 #endif /* mozilla_CheckedInt_h */