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