1 // Int primitive operations (tagged arbitrary-precision integers)
2 //
3 // These are registered in mypyc.primitives.int_ops.
4
5 #include <Python.h>
6 #include "CPy.h"
7
8 #ifndef _WIN32
9 // On 64-bit Linux and macOS, ssize_t and long are both 64 bits, and
10 // PyLong_FromLong is faster than PyLong_FromSsize_t, so use the faster one
11 #define CPyLong_FromSsize_t PyLong_FromLong
12 #else
13 // On 64-bit Windows, ssize_t is 64 bits but long is 32 bits, so we
14 // can't use the above trick
15 #define CPyLong_FromSsize_t PyLong_FromSsize_t
16 #endif
17
CPyTagged_FromSsize_t(Py_ssize_t value)18 CPyTagged CPyTagged_FromSsize_t(Py_ssize_t value) {
19 // We use a Python object if the value shifted left by 1 is too
20 // large for Py_ssize_t
21 if (unlikely(CPyTagged_TooBig(value))) {
22 PyObject *object = PyLong_FromSsize_t(value);
23 return ((CPyTagged)object) | CPY_INT_TAG;
24 } else {
25 return value << 1;
26 }
27 }
28
CPyTagged_FromObject(PyObject * object)29 CPyTagged CPyTagged_FromObject(PyObject *object) {
30 int overflow;
31 // The overflow check knows about CPyTagged's width
32 Py_ssize_t value = CPyLong_AsSsize_tAndOverflow(object, &overflow);
33 if (unlikely(overflow != 0)) {
34 Py_INCREF(object);
35 return ((CPyTagged)object) | CPY_INT_TAG;
36 } else {
37 return value << 1;
38 }
39 }
40
CPyTagged_StealFromObject(PyObject * object)41 CPyTagged CPyTagged_StealFromObject(PyObject *object) {
42 int overflow;
43 // The overflow check knows about CPyTagged's width
44 Py_ssize_t value = CPyLong_AsSsize_tAndOverflow(object, &overflow);
45 if (unlikely(overflow != 0)) {
46 return ((CPyTagged)object) | CPY_INT_TAG;
47 } else {
48 Py_DECREF(object);
49 return value << 1;
50 }
51 }
52
CPyTagged_BorrowFromObject(PyObject * object)53 CPyTagged CPyTagged_BorrowFromObject(PyObject *object) {
54 int overflow;
55 // The overflow check knows about CPyTagged's width
56 Py_ssize_t value = CPyLong_AsSsize_tAndOverflow(object, &overflow);
57 if (unlikely(overflow != 0)) {
58 return ((CPyTagged)object) | CPY_INT_TAG;
59 } else {
60 return value << 1;
61 }
62 }
63
CPyTagged_AsObject(CPyTagged x)64 PyObject *CPyTagged_AsObject(CPyTagged x) {
65 PyObject *value;
66 if (unlikely(CPyTagged_CheckLong(x))) {
67 value = CPyTagged_LongAsObject(x);
68 Py_INCREF(value);
69 } else {
70 value = CPyLong_FromSsize_t(CPyTagged_ShortAsSsize_t(x));
71 if (value == NULL) {
72 CPyError_OutOfMemory();
73 }
74 }
75 return value;
76 }
77
CPyTagged_StealAsObject(CPyTagged x)78 PyObject *CPyTagged_StealAsObject(CPyTagged x) {
79 PyObject *value;
80 if (unlikely(CPyTagged_CheckLong(x))) {
81 value = CPyTagged_LongAsObject(x);
82 } else {
83 value = CPyLong_FromSsize_t(CPyTagged_ShortAsSsize_t(x));
84 if (value == NULL) {
85 CPyError_OutOfMemory();
86 }
87 }
88 return value;
89 }
90
CPyTagged_AsSsize_t(CPyTagged x)91 Py_ssize_t CPyTagged_AsSsize_t(CPyTagged x) {
92 if (likely(CPyTagged_CheckShort(x))) {
93 return CPyTagged_ShortAsSsize_t(x);
94 } else {
95 return PyLong_AsSsize_t(CPyTagged_LongAsObject(x));
96 }
97 }
98
99 CPy_NOINLINE
CPyTagged_IncRef(CPyTagged x)100 void CPyTagged_IncRef(CPyTagged x) {
101 if (unlikely(CPyTagged_CheckLong(x))) {
102 Py_INCREF(CPyTagged_LongAsObject(x));
103 }
104 }
105
106 CPy_NOINLINE
CPyTagged_DecRef(CPyTagged x)107 void CPyTagged_DecRef(CPyTagged x) {
108 if (unlikely(CPyTagged_CheckLong(x))) {
109 Py_DECREF(CPyTagged_LongAsObject(x));
110 }
111 }
112
113 CPy_NOINLINE
CPyTagged_XDecRef(CPyTagged x)114 void CPyTagged_XDecRef(CPyTagged x) {
115 if (unlikely(CPyTagged_CheckLong(x))) {
116 Py_XDECREF(CPyTagged_LongAsObject(x));
117 }
118 }
119
CPyTagged_Negate(CPyTagged num)120 CPyTagged CPyTagged_Negate(CPyTagged num) {
121 if (CPyTagged_CheckShort(num)
122 && num != (CPyTagged) ((Py_ssize_t)1 << (CPY_INT_BITS - 1))) {
123 // The only possibility of an overflow error happening when negating a short is if we
124 // attempt to negate the most negative number.
125 return -num;
126 }
127 PyObject *num_obj = CPyTagged_AsObject(num);
128 PyObject *result = PyNumber_Negative(num_obj);
129 if (result == NULL) {
130 CPyError_OutOfMemory();
131 }
132 Py_DECREF(num_obj);
133 return CPyTagged_StealFromObject(result);
134 }
135
CPyTagged_Add(CPyTagged left,CPyTagged right)136 CPyTagged CPyTagged_Add(CPyTagged left, CPyTagged right) {
137 // TODO: Use clang/gcc extension __builtin_saddll_overflow instead.
138 if (likely(CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right))) {
139 CPyTagged sum = left + right;
140 if (likely(!CPyTagged_IsAddOverflow(sum, left, right))) {
141 return sum;
142 }
143 }
144 PyObject *left_obj = CPyTagged_AsObject(left);
145 PyObject *right_obj = CPyTagged_AsObject(right);
146 PyObject *result = PyNumber_Add(left_obj, right_obj);
147 if (result == NULL) {
148 CPyError_OutOfMemory();
149 }
150 Py_DECREF(left_obj);
151 Py_DECREF(right_obj);
152 return CPyTagged_StealFromObject(result);
153 }
154
CPyTagged_Subtract(CPyTagged left,CPyTagged right)155 CPyTagged CPyTagged_Subtract(CPyTagged left, CPyTagged right) {
156 // TODO: Use clang/gcc extension __builtin_saddll_overflow instead.
157 if (likely(CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right))) {
158 CPyTagged diff = left - right;
159 if (likely(!CPyTagged_IsSubtractOverflow(diff, left, right))) {
160 return diff;
161 }
162 }
163 PyObject *left_obj = CPyTagged_AsObject(left);
164 PyObject *right_obj = CPyTagged_AsObject(right);
165 PyObject *result = PyNumber_Subtract(left_obj, right_obj);
166 if (result == NULL) {
167 CPyError_OutOfMemory();
168 }
169 Py_DECREF(left_obj);
170 Py_DECREF(right_obj);
171 return CPyTagged_StealFromObject(result);
172 }
173
CPyTagged_Multiply(CPyTagged left,CPyTagged right)174 CPyTagged CPyTagged_Multiply(CPyTagged left, CPyTagged right) {
175 // TODO: Consider using some clang/gcc extension
176 if (CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right)) {
177 if (!CPyTagged_IsMultiplyOverflow(left, right)) {
178 return left * CPyTagged_ShortAsSsize_t(right);
179 }
180 }
181 PyObject *left_obj = CPyTagged_AsObject(left);
182 PyObject *right_obj = CPyTagged_AsObject(right);
183 PyObject *result = PyNumber_Multiply(left_obj, right_obj);
184 if (result == NULL) {
185 CPyError_OutOfMemory();
186 }
187 Py_DECREF(left_obj);
188 Py_DECREF(right_obj);
189 return CPyTagged_StealFromObject(result);
190 }
191
CPyTagged_FloorDivide(CPyTagged left,CPyTagged right)192 CPyTagged CPyTagged_FloorDivide(CPyTagged left, CPyTagged right) {
193 if (CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right)
194 && !CPyTagged_MaybeFloorDivideFault(left, right)) {
195 Py_ssize_t result = ((Py_ssize_t)left / CPyTagged_ShortAsSsize_t(right)) & ~1;
196 if (((Py_ssize_t)left < 0) != (((Py_ssize_t)right) < 0)) {
197 if (result / 2 * right != left) {
198 // Round down
199 result -= 2;
200 }
201 }
202 return result;
203 }
204 PyObject *left_obj = CPyTagged_AsObject(left);
205 PyObject *right_obj = CPyTagged_AsObject(right);
206 PyObject *result = PyNumber_FloorDivide(left_obj, right_obj);
207 Py_DECREF(left_obj);
208 Py_DECREF(right_obj);
209 // Handle exceptions honestly because it could be ZeroDivisionError
210 if (result == NULL) {
211 return CPY_INT_TAG;
212 } else {
213 return CPyTagged_StealFromObject(result);
214 }
215 }
216
CPyTagged_Remainder(CPyTagged left,CPyTagged right)217 CPyTagged CPyTagged_Remainder(CPyTagged left, CPyTagged right) {
218 if (CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right)
219 && !CPyTagged_MaybeRemainderFault(left, right)) {
220 Py_ssize_t result = (Py_ssize_t)left % (Py_ssize_t)right;
221 if (((Py_ssize_t)right < 0) != ((Py_ssize_t)left < 0) && result != 0) {
222 result += right;
223 }
224 return result;
225 }
226 PyObject *left_obj = CPyTagged_AsObject(left);
227 PyObject *right_obj = CPyTagged_AsObject(right);
228 PyObject *result = PyNumber_Remainder(left_obj, right_obj);
229 Py_DECREF(left_obj);
230 Py_DECREF(right_obj);
231 // Handle exceptions honestly because it could be ZeroDivisionError
232 if (result == NULL) {
233 return CPY_INT_TAG;
234 } else {
235 return CPyTagged_StealFromObject(result);
236 }
237 }
238
CPyTagged_IsEq_(CPyTagged left,CPyTagged right)239 bool CPyTagged_IsEq_(CPyTagged left, CPyTagged right) {
240 if (CPyTagged_CheckShort(right)) {
241 return false;
242 } else {
243 int result = PyObject_RichCompareBool(CPyTagged_LongAsObject(left),
244 CPyTagged_LongAsObject(right), Py_EQ);
245 if (result == -1) {
246 CPyError_OutOfMemory();
247 }
248 return result;
249 }
250 }
251
CPyTagged_IsLt_(CPyTagged left,CPyTagged right)252 bool CPyTagged_IsLt_(CPyTagged left, CPyTagged right) {
253 PyObject *left_obj = CPyTagged_AsObject(left);
254 PyObject *right_obj = CPyTagged_AsObject(right);
255 int result = PyObject_RichCompareBool(left_obj, right_obj, Py_LT);
256 Py_DECREF(left_obj);
257 Py_DECREF(right_obj);
258 if (result == -1) {
259 CPyError_OutOfMemory();
260 }
261 return result;
262 }
263
CPyLong_FromStrWithBase(PyObject * o,CPyTagged base)264 PyObject *CPyLong_FromStrWithBase(PyObject *o, CPyTagged base) {
265 Py_ssize_t base_size_t = CPyTagged_AsSsize_t(base);
266 return PyLong_FromUnicodeObject(o, base_size_t);
267 }
268
CPyLong_FromStr(PyObject * o)269 PyObject *CPyLong_FromStr(PyObject *o) {
270 CPyTagged base = CPyTagged_FromSsize_t(10);
271 return CPyLong_FromStrWithBase(o, base);
272 }
273
CPyLong_FromFloat(PyObject * o)274 PyObject *CPyLong_FromFloat(PyObject *o) {
275 if (PyLong_Check(o)) {
276 CPy_INCREF(o);
277 return o;
278 } else {
279 return PyLong_FromDouble(PyFloat_AS_DOUBLE(o));
280 }
281 }
282
CPyBool_Str(bool b)283 PyObject *CPyBool_Str(bool b) {
284 return PyObject_Str(b ? Py_True : Py_False);
285 }
286
CPyLong_NormalizeUnsigned(PyLongObject * v)287 static void CPyLong_NormalizeUnsigned(PyLongObject *v) {
288 Py_ssize_t i = v->ob_base.ob_size;
289 while (i > 0 && v->ob_digit[i - 1] == 0)
290 i--;
291 v->ob_base.ob_size = i;
292 }
293
294 // Bitwise op '&', '|' or '^' using the generic (slow) API
GenericBitwiseOp(CPyTagged a,CPyTagged b,char op)295 static CPyTagged GenericBitwiseOp(CPyTagged a, CPyTagged b, char op) {
296 PyObject *aobj = CPyTagged_AsObject(a);
297 PyObject *bobj = CPyTagged_AsObject(b);
298 PyObject *r;
299 if (op == '&') {
300 r = PyNumber_And(aobj, bobj);
301 } else if (op == '|') {
302 r = PyNumber_Or(aobj, bobj);
303 } else {
304 r = PyNumber_Xor(aobj, bobj);
305 }
306 if (unlikely(r == NULL)) {
307 CPyError_OutOfMemory();
308 }
309 Py_DECREF(aobj);
310 Py_DECREF(bobj);
311 return CPyTagged_StealFromObject(r);
312 }
313
314 // Return pointer to digits of a PyLong object. If it's a short
315 // integer, place digits in the buffer buf instead to avoid memory
316 // allocation (it's assumed to be big enough). Return the number of
317 // digits in *size. *size is negative if the integer is negative.
GetIntDigits(CPyTagged n,Py_ssize_t * size,digit * buf)318 static digit *GetIntDigits(CPyTagged n, Py_ssize_t *size, digit *buf) {
319 if (CPyTagged_CheckShort(n)) {
320 Py_ssize_t val = CPyTagged_ShortAsSsize_t(n);
321 bool neg = val < 0;
322 int len = 1;
323 if (neg) {
324 val = -val;
325 }
326 buf[0] = val & PyLong_MASK;
327 if (val > PyLong_MASK) {
328 val >>= PyLong_SHIFT;
329 buf[1] = val & PyLong_MASK;
330 if (val > PyLong_MASK) {
331 buf[2] = val >> PyLong_SHIFT;
332 len = 3;
333 } else {
334 len = 2;
335 }
336 }
337 *size = neg ? -len : len;
338 return buf;
339 } else {
340 PyLongObject *obj = (PyLongObject *)CPyTagged_LongAsObject(n);
341 *size = obj->ob_base.ob_size;
342 return obj->ob_digit;
343 }
344 }
345
346 // Shared implementation of bitwise '&', '|' and '^' (specified by op) for at least
347 // one long operand. This is somewhat optimized for performance.
BitwiseLongOp(CPyTagged a,CPyTagged b,char op)348 static CPyTagged BitwiseLongOp(CPyTagged a, CPyTagged b, char op) {
349 // Directly access the digits, as there is no fast C API function for this.
350 digit abuf[3];
351 digit bbuf[3];
352 Py_ssize_t asize;
353 Py_ssize_t bsize;
354 digit *adigits = GetIntDigits(a, &asize, abuf);
355 digit *bdigits = GetIntDigits(b, &bsize, bbuf);
356
357 PyLongObject *r;
358 if (unlikely(asize < 0 || bsize < 0)) {
359 // Negative operand. This is slower, but bitwise ops on them are pretty rare.
360 return GenericBitwiseOp(a, b, op);
361 }
362 // Optimized implementation for two non-negative integers.
363 // Swap a and b as needed to ensure a is no longer than b.
364 if (asize > bsize) {
365 digit *tmp = adigits;
366 adigits = bdigits;
367 bdigits = tmp;
368 Py_ssize_t tmp_size = asize;
369 asize = bsize;
370 bsize = tmp_size;
371 }
372 r = _PyLong_New(op == '&' ? asize : bsize);
373 if (unlikely(r == NULL)) {
374 CPyError_OutOfMemory();
375 }
376 Py_ssize_t i;
377 if (op == '&') {
378 for (i = 0; i < asize; i++) {
379 r->ob_digit[i] = adigits[i] & bdigits[i];
380 }
381 } else {
382 if (op == '|') {
383 for (i = 0; i < asize; i++) {
384 r->ob_digit[i] = adigits[i] | bdigits[i];
385 }
386 } else {
387 for (i = 0; i < asize; i++) {
388 r->ob_digit[i] = adigits[i] ^ bdigits[i];
389 }
390 }
391 for (; i < bsize; i++) {
392 r->ob_digit[i] = bdigits[i];
393 }
394 }
395 CPyLong_NormalizeUnsigned(r);
396 return CPyTagged_StealFromObject((PyObject *)r);
397 }
398
399 // Bitwise '&'
CPyTagged_And(CPyTagged left,CPyTagged right)400 CPyTagged CPyTagged_And(CPyTagged left, CPyTagged right) {
401 if (likely(CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right))) {
402 return left & right;
403 }
404 return BitwiseLongOp(left, right, '&');
405 }
406
407 // Bitwise '|'
CPyTagged_Or(CPyTagged left,CPyTagged right)408 CPyTagged CPyTagged_Or(CPyTagged left, CPyTagged right) {
409 if (likely(CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right))) {
410 return left | right;
411 }
412 return BitwiseLongOp(left, right, '|');
413 }
414
415 // Bitwise '^'
CPyTagged_Xor(CPyTagged left,CPyTagged right)416 CPyTagged CPyTagged_Xor(CPyTagged left, CPyTagged right) {
417 if (likely(CPyTagged_CheckShort(left) && CPyTagged_CheckShort(right))) {
418 return left ^ right;
419 }
420 return BitwiseLongOp(left, right, '^');
421 }
422
423 // Bitwise '~'
CPyTagged_Invert(CPyTagged num)424 CPyTagged CPyTagged_Invert(CPyTagged num) {
425 if (likely(CPyTagged_CheckShort(num) && num != CPY_TAGGED_ABS_MIN)) {
426 return ~num & ~CPY_INT_TAG;
427 } else {
428 PyObject *obj = CPyTagged_AsObject(num);
429 PyObject *result = PyNumber_Invert(obj);
430 if (unlikely(result == NULL)) {
431 CPyError_OutOfMemory();
432 }
433 Py_DECREF(obj);
434 return CPyTagged_StealFromObject(result);
435 }
436 }
437
438 // Bitwise '>>'
CPyTagged_Rshift(CPyTagged left,CPyTagged right)439 CPyTagged CPyTagged_Rshift(CPyTagged left, CPyTagged right) {
440 if (likely(CPyTagged_CheckShort(left)
441 && CPyTagged_CheckShort(right)
442 && (Py_ssize_t)right >= 0)) {
443 CPyTagged count = CPyTagged_ShortAsSsize_t(right);
444 if (unlikely(count >= CPY_INT_BITS)) {
445 if ((Py_ssize_t)left >= 0) {
446 return 0;
447 } else {
448 return CPyTagged_ShortFromInt(-1);
449 }
450 }
451 return ((Py_ssize_t)left >> count) & ~CPY_INT_TAG;
452 } else {
453 // Long integer or negative shift -- use generic op
454 PyObject *lobj = CPyTagged_AsObject(left);
455 PyObject *robj = CPyTagged_AsObject(right);
456 PyObject *result = PyNumber_Rshift(lobj, robj);
457 Py_DECREF(lobj);
458 Py_DECREF(robj);
459 if (result == NULL) {
460 // Propagate error (could be negative shift count)
461 return CPY_INT_TAG;
462 }
463 return CPyTagged_StealFromObject(result);
464 }
465 }
466
IsShortLshiftOverflow(Py_ssize_t short_int,Py_ssize_t shift)467 static inline bool IsShortLshiftOverflow(Py_ssize_t short_int, Py_ssize_t shift) {
468 return ((Py_ssize_t)(short_int << shift) >> shift) != short_int;
469 }
470
471 // Bitwise '<<'
CPyTagged_Lshift(CPyTagged left,CPyTagged right)472 CPyTagged CPyTagged_Lshift(CPyTagged left, CPyTagged right) {
473 if (likely(CPyTagged_CheckShort(left)
474 && CPyTagged_CheckShort(right)
475 && (Py_ssize_t)right >= 0
476 && right < CPY_INT_BITS * 2)) {
477 CPyTagged shift = CPyTagged_ShortAsSsize_t(right);
478 if (!IsShortLshiftOverflow(left, shift))
479 // Short integers, no overflow
480 return left << shift;
481 }
482 // Long integer or out of range shift -- use generic op
483 PyObject *lobj = CPyTagged_AsObject(left);
484 PyObject *robj = CPyTagged_AsObject(right);
485 PyObject *result = PyNumber_Lshift(lobj, robj);
486 Py_DECREF(lobj);
487 Py_DECREF(robj);
488 if (result == NULL) {
489 // Propagate error (could be negative shift count)
490 return CPY_INT_TAG;
491 }
492 return CPyTagged_StealFromObject(result);
493 }
494