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