CheckedInt.h revision cad810f21b803229eb11403f9209855525a25d57
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 50namespace WebCore { 51 52namespace 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 61struct unsupported_type {}; 62 63template<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) \ 71template<> 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 78CHECKEDINT_REGISTER_SUPPORTED_TYPE(int8_t, int16_t) 79CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint8_t, uint16_t) 80CHECKEDINT_REGISTER_SUPPORTED_TYPE(int16_t, int32_t) 81CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint16_t, uint32_t) 82CHECKEDINT_REGISTER_SUPPORTED_TYPE(int32_t, int64_t) 83CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint32_t, uint64_t) 84CHECKEDINT_REGISTER_SUPPORTED_TYPE(int64_t, unsupported_type) 85CHECKEDINT_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 95template<typename T> struct is_unsupported_type { enum { answer = 0 }; }; 96template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; }; 97 98template<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 131template<typename T> inline T has_sign_bit(T x) 132{ 133 return x >> integer_traits<T>::position_of_sign_bit; 134} 135 136template<typename T> inline T binary_complement(T x) 137{ 138 return ~x; 139} 140 141template<typename T, typename U, 142 bool is_T_signed = integer_traits<T>::is_signed, 143 bool is_U_signed = integer_traits<U>::is_signed> 144struct is_in_range_impl {}; 145 146template<typename T, typename U> 147struct 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 156template<typename T, typename U> 157struct 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 165template<typename T, typename U> 166struct 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 177template<typename T, typename U> 178struct 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 189template<typename T, typename U> inline T is_in_range(U x) 190{ 191 return is_in_range_impl<T, U>::run(x); 192} 193 194template<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 205template<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 214template<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> 217struct is_mul_valid_impl {}; 218 219template<typename T> 220struct 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 230template<typename T> 231struct 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 241template<typename T> 242struct 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 265template<typename T> 266struct 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 276template<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 281template<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 */ 340template<typename T> 341class CheckedInt 342{ 343protected: 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 355public: 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 420private: 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) \ 429template<typename T> \ 430inline 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 444CHECKEDINT_BASIC_BINARY_OPERATOR(add, +) 445CHECKEDINT_BASIC_BINARY_OPERATOR(sub, -) 446CHECKEDINT_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. 450template<typename T> 451inline 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 468template<typename T, typename U> 469struct cast_to_CheckedInt_impl 470{ 471 typedef CheckedInt<T> return_type; 472 static CheckedInt<T> run(const U& u) { return u; } 473}; 474 475template<typename T> 476struct 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 482template<typename T, typename U> 483inline typename cast_to_CheckedInt_impl<T, U>::return_type 484cast_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) \ 490template<typename T> \ 491template<typename U> \ 492CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(const U &rhs) \ 493{ \ 494 *this = *this OP cast_to_CheckedInt<T>(rhs); \ 495 return *this; \ 496} \ 497template<typename T, typename U> \ 498inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const U &rhs) \ 499{ \ 500 return lhs OP cast_to_CheckedInt<T>(rhs); \ 501} \ 502template<typename T, typename U> \ 503inline CheckedInt<T> operator OP(const U & lhs, const CheckedInt<T> &rhs) \ 504{ \ 505 return cast_to_CheckedInt<T>(lhs) OP rhs; \ 506} 507 508CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=) 509CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=) 510CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=) 511CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=) 512 513template<typename T, typename U> 514inline bool operator ==(const CheckedInt<T> &lhs, const U &rhs) 515{ 516 return lhs == cast_to_CheckedInt<T>(rhs); 517} 518 519template<typename T, typename U> 520inline 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 */ 528