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 (at) mozilla.com> 24 * Jeff Muizelaar <jmuizelaar (at) 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 66 #define CHECKEDINT_REGISTER_SUPPORTED_TYPE(T,_twice_bigger_type,_unsigned_type) \ 67 template<> struct integer_type_manually_recorded_info<T> \ 68 { \ 69 enum { is_supported = 1 }; \ 70 typedef _twice_bigger_type twice_bigger_type; \ 71 typedef _unsigned_type unsigned_type; \ 72 }; 73 74 // Type Twice Bigger Type Unsigned Type 75 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int8_t, int16_t, uint8_t) 76 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint8_t, uint16_t, uint8_t) 77 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int16_t, int32_t, uint16_t) 78 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint16_t, uint32_t, uint16_t) 79 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int32_t, int64_t, uint32_t) 80 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint32_t, uint64_t, uint32_t) 81 CHECKEDINT_REGISTER_SUPPORTED_TYPE(int64_t, unsupported_type, uint64_t) 82 CHECKEDINT_REGISTER_SUPPORTED_TYPE(uint64_t, unsupported_type, uint64_t) 83 84 // now implement the fallback for standard types like int, long, ... 85 // the difficulty is that they may or may not be equal to one of the above types, and/or 86 // to each other. This is why any attempt to handle at once PRInt8... types and standard types 87 // is bound to fail. 88 template<typename T> 89 struct is_standard_integer_type { enum { value = 0 }; }; 90 91 template<> 92 struct is_standard_integer_type<char> { enum { value = 1 }; }; 93 template<> 94 struct is_standard_integer_type<unsigned char> { enum { value = 1 }; }; 95 template<> 96 struct is_standard_integer_type<short> { enum { value = 1 }; }; 97 template<> 98 struct is_standard_integer_type<unsigned short> { enum { value = 1 }; }; 99 template<> 100 struct is_standard_integer_type<int> { enum { value = 1 }; }; 101 template<> 102 struct is_standard_integer_type<unsigned int> { enum { value = 1 }; }; 103 template<> 104 struct is_standard_integer_type<long> { enum { value = 1 }; }; 105 template<> 106 struct is_standard_integer_type<unsigned long> { enum { value = 1 }; }; 107 template<> 108 struct is_standard_integer_type<long long> { enum { value = 1 }; }; 109 template<> 110 struct is_standard_integer_type<unsigned long long> { enum { value = 1 }; }; 111 112 template<int size, bool is_signed> 113 struct explicitly_sized_integer_type {}; 114 115 template<> 116 struct explicitly_sized_integer_type<1, true> { typedef int8_t type; }; 117 template<> 118 struct explicitly_sized_integer_type<1, false> { typedef uint8_t type; }; 119 template<> 120 struct explicitly_sized_integer_type<2, true> { typedef int16_t type; }; 121 template<> 122 struct explicitly_sized_integer_type<2, false> { typedef uint16_t type; }; 123 template<> 124 struct explicitly_sized_integer_type<4, true> { typedef int32_t type; }; 125 template<> 126 struct explicitly_sized_integer_type<4, false> { typedef uint32_t type; }; 127 template<> 128 struct explicitly_sized_integer_type<8, true> { typedef int64_t type; }; 129 template<> 130 struct explicitly_sized_integer_type<8, false> { typedef uint64_t type; }; 131 132 template<typename T> struct integer_type_manually_recorded_info 133 { 134 enum { 135 is_supported = is_standard_integer_type<T>::value, 136 size = sizeof(T), 137 is_signed = (T(-1) > T(0)) ? 0 : 1 138 }; 139 typedef typename explicitly_sized_integer_type<size, is_signed>::type explicit_sized_type; 140 typedef integer_type_manually_recorded_info<explicit_sized_type> base; 141 typedef typename base::twice_bigger_type twice_bigger_type; 142 typedef typename base::unsigned_type unsigned_type; 143 }; 144 145 template<typename T, bool is_supported = integer_type_manually_recorded_info<T>::is_supported> 146 struct TYPE_NOT_SUPPORTED_BY_CheckedInt {}; 147 148 template<typename T> 149 struct TYPE_NOT_SUPPORTED_BY_CheckedInt<T, true> { static void run() {} }; 150 151 152 /*** Step 2: record some info about a given integer type, 153 *** including whether it is supported, whether a twice bigger integer type 154 *** is supported, what that twice bigger type is, and some stuff as found 155 *** in std::numeric_limits (which we don't use because int.. types may 156 *** not support it, if they are defined directly from compiler built-in types). 157 ***/ 158 159 template<typename T> struct is_unsupported_type { enum { answer = 0 }; }; 160 template<> struct is_unsupported_type<unsupported_type> { enum { answer = 1 }; }; 161 162 template<typename T> struct integer_traits 163 { 164 typedef typename integer_type_manually_recorded_info<T>::twice_bigger_type twice_bigger_type; 165 166 enum { 167 is_supported = integer_type_manually_recorded_info<T>::is_supported, 168 twice_bigger_type_is_supported 169 = is_unsupported_type< 170 typename integer_type_manually_recorded_info<T>::twice_bigger_type 171 >::answer ? 0 : 1, 172 size = sizeof(T), 173 position_of_sign_bit = CHAR_BIT * size - 1, 174 is_signed = (T(-1) > T(0)) ? 0 : 1 175 }; 176 177 static T min() 178 { 179 // bitwise ops may return a larger type, that's why we cast explicitly to T 180 return is_signed ? T(T(1) << position_of_sign_bit) : T(0); 181 } 182 183 static T max() 184 { 185 return ~min(); 186 } 187 }; 188 189 /*** Step 3: Implement the actual validity checks --- ideas taken from IntegerLib, code different. 190 ***/ 191 192 // bitwise ops may return a larger type, so it's good to use these inline helpers guaranteeing that 193 // the result is really of type T 194 195 template<typename T> inline T has_sign_bit(T x) 196 { 197 return x >> integer_traits<T>::position_of_sign_bit; 198 } 199 200 template<typename T> inline T binary_complement(T x) 201 { 202 return ~x; 203 } 204 205 template<typename T, typename U, 206 bool is_T_signed = integer_traits<T>::is_signed, 207 bool is_U_signed = integer_traits<U>::is_signed> 208 struct is_in_range_impl {}; 209 210 template<typename T, typename U> 211 struct is_in_range_impl<T, U, true, true> 212 { 213 static T run(U x) 214 { 215 return (x <= integer_traits<T>::max()) & 216 (x >= integer_traits<T>::min()); 217 } 218 }; 219 220 template<typename T, typename U> 221 struct is_in_range_impl<T, U, false, false> 222 { 223 static T run(U x) 224 { 225 return x <= integer_traits<T>::max(); 226 } 227 }; 228 229 template<typename T, typename U> 230 struct is_in_range_impl<T, U, true, false> 231 { 232 static T run(U x) 233 { 234 if (sizeof(T) > sizeof(U)) 235 return 1; 236 else 237 return x <= U(integer_traits<T>::max()); 238 } 239 }; 240 241 template<typename T, typename U> 242 struct is_in_range_impl<T, U, false, true> 243 { 244 static T run(U x) 245 { 246 if (sizeof(T) >= sizeof(U)) 247 return x >= 0; 248 else 249 return x >= 0 && x <= U(integer_traits<T>::max()); 250 } 251 }; 252 253 template<typename T, typename U> inline T is_in_range(U x) 254 { 255 return is_in_range_impl<T, U>::run(x); 256 } 257 258 template<typename T> inline T is_add_valid(T x, T y, T result) 259 { 260 return integer_traits<T>::is_signed ? 261 // addition is valid if the sign of x+y is equal to either that of x or that of y. 262 // Beware! These bitwise operations can return a larger integer type, if T was a 263 // small type like int8, so we explicitly cast to T. 264 has_sign_bit(binary_complement(T((result^x) & (result^y)))) 265 : 266 binary_complement(x) >= y; 267 } 268 269 template<typename T> inline T is_sub_valid(T x, T y, T result) 270 { 271 return integer_traits<T>::is_signed ? 272 // substraction is valid if either x and y have same sign, or x-y and x have same sign 273 has_sign_bit(binary_complement(T((result^x) & (x^y)))) 274 : 275 x >= y; 276 } 277 278 template<typename T, 279 bool is_signed = integer_traits<T>::is_signed, 280 bool twice_bigger_type_is_supported = integer_traits<T>::twice_bigger_type_is_supported> 281 struct is_mul_valid_impl {}; 282 283 template<typename T> 284 struct is_mul_valid_impl<T, true, true> 285 { 286 static T run(T x, T y) 287 { 288 typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type; 289 twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y); 290 return is_in_range<T>(product); 291 } 292 }; 293 294 template<typename T> 295 struct is_mul_valid_impl<T, false, true> 296 { 297 static T run(T x, T y) 298 { 299 typedef typename integer_traits<T>::twice_bigger_type twice_bigger_type; 300 twice_bigger_type product = twice_bigger_type(x) * twice_bigger_type(y); 301 return is_in_range<T>(product); 302 } 303 }; 304 305 template<typename T> 306 struct is_mul_valid_impl<T, true, false> 307 { 308 static T run(T x, T y) 309 { 310 const T max_value = integer_traits<T>::max(); 311 const T min_value = integer_traits<T>::min(); 312 313 if (x == 0 || y == 0) return true; 314 315 if (x > 0) { 316 if (y > 0) 317 return x <= max_value / y; 318 else 319 return y >= min_value / x; 320 } else { 321 if (y > 0) 322 return x >= min_value / y; 323 else 324 return y >= max_value / x; 325 } 326 } 327 }; 328 329 template<typename T> 330 struct is_mul_valid_impl<T, false, false> 331 { 332 static T run(T x, T y) 333 { 334 const T max_value = integer_traits<T>::max(); 335 if (x == 0 || y == 0) return true; 336 return x <= max_value / y; 337 } 338 }; 339 340 template<typename T> inline T is_mul_valid(T x, T y, T /*result not used*/) 341 { 342 return is_mul_valid_impl<T>::run(x, y); 343 } 344 345 template<typename T> inline T is_div_valid(T x, T y) 346 { 347 return integer_traits<T>::is_signed ? 348 // keep in mind that min/-1 is invalid because abs(min)>max 349 y != 0 && (x != integer_traits<T>::min() || y != T(-1)) 350 : 351 y != 0; 352 } 353 354 } // end namespace CheckedInt_internal 355 356 357 /*** Step 4: Now define the CheckedInt class. 358 ***/ 359 360 /** \class CheckedInt 361 * \brief Integer wrapper class checking for integer overflow and other errors 362 * \param T the integer type to wrap. Can be any of int8_t, uint8_t, int16_t, uint16_t, 363 * int32_t, uint32_t, int64_t, uint64_t. 364 * 365 * This class implements guarded integer arithmetic. Do a computation, then check that 366 * valid() returns true, you then have a guarantee that no problem, such as integer overflow, 367 * happened during this computation. 368 * 369 * The arithmetic operators in this class are guaranteed not to crash your app 370 * in case of a division by zero. 371 * 372 * For example, suppose that you want to implement a function that computes (x+y)/z, 373 * that doesn't crash if z==0, and that reports on error (divide by zero or integer overflow). 374 * You could code it as follows: 375 \code 376 bool compute_x_plus_y_over_z(int32_t x, int32_t y, int32_t z, int32_t *result) 377 { 378 CheckedInt<int32_t> checked_result = (CheckedInt<int32_t>(x) + y) / z; 379 *result = checked_result.value(); 380 return checked_result.valid(); 381 } 382 \endcode 383 * 384 * Implicit conversion from plain integers to checked integers is allowed. The plain integer 385 * is checked to be in range before being casted to the destination type. This means that the following 386 * lines all compile, and the resulting CheckedInts are correctly detected as valid or invalid: 387 * \code 388 CheckedInt<uint8_t> x(1); // 1 is of type int, is found to be in range for uint8_t, x is valid 389 CheckedInt<uint8_t> x(-1); // -1 is of type int, is found not to be in range for uint8_t, x is invalid 390 CheckedInt<int8_t> x(-1); // -1 is of type int, is found to be in range for int8_t, x is valid 391 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 392 CheckedInt<int32_t> x(uint32_t(123456789)); // 3123456789 is of type uint32_t, is found not to be in range 393 // for int32_t, x is invalid 394 * \endcode 395 * Implicit conversion from 396 * checked integers to plain integers is not allowed. As shown in the 397 * above example, to get the value of a checked integer as a normal integer, call value(). 398 * 399 * Arithmetic operations between checked and plain integers is allowed; the result type 400 * is the type of the checked integer. 401 * 402 * Safe integers of different types cannot be used in the same arithmetic expression. 403 */ 404 template<typename T> 405 class CheckedInt 406 { 407 protected: 408 T mValue; 409 T mIsValid; // stored as a T to limit the number of integer conversions when 410 // evaluating nested arithmetic expressions. 411 412 template<typename U> 413 CheckedInt(const U& value, bool isValid) : mValue(value), mIsValid(isValid) 414 { 415 CheckedInt_internal::TYPE_NOT_SUPPORTED_BY_CheckedInt<T>::run(); 416 } 417 418 public: 419 /** Constructs a checked integer with given \a value. The checked integer is initialized as valid or invalid 420 * depending on whether the \a value is in range. 421 * 422 * This constructor is not explicit. Instead, the type of its argument is a separate template parameter, 423 * ensuring that no conversion is performed before this constructor is actually called. 424 * As explained in the above documentation for class CheckedInt, this constructor checks that its argument is 425 * valid. 426 */ 427 template<typename U> 428 CheckedInt(const U& value) 429 : mValue(value), 430 mIsValid(CheckedInt_internal::is_in_range<T>(value)) 431 { 432 CheckedInt_internal::TYPE_NOT_SUPPORTED_BY_CheckedInt<T>::run(); 433 } 434 435 /** Constructs a valid checked integer with uninitialized value */ 436 CheckedInt() : mIsValid(1) 437 { 438 CheckedInt_internal::TYPE_NOT_SUPPORTED_BY_CheckedInt<T>::run(); 439 } 440 441 /** \returns the actual value */ 442 T value() const { return mValue; } 443 444 /** \returns true if the checked integer is valid, i.e. is not the result 445 * of an invalid operation or of an operation involving an invalid checked integer 446 */ 447 bool valid() const { return mIsValid; } 448 449 /** \returns the sum. Checks for overflow. */ 450 template<typename U> friend CheckedInt<U> operator +(const CheckedInt<U>& lhs, const CheckedInt<U>& rhs); 451 /** Adds. Checks for overflow. \returns self reference */ 452 template<typename U> CheckedInt& operator +=(const U &rhs); 453 /** \returns the difference. Checks for overflow. */ 454 template<typename U> friend CheckedInt<U> operator -(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs); 455 /** Substracts. Checks for overflow. \returns self reference */ 456 template<typename U> CheckedInt& operator -=(const U &rhs); 457 /** \returns the product. Checks for overflow. */ 458 template<typename U> friend CheckedInt<U> operator *(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs); 459 /** Multiplies. Checks for overflow. \returns self reference */ 460 template<typename U> CheckedInt& operator *=(const U &rhs); 461 /** \returns the quotient. Checks for overflow and for divide-by-zero. */ 462 template<typename U> friend CheckedInt<U> operator /(const CheckedInt<U>& lhs, const CheckedInt<U> &rhs); 463 /** Divides. Checks for overflow and for divide-by-zero. \returns self reference */ 464 template<typename U> CheckedInt& operator /=(const U &rhs); 465 466 /** \returns the opposite value. Checks for overflow. */ 467 CheckedInt operator -() const 468 { 469 T result = -value(); 470 /* give the compiler a good chance to perform RVO */ 471 return CheckedInt(result, 472 mIsValid & CheckedInt_internal::is_sub_valid(T(0), value(), result)); 473 } 474 475 /** \returns true if the left and right hand sides are valid and have the same value. */ 476 bool operator ==(const CheckedInt& other) const 477 { 478 return bool(mIsValid & other.mIsValid & T(value() == other.value())); 479 } 480 481 private: 482 /** operator!= is disabled. Indeed: (a!=b) should be the same as !(a==b) but that 483 * would mean that if a or b is invalid, (a!=b) is always true, which is very tricky. 484 */ 485 template<typename U> 486 bool operator !=(const U& other) const { return !(*this == other); } 487 }; 488 489 #define CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP) \ 490 template<typename T> \ 491 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs) \ 492 { \ 493 T x = lhs.value(); \ 494 T y = rhs.value(); \ 495 T result = x OP y; \ 496 T is_op_valid \ 497 = CheckedInt_internal::is_##NAME##_valid(x, y, result); \ 498 /* give the compiler a good chance to perform RVO */ \ 499 return CheckedInt<T>(result, \ 500 lhs.mIsValid & \ 501 rhs.mIsValid & \ 502 is_op_valid); \ 503 } 504 505 CHECKEDINT_BASIC_BINARY_OPERATOR(add, +) 506 CHECKEDINT_BASIC_BINARY_OPERATOR(sub, -) 507 CHECKEDINT_BASIC_BINARY_OPERATOR(mul, *) 508 509 // division can't be implemented by CHECKEDINT_BASIC_BINARY_OPERATOR 510 // because if rhs == 0, we are not allowed to even try to compute the quotient. 511 template<typename T> 512 inline CheckedInt<T> operator /(const CheckedInt<T> &lhs, const CheckedInt<T> &rhs) 513 { 514 T x = lhs.value(); 515 T y = rhs.value(); 516 T is_op_valid = CheckedInt_internal::is_div_valid(x, y); 517 T result = is_op_valid ? (x / y) : 0; 518 /* give the compiler a good chance to perform RVO */ 519 return CheckedInt<T>(result, 520 lhs.mIsValid & 521 rhs.mIsValid & 522 is_op_valid); 523 } 524 525 // implement cast_to_CheckedInt<T>(x), making sure that 526 // - it allows x to be either a CheckedInt<T> or any integer type that can be casted to T 527 // - if x is already a CheckedInt<T>, we just return a reference to it, instead of copying it (optimization) 528 529 template<typename T, typename U> 530 struct cast_to_CheckedInt_impl 531 { 532 typedef CheckedInt<T> return_type; 533 static CheckedInt<T> run(const U& u) { return u; } 534 }; 535 536 template<typename T> 537 struct cast_to_CheckedInt_impl<T, CheckedInt<T> > 538 { 539 typedef const CheckedInt<T>& return_type; 540 static const CheckedInt<T>& run(const CheckedInt<T>& u) { return u; } 541 }; 542 543 template<typename T, typename U> 544 inline typename cast_to_CheckedInt_impl<T, U>::return_type 545 cast_to_CheckedInt(const U& u) 546 { 547 return cast_to_CheckedInt_impl<T, U>::run(u); 548 } 549 550 #define CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(OP, COMPOUND_OP) \ 551 template<typename T> \ 552 template<typename U> \ 553 CheckedInt<T>& CheckedInt<T>::operator COMPOUND_OP(const U &rhs) \ 554 { \ 555 *this = *this OP cast_to_CheckedInt<T>(rhs); \ 556 return *this; \ 557 } \ 558 template<typename T, typename U> \ 559 inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs, const U &rhs) \ 560 { \ 561 return lhs OP cast_to_CheckedInt<T>(rhs); \ 562 } \ 563 template<typename T, typename U> \ 564 inline CheckedInt<T> operator OP(const U & lhs, const CheckedInt<T> &rhs) \ 565 { \ 566 return cast_to_CheckedInt<T>(lhs) OP rhs; \ 567 } 568 569 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(+, +=) 570 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(*, *=) 571 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(-, -=) 572 CHECKEDINT_CONVENIENCE_BINARY_OPERATORS(/, /=) 573 574 template<typename T, typename U> 575 inline bool operator ==(const CheckedInt<T> &lhs, const U &rhs) 576 { 577 return lhs == cast_to_CheckedInt<T>(rhs); 578 } 579 580 template<typename T, typename U> 581 inline bool operator ==(const U & lhs, const CheckedInt<T> &rhs) 582 { 583 return cast_to_CheckedInt<T>(lhs) == rhs; 584 } 585 586 } // end namespace WebCore 587 588 #endif /* CheckedInt_h */ 589
