rev 560 - in trunk: include/prothon src
SVN User <[email protected]> Fri, 28 May 2004 01:50:05 -0400
| Newsgroups | gmane.comp.lang.prothon.cvs |
|---|---|
| Message-ID | <[email protected]> |
Author: mark
Date: 2004-05-28 01:50:02 -0400 (Fri, 28 May 2004)
New Revision: 560
Removed:
trunk/src/builtins-bigint.c
Modified:
trunk/include/prothon/prothon.h
trunk/src/builtins-core.c
trunk/src/builtins-int.c
trunk/src/src.vcproj
Log:
started adding long support, build compiles again, should work as before but not tested
Modified: trunk/include/prothon/prothon.h
===================================================================
--- trunk/include/prothon/prothon.h 2004-05-28 00:09:58 UTC (rev 559)
+++ trunk/include/prothon/prothon.h 2004-05-28 05:50:02 UTC (rev 560)
@@ -201,7 +201,6 @@
#define ACC_USER2 2
#define ACC_SYSTEM 3
-
typedef struct obj_s {
obj_state_t state :3; // u8_t :2 when not debugging
data_type_t data_type :3; // u8_t :2 when not debugging
@@ -300,8 +299,10 @@
NAME_EXC, // 29 NameError
INDEX_EXC, // IndexError
TYPE_EXC, // TypeError
+ VALUE_EXC, // ValueError
MUTABLE_EXC, // Mutable Error
DIVIDEZERO_EXC, //
+ OVERFLOW_EXC, // OverflowError
OUTOFMEMORY_EXC, //
IOEXCEPTION, //
FUNCNOTFOUND_EXC, //
@@ -1240,4 +1241,77 @@
}
#endif
+//************************** PLATFORM SPECIFIC CONFIGURATIONS *****************
+/* PR_ARITHMETIC_RIGHT_SHIFT
+ * (from python)
+ * C doesn't define whether a right-shift of a signed integer sign-extends
+ * or zero-fills. Here a macro to force sign extension:
+ * PR_ARITHMETIC_RIGHT_SHIFT(TYPE, I, J)
+ * Return I >> J, forcing sign extension.
+ * Requirements:
+ * I is of basic signed type TYPE (char, short, int, long, or long long).
+ * TYPE is one of char, short, int, long, or long long, although long long
+ * must not be used except on platforms that support it.
+ * J is an integer >= 0 and strictly less than the number of bits in TYPE
+ * (because C doesn't define what happens for J outside that range either).
+ * Caution:
+ * I may be evaluated more than once.
+ */
+// define this only for the Macintosh
+#ifdef SIGNED_RIGHT_SHIFT_ZERO_FILLS
+#define PR_ARITHMETIC_RIGHT_SHIFT(TYPE, I, J) \
+ ((I) < 0 ? ~((~(unsigned TYPE)(I)) >> (J)) : (I) >> (J))
+#else
+#define PR_ARITHMETIC_RIGHT_SHIFT(TYPE, I, J) ((I) >> (J))
+#endif
+
+
+/* HUGE_VAL is supposed to expand to a positive double infinity. Python
+ * uses Py_HUGE_VAL instead because some platforms are broken in this
+ * respect. We used to embed code in pyport.h to try to worm around that,
+ * but different platforms are broken in conflicting ways. If you're on
+ * a platform where HUGE_VAL is defined incorrectly, fiddle your Python
+ * config to #define Py_HUGE_VAL to something that works on your platform.
+ */
+//#ifndef HUGE_VAL
+//#define HUGE_VAL ????
+//#endif
+
+/* Py_OVERFLOWED(X)
+ * Return 1 iff a libm function overflowed. Set errno to 0 before calling
+ * a libm function, and invoke this macro after, passing the function
+ * result.
+ * Caution:
+ * This isn't reliable. C99 no longer requires libm to set errno under
+ * any exceptional condition, but does require +- HUGE_VAL return
+ * values on overflow. A 754 box *probably* maps HUGE_VAL to a
+ * double infinity, and we're cool if that's so, unless the input
+ * was an infinity and an infinity is the expected result. A C89
+ * system sets errno to ERANGE, so we check for that too. We're
+ * out of luck if a C99 754 box doesn't map HUGE_VAL to +Inf, or
+ * if the returned result is a NaN, or if a C89 box returns HUGE_VAL
+ * in non-overflow cases.
+ * X is evaluated more than once.
+ * Some platforms have better way to spell this, so expect some #ifdef'ery.
+ *
+ * OpenBSD uses 'isinf()' because a compiler bug on that platform causes
+ * the longer macro version to be mis-compiled. This isn't optimal, and
+ * should be removed once a newer compiler is available on that platform.
+ * The system that had the failure was running OpenBSD 3.2 on Intel, with
+ * gcc 2.95.3.
+ *
+ * According to Tim's checkin, the FreeBSD systems use isinf() to work
+ * around a FPE bug on that platform.
+ */
+
+// We need to define HUGE_VAL and I don't know what value to use -- mch
+#if defined(__FreeBSD__) || defined(__OpenBSD__)
+#define Py_OVERFLOWED(X) isinf(X)
+#else
+#define Py_OVERFLOWED(X) ((X) != 0.0 && (errno == ERANGE))
+#endif
+//#define Py_OVERFLOWED(X) ((X) != 0.0 && (errno == ERANGE || \
+// (X) == Py_HUGE_VAL || \
+// (X) == -Py_HUGE_VAL))
+
#endif // PROTHON_H
Deleted: trunk/src/builtins-bigint.c
===================================================================
--- trunk/src/builtins-bigint.c 2004-05-28 00:09:58 UTC (rev 559)
+++ trunk/src/builtins-bigint.c 2004-05-28 05:50:02 UTC (rev 560)
@@ -1,2950 +0,0 @@
-/* ====================================================================
- * The Prothon License Agreement, Version 1.1
- *
- * Copyright (c) 2004 Hahn Creative Applications, http://hahnca.com.
- * All rights reserved.
- *
- * 1. This LICENSE AGREEMENT is between Hahn Creative Applications ("HCA"),
- * and the Individual or Organization ("Licensee") accessing and otherwise
- * using Prothon software in source or binary form and its associated
- * documentation.
- *
- * 2. Subject to the terms and conditions of this License Agreement, HCA
- * hereby grants Licensee a nonexclusive, royalty-free, world-wide license
- * to reproduce, analyze, test, perform and/or display publicly, prepare
- * derivative works, distribute, and otherwise use Prothon alone or in any
- * derivative version, provided, however, that HCA's License Agreement and
- * HCA's notice of copyright, i.e., "Copyright (c) 2004 Hahn Creative
- * Applications; All Rights Reserved" are retained in Prothon alone or
- * in any derivative version prepared by Licensee.
- *
- * 3. In the event Licensee prepares a derivative work that is based on or
- * incorporates Prothon or any part thereof, and wants to make the
- * derivative work available to others as provided herein, then Licensee
- * hereby agrees to include in any such work a brief summary of the
- * changes made to Prothon.
- *
- * 4. HCA is making Prothon available to Licensee on an "AS IS" basis.
- * HCA MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY
- * OF EXAMPLE, BUT NOT LIMITATION, HCA MAKES NO AND DISCLAIMS ANY
- * REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS FOR ANY
- * PARTICULAR PURPOSE OR THAT THE USE OF PROTHON WILL NOT INFRINGE ANY
- * THIRD PARTY RIGHTS.
- *
- * 5. HCA SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PROTHON
- * FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS A
- * RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PROTHON, OR ANY
- * DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.
- *
- * 6. This License Agreement will automatically terminate upon a material
- * breach of its terms and conditions.
- *
- * 7. Nothing in this License Agreement shall be deemed to create any
- * relationship of agency, partnership, or joint venture between HCA and
- * Licensee. This License Agreement does not grant permission to use HCA
- * trademarks or trade name in a trademark sense to endorse or promote
- * products or services of Licensee, or any third party.
- *
- * 8. By copying, installing or otherwise using Prothon, Licensee agrees
- * to be bound by the terms and conditions of this License Agreement.
- * ====================================================================
- */
-
-// builtins-bigint.c
-// copied from python/python/dist/src/Objects/longobject.c
-// and heavily modified for use in Prothon
-
-#include <prothon/prothon.h>
-
-/* Long (arbitrary precision) integer object implementation */
-
-/* For long multiplication, use the O(N**2) school algorithm unless
- * both operands contain more than KARATSUBA_CUTOFF digits (this
- * being an internal Python long digit, in base BASE).
- */
-#define KARATSUBA_CUTOFF 35
-#define SHIFT 15
-typedef u16_t wdigit;
-
-/* Forward */
-static obj_p long_normalize(obj_p);
-static obj_p mul1(obj_p, wdigit);
-static obj_p muladd1(obj_p, wdigit, wdigit);
-static obj_p divrem1(obj_p, digit, digit *);
-static obj_p long_format(obj_p aa, int base, int addL);
-
-/* Normalize (remove leading zeros from) a int object.
- Doesn't attempt to free the storage--in most cases, due to the nature
- of the algorithms used, this could save at most be one word anyway. */
-
-static obj_p long_normalize(register obj_p v) {
- int j = abs(v->ob_size);
- register int i = j;
-
- while (i > 0 && v->ob_digit[i-1] == 0)
- --i;
- if (i != j)
- v->ob_size = (v->ob_size < 0) ? -(i) : i;
- return v;
-}
-
-/* Allocate a new long int object with size digits.
- Return NULL and set exception if we run out of memory. */
-
-obj_p
-_PyLong_New(int size)
-{
- return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
-}
-
-obj_p
-_PyLong_Copy(obj_p src)
-{
- obj_p result;
- int i;
-
- assert(src != NULL);
- i = src->ob_size;
- if (i < 0)
- i = -(i);
- result = _PyLong_New(i);
- if (result != NULL) {
- result->ob_size = src->ob_size;
- while (--i >= 0)
- result->ob_digit[i] = src->ob_digit[i];
- }
- return (obj_p)result;
-}
-
-/* Create a new long int object from a C long int */
-
-obj_p
-PyLong_FromLong(long ival)
-{
- obj_p v;
- unsigned long t; /* unsigned so >> doesn't propagate sign bit */
- int ndigits = 0;
- int negative = 0;
-
- if (ival < 0) {
- ival = -ival;
- negative = 1;
- }
-
- /* Count the number of Python digits.
- We used to pick 5 ("big enough for anything"), but that's a
- waste of time and space given that 5*15 = 75 bits are rarely
- needed. */
- t = (unsigned long)ival;
- while (t) {
- ++ndigits;
- t >>= SHIFT;
- }
- v = _PyLong_New(ndigits);
- if (v != NULL) {
- digit *p = v->ob_digit;
- v->ob_size = negative ? -ndigits : ndigits;
- t = (unsigned long)ival;
- while (t) {
- *p++ = (digit)(t & MASK);
- t >>= SHIFT;
- }
- }
- return (obj_p)v;
-}
-
-/* Create a new long int object from a C unsigned long int */
-
-obj_p
-PyLong_FromUnsignedLong(unsigned long ival)
-{
- obj_p v;
- unsigned long t;
- int ndigits = 0;
-
- /* Count the number of Python digits. */
- t = (unsigned long)ival;
- while (t) {
- ++ndigits;
- t >>= SHIFT;
- }
- v = _PyLong_New(ndigits);
- if (v != NULL) {
- digit *p = v->ob_digit;
- v->ob_size = ndigits;
- while (ival) {
- *p++ = (digit)(ival & MASK);
- ival >>= SHIFT;
- }
- }
- return (obj_p)v;
-}
-
-/* Create a new long int object from a C double */
-
-obj_p
-PyLong_FromDouble(double dval)
-{
- obj_p v;
- double frac;
- int i, ndig, expo, neg;
- neg = 0;
- if (Py_IS_INFINITY(dval)) {
- PyErr_SetString(PyExc_OverflowError,
- "cannot convert float infinity to long");
- return NULL;
- }
- if (dval < 0.0) {
- neg = 1;
- dval = -dval;
- }
- frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
- if (expo <= 0)
- return PyLong_FromLong(0L);
- ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
- v = _PyLong_New(ndig);
- if (v == NULL)
- return NULL;
- frac = ldexp(frac, (expo-1) % SHIFT + 1);
- for (i = ndig; --i >= 0; ) {
- long bits = (long)frac;
- v->ob_digit[i] = (digit) bits;
- frac = frac - (double)bits;
- frac = ldexp(frac, SHIFT);
- }
- if (neg)
- v->ob_size = -(v->ob_size);
- return (obj_p)v;
-}
-
-/* Get a C long int from a long int object.
- Returns -1 and sets an error condition if overflow occurs. */
-
-long
-PyLong_AsLong(obj_p vv)
-{
- /* This version by Tim Peters */
- register obj_p v;
- unsigned long x, prev;
- int i, sign;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- if (vv != NULL && PyInt_Check(vv))
- return PyInt_AsLong(vv);
- PyErr_BadInternalCall();
- return -1;
- }
- v = (obj_p)vv;
- i = v->ob_size;
- sign = 1;
- x = 0;
- if (i < 0) {
- sign = -1;
- i = -(i);
- }
- while (--i >= 0) {
- prev = x;
- x = (x << SHIFT) + v->ob_digit[i];
- if ((x >> SHIFT) != prev)
- goto overflow;
- }
- /* Haven't lost any bits, but if the sign bit is set we're in
- * trouble *unless* this is the min negative number. So,
- * trouble iff sign bit set && (positive || some bit set other
- * than the sign bit).
- */
- if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
- goto overflow;
- return (long)x * sign;
-
- overflow:
- PyErr_SetString(PyExc_OverflowError,
- "long int too large to convert to int");
- return -1;
-}
-
-/* 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(obj_p vv)
-{
- register obj_p v;
- unsigned long x, prev;
- int i;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return (unsigned long) -1;
- }
- v = (obj_p)vv;
- i = v->ob_size;
- x = 0;
- if (i < 0) {
- PyErr_SetString(PyExc_OverflowError,
- "can't convert negative value to unsigned long");
- return (unsigned long) -1;
- }
- while (--i >= 0) {
- prev = x;
- x = (x << SHIFT) + v->ob_digit[i];
- if ((x >> SHIFT) != prev) {
- PyErr_SetString(PyExc_OverflowError,
- "long int too large to convert");
- return (unsigned long) -1;
- }
- }
- return x;
-}
-
-/* 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. */
-
-unsigned long
-PyLong_AsUnsignedLongMask(obj_p vv)
-{
- register obj_p v;
- unsigned long x;
- int i, sign;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return (unsigned long) -1;
- }
- v = (obj_p)vv;
- i = v->ob_size;
- sign = 1;
- x = 0;
- if (i < 0) {
- sign = -1;
- i = -i;
- }
- while (--i >= 0) {
- x = (x << SHIFT) + v->ob_digit[i];
- }
- return x * sign;
-}
-
-int
-_PyLong_Sign(obj_p vv)
-{
- obj_p v = (obj_p)vv;
-
- assert(v != NULL);
- assert(PyLong_Check(v));
-
- return v->ob_size == 0 ? 0 : (v->ob_size < 0 ? -1 : 1);
-}
-
-size_t
-_PyLong_NumBits(obj_p vv)
-{
- obj_p v = (obj_p)vv;
- size_t result = 0;
- int ndigits;
-
- assert(v != NULL);
- assert(PyLong_Check(v));
- ndigits = abs(v->ob_size);
- assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
- if (ndigits > 0) {
- digit msd = v->ob_digit[ndigits - 1];
-
- result = (ndigits - 1) * SHIFT;
- if (result / SHIFT != (size_t)ndigits - 1)
- goto Overflow;
- do {
- ++result;
- if (result == 0)
- goto Overflow;
- msd >>= 1;
- } while (msd);
- }
- return result;
-
-Overflow:
- PyErr_SetString(PyExc_OverflowError, "long has too many bits "
- "to express in a platform size_t");
- return (size_t)-1;
-}
-
-obj_p
-_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
- int little_endian, int is_signed)
-{
- const unsigned char* pstartbyte;/* LSB of bytes */
- int incr; /* direction to move pstartbyte */
- const unsigned char* pendbyte; /* MSB of bytes */
- size_t numsignificantbytes; /* number of bytes that matter */
- size_t ndigits; /* number of Python long digits */
- PyLongObject* v; /* result */
- int idigit = 0; /* next free index in v->ob_digit */
-
- if (n == 0)
- return PyLong_FromLong(0L);
-
- if (little_endian) {
- pstartbyte = bytes;
- pendbyte = bytes + n - 1;
- incr = 1;
- }
- else {
- pstartbyte = bytes + n - 1;
- pendbyte = bytes;
- incr = -1;
- }
-
- if (is_signed)
- is_signed = *pendbyte >= 0x80;
-
- /* Compute numsignificantbytes. This consists of finding the most
- significant byte. Leading 0 bytes are insignficant if the number
- is positive, and leading 0xff bytes if negative. */
- {
- size_t i;
- const unsigned char* p = pendbyte;
- const int pincr = -incr; /* search MSB to LSB */
- const unsigned char insignficant = is_signed ? 0xff : 0x00;
-
- for (i = 0; i < n; ++i, p += pincr) {
- if (*p != insignficant)
- break;
- }
- numsignificantbytes = n - i;
- /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
- actually has 2 significant bytes. OTOH, 0xff0001 ==
- -0x00ffff, so we wouldn't *need* to bump it there; but we
- do for 0xffff = -0x0001. To be safe without bothering to
- check every case, bump it regardless. */
- if (is_signed && numsignificantbytes < n)
- ++numsignificantbytes;
- }
-
- /* How many Python long digits do we need? We have
- 8*numsignificantbytes bits, and each Python long digit has SHIFT
- bits, so it's the ceiling of the quotient. */
- ndigits = (numsignificantbytes * 8 + SHIFT - 1) / SHIFT;
- if (ndigits > (size_t)INT_MAX)
- return PyErr_NoMemory();
- v = _PyLong_New((int)ndigits);
- if (v == NULL)
- return NULL;
-
- /* Copy the bits over. The tricky parts are computing 2's-comp on
- the fly for signed numbers, and dealing with the mismatch between
- 8-bit bytes and (probably) 15-bit Python digits.*/
- {
- size_t i;
- twodigits carry = 1; /* for 2's-comp calculation */
- twodigits accum = 0; /* sliding register */
- unsigned int accumbits = 0; /* number of bits in accum */
- const unsigned char* p = pstartbyte;
-
- for (i = 0; i < numsignificantbytes; ++i, p += incr) {
- twodigits thisbyte = *p;
- /* Compute correction for 2's comp, if needed. */
- if (is_signed) {
- thisbyte = (0xff ^ thisbyte) + carry;
- carry = thisbyte >> 8;
- thisbyte &= 0xff;
- }
- /* Because we're going LSB to MSB, thisbyte is
- more significant than what's already in accum,
- so needs to be prepended to accum. */
- accum |= thisbyte << accumbits;
- accumbits += 8;
- if (accumbits >= SHIFT) {
- /* There's enough to fill a Python digit. */
- assert(idigit < (int)ndigits);
- v->ob_digit[idigit] = (digit)(accum & MASK);
- ++idigit;
- accum >>= SHIFT;
- accumbits -= SHIFT;
- assert(accumbits < SHIFT);
- }
- }
- assert(accumbits < SHIFT);
- if (accumbits) {
- assert(idigit < (int)ndigits);
- v->ob_digit[idigit] = (digit)accum;
- ++idigit;
- }
- }
-
- v->ob_size = is_signed ? -idigit : idigit;
- return (obj_p)long_normalize(v);
-}
-
-int
-_PyLong_AsByteArray(PyLongObject* v,
- unsigned char* bytes, size_t n,
- int little_endian, int is_signed)
-{
- int i; /* index into v->ob_digit */
- int ndigits; /* |v->ob_size| */
- twodigits accum; /* sliding register */
- unsigned int accumbits; /* # bits in accum */
- int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
- twodigits carry; /* for computing 2's-comp */
- size_t j; /* # bytes filled */
- unsigned char* p; /* pointer to next byte in bytes */
- int pincr; /* direction to move p */
-
- assert(v != NULL && PyLong_Check(v));
-
- if (v->ob_size < 0) {
- ndigits = -(v->ob_size);
- if (!is_signed) {
- PyErr_SetString(PyExc_TypeError,
- "can't convert negative long to unsigned");
- return -1;
- }
- do_twos_comp = 1;
- }
- else {
- ndigits = v->ob_size;
- do_twos_comp = 0;
- }
-
- if (little_endian) {
- p = bytes;
- pincr = 1;
- }
- else {
- p = bytes + n - 1;
- pincr = -1;
- }
-
- /* Copy over all the Python digits.
- It's crucial that every Python digit except for the MSD contribute
- exactly SHIFT bits to the total, so first assert that the long is
- normalized. */
- assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
- j = 0;
- accum = 0;
- accumbits = 0;
- carry = do_twos_comp ? 1 : 0;
- for (i = 0; i < ndigits; ++i) {
- twodigits thisdigit = v->ob_digit[i];
- if (do_twos_comp) {
- thisdigit = (thisdigit ^ MASK) + carry;
- carry = thisdigit >> SHIFT;
- thisdigit &= MASK;
- }
- /* Because we're going LSB to MSB, thisdigit is more
- significant than what's already in accum, so needs to be
- prepended to accum. */
- accum |= thisdigit << accumbits;
- accumbits += SHIFT;
-
- /* The most-significant digit may be (probably is) at least
- partly empty. */
- if (i == ndigits - 1) {
- /* Count # of sign bits -- they needn't be stored,
- * although for signed conversion we need later to
- * make sure at least one sign bit gets stored.
- * First shift conceptual sign bit to real sign bit.
- */
- stwodigits s = (stwodigits)(thisdigit <<
- (8*sizeof(stwodigits) - SHIFT));
- unsigned int nsignbits = 0;
- while ((s < 0) == do_twos_comp && nsignbits < SHIFT) {
- ++nsignbits;
- s <<= 1;
- }
- accumbits -= nsignbits;
- }
-
- /* Store as many bytes as possible. */
- while (accumbits >= 8) {
- if (j >= n)
- goto Overflow;
- ++j;
- *p = (unsigned char)(accum & 0xff);
- p += pincr;
- accumbits -= 8;
- accum >>= 8;
- }
- }
-
- /* Store the straggler (if any). */
- assert(accumbits < 8);
- assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
- if (accumbits > 0) {
- if (j >= n)
- goto Overflow;
- ++j;
- if (do_twos_comp) {
- /* Fill leading bits of the byte with sign bits
- (appropriately pretending that the long had an
- infinite supply of sign bits). */
- accum |= (~(twodigits)0) << accumbits;
- }
- *p = (unsigned char)(accum & 0xff);
- p += pincr;
- }
- else if (j == n && n > 0 && is_signed) {
- /* The main loop filled the byte array exactly, so the code
- just above didn't get to ensure there's a sign bit, and the
- loop below wouldn't add one either. Make sure a sign bit
- exists. */
- unsigned char msb = *(p - pincr);
- int sign_bit_set = msb >= 0x80;
- assert(accumbits == 0);
- if (sign_bit_set == do_twos_comp)
- return 0;
- else
- goto Overflow;
- }
-
- /* Fill remaining bytes with copies of the sign bit. */
- {
- unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
- for ( ; j < n; ++j, p += pincr)
- *p = signbyte;
- }
-
- return 0;
-
-Overflow:
- PyErr_SetString(PyExc_OverflowError, "long too big to convert");
- return -1;
-
-}
-
-double
-_PyLong_AsScaledDouble(obj_p vv, int *exponent)
-{
-/* NBITS_WANTED should be > the number of bits in a double's precision,
- but small enough so that 2**NBITS_WANTED is within the normal double
- range. nbitsneeded is set to 1 less than that because the most-significant
- Python digit contains at least 1 significant bit, but we don't want to
- bother counting them (catering to the worst case cheaply).
-
- 57 is one more than VAX-D double precision; I (Tim) don't know of a double
- format with more precision than that; it's 1 larger so that we add in at
- least one round bit to stand in for the ignored least-significant bits.
-*/
-#define NBITS_WANTED 57
- obj_p v;
- double x;
- const double multiplier = (double)(1L << SHIFT);
- int i, sign;
- int nbitsneeded;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return -1;
- }
- v = (obj_p)vv;
- i = v->ob_size;
- sign = 1;
- if (i < 0) {
- sign = -1;
- i = -(i);
- }
- else if (i == 0) {
- *exponent = 0;
- return 0.0;
- }
- --i;
- x = (double)v->ob_digit[i];
- nbitsneeded = NBITS_WANTED - 1;
- /* Invariant: i Python digits remain unaccounted for. */
- while (i > 0 && nbitsneeded > 0) {
- --i;
- x = x * multiplier + (double)v->ob_digit[i];
- nbitsneeded -= SHIFT;
- }
- /* There are i digits we didn't shift in. Pretending they're all
- zeroes, the true value is x * 2**(i*SHIFT). */
- *exponent = i;
- assert(x > 0.0);
- return x * sign;
-#undef NBITS_WANTED
-}
-
-/* Get a C double from a long int object. */
-
-double
-PyLong_AsDouble(obj_p vv)
-{
- int e;
- 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;
- if (e > INT_MAX / SHIFT)
- goto overflow;
- errno = 0;
- x = ldexp(x, e * SHIFT);
- if (Py_OVERFLOWED(x))
- goto overflow;
- return x;
-
-overflow:
- PyErr_SetString(PyExc_OverflowError,
- "long int too large to convert to float");
- return -1.0;
-}
-
-/* Create a new long (or int) object from a C pointer */
-
-obj_p
-PyLong_FromVoidPtr(void *p)
-{
-#if SIZEOF_VOID_P <= SIZEOF_LONG
- return PyInt_FromLong((long)p);
-#else
-
-#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
- /* optimize null pointers */
- if (p == NULL)
- return PyInt_FromLong(0);
- return PyLong_FromLongLong((PY_LONG_LONG)p);
-
-#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
-}
-
-/* Get a C pointer from a long object (or an int object in some cases) */
-
-void *
-PyLong_AsVoidPtr(obj_p 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 (PyInt_Check(vv))
- x = PyInt_AS_LONG(vv);
- else
- x = PyLong_AsLong(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 (PyInt_Check(vv))
- x = PyInt_AS_LONG(vv);
- else
- x = PyLong_AsLongLong(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 ([email protected]), 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. */
-
-obj_p
-PyLong_FromLongLong(PY_LONG_LONG ival)
-{
- PY_LONG_LONG bytes = ival;
- int one = 1;
- return _PyLong_FromByteArray(
- (unsigned char *)&bytes,
- SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
-}
-
-/* Create a new long int object from a C unsigned PY_LONG_LONG int. */
-
-obj_p
-PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
-{
- unsigned PY_LONG_LONG bytes = ival;
- int one = 1;
- return _PyLong_FromByteArray(
- (unsigned char *)&bytes,
- SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
-}
-
-/* Get a C PY_LONG_LONG int from a long int object.
- Return -1 and set an error if overflow occurs. */
-
-PY_LONG_LONG
-PyLong_AsLongLong(obj_p vv)
-{
- PY_LONG_LONG bytes;
- int one = 1;
- int res;
-
- if (vv == NULL) {
- PyErr_BadInternalCall();
- return -1;
- }
- if (!PyLong_Check(vv)) {
- if (PyInt_Check(vv))
- return (PY_LONG_LONG)PyInt_AsLong(vv);
- PyErr_BadInternalCall();
- return -1;
- }
-
- res = _PyLong_AsByteArray(
- (obj_p)vv, (unsigned char *)&bytes,
- SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
-
- /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
- if (res < 0)
- return (PY_LONG_LONG)-1;
- else
- return bytes;
-}
-
-/* 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(obj_p vv)
-{
- unsigned PY_LONG_LONG bytes;
- int one = 1;
- int res;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return -1;
- }
-
- res = _PyLong_AsByteArray(
- (obj_p)vv, (unsigned char *)&bytes,
- SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
-
- /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
- if (res < 0)
- return (unsigned PY_LONG_LONG)res;
- else
- return bytes;
-}
-
-/* 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. */
-
-unsigned PY_LONG_LONG
-PyLong_AsUnsignedLongLongMask(obj_p vv)
-{
- register obj_p v;
- unsigned PY_LONG_LONG x;
- int i, sign;
-
- if (vv == NULL || !PyLong_Check(vv)) {
- PyErr_BadInternalCall();
- return (unsigned long) -1;
- }
- v = (obj_p)vv;
- i = v->ob_size;
- sign = 1;
- x = 0;
- if (i < 0) {
- sign = -1;
- i = -i;
- }
- while (--i >= 0) {
- x = (x << SHIFT) + v->ob_digit[i];
- }
- return x * sign;
-}
-#undef IS_LITTLE_ENDIAN
-
-#endif /* HAVE_LONG_LONG */
-
-
-static int
-convert_binop(obj_p v, obj_p w, obj_p *a, obj_p *b) {
- if (PyLong_Check(v)) {
- *a = (obj_p) v;
- Py_INCREF(v);
- }
- else if (PyInt_Check(v)) {
- *a = (obj_p) PyLong_FromLong(PyInt_AS_LONG(v));
- }
- else {
- return 0;
- }
- if (PyLong_Check(w)) {
- *b = (obj_p) w;
- Py_INCREF(w);
- }
- else if (PyInt_Check(w)) {
- *b = (obj_p) PyLong_FromLong(PyInt_AS_LONG(w));
- }
- else {
- Py_DECREF(*a);
- return 0;
- }
- return 1;
-}
-
-#define CONVERT_BINOP(v, w, a, b) \
- if (!convert_binop(v, w, a, b)) { \
- Py_INCREF(Py_NotImplemented); \
- return Py_NotImplemented; \
- }
-
-/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
- * is modified in place, by adding y to it. Carries are propagated as far as
- * x[m-1], and the remaining carry (0 or 1) is returned.
- */
-static digit
-v_iadd(digit *x, int m, digit *y, int n)
-{
- int i;
- digit carry = 0;
-
- assert(m >= n);
- for (i = 0; i < n; ++i) {
- carry += x[i] + y[i];
- x[i] = carry & MASK;
- carry >>= SHIFT;
- assert((carry & 1) == carry);
- }
- for (; carry && i < m; ++i) {
- carry += x[i];
- x[i] = carry & MASK;
- carry >>= SHIFT;
- assert((carry & 1) == carry);
- }
- return carry;
-}
-
-/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
- * is modified in place, by subtracting y from it. Borrows are propagated as
- * far as x[m-1], and the remaining borrow (0 or 1) is returned.
- */
-static digit
-v_isub(digit *x, int m, digit *y, int n)
-{
- int i;
- digit borrow = 0;
-
- assert(m >= n);
- for (i = 0; i < n; ++i) {
- borrow = x[i] - y[i] - borrow;
- x[i] = borrow & MASK;
- borrow >>= SHIFT;
- borrow &= 1; /* keep only 1 sign bit */
- }
- for (; borrow && i < m; ++i) {
- borrow = x[i] - borrow;
- x[i] = borrow & MASK;
- borrow >>= SHIFT;
- borrow &= 1;
- }
- return borrow;
-}
-
-/* Multiply by a single digit, ignoring the sign. */
-
-static obj_p
-mul1(obj_p a, wdigit n)
-{
- return muladd1(a, n, (digit)0);
-}
-
-/* Multiply by a single digit and add a single digit, ignoring the sign. */
-
-static obj_p
-muladd1(obj_p a, wdigit n, wdigit extra)
-{
- int size_a = abs(a->ob_size);
- obj_p z = _PyLong_New(size_a+1);
- twodigits carry = extra;
- int i;
-
- if (z == NULL)
- return NULL;
- for (i = 0; i < size_a; ++i) {
- carry += (twodigits)a->ob_digit[i] * n;
- z->ob_digit[i] = (digit) (carry & MASK);
- carry >>= SHIFT;
- }
- z->ob_digit[i] = (digit) carry;
- return long_normalize(z);
-}
-
-/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
- in pout, and returning the remainder. pin and pout point at the LSD.
- It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
- long_format, but that should be done with great care since longs are
- immutable. */
-
-static digit
-inplace_divrem1(digit *pout, digit *pin, int size, digit n)
-{
- twodigits rem = 0;
-
- assert(n > 0 && n <= MASK);
- pin += size;
- pout += size;
- while (--size >= 0) {
- digit hi;
- rem = (rem << SHIFT) + *--pin;
- *--pout = hi = (digit)(rem / n);
- rem -= hi * n;
- }
- return (digit)rem;
-}
-
-/* Divide a long integer by a digit, returning both the quotient
- (as function result) and the remainder (through *prem).
- The sign of a is ignored; n should not be zero. */
-
-static obj_p
-divrem1(obj_p a, digit n, digit *prem)
-{
- const int size = abs(a->ob_size);
- obj_p z;
-
- assert(n > 0 && n <= MASK);
- z = _PyLong_New(size);
- if (z == NULL)
- return NULL;
- *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
- return long_normalize(z);
-}
-
-/* Convert a long int object to a string, using a given conversion base.
- Return a string object.
- If base is 8 or 16, add the proper prefix '0' or '0x'. */
-
-static obj_p
-long_format(obj_p aa, int base, int addL)
-{
- register obj_p a = (obj_p)aa;
- PyStringObject *str;
- int i;
- const int size_a = abs(a->ob_size);
- char *p;
- int bits;
- char sign = '\0';
-
- if (a == NULL || !PyLong_Check(a)) {
- PyErr_BadInternalCall();
- return NULL;
- }
- assert(base >= 2 && base <= 36);
-
- /* Compute a rough upper bound for the length of the string */
- i = base;
- bits = 0;
- while (i > 1) {
- ++bits;
- i >>= 1;
- }
- i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
- str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
- if (str == NULL)
- return NULL;
- p = PyString_AS_STRING(str) + i;
- *p = '\0';
- if (addL)
- *--p = 'L';
- if (a->ob_size < 0)
- sign = '-';
-
- if (a->ob_size == 0) {
- *--p = '0';
- }
- else if ((base & (base - 1)) == 0) {
- /* JRH: special case for power-of-2 bases */
- twodigits accum = 0;
- int accumbits = 0; /* # of bits in accum */
- int basebits = 1; /* # of bits in base-1 */
- i = base;
- while ((i >>= 1) > 1)
- ++basebits;
-
- for (i = 0; i < size_a; ++i) {
- accum |= (twodigits)a->ob_digit[i] << accumbits;
- accumbits += SHIFT;
- assert(accumbits >= basebits);
- do {
- char cdigit = (char)(accum & (base - 1));
- cdigit += (cdigit < 10) ? '0' : 'A'-10;
- assert(p > PyString_AS_STRING(str));
- *--p = cdigit;
- accumbits -= basebits;
- accum >>= basebits;
- } while (i < size_a-1 ? accumbits >= basebits :
- accum > 0);
- }
- }
- else {
- /* Not 0, and base not a power of 2. Divide repeatedly by
- base, but for speed use the highest power of base that
- fits in a digit. */
- int size = size_a;
- digit *pin = a->ob_digit;
- obj_p scratch;
- /* powbasw <- largest power of base that fits in a digit. */
- digit powbase = base; /* powbase == base ** power */
- int power = 1;
- for (;;) {
- unsigned long newpow = powbase * (unsigned long)base;
- if (newpow >> SHIFT) /* doesn't fit in a digit */
- break;
- powbase = (digit)newpow;
- ++power;
- }
-
- /* Get a scratch area for repeated division. */
- scratch = _PyLong_New(size);
- if (scratch == NULL) {
- Py_DECREF(str);
- return NULL;
- }
-
- /* Repeatedly divide by powbase. */
- do {
- int ntostore = power;
- digit rem = inplace_divrem1(scratch->ob_digit,
- pin, size, powbase);
- pin = scratch->ob_digit; /* no need to use a again */
- if (pin[size - 1] == 0)
- --size;
- SIGCHECK({
- Py_DECREF(scratch);
- Py_DECREF(str);
- return NULL;
- })
-
- /* Break rem into digits. */
- assert(ntostore > 0);
- do {
- digit nextrem = (digit)(rem / base);
- char c = (char)(rem - nextrem * base);
- assert(p > PyString_AS_STRING(str));
- c += (c < 10) ? '0' : 'A'-10;
- *--p = c;
- rem = nextrem;
- --ntostore;
- /* Termination is a bit delicate: must not
- store leading zeroes, so must get out if
- remaining quotient and rem are both 0. */
- } while (ntostore && (size || rem));
- } while (size != 0);
- Py_DECREF(scratch);
- }
-
- if (base == 8) {
- if (size_a != 0)
- *--p = '0';
- }
- else if (base == 16) {
- *--p = 'x';
- *--p = '0';
- }
- else if (base != 10) {
- *--p = '#';
- *--p = '0' + base%10;
- if (base > 10)
- *--p = '0' + base/10;
- }
- if (sign)
- *--p = sign;
- if (p != PyString_AS_STRING(str)) {
- char *q = PyString_AS_STRING(str);
- assert(p > q);
- do {
- } while ((*q++ = *p++) != '\0');
- q--;
- _PyString_Resize((obj_p *)&str,
- (int) (q - PyString_AS_STRING(str)));
- }
- return (obj_p)str;
-}
-
-/* *str points to the first digit in a string of base base digits. base
- * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
- * non-digit (which may be *str!). A normalized long is returned.
- * The point to this routine is that it takes time linear in the number of
- * string characters.
- */
-static obj_p
-long_from_binary_base(char **str, int base)
-{
- char *p = *str;
- char *start = p;
- int bits_per_char;
- int n;
- obj_p z;
- twodigits accum;
- int bits_in_accum;
- digit *pdigit;
-
- assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
- n = base;
- for (bits_per_char = -1; n; ++bits_per_char)
- n >>= 1;
- /* n <- total # of bits needed, while setting p to end-of-string */
- n = 0;
- for (;;) {
- int k = -1;
- char ch = *p;
-
- if (ch <= '9')
- k = ch - '0';
- else if (ch >= 'a')
- k = ch - 'a' + 10;
- else if (ch >= 'A')
- k = ch - 'A' + 10;
- if (k < 0 || k >= base)
- break;
- ++p;
- }
- *str = p;
- n = (p - start) * bits_per_char;
- if (n / bits_per_char != p - start) {
- PyErr_SetString(PyExc_ValueError,
- "long string too large to convert");
- return NULL;
- }
- /* n <- # of Python digits needed, = ceiling(n/SHIFT). */
- n = (n + SHIFT - 1) / SHIFT;
- z = _PyLong_New(n);
- if (z == NULL)
- return NULL;
- /* Read string from right, and fill in long from left; i.e.,
- * from least to most significant in both.
- */
- accum = 0;
- bits_in_accum = 0;
- pdigit = z->ob_digit;
- while (--p >= start) {
- int k;
- char ch = *p;
-
- if (ch <= '9')
- k = ch - '0';
- else if (ch >= 'a')
- k = ch - 'a' + 10;
- else {
- assert(ch >= 'A');
- k = ch - 'A' + 10;
- }
- assert(k >= 0 && k < base);
- accum |= (twodigits)(k << bits_in_accum);
- bits_in_accum += bits_per_char;
- if (bits_in_accum >= SHIFT) {
- *pdigit++ = (digit)(accum & MASK);
- assert(pdigit - z->ob_digit <= n);
- accum >>= SHIFT;
- bits_in_accum -= SHIFT;
- assert(bits_in_accum < SHIFT);
- }
- }
- if (bits_in_accum) {
- assert(bits_in_accum <= SHIFT);
- *pdigit++ = (digit)accum;
- assert(pdigit - z->ob_digit <= n);
- }
- while (pdigit - z->ob_digit < n)
- *pdigit++ = 0;
- return long_normalize(z);
-}
-
-obj_p
-PyLong_FromString(char *str, char **pend, int base)
-{
- int sign = 1;
- char *start, *orig_str = str;
- obj_p z;
-
- if ((base != 0 && base < 2) || base > 36) {
- PyErr_SetString(PyExc_ValueError,
- "long() arg 2 must be >= 2 and <= 36");
- return NULL;
- }
- while (*str != '\0' && isspace(Py_CHARMASK(*str)))
- str++;
- if (*str == '+')
- ++str;
- else if (*str == '-') {
- ++str;
- sign = -1;
- }
- while (*str != '\0' && isspace(Py_CHARMASK(*str)))
- str++;
- if (base == 0) {
- if (str[0] != '0')
- base = 10;
- else if (str[1] == 'x' || str[1] == 'X')
- base = 16;
- else
- base = 8;
- }
- if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
- str += 2;
- start = str;
- if ((base & (base - 1)) == 0)
- z = long_from_binary_base(&str, base);
- else {
- z = _PyLong_New(0);
- for ( ; z != NULL; ++str) {
- int k = -1;
- obj_p temp;
-
- if (*str <= '9')
- k = *str - '0';
- else if (*str >= 'a')
- k = *str - 'a' + 10;
- else if (*str >= 'A')
- k = *str - 'A' + 10;
- if (k < 0 || k >= base)
- break;
- temp = muladd1(z, (digit)base, (digit)k);
- Py_DECREF(z);
- z = temp;
- }
- }
- if (z == NULL)
- return NULL;
- if (str == start)
- goto onError;
- if (sign < 0 && z != NULL && z->ob_size != 0)
- z->ob_size = -(z->ob_size);
- if (*str == 'L' || *str == 'l')
- str++;
- while (*str && isspace(Py_CHARMASK(*str)))
- str++;
- if (*str != '\0')
- goto onError;
- if (pend)
- *pend = str;
- return (obj_p) z;
-
- onError:
- PyErr_Format(PyExc_ValueError,
- "invalid literal for long(): %.200s", orig_str);
- Py_XDECREF(z);
- return NULL;
-}
-
-#ifdef Py_USING_UNICODE
-obj_p
-PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
-{
- obj_p result;
- char *buffer = 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;
-}
-#endif
-
-/* forward */
-static obj_p x_divrem
- (obj_p, obj_p, obj_p *);
-static obj_p long_pos(obj_p);
-static int long_divrem(obj_p, obj_p,
- obj_p *, obj_p *);
-
-/* Long division with remainder, top-level routine */
-
-static int
-long_divrem(obj_p a, obj_p b,
- obj_p *pdiv, obj_p *prem)
-{
- int size_a = abs(a->ob_size), size_b = abs(b->ob_size);
- obj_p z;
-
- if (size_b == 0) {
- PyErr_SetString(PyExc_ZeroDivisionError,
- "long division or modulo by zero");
- return -1;
- }
- if (size_a < size_b ||
- (size_a == size_b &&
- a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
- /* |a| < |b|. */
- *pdiv = _PyLong_New(0);
- Py_INCREF(a);
- *prem = (obj_p) a;
- return 0;
- }
- if (size_b == 1) {
- digit rem = 0;
- z = divrem1(a, b->ob_digit[0], &rem);
- if (z == NULL)
- return -1;
- *prem = (obj_p) PyLong_FromLong((long)rem);
- }
- else {
- z = x_divrem(a, b, prem);
- if (z == NULL)
- return -1;
- }
- /* Set the signs.
- The quotient z has the sign of a*b;
- the remainder r has the sign of a,
- so a = b*z + r. */
- if ((a->ob_size < 0) != (b->ob_size < 0))
- z->ob_size = -(z->ob_size);
- if (a->ob_size < 0 && (*prem)->ob_size != 0)
- (*prem)->ob_size = -((*prem)->ob_size);
- *pdiv = z;
- return 0;
-}
-
-/* Unsigned long division with remainder -- the algorithm */
-
-static obj_p
-x_divrem(obj_p v1, obj_p w1, obj_p *prem)
-{
- int size_v = abs(v1->ob_size), size_w = abs(w1->ob_size);
- digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
- obj_p v = mul1(v1, d);
- obj_p w = mul1(w1, d);
- obj_p a;
- int j, k;
-
- if (v == NULL || w == NULL) {
- Py_XDECREF(v);
- Py_XDECREF(w);
- return NULL;
- }
-
- assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
- assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
- assert(size_w == abs(w->ob_size)); /* That's how d was calculated */
-
- size_v = abs(v->ob_size);
- a = _PyLong_New(size_v - size_w + 1);
-
- for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) {
- digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
- twodigits q;
- stwodigits carry = 0;
- int i;
-
- SIGCHECK({
- Py_DECREF(a);
- a = NULL;
- break;
- })
- if (vj == w->ob_digit[size_w-1])
- q = MASK;
- else
- q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
- w->ob_digit[size_w-1];
-
- while (w->ob_digit[size_w-2]*q >
- ((
- ((twodigits)vj << SHIFT)
- + v->ob_digit[j-1]
- - q*w->ob_digit[size_w-1]
- ) << SHIFT)
- + v->ob_digit[j-2])
- --q;
-
- for (i = 0; i < size_w && i+k < size_v; ++i) {
- twodigits z = w->ob_digit[i] * q;
- digit zz = (digit) (z >> SHIFT);
- carry += v->ob_digit[i+k] - z
- + ((twodigits)zz << SHIFT);
- v->ob_digit[i+k] = (digit)(carry & MASK);
- carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
- carry, SHIFT);
- carry -= zz;
- }
-
- if (i+k < size_v) {
- carry += v->ob_digit[i+k];
- v->ob_digit[i+k] = 0;
- }
-
- if (carry == 0)
- a->ob_digit[k] = (digit) q;
- else {
- assert(carry == -1);
- a->ob_digit[k] = (digit) q-1;
- carry = 0;
- for (i = 0; i < size_w && i+k < size_v; ++i) {
- carry += v->ob_digit[i+k] + w->ob_digit[i];
- v->ob_digit[i+k] = (digit)(carry & MASK);
- carry = Py_ARITHMETIC_RIGHT_SHIFT(
- BASE_TWODIGITS_TYPE,
- carry, SHIFT);
- }
- }
- } /* for j, k */
-
- if (a == NULL)
- *prem = NULL;
- else {
- a = long_normalize(a);
- *prem = divrem1(v, d, &d);
- /* d receives the (unused) remainder */
- if (*prem == NULL) {
- Py_DECREF(a);
- a = NULL;
- }
- }
- Py_DECREF(v);
- Py_DECREF(w);
- return a;
-}
-
-/* Methods */
-
-static void
-long_dealloc(obj_p v)
-{
- v->ob_type->tp_free(v);
-}
-
-static obj_p
-long_repr(obj_p v)
-{
- return long_format(v, 10, 1);
-}
-
-static obj_p
-long_str(obj_p v)
-{
- return long_format(v, 10, 0);
-}
-
-static int
-long_compare(obj_p a, obj_p b)
-{
- int sign;
-
- if (a->ob_size != b->ob_size) {
- if (abs(a->ob_size) == 0 && abs(b->ob_size) == 0)
- sign = 0;
- else
- sign = a->ob_size - b->ob_size;
- }
- else {
- int i = abs(a->ob_size);
- while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
- ;
- if (i < 0)
- sign = 0;
- else {
- sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
- if (a->ob_size < 0)
- sign = -sign;
- }
- }
- return sign < 0 ? -1 : sign > 0 ? 1 : 0;
-}
-
-static long
-long_hash(obj_p v)
-{
- long x;
- int i, sign;
-
- /* This is designed so that Python ints and longs with the
- same value hash to the same value, otherwise comparisons
- of mapping keys will turn out weird */
- i = v->ob_size;
- sign = 1;
- x = 0;
- if (i < 0) {
- sign = -1;
- i = -(i);
- }
-#define LONG_BIT_SHIFT (8*sizeof(long) - SHIFT)
- while (--i >= 0) {
- /* Force a native long #-bits (32 or 64) circular shift */
- x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK);
- x += v->ob_digit[i];
- }
-#undef LONG_BIT_SHIFT
- x = x * sign;
- if (x == -1)
- x = -2;
- return x;
-}
-
-
-/* Add the absolute values of two long integers. */
-
-static obj_p
-x_add(obj_p a, obj_p b)
-{
- int size_a = abs(a->ob_size), size_b = abs(b->ob_size);
- obj_p z;
- int i;
- digit carry = 0;
-
- /* Ensure a is the larger of the two: */
- if (size_a < size_b) {
- { obj_p temp = a; a = b; b = temp; }
- { int size_temp = size_a;
- size_a = size_b;
- size_b = size_temp; }
- }
- z = _PyLong_New(size_a+1);
- if (z == NULL)
- return NULL;
- for (i = 0; i < size_b; ++i) {
- carry += a->ob_digit[i] + b->ob_digit[i];
- z->ob_digit[i] = carry & MASK;
- carry >>= SHIFT;
- }
- for (; i < size_a; ++i) {
- carry += a->ob_digit[i];
- z->ob_digit[i] = carry & MASK;
- carry >>= SHIFT;
- }
- z->ob_digit[i] = carry;
- return long_normalize(z);
-}
-
-/* Subtract the absolute values of two integers. */
-
-static obj_p
-x_sub(obj_p a, obj_p b)
-{
- int size_a = abs(a->ob_size), size_b = abs(b->ob_size);
- obj_p z;
- int i;
- int sign = 1;
- digit borrow = 0;
-
- /* Ensure a is the larger of the two: */
- if (size_a < size_b) {
- sign = -1;
- { obj_p temp = a; a = b; b = temp; }
- { int size_temp = size_a;
- size_a = size_b;
- size_b = size_temp; }
- }
- else if (size_a == size_b) {
- /* Find highest digit where a and b differ: */
- i = size_a;
- while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
- ;
- if (i < 0)
- return _PyLong_New(0);
- if (a->ob_digit[i] < b->ob_digit[i]) {
- sign = -1;
- { obj_p temp = a; a = b; b = temp; }
- }
- size_a = size_b = i+1;
- }
- z = _PyLong_New(size_a);
- if (z == NULL)
- return NULL;
- for (i = 0; i < size_b; ++i) {
- /* The following assumes unsigned arithmetic
- works module 2**N for some N>SHIFT. */
- borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
- z->ob_digit[i] = borrow & MASK;
- borrow >>= SHIFT;
- borrow &= 1; /* Keep only one sign bit */
- }
- for (; i < size_a; ++i) {
- borrow = a->ob_digit[i] - borrow;
- z->ob_digit[i] = borrow & MASK;
- borrow >>= SHIFT;
- borrow &= 1; /* Keep only one sign bit */
- }
- assert(borrow == 0);
- if (sign < 0)
- z->ob_size = -(z->ob_size);
- return long_normalize(z);
-}
-
-static obj_p
-long_add(obj_p v, obj_p w)
-{
- obj_p a, *b, *z;
-
- CONVERT_BINOP((obj_p)v, (obj_p)w, &a, &b);
-
- if (a->ob_size < 0) {
- if (b->ob_size < 0) {
- z = x_add(a, b);
- if (z != NULL && z->ob_size != 0)
- z->ob_size = -(z->ob_size);
- }
- else
- z = x_sub(b, a);
- }
- else {
- if (b->ob_size < 0)
- z = x_sub(a, b);
- else
- z = x_add(a, b);
- }
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p)z;
-}
-
-static obj_p
-long_sub(obj_p v, obj_p w)
-{
- obj_p a, *b, *z;
-
- CONVERT_BINOP((obj_p)v, (obj_p)w, &a, &b);
-
- if (a->ob_size < 0) {
- if (b->ob_size < 0)
- z = x_sub(a, b);
- else
- z = x_add(a, b);
- if (z != NULL && z->ob_size != 0)
- z->ob_size = -(z->ob_size);
- }
- else {
- if (b->ob_size < 0)
- z = x_add(a, b);
- else
- z = x_sub(a, b);
- }
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p)z;
-}
-
-/* Grade school multiplication, ignoring the signs.
- * Returns the absolute value of the product, or NULL if error.
- */
-static obj_p
-x_mul(obj_p a, obj_p b)
-{
- obj_p z;
- int size_a = abs(a->ob_size);
- int size_b = abs(b->ob_size);
- int i;
-
- z = _PyLong_New(size_a + size_b);
- if (z == NULL)
- return NULL;
-
- memset(z->ob_digit, 0, z->ob_size * sizeof(digit));
- for (i = 0; i < size_a; ++i) {
- twodigits carry = 0;
- twodigits f = a->ob_digit[i];
- int j;
- digit *pz = z->ob_digit + i;
-
- SIGCHECK({
- Py_DECREF(z);
- return NULL;
- })
- for (j = 0; j < size_b; ++j) {
- carry += *pz + b->ob_digit[j] * f;
- *pz++ = (digit) (carry & MASK);
- carry >>= SHIFT;
- }
- for (; carry != 0; ++j) {
- assert(i+j < z->ob_size);
- carry += *pz;
- *pz++ = (digit) (carry & MASK);
- carry >>= SHIFT;
- }
- }
- return long_normalize(z);
-}
-
-/* A helper for Karatsuba multiplication (k_mul).
- Takes a long "n" and an integer "size" representing the place to
- split, and sets low and high such that abs(n) == (high << size) + low,
- viewing the shift as being by digits. The sign bit is ignored, and
- the return values are >= 0.
- Returns 0 on success, -1 on failure.
-*/
-static int
-kmul_split(obj_p n, int size, obj_p *high, obj_p *low)
-{
- obj_p hi, *lo;
- int size_lo, size_hi;
- const int size_n = abs(n->ob_size);
-
- size_lo = MIN(size_n, size);
- size_hi = size_n - size_lo;
-
- if ((hi = _PyLong_New(size_hi)) == NULL)
- return -1;
- if ((lo = _PyLong_New(size_lo)) == NULL) {
- Py_DECREF(hi);
- return -1;
- }
-
- memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
- memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
-
- *high = long_normalize(hi);
- *low = long_normalize(lo);
- return 0;
-}
-
-static obj_p k_lopsided_mul(obj_p a, obj_p b);
-
-/* Karatsuba multiplication. Ignores the input signs, and returns the
- * absolute value of the product (or NULL if error).
- * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
- */
-static obj_p
-k_mul(obj_p a, obj_p b)
-{
- int asize = abs(a->ob_size);
- int bsize = abs(b->ob_size);
- obj_p ah = NULL;
- obj_p al = NULL;
- obj_p bh = NULL;
- obj_p bl = NULL;
- obj_p ret = NULL;
- obj_p t1, *t2, *t3;
- int shift; /* the number of digits we split off */
- int i;
-
- /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
- * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
- * Then the original product is
- * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
- * By picking X to be a power of 2, "*X" is just shifting, and it's
- * been reduced to 3 multiplies on numbers half the size.
- */
-
- /* We want to split based on the larger number; fiddle so that b
- * is largest.
- */
- if (asize > bsize) {
- t1 = a;
- a = b;
- b = t1;
-
- i = asize;
- asize = bsize;
- bsize = i;
- }
-
- /* Use gradeschool math when either number is too small. */
- if (asize <= KARATSUBA_CUTOFF) {
- if (asize == 0)
- return _PyLong_New(0);
- else
- return x_mul(a, b);
- }
-
- /* If a is small compared to b, splitting on b gives a degenerate
- * case with ah==0, and Karatsuba may be (even much) less efficient
- * than "grade school" then. However, we can still win, by viewing
- * b as a string of "big digits", each of width a->ob_size. That
- * leads to a sequence of balanced calls to k_mul.
- */
- if (2 * asize <= bsize)
- return k_lopsided_mul(a, b);
-
- /* Split a & b into hi & lo pieces. */
- shift = bsize >> 1;
- if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
- assert(ah->ob_size > 0); /* the split isn't degenerate */
-
- if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
-
- /* The plan:
- * 1. Allocate result space (asize + bsize digits: that's always
- * enough).
- * 2. Compute ah*bh, and copy into result at 2*shift.
- * 3. Compute al*bl, and copy into result at 0. Note that this
- * can't overlap with #2.
- * 4. Subtract al*bl from the result, starting at shift. This may
- * underflow (borrow out of the high digit), but we don't care:
- * we're effectively doing unsigned arithmetic mod
- * BASE**(sizea + sizeb), and so long as the *final* result fits,
- * borrows and carries out of the high digit can be ignored.
- * 5. Subtract ah*bh from the result, starting at shift.
- * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
- * at shift.
- */
-
- /* 1. Allocate result space. */
- ret = _PyLong_New(asize + bsize);
- if (ret == NULL) goto fail;
-#ifdef Py_DEBUG
- /* Fill with trash, to catch reference to uninitialized digits. */
- memset(ret->ob_digit, 0xDF, ret->ob_size * sizeof(digit));
-#endif
-
- /* 2. t1 <- ah*bh, and copy into high digits of result. */
- if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
- assert(t1->ob_size >= 0);
- assert(2*shift + t1->ob_size <= ret->ob_size);
- memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
- t1->ob_size * sizeof(digit));
-
- /* Zero-out the digits higher than the ah*bh copy. */
- i = ret->ob_size - 2*shift - t1->ob_size;
- if (i)
- memset(ret->ob_digit + 2*shift + t1->ob_size, 0,
- i * sizeof(digit));
-
- /* 3. t2 <- al*bl, and copy into the low digits. */
- if ((t2 = k_mul(al, bl)) == NULL) {
- Py_DECREF(t1);
- goto fail;
- }
- assert(t2->ob_size >= 0);
- assert(t2->ob_size <= 2*shift); /* no overlap with high digits */
- memcpy(ret->ob_digit, t2->ob_digit, t2->ob_size * sizeof(digit));
-
- /* Zero out remaining digits. */
- i = 2*shift - t2->ob_size; /* number of uninitialized digits */
- if (i)
- memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit));
-
- /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
- * because it's fresher in cache.
- */
- i = ret->ob_size - shift; /* # digits after shift */
- (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size);
- Py_DECREF(t2);
-
- (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size);
- Py_DECREF(t1);
-
- /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
- if ((t1 = x_add(ah, al)) == NULL) goto fail;
- Py_DECREF(ah);
- Py_DECREF(al);
- ah = al = NULL;
-
- if ((t2 = x_add(bh, bl)) == NULL) {
- Py_DECREF(t1);
- goto fail;
- }
- Py_DECREF(bh);
- Py_DECREF(bl);
- bh = bl = NULL;
-
- t3 = k_mul(t1, t2);
- Py_DECREF(t1);
- Py_DECREF(t2);
- if (t3 == NULL) goto fail;
- assert(t3->ob_size >= 0);
-
- /* Add t3. It's not obvious why we can't run out of room here.
- * See the (*) comment after this function.
- */
- (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size);
- Py_DECREF(t3);
-
- return long_normalize(ret);
-
- fail:
- Py_XDECREF(ret);
- Py_XDECREF(ah);
- Py_XDECREF(al);
- Py_XDECREF(bh);
- Py_XDECREF(bl);
- return NULL;
-}
-
-/* (*) Why adding t3 can't "run out of room" above.
-
-Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
-to start with:
-
-1. For any integer i, i = c(i/2) + f(i/2). In particular,
- bsize = c(bsize/2) + f(bsize/2).
-2. shift = f(bsize/2)
-3. asize <= bsize
-4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
- routine, so asize > bsize/2 >= f(bsize/2) in this routine.
-
-We allocated asize + bsize result digits, and add t3 into them at an offset
-of shift. This leaves asize+bsize-shift allocated digit positions for t3
-to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
-asize + c(bsize/2) available digit positions.
-
-bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
-at most c(bsize/2) digits + 1 bit.
-
-If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
-digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
-most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
-
-The product (ah+al)*(bh+bl) therefore has at most
-
- c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
-
-and we have asize + c(bsize/2) available digit positions. We need to show
-this is always enough. An instance of c(bsize/2) cancels out in both, so
-the question reduces to whether asize digits is enough to hold
-(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
-then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
-asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
-digit is enough to hold 2 bits. This is so since SHIFT=15 >= 2. If
-asize == bsize, then we're asking whether bsize digits is enough to hold
-c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
-is enough to hold 2 bits. This is so if bsize >= 2, which holds because
-bsize >= KARATSUBA_CUTOFF >= 2.
-
-Note that since there's always enough room for (ah+al)*(bh+bl), and that's
-clearly >= each of ah*bh and al*bl, there's always enough room to subtract
-ah*bh and al*bl too.
-*/
-
-/* b has at least twice the digits of a, and a is big enough that Karatsuba
- * would pay off *if* the inputs had balanced sizes. View b as a sequence
- * of slices, each with a->ob_size digits, and multiply the slices by a,
- * one at a time. This gives k_mul balanced inputs to work with, and is
- * also cache-friendly (we compute one double-width slice of the result
- * at a time, then move on, never bactracking except for the helpful
- * single-width slice overlap between successive partial sums).
- */
-static obj_p
-k_lopsided_mul(obj_p a, obj_p b)
-{
- const int asize = abs(a->ob_size);
- int bsize = abs(b->ob_size);
- int nbdone; /* # of b digits already multiplied */
- obj_p ret;
- obj_p bslice = NULL;
-
- assert(asize > KARATSUBA_CUTOFF);
- assert(2 * asize <= bsize);
-
- /* Allocate result space, and zero it out. */
- ret = _PyLong_New(asize + bsize);
- if (ret == NULL)
- return NULL;
- memset(ret->ob_digit, 0, ret->ob_size * sizeof(digit));
-
- /* Successive slices of b are copied into bslice. */
- bslice = _PyLong_New(asize);
- if (bslice == NULL)
- goto fail;
-
- nbdone = 0;
- while (bsize > 0) {
- obj_p product;
- const int nbtouse = MIN(bsize, asize);
-
- /* Multiply the next slice of b by a. */
- memcpy(bslice->ob_digit, b->ob_digit + nbdone,
- nbtouse * sizeof(digit));
- bslice->ob_size = nbtouse;
- product = k_mul(a, bslice);
- if (product == NULL)
- goto fail;
-
- /* Add into result. */
- (void)v_iadd(ret->ob_digit + nbdone, ret->ob_size - nbdone,
- product->ob_digit, product->ob_size);
- Py_DECREF(product);
-
- bsize -= nbtouse;
- nbdone += nbtouse;
- }
-
- Py_DECREF(bslice);
- return long_normalize(ret);
-
- fail:
- Py_DECREF(ret);
- Py_XDECREF(bslice);
- return NULL;
-}
-
-static obj_p
-long_mul(obj_p v, obj_p w)
-{
- obj_p a, *b, *z;
-
- if (!convert_binop((obj_p)v, (obj_p)w, &a, &b)) {
- Py_INCREF(Py_NotImplemented);
- return Py_NotImplemented;
- }
-
- z = k_mul(a, b);
- /* Negate if exactly one of the inputs is negative. */
- if (((a->ob_size ^ b->ob_size) < 0) && z)
- z->ob_size = -(z->ob_size);
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p)z;
-}
-
-/* The / and % operators are now defined in terms of divmod().
- The expression a mod b has the value a - b*floor(a/b).
- The long_divrem function gives the remainder after division of
- |a| by |b|, with the sign of a. This is also expressed
- as a - b*trunc(a/b), if trunc truncates towards zero.
- Some examples:
- a b a rem b a mod b
- 13 10 3 3
- -13 10 -3 7
- 13 -10 3 -7
- -13 -10 -3 -3
- So, to get from rem to mod, we have to add b if a and b
- have different signs. We then subtract one from the 'div'
- part of the outcome to keep the invariant intact. */
-
-static int
-l_divmod(obj_p v, obj_p w,
- obj_p *pdiv, obj_p *pmod)
-{
- obj_p div, *mod;
-
- if (long_divrem(v, w, &div, &mod) < 0)
- return -1;
- if ((mod->ob_size < 0 && w->ob_size > 0) ||
- (mod->ob_size > 0 && w->ob_size < 0)) {
- obj_p temp;
- obj_p one;
- temp = (obj_p) long_add(mod, w);
- Py_DECREF(mod);
- mod = temp;
- if (mod == NULL) {
- Py_DECREF(div);
- return -1;
- }
- one = (obj_p) PyLong_FromLong(1L);
- if (one == NULL ||
- (temp = (obj_p) long_sub(div, one)) == NULL) {
- Py_DECREF(mod);
- Py_DECREF(div);
- Py_XDECREF(one);
- return -1;
- }
- Py_DECREF(one);
- Py_DECREF(div);
- div = temp;
- }
- *pdiv = div;
- *pmod = mod;
- return 0;
-}
-
-static obj_p
-long_div(obj_p v, obj_p w)
-{
- obj_p a, *b, *div, *mod;
-
- CONVERT_BINOP(v, w, &a, &b);
-
- if (l_divmod(a, b, &div, &mod) < 0) {
- Py_DECREF(a);
- Py_DECREF(b);
- return NULL;
- }
- Py_DECREF(a);
- Py_DECREF(b);
- Py_DECREF(mod);
- return (obj_p)div;
-}
-
-static obj_p
-long_classic_div(obj_p v, obj_p w)
-{
- obj_p a, *b, *div, *mod;
-
- CONVERT_BINOP(v, w, &a, &b);
-
- if (Py_DivisionWarningFlag &&
- PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
- div = NULL;
- else if (l_divmod(a, b, &div, &mod) < 0)
- div = NULL;
- else
- Py_DECREF(mod);
-
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p)div;
-}
-
-static obj_p
-long_true_divide(obj_p v, obj_p w)
-{
- obj_p a, *b;
- double ad, bd;
- int aexp, bexp, failed;
-
- CONVERT_BINOP(v, w, &a, &b);
- ad = _PyLong_AsScaledDouble((obj_p)a, &aexp);
- bd = _PyLong_AsScaledDouble((obj_p)b, &bexp);
- failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
- Py_DECREF(a);
- Py_DECREF(b);
- if (failed)
- return NULL;
-
- if (bd == 0.0) {
- PyErr_SetString(PyExc_ZeroDivisionError,
- "long division or modulo by zero");
- return NULL;
- }
-
- /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */
- ad /= bd; /* overflow/underflow impossible here */
- aexp -= bexp;
- if (aexp > INT_MAX / SHIFT)
- goto overflow;
- else if (aexp < -(INT_MAX / SHIFT))
- return PyFloat_FromDouble(0.0); /* underflow to 0 */
- errno = 0;
- ad = ldexp(ad, aexp * SHIFT);
- if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
- goto overflow;
- return PyFloat_FromDouble(ad);
-
-overflow:
- PyErr_SetString(PyExc_OverflowError,
- "long/long too large for a float");
- return NULL;
-
-}
-
-static obj_p
-long_mod(obj_p v, obj_p w)
-{
- obj_p a, *b, *div, *mod;
-
- CONVERT_BINOP(v, w, &a, &b);
-
- if (l_divmod(a, b, &div, &mod) < 0) {
- Py_DECREF(a);
- Py_DECREF(b);
- return NULL;
- }
- Py_DECREF(a);
- Py_DECREF(b);
- Py_DECREF(div);
- return (obj_p)mod;
-}
-
-static obj_p
-long_divmod(obj_p v, obj_p w)
-{
- obj_p a, *b, *div, *mod;
- obj_p z;
-
- CONVERT_BINOP(v, w, &a, &b);
-
- if (l_divmod(a, b, &div, &mod) < 0) {
- Py_DECREF(a);
- Py_DECREF(b);
- return NULL;
- }
- z = PyTuple_New(2);
- if (z != NULL) {
- PyTuple_SetItem(z, 0, (obj_p) div);
- PyTuple_SetItem(z, 1, (obj_p) mod);
- }
- else {
- Py_DECREF(div);
- Py_DECREF(mod);
- }
- Py_DECREF(a);
- Py_DECREF(b);
- return z;
-}
-
-static obj_p
-long_pow(obj_p v, obj_p w, obj_p x)
-{
- obj_p a, *b;
- obj_p c;
- obj_p z, *div, *mod;
- int size_b, i;
-
- CONVERT_BINOP(v, w, &a, &b);
- if (PyLong_Check(x) || Py_None == x) {
- c = x;
- Py_INCREF(x);
- }
- else if (PyInt_Check(x)) {
- c = PyLong_FromLong(PyInt_AS_LONG(x));
- }
- else {
- Py_DECREF(a);
- Py_DECREF(b);
- Py_INCREF(Py_NotImplemented);
- return Py_NotImplemented;
- }
-
- if (c != Py_None && ((obj_p)c)->ob_size == 0) {
- PyErr_SetString(PyExc_ValueError,
- "pow() 3rd argument cannot be 0");
- z = NULL;
- goto error;
- }
-
- size_b = b->ob_size;
- if (size_b < 0) {
- Py_DECREF(a);
- Py_DECREF(b);
- Py_DECREF(c);
- if (x != Py_None) {
- PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
- "cannot be negative when 3rd argument specified");
- return NULL;
- }
- /* 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);
- }
- z = (obj_p)PyLong_FromLong(1L);
- for (i = 0; i < size_b; ++i) {
- digit bi = b->ob_digit[i];
- int j;
-
- for (j = 0; j < SHIFT; ++j) {
- obj_p temp;
-
- if (bi & 1) {
- temp = (obj_p)long_mul(z, a);
- Py_DECREF(z);
- if (c!=Py_None && temp!=NULL) {
- if (l_divmod(temp,(obj_p)c,
- &div,&mod) < 0) {
- Py_DECREF(temp);
- z = NULL;
- goto error;
- }
- Py_XDECREF(div);
- Py_DECREF(temp);
- temp = mod;
- }
- z = temp;
- if (z == NULL)
- break;
- }
- bi >>= 1;
- if (bi == 0 && i+1 == size_b)
- break;
- temp = (obj_p)long_mul(a, a);
- Py_DECREF(a);
- if (c!=Py_None && temp!=NULL) {
- if (l_divmod(temp, (obj_p)c, &div,
- &mod) < 0) {
- Py_DECREF(temp);
- z = NULL;
- goto error;
- }
- Py_XDECREF(div);
- Py_DECREF(temp);
- temp = mod;
- }
- a = temp;
- if (a == NULL) {
- Py_DECREF(z);
- z = NULL;
- break;
- }
- }
- if (a == NULL || z == NULL)
- break;
- }
- if (c!=Py_None && z!=NULL) {
- if (l_divmod(z, (obj_p)c, &div, &mod) < 0) {
- Py_DECREF(z);
- z = NULL;
- }
- else {
- Py_XDECREF(div);
- Py_DECREF(z);
- z = mod;
- }
- }
- error:
- Py_XDECREF(a);
- Py_DECREF(b);
- Py_DECREF(c);
- return (obj_p)z;
-}
-
-static obj_p
-long_invert(obj_p v)
-{
- /* Implement ~x as -(x+1) */
- obj_p x;
- obj_p w;
- w = (obj_p)PyLong_FromLong(1L);
- if (w == NULL)
- return NULL;
- x = (obj_p) long_add(v, w);
- Py_DECREF(w);
- if (x == NULL)
- return NULL;
- x->ob_size = -(x->ob_size);
- return (obj_p)x;
-}
-
-static obj_p
-long_pos(obj_p v)
-{
- if (PyLong_CheckExact(v)) {
- Py_INCREF(v);
- return (obj_p)v;
- }
- else
- return _PyLong_Copy(v);
-}
-
-static obj_p
-long_neg(obj_p v)
-{
- obj_p z;
- if (v->ob_size == 0 && PyLong_CheckExact(v)) {
- /* -0 == 0 */
- Py_INCREF(v);
- return (obj_p) v;
- }
- z = (obj_p)_PyLong_Copy(v);
- if (z != NULL)
- z->ob_size = -(v->ob_size);
- return (obj_p)z;
-}
-
-static obj_p
-long_abs(obj_p v)
-{
- if (v->ob_size < 0)
- return long_neg(v);
- else
- return long_pos(v);
-}
-
-static int
-long_nonzero(obj_p v)
-{
- return abs(v->ob_size) != 0;
-}
-
-static obj_p
-long_rshift(obj_p v, obj_p w)
-{
- obj_p a, *b;
- obj_p z = NULL;
- long shiftby;
- int newsize, wordshift, loshift, hishift, i, j;
- digit lomask, himask;
-
- CONVERT_BINOP((obj_p)v, (obj_p)w, &a, &b);
-
- if (a->ob_size < 0) {
- /* Right shifting negative numbers is harder */
- obj_p a1, *a2;
- a1 = (obj_p) long_invert(a);
- if (a1 == NULL)
- goto rshift_error;
- a2 = (obj_p) long_rshift(a1, b);
- Py_DECREF(a1);
- if (a2 == NULL)
- goto rshift_error;
- z = (obj_p) long_invert(a2);
- Py_DECREF(a2);
- }
- else {
-
- shiftby = PyLong_AsLong((obj_p)b);
- if (shiftby == -1L && PyErr_Occurred())
- goto rshift_error;
- if (shiftby < 0) {
- PyErr_SetString(PyExc_ValueError,
- "negative shift count");
- goto rshift_error;
- }
- wordshift = shiftby / SHIFT;
- newsize = abs(a->ob_size) - wordshift;
- if (newsize <= 0) {
- z = _PyLong_New(0);
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p)z;
- }
- loshift = shiftby % SHIFT;
- hishift = SHIFT - loshift;
- lomask = ((digit)1 << hishift) - 1;
- himask = MASK ^ lomask;
- z = _PyLong_New(newsize);
- if (z == NULL)
- goto rshift_error;
- if (a->ob_size < 0)
- z->ob_size = -(z->ob_size);
- for (i = 0, j = wordshift; i < newsize; i++, j++) {
- z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
- if (i+1 < newsize)
- z->ob_digit[i] |=
- (a->ob_digit[j+1] << hishift) & himask;
- }
- z = long_normalize(z);
- }
-rshift_error:
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p) z;
-
-}
-
-static obj_p
-long_lshift(obj_p v, obj_p w)
-{
- /* This version due to Tim Peters */
- obj_p a, *b;
- obj_p z = NULL;
- long shiftby;
- int oldsize, newsize, wordshift, remshift, i, j;
- twodigits accum;
-
- CONVERT_BINOP(v, w, &a, &b);
-
- shiftby = PyLong_AsLong((obj_p)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;
- }
- /* wordshift, remshift = divmod(shiftby, SHIFT) */
- wordshift = (int)shiftby / SHIFT;
- remshift = (int)shiftby - wordshift * SHIFT;
-
- oldsize = abs(a->ob_size);
- newsize = oldsize + wordshift;
- if (remshift)
- ++newsize;
- z = _PyLong_New(newsize);
- if (z == NULL)
- goto lshift_error;
- if (a->ob_size < 0)
- z->ob_size = -(z->ob_size);
- for (i = 0; i < wordshift; i++)
- z->ob_digit[i] = 0;
- accum = 0;
- for (i = wordshift, j = 0; j < oldsize; i++, j++) {
- accum |= (twodigits)a->ob_digit[j] << remshift;
- z->ob_digit[i] = (digit)(accum & MASK);
- accum >>= SHIFT;
- }
- if (remshift)
- z->ob_digit[newsize-1] = (digit)accum;
- else
- assert(!accum);
- z = long_normalize(z);
-lshift_error:
- Py_DECREF(a);
- Py_DECREF(b);
- return (obj_p) z;
-}
-
-
-/* Bitwise and/xor/or operations */
-
-static obj_p
-long_bitwise(obj_p a,
- int op, /* '&', '|', '^' */
- obj_p b)
-{
- digit maska, maskb; /* 0 or MASK */
- int negz;
- int size_a, size_b, size_z;
- obj_p z;
- int i;
- digit diga, digb;
- obj_p v;
-
- if (a->ob_size < 0) {
- a = (obj_p) long_invert(a);
- maska = MASK;
- }
- else {
- Py_INCREF(a);
- maska = 0;
- }
- if (b->ob_size < 0) {
- b = (obj_p) long_invert(b);
- maskb = MASK;
- }
- else {
- Py_INCREF(b);
- maskb = 0;
- }
-
- negz = 0;
- switch (op) {
- case '^':
- if (maska != maskb) {
- maska ^= MASK;
- negz = -1;
- }
- break;
- case '&':
- if (maska && maskb) {
- op = '|';
- maska ^= MASK;
- maskb ^= MASK;
- negz = -1;
- }
- break;
- case '|':
- if (maska || maskb) {
- op = '&';
- maska ^= MASK;
- maskb ^= MASK;
- negz = -1;
- }
- break;
- }
-
- /* JRH: The original logic here was to allocate the result value (z)
- as the longer of the two operands. However, there are some cases
- where the result is guaranteed to be shorter than that: AND of two
- positives, OR of two negatives: use the shorter number. AND with
- mixed signs: use the positive number. OR with mixed signs: use the
- negative number. After the transformations above, op will be '&'
- iff one of these cases applies, and mask will be non-0 for operands
- whose length should be ignored.
- */
-
- size_a = a->ob_size;
- size_b = b->ob_size;
- size_z = op == '&'
- ? (maska
- ? size_b
- : (maskb ? size_a : MIN(size_a, size_b)))
- : MAX(size_a, size_b);
- z = _PyLong_New(size_z);
- if (a == NULL || b == NULL || z == NULL) {
- Py_XDECREF(a);
- Py_XDECREF(b);
- Py_XDECREF(z);
- return NULL;
- }
-
- for (i = 0; i < size_z; ++i) {
- diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
- digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
- switch (op) {
- case '&': z->ob_digit[i] = diga & digb; break;
- case '|': z->ob_digit[i] = diga | digb; break;
- case '^': z->ob_digit[i] = diga ^ digb; break;
- }
- }
-
- Py_DECREF(a);
- Py_DECREF(b);
- z = long_normalize(z);
- if (negz == 0)
- return (obj_p) z;
- v = long_invert(z);
- Py_DECREF(z);
- return v;
-}
-
-static obj_p
-long_and(obj_p v, obj_p w)
-{
- obj_p a, *b;
- obj_p c;
- CONVERT_BINOP(v, w, &a, &b);
- c = long_bitwise(a, '&', b);
- Py_DECREF(a);
- Py_DECREF(b);
- return c;
-}
-
-static obj_p
-long_xor(obj_p v, obj_p w)
-{
- obj_p a, *b;
- obj_p c;
- CONVERT_BINOP(v, w, &a, &b);
- c = long_bitwise(a, '^', b);
- Py_DECREF(a);
- Py_DECREF(b);
- return c;
-}
-
-static obj_p
-long_or(obj_p v, obj_p w)
-{
- obj_p a, *b;
- obj_p c;
- CONVERT_BINOP(v, w, &a, &b);
- c = long_bitwise(a, '|', b);
- Py_DECREF(a);
- Py_DECREF(b);
- return c;
-}
-
-static int
-long_coerce(obj_p *pv, obj_p *pw)
-{
- if (PyInt_Check(*pw)) {
- *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
- Py_INCREF(*pv);
- return 0;
- }
- else if (PyLong_Check(*pw)) {
- Py_INCREF(*pv);
- Py_INCREF(*pw);
- return 0;
- }
- return 1; /* Can't do it */
-}
-
-static obj_p
-long_long(obj_p v)
-{
- Py_INCREF(v);
- return v;
-}
-
-static obj_p
-long_int(obj_p v)
-{
- long x;
- x = PyLong_AsLong(v);
- if (PyErr_Occurred()) {
- if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
- PyErr_Clear();
- if (PyLong_CheckExact(v)) {
- Py_INCREF(v);
- return v;
- }
- else
- return _PyLong_Copy((obj_p)v);
- }
- else
- return NULL;
- }
- return PyInt_FromLong(x);
-}
-
-static obj_p
-long_float(obj_p v)
-{
- double result;
- result = PyLong_AsDouble(v);
- if (result == -1.0 && PyErr_Occurred())
- return NULL;
- return PyFloat_FromDouble(result);
-}
-
-static obj_p
-long_oct(obj_p v)
-{
- return long_format(v, 8, 1);
-}
-
-static obj_p
-long_hex(obj_p v)
-{
- return long_format(v, 16, 1);
-}
-
-static obj_p
-long_subtype_new(PyTypeObject *type, obj_p args, obj_p kwds);
-
-static obj_p
-long_new(PyTypeObject *type, obj_p args, obj_p kwds)
-{
- obj_p 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:long", kwlist,
- &x, &base))
- return NULL;
- if (x == NULL)
- return PyLong_FromLong(0L);
- if (base == -909)
- return PyNumber_Long(x);
- else if (PyString_Check(x))
- return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
-#ifdef Py_USING_UNICODE
- else if (PyUnicode_Check(x))
- return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
- PyUnicode_GET_SIZE(x),
- base);
-#endif
- else {
- PyErr_SetString(PyExc_TypeError,
- "long() 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 obj_p
-long_subtype_new(PyTypeObject *type, obj_p args, obj_p kwds)
-{
- obj_p tmp, *new;
- int i, n;
-
- assert(PyType_IsSubtype(type, &PyLong_Type));
- tmp = (obj_p)long_new(&PyLong_Type, args, kwds);
- if (tmp == NULL)
- return NULL;
- assert(PyLong_CheckExact(tmp));
- n = tmp->ob_size;
- if (n < 0)
- n = -n;
- new = (obj_p)type->tp_alloc(type, n);
- if (new == NULL) {
- Py_DECREF(tmp);
- return NULL;
- }
- assert(PyLong_Check(new));
- new->ob_size = tmp->ob_size;
- for (i = 0; i < n; i++)
- new->ob_digit[i] = tmp->ob_digit[i];
- Py_DECREF(tmp);
- return (obj_p)new;
-}
-
-static obj_p
-long_getnewargs(obj_p v)
-{
- return Py_BuildValue("(N)", _PyLong_Copy(v));
-}
-
-static PyMethodDef long_methods[] = {
- {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS},
- {NULL, NULL} /* sentinel */
-};
-
-PyDoc_STRVAR(long_doc,
-"long(x[, base]) -> integer\n\
-\n\
-Convert a string or number to a long 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*/
- (binaryfunc) long_classic_div, /*nb_divide*/
- (binaryfunc) long_mod, /*nb_remainder*/
- (binaryfunc) long_divmod, /*nb_divmod*/
- (ternaryfunc) long_pow, /*nb_power*/
- (unaryfunc) long_neg, /*nb_negative*/
- (unaryfunc) long_pos, /*tp_positive*/
- (unaryfunc) long_abs, /*tp_absolute*/
- (inquiry) long_nonzero, /*tp_nonzero*/
- (unaryfunc) long_invert, /*nb_invert*/
- (binaryfunc) long_lshift, /*nb_lshift*/
- (binaryfunc) long_rshift, /*nb_rshift*/
- (binaryfunc) long_and, /*nb_and*/
- (binaryfunc) long_xor, /*nb_xor*/
- (binaryfunc) long_or, /*nb_or*/
- (coercion) long_coerce, /*nb_coerce*/
- (unaryfunc) long_int, /*nb_int*/
- (unaryfunc) long_long, /*nb_long*/
- (unaryfunc) long_float, /*nb_float*/
- (unaryfunc) long_oct, /*nb_oct*/
- (unaryfunc) long_hex, /*nb_hex*/
- 0, /* nb_inplace_add */
- 0, /* nb_inplace_subtract */
- 0, /* nb_inplace_multiply */
- 0, /* nb_inplace_divide */
- 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 */
- (binaryfunc)long_div, /* nb_floor_divide */
- long_true_divide, /* nb_true_divide */
- 0, /* nb_inplace_floor_divide */
- 0, /* nb_inplace_true_divide */
-};
-
-PyTypeObject PyLong_Type = {
- PyObject_HEAD_INIT(&PyType_Type)
- 0, /* ob_size */
- "long", /* tp_name */
- sizeof(PyLongObject) - sizeof(digit), /* tp_basicsize */
- sizeof(digit), /* tp_itemsize */
- (destructor)long_dealloc, /* tp_dealloc */
- 0, /* tp_print */
- 0, /* tp_getattr */
- 0, /* tp_setattr */
- (cmpfunc)long_compare, /* tp_compare */
- (reprfunc)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 */
- (reprfunc)long_str, /* tp_str */
- PyObject_GenericGetAttr, /* tp_getattro */
- 0, /* tp_setattro */
- 0, /* tp_as_buffer */
- Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
- Py_TPFLAGS_BASETYPE, /* tp_flags */
- long_doc, /* tp_doc */
- 0, /* tp_traverse */
- 0, /* tp_clear */
- 0, /* tp_richcompare */
- 0, /* tp_weaklistoffset */
- 0, /* tp_iter */
- 0, /* tp_iternext */
- long_methods, /* tp_methods */
- 0, /* tp_members */
- 0, /* 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 */
-};
-
Modified: trunk/src/builtins-core.c
===================================================================
--- trunk/src/builtins-core.c 2004-05-28 00:09:58 UTC (rev 559)
+++ trunk/src/builtins-core.c 2004-05-28 05:50:02 UTC (rev 560)
@@ -491,8 +491,10 @@
EXCEPTION_DECLARE(Exception_OBJ, INDEX_EXC, IndexError, "Index Error");
EXCEPTION_DECLARE(Exception_OBJ, FUNCNOTFOUND_EXC, FunctionNotFound, "Function not found Error");
EXCEPTION_DECLARE(Exception_OBJ, TYPE_EXC, TypeError, "Type Error");
+EXCEPTION_DECLARE(Exception_OBJ, VALUE_EXC, ValueError, "Value Error");
EXCEPTION_DECLARE(Exception_OBJ, MUTABLE_EXC, MutableError, "Mutable Error");
EXCEPTION_DECLARE(Exception_OBJ, DIVIDEZERO_EXC, DivideByZero, "Divide by zero Error");
+EXCEPTION_DECLARE(Exception_OBJ, OVERFLOW_EXC, OverflowError, "Overflow Error");
EXCEPTION_DECLARE(Exception_OBJ, OUTOFMEMORY_EXC, OutOfMemoryError, "Out of memory Error");
EXCEPTION_DECLARE(Exception_OBJ, IOEXCEPTION, IOError, "IO Error");
EXCEPTION_DECLARE(OBJ(IOEXCEPTION), FILENOTFOUND_EXC, FileNotFound, "File not found Error");
Modified: trunk/src/builtins-int.c
===================================================================
--- trunk/src/builtins-int.c 2004-05-28 00:09:58 UTC (rev 559)
+++ trunk/src/builtins-int.c 2004-05-28 05:50:02 UTC (rev 560)
@@ -25,7 +25,7 @@
* changes made to Prothon.
*
* 4. HCA is making Prothon available to Licensee on an "AS IS" basis.
- * HCA MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY
+ * HCA MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY
* OF EXAMPLE, BUT NOT LIMITATION, HCA MAKES NO AND DISCLAIMS ANY
* REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS FOR ANY
* PARTICULAR PURPOSE OR THAT THE USE OF PROTHON WILL NOT INFRINGE ANY
@@ -41,7 +41,7 @@
*
* 7. Nothing in this License Agreement shall be deemed to create any
* relationship of agency, partnership, or joint venture between HCA and
- * Licensee. This License Agreement does not grant permission to use HCA
+ * Licensee. This License Agreement does not grant permission to use HCA
* trademarks or trade name in a trademark sense to endorse or promote
* products or services of Licensee, or any third party.
*
@@ -50,11 +50,11 @@
* ====================================================================
*/
+// builtins-int.c
-// builtins.c
-
#include <stdio.h>
#include <string.h>
+#include <math.h>
#include <apr_strings.h>
@@ -64,6 +64,63 @@
#include "object.h"
#include <prothon/prothon_dll.h>
+/* includes (arbitrary precision) integer object implementation */
+// copied from python/python/dist/src/Objects/longobject.c
+// and heavily modified for use in Prothon
+
+/* For long multiplication, use the O(N**2) school algorithm unless
+ * both operands contain more than KARATSUBA_CUTOFF digits (this
+ * being an internal long digit, in base BASE).
+ */
+#define KARATSUBA_CUTOFF 35
+
+#define INT_MAX 2147483647 /* maximum (signed) int value */
+#define Py_IS_INFINITY(X) ((X) && (X)*0.5 == (X))
+
+typedef u16_t digit;
+typedef u32_t wdigit;
+#define BASE_TWODIGITS_TYPE long
+typedef unsigned BASE_TWODIGITS_TYPE twodigits;
+typedef BASE_TWODIGITS_TYPE stwodigits; /* signed variant of twodigits */
+
+#define SHIFT 15
+#define BASE ((digit)1 << SHIFT)
+#define MASK ((int)(BASE - 1))
+
+typedef struct {
+ int size;
+ digit digit[];
+} long_t;
+
+typedef long_t* long_p;
+
+#define SIGCHECK(x) if (0) x
+#define Py_CHARMASK(c) ((c) & 0xff)
+#define Py_INCREF
+#define Py_XDECREF
+
+/* Forward */
+static long_p long_normalize(long_p);
+static long_p mul1(long_p, wdigit);
+static long_p muladd1(long_p, wdigit, wdigit);
+static long_p divrem1(long_p, digit, digit *);
+static obj_p long_format(long_p aa, int base, int addL);
+
+/* Long integer representation.
+ The absolute value of a number is equal to
+ SUM(for i=0 through abs(size)-1) digit[i] * 2**(SHIFT*i)
+ Negative numbers are represented with size < 0;
+ zero is represented by size == 0.
+ In a normalized number, digit[abs(size)-1] (the most significant
+ digit) is never zero. Also, in all cases, for all valid i,
+ 0 <= digit[i] <= MASK.
+ The allocation function takes care of allocating extra memory
+ so that digit[0] ... digit[abs(size)-1] are actually available.
+*/
+
+MODULE_DECLARE(Int);
+MODULE_DECLARE(IntGen);
+
//********************************* new_int_obj *******************************
obj_p new_int_obj(isp ist, i64_t num){
obj_p obj = NEW_OBJ(OBJ(INT_PROTO));
@@ -74,12 +131,1927 @@
return obj;
}
-MODULE_DECLARE(Int);
-MODULE_DECLARE(IntGen);
+/* Normalize (remove leading zeros from) a int object.
+ Doesn't attempt to free the storage--in most cases, due to the nature
+ of the algorithms used, this could save at most be one word anyway. */
+static long_p long_normalize(register long_p v) {
+ int j = abs(v->size);
+ register int i = j;
-// ***************************** INT *******************************************
+ while (i > 0 && v->digit[i-1] == 0)
+ --i;
+ if (i != j)
+ v->size = (v->size < 0) ? -(i) : i;
+ return v;
+}
+/* Allocate a new long int object with size digits.
+ Return NULL and set exception if we run out of memory. */
+
+long_p new_longp_non_init(int size) {
+ return (long_p) pr_malloc(sizeof(long_t) + size * sizeof(digit));
+}
+
+long_p copy_longp(long_p src) {
+ long_p result;
+ int i;
+
+ assert(src != NULL);
+ i = src->size;
+ if (i < 0)
+ i = -(i);
+ result = new_longp_non_init(i);
+ if (result != NULL) {
+ result->size = src->size;
+ while (--i >= 0)
+ result->digit[i] = src->digit[i];
+ }
+ return (long_p)result;
+}
+
+/* Create a new long_p from a i64_t */
+long_p new_longp(i64_t ival)
+{
+ long_p v;
+ u64_t t; /* unsigned so >> doesn't propagate sign bit */
+ int ndigits = 0;
+ int negative = 0;
+
+ if (ival < 0) {
+ ival = -ival;
+ negative = 1;
+ }
+ /* Count the number of digits.
+ We used to pick 5 ("big enough for anything"), but that's a
+ waste of time and space given that 5*15 = 75 bits are rarely
+ needed. */
+ t = (u64_t) ival;
+ while (t) {
+ ++ndigits;
+ t >>= SHIFT;
+ }
+ v = new_longp_non_init(ndigits);
+ if (v != NULL) {
+ digit *p = v->digit;
+ v->size = negative ? -ndigits : ndigits;
+ t = (unsigned long)ival;
+ while (t) {
+ *p++ = (digit)(t & MASK);
+ t >>= SHIFT;
+ }
+ }
+ return (long_p) v;
+}
+
+/* Create a new long int object from a C double */
+long_p double2longp(double dval) {
+ long_p v;
+ double frac;
+ int i, ndig, expo, neg;
+ neg = 0;
+ if (Py_IS_INFINITY(dval)) {
+ raise_exception(ist, OBJ(OVERFLOW_EXC),
+ "cannot convert float infinity to long");
+ return NULL;
+ }
+ if (dval < 0.0) {
+ neg = 1;
+ dval = -dval;
+ }
+ frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
+ if (expo <= 0)
+ return new_longp(0L);
+ ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
+ v = new_longp_non_init(ndig);
+ if (v == NULL)
+ return NULL;
+ frac = ldexp(frac, (expo-1) % SHIFT + 1);
+ for (i = ndig; --i >= 0; ) {
+ long bits = (long)frac;
+ v->digit[i] = (digit) bits;
+ frac = frac - (double)bits;
+ frac = ldexp(frac, SHIFT);
+ }
+ if (neg)
+ v->size = -(v->size);
+ return (long_p)v;
+}
+
+/* Get a C long int from a long int object.
+ Returns -1 and sets an error condition if overflow occurs. */
+
+i64_t longp2int64(long_p vv) {
+ /* This version by Tim Peters */
+ register long_p v;
+ u64_t x, prev;
+ int i, sign;
+
+ v = (long_p) vv;
+ i = v->size;
+ sign = 1;
+ x = 0;
+ if (i < 0) {
+ sign = -1;
+ i = -(i);
+ }
+ while (--i >= 0) {
+ prev = x;
+ x = (x << SHIFT) + v->digit[i];
+ if ((x >> SHIFT) != prev)
+ goto overflow;
+ }
+ /* Haven't lost any bits, but if the sign bit is set we're in
+ * trouble *unless* this is the min negative number. So,
+ * trouble iff sign bit set && (positive || some bit set other
+ * than the sign bit).
+ */
+ if ((i64_t) x < 0 && (sign > 0 || (x << 1) != 0))
+ goto overflow;
+ return (i64_t) x * sign;
+
+ overflow:
+ raise_exception(ist, OBJ(OVERFLOW_EXC),
+ "long int too large to convert to int");
+ return -1;
+}
+
+int _PyLong_Sign(long_p vv)
+{
+ long_p v = (long_p)vv;
+ assert(v != NULL);
+ return v->size == 0 ? 0 : (v->size < 0 ? -1 : 1);
+}
+
+size_t
+_PyLong_NumBits(long_p vv)
+{
+ long_p v = (long_p)vv;
+ size_t result = 0;
+ int ndigits;
+
+ assert(v != NULL);
+ assert(PyLong_Check(v));
+ ndigits = abs(v->size);
+ assert(ndigits == 0 || v->digit[ndigits - 1] != 0);
+ if (ndigits > 0) {
+ digit msd = v->digit[ndigits - 1];
+
+ result = (ndigits - 1) * SHIFT;
+ if (result / SHIFT != (size_t)ndigits - 1)
+ goto Overflow;
+ do {
+ ++result;
+ if (result == 0)
+ goto Overflow;
+ msd >>= 1;
+ } while (msd);
+ }
+ return result;
+
+Overflow:
+ raise_exception(ist, OBJ(OVERFLOW_EXC), "long has too many bits "
+ "to express in a platform size_t");
+ return (size_t)-1;
+}
+
+
+double _PyLong_AsScaledDouble(long_p vv, int *exponent)
+{
+/* NBITS_WANTED should be > the number of bits in a double's precision,
+ but small enough so that 2**NBITS_WANTED is within the normal double
+ range. nbitsneeded is set to 1 less than that because the most-significant
+ digit contains at least 1 significant bit, but we don't want to
+ bother counting them (catering to the worst case cheaply).
+
+ 57 is one more than VAX-D double precision; I (Tim) don't know of a double
+ format with more precision than that; it's 1 larger so that we add in at
+ least one round bit to stand in for the ignored least-significant bits.
+*/
+#define NBITS_WANTED 57
+ long_p v;
+ double x;
+ const double multiplier = (double)(1L << SHIFT);
+ int i, sign;
+ int nbitsneeded;
+
+ v = (long_p)vv;
+ i = v->size;
+ sign = 1;
+ if (i < 0) {
+ sign = -1;
+ i = -(i);
+ }
+ else if (i == 0) {
+ *exponent = 0;
+ return 0.0;
+ }
+ --i;
+ x = (double)v->digit[i];
+ nbitsneeded = NBITS_WANTED - 1;
+ /* Invariant: i digits remain unaccounted for. */
+ while (i > 0 && nbitsneeded > 0) {
+ --i;
+ x = x * multiplier + (double)v->digit[i];
+ nbitsneeded -= SHIFT;
+ }
+ /* There are i digits we didn't shift in. Pretending they're all
+ zeroes, the true value is x * 2**(i*SHIFT). */
+ *exponent = i;
+ assert(x > 0.0);
+ return x * sign;
+#undef NBITS_WANTED
+}
+
+/* Get a C double from a long int object. */
+
+double PyLong_AsDouble(long_p vv)
+{
+ int e;
+ double x;
+
+ x = _PyLong_AsScaledDouble(vv, &e);
+ //if (x == -1.0 && PyErr_Occurred())
+ // return -1.0;
+ if (e > INT_MAX / SHIFT)
+ goto overflow;
+ errno = 0;
+ x = ldexp(x, e * SHIFT);
+ if (Py_OVERFLOWED(x))
+ goto overflow;
+ return x;
+
+overflow:
+ raise_exception(ist, OBJ(OVERFLOW_EXC),
+ "long int too large to convert to float");
+ return -1.0;
+}
+
+
+#define CONVERT_BINOP(v, w, a, b) *a=v; *b=w;
+
+/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
+ * is modified in place, by adding y to it. Carries are propagated as far as
+ * x[m-1], and the remaining carry (0 or 1) is returned.
+ */
+static digit
+v_iadd(digit *x, int m, digit *y, int n)
+{
+ int i;
+ digit carry = 0;
+
+ assert(m >= n);
+ for (i = 0; i < n; ++i) {
+ carry += x[i] + y[i];
+ x[i] = carry & MASK;
+ carry >>= SHIFT;
+ assert((carry & 1) == carry);
+ }
+ for (; carry && i < m; ++i) {
+ carry += x[i];
+ x[i] = carry & MASK;
+ carry >>= SHIFT;
+ assert((carry & 1) == carry);
+ }
+ return carry;
+}
+
+/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
+ * is modified in place, by subtracting y from it. Borrows are propagated as
+ * far as x[m-1], and the remaining borrow (0 or 1) is returned.
+ */
+static digit
+v_isub(digit *x, int m, digit *y, int n)
+{
+ int i;
+ digit borrow = 0;
+
+ assert(m >= n);
+ for (i = 0; i < n; ++i) {
+ borrow = x[i] - y[i] - borrow;
+ x[i] = borrow & MASK;
+ borrow >>= SHIFT;
+ borrow &= 1; /* keep only 1 sign bit */
+ }
+ for (; borrow && i < m; ++i) {
+ borrow = x[i] - borrow;
+ x[i] = borrow & MASK;
+ borrow >>= SHIFT;
+ borrow &= 1;
+ }
+ return borrow;
+}
+
+/* Multiply by a single digit, ignoring the sign. */
+
+static long_p
+mul1(long_p a, wdigit n)
+{
+ return muladd1(a, n, (digit)0);
+}
+
+/* Multiply by a single digit and add a single digit, ignoring the sign. */
+
+static long_p
+muladd1(long_p a, wdigit n, wdigit extra)
+{
+ int size_a = abs(a->size);
+ long_p z = new_longp_non_init(size_a+1);
+ twodigits carry = extra;
+ int i;
+
+ if (z == NULL)
+ return NULL;
+ for (i = 0; i < size_a; ++i) {
+ carry += (twodigits)a->digit[i] * n;
+ z->digit[i] = (digit) (carry & MASK);
+ carry >>= SHIFT;
+ }
+ z->digit[i] = (digit) carry;
+ return long_normalize(z);
+}
+
+/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
+ in pout, and returning the remainder. pin and pout point at the LSD.
+ It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
+ long_format, but that should be done with great care since longs are
+ immutable. */
+
+static digit
+inplace_divrem1(digit *pout, digit *pin, int size, digit n)
+{
+ twodigits rem = 0;
+
+ assert(n > 0 && n <= MASK);
+ pin += size;
+ pout += size;
+ while (--size >= 0) {
+ digit hi;
+ rem = (rem << SHIFT) + *--pin;
+ *--pout = hi = (digit)(rem / n);
+ rem -= hi * n;
+ }
+ return (digit)rem;
+}
+
+/* Divide a long integer by a digit, returning both the quotient
+ (as function result) and the remainder (through *prem).
+ The sign of a is ignored; n should not be zero. */
+
+static long_p
+divrem1(long_p a, digit n, digit *prem)
+{
+ const int size = abs(a->size);
+ long_p z;
+
+ assert(n > 0 && n <= MASK);
+ z = new_longp_non_init(size);
+ if (z == NULL)
+ return NULL;
+ *prem = inplace_divrem1(z->digit, a->digit, size, n);
+ return long_normalize(z);
+}
+
+/* Convert a long int object to a string, using a given conversion base.
+ Return a string object.
+ If base is 8 or 16, add the proper prefix '0' or '0x'. */
+static obj_p long_format(long_p aa, int base, int addL) {
+ register long_p a = (long_p) aa;
+ obj_p str;
+ int i;
+ const int size_a = abs(a->size);
+ char *p;
+ int bits;
+ char sign = '\0';
+
+ assert(base >= 2 && base <= 36);
+
+ /* Compute a rough upper bound for the length of the string */
+ i = base;
+ bits = 0;
+ while (i > 1) {
+ ++bits;
+ i >>= 1;
+ }
+ i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
+ str = new_string_n_obj(ist, "", i);
+ if (str == NULL)
+ return NULL;
+ p = pr_strptr(str) + i;
+ if (addL)
+ *--p = 'L';
+ if (a->size < 0)
+ sign = '-';
+
+ if (a->size == 0) {
+ *--p = '0';
+ }
+ else if ((base & (base - 1)) == 0) {
+ /* JRH: special case for power-of-2 bases */
+ twodigits accum = 0;
+ int accumbits = 0; /* # of bits in accum */
+ int basebits = 1; /* # of bits in base-1 */
+ i = base;
+ while ((i >>= 1) > 1)
+ ++basebits;
+
+ for (i = 0; i < size_a; ++i) {
+ accum |= (twodigits)a->digit[i] << accumbits;
+ accumbits += SHIFT;
+ assert(accumbits >= basebits);
+ do {
+ char cdigit = (char)(accum & (base - 1));
+ cdigit += (cdigit < 10) ? '0' : 'A'-10;
+ assert(p > PyString_AS_STRING(str));
+ *--p = cdigit;
+ accumbits -= basebits;
+ accum >>= basebits;
+ } while (i < size_a-1 ? accumbits >= basebits :
+ accum > 0);
+ }
+ }
+ else {
+ /* Not 0, and base not a power of 2. Divide repeatedly by
+ base, but for speed use the highest power of base that
+ fits in a digit. */
+ int size = size_a;
+ digit *pin = a->digit;
+ long_p scratch;
+ /* powbasw <- largest power of base that fits in a digit. */
+ digit powbase = base; /* powbase == base ** power */
+ int power = 1;
+ for (;;) {
+ unsigned long newpow = powbase * (unsigned long)base;
+ if (newpow >> SHIFT) /* doesn't fit in a digit */
+ break;
+ powbase = (digit)newpow;
+ ++power;
+ }
+
+ /* Get a scratch area for repeated division. */
+ scratch = new_longp_non_init(size);
+ if (scratch == NULL) {
+ pr_free(str);
+ return NULL;
+ }
+
+ /* Repeatedly divide by powbase. */
+ do {
+ int ntostore = power;
+ digit rem = inplace_divrem1(scratch->digit,
+ pin, size, powbase);
+ pin = scratch->digit; /* no need to use a again */
+ if (pin[size - 1] == 0)
+ --size;
+ SIGCHECK({
+ pr_free(scratch);
+ pr_free(str);
+ return NULL;
+ })
+
+ /* Break rem into digits. */
+ assert(ntostore > 0);
+ do {
+ digit nextrem = (digit)(rem / base);
+ char c = (char)(rem - nextrem * base);
+ assert(p > PyString_AS_STRING(str));
+ c += (c < 10) ? '0' : 'A'-10;
+ *--p = c;
+ rem = nextrem;
+ --ntostore;
+ /* Termination is a bit delicate: must not
+ store leading zeroes, so must get out if
+ remaining quotient and rem are both 0. */
+ } while (ntostore && (size || rem));
+ } while (size != 0);
+ pr_free(scratch);
+ }
+
+ if (base == 8) {
+ if (size_a != 0)
+ *--p = '0';
+ }
+ else if (base == 16) {
+ *--p = 'x';
+ *--p = '0';
+ }
+ else if (base != 10) {
+ *--p = '#';
+ *--p = '0' + base%10;
+ if (base > 10)
+ *--p = '0' + base/10;
+ }
+ if (sign)
+ *--p = sign;
+ if (p != pr_strptr(str)) {
+ char *q = pr_strptr(str);
+ assert(p > q);
+ do {
+ } while ((*q++ = *p++) != '\0');
+ }
+ return NEW_STRING(pr_strptr(str));
+}
+
+/* *str points to the first digit in a string of base base digits. base
+ * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
+ * non-digit (which may be *str!). A normalized long is returned.
+ * The point to this routine is that it takes time linear in the number of
+ * string characters.
+ */
+static long_p long_from_binary_base(char **str, int base) {
+ char *p = *str;
+ char *start = p;
+ int bits_per_char;
+ int n;
+ long_p z;
+ twodigits accum;
+ int bits_in_accum;
+ digit *pdigit;
+
+ assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
+ n = base;
+ for (bits_per_char = -1; n; ++bits_per_char)
+ n >>= 1;
+ /* n <- total # of bits needed, while setting p to end-of-string */
+ n = 0;
+ for (;;) {
+ int k = -1;
+ char ch = *p;
+
+ if (ch <= '9')
+ k = ch - '0';
+ else if (ch >= 'a')
+ k = ch - 'a' + 10;
+ else if (ch >= 'A')
+ k = ch - 'A' + 10;
+ if (k < 0 || k >= base)
+ break;
+ ++p;
+ }
+ *str = p;
+ n = (int) (p - start) * bits_per_char;
+ if (n / bits_per_char != p - start) {
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "long string too large to convert");
+ return NULL;
+ }
+ /* n <- # of digits needed, = ceiling(n/SHIFT). */
+ n = (n + SHIFT - 1) / SHIFT;
+ z = new_longp_non_init(n);
+ if (z == NULL)
+ return NULL;
+ /* Read string from right, and fill in long from left; i.e.,
+ * from least to most significant in both.
+ */
+ accum = 0;
+ bits_in_accum = 0;
+ pdigit = z->digit;
+ while (--p >= start) {
+ int k;
+ char ch = *p;
+
+ if (ch <= '9')
+ k = ch - '0';
+ else if (ch >= 'a')
+ k = ch - 'a' + 10;
+ else {
+ assert(ch >= 'A');
+ k = ch - 'A' + 10;
+ }
+ assert(k >= 0 && k < base);
+ accum |= (twodigits)(k << bits_in_accum);
+ bits_in_accum += bits_per_char;
+ if (bits_in_accum >= SHIFT) {
+ *pdigit++ = (digit)(accum & MASK);
+ assert(pdigit - z->digit <= n);
+ accum >>= SHIFT;
+ bits_in_accum -= SHIFT;
+ assert(bits_in_accum < SHIFT);
+ }
+ }
+ if (bits_in_accum) {
+ assert(bits_in_accum <= SHIFT);
+ *pdigit++ = (digit)accum;
+ assert(pdigit - z->digit <= n);
+ }
+ while (pdigit - z->digit < n)
+ *pdigit++ = 0;
+ return long_normalize(z);
+}
+
+long_p
+PyLong_FromString(char *str, char **pend, int base)
+{
+ int sign = 1;
+ char *start, *orig_str = str;
+ long_p z;
+
+ if ((base != 0 && base < 2) || base > 36) {
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "long() arg 2 must be >= 2 and <= 36");
+ return NULL;
+ }
+ while (*str != '\0' && isspace(Py_CHARMASK(*str)))
+ str++;
+ if (*str == '+')
+ ++str;
+ else if (*str == '-') {
+ ++str;
+ sign = -1;
+ }
+ while (*str != '\0' && isspace(Py_CHARMASK(*str)))
+ str++;
+ if (base == 0) {
+ if (str[0] != '0')
+ base = 10;
+ else if (str[1] == 'x' || str[1] == 'X')
+ base = 16;
+ else
+ base = 8;
+ }
+ if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
+ str += 2;
+ start = str;
+ if ((base & (base - 1)) == 0)
+ z = long_from_binary_base(&str, base);
+ else {
+ z = new_longp_non_init(0);
+ for ( ; z != NULL; ++str) {
+ int k = -1;
+ long_p temp;
+
+ if (*str <= '9')
+ k = *str - '0';
+ else if (*str >= 'a')
+ k = *str - 'a' + 10;
+ else if (*str >= 'A')
+ k = *str - 'A' + 10;
+ if (k < 0 || k >= base)
+ break;
+ temp = muladd1(z, (digit)base, (digit)k);
+ pr_free(z);
+ z = temp;
+ }
+ }
+ if (z == NULL)
+ return NULL;
+ if (str == start)
+ goto onError;
+ if (sign < 0 && z != NULL && z->size != 0)
+ z->size = -(z->size);
+ if (*str == 'L' || *str == 'l')
+ str++;
+ while (*str && isspace(Py_CHARMASK(*str)))
+ str++;
+ if (*str != '\0')
+ goto onError;
+ if (pend)
+ *pend = str;
+ return (long_p) z;
+
+ onError:
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "invalid literal for long(): %.200s", orig_str);
+ Py_XDECREF(z);
+ return NULL;
+}
+
+#ifdef Py_USING_UNICODE
+long_p
+PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
+{
+ long_p result;
+ char *buffer = 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;
+}
+#endif
+
+/* forward */
+static long_p x_divrem
+ (long_p, long_p, long_p *);
+static long_p long_pos(long_p);
+static int long_divrem(long_p, long_p,
+ long_p *, long_p *);
+
+/* Long division with remainder, top-level routine */
+
+static int
+long_divrem(long_p a, long_p b,
+ long_p *pdiv, long_p *prem)
+{
+ int size_a = abs(a->size), size_b = abs(b->size);
+ long_p z;
+
+ if (size_b == 0) {
+ raise_exception(ist, OBJ(DIVIDEZERO_EXC),
+ "long division or modulo by zero");
+ return -1;
+ }
+ if (size_a < size_b ||
+ (size_a == size_b &&
+ a->digit[size_a-1] < b->digit[size_b-1])) {
+ /* |a| < |b|. */
+ *pdiv = new_longp_non_init(0);
+ Py_INCREF(a);
+ *prem = (long_p) a;
+ return 0;
+ }
+ if (size_b == 1) {
+ digit rem = 0;
+ z = divrem1(a, b->digit[0], &rem);
+ if (z == NULL)
+ return -1;
+ *prem = (long_p) new_longp((long)rem);
+ }
+ else {
+ z = x_divrem(a, b, prem);
+ if (z == NULL)
+ return -1;
+ }
+ /* Set the signs.
+ The quotient z has the sign of a*b;
+ the remainder r has the sign of a,
+ so a = b*z + r. */
+ if ((a->size < 0) != (b->size < 0))
+ z->size = -(z->size);
+ if (a->size < 0 && (*prem)->size != 0)
+ (*prem)->size = -((*prem)->size);
+ *pdiv = z;
+ return 0;
+}
+
+/* Unsigned long division with remainder -- the algorithm */
+
+static long_p
+x_divrem(long_p v1, long_p w1, long_p *prem)
+{
+ int size_v = abs(v1->size), size_w = abs(w1->size);
+ digit d = (digit) ((twodigits)BASE / (w1->digit[size_w-1] + 1));
+ long_p v = mul1(v1, d);
+ long_p w = mul1(w1, d);
+ long_p a;
+ int j, k;
+
+ if (v == NULL || w == NULL) {
+ Py_XDECREF(v);
+ Py_XDECREF(w);
+ return NULL;
+ }
+
+ assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
+ assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
+ assert(size_w == abs(w->size)); /* That's how d was calculated */
+
+ size_v = abs(v->size);
+ a = new_longp_non_init(size_v - size_w + 1);
+
+ for (j = size_v, k = a->size-1; a != NULL && k >= 0; --j, --k) {
+ digit vj = (j >= size_v) ? 0 : v->digit[j];
+ twodigits q;
+ stwodigits carry = 0;
+ int i;
+
+ SIGCHECK({
+ pr_free(a);
+ a = NULL;
+ break;
+ })
+ if (vj == w->digit[size_w-1])
+ q = MASK;
+ else
+ q = (((twodigits)vj << SHIFT) + v->digit[j-1]) /
+ w->digit[size_w-1];
+
+ while (w->digit[size_w-2]*q >
+ ((
+ ((twodigits)vj << SHIFT)
+ + v->digit[j-1]
+ - q*w->digit[size_w-1]
+ ) << SHIFT)
+ + v->digit[j-2])
+ --q;
+
+ for (i = 0; i < size_w && i+k < size_v; ++i) {
+ twodigits z = w->digit[i] * q;
+ digit zz = (digit) (z >> SHIFT);
+ carry += v->digit[i+k] - z
+ + ((twodigits)zz << SHIFT);
+ v->digit[i+k] = (digit)(carry & MASK);
+ carry = PR_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
+ carry, SHIFT);
+ carry -= zz;
+ }
+
+ if (i+k < size_v) {
+ carry += v->digit[i+k];
+ v->digit[i+k] = 0;
+ }
+
+ if (carry == 0)
+ a->digit[k] = (digit) q;
+ else {
+ assert(carry == -1);
+ a->digit[k] = (digit) q-1;
+ carry = 0;
+ for (i = 0; i < size_w && i+k < size_v; ++i) {
+ carry += v->digit[i+k] + w->digit[i];
+ v->digit[i+k] = (digit)(carry & MASK);
+ carry = PR_ARITHMETIC_RIGHT_SHIFT(
+ BASE_TWODIGITS_TYPE,
+ carry, SHIFT);
+ }
+ }
+ } /* for j, k */
+
+ if (a == NULL)
+ *prem = NULL;
+ else {
+ a = long_normalize(a);
+ *prem = divrem1(v, d, &d);
+ /* d receives the (unused) remainder */
+ if (*prem == NULL) {
+ pr_free(a);
+ a = NULL;
+ }
+ }
+ pr_free(v);
+ pr_free(w);
+ return a;
+}
+
+/* Methods */
+
+
+static int long_compare(long_p a, long_p b)
+{
+ int sign;
+
+ if (a->size != b->size) {
+ if (abs(a->size) == 0 && abs(b->size) == 0)
+ sign = 0;
+ else
+ sign = a->size - b->size;
+ }
+ else {
+ int i = abs(a->size);
+ while (--i >= 0 && a->digit[i] == b->digit[i])
+ ;
+ if (i < 0)
+ sign = 0;
+ else {
+ sign = (int)a->digit[i] - (int)b->digit[i];
+ if (a->size < 0)
+ sign = -sign;
+ }
+ }
+ return sign < 0 ? -1 : sign > 0 ? 1 : 0;
+}
+
+static long
+long_hash(long_p v)
+{
+ long x;
+ int i, sign;
+
+ /* This is designed so that ints and longs with the
+ same value hash to the same value, otherwise comparisons
+ of mapping keys will turn out weird */
+ i = v->size;
+ sign = 1;
+ x = 0;
+ if (i < 0) {
+ sign = -1;
+ i = -(i);
+ }
+#define LONG_BIT_SHIFT (8*sizeof(long) - SHIFT)
+ while (--i >= 0) {
+ /* Force a native long #-bits (32 or 64) circular shift */
+ x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK);
+ x += v->digit[i];
+ }
+#undef LONG_BIT_SHIFT
+ x = x * sign;
+ if (x == -1)
+ x = -2;
+ return x;
+}
+
+
+/* Add the absolute values of two long integers. */
+
+static long_p
+x_add(long_p a, long_p b)
+{
+ int size_a = abs(a->size), size_b = abs(b->size);
+ long_p z;
+ int i;
+ digit carry = 0;
+
+ /* Ensure a is the larger of the two: */
+ if (size_a < size_b) {
+ { long_p temp = a; a = b; b = temp; }
+ { int size_temp = size_a;
+ size_a = size_b;
+ size_b = size_temp; }
+ }
+ z = new_longp_non_init(size_a+1);
+ if (z == NULL)
+ return NULL;
+ for (i = 0; i < size_b; ++i) {
+ carry += a->digit[i] + b->digit[i];
+ z->digit[i] = carry & MASK;
+ carry >>= SHIFT;
+ }
+ for (; i < size_a; ++i) {
+ carry += a->digit[i];
+ z->digit[i] = carry & MASK;
+ carry >>= SHIFT;
+ }
+ z->digit[i] = carry;
+ return long_normalize(z);
+}
+
+/* Subtract the absolute values of two integers. */
+
+static long_p
+x_sub(long_p a, long_p b)
+{
+ int size_a = abs(a->size), size_b = abs(b->size);
+ long_p z;
+ int i;
+ int sign = 1;
+ digit borrow = 0;
+
+ /* Ensure a is the larger of the two: */
+ if (size_a < size_b) {
+ sign = -1;
+ { long_p temp = a; a = b; b = temp; }
+ { int size_temp = size_a;
+ size_a = size_b;
+ size_b = size_temp; }
+ }
+ else if (size_a == size_b) {
+ /* Find highest digit where a and b differ: */
+ i = size_a;
+ while (--i >= 0 && a->digit[i] == b->digit[i])
+ ;
+ if (i < 0)
+ return new_longp_non_init(0);
+ if (a->digit[i] < b->digit[i]) {
+ sign = -1;
+ { long_p temp = a; a = b; b = temp; }
+ }
+ size_a = size_b = i+1;
+ }
+ z = new_longp_non_init(size_a);
+ if (z == NULL)
+ return NULL;
+ for (i = 0; i < size_b; ++i) {
+ /* The following assumes unsigned arithmetic
+ works module 2**N for some N>SHIFT. */
+ borrow = a->digit[i] - b->digit[i] - borrow;
+ z->digit[i] = borrow & MASK;
+ borrow >>= SHIFT;
+ borrow &= 1; /* Keep only one sign bit */
+ }
+ for (; i < size_a; ++i) {
+ borrow = a->digit[i] - borrow;
+ z->digit[i] = borrow & MASK;
+ borrow >>= SHIFT;
+ borrow &= 1; /* Keep only one sign bit */
+ }
+ assert(borrow == 0);
+ if (sign < 0)
+ z->size = -(z->size);
+ return long_normalize(z);
+}
+
+static long_p
+long_add(long_p v, long_p w)
+{
+ long_p a, b, z;
+
+ CONVERT_BINOP((long_p)v, (long_p)w, &a, &b);
+
+ if (a->size < 0) {
+ if (b->size < 0) {
+ z = x_add(a, b);
+ if (z != NULL && z->size != 0)
+ z->size = -(z->size);
+ }
+ else
+ z = x_sub(b, a);
+ }
+ else {
+ if (b->size < 0)
+ z = x_sub(a, b);
+ else
+ z = x_add(a, b);
+ }
+ pr_free(a);
+ pr_free(b);
+ return (long_p)z;
+}
+
+static long_p
+long_sub(long_p v, long_p w)
+{
+ long_p a, b, z;
+
+ CONVERT_BINOP((long_p)v, (long_p)w, &a, &b);
+
+ if (a->size < 0) {
+ if (b->size < 0)
+ z = x_sub(a, b);
+ else
+ z = x_add(a, b);
+ if (z != NULL && z->size != 0)
+ z->size = -(z->size);
+ }
+ else {
+ if (b->size < 0)
+ z = x_add(a, b);
+ else
+ z = x_sub(a, b);
+ }
+ pr_free(a);
+ pr_free(b);
+ return (long_p)z;
+}
+
+/* Grade school multiplication, ignoring the signs.
+ * Returns the absolute value of the product, or NULL if error.
+ */
+static long_p
+x_mul(long_p a, long_p b)
+{
+ long_p z;
+ int size_a = abs(a->size);
+ int size_b = abs(b->size);
+ int i;
+
+ z = new_longp_non_init(size_a + size_b);
+ if (z == NULL)
+ return NULL;
+
+ memset(z->digit, 0, z->size * sizeof(digit));
+ for (i = 0; i < size_a; ++i) {
+ twodigits carry = 0;
+ twodigits f = a->digit[i];
+ int j;
+ digit *pz = z->digit + i;
+
+ SIGCHECK({
+ pr_free(z);
+ return NULL;
+ })
+ for (j = 0; j < size_b; ++j) {
+ carry += *pz + b->digit[j] * f;
+ *pz++ = (digit) (carry & MASK);
+ carry >>= SHIFT;
+ }
+ for (; carry != 0; ++j) {
+ assert(i+j < z->size);
+ carry += *pz;
+ *pz++ = (digit) (carry & MASK);
+ carry >>= SHIFT;
+ }
+ }
+ return long_normalize(z);
+}
+
+/* A helper for Karatsuba multiplication (k_mul).
+ Takes a long "n" and an integer "size" representing the place to
+ split, and sets low and high such that abs(n) == (high << size) + low,
+ viewing the shift as being by digits. The sign bit is ignored, and
+ the return values are >= 0.
+ Returns 0 on success, -1 on failure.
+*/
+static int
+kmul_split(long_p n, int size, long_p *high, long_p *low)
+{
+ long_p hi, lo;
+ int size_lo, size_hi;
+ const int size_n = abs(n->size);
+
+ size_lo = min(size_n, size);
+ size_hi = size_n - size_lo;
+
+ if ((hi = new_longp_non_init(size_hi)) == NULL)
+ return -1;
+ if ((lo = new_longp_non_init(size_lo)) == NULL) {
+ pr_free(hi);
+ return -1;
+ }
+
+ memcpy(lo->digit, n->digit, size_lo * sizeof(digit));
+ memcpy(hi->digit, n->digit + size_lo, size_hi * sizeof(digit));
+
+ *high = long_normalize(hi);
+ *low = long_normalize(lo);
+ return 0;
+}
+
+static long_p k_lopsided_mul(long_p a, long_p b);
+
+/* Karatsuba multiplication. Ignores the input signs, and returns the
+ * absolute value of the product (or NULL if error).
+ * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
+ */
+static long_p
+k_mul(long_p a, long_p b)
+{
+ int asize = abs(a->size);
+ int bsize = abs(b->size);
+ long_p ah = NULL;
+ long_p al = NULL;
+ long_p bh = NULL;
+ long_p bl = NULL;
+ long_p ret = NULL;
+ long_p t1, t2, t3;
+ int shift; /* the number of digits we split off */
+ int i;
+
+ /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
+ * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl
+ * Then the original product is
+ * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
+ * By picking X to be a power of 2, "*X" is just shifting, and it's
+ * been reduced to 3 multiplies on numbers half the size.
+ */
+
+ /* We want to split based on the larger number; fiddle so that b
+ * is largest.
+ */
+ if (asize > bsize) {
+ t1 = a;
+ a = b;
+ b = t1;
+
+ i = asize;
+ asize = bsize;
+ bsize = i;
+ }
+
+ /* Use gradeschool math when either number is too small. */
+ if (asize <= KARATSUBA_CUTOFF) {
+ if (asize == 0)
+ return new_longp_non_init(0);
+ else
+ return x_mul(a, b);
+ }
+
+ /* If a is small compared to b, splitting on b gives a degenerate
+ * case with ah==0, and Karatsuba may be (even much) less efficient
+ * than "grade school" then. However, we can still win, by viewing
+ * b as a string of "big digits", each of width a->size. That
+ * leads to a sequence of balanced calls to k_mul.
+ */
+ if (2 * asize <= bsize)
+ return k_lopsided_mul(a, b);
+
+ /* Split a & b into hi & lo pieces. */
+ shift = bsize >> 1;
+ if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
+ assert(ah->size > 0); /* the split isn't degenerate */
+
+ if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
+
+ /* The plan:
+ * 1. Allocate result space (asize + bsize digits: that's always
+ * enough).
+ * 2. Compute ah*bh, and copy into result at 2*shift.
+ * 3. Compute al*bl, and copy into result at 0. Note that this
+ * can't overlap with #2.
+ * 4. Subtract al*bl from the result, starting at shift. This may
+ * underflow (borrow out of the high digit), but we don't care:
+ * we're effectively doing unsigned arithmetic mod
+ * BASE**(sizea + sizeb), and so long as the *final* result fits,
+ * borrows and carries out of the high digit can be ignored.
+ * 5. Subtract ah*bh from the result, starting at shift.
+ * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
+ * at shift.
+ */
+
+ /* 1. Allocate result space. */
+ ret = new_longp_non_init(asize + bsize);
+ if (ret == NULL) goto fail;
+#ifdef Py_DEBUG
+ /* Fill with trash, to catch reference to uninitialized digits. */
+ memset(ret->digit, 0xDF, ret->size * sizeof(digit));
+#endif
+
+ /* 2. t1 <- ah*bh, and copy into high digits of result. */
+ if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
+ assert(t1->size >= 0);
+ assert(2*shift + t1->size <= ret->size);
+ memcpy(ret->digit + 2*shift, t1->digit,
+ t1->size * sizeof(digit));
+
+ /* Zero-out the digits higher than the ah*bh copy. */
+ i = ret->size - 2*shift - t1->size;
+ if (i)
+ memset(ret->digit + 2*shift + t1->size, 0,
+ i * sizeof(digit));
+
+ /* 3. t2 <- al*bl, and copy into the low digits. */
+ if ((t2 = k_mul(al, bl)) == NULL) {
+ pr_free(t1);
+ goto fail;
+ }
+ assert(t2->size >= 0);
+ assert(t2->size <= 2*shift); /* no overlap with high digits */
+ memcpy(ret->digit, t2->digit, t2->size * sizeof(digit));
+
+ /* Zero out remaining digits. */
+ i = 2*shift - t2->size; /* number of uninitialized digits */
+ if (i)
+ memset(ret->digit + t2->size, 0, i * sizeof(digit));
+
+ /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first
+ * because it's fresher in cache.
+ */
+ i = ret->size - shift; /* # digits after shift */
+ (void)v_isub(ret->digit + shift, i, t2->digit, t2->size);
+ pr_free(t2);
+
+ (void)v_isub(ret->digit + shift, i, t1->digit, t1->size);
+ pr_free(t1);
+
+ /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
+ if ((t1 = x_add(ah, al)) == NULL) goto fail;
+ pr_free(ah);
+ pr_free(al);
+ ah = al = NULL;
+
+ if ((t2 = x_add(bh, bl)) == NULL) {
+ pr_free(t1);
+ goto fail;
+ }
+ pr_free(bh);
+ pr_free(bl);
+ bh = bl = NULL;
+
+ t3 = k_mul(t1, t2);
+ pr_free(t1);
+ pr_free(t2);
+ if (t3 == NULL) goto fail;
+ assert(t3->size >= 0);
+
+ /* Add t3. It's not obvious why we can't run out of room here.
+ * See the (*) comment after this function.
+ */
+ (void)v_iadd(ret->digit + shift, i, t3->digit, t3->size);
+ pr_free(t3);
+
+ return long_normalize(ret);
+
+ fail:
+ Py_XDECREF(ret);
+ Py_XDECREF(ah);
+ Py_XDECREF(al);
+ Py_XDECREF(bh);
+ Py_XDECREF(bl);
+ return NULL;
+}
+
+/* (*) Why adding t3 can't "run out of room" above.
+
+Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
+to start with:
+
+1. For any integer i, i = c(i/2) + f(i/2). In particular,
+ bsize = c(bsize/2) + f(bsize/2).
+2. shift = f(bsize/2)
+3. asize <= bsize
+4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
+ routine, so asize > bsize/2 >= f(bsize/2) in this routine.
+
+We allocated asize + bsize result digits, and add t3 into them at an offset
+of shift. This leaves asize+bsize-shift allocated digit positions for t3
+to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
+asize + c(bsize/2) available digit positions.
+
+bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
+at most c(bsize/2) digits + 1 bit.
+
+If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
+digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
+most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
+
+The product (ah+al)*(bh+bl) therefore has at most
+
+ c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
+
+and we have asize + c(bsize/2) available digit positions. We need to show
+this is always enough. An instance of c(bsize/2) cancels out in both, so
+the question reduces to whether asize digits is enough to hold
+(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
+then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
+asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
+digit is enough to hold 2 bits. This is so since SHIFT=15 >= 2. If
+asize == bsize, then we're asking whether bsize digits is enough to hold
+c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
+is enough to hold 2 bits. This is so if bsize >= 2, which holds because
+bsize >= KARATSUBA_CUTOFF >= 2.
+
+Note that since there's always enough room for (ah+al)*(bh+bl), and that's
+clearly >= each of ah*bh and al*bl, there's always enough room to subtract
+ah*bh and al*bl too.
+*/
+
+/* b has at least twice the digits of a, and a is big enough that Karatsuba
+ * would pay off *if* the inputs had balanced sizes. View b as a sequence
+ * of slices, each with a->size digits, and multiply the slices by a,
+ * one at a time. This gives k_mul balanced inputs to work with, and is
+ * also cache-friendly (we compute one double-width slice of the result
+ * at a time, then move on, never bactracking except for the helpful
+ * single-width slice overlap between successive partial sums).
+ */
+static long_p
+k_lopsided_mul(long_p a, long_p b)
+{
+ const int asize = abs(a->size);
+ int bsize = abs(b->size);
+ int nbdone; /* # of b digits already multiplied */
+ long_p ret;
+ long_p bslice = NULL;
+
+ assert(asize > KARATSUBA_CUTOFF);
+ assert(2 * asize <= bsize);
+
+ /* Allocate result space, and zero it out. */
+ ret = new_longp_non_init(asize + bsize);
+ if (ret == NULL)
+ return NULL;
+ memset(ret->digit, 0, ret->size * sizeof(digit));
+
+ /* Successive slices of b are copied into bslice. */
+ bslice = new_longp_non_init(asize);
+ if (bslice == NULL)
+ goto fail;
+
+ nbdone = 0;
+ while (bsize > 0) {
+ long_p product;
+ const int nbtouse = min(bsize, asize);
+
+ /* Multiply the next slice of b by a. */
+ memcpy(bslice->digit, b->digit + nbdone,
+ nbtouse * sizeof(digit));
+ bslice->size = nbtouse;
+ product = k_mul(a, bslice);
+ if (product == NULL)
+ goto fail;
+
+ /* Add into result. */
+ (void)v_iadd(ret->digit + nbdone, ret->size - nbdone,
+ product->digit, product->size);
+ pr_free(product);
+
+ bsize -= nbtouse;
+ nbdone += nbtouse;
+ }
+
+ pr_free(bslice);
+ return long_normalize(ret);
+
+ fail:
+ pr_free(ret);
+ Py_XDECREF(bslice);
+ return NULL;
+}
+
+static long_p
+long_mul(long_p v, long_p w)
+{
+ long_p a=v, b=w, z;
+
+ z = k_mul(a, b);
+ /* Negate if exactly one of the inputs is negative. */
+ if (((a->size ^ b->size) < 0) && z)
+ z->size = -(z->size);
+ pr_free(a);
+ pr_free(b);
+ return (long_p)z;
+}
+
+/* The / and % operators are now defined in terms of divmod().
+ The expression a mod b has the value a - b*floor(a/b).
+ The long_divrem function gives the remainder after division of
+ |a| by |b|, with the sign of a. This is also expressed
+ as a - b*trunc(a/b), if trunc truncates towards zero.
+ Some examples:
+ a b a rem b a mod b
+ 13 10 3 3
+ -13 10 -3 7
+ 13 -10 3 -7
+ -13 -10 -3 -3
+ So, to get from rem to mod, we have to add b if a and b
+ have different signs. We then subtract one from the 'div'
+ part of the outcome to keep the invariant intact. */
+
+static int
+l_divmod(long_p v, long_p w,
+ long_p *pdiv, long_p *pmod)
+{
+ long_p div, mod;
+
+ if (long_divrem(v, w, &div, &mod) < 0)
+ return -1;
+ if ((mod->size < 0 && w->size > 0) ||
+ (mod->size > 0 && w->size < 0)) {
+ long_p temp;
+ long_p one;
+ temp = (long_p) long_add(mod, w);
+ pr_free(mod);
+ mod = temp;
+ if (mod == NULL) {
+ pr_free(div);
+ return -1;
+ }
+ one = (long_p) new_longp(1L);
+ if (one == NULL ||
+ (temp = (long_p) long_sub(div, one)) == NULL) {
+ pr_free(mod);
+ pr_free(div);
+ Py_XDECREF(one);
+ return -1;
+ }
+ pr_free(one);
+ pr_free(div);
+ div = temp;
+ }
+ *pdiv = div;
+ *pmod = mod;
+ return 0;
+}
+
+static long_p
+long_div(long_p v, long_p w)
+{
+ long_p a, b, div, mod;
+
+ CONVERT_BINOP(v, w, &a, &b);
+
+ if (l_divmod(a, b, &div, &mod) < 0) {
+ pr_free(a);
+ pr_free(b);
+ return NULL;
+ }
+ pr_free(a);
+ pr_free(b);
+ pr_free(mod);
+ return (long_p)div;
+}
+
+static long_p
+long_classic_div(long_p v, long_p w)
+{
+ long_p a, b, div, mod;
+
+ CONVERT_BINOP(v, w, &a, &b);
+
+ if (l_divmod(a, b, &div, &mod) < 0)
+ div = NULL;
+ else
+ pr_free(mod);
+
+ pr_free(a);
+ pr_free(b);
+ return (long_p) div;
+}
+
+static double long_true_divide(long_p v, long_p w)
+{
+ long_p a, b;
+ double ad, bd;
+ int aexp, bexp;
+
+ CONVERT_BINOP(v, w, &a, &b);
+ ad = _PyLong_AsScaledDouble((long_p)a, &aexp);
+ bd = _PyLong_AsScaledDouble((long_p)b, &bexp);
+ pr_free(a);
+ pr_free(b);
+
+ if (bd == 0.0) {
+ raise_exception(ist, OBJ(DIVIDEZERO_EXC),
+ "long division or modulo by zero");
+ return 0.0;
+ }
+
+ /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */
+ ad /= bd; /* overflow/underflow impossible here */
+ aexp -= bexp;
+ if (aexp > INT_MAX / SHIFT)
+ goto overflow;
+ else if (aexp < -(INT_MAX / SHIFT))
+ return 0.0; /* underflow to 0 */
+ errno = 0;
+ ad = ldexp(ad, aexp * SHIFT);
+ if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
+ goto overflow;
+ return ad;
+
+overflow:
+ raise_exception(ist, OBJ(OVERFLOW_EXC),
+ "integer too large for a float");
+ return 0.0;
+
+}
+
+static long_p
+long_mod(long_p v, long_p w)
+{
+ long_p a, b, div, mod;
+
+ CONVERT_BINOP(v, w, &a, &b);
+
+ if (l_divmod(a, b, &div, &mod) < 0) {
+ pr_free(a);
+ pr_free(b);
+ return NULL;
+ }
+ pr_free(a);
+ pr_free(b);
+ pr_free(div);
+ return (long_p)mod;
+}
+
+// w must be positive
+// handle negative using floats without calling this
+static long_p long_pow(long_p v, long_p w, long_p x)
+{
+ long_p a, b;
+ long_p c;
+ long_p z, div, mod;
+ int size_b, i;
+
+ CONVERT_BINOP(v, w, &a, &b);
+ c = x;
+ if (c && ((long_p)c)->size == 0) {
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "pow() 3rd argument cannot be 0");
+ z = NULL;
+ goto error;
+ }
+ size_b = b->size;
+ z = (long_p)new_longp(1);
+ for (i = 0; i < size_b; ++i) {
+ digit bi = b->digit[i];
+ int j;
+
+ for (j = 0; j < SHIFT; ++j) {
+ long_p temp;
+
+ if (bi & 1) {
+ temp = (long_p)long_mul(z, a);
+ pr_free(z);
+ if (c && temp!=NULL) {
+ if (l_divmod(temp,(long_p)c,
+ &div,&mod) < 0) {
+ pr_free(temp);
+ z = NULL;
+ goto error;
+ }
+ Py_XDECREF(div);
+ pr_free(temp);
+ temp = mod;
+ }
+ z = temp;
+ if (z == NULL)
+ break;
+ }
+ bi >>= 1;
+ if (bi == 0 && i+1 == size_b)
+ break;
+ temp = (long_p)long_mul(a, a);
+ pr_free(a);
+ if (c && temp!=NULL) {
+ if (l_divmod(temp, (long_p)c, &div,
+ &mod) < 0) {
+ pr_free(temp);
+ z = NULL;
+ goto error;
+ }
+ Py_XDECREF(div);
+ pr_free(temp);
+ temp = mod;
+ }
+ a = temp;
+ if (a == NULL) {
+ pr_free(z);
+ z = NULL;
+ break;
+ }
+ }
+ if (a == NULL || z == NULL)
+ break;
+ }
+ if (c && z!=NULL) {
+ if (l_divmod(z, (long_p)c, &div, &mod) < 0) {
+ pr_free(z);
+ z = NULL;
+ }
+ else {
+ Py_XDECREF(div);
+ pr_free(z);
+ z = mod;
+ }
+ }
+ error:
+ Py_XDECREF(a);
+ pr_free(b);
+ pr_free(c);
+ return (long_p)z;
+}
+
+static long_p
+long_invert(long_p v)
+{
+ /* Implement ~x as -(x+1) */
+ long_p x;
+ long_p w;
+ w = (long_p)new_longp(1L);
+ if (w == NULL)
+ return NULL;
+ x = (long_p) long_add(v, w);
+ pr_free(w);
+ if (x == NULL)
+ return NULL;
+ x->size = -(x->size);
+ return (long_p)x;
+}
+
+static long_p long_rshift(long_p v, long_p w) {
+ long_p a, b;
+ long_p z = NULL;
+ i64_t shiftby, newsize, wordshift, loshift, hishift;
+ int i, j;
+ digit lomask, himask;
+
+ CONVERT_BINOP((long_p)v, (long_p)w, &a, &b);
+
+ if (a->size < 0) {
+ /* Right shifting negative numbers is harder */
+ long_p a1, a2;
+ a1 = (long_p) long_invert(a);
+ if (a1 == NULL)
+ goto rshift_error;
+ a2 = (long_p) long_rshift(a1, b);
+ pr_free(a1);
+ if (a2 == NULL)
+ goto rshift_error;
+ z = (long_p) long_invert(a2);
+ pr_free(a2);
+ }
+ else {
+
+ shiftby = longp2int64((long_p)b);
+ if (shiftby < 0) {
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "negative shift count");
+ goto rshift_error;
+ }
+ wordshift = shiftby / SHIFT;
+ newsize = abs(a->size) - wordshift;
+ if (newsize <= 0) {
+ z = new_longp_non_init(0);
+ pr_free(a);
+ pr_free(b);
+ return (long_p)z;
+ }
+ loshift = shiftby % SHIFT;
+ hishift = SHIFT - loshift;
+ lomask = ((digit)1 << hishift) - 1;
+ himask = MASK ^ lomask;
+ z = new_longp_non_init((int)newsize);
+ if (z == NULL)
+ goto rshift_error;
+ if (a->size < 0)
+ z->size = -(z->size);
+ for (i = 0, j = (int) wordshift; i < newsize; i++, j++) {
+ z->digit[i] = (a->digit[j] >> loshift) & lomask;
+ if (i+1 < newsize)
+ z->digit[i] |=
+ (a->digit[j+1] << hishift) & himask;
+ }
+ z = long_normalize(z);
+ }
+rshift_error:
+ pr_free(a);
+ pr_free(b);
+ return (long_p) z;
+
+}
+
+static long_p
+long_lshift(long_p v, long_p w)
+{
+ /* This version due to Tim Peters */
+ long_p a, b;
+ long_p z = NULL;
+ i64_t shiftby;
+ int oldsize, newsize, wordshift, remshift, i, j;
+ twodigits accum;
+
+ CONVERT_BINOP(v, w, &a, &b);
+
+ shiftby = longp2int64((long_p)b);
+ if (shiftby < 0) {
+ raise_exception(ist, OBJ(VALUE_EXC), "negative shift count");
+ goto lshift_error;
+ }
+ if ((long)(int)shiftby != shiftby) {
+ raise_exception(ist, OBJ(VALUE_EXC),
+ "outrageous left shift count");
+ goto lshift_error;
+ }
+ /* wordshift, remshift = divmod(shiftby, SHIFT) */
+ wordshift = (int)shiftby / SHIFT;
+ remshift = (int)shiftby - wordshift * SHIFT;
+
+ oldsize = abs(a->size);
+ newsize = oldsize + wordshift;
+ if (remshift)
+ ++newsize;
+ z = new_longp_non_init(newsize);
+ if (z == NULL)
+ goto lshift_error;
+ if (a->size < 0)
+ z->size = -(z->size);
+ for (i = 0; i < wordshift; i++)
+ z->digit[i] = 0;
+ accum = 0;
+ for (i = wordshift, j = 0; j < oldsize; i++, j++) {
+ accum |= (twodigits)a->digit[j] << remshift;
+ z->digit[i] = (digit)(accum & MASK);
+ accum >>= SHIFT;
+ }
+ if (remshift)
+ z->digit[newsize-1] = (digit)accum;
+ else
+ assert(!accum);
+ z = long_normalize(z);
+lshift_error:
+ pr_free(a);
+ pr_free(b);
+ return (long_p) z;
+}
+
+
+/* Bitwise and/xor/or operations */
+
+static long_p
+long_bitwise(long_p a,
+ int op, /* '&', '|', '^' */
+ long_p b)
+{
+ digit maska, maskb; /* 0 or MASK */
+ int negz;
+ int size_a, size_b, size_z;
+ long_p z;
+ int i;
+ digit diga, digb;
+ long_p v;
+
+ if (a->size < 0) {
+ a = (long_p) long_invert(a);
+ maska = MASK;
+ }
+ else {
+ Py_INCREF(a);
+ maska = 0;
+ }
+ if (b->size < 0) {
+ b = (long_p) long_invert(b);
+ maskb = MASK;
+ }
+ else {
+ Py_INCREF(b);
+ maskb = 0;
+ }
+
+ negz = 0;
+ switch (op) {
+ case '^':
+ if (maska != maskb) {
+ maska ^= MASK;
+ negz = -1;
+ }
+ break;
+ case '&':
+ if (maska && maskb) {
+ op = '|';
+ maska ^= MASK;
+ maskb ^= MASK;
+ negz = -1;
+ }
+ break;
+ case '|':
+ if (maska || maskb) {
+ op = '&';
+ maska ^= MASK;
+ maskb ^= MASK;
+ negz = -1;
+ }
+ break;
+ }
+
+ /* JRH: The original logic here was to allocate the result value (z)
+ as the longer of the two operands. However, there are some cases
+ where the result is guaranteed to be shorter than that: AND of two
+ positives, OR of two negatives: use the shorter number. AND with
+ mixed signs: use the positive number. OR with mixed signs: use the
+ negative number. After the transformations above, op will be '&'
+ iff one of these cases applies, and mask will be non-0 for operands
+ whose length should be ignored.
+ */
+
+ size_a = a->size;
+ size_b = b->size;
+ size_z = op == '&'
+ ? (maska
+ ? size_b
+ : (maskb ? size_a : min(size_a, size_b)))
+ : max(size_a, size_b);
+ z = new_longp_non_init(size_z);
+ if (a == NULL || b == NULL || z == NULL) {
+ Py_XDECREF(a);
+ Py_XDECREF(b);
+ Py_XDECREF(z);
+ return NULL;
+ }
+
+ for (i = 0; i < size_z; ++i) {
+ diga = (i < size_a ? a->digit[i] : 0) ^ maska;
+ digb = (i < size_b ? b->digit[i] : 0) ^ maskb;
+ switch (op) {
+ case '&': z->digit[i] = diga & digb; break;
+ case '|': z->digit[i] = diga | digb; break;
+ case '^': z->digit[i] = diga ^ digb; break;
+ }
+ }
+
+ pr_free(a);
+ pr_free(b);
+ z = long_normalize(z);
+ if (negz == 0)
+ return (long_p) z;
+ v = long_invert(z);
+ pr_free(z);
+ return v;
+}
+
+static long_p
+long_and(long_p v, long_p w)
+{
+ long_p a, b;
+ long_p c;
+ CONVERT_BINOP(v, w, &a, &b);
+ c = long_bitwise(a, '&', b);
+ pr_free(a);
+ pr_free(b);
+ return c;
+}
+
+static long_p
+long_xor(long_p v, long_p w)
+{
+ long_p a, b;
+ long_p c;
+ CONVERT_BINOP(v, w, &a, &b);
+ c = long_bitwise(a, '^', b);
+ pr_free(a);
+ pr_free(b);
+ return c;
+}
+
+static long_p
+long_or(long_p v, long_p w)
+{
+ long_p a, b;
+ long_p c;
+ CONVERT_BINOP(v, w, &a, &b);
+ c = long_bitwise(a, '|', b);
+ pr_free(a);
+ pr_free(b);
+ return c;
+}
+
+
+// ***************************** INT MODULE ***********************************
+
#define INT_DATA_SIZE 8
#define is_Int(objid) (has_proto(ist, objid, Int_OBJ))
#define Int_value(objid) (objid->data.i64)
@@ -93,9 +2065,9 @@
set_attr(ist, OBJ(OBJECT), sym(ist, "Int"), Int_OBJ);
MODULE_SET_DOC(Int, "integer object prototype");
set_obj_id(Int_OBJ, *, Int);
- Int_OBJ->data_type = DATA_TYPE_IMMDATA;
+ Int_OBJ->data_type = DATA_TYPE_IMMDATA;
Int_OBJ->imm_data_len = IMMEDIATE_DATA_LEN;
- Int_OBJ->data.i64 = 0;
+ Int_OBJ->data.i64 = 0;
/* Dependent objects */
OBJ(ZERO_INT) = NEW_INT(0);
@@ -115,7 +2087,7 @@
INT_64_PARAM(0,i);
SET_TYPE_IF_EXC(Int_OBJ, self, DATA_TYPE_IMMDATA) return NULL;
self->imm_data_len = IMMEDIATE_DATA_LEN;
- self->data.i64 = i;
+ self->data.i64 = i;
return OBJ(NONE);
}
@@ -176,10 +2148,10 @@
raise_exception(ist, OBJ(TYPE_EXC), "Integer cannot be divided by this object");
return OBJ(NONE);
}
- float_self = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), self); if_exc_return NULL;
+ float_self = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), self); if_exc_return NULL;
float_other = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), other); if_exc_return NULL;
res = call_func1(ist, float_self, SYM(DIV_), float_other);
- del_unlock(float_self); del_unlock(float_other);
+ del_unlock(float_self); del_unlock(float_other);
return res;
}
@@ -243,7 +2215,7 @@
obj_p res;
obj_p float_self, float_other, other = parms[1];
BIN_CONTENT_CHK(Int);
- float_self = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), self); if_exc_return NULL;
+ float_self = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), self); if_exc_return NULL;
float_other = call_func1(ist, OBJ(FLOAT_PROTO), SYM(COERCE_), other); if_exc_return NULL;
res = call_func1(ist, float_self, SYM(POW_), float_other);
del_unlock(float_self); del_unlock(float_other);
@@ -278,7 +2250,7 @@
return OBJ(PR_FALSE);
}
if (Int_value(self) == Int_value(other)) return OBJ(PR_TRUE);
- else return OBJ(PR_FALSE);
+ else return OBJ(PR_FALSE);
}
DEF(Int, invert_, NULL){
BIN_CONTENT_CHK(Int);
@@ -363,7 +2335,7 @@
obj_p limit, res;
BIN_CONTENT_CHK(IntGen);
if ( !(limit=get_attr(ist, self, SYM_LIMIT)) ||
- Int_value(self) == Int_value(limit) ) {
+ Int_value(self) == Int_value(limit) ) {
if (limit) {
read_unlock(ist, self);
del_attr(ist, self, SYM_LIMIT);
Modified: trunk/src/src.vcproj
===================================================================
--- trunk/src/src.vcproj 2004-05-28 00:09:58 UTC (rev 559)
+++ trunk/src/src.vcproj 2004-05-28 05:50:02 UTC (rev 560)
@@ -137,9 +137,6 @@
RelativePath=".\builtins-attrdict.c">
</File>
<File
- RelativePath=".\builtins-bigint.c">
- </File>
- <File
RelativePath=".\builtins-core.c">
</File>
<File