Overflow.c 11.7 KB
Newer Older
1 2 3
/*
These functions provide integer arithmetic with integer checking.  They do not
actually raise an exception when an overflow is detected, but rather set a bit
Unknown's avatar
Unknown committed
4
in the overflow parameter.  (This parameter may be re-used across several
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
arithmetic operations, so should be or-ed rather than assigned to.)

The implementation is divided into two parts, the signed and unsigned basecases,
which is where the magic happens, and a generic template matching a specific
type to an implementation based on its (c-compile-time) size and signedness.

When possible, branching is avoided, and preference is given to speed over
accuracy (a low rate of falsely "detected" overflows are acceptable,
undetected overflows are not).


TODO: Hook up checking.
TODO: Conditionally support 128-bit with intmax_t?
*/

/////////////// Common.proto ///////////////

22
static int __Pyx_check_twos_complement(void) {
23 24 25 26 27 28 29 30 31 32 33
    if (-1 != ~0) {
        PyErr_SetString(PyExc_RuntimeError, "Two's complement required for overflow checks.");
        return 1;
    } else if (sizeof(short) == sizeof(int)) {
        PyErr_SetString(PyExc_RuntimeError, "sizeof(short) < sizeof(int) required for overflow checks.");
        return 1;
    } else {
        return 0;
    }
}

Stefan Behnel's avatar
Stefan Behnel committed
34 35
#define __PYX_IS_UNSIGNED(type) (((type) -1) > 0)
#define __PYX_SIGN_BIT(type)    (((unsigned type) 1) << (sizeof(type) * 8 - 1))
36 37 38 39 40 41 42
#define __PYX_HALF_MAX(type)    (((type) 1) << (sizeof(type) * 8 - 2))
#define __PYX_MIN(type)         (__PYX_IS_UNSIGNED(type) ? (type) 0 : 0 - __PYX_HALF_MAX(type) - __PYX_HALF_MAX(type))
#define __PYX_MAX(type)         (~__PYX_MIN(type))

#define __Pyx_add_no_overflow(a, b, overflow) ((a) + (b))
#define __Pyx_add_const_no_overflow(a, b, overflow) ((a) + (b))
#define __Pyx_sub_no_overflow(a, b, overflow) ((a) - (b))
43
#define __Pyx_sub_const_no_overflow(a, b, overflow) ((a) - (b))
44 45 46 47 48
#define __Pyx_mul_no_overflow(a, b, overflow) ((a) * (b))
#define __Pyx_mul_const_no_overflow(a, b, overflow) ((a) * (b))
#define __Pyx_div_no_overflow(a, b, overflow) ((a) / (b))
#define __Pyx_div_const_no_overflow(a, b, overflow) ((a) / (b))

49
/////////////// Common.init ///////////////
50

51
__Pyx_check_twos_complement();
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

/////////////// BaseCaseUnsigned.proto ///////////////

static CYTHON_INLINE {{UINT}} __Pyx_add_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
static CYTHON_INLINE {{UINT}} __Pyx_sub_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
static CYTHON_INLINE {{UINT}} __Pyx_mul_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);
static CYTHON_INLINE {{UINT}} __Pyx_div_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow);

// Use these when b is known at compile time.
#define __Pyx_add_const_{{NAME}}_checking_overflow __Pyx_add_{{NAME}}_checking_overflow
#define __Pyx_sub_const_{{NAME}}_checking_overflow __Pyx_sub_{{NAME}}_checking_overflow
static CYTHON_INLINE {{UINT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} constant, int *overflow);
#define __Pyx_div_const_{{NAME}}_checking_overflow __Pyx_div_{{NAME}}_checking_overflow

/////////////// BaseCaseUnsigned ///////////////

static CYTHON_INLINE {{UINT}} __Pyx_add_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) {
    {{UINT}} r = a + b;
    *overflow |= r < a;
    return r;
}

static CYTHON_INLINE {{UINT}} __Pyx_sub_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) {
    {{UINT}} r = a - b;
    *overflow |= r > a;
    return r;
}

static CYTHON_INLINE {{UINT}} __Pyx_mul_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) {
Robert Bradshaw's avatar
Robert Bradshaw committed
81
    if (sizeof({{UINT}}) < sizeof(unsigned long)) {
82 83 84
        unsigned long big_r = ((unsigned long) a) * ((unsigned long) b);
        {{UINT}} r = ({{UINT}}) big_r;
        *overflow |= big_r != r;
85
        return r;
86
#ifdef HAVE_LONG_LONG
87 88
    } else if (sizeof({{UINT}}) < sizeof(unsigned PY_LONG_LONG)) {
        unsigned PY_LONG_LONG big_r = ((unsigned PY_LONG_LONG) a) * ((unsigned PY_LONG_LONG) b);
89 90
        {{UINT}} r = ({{UINT}}) big_r;
        *overflow |= big_r != r;
91
        return r;
92
#endif
93 94 95
    } else {
        {{UINT}} prod = a * b;
        double dprod = ((double) a) * ((double) b);
96 97 98
        // Overflow results in an error of at least 2^sizeof(UINT),
        // whereas rounding represents an error on the order of 2^(sizeof(UINT)-53).
        *overflow |= fabs(dprod - prod) > (__PYX_MAX({{UINT}}) / 2);
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
        return prod;
    }
}

