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