Objects/longobject.c

   1
   2
   3 /* Long (arbitrary precision) integer object implementation */
   4
   5 /* XXX The functional organization of this file is terrible */
   6
   7 #include "Python.h"
   8 #include "longintrepr.h"
   9
  10 #include <ctype.h>
  11
  12 /* For long multiplication, use the O(N**2) school algorithm unless
  13  * both operands contain more than KARATSUBA_CUTOFF digits (this
  14  * being an internal Python long digit, in base BASE).
  15  */
  16 #define KARATSUBA_CUTOFF 70
  17 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
  18
  19 /* For exponentiation, use the binary left-to-right algorithm
  20  * unless the exponent contains more than FIVEARY_CUTOFF digits.
  21  * In that case, do 5 bits at a time.  The potential drawback is that
  22  * a table of 2**5 intermediate results is computed.
  23  */
  24 #define FIVEARY_CUTOFF 8
  25
  26 #define ABS(x) ((x) < 0 ? -(x) : (x))
  27
  28 #undef MIN
  29 #undef MAX
  30 #define MAX(x, y) ((x) < (y) ? (y) : (x))
  31 #define MIN(x, y) ((x) > (y) ? (y) : (x))
  32
  33 /* Forward */
  34 static PyLongObject *long_normalize(PyLongObject *);
  35 static PyLongObject *mul1(PyLongObject *, wdigit);
  36 static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
  37 static PyLongObject *divrem1(PyLongObject *, digit, digit *);
  38 static PyObject *long_format(PyObject *aa, int base, int addL);
  39
  40 #define SIGCHECK(PyTryBlock) \
  41         if (--_Py_Ticker < 0) { \
  42                 _Py_Ticker = _Py_CheckInterval; \
  43                 if (PyErr_CheckSignals()) PyTryBlock \
  44         }
  45
  46 /* Normalize (remove leading zeros from) a long int object.
  47    Doesn't attempt to free the storage--in most cases, due to the nature
  48    of the algorithms used, this could save at most be one word anyway. */
  49
  50 static PyLongObject *
  51 long_normalize(register PyLongObject *v)
  52 {
  53         Py_ssize_t j = ABS(v->ob_size);
  54         Py_ssize_t i = j;
  55
  56         while (i > 0 && v->ob_digit[i-1] == 0)
  57                 --i;
  58         if (i != j)
  59                 v->ob_size = (v->ob_size < 0) ? -(i) : i;
  60         return v;
  61 }
  62
  63 /* Allocate a new long int object with size digits.
  64    Return NULL and set exception if we run out of memory. */
  65
  66 PyLongObject *
  67 _PyLong_New(Py_ssize_t size)
  68 {
  69         if (size > PY_SSIZE_T_MAX) {
  70                 PyErr_NoMemory();
  71                 return NULL;
  72         }
  73         return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
  74 }
  75
  76 PyObject *
  77 _PyLong_Copy(PyLongObject *src)
  78 {
  79         PyLongObject *result;
  80         Py_ssize_t i;
  81
  82         assert(src != NULL);
  83         i = src->ob_size;
  84         if (i < 0)
  85                 i = -(i);
  86         result = _PyLong_New(i);
  87         if (result != NULL) {
  88                 result->ob_size = src->ob_size;
  89                 while (--i >= 0)
  90                         result->ob_digit[i] = src->ob_digit[i];
  91         }
  92         return (PyObject *)result;
  93 }
  94
  95 /* Create a new long int object from a C long int */
  96
  97 PyObject *
  98 PyLong_FromLong(long ival)
  99 {
 100         PyLongObject *v;
 101         unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
 102         int ndigits = 0;
 103         int negative = 0;
 104
 105         if (ival < 0) {
 106                 ival = -ival;
 107                 negative = 1;
 108         }
 109
 110         /* Count the number of Python digits.
 111            We used to pick 5 ("big enough for anything"), but that's a
 112            waste of time and space given that 5*15 = 75 bits are rarely
 113            needed. */
 114         t = (unsigned long)ival;
 115         while (t) {
 116                 ++ndigits;
 117                 t >>= SHIFT;
 118         }
 119         v = _PyLong_New(ndigits);
 120         if (v != NULL) {
 121                 digit *p = v->ob_digit;
 122                 v->ob_size = negative ? -ndigits : ndigits;
 123                 t = (unsigned long)ival;
 124                 while (t) {
 125                         *p++ = (digit)(t & MASK);
 126                         t >>= SHIFT;
 127                 }
 128         }
 129         return (PyObject *)v;
 130 }
 131
 132 /* Create a new long int object from a C unsigned long int */
 133
 134 PyObject *
 135 PyLong_FromUnsignedLong(unsigned long ival)
 136 {
 137         PyLongObject *v;
 138         unsigned long t;
 139         int ndigits = 0;
 140
 141         /* Count the number of Python digits. */
 142         t = (unsigned long)ival;
 143         while (t) {
 144                 ++ndigits;
 145                 t >>= SHIFT;
 146         }
 147         v = _PyLong_New(ndigits);
 148         if (v != NULL) {
 149                 digit *p = v->ob_digit;
 150                 v->ob_size = ndigits;
 151                 while (ival) {
 152                         *p++ = (digit)(ival & MASK);
 153                         ival >>= SHIFT;
 154                 }
 155         }
 156         return (PyObject *)v;
 157 }
 158
 159 /* Create a new long int object from a C double */
 160
 161 PyObject *
 162 PyLong_FromDouble(double dval)
 163 {
 164         PyLongObject *v;
 165         double frac;
 166         int i, ndig, expo, neg;
 167         neg = 0;
 168         if (Py_IS_INFINITY(dval)) {
 169                 PyErr_SetString(PyExc_OverflowError,
 170                         "cannot convert float infinity to long");
 171                 return NULL;
 172         }
 173         if (dval < 0.0) {
 174                 neg = 1;
 175                 dval = -dval;
 176         }
 177         frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
 178         if (expo <= 0)
 179                 return PyLong_FromLong(0L);
 180         ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
 181         v = _PyLong_New(ndig);
 182         if (v == NULL)
 183                 return NULL;
 184         frac = ldexp(frac, (expo-1) % SHIFT + 1);
 185         for (i = ndig; --i >= 0; ) {
 186                 long bits = (long)frac;
 187                 v->ob_digit[i] = (digit) bits;
 188                 frac = frac - (double)bits;
 189                 frac = ldexp(frac, SHIFT);
 190         }
 191         if (neg)
 192                 v->ob_size = -(v->ob_size);
 193         return (PyObject *)v;
 194 }
 195
 196 /* Get a C long int from a long int object.
 197    Returns -1 and sets an error condition if overflow occurs. */
 198
 199 long
 200 PyLong_AsLong(PyObject *vv)
 201 {
 202         /* This version by Tim Peters */
 203         register PyLongObject *v;
 204         unsigned long x, prev;
 205         Py_ssize_t i;
 206         int sign;
 207
 208         if (vv == NULL || !PyLong_Check(vv)) {
 209                 if (vv != NULL && PyInt_Check(vv))
 210                         return PyInt_AsLong(vv);
 211                 PyErr_BadInternalCall();
 212                 return -1;
 213         }
 214         v = (PyLongObject *)vv;
 215         i = v->ob_size;
 216         sign = 1;
 217         x = 0;
 218         if (i < 0) {
 219                 sign = -1;
 220                 i = -(i);
 221         }
 222         while (--i >= 0) {
 223                 prev = x;
 224                 x = (x << SHIFT) + v->ob_digit[i];
 225                 if ((x >> SHIFT) != prev)
 226                         goto overflow;
 227         }
 228         /* Haven't lost any bits, but if the sign bit is set we're in
 229          * trouble *unless* this is the min negative number.  So,
 230          * trouble iff sign bit set && (positive || some bit set other
 231          * than the sign bit).
 232          */
 233         if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
 234                 goto overflow;
 235         return (long)x * sign;
 236
 237  overflow:
 238         PyErr_SetString(PyExc_OverflowError,
 239                         "long int too large to convert to int");
 240         return -1;
 241 }
 242
 243 static Py_ssize_t
 244 _long_as_ssize_t(PyObject *vv) {
 245         register PyLongObject *v;
 246         size_t x, prev;
 247         Py_ssize_t i;
 248         int sign;
 249
 250         if (vv == NULL || !PyLong_Check(vv)) {
 251                 PyErr_BadInternalCall();
 252                 return -1;
 253         }
 254         v = (PyLongObject *)vv;
 255         i = v->ob_size;
 256         sign = 1;
 257         x = 0;
 258         if (i < 0) {
 259                 sign = -1;
 260                 i = -(i);
 261         }
 262         while (--i >= 0) {
 263                 prev = x;
 264                 x = (x << SHIFT) + v->ob_digit[i];
 265                 if ((x >> SHIFT) != prev)
 266                         goto overflow;
 267         }
 268         /* Haven't lost any bits, but if the sign bit is set we're in
 269          * trouble *unless* this is the min negative number.  So,
 270          * trouble iff sign bit set && (positive || some bit set other
 271          * than the sign bit).
 272          */
 273         if ((Py_ssize_t)x < 0 && (sign > 0 || (x << 1) != 0))
 274                 goto overflow;
 275         return (Py_ssize_t)x * sign;
 276
 277  overflow:
 278         PyErr_SetString(PyExc_OverflowError,
 279                         "long int too large to convert to int");
 280         if (sign > 0)
 281                 return PY_SSIZE_T_MAX;
 282         else
 283                 return PY_SSIZE_T_MIN;
 284 }
 285
 286 /* Get a Py_ssize_t from a long int object.
 287    Returns -1 and sets an error condition if overflow occurs. */
 288
 289 Py_ssize_t
 290 _PyLong_AsSsize_t(PyObject *vv)
 291 {
 292         Py_ssize_t x;
 293
 294         x = _long_as_ssize_t(vv);
 295         if (PyErr_Occurred()) return -1;
 296         return x;
 297 }
 298
 299
 300 /* Get a Py_ssize_t from a long int object.
 301    Silently reduce values larger than PY_SSIZE_T_MAX to PY_SSIZE_T_MAX,
 302    and silently boost values less than -PY_SSIZE_T_MAX-1 to -PY_SSIZE_T_MAX-1.
 303    On error, return -1 with an exception set.
 304 */
 305
 306 static Py_ssize_t
 307 long_index(PyObject *vv)
 308 {
 309         Py_ssize_t x;
 310
 311         x = _long_as_ssize_t(vv);
 312         if (PyErr_Occurred()) {
 313                 /* If overflow error, ignore the error */
 314                 if (x != -1) {
 315                         PyErr_Clear();
 316                 }
 317         }
 318         return x;
 319 }
 320
 321 /* Get a C unsigned long int from a long int object.
 322    Returns -1 and sets an error condition if overflow occurs. */
 323
 324 unsigned long
 325 PyLong_AsUnsignedLong(PyObject *vv)
 326 {
 327         register PyLongObject *v;
 328         unsigned long x, prev;
 329         Py_ssize_t i;
 330
 331         if (vv == NULL || !PyLong_Check(vv)) {
 332                 if (vv != NULL && PyInt_Check(vv)) {
 333                         long val = PyInt_AsLong(vv);
 334                         if (val < 0) {
 335                                 PyErr_SetString(PyExc_OverflowError,
 336                                 "can't convert negative value to unsigned long");
 337                                 return (unsigned long) -1;
 338                         }
 339                         return val;
 340                 }
 341                 PyErr_BadInternalCall();
 342                 return (unsigned long) -1;
 343         }
 344         v = (PyLongObject *)vv;
 345         i = v->ob_size;
 346         x = 0;
 347         if (i < 0) {
 348                 PyErr_SetString(PyExc_OverflowError,
 349                            "can't convert negative value to unsigned long");
 350                 return (unsigned long) -1;
 351         }
 352         while (--i >= 0) {
 353                 prev = x;
 354                 x = (x << SHIFT) + v->ob_digit[i];
 355                 if ((x >> SHIFT) != prev) {
 356                         PyErr_SetString(PyExc_OverflowError,
 357                                 "long int too large to convert");
 358                         return (unsigned long) -1;
 359                 }
 360         }
 361         return x;
 362 }
 363
 364 /* Get a C unsigned long int from a long int object, ignoring the high bits.
 365    Returns -1 and sets an error condition if an error occurs. */
 366
 367 unsigned long
 368 PyLong_AsUnsignedLongMask(PyObject *vv)
 369 {
 370         register PyLongObject *v;
 371         unsigned long x;
 372         Py_ssize_t i;
 373         int sign;
 374
 375         if (vv == NULL || !PyLong_Check(vv)) {
 376                 if (vv != NULL && PyInt_Check(vv))
 377                         return PyInt_AsUnsignedLongMask(vv);
 378                 PyErr_BadInternalCall();
 379                 return (unsigned long) -1;
 380         }
 381         v = (PyLongObject *)vv;
 382         i = v->ob_size;
 383         sign = 1;
 384         x = 0;
 385         if (i < 0) {
 386                 sign = -1;
 387                 i = -i;
 388         }
 389         while (--i >= 0) {
 390                 x = (x << SHIFT) + v->ob_digit[i];
 391         }
 392         return x * sign;
 393 }
 394
 395 int
 396 _PyLong_Sign(PyObject *vv)
 397 {
 398         PyLongObject *v = (PyLongObject *)vv;
 399
 400         assert(v != NULL);
 401         assert(PyLong_Check(v));
 402
 403         return v->ob_size == 0 ? 0 : (v->ob_size < 0 ? -1 : 1);
 404 }
 405
 406 size_t
 407 _PyLong_NumBits(PyObject *vv)
 408 {
 409         PyLongObject *v = (PyLongObject *)vv;
 410         size_t result = 0;
 411         Py_ssize_t ndigits;
 412
 413         assert(v != NULL);
 414         assert(PyLong_Check(v));
 415         ndigits = ABS(v->ob_size);
 416         assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
 417         if (ndigits > 0) {
 418                 digit msd = v->ob_digit[ndigits - 1];
 419
 420                 result = (ndigits - 1) * SHIFT;
 421                 if (result / SHIFT != (size_t)(ndigits - 1))
 422                         goto Overflow;
 423                 do {
 424                         ++result;
 425                         if (result == 0)
 426                                 goto Overflow;
 427                         msd >>= 1;
 428                 } while (msd);
 429         }
 430         return result;
 431
 432 Overflow:
 433         PyErr_SetString(PyExc_OverflowError, "long has too many bits "
 434                         "to express in a platform size_t");
 435         return (size_t)-1;
 436 }
 437
 438 PyObject *
 439 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
 440                       int little_endian, int is_signed)
 441 {
 442         const unsigned char* pstartbyte;/* LSB of bytes */
 443         int incr;                       /* direction to move pstartbyte */
 444         const unsigned char* pendbyte;  /* MSB of bytes */
 445         size_t numsignificantbytes;     /* number of bytes that matter */
 446         size_t ndigits;                 /* number of Python long digits */
 447         PyLongObject* v;                /* result */
 448         int idigit = 0;                 /* next free index in v->ob_digit */
 449
 450         if (n == 0)
 451                 return PyLong_FromLong(0L);
 452
 453         if (little_endian) {
 454                 pstartbyte = bytes;
 455                 pendbyte = bytes + n - 1;
 456                 incr = 1;
 457         }
 458         else {
 459                 pstartbyte = bytes + n - 1;
 460                 pendbyte = bytes;
 461                 incr = -1;
 462         }
 463
 464         if (is_signed)
 465                 is_signed = *pendbyte >= 0x80;
 466
 467         /* Compute numsignificantbytes.  This consists of finding the most
 468            significant byte.  Leading 0 bytes are insignficant if the number
 469            is positive, and leading 0xff bytes if negative. */
 470         {
 471                 size_t i;
 472                 const unsigned char* p = pendbyte;
 473                 const int pincr = -incr;  /* search MSB to LSB */
 474                 const unsigned char insignficant = is_signed ? 0xff : 0x00;
 475
 476                 for (i = 0; i < n; ++i, p += pincr) {
 477                         if (*p != insignficant)
 478                                 break;
 479                 }
 480                 numsignificantbytes = n - i;
 481                 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
 482                    actually has 2 significant bytes.  OTOH, 0xff0001 ==
 483                    -0x00ffff, so we wouldn't *need* to bump it there; but we
 484                    do for 0xffff = -0x0001.  To be safe without bothering to
 485                    check every case, bump it regardless. */
 486                 if (is_signed && numsignificantbytes < n)
 487                         ++numsignificantbytes;
 488         }
 489
 490         /* How many Python long digits do we need?  We have
 491            8*numsignificantbytes bits, and each Python long digit has SHIFT
 492            bits, so it's the ceiling of the quotient. */
 493         ndigits = (numsignificantbytes * 8 + SHIFT - 1) / SHIFT;
 494         if (ndigits > (size_t)INT_MAX)
 495                 return PyErr_NoMemory();
 496         v = _PyLong_New((int)ndigits);
 497         if (v == NULL)
 498                 return NULL;
 499
 500         /* Copy the bits over.  The tricky parts are computing 2's-comp on
 501            the fly for signed numbers, and dealing with the mismatch between
 502            8-bit bytes and (probably) 15-bit Python digits.*/
 503         {
 504                 size_t i;
 505                 twodigits carry = 1;            /* for 2's-comp calculation */
 506                 twodigits accum = 0;            /* sliding register */
 507                 unsigned int accumbits = 0;     /* number of bits in accum */
 508                 const unsigned char* p = pstartbyte;
 509
 510                 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
 511                         twodigits thisbyte = *p;
 512                         /* Compute correction for 2's comp, if needed. */
 513                         if (is_signed) {
 514                                 thisbyte = (0xff ^ thisbyte) + carry;
 515                                 carry = thisbyte >> 8;
 516                                 thisbyte &= 0xff;
 517                         }
 518                         /* Because we're going LSB to MSB, thisbyte is
 519                            more significant than what's already in accum,
 520                            so needs to be prepended to accum. */
 521                         accum |= thisbyte << accumbits;
 522                         accumbits += 8;
 523                         if (accumbits >= SHIFT) {
 524                                 /* There's enough to fill a Python digit. */
 525                                 assert(idigit < (int)ndigits);
 526                                 v->ob_digit[idigit] = (digit)(accum & MASK);
 527                                 ++idigit;
 528                                 accum >>= SHIFT;
 529                                 accumbits -= SHIFT;
 530                                 assert(accumbits < SHIFT);
 531                         }
 532                 }
 533                 assert(accumbits < SHIFT);
 534                 if (accumbits) {
 535                         assert(idigit < (int)ndigits);
 536                         v->ob_digit[idigit] = (digit)accum;
 537                         ++idigit;
 538                 }
 539         }
 540
 541         v->ob_size = is_signed ? -idigit : idigit;
 542         return (PyObject *)long_normalize(v);
 543 }
 544
 545 int
 546 _PyLong_AsByteArray(PyLongObject* v,
 547                     unsigned char* bytes, size_t n,
 548                     int little_endian, int is_signed)
 549 {
 550         int i;                  /* index into v->ob_digit */
 551         Py_ssize_t ndigits;             /* |v->ob_size| */
 552         twodigits accum;        /* sliding register */
 553         unsigned int accumbits; /* # bits in accum */
 554         int do_twos_comp;       /* store 2's-comp?  is_signed and v < 0 */
 555         twodigits carry;        /* for computing 2's-comp */
 556         size_t j;               /* # bytes filled */
 557         unsigned char* p;       /* pointer to next byte in bytes */
 558         int pincr;              /* direction to move p */
 559
 560         assert(v != NULL && PyLong_Check(v));
 561
 562         if (v->ob_size < 0) {
 563                 ndigits = -(v->ob_size);
 564                 if (!is_signed) {
 565                         PyErr_SetString(PyExc_TypeError,
 566                                 "can't convert negative long to unsigned");
 567                         return -1;
 568                 }
 569                 do_twos_comp = 1;
 570         }
 571         else {
 572                 ndigits = v->ob_size;
 573                 do_twos_comp = 0;
 574         }
 575
 576         if (little_endian) {
 577                 p = bytes;
 578                 pincr = 1;
 579         }
 580         else {
 581                 p = bytes + n - 1;
 582                 pincr = -1;
 583         }
 584
 585         /* Copy over all the Python digits.
 586            It's crucial that every Python digit except for the MSD contribute
 587            exactly SHIFT bits to the total, so first assert that the long is
 588            normalized. */
 589         assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
 590         j = 0;
 591         accum = 0;
 592         accumbits = 0;
 593         carry = do_twos_comp ? 1 : 0;
 594         for (i = 0; i < ndigits; ++i) {
 595                 twodigits thisdigit = v->ob_digit[i];
 596                 if (do_twos_comp) {
 597                         thisdigit = (thisdigit ^ MASK) + carry;
 598                         carry = thisdigit >> SHIFT;
 599                         thisdigit &= MASK;
 600                 }
 601                 /* Because we're going LSB to MSB, thisdigit is more
 602                    significant than what's already in accum, so needs to be
 603                    prepended to accum. */
 604                 accum |= thisdigit << accumbits;
 605                 accumbits += SHIFT;
 606
 607                 /* The most-significant digit may be (probably is) at least
 608                    partly empty. */
 609                 if (i == ndigits - 1) {
 610                         /* Count # of sign bits -- they needn't be stored,
 611                          * although for signed conversion we need later to
 612                          * make sure at least one sign bit gets stored.
 613                          * First shift conceptual sign bit to real sign bit.
 614                          */
 615                         stwodigits s = (stwodigits)(thisdigit <<
 616                                 (8*sizeof(stwodigits) - SHIFT));
 617                         unsigned int nsignbits = 0;
 618                         while ((s < 0) == do_twos_comp && nsignbits < SHIFT) {
 619                                 ++nsignbits;
 620                                 s <<= 1;
 621                         }
 622                         accumbits -= nsignbits;
 623                 }
 624
 625                 /* Store as many bytes as possible. */
 626                 while (accumbits >= 8) {
 627                         if (j >= n)
 628                                 goto Overflow;
 629                         ++j;
 630                         *p = (unsigned char)(accum & 0xff);
 631                         p += pincr;
 632                         accumbits -= 8;
 633                         accum >>= 8;
 634                 }
 635         }
 636
 637         /* Store the straggler (if any). */
 638         assert(accumbits < 8);
 639         assert(carry == 0);  /* else do_twos_comp and *every* digit was 0 */
 640         if (accumbits > 0) {
 641                 if (j >= n)
 642                         goto Overflow;
 643                 ++j;
 644                 if (do_twos_comp) {
 645                         /* Fill leading bits of the byte with sign bits
 646                            (appropriately pretending that the long had an
 647                            infinite supply of sign bits). */
 648                         accum |= (~(twodigits)0) << accumbits;
 649                 }
 650                 *p = (unsigned char)(accum & 0xff);
 651                 p += pincr;
 652         }
 653         else if (j == n && n > 0 && is_signed) {
 654                 /* The main loop filled the byte array exactly, so the code
 655                    just above didn't get to ensure there's a sign bit, and the
 656                    loop below wouldn't add one either.  Make sure a sign bit
 657                    exists. */
 658                 unsigned char msb = *(p - pincr);
 659                 int sign_bit_set = msb >= 0x80;
 660                 assert(accumbits == 0);
 661                 if (sign_bit_set == do_twos_comp)
 662                         return 0;
 663                 else
 664                         goto Overflow;
 665         }
 666
 667         /* Fill remaining bytes with copies of the sign bit. */
 668         {
 669                 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
 670                 for ( ; j < n; ++j, p += pincr)
 671                         *p = signbyte;
 672         }
 673
 674         return 0;
 675
 676 Overflow:
 677         PyErr_SetString(PyExc_OverflowError, "long too big to convert");
 678         return -1;
 679
 680 }
 681
 682 double
 683 _PyLong_AsScaledDouble(PyObject *vv, int *exponent)
 684 {
 685 /* NBITS_WANTED should be > the number of bits in a double's precision,
 686    but small enough so that 2**NBITS_WANTED is within the normal double
 687    range.  nbitsneeded is set to 1 less than that because the most-significant
 688    Python digit contains at least 1 significant bit, but we don't want to
 689    bother counting them (catering to the worst case cheaply).
 690
 691    57 is one more than VAX-D double precision; I (Tim) don't know of a double
 692    format with more precision than that; it's 1 larger so that we add in at
 693    least one round bit to stand in for the ignored least-significant bits.
 694 */
 695 #define NBITS_WANTED 57
 696         PyLongObject *v;
 697         double x;
 698         const double multiplier = (double)(1L << SHIFT);
 699         Py_ssize_t i;
 700         int sign;
 701         int nbitsneeded;
 702
 703         if (vv == NULL || !PyLong_Check(vv)) {
 704                 PyErr_BadInternalCall();
 705                 return -1;
 706         }
 707         v = (PyLongObject *)vv;
 708         i = v->ob_size;
 709         sign = 1;
 710         if (i < 0) {
 711                 sign = -1;
 712                 i = -(i);
 713         }
 714         else if (i == 0) {
 715                 *exponent = 0;
 716                 return 0.0;
 717         }
 718         --i;
 719         x = (double)v->ob_digit[i];
 720         nbitsneeded = NBITS_WANTED - 1;
 721         /* Invariant:  i Python digits remain unaccounted for. */
 722         while (i > 0 && nbitsneeded > 0) {
 723                 --i;
 724                 x = x * multiplier + (double)v->ob_digit[i];
 725                 nbitsneeded -= SHIFT;
 726         }
 727         /* There are i digits we didn't shift in.  Pretending they're all
 728            zeroes, the true value is x * 2**(i*SHIFT). */
 729         *exponent = i;
 730         assert(x > 0.0);
 731         return x * sign;
 732 #undef NBITS_WANTED
 733 }
 734
 735 /* Get a C double from a long int object. */
 736
 737 double
 738 PyLong_AsDouble(PyObject *vv)
 739 {
 740         int e = -1;
 741         double x;
 742
 743         if (vv == NULL || !PyLong_Check(vv)) {
 744                 PyErr_BadInternalCall();
 745                 return -1;
 746         }
 747         x = _PyLong_AsScaledDouble(vv, &e);
 748         if (x == -1.0 && PyErr_Occurred())
 749                 return -1.0;
 750         /* 'e' initialized to -1 to silence gcc-4.0.x, but it should be
 751            set correctly after a successful _PyLong_AsScaledDouble() call */
 752         assert(e >= 0);
 753         if (e > INT_MAX / SHIFT)
 754                 goto overflow;
 755         errno = 0;
 756         x = ldexp(x, e * SHIFT);
 757         if (Py_OVERFLOWED(x))
 758                 goto overflow;
 759         return x;
 760
 761 overflow:
 762         PyErr_SetString(PyExc_OverflowError,
 763                 "long int too large to convert to float");
 764         return -1.0;
 765 }
 766
 767 /* Create a new long (or int) object from a C pointer */
 768
 769 PyObject *
 770 PyLong_FromVoidPtr(void *p)
 771 {
 772 #if SIZEOF_VOID_P <= SIZEOF_LONG
 773         if ((long)p < 0)
 774                 return PyLong_FromUnsignedLong((unsigned long)p);
 775         return PyInt_FromLong((long)p);
 776 #else
 777
 778 #ifndef HAVE_LONG_LONG
 779 #   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 780 #endif
 781 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 782 #   error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
 783 #endif
 784         /* optimize null pointers */
 785         if (p == NULL)
 786                 return PyInt_FromLong(0);
 787         return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);
 788
 789 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 790 }
 791
 792 /* Get a C pointer from a long object (or an int object in some cases) */
 793
 794 void *
 795 PyLong_AsVoidPtr(PyObject *vv)
 796 {
 797         /* This function will allow int or long objects. If vv is neither,
 798            then the PyLong_AsLong*() functions will raise the exception:
 799            PyExc_SystemError, "bad argument to internal function"
 800         */
 801 #if SIZEOF_VOID_P <= SIZEOF_LONG
 802         long x;
 803
 804         if (PyInt_Check(vv))
 805                 x = PyInt_AS_LONG(vv);
 806         else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
 807                 x = PyLong_AsLong(vv);
 808         else
 809                 x = PyLong_AsUnsignedLong(vv);
 810 #else
 811
 812 #ifndef HAVE_LONG_LONG
 813 #   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 814 #endif
 815 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 816 #   error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
 817 #endif
 818         PY_LONG_LONG x;
 819
 820         if (PyInt_Check(vv))
 821                 x = PyInt_AS_LONG(vv);
 822         else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
 823                 x = PyLong_AsLongLong(vv);
 824         else
 825                 x = PyLong_AsUnsignedLongLong(vv);
 826
 827 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 828
 829         if (x == -1 && PyErr_Occurred())
 830                 return NULL;
 831         return (void *)x;
 832 }
 833
 834 #ifdef HAVE_LONG_LONG
 835
 836 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
 837  * rewritten to use the newer PyLong_{As,From}ByteArray API.
 838  */
 839
 840 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
 841
 842 /* Create a new long int object from a C PY_LONG_LONG int. */
 843
 844 PyObject *
 845 PyLong_FromLongLong(PY_LONG_LONG ival)
 846 {
 847         PyLongObject *v;
 848         unsigned PY_LONG_LONG t;  /* unsigned so >> doesn't propagate sign bit */
 849         int ndigits = 0;
 850         int negative = 0;
 851
 852         if (ival < 0) {
 853                 ival = -ival;
 854                 negative = 1;
 855         }
 856
 857         /* Count the number of Python digits.
 858            We used to pick 5 ("big enough for anything"), but that's a
 859            waste of time and space given that 5*15 = 75 bits are rarely
 860            needed. */
 861         t = (unsigned PY_LONG_LONG)ival;
 862         while (t) {
 863                 ++ndigits;
 864                 t >>= SHIFT;
 865         }
 866         v = _PyLong_New(ndigits);
 867         if (v != NULL) {
 868                 digit *p = v->ob_digit;
 869                 v->ob_size = negative ? -ndigits : ndigits;
 870                 t = (unsigned PY_LONG_LONG)ival;
 871                 while (t) {
 872                         *p++ = (digit)(t & MASK);
 873                         t >>= SHIFT;
 874                 }
 875         }
 876         return (PyObject *)v;
 877 }
 878
 879 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
 880
 881 PyObject *
 882 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
 883 {
 884         PyLongObject *v;
 885         unsigned PY_LONG_LONG t;
 886         int ndigits = 0;
 887
 888         /* Count the number of Python digits. */
 889         t = (unsigned PY_LONG_LONG)ival;
 890         while (t) {
 891                 ++ndigits;
 892                 t >>= SHIFT;
 893         }
 894         v = _PyLong_New(ndigits);
 895         if (v != NULL) {
 896                 digit *p = v->ob_digit;
 897                 v->ob_size = ndigits;
 898                 while (ival) {
 899                         *p++ = (digit)(ival & MASK);
 900                         ival >>= SHIFT;
 901                 }
 902         }
 903         return (PyObject *)v;
 904 }
 905
 906 /* Create a new long int object from a C Py_ssize_t. */
 907
 908 PyObject *
 909 _PyLong_FromSsize_t(Py_ssize_t ival)
 910 {
 911         Py_ssize_t bytes = ival;
 912         int one = 1;
 913         return _PyLong_FromByteArray(
 914                         (unsigned char *)&bytes,
 915                         SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
 916 }
 917
 918 /* Create a new long int object from a C size_t. */
 919
 920 PyObject *
 921 _PyLong_FromSize_t(size_t ival)
 922 {
 923         size_t bytes = ival;
 924         int one = 1;
 925         return _PyLong_FromByteArray(
 926                         (unsigned char *)&bytes,
 927                         SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
 928 }
 929
 930 /* Get a C PY_LONG_LONG int from a long int object.
 931    Return -1 and set an error if overflow occurs. */
 932
 933 PY_LONG_LONG
 934 PyLong_AsLongLong(PyObject *vv)
 935 {
 936         PY_LONG_LONG bytes;
 937         int one = 1;
 938         int res;
 939
 940         if (vv == NULL) {
 941                 PyErr_BadInternalCall();
 942                 return -1;
 943         }
 944         if (!PyLong_Check(vv)) {
 945                 PyNumberMethods *nb;
 946                 PyObject *io;
 947                 if (PyInt_Check(vv))
 948                         return (PY_LONG_LONG)PyInt_AsLong(vv);
 949                 if ((nb = vv->ob_type->tp_as_number) == NULL ||
 950                     nb->nb_int == NULL) {
 951                         PyErr_SetString(PyExc_TypeError, "an integer is required");
 952                         return -1;
 953                 }
 954                 io = (*nb->nb_int) (vv);
 955                 if (io == NULL)
 956                         return -1;
 957                 if (PyInt_Check(io)) {
 958                         bytes = PyInt_AsLong(io);
 959                         Py_DECREF(io);
 960                         return bytes;
 961                 }
 962                 if (PyLong_Check(io)) {
 963                         bytes = PyLong_AsLongLong(io);
 964                         Py_DECREF(io);
 965                         return bytes;
 966                 }
 967                 Py_DECREF(io);
 968                 PyErr_SetString(PyExc_TypeError, "integer conversion failed");
 969                 return -1;
 970         }
 971
 972         res = _PyLong_AsByteArray(
 973                         (PyLongObject *)vv, (unsigned char *)&bytes,
 974                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
 975
 976         /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
 977         if (res < 0)
 978                 return (PY_LONG_LONG)-1;
 979         else
 980                 return bytes;
 981 }
 982
 983 /* Get a C unsigned PY_LONG_LONG int from a long int object.
 984    Return -1 and set an error if overflow occurs. */
 985
 986 unsigned PY_LONG_LONG
 987 PyLong_AsUnsignedLongLong(PyObject *vv)
 988 {
 989         unsigned PY_LONG_LONG bytes;
 990         int one = 1;
 991         int res;
 992
 993         if (vv == NULL || !PyLong_Check(vv)) {
 994                 PyErr_BadInternalCall();
 995                 return (unsigned PY_LONG_LONG)-1;
 996         }
 997
 998         res = _PyLong_AsByteArray(
 999                         (PyLongObject *)vv, (unsigned char *)&bytes,
1000                         SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
1001
1002         /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
1003         if (res < 0)
1004                 return (unsigned PY_LONG_LONG)res;
1005         else
1006                 return bytes;
1007 }
1008
1009 /* Get a C unsigned long int from a long int object, ignoring the high bits.
1010    Returns -1 and sets an error condition if an error occurs. */
1011
1012 unsigned PY_LONG_LONG
1013 PyLong_AsUnsignedLongLongMask(PyObject *vv)
1014 {
1015         register PyLongObject *v;
1016         unsigned PY_LONG_LONG x;
1017         Py_ssize_t i;
1018         int sign;
1019
1020         if (vv == NULL || !PyLong_Check(vv)) {
1021                 PyErr_BadInternalCall();
1022                 return (unsigned long) -1;
1023         }
1024         v = (PyLongObject *)vv;
1025         i = v->ob_size;
1026         sign = 1;
1027         x = 0;
1028         if (i < 0) {
1029                 sign = -1;
1030                 i = -i;
1031         }
1032         while (--i >= 0) {
1033                 x = (x << SHIFT) + v->ob_digit[i];
1034         }
1035         return x * sign;
1036 }
1037 #undef IS_LITTLE_ENDIAN
1038
1039 #endif /* HAVE_LONG_LONG */
1040
1041
1042 static int
1043 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
1044         if (PyLong_Check(v)) {
1045                 *a = (PyLongObject *) v;
1046                 Py_INCREF(v);
1047         }
1048         else if (PyInt_Check(v)) {
1049                 *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
1050         }
1051         else {
1052                 return 0;
1053         }
1054         if (PyLong_Check(w)) {
1055                 *b = (PyLongObject *) w;
1056                 Py_INCREF(w);
1057         }
1058         else if (PyInt_Check(w)) {
1059                 *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
1060         }
1061         else {
1062                 Py_DECREF(*a);
1063                 return 0;
1064         }
1065         return 1;
1066 }
1067
1068 #define CONVERT_BINOP(v, w, a, b) \
1069         if (!convert_binop(v, w, a, b)) { \
1070                 Py_INCREF(Py_NotImplemented); \
1071                 return Py_NotImplemented; \
1072         }
1073
1074 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
1075  * is modified in place, by adding y to it.  Carries are propagated as far as
1076  * x[m-1], and the remaining carry (0 or 1) is returned.
1077  */
1078 static digit
1079 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1080 {
1081         int i;
1082         digit carry = 0;
1083
1084         assert(m >= n);
1085         for (i = 0; i < n; ++i) {
1086                 carry += x[i] + y[i];
1087                 x[i] = carry & MASK;
1088                 carry >>= SHIFT;
1089                 assert((carry & 1) == carry);
1090         }
1091         for (; carry && i < m; ++i) {
1092                 carry += x[i];
1093                 x[i] = carry & MASK;
1094                 carry >>= SHIFT;
1095                 assert((carry & 1) == carry);
1096         }
1097         return carry;
1098 }
1099
1100 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required.  x[0:n]
1101  * is modified in place, by subtracting y from it.  Borrows are propagated as
1102  * far as x[m-1], and the remaining borrow (0 or 1) is returned.
1103  */
1104 static digit
1105 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n)
1106 {
1107         int i;
1108         digit borrow = 0;
1109
1110         assert(m >= n);
1111         for (i = 0; i < n; ++i) {
1112                 borrow = x[i] - y[i] - borrow;
1113                 x[i] = borrow & MASK;
1114                 borrow >>= SHIFT;
1115                 borrow &= 1;    /* keep only 1 sign bit */
1116         }
1117         for (; borrow && i < m; ++i) {
1118                 borrow = x[i] - borrow;
1119                 x[i] = borrow & MASK;
1120                 borrow >>= SHIFT;
1121                 borrow &= 1;
1122         }
1123         return borrow;
1124 }
1125
1126 /* Multiply by a single digit, ignoring the sign. */
1127
1128 static PyLongObject *
1129 mul1(PyLongObject *a, wdigit n)
1130 {
1131         return muladd1(a, n, (digit)0);
1132 }
1133
1134 /* Multiply by a single digit and add a single digit, ignoring the sign. */
1135
1136 static PyLongObject *
1137 muladd1(PyLongObject *a, wdigit n, wdigit extra)
1138 {
1139         Py_ssize_t size_a = ABS(a->ob_size);
1140         PyLongObject *z = _PyLong_New(size_a+1);
1141         twodigits carry = extra;
1142         Py_ssize_t i;
1143
1144         if (z == NULL)
1145                 return NULL;
1146         for (i = 0; i < size_a; ++i) {
1147                 carry += (twodigits)a->ob_digit[i] * n;
1148                 z->ob_digit[i] = (digit) (carry & MASK);
1149                 carry >>= SHIFT;
1150         }
1151         z->ob_digit[i] = (digit) carry;
1152         return long_normalize(z);
1153 }
1154
1155 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1156    in pout, and returning the remainder.  pin and pout point at the LSD.
1157    It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1158    long_format, but that should be done with great care since longs are
1159    immutable. */
1160
1161 static digit
1162 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
1163 {
1164         twodigits rem = 0;
1165
1166         assert(n > 0 && n <= MASK);
1167         pin += size;
1168         pout += size;
1169         while (--size >= 0) {
1170                 digit hi;
1171                 rem = (rem << SHIFT) + *--pin;
1172                 *--pout = hi = (digit)(rem / n);
1173                 rem -= hi * n;
1174         }
1175         return (digit)rem;
1176 }
1177
1178 /* Divide a long integer by a digit, returning both the quotient
1179    (as function result) and the remainder (through *prem).
1180    The sign of a is ignored; n should not be zero. */
1181
1182 static PyLongObject *
1183 divrem1(PyLongObject *a, digit n, digit *prem)
1184 {
1185         const Py_ssize_t size = ABS(a->ob_size);
1186         PyLongObject *z;
1187
1188         assert(n > 0 && n <= MASK);
1189         z = _PyLong_New(size);
1190         if (z == NULL)
1191                 return NULL;
1192         *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1193         return long_normalize(z);
1194 }
1195
1196 /* Convert a long int object to a string, using a given conversion base.
1197    Return a string object.
1198    If base is 8 or 16, add the proper prefix '0' or '0x'. */
1199
1200 static PyObject *
1201 long_format(PyObject *aa, int base, int addL)
1202 {
1203         register PyLongObject *a = (PyLongObject *)aa;
1204         PyStringObject *str;
1205         Py_ssize_t i;
1206         const Py_ssize_t size_a = ABS(a->ob_size);
1207         char *p;
1208         int bits;
1209         char sign = '\0';
1210
1211         if (a == NULL || !PyLong_Check(a)) {
1212                 PyErr_BadInternalCall();
1213                 return NULL;
1214         }
1215         assert(base >= 2 && base <= 36);
1216
1217         /* Compute a rough upper bound for the length of the string */
1218         i = base;
1219         bits = 0;
1220         while (i > 1) {
1221                 ++bits;
1222                 i >>= 1;
1223         }
1224         i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
1225         str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
1226         if (str == NULL)
1227                 return NULL;
1228         p = PyString_AS_STRING(str) + i;
1229         *p = '\0';
1230         if (addL)
1231                 *--p = 'L';
1232         if (a->ob_size < 0)
1233                 sign = '-';
1234
1235         if (a->ob_size == 0) {
1236                 *--p = '0';
1237         }
1238         else if ((base & (base - 1)) == 0) {
1239                 /* JRH: special case for power-of-2 bases */
1240                 twodigits accum = 0;
1241                 int accumbits = 0;      /* # of bits in accum */
1242                 int basebits = 1;       /* # of bits in base-1 */
1243                 i = base;
1244                 while ((i >>= 1) > 1)
1245                         ++basebits;
1246
1247                 for (i = 0; i < size_a; ++i) {
1248                         accum |= (twodigits)a->ob_digit[i] << accumbits;
1249                         accumbits += SHIFT;
1250                         assert(accumbits >= basebits);
1251                         do {
1252                                 char cdigit = (char)(accum & (base - 1));
1253                                 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1254                                 assert(p > PyString_AS_STRING(str));
1255                                 *--p = cdigit;
1256                                 accumbits -= basebits;
1257                                 accum >>= basebits;
1258                         } while (i < size_a-1 ? accumbits >= basebits :
1259                                                 accum > 0);
1260                 }
1261         }
1262         else {
1263                 /* Not 0, and base not a power of 2.  Divide repeatedly by
1264                    base, but for speed use the highest power of base that
1265                    fits in a digit. */
1266                 Py_ssize_t size = size_a;
1267                 digit *pin = a->ob_digit;
1268                 PyLongObject *scratch;
1269                 /* powbasw <- largest power of base that fits in a digit. */
1270                 digit powbase = base;  /* powbase == base ** power */
1271                 int power = 1;
1272                 for (;;) {
1273                         unsigned long newpow = powbase * (unsigned long)base;
1274                         if (newpow >> SHIFT)  /* doesn't fit in a digit */
1275                                 break;
1276                         powbase = (digit)newpow;
1277                         ++power;
1278                 }
1279
1280                 /* Get a scratch area for repeated division. */
1281                 scratch = _PyLong_New(size);
1282                 if (scratch == NULL) {
1283                         Py_DECREF(str);
1284                         return NULL;
1285                 }
1286
1287                 /* Repeatedly divide by powbase. */
1288                 do {
1289                         int ntostore = power;
1290                         digit rem = inplace_divrem1(scratch->ob_digit,
1291                                                      pin, size, powbase);
1292                         pin = scratch->ob_digit; /* no need to use a again */
1293                         if (pin[size - 1] == 0)
1294                                 --size;
1295                         SIGCHECK({
1296                                 Py_DECREF(scratch);
1297                                 Py_DECREF(str);
1298                                 return NULL;
1299                         })
1300
1301                         /* Break rem into digits. */
1302                         assert(ntostore > 0);
1303                         do {
1304                                 digit nextrem = (digit)(rem / base);
1305                                 char c = (char)(rem - nextrem * base);
1306                                 assert(p > PyString_AS_STRING(str));
1307                                 c += (c < 10) ? '0' : 'a'-10;
1308                                 *--p = c;
1309                                 rem = nextrem;
1310                                 --ntostore;
1311                                 /* Termination is a bit delicate:  must not
1312                                    store leading zeroes, so must get out if
1313                                    remaining quotient and rem are both 0. */
1314                         } while (ntostore && (size || rem));
1315                 } while (size != 0);
1316                 Py_DECREF(scratch);
1317         }
1318
1319         if (base == 8) {
1320                 if (size_a != 0)
1321                         *--p = '0';
1322         }
1323         else if (base == 16) {
1324                 *--p = 'x';
1325                 *--p = '0';
1326         }
1327         else if (base != 10) {
1328                 *--p = '#';
1329                 *--p = '0' + base%10;
1330                 if (base > 10)
1331                         *--p = '0' + base/10;
1332         }
1333         if (sign)
1334                 *--p = sign;
1335         if (p != PyString_AS_STRING(str)) {
1336                 char *q = PyString_AS_STRING(str);
1337                 assert(p > q);
1338                 do {
1339                 } while ((*q++ = *p++) != '\0');
1340                 q--;
1341                 _PyString_Resize((PyObject **)&str,
1342                                  (int) (q - PyString_AS_STRING(str)));
1343         }
1344         return (PyObject *)str;
1345 }
1346
1347 /* Table of digit values for 8-bit string -> integer conversion.
1348  * '0' maps to 0, ..., '9' maps to 9.
1349  * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1350  * All other indices map to 37.
1351  * Note that when converting a base B string, a char c is a legitimate
1352  * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.
1353  */
1354 int _PyLong_DigitValue[256] = {
1355         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1356         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1357         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1358         0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  37, 37, 37, 37, 37, 37,
1359         37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1360         25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1361         37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1362         25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1363         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1364         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1365         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1366         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1367         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1368         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1369         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1370         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1371 };
1372
1373 /* *str points to the first digit in a string of base `base` digits.  base
1374  * is a power of 2 (2, 4, 8, 16, or 32).  *str is set to point to the first
1375  * non-digit (which may be *str!).  A normalized long is returned.
1376  * The point to this routine is that it takes time linear in the number of
1377  * string characters.
1378  */
1379 static PyLongObject *
1380 long_from_binary_base(char **str, int base)
1381 {
1382         char *p = *str;
1383         char *start = p;
1384         int bits_per_char;
1385         Py_ssize_t n;
1386         PyLongObject *z;
1387         twodigits accum;
1388         int bits_in_accum;
1389         digit *pdigit;
1390
1391         assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1392         n = base;
1393         for (bits_per_char = -1; n; ++bits_per_char)
1394                 n >>= 1;
1395         /* n <- total # of bits needed, while setting p to end-of-string */
1396         n = 0;
1397         while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
1398                 ++p;
1399         *str = p;
1400         n = (p - start) * bits_per_char;
1401         if (n / bits_per_char != p - start) {
1402                 PyErr_SetString(PyExc_ValueError,
1403                                 "long string too large to convert");
1404                 return NULL;
1405         }
1406         /* n <- # of Python digits needed, = ceiling(n/SHIFT). */
1407         n = (n + SHIFT - 1) / SHIFT;
1408         z = _PyLong_New(n);
1409         if (z == NULL)
1410                 return NULL;
1411         /* Read string from right, and fill in long from left; i.e.,
1412          * from least to most significant in both.
1413          */
1414         accum = 0;
1415         bits_in_accum = 0;
1416         pdigit = z->ob_digit;
1417         while (--p >= start) {
1418                 int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
1419                 assert(k >= 0 && k < base);
1420                 accum |= (twodigits)(k << bits_in_accum);
1421                 bits_in_accum += bits_per_char;
1422                 if (bits_in_accum >= SHIFT) {
1423                         *pdigit++ = (digit)(accum & MASK);
1424                         assert(pdigit - z->ob_digit <= (int)n);
1425                         accum >>= SHIFT;
1426                         bits_in_accum -= SHIFT;
1427                         assert(bits_in_accum < SHIFT);
1428                 }
1429         }
1430         if (bits_in_accum) {
1431                 assert(bits_in_accum <= SHIFT);
1432                 *pdigit++ = (digit)accum;
1433                 assert(pdigit - z->ob_digit <= (int)n);
1434         }
1435         while (pdigit - z->ob_digit < n)
1436                 *pdigit++ = 0;
1437         return long_normalize(z);
1438 }
1439
1440 PyObject *
1441 PyLong_FromString(char *str, char **pend, int base)
1442 {
1443         int sign = 1;
1444         char *start, *orig_str = str;
1445         PyLongObject *z;
1446         PyObject *strobj, *strrepr;
1447         Py_ssize_t slen;
1448
1449         if ((base != 0 && base < 2) || base > 36) {
1450                 PyErr_SetString(PyExc_ValueError,
1451                                 "long() arg 2 must be >= 2 and <= 36");
1452                 return NULL;
1453         }
1454         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1455                 str++;
1456         if (*str == '+')
1457                 ++str;
1458         else if (*str == '-') {
1459                 ++str;
1460                 sign = -1;
1461         }
1462         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1463                 str++;
1464         if (base == 0) {
1465                 if (str[0] != '0')
1466                         base = 10;
1467                 else if (str[1] == 'x' || str[1] == 'X')
1468                         base = 16;
1469                 else
1470                         base = 8;
1471         }
1472         if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
1473                 str += 2;
1474
1475         start = str;
1476         if ((base & (base - 1)) == 0)
1477                 z = long_from_binary_base(&str, base);
1478         else {
1479 /***
1480 Binary bases can be converted in time linear in the number of digits, because
1481 Python's representation base is binary.  Other bases (including decimal!) use
1482 the simple quadratic-time algorithm below, complicated by some speed tricks.
1483
1484 First some math:  the largest integer that can be expressed in N base-B digits
1485 is B**N-1.  Consequently, if we have an N-digit input in base B, the worst-
1486 case number of Python digits needed to hold it is the smallest integer n s.t.
1487
1488     BASE**n-1 >= B**N-1  [or, adding 1 to both sides]
1489     BASE**n >= B**N      [taking logs to base BASE]
1490     n >= log(B**N)/log(BASE) = N * log(B)/log(BASE)
1491
1492 The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
1493 this quickly.  A Python long with that much space is reserved near the start,
1494 and the result is computed into it.
1495
1496 The input string is actually treated as being in base base**i (i.e., i digits
1497 are processed at a time), where two more static arrays hold:
1498
1499     convwidth_base[base] = the largest integer i such that base**i <= BASE
1500     convmultmax_base[base] = base ** convwidth_base[base]
1501
1502 The first of these is the largest i such that i consecutive input digits
1503 must fit in a single Python digit.  The second is effectively the input
1504 base we're really using.
1505
1506 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1507 convmultmax_base[base], the result is "simply"
1508
1509    (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1510
1511 where B = convmultmax_base[base].
1512
1513 Error analysis:  as above, the number of Python digits `n` needed is worst-
1514 case
1515
1516     n >= N * log(B)/log(BASE)
1517
1518 where `N` is the number of input digits in base `B`.  This is computed via
1519
1520     size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
1521
1522 below.  Two numeric concerns are how much space this can waste, and whether
1523 the computed result can be too small.  To be concrete, assume BASE = 2**15,
1524 which is the default (and it's unlikely anyone changes that).
1525
1526 Waste isn't a problem:  provided the first input digit isn't 0, the difference
1527 between the worst-case input with N digits and the smallest input with N
1528 digits is about a factor of B, but B is small compared to BASE so at most
1529 one allocated Python digit can remain unused on that count.  If
1530 N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
1531 and adding 1 returns a result 1 larger than necessary.  However, that can't
1532 happen:  whenever B is a power of 2, long_from_binary_base() is called
1533 instead, and it's impossible for B**i to be an integer power of 2**15 when
1534 B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
1535 an exact integer when B is not a power of 2, since B**i has a prime factor
1536 other than 2 in that case, but (2**15)**j's only prime factor is 2).
1537
1538 The computed result can be too small if the true value of N*log(B)/log(BASE)
1539 is a little bit larger than an exact integer, but due to roundoff errors (in
1540 computing log(B), log(BASE), their quotient, and/or multiplying that by N)
1541 yields a numeric result a little less than that integer.  Unfortunately, "how
1542 close can a transcendental function get to an integer over some range?"
1543 questions are generally theoretically intractable.  Computer analysis via
1544 continued fractions is practical:  expand log(B)/log(BASE) via continued
1545 fractions, giving a sequence i/j of "the best" rational approximations.  Then
1546 j*log(B)/log(BASE) is approximately equal to (the integer) i.  This shows that
1547 we can get very close to being in trouble, but very rarely.  For example,
1548 76573 is a denominator in one of the continued-fraction approximations to
1549 log(10)/log(2**15), and indeed:
1550
1551     >>> log(10)/log(2**15)*76573
1552     16958.000000654003
1553
1554 is very close to an integer.  If we were working with IEEE single-precision,
1555 rounding errors could kill us.  Finding worst cases in IEEE double-precision
1556 requires better-than-double-precision log() functions, and Tim didn't bother.
1557 Instead the code checks to see whether the allocated space is enough as each
1558 new Python digit is added, and copies the whole thing to a larger long if not.
1559 This should happen extremely rarely, and in fact I don't have a test case
1560 that triggers it(!).  Instead the code was tested by artificially allocating
1561 just 1 digit at the start, so that the copying code was exercised for every
1562 digit beyond the first.
1563 ***/
1564                 register twodigits c;   /* current input character */
1565                 Py_ssize_t size_z;
1566                 int i;
1567                 int convwidth;
1568                 twodigits convmultmax, convmult;
1569                 digit *pz, *pzstop;
1570                 char* scan;
1571
1572                 static double log_base_BASE[37] = {0.0e0,};
1573                 static int convwidth_base[37] = {0,};
1574                 static twodigits convmultmax_base[37] = {0,};
1575
1576                 if (log_base_BASE[base] == 0.0) {
1577                         twodigits convmax = base;
1578                         int i = 1;
1579
1580                         log_base_BASE[base] = log((double)base) /
1581                                                 log((double)BASE);
1582                         for (;;) {
1583                                 twodigits next = convmax * base;
1584                                 if (next > BASE)
1585                                         break;
1586                                 convmax = next;
1587                                 ++i;
1588                         }
1589                         convmultmax_base[base] = convmax;
1590                         assert(i > 0);
1591                         convwidth_base[base] = i;
1592                 }
1593
1594                 /* Find length of the string of numeric characters. */
1595                 scan = str;
1596                 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1597                         ++scan;
1598
1599                 /* Create a long object that can contain the largest possible
1600                  * integer with this base and length.  Note that there's no
1601                  * need to initialize z->ob_digit -- no slot is read up before
1602                  * being stored into.
1603                  */
1604                 size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
1605                 /* Uncomment next line to test exceedingly rare copy code */
1606                 /* size_z = 1; */
1607                 assert(size_z > 0);
1608                 z = _PyLong_New(size_z);
1609                 if (z == NULL)
1610                         return NULL;
1611                 z->ob_size = 0;
1612
1613                 /* `convwidth` consecutive input digits are treated as a single
1614                  * digit in base `convmultmax`.
1615                  */
1616                 convwidth = convwidth_base[base];
1617                 convmultmax = convmultmax_base[base];
1618
1619                 /* Work ;-) */
1620                 while (str < scan) {
1621                         /* grab up to convwidth digits from the input string */
1622                         c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
1623                         for (i = 1; i < convwidth && str != scan; ++i, ++str) {
1624                                 c = (twodigits)(c *  base +
1625                                         _PyLong_DigitValue[Py_CHARMASK(*str)]);
1626                                 assert(c < BASE);
1627                         }
1628
1629                         convmult = convmultmax;
1630                         /* Calculate the shift only if we couldn't get
1631                          * convwidth digits.
1632                          */
1633                         if (i != convwidth) {
1634                                 convmult = base;
1635                                 for ( ; i > 1; --i)
1636                                         convmult *= base;
1637                         }
1638
1639                         /* Multiply z by convmult, and add c. */
1640                         pz = z->ob_digit;
1641                         pzstop = pz + z->ob_size;
1642                         for (; pz < pzstop; ++pz) {
1643                                 c += (twodigits)*pz * convmult;
1644                                 *pz = (digit)(c & MASK);
1645                                 c >>= SHIFT;
1646                         }
1647                         /* carry off the current end? */
1648                         if (c) {
1649                                 assert(c < BASE);
1650                                 if (z->ob_size < size_z) {
1651                                         *pz = (digit)c;
1652                                         ++z->ob_size;
1653                                 }
1654                                 else {
1655                                         PyLongObject *tmp;
1656                                         /* Extremely rare.  Get more space. */
1657                                         assert(z->ob_size == size_z);
1658                                         tmp = _PyLong_New(size_z + 1);
1659                                         if (tmp == NULL) {
1660                                                 Py_DECREF(z);
1661                                                 return NULL;
1662                                         }
1663                                         memcpy(tmp->ob_digit,
1664                                                z->ob_digit,
1665                                                sizeof(digit) * size_z);
1666                                         Py_DECREF(z);
1667                                         z = tmp;
1668                                         z->ob_digit[size_z] = (digit)c;
1669                                         ++size_z;
1670                                 }
1671                         }
1672                 }
1673         }
1674         if (z == NULL)
1675                 return NULL;
1676         if (str == start)
1677                 goto onError;
1678         if (sign < 0)
1679                 z->ob_size = -(z->ob_size);
1680         if (*str == 'L' || *str == 'l')
1681                 str++;
1682         while (*str && isspace(Py_CHARMASK(*str)))
1683                 str++;
1684         if (*str != '\0')
1685                 goto onError;
1686         if (pend)
1687                 *pend = str;
1688         return (PyObject *) z;
1689
1690  onError:
1691         Py_XDECREF(z);
1692         slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
1693         strobj = PyString_FromStringAndSize(orig_str, slen);
1694         if (strobj == NULL)
1695                 return NULL;
1696         strrepr = PyObject_Repr(strobj);
1697         Py_DECREF(strobj);
1698         if (strrepr == NULL)
1699                 return NULL;
1700         PyErr_Format(PyExc_ValueError,
1701                      "invalid literal for long() with base %d: %s",
1702                      base, PyString_AS_STRING(strrepr));
1703         Py_DECREF(strrepr);
1704         return NULL;
1705 }
1706
1707 #ifdef Py_USING_UNICODE
1708 PyObject *
1709 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
1710 {
1711         PyObject *result;
1712         char *buffer = (char *)PyMem_MALLOC(length+1);
1713
1714         if (buffer == NULL)
1715                 return NULL;
1716
1717         if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
1718                 PyMem_FREE(buffer);
1719                 return NULL;
1720         }
1721         result = PyLong_FromString(buffer, NULL, base);
1722         PyMem_FREE(buffer);
1723         return result;
1724 }
1725 #endif
1726
1727 /* forward */
1728 static PyLongObject *x_divrem
1729         (PyLongObject *, PyLongObject *, PyLongObject **);
1730 static PyObject *long_pos(PyLongObject *);
1731 static int long_divrem(PyLongObject *, PyLongObject *,
1732         PyLongObject **, PyLongObject **);
1733
1734 /* Long division with remainder, top-level routine */
1735
1736 static int
1737 long_divrem(PyLongObject *a, PyLongObject *b,
1738             PyLongObject **pdiv, PyLongObject **prem)
1739 {
1740         Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1741         PyLongObject *z;
1742
1743         if (size_b == 0) {
1744                 PyErr_SetString(PyExc_ZeroDivisionError,
1745                                 "long division or modulo by zero");
1746                 return -1;
1747         }
1748         if (size_a < size_b ||
1749             (size_a == size_b &&
1750              a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
1751                 /* |a| < |b|. */
1752                 *pdiv = _PyLong_New(0);
1753                 Py_INCREF(a);
1754                 *prem = (PyLongObject *) a;
1755                 return 0;
1756         }
1757         if (size_b == 1) {
1758                 digit rem = 0;
1759                 z = divrem1(a, b->ob_digit[0], &rem);
1760                 if (z == NULL)
1761                         return -1;
1762                 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
1763         }
1764         else {
1765                 z = x_divrem(a, b, prem);
1766                 if (z == NULL)
1767                         return -1;
1768         }
1769         /* Set the signs.
1770            The quotient z has the sign of a*b;
1771            the remainder r has the sign of a,
1772            so a = b*z + r. */
1773         if ((a->ob_size < 0) != (b->ob_size < 0))
1774                 z->ob_size = -(z->ob_size);
1775         if (a->ob_size < 0 && (*prem)->ob_size != 0)
1776                 (*prem)->ob_size = -((*prem)->ob_size);
1777         *pdiv = z;
1778         return 0;
1779 }
1780
1781 /* Unsigned long division with remainder -- the algorithm */
1782
1783 static PyLongObject *
1784 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
1785 {
1786         Py_ssize_t size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size);
1787         digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
1788         PyLongObject *v = mul1(v1, d);
1789         PyLongObject *w = mul1(w1, d);
1790         PyLongObject *a;
1791         Py_ssize_t j, k;
1792
1793         if (v == NULL || w == NULL) {
1794                 Py_XDECREF(v);
1795                 Py_XDECREF(w);
1796                 return NULL;
1797         }
1798
1799         assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
1800         assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
1801         assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */
1802
1803         size_v = ABS(v->ob_size);
1804         k = size_v - size_w;
1805         a = _PyLong_New(k + 1);
1806
1807         for (j = size_v; a != NULL && k >= 0; --j, --k) {
1808                 digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
1809                 twodigits q;
1810                 stwodigits carry = 0;
1811                 int i;
1812
1813                 SIGCHECK({
1814                         Py_DECREF(a);
1815                         a = NULL;
1816                         break;
1817                 })
1818                 if (vj == w->ob_digit[size_w-1])
1819                         q = MASK;
1820                 else
1821                         q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
1822                                 w->ob_digit[size_w-1];
1823
1824                 while (w->ob_digit[size_w-2]*q >
1825                                 ((
1826                                         ((twodigits)vj << SHIFT)
1827                                         + v->ob_digit[j-1]
1828                                         - q*w->ob_digit[size_w-1]
1829                                                                 ) << SHIFT)
1830                                 + v->ob_digit[j-2])
1831                         --q;
1832
1833                 for (i = 0; i < size_w && i+k < size_v; ++i) {
1834                         twodigits z = w->ob_digit[i] * q;
1835                         digit zz = (digit) (z >> SHIFT);
1836                         carry += v->ob_digit[i+k] - z
1837                                 + ((twodigits)zz << SHIFT);
1838                         v->ob_digit[i+k] = (digit)(carry & MASK);
1839                         carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
1840                                                           carry, SHIFT);
1841                         carry -= zz;
1842                 }
1843
1844                 if (i+k < size_v) {
1845                         carry += v->ob_digit[i+k];
1846                         v->ob_digit[i+k] = 0;
1847                 }
1848
1849                 if (carry == 0)
1850                         a->ob_digit[k] = (digit) q;
1851                 else {
1852                         assert(carry == -1);
1853                         a->ob_digit[k] = (digit) q-1;
1854                         carry = 0;
1855                         for (i = 0; i < size_w && i+k < size_v; ++i) {
1856                                 carry += v->ob_digit[i+k] + w->ob_digit[i];
1857                                 v->ob_digit[i+k] = (digit)(carry & MASK);
1858                                 carry = Py_ARITHMETIC_RIGHT_SHIFT(
1859                                                 BASE_TWODIGITS_TYPE,
1860                                                 carry, SHIFT);
1861                         }
1862                 }
1863         } /* for j, k */
1864
1865         if (a == NULL)
1866                 *prem = NULL;
1867         else {
1868                 a = long_normalize(a);
1869                 *prem = divrem1(v, d, &d);
1870                 /* d receives the (unused) remainder */
1871                 if (*prem == NULL) {
1872                         Py_DECREF(a);
1873                         a = NULL;
1874                 }
1875         }
1876         Py_DECREF(v);
1877         Py_DECREF(w);
1878         return a;
1879 }
1880
1881 /* Methods */
1882
1883 static void
1884 long_dealloc(PyObject *v)
1885 {
1886         v->ob_type->tp_free(v);
1887 }
1888
1889 static PyObject *
1890 long_repr(PyObject *v)
1891 {
1892         return long_format(v, 10, 1);
1893 }
1894
1895 static PyObject *
1896 long_str(PyObject *v)
1897 {
1898         return long_format(v, 10, 0);
1899 }
1900
1901 static int
1902 long_compare(PyLongObject *a, PyLongObject *b)
1903 {
1904         Py_ssize_t sign;
1905
1906         if (a->ob_size != b->ob_size) {
1907                 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0)
1908                         sign = 0;
1909                 else
1910                         sign = a->ob_size - b->ob_size;
1911         }
1912         else {
1913                 Py_ssize_t i = ABS(a->ob_size);
1914                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1915                         ;
1916                 if (i < 0)
1917                         sign = 0;
1918                 else {
1919                         sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
1920                         if (a->ob_size < 0)
1921                                 sign = -sign;
1922                 }
1923         }
1924         return sign < 0 ? -1 : sign > 0 ? 1 : 0;
1925 }
1926
1927 static long
1928 long_hash(PyLongObject *v)
1929 {
1930         long x;
1931         Py_ssize_t i;
1932         int sign;
1933
1934         /* This is designed so that Python ints and longs with the
1935            same value hash to the same value, otherwise comparisons
1936            of mapping keys will turn out weird */
1937         i = v->ob_size;
1938         sign = 1;
1939         x = 0;
1940         if (i < 0) {
1941                 sign = -1;
1942                 i = -(i);
1943         }
1944 #define LONG_BIT_SHIFT  (8*sizeof(long) - SHIFT)
1945         while (--i >= 0) {
1946                 /* Force a native long #-bits (32 or 64) circular shift */
1947                 x = ((x << SHIFT) & ~MASK) | ((x >> LONG_BIT_SHIFT) & MASK);
1948                 x += v->ob_digit[i];
1949         }
1950 #undef LONG_BIT_SHIFT
1951         x = x * sign;
1952         if (x == -1)
1953                 x = -2;
1954         return x;
1955 }
1956
1957
1958 /* Add the absolute values of two long integers. */
1959
1960 static PyLongObject *
1961 x_add(PyLongObject *a, PyLongObject *b)
1962 {
1963         Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1964         PyLongObject *z;
1965         int i;
1966         digit carry = 0;
1967
1968         /* Ensure a is the larger of the two: */
1969         if (size_a < size_b) {
1970                 { PyLongObject *temp = a; a = b; b = temp; }
1971                 { Py_ssize_t size_temp = size_a;
1972                   size_a = size_b;
1973                   size_b = size_temp; }
1974         }
1975         z = _PyLong_New(size_a+1);
1976         if (z == NULL)
1977                 return NULL;
1978         for (i = 0; i < size_b; ++i) {
1979                 carry += a->ob_digit[i] + b->ob_digit[i];
1980                 z->ob_digit[i] = carry & MASK;
1981                 carry >>= SHIFT;
1982         }
1983         for (; i < size_a; ++i) {
1984                 carry += a->ob_digit[i];
1985                 z->ob_digit[i] = carry & MASK;
1986                 carry >>= SHIFT;
1987         }
1988         z->ob_digit[i] = carry;
1989         return long_normalize(z);
1990 }
1991
1992 /* Subtract the absolute values of two integers. */
1993
1994 static PyLongObject *
1995 x_sub(PyLongObject *a, PyLongObject *b)
1996 {
1997         Py_ssize_t size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1998         PyLongObject *z;
1999         Py_ssize_t i;
2000         int sign = 1;
2001         digit borrow = 0;
2002
2003         /* Ensure a is the larger of the two: */
2004         if (size_a < size_b) {
2005                 sign = -1;
2006                 { PyLongObject *temp = a; a = b; b = temp; }
2007                 { Py_ssize_t size_temp = size_a;
2008                   size_a = size_b;
2009                   size_b = size_temp; }
2010         }
2011         else if (size_a == size_b) {
2012                 /* Find highest digit where a and b differ: */
2013                 i = size_a;
2014                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2015                         ;
2016                 if (i < 0)
2017                         return _PyLong_New(0);
2018                 if (a->ob_digit[i] < b->ob_digit[i]) {
2019                         sign = -1;
2020                         { PyLongObject *temp = a; a = b; b = temp; }
2021                 }
2022                 size_a = size_b = i+1;
2023         }
2024         z = _PyLong_New(size_a);
2025         if (z == NULL)
2026                 return NULL;
2027         for (i = 0; i < size_b; ++i) {
2028                 /* The following assumes unsigned arithmetic
2029                    works module 2**N for some N>SHIFT. */
2030                 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
2031                 z->ob_digit[i] = borrow & MASK;
2032                 borrow >>= SHIFT;
2033                 borrow &= 1; /* Keep only one sign bit */
2034         }
2035         for (; i < size_a; ++i) {
2036                 borrow = a->ob_digit[i] - borrow;
2037                 z->ob_digit[i] = borrow & MASK;
2038                 borrow >>= SHIFT;
2039                 borrow &= 1; /* Keep only one sign bit */
2040         }
2041         assert(borrow == 0);
2042         if (sign < 0)
2043                 z->ob_size = -(z->ob_size);
2044         return long_normalize(z);
2045 }
2046
2047 static PyObject *
2048 long_add(PyLongObject *v, PyLongObject *w)
2049 {
2050         PyLongObject *a, *b, *z;
2051
2052         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2053
2054         if (a->ob_size < 0) {
2055                 if (b->ob_size < 0) {
2056                         z = x_add(a, b);
2057                         if (z != NULL && z->ob_size != 0)
2058                                 z->ob_size = -(z->ob_size);
2059                 }
2060                 else
2061                         z = x_sub(b, a);
2062         }
2063         else {
2064                 if (b->ob_size < 0)
2065                         z = x_sub(a, b);
2066                 else
2067                         z = x_add(a, b);
2068         }
2069         Py_DECREF(a);
2070         Py_DECREF(b);
2071         return (PyObject *)z;
2072 }
2073
2074 static PyObject *
2075 long_sub(PyLongObject *v, PyLongObject *w)
2076 {
2077         PyLongObject *a, *b, *z;
2078
2079         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2080
2081         if (a->ob_size < 0) {
2082                 if (b->ob_size < 0)
2083                         z = x_sub(a, b);
2084                 else
2085                         z = x_add(a, b);
2086                 if (z != NULL && z->ob_size != 0)
2087                         z->ob_size = -(z->ob_size);
2088         }
2089         else {
2090                 if (b->ob_size < 0)
2091                         z = x_add(a, b);
2092                 else
2093                         z = x_sub(a, b);
2094         }
2095         Py_DECREF(a);
2096         Py_DECREF(b);
2097         return (PyObject *)z;
2098 }
2099
2100 /* Grade school multiplication, ignoring the signs.
2101  * Returns the absolute value of the product, or NULL if error.
2102  */
2103 static PyLongObject *
2104 x_mul(PyLongObject *a, PyLongObject *b)
2105 {
2106         PyLongObject *z;
2107         Py_ssize_t size_a = ABS(a->ob_size);
2108         Py_ssize_t size_b = ABS(b->ob_size);
2109         Py_ssize_t i;
2110
2111         z = _PyLong_New(size_a + size_b);
2112         if (z == NULL)
2113                 return NULL;
2114
2115         memset(z->ob_digit, 0, z->ob_size * sizeof(digit));
2116         if (a == b) {
2117                 /* Efficient squaring per HAC, Algorithm 14.16:
2118                  * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2119                  * Gives slightly less than a 2x speedup when a == b,
2120                  * via exploiting that each entry in the multiplication
2121                  * pyramid appears twice (except for the size_a squares).
2122                  */
2123                 for (i = 0; i < size_a; ++i) {
2124                         twodigits carry;
2125                         twodigits f = a->ob_digit[i];
2126                         digit *pz = z->ob_digit + (i << 1);
2127                         digit *pa = a->ob_digit + i + 1;
2128                         digit *paend = a->ob_digit + size_a;
2129
2130                         SIGCHECK({
2131                                 Py_DECREF(z);
2132                                 return NULL;
2133                         })
2134
2135                         carry = *pz + f * f;
2136                         *pz++ = (digit)(carry & MASK);
2137                         carry >>= SHIFT;
2138                         assert(carry <= MASK);
2139
2140                         /* Now f is added in twice in each column of the
2141                          * pyramid it appears.  Same as adding f<<1 once.
2142                          */
2143                         f <<= 1;
2144                         while (pa < paend) {
2145                                 carry += *pz + *pa++ * f;
2146                                 *pz++ = (digit)(carry & MASK);
2147                                 carry >>= SHIFT;
2148                                 assert(carry <= (MASK << 1));
2149                         }
2150                         if (carry) {
2151                                 carry += *pz;
2152                                 *pz++ = (digit)(carry & MASK);
2153                                 carry >>= SHIFT;
2154                         }
2155                         if (carry)
2156                                 *pz += (digit)(carry & MASK);
2157                         assert((carry >> SHIFT) == 0);
2158                 }
2159         }
2160         else {  /* a is not the same as b -- gradeschool long mult */
2161                 for (i = 0; i < size_a; ++i) {
2162                         twodigits carry = 0;
2163                         twodigits f = a->ob_digit[i];
2164                         digit *pz = z->ob_digit + i;
2165                         digit *pb = b->ob_digit;
2166                         digit *pbend = b->ob_digit + size_b;
2167
2168                         SIGCHECK({
2169                                 Py_DECREF(z);
2170                                 return NULL;
2171                         })
2172
2173                         while (pb < pbend) {
2174                                 carry += *pz + *pb++ * f;
2175                                 *pz++ = (digit)(carry & MASK);
2176                                 carry >>= SHIFT;
2177                                 assert(carry <= MASK);
2178                         }
2179                         if (carry)
2180                                 *pz += (digit)(carry & MASK);
2181                         assert((carry >> SHIFT) == 0);
2182                 }
2183         }
2184         return long_normalize(z);
2185 }
2186
2187 /* A helper for Karatsuba multiplication (k_mul).
2188    Takes a long "n" and an integer "size" representing the place to
2189    split, and sets low and high such that abs(n) == (high << size) + low,
2190    viewing the shift as being by digits.  The sign bit is ignored, and
2191    the return values are >= 0.
2192    Returns 0 on success, -1 on failure.
2193 */
2194 static int
2195 kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low)
2196 {
2197         PyLongObject *hi, *lo;
2198         Py_ssize_t size_lo, size_hi;
2199         const Py_ssize_t size_n = ABS(n->ob_size);
2200
2201         size_lo = MIN(size_n, size);
2202         size_hi = size_n - size_lo;
2203
2204         if ((hi = _PyLong_New(size_hi)) == NULL)
2205                 return -1;
2206         if ((lo = _PyLong_New(size_lo)) == NULL) {
2207                 Py_DECREF(hi);
2208                 return -1;
2209         }
2210
2211         memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
2212         memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
2213
2214         *high = long_normalize(hi);
2215         *low = long_normalize(lo);
2216         return 0;
2217 }
2218
2219 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2220
2221 /* Karatsuba multiplication.  Ignores the input signs, and returns the
2222  * absolute value of the product (or NULL if error).
2223  * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2224  */
2225 static PyLongObject *
2226 k_mul(PyLongObject *a, PyLongObject *b)
2227 {
2228         Py_ssize_t asize = ABS(a->ob_size);
2229         Py_ssize_t bsize = ABS(b->ob_size);
2230         PyLongObject *ah = NULL;
2231         PyLongObject *al = NULL;
2232         PyLongObject *bh = NULL;
2233         PyLongObject *bl = NULL;
2234         PyLongObject *ret = NULL;
2235         PyLongObject *t1, *t2, *t3;
2236         Py_ssize_t shift;       /* the number of digits we split off */
2237         Py_ssize_t i;
2238
2239         /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2240          * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
2241          * Then the original product is
2242          *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
2243          * By picking X to be a power of 2, "*X" is just shifting, and it's
2244          * been reduced to 3 multiplies on numbers half the size.
2245          */
2246
2247         /* We want to split based on the larger number; fiddle so that b
2248          * is largest.
2249          */
2250         if (asize > bsize) {
2251                 t1 = a;
2252                 a = b;
2253                 b = t1;
2254
2255                 i = asize;
2256                 asize = bsize;
2257                 bsize = i;
2258         }
2259
2260         /* Use gradeschool math when either number is too small. */
2261         i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2262         if (asize <= i) {
2263                 if (asize == 0)
2264                         return _PyLong_New(0);
2265                 else
2266                         return x_mul(a, b);
2267         }
2268
2269         /* If a is small compared to b, splitting on b gives a degenerate
2270          * case with ah==0, and Karatsuba may be (even much) less efficient
2271          * than "grade school" then.  However, we can still win, by viewing
2272          * b as a string of "big digits", each of width a->ob_size.  That
2273          * leads to a sequence of balanced calls to k_mul.
2274          */
2275         if (2 * asize <= bsize)
2276                 return k_lopsided_mul(a, b);
2277
2278         /* Split a & b into hi & lo pieces. */
2279         shift = bsize >> 1;
2280         if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
2281         assert(ah->ob_size > 0);        /* the split isn't degenerate */
2282
2283         if (a == b) {
2284                 bh = ah;
2285                 bl = al;
2286                 Py_INCREF(bh);
2287                 Py_INCREF(bl);
2288         }
2289         else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
2290
2291         /* The plan:
2292          * 1. Allocate result space (asize + bsize digits:  that's always
2293          *    enough).
2294          * 2. Compute ah*bh, and copy into result at 2*shift.
2295          * 3. Compute al*bl, and copy into result at 0.  Note that this
2296          *    can't overlap with #2.
2297          * 4. Subtract al*bl from the result, starting at shift.  This may
2298          *    underflow (borrow out of the high digit), but we don't care:
2299          *    we're effectively doing unsigned arithmetic mod
2300          *    BASE**(sizea + sizeb), and so long as the *final* result fits,
2301          *    borrows and carries out of the high digit can be ignored.
2302          * 5. Subtract ah*bh from the result, starting at shift.
2303          * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2304          *    at shift.
2305          */
2306
2307         /* 1. Allocate result space. */
2308         ret = _PyLong_New(asize + bsize);
2309         if (ret == NULL) goto fail;
2310 #ifdef Py_DEBUG
2311         /* Fill with trash, to catch reference to uninitialized digits. */
2312         memset(ret->ob_digit, 0xDF, ret->ob_size * sizeof(digit));
2313 #endif
2314
2315         /* 2. t1 <- ah*bh, and copy into high digits of result. */
2316         if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
2317         assert(t1->ob_size >= 0);
2318         assert(2*shift + t1->ob_size <= ret->ob_size);
2319         memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
2320                t1->ob_size * sizeof(digit));
2321
2322         /* Zero-out the digits higher than the ah*bh copy. */
2323         i = ret->ob_size - 2*shift - t1->ob_size;
2324         if (i)
2325                 memset(ret->ob_digit + 2*shift + t1->ob_size, 0,
2326                        i * sizeof(digit));
2327
2328         /* 3. t2 <- al*bl, and copy into the low digits. */
2329         if ((t2 = k_mul(al, bl)) == NULL) {
2330                 Py_DECREF(t1);
2331                 goto fail;
2332         }
2333         assert(t2->ob_size >= 0);
2334         assert(t2->ob_size <= 2*shift); /* no overlap with high digits */
2335         memcpy(ret->ob_digit, t2->ob_digit, t2->ob_size * sizeof(digit));
2336
2337         /* Zero out remaining digits. */
2338         i = 2*shift - t2->ob_size;      /* number of uninitialized digits */
2339         if (i)
2340                 memset(ret->ob_digit + t2->ob_size, 0, i * sizeof(digit));
2341
2342         /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2).  We do al*bl first
2343          * because it's fresher in cache.
2344          */
2345         i = ret->ob_size - shift;  /* # digits after shift */
2346         (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, t2->ob_size);
2347         Py_DECREF(t2);
2348
2349         (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, t1->ob_size);
2350         Py_DECREF(t1);
2351
2352         /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2353         if ((t1 = x_add(ah, al)) == NULL) goto fail;
2354         Py_DECREF(ah);
2355         Py_DECREF(al);
2356         ah = al = NULL;
2357
2358         if (a == b) {
2359                 t2 = t1;
2360                 Py_INCREF(t2);
2361         }
2362         else if ((t2 = x_add(bh, bl)) == NULL) {
2363                 Py_DECREF(t1);
2364                 goto fail;
2365         }
2366         Py_DECREF(bh);
2367         Py_DECREF(bl);
2368         bh = bl = NULL;
2369
2370         t3 = k_mul(t1, t2);
2371         Py_DECREF(t1);
2372         Py_DECREF(t2);
2373         if (t3 == NULL) goto fail;
2374         assert(t3->ob_size >= 0);
2375
2376         /* Add t3.  It's not obvious why we can't run out of room here.
2377          * See the (*) comment after this function.
2378          */
2379         (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, t3->ob_size);
2380         Py_DECREF(t3);
2381
2382         return long_normalize(ret);
2383
2384  fail:
2385         Py_XDECREF(ret);
2386         Py_XDECREF(ah);
2387         Py_XDECREF(al);
2388         Py_XDECREF(bh);
2389         Py_XDECREF(bl);
2390         return NULL;
2391 }
2392
2393 /* (*) Why adding t3 can't "run out of room" above.
2394
2395 Let f(x) mean the floor of x and c(x) mean the ceiling of x.  Some facts
2396 to start with:
2397
2398 1. For any integer i, i = c(i/2) + f(i/2).  In particular,
2399    bsize = c(bsize/2) + f(bsize/2).
2400 2. shift = f(bsize/2)
2401 3. asize <= bsize
2402 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2403    routine, so asize > bsize/2 >= f(bsize/2) in this routine.
2404
2405 We allocated asize + bsize result digits, and add t3 into them at an offset
2406 of shift.  This leaves asize+bsize-shift allocated digit positions for t3
2407 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2408 asize + c(bsize/2) available digit positions.
2409
2410 bh has c(bsize/2) digits, and bl at most f(size/2) digits.  So bh+hl has
2411 at most c(bsize/2) digits + 1 bit.
2412
2413 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2414 digits, and al has at most f(bsize/2) digits in any case.  So ah+al has at
2415 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
2416
2417 The product (ah+al)*(bh+bl) therefore has at most
2418
2419     c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2420
2421 and we have asize + c(bsize/2) available digit positions.  We need to show
2422 this is always enough.  An instance of c(bsize/2) cancels out in both, so
2423 the question reduces to whether asize digits is enough to hold
2424 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits.  If asize < bsize,
2425 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits.  By #4,
2426 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
2427 digit is enough to hold 2 bits.  This is so since SHIFT=15 >= 2.  If
2428 asize == bsize, then we're asking whether bsize digits is enough to hold
2429 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2430 is enough to hold 2 bits.  This is so if bsize >= 2, which holds because
2431 bsize >= KARATSUBA_CUTOFF >= 2.
2432
2433 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2434 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2435 ah*bh and al*bl too.
2436 */
2437
2438 /* b has at least twice the digits of a, and a is big enough that Karatsuba
2439  * would pay off *if* the inputs had balanced sizes.  View b as a sequence
2440  * of slices, each with a->ob_size digits, and multiply the slices by a,
2441  * one at a time.  This gives k_mul balanced inputs to work with, and is
2442  * also cache-friendly (we compute one double-width slice of the result
2443  * at a time, then move on, never bactracking except for the helpful
2444  * single-width slice overlap between successive partial sums).
2445  */
2446 static PyLongObject *
2447 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2448 {
2449         const Py_ssize_t asize = ABS(a->ob_size);
2450         Py_ssize_t bsize = ABS(b->ob_size);
2451         Py_ssize_t nbdone;      /* # of b digits already multiplied */
2452         PyLongObject *ret;
2453         PyLongObject *bslice = NULL;
2454
2455         assert(asize > KARATSUBA_CUTOFF);
2456         assert(2 * asize <= bsize);
2457
2458         /* Allocate result space, and zero it out. */
2459         ret = _PyLong_New(asize + bsize);
2460         if (ret == NULL)
2461                 return NULL;
2462         memset(ret->ob_digit, 0, ret->ob_size * sizeof(digit));
2463
2464         /* Successive slices of b are copied into bslice. */
2465         bslice = _PyLong_New(asize);
2466         if (bslice == NULL)
2467                 goto fail;
2468
2469         nbdone = 0;
2470         while (bsize > 0) {
2471                 PyLongObject *product;
2472                 const Py_ssize_t nbtouse = MIN(bsize, asize);
2473
2474                 /* Multiply the next slice of b by a. */
2475                 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
2476                        nbtouse * sizeof(digit));
2477                 bslice->ob_size = nbtouse;
2478                 product = k_mul(a, bslice);
2479                 if (product == NULL)
2480                         goto fail;
2481
2482                 /* Add into result. */
2483                 (void)v_iadd(ret->ob_digit + nbdone, ret->ob_size - nbdone,
2484                              product->ob_digit, product->ob_size);
2485                 Py_DECREF(product);
2486
2487                 bsize -= nbtouse;
2488                 nbdone += nbtouse;
2489         }
2490
2491         Py_DECREF(bslice);
2492         return long_normalize(ret);
2493
2494  fail:
2495         Py_DECREF(ret);
2496         Py_XDECREF(bslice);
2497         return NULL;
2498 }
2499
2500 static PyObject *
2501 long_mul(PyLongObject *v, PyLongObject *w)
2502 {
2503         PyLongObject *a, *b, *z;
2504
2505         if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
2506                 Py_INCREF(Py_NotImplemented);
2507                 return Py_NotImplemented;
2508         }
2509
2510         z = k_mul(a, b);
2511         /* Negate if exactly one of the inputs is negative. */
2512         if (((a->ob_size ^ b->ob_size) < 0) && z)
2513                 z->ob_size = -(z->ob_size);
2514         Py_DECREF(a);
2515         Py_DECREF(b);
2516         return (PyObject *)z;
2517 }
2518
2519 /* The / and % operators are now defined in terms of divmod().
2520    The expression a mod b has the value a - b*floor(a/b).
2521    The long_divrem function gives the remainder after division of
2522    |a| by |b|, with the sign of a.  This is also expressed
2523    as a - b*trunc(a/b), if trunc truncates towards zero.
2524    Some examples:
2525          a       b      a rem b         a mod b
2526          13      10      3               3
2527         -13      10     -3               7
2528          13     -10      3              -7
2529         -13     -10     -3              -3
2530    So, to get from rem to mod, we have to add b if a and b
2531    have different signs.  We then subtract one from the 'div'
2532    part of the outcome to keep the invariant intact. */
2533
2534 /* Compute
2535  *     *pdiv, *pmod = divmod(v, w)
2536  * NULL can be passed for pdiv or pmod, in which case that part of
2537  * the result is simply thrown away.  The caller owns a reference to
2538  * each of these it requests (does not pass NULL for).
2539  */
2540 static int
2541 l_divmod(PyLongObject *v, PyLongObject *w,
2542          PyLongObject **pdiv, PyLongObject **pmod)
2543 {
2544         PyLongObject *div, *mod;
2545
2546         if (long_divrem(v, w, &div, &mod) < 0)
2547                 return -1;
2548         if ((mod->ob_size < 0 && w->ob_size > 0) ||
2549             (mod->ob_size > 0 && w->ob_size < 0)) {
2550                 PyLongObject *temp;
2551                 PyLongObject *one;
2552                 temp = (PyLongObject *) long_add(mod, w);
2553                 Py_DECREF(mod);
2554                 mod = temp;
2555                 if (mod == NULL) {
2556                         Py_DECREF(div);
2557                         return -1;
2558                 }
2559                 one = (PyLongObject *) PyLong_FromLong(1L);
2560                 if (one == NULL ||
2561                     (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
2562                         Py_DECREF(mod);
2563                         Py_DECREF(div);
2564                         Py_XDECREF(one);
2565                         return -1;
2566                 }
2567                 Py_DECREF(one);
2568                 Py_DECREF(div);
2569                 div = temp;
2570         }
2571         if (pdiv != NULL)
2572                 *pdiv = div;
2573         else
2574                 Py_DECREF(div);
2575
2576         if (pmod != NULL)
2577                 *pmod = mod;
2578         else
2579                 Py_DECREF(mod);
2580
2581         return 0;
2582 }
2583
2584 static PyObject *
2585 long_div(PyObject *v, PyObject *w)
2586 {
2587         PyLongObject *a, *b, *div;
2588
2589         CONVERT_BINOP(v, w, &a, &b);
2590         if (l_divmod(a, b, &div, NULL) < 0)
2591                 div = NULL;
2592         Py_DECREF(a);
2593         Py_DECREF(b);
2594         return (PyObject *)div;
2595 }
2596
2597 static PyObject *
2598 long_classic_div(PyObject *v, PyObject *w)
2599 {
2600         PyLongObject *a, *b, *div;
2601
2602         CONVERT_BINOP(v, w, &a, &b);
2603         if (Py_DivisionWarningFlag &&
2604             PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
2605                 div = NULL;
2606         else if (l_divmod(a, b, &div, NULL) < 0)
2607                 div = NULL;
2608         Py_DECREF(a);
2609         Py_DECREF(b);
2610         return (PyObject *)div;
2611 }
2612
2613 static PyObject *
2614 long_true_divide(PyObject *v, PyObject *w)
2615 {
2616         PyLongObject *a, *b;
2617         double ad, bd;
2618         int failed, aexp = -1, bexp = -1;
2619
2620         CONVERT_BINOP(v, w, &a, &b);
2621         ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
2622         bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
2623         failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
2624         Py_DECREF(a);
2625         Py_DECREF(b);
2626         if (failed)
2627                 return NULL;
2628         /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
2629            but should really be set correctly after sucessful calls to
2630            _PyLong_AsScaledDouble() */
2631         assert(aexp >= 0 && bexp >= 0);
2632
2633         if (bd == 0.0) {
2634                 PyErr_SetString(PyExc_ZeroDivisionError,
2635                         "long division or modulo by zero");
2636                 return NULL;
2637         }
2638
2639         /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */
2640         ad /= bd;       /* overflow/underflow impossible here */
2641         aexp -= bexp;
2642         if (aexp > INT_MAX / SHIFT)
2643                 goto overflow;
2644         else if (aexp < -(INT_MAX / SHIFT))
2645                 return PyFloat_FromDouble(0.0); /* underflow to 0 */
2646         errno = 0;
2647         ad = ldexp(ad, aexp * SHIFT);
2648         if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
2649                 goto overflow;
2650         return PyFloat_FromDouble(ad);
2651
2652 overflow:
2653         PyErr_SetString(PyExc_OverflowError,
2654                 "long/long too large for a float");
2655         return NULL;
2656
2657 }
2658
2659 static PyObject *
2660 long_mod(PyObject *v, PyObject *w)
2661 {
2662         PyLongObject *a, *b, *mod;
2663
2664         CONVERT_BINOP(v, w, &a, &b);
2665
2666         if (l_divmod(a, b, NULL, &mod) < 0)
2667                 mod = NULL;
2668         Py_DECREF(a);
2669         Py_DECREF(b);
2670         return (PyObject *)mod;
2671 }
2672
2673 static PyObject *
2674 long_divmod(PyObject *v, PyObject *w)
2675 {
2676         PyLongObject *a, *b, *div, *mod;
2677         PyObject *z;
2678
2679         CONVERT_BINOP(v, w, &a, &b);
2680
2681         if (l_divmod(a, b, &div, &mod) < 0) {
2682                 Py_DECREF(a);
2683                 Py_DECREF(b);
2684                 return NULL;
2685         }
2686         z = PyTuple_New(2);
2687         if (z != NULL) {
2688                 PyTuple_SetItem(z, 0, (PyObject *) div);
2689                 PyTuple_SetItem(z, 1, (PyObject *) mod);
2690         }
2691         else {
2692                 Py_DECREF(div);
2693                 Py_DECREF(mod);
2694         }
2695         Py_DECREF(a);
2696         Py_DECREF(b);
2697         return z;
2698 }
2699
2700 /* pow(v, w, x) */
2701 static PyObject *
2702 long_pow(PyObject *v, PyObject *w, PyObject *x)
2703 {
2704         PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
2705         int negativeOutput = 0;  /* if x<0 return negative output */
2706
2707         PyLongObject *z = NULL;  /* accumulated result */
2708         Py_ssize_t i, j, k;             /* counters */
2709         PyLongObject *temp = NULL;
2710
2711         /* 5-ary values.  If the exponent is large enough, table is
2712          * precomputed so that table[i] == a**i % c for i in range(32).
2713          */
2714         PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2715                                    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
2716
2717         /* a, b, c = v, w, x */
2718         CONVERT_BINOP(v, w, &a, &b);
2719         if (PyLong_Check(x)) {
2720                 c = (PyLongObject *)x;
2721                 Py_INCREF(x);
2722         }
2723         else if (PyInt_Check(x)) {
2724                 c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x));
2725                 if (c == NULL)
2726                         goto Error;
2727         }
2728         else if (x == Py_None)
2729                 c = NULL;
2730         else {
2731                 Py_DECREF(a);
2732                 Py_DECREF(b);
2733                 Py_INCREF(Py_NotImplemented);
2734                 return Py_NotImplemented;
2735         }
2736
2737         if (b->ob_size < 0) {  /* if exponent is negative */
2738                 if (c) {
2739                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
2740                             "cannot be negative when 3rd argument specified");
2741                         goto Error;
2742                 }
2743                 else {
2744                         /* else return a float.  This works because we know
2745                            that this calls float_pow() which converts its
2746                            arguments to double. */
2747                         Py_DECREF(a);
2748                         Py_DECREF(b);
2749                         return PyFloat_Type.tp_as_number->nb_power(v, w, x);
2750                 }
2751         }
2752
2753         if (c) {
2754                 /* if modulus == 0:
2755                        raise ValueError() */
2756                 if (c->ob_size == 0) {
2757                         PyErr_SetString(PyExc_ValueError,
2758                                         "pow() 3rd argument cannot be 0");
2759                         goto Error;
2760                 }
2761
2762                 /* if modulus < 0:
2763                        negativeOutput = True
2764                        modulus = -modulus */
2765                 if (c->ob_size < 0) {
2766                         negativeOutput = 1;
2767                         temp = (PyLongObject *)_PyLong_Copy(c);
2768                         if (temp == NULL)
2769                                 goto Error;
2770                         Py_DECREF(c);
2771                         c = temp;
2772                         temp = NULL;
2773                         c->ob_size = - c->ob_size;
2774                 }
2775
2776                 /* if modulus == 1:
2777                        return 0 */
2778                 if ((c->ob_size == 1) && (c->ob_digit[0] == 1)) {
2779                         z = (PyLongObject *)PyLong_FromLong(0L);
2780                         goto Done;
2781                 }
2782
2783                 /* if base < 0:
2784                        base = base % modulus
2785                    Having the base positive just makes things easier. */
2786                 if (a->ob_size < 0) {
2787                         if (l_divmod(a, c, NULL, &temp) < 0)
2788                                 goto Error;
2789                         Py_DECREF(a);
2790                         a = temp;
2791                         temp = NULL;
2792                 }
2793         }
2794
2795         /* At this point a, b, and c are guaranteed non-negative UNLESS
2796            c is NULL, in which case a may be negative. */
2797
2798         z = (PyLongObject *)PyLong_FromLong(1L);
2799         if (z == NULL)
2800                 goto Error;
2801
2802         /* Perform a modular reduction, X = X % c, but leave X alone if c
2803          * is NULL.
2804          */
2805 #define REDUCE(X)                                       \
2806         if (c != NULL) {                                \
2807                 if (l_divmod(X, c, NULL, &temp) < 0)    \
2808                         goto Error;                     \
2809                 Py_XDECREF(X);                          \
2810                 X = temp;                               \
2811                 temp = NULL;                            \
2812         }
2813
2814         /* Multiply two values, then reduce the result:
2815            result = X*Y % c.  If c is NULL, skip the mod. */
2816 #define MULT(X, Y, result)                              \
2817 {                                                       \
2818         temp = (PyLongObject *)long_mul(X, Y);          \
2819         if (temp == NULL)                               \
2820                 goto Error;                             \
2821         Py_XDECREF(result);                             \
2822         result = temp;                                  \
2823         temp = NULL;                                    \
2824         REDUCE(result)                                  \
2825 }
2826
2827         if (b->ob_size <= FIVEARY_CUTOFF) {
2828                 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
2829                 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
2830                 for (i = b->ob_size - 1; i >= 0; --i) {
2831                         digit bi = b->ob_digit[i];
2832
2833                         for (j = 1 << (SHIFT-1); j != 0; j >>= 1) {
2834                                 MULT(z, z, z)
2835                                 if (bi & j)
2836                                         MULT(z, a, z)
2837                         }
2838                 }
2839         }
2840         else {
2841                 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
2842                 Py_INCREF(z);   /* still holds 1L */
2843                 table[0] = z;
2844                 for (i = 1; i < 32; ++i)
2845                         MULT(table[i-1], a, table[i])
2846
2847                 for (i = b->ob_size - 1; i >= 0; --i) {
2848                         const digit bi = b->ob_digit[i];
2849
2850                         for (j = SHIFT - 5; j >= 0; j -= 5) {
2851                                 const int index = (bi >> j) & 0x1f;
2852                                 for (k = 0; k < 5; ++k)
2853                                         MULT(z, z, z)
2854                                 if (index)
2855                                         MULT(z, table[index], z)
2856                         }
2857                 }
2858         }
2859
2860         if (negativeOutput && (z->ob_size != 0)) {
2861                 temp = (PyLongObject *)long_sub(z, c);
2862                 if (temp == NULL)
2863                         goto Error;
2864                 Py_DECREF(z);
2865                 z = temp;
2866                 temp = NULL;
2867         }
2868         goto Done;
2869
2870  Error:
2871         if (z != NULL) {
2872                 Py_DECREF(z);
2873                 z = NULL;
2874         }
2875         /* fall through */
2876  Done:
2877         if (b->ob_size > FIVEARY_CUTOFF) {
2878                 for (i = 0; i < 32; ++i)
2879                         Py_XDECREF(table[i]);
2880         }
2881         Py_DECREF(a);
2882         Py_DECREF(b);
2883         Py_XDECREF(c);
2884         Py_XDECREF(temp);
2885         return (PyObject *)z;
2886 }
2887
2888 static PyObject *
2889 long_invert(PyLongObject *v)
2890 {
2891         /* Implement ~x as -(x+1) */
2892         PyLongObject *x;
2893         PyLongObject *w;
2894         w = (PyLongObject *)PyLong_FromLong(1L);
2895         if (w == NULL)
2896                 return NULL;
2897         x = (PyLongObject *) long_add(v, w);
2898         Py_DECREF(w);
2899         if (x == NULL)
2900                 return NULL;
2901         x->ob_size = -(x->ob_size);
2902         return (PyObject *)x;
2903 }
2904
2905 static PyObject *
2906 long_pos(PyLongObject *v)
2907 {
2908         if (PyLong_CheckExact(v)) {
2909                 Py_INCREF(v);
2910                 return (PyObject *)v;
2911         }
2912         else
2913                 return _PyLong_Copy(v);
2914 }
2915
2916 static PyObject *
2917 long_neg(PyLongObject *v)
2918 {
2919         PyLongObject *z;
2920         if (v->ob_size == 0 && PyLong_CheckExact(v)) {
2921                 /* -0 == 0 */
2922                 Py_INCREF(v);
2923                 return (PyObject *) v;
2924         }
2925         z = (PyLongObject *)_PyLong_Copy(v);
2926         if (z != NULL)
2927                 z->ob_size = -(v->ob_size);
2928         return (PyObject *)z;
2929 }
2930
2931 static PyObject *
2932 long_abs(PyLongObject *v)
2933 {
2934         if (v->ob_size < 0)
2935                 return long_neg(v);
2936         else
2937                 return long_pos(v);
2938 }
2939
2940 static int
2941 long_nonzero(PyLongObject *v)
2942 {
2943         return ABS(v->ob_size) != 0;
2944 }
2945
2946 static PyObject *
2947 long_rshift(PyLongObject *v, PyLongObject *w)
2948 {
2949         PyLongObject *a, *b;
2950         PyLongObject *z = NULL;
2951         long shiftby;
2952         Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
2953         digit lomask, himask;
2954
2955         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2956
2957         if (a->ob_size < 0) {
2958                 /* Right shifting negative numbers is harder */
2959                 PyLongObject *a1, *a2;
2960                 a1 = (PyLongObject *) long_invert(a);
2961                 if (a1 == NULL)
2962                         goto rshift_error;
2963                 a2 = (PyLongObject *) long_rshift(a1, b);
2964                 Py_DECREF(a1);
2965                 if (a2 == NULL)
2966                         goto rshift_error;
2967                 z = (PyLongObject *) long_invert(a2);
2968                 Py_DECREF(a2);
2969         }
2970         else {
2971
2972                 shiftby = PyLong_AsLong((PyObject *)b);
2973                 if (shiftby == -1L && PyErr_Occurred())
2974                         goto rshift_error;
2975                 if (shiftby < 0) {
2976                         PyErr_SetString(PyExc_ValueError,
2977                                         "negative shift count");
2978                         goto rshift_error;
2979                 }
2980                 wordshift = shiftby / SHIFT;
2981                 newsize = ABS(a->ob_size) - wordshift;
2982                 if (newsize <= 0) {
2983                         z = _PyLong_New(0);
2984                         Py_DECREF(a);
2985                         Py_DECREF(b);
2986                         return (PyObject *)z;
2987                 }
2988                 loshift = shiftby % SHIFT;
2989                 hishift = SHIFT - loshift;
2990                 lomask = ((digit)1 << hishift) - 1;
2991                 himask = MASK ^ lomask;
2992                 z = _PyLong_New(newsize);
2993                 if (z == NULL)
2994                         goto rshift_error;
2995                 if (a->ob_size < 0)
2996                         z->ob_size = -(z->ob_size);
2997                 for (i = 0, j = wordshift; i < newsize; i++, j++) {
2998                         z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
2999                         if (i+1 < newsize)
3000                                 z->ob_digit[i] |=
3001                                   (a->ob_digit[j+1] << hishift) & himask;
3002                 }
3003                 z = long_normalize(z);
3004         }
3005 rshift_error:
3006         Py_DECREF(a);
3007         Py_DECREF(b);
3008         return (PyObject *) z;
3009
3010 }
3011
3012 static PyObject *
3013 long_lshift(PyObject *v, PyObject *w)
3014 {
3015         /* This version due to Tim Peters */
3016         PyLongObject *a, *b;
3017         PyLongObject *z = NULL;
3018         long shiftby;
3019         Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
3020         twodigits accum;
3021
3022         CONVERT_BINOP(v, w, &a, &b);
3023
3024         shiftby = PyLong_AsLong((PyObject *)b);
3025         if (shiftby == -1L && PyErr_Occurred())
3026                 goto lshift_error;
3027         if (shiftby < 0) {
3028                 PyErr_SetString(PyExc_ValueError, "negative shift count");
3029                 goto lshift_error;
3030         }
3031         if ((long)(int)shiftby != shiftby) {
3032                 PyErr_SetString(PyExc_ValueError,
3033                                 "outrageous left shift count");
3034                 goto lshift_error;
3035         }
3036         /* wordshift, remshift = divmod(shiftby, SHIFT) */
3037         wordshift = (int)shiftby / SHIFT;
3038         remshift  = (int)shiftby - wordshift * SHIFT;
3039
3040         oldsize = ABS(a->ob_size);
3041         newsize = oldsize + wordshift;
3042         if (remshift)
3043                 ++newsize;
3044         z = _PyLong_New(newsize);
3045         if (z == NULL)
3046                 goto lshift_error;
3047         if (a->ob_size < 0)
3048                 z->ob_size = -(z->ob_size);
3049         for (i = 0; i < wordshift; i++)
3050                 z->ob_digit[i] = 0;
3051         accum = 0;
3052         for (i = wordshift, j = 0; j < oldsize; i++, j++) {
3053                 accum |= (twodigits)a->ob_digit[j] << remshift;
3054                 z->ob_digit[i] = (digit)(accum & MASK);
3055                 accum >>= SHIFT;
3056         }
3057         if (remshift)
3058                 z->ob_digit[newsize-1] = (digit)accum;
3059         else
3060                 assert(!accum);
3061         z = long_normalize(z);
3062 lshift_error:
3063         Py_DECREF(a);
3064         Py_DECREF(b);
3065         return (PyObject *) z;
3066 }
3067
3068
3069 /* Bitwise and/xor/or operations */
3070
3071 static PyObject *
3072 long_bitwise(PyLongObject *a,
3073              int op,  /* '&', '|', '^' */
3074              PyLongObject *b)
3075 {
3076         digit maska, maskb; /* 0 or MASK */
3077         int negz;
3078         Py_ssize_t size_a, size_b, size_z;
3079         PyLongObject *z;
3080         int i;
3081         digit diga, digb;
3082         PyObject *v;
3083
3084         if (a->ob_size < 0) {
3085                 a = (PyLongObject *) long_invert(a);
3086                 if (a == NULL)
3087                         return NULL;
3088                 maska = MASK;
3089         }
3090         else {
3091                 Py_INCREF(a);
3092                 maska = 0;
3093         }
3094         if (b->ob_size < 0) {
3095                 b = (PyLongObject *) long_invert(b);
3096                 if (b == NULL) {
3097                         Py_DECREF(a);
3098                         return NULL;
3099                 }
3100                 maskb = MASK;
3101         }
3102         else {
3103                 Py_INCREF(b);
3104                 maskb = 0;
3105         }
3106
3107         negz = 0;
3108         switch (op) {
3109         case '^':
3110                 if (maska != maskb) {
3111                         maska ^= MASK;
3112                         negz = -1;
3113                 }
3114                 break;
3115         case '&':
3116                 if (maska && maskb) {
3117                         op = '|';
3118                         maska ^= MASK;
3119                         maskb ^= MASK;
3120                         negz = -1;
3121                 }
3122                 break;
3123         case '|':
3124                 if (maska || maskb) {
3125                         op = '&';
3126                         maska ^= MASK;
3127                         maskb ^= MASK;
3128                         negz = -1;
3129                 }
3130                 break;
3131         }
3132
3133         /* JRH: The original logic here was to allocate the result value (z)
3134            as the longer of the two operands.  However, there are some cases
3135            where the result is guaranteed to be shorter than that: AND of two
3136            positives, OR of two negatives: use the shorter number.  AND with
3137            mixed signs: use the positive number.  OR with mixed signs: use the
3138            negative number.  After the transformations above, op will be '&'
3139            iff one of these cases applies, and mask will be non-0 for operands
3140            whose length should be ignored.
3141         */
3142
3143         size_a = a->ob_size;
3144         size_b = b->ob_size;
3145         size_z = op == '&'
3146                 ? (maska
3147                    ? size_b
3148                    : (maskb ? size_a : MIN(size_a, size_b)))
3149                 : MAX(size_a, size_b);
3150         z = _PyLong_New(size_z);
3151         if (z == NULL) {
3152                 Py_XDECREF(a);
3153                 Py_XDECREF(b);
3154                 Py_XDECREF(z);
3155                 return NULL;
3156         }
3157
3158         for (i = 0; i < size_z; ++i) {
3159                 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
3160                 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
3161                 switch (op) {
3162                 case '&': z->ob_digit[i] = diga & digb; break;
3163                 case '|': z->ob_digit[i] = diga | digb; break;
3164                 case '^': z->ob_digit[i] = diga ^ digb; break;
3165                 }
3166         }
3167
3168         Py_DECREF(a);
3169         Py_DECREF(b);
3170         z = long_normalize(z);
3171         if (negz == 0)
3172                 return (PyObject *) z;
3173         v = long_invert(z);
3174         Py_DECREF(z);
3175         return v;
3176 }
3177
3178 static PyObject *
3179 long_and(PyObject *v, PyObject *w)
3180 {
3181         PyLongObject *a, *b;
3182         PyObject *c;
3183         CONVERT_BINOP(v, w, &a, &b);
3184         c = long_bitwise(a, '&', b);
3185         Py_DECREF(a);
3186         Py_DECREF(b);
3187         return c;
3188 }
3189
3190 static PyObject *
3191 long_xor(PyObject *v, PyObject *w)
3192 {
3193         PyLongObject *a, *b;
3194         PyObject *c;
3195         CONVERT_BINOP(v, w, &a, &b);
3196         c = long_bitwise(a, '^', b);
3197         Py_DECREF(a);
3198         Py_DECREF(b);
3199         return c;
3200 }
3201
3202 static PyObject *
3203 long_or(PyObject *v, PyObject *w)
3204 {
3205         PyLongObject *a, *b;
3206         PyObject *c;
3207         CONVERT_BINOP(v, w, &a, &b);
3208         c = long_bitwise(a, '|', b);
3209         Py_DECREF(a);
3210         Py_DECREF(b);
3211         return c;
3212 }
3213
3214 static int
3215 long_coerce(PyObject **pv, PyObject **pw)
3216 {
3217         if (PyInt_Check(*pw)) {
3218                 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
3219                 Py_INCREF(*pv);
3220                 return 0;
3221         }
3222         else if (PyLong_Check(*pw)) {
3223                 Py_INCREF(*pv);
3224                 Py_INCREF(*pw);
3225                 return 0;
3226         }
3227         return 1; /* Can't do it */
3228 }
3229
3230 static PyObject *
3231 long_long(PyObject *v)
3232 {
3233         if (PyLong_CheckExact(v))
3234                 Py_INCREF(v);
3235         else
3236                 v = _PyLong_Copy((PyLongObject *)v);
3237         return v;
3238 }
3239
3240 static PyObject *
3241 long_int(PyObject *v)
3242 {
3243         long x;
3244         x = PyLong_AsLong(v);
3245         if (PyErr_Occurred()) {
3246                 if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
3247                                 PyErr_Clear();
3248                                 if (PyLong_CheckExact(v)) {
3249                                         Py_INCREF(v);
3250                                         return v;
3251                                 }
3252                                 else
3253                                         return _PyLong_Copy((PyLongObject *)v);
3254                 }
3255                 else
3256                         return NULL;
3257         }
3258         return PyInt_FromLong(x);
3259 }
3260
3261 static PyObject *
3262 long_float(PyObject *v)
3263 {
3264         double result;
3265         result = PyLong_AsDouble(v);
3266         if (result == -1.0 && PyErr_Occurred())
3267                 return NULL;
3268         return PyFloat_FromDouble(result);
3269 }
3270
3271 static PyObject *
3272 long_oct(PyObject *v)
3273 {
3274         return long_format(v, 8, 1);
3275 }
3276
3277 static PyObject *
3278 long_hex(PyObject *v)
3279 {
3280         return long_format(v, 16, 1);
3281 }
3282
3283 static PyObject *
3284 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
3285
3286 static PyObject *
3287 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3288 {
3289         PyObject *x = NULL;
3290         int base = -909;                     /* unlikely! */
3291         static char *kwlist[] = {"x", "base", 0};
3292
3293         if (type != &PyLong_Type)
3294                 return long_subtype_new(type, args, kwds); /* Wimp out */
3295         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
3296                                          &x, &base))
3297                 return NULL;
3298         if (x == NULL)
3299                 return PyLong_FromLong(0L);
3300         if (base == -909)
3301                 return PyNumber_Long(x);
3302         else if (PyString_Check(x))
3303                 return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
3304 #ifdef Py_USING_UNICODE
3305         else if (PyUnicode_Check(x))
3306                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
3307                                           PyUnicode_GET_SIZE(x),
3308                                           base);
3309 #endif
3310         else {
3311                 PyErr_SetString(PyExc_TypeError,
3312                         "long() can't convert non-string with explicit base");
3313                 return NULL;
3314         }
3315 }
3316
3317 /* Wimpy, slow approach to tp_new calls for subtypes of long:
3318    first create a regular long from whatever arguments we got,
3319    then allocate a subtype instance and initialize it from
3320    the regular long.  The regular long is then thrown away.
3321 */
3322 static PyObject *
3323 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3324 {
3325         PyLongObject *tmp, *newobj;
3326         Py_ssize_t i, n;
3327
3328         assert(PyType_IsSubtype(type, &PyLong_Type));
3329         tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
3330         if (tmp == NULL)
3331                 return NULL;
3332         assert(PyLong_CheckExact(tmp));
3333         n = tmp->ob_size;
3334         if (n < 0)
3335                 n = -n;
3336         newobj = (PyLongObject *)type->tp_alloc(type, n);
3337         if (newobj == NULL) {
3338                 Py_DECREF(tmp);
3339                 return NULL;
3340         }
3341         assert(PyLong_Check(newobj));
3342         newobj->ob_size = tmp->ob_size;
3343         for (i = 0; i < n; i++)
3344                 newobj->ob_digit[i] = tmp->ob_digit[i];
3345         Py_DECREF(tmp);
3346         return (PyObject *)newobj;
3347 }
3348
3349 static PyObject *
3350 long_getnewargs(PyLongObject *v)
3351 {
3352         return Py_BuildValue("(N)", _PyLong_Copy(v));
3353 }
3354
3355 static PyMethodDef long_methods[] = {
3356         {"__getnewargs__",      (PyCFunction)long_getnewargs,   METH_NOARGS},
3357         {NULL,          NULL}           /* sentinel */
3358 };
3359
3360 PyDoc_STRVAR(long_doc,
3361 "long(x[, base]) -> integer\n\
3362 \n\
3363 Convert a string or number to a long integer, if possible.  A floating\n\
3364 point argument will be truncated towards zero (this does not include a\n\
3365 string representation of a floating point number!)  When converting a\n\
3366 string, use the optional base.  It is an error to supply a base when\n\
3367 converting a non-string.");
3368
3369 static PyNumberMethods long_as_number = {
3370         (binaryfunc)    long_add,       /*nb_add*/
3371         (binaryfunc)    long_sub,       /*nb_subtract*/
3372         (binaryfunc)    long_mul,       /*nb_multiply*/
3373                         long_classic_div, /*nb_divide*/
3374                         long_mod,       /*nb_remainder*/
3375                         long_divmod,    /*nb_divmod*/
3376                         long_pow,       /*nb_power*/
3377         (unaryfunc)     long_neg,       /*nb_negative*/
3378         (unaryfunc)     long_pos,       /*tp_positive*/
3379         (unaryfunc)     long_abs,       /*tp_absolute*/
3380         (inquiry)       long_nonzero,   /*tp_nonzero*/
3381         (unaryfunc)     long_invert,    /*nb_invert*/
3382                         long_lshift,    /*nb_lshift*/
3383         (binaryfunc)    long_rshift,    /*nb_rshift*/
3384                         long_and,       /*nb_and*/
3385                         long_xor,       /*nb_xor*/
3386                         long_or,        /*nb_or*/
3387                         long_coerce,    /*nb_coerce*/
3388                         long_int,       /*nb_int*/
3389                         long_long,      /*nb_long*/
3390                         long_float,     /*nb_float*/
3391                         long_oct,       /*nb_oct*/
3392                         long_hex,       /*nb_hex*/
3393         0,                              /* nb_inplace_add */
3394         0,                              /* nb_inplace_subtract */
3395         0,                              /* nb_inplace_multiply */
3396         0,                              /* nb_inplace_divide */
3397         0,                              /* nb_inplace_remainder */
3398         0,                              /* nb_inplace_power */
3399         0,                              /* nb_inplace_lshift */
3400         0,                              /* nb_inplace_rshift */
3401         0,                              /* nb_inplace_and */
3402         0,                              /* nb_inplace_xor */
3403         0,                              /* nb_inplace_or */
3404         long_div,                       /* nb_floor_divide */
3405         long_true_divide,               /* nb_true_divide */
3406         0,                              /* nb_inplace_floor_divide */
3407         0,                              /* nb_inplace_true_divide */
3408         long_index,                     /* nb_index */
3409 };
3410
3411 PyTypeObject PyLong_Type = {
3412         PyObject_HEAD_INIT(&PyType_Type)
3413         0,                                      /* ob_size */
3414         "long",                                 /* tp_name */
3415         sizeof(PyLongObject) - sizeof(digit),   /* tp_basicsize */
3416         sizeof(digit),                          /* tp_itemsize */
3417         long_dealloc,                           /* tp_dealloc */
3418         0,                                      /* tp_print */
3419         0,                                      /* tp_getattr */
3420         0,                                      /* tp_setattr */
3421         (cmpfunc)long_compare,                  /* tp_compare */
3422         long_repr,                              /* tp_repr */
3423         &long_as_number,                        /* tp_as_number */
3424         0,                                      /* tp_as_sequence */
3425         0,                                      /* tp_as_mapping */
3426         (hashfunc)long_hash,                    /* tp_hash */
3427         0,                                      /* tp_call */
3428         long_str,                               /* tp_str */
3429         PyObject_GenericGetAttr,                /* tp_getattro */
3430         0,                                      /* tp_setattro */
3431         0,                                      /* tp_as_buffer */
3432         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
3433                 Py_TPFLAGS_BASETYPE,            /* tp_flags */
3434         long_doc,                               /* tp_doc */
3435         0,                                      /* tp_traverse */
3436         0,                                      /* tp_clear */
3437         0,                                      /* tp_richcompare */
3438         0,                                      /* tp_weaklistoffset */
3439         0,                                      /* tp_iter */
3440         0,                                      /* tp_iternext */
3441         long_methods,                           /* tp_methods */
3442         0,                                      /* tp_members */
3443         0,                                      /* tp_getset */
3444         0,                                      /* tp_base */
3445         0,                                      /* tp_dict */
3446         0,                                      /* tp_descr_get */
3447         0,                                      /* tp_descr_set */
3448         0,                                      /* tp_dictoffset */
3449         0,                                      /* tp_init */
3450         0,                                      /* tp_alloc */
3451         long_new,                               /* tp_new */
3452         PyObject_Del,                           /* tp_free */
3453 };