Objects/longobject.c

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