Python-2.7.3/Objects/longobject.c

Location Tool Test ID Function Issue
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:1150:9 clang-analyzer Access to field 'ob_refcnt' results in a dereference of a null pointer
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:1150:9 clang-analyzer Access to field 'ob_refcnt' results in a dereference of a null pointer
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:1471:46 clang-analyzer Division by zero
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2095:5 clang-analyzer Value stored to 'carry' is never read
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2175:5 clang-analyzer Value stored to 'carry' is never read
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2275:33 clang-analyzer The left expression of the compound assignment is an uninitialized value. The computed value will also be garbage
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2275:33 clang-analyzer The left expression of the compound assignment is an uninitialized value. The computed value will also be garbage
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2283:53 clang-analyzer The left operand of '&' is a garbage value
/builddir/build/BUILD/Python-2.7.3/Objects/longobject.c:2283:53 clang-analyzer The left operand of '&' is a garbage value
   1 /* Long (arbitrary precision) integer object implementation */
   2 
   3 /* XXX The functional organization of this file is terrible */
   4 
   5 #include "Python.h"
   6 #include "longintrepr.h"
   7 #include "structseq.h"
   8 
   9 #include <float.h>
  10 #include <ctype.h>
  11 #include <stddef.h>
  12 
  13 /* For long multiplication, use the O(N**2) school algorithm unless
  14  * both operands contain more than KARATSUBA_CUTOFF digits (this
  15  * being an internal Python long digit, in base PyLong_BASE).
  16  */
  17 #define KARATSUBA_CUTOFF 70
  18 #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
  19 
  20 /* For exponentiation, use the binary left-to-right algorithm
  21  * unless the exponent contains more than FIVEARY_CUTOFF digits.
  22  * In that case, do 5 bits at a time.  The potential drawback is that
  23  * a table of 2**5 intermediate results is computed.
  24  */
  25 #define FIVEARY_CUTOFF 8
  26 
  27 #define ABS(x) ((x) < 0 ? -(x) : (x))
  28 
  29 #undef MIN
  30 #undef MAX
  31 #define MAX(x, y) ((x) < (y) ? (y) : (x))
  32 #define MIN(x, y) ((x) > (y) ? (y) : (x))
  33 
  34 #define SIGCHECK(PyTryBlock)                            \
  35     do {                                                \
  36         if (--_Py_Ticker < 0) {                         \
  37             _Py_Ticker = _Py_CheckInterval;             \
  38             if (PyErr_CheckSignals()) PyTryBlock        \
  39                                           }             \
  40     } while(0)
  41 
  42 /* Normalize (remove leading zeros from) a long int object.
  43    Doesn't attempt to free the storage--in most cases, due to the nature
  44    of the algorithms used, this could save at most be one word anyway. */
  45 
  46 static PyLongObject *
  47 long_normalize(register PyLongObject *v)
  48 {
  49     Py_ssize_t j = ABS(Py_SIZE(v));
  50     Py_ssize_t i = j;
  51 
  52     while (i > 0 && v->ob_digit[i-1] == 0)
  53         --i;
  54     if (i != j)
  55         Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
  56     return v;
  57 }
  58 
  59 /* Allocate a new long int object with size digits.
  60    Return NULL and set exception if we run out of memory. */
  61 
  62 #define MAX_LONG_DIGITS \
  63     ((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
  64 
  65 PyLongObject *
  66 _PyLong_New(Py_ssize_t size)
  67 {
  68     if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
  69         PyErr_SetString(PyExc_OverflowError,
  70                         "too many digits in integer");
  71         return NULL;
  72     }
  73     /* coverity[ampersand_in_size] */
  74     /* XXX(nnorwitz): PyObject_NEW_VAR / _PyObject_VAR_SIZE need to detect
  75        overflow */
  76     return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
  77 }
  78 
  79 PyObject *
  80 _PyLong_Copy(PyLongObject *src)
  81 {
  82     PyLongObject *result;
  83     Py_ssize_t i;
  84 
  85     assert(src != NULL);
  86     i = src->ob_size;
  87     if (i < 0)
  88         i = -(i);
  89     result = _PyLong_New(i);
  90     if (result != NULL) {
  91         result->ob_size = src->ob_size;
  92         while (--i >= 0)
  93             result->ob_digit[i] = src->ob_digit[i];
  94     }
  95     return (PyObject *)result;
  96 }
  97 
  98 /* Create a new long int object from a C long int */
  99 
 100 PyObject *
 101 PyLong_FromLong(long ival)
 102 {
 103     PyLongObject *v;
 104     unsigned long abs_ival;
 105     unsigned long t;  /* unsigned so >> doesn't propagate sign bit */
 106     int ndigits = 0;
 107     int negative = 0;
 108 
 109     if (ival < 0) {
 110         /* if LONG_MIN == -LONG_MAX-1 (true on most platforms) then
 111            ANSI C says that the result of -ival is undefined when ival
 112            == LONG_MIN.  Hence the following workaround. */
 113         abs_ival = (unsigned long)(-1-ival) + 1;
 114         negative = 1;
 115     }
 116     else {
 117         abs_ival = (unsigned long)ival;
 118     }
 119 
 120     /* Count the number of Python digits.
 121        We used to pick 5 ("big enough for anything"), but that's a
 122        waste of time and space given that 5*15 = 75 bits are rarely
 123        needed. */
 124     t = abs_ival;
 125     while (t) {
 126         ++ndigits;
 127         t >>= PyLong_SHIFT;
 128     }
 129     v = _PyLong_New(ndigits);
 130     if (v != NULL) {
 131         digit *p = v->ob_digit;
 132         v->ob_size = negative ? -ndigits : ndigits;
 133         t = abs_ival;
 134         while (t) {
 135             *p++ = (digit)(t & PyLong_MASK);
 136             t >>= PyLong_SHIFT;
 137         }
 138     }
 139     return (PyObject *)v;
 140 }
 141 
 142 /* Create a new long int object from a C unsigned long int */
 143 
 144 PyObject *
 145 PyLong_FromUnsignedLong(unsigned long ival)
 146 {
 147     PyLongObject *v;
 148     unsigned long t;
 149     int ndigits = 0;
 150 
 151     /* Count the number of Python digits. */
 152     t = (unsigned long)ival;
 153     while (t) {
 154         ++ndigits;
 155         t >>= PyLong_SHIFT;
 156     }
 157     v = _PyLong_New(ndigits);
 158     if (v != NULL) {
 159         digit *p = v->ob_digit;
 160         Py_SIZE(v) = ndigits;
 161         while (ival) {
 162             *p++ = (digit)(ival & PyLong_MASK);
 163             ival >>= PyLong_SHIFT;
 164         }
 165     }
 166     return (PyObject *)v;
 167 }
 168 
 169 /* Create a new long int object from a C double */
 170 
 171 PyObject *
 172 PyLong_FromDouble(double dval)
 173 {
 174     PyLongObject *v;
 175     double frac;
 176     int i, ndig, expo, neg;
 177     neg = 0;
 178     if (Py_IS_INFINITY(dval)) {
 179         PyErr_SetString(PyExc_OverflowError,
 180                         "cannot convert float infinity to integer");
 181         return NULL;
 182     }
 183     if (Py_IS_NAN(dval)) {
 184         PyErr_SetString(PyExc_ValueError,
 185                         "cannot convert float NaN to integer");
 186         return NULL;
 187     }
 188     if (dval < 0.0) {
 189         neg = 1;
 190         dval = -dval;
 191     }
 192     frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
 193     if (expo <= 0)
 194         return PyLong_FromLong(0L);
 195     ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
 196     v = _PyLong_New(ndig);
 197     if (v == NULL)
 198         return NULL;
 199     frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
 200     for (i = ndig; --i >= 0; ) {
 201         digit bits = (digit)frac;
 202         v->ob_digit[i] = bits;
 203         frac = frac - (double)bits;
 204         frac = ldexp(frac, PyLong_SHIFT);
 205     }
 206     if (neg)
 207         Py_SIZE(v) = -(Py_SIZE(v));
 208     return (PyObject *)v;
 209 }
 210 
 211 /* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
 212  * anything about what happens when a signed integer operation overflows,
 213  * and some compilers think they're doing you a favor by being "clever"
 214  * then.  The bit pattern for the largest postive signed long is
 215  * (unsigned long)LONG_MAX, and for the smallest negative signed long
 216  * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
 217  * However, some other compilers warn about applying unary minus to an
 218  * unsigned operand.  Hence the weird "0-".
 219  */
 220 #define PY_ABS_LONG_MIN         (0-(unsigned long)LONG_MIN)
 221 #define PY_ABS_SSIZE_T_MIN      (0-(size_t)PY_SSIZE_T_MIN)
 222 
 223 /* Get a C long int from a Python long or Python int object.
 224    On overflow, returns -1 and sets *overflow to 1 or -1 depending
 225    on the sign of the result.  Otherwise *overflow is 0.
 226 
 227    For other errors (e.g., type error), returns -1 and sets an error
 228    condition.
 229 */
 230 
 231 long
 232 PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
 233 {
 234     /* This version by Tim Peters */
 235     register PyLongObject *v;
 236     unsigned long x, prev;
 237     long res;
 238     Py_ssize_t i;
 239     int sign;
 240     int do_decref = 0; /* if nb_int was called */
 241 
 242     *overflow = 0;
 243     if (vv == NULL) {
 244         PyErr_BadInternalCall();
 245         return -1;
 246     }
 247 
 248     if(PyInt_Check(vv))
 249         return PyInt_AsLong(vv);
 250 
 251     if (!PyLong_Check(vv)) {
 252         PyNumberMethods *nb;
 253         nb = vv->ob_type->tp_as_number;
 254         if (nb == NULL || nb->nb_int == NULL) {
 255             PyErr_SetString(PyExc_TypeError,
 256                             "an integer is required");
 257             return -1;
 258         }
 259         vv = (*nb->nb_int) (vv);
 260         if (vv == NULL)
 261             return -1;
 262         do_decref = 1;
 263         if(PyInt_Check(vv)) {
 264             res = PyInt_AsLong(vv);
 265             goto exit;
 266         }
 267         if (!PyLong_Check(vv)) {
 268             Py_DECREF(vv);
 269             PyErr_SetString(PyExc_TypeError,
 270                             "nb_int should return int object");
 271             return -1;
 272         }
 273     }
 274 
 275     res = -1;
 276     v = (PyLongObject *)vv;
 277     i = Py_SIZE(v);
 278 
 279     switch (i) {
 280     case -1:
 281         res = -(sdigit)v->ob_digit[0];
 282         break;
 283     case 0:
 284         res = 0;
 285         break;
 286     case 1:
 287         res = v->ob_digit[0];
 288         break;
 289     default:
 290         sign = 1;
 291         x = 0;
 292         if (i < 0) {
 293             sign = -1;
 294             i = -(i);
 295         }
 296         while (--i >= 0) {
 297             prev = x;
 298             x = (x << PyLong_SHIFT) + v->ob_digit[i];
 299             if ((x >> PyLong_SHIFT) != prev) {
 300                 *overflow = sign;
 301                 goto exit;
 302             }
 303         }
 304         /* Haven't lost any bits, but casting to long requires extra
 305          * care (see comment above).
 306          */
 307         if (x <= (unsigned long)LONG_MAX) {
 308             res = (long)x * sign;
 309         }
 310         else if (sign < 0 && x == PY_ABS_LONG_MIN) {
 311             res = LONG_MIN;
 312         }
 313         else {
 314             *overflow = sign;
 315             /* res is already set to -1 */
 316         }
 317     }
 318   exit:
 319     if (do_decref) {
 320         Py_DECREF(vv);
 321     }
 322     return res;
 323 }
 324 
 325 /* Get a C long int from a long int object.
 326    Returns -1 and sets an error condition if overflow occurs. */
 327 
 328 long
 329 PyLong_AsLong(PyObject *obj)
 330 {
 331     int overflow;
 332     long result = PyLong_AsLongAndOverflow(obj, &overflow);
 333     if (overflow) {
 334         /* XXX: could be cute and give a different
 335            message for overflow == -1 */
 336         PyErr_SetString(PyExc_OverflowError,
 337                         "Python int too large to convert to C long");
 338     }
 339     return result;
 340 }
 341 
 342 /* Get a Py_ssize_t from a long int object.
 343    Returns -1 and sets an error condition if overflow occurs. */
 344 
 345 Py_ssize_t
 346 PyLong_AsSsize_t(PyObject *vv) {
 347     register PyLongObject *v;
 348     size_t x, prev;
 349     Py_ssize_t i;
 350     int sign;
 351 
 352     if (vv == NULL || !PyLong_Check(vv)) {
 353         PyErr_BadInternalCall();
 354         return -1;
 355     }
 356     v = (PyLongObject *)vv;
 357     i = v->ob_size;
 358     sign = 1;
 359     x = 0;
 360     if (i < 0) {
 361         sign = -1;
 362         i = -(i);
 363     }
 364     while (--i >= 0) {
 365         prev = x;
 366         x = (x << PyLong_SHIFT) | v->ob_digit[i];
 367         if ((x >> PyLong_SHIFT) != prev)
 368             goto overflow;
 369     }
 370     /* Haven't lost any bits, but casting to a signed type requires
 371      * extra care (see comment above).
 372      */
 373     if (x <= (size_t)PY_SSIZE_T_MAX) {
 374         return (Py_ssize_t)x * sign;
 375     }
 376     else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
 377         return PY_SSIZE_T_MIN;
 378     }
 379     /* else overflow */
 380 
 381   overflow:
 382     PyErr_SetString(PyExc_OverflowError,
 383                     "long int too large to convert to int");
 384     return -1;
 385 }
 386 
 387 /* Get a C unsigned long int from a long int object.
 388    Returns -1 and sets an error condition if overflow occurs. */
 389 
 390 unsigned long
 391 PyLong_AsUnsignedLong(PyObject *vv)
 392 {
 393     register PyLongObject *v;
 394     unsigned long x, prev;
 395     Py_ssize_t i;
 396 
 397     if (vv == NULL || !PyLong_Check(vv)) {
 398         if (vv != NULL && PyInt_Check(vv)) {
 399             long val = PyInt_AsLong(vv);
 400             if (val < 0) {
 401                 PyErr_SetString(PyExc_OverflowError,
 402                                 "can't convert negative value "
 403                                 "to unsigned long");
 404                 return (unsigned long) -1;
 405             }
 406             return val;
 407         }
 408         PyErr_BadInternalCall();
 409         return (unsigned long) -1;
 410     }
 411     v = (PyLongObject *)vv;
 412     i = Py_SIZE(v);
 413     x = 0;
 414     if (i < 0) {
 415         PyErr_SetString(PyExc_OverflowError,
 416                         "can't convert negative value to unsigned long");
 417         return (unsigned long) -1;
 418     }
 419     while (--i >= 0) {
 420         prev = x;
 421         x = (x << PyLong_SHIFT) | v->ob_digit[i];
 422         if ((x >> PyLong_SHIFT) != prev) {
 423             PyErr_SetString(PyExc_OverflowError,
 424                             "long int too large to convert");
 425             return (unsigned long) -1;
 426         }
 427     }
 428     return x;
 429 }
 430 
 431 /* Get a C unsigned long int from a long int object, ignoring the high bits.
 432    Returns -1 and sets an error condition if an error occurs. */
 433 
 434 unsigned long
 435 PyLong_AsUnsignedLongMask(PyObject *vv)
 436 {
 437     register PyLongObject *v;
 438     unsigned long x;
 439     Py_ssize_t i;
 440     int sign;
 441 
 442     if (vv == NULL || !PyLong_Check(vv)) {
 443         if (vv != NULL && PyInt_Check(vv))
 444             return PyInt_AsUnsignedLongMask(vv);
 445         PyErr_BadInternalCall();
 446         return (unsigned long) -1;
 447     }
 448     v = (PyLongObject *)vv;
 449     i = v->ob_size;
 450     sign = 1;
 451     x = 0;
 452     if (i < 0) {
 453         sign = -1;
 454         i = -i;
 455     }
 456     while (--i >= 0) {
 457         x = (x << PyLong_SHIFT) | v->ob_digit[i];
 458     }
 459     return x * sign;
 460 }
 461 
 462 int
 463 _PyLong_Sign(PyObject *vv)
 464 {
 465     PyLongObject *v = (PyLongObject *)vv;
 466 
 467     assert(v != NULL);
 468     assert(PyLong_Check(v));
 469 
 470     return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
 471 }
 472 
 473 size_t
 474 _PyLong_NumBits(PyObject *vv)
 475 {
 476     PyLongObject *v = (PyLongObject *)vv;
 477     size_t result = 0;
 478     Py_ssize_t ndigits;
 479 
 480     assert(v != NULL);
 481     assert(PyLong_Check(v));
 482     ndigits = ABS(Py_SIZE(v));
 483     assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
 484     if (ndigits > 0) {
 485         digit msd = v->ob_digit[ndigits - 1];
 486 
 487         result = (ndigits - 1) * PyLong_SHIFT;
 488         if (result / PyLong_SHIFT != (size_t)(ndigits - 1))
 489             goto Overflow;
 490         do {
 491             ++result;
 492             if (result == 0)
 493                 goto Overflow;
 494             msd >>= 1;
 495         } while (msd);
 496     }
 497     return result;
 498 
 499   Overflow:
 500     PyErr_SetString(PyExc_OverflowError, "long has too many bits "
 501                     "to express in a platform size_t");
 502     return (size_t)-1;
 503 }
 504 
 505 PyObject *
 506 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
 507                       int little_endian, int is_signed)
 508 {
 509     const unsigned char* pstartbyte;    /* LSB of bytes */
 510     int incr;                           /* direction to move pstartbyte */
 511     const unsigned char* pendbyte;      /* MSB of bytes */
 512     size_t numsignificantbytes;         /* number of bytes that matter */
 513     Py_ssize_t ndigits;                 /* number of Python long digits */
 514     PyLongObject* v;                    /* result */
 515     Py_ssize_t idigit = 0;              /* next free index in v->ob_digit */
 516 
 517     if (n == 0)
 518         return PyLong_FromLong(0L);
 519 
 520     if (little_endian) {
 521         pstartbyte = bytes;
 522         pendbyte = bytes + n - 1;
 523         incr = 1;
 524     }
 525     else {
 526         pstartbyte = bytes + n - 1;
 527         pendbyte = bytes;
 528         incr = -1;
 529     }
 530 
 531     if (is_signed)
 532         is_signed = *pendbyte >= 0x80;
 533 
 534     /* Compute numsignificantbytes.  This consists of finding the most
 535        significant byte.  Leading 0 bytes are insignificant if the number
 536        is positive, and leading 0xff bytes if negative. */
 537     {
 538         size_t i;
 539         const unsigned char* p = pendbyte;
 540         const int pincr = -incr;  /* search MSB to LSB */
 541         const unsigned char insignficant = is_signed ? 0xff : 0x00;
 542 
 543         for (i = 0; i < n; ++i, p += pincr) {
 544             if (*p != insignficant)
 545                 break;
 546         }
 547         numsignificantbytes = n - i;
 548         /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
 549            actually has 2 significant bytes.  OTOH, 0xff0001 ==
 550            -0x00ffff, so we wouldn't *need* to bump it there; but we
 551            do for 0xffff = -0x0001.  To be safe without bothering to
 552            check every case, bump it regardless. */
 553         if (is_signed && numsignificantbytes < n)
 554             ++numsignificantbytes;
 555     }
 556 
 557     /* How many Python long digits do we need?  We have
 558        8*numsignificantbytes bits, and each Python long digit has
 559        PyLong_SHIFT bits, so it's the ceiling of the quotient. */
 560     /* catch overflow before it happens */
 561     if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
 562         PyErr_SetString(PyExc_OverflowError,
 563                         "byte array too long to convert to int");
 564         return NULL;
 565     }
 566     ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
 567     v = _PyLong_New(ndigits);
 568     if (v == NULL)
 569         return NULL;
 570 
 571     /* Copy the bits over.  The tricky parts are computing 2's-comp on
 572        the fly for signed numbers, and dealing with the mismatch between
 573        8-bit bytes and (probably) 15-bit Python digits.*/
 574     {
 575         size_t i;
 576         twodigits carry = 1;                    /* for 2's-comp calculation */
 577         twodigits accum = 0;                    /* sliding register */
 578         unsigned int accumbits = 0;             /* number of bits in accum */
 579         const unsigned char* p = pstartbyte;
 580 
 581         for (i = 0; i < numsignificantbytes; ++i, p += incr) {
 582             twodigits thisbyte = *p;
 583             /* Compute correction for 2's comp, if needed. */
 584             if (is_signed) {
 585                 thisbyte = (0xff ^ thisbyte) + carry;
 586                 carry = thisbyte >> 8;
 587                 thisbyte &= 0xff;
 588             }
 589             /* Because we're going LSB to MSB, thisbyte is
 590                more significant than what's already in accum,
 591                so needs to be prepended to accum. */
 592             accum |= (twodigits)thisbyte << accumbits;
 593             accumbits += 8;
 594             if (accumbits >= PyLong_SHIFT) {
 595                 /* There's enough to fill a Python digit. */
 596                 assert(idigit < ndigits);
 597                 v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
 598                 ++idigit;
 599                 accum >>= PyLong_SHIFT;
 600                 accumbits -= PyLong_SHIFT;
 601                 assert(accumbits < PyLong_SHIFT);
 602             }
 603         }
 604         assert(accumbits < PyLong_SHIFT);
 605         if (accumbits) {
 606             assert(idigit < ndigits);
 607             v->ob_digit[idigit] = (digit)accum;
 608             ++idigit;
 609         }
 610     }
 611 
 612     Py_SIZE(v) = is_signed ? -idigit : idigit;
 613     return (PyObject *)long_normalize(v);
 614 }
 615 
 616 int
 617 _PyLong_AsByteArray(PyLongObject* v,
 618                     unsigned char* bytes, size_t n,
 619                     int little_endian, int is_signed)
 620 {
 621     Py_ssize_t i;               /* index into v->ob_digit */
 622     Py_ssize_t ndigits;         /* |v->ob_size| */
 623     twodigits accum;            /* sliding register */
 624     unsigned int accumbits;     /* # bits in accum */
 625     int do_twos_comp;           /* store 2's-comp?  is_signed and v < 0 */
 626     digit carry;                /* for computing 2's-comp */
 627     size_t j;                   /* # bytes filled */
 628     unsigned char* p;           /* pointer to next byte in bytes */
 629     int pincr;                  /* direction to move p */
 630 
 631     assert(v != NULL && PyLong_Check(v));
 632 
 633     if (Py_SIZE(v) < 0) {
 634         ndigits = -(Py_SIZE(v));
 635         if (!is_signed) {
 636             PyErr_SetString(PyExc_OverflowError,
 637                             "can't convert negative long to unsigned");
 638             return -1;
 639         }
 640         do_twos_comp = 1;
 641     }
 642     else {
 643         ndigits = Py_SIZE(v);
 644         do_twos_comp = 0;
 645     }
 646 
 647     if (little_endian) {
 648         p = bytes;
 649         pincr = 1;
 650     }
 651     else {
 652         p = bytes + n - 1;
 653         pincr = -1;
 654     }
 655 
 656     /* Copy over all the Python digits.
 657        It's crucial that every Python digit except for the MSD contribute
 658        exactly PyLong_SHIFT bits to the total, so first assert that the long is
 659        normalized. */
 660     assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
 661     j = 0;
 662     accum = 0;
 663     accumbits = 0;
 664     carry = do_twos_comp ? 1 : 0;
 665     for (i = 0; i < ndigits; ++i) {
 666         digit thisdigit = v->ob_digit[i];
 667         if (do_twos_comp) {
 668             thisdigit = (thisdigit ^ PyLong_MASK) + carry;
 669             carry = thisdigit >> PyLong_SHIFT;
 670             thisdigit &= PyLong_MASK;
 671         }
 672         /* Because we're going LSB to MSB, thisdigit is more
 673            significant than what's already in accum, so needs to be
 674            prepended to accum. */
 675         accum |= (twodigits)thisdigit << accumbits;
 676 
 677         /* The most-significant digit may be (probably is) at least
 678            partly empty. */
 679         if (i == ndigits - 1) {
 680             /* Count # of sign bits -- they needn't be stored,
 681              * although for signed conversion we need later to
 682              * make sure at least one sign bit gets stored. */
 683             digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
 684             while (s != 0) {
 685                 s >>= 1;
 686                 accumbits++;
 687             }
 688         }
 689         else
 690             accumbits += PyLong_SHIFT;
 691 
 692         /* Store as many bytes as possible. */
 693         while (accumbits >= 8) {
 694             if (j >= n)
 695                 goto Overflow;
 696             ++j;
 697             *p = (unsigned char)(accum & 0xff);
 698             p += pincr;
 699             accumbits -= 8;
 700             accum >>= 8;
 701         }
 702     }
 703 
 704     /* Store the straggler (if any). */
 705     assert(accumbits < 8);
 706     assert(carry == 0);  /* else do_twos_comp and *every* digit was 0 */
 707     if (accumbits > 0) {
 708         if (j >= n)
 709             goto Overflow;
 710         ++j;
 711         if (do_twos_comp) {
 712             /* Fill leading bits of the byte with sign bits
 713                (appropriately pretending that the long had an
 714                infinite supply of sign bits). */
 715             accum |= (~(twodigits)0) << accumbits;
 716         }
 717         *p = (unsigned char)(accum & 0xff);
 718         p += pincr;
 719     }
 720     else if (j == n && n > 0 && is_signed) {
 721         /* The main loop filled the byte array exactly, so the code
 722            just above didn't get to ensure there's a sign bit, and the
 723            loop below wouldn't add one either.  Make sure a sign bit
 724            exists. */
 725         unsigned char msb = *(p - pincr);
 726         int sign_bit_set = msb >= 0x80;
 727         assert(accumbits == 0);
 728         if (sign_bit_set == do_twos_comp)
 729             return 0;
 730         else
 731             goto Overflow;
 732     }
 733 
 734     /* Fill remaining bytes with copies of the sign bit. */
 735     {
 736         unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
 737         for ( ; j < n; ++j, p += pincr)
 738             *p = signbyte;
 739     }
 740 
 741     return 0;
 742 
 743   Overflow:
 744     PyErr_SetString(PyExc_OverflowError, "long too big to convert");
 745     return -1;
 746 
 747 }
 748 
 749 /* Create a new long (or int) object from a C pointer */
 750 
 751 PyObject *
 752 PyLong_FromVoidPtr(void *p)
 753 {
 754 #if SIZEOF_VOID_P <= SIZEOF_LONG
 755     if ((long)p < 0)
 756         return PyLong_FromUnsignedLong((unsigned long)p);
 757     return PyInt_FromLong((long)p);
 758 #else
 759 
 760 #ifndef HAVE_LONG_LONG
 761 #   error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 762 #endif
 763 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 764 #   error "PyLong_FromVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
 765 #endif
 766     /* optimize null pointers */
 767     if (p == NULL)
 768         return PyInt_FromLong(0);
 769     return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)p);
 770 
 771 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 772 }
 773 
 774 /* Get a C pointer from a long object (or an int object in some cases) */
 775 
 776 void *
 777 PyLong_AsVoidPtr(PyObject *vv)
 778 {
 779     /* This function will allow int or long objects. If vv is neither,
 780        then the PyLong_AsLong*() functions will raise the exception:
 781        PyExc_SystemError, "bad argument to internal function"
 782     */
 783 #if SIZEOF_VOID_P <= SIZEOF_LONG
 784     long x;
 785 
 786     if (PyInt_Check(vv))
 787         x = PyInt_AS_LONG(vv);
 788     else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
 789         x = PyLong_AsLong(vv);
 790     else
 791         x = PyLong_AsUnsignedLong(vv);
 792 #else
 793 
 794 #ifndef HAVE_LONG_LONG
 795 #   error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
 796 #endif
 797 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
 798 #   error "PyLong_AsVoidPtr: sizeof(PY_LONG_LONG) < sizeof(void*)"
 799 #endif
 800     PY_LONG_LONG x;
 801 
 802     if (PyInt_Check(vv))
 803         x = PyInt_AS_LONG(vv);
 804     else if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
 805         x = PyLong_AsLongLong(vv);
 806     else
 807         x = PyLong_AsUnsignedLongLong(vv);
 808 
 809 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
 810 
 811     if (x == -1 && PyErr_Occurred())
 812         return NULL;
 813     return (void *)x;
 814 }
 815 
 816 #ifdef HAVE_LONG_LONG
 817 
 818 /* Initial PY_LONG_LONG support by Chris Herborth (chrish@qnx.com), later
 819  * rewritten to use the newer PyLong_{As,From}ByteArray API.
 820  */
 821 
 822 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
 823 #define PY_ABS_LLONG_MIN (0-(unsigned PY_LONG_LONG)PY_LLONG_MIN)
 824 
 825 /* Create a new long int object from a C PY_LONG_LONG int. */
 826 
 827 PyObject *
 828 PyLong_FromLongLong(PY_LONG_LONG ival)
 829 {
 830     PyLongObject *v;
 831     unsigned PY_LONG_LONG abs_ival;
 832     unsigned PY_LONG_LONG t;  /* unsigned so >> doesn't propagate sign bit */
 833     int ndigits = 0;
 834     int negative = 0;
 835 
 836     if (ival < 0) {
 837         /* avoid signed overflow on negation;  see comments
 838            in PyLong_FromLong above. */
 839         abs_ival = (unsigned PY_LONG_LONG)(-1-ival) + 1;
 840         negative = 1;
 841     }
 842     else {
 843         abs_ival = (unsigned PY_LONG_LONG)ival;
 844     }
 845 
 846     /* Count the number of Python digits.
 847        We used to pick 5 ("big enough for anything"), but that's a
 848        waste of time and space given that 5*15 = 75 bits are rarely
 849        needed. */
 850     t = abs_ival;
 851     while (t) {
 852         ++ndigits;
 853         t >>= PyLong_SHIFT;
 854     }
 855     v = _PyLong_New(ndigits);
 856     if (v != NULL) {
 857         digit *p = v->ob_digit;
 858         Py_SIZE(v) = negative ? -ndigits : ndigits;
 859         t = abs_ival;
 860         while (t) {
 861             *p++ = (digit)(t & PyLong_MASK);
 862             t >>= PyLong_SHIFT;
 863         }
 864     }
 865     return (PyObject *)v;
 866 }
 867 
 868 /* Create a new long int object from a C unsigned PY_LONG_LONG int. */
 869 
 870 PyObject *
 871 PyLong_FromUnsignedLongLong(unsigned PY_LONG_LONG ival)
 872 {
 873     PyLongObject *v;
 874     unsigned PY_LONG_LONG t;
 875     int ndigits = 0;
 876 
 877     /* Count the number of Python digits. */
 878     t = (unsigned PY_LONG_LONG)ival;
 879     while (t) {
 880         ++ndigits;
 881         t >>= PyLong_SHIFT;
 882     }
 883     v = _PyLong_New(ndigits);
 884     if (v != NULL) {
 885         digit *p = v->ob_digit;
 886         Py_SIZE(v) = ndigits;
 887         while (ival) {
 888             *p++ = (digit)(ival & PyLong_MASK);
 889             ival >>= PyLong_SHIFT;
 890         }
 891     }
 892     return (PyObject *)v;
 893 }
 894 
 895 /* Create a new long int object from a C Py_ssize_t. */
 896 
 897 PyObject *
 898 PyLong_FromSsize_t(Py_ssize_t ival)
 899 {
 900     Py_ssize_t bytes = ival;
 901     int one = 1;
 902     return _PyLong_FromByteArray((unsigned char *)&bytes,
 903                                  SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 1);
 904 }
 905 
 906 /* Create a new long int object from a C size_t. */
 907 
 908 PyObject *
 909 PyLong_FromSize_t(size_t ival)
 910 {
 911     size_t bytes = ival;
 912     int one = 1;
 913     return _PyLong_FromByteArray((unsigned char *)&bytes,
 914                                  SIZEOF_SIZE_T, IS_LITTLE_ENDIAN, 0);
 915 }
 916 
 917 /* Get a C PY_LONG_LONG int from a long int object.
 918    Return -1 and set an error if overflow occurs. */
 919 
 920 PY_LONG_LONG
 921 PyLong_AsLongLong(PyObject *vv)
 922 {
 923     PY_LONG_LONG bytes;
 924     int one = 1;
 925     int res;
 926 
 927     if (vv == NULL) {
 928         PyErr_BadInternalCall();
 929         return -1;
 930     }
 931     if (!PyLong_Check(vv)) {
 932         PyNumberMethods *nb;
 933         PyObject *io;
 934         if (PyInt_Check(vv))
 935             return (PY_LONG_LONG)PyInt_AsLong(vv);
 936         if ((nb = vv->ob_type->tp_as_number) == NULL ||
 937             nb->nb_int == NULL) {
 938             PyErr_SetString(PyExc_TypeError, "an integer is required");
 939             return -1;
 940         }
 941         io = (*nb->nb_int) (vv);
 942         if (io == NULL)
 943             return -1;
 944         if (PyInt_Check(io)) {
 945             bytes = PyInt_AsLong(io);
 946             Py_DECREF(io);
 947             return bytes;
 948         }
 949         if (PyLong_Check(io)) {
 950             bytes = PyLong_AsLongLong(io);
 951             Py_DECREF(io);
 952             return bytes;
 953         }
 954         Py_DECREF(io);
 955         PyErr_SetString(PyExc_TypeError, "integer conversion failed");
 956         return -1;
 957     }
 958 
 959     res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
 960                               SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
 961 
 962     /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
 963     if (res < 0)
 964         return (PY_LONG_LONG)-1;
 965     else
 966         return bytes;
 967 }
 968 
 969 /* Get a C unsigned PY_LONG_LONG int from a long int object.
 970    Return -1 and set an error if overflow occurs. */
 971 
 972 unsigned PY_LONG_LONG
 973 PyLong_AsUnsignedLongLong(PyObject *vv)
 974 {
 975     unsigned PY_LONG_LONG bytes;
 976     int one = 1;
 977     int res;
 978 
 979     if (vv == NULL || !PyLong_Check(vv)) {
 980         PyErr_BadInternalCall();
 981         return (unsigned PY_LONG_LONG)-1;
 982     }
 983 
 984     res = _PyLong_AsByteArray((PyLongObject *)vv, (unsigned char *)&bytes,
 985                               SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
 986 
 987     /* Plan 9 can't handle PY_LONG_LONG in ? : expressions */
 988     if (res < 0)
 989         return (unsigned PY_LONG_LONG)res;
 990     else
 991         return bytes;
 992 }
 993 
 994 /* Get a C unsigned long int from a long int object, ignoring the high bits.
 995    Returns -1 and sets an error condition if an error occurs. */
 996 
 997 unsigned PY_LONG_LONG
 998 PyLong_AsUnsignedLongLongMask(PyObject *vv)
 999 {
1000     register PyLongObject *v;
1001     unsigned PY_LONG_LONG x;
1002     Py_ssize_t i;
1003     int sign;
1004 
1005     if (vv == NULL || !PyLong_Check(vv)) {
1006         PyErr_BadInternalCall();
1007         return (unsigned long) -1;
1008     }
1009     v = (PyLongObject *)vv;
1010     i = v->ob_size;
1011     sign = 1;
1012     x = 0;
1013     if (i < 0) {
1014         sign = -1;
1015         i = -i;
1016     }
1017     while (--i >= 0) {
1018         x = (x << PyLong_SHIFT) | v->ob_digit[i];
1019     }
1020     return x * sign;
1021 }
1022 
1023 /* Get a C long long int from a Python long or Python int object.
1024    On overflow, returns -1 and sets *overflow to 1 or -1 depending
1025    on the sign of the result.  Otherwise *overflow is 0.
1026 
1027    For other errors (e.g., type error), returns -1 and sets an error
1028    condition.
1029 */
1030 
1031 PY_LONG_LONG
1032 PyLong_AsLongLongAndOverflow(PyObject *vv, int *overflow)
1033 {
1034     /* This version by Tim Peters */
1035     register PyLongObject *v;
1036     unsigned PY_LONG_LONG x, prev;
1037     PY_LONG_LONG res;
1038     Py_ssize_t i;
1039     int sign;
1040     int do_decref = 0; /* if nb_int was called */
1041 
1042     *overflow = 0;
1043     if (vv == NULL) {
1044         PyErr_BadInternalCall();
1045         return -1;
1046     }
1047 
1048     if (PyInt_Check(vv))
1049         return PyInt_AsLong(vv);
1050 
1051     if (!PyLong_Check(vv)) {
1052         PyNumberMethods *nb;
1053         nb = vv->ob_type->tp_as_number;
1054         if (nb == NULL || nb->nb_int == NULL) {
1055             PyErr_SetString(PyExc_TypeError,
1056                             "an integer is required");
1057             return -1;
1058         }
1059         vv = (*nb->nb_int) (vv);
1060         if (vv == NULL)
1061             return -1;
1062         do_decref = 1;
1063         if(PyInt_Check(vv)) {
1064             res = PyInt_AsLong(vv);
1065             goto exit;
1066         }
1067         if (!PyLong_Check(vv)) {
1068             Py_DECREF(vv);
1069             PyErr_SetString(PyExc_TypeError,
1070                             "nb_int should return int object");
1071             return -1;
1072         }
1073     }
1074 
1075     res = -1;
1076     v = (PyLongObject *)vv;
1077     i = Py_SIZE(v);
1078 
1079     switch (i) {
1080     case -1:
1081         res = -(sdigit)v->ob_digit[0];
1082         break;
1083     case 0:
1084         res = 0;
1085         break;
1086     case 1:
1087         res = v->ob_digit[0];
1088         break;
1089     default:
1090         sign = 1;
1091         x = 0;
1092         if (i < 0) {
1093             sign = -1;
1094             i = -(i);
1095         }
1096         while (--i >= 0) {
1097             prev = x;
1098             x = (x << PyLong_SHIFT) + v->ob_digit[i];
1099             if ((x >> PyLong_SHIFT) != prev) {
1100                 *overflow = sign;
1101                 goto exit;
1102             }
1103         }
1104         /* Haven't lost any bits, but casting to long requires extra
1105          * care (see comment above).
1106          */
1107         if (x <= (unsigned PY_LONG_LONG)PY_LLONG_MAX) {
1108             res = (PY_LONG_LONG)x * sign;
1109         }
1110         else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
1111             res = PY_LLONG_MIN;
1112         }
1113         else {
1114             *overflow = sign;
1115             /* res is already set to -1 */
1116         }
1117     }
1118   exit:
1119     if (do_decref) {
1120         Py_DECREF(vv);
1121     }
1122     return res;
1123 }
1124 
1125 #undef IS_LITTLE_ENDIAN
1126 
1127 #endif /* HAVE_LONG_LONG */
1128 
1129 
1130 static int
1131 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
1132     if (PyLong_Check(v)) {
1133         *a = (PyLongObject *) v;
1134         Py_INCREF(v);
1135     }
1136     else if (PyInt_Check(v)) {
1137         *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
1138     }
1139     else {
1140         return 0;
1141     }
1142     if (PyLong_Check(w)) {
1143         *b = (PyLongObject *) w;
1144         Py_INCREF(w);
1145     }
1146     else if (PyInt_Check(w)) {
1147         *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
1148     }
1149     else {
1150         Py_DECREF(*a);
Access to field 'ob_refcnt' results in a dereference of a null pointer
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

Access to field 'ob_refcnt' results in a dereference of a null pointer
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

1151 return 0; 1152 } 1153 return 1; 1154 } 1155 1156 #define CONVERT_BINOP(v, w, a, b) \ 1157 do { \ 1158 if (!convert_binop(v, w, a, b)) { \ 1159 Py_INCREF(Py_NotImplemented); \ 1160 return Py_NotImplemented; \ 1161 } \ 1162 } while(0) \ 1163 1164 /* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d < 1165 2**k if d is nonzero, else 0. */ 1166 1167 static const unsigned char BitLengthTable[32] = { 1168 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 1169 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 1170 }; 1171 1172 static int 1173 bits_in_digit(digit d) 1174 { 1175 int d_bits = 0; 1176 while (d >= 32) { 1177 d_bits += 6; 1178 d >>= 6; 1179 } 1180 d_bits += (int)BitLengthTable[d]; 1181 return d_bits; 1182 } 1183 1184 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] 1185 * is modified in place, by adding y to it. Carries are propagated as far as 1186 * x[m-1], and the remaining carry (0 or 1) is returned. 1187 */ 1188 static digit 1189 v_iadd(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) 1190 { 1191 Py_ssize_t i; 1192 digit carry = 0; 1193 1194 assert(m >= n); 1195 for (i = 0; i < n; ++i) { 1196 carry += x[i] + y[i]; 1197 x[i] = carry & PyLong_MASK; 1198 carry >>= PyLong_SHIFT; 1199 assert((carry & 1) == carry); 1200 } 1201 for (; carry && i < m; ++i) { 1202 carry += x[i]; 1203 x[i] = carry & PyLong_MASK; 1204 carry >>= PyLong_SHIFT; 1205 assert((carry & 1) == carry); 1206 } 1207 return carry; 1208 } 1209 1210 /* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n] 1211 * is modified in place, by subtracting y from it. Borrows are propagated as 1212 * far as x[m-1], and the remaining borrow (0 or 1) is returned. 1213 */ 1214 static digit 1215 v_isub(digit *x, Py_ssize_t m, digit *y, Py_ssize_t n) 1216 { 1217 Py_ssize_t i; 1218 digit borrow = 0; 1219 1220 assert(m >= n); 1221 for (i = 0; i < n; ++i) { 1222 borrow = x[i] - y[i] - borrow; 1223 x[i] = borrow & PyLong_MASK; 1224 borrow >>= PyLong_SHIFT; 1225 borrow &= 1; /* keep only 1 sign bit */ 1226 } 1227 for (; borrow && i < m; ++i) { 1228 borrow = x[i] - borrow; 1229 x[i] = borrow & PyLong_MASK; 1230 borrow >>= PyLong_SHIFT; 1231 borrow &= 1; 1232 } 1233 return borrow; 1234 } 1235 1236 /* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put 1237 * result in z[0:m], and return the d bits shifted out of the top. 1238 */ 1239 static digit 1240 v_lshift(digit *z, digit *a, Py_ssize_t m, int d) 1241 { 1242 Py_ssize_t i; 1243 digit carry = 0; 1244 1245 assert(0 <= d && d < PyLong_SHIFT); 1246 for (i=0; i < m; i++) { 1247 twodigits acc = (twodigits)a[i] << d | carry; 1248 z[i] = (digit)acc & PyLong_MASK; 1249 carry = (digit)(acc >> PyLong_SHIFT); 1250 } 1251 return carry; 1252 } 1253 1254 /* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put 1255 * result in z[0:m], and return the d bits shifted out of the bottom. 1256 */ 1257 static digit 1258 v_rshift(digit *z, digit *a, Py_ssize_t m, int d) 1259 { 1260 Py_ssize_t i; 1261 digit carry = 0; 1262 digit mask = ((digit)1 << d) - 1U; 1263 1264 assert(0 <= d && d < PyLong_SHIFT); 1265 for (i=m; i-- > 0;) { 1266 twodigits acc = (twodigits)carry << PyLong_SHIFT | a[i]; 1267 carry = (digit)acc & mask; 1268 z[i] = (digit)(acc >> d); 1269 } 1270 return carry; 1271 } 1272 1273 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient 1274 in pout, and returning the remainder. pin and pout point at the LSD. 1275 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in 1276 _PyLong_Format, but that should be done with great care since longs are 1277 immutable. */ 1278 1279 static digit 1280 inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n) 1281 { 1282 twodigits rem = 0; 1283 1284 assert(n > 0 && n <= PyLong_MASK); 1285 pin += size; 1286 pout += size; 1287 while (--size >= 0) { 1288 digit hi; 1289 rem = (rem << PyLong_SHIFT) | *--pin; 1290 *--pout = hi = (digit)(rem / n); 1291 rem -= (twodigits)hi * n; 1292 } 1293 return (digit)rem; 1294 } 1295 1296 /* Divide a long integer by a digit, returning both the quotient 1297 (as function result) and the remainder (through *prem). 1298 The sign of a is ignored; n should not be zero. */ 1299 1300 static PyLongObject * 1301 divrem1(PyLongObject *a, digit n, digit *prem) 1302 { 1303 const Py_ssize_t size = ABS(Py_SIZE(a)); 1304 PyLongObject *z; 1305 1306 assert(n > 0 && n <= PyLong_MASK); 1307 z = _PyLong_New(size); 1308 if (z == NULL) 1309 return NULL; 1310 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n); 1311 return long_normalize(z); 1312 } 1313 1314 /* Convert a long integer to a base 10 string. Returns a new non-shared 1315 string. (Return value is non-shared so that callers can modify the 1316 returned value if necessary.) */ 1317 1318 static PyObject * 1319 long_to_decimal_string(PyObject *aa, int addL) 1320 { 1321 PyLongObject *scratch, *a; 1322 PyObject *str; 1323 Py_ssize_t size, strlen, size_a, i, j; 1324 digit *pout, *pin, rem, tenpow; 1325 char *p; 1326 int negative; 1327 1328 a = (PyLongObject *)aa; 1329 if (a == NULL || !PyLong_Check(a)) { 1330 PyErr_BadInternalCall(); 1331 return NULL; 1332 } 1333 size_a = ABS(Py_SIZE(a)); 1334 negative = Py_SIZE(a) < 0; 1335 1336 /* quick and dirty upper bound for the number of digits 1337 required to express a in base _PyLong_DECIMAL_BASE: 1338 1339 #digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE)) 1340 1341 But log2(a) < size_a * PyLong_SHIFT, and 1342 log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT 1343 > 3 * _PyLong_DECIMAL_SHIFT 1344 */ 1345 if (size_a > PY_SSIZE_T_MAX / PyLong_SHIFT) { 1346 PyErr_SetString(PyExc_OverflowError, 1347 "long is too large to format"); 1348 return NULL; 1349 } 1350 /* the expression size_a * PyLong_SHIFT is now safe from overflow */ 1351 size = 1 + size_a * PyLong_SHIFT / (3 * _PyLong_DECIMAL_SHIFT); 1352 scratch = _PyLong_New(size); 1353 if (scratch == NULL) 1354 return NULL; 1355 1356 /* convert array of base _PyLong_BASE digits in pin to an array of 1357 base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP, 1358 Volume 2 (3rd edn), section 4.4, Method 1b). */ 1359 pin = a->ob_digit; 1360 pout = scratch->ob_digit; 1361 size = 0; 1362 for (i = size_a; --i >= 0; ) { 1363 digit hi = pin[i]; 1364 for (j = 0; j < size; j++) { 1365 twodigits z = (twodigits)pout[j] << PyLong_SHIFT | hi; 1366 hi = (digit)(z / _PyLong_DECIMAL_BASE); 1367 pout[j] = (digit)(z - (twodigits)hi * 1368 _PyLong_DECIMAL_BASE); 1369 } 1370 while (hi) { 1371 pout[size++] = hi % _PyLong_DECIMAL_BASE; 1372 hi /= _PyLong_DECIMAL_BASE; 1373 } 1374 /* check for keyboard interrupt */ 1375 SIGCHECK({ 1376 Py_DECREF(scratch); 1377 return NULL; 1378 }); 1379 } 1380 /* pout should have at least one digit, so that the case when a = 0 1381 works correctly */ 1382 if (size == 0) 1383 pout[size++] = 0; 1384 1385 /* calculate exact length of output string, and allocate */ 1386 strlen = (addL != 0) + negative + 1387 1 + (size - 1) * _PyLong_DECIMAL_SHIFT; 1388 tenpow = 10; 1389 rem = pout[size-1]; 1390 while (rem >= tenpow) { 1391 tenpow *= 10; 1392 strlen++; 1393 } 1394 str = PyString_FromStringAndSize(NULL, strlen); 1395 if (str == NULL) { 1396 Py_DECREF(scratch); 1397 return NULL; 1398 } 1399 1400 /* fill the string right-to-left */ 1401 p = PyString_AS_STRING(str) + strlen; 1402 *p = '\0'; 1403 if (addL) 1404 *--p = 'L'; 1405 /* pout[0] through pout[size-2] contribute exactly 1406 _PyLong_DECIMAL_SHIFT digits each */ 1407 for (i=0; i < size - 1; i++) { 1408 rem = pout[i]; 1409 for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) { 1410 *--p = '0' + rem % 10; 1411 rem /= 10; 1412 } 1413 } 1414 /* pout[size-1]: always produce at least one decimal digit */ 1415 rem = pout[i]; 1416 do { 1417 *--p = '0' + rem % 10; 1418 rem /= 10; 1419 } while (rem != 0); 1420 1421 /* and sign */ 1422 if (negative) 1423 *--p = '-'; 1424 1425 /* check we've counted correctly */ 1426 assert(p == PyString_AS_STRING(str)); 1427 Py_DECREF(scratch); 1428 return (PyObject *)str; 1429 } 1430 1431 /* Convert the long to a string object with given base, 1432 appending a base prefix of 0[box] if base is 2, 8 or 16. 1433 Add a trailing "L" if addL is non-zero. 1434 If newstyle is zero, then use the pre-2.6 behavior of octal having 1435 a leading "0", instead of the prefix "0o" */ 1436 PyAPI_FUNC(PyObject *) 1437 _PyLong_Format(PyObject *aa, int base, int addL, int newstyle) 1438 { 1439 register PyLongObject *a = (PyLongObject *)aa; 1440 PyStringObject *str; 1441 Py_ssize_t i, sz; 1442 Py_ssize_t size_a; 1443 char *p; 1444 int bits; 1445 char sign = '\0'; 1446 1447 if (base == 10) 1448 return long_to_decimal_string((PyObject *)a, addL); 1449 1450 if (a == NULL || !PyLong_Check(a)) { 1451 PyErr_BadInternalCall(); 1452 return NULL; 1453 } 1454 assert(base >= 2 && base <= 36); 1455 size_a = ABS(Py_SIZE(a)); 1456 1457 /* Compute a rough upper bound for the length of the string */ 1458 i = base; 1459 bits = 0; 1460 while (i > 1) { 1461 ++bits; 1462 i >>= 1; 1463 } 1464 i = 5 + (addL ? 1 : 0); 1465 /* ensure we don't get signed overflow in sz calculation */ 1466 if (size_a > (PY_SSIZE_T_MAX - i) / PyLong_SHIFT) { 1467 PyErr_SetString(PyExc_OverflowError, 1468 "long is too large to format"); 1469 return NULL; 1470 } 1471 sz = i + 1 + (size_a * PyLong_SHIFT - 1) / bits;
Division by zero
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

