1/* 2These functions provide integer arithmetic with integer checking. They do not 3actually raise an exception when an overflow is detected, but rather set a bit 4in the overflow parameter. (This parameter may be re-used accross several 5arithmetic operations, so should be or-ed rather than assigned to.) 6 7The implementation is divided into two parts, the signed and unsigned basecases, 8which is where the magic happens, and a generic template matching a specific 9type to an implementation based on its (c-compile-time) size and signedness. 10 11When possible, branching is avoided, and preference is given to speed over 12accuracy (a low rate of falsely "detected" overflows are acceptable, 13undetected overflows are not). 14 15 16TODO: Hook up checking. 17TODO: Conditionally support 128-bit with intmax_t? 18*/ 19 20/////////////// Common.proto /////////////// 21 22static int __Pyx_check_twos_complement(void) { 23 if (-1 != ~0) { 24 PyErr_SetString(PyExc_RuntimeError, "Two's complement required for overflow checks."); 25 return 1; 26 } else if (sizeof(short) == sizeof(int)) { 27 PyErr_SetString(PyExc_RuntimeError, "sizeof(short) < sizeof(int) required for overflow checks."); 28 return 1; 29 } else { 30 return 0; 31 } 32} 33 34#define __PYX_IS_UNSIGNED(type) (((type) -1) > 0) 35#define __PYX_SIGN_BIT(type) (((unsigned type) 1) << (sizeof(type) * 8 - 1)) 36#define __PYX_HALF_MAX(type) (((type) 1) << (sizeof(type) * 8 - 2)) 37#define __PYX_MIN(type) (__PYX_IS_UNSIGNED(type) ? (type) 0 : 0 - __PYX_HALF_MAX(type) - __PYX_HALF_MAX(type)) 38#define __PYX_MAX(type) (~__PYX_MIN(type)) 39 40#define __Pyx_add_no_overflow(a, b, overflow) ((a) + (b)) 41#define __Pyx_add_const_no_overflow(a, b, overflow) ((a) + (b)) 42#define __Pyx_sub_no_overflow(a, b, overflow) ((a) - (b)) 43#define __Pyx_sub_const_no_overflow(a, b, overflow) ((a) - (b)) 44#define __Pyx_mul_no_overflow(a, b, overflow) ((a) * (b)) 45#define __Pyx_mul_const_no_overflow(a, b, overflow) ((a) * (b)) 46#define __Pyx_div_no_overflow(a, b, overflow) ((a) / (b)) 47#define __Pyx_div_const_no_overflow(a, b, overflow) ((a) / (b)) 48 49/////////////// Common.init /////////////// 50 51__Pyx_check_twos_complement(); 52 53/////////////// BaseCaseUnsigned.proto /////////////// 54 55static CYTHON_INLINE {{UINT}} __Pyx_add_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow); 56static CYTHON_INLINE {{UINT}} __Pyx_sub_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow); 57static CYTHON_INLINE {{UINT}} __Pyx_mul_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow); 58static CYTHON_INLINE {{UINT}} __Pyx_div_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow); 59 60// Use these when b is known at compile time. 61#define __Pyx_add_const_{{NAME}}_checking_overflow __Pyx_add_{{NAME}}_checking_overflow 62#define __Pyx_sub_const_{{NAME}}_checking_overflow __Pyx_sub_{{NAME}}_checking_overflow 63static CYTHON_INLINE {{UINT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} constant, int *overflow); 64#define __Pyx_div_const_{{NAME}}_checking_overflow __Pyx_div_{{NAME}}_checking_overflow 65 66/////////////// BaseCaseUnsigned /////////////// 67 68static CYTHON_INLINE {{UINT}} __Pyx_add_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) { 69 {{UINT}} r = a + b; 70 *overflow |= r < a; 71 return r; 72} 73 74static CYTHON_INLINE {{UINT}} __Pyx_sub_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) { 75 {{UINT}} r = a - b; 76 *overflow |= r > a; 77 return r; 78} 79 80static CYTHON_INLINE {{UINT}} __Pyx_mul_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) { 81 if (sizeof({{UINT}}) < sizeof(unsigned long)) { 82 unsigned long big_r = ((unsigned long) a) * ((unsigned long) b); 83 {{UINT}} r = ({{UINT}}) big_r; 84 *overflow |= big_r != r; 85 return r; 86 } else if (sizeof({{UINT}}) < sizeof(unsigned long long)) { 87 unsigned long long big_r = ((unsigned long long) a) * ((unsigned long long) b); 88 {{UINT}} r = ({{UINT}}) big_r; 89 *overflow |= big_r != r; 90 return r; 91 } else { 92 {{UINT}} prod = a * b; 93 double dprod = ((double) a) * ((double) b); 94 // Overflow results in an error of at least 2^sizeof(UINT), 95 // whereas rounding represents an error on the order of 2^(sizeof(UINT)-53). 96 *overflow |= fabs(dprod - prod) > (__PYX_MAX({{UINT}}) / 2); 97 return prod; 98 } 99} 100 101static CYTHON_INLINE {{UINT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) { 102 if (b > 1) { 103 *overflow |= a > __PYX_MAX({{UINT}}) / b; 104 } 105 return a * b; 106} 107 108 109static CYTHON_INLINE {{UINT}} __Pyx_div_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) { 110 if (b == 0) { 111 *overflow |= 1; 112 return 0; 113 } 114 return a / b; 115} 116 117 118/////////////// BaseCaseSigned.proto /////////////// 119 120static CYTHON_INLINE {{INT}} __Pyx_add_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 121static CYTHON_INLINE {{INT}} __Pyx_sub_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 122static CYTHON_INLINE {{INT}} __Pyx_mul_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 123static CYTHON_INLINE {{INT}} __Pyx_div_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 124 125 126// Use when b is known at compile time. 127static CYTHON_INLINE {{INT}} __Pyx_add_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 128static CYTHON_INLINE {{INT}} __Pyx_sub_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow); 129static CYTHON_INLINE {{INT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} constant, int *overflow); 130#define __Pyx_div_const_{{NAME}}_checking_overflow __Pyx_div_{{NAME}}_checking_overflow 131 132/////////////// BaseCaseSigned /////////////// 133 134static CYTHON_INLINE {{INT}} __Pyx_add_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 135 if (sizeof({{INT}}) < sizeof(long)) { 136 long big_r = ((long) a) + ((long) b); 137 {{INT}} r = ({{INT}}) big_r; 138 *overflow |= big_r != r; 139 return r; 140 } else if (sizeof({{INT}}) < sizeof(long long)) { 141 long long big_r = ((long long) a) + ((long long) b); 142 {{INT}} r = ({{INT}}) big_r; 143 *overflow |= big_r != r; 144 return r; 145 } else { 146 // Signed overflow undefined, but unsigned overflow is well defined. 147 {{INT}} r = ({{INT}}) ((unsigned {{INT}}) a + (unsigned {{INT}}) b); 148 // Overflow happened if the operands have the same sign, but the result 149 // has opposite sign. 150 // sign(a) == sign(b) != sign(r) 151 {{INT}} sign_a = __PYX_SIGN_BIT({{INT}}) & a; 152 {{INT}} sign_b = __PYX_SIGN_BIT({{INT}}) & b; 153 {{INT}} sign_r = __PYX_SIGN_BIT({{INT}}) & r; 154 *overflow |= (sign_a == sign_b) & (sign_a != sign_r); 155 return r; 156 } 157} 158 159static CYTHON_INLINE {{INT}} __Pyx_add_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 160 if (b > 0) { 161 *overflow |= a > __PYX_MAX({{INT}}) - b; 162 } else if (b < 0) { 163 *overflow |= a < __PYX_MIN({{INT}}) - b; 164 } 165 return a + b; 166} 167 168static CYTHON_INLINE {{INT}} __Pyx_sub_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 169 *overflow |= b == __PYX_MIN({{INT}}); 170 return __Pyx_add_{{NAME}}_checking_overflow(a, -b, overflow); 171} 172 173static CYTHON_INLINE {{INT}} __Pyx_sub_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 174 *overflow |= b == __PYX_MIN({{INT}}); 175 return __Pyx_add_const_{{NAME}}_checking_overflow(a, -b, overflow); 176} 177 178static CYTHON_INLINE {{INT}} __Pyx_mul_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 179 if (sizeof({{INT}}) < sizeof(long)) { 180 long big_r = ((long) a) * ((long) b); 181 {{INT}} r = ({{INT}}) big_r; 182 *overflow |= big_r != r; 183 return ({{INT}}) r; 184 } else if (sizeof({{INT}}) < sizeof(long long)) { 185 long long big_r = ((long long) a) * ((long long) b); 186 {{INT}} r = ({{INT}}) big_r; 187 *overflow |= big_r != r; 188 return ({{INT}}) r; 189 } else { 190 {{INT}} prod = a * b; 191 double dprod = ((double) a) * ((double) b); 192 // Overflow results in an error of at least 2^sizeof(INT), 193 // whereas rounding represents an error on the order of 2^(sizeof(INT)-53). 194 *overflow |= fabs(dprod - prod) > (__PYX_MAX({{INT}}) / 2); 195 return prod; 196 } 197} 198 199static CYTHON_INLINE {{INT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 200 if (b > 1) { 201 *overflow |= a > __PYX_MAX({{INT}}) / b; 202 *overflow |= a < __PYX_MIN({{INT}}) / b; 203 } else if (b == -1) { 204 *overflow |= a == __PYX_MIN({{INT}}); 205 } else if (b < -1) { 206 *overflow |= a > __PYX_MIN({{INT}}) / b; 207 *overflow |= a < __PYX_MAX({{INT}}) / b; 208 } 209 return a * b; 210} 211 212static CYTHON_INLINE {{INT}} __Pyx_div_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) { 213 if (b == 0) { 214 *overflow |= 1; 215 return 0; 216 } 217 *overflow |= (a == __PYX_MIN({{INT}})) & (b == -1); 218 return a / b; 219} 220 221 222/////////////// SizeCheck.init /////////////// 223 224__Pyx_check_sane_{{NAME}}(); 225 226/////////////// SizeCheck.proto /////////////// 227 228static int __Pyx_check_sane_{{NAME}}(void) { 229 if (sizeof({{TYPE}}) <= sizeof(int) || 230 sizeof({{TYPE}}) == sizeof(long) || 231 sizeof({{TYPE}}) == sizeof(long long)) { 232 return 0; 233 } else { 234 PyErr_Format(PyExc_RuntimeError, \ 235 "Bad size for int type %.{{max(60, len(TYPE))}}s: %d", "{{TYPE}}", (int) sizeof({{TYPE}})); 236 return 1; 237 } 238} 239 240 241/////////////// Binop.proto /////////////// 242 243static CYTHON_INLINE {{TYPE}} __Pyx_{{BINOP}}_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow); 244 245/////////////// Binop /////////////// 246 247static CYTHON_INLINE {{TYPE}} __Pyx_{{BINOP}}_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow) { 248 if (sizeof({{TYPE}}) < sizeof(int)) { 249 return __Pyx_{{BINOP}}_no_overflow(a, b, overflow); 250 } else if (__PYX_IS_UNSIGNED({{TYPE}})) { 251 if (sizeof({{TYPE}}) == sizeof(unsigned int)) { 252 return __Pyx_{{BINOP}}_unsigned_int_checking_overflow(a, b, overflow); 253 } else if (sizeof({{TYPE}}) == sizeof(unsigned long)) { 254 return __Pyx_{{BINOP}}_unsigned_long_checking_overflow(a, b, overflow); 255 } else if (sizeof({{TYPE}}) == sizeof(unsigned long long)) { 256 return __Pyx_{{BINOP}}_unsigned_long_long_checking_overflow(a, b, overflow); 257 } else { 258 abort(); return 0; // handled elsewhere 259 } 260 } else { 261 if (sizeof({{TYPE}}) == sizeof(int)) { 262 return __Pyx_{{BINOP}}_int_checking_overflow(a, b, overflow); 263 } else if (sizeof({{TYPE}}) == sizeof(long)) { 264 return __Pyx_{{BINOP}}_long_checking_overflow(a, b, overflow); 265 } else if (sizeof({{TYPE}}) == sizeof(long long)) { 266 return __Pyx_{{BINOP}}_long_long_checking_overflow(a, b, overflow); 267 } else { 268 abort(); return 0; // handled elsewhere 269 } 270 } 271} 272 273/////////////// LeftShift.proto /////////////// 274 275static CYTHON_INLINE {{TYPE}} __Pyx_lshift_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow) { 276 *overflow |= 277#if {{SIGNED}} 278 (b < 0) | 279#endif 280 (b > ({{TYPE}}) (8 * sizeof({{TYPE}}))) | (a > (__PYX_MAX({{TYPE}}) >> b)); 281 return a << b; 282} 283#define __Pyx_lshift_const_{{NAME}}_checking_overflow __Pyx_lshift_{{NAME}}_checking_overflow 284 285