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