1472 assert(sz >= 0); 1473 str = (PyStringObject *) PyString_FromStringAndSize((char *)0, sz); 1474 if (str == NULL) 1475 return NULL; 1476 p = PyString_AS_STRING(str) + sz; 1477 *p = '\0'; 1478 if (addL) 1479 *--p = 'L'; 1480 if (a->ob_size < 0) 1481 sign = '-'; 1482 1483 if (a->ob_size == 0) { 1484 *--p = '0'; 1485 } 1486 else if ((base & (base - 1)) == 0) { 1487 /* JRH: special case for power-of-2 bases */ 1488 twodigits accum = 0; 1489 int accumbits = 0; /* # of bits in accum */ 1490 int basebits = 1; /* # of bits in base-1 */ 1491 i = base; 1492 while ((i >>= 1) > 1) 1493 ++basebits; 1494 1495 for (i = 0; i < size_a; ++i) { 1496 accum |= (twodigits)a->ob_digit[i] << accumbits; 1497 accumbits += PyLong_SHIFT; 1498 assert(accumbits >= basebits); 1499 do { 1500 char cdigit = (char)(accum & (base - 1)); 1501 cdigit += (cdigit < 10) ? '0' : 'a'-10; 1502 assert(p > PyString_AS_STRING(str)); 1503 *--p = cdigit; 1504 accumbits -= basebits; 1505 accum >>= basebits; 1506 } while (i < size_a-1 ? accumbits >= basebits : accum > 0); 1507 } 1508 } 1509 else { 1510 /* Not 0, and base not a power of 2. Divide repeatedly by 1511 base, but for speed use the highest power of base that 1512 fits in a digit. */ 1513 Py_ssize_t size = size_a; 1514 digit *pin = a->ob_digit; 1515 PyLongObject *scratch; 1516 /* powbasw <- largest power of base that fits in a digit. */ 1517 digit powbase = base; /* powbase == base ** power */ 1518 int power = 1; 1519 for (;;) { 1520 twodigits newpow = powbase * (twodigits)base; 1521 if (newpow >> PyLong_SHIFT) 1522 /* doesn't fit in a digit */ 1523 break; 1524 powbase = (digit)newpow; 1525 ++power; 1526 } 1527 1528 /* Get a scratch area for repeated division. */ 1529 scratch = _PyLong_New(size); 1530 if (scratch == NULL) { 1531 Py_DECREF(str); 1532 return NULL; 1533 } 1534 1535 /* Repeatedly divide by powbase. */ 1536 do { 1537 int ntostore = power; 1538 digit rem = inplace_divrem1(scratch->ob_digit, 1539 pin, size, powbase); 1540 pin = scratch->ob_digit; /* no need to use a again */ 1541 if (pin[size - 1] == 0) 1542 --size; 1543 SIGCHECK({ 1544 Py_DECREF(scratch); 1545 Py_DECREF(str); 1546 return NULL; 1547 }); 1548 1549 /* Break rem into digits. */ 1550 assert(ntostore > 0); 1551 do { 1552 digit nextrem = (digit)(rem / base); 1553 char c = (char)(rem - nextrem * base); 1554 assert(p > PyString_AS_STRING(str)); 1555 c += (c < 10) ? '0' : 'a'-10; 1556 *--p = c; 1557 rem = nextrem; 1558 --ntostore; 1559 /* Termination is a bit delicate: must not 1560 store leading zeroes, so must get out if 1561 remaining quotient and rem are both 0. */ 1562 } while (ntostore && (size || rem)); 1563 } while (size != 0); 1564 Py_DECREF(scratch); 1565 } 1566 1567 if (base == 2) { 1568 *--p = 'b'; 1569 *--p = '0'; 1570 } 1571 else if (base == 8) { 1572 if (newstyle) { 1573 *--p = 'o'; 1574 *--p = '0'; 1575 } 1576 else 1577 if (size_a != 0) 1578 *--p = '0'; 1579 } 1580 else if (base == 16) { 1581 *--p = 'x'; 1582 *--p = '0'; 1583 } 1584 else if (base != 10) { 1585 *--p = '#'; 1586 *--p = '0' + base%10; 1587 if (base > 10) 1588 *--p = '0' + base/10; 1589 } 1590 if (sign) 1591 *--p = sign; 1592 if (p != PyString_AS_STRING(str)) { 1593 char *q = PyString_AS_STRING(str); 1594 assert(p > q); 1595 do { 1596 } while ((*q++ = *p++) != '\0'); 1597 q--; 1598 _PyString_Resize((PyObject **)&str, 1599 (Py_ssize_t) (q - PyString_AS_STRING(str))); 1600 } 1601 return (PyObject *)str; 1602 } 1603 1604 /* Table of digit values for 8-bit string -> integer conversion. 1605 * '0' maps to 0, ..., '9' maps to 9. 1606 * 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35. 1607 * All other indices map to 37. 1608 * Note that when converting a base B string, a char c is a legitimate 1609 * base B digit iff _PyLong_DigitValue[Py_CHARMASK(c)] < B. 1610 */ 1611 int _PyLong_DigitValue[256] = { 1612 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1613 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1614 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1615 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37, 1616 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1617 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37, 1618 37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 1619 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37, 1620 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1621 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1622 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1623 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1624 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1625 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1626 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1627 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 1628 }; 1629 1630 /* *str points to the first digit in a string of base `base` digits. base 1631 * is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first 1632 * non-digit (which may be *str!). A normalized long is returned. 1633 * The point to this routine is that it takes time linear in the number of 1634 * string characters. 1635 */ 1636 static PyLongObject * 1637 long_from_binary_base(char **str, int base) 1638 { 1639 char *p = *str; 1640 char *start = p; 1641 int bits_per_char; 1642 Py_ssize_t n; 1643 PyLongObject *z; 1644 twodigits accum; 1645 int bits_in_accum; 1646 digit *pdigit; 1647 1648 assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0); 1649 n = base; 1650 for (bits_per_char = -1; n; ++bits_per_char) 1651 n >>= 1; 1652 /* n <- total # of bits needed, while setting p to end-of-string */ 1653 while (_PyLong_DigitValue[Py_CHARMASK(*p)] < base) 1654 ++p; 1655 *str = p; 1656 /* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */ 1657 n = (p - start) * bits_per_char + PyLong_SHIFT - 1; 1658 if (n / bits_per_char < p - start) { 1659 PyErr_SetString(PyExc_ValueError, 1660 "long string too large to convert"); 1661 return NULL; 1662 } 1663 n = n / PyLong_SHIFT; 1664 z = _PyLong_New(n); 1665 if (z == NULL) 1666 return NULL; 1667 /* Read string from right, and fill in long from left; i.e., 1668 * from least to most significant in both. 1669 */ 1670 accum = 0; 1671 bits_in_accum = 0; 1672 pdigit = z->ob_digit; 1673 while (--p >= start) { 1674 int k = _PyLong_DigitValue[Py_CHARMASK(*p)]; 1675 assert(k >= 0 && k < base); 1676 accum |= (twodigits)k << bits_in_accum; 1677 bits_in_accum += bits_per_char; 1678 if (bits_in_accum >= PyLong_SHIFT) { 1679 *pdigit++ = (digit)(accum & PyLong_MASK); 1680 assert(pdigit - z->ob_digit <= n); 1681 accum >>= PyLong_SHIFT; 1682 bits_in_accum -= PyLong_SHIFT; 1683 assert(bits_in_accum < PyLong_SHIFT); 1684 } 1685 } 1686 if (bits_in_accum) { 1687 assert(bits_in_accum <= PyLong_SHIFT); 1688 *pdigit++ = (digit)accum; 1689 assert(pdigit - z->ob_digit <= n); 1690 } 1691 while (pdigit - z->ob_digit < n) 1692 *pdigit++ = 0; 1693 return long_normalize(z); 1694 } 1695 1696 PyObject * 1697 PyLong_FromString(char *str, char **pend, int base) 1698 { 1699 int sign = 1; 1700 char *start, *orig_str = str; 1701 PyLongObject *z; 1702 PyObject *strobj, *strrepr; 1703 Py_ssize_t slen; 1704 1705 if ((base != 0 && base < 2) || base > 36) { 1706 PyErr_SetString(PyExc_ValueError, 1707 "long() arg 2 must be >= 2 and <= 36"); 1708 return NULL; 1709 } 1710 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 1711 str++; 1712 if (*str == '+') 1713 ++str; 1714 else if (*str == '-') { 1715 ++str; 1716 sign = -1; 1717 } 1718 while (*str != '\0' && isspace(Py_CHARMASK(*str))) 1719 str++; 1720 if (base == 0) { 1721 /* No base given. Deduce the base from the contents 1722 of the string */ 1723 if (str[0] != '0') 1724 base = 10; 1725 else if (str[1] == 'x' || str[1] == 'X') 1726 base = 16; 1727 else if (str[1] == 'o' || str[1] == 'O') 1728 base = 8; 1729 else if (str[1] == 'b' || str[1] == 'B') 1730 base = 2; 1731 else 1732 /* "old" (C-style) octal literal, still valid in 1733 2.x, although illegal in 3.x */ 1734 base = 8; 1735 } 1736 /* Whether or not we were deducing the base, skip leading chars 1737 as needed */ 1738 if (str[0] == '0' && 1739 ((base == 16 && (str[1] == 'x' || str[1] == 'X')) || 1740 (base == 8 && (str[1] == 'o' || str[1] == 'O')) || 1741 (base == 2 && (str[1] == 'b' || str[1] == 'B')))) 1742 str += 2; 1743 1744 start = str; 1745 if ((base & (base - 1)) == 0) 1746 z = long_from_binary_base(&str, base); 1747 else { 1748 /*** 1749 Binary bases can be converted in time linear in the number of digits, because 1750 Python's representation base is binary. Other bases (including decimal!) use 1751 the simple quadratic-time algorithm below, complicated by some speed tricks. 1752 1753 First some math: the largest integer that can be expressed in N base-B digits 1754 is B**N-1. Consequently, if we have an N-digit input in base B, the worst- 1755 case number of Python digits needed to hold it is the smallest integer n s.t. 1756 1757 PyLong_BASE**n-1 >= B**N-1 [or, adding 1 to both sides] 1758 PyLong_BASE**n >= B**N [taking logs to base PyLong_BASE] 1759 n >= log(B**N)/log(PyLong_BASE) = N * log(B)/log(PyLong_BASE) 1760 1761 The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so 1762 we can compute this quickly. A Python long with that much space is reserved 1763 near the start, and the result is computed into it. 1764 1765 The input string is actually treated as being in base base**i (i.e., i digits 1766 are processed at a time), where two more static arrays hold: 1767 1768 convwidth_base[base] = the largest integer i such that 1769 base**i <= PyLong_BASE 1770 convmultmax_base[base] = base ** convwidth_base[base] 1771 1772 The first of these is the largest i such that i consecutive input digits 1773 must fit in a single Python digit. The second is effectively the input 1774 base we're really using. 1775 1776 Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base 1777 convmultmax_base[base], the result is "simply" 1778 1779 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1 1780 1781 where B = convmultmax_base[base]. 1782 1783 Error analysis: as above, the number of Python digits `n` needed is worst- 1784 case 1785 1786 n >= N * log(B)/log(PyLong_BASE) 1787 1788 where `N` is the number of input digits in base `B`. This is computed via 1789 1790 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1; 1791 1792 below. Two numeric concerns are how much space this can waste, and whether 1793 the computed result can be too small. To be concrete, assume PyLong_BASE = 1794 2**15, which is the default (and it's unlikely anyone changes that). 1795 1796 Waste isn't a problem: provided the first input digit isn't 0, the difference 1797 between the worst-case input with N digits and the smallest input with N 1798 digits is about a factor of B, but B is small compared to PyLong_BASE so at 1799 most one allocated Python digit can remain unused on that count. If 1800 N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating 1801 that and adding 1 returns a result 1 larger than necessary. However, that 1802 can't happen: whenever B is a power of 2, long_from_binary_base() is called 1803 instead, and it's impossible for B**i to be an integer power of 2**15 when B 1804 is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be 1805 an exact integer when B is not a power of 2, since B**i has a prime factor 1806 other than 2 in that case, but (2**15)**j's only prime factor is 2). 1807 1808 The computed result can be too small if the true value of 1809 N*log(B)/log(PyLong_BASE) is a little bit larger than an exact integer, but 1810 due to roundoff errors (in computing log(B), log(PyLong_BASE), their quotient, 1811 and/or multiplying that by N) yields a numeric result a little less than that 1812 integer. Unfortunately, "how close can a transcendental function get to an 1813 integer over some range?" questions are generally theoretically intractable. 1814 Computer analysis via continued fractions is practical: expand 1815 log(B)/log(PyLong_BASE) via continued fractions, giving a sequence i/j of "the 1816 best" rational approximations. Then j*log(B)/log(PyLong_BASE) is 1817 approximately equal to (the integer) i. This shows that we can get very close 1818 to being in trouble, but very rarely. For example, 76573 is a denominator in 1819 one of the continued-fraction approximations to log(10)/log(2**15), and 1820 indeed: 1821 1822 >>> log(10)/log(2**15)*76573 1823 16958.000000654003 1824 1825 is very close to an integer. If we were working with IEEE single-precision, 1826 rounding errors could kill us. Finding worst cases in IEEE double-precision 1827 requires better-than-double-precision log() functions, and Tim didn't bother. 1828 Instead the code checks to see whether the allocated space is enough as each 1829 new Python digit is added, and copies the whole thing to a larger long if not. 1830 This should happen extremely rarely, and in fact I don't have a test case 1831 that triggers it(!). Instead the code was tested by artificially allocating 1832 just 1 digit at the start, so that the copying code was exercised for every 1833 digit beyond the first. 1834 ***/ 1835 register twodigits c; /* current input character */ 1836 Py_ssize_t size_z; 1837 int i; 1838 int convwidth; 1839 twodigits convmultmax, convmult; 1840 digit *pz, *pzstop; 1841 char* scan; 1842 1843 static double log_base_PyLong_BASE[37] = {0.0e0,}; 1844 static int convwidth_base[37] = {0,}; 1845 static twodigits convmultmax_base[37] = {0,}; 1846 1847 if (log_base_PyLong_BASE[base] == 0.0) { 1848 twodigits convmax = base; 1849 int i = 1; 1850 1851 log_base_PyLong_BASE[base] = (log((double)base) / 1852 log((double)PyLong_BASE)); 1853 for (;;) { 1854 twodigits next = convmax * base; 1855 if (next > PyLong_BASE) 1856 break; 1857 convmax = next; 1858 ++i; 1859 } 1860 convmultmax_base[base] = convmax; 1861 assert(i > 0); 1862 convwidth_base[base] = i; 1863 } 1864 1865 /* Find length of the string of numeric characters. */ 1866 scan = str; 1867 while (_PyLong_DigitValue[Py_CHARMASK(*scan)] < base) 1868 ++scan; 1869 1870 /* Create a long object that can contain the largest possible 1871 * integer with this base and length. Note that there's no 1872 * need to initialize z->ob_digit -- no slot is read up before 1873 * being stored into. 1874 */ 1875 size_z = (Py_ssize_t)((scan - str) * log_base_PyLong_BASE[base]) + 1; 1876 /* Uncomment next line to test exceedingly rare copy code */ 1877 /* size_z = 1; */ 1878 assert(size_z > 0); 1879 z = _PyLong_New(size_z); 1880 if (z == NULL) 1881 return NULL; 1882 Py_SIZE(z) = 0; 1883 1884 /* `convwidth` consecutive input digits are treated as a single 1885 * digit in base `convmultmax`. 1886 */ 1887 convwidth = convwidth_base[base]; 1888 convmultmax = convmultmax_base[base]; 1889 1890 /* Work ;-) */ 1891 while (str < scan) { 1892 /* grab up to convwidth digits from the input string */ 1893 c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)]; 1894 for (i = 1; i < convwidth && str != scan; ++i, ++str) { 1895 c = (twodigits)(c * base + 1896 _PyLong_DigitValue[Py_CHARMASK(*str)]); 1897 assert(c < PyLong_BASE); 1898 } 1899 1900 convmult = convmultmax; 1901 /* Calculate the shift only if we couldn't get 1902 * convwidth digits. 1903 */ 1904 if (i != convwidth) { 1905 convmult = base; 1906 for ( ; i > 1; --i) 1907 convmult *= base; 1908 } 1909 1910 /* Multiply z by convmult, and add c. */ 1911 pz = z->ob_digit; 1912 pzstop = pz + Py_SIZE(z); 1913 for (; pz < pzstop; ++pz) { 1914 c += (twodigits)*pz * convmult; 1915 *pz = (digit)(c & PyLong_MASK); 1916 c >>= PyLong_SHIFT; 1917 } 1918 /* carry off the current end? */ 1919 if (c) { 1920 assert(c < PyLong_BASE); 1921 if (Py_SIZE(z) < size_z) { 1922 *pz = (digit)c; 1923 ++Py_SIZE(z); 1924 } 1925 else { 1926 PyLongObject *tmp; 1927 /* Extremely rare. Get more space. */ 1928 assert(Py_SIZE(z) == size_z); 1929 tmp = _PyLong_New(size_z + 1); 1930 if (tmp == NULL) { 1931 Py_DECREF(z); 1932 return NULL; 1933 } 1934 memcpy(tmp->ob_digit, 1935 z->ob_digit, 1936 sizeof(digit) * size_z); 1937 Py_DECREF(z); 1938 z = tmp; 1939 z->ob_digit[size_z] = (digit)c; 1940 ++size_z; 1941 } 1942 } 1943 } 1944 } 1945 if (z == NULL) 1946 return NULL; 1947 if (str == start) 1948 goto onError; 1949 if (sign < 0) 1950 Py_SIZE(z) = -(Py_SIZE(z)); 1951 if (*str == 'L' || *str == 'l') 1952 str++; 1953 while (*str && isspace(Py_CHARMASK(*str))) 1954 str++; 1955 if (*str != '\0') 1956 goto onError; 1957 if (pend) 1958 *pend = str; 1959 return (PyObject *) z; 1960 1961 onError: 1962 Py_XDECREF(z); 1963 slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200; 1964 strobj = PyString_FromStringAndSize(orig_str, slen); 1965 if (strobj == NULL) 1966 return NULL; 1967 strrepr = PyObject_Repr(strobj); 1968 Py_DECREF(strobj); 1969 if (strrepr == NULL) 1970 return NULL; 1971 PyErr_Format(PyExc_ValueError, 1972 "invalid literal for long() with base %d: %s", 1973 base, PyString_AS_STRING(strrepr)); 1974 Py_DECREF(strrepr); 1975 return NULL; 1976 } 1977 1978 #ifdef Py_USING_UNICODE 1979 PyObject * 1980 PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base) 1981 { 1982 PyObject *result; 1983 char *buffer = (char *)PyMem_MALLOC(length+1); 1984 1985 if (buffer == NULL) 1986 return NULL; 1987 1988 if (PyUnicode_EncodeDecimal(u, length, buffer, NULL)) { 1989 PyMem_FREE(buffer); 1990 return NULL; 1991 } 1992 result = PyLong_FromString(buffer, NULL, base); 1993 PyMem_FREE(buffer); 1994 return result; 1995 } 1996 #endif 1997 1998 /* forward */ 1999 static PyLongObject *x_divrem 2000 (PyLongObject *, PyLongObject *, PyLongObject **); 2001 static PyObject *long_long(PyObject *v); 2002 2003 /* Long division with remainder, top-level routine */ 2004 2005 static int 2006 long_divrem(PyLongObject *a, PyLongObject *b, 2007 PyLongObject **pdiv, PyLongObject **prem) 2008 { 2009 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b)); 2010 PyLongObject *z; 2011 2012 if (size_b == 0) { 2013 PyErr_SetString(PyExc_ZeroDivisionError, 2014 "long division or modulo by zero"); 2015 return -1; 2016 } 2017 if (size_a < size_b || 2018 (size_a == size_b && 2019 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) { 2020 /* |a| < |b|. */ 2021 *pdiv = _PyLong_New(0); 2022 if (*pdiv == NULL) 2023 return -1; 2024 Py_INCREF(a); 2025 *prem = (PyLongObject *) a; 2026 return 0; 2027 } 2028 if (size_b == 1) { 2029 digit rem = 0; 2030 z = divrem1(a, b->ob_digit[0], &rem); 2031 if (z == NULL) 2032 return -1; 2033 *prem = (PyLongObject *) PyLong_FromLong((long)rem); 2034 if (*prem == NULL) { 2035 Py_DECREF(z); 2036 return -1; 2037 } 2038 } 2039 else { 2040 z = x_divrem(a, b, prem); 2041 if (z == NULL) 2042 return -1; 2043 } 2044 /* Set the signs. 2045 The quotient z has the sign of a*b; 2046 the remainder r has the sign of a, 2047 so a = b*z + r. */ 2048 if ((a->ob_size < 0) != (b->ob_size < 0)) 2049 z->ob_size = -(z->ob_size); 2050 if (a->ob_size < 0 && (*prem)->ob_size != 0) 2051 (*prem)->ob_size = -((*prem)->ob_size); 2052 *pdiv = z; 2053 return 0; 2054 } 2055 2056 /* Unsigned long division with remainder -- the algorithm. The arguments v1 2057 and w1 should satisfy 2 <= ABS(Py_SIZE(w1)) <= ABS(Py_SIZE(v1)). */ 2058 2059 static PyLongObject * 2060 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem) 2061 { 2062 PyLongObject *v, *w, *a; 2063 Py_ssize_t i, k, size_v, size_w; 2064 int d; 2065 digit wm1, wm2, carry, q, r, vtop, *v0, *vk, *w0, *ak; 2066 twodigits vv; 2067 sdigit zhi; 2068 stwodigits z; 2069 2070 /* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd 2071 edn.), section 4.3.1, Algorithm D], except that we don't explicitly 2072 handle the special case when the initial estimate q for a quotient 2073 digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and 2074 that won't overflow a digit. */ 2075 2076 /* allocate space; w will also be used to hold the final remainder */ 2077 size_v = ABS(Py_SIZE(v1)); 2078 size_w = ABS(Py_SIZE(w1)); 2079 assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */ 2080 v = _PyLong_New(size_v+1); 2081 if (v == NULL) { 2082 *prem = NULL; 2083 return NULL; 2084 } 2085 w = _PyLong_New(size_w); 2086 if (w == NULL) { 2087 Py_DECREF(v); 2088 *prem = NULL; 2089 return NULL; 2090 } 2091 2092 /* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2. 2093 shift v1 left by the same amount. Results go into w and v. */ 2094 d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]); 2095 carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
Value stored to 'carry' is never read
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

