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