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