static CYTHON_INLINE {{UINT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) {
    if (b > 1) {
        *overflow |= a > __PYX_MAX({{UINT}}) / b;
    }
    return a * b;
}


static CYTHON_INLINE {{UINT}} __Pyx_div_{{NAME}}_checking_overflow({{UINT}} a, {{UINT}} b, int *overflow) {
    if (b == 0) {
        *overflow |= 1;
        return 0;
    }
    return a / b;
}


/////////////// BaseCaseSigned.proto ///////////////

static CYTHON_INLINE {{INT}} __Pyx_add_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
static CYTHON_INLINE {{INT}} __Pyx_sub_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
static CYTHON_INLINE {{INT}} __Pyx_mul_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
static CYTHON_INLINE {{INT}} __Pyx_div_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);


// Use when b is known at compile time.
static CYTHON_INLINE {{INT}} __Pyx_add_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
static CYTHON_INLINE {{INT}} __Pyx_sub_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow);
static CYTHON_INLINE {{INT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} constant, int *overflow);
#define __Pyx_div_const_{{NAME}}_checking_overflow __Pyx_div_{{NAME}}_checking_overflow

/////////////// BaseCaseSigned ///////////////

static CYTHON_INLINE {{INT}} __Pyx_add_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    if (sizeof({{INT}}) < sizeof(long)) {
        long big_r = ((long) a) + ((long) b);
        {{INT}} r = ({{INT}}) big_r;
        *overflow |= big_r != r;
141
        return r;
142
#ifdef HAVE_LONG_LONG
143 144
    } else if (sizeof({{INT}}) < sizeof(PY_LONG_LONG)) {
        PY_LONG_LONG big_r = ((PY_LONG_LONG) a) + ((PY_LONG_LONG) b);
145 146
        {{INT}} r = ({{INT}}) big_r;
        *overflow |= big_r != r;
147
        return r;
148
#endif
149
    } else {
150
        // Signed overflow undefined, but unsigned overflow is well defined.
151
        {{INT}} r = ({{INT}}) ((unsigned {{INT}}) a + (unsigned {{INT}}) b);
152 153
        // Overflow happened if the operands have the same sign, but the result
        // has opposite sign.
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
        // sign(a) == sign(b) != sign(r)
        {{INT}} sign_a = __PYX_SIGN_BIT({{INT}}) & a;
        {{INT}} sign_b = __PYX_SIGN_BIT({{INT}}) & b;
        {{INT}} sign_r = __PYX_SIGN_BIT({{INT}}) & r;
        *overflow |= (sign_a == sign_b) & (sign_a != sign_r);
        return r;
    }
}

static CYTHON_INLINE {{INT}} __Pyx_add_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    if (b > 0) {
        *overflow |= a > __PYX_MAX({{INT}}) - b;
    } else if (b < 0) {
        *overflow |= a < __PYX_MIN({{INT}}) - b;
    }
    return a + b;
}

static CYTHON_INLINE {{INT}} __Pyx_sub_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    *overflow |= b == __PYX_MIN({{INT}});
    return __Pyx_add_{{NAME}}_checking_overflow(a, -b, overflow);
}

static CYTHON_INLINE {{INT}} __Pyx_sub_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    *overflow |= b == __PYX_MIN({{INT}});
    return __Pyx_add_const_{{NAME}}_checking_overflow(a, -b, overflow);
}

static CYTHON_INLINE {{INT}} __Pyx_mul_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    if (sizeof({{INT}}) < sizeof(long)) {
        long big_r = ((long) a) * ((long) b);
        {{INT}} r = ({{INT}}) big_r;
        *overflow |= big_r != r;
        return ({{INT}}) r;
188
#ifdef HAVE_LONG_LONG
189 190
    } else if (sizeof({{INT}}) < sizeof(PY_LONG_LONG)) {
        PY_LONG_LONG big_r = ((PY_LONG_LONG) a) * ((PY_LONG_LONG) b);
191 192 193
        {{INT}} r = ({{INT}}) big_r;
        *overflow |= big_r != r;
        return ({{INT}}) r;
194
#endif
195 196 197
    } else {
        {{INT}} prod = a * b;
        double dprod = ((double) a) * ((double) b);
198 199 200
        // Overflow results in an error of at least 2^sizeof(INT),
        // whereas rounding represents an error on the order of 2^(sizeof(INT)-53).
        *overflow |= fabs(dprod - prod) > (__PYX_MAX({{INT}}) / 2);
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
        return prod;
    }
}

