(original) (raw)

/* Long (arbitrary precision) integer object implementation */ /* XXX The functional organization of this file is terrible */ #include "Python.h" #include "longintrepr.h" #include #undef COUNT_ALLOCS #ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257 #endif #ifndef NSMALLNEGINTS #define NSMALLNEGINTS 5 #endif #define INT_OPERATIONS #define ABS(x) ((x) < 0 ? -(x) : (x)) #define MPZ(x) (((PyLongObject*)x)->number) #define SIGN(x) mpz_sgn(MPZ(x)) #define FITS_INT(x) mpz_fits_sint_p(MPZ(x)) #define FITS_UINT(x) mpz_fits_uint_p(MPZ(x)) #define GET_INT(x) mpz_get_si(MPZ(x)) #define GET_UINT(x) mpz_get_ui(MPZ(x)) #define MPZ_ENDIAN(little_endian) ((little_endian)?-1:1) #if NSMALLNEGINTS + NSMALLPOSINTS > 0 /* Small integers are preallocated in this array so that they can be shared. The integers that are preallocated are those in the range -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive). */ static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS]; #ifdef COUNT_ALLOCS int quick_int_allocs, quick_neg_int_allocs; #endif static PyObject * get_small_int(int ival) { PyObject *v = (PyObject*)(small_ints + ival + NSMALLNEGINTS); Py_INCREF(v); #ifdef COUNT_ALLOCS if (ival >= 0) quick_int_allocs++; else quick_neg_int_allocs++; #endif return v; } #define CHECK_SMALL_INT(ival) \ if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \ return get_small_int((int)ival); \ } #define CHECK_SMALL_UINT(ival) \ do if (ival < NSMALLPOSINTS) { \ return get_small_int((int)ival); \ } while(0) static PyLongObject * maybe_small_long(PyLongObject *v) { int val; if (!FITS_INT(v)) return v; val = GET_INT(v); if (-NSMALLNEGINTS <= val && val < NSMALLPOSINTS) { Py_DECREF(v); return (PyLongObject *)get_small_int(val); } return v; } #else #define CHECK_SMALL_INT(ival) #define maybe_small_long(val) (val) #endif static PyObject* long_neg(PyLongObject *v); static PyObject* long_invert(PyLongObject *v); static PyObject* long_long(PyObject *v); static void PyLong_FatalMemoryError(void) { Py_FatalError("unable to allocate memory for an integer"); } static void* PyLong_Malloc(size_t size) { void *p = PyObject_MALLOC(size); if (!p) PyLong_FatalMemoryError(); return p; } static void* PyLong_Realloc(void *ptr, size_t oldsize, size_t newsize) { void *p = PyObject_Realloc(ptr, newsize); if (!p) PyLong_FatalMemoryError(); return p; } static void PyLong_Free(void *ptr, size_t size) { PyObject_FREE(ptr); } /* Allocate a new long int object with size digits. Return NULL and set exception if we run out of memory. */ PyLongObject * _PyLong_New(void) { PyLongObject *result; result = PyObject_MALLOC(sizeof(PyLongObject)); if (!result) { PyErr_NoMemory(); return NULL; } PyObject_INIT(result, &PyLong_Type); mpz_init (result->number); return result; } PyObject * _PyLong_Copy(PyLongObject *src) { PyLongObject *result; assert(src != NULL); result = _PyLong_New(); mpz_set(result->number, src->number); return (PyObject *)result; } /* Create a new long int object from a C long int */ PyObject * PyLong_FromLong(long ival) { PyLongObject *v; CHECK_SMALL_INT(ival); v = _PyLong_New(); mpz_set_si(v->number, ival); return (PyObject *)v; } /* Create a new long int object from a C unsigned long int */ PyObject * PyLong_FromUnsignedLong(unsigned long ival) { PyLongObject *v; CHECK_SMALL_UINT(ival); v = _PyLong_New(); mpz_set_ui(v->number, ival); return (PyObject *)v; } /* Create a new long int object from a C double */ PyObject * PyLong_FromDouble(double dval) { PyLongObject *v; if (Py_IS_INFINITY(dval)) { PyErr_SetString(PyExc_OverflowError, "cannot convert float infinity to integer"); return NULL; } if (Py_IS_NAN(dval)) { PyErr_SetString(PyExc_ValueError, "cannot convert float NaN to integer"); return NULL; } v = _PyLong_New(); mpz_set_d(v->number, dval); return (PyObject *)v; } /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define * anything about what happens when a signed integer operation overflows, * and some compilers think they're doing you a favor by being "clever" * then. The bit pattern for the largest postive signed long is * (unsigned long)LONG_MAX, and for the smallest negative signed long * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN. * However, some other compilers warn about applying unary minus to an * unsigned operand. Hence the weird "0-". */ #define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN) #define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN) /* Get a C long int from a long int object. Returns -1 and sets an error condition if overflow occurs. */ long PyLong_AsLongAndOverflow(PyObject *vv, int *overflow) { union { long number; unsigned char bytes[sizeof(long)]; } result; int res; int do_decref = 0; /* if nb_int was called */ *overflow = 0; if (vv == NULL) { PyErr_BadInternalCall(); return -1; } if (!PyLong_Check(vv)) { PyNumberMethods *nb; if ((nb = vv->ob_type->tp_as_number) == NULL || nb->nb_int == NULL) { PyErr_SetString(PyExc_TypeError, "an integer is required"); return -1; } vv = (*nb->nb_int) (vv); if (vv == NULL) return -1; do_decref = 1; if (!PyLong_Check(vv)) { Py_DECREF(vv); PyErr_SetString(PyExc_TypeError, "nb_int should return int object"); return -1; } } res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1); if (res != 0) { result.number = -1L; *overflow = 1; } if (do_decref) { Py_DECREF(vv); } return result.number; } long PyLong_AsLong(PyObject *obj) { int overflow; long result = PyLong_AsLongAndOverflow(obj, &overflow); if (overflow) { /* XXX: could be cute and give a different message for overflow == -1 */ PyErr_SetString(PyExc_OverflowError, "Python int too large to convert to C long"); } return result; } /* Get a Py_ssize_t from a long int object. Returns -1 and sets an error condition if overflow occurs. */ Py_ssize_t PyLong_AsSsize_t(PyObject *vv) { union { Py_ssize_t number; unsigned char bytes[sizeof(Py_ssize_t)]; } result; int res; if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return -1; } res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1); if (res != 0) return -1; return result.number; } /* Get a C unsigned long int from a long int object. Returns -1 and sets an error condition if overflow occurs. */ unsigned long PyLong_AsUnsignedLong(PyObject *vv) { if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return (unsigned long) -1; } if (!FITS_UINT(vv)) { PyErr_SetString(PyExc_OverflowError, "can't convert negative value to unsigned int"); return (unsigned long) -1; } return GET_UINT(vv); } /* Get a C unsigned long int from a long int object. Returns -1 and sets an error condition if overflow occurs. */ size_t PyLong_AsSize_t(PyObject *vv) { union { size_t number; unsigned char bytes[sizeof(size_t)]; } result; int res; if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return (unsigned long) -1; } res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 0); if (res != 0) return -1; return result.number; } /* Get a C unsigned long int from a long int object, ignoring the high bits. Returns -1 and sets an error condition if an error occurs. */ static unsigned long _PyLong_AsUnsignedLongMask(PyLongObject *orig) { PyLongObject* v; PyObject* mask; unsigned long ival; mask = PyLong_FromUnsignedLong(ULONG_MAX); v = _PyLong_New(); mpz_set(MPZ(v), MPZ(orig)); mpz_and(MPZ(v), MPZ(v), MPZ(mask)); ival = GET_UINT(v); Py_DECREF(mask); Py_DECREF(v); return ival; } unsigned long PyLong_AsUnsignedLongMask(register PyObject *op) { PyNumberMethods *nb; PyLongObject *lo; unsigned long val; if (op && PyLong_Check(op)) return _PyLong_AsUnsignedLongMask((PyLongObject *)op); if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL || nb->nb_int == NULL) { PyErr_SetString(PyExc_TypeError, "an integer is required"); return (unsigned long)-1; } lo = (PyLongObject*) (*nb->nb_int) (op); if (lo == NULL) return (unsigned long)-1; if (PyLong_Check(lo)) { val = _PyLong_AsUnsignedLongMask(lo); Py_DECREF(lo); if (PyErr_Occurred()) return (unsigned long)-1; return val; } else { Py_DECREF(lo); PyErr_SetString(PyExc_TypeError, "nb_int should return int object"); return (unsigned long)-1; } } int _PyLong_Sign(PyObject *vv) { return SIGN(vv); } size_t _PyLong_NumBits(PyObject *vv) { assert(v != NULL); assert(PyLong_Check(v)); if (SIGN(vv) == 0) return 0; return mpz_sizeinbase(MPZ(vv), 2); } PyObject * _PyLong_FromByteArray(const unsigned char* constbytes, size_t n, int little_endian, int is_signed) { PyLongObject *result; int order; int neg; /* FIXME: don't use the stack! */ unsigned char bytes[n]; if (n == 0) return PyLong_FromLong(0L); result = _PyLong_New(); if (!result) return NULL; neg = 0; memcpy(bytes, constbytes, n); if (is_signed) { size_t index; if (little_endian) index = n-1; else index = 0; if (bytes[index] >= 0x80) { size_t i; for (i=0; i<n; i++)="" bytes[i]="~bytes[i];" neg="1;" }="" order="MPZ_ENDIAN(little_endian);" mpz_import(result-="">number, n, order, sizeof(bytes[0]), order, 0, bytes); if (neg) { PyObject* invert = long_invert(result); Py_DECREF(result); if (!invert) return NULL; result = (PyLongObject*)invert; } return (PyObject*)result; } int _PyLong_AsByteArray(PyLongObject* v, unsigned char* bytes, size_t n, int little_endian, int is_signed) { size_t count; assert(v != NULL && PyLong_Check(v)); int order; if (SIGN(v) < 0) { if (!is_signed) { PyErr_SetString(PyExc_TypeError, "can't convert negative int to unsigned"); return -1; } } count = mpz_sizeinbase(MPZ(v), 256); if (count > n) goto overflow; order = MPZ_ENDIAN(little_endian); mpz_export(bytes, &count, order, sizeof(bytes[0]), order, 0, v->number); if (count != n) { size_t padding = n - count; if (little_endian) { memset(bytes + count, 0, padding); } else { memmove(bytes + padding, bytes, count); memset(bytes, 0, padding); } } if (SIGN(v) < 0) { ssize_t i; for (i=0; i<n; i++)="" {="" bytes[i]="~bytes[i];" }="" if="" (little_endian)="" for="" (i="0;" i<n;="" (bytes[i]="" !="0xff)" bytes[i]++;="" break;="" else="" 0<="i;" i--)="" (is_signed="" &&="" (count="=" n))="" int="" s1="SIGN(v)," s2,="" index;="" (s1="" index="n-1;" (bytes[index]="">= 0x80) s2 = -1; else s2 = 1; if (s1 != s2) goto overflow; } } return 0; overflow: PyErr_SetString(PyExc_OverflowError, "int too big to convert"); return -1; } double _PyLong_AsScaledDouble(PyObject *vv, int *exponent) { double result; long long_exponent; if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return -1; } result = mpz_get_d_2exp(&long_exponent, MPZ(vv)); *exponent = long_exponent; return result; } /* Get a C double from a long int object. */ double PyLong_AsDouble(PyObject *vv) { int e = -1; double x; if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return -1; } x = _PyLong_AsScaledDouble(vv, &e); if (x == -1.0 && PyErr_Occurred()) return -1.0; /* 'e' initialized to -1 to silence gcc-4.0.x, but it should be set correctly after a successful _PyLong_AsScaledDouble() call */ assert(e >= 0); if (e > INT_MAX) goto overflow; errno = 0; x = ldexp(x, e); if (Py_OVERFLOWED(x)) goto overflow; return x; overflow: PyErr_SetString(PyExc_OverflowError, "Python int too large to convert to C double"); return -1.0; } /* Create a new long (or int) object from a C pointer */ PyObject * PyLong_FromVoidPtr(void *p) { #ifndef HAVE_LONG_LONG # error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long" #endif #if SIZEOF_LONG_LONG < SIZEOF_VOID_P # error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)" #endif /* special-case null pointer */ if (!p) return PyLong_FromLong(0); return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)(Py_uintptr_t)p); } /* Get a C pointer from a long object (or an int object in some cases) */ void * PyLong_AsVoidPtr(PyObject *vv) { /* This function will allow int or long objects. If vv is neither, then the PyLong_AsLong*() functions will raise the exception: PyExc_SystemError, "bad argument to internal function" */ #if SIZEOF_VOID_P <= SIZEOF_LONG long x; if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0) x = PyLong_AsLong(vv); else x = PyLong_AsUnsignedLong(vv); #else #ifndef HAVE_LONG_LONG # error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long" #endif #if SIZEOF_LONG_LONG < SIZEOF_VOID_P # error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)" #endif PY_LONG_LONG x; if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0) x = PyLong_AsLongLong(vv); else x = PyLong_AsUnsignedLongLong(vv); #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */ if (x == -1 && PyErr_Occurred()) return NULL; return (void *)x; } #ifdef HAVE_LONG_LONG /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later * rewritten to use the newer PyLong_{As,From}ByteArray API. */ #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one /* Create a new long int object from a C PY_LONG_LONG int. */ PyObject * PyLong_FromLongLong(PY_LONG_LONG ival) { union { PY_LONG_LONG number; unsigned char bytes[sizeof(PY_LONG_LONG)]; } val; CHECK_SMALL_INT(ival); val.number = ival; return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 1); } /* Create a new long int object from a C unsigned PY_LONG_LONG int. */ PyObject * PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival) { union { unsigned PY_LONG_LONG number; unsigned char bytes[sizeof(unsigned PY_LONG_LONG)]; } val; CHECK_SMALL_UINT(ival); val.number = ival; return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 0); } /* Create a new long int object from a C Py_ssize_t. */ PyObject * PyLong_FromSsize_t(Py_ssize_t ival) { union { Py_ssize_t number; unsigned char bytes[sizeof(Py_ssize_t)]; } val; CHECK_SMALL_INT(ival); val.number = ival; return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 1); } /* Create a new long int object from a C size_t. */ PyObject * PyLong_FromSize_t(size_t ival) { union { ssize_t number; unsigned char bytes[sizeof(ssize_t)]; } val; CHECK_SMALL_UINT(ival); val.number = ival; return _PyLong_FromByteArray(val.bytes, sizeof(val.bytes), 1, 0); } /* Get a C PY_LONG_LONG int from a long int object. Return -1 and set an error if overflow occurs. */ static PY_LONG_LONG _PyLong_AsLongLong(PyObject *vv) { union { PY_LONG_LONG number; unsigned char bytes[sizeof(PY_LONG_LONG)]; } result; int res; res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 1); if (res != 0) return (PY_LONG_LONG)-1; return result.number; } PY_LONG_LONG PyLong_AsLongLong(PyObject *vv) { PY_LONG_LONG bytes; if (vv == NULL) { PyErr_BadInternalCall(); return -1; } if (!PyLong_Check(vv)) { PyNumberMethods *nb; PyObject *io; if ((nb = vv->ob_type->tp_as_number) == NULL || nb->nb_int == NULL) { PyErr_SetString(PyExc_TypeError, "an integer is required"); return -1; } io = (*nb->nb_int) (vv); if (io == NULL) return -1; if (PyLong_Check(io)) { bytes = _PyLong_AsLongLong((PyObject*)io); Py_DECREF(io); return bytes; } Py_DECREF(io); PyErr_SetString(PyExc_TypeError, "integer conversion failed"); return -1; } return _PyLong_AsLongLong((PyObject*)vv); } /* Get a C unsigned PY_LONG_LONG int from a long int object. Return -1 and set an error if overflow occurs. */ unsigned PY_LONG_LONG PyLong_AsUnsignedLongLong(PyObject *vv) { union { unsigned PY_LONG_LONG number; unsigned char bytes[sizeof(unsigned PY_LONG_LONG)]; } result; int res; if (vv == NULL || !PyLong_Check(vv)) { PyErr_BadInternalCall(); return (unsigned PY_LONG_LONG)-1; } res = _PyLong_AsByteArray((PyLongObject*)vv, result.bytes, sizeof(result.bytes), 1, 0); if (res != 0) return (unsigned PY_LONG_LONG)-1; return result.number; } static unsigned PY_LONG_LONG _PyLong_AsUnsignedLongLongMask(PyObject *orig) { PyLongObject* v; PyObject* mask; unsigned PY_LONG_LONG ival; mask = PyLong_FromUnsignedLongLong(ULLONG_MAX); v = _PyLong_New(); mpz_set(MPZ(v), MPZ(orig)); mpz_and(MPZ(v), MPZ(v), MPZ(mask)); ival = PyLong_AsUnsignedLongLong((PyObject*)v); Py_DECREF(mask); Py_DECREF(v); return ival; } unsigned PY_LONG_LONG PyLong_AsUnsignedLongLongMask(register PyObject *op) { PyNumberMethods *nb; PyLongObject *lo; unsigned PY_LONG_LONG val; if (op && PyLong_Check(op)) return _PyLong_AsUnsignedLongLongMask(op); if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL || nb->nb_int == NULL) { PyErr_SetString(PyExc_TypeError, "an integer is required"); return (unsigned PY_LONG_LONG)-1; } lo = (PyLongObject*) (*nb->nb_int) (op); if (lo == NULL) return (unsigned PY_LONG_LONG)-1; if (PyLong_Check(lo)) { val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo); Py_DECREF(lo); if (PyErr_Occurred()) return (unsigned PY_LONG_LONG)-1; return val; } else { Py_DECREF(lo); PyErr_SetString(PyExc_TypeError, "nb_int should return int object"); return (unsigned PY_LONG_LONG)-1; } } #undef IS_LITTLE_ENDIAN #endif /* HAVE_LONG_LONG */ #define CHECK_BINOP(v,w) \ if (!PyLong_Check(v) || !PyLong_Check(w)) { \ Py_INCREF(Py_NotImplemented); \ return Py_NotImplemented; \ } PyObject * _PyLong_Format(PyObject *aa, int base) { register PyLongObject *a = (PyLongObject *)aa; char* c_str, *c_str_ptr; size_t len; PyObject *str; Py_UNICODE *strptr; c_str = mpz_get_str(NULL, base, a->number); if (!c_str) { /* FIXME: use mpz error code */ PyErr_NoMemory(); return NULL; } /* NEED MODIFIABLE STRING, ref=1 */ len = strlen(c_str); if (base == 2 || base == 8 || base == 16) len += 2; else if (base != 10) len += 3; str = PyUnicode_FromStringAndSize(NULL, len); c_str_ptr = c_str; strptr = PyUnicode_AS_UNICODE(str); if (*c_str_ptr == '-') { *strptr++ = *c_str_ptr++; } if (base == 16) { *strptr++ = '0'; *strptr++ = 'x'; } else if (base == 8) { *strptr++ = '0'; *strptr++ = 'o'; } else if (base == 2) { *strptr++ = '0'; *strptr++ = 'b'; } else if (base != 10) { if (base > 10) *strptr++ = '0' + base/10; *strptr++ = '0' + base%10; *strptr++ = '#'; } for(; *c_str_ptr != '\0'; c_str_ptr++) { *strptr++ = *c_str_ptr; } PyLong_Free(c_str, 0); return (PyObject *)str; } PyObject * PyLong_FromString(char *str, char **pend, int base) { PyLongObject *result; int sign = 1, error_if_nonzero = 0; int ret; char *orig_str; if ((base != 0 && base < 2) || base > 36) { PyErr_SetString(PyExc_ValueError, "int() arg 2 must be >= 2 and <= 36"); return NULL; } orig_str = str; while (*str != '\0' && isspace(Py_CHARMASK(*str))) str++; if (*str == '+') ++str; else if (*str == '-') { ++str; sign = -1; } if (base == 0) { if (str[0] != '0') base = 10; else if (str[1] == 'x' || str[1] == 'X') base = 16; else if (str[1] == 'o' || str[1] == 'O') base = 8; else if (str[1] == 'b' || str[1] == 'B') base = 2; else { /* "old" (C-style) octal literal, now invalid. it might still be zero though */ error_if_nonzero = 1; base = 10; } } if (str[0] == '0' && ((base == 16 && (str[1] == 'x' || str[1] == 'X')) || (base == 8 && (str[1] == 'o' || str[1] == 'O')) || (base == 2 && (str[1] == 'b' || str[1] == 'B')))) str += 2; result = _PyLong_New(); if (!result) return NULL; ret = mpz_set_str(result->number, str, base); if (ret != 0) { PyObject *strobj; Py_ssize_t slen; Py_XDECREF(result); slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200; strobj = PyUnicode_FromStringAndSize(orig_str, slen); if (strobj == NULL) { return NULL; } if (error_if_nonzero) { /* reset the base to 0, else the exception message doesn't make too much sense */ base = 0; } PyErr_Format(PyExc_ValueError, "invalid literal for int() with base %d: %R", base, strobj); Py_DECREF(strobj); return NULL; } if (sign < 0) mpz_neg(MPZ(result), MPZ(result)); result = maybe_small_long(result); return (PyObject*)result; } PyObject * PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base) { PyObject *result; char *buffer = (char *)PyMem_MALLOC(length+1); if (buffer == NULL) return NULL; if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) { PyMem_FREE(buffer); return NULL; } result = PyLong_FromString(buffer, NULL, base); PyMem_FREE(buffer); return result; } /* Methods */ static void long_dealloc(PyObject *v) { mpz_clear(MPZ(v)); Py_TYPE(v)->tp_free(v); } static PyObject * long_repr(PyObject *v) { return _PyLong_Format(v, 10); } static int long_compare(PyLongObject *a, PyLongObject *b) { int r = mpz_cmp(a->number, b->number); if (r > 0) return 1; else if (r < 0) return -1; else return 0; } static PyObject * long_richcompare(PyObject *self, PyObject *other, int op) { PyObject *result; CHECK_BINOP(self, other); result = Py_CmpToRich(op, long_compare((PyLongObject*)self, (PyLongObject*)other)); return result; } static long long_hash(PyLongObject *v) { long x; /* FIXME: Use MSB! */ x = GET_INT(v); if (x == -1) x = -2; return x; } static PyObject * long_add(PyLongObject *a, PyLongObject *b) { PyLongObject *z; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(a) && FITS_INT(b)) { int aa = GET_INT(a); int bb = GET_INT(b); int sum = aa + bb; if (((aa < 0) ^ (bb < 0)) || ((aa < 0) == (sum < 0))) { return PyLong_FromLong(sum); } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_add(z->number, a->number, b->number); return (PyObject*) maybe_small_long(z); } static PyObject * long_sub(PyLongObject *a, PyLongObject *b) { PyLongObject *z; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(a) && FITS_INT(b)) { int aa = GET_INT(a); int bb = GET_INT(b); int diff = aa - bb; if (((aa < 0) == (bb < 0)) || ((aa < 0) == (diff < 0))) { return PyLong_FromLong(diff); } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_sub(z->number, a->number, b->number); return (PyObject*) maybe_small_long(z); } static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { PyLongObject *z; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(a) && FITS_INT(b)) { int aa = GET_INT(a); int bb = GET_INT(b); int product; if (aa != INT_MIN || (bb == 0) || (bb == 1)) { product = aa * bb; if (aa == 0 || bb == 0 || (product / bb) == aa) { return PyLong_FromLong(product); } } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_mul(z->number, a->number, b->number); return (PyObject*) maybe_small_long(z); } static PyObject * long_div(PyObject *a, PyObject *b) { PyLongObject *div; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(b)) { int bb = GET_INT(b); if (bb == 0) { PyErr_SetString(PyExc_ZeroDivisionError, "integer division or modulo by zero"); return NULL; } if (FITS_INT(a)) { int aa = GET_INT(a); if (aa != INT_MIN || bb != -1) { int q = aa / bb; if (((aa < 0) != (bb < 0)) && (aa % bb != 0)) q -= 1; div = (PyLongObject*)PyLong_FromLong(q); return (PyObject*)div; } } } #endif div = _PyLong_New(); if (!div) return NULL; mpz_fdiv_q(div->number, MPZ(a), MPZ(b)); return (PyObject *)div; } static PyObject * long_true_divide(PyObject *a, PyObject *b) { double ad, bd; int failed, aexp = -1, bexp = -1; CHECK_BINOP(a, b); ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp); bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp); failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred(); if (failed) return NULL; /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x, but should really be set correctly after sucessful calls to _PyLong_AsScaledDouble() */ assert(aexp >= 0 && bexp >= 0); if (bd == 0.0) { PyErr_SetString(PyExc_ZeroDivisionError, "int division or modulo by zero"); return NULL; } /* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */ ad /= bd; /* overflow/underflow impossible here */ aexp -= bexp; if (aexp > INT_MAX) goto overflow; else if (aexp < -INT_MAX) return PyFloat_FromDouble(0.0); /* underflow to 0 */ errno = 0; ad = ldexp(ad, aexp); if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */ goto overflow; return PyFloat_FromDouble(ad); overflow: PyErr_SetString(PyExc_OverflowError, "int/int too large for a float"); return NULL; } static PyObject * long_mod(PyObject *a, PyObject *b) { PyLongObject *z; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(b)) { int aa, bb, r; bb = GET_INT(b); if (bb == 0) { PyErr_SetString(PyExc_ZeroDivisionError, "integer division or modulo by zero"); return NULL; } if (FITS_INT(a)) { aa = GET_INT(a); r = aa % bb; if (r && (aa < 0) != (bb < 0)) r += bb; z = (PyLongObject*)PyLong_FromLong(r); return (PyObject*)z; } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_mod(z->number, MPZ(a), MPZ(b)); if (mpz_cmp_ui(z->number, 0) != 0 && SIGN(b) < 0 && mpz_cmp_si(MPZ(b), -1) != 0) { mpz_add(z->number, z->number, MPZ(b)); } return (PyObject *)z; } static PyObject * long_divmod(PyObject *a, PyObject *b) { PyLongObject *div, *mod; PyObject *z; CHECK_BINOP(a, b); #ifdef INT_OPERATIONS if (FITS_INT(a) && FITS_INT(b)) { int aa = GET_INT(a); int bb = GET_INT(b); if (aa != INT_MIN || bb != -1) { int divi = aa / bb; int modi = aa % bb; if (((aa < 0) != (bb < 0)) && (modi != 0)) { divi -= 1; modi += bb; } return Py_BuildValue("(ii)", divi, modi); } } #endif div = _PyLong_New(); if (!div) return NULL; mod = _PyLong_New(); if (!mod) { Py_DECREF(div); return NULL; } mpz_fdiv_qr(div->number, mod->number, MPZ(a), MPZ(b)); z = PyTuple_New(2); if (z != NULL) { PyTuple_SetItem(z, 0, (PyObject *) div); PyTuple_SetItem(z, 1, (PyObject *) mod); } else { Py_DECREF(div); Py_DECREF(mod); } return z; } /* pow(v, w, x) */ static PyObject * long_pow(PyObject *v, PyObject *w, PyObject *x) { PyLongObject *z; PyLongObject *c; CHECK_BINOP(v, w); z = _PyLong_New(); if (!z) return NULL; if (PyLong_Check(x)) { c = (PyLongObject *)x; } else { if (x != Py_None) { Py_INCREF(Py_NotImplemented); return Py_NotImplemented; } else { c = NULL; } } if (SIGN(w) < 0) { if (c) { PyErr_SetString(PyExc_TypeError, "pow() 2nd argument " "cannot be negative when 3rd argument specified"); goto error; } /* else return a float. This works because we know that this calls float_pow() which converts its arguments to double. */ return PyFloat_Type.tp_as_number->nb_power(v, w, x); } if (c) { if (SIGN(c) == 0) { PyErr_SetString(PyExc_ValueError, "pow() 3rd argument cannot be 0"); goto error; } mpz_powm(MPZ(z), MPZ(v), MPZ(w), MPZ(c)); if (SIGN(c) < 0 && SIGN(z) != 0) mpz_add(MPZ(z), MPZ(z), MPZ(c)); } else { int exp; if (!FITS_INT(w)) { PyErr_SetString(PyExc_OverflowError, "exponent doesn't fit in an integer"); return NULL; } exp = GET_INT(w); mpz_pow_ui(z->number, MPZ(v), exp); } return (PyObject*) maybe_small_long(z); error: Py_DECREF(z); return NULL; } static PyObject * long_invert(PyLongObject *v) { PyLongObject *z; #ifdef INT_OPERATIONS if (FITS_INT(v)) return PyLong_FromLong(-(GET_INT(v)+1)); #endif z = _PyLong_New(); if (!z) return NULL; mpz_neg(z->number, v->number); mpz_sub_ui(z->number, z->number, 1); return (PyObject *)z; } static PyObject * long_neg(PyLongObject *v) { PyLongObject *z; #ifdef INT_OPERATIONS if (FITS_INT(v)) { int val = GET_INT(v); int neg = -val; if (neg != val) return PyLong_FromLong(neg); } #endif z = _PyLong_New(); if (!z) return NULL; mpz_neg(z->number, v->number); return (PyObject *)z; } static PyObject * long_abs(PyLongObject *v) { PyLongObject *z; #ifdef INT_OPERATIONS if (FITS_INT(v)) { int val = GET_INT(v); int aval = ABS(val); if (val != aval) { return PyLong_FromLong(aval); } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_abs(z->number, v->number); return (PyObject *)z; } static int long_bool(PyLongObject *v) { return SIGN(v) != 0; } static PyObject * long_rshift(PyLongObject *a, PyLongObject *b) { PyLongObject *z = NULL; long shiftby; CHECK_BINOP(a, b); if ((mpz_cmp_si(MPZ(a), 0) < 0)) { /* Right shifting negative numbers is harder */ PyLongObject *a1, *a2; a1 = (PyLongObject *) long_invert(a); if (a1 == NULL) goto rshift_error; a2 = (PyLongObject *) long_rshift(a1, b); Py_DECREF(a1); if (a2 == NULL) goto rshift_error; z = (PyLongObject *) long_invert(a2); Py_DECREF(a2); z = maybe_small_long(z); return (PyObject *) z; } shiftby = PyLong_AsLong((PyObject *)b); if (shiftby == -1L && PyErr_Occurred()) goto rshift_error; if (shiftby < 0) { PyErr_SetString(PyExc_ValueError, "negative shift count"); goto rshift_error; } #ifdef INT_OPERATIONS if (FITS_INT(a)) { int aa = GET_INT(a); int shifted; if (shiftby < sizeof(int) * 8) shifted = aa >> shiftby; else shifted = 0; return PyLong_FromLong(shifted); } #endif z = _PyLong_New(); if (!z) return NULL; mpz_fdiv_q_2exp(z->number, a->number, shiftby); z = maybe_small_long(z); rshift_error: return (PyObject *) z; } static PyObject * long_lshift(PyObject *v, PyObject *w) { /* This version due to Tim Peters */ PyLongObject *a = (PyLongObject*)v; PyLongObject *b = (PyLongObject*)w; PyLongObject *z = NULL; long shiftby; CHECK_BINOP(a, b); shiftby = PyLong_AsLong((PyObject *)b); if (shiftby == -1L && PyErr_Occurred()) goto lshift_error; if (shiftby < 0) { PyErr_SetString(PyExc_ValueError, "negative shift count"); goto lshift_error; } if ((long)(int)shiftby != shiftby) { PyErr_SetString(PyExc_ValueError, "outrageous left shift count"); goto lshift_error; } #ifdef INT_OPERATIONS if ((shiftby < sizeof(int) * 8) && FITS_INT(a)) { int aa = GET_INT(a); int shifted = aa << shiftby; if ((shifted >> shiftby) == aa) { return PyLong_FromLong(shifted); } } #endif z = _PyLong_New(); if (!z) return NULL; mpz_mul_2exp(z->number, a->number, shiftby); z = maybe_small_long(z); lshift_error: return (PyObject *) z; } /* Bitwise and/xor/or operations */ static PyObject * long_bitwise(PyLongObject *a, int op, /* '&', '|', '^' */ PyLongObject *b) { PyLongObject *z; #ifdef INT_OPERATIONS if (FITS_INT(a) && FITS_INT(b)) { int aa = GET_INT(a); int bb = GET_INT(b); int r; switch (op) { case '^': r = aa ^ bb; break; case '&': r = aa & bb; break; case '|': r = aa | bb; break; } return PyLong_FromLong(r); } #endif z = _PyLong_New(); if (!z) return NULL; switch (op) { case '^': mpz_xor(z->number, MPZ(a), MPZ(b)); break; case '&': mpz_and(z->number, MPZ(a), MPZ(b)); break; case '|': mpz_ior(z->number, MPZ(a), MPZ(b)); break; } return (PyObject*) maybe_small_long(z); } static PyObject * long_and(PyObject *a, PyObject *b) { PyObject *c; CHECK_BINOP(a, b); c = long_bitwise((PyLongObject*)a, '&', (PyLongObject*)b); return c; } static PyObject * long_xor(PyObject *a, PyObject *b) { PyObject *c; CHECK_BINOP(a, b); c = long_bitwise((PyLongObject*)a, '^', (PyLongObject*)b); return c; } static PyObject * long_or(PyObject *a, PyObject *b) { PyObject *c; CHECK_BINOP(a, b); c = long_bitwise((PyLongObject*)a, '|', (PyLongObject*)b); return c; } static PyObject * long_long(PyObject *v) { if (PyLong_CheckExact(v)) Py_INCREF(v); else v = _PyLong_Copy((PyLongObject *)v); return v; } static PyObject * long_float(PyObject *v) { double result; result = PyLong_AsDouble(v); if (result == -1.0 && PyErr_Occurred()) return NULL; return PyFloat_FromDouble(result); } static PyObject * long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds); static PyObject * long_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *x = NULL; int base = -909; /* unlikely! */ static char *kwlist[] = {"x", "base", 0}; if (type != &PyLong_Type) return long_subtype_new(type, args, kwds); /* Wimp out */ if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:int", kwlist, &x, &base)) return NULL; if (x == NULL) return PyLong_FromLong(0L); if (base == -909) return PyNumber_Long(x); else if (PyUnicode_Check(x)) return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x), PyUnicode_GET_SIZE(x), base); else if (PyByteArray_Check(x) || PyBytes_Check(x)) { /* Since PyLong_FromString doesn't have a length parameter, * check here for possible NULs in the string. */ char *string; int size = Py_SIZE(x); if (PyByteArray_Check(x)) string = PyByteArray_AS_STRING(x); else string = PyBytes_AS_STRING(x); if (strlen(string) != size) { /* We only see this if there's a null byte in x, x is a bytes or buffer, *and* a base is given. */ PyErr_Format(PyExc_ValueError, "invalid literal for int() with base %d: %R", base, x); return NULL; } return PyLong_FromString(string, NULL, base); } else { PyErr_SetString(PyExc_TypeError, "int() can't convert non-string with explicit base"); return NULL; } } /* Wimpy, slow approach to tp_new calls for subtypes of long: first create a regular long from whatever arguments we got, then allocate a subtype instance and initialize it from the regular long. The regular long is then thrown away. */ static PyObject * long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyLongObject *tmp, *newobj; assert(PyType_IsSubtype(type, &PyLong_Type)); tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds); if (tmp == NULL) return NULL; assert(PyLong_CheckExact(tmp)); newobj = (PyLongObject *)type->tp_alloc(type, 0); if (newobj == NULL) { Py_DECREF(tmp); return NULL; } assert(PyLong_Check(newobj)); mpz_init(newobj->number); mpz_set(newobj->number, tmp->number); Py_DECREF(tmp); return (PyObject *)newobj; } static PyObject * long_getnewargs(PyLongObject *v) { return Py_BuildValue("(N)", _PyLong_Copy(v)); } static PyObject * long_getN(PyLongObject *v, void *context) { return PyLong_FromLong((Py_intptr_t)context); } static PyObject * long__format__(PyObject *self, PyObject *args) { PyObject *format_spec; if (!PyArg_ParseTuple(args, "U:__format__", &format_spec)) return NULL; return _PyLong_FormatAdvanced(self, PyUnicode_AS_UNICODE(format_spec), PyUnicode_GET_SIZE(format_spec)); } static PyObject * long_round(PyObject *self, PyObject *args) { #define UNDEF_NDIGITS (-0x7fffffff) /* Unlikely ndigits value */ int ndigits = UNDEF_NDIGITS; double x; PyObject *res; if (!PyArg_ParseTuple(args, "|i", &ndigits)) return NULL; if (ndigits == UNDEF_NDIGITS) return long_long(self); /* If called with two args, defer to float.__round__(). */ x = PyLong_AsDouble(self); if (x == -1.0 && PyErr_Occurred()) return NULL; self = PyFloat_FromDouble(x); if (self == NULL) return NULL; res = PyObject_CallMethod(self, "__round__", "i", ndigits); Py_DECREF(self); return res; #undef UNDEF_NDIGITS } static PyObject * long_numbits(PyObject *self) { size_t bits = _PyLong_NumBits(self); return PyLong_FromUnsignedLong(bits); } static PyObject * long_sizeof(PyLongObject *v) { Py_ssize_t res; /* FIXME: compute real memory used space in bytes */ res = sizeof(PyVarObject) /* + abs(Py_SIZE(v))*sizeof(limb_t) */; return PyLong_FromSsize_t(res); } #if 0 static PyObject * long_is_finite(PyObject *v) { Py_RETURN_TRUE; } #endif static PyMethodDef long_methods[] = { {"conjugate", (PyCFunction)long_long, METH_NOARGS, "Returns self, the complex conjugate of any int."}, #if 0 {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS, "Returns always True."}, #endif {"__trunc__", (PyCFunction)long_long, METH_NOARGS, "Truncating an Integral returns itself."}, {"__floor__", (PyCFunction)long_long, METH_NOARGS, "Flooring an Integral returns itself."}, {"__ceil__", (PyCFunction)long_long, METH_NOARGS, "Ceiling of an Integral returns itself."}, {"numbits", (PyCFunction)long_numbits, METH_NOARGS, "Number of bits."}, {"__round__", (PyCFunction)long_round, METH_VARARGS, "Rounding an Integral returns itself.\n" "Rounding with an ndigits arguments defers to float.__round__."}, {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS}, {"__format__", (PyCFunction)long__format__, METH_VARARGS}, {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS, "Returns size in memory, in bytes"}, {NULL, NULL} /* sentinel */ }; static PyGetSetDef long_getset[] = { {"real", (getter)long_long, (setter)NULL, "the real part of a complex number", NULL}, {"imag", (getter)long_getN, (setter)NULL, "the imaginary part of a complex number", (void*)0}, {"numerator", (getter)long_long, (setter)NULL, "the numerator of a rational number in lowest terms", NULL}, {"denominator", (getter)long_getN, (setter)NULL, "the denominator of a rational number in lowest terms", (void*)1}, {NULL} /* Sentinel */ }; PyDoc_STRVAR(long_doc, "int(x[, base]) -> integer\n\ \n\ Convert a string or number to an integer, if possible. A floating\n\ point argument will be truncated towards zero (this does not include a\n\ string representation of a floating point number!) When converting a\n\ string, use the optional base. It is an error to supply a base when\n\ converting a non-string."); static PyNumberMethods long_as_number = { (binaryfunc) long_add, /*nb_add*/ (binaryfunc) long_sub, /*nb_subtract*/ (binaryfunc) long_mul, /*nb_multiply*/ long_mod, /*nb_remainder*/ long_divmod, /*nb_divmod*/ long_pow, /*nb_power*/ (unaryfunc) long_neg, /*nb_negative*/ (unaryfunc) long_long, /*tp_positive*/ (unaryfunc) long_abs, /*tp_absolute*/ (inquiry) long_bool, /*tp_bool*/ (unaryfunc) long_invert, /*nb_invert*/ long_lshift, /*nb_lshift*/ (binaryfunc) long_rshift, /*nb_rshift*/ long_and, /*nb_and*/ long_xor, /*nb_xor*/ long_or, /*nb_or*/ long_long, /*nb_int*/ long_long, /*nb_long*/ long_float, /*nb_float*/ 0, /* nb_inplace_add */ 0, /* nb_inplace_subtract */ 0, /* nb_inplace_multiply */ 0, /* nb_inplace_remainder */ 0, /* nb_inplace_power */ 0, /* nb_inplace_lshift */ 0, /* nb_inplace_rshift */ 0, /* nb_inplace_and */ 0, /* nb_inplace_xor */ 0, /* nb_inplace_or */ long_div, /* nb_floor_divide */ long_true_divide, /* nb_true_divide */ 0, /* nb_inplace_floor_divide */ 0, /* nb_inplace_true_divide */ long_long, /* nb_index */ }; PyTypeObject PyLong_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "int", /* tp_name */ sizeof(PyLongObject), /* tp_basicsize */ 0, /* tp_itemsize */ long_dealloc, /* tp_dealloc */ 0, /* tp_print */ 0, /* tp_getattr */ 0, /* tp_setattr */ 0, /* tp_compare */ long_repr, /* tp_repr */ &long_as_number, /* tp_as_number */ 0, /* tp_as_sequence */ 0, /* tp_as_mapping */ (hashfunc)long_hash, /* tp_hash */ 0, /* tp_call */ long_repr, /* tp_str */ PyObject_GenericGetAttr, /* tp_getattro */ 0, /* tp_setattro */ 0, /* tp_as_buffer */ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */ long_doc, /* tp_doc */ 0, /* tp_traverse */ 0, /* tp_clear */ long_richcompare, /* tp_richcompare */ 0, /* tp_weaklistoffset */ 0, /* tp_iter */ 0, /* tp_iternext */ long_methods, /* tp_methods */ 0, /* tp_members */ long_getset, /* tp_getset */ 0, /* tp_base */ 0, /* tp_dict */ 0, /* tp_descr_get */ 0, /* tp_descr_set */ 0, /* tp_dictoffset */ 0, /* tp_init */ 0, /* tp_alloc */ long_new, /* tp_new */ PyObject_Del, /* tp_free */ }; int _PyLong_Init(void) { PyLongObject *v; #if NSMALLNEGINTS + NSMALLPOSINTS > 0 int ival; #endif mp_set_memory_functions( PyLong_Malloc, PyLong_Realloc, PyLong_Free ); #if NSMALLNEGINTS + NSMALLPOSINTS > 0 v = small_ints; for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) { PyObject_INIT(v, &PyLong_Type); mpz_init (v->number); mpz_set_si(v->number, ival); } #endif PyObject_INIT(&_Py_TrueStruct, &PyBool_Type); PyObject_INIT(&_Py_FalseStruct, &PyBool_Type); mpz_init(_Py_TrueStruct.number); mpz_init(_Py_FalseStruct.number); mpz_set_si(_Py_TrueStruct.number, 1); return 1; } void PyLong_Fini(void) { /* Integers are currently statically allocated. Py_DECREF is not needed, but Python must forget about the reference or multiple reinitializations will fail. */ #if NSMALLNEGINTS + NSMALLPOSINTS > 0 int i; PyLongObject *v = small_ints; for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) { _Py_DEC_REFTOTAL; _Py_ForgetReference((PyObject*)v); } #endif mpz_clear(_Py_FalseStruct.number); mpz_clear(_Py_TrueStruct.number); } </n;></n;>