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 = z / _PyLong_DECIMAL_BASE;
1417                         pout[j] = z - (twodigits)hi * _PyLong_DECIMAL_BASE;
1418                 }
1419                 while (hi) {
1420                         pout[size++] = hi % _PyLong_DECIMAL_BASE;
1421                         hi /= _PyLong_DECIMAL_BASE;
1422                 }
1423                 /* check for keyboard interrupt */
1424                 SIGCHECK({
1425                         Py_DECREF(scratch);
1426                         return NULL;
1427                 })
1428         }
1429         /* pout should have at least one digit, so that the case when a = 0
1430            works correctly */
1431         if (size == 0)
1432                 pout[size++] = 0;
1433
1434         /* calculate exact length of output string, and allocate */
1435         strlen = (addL != 0) + negative +
1436                 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
1437         tenpow = 10;
1438         rem = pout[size-1];
1439         while (rem >= tenpow) {
1440                 tenpow *= 10;
1441                 strlen++;
1442         }
1443         str = PyString_FromStringAndSize(NULL, strlen);
1444         if (str == NULL) {
1445                 Py_DECREF(scratch);
1446                 return NULL;
1447         }
1448
1449         /* fill the string right-to-left */
1450         p = PyString_AS_STRING(str) + strlen;
1451         *p = '\0';
1452         if (addL)
1453                 *--p = 'L';
1454         /* pout[0] through pout[size-2] contribute exactly
1455            _PyLong_DECIMAL_SHIFT digits each */
1456         for (i=0; i < size - 1; i++) {
1457                 rem = pout[i];
1458                 for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) {
1459                         *--p = '0' + rem % 10;
1460                         rem /= 10;
1461                 }
1462         }
1463         /* pout[size-1]: always produce at least one decimal digit */
1464         rem = pout[i];
1465         do {
1466                 *--p = '0' + rem % 10;
1467                 rem /= 10;
1468         } while (rem != 0);
1469
1470         /* and sign */
1471         if (negative)
1472                 *--p = '-';
1473
1474         /* check we've counted correctly */
1475         assert(p == PyString_AS_STRING(str));
1476         Py_DECREF(scratch);
1477         return (PyObject *)str;
1478 }
1479
1480 /* Convert the long to a string object with given base,
1481    appending a base prefix of 0[box] if base is 2, 8 or 16.
1482    Add a trailing "L" if addL is non-zero.
1483    If newstyle is zero, then use the pre-2.6 behavior of octal having
1484    a leading "0", instead of the prefix "0o" */
1485 PyAPI_FUNC(PyObject *)
1486 _PyLong_Format(PyObject *aa, int base, int addL, int newstyle)
1487 {
1488         register PyLongObject *a = (PyLongObject *)aa;
1489         PyStringObject *str;
1490         Py_ssize_t i, sz;
1491         Py_ssize_t size_a;
1492         char *p;
1493         int bits;
1494         char sign = '\0';
1495
1496         if (base == 10)
1497                 return long_to_decimal_string((PyObject *)a, addL);
1498
1499         if (a == NULL || !PyLong_Check(a)) {
1500                 PyErr_BadInternalCall();
1501                 return NULL;
1502         }
1503         assert(base >= 2 && base <= 36);
1504         size_a = ABS(Py_SIZE(a));
1505
1506         /* Compute a rough upper bound for the length of the string */
1507         i = base;
1508         bits = 0;
1509         while (i > 1) {
1510                 ++bits;
1511                 i >>= 1;
1512         }
1513         i = 5 + (addL ? 1 : 0);
1514         /* ensure we don't get signed overflow in sz calculation */
1515         if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) {
1516                 PyErr_SetString(PyExc_OverflowError,
1517                                 "long is too large to format");
1518                 return NULL;
1519         }
1520         sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
1521         assert(sz >= 0);
1522         str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz);
1523         if (str == NULL)
1524                 return NULL;
1525         p = PyString_AS_STRING(str) + sz;
1526         *p = '\0';
1527         if (addL)
1528                 *--p = 'L';
1529         if (a->ob_size < 0)
1530                 sign = '-';
1531
1532         if (a->ob_size == 0) {
1533                 *--p = '0';
1534         }
1535         else if ((base & (base - 1)) == 0) {
1536                 /* JRH: special case for power-of-2 bases */
1537                 twodigits accum = 0;
1538                 int accumbits = 0;      /* # of bits in accum */
1539                 int basebits = 1;       /* # of bits in base-1 */
1540                 i = base;
1541                 while ((i >>= 1) > 1)
1542                         ++basebits;
1543
1544                 for (i = 0; i < size_a; ++i) {
1545                         accum |= (twodigits)a->ob_digit[i] << accumbits;
1546                         accumbits += PyLong_SHIFT;
1547                         assert(accumbits >= basebits);
1548                         do {
1549                                 char cdigit = (char)(accum & (base - 1));
1550                                 cdigit += (cdigit < 10) ? '0' : 'a'-10;
1551                                 assert(p > PyString_AS_STRING(str));
1552                                 *--p = cdigit;
1553                                 accumbits -= basebits;
1554                                 accum >>= basebits;
1555                         } while (i < size_a-1 ? accumbits >= basebits :
1556                                                 accum > 0);
1557                 }
1558         }
1559         else {
1560                 /* Not 0, and base not a power of 2.  Divide repeatedly by
1561                    base, but for speed use the highest power of base that
1562                    fits in a digit. */
1563                 Py_ssize_t size = size_a;
1564                 digit *pin = a->ob_digit;
1565                 PyLongObject *scratch;
1566                 /* powbasw <- largest power of base that fits in a digit. */
1567                 digit powbase = base;  /* powbase == base ** power */
1568                 int power = 1;
1569                 for (;;) {
1570                         twodigits newpow = powbase * (twodigits)base;
1571                         if (newpow >> PyLong_SHIFT)
1572                                 /* doesn't fit in a digit */
1573                                 break;
1574                         powbase = (digit)newpow;
1575                         ++power;
1576                 }
1577
1578                 /* Get a scratch area for repeated division. */
1579                 scratch = _PyLong_New(size);
1580                 if (scratch == NULL) {
1581                         Py_DECREF(str);
1582                         return NULL;
1583                 }
1584
1585                 /* Repeatedly divide by powbase. */
1586                 do {
1587                         int ntostore = power;
1588                         digit rem = inplace_divrem1(scratch->ob_digit,
1589                                                      pin, size, powbase);
1590                         pin = scratch->ob_digit; /* no need to use a again */
1591                         if (pin[size - 1] == 0)
1592                                 --size;
1593                         SIGCHECK({
1594                                 Py_DECREF(scratch);
1595                                 Py_DECREF(str);
1596                                 return NULL;
1597                         })
1598
1599                         /* Break rem into digits. */
1600                         assert(ntostore > 0);
1601                         do {
1602                                 digit nextrem = (digit)(rem / base);
1603                                 char c = (char)(rem - nextrem * base);
1604                                 assert(p > PyString_AS_STRING(str));
1605                                 c += (c < 10) ? '0' : 'a'-10;
1606                                 *--p = c;
1607                                 rem = nextrem;
1608                                 --ntostore;
1609                                 /* Termination is a bit delicate:  must not
1610                                    store leading zeroes, so must get out if
1611                                    remaining quotient and rem are both 0. */
1612                         } while (ntostore && (size || rem));
1613                 } while (size != 0);
1614                 Py_DECREF(scratch);
1615         }
1616
1617         if (base == 2) {
1618                 *--p = 'b';
1619                 *--p = '0';
1620         }
1621         else if (base == 8) {
1622                 if (newstyle) {
1623                         *--p = 'o';
1624                         *--p = '0';
1625                 }
1626                 else
1627                         if (size_a != 0)
1628                                 *--p = '0';
1629         }
1630         else if (base == 16) {
1631                 *--p = 'x';
1632                 *--p = '0';
1633         }
1634         else if (base != 10) {
1635                 *--p = '#';
1636                 *--p = '0' + base%10;
1637                 if (base > 10)
1638                         *--p = '0' + base/10;
1639         }
1640         if (sign)
1641                 *--p = sign;
1642         if (p != PyString_AS_STRING(str)) {
1643                 char *q = PyString_AS_STRING(str);
1644                 assert(p > q);
1645                 do {
1646                 } while ((*q++ = *p++) != '\0');
1647                 q--;
1648                 _PyString_Resize((PyObject **)&str,
1649                                  (Py_ssize_t) (q - PyString_AS_STRING(str)));
1650         }
1651         return (PyObject *)str;
1652 }
1653
1654 /* Table of digit values for 8-bit string -> integer conversion.
1655  * '0' maps to 0, ..., '9' maps to 9.
1656  * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1657  * All other indices map to 37.
1658  * Note that when converting a base B string, a char c is a legitimate
1659  * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B.
1660  */
1661 int _PyLong_DigitValue[256] = {
1662         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
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         0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  37, 37, 37, 37, 37, 37,
1666         37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1667         25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1668         37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1669         25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1670         37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 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 };
1679
1680 /* *str points to the first digit in a string of base `base` digits.  base
1681  * is a power of 2 (2, 4, 8, 16, or 32).  *str is set to point to the first
1682  * non-digit (which may be *str!).  A normalized long is returned.
1683  * The point to this routine is that it takes time linear in the number of
1684  * string characters.
1685  */
1686 static PyLongObject *
1687 long_from_binary_base(char **str, int base)
1688 {
1689         char *p = *str;
1690         char *start = p;
1691         int bits_per_char;
1692         Py_ssize_t n;
1693         PyLongObject *z;
1694         twodigits accum;
1695         int bits_in_accum;
1696         digit *pdigit;
1697
1698         assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
1699         n = base;
1700         for (bits_per_char = -1; n; ++bits_per_char)
1701                 n >>= 1;
1702         /* n <- total # of bits needed, while setting p to end-of-string */
1703         while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base)
1704                 ++p;
1705         *str = p;
1706         /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
1707         n = (p - start) * bits_per_char + PyLong_SHIFT - 1;
1708         if (n / bits_per_char < p - start) {
1709                 PyErr_SetString(PyExc_ValueError,
1710                                 "long string too large to convert");
1711                 return NULL;
1712         }
1713         n = n / PyLong_SHIFT;
1714         z = _PyLong_New(n);
1715         if (z == NULL)
1716                 return NULL;
1717         /* Read string from right, and fill in long from left; i.e.,
1718          * from least to most significant in both.
1719          */
1720         accum = 0;
1721         bits_in_accum = 0;
1722         pdigit = z->ob_digit;
1723         while (--p >= start) {
1724                 int k = _PyLong_DigitValue[Py_CHARMASK(*p)];
1725                 assert(k >= 0 && k < base);
1726                 accum |= (twodigits)k << bits_in_accum;
1727                 bits_in_accum += bits_per_char;
1728                 if (bits_in_accum >= PyLong_SHIFT) {
1729                         *pdigit++ = (digit)(accum & PyLong_MASK);
1730                         assert(pdigit - z->ob_digit <= n);
1731                         accum >>= PyLong_SHIFT;
1732                         bits_in_accum -= PyLong_SHIFT;
1733                         assert(bits_in_accum < PyLong_SHIFT);
1734                 }
1735         }
1736         if (bits_in_accum) {
1737                 assert(bits_in_accum <= PyLong_SHIFT);
1738                 *pdigit++ = (digit)accum;
1739                 assert(pdigit - z->ob_digit <= n);
1740         }
1741         while (pdigit - z->ob_digit < n)
1742                 *pdigit++ = 0;
1743         return long_normalize(z);
1744 }
1745
1746 PyObject *
1747 PyLong_FromString(char *str, char **pend, int base)
1748 {
1749         int sign = 1;
1750         char *start, *orig_str = str;
1751         PyLongObject *z;
1752         PyObject *strobj, *strrepr;
1753         Py_ssize_t slen;
1754
1755         if ((base != 0 && base < 2) || base > 36) {
1756                 PyErr_SetString(PyExc_ValueError,
1757                                 "long() arg 2 must be >= 2 and <= 36");
1758                 return NULL;
1759         }
1760         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1761                 str++;
1762         if (*str == '+')
1763                 ++str;
1764         else if (*str == '-') {
1765                 ++str;
1766                 sign = -1;
1767         }
1768         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1769                 str++;
1770         if (base == 0) {
1771                 /* No base given.  Deduce the base from the contents
1772                    of the string */
1773                 if (str[0] != '0')
1774                         base = 10;
1775                 else if (str[1] == 'x' || str[1] == 'X')
1776                         base = 16;
1777                 else if (str[1] == 'o' || str[1] == 'O')
1778                         base = 8;
1779                 else if (str[1] == 'b' || str[1] == 'B')
1780                         base = 2;
1781                 else
1782                         /* "old" (C-style) octal literal, still valid in
1783                            2.x, although illegal in 3.x */
1784                         base = 8;
1785         }
1786         /* Whether or not we were deducing the base, skip leading chars
1787            as needed */
1788         if (str[0] == '0' &&
1789             ((base == 16 && (str[1] == 'x' || str[1] == 'X')) ||
1790              (base == 8  && (str[1] == 'o' || str[1] == 'O')) ||
1791              (base == 2  && (str[1] == 'b' || str[1] == 'B'))))
1792                 str += 2;
1793
1794         start = str;
1795         if ((base & (base - 1)) == 0)
1796                 z = long_from_binary_base(&str, base);
1797         else {
1798 /***
1799 Binary bases can be converted in time linear in the number of digits, because
1800 Python's representation base is binary.  Other bases (including decimal!) use
1801 the simple quadratic-time algorithm below, complicated by some speed tricks.
1802
1803 First some math:  the largest integer that can be expressed in N base-B digits
1804 is B**N-1.  Consequently, if we have an N-digit input in base B, the worst-
1805 case number of Python digits needed to hold it is the smallest integer n s.t.
1806
1807     PyLong_BASE**n-1 >= B**N-1  [or, adding 1 to both sides]
1808     PyLong_BASE**n >= B**N      [taking logs to base PyLong_BASE]
1809     n >= log(B**N)/log(PyLong_BASE) = N * log(B)/log(PyLong_BASE)
1810
1811 The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so we can compute
1812 this quickly.  A Python long with that much space is reserved near the start,
1813 and the result is computed into it.
1814
1815 The input string is actually treated as being in base base**i (i.e., i digits
1816 are processed at a time), where two more static arrays hold:
1817
1818     convwidth_base[base] = the largest integer i such that base**i <= PyLong_BASE
1819     convmultmax_base[base] = base ** convwidth_base[base]
1820
1821 The first of these is the largest i such that i consecutive input digits
1822 must fit in a single Python digit.  The second is effectively the input
1823 base we're really using.
1824
1825 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
1826 convmultmax_base[base], the result is "simply"
1827
1828    (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1
1829
1830 where B = convmultmax_base[base].
1831
1832 Error analysis:  as above, the number of Python digits `n` needed is worst-
1833 case
1834
1835     n >= N * log(B)/log(PyLong_BASE)
1836
1837 where `N` is the number of input digits in base `B`.  This is computed via
1838
1839     size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1840
1841 below.  Two numeric concerns are how much space this can waste, and whether
1842 the computed result can be too small.  To be concrete, assume PyLong_BASE = 2**15,
1843 which is the default (and it's unlikely anyone changes that).
1844
1845 Waste isn't a problem:  provided the first input digit isn't 0, the difference
1846 between the worst-case input with N digits and the smallest input with N
1847 digits is about a factor of B, but B is small compared to PyLong_BASE so at most
1848 one allocated Python digit can remain unused on that count.  If
1849 N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating that
1850 and adding 1 returns a result 1 larger than necessary.  However, that can't
1851 happen:  whenever B is a power of 2, long_from_binary_base() is called
1852 instead, and it's impossible for B**i to be an integer power of 2**15 when
1853 B is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be
1854 an exact integer when B is not a power of 2, since B**i has a prime factor
1855 other than 2 in that case, but (2**15)**j's only prime factor is 2).
1856
1857 The computed result can be too small if the true value of N*log(B)/log(PyLong_BASE)
1858 is a little bit larger than an exact integer, but due to roundoff errors (in
1859 computing log(B), log(PyLong_BASE), their quotient, and/or multiplying that by N)
1860 yields a numeric result a little less than that integer.  Unfortunately, "how
1861 close can a transcendental function get to an integer over some range?"
1862 questions are generally theoretically intractable.  Computer analysis via
1863 continued fractions is practical:  expand log(B)/log(PyLong_BASE) via continued
1864 fractions, giving a sequence i/j of "the best" rational approximations.  Then
1865 j*log(B)/log(PyLong_BASE) is approximately equal to (the integer) i.  This shows that
1866 we can get very close to being in trouble, but very rarely.  For example,
1867 76573 is a denominator in one of the continued-fraction approximations to
1868 log(10)/log(2**15), and indeed:
1869
1870     >>> log(10)/log(2**15)*76573
1871     16958.000000654003
1872
1873 is very close to an integer.  If we were working with IEEE single-precision,
1874 rounding errors could kill us.  Finding worst cases in IEEE double-precision
1875 requires better-than-double-precision log() functions, and Tim didn't bother.
1876 Instead the code checks to see whether the allocated space is enough as each
1877 new Python digit is added, and copies the whole thing to a larger long if not.
1878 This should happen extremely rarely, and in fact I don't have a test case
1879 that triggers it(!).  Instead the code was tested by artificially allocating
1880 just 1 digit at the start, so that the copying code was exercised for every
1881 digit beyond the first.
1882 ***/
1883                 register twodigits c;   /* current input character */
1884                 Py_ssize_t size_z;
1885                 int i;
1886                 int convwidth;
1887                 twodigits convmultmax, convmult;
1888                 digit *pz, *pzstop;
1889                 char* scan;
1890
1891                 static double log_base_PyLong_BASE[37] = {0.0e0,};
1892                 static int convwidth_base[37] = {0,};
1893                 static twodigits convmultmax_base[37] = {0,};
1894
1895                 if (log_base_PyLong_BASE[base] == 0.0) {
1896                         twodigits convmax = base;
1897                         int i = 1;
1898
1899                         log_base_PyLong_BASE[base] = log((double)base) /
1900                                                 log((double)PyLong_BASE);
1901                         for (;;) {
1902                                 twodigits next = convmax * base;
1903                                 if (next > PyLong_BASE)
1904                                         break;
1905                                 convmax = next;
1906                                 ++i;
1907                         }
1908                         convmultmax_base[base] = convmax;
1909                         assert(i > 0);
1910                         convwidth_base[base] = i;
1911                 }
1912
1913                 /* Find length of the string of numeric characters. */
1914                 scan = str;
1915                 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base)
1916                         ++scan;
1917
1918                 /* Create a long object that can contain the largest possible
1919                  * integer with this base and length.  Note that there's no
1920                  * need to initialize z->ob_digit -- no slot is read up before
1921                  * being stored into.
1922                  */
1923                 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1;
1924                 /* Uncomment next line to test exceedingly rare copy code */
1925                 /* size_z = 1; */
1926                 assert(size_z > 0);
1927                 z = _PyLong_New(size_z);
1928                 if (z == NULL)
1929                         return NULL;
1930                 Py_SIZE(z) = 0;
1931
1932                 /* `convwidth` consecutive input digits are treated as a single
1933                  * digit in base `convmultmax`.
1934                  */
1935                 convwidth = convwidth_base[base];
1936                 convmultmax = convmultmax_base[base];
1937
1938                 /* Work ;-) */
1939                 while (str < scan) {
1940                         /* grab up to convwidth digits from the input string */
1941                         c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
1942                         for (i = 1; i < convwidth && str != scan; ++i, ++str) {
1943                                 c = (twodigits)(c *  base +
1944                                         _PyLong_DigitValue[Py_CHARMASK(*str)]);
1945                                 assert(c < PyLong_BASE);
1946                         }
1947
1948                         convmult = convmultmax;
1949                         /* Calculate the shift only if we couldn't get
1950                          * convwidth digits.
1951                          */
1952                         if (i != convwidth) {
1953                                 convmult = base;
1954                                 for ( ; i > 1; --i)
1955                                         convmult *= base;
1956                         }
1957
1958                         /* Multiply z by convmult, and add c. */
1959                         pz = z->ob_digit;
1960                         pzstop = pz + Py_SIZE(z);
1961                         for (; pz < pzstop; ++pz) {
1962                                 c += (twodigits)*pz * convmult;
1963                                 *pz = (digit)(c & PyLong_MASK);
1964                                 c >>= PyLong_SHIFT;
1965                         }
1966                         /* carry off the current end? */
1967                         if (c) {
1968                                 assert(c < PyLong_BASE);
1969                                 if (Py_SIZE(z) < size_z) {
1970                                         *pz = (digit)c;
1971                                         ++Py_SIZE(z);
1972                                 }
1973                                 else {
1974                                         PyLongObject *tmp;
1975                                         /* Extremely rare.  Get more space. */
1976                                         assert(Py_SIZE(z) == size_z);
1977                                         tmp = _PyLong_New(size_z + 1);
1978                                         if (tmp == NULL) {
1979                                                 Py_DECREF(z);
1980                                                 return NULL;
1981                                         }
1982                                         memcpy(tmp->ob_digit,
1983                                                z->ob_digit,
1984                                                sizeof(digit) * size_z);
1985                                         Py_DECREF(z);
1986                                         z = tmp;
1987                                         z->ob_digit[size_z] = (digit)c;
1988                                         ++size_z;
1989                                 }
1990                         }
1991                 }
1992         }
1993         if (z == NULL)
1994                 return NULL;
1995         if (str == start)
1996                 goto onError;
1997         if (sign < 0)
1998                 Py_SIZE(z) = -(Py_SIZE(z));
1999         if (*str == 'L' || *str == 'l')
2000                 str++;
2001         while (*str && isspace(Py_CHARMASK(*str)))
2002                 str++;
2003         if (*str != '\0')
2004                 goto onError;
2005         if (pend)
2006                 *pend = str;
2007         return (PyObject *) z;
2008
2009  onError:
2010         Py_XDECREF(z);
2011         slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
2012         strobj = PyString_FromStringAndSize(orig_str, slen);
2013         if (strobj == NULL)
2014                 return NULL;
2015         strrepr = PyObject_Repr(strobj);
2016         Py_DECREF(strobj);
2017         if (strrepr == NULL)
2018                 return NULL;
2019         PyErr_Format(PyExc_ValueError,
2020                      "invalid literal for long() with base %d: %s",
2021                      base, PyString_AS_STRING(strrepr));
2022         Py_DECREF(strrepr);
2023         return NULL;
2024 }
2025
2026 #ifdef Py_USING_UNICODE
2027 PyObject *
2028 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
2029 {
2030         PyObject *result;
2031         char *buffer = (char *)PyMem_MALLOC(length+1);
2032
2033         if (buffer == NULL)
2034                 return NULL;
2035
2036         if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) {
2037                 PyMem_FREE(buffer);
2038                 return NULL;
2039         }
2040         result = PyLong_FromString(buffer, NULL, base);
2041         PyMem_FREE(buffer);
2042         return result;
2043 }
2044 #endif
2045
2046 /* forward */
2047 static PyLongObject *x_divrem
2048         (PyLongObject *, PyLongObject *, PyLongObject **);
2049 static PyObject *long_long(PyObject *v);
2050
2051 /* Long division with remainder, top-level routine */
2052
2053 static int
2054 long_divrem(PyLongObject *a, PyLongObject *b,
2055             PyLongObject **pdiv, PyLongObject **prem)
2056 {
2057         Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2058         PyLongObject *z;
2059
2060         if (size_b == 0) {
2061                 PyErr_SetString(PyExc_ZeroDivisionError,
2062                                 "long division or modulo by zero");
2063                 return -1;
2064         }
2065         if (size_a < size_b ||
2066             (size_a == size_b &&
2067              a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2068                 /* |a| < |b|. */
2069                 *pdiv = _PyLong_New(0);
2070                 if (*pdiv == NULL)
2071                         return -1;
2072                 Py_INCREF(a);
2073                 *prem = (PyLongObject *) a;
2074                 return 0;
2075         }
2076         if (size_b == 1) {
2077                 digit rem = 0;
2078                 z = divrem1(a, b->ob_digit[0], &rem);
2079                 if (z == NULL)
2080                         return -1;
2081                 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
2082                 if (*prem == NULL) {
2083                         Py_DECREF(z);
2084                         return -1;
2085                 }
2086         }
2087         else {
2088                 z = x_divrem(a, b, prem);
2089                 if (z == NULL)
2090                         return -1;
2091         }
2092         /* Set the signs.
2093            The quotient z has the sign of a*b;
2094            the remainder r has the sign of a,
2095            so a = b*z + r. */
2096         if ((a->ob_size < 0) != (b->ob_size < 0))
2097                 z->ob_size = -(z->ob_size);
2098         if (a->ob_size < 0 && (*prem)->ob_size != 0)
2099                 (*prem)->ob_size = -((*prem)->ob_size);
2100         *pdiv = z;
2101         return 0;
2102 }
2103
2104 /* Unsigned long division with remainder -- the algorithm.  The arguments v1
2105    and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */
2106
2107 static PyLongObject *
2108 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
2109 {
2110         PyLongObject *v, *w, *a;
2111         Py_ssize_t i, k, size_v, size_w;
2112         int d;
2113         digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak;
2114         twodigits vv;
2115         sdigit zhi;
2116         stwodigits z;
2117
2118         /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
2119            edn.), section 4.3.1, Algorithm D], except that we don't explicitly
2120            handle the special case when the initial estimate q for a quotient
2121            digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
2122            that won't overflow a digit. */
2123
2124         /* allocate space; w will also be used to hold the final remainder */
2125         size_v = ABS(Py_SIZE(v1));
2126         size_w = ABS(Py_SIZE(w1));
2127         assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
2128         v = _PyLong_New(size_v+1);
2129         if (v == NULL) {
2130                 *prem = NULL;
2131                 return NULL;
2132         }
2133         w = _PyLong_New(size_w);
2134         if (w == NULL) {
2135                 Py_DECREF(v);
2136                 *prem = NULL;
2137                 return NULL;
2138         }
2139
2140         /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
2141            shift v1 left by the same amount.  Results go into w and v. */
2142         d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
2143         carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
2144         assert(carry == 0);
2145         carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
2146         if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
2147                 v->ob_digit[size_v] = carry;
2148                 size_v++;
2149         }
2150
2151         /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
2152            at most (and usually exactly) k = size_v - size_w digits. */
2153         k = size_v - size_w;
2154         assert(k >= 0);
2155         a = _PyLong_New(k);
2156         if (a == NULL) {
2157                 Py_DECREF(w);
2158                 Py_DECREF(v);
2159                 *prem = NULL;
2160                 return NULL;
2161         }
2162         v0 = v->ob_digit;
2163         w0 = w->ob_digit;
2164         wm1 = w0[size_w-1];
2165         wm2 = w0[size_w-2];
2166         for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
2167                 /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
2168                    single-digit quotient q, remainder in vk[0:size_w]. */
2169
2170                 SIGCHECK({
2171                         Py_DECREF(a);
2172                         Py_DECREF(w);
2173                         Py_DECREF(v);
2174                         *prem = NULL;
2175                         return NULL;
2176                 })
2177
2178                 /* estimate quotient digit q; may overestimate by 1 (rare) */
2179                 vtop = vk[size_w];
2180                 assert(vtop <= wm1);
2181                 vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1];
2182                 q = (digit)(vv / wm1);
2183                 r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
2184                 while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
2185                                              | vk[size_w-2])) {
2186                         --q;
2187                         r += wm1;
2188                         if (r >= PyLong_BASE)
2189                                 break;
2190                 }
2191                 assert(q <= PyLong_BASE);
2192
2193                 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */
2194                 zhi = 0;
2195                 for (i = 0; i < size_w; ++i) {
2196                         /* invariants: -PyLong_BASE <= -q <= zhi <= 0;
2197                            -PyLong_BASE * q <= z < PyLong_BASE */
2198                         z = (sdigit)vk[i] + zhi -
2199                                 (stwodigits)q * (stwodigits)w0[i];
2200                         vk[i] = (digit)z & PyLong_MASK;
2201                         zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
2202                                                         z, PyLong_SHIFT);
2203                 }
2204
2205                 /* add w back if q was too large (this branch taken rarely) */
2206                 assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0);
2207                 if ((sdigit)vtop + zhi < 0) {
2208                         carry = 0;
2209                         for (i = 0; i < size_w; ++i) {
2210                                 carry += vk[i] + w0[i];
2211                                 vk[i] = carry & PyLong_MASK;
2212                                 carry >>= PyLong_SHIFT;
2213                         }
2214                         --q;
2215                 }
2216
2217                 /* store quotient digit */
2218                 assert(q < PyLong_BASE);
2219                 *--ak = q;
2220         }
2221
2222         /* unshift remainder; we reuse w to store the result */
2223         carry = v_rshift(w0, v0, size_w, d);
2224         assert(carry==0);
2225         Py_DECREF(v);
2226
2227         *prem = long_normalize(w);
2228         return long_normalize(a);
2229 }
2230
2231 /* Methods */
2232
2233 static void
2234 long_dealloc(PyObject *v)
2235 {
2236         Py_TYPE(v)->tp_free(v);
2237 }
2238
2239 static PyObject *
2240 long_repr(PyObject *v)
2241 {
2242         return _PyLong_Format(v, 10, 1, 0);
2243 }
2244
2245 static PyObject *
2246 long_str(PyObject *v)
2247 {
2248         return _PyLong_Format(v, 10, 0, 0);
2249 }
2250
2251 static int
2252 long_compare(PyLongObject *a, PyLongObject *b)
2253 {
2254         Py_ssize_t sign;
2255
2256         if (Py_SIZE(a) != Py_SIZE(b)) {
2257                 if (ABS(Py_SIZE(a)) == 0 && ABS(Py_SIZE(b)) == 0)
2258                         sign = 0;
2259                 else
2260                         sign = Py_SIZE(a) - Py_SIZE(b);
2261         }
2262         else {
2263                 Py_ssize_t i = ABS(Py_SIZE(a));
2264                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2265                         ;
2266                 if (i < 0)
2267                         sign = 0;
2268                 else {
2269                         sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
2270                         if (Py_SIZE(a) < 0)
2271                                 sign = -sign;
2272                 }
2273         }
2274         return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2275 }
2276
2277 static long
2278 long_hash(PyLongObject *v)
2279 {
2280         unsigned long x;
2281         Py_ssize_t i;
2282         int sign;
2283
2284         /* This is designed so that Python ints and longs with the
2285            same value hash to the same value, otherwise comparisons
2286            of mapping keys will turn out weird */
2287         i = v->ob_size;
2288         sign = 1;
2289         x = 0;
2290         if (i < 0) {
2291                 sign = -1;
2292                 i = -(i);
2293         }
2294         /* The following loop produces a C unsigned long x such that x is
2295            congruent to the absolute value of v modulo ULONG_MAX.  The
2296            resulting x is nonzero if and only if v is. */
2297         while (--i >= 0) {
2298                 /* Force a native long #-bits (32 or 64) circular shift */
2299                 x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT);
2300                 x += v->ob_digit[i];
2301                 /* If the addition above overflowed we compensate by
2302                    incrementing.  This preserves the value modulo
2303                    ULONG_MAX. */
2304                 if (x < v->ob_digit[i])
2305                         x++;
2306         }
2307         x = x * sign;
2308         if (x == (unsigned long)-1)
2309                 x = (unsigned long)-2;
2310         return (long)x;
2311 }
2312
2313
2314 /* Add the absolute values of two long integers. */
2315
2316 static PyLongObject *
2317 x_add(PyLongObject *a, PyLongObject *b)
2318 {
2319         Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2320         PyLongObject *z;
2321         Py_ssize_t i;
2322         digit carry = 0;
2323
2324         /* Ensure a is the larger of the two: */
2325         if (size_a < size_b) {
2326                 { PyLongObject *temp = a; a = b; b = temp; }
2327                 { Py_ssize_t size_temp = size_a;
2328                   size_a = size_b;
2329                   size_b = size_temp; }
2330         }
2331         z = _PyLong_New(size_a+1);
2332         if (z == NULL)
2333                 return NULL;
2334         for (i = 0; i < size_b; ++i) {
2335                 carry += a->ob_digit[i] + b->ob_digit[i];
2336                 z->ob_digit[i] = carry & PyLong_MASK;
2337                 carry >>= PyLong_SHIFT;
2338         }
2339         for (; i < size_a; ++i) {
2340                 carry += a->ob_digit[i];
2341                 z->ob_digit[i] = carry & PyLong_MASK;
2342                 carry >>= PyLong_SHIFT;
2343         }
2344         z->ob_digit[i] = carry;
2345         return long_normalize(z);
2346 }
2347
2348 /* Subtract the absolute values of two integers. */
2349
2350 static PyLongObject *
2351 x_sub(PyLongObject *a, PyLongObject *b)
2352 {
2353         Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b));
2354         PyLongObject *z;
2355         Py_ssize_t i;
2356         int sign = 1;
2357         digit borrow = 0;
2358
2359         /* Ensure a is the larger of the two: */
2360         if (size_a < size_b) {
2361                 sign = -1;
2362                 { PyLongObject *temp = a; a = b; b = temp; }
2363                 { Py_ssize_t size_temp = size_a;
2364                   size_a = size_b;
2365                   size_b = size_temp; }
2366         }
2367         else if (size_a == size_b) {
2368                 /* Find highest digit where a and b differ: */
2369                 i = size_a;
2370                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2371                         ;
2372                 if (i < 0)
2373                         return _PyLong_New(0);
2374                 if (a->ob_digit[i] < b->ob_digit[i]) {
2375                         sign = -1;
2376                         { PyLongObject *temp = a; a = b; b = temp; }
2377                 }
2378                 size_a = size_b = i+1;
2379         }
2380         z = _PyLong_New(size_a);
2381         if (z == NULL)
2382                 return NULL;
2383         for (i = 0; i < size_b; ++i) {
2384                 /* The following assumes unsigned arithmetic
2385                    works module 2**N for some N>PyLong_SHIFT. */
2386                 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
2387                 z->ob_digit[i] = borrow & PyLong_MASK;
2388                 borrow >>= PyLong_SHIFT;
2389                 borrow &= 1; /* Keep only one sign bit */
2390         }
2391         for (; i < size_a; ++i) {
2392                 borrow = a->ob_digit[i] - borrow;
2393                 z->ob_digit[i] = borrow & PyLong_MASK;
2394                 borrow >>= PyLong_SHIFT;
2395                 borrow &= 1; /* Keep only one sign bit */
2396         }
2397         assert(borrow == 0);
2398         if (sign < 0)
2399                 z->ob_size = -(z->ob_size);
2400         return long_normalize(z);
2401 }
2402
2403 static PyObject *
2404 long_add(PyLongObject *v, PyLongObject *w)
2405 {
2406         PyLongObject *a, *b, *z;
2407
2408         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2409
2410         if (a->ob_size < 0) {
2411                 if (b->ob_size < 0) {
2412                         z = x_add(a, b);
2413                         if (z != NULL && z->ob_size != 0)
2414                                 z->ob_size = -(z->ob_size);
2415                 }
2416                 else
2417                         z = x_sub(b, a);
2418         }
2419         else {
2420                 if (b->ob_size < 0)
2421                         z = x_sub(a, b);
2422                 else
2423                         z = x_add(a, b);
2424         }
2425         Py_DECREF(a);
2426         Py_DECREF(b);
2427         return (PyObject *)z;
2428 }
2429
2430 static PyObject *
2431 long_sub(PyLongObject *v, PyLongObject *w)
2432 {
2433         PyLongObject *a, *b, *z;
2434
2435         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
2436
2437         if (a->ob_size < 0) {
2438                 if (b->ob_size < 0)
2439                         z = x_sub(a, b);
2440                 else
2441                         z = x_add(a, b);
2442                 if (z != NULL && z->ob_size != 0)
2443                         z->ob_size = -(z->ob_size);
2444         }
2445         else {
2446                 if (b->ob_size < 0)
2447                         z = x_add(a, b);
2448                 else
2449                         z = x_sub(a, b);
2450         }
2451         Py_DECREF(a);
2452         Py_DECREF(b);
2453         return (PyObject *)z;
2454 }
2455
2456 /* Grade school multiplication, ignoring the signs.
2457  * Returns the absolute value of the product, or NULL if error.
2458  */
2459 static PyLongObject *
2460 x_mul(PyLongObject *a, PyLongObject *b)
2461 {
2462         PyLongObject *z;
2463         Py_ssize_t size_a = ABS(Py_SIZE(a));
2464         Py_ssize_t size_b = ABS(Py_SIZE(b));
2465         Py_ssize_t i;
2466
2467         z = _PyLong_New(size_a + size_b);
2468         if (z == NULL)
2469                 return NULL;
2470
2471         memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
2472         if (a == b) {
2473                 /* Efficient squaring per HAC, Algorithm 14.16:
2474                  * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
2475                  * Gives slightly less than a 2x speedup when a == b,
2476                  * via exploiting that each entry in the multiplication
2477                  * pyramid appears twice (except for the size_a squares).
2478                  */
2479                 for (i = 0; i < size_a; ++i) {
2480                         twodigits carry;
2481                         twodigits f = a->ob_digit[i];
2482                         digit *pz = z->ob_digit + (i << 1);
2483                         digit *pa = a->ob_digit + i + 1;
2484                         digit *paend = a->ob_digit + size_a;
2485
2486                         SIGCHECK({
2487                                 Py_DECREF(z);
2488                                 return NULL;
2489                         })
2490
2491                         carry = *pz + f * f;
2492                         *pz++ = (digit)(carry & PyLong_MASK);
2493                         carry >>= PyLong_SHIFT;
2494                         assert(carry <= PyLong_MASK);
2495
2496                         /* Now f is added in twice in each column of the
2497                          * pyramid it appears.  Same as adding f<<1 once.
2498                          */
2499                         f <<= 1;
2500                         while (pa < paend) {
2501                                 carry += *pz + *pa++ * f;
2502                                 *pz++ = (digit)(carry & PyLong_MASK);
2503                                 carry >>= PyLong_SHIFT;
2504                                 assert(carry <= (PyLong_MASK << 1));
2505                         }
2506                         if (carry) {
2507                                 carry += *pz;
2508                                 *pz++ = (digit)(carry & PyLong_MASK);
2509                                 carry >>= PyLong_SHIFT;
2510                         }
2511                         if (carry)
2512                                 *pz += (digit)(carry & PyLong_MASK);
2513                         assert((carry >> PyLong_SHIFT) == 0);
2514                 }
2515         }
2516         else {  /* a is not the same as b -- gradeschool long mult */
2517                 for (i = 0; i < size_a; ++i) {
2518                         twodigits carry = 0;
2519                         twodigits f = a->ob_digit[i];
2520                         digit *pz = z->ob_digit + i;
2521                         digit *pb = b->ob_digit;
2522                         digit *pbend = b->ob_digit + size_b;
2523
2524                         SIGCHECK({
2525                                 Py_DECREF(z);
2526                                 return NULL;
2527                         })
2528
2529                         while (pb < pbend) {
2530                                 carry += *pz + *pb++ * f;
2531                                 *pz++ = (digit)(carry & PyLong_MASK);
2532                                 carry >>= PyLong_SHIFT;
2533                                 assert(carry <= PyLong_MASK);
2534                         }
2535                         if (carry)
2536                                 *pz += (digit)(carry & PyLong_MASK);
2537                         assert((carry >> PyLong_SHIFT) == 0);
2538                 }
2539         }
2540         return long_normalize(z);
2541 }
2542
2543 /* A helper for Karatsuba multiplication (k_mul).
2544    Takes a long "n" and an integer "size" representing the place to
2545    split, and sets low and high such that abs(n) == (high << size) + low,
2546    viewing the shift as being by digits.  The sign bit is ignored, and
2547    the return values are >= 0.
2548    Returns 0 on success, -1 on failure.
2549 */
2550 static int
2551 kmul_split(PyLongObject *n, Py_ssize_t size, PyLongObject **high, PyLongObject **low)
2552 {
2553         PyLongObject *hi, *lo;
2554         Py_ssize_t size_lo, size_hi;
2555         const Py_ssize_t size_n = ABS(Py_SIZE(n));
2556
2557         size_lo = MIN(size_n, size);
2558         size_hi = size_n - size_lo;
2559
2560         if ((hi = _PyLong_New(size_hi)) == NULL)
2561                 return -1;
2562         if ((lo = _PyLong_New(size_lo)) == NULL) {
2563                 Py_DECREF(hi);
2564                 return -1;
2565         }
2566
2567         memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
2568         memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
2569
2570         *high = long_normalize(hi);
2571         *low = long_normalize(lo);
2572         return 0;
2573 }
2574
2575 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b);
2576
2577 /* Karatsuba multiplication.  Ignores the input signs, and returns the
2578  * absolute value of the product (or NULL if error).
2579  * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
2580  */
2581 static PyLongObject *
2582 k_mul(PyLongObject *a, PyLongObject *b)
2583 {
2584         Py_ssize_t asize = ABS(Py_SIZE(a));
2585         Py_ssize_t bsize = ABS(Py_SIZE(b));
2586         PyLongObject *ah = NULL;
2587         PyLongObject *al = NULL;
2588         PyLongObject *bh = NULL;
2589         PyLongObject *bl = NULL;
2590         PyLongObject *ret = NULL;
2591         PyLongObject *t1, *t2, *t3;
2592         Py_ssize_t shift;       /* the number of digits we split off */
2593         Py_ssize_t i;
2594
2595         /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl
2596          * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh  + ah*bh + al*bl
2597          * Then the original product is
2598          *     ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl
2599          * By picking X to be a power of 2, "*X" is just shifting, and it's
2600          * been reduced to 3 multiplies on numbers half the size.
2601          */
2602
2603         /* We want to split based on the larger number; fiddle so that b
2604          * is largest.
2605          */
2606         if (asize > bsize) {
2607                 t1 = a;
2608                 a = b;
2609                 b = t1;
2610
2611                 i = asize;
2612                 asize = bsize;
2613                 bsize = i;
2614         }
2615
2616         /* Use gradeschool math when either number is too small. */
2617         i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
2618         if (asize <= i) {
2619                 if (asize == 0)
2620                         return _PyLong_New(0);
2621                 else
2622                         return x_mul(a, b);
2623         }
2624
2625         /* If a is small compared to b, splitting on b gives a degenerate
2626          * case with ah==0, and Karatsuba may be (even much) less efficient
2627          * than "grade school" then.  However, we can still win, by viewing
2628          * b as a string of "big digits", each of width a->ob_size.  That
2629          * leads to a sequence of balanced calls to k_mul.
2630          */
2631         if (2 * asize <= bsize)
2632                 return k_lopsided_mul(a, b);
2633
2634         /* Split a & b into hi & lo pieces. */
2635         shift = bsize >> 1;
2636         if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
2637         assert(Py_SIZE(ah) > 0);        /* the split isn't degenerate */
2638
2639         if (a == b) {
2640                 bh = ah;
2641                 bl = al;
2642                 Py_INCREF(bh);
2643                 Py_INCREF(bl);
2644         }
2645         else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
2646
2647         /* The plan:
2648          * 1. Allocate result space (asize + bsize digits:  that's always
2649          *    enough).
2650          * 2. Compute ah*bh, and copy into result at 2*shift.
2651          * 3. Compute al*bl, and copy into result at 0.  Note that this
2652          *    can't overlap with #2.
2653          * 4. Subtract al*bl from the result, starting at shift.  This may
2654          *    underflow (borrow out of the high digit), but we don't care:
2655          *    we're effectively doing unsigned arithmetic mod
2656          *    PyLong_BASE**(sizea + sizeb), and so long as the *final* result fits,
2657          *    borrows and carries out of the high digit can be ignored.
2658          * 5. Subtract ah*bh from the result, starting at shift.
2659          * 6. Compute (ah+al)*(bh+bl), and add it into the result starting
2660          *    at shift.
2661          */
2662
2663         /* 1. Allocate result space. */
2664         ret = _PyLong_New(asize + bsize);
2665         if (ret == NULL) goto fail;
2666 #ifdef Py_DEBUG
2667         /* Fill with trash, to catch reference to uninitialized digits. */
2668         memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
2669 #endif
2670
2671         /* 2. t1 <- ah*bh, and copy into high digits of result. */
2672         if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
2673         assert(Py_SIZE(t1) >= 0);
2674         assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
2675         memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
2676                Py_SIZE(t1) * sizeof(digit));
2677
2678         /* Zero-out the digits higher than the ah*bh copy. */
2679         i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
2680         if (i)
2681                 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
2682                        i * sizeof(digit));
2683
2684         /* 3. t2 <- al*bl, and copy into the low digits. */
2685         if ((t2 = k_mul(al, bl)) == NULL) {
2686                 Py_DECREF(t1);
2687                 goto fail;
2688         }
2689         assert(Py_SIZE(t2) >= 0);
2690         assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */
2691         memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
2692
2693         /* Zero out remaining digits. */
2694         i = 2*shift - Py_SIZE(t2);      /* number of uninitialized digits */
2695         if (i)
2696                 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
2697
2698         /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2).  We do al*bl first
2699          * because it's fresher in cache.
2700          */
2701         i = Py_SIZE(ret) - shift;  /* # digits after shift */
2702         (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
2703         Py_DECREF(t2);
2704
2705         (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
2706         Py_DECREF(t1);
2707
2708         /* 6. t3 <- (ah+al)(bh+bl), and add into result. */
2709         if ((t1 = x_add(ah, al)) == NULL) goto fail;
2710         Py_DECREF(ah);
2711         Py_DECREF(al);
2712         ah = al = NULL;
2713
2714         if (a == b) {
2715                 t2 = t1;
2716                 Py_INCREF(t2);
2717         }
2718         else if ((t2 = x_add(bh, bl)) == NULL) {
2719                 Py_DECREF(t1);
2720                 goto fail;
2721         }
2722         Py_DECREF(bh);
2723         Py_DECREF(bl);
2724         bh = bl = NULL;
2725
2726         t3 = k_mul(t1, t2);
2727         Py_DECREF(t1);
2728         Py_DECREF(t2);
2729         if (t3 == NULL) goto fail;
2730         assert(Py_SIZE(t3) >= 0);
2731
2732         /* Add t3.  It's not obvious why we can't run out of room here.
2733          * See the (*) comment after this function.
2734          */
2735         (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
2736         Py_DECREF(t3);
2737
2738         return long_normalize(ret);
2739
2740  fail:
2741         Py_XDECREF(ret);
2742         Py_XDECREF(ah);
2743         Py_XDECREF(al);
2744         Py_XDECREF(bh);
2745         Py_XDECREF(bl);
2746         return NULL;
2747 }
2748
2749 /* (*) Why adding t3 can't "run out of room" above.
2750
2751 Let f(x) mean the floor of x and c(x) mean the ceiling of x.  Some facts
2752 to start with:
2753
2754 1. For any integer i, i = c(i/2) + f(i/2).  In particular,
2755    bsize = c(bsize/2) + f(bsize/2).
2756 2. shift = f(bsize/2)
2757 3. asize <= bsize
2758 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this
2759    routine, so asize > bsize/2 >= f(bsize/2) in this routine.
2760
2761 We allocated asize + bsize result digits, and add t3 into them at an offset
2762 of shift.  This leaves asize+bsize-shift allocated digit positions for t3
2763 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
2764 asize + c(bsize/2) available digit positions.
2765
2766 bh has c(bsize/2) digits, and bl at most f(size/2) digits.  So bh+hl has
2767 at most c(bsize/2) digits + 1 bit.
2768
2769 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
2770 digits, and al has at most f(bsize/2) digits in any case.  So ah+al has at
2771 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
2772
2773 The product (ah+al)*(bh+bl) therefore has at most
2774
2775     c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
2776
2777 and we have asize + c(bsize/2) available digit positions.  We need to show
2778 this is always enough.  An instance of c(bsize/2) cancels out in both, so
2779 the question reduces to whether asize digits is enough to hold
2780 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits.  If asize < bsize,
2781 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits.  By #4,
2782 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
2783 digit is enough to hold 2 bits.  This is so since PyLong_SHIFT=15 >= 2.  If
2784 asize == bsize, then we're asking whether bsize digits is enough to hold
2785 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
2786 is enough to hold 2 bits.  This is so if bsize >= 2, which holds because
2787 bsize >= KARATSUBA_CUTOFF >= 2.
2788
2789 Note that since there's always enough room for (ah+al)*(bh+bl), and that's
2790 clearly >= each of ah*bh and al*bl, there's always enough room to subtract
2791 ah*bh and al*bl too.
2792 */
2793
2794 /* b has at least twice the digits of a, and a is big enough that Karatsuba
2795  * would pay off *if* the inputs had balanced sizes.  View b as a sequence
2796  * of slices, each with a->ob_size digits, and multiply the slices by a,
2797  * one at a time.  This gives k_mul balanced inputs to work with, and is
2798  * also cache-friendly (we compute one double-width slice of the result
2799  * at a time, then move on, never bactracking except for the helpful
2800  * single-width slice overlap between successive partial sums).
2801  */
2802 static PyLongObject *
2803 k_lopsided_mul(PyLongObject *a, PyLongObject *b)
2804 {
2805         const Py_ssize_t asize = ABS(Py_SIZE(a));
2806         Py_ssize_t bsize = ABS(Py_SIZE(b));
2807         Py_ssize_t nbdone;      /* # of b digits already multiplied */
2808         PyLongObject *ret;
2809         PyLongObject *bslice = NULL;
2810
2811         assert(asize > KARATSUBA_CUTOFF);
2812         assert(2 * asize <= bsize);
2813
2814         /* Allocate result space, and zero it out. */
2815         ret = _PyLong_New(asize + bsize);
2816         if (ret == NULL)
2817                 return NULL;
2818         memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
2819
2820         /* Successive slices of b are copied into bslice. */
2821         bslice = _PyLong_New(asize);
2822         if (bslice == NULL)
2823                 goto fail;
2824
2825         nbdone = 0;
2826         while (bsize > 0) {
2827                 PyLongObject *product;
2828                 const Py_ssize_t nbtouse = MIN(bsize, asize);
2829
2830                 /* Multiply the next slice of b by a. */
2831                 memcpy(bslice->ob_digit, b->ob_digit + nbdone,
2832                        nbtouse * sizeof(digit));
2833                 Py_SIZE(bslice) = nbtouse;
2834                 product = k_mul(a, bslice);
2835                 if (product == NULL)
2836                         goto fail;
2837
2838                 /* Add into result. */
2839                 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
2840                              product->ob_digit, Py_SIZE(product));
2841                 Py_DECREF(product);
2842
2843                 bsize -= nbtouse;
2844                 nbdone += nbtouse;
2845         }
2846
2847         Py_DECREF(bslice);
2848         return long_normalize(ret);
2849
2850  fail:
2851         Py_DECREF(ret);
2852         Py_XDECREF(bslice);
2853         return NULL;
2854 }
2855
2856 static PyObject *
2857 long_mul(PyLongObject *v, PyLongObject *w)
2858 {
2859         PyLongObject *a, *b, *z;
2860
2861         if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
2862                 Py_INCREF(Py_NotImplemented);
2863                 return Py_NotImplemented;
2864         }
2865
2866         z = k_mul(a, b);
2867         /* Negate if exactly one of the inputs is negative. */
2868         if (((a->ob_size ^ b->ob_size) < 0) && z)
2869                 z->ob_size = -(z->ob_size);
2870         Py_DECREF(a);
2871         Py_DECREF(b);
2872         return (PyObject *)z;
2873 }
2874
2875 /* The / and % operators are now defined in terms of divmod().
2876    The expression a mod b has the value a - b*floor(a/b).
2877    The long_divrem function gives the remainder after division of
2878    |a| by |b|, with the sign of a.  This is also expressed
2879    as a - b*trunc(a/b), if trunc truncates towards zero.
2880    Some examples:
2881          a       b      a rem b         a mod b
2882          13      10      3               3
2883         -13      10     -3               7
2884          13     -10      3              -7
2885         -13     -10     -3              -3
2886    So, to get from rem to mod, we have to add b if a and b
2887    have different signs.  We then subtract one from the 'div'
2888    part of the outcome to keep the invariant intact. */
2889
2890 /* Compute
2891  *     *pdiv, *pmod = divmod(v, w)
2892  * NULL can be passed for pdiv or pmod, in which case that part of
2893  * the result is simply thrown away.  The caller owns a reference to
2894  * each of these it requests (does not pass NULL for).
2895  */
2896 static int
2897 l_divmod(PyLongObject *v, PyLongObject *w,
2898          PyLongObject **pdiv, PyLongObject **pmod)
2899 {
2900         PyLongObject *div, *mod;
2901
2902         if (long_divrem(v, w, &div, &mod) < 0)
2903                 return -1;
2904         if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) ||
2905             (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
2906                 PyLongObject *temp;
2907                 PyLongObject *one;
2908                 temp = (PyLongObject *) long_add(mod, w);
2909                 Py_DECREF(mod);
2910                 mod = temp;
2911                 if (mod == NULL) {
2912                         Py_DECREF(div);
2913                         return -1;
2914                 }
2915                 one = (PyLongObject *) PyLong_FromLong(1L);
2916                 if (one == NULL ||
2917                     (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
2918                         Py_DECREF(mod);
2919                         Py_DECREF(div);
2920                         Py_XDECREF(one);
2921                         return -1;
2922                 }
2923                 Py_DECREF(one);
2924                 Py_DECREF(div);
2925                 div = temp;
2926         }
2927         if (pdiv != NULL)
2928                 *pdiv = div;
2929         else
2930                 Py_DECREF(div);
2931
2932         if (pmod != NULL)
2933                 *pmod = mod;
2934         else
2935                 Py_DECREF(mod);
2936
2937         return 0;
2938 }
2939
2940 static PyObject *
2941 long_div(PyObject *v, PyObject *w)
2942 {
2943         PyLongObject *a, *b, *div;
2944
2945         CONVERT_BINOP(v, w, &a, &b);
2946         if (l_divmod(a, b, &div, NULL) < 0)
2947                 div = NULL;
2948         Py_DECREF(a);
2949         Py_DECREF(b);
2950         return (PyObject *)div;
2951 }
2952
2953 static PyObject *
2954 long_classic_div(PyObject *v, PyObject *w)
2955 {
2956         PyLongObject *a, *b, *div;
2957
2958         CONVERT_BINOP(v, w, &a, &b);
2959         if (Py_DivisionWarningFlag &&
2960             PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
2961                 div = NULL;
2962         else if (l_divmod(a, b, &div, NULL) < 0)
2963                 div = NULL;
2964         Py_DECREF(a);
2965         Py_DECREF(b);
2966         return (PyObject *)div;
2967 }
2968
2969 static PyObject *
2970 long_true_divide(PyObject *v, PyObject *w)
2971 {
2972         PyLongObject *a, *b;
2973         double ad, bd;
2974         int failed, aexp = -1, bexp = -1;
2975
2976         CONVERT_BINOP(v, w, &a, &b);
2977         ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
2978         bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
2979         failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
2980         Py_DECREF(a);
2981         Py_DECREF(b);
2982         if (failed)
2983                 return NULL;
2984         /* 'aexp' and 'bexp' were initialized to -1 to silence gcc-4.0.x,
2985            but should really be set correctly after sucessful calls to
2986            _PyLong_AsScaledDouble() */
2987         assert(aexp >= 0 && bexp >= 0);
2988
2989         if (bd == 0.0) {
2990                 PyErr_SetString(PyExc_ZeroDivisionError,
2991                         "long division or modulo by zero");
2992                 return NULL;
2993         }
2994
2995         /* True value is very close to ad/bd * 2**(PyLong_SHIFT*(aexp-bexp)) */
2996         ad /= bd;       /* overflow/underflow impossible here */
2997         aexp -= bexp;
2998         if (aexp > INT_MAX / PyLong_SHIFT)
2999                 goto overflow;
3000         else if (aexp < -(INT_MAX / PyLong_SHIFT))
3001                 return PyFloat_FromDouble(0.0); /* underflow to 0 */
3002         errno = 0;
3003         ad = ldexp(ad, aexp * PyLong_SHIFT);
3004         if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
3005                 goto overflow;
3006         return PyFloat_FromDouble(ad);
3007
3008 overflow:
3009         PyErr_SetString(PyExc_OverflowError,
3010                 "long/long too large for a float");
3011         return NULL;
3012
3013 }
3014
3015 static PyObject *
3016 long_mod(PyObject *v, PyObject *w)
3017 {
3018         PyLongObject *a, *b, *mod;
3019
3020         CONVERT_BINOP(v, w, &a, &b);
3021
3022         if (l_divmod(a, b, NULL, &mod) < 0)
3023                 mod = NULL;
3024         Py_DECREF(a);
3025         Py_DECREF(b);
3026         return (PyObject *)mod;
3027 }
3028
3029 static PyObject *
3030 long_divmod(PyObject *v, PyObject *w)
3031 {
3032         PyLongObject *a, *b, *div, *mod;
3033         PyObject *z;
3034
3035         CONVERT_BINOP(v, w, &a, &b);
3036
3037         if (l_divmod(a, b, &div, &mod) < 0) {
3038                 Py_DECREF(a);
3039                 Py_DECREF(b);
3040                 return NULL;
3041         }
3042         z = PyTuple_New(2);
3043         if (z != NULL) {
3044                 PyTuple_SetItem(z, 0, (PyObject *) div);
3045                 PyTuple_SetItem(z, 1, (PyObject *) mod);
3046         }
3047         else {
3048                 Py_DECREF(div);
3049                 Py_DECREF(mod);
3050         }
3051         Py_DECREF(a);
3052         Py_DECREF(b);
3053         return z;
3054 }
3055
3056 /* pow(v, w, x) */
3057 static PyObject *
3058 long_pow(PyObject *v, PyObject *w, PyObject *x)
3059 {
3060         PyLongObject *a, *b, *c; /* a,b,c = v,w,x */
3061         int negativeOutput = 0;  /* if x<0 return negative output */
3062
3063         PyLongObject *z = NULL;  /* accumulated result */
3064         Py_ssize_t i, j, k;             /* counters */
3065         PyLongObject *temp = NULL;
3066
3067         /* 5-ary values.  If the exponent is large enough, table is
3068          * precomputed so that table[i] == a**i % c for i in range(32).
3069          */
3070         PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3071                                    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
3072
3073         /* a, b, c = v, w, x */
3074         CONVERT_BINOP(v, w, &a, &b);
3075         if (PyLong_Check(x)) {
3076                 c = (PyLongObject *)x;
3077                 Py_INCREF(x);
3078         }
3079         else if (PyInt_Check(x)) {
3080                 c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x));
3081                 if (c == NULL)
3082                         goto Error;
3083         }
3084         else if (x == Py_None)
3085                 c = NULL;
3086         else {
3087                 Py_DECREF(a);
3088                 Py_DECREF(b);
3089                 Py_INCREF(Py_NotImplemented);
3090                 return Py_NotImplemented;
3091         }
3092
3093         if (Py_SIZE(b) < 0) {  /* if exponent is negative */
3094                 if (c) {
3095                         PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
3096                             "cannot be negative when 3rd argument specified");
3097                         goto Error;
3098                 }
3099                 else {
3100                         /* else return a float.  This works because we know
3101                            that this calls float_pow() which converts its
3102                            arguments to double. */
3103                         Py_DECREF(a);
3104                         Py_DECREF(b);
3105                         return PyFloat_Type.tp_as_number->nb_power(v, w, x);
3106                 }
3107         }
3108
3109         if (c) {
3110                 /* if modulus == 0:
3111                        raise ValueError() */
3112                 if (Py_SIZE(c) == 0) {
3113                         PyErr_SetString(PyExc_ValueError,
3114                                         "pow() 3rd argument cannot be 0");
3115                         goto Error;
3116                 }
3117
3118                 /* if modulus < 0:
3119                        negativeOutput = True
3120                        modulus = -modulus */
3121                 if (Py_SIZE(c) < 0) {
3122                         negativeOutput = 1;
3123                         temp = (PyLongObject *)_PyLong_Copy(c);
3124                         if (temp == NULL)
3125                                 goto Error;
3126                         Py_DECREF(c);
3127                         c = temp;
3128                         temp = NULL;
3129                         c->ob_size = - c->ob_size;
3130                 }
3131
3132                 /* if modulus == 1:
3133                        return 0 */
3134                 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
3135                         z = (PyLongObject *)PyLong_FromLong(0L);
3136                         goto Done;
3137                 }
3138
3139                 /* if base < 0:
3140                        base = base % modulus
3141                    Having the base positive just makes things easier. */
3142                 if (Py_SIZE(a) < 0) {
3143                         if (l_divmod(a, c, NULL, &temp) < 0)
3144                                 goto Error;
3145                         Py_DECREF(a);
3146                         a = temp;
3147                         temp = NULL;
3148                 }
3149         }
3150
3151         /* At this point a, b, and c are guaranteed non-negative UNLESS
3152            c is NULL, in which case a may be negative. */
3153
3154         z = (PyLongObject *)PyLong_FromLong(1L);
3155         if (z == NULL)
3156                 goto Error;
3157
3158         /* Perform a modular reduction, X = X % c, but leave X alone if c
3159          * is NULL.
3160          */
3161 #define REDUCE(X)                                       \
3162         if (c != NULL) {                                \
3163                 if (l_divmod(X, c, NULL, &temp) < 0)    \
3164                         goto Error;                     \
3165                 Py_XDECREF(X);                          \
3166                 X = temp;                               \
3167                 temp = NULL;                            \
3168         }
3169
3170         /* Multiply two values, then reduce the result:
3171            result = X*Y % c.  If c is NULL, skip the mod. */
3172 #define MULT(X, Y, result)                              \
3173 {                                                       \
3174         temp = (PyLongObject *)long_mul(X, Y);          \
3175         if (temp == NULL)                               \
3176                 goto Error;                             \
3177         Py_XDECREF(result);                             \
3178         result = temp;                                  \
3179         temp = NULL;                                    \
3180         REDUCE(result)                                  \
3181 }
3182
3183         if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
3184                 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
3185                 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf    */
3186                 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3187                         digit bi = b->ob_digit[i];
3188
3189                         for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
3190                                 MULT(z, z, z)
3191                                 if (bi & j)
3192                                         MULT(z, a, z)
3193                         }
3194                 }
3195         }
3196         else {
3197                 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
3198                 Py_INCREF(z);   /* still holds 1L */
3199                 table[0] = z;
3200                 for (i = 1; i < 32; ++i)
3201                         MULT(table[i-1], a, table[i])
3202
3203                 for (i = Py_SIZE(b) - 1; i >= 0; --i) {
3204                         const digit bi = b->ob_digit[i];
3205
3206                         for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
3207                                 const int index = (bi >> j) & 0x1f;
3208                                 for (k = 0; k < 5; ++k)
3209                                         MULT(z, z, z)
3210                                 if (index)
3211                                         MULT(z, table[index], z)
3212                         }
3213                 }
3214         }
3215
3216         if (negativeOutput && (Py_SIZE(z) != 0)) {
3217                 temp = (PyLongObject *)long_sub(z, c);
3218                 if (temp == NULL)
3219                         goto Error;
3220                 Py_DECREF(z);
3221                 z = temp;
3222                 temp = NULL;
3223         }
3224         goto Done;
3225
3226  Error:
3227         if (z != NULL) {
3228                 Py_DECREF(z);
3229                 z = NULL;
3230         }
3231         /* fall through */
3232  Done:
3233         if (Py_SIZE(b) > FIVEARY_CUTOFF) {
3234                 for (i = 0; i < 32; ++i)
3235                         Py_XDECREF(table[i]);
3236         }
3237         Py_DECREF(a);
3238         Py_DECREF(b);
3239         Py_XDECREF(c);
3240         Py_XDECREF(temp);
3241         return (PyObject *)z;
3242 }
3243
3244 static PyObject *
3245 long_invert(PyLongObject *v)
3246 {
3247         /* Implement ~x as -(x+1) */
3248         PyLongObject *x;
3249         PyLongObject *w;
3250         w = (PyLongObject *)PyLong_FromLong(1L);
3251         if (w == NULL)
3252                 return NULL;
3253         x = (PyLongObject *) long_add(v, w);
3254         Py_DECREF(w);
3255         if (x == NULL)
3256                 return NULL;
3257         Py_SIZE(x) = -(Py_SIZE(x));
3258         return (PyObject *)x;
3259 }
3260
3261 static PyObject *
3262 long_neg(PyLongObject *v)
3263 {
3264         PyLongObject *z;
3265         if (v->ob_size == 0 && PyLong_CheckExact(v)) {
3266                 /* -0 == 0 */
3267                 Py_INCREF(v);
3268                 return (PyObject *) v;
3269         }
3270         z = (PyLongObject *)_PyLong_Copy(v);
3271         if (z != NULL)
3272                 z->ob_size = -(v->ob_size);
3273         return (PyObject *)z;
3274 }
3275
3276 static PyObject *
3277 long_abs(PyLongObject *v)
3278 {
3279         if (v->ob_size < 0)
3280                 return long_neg(v);
3281         else
3282                 return long_long((PyObject *)v);
3283 }
3284
3285 static int
3286 long_nonzero(PyLongObject *v)
3287 {
3288         return ABS(Py_SIZE(v)) != 0;
3289 }
3290
3291 static PyObject *
3292 long_rshift(PyLongObject *v, PyLongObject *w)
3293 {
3294         PyLongObject *a, *b;
3295         PyLongObject *z = NULL;
3296         long shiftby;
3297         Py_ssize_t newsize, wordshift, loshift, hishift, i, j;
3298         digit lomask, himask;
3299
3300         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
3301
3302         if (Py_SIZE(a) < 0) {
3303                 /* Right shifting negative numbers is harder */
3304                 PyLongObject *a1, *a2;
3305                 a1 = (PyLongObject *) long_invert(a);
3306                 if (a1 == NULL)
3307                         goto rshift_error;
3308                 a2 = (PyLongObject *) long_rshift(a1, b);
3309                 Py_DECREF(a1);
3310                 if (a2 == NULL)
3311                         goto rshift_error;
3312                 z = (PyLongObject *) long_invert(a2);
3313                 Py_DECREF(a2);
3314         }
3315         else {
3316
3317                 shiftby = PyLong_AsLong((PyObject *)b);
3318                 if (shiftby == -1L && PyErr_Occurred())
3319                         goto rshift_error;
3320                 if (shiftby < 0) {
3321                         PyErr_SetString(PyExc_ValueError,
3322                                         "negative shift count");
3323                         goto rshift_error;
3324                 }
3325                 wordshift = shiftby / PyLong_SHIFT;
3326                 newsize = ABS(Py_SIZE(a)) - wordshift;
3327                 if (newsize <= 0) {
3328                         z = _PyLong_New(0);
3329                         Py_DECREF(a);
3330                         Py_DECREF(b);
3331                         return (PyObject *)z;
3332                 }
3333                 loshift = shiftby % PyLong_SHIFT;
3334                 hishift = PyLong_SHIFT - loshift;
3335                 lomask = ((digit)1 << hishift) - 1;
3336                 himask = PyLong_MASK ^ lomask;
3337                 z = _PyLong_New(newsize);
3338                 if (z == NULL)
3339                         goto rshift_error;
3340                 if (Py_SIZE(a) < 0)
3341                         Py_SIZE(z) = -(Py_SIZE(z));
3342                 for (i = 0, j = wordshift; i < newsize; i++, j++) {
3343                         z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
3344                         if (i+1 < newsize)
3345                                 z->ob_digit[i] |=
3346                                   (a->ob_digit[j+1] << hishift) & himask;
3347                 }
3348                 z = long_normalize(z);
3349         }
3350 rshift_error:
3351         Py_DECREF(a);
3352         Py_DECREF(b);
3353         return (PyObject *) z;
3354
3355 }
3356
3357 static PyObject *
3358 long_lshift(PyObject *v, PyObject *w)
3359 {
3360         /* This version due to Tim Peters */
3361         PyLongObject *a, *b;
3362         PyLongObject *z = NULL;
3363         long shiftby;
3364         Py_ssize_t oldsize, newsize, wordshift, remshift, i, j;
3365         twodigits accum;
3366
3367         CONVERT_BINOP(v, w, &a, &b);
3368
3369         shiftby = PyLong_AsLong((PyObject *)b);
3370         if (shiftby == -1L && PyErr_Occurred())
3371                 goto lshift_error;
3372         if (shiftby < 0) {
3373                 PyErr_SetString(PyExc_ValueError, "negative shift count");
3374                 goto lshift_error;
3375         }
3376         if ((long)(int)shiftby != shiftby) {
3377                 PyErr_SetString(PyExc_ValueError,
3378                                 "outrageous left shift count");
3379                 goto lshift_error;
3380         }
3381         /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
3382         wordshift = (int)shiftby / PyLong_SHIFT;
3383         remshift  = (int)shiftby - wordshift * PyLong_SHIFT;
3384
3385         oldsize = ABS(a->ob_size);
3386         newsize = oldsize + wordshift;
3387         if (remshift)
3388                 ++newsize;
3389         z = _PyLong_New(newsize);
3390         if (z == NULL)
3391                 goto lshift_error;
3392         if (a->ob_size < 0)
3393                 z->ob_size = -(z->ob_size);
3394         for (i = 0; i < wordshift; i++)
3395                 z->ob_digit[i] = 0;
3396         accum = 0;
3397         for (i = wordshift, j = 0; j < oldsize; i++, j++) {
3398                 accum |= (twodigits)a->ob_digit[j] << remshift;
3399                 z->ob_digit[i] = (digit)(accum & PyLong_MASK);
3400                 accum >>= PyLong_SHIFT;
3401         }
3402         if (remshift)
3403                 z->ob_digit[newsize-1] = (digit)accum;
3404         else
3405                 assert(!accum);
3406         z = long_normalize(z);
3407 lshift_error:
3408         Py_DECREF(a);
3409         Py_DECREF(b);
3410         return (PyObject *) z;
3411 }
3412
3413
3414 /* Bitwise and/xor/or operations */
3415
3416 static PyObject *
3417 long_bitwise(PyLongObject *a,
3418              int op,  /* '&', '|', '^' */
3419              PyLongObject *b)
3420 {
3421         digit maska, maskb; /* 0 or PyLong_MASK */
3422         int negz;
3423         Py_ssize_t size_a, size_b, size_z, i;
3424         PyLongObject *z;
3425         digit diga, digb;
3426         PyObject *v;
3427
3428         if (Py_SIZE(a) < 0) {
3429                 a = (PyLongObject *) long_invert(a);
3430                 if (a == NULL)
3431                         return NULL;
3432                 maska = PyLong_MASK;
3433         }
3434         else {
3435                 Py_INCREF(a);
3436                 maska = 0;
3437         }
3438         if (Py_SIZE(b) < 0) {
3439                 b = (PyLongObject *) long_invert(b);
3440                 if (b == NULL) {
3441                         Py_DECREF(a);
3442                         return NULL;
3443                 }
3444                 maskb = PyLong_MASK;
3445         }
3446         else {
3447                 Py_INCREF(b);
3448                 maskb = 0;
3449         }
3450
3451         negz = 0;
3452         switch (op) {
3453         case '^':
3454                 if (maska != maskb) {
3455                         maska ^= PyLong_MASK;
3456                         negz = -1;
3457                 }
3458                 break;
3459         case '&':
3460                 if (maska && maskb) {
3461                         op = '|';
3462                         maska ^= PyLong_MASK;
3463                         maskb ^= PyLong_MASK;
3464                         negz = -1;
3465                 }
3466                 break;
3467         case '|':
3468                 if (maska || maskb) {
3469                         op = '&';
3470                         maska ^= PyLong_MASK;
3471                         maskb ^= PyLong_MASK;
3472                         negz = -1;
3473                 }
3474                 break;
3475         }
3476
3477         /* JRH: The original logic here was to allocate the result value (z)
3478            as the longer of the two operands.  However, there are some cases
3479            where the result is guaranteed to be shorter than that: AND of two
3480            positives, OR of two negatives: use the shorter number.  AND with
3481            mixed signs: use the positive number.  OR with mixed signs: use the
3482            negative number.  After the transformations above, op will be '&'
3483            iff one of these cases applies, and mask will be non-0 for operands
3484            whose length should be ignored.
3485         */
3486
3487         size_a = Py_SIZE(a);
3488         size_b = Py_SIZE(b);
3489         size_z = op == '&'
3490                 ? (maska
3491                    ? size_b
3492                    : (maskb ? size_a : MIN(size_a, size_b)))
3493                 : MAX(size_a, size_b);
3494         z = _PyLong_New(size_z);
3495         if (z == NULL) {
3496                 Py_DECREF(a);
3497                 Py_DECREF(b);
3498                 return NULL;
3499         }
3500
3501         for (i = 0; i < size_z; ++i) {
3502                 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
3503                 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
3504                 switch (op) {
3505                 case '&': z->ob_digit[i] = diga & digb; break;
3506                 case '|': z->ob_digit[i] = diga | digb; break;
3507                 case '^': z->ob_digit[i] = diga ^ digb; break;
3508                 }
3509         }
3510
3511         Py_DECREF(a);
3512         Py_DECREF(b);
3513         z = long_normalize(z);
3514         if (negz == 0)
3515                 return (PyObject *) z;
3516         v = long_invert(z);
3517         Py_DECREF(z);
3518         return v;
3519 }
3520
3521 static PyObject *
3522 long_and(PyObject *v, PyObject *w)
3523 {
3524         PyLongObject *a, *b;
3525         PyObject *c;
3526         CONVERT_BINOP(v, w, &a, &b);
3527         c = long_bitwise(a, '&', b);
3528         Py_DECREF(a);
3529         Py_DECREF(b);
3530         return c;
3531 }
3532
3533 static PyObject *
3534 long_xor(PyObject *v, PyObject *w)
3535 {
3536         PyLongObject *a, *b;
3537         PyObject *c;
3538         CONVERT_BINOP(v, w, &a, &b);
3539         c = long_bitwise(a, '^', b);
3540         Py_DECREF(a);
3541         Py_DECREF(b);
3542         return c;
3543 }
3544
3545 static PyObject *
3546 long_or(PyObject *v, PyObject *w)
3547 {
3548         PyLongObject *a, *b;
3549         PyObject *c;
3550         CONVERT_BINOP(v, w, &a, &b);
3551         c = long_bitwise(a, '|', b);
3552         Py_DECREF(a);
3553         Py_DECREF(b);
3554         return c;
3555 }
3556
3557 static int
3558 long_coerce(PyObject **pv, PyObject **pw)
3559 {
3560         if (PyInt_Check(*pw)) {
3561                 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
3562                 if (*pw == NULL)
3563                         return -1;
3564                 Py_INCREF(*pv);
3565                 return 0;
3566         }
3567         else if (PyLong_Check(*pw)) {
3568                 Py_INCREF(*pv);
3569                 Py_INCREF(*pw);
3570                 return 0;
3571         }
3572         return 1; /* Can't do it */
3573 }
3574
3575 static PyObject *
3576 long_long(PyObject *v)
3577 {
3578         if (PyLong_CheckExact(v))
3579                 Py_INCREF(v);
3580         else
3581                 v = _PyLong_Copy((PyLongObject *)v);
3582         return v;
3583 }
3584
3585 static PyObject *
3586 long_int(PyObject *v)
3587 {
3588         long x;
3589         x = PyLong_AsLong(v);
3590         if (PyErr_Occurred()) {
3591                 if (PyErr_ExceptionMatches(PyExc_OverflowError)) {
3592                                 PyErr_Clear();
3593                                 if (PyLong_CheckExact(v)) {
3594                                         Py_INCREF(v);
3595                                         return v;
3596                                 }
3597                                 else
3598                                         return _PyLong_Copy((PyLongObject *)v);
3599                 }
3600                 else
3601                         return NULL;
3602         }
3603         return PyInt_FromLong(x);
3604 }
3605
3606 static PyObject *
3607 long_float(PyObject *v)
3608 {
3609         double result;
3610         result = PyLong_AsDouble(v);
3611         if (result == -1.0 && PyErr_Occurred())
3612                 return NULL;
3613         return PyFloat_FromDouble(result);
3614 }
3615
3616 static PyObject *
3617 long_oct(PyObject *v)
3618 {
3619         return _PyLong_Format(v, 8, 1, 0);
3620 }
3621
3622 static PyObject *
3623 long_hex(PyObject *v)
3624 {
3625         return _PyLong_Format(v, 16, 1, 0);
3626 }
3627
3628 static PyObject *
3629 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
3630
3631 static PyObject *
3632 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3633 {
3634         PyObject *x = NULL;
3635         int base = -909;                     /* unlikely! */
3636         static char *kwlist[] = {"x", "base", 0};
3637
3638         if (type != &PyLong_Type)
3639                 return long_subtype_new(type, args, kwds); /* Wimp out */
3640         if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
3641                                          &x, &base))
3642                 return NULL;
3643         if (x == NULL)
3644                 return PyLong_FromLong(0L);
3645         if (base == -909)
3646                 return PyNumber_Long(x);
3647         else if (PyString_Check(x)) {
3648                 /* Since PyLong_FromString doesn't have a length parameter,
3649                  * check here for possible NULs in the string. */
3650                 char *string = PyString_AS_STRING(x);
3651                 if (strlen(string) != (size_t)PyString_Size(x)) {
3652                         /* create a repr() of the input string,
3653                          * just like PyLong_FromString does. */
3654                         PyObject *srepr;
3655                         srepr = PyObject_Repr(x);
3656                         if (srepr == NULL)
3657                                 return NULL;
3658                         PyErr_Format(PyExc_ValueError,
3659                              "invalid literal for long() with base %d: %s",
3660                              base, PyString_AS_STRING(srepr));
3661                         Py_DECREF(srepr);
3662                         return NULL;
3663                 }
3664                 return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
3665         }
3666 #ifdef Py_USING_UNICODE
3667         else if (PyUnicode_Check(x))
3668                 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
3669                                           PyUnicode_GET_SIZE(x),
3670                                           base);
3671 #endif
3672         else {
3673                 PyErr_SetString(PyExc_TypeError,
3674                         "long() can't convert non-string with explicit base");
3675                 return NULL;
3676         }
3677 }
3678
3679 /* Wimpy, slow approach to tp_new calls for subtypes of long:
3680    first create a regular long from whatever arguments we got,
3681    then allocate a subtype instance and initialize it from
3682    the regular long.  The regular long is then thrown away.
3683 */
3684 static PyObject *
3685 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
3686 {
3687         PyLongObject *tmp, *newobj;
3688         Py_ssize_t i, n;
3689
3690         assert(PyType_IsSubtype(type, &PyLong_Type));
3691         tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
3692         if (tmp == NULL)
3693                 return NULL;
3694         assert(PyLong_CheckExact(tmp));
3695         n = Py_SIZE(tmp);
3696         if (n < 0)
3697                 n = -n;
3698         newobj = (PyLongObject *)type->tp_alloc(type, n);
3699         if (newobj == NULL) {
3700                 Py_DECREF(tmp);
3701                 return NULL;
3702         }
3703         assert(PyLong_Check(newobj));
3704         Py_SIZE(newobj) = Py_SIZE(tmp);
3705         for (i = 0; i < n; i++)
3706                 newobj->ob_digit[i] = tmp->ob_digit[i];
3707         Py_DECREF(tmp);
3708         return (PyObject *)newobj;
3709 }
3710
3711 static PyObject *
3712 long_getnewargs(PyLongObject *v)
3713 {
3714         return Py_BuildValue("(N)", _PyLong_Copy(v));
3715 }
3716
3717 static PyObject *
3718 long_get0(PyLongObject *v, void *context) {
3719         return PyLong_FromLong(0L);
3720 }
3721
3722 static PyObject *
3723 long_get1(PyLongObject *v, void *context) {
3724         return PyLong_FromLong(1L);
3725 }
3726
3727 static PyObject *
3728 long__format__(PyObject *self, PyObject *args)
3729 {
3730         PyObject *format_spec;
3731
3732         if (!PyArg_ParseTuple(args, "O:__format__", &format_spec))
3733                 return NULL;
3734         if (PyBytes_Check(format_spec))
3735                 return _PyLong_FormatAdvanced(self,
3736                                               PyBytes_AS_STRING(format_spec),
3737                                               PyBytes_GET_SIZE(format_spec));
3738         if (PyUnicode_Check(format_spec)) {
3739                 /* Convert format_spec to a str */
3740                 PyObject *result;
3741                 PyObject *str_spec = PyObject_Str(format_spec);
3742
3743                 if (str_spec == NULL)
3744                         return NULL;
3745
3746                 result = _PyLong_FormatAdvanced(self,
3747                                                 PyBytes_AS_STRING(str_spec),
3748                                                 PyBytes_GET_SIZE(str_spec));
3749
3750                 Py_DECREF(str_spec);
3751                 return result;
3752         }
3753         PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode");
3754         return NULL;
3755 }
3756
3757 static PyObject *
3758 long_sizeof(PyLongObject *v)
3759 {
3760         Py_ssize_t res;
3761
3762         res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit);
3763         return PyInt_FromSsize_t(res);
3764 }
3765
3766 static PyObject *
3767 long_bit_length(PyLongObject *v)
3768 {
3769         PyLongObject *result, *x, *y;
3770         Py_ssize_t ndigits, msd_bits = 0;
3771         digit msd;
3772
3773         assert(v != NULL);
3774         assert(PyLong_Check(v));
3775
3776         ndigits = ABS(Py_SIZE(v));
3777         if (ndigits == 0)
3778                 return PyInt_FromLong(0);
3779
3780         msd = v->ob_digit[ndigits-1];
3781         while (msd >= 32) {
3782                 msd_bits += 6;
3783                 msd >>= 6;
3784         }
3785         msd_bits += (long)(BitLengthTable[msd]);
3786
3787         if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
3788                 return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
3789
3790         /* expression above may overflow; use Python integers instead */
3791         result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
3792         if (result == NULL)
3793                 return NULL;
3794         x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
3795         if (x == NULL)
3796                 goto error;
3797         y = (PyLongObject *)long_mul(result, x);
3798         Py_DECREF(x);
3799         if (y == NULL)
3800                 goto error;
3801         Py_DECREF(result);
3802         result = y;
3803
3804         x = (PyLongObject *)PyLong_FromLong(msd_bits);
3805         if (x == NULL)
3806                 goto error;
3807         y = (PyLongObject *)long_add(result, x);
3808         Py_DECREF(x);
3809         if (y == NULL)
3810                 goto error;
3811         Py_DECREF(result);
3812         result = y;
3813
3814         return (PyObject *)result;
3815
3816 error:
3817         Py_DECREF(result);
3818         return NULL;
3819 }
3820
3821 PyDoc_STRVAR(long_bit_length_doc,
3822 "long.bit_length() -> int or long\n\
3823 \n\
3824 Number of bits necessary to represent self in binary.\n\
3825 >>> bin(37L)\n\
3826 '0b100101'\n\
3827 >>> (37L).bit_length()\n\
3828 6");
3829
3830 #if 0
3831 static PyObject *
3832 long_is_finite(PyObject *v)
3833 {
3834         Py_RETURN_TRUE;
3835 }
3836 #endif
3837
3838 static PyMethodDef long_methods[] = {
3839         {"conjugate",   (PyCFunction)long_long, METH_NOARGS,
3840          "Returns self, the complex conjugate of any long."},
3841         {"bit_length",  (PyCFunction)long_bit_length, METH_NOARGS,
3842          long_bit_length_doc},
3843 #if 0
3844         {"is_finite",   (PyCFunction)long_is_finite,    METH_NOARGS,
3845          "Returns always True."},
3846 #endif
3847         {"__trunc__",   (PyCFunction)long_long, METH_NOARGS,
3848          "Truncating an Integral returns itself."},
3849         {"__getnewargs__",      (PyCFunction)long_getnewargs,   METH_NOARGS},
3850         {"__format__", (PyCFunction)long__format__, METH_VARARGS},
3851         {"__sizeof__",  (PyCFunction)long_sizeof, METH_NOARGS,
3852          "Returns size in memory, in bytes"},
3853         {NULL,          NULL}           /* sentinel */
3854 };
3855
3856 static PyGetSetDef long_getset[] = {
3857     {"real",
3858      (getter)long_long, (setter)NULL,
3859      "the real part of a complex number",
3860      NULL},
3861     {"imag",
3862      (getter)long_get0, (setter)NULL,
3863      "the imaginary part of a complex number",
3864      NULL},
3865     {"numerator",
3866      (getter)long_long, (setter)NULL,
3867      "the numerator of a rational number in lowest terms",
3868      NULL},
3869     {"denominator",
3870      (getter)long_get1, (setter)NULL,
3871      "the denominator of a rational number in lowest terms",
3872      NULL},
3873     {NULL}  /* Sentinel */
3874 };
3875
3876 PyDoc_STRVAR(long_doc,
3877 "long(x[, base]) -> integer\n\
3878 \n\
3879 Convert a string or number to a long integer, if possible.  A floating\n\
3880 point argument will be truncated towards zero (this does not include a\n\
3881 string representation of a floating point number!)  When converting a\n\
3882 string, use the optional base.  It is an error to supply a base when\n\
3883 converting a non-string.");
3884
3885 static PyNumberMethods long_as_number = {
3886         (binaryfunc)    long_add,       /*nb_add*/
3887         (binaryfunc)    long_sub,       /*nb_subtract*/
3888         (binaryfunc)    long_mul,       /*nb_multiply*/
3889                         long_classic_div, /*nb_divide*/
3890                         long_mod,       /*nb_remainder*/
3891                         long_divmod,    /*nb_divmod*/
3892                         long_pow,       /*nb_power*/
3893         (unaryfunc)     long_neg,       /*nb_negative*/
3894         (unaryfunc)     long_long,      /*tp_positive*/
3895         (unaryfunc)     long_abs,       /*tp_absolute*/
3896         (inquiry)       long_nonzero,   /*tp_nonzero*/
3897         (unaryfunc)     long_invert,    /*nb_invert*/
3898                         long_lshift,    /*nb_lshift*/
3899         (binaryfunc)    long_rshift,    /*nb_rshift*/
3900                         long_and,       /*nb_and*/
3901                         long_xor,       /*nb_xor*/
3902                         long_or,        /*nb_or*/
3903                         long_coerce,    /*nb_coerce*/
3904                         long_int,       /*nb_int*/
3905                         long_long,      /*nb_long*/
3906                         long_float,     /*nb_float*/
3907                         long_oct,       /*nb_oct*/
3908                         long_hex,       /*nb_hex*/
3909         0,                              /* nb_inplace_add */
3910         0,                              /* nb_inplace_subtract */
3911         0,                              /* nb_inplace_multiply */
3912         0,                              /* nb_inplace_divide */
3913         0,                              /* nb_inplace_remainder */
3914         0,                              /* nb_inplace_power */
3915         0,                              /* nb_inplace_lshift */
3916         0,                              /* nb_inplace_rshift */
3917         0,                              /* nb_inplace_and */
3918         0,                              /* nb_inplace_xor */
3919         0,                              /* nb_inplace_or */
3920         long_div,                       /* nb_floor_divide */
3921         long_true_divide,               /* nb_true_divide */
3922         0,                              /* nb_inplace_floor_divide */
3923         0,                              /* nb_inplace_true_divide */
3924         long_long,                      /* nb_index */
3925 };
3926
3927 PyTypeObject PyLong_Type = {
3928         PyObject_HEAD_INIT(&PyType_Type)
3929         0,                                      /* ob_size */
3930         "long",                                 /* tp_name */
3931         offsetof(PyLongObject, ob_digit),       /* tp_basicsize */
3932         sizeof(digit),                          /* tp_itemsize */
3933         long_dealloc,                           /* tp_dealloc */
3934         0,                                      /* tp_print */
3935         0,                                      /* tp_getattr */
3936         0,                                      /* tp_setattr */
3937         (cmpfunc)long_compare,                  /* tp_compare */
3938         long_repr,                              /* tp_repr */
3939         &long_as_number,                        /* tp_as_number */
3940         0,                                      /* tp_as_sequence */
3941         0,                                      /* tp_as_mapping */
3942         (hashfunc)long_hash,                    /* tp_hash */
3943         0,                                      /* tp_call */
3944         long_str,                               /* tp_str */
3945         PyObject_GenericGetAttr,                /* tp_getattro */
3946         0,                                      /* tp_setattro */
3947         0,                                      /* tp_as_buffer */
3948         Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
3949                 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
3950         long_doc,                               /* tp_doc */
3951         0,                                      /* tp_traverse */
3952         0,                                      /* tp_clear */
3953         0,                                      /* tp_richcompare */
3954         0,                                      /* tp_weaklistoffset */
3955         0,                                      /* tp_iter */
3956         0,                                      /* tp_iternext */
3957         long_methods,                           /* tp_methods */
3958         0,                                      /* tp_members */
3959         long_getset,                            /* tp_getset */
3960         0,                                      /* tp_base */
3961         0,                                      /* tp_dict */
3962         0,                                      /* tp_descr_get */
3963         0,                                      /* tp_descr_set */
3964         0,                                      /* tp_dictoffset */
3965         0,                                      /* tp_init */
3966         0,                                      /* tp_alloc */
3967         long_new,                               /* tp_new */
3968         PyObject_Del,                           /* tp_free */
3969 };
3970
3971 static PyTypeObject Long_InfoType;
3972
3973 PyDoc_STRVAR(long_info__doc__,
3974 "sys.long_info\n\
3975 \n\
3976 A struct sequence that holds information about Python's\n\
3977 internal representation of integers.  The attributes are read only.");
3978
3979 static PyStructSequence_Field long_info_fields[] = {
3980         {"bits_per_digit", "size of a digit in bits"},
3981         {"sizeof_digit", "size in bytes of the C type used to "
3982                          "represent a digit"},
3983         {NULL, NULL}
3984 };
3985
3986 static PyStructSequence_Desc long_info_desc = {
3987         "sys.long_info",   /* name */
3988         long_info__doc__,  /* doc */
3989         long_info_fields,  /* fields */
3990         2                 /* number of fields */
3991 };
3992
3993 PyObject *
3994 PyLong_GetInfo(void)
3995 {
3996         PyObject* long_info;
3997         int field = 0;
3998         long_info = PyStructSequence_New(&Long_InfoType);
3999         if (long_info == NULL)
4000                 return NULL;
4001         PyStructSequence_SET_ITEM(long_info, field++,
4002                                   PyInt_FromLong(PyLong_SHIFT));
4003         PyStructSequence_SET_ITEM(long_info, field++,
4004                                   PyInt_FromLong(sizeof(digit)));
4005         if (PyErr_Occurred()) {
4006                 Py_CLEAR(long_info);
4007                 return NULL;
4008         }
4009         return long_info;
4010 }
4011
4012 int
4013 _PyLong_Init(void)
4014 {
4015         /* initialize long_info */
4016         if (Long_InfoType.tp_name == 0)
4017                 PyStructSequence_InitType(&Long_InfoType, &long_info_desc);
4018         return 1;
4019 }