static CYTHON_INLINE {{INT}} __Pyx_mul_const_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    if (b > 1) {
        *overflow |= a > __PYX_MAX({{INT}}) / b;
        *overflow |= a < __PYX_MIN({{INT}}) / b;
    } else if (b == -1) {
        *overflow |= a == __PYX_MIN({{INT}});
    } else if (b < -1) {
        *overflow |= a > __PYX_MIN({{INT}}) / b;
        *overflow |= a < __PYX_MAX({{INT}}) / b;
    }
    return a * b;
}

static CYTHON_INLINE {{INT}} __Pyx_div_{{NAME}}_checking_overflow({{INT}} a, {{INT}} b, int *overflow) {
    if (b == 0) {
        *overflow |= 1;
        return 0;
    }
    *overflow |= (a == __PYX_MIN({{INT}})) & (b == -1);
    return a / b;
}


228 229 230 231
/////////////// SizeCheck.init ///////////////

__Pyx_check_sane_{{NAME}}();

232 233
/////////////// SizeCheck.proto ///////////////

234
static int __Pyx_check_sane_{{NAME}}(void) {
235
    if (sizeof({{TYPE}}) <= sizeof(int) ||
236 237 238 239
#ifdef HAVE_LONG_LONG
            sizeof({{TYPE}}) == sizeof(PY_LONG_LONG) ||
#endif
            sizeof({{TYPE}}) == sizeof(long)) {
240 241
        return 0;
    } else {
242 243
        PyErr_Format(PyExc_RuntimeError, \
            "Bad size for int type %.{{max(60, len(TYPE))}}s: %d", "{{TYPE}}", (int) sizeof({{TYPE}}));
244 245 246 247 248 249 250 251 252 253 254 255 256 257 258
        return 1;
    }
}


/////////////// Binop.proto ///////////////

static CYTHON_INLINE {{TYPE}} __Pyx_{{BINOP}}_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow);

/////////////// Binop ///////////////

static CYTHON_INLINE {{TYPE}} __Pyx_{{BINOP}}_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow) {
    if (sizeof({{TYPE}}) < sizeof(int)) {
        return __Pyx_{{BINOP}}_no_overflow(a, b, overflow);
    } else if (__PYX_IS_UNSIGNED({{TYPE}})) {
Robert Bradshaw's avatar
Robert Bradshaw committed
259
        if (sizeof({{TYPE}}) == sizeof(unsigned int)) {
260
            return __Pyx_{{BINOP}}_unsigned_int_checking_overflow(a, b, overflow);
Robert Bradshaw's avatar
Robert Bradshaw committed
261
        } else if (sizeof({{TYPE}}) == sizeof(unsigned long)) {
262
            return __Pyx_{{BINOP}}_unsigned_long_checking_overflow(a, b, overflow);
263
#ifdef HAVE_LONG_LONG
264
        } else if (sizeof({{TYPE}}) == sizeof(unsigned PY_LONG_LONG)) {
265
            return __Pyx_{{BINOP}}_unsigned_long_long_checking_overflow(a, b, overflow);
266
#endif
267
        } else {
268
            abort(); return 0; /* handled elsewhere */
269 270 271 272 273 274
        }
    } else {
        if (sizeof({{TYPE}}) == sizeof(int)) {
            return __Pyx_{{BINOP}}_int_checking_overflow(a, b, overflow);
        } else if (sizeof({{TYPE}}) == sizeof(long)) {
            return __Pyx_{{BINOP}}_long_checking_overflow(a, b, overflow);
275
#ifdef HAVE_LONG_LONG
276
        } else if (sizeof({{TYPE}}) == sizeof(PY_LONG_LONG)) {
277
            return __Pyx_{{BINOP}}_long_long_checking_overflow(a, b, overflow);
278
#endif
279
        } else {
280
            abort(); return 0; /* handled elsewhere */
281 282 283
        }
    }
}
284 285 286 287

/////////////// LeftShift.proto ///////////////

static CYTHON_INLINE {{TYPE}} __Pyx_lshift_{{NAME}}_checking_overflow({{TYPE}} a, {{TYPE}} b, int *overflow) {
288 289 290 291
    *overflow |=
#if {{SIGNED}}
        (b < 0) |
#endif
292
        (b > ({{TYPE}}) (8 * sizeof({{TYPE}}))) | (a > (__PYX_MAX({{TYPE}}) >> b));
293 294 295 296
    return a << b;
}
#define __Pyx_lshift_const_{{NAME}}_checking_overflow __Pyx_lshift_{{NAME}}_checking_overflow

297 298 299 300 301 302 303

/////////////// UnaryNegOverflows.proto ///////////////

//FIXME: shouldn't the macro name be prefixed by "__Pyx_" ?  Too late now, I guess...
// from intobject.c
#define UNARY_NEG_WOULD_OVERFLOW(x)    \
        (((x) < 0) & ((unsigned long)(x) == 0-(unsigned long)(x)))