third_party/cython/src/Cython/Utility/Overflow.c

   1 /*
   2 These functions provide integer arithmetic with integer checking.  They do not
   3 actually raise an exception when an overflow is detected, but rather set a bit
   4 in the overflow parameter.  (This parameter may be re-used accross several
   5 arithmetic operations, so should be or-ed rather than assigned to.)
   6
   7 The implementation is divided into two parts, the signed and unsigned basecases,
   8 which is where the magic happens, and a generic template matching a specific
   9 type to an implementation based on its (c-compile-time) size and signedness.
  10
  11 When possible, branching is avoided, and preference is given to speed over
  12 accuracy (a low rate of falsely "detected" overflows are acceptable,
  13 undetected overflows are not).
  14
  15
  16 TODO: Hook up checking.
  17 TODO: Conditionally support 128-bit with intmax_t?
  18 */
  19
  20 /////////////// Common.proto ///////////////
  21
  22 static 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
  55 static CYTHON_INLINE {{UINT}} __Pyx_add_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
  56 static CYTHON_INLINE {{UINT}} __Pyx_sub_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
  57 static CYTHON_INLINE {{UINT}} __Pyx_mul_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
  58 static 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
  63 static 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
  68 static 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
  74 static 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
  80 static 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
 101 static 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
 109 static 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
 120 static CYTHON_INLINE {{INT}} __Pyx_add_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
 121 static CYTHON_INLINE {{INT}} __Pyx_sub_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
 122 static CYTHON_INLINE {{INT}} __Pyx_mul_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
 123 static 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.
 127 static CYTHON_INLINE {{INT}} __Pyx_add_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
 128 static CYTHON_INLINE {{INT}} __Pyx_sub_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
 129 static 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
 134 static 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
 159 static 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
 168 static 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
 173 static 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
 178 static 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
 199 static 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
 212 static 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
 228 static 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
 243 static CYTHON_INLINE {{TYPE}} __Pyx_{{BINOP}}_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow);
 244
 245 /////////////// Binop ///////////////
 246
 247 static 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
 275 static 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