2096 assert(carry == 0); 2097 carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d); 2098 if (carry != 0 || v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) { 2099 v->ob_digit[size_v] = carry; 2100 size_v++; 2101 } 2102 2103 /* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has 2104 at most (and usually exactly) k = size_v - size_w digits. */ 2105 k = size_v - size_w; 2106 assert(k >= 0); 2107 a = _PyLong_New(k); 2108 if (a == NULL) { 2109 Py_DECREF(w); 2110 Py_DECREF(v); 2111 *prem = NULL; 2112 return NULL; 2113 } 2114 v0 = v->ob_digit; 2115 w0 = w->ob_digit; 2116 wm1 = w0[size_w-1]; 2117 wm2 = w0[size_w-2]; 2118 for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) { 2119 /* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving 2120 single-digit quotient q, remainder in vk[0:size_w]. */ 2121 2122 SIGCHECK({ 2123 Py_DECREF(a); 2124 Py_DECREF(w); 2125 Py_DECREF(v); 2126 *prem = NULL; 2127 return NULL; 2128 }); 2129 2130 /* estimate quotient digit q; may overestimate by 1 (rare) */ 2131 vtop = vk[size_w]; 2132 assert(vtop <= wm1); 2133 vv = ((twodigits)vtop << PyLong_SHIFT) | vk[size_w-1]; 2134 q = (digit)(vv / wm1); 2135 r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */ 2136 while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT) 2137 | vk[size_w-2])) { 2138 --q; 2139 r += wm1; 2140 if (r >= PyLong_BASE) 2141 break; 2142 } 2143 assert(q <= PyLong_BASE); 2144 2145 /* subtract q*w0[0:size_w] from vk[0:size_w+1] */ 2146 zhi = 0; 2147 for (i = 0; i < size_w; ++i) { 2148 /* invariants: -PyLong_BASE <= -q <= zhi <= 0; 2149 -PyLong_BASE * q <= z < PyLong_BASE */ 2150 z = (sdigit)vk[i] + zhi - 2151 (stwodigits)q * (stwodigits)w0[i]; 2152 vk[i] = (digit)z & PyLong_MASK; 2153 zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits, 2154 z, PyLong_SHIFT); 2155 } 2156 2157 /* add w back if q was too large (this branch taken rarely) */ 2158 assert((sdigit)vtop + zhi == -1 || (sdigit)vtop + zhi == 0); 2159 if ((sdigit)vtop + zhi < 0) { 2160 carry = 0; 2161 for (i = 0; i < size_w; ++i) { 2162 carry += vk[i] + w0[i]; 2163 vk[i] = carry & PyLong_MASK; 2164 carry >>= PyLong_SHIFT; 2165 } 2166 --q; 2167 } 2168 2169 /* store quotient digit */ 2170 assert(q < PyLong_BASE); 2171 *--ak = q; 2172 } 2173 2174 /* unshift remainder; we reuse w to store the result */ 2175 carry = v_rshift(w0, v0, size_w, d);
Value stored to 'carry' is never read
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

