Objects/longobject.c

   1
   2 /* Long (arbitrary precision) integer object implementation */
   3
   4 /* XXX The functional organization of this file is terrible */
   5
   6 #include "Python.h"
   7 #include "longintrepr.h"
   8
   9 #include <ctype.h>
  10
  11 /* For long multiplication, use the O(N**2) school algorithm unless
  12  * both operands contain more than KARATSUBA_CUTOFF digits (this
  13  * being an internal Python long digit, in base BASE).
  14  */
  15 #define KARATSUBA_CUTOFF 35
  16
  17 #define ABS(x) ((x) < 0 ? -(x) : (x))
  18
  19 #undef MIN
  20 #undef MAX
  21 #define MAX(x, y) ((x) < (y) ? (y) : (x))
  22 #define MIN(x, y) ((x) > (y) ? (y) : (x))
  23
  24 /* Forward */
  25 static PyLongObject *long_normalize(PyLongObject *);
  26 static PyLongObject *mul1(PyLongObject *, wdigit);
  27 static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
  28 static PyLongObject *divrem1(PyLongObject *, digit, digit *);
  29 static PyObject *long_format(PyObject *aa, int base, int addL);
  30
  31 #define SIGCHECK(PyTryBlock) \
  32         if (--_Py_Ticker < 0) { \
  33                 _Py_Ticker = _Py_CheckInterval; \
  34                 if (PyErr_CheckSignals()) { PyTryBlock; } \
  35         }
  36
  37 /* Normalize (remove leading zeros from) a long int object.
  38    Doesn't attempt to free the storage--in most cases, due to the nature
  39    of the algorithms used, this could save at most be one word anyway. */
  40
  41 static PyLongObject *
  42 long_normalize(register PyLongObject *v)
  43 {
  44         int j = ABS(v->ob_size);
  45         register int i = j;
  46
  47         while (i > 0 && v->ob_digit[i-1] == 0)
  48                 --i;
  49         if (i != j)
  50                 v->ob_size = (v->ob_size < 0) ? -(i) : i;
  51         return v;
  52 }
  53
  54 /* Allocate a new long int object with size digits.
  55    Return NULL and set exception if we run out of memory. */
  56
  57 PyLongObject *
  58 _PyLong_New(int size)
  59 {
  60         return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
  61 }
  62
  63 PyObject *
  64 _PyLong_Copy(PyLongObject *src)
  65 {
  66         PyLongObject *result;
  67         int i;
  68
  69         assert(src != NULL);
  70         i = src->ob_size;
  71         if (i < 0)
  72                 i = -(i);
  73         result = _PyLong_New(i);
  74         if (result != NULL) {
  75                 result->ob_size = src->ob_size;
  76                 while (--i >= 0)
  77                         result->ob_digit[i] = src->ob_digit[i];
  78         }
  79         return (PyObject *)result;
  80 }
  81
  82 /* Create a new long int object from a C long int */
  83
  84 PyObject *
  85 PyLong_FromLong(long ival)
  86 {
  87         PyLongObject *v;
  88         unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
  89         int ndigits = 0;
  90         int negative = 0;
  91
  92         if (ival < 0) {
  93                 ival = -ival;
  94                 negative = 1;
  95         }
  96
  97         /* Count the number of Python digits.
  98            We used to pick 5 ("big enough for anything"), but that's a
  99            waste of time and space given that 5*15 = 75 bits are rarely
 100            needed. */
 101         t = (unsigned long)ival;
 102         while (t) {
 103                 ++ndigits;
 104                 t >>= SHIFT;
 105         }
 106         v = _PyLong_New(ndigits);
 107         if (v != NULL) {
 108                 digit *p = v->ob_digit;
 109                 v->ob_size = negative ? -ndigits : ndigits;
 110                 t = (unsigned long)ival;
 111                 while (t) {
 112                         *p++ = (digit)(t & MASK);
 113                         t >>= SHIFT;
 114                 }
 115         }
 116         return (PyObject *)v;
 117 }
 118
 119 /* Create a new long int object from a C unsigned long int */
 120
 121 PyObject *
 122 PyLong_FromUnsignedLong(unsigned long ival)
 123 {
 124         PyLongObject *v;
 125         unsigned long t;
 126         int ndigits = 0;
 127
 128         /* Count the number of Python digits. */
 129         t = (unsigned long)ival;
 130         while (t) {
 131                 ++ndigits;
 132                 t >>= SHIFT;
 133         }
 134         v = _PyLong_New(ndigits);
 135         if (v != NULL) {
 136                 digit *p = v->ob_digit;
 137                 v->ob_size = ndigits;
 138                 while (ival) {
 139                         *p++ = (digit)(ival & MASK);
 140                         ival >>= SHIFT;
 141                 }
 142         }
 143         return (PyObject *)v;
 144 }
 145
 146 /* Create a new long int object from a C double */
 147
 148 PyObject *
 149 PyLong_FromDouble(double dval)
 150 {
 151         PyLongObject *v;
 152         double frac;
 153         int i, ndig, expo, neg;
 154         neg = 0;
 155         if (Py_IS_INFINITY(dval)) {
 156                 PyErr_SetString(PyExc_OverflowError,
 157                         "cannot convert float infinity to long");
 158                 return NULL;
 159         }
 160         if (dval < 0.0) {
 161                 neg = 1;
 162                 dval = -dval;
 163         }
 164         frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
 165         if (expo <= 0)
 166                 return PyLong_FromLong(0L);
 167         ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
 168         v = _PyLong_New(ndig);
 169         if (v == NULL)
 170                 return NULL;
 171         frac = ldexp(frac, (expo-1) % SHIFT + 1);
 172         for (i = ndig; --i >= 0; ) {
 173                 long bits = (long)frac;
 174                 v->ob_digit[i] = (digit) bits;
 175                 frac = frac - (double)bits;
 176                 frac = ldexp(frac, SHIFT);
 177         }
 178         if (neg)
 179                 v->ob_size = -(v->ob_size);
 180         return (PyObject *)v;
 181 }
 182
 183 /* Get a C long int from a long int object.
 184    Returns -1 and sets an error condition if overflow occurs. */
 185
 186 long
 187 PyLong_AsLong(PyObject *vv)
 188 {
 189         /* This version by Tim Peters */
 190         register PyLongObject *v;
 191         unsigned long x, prev;
 192         int i, sign;
 193
 194         if (vv == NULL || !PyLong_Check(vv)) {
 195                 if (vv != NULL && PyInt_Check(vv))
 196                         return PyInt_AsLong(vv);
 197                 PyErr_BadInternalCall();
 198                 return -1;
 199         }
 200         v = (PyLongObject *)vv;
 201         i = v->ob_size;
 202         sign = 1;
 203         x = 0;
 204         if (i < 0) {
 205                 sign = -1;
 206                 i = -(i);
 207         }
 208         while (--i >= 0) {
 209                 prev = x;
 210                 x = (x << SHIFT) + v->ob_digit[i];
 211                 if ((x >> SHIFT) != prev)
 212                         goto overflow;
 213         }
 214         /* Haven't lost any bits, but if the sign bit is set we're in
 215          * trouble *unless* this is the min negative number.  So,
 216          * trouble iff sign bit set && (positive || some bit set other
 217          * than the sign bit).
 218          */
 219         if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
 220                 goto overflow;
 221         return (long)x * sign;
 222
 223  overflow:
 224         PyErr_SetString(PyExc_OverflowError,
 225                         "long int too large to convert to int");
 226         return -1;
 227 }
 228
 229 /* Get a C unsigned long int from a long int object.
 230    Returns -1 and sets an error condition if overflow occurs. */
 231
 232 unsigned long
 233 PyLong_AsUnsignedLong(PyObject *vv)
 234 {
 235         register PyLongObject *v;
 236         unsigned long x, prev;
 237         int i;
 238
 239         if (vv == NULL || !PyLong_Check(vv)) {
 240                 PyErr_BadInternalCall();
 241                 return (unsigned long) -1;
 242         }
 243         v = (PyLongObject *)vv;
 244         i = v->ob_size;
 245         x = 0;
 246         if (i < 0) {
 247                 PyErr_SetString(PyExc_OverflowError,
 248                            "can't convert negative value to unsigned long");
 249                 return (unsigned long) -1;
 250         }
 251         while (--i >= 0) {
 252                 prev = x;
 253                 x = (x << SHIFT) + v->ob_digit[i];
 254                 if ((x >> SHIFT) != prev) {
 255                         PyErr_SetString(PyExc_OverflowError,
 256                                 "long int too large to convert");
 257                         return (unsigned long) -1;
 258                 }
 259         }
 260         return x;
 261 }
 262
 263 PyObject *
 264 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
 265                       int little_endian, int is_signed)
 266 {
 267         const unsigned char* pstartbyte;/* LSB of bytes */
 268         int incr;                       /* direction to move pstartbyte */
 269         const unsigned char* pendbyte;  /* MSB of bytes */
 270         size_t numsignificantbytes;     /* number of bytes that matter */
 271         size_t ndigits;                 /* number of Python long digits */
 272         PyLongObject* v;                /* result */
 273         int idigit = 0;                 /* next free index in v->ob_digit */
 274
 275         if (n == 0)
 276                 return PyLong_FromLong(0L);
 277
 278         if (little_endian) {
 279                 pstartbyte = bytes;
 280                 pendbyte = bytes + n - 1;
 281                 incr = 1;
 282         }
 283         else {
 284                 pstartbyte = bytes + n - 1;
 285                 pendbyte = bytes;
 286                 incr = -1;
 287         }
 288
 289         if (is_signed)
 290                 is_signed = *pendbyte >= 0x80;
 291
 292         /* Compute numsignificantbytes.  This consists of finding the most
 293            significant byte.  Leading 0 bytes are insignficant if the number
 294            is positive, and leading 0xff bytes if negative. */
 295         {
 296                 size_t i;
 297                 const unsigned char* p = pendbyte;
 298                 const int pincr = -incr;  /* search MSB to LSB */
 299                 const unsigned char insignficant = is_signed ? 0xff : 0x00;
 300
 301                 for (i = 0; i < n; ++i, p += pincr) {
 302                         if (*p != insignficant)
 303                                 break;
 304                 }
 305                 numsignificantbytes = n - i;
 306                 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
 307                    actually has 2 significant bytes.  OTOH, 0xff0001 ==
 308                    -0x00ffff, so we wouldn't *need* to bump it there; but we
 309                    do for 0xffff = -0x0001.  To be safe without bothering to
 310                    check every case, bump it regardless. */
 311                 if (is_signed && numsignificantbytes < n)
 312                         ++numsignificantbytes;
 313         }
 314
 315         /* How many Python long digits do we need?  We have
 316            8*numsignificantbytes bits, and each Python long digit has SHIFT
 317            bits, so it's the ceiling of the quotient. */
 318         ndigits = (numsignificantbytes * 8 + SHIFT - 1) / SHIFT;
 319         if (ndigits > (size_t)INT_MAX)
 320                 return PyErr_NoMemory();
 321         v = _PyLong_New((int)ndigits);
 322         if (v == NULL)
 323                 return NULL;
 324
 325         /* Copy the bits over.  The tricky parts are computing 2's-comp on
 326            the fly for signed numbers, and dealing with the mismatch between
 327            8-bit bytes and (probably) 15-bit Python digits.*/
 328         {
 329                 size_t i;
 330                 twodigits carry = 1;            /* for 2's-comp calculation */
 331                 twodigits accum = 0;            /* sliding register */
 332                 unsigned int accumbits = 0;     /* number of bits in accum */
 333                 const unsigned char* p = pstartbyte;
 334
 335                 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
 336                         twodigits thisbyte = *p;
 337                         /* Compute correction for 2's comp, if needed. */
 338                         if (is_signed) {
 339                                 thisbyte = (0xff ^ thisbyte) + carry;
 340                                 carry = thisbyte >> 8;
 341                                 thisbyte &= 0xff;
 342                         }
 343                         /* Because we're going LSB to MSB, thisbyte is
 344                            more significant than what's already in accum,
 345                            so needs to be prepended to accum. */
 346                         accum |= thisbyte << accumbits;
 347                         accumbits += 8;
 348                         if (accumbits >= SHIFT) {
 349                                 /* There's enough to fill a Python digit. */
 350                                 assert(idigit < (int)ndigits);
 351                                 v->ob_digit[idigit] = (digit)(accum & MASK);
 352                                 ++idigit;
 353                                 accum >>= SHIFT;
 354                                 accumbits -= SHIFT;
 355                                 assert(accumbits < SHIFT);
 356                         }
 357                 }
 358                 assert(accumbits < SHIFT);
 359                 if (accumbits) {
 360                         assert(idigit < (int)ndigits);
 361                         v->ob_digit[idigit] = (digit)accum;
 362                         ++idigit;
 363                 }
 364         }
 365
 366         v->ob_size = is_signed ? -idigit : idigit;
 367         return (PyObject *)long_normalize(v);
 368 }
 369
 370 int
 371 _PyLong_AsByteArray(PyLongObject* v,
 372                     unsigned char* bytes, size_t n,
 373                     int little_endian, int is_signed)
 374 {
 375         int i;                  /* index into v->ob_digit */
 376         int ndigits;            /* |v->ob_size| */
 377         twodigits accum;        /* sliding register */
 378         unsigned int accumbits; /* # bits in accum */
 379         int do_twos_comp;       /* store 2's-comp?  is_signed and v < 0 */
 380         twodigits carry;        /* for computing 2's-comp */
 381         size_t j;               /* # bytes filled */
 382         unsigned char* p;       /* pointer to next byte in bytes */
 383         int pincr;              /* direction to move p */
 384
 385         assert(v != NULL && PyLong_Check(v));
 386
 387         if (v->ob_size < 0) {
 388                 ndigits = -(v->ob_size);
 389                 if (!is_signed) {
 390                         PyErr_SetString(PyExc_TypeError,
 391                                 "can't convert negative long to unsigned");
 392                         return -1;
 393                 }
 394                 do_twos_comp = 1;
 395         }
 396         else {
 397                 ndigits = v->ob_size;
 398                 do_twos_comp = 0;
 399         }
 400
 401         if (little_endian) {
 402                 p = bytes;
 403                 pincr = 1;
 404         }
 405         else {
 406                 p = bytes + n - 1;
 407                 pincr = -1;
 408         }
 409
 410         /* Copy over all the Python digits.
 411            It's crucial that every Python digit except for the MSD contribute
 412            exactly SHIFT bits to the total, so first assert that the long is
 413            normalized. */
 414         assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
 415         j = 0;
 416         accum = 0;
 417         accumbits = 0;
 418         carry = do_twos_comp ? 1 : 0;
 419         for (i = 0; i < ndigits; ++i) {
 420                 twodigits thisdigit = v->ob_digit[i];
 421                 if (do_twos_comp) {
 422                         thisdigit = (thisdigit ^ MASK) + carry;
 423                         carry = thisdigit >> SHIFT;
 424                         thisdigit &= MASK;
 425                 }
 426                 /* Because we're going LSB to MSB, thisdigit is more
 427                    significant than what's already in accum, so needs to be
 428                    prepended to accum. */
 429                 accum |= thisdigit << accumbits;
 430                 accumbits += SHIFT;
 431
 432                 /* The most-significant digit may be (probably is) at least
 433                    partly empty. */
 434                 if (i == ndigits - 1) {
 435                         /* Count # of sign bits -- they needn't be stored,
 436                          * although for signed conversion we need later to
 437                          * make sure at least one sign bit gets stored.
 438                          * First shift conceptual sign bit to real sign bit.
 439                          */
 440                         stwodigits s = (stwodigits)(thisdigit <<
 441                                 (8*sizeof(stwodigits) - SHIFT));
 442                         unsigned int nsignbits = 0;
 443                         while ((s < 0) == do_twos_comp && nsignbits < SHIFT) {
 444                                 ++nsignbits;
 445                                 s <<= 1;
 446                         }
 447                         accumbits -= nsignbits;
 448                 }
 449
 450                 /* Store as many bytes as possible. */
 451                 while (accumbits >= 8) {
 452                         if (j >= n)
 453                                 goto Overflow;
 454                         ++j;
 455                         *p = (unsigned char)(accum & 0xff);
 456                         p += pincr;
 457                         accumbits -= 8;
 458                         accum >>= 8;
 459                 }
 460         }
 461
 462         /* Store the straggler (if any). */
 463         assert(accumbits < 8);
 464         assert(carry == 0);  /* else do_twos_comp and *every* digit was 0 */
 465         if (accumbits > 0) {
 466                 if (j >= n)
 467                         goto Overflow;
 468                 ++j;
 469                 if (do_twos_comp) {
 470                         /* Fill leading bits of the byte with sign bits
 471                            (appropriately pretending that the long had an
 472                            infinite supply of sign bits). */
 473                         accum |= (~(twodigits)0) << accumbits;
 474                 }
 475                 *p = (unsigned char)(accum & 0xff);
 476                 p += pincr;
 477         }
 478         else if (j == n && n > 0 && is_signed) {
 479                 /* The main loop filled the byte array exactly, so the code
 480                    just above didn't get to ensure there's a sign bit, and the
 481                    loop below wouldn't add one either.  Make sure a sign bit
 482                    exists. */
 483                 unsigned char msb = *(p - pincr);
 484                 int sign_bit_set = msb >= 0x80;
 485                 assert(accumbits == 0);
 486                 if (sign_bit_set == do_twos_comp)
 487                         return 0;
 488                 else
 489                         goto Overflow;
 490         }
 491
 492         /* Fill remaining bytes with copies of the sign bit. */
 493         {
 494                 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
 495                 for ( ; j < n; ++j, p += pincr)
 496                         *p = signbyte;
 497         }
 498
 499         return 0;
 500
 501 Overflow:
 502         PyErr_SetString(PyExc_OverflowError, "long too big to convert");
 503         return -1;
 504
 505 }
 506
 507 double
 508 _PyLong_AsScaledDouble(PyObject *vv, int *exponent)
 509 {
 510 /* NBITS_WANTED should be > the number of bits in a double's precision,
 511    but small enough so that 2**NBITS_WANTED is within the normal double
 512    range.  nbitsneeded is set to 1 less than that because the most-significant
 513    Python digit contains at least 1 significant bit, but we don't want to
 514    bother counting them (catering to the worst case cheaply).
 515
 516    57 is one more than VAX-D double precision; I (Tim) don't know of a double
 517    format with more precision than that; it's 1 larger so that we add in at
 518    least one round bit to stand in for the ignored least-significant bits.
 519 */
 520 #define NBITS_WANTED 57
 521         PyLongObject *v;
 522         double x;
 523         const double multiplier = (double)(1L << SHIFT);
 524         int i, sign;
 525         int nbitsneeded;
 526
 527         if (vv == NULL || !PyLong_Check(vv)) {
 528                 PyErr_BadInternalCall();
 529                 return -1;
 530         }
 531         v = (PyLongObject *)vv;
 532         i = v->ob_size;
 533         sign = 1;
 534         if (i < 0) {
 535                 sign = -1;
 536                 i = -(i);
 537         }
 538         else if (i == 0) {
 539                 *exponent = 0;
 540                 return 0.0;
 541         }
 542         --i;
 543         x = (double)v->ob_digit[i];
 544         nbitsneeded = NBITS_WANTED - 1;
 545         /* Invariant:  i Python digits remain unaccounted for. */
 546         while (i > 0 && nbitsneeded > 0) {
 547                 --i;
 548                 x = x * multiplier + (double)v->ob_digit[i];
 549                 nbitsneeded -= SHIFT;
 550         }
 551         /* There are i digits we didn't shift in.  Pretending they're all
 552            zeroes, the true value is x * 2**(i*SHIFT). */
 553         *exponent = i;
 554         assert(x > 0.0);
 555         return x * sign;
 556 #undef NBITS_WANTED
 557 }
 558
 559 /* Get a C double from a long int object. */
 560
 561 double
 562 PyLong_AsDouble(PyObject *vv)
 563 {
 564         int e;
 565         double x;
 566
 567         if (vv == NULL || !PyLong_Check(vv)) {
 568                 PyErr_BadInternalCall();
 569                 return -1;
 570         }
 571         x = _PyLong_AsScaledDouble(vv, &e);
 572         if (x == -1.0 && PyErr_Occurred())
 573                 return -1.0;
 574         if (e > INT_MAX / SHIFT)
 575                 goto overflow;
 576         errno = 0;
 577         x = ldexp(x, e * SHIFT);
 578         if (Py_OVERFLOWED(x))
 579                 goto overflow;
 580         return x;
 581
 582 overflow:
 583         PyErr_SetString(PyExc_OverflowError,
 584                 "long int too large to convert to float");
 585         return -1.0;
 586 }
 587
 588 /* Create a new long (or int) object from a C pointer */
 589
 590 PyObject *
 591 PyLong_FromVoidPtr(void *p)
 592 {
 593 #if SIZEOF_VOID_P <= SIZEOF_LONG
 594         return PyInt_FromLong((long)p);
 595 #else
 596
 597 #ifndef HAVE_LONG_LONG
 598 #   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 599 #endif
 600 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 601 #   error "PyLong_FromVoidPtr: sizeof(LONG_LONG) < sizeof(void*)"
 602 #endif
 603         /* optimize null pointers */
 604         if (p == NULL)
 605                 return PyInt_FromLong(0);
 606         return PyLong_FromLongLong((LONG_LONG)p);
 607
 608 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 609 }
 610
 611 /* Get a C pointer from a long object (or an int object in some cases) */
 612
 613 void *
 614 PyLong_AsVoidPtr(PyObject *vv)
 615 {
 616         /* This function will allow int or long objects. If vv is neither,
 617            then the PyLong_AsLong*() functions will raise the exception:
 618            PyExc_SystemError, "bad argument to internal function"
 619         */
 620 #if SIZEOF_VOID_P <= SIZEOF_LONG
 621         long x;
 622
 623         if (PyInt_Check(vv))
 624                 x = PyInt_AS_LONG(vv);
 625         else
 626                 x = PyLong_AsLong(vv);
 627 #else
 628
 629 #ifndef HAVE_LONG_LONG
 630 #   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 631 #endif
 632 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 633 #   error "PyLong_AsVoidPtr: sizeof(LONG_LONG) < sizeof(void*)"
 634 #endif
 635         LONG_LONG x;
 636
 637         if (PyInt_Check(vv))
 638                 x = PyInt_AS_LONG(vv);
 639         else
 640                 x = PyLong_AsLongLong(vv);
 641
 642 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 643
 644         if (x == -1 && PyErr_Occurred())
 645                 return NULL;
 646         return (void *)x;
 647 }
 648
 649 #ifdef HAVE_LONG_LONG
 650
 651 /* Initial LONG_LONG support by Chris Herborth (chrish@qnx.com), later
 652  * rewritten to use the newer PyLong_{As,From}ByteArray API.
 653  */
 654
 655 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
 656
 657 /* Create a new long int object from a C LONG_LONG int. */
 658
 659 PyObject *
 660 PyLong_FromLongLong(LONG_LONG ival)
 661 {
 662         LONG_LONG bytes = ival;
 663         int one = 1;
 664         return _PyLong_FromByteArray(
 665                         (unsigned char *)&bytes,
 666                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
 667 }
 668
 669 /* Create a new long int object from a C unsigned LONG_LONG int. */
 670
 671 PyObject *
 672 PyLong_FromUnsignedLongLong(unsigned LONG_LONG ival)
 673 {
 674         unsigned LONG_LONG bytes = ival;
 675         int one = 1;
 676         return _PyLong_FromByteArray(
 677                         (unsigned char *)&bytes,
 678                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
 679 }
 680
 681 /* Get a C LONG_LONG int from a long int object.
 682    Return -1 and set an error if overflow occurs. */
 683
 684 LONG_LONG
 685 PyLong_AsLongLong(PyObject *vv)
 686 {
 687         LONG_LONG bytes;
 688         int one = 1;
 689         int res;
 690
 691         if (vv == NULL) {
 692                 PyErr_BadInternalCall();
 693                 return -1;
 694         }
 695         if (!PyLong_Check(vv)) {
 696                 if (PyInt_Check(vv))
 697                         return (LONG_LONG)PyInt_AsLong(vv);
 698                 PyErr_BadInternalCall();
 699                 return -1;
 700         }
 701
 702         res = _PyLong_AsByteArray(
 703                         (PyLongObject *)vv, (unsigned char *)&bytes,
 704                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
 705
 706         /* Plan 9 can't handle LONG_LONG in ? : expressions */
 707         if (res < 0)
 708                 return (LONG_LONG)-1;
 709         else
 710                 return bytes;
 711 }
 712
 713 /* Get a C unsigned LONG_LONG int from a long int object.
 714    Return -1 and set an error if overflow occurs. */
 715
 716 unsigned LONG_LONG
 717 PyLong_AsUnsignedLongLong(PyObject *vv)
 718 {
 719         unsigned LONG_LONG bytes;
 720         int one = 1;
 721         int res;
 722
 723         if (vv == NULL || !PyLong_Check(vv)) {
 724                 PyErr_BadInternalCall();
 725                 return -1;
 726         }
 727
 728         res = _PyLong_AsByteArray(
 729                         (PyLongObject *)vv, (unsigned char *)&bytes,
 730                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
 731
 732         /* Plan 9 can't handle LONG_LONG in ? : expressions */
 733         if (res < 0)
 734                 return (unsigned LONG_LONG)res;
 735         else
 736                 return bytes;
 737 }
 738
 739 #undef IS_LITTLE_ENDIAN
 740
 741 #endif /* HAVE_LONG_LONG */
 742
 743
 744 static int
 745 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
 746         if (PyLong_Check(v)) {
 747                 *a = (PyLongObject *) v;
 748                 Py_INCREF(v);
 749         }
 750         else if (PyInt_Check(v)) {
 751                 *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
 752         }
 753         else {
 754                 return 0;
 755         }
 756         if (PyLong_Check(w)) {
 757                 *b = (PyLongObject *) w;
 758                 Py_INCREF(w);
 759         }
 760         else if (PyInt_Check(w)) {
 761                 *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
 762         }
 763         else {
 764                 Py_DECREF(*a);
 765                 return 0;
 766         }
 767         return 1;
 768 }
 769
 770 #define CONVERT_BINOP(v, w, a, b) \
 771         if (!convert_binop(v, w, a, b)) { \
 772                 Py_INCREF(Py_NotImplemented); \
 773                 return Py_NotImplemented; \
 774         }
 775
 776 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
 777  * is modified in place, by adding y to it.  Carries are propagated as far as
 778  * x[m-1], and the remaining carry (0 or 1) is returned.
 779  */
 780 static digit
 781 v_iadd(digit *x, int m, digit *y, int n)
 782 {
 783         int i;
 784         digit carry = 0;
 785
 786         assert(m >= n);
 787         for (i = 0; i < n; ++i) {
 788                 carry += x[i] + y[i];
 789                 x[i] = carry & MASK;
 790                 carry >>= SHIFT;
 791                 assert((carry & 1) == carry);
 792         }
 793         for (; carry && i < m; ++i) {
 794                 carry += x[i];
 795                 x[i] = carry & MASK;
 796                 carry >>= SHIFT;
 797                 assert((carry & 1) == carry);
 798         }
 799         return carry;
 800 }
 801
 802 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
 803  * is modified in place, by subtracting y from it.  Borrows are propagated as
 804  * far as x[m-1], and the remaining borrow (0 or 1) is returned.
 805  */
 806 static digit
 807 v_isub(digit *x, int m, digit *y, int n)
 808 {
 809         int i;
 810         digit borrow = 0;
 811
 812         assert(m >= n);
 813         for (i = 0; i < n; ++i) {
 814                 borrow = x[i] - y[i] - borrow;
 815                 x[i] = borrow & MASK;
 816                 borrow >>= SHIFT;
 817                 borrow &= 1;    /* keep only 1 sign bit */
 818         }
 819         for (; borrow && i < m; ++i) {
 820                 borrow = x[i] - borrow;
 821                 x[i] = borrow & MASK;
 822                 borrow >>= SHIFT;
 823                 borrow &= 1;
 824         }
 825         return borrow;
 826 }
 827
 828 /* Multiply by a single digit, ignoring the sign. */
 829
 830 static PyLongObject *
 831 mul1(PyLongObject *a, wdigit n)
 832 {
 833         return muladd1(a, n, (digit)0);
 834 }
 835
 836 /* Multiply by a single digit and add a single digit, ignoring the sign. */
 837
 838 static PyLongObject *
 839 muladd1(PyLongObject *a, wdigit n, wdigit extra)
 840 {
 841         int size_a = ABS(a->ob_size);
 842         PyLongObject *z = _PyLong_New(size_a+1);
 843         twodigits carry = extra;
 844         int i;
 845
 846         if (z == NULL)
 847                 return NULL;
 848         for (i = 0; i < size_a; ++i) {
 849                 carry += (twodigits)a->ob_digit[i] * n;
 850                 z->ob_digit[i] = (digit) (carry & MASK);
 851                 carry >>= SHIFT;
 852         }
 853         z->ob_digit[i] = (digit) carry;
 854         return long_normalize(z);
 855 }
 856
 857 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
 858    in pout, and returning the remainder.  pin and pout point at the LSD.
 859    It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
 860    long_format, but that should be done with great care since longs are
 861    immutable. */
 862
 863 static digit
 864 inplace_divrem1(digit *pout, digit *pin, int size, digit n)
 865 {
 866         twodigits rem = 0;
 867
 868         assert(n > 0 && n <= MASK);
 869         pin += size;
 870         pout += size;
 871         while (--size >= 0) {
 872                 digit hi;
 873                 rem = (rem << SHIFT) + *--pin;
 874                 *--pout = hi = (digit)(rem / n);
 875                 rem -= hi * n;
 876         }
 877         return (digit)rem;
 878 }
 879
 880 /* Divide a long integer by a digit, returning both the quotient
 881    (as function result) and the remainder (through *prem).
 882    The sign of a is ignored; n should not be zero. */
 883
 884 static PyLongObject *
 885 divrem1(PyLongObject *a, digit n, digit *prem)
 886 {
 887         const int size = ABS(a->ob_size);
 888         PyLongObject *z;
 889
 890         assert(n > 0 && n <= MASK);
 891         z = _PyLong_New(size);
 892         if (z == NULL)
 893                 return NULL;
 894         *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
 895         return long_normalize(z);
 896 }
 897
 898 /* Convert a long int object to a string, using a given conversion base.
 899    Return a string object.
 900    If base is 8 or 16, add the proper prefix '0' or '0x'. */
 901
 902 static PyObject *
 903 long_format(PyObject *aa, int base, int addL)
 904 {
 905         register PyLongObject *a = (PyLongObject *)aa;
 906         PyStringObject *str;
 907         int i;
 908         const int size_a = ABS(a->ob_size);
 909         char *p;
 910         int bits;
 911         char sign = '\0';
 912
 913         if (a == NULL || !PyLong_Check(a)) {
 914                 PyErr_BadInternalCall();
 915                 return NULL;
 916         }
 917         assert(base >= 2 && base <= 36);
 918
 919         /* Compute a rough upper bound for the length of the string */
 920         i = base;
 921         bits = 0;
 922         while (i > 1) {
 923                 ++bits;
 924                 i >>= 1;
 925         }
 926         i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
 927         str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
 928         if (str == NULL)
 929                 return NULL;
 930         p = PyString_AS_STRING(str) + i;
 931         *p = '\0';
 932         if (addL)
 933                 *--p = 'L';
 934         if (a->ob_size < 0)
 935                 sign = '-';
 936
 937         if (a->ob_size == 0) {
 938                 *--p = '0';
 939         }
 940         else if ((base & (base - 1)) == 0) {
 941                 /* JRH: special case for power-of-2 bases */
 942                 twodigits accum = 0;
 943                 int accumbits = 0;      /* # of bits in accum */
 944                 int basebits = 1;       /* # of bits in base-1 */
 945                 i = base;
 946                 while ((i >>= 1) > 1)
 947                         ++basebits;
 948
 949                 for (i = 0; i < size_a; ++i) {
 950                         accum |= (twodigits)a->ob_digit[i] << accumbits;
 951                         accumbits += SHIFT;
 952                         assert(accumbits >= basebits);
 953                         do {
 954                                 char cdigit = (char)(accum & (base - 1));
 955                                 cdigit += (cdigit < 10) ? '0' : 'A'-10;
 956                                 assert(p > PyString_AS_STRING(str));
 957                                 *--p = cdigit;
 958                                 accumbits -= basebits;
 959                                 accum >>= basebits;
 960                         } while (i < size_a-1 ? accumbits >= basebits :
 961                                                 accum > 0);
 962                 }
 963         }
 964         else {
 965                 /* Not 0, and base not a power of 2.  Divide repeatedly by
 966                    base, but for speed use the highest power of base that
 967                    fits in a digit. */
 968                 int size = size_a;
 969                 digit *pin = a->ob_digit;
 970                 PyLongObject *scratch;
 971                 /* powbasw <- largest power of base that fits in a digit. */
 972                 digit powbase = base;  /* powbase == base ** power */
 973                 int power = 1;
 974                 for (;;) {
 975                         unsigned long newpow = powbase * (unsigned long)base;
 976                         if (newpow >> SHIFT)  /* doesn't fit in a digit */
 977                                 break;
 978                         powbase = (digit)newpow;
 979                         ++power;
 980                 }
 981
 982                 /* Get a scratch area for repeated division. */
 983                 scratch = _PyLong_New(size);
 984                 if (scratch == NULL) {
 985                         Py_DECREF(str);
 986                         return NULL;
 987                 }
 988
 989                 /* Repeatedly divide by powbase. */
 990                 do {
 991                         int ntostore = power;
 992                         digit rem = inplace_divrem1(scratch->ob_digit,
 993                                                      pin, size, powbase);
 994                         pin = scratch->ob_digit; /* no need to use a again */
 995                         if (pin[size - 1] == 0)
 996                                 --size;
 997                         SIGCHECK({
 998                                 Py_DECREF(scratch);
 999                                 Py_DECREF(str);
1000                                 return NULL;
1001                         })
1002
1003                         /* Break rem into digits. */
1004                         assert(ntostore > 0);
1005                         do {
1006                                 digit nextrem = (digit)(rem / base);
1007                                 char c = (char)(rem - nextrem * base);
1008                                 assert(p > PyString_AS_STRING(str));
1009                                 c += (c < 10) ? '0' : 'A'-10;
1010                                 *--p = c;
1011                                 rem = nextrem;
1012                                 --ntostore;
1013                                 /* Termination is a bit delicate:  must not
1014                                    store leading zeroes, so must get out if
1015                                    remaining quotient and rem are both 0. */
1016                         } while (ntostore && (size || rem));
1017                 } while (size != 0);
1018                 Py_DECREF(scratch);
1019         }
1020
1021         if (base == 8) {
1022                 if (size_a != 0)
1023                         *--p = '0';
1024         }
1025         else if (base == 16) {
1026                 *--p = 'x';
1027                 *--p = '0';
1028         }
1029         else if (base != 10) {
1030                 *--p = '#';
1031                 *--p = '0' + base%10;
1032                 if (base > 10)
1033                         *--p = '0' + base/10;
1034         }
1035         if (sign)
1036                 *--p = sign;
1037         if (p != PyString_AS_STRING(str)) {
1038                 char *q = PyString_AS_STRING(str);
1039                 assert(p > q);
1040                 do {
1041                 } while ((*q++ = *p++) != '\0');
1042                 q--;
1043                 _PyString_Resize((PyObject **)&str,
1044                                  (int) (q - PyString_AS_STRING(str)));
1045         }
1046         return (PyObject *)str;
1047 }
1048
1049 PyObject *
1050 PyLong_FromString(char *str, char **pend, int base)
1051 {
1052         int sign = 1;
1053         char *start, *orig_str = str;
1054         PyLongObject *z;
1055
1056         if ((base != 0 && base < 2) || base > 36) {
1057                 PyErr_SetString(PyExc_ValueError,
1058                                 "long() arg 2 must be >= 2 and <= 36");
1059                 return NULL;
1060         }
1061         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1062                 str++;
1063         if (*str == '+')
1064                 ++str;
1065         else if (*str == '-') {
1066                 ++str;
1067                 sign = -1;
1068         }
1069         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1070                 str++;
1071         if (base == 0) {
1072                 if (str[0] != '0')
1073                         base = 10;
1074                 else if (str[1] == 'x' || str[1] == 'X')
1075                         base = 16;
1076                 else
1077                         base = 8;
1078         }
1079         if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
1080                 str += 2;
1081         z = _PyLong_New(0);
1082         start = str;
1083         for ( ; z != NULL; ++str) {
1084                 int k = -1;
1085                 PyLongObject *temp;
1086
1087                 if (*str <= '9')
1088                         k = *str - '0';
1089                 else if (*str >= 'a')
1090                         k = *str - 'a' + 10;
1091                 else if (*str >= 'A')
1092                         k = *str - 'A' + 10;
1093                 if (k < 0 || k >= base)
1094                         break;
1095                 temp = muladd1(z, (digit)base, (digit)k);
1096                 Py_DECREF(z);
1097                 z = temp;
1098         }
1099         if (z == NULL)
1100                 return NULL;
1101         if (str == start)
1102                 goto onError;
1103         if (sign < 0 && z != NULL && z->ob_size != 0)
1104                 z->ob_size = -(z->ob_size);
1105         if (*str == 'L' || *str == 'l')
1106                 str++;
1107         while (*str && isspace(Py_CHARMASK(*str)))
1108                 str++;
1109         if (*str != '\0')
1110                 goto onError;
1111         if (pend)
1112                 *pend = str;
1113         return (PyObject *) z;
1114
1115  onError:
1116         PyErr_Format(PyExc_ValueError,
1117                      "invalid literal for long(): %.200s", orig_str);
1118         Py_XDECREF(z);
1119         return NULL;
1120 }
1121
1122 #ifdef Py_USING_UNICODE
1123 PyObject *
1124 PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
1125 {
1126         PyObject *result;
1127         char *buffer = PyMem_MALLOC(length+1);
1128
1129         if (buffer == NULL)
1130                 return NULL;
1131
1132         if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
1133                 PyMem_FREE(buffer);
1134                 return NULL;
1135         }
1136         result = PyLong_FromString(buffer, NULL, base);
1137         PyMem_FREE(buffer);
1138         return result;
1139 }
1140 #endif
1141
1142 /* forward */
1143 static PyLongObject *x_divrem
1144         (PyLongObject *, PyLongObject *, PyLongObject **);
1145 static PyObject *long_pos(PyLongObject *);
1146 static int long_divrem(PyLongObject *, PyLongObject *,
1147         PyLongObject **, PyLongObject **);
1148
1149 /* Long division with remainder, top-level routine */
1150
1151 static int
1152 long_divrem(PyLongObject *a, PyLongObject *b,
1153             PyLongObject **pdiv, PyLongObject **prem)
1154 {
1155         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1156         PyLongObject *z;
1157
1158         if (size_b == 0) {
1159                 PyErr_SetString(PyExc_ZeroDivisionError,
1160                                 "long division or modulo by zero");
1161                 return -1;
1162         }
1163         if (size_a < size_b ||
1164             (size_a == size_b &&
1165              a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
1166                 /* |a| < |b|. */
1167                 *pdiv = _PyLong_New(0);
1168                 Py_INCREF(a);
1169                 *prem = (PyLongObject *) a;
1170                 return 0;
1171         }
1172         if (size_b == 1) {
1173                 digit rem = 0;
1174                 z = divrem1(a, b->ob_digit[0], &rem);
1175                 if (z == NULL)
1176                         return -1;
1177                 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
1178         }
1179         else {
1180                 z = x_divrem(a, b, prem);
1181                 if (z == NULL)
1182                         return -1;
1183         }
1184         /* Set the signs.
1185            The quotient z has the sign of a*b;
1186            the remainder r has the sign of a,
1187            so a = b*z + r. */
1188         if ((a->ob_size < 0) != (b->ob_size < 0))
1189                 z->ob_size = -(z->ob_size);
1190         if (a->ob_size < 0 && (*prem)->ob_size != 0)
1191                 (*prem)->ob_size = -((*prem)->ob_size);
1192         *pdiv = z;
1193         return 0;
1194 }
1195
1196 /* Unsigned long division with remainder -- the algorithm */
1197
1198 static PyLongObject *
1199 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
1200 {
1201         int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size);
1202         digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
1203         PyLongObject *v = mul1(v1, d);
1204         PyLongObject *w = mul1(w1, d);
1205         PyLongObject *a;
1206         int j, k;
1207
1208         if (v == NULL || w == NULL) {
1209                 Py_XDECREF(v);
1210                 Py_XDECREF(w);
1211                 return NULL;
1212         }
1213
1214         assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
1215         assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
1216         assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */
1217
1218         size_v = ABS(v->ob_size);
1219         a = _PyLong_New(size_v - size_w + 1);
1220
1221         for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) {
1222                 digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
1223                 twodigits q;
1224                 stwodigits carry = 0;
1225                 int i;
1226
1227                 SIGCHECK({
1228                         Py_DECREF(a);
1229                         a = NULL;
1230                         break;
1231                 })
1232                 if (vj == w->ob_digit[size_w-1])
1233                         q = MASK;
1234                 else
1235                         q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
1236                                 w->ob_digit[size_w-1];
1237
1238                 while (w->ob_digit[size_w-2]*q >
1239                                 ((
1240                                         ((twodigits)vj << SHIFT)
1241                                         + v->ob_digit[j-1]
1242                                         - q*w->ob_digit[size_w-1]
1243                                                                 ) << SHIFT)
1244                                 + v->ob_digit[j-2])
1245                         --q;
1246
1247                 for (i = 0; i < size_w && i+k < size_v; ++i) {
1248                         twodigits z = w->ob_digit[i] * q;
1249                         digit zz = (digit) (z >> SHIFT);
1250                         carry += v->ob_digit[i+k] - z
1251                                 + ((twodigits)zz << SHIFT);
1252                         v->ob_digit[i+k] = carry & MASK;
1253                         carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
1254                                                           carry, SHIFT);
1255                         carry -= zz;
1256                 }
1257
1258                 if (i+k < size_v) {
1259                         carry += v->ob_digit[i+k];
1260                         v->ob_digit[i+k] = 0;
1261                 }
1262
1263                 if (carry == 0)
1264                         a->ob_digit[k] = (digit) q;
1265                 else {
1266                         assert(carry == -1);
1267                         a->ob_digit[k] = (digit) q-1;
1268                         carry = 0;
1269                         for (i = 0; i < size_w && i+k < size_v; ++i) {
1270                                 carry += v->ob_digit[i+k] + w->ob_digit[i];
1271                                 v->ob_digit[i+k] = carry & MASK;
1272                                 carry = Py_ARITHMETIC_RIGHT_SHIFT(
1273                                                 BASE_TWODIGITS_TYPE,
1274                                                 carry, SHIFT);
1275                         }
1276                 }
1277         } /* for j, k */
1278
1279         if (a == NULL)
1280                 *prem = NULL;
1281         else {
1282                 a = long_normalize(a);
1283                 *prem = divrem1(v, d, &d);
1284                 /* d receives the (unused) remainder */
1285                 if (*prem == NULL) {
1286                         Py_DECREF(a);
1287                         a = NULL;
1288                 }
1289         }
1290         Py_DECREF(v);
1291         Py_DECREF(w);
1292         return a;
1293 }
1294
1295 /* Methods */
1296
1297 static void
1298 long_dealloc(PyObject *v)
1299 {
1300         v->ob_type->tp_free(v);
1301 }
1302
1303 static PyObject *
1304 long_repr(PyObject *v)
1305 {
1306         return long_format(v, 10, 1);
1307 }
1308
1309 static PyObject *
1310 long_str(PyObject *v)
1311 {
1312         return long_format(v, 10, 0);
1313 }
1314
1315 static int
1316 long_compare(PyLongObject *a, PyLongObject *b)
1317 {
1318         int sign;
1319
1320         if (a->ob_size != b->ob_size) {
1321                 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0)
1322                         sign = 0;
1323                 else
1324                         sign = a->ob_size - b->ob_size;
1325         }
1326         else {
1327                 int i = ABS(a->ob_size);
1328                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1329                         ;
1330                 if (i < 0)
1331                         sign = 0;
1332                 else {
1333                         sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
1334                         if (a->ob_size < 0)
1335                                 sign = -sign;
1336                 }
1337         }
1338         return sign < 0 ? -1 : sign > 0 ? 1 : 0;
1339 }
1340
1341 static long
1342 long_hash(PyLongObject *v)
1343 {
1344         long x;
1345         int i, sign;
1346
1347         /* This is designed so that Python ints and longs with the
1348            same value hash to the same value, otherwise comparisons
1349            of mapping keys will turn out weird */
1350         i = v->ob_size;
1351         sign = 1;
1352         x = 0;
1353         if (i < 0) {
1354                 sign = -1;
1355                 i = -(i);
1356         }
1357         while (--i >= 0) {
1358                 /* Force a 32-bit circular shift */
1359                 x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK);
1360                 x += v->ob_digit[i];
1361         }
1362         x = x * sign;
1363         if (x == -1)
1364                 x = -2;
1365         return x;
1366 }
1367
1368
1369 /* Add the absolute values of two long integers. */
1370
1371 static PyLongObject *
1372 x_add(PyLongObject *a, PyLongObject *b)
1373 {
1374         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1375         PyLongObject *z;
1376         int i;
1377         digit carry = 0;
1378
1379         /* Ensure a is the larger of the two: */
1380         if (size_a < size_b) {
1381                 { PyLongObject *temp = a; a = b; b = temp; }
1382                 { int size_temp = size_a;
1383                   size_a = size_b;
1384                   size_b = size_temp; }
1385         }
1386         z = _PyLong_New(size_a+1);
1387         if (z == NULL)
1388                 return NULL;
1389         for (i = 0; i < size_b; ++i) {
1390                 carry += a->ob_digit[i] + b->ob_digit[i];
1391                 z->ob_digit[i] = carry & MASK;
1392                 carry >>= SHIFT;
1393         }
1394         for (; i < size_a; ++i) {
1395                 carry += a->ob_digit[i];
1396                 z->ob_digit[i] = carry & MASK;
1397                 carry >>= SHIFT;
1398         }
1399         z->ob_digit[i] = carry;
1400         return long_normalize(z);
1401 }
1402
1403 /* Subtract the absolute values of two integers. */
1404
1405 static PyLongObject *
1406 x_sub(PyLongObject *a, PyLongObject *b)
1407 {
1408         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1409         PyLongObject *z;
1410         int i;
1411         int sign = 1;
1412         digit borrow = 0;
1413
1414         /* Ensure a is the larger of the two: */
1415         if (size_a < size_b) {
1416                 sign = -1;
1417                 { PyLongObject *temp = a; a = b; b = temp; }
1418                 { int size_temp = size_a;
1419                   size_a = size_b;
1420                   size_b = size_temp; }
1421         }
1422         else if (size_a == size_b) {
1423                 /* Find highest digit where a and b differ: */
1424                 i = size_a;
1425                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1426                         ;
1427                 if (i < 0)
1428                         return _PyLong_New(0);
1429                 if (a->ob_digit[i] < b->ob_digit[i]) {
1430                         sign = -1;
1431                         { PyLongObject *temp = a; a = b; b = temp; }
1432                 }
1433                 size_a = size_b = i+1;
1434         }
1435         z = _PyLong_New(size_a);
1436         if (z == NULL)
1437                 return NULL;
1438         for (i = 0; i < size_b; ++i) {
1439                 /* The following assumes unsigned arithmetic
1440                    works module 2**N for some N>SHIFT. */
1441                 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
1442                 z->ob_digit[i] = borrow & MASK;
1443                 borrow >>= SHIFT;
1444                 borrow &= 1; /* Keep only one sign bit */
1445         }
1446         for (; i < size_a; ++i) {
1447                 borrow = a->ob_digit[i] - borrow;
1448                 z->ob_digit[i] = borrow & MASK;
1449                 borrow >>= SHIFT;
1450                 borrow &= 1; /* Keep only one sign bit */
1451         }
1452         assert(borrow == 0);
1453         if (sign < 0)
1454                 z->ob_size = -(z->ob_size);
1455         return long_normalize(z);
1456 }
1457
1458 static PyObject *
1459 long_add(PyLongObject *v, PyLongObject *w)
1460 {
1461         PyLongObject *a, *b, *z;
1462
1463         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1464
1465         if (a->ob_size < 0) {
1466                 if (b->ob_size < 0) {
1467                         z = x_add(a, b);
1468                         if (z != NULL && z->ob_size != 0)
1469                                 z->ob_size = -(z->ob_size);
1470                 }
1471                 else
1472                         z = x_sub(b, a);
1473         }
1474         else {
1475                 if (b->ob_size < 0)
1476                         z = x_sub(a, b);
1477                 else
1478                         z = x_add(a, b);
1479         }
1480         Py_DECREF(a);
1481         Py_DECREF(b);
1482         return (PyObject *)z;
1483 }
1484
1485 static PyObject *
1486 long_sub(PyLongObject *v, PyLongObject *w)
1487 {
1488         PyLongObject *a, *b, *z;
1489
1490         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1491
1492         if (a->ob_size < 0) {
1493                 if (b->ob_size < 0)
1494                         z = x_sub(a, b);
1495                 else
1496                         z = x_add(a, b);
1497                 if (z != NULL && z->ob_size != 0)
1498                         z->ob_size = -(z->ob_size);
1499         }
1500         else {
1501                 if (b->ob_size < 0)
1502                         z = x_add(a, b);
1503                 else
1504                         z = x_sub(a, b);
1505         }
1506         Py_DECREF(a);
1507         Py_DECREF(b);
1508         return (PyObject *)z;
1509 }
1510
1511 /* Grade school multiplication, ignoring the signs.
1512  * Returns the absolute value of the product, or NULL if error.
1513  */
1514 static PyLongObject *
1515 x_mul(PyLongObject *a, PyLongObject *b)
1516 {
1517         PyLongObject *z;
1518         int size_a = ABS(a->ob_size);
1519         int size_b = ABS(b->ob_size);
1520         int i;
1521
1522         z = _PyLong_New(size_a + size_b);
1523         if (z == NULL)
1524                 return NULL;
1525
1526         memset(z->ob_digit, 0, z->ob_size * sizeof(digit));
1527         for (i = 0; i < size_a; ++i) {
1528                 twodigits carry = 0;
1529                 twodigits f = a->ob_digit[i];
1530                 int j;
1531                 digit *pz = z->ob_digit + i;
1532
1533                 SIGCHECK({
1534                         Py_DECREF(z);
1535                         return NULL;
1536                 })
1537                 for (j = 0; j < size_b; ++j) {
1538                         carry += *pz + b->ob_digit[j] * f;
1539                         *pz++ = (digit) (carry & MASK);
1540                         carry >>= SHIFT;
1541                 }
1542                 for (; carry != 0; ++j) {
1543                         assert(i+j < z->ob_size);
1544                         carry += *pz;
1545                         *pz++ = (digit) (carry & MASK);
1546                         carry >>= SHIFT;
1547                 }
1548         }
1549         return long_normalize(z);
1550 }
1551
1552 /* A helper for Karatsuba multiplication (k_mul).
1553    Takes a long "n" and an integer "size" representing the place to
1554    split, and sets low and high such that abs(n) == (high << size) + low,
1555    viewing the shift as being by digits.  The sign bit is ignored, and
1556    the return values are >= 0.
1557    Returns 0 on success, -1 on failure.
1558 */
1559 static int
1560 kmul_split(PyLongObject *n, int size, PyLongObject **high, PyLongObject **low)
1561 {
1562         PyLongObject *hi, *lo;
1563         int size_lo, size_hi;
1564         const int size_n = ABS(n->ob_size);
1565
1566         size_lo = MIN(size_n, size);
1567         size_hi = size_n - size_lo;
1568
1569         if ((hi = _PyLong_New(size_hi)) == NULL)
1570                 return -1;
1571         if ((lo = _PyLong_New(size_lo)) == NULL) {
1572                 Py_DECREF(hi);
1573                 return -1;
1574         }
1575
1576         memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
1577         memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
1578
1579         *high = long_normalize(hi);
1580         *low = long_normalize(lo);
1581         return 0;
1582 }
1583
1584 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
1585
1586 /* Karatsuba multiplication.  Ignores the input signs, and returns the
1587  * absolute value of the product (or NULL if error).
1588  * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
1589  */
1590 static PyLongObject *
1591 k_mul(PyLongObject *a, PyLongObject *b)
1592 {
1593         int asize = ABS(a->ob_size);
1594         int bsize = ABS(b->ob_size);
1595         PyLongObject *ah = NULL;
1596         PyLongObject *al = NULL;
1597         PyLongObject *bh = NULL;
1598         PyLongObject *bl = NULL;
1599         PyLongObject *ret = NULL;
1600         PyLongObject *t1, *t2, *t3;
1601         int shift;      /* the number of digits we split off */
1602         int i;
1603
1604         /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
1605          * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
1606          * Then the original product is
1607          *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
1608          * By picking X to be a power of 2, "*X" is just shifting, and it's
1609          * been reduced to 3 multiplies on numbers half the size.
1610          */
1611
1612         /* We want to split based on the larger number; fiddle so that b
1613          * is largest.
1614          */
1615         if (asize > bsize) {
1616                 t1 = a;
1617                 a = b;
1618                 b = t1;
1619
1620                 i = asize;
1621                 asize = bsize;
1622                 bsize = i;
1623         }
1624
1625         /* Use gradeschool math when either number is too small. */
1626         if (asize <= KARATSUBA_CUTOFF) {
1627                 if (asize == 0)
1628                         return _PyLong_New(0);
1629                 else
1630                         return x_mul(a, b);
1631         }
1632
1633         /* If a is small compared to b, splitting on b gives a degenerate
1634          * case with ah==0, and Karatsuba may be (even much) less efficient
1635          * than "grade school" then.  However, we can still win, by viewing
1636          * b as a string of "big digits", each of width a->ob_size.  That
1637          * leads to a sequence of balanced calls to k_mul.
1638          */
1639         if (2 * asize <= bsize)
1640                 return k_lopsided_mul(a, b);
1641
1642         /* Split a & b into hi & lo pieces. */
1643         shift = bsize >> 1;
1644         if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
1645         assert(ah->ob_size > 0);        /* the split isn't degenerate */
1646
1647         if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
1648
1649         /* The plan:
1650          * 1. Allocate result space (asize + bsize digits:  that's always
1651          *    enough).
1652          * 2. Compute ah*bh, and copy into result at 2*shift.
1653          * 3. Compute al*bl, and copy into result at 0.  Note that this
1654          *    can't overlap with #2.
1655          * 4. Subtract al*bl from the result, starting at shift.  This may
1656          *    underflow (borrow out of the high digit), but we don't care:
1657          *    we're effectively doing unsigned arithmetic mod
1658          *    BASE**(sizea + sizeb), and so long as the *final* result fits,
1659          *    borrows and carries out of the high digit can be ignored.
1660          * 5. Subtract ah*bh from the result, starting at shift.
1661          * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
1662          *    at shift.
1663          */
1664
1665         /* 1. Allocate result space. */
1666         ret = _PyLong_New(asize + bsize);
1667         if (ret == NULL) goto fail;
1668 #ifdef Py_DEBUG
1669         /* Fill with trash, to catch reference to uninitialized digits. */
1670         memset(ret->ob_digit, 0xDF, ret->ob_size * sizeof(digit));
1671 #endif
1672
1673         /* 2. t1 <- ah*bh, and copy into high digits of result. */
1674         if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
1675         assert(t1->ob_size >= 0);
1676         assert(2*shift + t1->ob_size <= ret->ob_size);
1677         memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
1678                t1->ob_size * sizeof(digit));
1679
1680         /* Zero-out the digits higher than the ah*bh copy. */
1681         i = ret->ob_size - 2*shift - t1->ob_size;
1682         if (i)
1683                 memset(ret->ob_digit + 2*shift + t1->ob_size, 0,
1684                        i * sizeof(digit));
1685
1686         /* 3. t2 <- al*bl, and copy into the low digits. */
1687         if ((t2 = k_mul(al, bl)) == NULL) {
1688                 Py_DECREF(t1);
1689                 goto fail;
1690         }
1691         assert(t2->ob_size >= 0);
1692         assert(t2->ob_size <= 2*shift); /* no overlap with high digits */
1693         memcpy(ret->ob_digit, t2->ob_digit, t2->ob_size * sizeof(digit));
1694
1695         /* Zero out remaining digits. */
1696         i = 2*shift - t2->ob_size;      /* number of uninitialized digits */
1697         if (i)
1698                 memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit));
1699
1700         /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2).  We do al*bl first
1701          * because it's fresher in cache.
1702          */
1703         i = ret->ob_size - shift;  /* # digits after shift */
1704         (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size);
1705         Py_DECREF(t2);
1706
1707         (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size);
1708         Py_DECREF(t1);
1709
1710         /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
1711         if ((t1 = x_add(ah, al)) == NULL) goto fail;
1712         Py_DECREF(ah);
1713         Py_DECREF(al);
1714         ah = al = NULL;
1715
1716         if ((t2 = x_add(bh, bl)) == NULL) {
1717                 Py_DECREF(t1);
1718                 goto fail;
1719         }
1720         Py_DECREF(bh);
1721         Py_DECREF(bl);
1722         bh = bl = NULL;
1723
1724         t3 = k_mul(t1, t2);
1725         Py_DECREF(t1);
1726         Py_DECREF(t2);
1727         if (t3 == NULL) goto fail;
1728         assert(t3->ob_size >= 0);
1729
1730         /* Add t3.  It's not obvious why we can't run out of room here.
1731          * See the (*) comment after this function.
1732          */
1733         (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size);
1734         Py_DECREF(t3);
1735
1736         return long_normalize(ret);
1737
1738  fail:
1739         Py_XDECREF(ret);
1740         Py_XDECREF(ah);
1741         Py_XDECREF(al);
1742         Py_XDECREF(bh);
1743         Py_XDECREF(bl);
1744         return NULL;
1745 }
1746
1747 /* (*) Why adding t3 can't "run out of room" above.
1748
1749 Let f(x) mean the floor of x and c(x) mean the ceiling of x.  Some facts
1750 to start with:
1751
1752 1. For any integer i, i = c(i/2) + f(i/2).  In particular,
1753    bsize = c(bsize/2) + f(bsize/2).
1754 2. shift = f(bsize/2)
1755 3. asize <= bsize
1756 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
1757    routine, so asize > bsize/2 >= f(bsize/2) in this routine.
1758
1759 We allocated asize + bsize result digits, and add t3 into them at an offset
1760 of shift.  This leaves asize+bsize-shift allocated digit positions for t3
1761 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
1762 asize + c(bsize/2) available digit positions.
1763
1764 bh has c(bsize/2) digits, and bl at most f(size/2) digits.  So bh+hl has
1765 at most c(bsize/2) digits + 1 bit.
1766
1767 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
1768 digits, and al has at most f(bsize/2) digits in any case.  So ah+al has at
1769 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
1770
1771 The product (ah+al)*(bh+bl) therefore has at most
1772
1773     c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
1774
1775 and we have asize + c(bsize/2) available digit positions.  We need to show
1776 this is always enough.  An instance of c(bsize/2) cancels out in both, so
1777 the question reduces to whether asize digits is enough to hold
1778 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits.  If asize < bsize,
1779 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits.  By #4,
1780 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
1781 digit is enough to hold 2 bits.  This is so since SHIFT=15 >= 2.  If
1782 asize == bsize, then we're asking whether bsize digits is enough to hold
1783 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
1784 is enough to hold 2 bits.  This is so if bsize >= 2, which holds because
1785 bsize >= KARATSUBA_CUTOFF >= 2.
1786
1787 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
1788 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
1789 ah*bh and al*bl too.
1790 */
1791
1792 /* b has at least twice the digits of a, and a is big enough that Karatsuba
1793  * would pay off *if* the inputs had balanced sizes.  View b as a sequence
1794  * of slices, each with a->ob_size digits, and multiply the slices by a,
1795  * one at a time.  This gives k_mul balanced inputs to work with, and is
1796  * also cache-friendly (we compute one double-width slice of the result
1797  * at a time, then move on, never bactracking except for the helpful
1798  * single-width slice overlap between successive partial sums).
1799  */
1800 static PyLongObject *
1801 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
1802 {
1803         const int asize = ABS(a->ob_size);
1804         int bsize = ABS(b->ob_size);
1805         int nbdone;     /* # of b digits already multiplied */
1806         PyLongObject *ret;
1807         PyLongObject *bslice = NULL;
1808
1809         assert(asize > KARATSUBA_CUTOFF);
1810         assert(2 * asize <= bsize);
1811
1812         /* Allocate result space, and zero it out. */
1813         ret = _PyLong_New(asize + bsize);
1814         if (ret == NULL)
1815                 return NULL;
1816         memset(ret->ob_digit, 0, ret->ob_size * sizeof(digit));
1817
1818         /* Successive slices of b are copied into bslice. */
1819         bslice = _PyLong_New(asize);
1820         if (bslice == NULL)
1821                 goto fail;
1822
1823         nbdone = 0;
1824         while (bsize > 0) {
1825                 PyLongObject *product;
1826                 const int nbtouse = MIN(bsize, asize);
1827
1828                 /* Multiply the next slice of b by a. */
1829                 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
1830                        nbtouse * sizeof(digit));
1831                 bslice->ob_size = nbtouse;
1832                 product = k_mul(a, bslice);
1833                 if (product == NULL)
1834                         goto fail;
1835
1836                 /* Add into result. */
1837                 (void)v_iadd(ret->ob_digit + nbdone, ret->ob_size - nbdone,
1838                              product->ob_digit, product->ob_size);
1839                 Py_DECREF(product);
1840
1841                 bsize -= nbtouse;
1842                 nbdone += nbtouse;
1843         }
1844
1845         Py_DECREF(bslice);
1846         return long_normalize(ret);
1847
1848  fail:
1849         Py_DECREF(ret);
1850         Py_XDECREF(bslice);
1851         return NULL;
1852 }
1853
1854 static PyObject *
1855 long_mul(PyLongObject *v, PyLongObject *w)
1856 {
1857         PyLongObject *a, *b, *z;
1858
1859         if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
1860                 Py_INCREF(Py_NotImplemented);
1861                 return Py_NotImplemented;
1862         }
1863
1864         z = k_mul(a, b);
1865         /* Negate if exactly one of the inputs is negative. */
1866         if (((a->ob_size ^ b->ob_size) < 0) && z)
1867                 z->ob_size = -(z->ob_size);
1868         Py_DECREF(a);
1869         Py_DECREF(b);
1870         return (PyObject *)z;
1871 }
1872
1873 /* The / and % operators are now defined in terms of divmod().
1874    The expression a mod b has the value a - b*floor(a/b).
1875    The long_divrem function gives the remainder after division of
1876    |a| by |b|, with the sign of a.  This is also expressed
1877    as a - b*trunc(a/b), if trunc truncates towards zero.
1878    Some examples:
1879          a       b      a rem b         a mod b
1880          13      10      3               3
1881         -13      10     -3               7
1882          13     -10      3              -7
1883         -13     -10     -3              -3
1884    So, to get from rem to mod, we have to add b if a and b
1885    have different signs.  We then subtract one from the 'div'
1886    part of the outcome to keep the invariant intact. */
1887
1888 static int
1889 l_divmod(PyLongObject *v, PyLongObject *w,
1890          PyLongObject **pdiv, PyLongObject **pmod)
1891 {
1892         PyLongObject *div, *mod;
1893
1894         if (long_divrem(v, w, &div, &mod) < 0)
1895                 return -1;
1896         if ((mod->ob_size < 0 && w->ob_size > 0) ||
1897             (mod->ob_size > 0 && w->ob_size < 0)) {
1898                 PyLongObject *temp;
1899                 PyLongObject *one;
1900                 temp = (PyLongObject *) long_add(mod, w);
1901                 Py_DECREF(mod);
1902                 mod = temp;
1903                 if (mod == NULL) {
1904                         Py_DECREF(div);
1905                         return -1;
1906                 }
1907                 one = (PyLongObject *) PyLong_FromLong(1L);
1908                 if (one == NULL ||
1909                     (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
1910                         Py_DECREF(mod);
1911                         Py_DECREF(div);
1912                         Py_XDECREF(one);
1913                         return -1;
1914                 }
1915                 Py_DECREF(one);
1916                 Py_DECREF(div);
1917                 div = temp;
1918         }
1919         *pdiv = div;
1920         *pmod = mod;
1921         return 0;
1922 }
1923
1924 static PyObject *
1925 long_div(PyObject *v, PyObject *w)
1926 {
1927         PyLongObject *a, *b, *div, *mod;
1928
1929         CONVERT_BINOP(v, w, &a, &b);
1930
1931         if (l_divmod(a, b, &div, &mod) < 0) {
1932                 Py_DECREF(a);
1933                 Py_DECREF(b);
1934                 return NULL;
1935         }
1936         Py_DECREF(a);
1937         Py_DECREF(b);
1938         Py_DECREF(mod);
1939         return (PyObject *)div;
1940 }
1941
1942 static PyObject *
1943 long_classic_div(PyObject *v, PyObject *w)
1944 {
1945         PyLongObject *a, *b, *div, *mod;
1946
1947         CONVERT_BINOP(v, w, &a, &b);
1948
1949         if (Py_DivisionWarningFlag &&
1950             PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
1951                 div = NULL;
1952         else if (l_divmod(a, b, &div, &mod) < 0)
1953                 div = NULL;
1954         else
1955                 Py_DECREF(mod);
1956
1957         Py_DECREF(a);
1958         Py_DECREF(b);
1959         return (PyObject *)div;
1960 }
1961
1962 static PyObject *
1963 long_true_divide(PyObject *v, PyObject *w)
1964 {
1965         PyLongObject *a, *b;
1966         double ad, bd;
1967         int aexp, bexp, failed;
1968
1969         CONVERT_BINOP(v, w, &a, &b);
1970         ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
1971         bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
1972         failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
1973         Py_DECREF(a);
1974         Py_DECREF(b);
1975         if (failed)
1976                 return NULL;
1977
1978         if (bd == 0.0) {
1979                 PyErr_SetString(PyExc_ZeroDivisionError,
1980                         "long division or modulo by zero");
1981                 return NULL;
1982         }
1983
1984         /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */
1985         ad /= bd;       /* overflow/underflow impossible here */
1986         aexp -= bexp;
1987         if (aexp > INT_MAX / SHIFT)
1988                 goto overflow;
1989         else if (aexp < -(INT_MAX / SHIFT))
1990                 return PyFloat_FromDouble(0.0); /* underflow to 0 */
1991         errno = 0;
1992         ad = ldexp(ad, aexp * SHIFT);
1993         if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
1994                 goto overflow;
1995         return PyFloat_FromDouble(ad);
1996
1997 overflow:
1998         PyErr_SetString(PyExc_OverflowError,
1999                 "long/long too large for a float");
2000         return NULL;
2001
2002 }
2003
2004 static PyObject *
2005 long_mod(PyObject *v, PyObject *w)
2006 {
2007         PyLongObject *a, *b, *div, *mod;
2008
2009         CONVERT_BINOP(v, w, &a, &b);
2010
2011         if (l_divmod(a, b, &div, &mod) < 0) {
2012                 Py_DECREF(a);
2013                 Py_DECREF(b);
2014                 return NULL;
2015         }
2016         Py_DECREF(a);
2017         Py_DECREF(b);
2018         Py_DECREF(div);
2019         return (PyObject *)mod;
2020 }
2021
2022 static PyObject *
2023 long_divmod(PyObject *v, PyObject *w)
2024 {
2025         PyLongObject *a, *b, *div, *mod;
2026         PyObject *z;
2027
2028         CONVERT_BINOP(v, w, &a, &b);
2029
2030         if (l_divmod(a, b, &div, &mod) < 0) {
2031                 Py_DECREF(a);
2032                 Py_DECREF(b);
2033                 return NULL;
2034         }
2035         z = PyTuple_New(2);
2036         if (z != NULL) {
2037                 PyTuple_SetItem(z, 0, (PyObject *) div);
2038                 PyTuple_SetItem(z, 1, (PyObject *) mod);
2039         }
2040         else {
2041                 Py_DECREF(div);
2042                 Py_DECREF(mod);
2043         }
2044         Py_DECREF(a);
2045         Py_DECREF(b);
2046         return z;
2047 }
2048
2049 static PyObject *
2050 long_pow(PyObject *v, PyObject *w, PyObject *x)
2051 {
2052         PyLongObject *a, *b;
2053         PyObject *c;
2054         PyLongObject *z, *div, *mod;
2055         int size_b, i;
2056
2057         CONVERT_BINOP(v, w, &a, &b);
2058         if (PyLong_Check(x) || Py_None == x) {
2059                 c = x;
2060                 Py_INCREF(x);
2061         }
2062         else if (PyInt_Check(x)) {
2063                 c = PyLong_FromLong(PyInt_AS_LONG(x));
2064         }
2065         else {
2066                 Py_DECREF(a);
2067                 Py_DECREF(b);
2068                 Py_INCREF(Py_NotImplemented);
2069                 return Py_NotImplemented;
2070         }
2071
2072         if (c != Py_None && ((PyLongObject *)c)->ob_size == 0) {
2073                 PyErr_SetString(PyExc_ValueError,
2074                                 "pow() 3rd argument cannot be 0");
2075                 z = NULL;
2076                 goto error;
2077         }
2078
2079         size_b = b->ob_size;
2080         if (size_b < 0) {
2081                 Py_DECREF(a);
2082                 Py_DECREF(b);
2083                 Py_DECREF(c);
2084                 if (x != Py_None) {
2085                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
2086                              "cannot be negative when 3rd argument specified");
2087                         return NULL;
2088                 }
2089                 /* Return a float.  This works because we know that
2090                    this calls float_pow() which converts its
2091                    arguments to double. */
2092                 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
2093         }
2094         z = (PyLongObject *)PyLong_FromLong(1L);
2095         for (i = 0; i < size_b; ++i) {
2096                 digit bi = b->ob_digit[i];
2097                 int j;
2098
2099                 for (j = 0; j < SHIFT; ++j) {
2100                         PyLongObject *temp;
2101
2102                         if (bi & 1) {
2103                                 temp = (PyLongObject *)long_mul(z, a);
2104                                 Py_DECREF(z);
2105                                 if (c!=Py_None && temp!=NULL) {
2106                                         if (l_divmod(temp,(PyLongObject *)c,
2107                                                         &div,&mod) < 0) {
2108                                                 Py_DECREF(temp);
2109                                                 z = NULL;
2110                                                 goto error;
2111                                         }
2112                                         Py_XDECREF(div);
2113                                         Py_DECREF(temp);
2114                                         temp = mod;
2115                                 }
2116                                 z = temp;
2117                                 if (z == NULL)
2118                                         break;
2119                         }
2120                         bi >>= 1;
2121                         if (bi == 0 && i+1 == size_b)
2122                                 break;
2123                         temp = (PyLongObject *)long_mul(a, a);
2124                         Py_DECREF(a);
2125                         if (c!=Py_None && temp!=NULL) {
2126                                 if (l_divmod(temp, (PyLongObject *)c, &div,
2127                                                         &mod) < 0) {
2128                                         Py_DECREF(temp);
2129                                         z = NULL;
2130                                         goto error;
2131                                 }
2132                                 Py_XDECREF(div);
2133                                 Py_DECREF(temp);
2134                                 temp = mod;
2135                         }
2136                         a = temp;
2137                         if (a == NULL) {
2138                                 Py_DECREF(z);
2139                                 z = NULL;
2140                                 break;
2141                         }
2142                 }
2143                 if (a == NULL || z == NULL)
2144                         break;
2145         }
2146         if (c!=Py_None && z!=NULL) {
2147                 if (l_divmod(z, (PyLongObject *)c, &div, &mod) < 0) {
2148                         Py_DECREF(z);
2149                         z = NULL;
2150                 }
2151                 else {
2152                         Py_XDECREF(div);
2153                         Py_DECREF(z);
2154                         z = mod;
2155                 }
2156         }
2157   error:
2158         Py_XDECREF(a);
2159         Py_DECREF(b);
2160         Py_DECREF(c);
2161         return (PyObject *)z;
2162 }
2163
2164 static PyObject *
2165 long_invert(PyLongObject *v)
2166 {
2167         /* Implement ~x as -(x+1) */
2168         PyLongObject *x;
2169         PyLongObject *w;
2170         w = (PyLongObject *)PyLong_FromLong(1L);
2171         if (w == NULL)
2172                 return NULL;
2173         x = (PyLongObject *) long_add(v, w);
2174         Py_DECREF(w);
2175         if (x == NULL)
2176                 return NULL;
2177         x->ob_size = -(x->ob_size);
2178         return (PyObject *)x;
2179 }
2180
2181 static PyObject *
2182 long_pos(PyLongObject *v)
2183 {
2184         if (PyLong_CheckExact(v)) {
2185                 Py_INCREF(v);
2186                 return (PyObject *)v;
2187         }
2188         else
2189                 return _PyLong_Copy(v);
2190 }
2191
2192 static PyObject *
2193 long_neg(PyLongObject *v)
2194 {
2195         PyLongObject *z;
2196         if (v->ob_size == 0 && PyLong_CheckExact(v)) {
2197                 /* -0 == 0 */
2198                 Py_INCREF(v);
2199                 return (PyObject *) v;
2200         }
2201         z = (PyLongObject *)_PyLong_Copy(v);
2202         if (z != NULL)
2203                 z->ob_size = -(v->ob_size);
2204         return (PyObject *)z;
2205 }
2206
2207 static PyObject *
2208 long_abs(PyLongObject *v)
2209 {
2210         if (v->ob_size < 0)
2211                 return long_neg(v);
2212         else
2213                 return long_pos(v);
2214 }
2215
2216 static int
2217 long_nonzero(PyLongObject *v)
2218 {
2219         return ABS(v->ob_size) != 0;
2220 }
2221
2222 static PyObject *
2223 long_rshift(PyLongObject *v, PyLongObject *w)
2224 {
2225         PyLongObject *a, *b;
2226         PyLongObject *z = NULL;
2227         long shiftby;
2228         int newsize, wordshift, loshift, hishift, i, j;
2229         digit lomask, himask;
2230
2231         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2232
2233         if (a->ob_size < 0) {
2234                 /* Right shifting negative numbers is harder */
2235                 PyLongObject *a1, *a2;
2236                 a1 = (PyLongObject *) long_invert(a);
2237                 if (a1 == NULL)
2238                         goto rshift_error;
2239                 a2 = (PyLongObject *) long_rshift(a1, b);
2240                 Py_DECREF(a1);
2241                 if (a2 == NULL)
2242                         goto rshift_error;
2243                 z = (PyLongObject *) long_invert(a2);
2244                 Py_DECREF(a2);
2245         }
2246         else {
2247
2248                 shiftby = PyLong_AsLong((PyObject *)b);
2249                 if (shiftby == -1L && PyErr_Occurred())
2250                         goto rshift_error;
2251                 if (shiftby < 0) {
2252                         PyErr_SetString(PyExc_ValueError,
2253                                         "negative shift count");
2254                         goto rshift_error;
2255                 }
2256                 wordshift = shiftby / SHIFT;
2257                 newsize = ABS(a->ob_size) - wordshift;
2258                 if (newsize <= 0) {
2259                         z = _PyLong_New(0);
2260                         Py_DECREF(a);
2261                         Py_DECREF(b);
2262                         return (PyObject *)z;
2263                 }
2264                 loshift = shiftby % SHIFT;
2265                 hishift = SHIFT - loshift;
2266                 lomask = ((digit)1 << hishift) - 1;
2267                 himask = MASK ^ lomask;
2268                 z = _PyLong_New(newsize);
2269                 if (z == NULL)
2270                         goto rshift_error;
2271                 if (a->ob_size < 0)
2272                         z->ob_size = -(z->ob_size);
2273                 for (i = 0, j = wordshift; i < newsize; i++, j++) {
2274                         z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
2275                         if (i+1 < newsize)
2276                                 z->ob_digit[i] |=
2277                                   (a->ob_digit[j+1] << hishift) & himask;
2278                 }
2279                 z = long_normalize(z);
2280         }
2281 rshift_error:
2282         Py_DECREF(a);
2283         Py_DECREF(b);
2284         return (PyObject *) z;
2285
2286 }
2287
2288 static PyObject *
2289 long_lshift(PyObject *v, PyObject *w)
2290 {
2291         /* This version due to Tim Peters */
2292         PyLongObject *a, *b;
2293         PyLongObject *z = NULL;
2294         long shiftby;
2295         int oldsize, newsize, wordshift, remshift, i, j;
2296         twodigits accum;
2297
2298         CONVERT_BINOP(v, w, &a, &b);
2299
2300         shiftby = PyLong_AsLong((PyObject *)b);
2301         if (shiftby == -1L && PyErr_Occurred())
2302                 goto lshift_error;
2303         if (shiftby < 0) {
2304                 PyErr_SetString(PyExc_ValueError, "negative shift count");
2305                 goto lshift_error;
2306         }
2307         if ((long)(int)shiftby != shiftby) {
2308                 PyErr_SetString(PyExc_ValueError,
2309                                 "outrageous left shift count");
2310                 goto lshift_error;
2311         }
2312         /* wordshift, remshift = divmod(shiftby, SHIFT) */
2313         wordshift = (int)shiftby / SHIFT;
2314         remshift  = (int)shiftby - wordshift * SHIFT;
2315
2316         oldsize = ABS(a->ob_size);
2317         newsize = oldsize + wordshift;
2318         if (remshift)
2319                 ++newsize;
2320         z = _PyLong_New(newsize);
2321         if (z == NULL)
2322                 goto lshift_error;
2323         if (a->ob_size < 0)
2324                 z->ob_size = -(z->ob_size);
2325         for (i = 0; i < wordshift; i++)
2326                 z->ob_digit[i] = 0;
2327         accum = 0;
2328         for (i = wordshift, j = 0; j < oldsize; i++, j++) {
2329                 accum |= (twodigits)a->ob_digit[j] << remshift;
2330                 z->ob_digit[i] = (digit)(accum & MASK);
2331                 accum >>= SHIFT;
2332         }
2333         if (remshift)
2334                 z->ob_digit[newsize-1] = (digit)accum;
2335         else
2336                 assert(!accum);
2337         z = long_normalize(z);
2338 lshift_error:
2339         Py_DECREF(a);
2340         Py_DECREF(b);
2341         return (PyObject *) z;
2342 }
2343
2344
2345 /* Bitwise and/xor/or operations */
2346
2347 static PyObject *
2348 long_bitwise(PyLongObject *a,
2349              int op,  /* '&', '|', '^' */
2350              PyLongObject *b)
2351 {
2352         digit maska, maskb; /* 0 or MASK */
2353         int negz;
2354         int size_a, size_b, size_z;
2355         PyLongObject *z;
2356         int i;
2357         digit diga, digb;
2358         PyObject *v;
2359
2360         if (a->ob_size < 0) {
2361                 a = (PyLongObject *) long_invert(a);
2362                 maska = MASK;
2363         }
2364         else {
2365                 Py_INCREF(a);
2366                 maska = 0;
2367         }
2368         if (b->ob_size < 0) {
2369                 b = (PyLongObject *) long_invert(b);
2370                 maskb = MASK;
2371         }
2372         else {
2373                 Py_INCREF(b);
2374                 maskb = 0;
2375         }
2376
2377         negz = 0;
2378         switch (op) {
2379         case '^':
2380                 if (maska != maskb) {
2381                         maska ^= MASK;
2382                         negz = -1;
2383                 }
2384                 break;
2385         case '&':
2386                 if (maska && maskb) {
2387                         op = '|';
2388                         maska ^= MASK;
2389                         maskb ^= MASK;
2390                         negz = -1;
2391                 }
2392                 break;
2393         case '|':
2394                 if (maska || maskb) {
2395                         op = '&';
2396                         maska ^= MASK;
2397                         maskb ^= MASK;
2398                         negz = -1;
2399                 }
2400                 break;
2401         }
2402
2403         /* JRH: The original logic here was to allocate the result value (z)
2404            as the longer of the two operands.  However, there are some cases
2405            where the result is guaranteed to be shorter than that: AND of two
2406            positives, OR of two negatives: use the shorter number.  AND with
2407            mixed signs: use the positive number.  OR with mixed signs: use the
2408            negative number.  After the transformations above, op will be '&'
2409            iff one of these cases applies, and mask will be non-0 for operands
2410            whose length should be ignored.
2411         */
2412
2413         size_a = a->ob_size;
2414         size_b = b->ob_size;
2415         size_z = op == '&'
2416                 ? (maska
2417                    ? size_b
2418                    : (maskb ? size_a : MIN(size_a, size_b)))
2419                 : MAX(size_a, size_b);
2420         z = _PyLong_New(size_z);
2421         if (a == NULL || b == NULL || z == NULL) {
2422                 Py_XDECREF(a);
2423                 Py_XDECREF(b);
2424                 Py_XDECREF(z);
2425                 return NULL;
2426         }
2427
2428         for (i = 0; i < size_z; ++i) {
2429                 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
2430                 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
2431                 switch (op) {
2432                 case '&': z->ob_digit[i] = diga & digb; break;
2433                 case '|': z->ob_digit[i] = diga | digb; break;
2434                 case '^': z->ob_digit[i] = diga ^ digb; break;
2435                 }
2436         }
2437
2438         Py_DECREF(a);
2439         Py_DECREF(b);
2440         z = long_normalize(z);
2441         if (negz == 0)
2442                 return (PyObject *) z;
2443         v = long_invert(z);
2444         Py_DECREF(z);
2445         return v;
2446 }
2447
2448 static PyObject *
2449 long_and(PyObject *v, PyObject *w)
2450 {
2451         PyLongObject *a, *b;
2452         PyObject *c;
2453         CONVERT_BINOP(v, w, &a, &b);
2454         c = long_bitwise(a, '&', b);
2455         Py_DECREF(a);
2456         Py_DECREF(b);
2457         return c;
2458 }
2459
2460 static PyObject *
2461 long_xor(PyObject *v, PyObject *w)
2462 {
2463         PyLongObject *a, *b;
2464         PyObject *c;
2465         CONVERT_BINOP(v, w, &a, &b);
2466         c = long_bitwise(a, '^', b);
2467         Py_DECREF(a);
2468         Py_DECREF(b);
2469         return c;
2470 }
2471
2472 static PyObject *
2473 long_or(PyObject *v, PyObject *w)
2474 {
2475         PyLongObject *a, *b;
2476         PyObject *c;
2477         CONVERT_BINOP(v, w, &a, &b);
2478         c = long_bitwise(a, '|', b);
2479         Py_DECREF(a);
2480         Py_DECREF(b);
2481         return c;
2482 }
2483
2484 static int
2485 long_coerce(PyObject **pv, PyObject **pw)
2486 {
2487         if (PyInt_Check(*pw)) {
2488                 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
2489                 Py_INCREF(*pv);
2490                 return 0;
2491         }
2492         else if (PyLong_Check(*pw)) {
2493                 Py_INCREF(*pv);
2494                 Py_INCREF(*pw);
2495                 return 0;
2496         }
2497         return 1; /* Can't do it */
2498 }
2499
2500 static PyObject *
2501 long_long(PyObject *v)
2502 {
2503         Py_INCREF(v);
2504         return v;
2505 }
2506
2507 static PyObject *
2508 long_int(PyObject *v)
2509 {
2510         long x;
2511         x = PyLong_AsLong(v);
2512         if (PyErr_Occurred()) {
2513                 if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
2514                                 PyErr_Clear();
2515                                 if (PyLong_CheckExact(v)) {
2516                                         Py_INCREF(v);
2517                                         return v;
2518                                 }
2519                                 else
2520                                         return _PyLong_Copy((PyLongObject *)v);
2521                 }
2522                 else
2523                         return NULL;
2524         }
2525         return PyInt_FromLong(x);
2526 }
2527
2528 static PyObject *
2529 long_float(PyObject *v)
2530 {
2531         double result;
2532         result = PyLong_AsDouble(v);
2533         if (result == -1.0 && PyErr_Occurred())
2534                 return NULL;
2535         return PyFloat_FromDouble(result);
2536 }
2537
2538 static PyObject *
2539 long_oct(PyObject *v)
2540 {
2541         return long_format(v, 8, 1);
2542 }
2543
2544 static PyObject *
2545 long_hex(PyObject *v)
2546 {
2547         return long_format(v, 16, 1);
2548 }
2549
2550 static PyObject *
2551 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
2552
2553 static PyObject *
2554 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2555 {
2556         PyObject *x = NULL;
2557         int base = -909;                     /* unlikely! */
2558         static char *kwlist[] = {"x", "base", 0};
2559
2560         if (type != &PyLong_Type)
2561                 return long_subtype_new(type, args, kwds); /* Wimp out */
2562         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
2563                                          &x, &base))
2564                 return NULL;
2565         if (x == NULL)
2566                 return PyLong_FromLong(0L);
2567         if (base == -909)
2568                 return PyNumber_Long(x);
2569         else if (PyString_Check(x))
2570                 return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
2571 #ifdef Py_USING_UNICODE
2572         else if (PyUnicode_Check(x))
2573                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
2574                                           PyUnicode_GET_SIZE(x),
2575                                           base);
2576 #endif
2577         else {
2578                 PyErr_SetString(PyExc_TypeError,
2579                         "long() can't convert non-string with explicit base");
2580                 return NULL;
2581         }
2582 }
2583
2584 /* Wimpy, slow approach to tp_new calls for subtypes of long:
2585    first create a regular long from whatever arguments we got,
2586    then allocate a subtype instance and initialize it from
2587    the regular long.  The regular long is then thrown away.
2588 */
2589 static PyObject *
2590 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2591 {
2592         PyLongObject *tmp, *new;
2593         int i, n;
2594
2595         assert(PyType_IsSubtype(type, &PyLong_Type));
2596         tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
2597         if (tmp == NULL)
2598                 return NULL;
2599         assert(PyLong_CheckExact(tmp));
2600         n = tmp->ob_size;
2601         if (n < 0)
2602                 n = -n;
2603         new = (PyLongObject *)type->tp_alloc(type, n);
2604         if (new == NULL)
2605                 return NULL;
2606         assert(PyLong_Check(new));
2607         new->ob_size = tmp->ob_size;
2608         for (i = 0; i < n; i++)
2609                 new->ob_digit[i] = tmp->ob_digit[i];
2610         Py_DECREF(tmp);
2611         return (PyObject *)new;
2612 }
2613
2614 PyDoc_STRVAR(long_doc,
2615 "long(x[, base]) -> integer\n\
2616 \n\
2617 Convert a string or number to a long integer, if possible.  A floating\n\
2618 point argument will be truncated towards zero (this does not include a\n\
2619 string representation of a floating point number!)  When converting a\n\
2620 string, use the optional base.  It is an error to supply a base when\n\
2621 converting a non-string.");
2622
2623 static PyNumberMethods long_as_number = {
2624         (binaryfunc)    long_add,       /*nb_add*/
2625         (binaryfunc)    long_sub,       /*nb_subtract*/
2626         (binaryfunc)    long_mul,       /*nb_multiply*/
2627         (binaryfunc)    long_classic_div, /*nb_divide*/
2628         (binaryfunc)    long_mod,       /*nb_remainder*/
2629         (binaryfunc)    long_divmod,    /*nb_divmod*/
2630         (ternaryfunc)   long_pow,       /*nb_power*/
2631         (unaryfunc)     long_neg,       /*nb_negative*/
2632         (unaryfunc)     long_pos,       /*tp_positive*/
2633         (unaryfunc)     long_abs,       /*tp_absolute*/
2634         (inquiry)       long_nonzero,   /*tp_nonzero*/
2635         (unaryfunc)     long_invert,    /*nb_invert*/
2636         (binaryfunc)    long_lshift,    /*nb_lshift*/
2637         (binaryfunc)    long_rshift,    /*nb_rshift*/
2638         (binaryfunc)    long_and,       /*nb_and*/
2639         (binaryfunc)    long_xor,       /*nb_xor*/
2640         (binaryfunc)    long_or,        /*nb_or*/
2641         (coercion)      long_coerce,    /*nb_coerce*/
2642         (unaryfunc)     long_int,       /*nb_int*/
2643         (unaryfunc)     long_long,      /*nb_long*/
2644         (unaryfunc)     long_float,     /*nb_float*/
2645         (unaryfunc)     long_oct,       /*nb_oct*/
2646         (unaryfunc)     long_hex,       /*nb_hex*/
2647         0,                              /* nb_inplace_add */
2648         0,                              /* nb_inplace_subtract */
2649         0,                              /* nb_inplace_multiply */
2650         0,                              /* nb_inplace_divide */
2651         0,                              /* nb_inplace_remainder */
2652         0,                              /* nb_inplace_power */
2653         0,                              /* nb_inplace_lshift */
2654         0,                              /* nb_inplace_rshift */
2655         0,                              /* nb_inplace_and */
2656         0,                              /* nb_inplace_xor */
2657         0,                              /* nb_inplace_or */
2658         (binaryfunc)long_div,           /* nb_floor_divide */
2659         long_true_divide,               /* nb_true_divide */
2660         0,                              /* nb_inplace_floor_divide */
2661         0,                              /* nb_inplace_true_divide */
2662 };
2663
2664 PyTypeObject PyLong_Type = {
2665         PyObject_HEAD_INIT(&PyType_Type)
2666         0,                                      /* ob_size */
2667         "long",                                 /* tp_name */
2668         sizeof(PyLongObject) - sizeof(digit),   /* tp_basicsize */
2669         sizeof(digit),                          /* tp_itemsize */
2670         (destructor)long_dealloc,               /* tp_dealloc */
2671         0,                                      /* tp_print */
2672         0,                                      /* tp_getattr */
2673         0,                                      /* tp_setattr */
2674         (cmpfunc)long_compare,                  /* tp_compare */
2675         (reprfunc)long_repr,                    /* tp_repr */
2676         &long_as_number,                        /* tp_as_number */
2677         0,                                      /* tp_as_sequence */
2678         0,                                      /* tp_as_mapping */
2679         (hashfunc)long_hash,                    /* tp_hash */
2680         0,                                      /* tp_call */
2681         (reprfunc)long_str,                     /* tp_str */
2682         PyObject_GenericGetAttr,                /* tp_getattro */
2683         0,                                      /* tp_setattro */
2684         0,                                      /* tp_as_buffer */
2685         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
2686                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
2687         long_doc,                               /* tp_doc */
2688         0,                                      /* tp_traverse */
2689         0,                                      /* tp_clear */
2690         0,                                      /* tp_richcompare */
2691         0,                                      /* tp_weaklistoffset */
2692         0,                                      /* tp_iter */
2693         0,                                      /* tp_iternext */
2694         0,                                      /* tp_methods */
2695         0,                                      /* tp_members */
2696         0,                                      /* tp_getset */
2697         0,                                      /* tp_base */
2698         0,                                      /* tp_dict */
2699         0,                                      /* tp_descr_get */
2700         0,                                      /* tp_descr_set */
2701         0,                                      /* tp_dictoffset */
2702         0,                                      /* tp_init */
2703         0,                                      /* tp_alloc */
2704         long_new,                               /* tp_new */
2705         PyObject_Del,                           /* tp_free */
2706 };