2176 assert(carry==0); 2177 Py_DECREF(v); 2178 2179 *prem = long_normalize(w); 2180 return long_normalize(a); 2181 } 2182 2183 /* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <= 2184 abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is 2185 rounded to DBL_MANT_DIG significant bits using round-half-to-even. 2186 If a == 0, return 0.0 and set *e = 0. If the resulting exponent 2187 e is larger than PY_SSIZE_T_MAX, raise OverflowError and return 2188 -1.0. */ 2189 2190 /* attempt to define 2.0**DBL_MANT_DIG as a compile-time constant */ 2191 #if DBL_MANT_DIG == 53 2192 #define EXP2_DBL_MANT_DIG 9007199254740992.0 2193 #else 2194 #define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG)) 2195 #endif 2196 2197 double 2198 _PyLong_Frexp(PyLongObject *a, Py_ssize_t *e) 2199 { 2200 Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size; 2201 /* See below for why x_digits is always large enough. */ 2202 digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT]; 2203 double dx; 2204 /* Correction term for round-half-to-even rounding. For a digit x, 2205 "x + half_even_correction[x & 7]" gives x rounded to the nearest 2206 multiple of 4, rounding ties to a multiple of 8. */ 2207 static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1}; 2208 2209 a_size = ABS(Py_SIZE(a)); 2210 if (a_size == 0) { 2211 /* Special case for 0: significand 0.0, exponent 0. */ 2212 *e = 0; 2213 return 0.0; 2214 } 2215 a_bits = bits_in_digit(a->ob_digit[a_size-1]); 2216 /* The following is an overflow-free version of the check 2217 "if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */ 2218 if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 && 2219 (a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 || 2220 a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1)) 2221 goto overflow; 2222 a_bits = (a_size - 1) * PyLong_SHIFT + a_bits; 2223 2224 /* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size] 2225 (shifting left if a_bits <= DBL_MANT_DIG + 2). 2226 2227 Number of digits needed for result: write // for floor division. 2228 Then if shifting left, we end up using 2229 2230 1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT 2231 2232 digits. If shifting right, we use 2233 2234 a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT 2235 2236 digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with 2237 the inequalities 2238 2239 m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT 2240 m // PyLong_SHIFT - n // PyLong_SHIFT <= 2241 1 + (m - n - 1) // PyLong_SHIFT, 2242 2243 valid for any integers m and n, we find that x_size satisfies 2244 2245 x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT 2246 2247 in both cases. 2248 */ 2249 if (a_bits <= DBL_MANT_DIG + 2) { 2250 shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT; 2251 shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT; 2252 x_size = 0; 2253 while (x_size < shift_digits) 2254 x_digits[x_size++] = 0; 2255 rem = v_lshift(x_digits + x_size, a->ob_digit, a_size, 2256 (int)shift_bits); 2257 x_size += a_size; 2258 x_digits[x_size++] = rem; 2259 } 2260 else { 2261 shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT; 2262 shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT; 2263 rem = v_rshift(x_digits, a->ob_digit + shift_digits, 2264 a_size - shift_digits, (int)shift_bits); 2265 x_size = a_size - shift_digits; 2266 /* For correct rounding below, we need the least significant 2267 bit of x to be 'sticky' for this shift: if any of the bits 2268 shifted out was nonzero, we set the least significant bit 2269 of x. */ 2270 if (rem) 2271 x_digits[0] |= 1; 2272 else 2273 while (shift_digits > 0) 2274 if (a->ob_digit[--shift_digits]) { 2275 x_digits[0] |= 1;
The left expression of the compound assignment is an uninitialized value. The computed value will also be garbage
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

The left expression of the compound assignment is an uninitialized value. The computed value will also be garbage
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

2276 break; 2277 } 2278 } 2279 assert(1 <= x_size && 2280 x_size <= (Py_ssize_t)(sizeof(x_digits)/sizeof(digit))); 2281 2282 /* Round, and convert to double. */ 2283 x_digits[0] += half_even_correction[x_digits[0] & 7];
The left operand of '&' is a garbage value
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

The left operand of '&' is a garbage value
(emitted by clang-analyzer)

TODO: a detailed trace is available in the data model (not yet rendered in this report)

2284 dx = x_digits[--x_size]; 2285 while (x_size > 0) 2286 dx = dx * PyLong_BASE + x_digits[--x_size]; 2287 2288 /* Rescale; make correction if result is 1.0. */ 2289 dx /= 4.0 * EXP2_DBL_MANT_DIG; 2290 if (dx == 1.0) { 2291 if (a_bits == PY_SSIZE_T_MAX) 2292 goto overflow; 2293 dx = 0.5; 2294 a_bits += 1; 2295 } 2296 2297 *e = a_bits; 2298 return Py_SIZE(a) < 0 ? -dx : dx; 2299 2300 overflow: 2301 /* exponent > PY_SSIZE_T_MAX */ 2302 PyErr_SetString(PyExc_OverflowError, 2303 "huge integer: number of bits overflows a Py_ssize_t"); 2304 *e = 0; 2305 return -1.0; 2306 } 2307 2308 /* Get a C double from a long int object. Rounds to the nearest double, 2309 using the round-half-to-even rule in the case of a tie. */ 2310 2311 double 2312 PyLong_AsDouble(PyObject *v) 2313 { 2314 Py_ssize_t exponent; 2315 double x; 2316 2317 if (v == NULL || !PyLong_Check(v)) { 2318 PyErr_BadInternalCall(); 2319 return -1.0; 2320 } 2321 x = _PyLong_Frexp((PyLongObject *)v, &exponent); 2322 if ((x == -1.0 && PyErr_Occurred()) || exponent > DBL_MAX_EXP) { 2323 PyErr_SetString(PyExc_OverflowError, 2324 "long int too large to convert to float"); 2325 return -1.0; 2326 } 2327 return ldexp(x, (int)exponent); 2328 } 2329 2330 /* Methods */ 2331 2332 static void 2333 long_dealloc(PyObject *v) 2334 { 2335 Py_TYPE(v)->tp_free(v); 2336 } 2337 2338 static PyObject * 2339 long_repr(PyObject *v) 2340 { 2341 return _PyLong_Format(v, 10, 1, 0); 2342 } 2343 2344 static PyObject * 2345 long_str(PyObject *v) 2346 { 2347 return _PyLong_Format(v, 10, 0, 0); 2348 } 2349 2350 static int 2351 long_compare(PyLongObject *a, PyLongObject *b) 2352 { 2353 Py_ssize_t sign; 2354 2355 if (Py_SIZE(a) != Py_SIZE(b)) { 2356 sign = Py_SIZE(a) - Py_SIZE(b); 2357 } 2358 else { 2359 Py_ssize_t i = ABS(Py_SIZE(a)); 2360 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 2361 ; 2362 if (i < 0) 2363 sign = 0; 2364 else { 2365 sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i]; 2366 if (Py_SIZE(a) < 0) 2367 sign = -sign; 2368 } 2369 } 2370 return sign < 0 ? -1 : sign > 0 ? 1 : 0; 2371 } 2372 2373 static long 2374 long_hash(PyLongObject *v) 2375 { 2376 unsigned long x; 2377 Py_ssize_t i; 2378 int sign; 2379 2380 /* This is designed so that Python ints and longs with the 2381 same value hash to the same value, otherwise comparisons 2382 of mapping keys will turn out weird */ 2383 i = v->ob_size; 2384 sign = 1; 2385 x = 0; 2386 if (i < 0) { 2387 sign = -1; 2388 i = -(i); 2389 } 2390 /* The following loop produces a C unsigned long x such that x is 2391 congruent to the absolute value of v modulo ULONG_MAX. The 2392 resulting x is nonzero if and only if v is. */ 2393 while (--i >= 0) { 2394 /* Force a native long #-bits (32 or 64) circular shift */ 2395 x = (x >> (8*SIZEOF_LONG-PyLong_SHIFT)) | (x << PyLong_SHIFT); 2396 x += v->ob_digit[i]; 2397 /* If the addition above overflowed we compensate by 2398 incrementing. This preserves the value modulo 2399 ULONG_MAX. */ 2400 if (x < v->ob_digit[i]) 2401 x++; 2402 } 2403 x = x * sign; 2404 if (x == (unsigned long)-1) 2405 x = (unsigned long)-2; 2406 return (long)x; 2407 } 2408 2409 2410 /* Add the absolute values of two long integers. */ 2411 2412 static PyLongObject * 2413 x_add(PyLongObject *a, PyLongObject *b) 2414 { 2415 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b)); 2416 PyLongObject *z; 2417 Py_ssize_t i; 2418 digit carry = 0; 2419 2420 /* Ensure a is the larger of the two: */ 2421 if (size_a < size_b) { 2422 { PyLongObject *temp = a; a = b; b = temp; } 2423 { Py_ssize_t size_temp = size_a; 2424 size_a = size_b; 2425 size_b = size_temp; } 2426 } 2427 z = _PyLong_New(size_a+1); 2428 if (z == NULL) 2429 return NULL; 2430 for (i = 0; i < size_b; ++i) { 2431 carry += a->ob_digit[i] + b->ob_digit[i]; 2432 z->ob_digit[i] = carry & PyLong_MASK; 2433 carry >>= PyLong_SHIFT; 2434 } 2435 for (; i < size_a; ++i) { 2436 carry += a->ob_digit[i]; 2437 z->ob_digit[i] = carry & PyLong_MASK; 2438 carry >>= PyLong_SHIFT; 2439 } 2440 z->ob_digit[i] = carry; 2441 return long_normalize(z); 2442 } 2443 2444 /* Subtract the absolute values of two integers. */ 2445 2446 static PyLongObject * 2447 x_sub(PyLongObject *a, PyLongObject *b) 2448 { 2449 Py_ssize_t size_a = ABS(Py_SIZE(a)), size_b = ABS(Py_SIZE(b)); 2450 PyLongObject *z; 2451 Py_ssize_t i; 2452 int sign = 1; 2453 digit borrow = 0; 2454 2455 /* Ensure a is the larger of the two: */ 2456 if (size_a < size_b) { 2457 sign = -1; 2458 { PyLongObject *temp = a; a = b; b = temp; } 2459 { Py_ssize_t size_temp = size_a; 2460 size_a = size_b; 2461 size_b = size_temp; } 2462 } 2463 else if (size_a == size_b) { 2464 /* Find highest digit where a and b differ: */ 2465 i = size_a; 2466 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]) 2467 ; 2468 if (i < 0) 2469 return _PyLong_New(0); 2470 if (a->ob_digit[i] < b->ob_digit[i]) { 2471 sign = -1; 2472 { PyLongObject *temp = a; a = b; b = temp; } 2473 } 2474 size_a = size_b = i+1; 2475 } 2476 z = _PyLong_New(size_a); 2477 if (z == NULL) 2478 return NULL; 2479 for (i = 0; i < size_b; ++i) { 2480 /* The following assumes unsigned arithmetic 2481 works module 2**N for some N>PyLong_SHIFT. */ 2482 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow; 2483 z->ob_digit[i] = borrow & PyLong_MASK; 2484 borrow >>= PyLong_SHIFT; 2485 borrow &= 1; /* Keep only one sign bit */ 2486 } 2487 for (; i < size_a; ++i) { 2488 borrow = a->ob_digit[i] - borrow; 2489 z->ob_digit[i] = borrow & PyLong_MASK; 2490 borrow >>= PyLong_SHIFT; 2491 borrow &= 1; /* Keep only one sign bit */ 2492 } 2493 assert(borrow == 0); 2494 if (sign < 0) 2495 z->ob_size = -(z->ob_size); 2496 return long_normalize(z); 2497 } 2498 2499 static PyObject * 2500 long_add(PyLongObject *v, PyLongObject *w) 2501 { 2502 PyLongObject *a, *b, *z; 2503 2504 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 2505 2506 if (a->ob_size < 0) { 2507 if (b->ob_size < 0) { 2508 z = x_add(a, b); 2509 if (z != NULL && z->ob_size != 0) 2510 z->ob_size = -(z->ob_size); 2511 } 2512 else 2513 z = x_sub(b, a); 2514 } 2515 else { 2516 if (b->ob_size < 0) 2517 z = x_sub(a, b); 2518 else 2519 z = x_add(a, b); 2520 } 2521 Py_DECREF(a); 2522 Py_DECREF(b); 2523 return (PyObject *)z; 2524 } 2525 2526 static PyObject * 2527 long_sub(PyLongObject *v, PyLongObject *w) 2528 { 2529 PyLongObject *a, *b, *z; 2530 2531 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 2532 2533 if (a->ob_size < 0) { 2534 if (b->ob_size < 0) 2535 z = x_sub(a, b); 2536 else 2537 z = x_add(a, b); 2538 if (z != NULL && z->ob_size != 0) 2539 z->ob_size = -(z->ob_size); 2540 } 2541 else { 2542 if (b->ob_size < 0) 2543 z = x_add(a, b); 2544 else 2545 z = x_sub(a, b); 2546 } 2547 Py_DECREF(a); 2548 Py_DECREF(b); 2549 return (PyObject *)z; 2550 } 2551 2552 /* Grade school multiplication, ignoring the signs. 2553 * Returns the absolute value of the product, or NULL if error. 2554 */ 2555 static PyLongObject * 2556 x_mul(PyLongObject *a, PyLongObject *b) 2557 { 2558 PyLongObject *z; 2559 Py_ssize_t size_a = ABS(Py_SIZE(a)); 2560 Py_ssize_t size_b = ABS(Py_SIZE(b)); 2561 Py_ssize_t i; 2562 2563 z = _PyLong_New(size_a + size_b); 2564 if (z == NULL) 2565 return NULL; 2566 2567 memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit)); 2568 if (a == b) { 2569 /* Efficient squaring per HAC, Algorithm 14.16: 2570 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf 2571 * Gives slightly less than a 2x speedup when a == b, 2572 * via exploiting that each entry in the multiplication 2573 * pyramid appears twice (except for the size_a squares). 2574 */ 2575 for (i = 0; i < size_a; ++i) { 2576 twodigits carry; 2577 twodigits f = a->ob_digit[i]; 2578 digit *pz = z->ob_digit + (i << 1); 2579 digit *pa = a->ob_digit + i + 1; 2580 digit *paend = a->ob_digit + size_a; 2581 2582 SIGCHECK({ 2583 Py_DECREF(z); 2584 return NULL; 2585 }); 2586 2587 carry = *pz + f * f; 2588 *pz++ = (digit)(carry & PyLong_MASK); 2589 carry >>= PyLong_SHIFT; 2590 assert(carry <= PyLong_MASK); 2591 2592 /* Now f is added in twice in each column of the 2593 * pyramid it appears. Same as adding f<<1 once. 2594 */ 2595 f <<= 1; 2596 while (pa < paend) { 2597 carry += *pz + *pa++ * f; 2598 *pz++ = (digit)(carry & PyLong_MASK); 2599 carry >>= PyLong_SHIFT; 2600 assert(carry <= (PyLong_MASK << 1)); 2601 } 2602 if (carry) { 2603 carry += *pz; 2604 *pz++ = (digit)(carry & PyLong_MASK); 2605 carry >>= PyLong_SHIFT; 2606 } 2607 if (carry) 2608 *pz += (digit)(carry & PyLong_MASK); 2609 assert((carry >> PyLong_SHIFT) == 0); 2610 } 2611 } 2612 else { /* a is not the same as b -- gradeschool long mult */ 2613 for (i = 0; i < size_a; ++i) { 2614 twodigits carry = 0; 2615 twodigits f = a->ob_digit[i]; 2616 digit *pz = z->ob_digit + i; 2617 digit *pb = b->ob_digit; 2618 digit *pbend = b->ob_digit + size_b; 2619 2620 SIGCHECK({ 2621 Py_DECREF(z); 2622 return NULL; 2623 }); 2624 2625 while (pb < pbend) { 2626 carry += *pz + *pb++ * f; 2627 *pz++ = (digit)(carry & PyLong_MASK); 2628 carry >>= PyLong_SHIFT; 2629 assert(carry <= PyLong_MASK); 2630 } 2631 if (carry) 2632 *pz += (digit)(carry & PyLong_MASK); 2633 assert((carry >> PyLong_SHIFT) == 0); 2634 } 2635 } 2636 return long_normalize(z); 2637 } 2638 2639 /* A helper for Karatsuba multiplication (k_mul). 2640 Takes a long "n" and an integer "size" representing the place to 2641 split, and sets low and high such that abs(n) == (high << size) + low, 2642 viewing the shift as being by digits. The sign bit is ignored, and 2643 the return values are >= 0. 2644 Returns 0 on success, -1 on failure. 2645 */ 2646 static int 2647 kmul_split(PyLongObject *n, 2648 Py_ssize_t size, 2649 PyLongObject **high, 2650 PyLongObject **low) 2651 { 2652 PyLongObject *hi, *lo; 2653 Py_ssize_t size_lo, size_hi; 2654 const Py_ssize_t size_n = ABS(Py_SIZE(n)); 2655 2656 size_lo = MIN(size_n, size); 2657 size_hi = size_n - size_lo; 2658 2659 if ((hi = _PyLong_New(size_hi)) == NULL) 2660 return -1; 2661 if ((lo = _PyLong_New(size_lo)) == NULL) { 2662 Py_DECREF(hi); 2663 return -1; 2664 } 2665 2666 memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit)); 2667 memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit)); 2668 2669 *high = long_normalize(hi); 2670 *low = long_normalize(lo); 2671 return 0; 2672 } 2673 2674 static PyLongObject *k_lopsided_mul(PyLongObject *a, PyLongObject *b); 2675 2676 /* Karatsuba multiplication. Ignores the input signs, and returns the 2677 * absolute value of the product (or NULL if error). 2678 * See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295). 2679 */ 2680 static PyLongObject * 2681 k_mul(PyLongObject *a, PyLongObject *b) 2682 { 2683 Py_ssize_t asize = ABS(Py_SIZE(a)); 2684 Py_ssize_t bsize = ABS(Py_SIZE(b)); 2685 PyLongObject *ah = NULL; 2686 PyLongObject *al = NULL; 2687 PyLongObject *bh = NULL; 2688 PyLongObject *bl = NULL; 2689 PyLongObject *ret = NULL; 2690 PyLongObject *t1, *t2, *t3; 2691 Py_ssize_t shift; /* the number of digits we split off */ 2692 Py_ssize_t i; 2693 2694 /* (ah*X+al)(bh*X+bl) = ah*bh*X*X + (ah*bl + al*bh)*X + al*bl 2695 * Let k = (ah+al)*(bh+bl) = ah*bl + al*bh + ah*bh + al*bl 2696 * Then the original product is 2697 * ah*bh*X*X + (k - ah*bh - al*bl)*X + al*bl 2698 * By picking X to be a power of 2, "*X" is just shifting, and it's 2699 * been reduced to 3 multiplies on numbers half the size. 2700 */ 2701 2702 /* We want to split based on the larger number; fiddle so that b 2703 * is largest. 2704 */ 2705 if (asize > bsize) { 2706 t1 = a; 2707 a = b; 2708 b = t1; 2709 2710 i = asize; 2711 asize = bsize; 2712 bsize = i; 2713 } 2714 2715 /* Use gradeschool math when either number is too small. */ 2716 i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF; 2717 if (asize <= i) { 2718 if (asize == 0) 2719 return _PyLong_New(0); 2720 else 2721 return x_mul(a, b); 2722 } 2723 2724 /* If a is small compared to b, splitting on b gives a degenerate 2725 * case with ah==0, and Karatsuba may be (even much) less efficient 2726 * than "grade school" then. However, we can still win, by viewing 2727 * b as a string of "big digits", each of width a->ob_size. That 2728 * leads to a sequence of balanced calls to k_mul. 2729 */ 2730 if (2 * asize <= bsize) 2731 return k_lopsided_mul(a, b); 2732 2733 /* Split a & b into hi & lo pieces. */ 2734 shift = bsize >> 1; 2735 if (kmul_split(a, shift, &ah, &al) < 0) goto fail; 2736 assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */ 2737 2738 if (a == b) { 2739 bh = ah; 2740 bl = al; 2741 Py_INCREF(bh); 2742 Py_INCREF(bl); 2743 } 2744 else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail; 2745 2746 /* The plan: 2747 * 1. Allocate result space (asize + bsize digits: that's always 2748 * enough). 2749 * 2. Compute ah*bh, and copy into result at 2*shift. 2750 * 3. Compute al*bl, and copy into result at 0. Note that this 2751 * can't overlap with #2. 2752 * 4. Subtract al*bl from the result, starting at shift. This may 2753 * underflow (borrow out of the high digit), but we don't care: 2754 * we're effectively doing unsigned arithmetic mod 2755 * PyLong_BASE**(sizea + sizeb), and so long as the *final* result fits, 2756 * borrows and carries out of the high digit can be ignored. 2757 * 5. Subtract ah*bh from the result, starting at shift. 2758 * 6. Compute (ah+al)*(bh+bl), and add it into the result starting 2759 * at shift. 2760 */ 2761 2762 /* 1. Allocate result space. */ 2763 ret = _PyLong_New(asize + bsize); 2764 if (ret == NULL) goto fail; 2765 #ifdef Py_DEBUG 2766 /* Fill with trash, to catch reference to uninitialized digits. */ 2767 memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit)); 2768 #endif 2769 2770 /* 2. t1 <- ah*bh, and copy into high digits of result. */ 2771 if ((t1 = k_mul(ah, bh)) == NULL) goto fail; 2772 assert(Py_SIZE(t1) >= 0); 2773 assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret)); 2774 memcpy(ret->ob_digit + 2*shift, t1->ob_digit, 2775 Py_SIZE(t1) * sizeof(digit)); 2776 2777 /* Zero-out the digits higher than the ah*bh copy. */ 2778 i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1); 2779 if (i) 2780 memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0, 2781 i * sizeof(digit)); 2782 2783 /* 3. t2 <- al*bl, and copy into the low digits. */ 2784 if ((t2 = k_mul(al, bl)) == NULL) { 2785 Py_DECREF(t1); 2786 goto fail; 2787 } 2788 assert(Py_SIZE(t2) >= 0); 2789 assert(Py_SIZE(t2) <= 2*shift); /* no overlap with high digits */ 2790 memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit)); 2791 2792 /* Zero out remaining digits. */ 2793 i = 2*shift - Py_SIZE(t2); /* number of uninitialized digits */ 2794 if (i) 2795 memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit)); 2796 2797 /* 4 & 5. Subtract ah*bh (t1) and al*bl (t2). We do al*bl first 2798 * because it's fresher in cache. 2799 */ 2800 i = Py_SIZE(ret) - shift; /* # digits after shift */ 2801 (void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2)); 2802 Py_DECREF(t2); 2803 2804 (void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1)); 2805 Py_DECREF(t1); 2806 2807 /* 6. t3 <- (ah+al)(bh+bl), and add into result. */ 2808 if ((t1 = x_add(ah, al)) == NULL) goto fail; 2809 Py_DECREF(ah); 2810 Py_DECREF(al); 2811 ah = al = NULL; 2812 2813 if (a == b) { 2814 t2 = t1; 2815 Py_INCREF(t2); 2816 } 2817 else if ((t2 = x_add(bh, bl)) == NULL) { 2818 Py_DECREF(t1); 2819 goto fail; 2820 } 2821 Py_DECREF(bh); 2822 Py_DECREF(bl); 2823 bh = bl = NULL; 2824 2825 t3 = k_mul(t1, t2); 2826 Py_DECREF(t1); 2827 Py_DECREF(t2); 2828 if (t3 == NULL) goto fail; 2829 assert(Py_SIZE(t3) >= 0); 2830 2831 /* Add t3. It's not obvious why we can't run out of room here. 2832 * See the (*) comment after this function. 2833 */ 2834 (void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3)); 2835 Py_DECREF(t3); 2836 2837 return long_normalize(ret); 2838 2839 fail: 2840 Py_XDECREF(ret); 2841 Py_XDECREF(ah); 2842 Py_XDECREF(al); 2843 Py_XDECREF(bh); 2844 Py_XDECREF(bl); 2845 return NULL; 2846 } 2847 2848 /* (*) Why adding t3 can't "run out of room" above. 2849 2850 Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts 2851 to start with: 2852 2853 1. For any integer i, i = c(i/2) + f(i/2). In particular, 2854 bsize = c(bsize/2) + f(bsize/2). 2855 2. shift = f(bsize/2) 2856 3. asize <= bsize 2857 4. Since we call k_lopsided_mul if asize*2 <= bsize, asize*2 > bsize in this 2858 routine, so asize > bsize/2 >= f(bsize/2) in this routine. 2859 2860 We allocated asize + bsize result digits, and add t3 into them at an offset 2861 of shift. This leaves asize+bsize-shift allocated digit positions for t3 2862 to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) = 2863 asize + c(bsize/2) available digit positions. 2864 2865 bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has 2866 at most c(bsize/2) digits + 1 bit. 2867 2868 If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2) 2869 digits, and al has at most f(bsize/2) digits in any case. So ah+al has at 2870 most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit. 2871 2872 The product (ah+al)*(bh+bl) therefore has at most 2873 2874 c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits 2875 2876 and we have asize + c(bsize/2) available digit positions. We need to show 2877 this is always enough. An instance of c(bsize/2) cancels out in both, so 2878 the question reduces to whether asize digits is enough to hold 2879 (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize, 2880 then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4, 2881 asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1 2882 digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If 2883 asize == bsize, then we're asking whether bsize digits is enough to hold 2884 c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits 2885 is enough to hold 2 bits. This is so if bsize >= 2, which holds because 2886 bsize >= KARATSUBA_CUTOFF >= 2. 2887 2888 Note that since there's always enough room for (ah+al)*(bh+bl), and that's 2889 clearly >= each of ah*bh and al*bl, there's always enough room to subtract 2890 ah*bh and al*bl too. 2891 */ 2892 2893 /* b has at least twice the digits of a, and a is big enough that Karatsuba 2894 * would pay off *if* the inputs had balanced sizes. View b as a sequence 2895 * of slices, each with a->ob_size digits, and multiply the slices by a, 2896 * one at a time. This gives k_mul balanced inputs to work with, and is 2897 * also cache-friendly (we compute one double-width slice of the result 2898 * at a time, then move on, never backtracking except for the helpful 2899 * single-width slice overlap between successive partial sums). 2900 */ 2901 static PyLongObject * 2902 k_lopsided_mul(PyLongObject *a, PyLongObject *b) 2903 { 2904 const Py_ssize_t asize = ABS(Py_SIZE(a)); 2905 Py_ssize_t bsize = ABS(Py_SIZE(b)); 2906 Py_ssize_t nbdone; /* # of b digits already multiplied */ 2907 PyLongObject *ret; 2908 PyLongObject *bslice = NULL; 2909 2910 assert(asize > KARATSUBA_CUTOFF); 2911 assert(2 * asize <= bsize); 2912 2913 /* Allocate result space, and zero it out. */ 2914 ret = _PyLong_New(asize + bsize); 2915 if (ret == NULL) 2916 return NULL; 2917 memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit)); 2918 2919 /* Successive slices of b are copied into bslice. */ 2920 bslice = _PyLong_New(asize); 2921 if (bslice == NULL) 2922 goto fail; 2923 2924 nbdone = 0; 2925 while (bsize > 0) { 2926 PyLongObject *product; 2927 const Py_ssize_t nbtouse = MIN(bsize, asize); 2928 2929 /* Multiply the next slice of b by a. */ 2930 memcpy(bslice->ob_digit, b->ob_digit + nbdone, 2931 nbtouse * sizeof(digit)); 2932 Py_SIZE(bslice) = nbtouse; 2933 product = k_mul(a, bslice); 2934 if (product == NULL) 2935 goto fail; 2936 2937 /* Add into result. */ 2938 (void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone, 2939 product->ob_digit, Py_SIZE(product)); 2940 Py_DECREF(product); 2941 2942 bsize -= nbtouse; 2943 nbdone += nbtouse; 2944 } 2945 2946 Py_DECREF(bslice); 2947 return long_normalize(ret); 2948 2949 fail: 2950 Py_DECREF(ret); 2951 Py_XDECREF(bslice); 2952 return NULL; 2953 } 2954 2955 static PyObject * 2956 long_mul(PyLongObject *v, PyLongObject *w) 2957 { 2958 PyLongObject *a, *b, *z; 2959 2960 if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) { 2961 Py_INCREF(Py_NotImplemented); 2962 return Py_NotImplemented; 2963 } 2964 2965 z = k_mul(a, b); 2966 /* Negate if exactly one of the inputs is negative. */ 2967 if (((a->ob_size ^ b->ob_size) < 0) && z) 2968 z->ob_size = -(z->ob_size); 2969 Py_DECREF(a); 2970 Py_DECREF(b); 2971 return (PyObject *)z; 2972 } 2973 2974 /* The / and % operators are now defined in terms of divmod(). 2975 The expression a mod b has the value a - b*floor(a/b). 2976 The long_divrem function gives the remainder after division of 2977 |a| by |b|, with the sign of a. This is also expressed 2978 as a - b*trunc(a/b), if trunc truncates towards zero. 2979 Some examples: 2980 a b a rem b a mod b 2981 13 10 3 3 2982 -13 10 -3 7 2983 13 -10 3 -7 2984 -13 -10 -3 -3 2985 So, to get from rem to mod, we have to add b if a and b 2986 have different signs. We then subtract one from the 'div' 2987 part of the outcome to keep the invariant intact. */ 2988 2989 /* Compute 2990 * *pdiv, *pmod = divmod(v, w) 2991 * NULL can be passed for pdiv or pmod, in which case that part of 2992 * the result is simply thrown away. The caller owns a reference to 2993 * each of these it requests (does not pass NULL for). 2994 */ 2995 static int 2996 l_divmod(PyLongObject *v, PyLongObject *w, 2997 PyLongObject **pdiv, PyLongObject **pmod) 2998 { 2999 PyLongObject *div, *mod; 3000 3001 if (long_divrem(v, w, &div, &mod) < 0) 3002 return -1; 3003 if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) || 3004 (Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) { 3005 PyLongObject *temp; 3006 PyLongObject *one; 3007 temp = (PyLongObject *) long_add(mod, w); 3008 Py_DECREF(mod); 3009 mod = temp; 3010 if (mod == NULL) { 3011 Py_DECREF(div); 3012 return -1; 3013 } 3014 one = (PyLongObject *) PyLong_FromLong(1L); 3015 if (one == NULL || 3016 (temp = (PyLongObject *) long_sub(div, one)) == NULL) { 3017 Py_DECREF(mod); 3018 Py_DECREF(div); 3019 Py_XDECREF(one); 3020 return -1; 3021 } 3022 Py_DECREF(one); 3023 Py_DECREF(div); 3024 div = temp; 3025 } 3026 if (pdiv != NULL) 3027 *pdiv = div; 3028 else 3029 Py_DECREF(div); 3030 3031 if (pmod != NULL) 3032 *pmod = mod; 3033 else 3034 Py_DECREF(mod); 3035 3036 return 0; 3037 } 3038 3039 static PyObject * 3040 long_div(PyObject *v, PyObject *w) 3041 { 3042 PyLongObject *a, *b, *div; 3043 3044 CONVERT_BINOP(v, w, &a, &b); 3045 if (l_divmod(a, b, &div, NULL) < 0) 3046 div = NULL; 3047 Py_DECREF(a); 3048 Py_DECREF(b); 3049 return (PyObject *)div; 3050 } 3051 3052 static PyObject * 3053 long_classic_div(PyObject *v, PyObject *w) 3054 { 3055 PyLongObject *a, *b, *div; 3056 3057 CONVERT_BINOP(v, w, &a, &b); 3058 if (Py_DivisionWarningFlag && 3059 PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0) 3060 div = NULL; 3061 else if (l_divmod(a, b, &div, NULL) < 0) 3062 div = NULL; 3063 Py_DECREF(a); 3064 Py_DECREF(b); 3065 return (PyObject *)div; 3066 } 3067 3068 /* PyLong/PyLong -> float, with correctly rounded result. */ 3069 3070 #define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT) 3071 #define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT) 3072 3073 static PyObject * 3074 long_true_divide(PyObject *v, PyObject *w) 3075 { 3076 PyLongObject *a, *b, *x; 3077 Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits; 3078 digit mask, low; 3079 int inexact, negate, a_is_small, b_is_small; 3080 double dx, result; 3081 3082 CONVERT_BINOP(v, w, &a, &b); 3083 3084 /* 3085 Method in a nutshell: 3086 3087 0. reduce to case a, b > 0; filter out obvious underflow/overflow 3088 1. choose a suitable integer 'shift' 3089 2. use integer arithmetic to compute x = floor(2**-shift*a/b) 3090 3. adjust x for correct rounding 3091 4. convert x to a double dx with the same value 3092 5. return ldexp(dx, shift). 3093 3094 In more detail: 3095 3096 0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b 3097 returns either 0.0 or -0.0, depending on the sign of b. For a and 3098 b both nonzero, ignore signs of a and b, and add the sign back in 3099 at the end. Now write a_bits and b_bits for the bit lengths of a 3100 and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise 3101 for b). Then 3102 3103 2**(a_bits - b_bits - 1) < a/b < 2**(a_bits - b_bits + 1). 3104 3105 So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and 3106 so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP - 3107 DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of 3108 the way, we can assume that 3109 3110 DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP. 3111 3112 1. The integer 'shift' is chosen so that x has the right number of 3113 bits for a double, plus two or three extra bits that will be used 3114 in the rounding decisions. Writing a_bits and b_bits for the 3115 number of significant bits in a and b respectively, a 3116 straightforward formula for shift is: 3117 3118 shift = a_bits - b_bits - DBL_MANT_DIG - 2 3119 3120 This is fine in the usual case, but if a/b is smaller than the 3121 smallest normal float then it can lead to double rounding on an 3122 IEEE 754 platform, giving incorrectly rounded results. So we 3123 adjust the formula slightly. The actual formula used is: 3124 3125 shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2 3126 3127 2. The quantity x is computed by first shifting a (left -shift bits 3128 if shift <= 0, right shift bits if shift > 0) and then dividing by 3129 b. For both the shift and the division, we keep track of whether 3130 the result is inexact, in a flag 'inexact'; this information is 3131 needed at the rounding stage. 3132 3133 With the choice of shift above, together with our assumption that 3134 a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows 3135 that x >= 1. 3136 3137 3. Now x * 2**shift <= a/b < (x+1) * 2**shift. We want to replace 3138 this with an exactly representable float of the form 3139 3140 round(x/2**extra_bits) * 2**(extra_bits+shift). 3141 3142 For float representability, we need x/2**extra_bits < 3143 2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP - 3144 DBL_MANT_DIG. This translates to the condition: 3145 3146 extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG 3147 3148 To round, we just modify the bottom digit of x in-place; this can 3149 end up giving a digit with value > PyLONG_MASK, but that's not a 3150 problem since digits can hold values up to 2*PyLONG_MASK+1. 3151 3152 With the original choices for shift above, extra_bits will always 3153 be 2 or 3. Then rounding under the round-half-to-even rule, we 3154 round up iff the most significant of the extra bits is 1, and 3155 either: (a) the computation of x in step 2 had an inexact result, 3156 or (b) at least one other of the extra bits is 1, or (c) the least 3157 significant bit of x (above those to be rounded) is 1. 3158 3159 4. Conversion to a double is straightforward; all floating-point 3160 operations involved in the conversion are exact, so there's no 3161 danger of rounding errors. 3162 3163 5. Use ldexp(x, shift) to compute x*2**shift, the final result. 3164 The result will always be exactly representable as a double, except 3165 in the case that it overflows. To avoid dependence on the exact 3166 behaviour of ldexp on overflow, we check for overflow before 3167 applying ldexp. The result of ldexp is adjusted for sign before 3168 returning. 3169 */ 3170 3171 /* Reduce to case where a and b are both positive. */ 3172 a_size = ABS(Py_SIZE(a)); 3173 b_size = ABS(Py_SIZE(b)); 3174 negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0); 3175 if (b_size == 0) { 3176 PyErr_SetString(PyExc_ZeroDivisionError, 3177 "division by zero"); 3178 goto error; 3179 } 3180 if (a_size == 0) 3181 goto underflow_or_zero; 3182 3183 /* Fast path for a and b small (exactly representable in a double). 3184 Relies on floating-point division being correctly rounded; results 3185 may be subject to double rounding on x86 machines that operate with 3186 the x87 FPU set to 64-bit precision. */ 3187 a_is_small = a_size <= MANT_DIG_DIGITS || 3188 (a_size == MANT_DIG_DIGITS+1 && 3189 a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0); 3190 b_is_small = b_size <= MANT_DIG_DIGITS || 3191 (b_size == MANT_DIG_DIGITS+1 && 3192 b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0); 3193 if (a_is_small && b_is_small) { 3194 double da, db; 3195 da = a->ob_digit[--a_size]; 3196 while (a_size > 0) 3197 da = da * PyLong_BASE + a->ob_digit[--a_size]; 3198 db = b->ob_digit[--b_size]; 3199 while (b_size > 0) 3200 db = db * PyLong_BASE + b->ob_digit[--b_size]; 3201 result = da / db; 3202 goto success; 3203 } 3204 3205 /* Catch obvious cases of underflow and overflow */ 3206 diff = a_size - b_size; 3207 if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1) 3208 /* Extreme overflow */ 3209 goto overflow; 3210 else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT) 3211 /* Extreme underflow */ 3212 goto underflow_or_zero; 3213 /* Next line is now safe from overflowing a Py_ssize_t */ 3214 diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) - 3215 bits_in_digit(b->ob_digit[b_size - 1]); 3216 /* Now diff = a_bits - b_bits. */ 3217 if (diff > DBL_MAX_EXP) 3218 goto overflow; 3219 else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1) 3220 goto underflow_or_zero; 3221 3222 /* Choose value for shift; see comments for step 1 above. */ 3223 shift = MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2; 3224 3225 inexact = 0; 3226 3227 /* x = abs(a * 2**-shift) */ 3228 if (shift <= 0) { 3229 Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT; 3230 digit rem; 3231 /* x = a << -shift */ 3232 if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) { 3233 /* In practice, it's probably impossible to end up 3234 here. Both a and b would have to be enormous, 3235 using close to SIZE_T_MAX bytes of memory each. */ 3236 PyErr_SetString(PyExc_OverflowError, 3237 "intermediate overflow during division"); 3238 goto error; 3239 } 3240 x = _PyLong_New(a_size + shift_digits + 1); 3241 if (x == NULL) 3242 goto error; 3243 for (i = 0; i < shift_digits; i++) 3244 x->ob_digit[i] = 0; 3245 rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit, 3246 a_size, -shift % PyLong_SHIFT); 3247 x->ob_digit[a_size + shift_digits] = rem; 3248 } 3249 else { 3250 Py_ssize_t shift_digits = shift / PyLong_SHIFT; 3251 digit rem; 3252 /* x = a >> shift */ 3253 assert(a_size >= shift_digits); 3254 x = _PyLong_New(a_size - shift_digits); 3255 if (x == NULL) 3256 goto error; 3257 rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits, 3258 a_size - shift_digits, shift % PyLong_SHIFT); 3259 /* set inexact if any of the bits shifted out is nonzero */ 3260 if (rem) 3261 inexact = 1; 3262 while (!inexact && shift_digits > 0) 3263 if (a->ob_digit[--shift_digits]) 3264 inexact = 1; 3265 } 3266 long_normalize(x); 3267 x_size = Py_SIZE(x); 3268 3269 /* x //= b. If the remainder is nonzero, set inexact. We own the only 3270 reference to x, so it's safe to modify it in-place. */ 3271 if (b_size == 1) { 3272 digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size, 3273 b->ob_digit[0]); 3274 long_normalize(x); 3275 if (rem) 3276 inexact = 1; 3277 } 3278 else { 3279 PyLongObject *div, *rem; 3280 div = x_divrem(x, b, &rem); 3281 Py_DECREF(x); 3282 x = div; 3283 if (x == NULL) 3284 goto error; 3285 if (Py_SIZE(rem)) 3286 inexact = 1; 3287 Py_DECREF(rem); 3288 } 3289 x_size = ABS(Py_SIZE(x)); 3290 assert(x_size > 0); /* result of division is never zero */ 3291 x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]); 3292 3293 /* The number of extra bits that have to be rounded away. */ 3294 extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG; 3295 assert(extra_bits == 2 || extra_bits == 3); 3296 3297 /* Round by directly modifying the low digit of x. */ 3298 mask = (digit)1 << (extra_bits - 1); 3299 low = x->ob_digit[0] | inexact; 3300 if (low & mask && low & (3*mask-1)) 3301 low += mask; 3302 x->ob_digit[0] = low & ~(mask-1U); 3303 3304 /* Convert x to a double dx; the conversion is exact. */ 3305 dx = x->ob_digit[--x_size]; 3306 while (x_size > 0) 3307 dx = dx * PyLong_BASE + x->ob_digit[--x_size]; 3308 Py_DECREF(x); 3309 3310 /* Check whether ldexp result will overflow a double. */ 3311 if (shift + x_bits >= DBL_MAX_EXP && 3312 (shift + x_bits > DBL_MAX_EXP || dx == ldexp(1.0, (int)x_bits))) 3313 goto overflow; 3314 result = ldexp(dx, (int)shift); 3315 3316 success: 3317 Py_DECREF(a); 3318 Py_DECREF(b); 3319 return PyFloat_FromDouble(negate ? -result : result); 3320 3321 underflow_or_zero: 3322 Py_DECREF(a); 3323 Py_DECREF(b); 3324 return PyFloat_FromDouble(negate ? -0.0 : 0.0); 3325 3326 overflow: 3327 PyErr_SetString(PyExc_OverflowError, 3328 "integer division result too large for a float"); 3329 error: 3330 Py_DECREF(a); 3331 Py_DECREF(b); 3332 return NULL; 3333 } 3334 3335 static PyObject * 3336 long_mod(PyObject *v, PyObject *w) 3337 { 3338 PyLongObject *a, *b, *mod; 3339 3340 CONVERT_BINOP(v, w, &a, &b); 3341 3342 if (l_divmod(a, b, NULL, &mod) < 0) 3343 mod = NULL; 3344 Py_DECREF(a); 3345 Py_DECREF(b); 3346 return (PyObject *)mod; 3347 } 3348 3349 static PyObject * 3350 long_divmod(PyObject *v, PyObject *w) 3351 { 3352 PyLongObject *a, *b, *div, *mod; 3353 PyObject *z; 3354 3355 CONVERT_BINOP(v, w, &a, &b); 3356 3357 if (l_divmod(a, b, &div, &mod) < 0) { 3358 Py_DECREF(a); 3359 Py_DECREF(b); 3360 return NULL; 3361 } 3362 z = PyTuple_New(2); 3363 if (z != NULL) { 3364 PyTuple_SetItem(z, 0, (PyObject *) div); 3365 PyTuple_SetItem(z, 1, (PyObject *) mod); 3366 } 3367 else { 3368 Py_DECREF(div); 3369 Py_DECREF(mod); 3370 } 3371 Py_DECREF(a); 3372 Py_DECREF(b); 3373 return z; 3374 } 3375 3376 /* pow(v, w, x) */ 3377 static PyObject * 3378 long_pow(PyObject *v, PyObject *w, PyObject *x) 3379 { 3380 PyLongObject *a, *b, *c; /* a,b,c = v,w,x */ 3381 int negativeOutput = 0; /* if x<0 return negative output */ 3382 3383 PyLongObject *z = NULL; /* accumulated result */ 3384 Py_ssize_t i, j, k; /* counters */ 3385 PyLongObject *temp = NULL; 3386 3387 /* 5-ary values. If the exponent is large enough, table is 3388 * precomputed so that table[i] == a**i % c for i in range(32). 3389 */ 3390 PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 3391 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; 3392 3393 /* a, b, c = v, w, x */ 3394 CONVERT_BINOP(v, w, &a, &b); 3395 if (PyLong_Check(x)) { 3396 c = (PyLongObject *)x; 3397 Py_INCREF(x); 3398 } 3399 else if (PyInt_Check(x)) { 3400 c = (PyLongObject *)PyLong_FromLong(PyInt_AS_LONG(x)); 3401 if (c == NULL) 3402 goto Error; 3403 } 3404 else if (x == Py_None) 3405 c = NULL; 3406 else { 3407 Py_DECREF(a); 3408 Py_DECREF(b); 3409 Py_INCREF(Py_NotImplemented); 3410 return Py_NotImplemented; 3411 } 3412 3413 if (Py_SIZE(b) < 0) { /* if exponent is negative */ 3414 if (c) { 3415 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument " 3416 "cannot be negative when 3rd argument specified"); 3417 goto Error; 3418 } 3419 else { 3420 /* else return a float. This works because we know 3421 that this calls float_pow() which converts its 3422 arguments to double. */ 3423 Py_DECREF(a); 3424 Py_DECREF(b); 3425 return PyFloat_Type.tp_as_number->nb_power(v, w, x); 3426 } 3427 } 3428 3429 if (c) { 3430 /* if modulus == 0: 3431 raise ValueError() */ 3432 if (Py_SIZE(c) == 0) { 3433 PyErr_SetString(PyExc_ValueError, 3434 "pow() 3rd argument cannot be 0"); 3435 goto Error; 3436 } 3437 3438 /* if modulus < 0: 3439 negativeOutput = True 3440 modulus = -modulus */ 3441 if (Py_SIZE(c) < 0) { 3442 negativeOutput = 1; 3443 temp = (PyLongObject *)_PyLong_Copy(c); 3444 if (temp == NULL) 3445 goto Error; 3446 Py_DECREF(c); 3447 c = temp; 3448 temp = NULL; 3449 c->ob_size = - c->ob_size; 3450 } 3451 3452 /* if modulus == 1: 3453 return 0 */ 3454 if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) { 3455 z = (PyLongObject *)PyLong_FromLong(0L); 3456 goto Done; 3457 } 3458 3459 /* if base < 0: 3460 base = base % modulus 3461 Having the base positive just makes things easier. */ 3462 if (Py_SIZE(a) < 0) { 3463 if (l_divmod(a, c, NULL, &temp) < 0) 3464 goto Error; 3465 Py_DECREF(a); 3466 a = temp; 3467 temp = NULL; 3468 } 3469 } 3470 3471 /* At this point a, b, and c are guaranteed non-negative UNLESS 3472 c is NULL, in which case a may be negative. */ 3473 3474 z = (PyLongObject *)PyLong_FromLong(1L); 3475 if (z == NULL) 3476 goto Error; 3477 3478 /* Perform a modular reduction, X = X % c, but leave X alone if c 3479 * is NULL. 3480 */ 3481 #define REDUCE(X) \ 3482 do { \ 3483 if (c != NULL) { \ 3484 if (l_divmod(X, c, NULL, &temp) < 0) \ 3485 goto Error; \ 3486 Py_XDECREF(X); \ 3487 X = temp; \ 3488 temp = NULL; \ 3489 } \ 3490 } while(0) 3491 3492 /* Multiply two values, then reduce the result: 3493 result = X*Y % c. If c is NULL, skip the mod. */ 3494 #define MULT(X, Y, result) \ 3495 do { \ 3496 temp = (PyLongObject *)long_mul(X, Y); \ 3497 if (temp == NULL) \ 3498 goto Error; \ 3499 Py_XDECREF(result); \ 3500 result = temp; \ 3501 temp = NULL; \ 3502 REDUCE(result); \ 3503 } while(0) 3504 3505 if (Py_SIZE(b) <= FIVEARY_CUTOFF) { 3506 /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */ 3507 /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */ 3508 for (i = Py_SIZE(b) - 1; i >= 0; --i) { 3509 digit bi = b->ob_digit[i]; 3510 3511 for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) { 3512 MULT(z, z, z); 3513 if (bi & j) 3514 MULT(z, a, z); 3515 } 3516 } 3517 } 3518 else { 3519 /* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */ 3520 Py_INCREF(z); /* still holds 1L */ 3521 table[0] = z; 3522 for (i = 1; i < 32; ++i) 3523 MULT(table[i-1], a, table[i]); 3524 3525 for (i = Py_SIZE(b) - 1; i >= 0; --i) { 3526 const digit bi = b->ob_digit[i]; 3527 3528 for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) { 3529 const int index = (bi >> j) & 0x1f; 3530 for (k = 0; k < 5; ++k) 3531 MULT(z, z, z); 3532 if (index) 3533 MULT(z, table[index], z); 3534 } 3535 } 3536 } 3537 3538 if (negativeOutput && (Py_SIZE(z) != 0)) { 3539 temp = (PyLongObject *)long_sub(z, c); 3540 if (temp == NULL) 3541 goto Error; 3542 Py_DECREF(z); 3543 z = temp; 3544 temp = NULL; 3545 } 3546 goto Done; 3547 3548 Error: 3549 if (z != NULL) { 3550 Py_DECREF(z); 3551 z = NULL; 3552 } 3553 /* fall through */ 3554 Done: 3555 if (Py_SIZE(b) > FIVEARY_CUTOFF) { 3556 for (i = 0; i < 32; ++i) 3557 Py_XDECREF(table[i]); 3558 } 3559 Py_DECREF(a); 3560 Py_DECREF(b); 3561 Py_XDECREF(c); 3562 Py_XDECREF(temp); 3563 return (PyObject *)z; 3564 } 3565 3566 static PyObject * 3567 long_invert(PyLongObject *v) 3568 { 3569 /* Implement ~x as -(x+1) */ 3570 PyLongObject *x; 3571 PyLongObject *w; 3572 w = (PyLongObject *)PyLong_FromLong(1L); 3573 if (w == NULL) 3574 return NULL; 3575 x = (PyLongObject *) long_add(v, w); 3576 Py_DECREF(w); 3577 if (x == NULL) 3578 return NULL; 3579 Py_SIZE(x) = -(Py_SIZE(x)); 3580 return (PyObject *)x; 3581 } 3582 3583 static PyObject * 3584 long_neg(PyLongObject *v) 3585 { 3586 PyLongObject *z; 3587 if (v->ob_size == 0 && PyLong_CheckExact(v)) { 3588 /* -0 == 0 */ 3589 Py_INCREF(v); 3590 return (PyObject *) v; 3591 } 3592 z = (PyLongObject *)_PyLong_Copy(v); 3593 if (z != NULL) 3594 z->ob_size = -(v->ob_size); 3595 return (PyObject *)z; 3596 } 3597 3598 static PyObject * 3599 long_abs(PyLongObject *v) 3600 { 3601 if (v->ob_size < 0) 3602 return long_neg(v); 3603 else 3604 return long_long((PyObject *)v); 3605 } 3606 3607 static int 3608 long_nonzero(PyLongObject *v) 3609 { 3610 return Py_SIZE(v) != 0; 3611 } 3612 3613 static PyObject * 3614 long_rshift(PyLongObject *v, PyLongObject *w) 3615 { 3616 PyLongObject *a, *b; 3617 PyLongObject *z = NULL; 3618 Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j; 3619 digit lomask, himask; 3620 3621 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b); 3622 3623 if (Py_SIZE(a) < 0) { 3624 /* Right shifting negative numbers is harder */ 3625 PyLongObject *a1, *a2; 3626 a1 = (PyLongObject *) long_invert(a); 3627 if (a1 == NULL) 3628 goto rshift_error; 3629 a2 = (PyLongObject *) long_rshift(a1, b); 3630 Py_DECREF(a1); 3631 if (a2 == NULL) 3632 goto rshift_error; 3633 z = (PyLongObject *) long_invert(a2); 3634 Py_DECREF(a2); 3635 } 3636 else { 3637 shiftby = PyLong_AsSsize_t((PyObject *)b); 3638 if (shiftby == -1L && PyErr_Occurred()) 3639 goto rshift_error; 3640 if (shiftby < 0) { 3641 PyErr_SetString(PyExc_ValueError, 3642 "negative shift count"); 3643 goto rshift_error; 3644 } 3645 wordshift = shiftby / PyLong_SHIFT; 3646 newsize = ABS(Py_SIZE(a)) - wordshift; 3647 if (newsize <= 0) { 3648 z = _PyLong_New(0); 3649 Py_DECREF(a); 3650 Py_DECREF(b); 3651 return (PyObject *)z; 3652 } 3653 loshift = shiftby % PyLong_SHIFT; 3654 hishift = PyLong_SHIFT - loshift; 3655 lomask = ((digit)1 << hishift) - 1; 3656 himask = PyLong_MASK ^ lomask; 3657 z = _PyLong_New(newsize); 3658 if (z == NULL) 3659 goto rshift_error; 3660 if (Py_SIZE(a) < 0) 3661 Py_SIZE(z) = -(Py_SIZE(z)); 3662 for (i = 0, j = wordshift; i < newsize; i++, j++) { 3663 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask; 3664 if (i+1 < newsize) 3665 z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask; 3666 } 3667 z = long_normalize(z); 3668 } 3669 rshift_error: 3670 Py_DECREF(a); 3671 Py_DECREF(b); 3672 return (PyObject *) z; 3673 3674 } 3675 3676 static PyObject * 3677 long_lshift(PyObject *v, PyObject *w) 3678 { 3679 /* This version due to Tim Peters */ 3680 PyLongObject *a, *b; 3681 PyLongObject *z = NULL; 3682 Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j; 3683 twodigits accum; 3684 3685 CONVERT_BINOP(v, w, &a, &b); 3686 3687 shiftby = PyLong_AsSsize_t((PyObject *)b); 3688 if (shiftby == -1L && PyErr_Occurred()) 3689 goto lshift_error; 3690 if (shiftby < 0) { 3691 PyErr_SetString(PyExc_ValueError, "negative shift count"); 3692 goto lshift_error; 3693 } 3694 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */ 3695 wordshift = shiftby / PyLong_SHIFT; 3696 remshift = shiftby - wordshift * PyLong_SHIFT; 3697 3698 oldsize = ABS(a->ob_size); 3699 newsize = oldsize + wordshift; 3700 if (remshift) 3701 ++newsize; 3702 z = _PyLong_New(newsize); 3703 if (z == NULL) 3704 goto lshift_error; 3705 if (a->ob_size < 0) 3706 z->ob_size = -(z->ob_size); 3707 for (i = 0; i < wordshift; i++) 3708 z->ob_digit[i] = 0; 3709 accum = 0; 3710 for (i = wordshift, j = 0; j < oldsize; i++, j++) { 3711 accum |= (twodigits)a->ob_digit[j] << remshift; 3712 z->ob_digit[i] = (digit)(accum & PyLong_MASK); 3713 accum >>= PyLong_SHIFT; 3714 } 3715 if (remshift) 3716 z->ob_digit[newsize-1] = (digit)accum; 3717 else 3718 assert(!accum); 3719 z = long_normalize(z); 3720 lshift_error: 3721 Py_DECREF(a); 3722 Py_DECREF(b); 3723 return (PyObject *) z; 3724 } 3725 3726 /* Compute two's complement of digit vector a[0:m], writing result to 3727 z[0:m]. The digit vector a need not be normalized, but should not 3728 be entirely zero. a and z may point to the same digit vector. */ 3729 3730 static void 3731 v_complement(digit *z, digit *a, Py_ssize_t m) 3732 { 3733 Py_ssize_t i; 3734 digit carry = 1; 3735 for (i = 0; i < m; ++i) { 3736 carry += a[i] ^ PyLong_MASK; 3737 z[i] = carry & PyLong_MASK; 3738 carry >>= PyLong_SHIFT; 3739 } 3740 assert(carry == 0); 3741 } 3742 3743 /* Bitwise and/xor/or operations */ 3744 3745 static PyObject * 3746 long_bitwise(PyLongObject *a, 3747 int op, /* '&', '|', '^' */ 3748 PyLongObject *b) 3749 { 3750 int nega, negb, negz; 3751 Py_ssize_t size_a, size_b, size_z, i; 3752 PyLongObject *z; 3753 3754 /* Bitwise operations for negative numbers operate as though 3755 on a two's complement representation. So convert arguments 3756 from sign-magnitude to two's complement, and convert the 3757 result back to sign-magnitude at the end. */ 3758 3759 /* If a is negative, replace it by its two's complement. */ 3760 size_a = ABS(Py_SIZE(a)); 3761 nega = Py_SIZE(a) < 0; 3762 if (nega) { 3763 z = _PyLong_New(size_a); 3764 if (z == NULL) 3765 return NULL; 3766 v_complement(z->ob_digit, a->ob_digit, size_a); 3767 a = z; 3768 } 3769 else 3770 /* Keep reference count consistent. */ 3771 Py_INCREF(a); 3772 3773 /* Same for b. */ 3774 size_b = ABS(Py_SIZE(b)); 3775 negb = Py_SIZE(b) < 0; 3776 if (negb) { 3777 z = _PyLong_New(size_b); 3778 if (z == NULL) { 3779 Py_DECREF(a); 3780 return NULL; 3781 } 3782 v_complement(z->ob_digit, b->ob_digit, size_b); 3783 b = z; 3784 } 3785 else 3786 Py_INCREF(b); 3787 3788 /* Swap a and b if necessary to ensure size_a >= size_b. */ 3789 if (size_a < size_b) { 3790 z = a; a = b; b = z; 3791 size_z = size_a; size_a = size_b; size_b = size_z; 3792 negz = nega; nega = negb; negb = negz; 3793 } 3794 3795 /* JRH: The original logic here was to allocate the result value (z) 3796 as the longer of the two operands. However, there are some cases 3797 where the result is guaranteed to be shorter than that: AND of two 3798 positives, OR of two negatives: use the shorter number. AND with 3799 mixed signs: use the positive number. OR with mixed signs: use the 3800 negative number. 3801 */ 3802 switch (op) { 3803 case '^': 3804 negz = nega ^ negb; 3805 size_z = size_a; 3806 break; 3807 case '&': 3808 negz = nega & negb; 3809 size_z = negb ? size_a : size_b; 3810 break; 3811 case '|': 3812 negz = nega | negb; 3813 size_z = negb ? size_b : size_a; 3814 break; 3815 default: 3816 PyErr_BadArgument(); 3817 return NULL; 3818 } 3819 3820 /* We allow an extra digit if z is negative, to make sure that 3821 the final two's complement of z doesn't overflow. */ 3822 z = _PyLong_New(size_z + negz); 3823 if (z == NULL) { 3824 Py_DECREF(a); 3825 Py_DECREF(b); 3826 return NULL; 3827 } 3828 3829 /* Compute digits for overlap of a and b. */ 3830 switch(op) { 3831 case '&': 3832 for (i = 0; i < size_b; ++i) 3833 z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i]; 3834 break; 3835 case '|': 3836 for (i = 0; i < size_b; ++i) 3837 z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i]; 3838 break; 3839 case '^': 3840 for (i = 0; i < size_b; ++i) 3841 z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i]; 3842 break; 3843 default: 3844 PyErr_BadArgument(); 3845 return NULL; 3846 } 3847 3848 /* Copy any remaining digits of a, inverting if necessary. */ 3849 if (op == '^' && negb) 3850 for (; i < size_z; ++i) 3851 z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK; 3852 else if (i < size_z) 3853 memcpy(&z->ob_digit[i], &a->ob_digit[i], 3854 (size_z-i)*sizeof(digit)); 3855 3856 /* Complement result if negative. */ 3857 if (negz) { 3858 Py_SIZE(z) = -(Py_SIZE(z)); 3859 z->ob_digit[size_z] = PyLong_MASK; 3860 v_complement(z->ob_digit, z->ob_digit, size_z+1); 3861 } 3862 3863 Py_DECREF(a); 3864 Py_DECREF(b); 3865 return (PyObject *)long_normalize(z); 3866 } 3867 3868 static PyObject * 3869 long_and(PyObject *v, PyObject *w) 3870 { 3871 PyLongObject *a, *b; 3872 PyObject *c; 3873 CONVERT_BINOP(v, w, &a, &b); 3874 c = long_bitwise(a, '&', b); 3875 Py_DECREF(a); 3876 Py_DECREF(b); 3877 return c; 3878 } 3879 3880 static PyObject * 3881 long_xor(PyObject *v, PyObject *w) 3882 { 3883 PyLongObject *a, *b; 3884 PyObject *c; 3885 CONVERT_BINOP(v, w, &a, &b); 3886 c = long_bitwise(a, '^', b); 3887 Py_DECREF(a); 3888 Py_DECREF(b); 3889 return c; 3890 } 3891 3892 static PyObject * 3893 long_or(PyObject *v, PyObject *w) 3894 { 3895 PyLongObject *a, *b; 3896 PyObject *c; 3897 CONVERT_BINOP(v, w, &a, &b); 3898 c = long_bitwise(a, '|', b); 3899 Py_DECREF(a); 3900 Py_DECREF(b); 3901 return c; 3902 } 3903 3904 static int 3905 long_coerce(PyObject **pv, PyObject **pw) 3906 { 3907 if (PyInt_Check(*pw)) { 3908 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw)); 3909 if (*pw == NULL) 3910 return -1; 3911 Py_INCREF(*pv); 3912 return 0; 3913 } 3914 else if (PyLong_Check(*pw)) { 3915 Py_INCREF(*pv); 3916 Py_INCREF(*pw); 3917 return 0; 3918 } 3919 return 1; /* Can't do it */ 3920 } 3921 3922 static PyObject * 3923 long_long(PyObject *v) 3924 { 3925 if (PyLong_CheckExact(v)) 3926 Py_INCREF(v); 3927 else 3928 v = _PyLong_Copy((PyLongObject *)v); 3929 return v; 3930 } 3931 3932 static PyObject * 3933 long_int(PyObject *v) 3934 { 3935 long x; 3936 x = PyLong_AsLong(v); 3937 if (PyErr_Occurred()) { 3938 if (PyErr_ExceptionMatches(PyExc_OverflowError)) { 3939 PyErr_Clear(); 3940 if (PyLong_CheckExact(v)) { 3941 Py_INCREF(v); 3942 return v; 3943 } 3944 else 3945 return _PyLong_Copy((PyLongObject *)v); 3946 } 3947 else 3948 return NULL; 3949 } 3950 return PyInt_FromLong(x); 3951 } 3952 3953 static PyObject * 3954 long_float(PyObject *v) 3955 { 3956 double result; 3957 result = PyLong_AsDouble(v); 3958 if (result == -1.0 && PyErr_Occurred()) 3959 return NULL; 3960 return PyFloat_FromDouble(result); 3961 } 3962 3963 static PyObject * 3964 long_oct(PyObject *v) 3965 { 3966 return _PyLong_Format(v, 8, 1, 0); 3967 } 3968 3969 static PyObject * 3970 long_hex(PyObject *v) 3971 { 3972 return _PyLong_Format(v, 16, 1, 0); 3973 } 3974 3975 static PyObject * 3976 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds); 3977 3978 static PyObject * 3979 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 3980 { 3981 PyObject *x = NULL; 3982 int base = -909; /* unlikely! */ 3983 static char *kwlist[] = {"x", "base", 0}; 3984 3985 if (type != &PyLong_Type) 3986 return long_subtype_new(type, args, kwds); /* Wimp out */ 3987 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist, 3988 &x, &base)) 3989 return NULL; 3990 if (x == NULL) 3991 return PyLong_FromLong(0L); 3992 if (base == -909) 3993 return PyNumber_Long(x); 3994 else if (PyString_Check(x)) { 3995 /* Since PyLong_FromString doesn't have a length parameter, 3996 * check here for possible NULs in the string. */ 3997 char *string = PyString_AS_STRING(x); 3998 if (strlen(string) != (size_t)PyString_Size(x)) { 3999 /* create a repr() of the input string, 4000 * just like PyLong_FromString does. */ 4001 PyObject *srepr; 4002 srepr = PyObject_Repr(x); 4003 if (srepr == NULL) 4004 return NULL; 4005 PyErr_Format(PyExc_ValueError, 4006 "invalid literal for long() with base %d: %s", 4007 base, PyString_AS_STRING(srepr)); 4008 Py_DECREF(srepr); 4009 return NULL; 4010 } 4011 return PyLong_FromString(PyString_AS_STRING(x), NULL, base); 4012 } 4013 #ifdef Py_USING_UNICODE 4014 else if (PyUnicode_Check(x)) 4015 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x), 4016 PyUnicode_GET_SIZE(x), 4017 base); 4018 #endif 4019 else { 4020 PyErr_SetString(PyExc_TypeError, 4021 "long() can't convert non-string with explicit base"); 4022 return NULL; 4023 } 4024 } 4025 4026 /* Wimpy, slow approach to tp_new calls for subtypes of long: 4027 first create a regular long from whatever arguments we got, 4028 then allocate a subtype instance and initialize it from 4029 the regular long. The regular long is then thrown away. 4030 */ 4031 static PyObject * 4032 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 4033 { 4034 PyLongObject *tmp, *newobj; 4035 Py_ssize_t i, n; 4036 4037 assert(PyType_IsSubtype(type, &PyLong_Type)); 4038 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds); 4039 if (tmp == NULL) 4040 return NULL; 4041 assert(PyLong_CheckExact(tmp)); 4042 n = Py_SIZE(tmp); 4043 if (n < 0) 4044 n = -n; 4045 newobj = (PyLongObject *)type->tp_alloc(type, n); 4046 if (newobj == NULL) { 4047 Py_DECREF(tmp); 4048 return NULL; 4049 } 4050 assert(PyLong_Check(newobj)); 4051 Py_SIZE(newobj) = Py_SIZE(tmp); 4052 for (i = 0; i < n; i++) 4053 newobj->ob_digit[i] = tmp->ob_digit[i]; 4054 Py_DECREF(tmp); 4055 return (PyObject *)newobj; 4056 } 4057 4058 static PyObject * 4059 long_getnewargs(PyLongObject *v) 4060 { 4061 return Py_BuildValue("(N)", _PyLong_Copy(v)); 4062 } 4063 4064 static PyObject * 4065 long_get0(PyLongObject *v, void *context) { 4066 return PyLong_FromLong(0L); 4067 } 4068 4069 static PyObject * 4070 long_get1(PyLongObject *v, void *context) { 4071 return PyLong_FromLong(1L); 4072 } 4073 4074 static PyObject * 4075 long__format__(PyObject *self, PyObject *args) 4076 { 4077 PyObject *format_spec; 4078 4079 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec)) 4080 return NULL; 4081 if (PyBytes_Check(format_spec)) 4082 return _PyLong_FormatAdvanced(self, 4083 PyBytes_AS_STRING(format_spec), 4084 PyBytes_GET_SIZE(format_spec)); 4085 if (PyUnicode_Check(format_spec)) { 4086 /* Convert format_spec to a str */ 4087 PyObject *result; 4088 PyObject *str_spec = PyObject_Str(format_spec); 4089 4090 if (str_spec == NULL) 4091 return NULL; 4092 4093 result = _PyLong_FormatAdvanced(self, 4094 PyBytes_AS_STRING(str_spec), 4095 PyBytes_GET_SIZE(str_spec)); 4096 4097 Py_DECREF(str_spec); 4098 return result; 4099 } 4100 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode"); 4101 return NULL; 4102 } 4103 4104 static PyObject * 4105 long_sizeof(PyLongObject *v) 4106 { 4107 Py_ssize_t res; 4108 4109 res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit); 4110 return PyInt_FromSsize_t(res); 4111 } 4112 4113 static PyObject * 4114 long_bit_length(PyLongObject *v) 4115 { 4116 PyLongObject *result, *x, *y; 4117 Py_ssize_t ndigits, msd_bits = 0; 4118 digit msd; 4119 4120 assert(v != NULL); 4121 assert(PyLong_Check(v)); 4122 4123 ndigits = ABS(Py_SIZE(v)); 4124 if (ndigits == 0) 4125 return PyInt_FromLong(0); 4126 4127 msd = v->ob_digit[ndigits-1]; 4128 while (msd >= 32) { 4129 msd_bits += 6; 4130 msd >>= 6; 4131 } 4132 msd_bits += (long)(BitLengthTable[msd]); 4133 4134 if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT) 4135 return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits); 4136 4137 /* expression above may overflow; use Python integers instead */ 4138 result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1); 4139 if (result == NULL) 4140 return NULL; 4141 x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT); 4142 if (x == NULL) 4143 goto error; 4144 y = (PyLongObject *)long_mul(result, x); 4145 Py_DECREF(x); 4146 if (y == NULL) 4147 goto error; 4148 Py_DECREF(result); 4149 result = y; 4150 4151 x = (PyLongObject *)PyLong_FromLong((long)msd_bits); 4152 if (x == NULL) 4153 goto error; 4154 y = (PyLongObject *)long_add(result, x); 4155 Py_DECREF(x); 4156 if (y == NULL) 4157 goto error; 4158 Py_DECREF(result); 4159 result = y; 4160 4161 return (PyObject *)result; 4162 4163 error: 4164 Py_DECREF(result); 4165 return NULL; 4166 } 4167 4168 PyDoc_STRVAR(long_bit_length_doc, 4169 "long.bit_length() -> int or long\n\ 4170 \n\ 4171 Number of bits necessary to represent self in binary.\n\ 4172 >>> bin(37L)\n\ 4173 '0b100101'\n\ 4174 >>> (37L).bit_length()\n\ 4175 6"); 4176 4177 #if 0 4178 static PyObject * 4179 long_is_finite(PyObject *v) 4180 { 4181 Py_RETURN_TRUE; 4182 } 4183 #endif 4184 4185 static PyMethodDef long_methods[] = { 4186 {"conjugate", (PyCFunction)long_long, METH_NOARGS, 4187 "Returns self, the complex conjugate of any long."}, 4188 {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS, 4189 long_bit_length_doc}, 4190 #if 0 4191 {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS, 4192 "Returns always True."}, 4193 #endif 4194 {"__trunc__", (PyCFunction)long_long, METH_NOARGS, 4195 "Truncating an Integral returns itself."}, 4196 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS}, 4197 {"__format__", (PyCFunction)long__format__, METH_VARARGS}, 4198 {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS, 4199 "Returns size in memory, in bytes"}, 4200 {NULL, NULL} /* sentinel */ 4201 }; 4202 4203 static PyGetSetDef long_getset[] = { 4204 {"real", 4205 (getter)long_long, (setter)NULL, 4206 "the real part of a complex number", 4207 NULL}, 4208 {"imag", 4209 (getter)long_get0, (setter)NULL, 4210 "the imaginary part of a complex number", 4211 NULL}, 4212 {"numerator", 4213 (getter)long_long, (setter)NULL, 4214 "the numerator of a rational number in lowest terms", 4215 NULL}, 4216 {"denominator", 4217 (getter)long_get1, (setter)NULL, 4218 "the denominator of a rational number in lowest terms", 4219 NULL}, 4220 {NULL} /* Sentinel */ 4221 }; 4222 4223 PyDoc_STRVAR(long_doc, 4224 "long(x[, base]) -> integer\n\ 4225 \n\ 4226 Convert a string or number to a long integer, if possible. A floating\n\ 4227 point argument will be truncated towards zero (this does not include a\n\ 4228 string representation of a floating point number!) When converting a\n\ 4229 string, use the optional base. It is an error to supply a base when\n\ 4230 converting a non-string."); 4231 4232 static PyNumberMethods long_as_number = { 4233 (binaryfunc)long_add, /*nb_add*/ 4234 (binaryfunc)long_sub, /*nb_subtract*/ 4235 (binaryfunc)long_mul, /*nb_multiply*/ 4236 long_classic_div, /*nb_divide*/ 4237 long_mod, /*nb_remainder*/ 4238 long_divmod, /*nb_divmod*/ 4239 long_pow, /*nb_power*/ 4240 (unaryfunc)long_neg, /*nb_negative*/ 4241 (unaryfunc)long_long, /*tp_positive*/ 4242 (unaryfunc)long_abs, /*tp_absolute*/ 4243 (inquiry)long_nonzero, /*tp_nonzero*/ 4244 (unaryfunc)long_invert, /*nb_invert*/ 4245 long_lshift, /*nb_lshift*/ 4246 (binaryfunc)long_rshift, /*nb_rshift*/ 4247 long_and, /*nb_and*/ 4248 long_xor, /*nb_xor*/ 4249 long_or, /*nb_or*/ 4250 long_coerce, /*nb_coerce*/ 4251 long_int, /*nb_int*/ 4252 long_long, /*nb_long*/ 4253 long_float, /*nb_float*/ 4254 long_oct, /*nb_oct*/ 4255 long_hex, /*nb_hex*/ 4256 0, /* nb_inplace_add */ 4257 0, /* nb_inplace_subtract */ 4258 0, /* nb_inplace_multiply */ 4259 0, /* nb_inplace_divide */ 4260 0, /* nb_inplace_remainder */ 4261 0, /* nb_inplace_power */ 4262 0, /* nb_inplace_lshift */ 4263 0, /* nb_inplace_rshift */ 4264 0, /* nb_inplace_and */ 4265 0, /* nb_inplace_xor */ 4266 0, /* nb_inplace_or */ 4267 long_div, /* nb_floor_divide */ 4268 long_true_divide, /* nb_true_divide */ 4269 0, /* nb_inplace_floor_divide */ 4270 0, /* nb_inplace_true_divide */ 4271 long_long, /* nb_index */ 4272 }; 4273 4274 PyTypeObject PyLong_Type = { 4275 PyObject_HEAD_INIT(&PyType_Type) 4276 0, /* ob_size */ 4277 "long", /* tp_name */ 4278 offsetof(PyLongObject, ob_digit), /* tp_basicsize */ 4279 sizeof(digit), /* tp_itemsize */ 4280 long_dealloc, /* tp_dealloc */ 4281 0, /* tp_print */ 4282 0, /* tp_getattr */ 4283 0, /* tp_setattr */ 4284 (cmpfunc)long_compare, /* tp_compare */ 4285 long_repr, /* tp_repr */ 4286 &long_as_number, /* tp_as_number */ 4287 0, /* tp_as_sequence */ 4288 0, /* tp_as_mapping */ 4289 (hashfunc)long_hash, /* tp_hash */ 4290 0, /* tp_call */ 4291 long_str, /* tp_str */ 4292 PyObject_GenericGetAttr, /* tp_getattro */ 4293 0, /* tp_setattro */ 4294 0, /* tp_as_buffer */ 4295 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES | 4296 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */ 4297 long_doc, /* tp_doc */ 4298 0, /* tp_traverse */ 4299 0, /* tp_clear */ 4300 0, /* tp_richcompare */ 4301 0, /* tp_weaklistoffset */ 4302 0, /* tp_iter */ 4303 0, /* tp_iternext */ 4304 long_methods, /* tp_methods */ 4305 0, /* tp_members */ 4306 long_getset, /* tp_getset */ 4307 0, /* tp_base */ 4308 0, /* tp_dict */ 4309 0, /* tp_descr_get */ 4310 0, /* tp_descr_set */ 4311 0, /* tp_dictoffset */ 4312 0, /* tp_init */ 4313 0, /* tp_alloc */ 4314 long_new, /* tp_new */ 4315 PyObject_Del, /* tp_free */ 4316 }; 4317 4318 static PyTypeObject Long_InfoType; 4319 4320 PyDoc_STRVAR(long_info__doc__, 4321 "sys.long_info\n\ 4322 \n\ 4323 A struct sequence that holds information about Python's\n\ 4324 internal representation of integers. The attributes are read only."); 4325 4326 static PyStructSequence_Field long_info_fields[] = { 4327 {"bits_per_digit", "size of a digit in bits"}, 4328 {"sizeof_digit", "size in bytes of the C type used to represent a digit"}, 4329 {NULL, NULL} 4330 }; 4331 4332 static PyStructSequence_Desc long_info_desc = { 4333 "sys.long_info", /* name */ 4334 long_info__doc__, /* doc */ 4335 long_info_fields, /* fields */ 4336 2 /* number of fields */ 4337 }; 4338 4339 PyObject * 4340 PyLong_GetInfo(void) 4341 { 4342 PyObject* long_info; 4343 int field = 0; 4344 long_info = PyStructSequence_New(&Long_InfoType); 4345 if (long_info == NULL) 4346 return NULL; 4347 PyStructSequence_SET_ITEM(long_info, field++, 4348 PyInt_FromLong(PyLong_SHIFT)); 4349 PyStructSequence_SET_ITEM(long_info, field++, 4350 PyInt_FromLong(sizeof(digit))); 4351 if (PyErr_Occurred()) { 4352 Py_CLEAR(long_info); 4353 return NULL; 4354 } 4355 return long_info; 4356 } 4357 4358 int 4359 _PyLong_Init(void) 4360 { 4361 /* initialize long_info */ 4362 if (Long_InfoType.tp_name == 0) 4363 PyStructSequence_InitType(&Long_InfoType, &long_info_desc); 4364 return 1; 4365 }