longobject.c revision 89446b2c91b664a851874b43a295859c8383343d
176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* Long (arbitrary precision) integer object implementation */ 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* XXX The functional organization of this file is terrible */ 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "Python.h" 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "longintrepr.h" 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include "structseq.h" 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <float.h> 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <ctype.h> 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stddef.h> 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* For long multiplication, use the O(N**2) school algorithm unless 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * both operands contain more than KARATSUBA_CUTOFF digits (this 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * being an internal Python long digit, in base PyLong_BASE). 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define KARATSUBA_CUTOFF 70 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF) 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* For exponentiation, use the binary left-to-right algorithm 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * unless the exponent contains more than FIVEARY_CUTOFF digits. 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * In that case, do 5 bits at a time. The potential drawback is that 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * a table of 2**5 intermediate results is computed. 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define FIVEARY_CUTOFF 8 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define ABS(x) ((x) < 0 ? -(x) : (x)) 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#undef MIN 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#undef MAX 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define MAX(x, y) ((x) < (y) ? (y) : (x)) 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define MIN(x, y) ((x) > (y) ? (y) : (x)) 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define SIGCHECK(PyTryBlock) \ 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do { \ 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (--_Py_Ticker < 0) { \ 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman _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 46static PyLongObject * 47long_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 65PyLongObject * 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 79PyObject * 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 100PyObject * 101PyLong_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 144PyObject * 145PyLong_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 171PyObject * 172PyLong_FromDouble(double dval) 173{ 174 PyLongObject *v; 175 double frac; 176 int i, ndig, expo, neg; 177 neg = 0; 178 if (Py_IS_INFINITY(dval)) { 179 PyErr_SetString(PyExc_OverflowError, 180 "cannot convert float infinity to integer"); 181 return NULL; 182 } 183 if (Py_IS_NAN(dval)) { 184 PyErr_SetString(PyExc_ValueError, 185 "cannot convert float NaN to integer"); 186 return NULL; 187 } 188 if (dval < 0.0) { 189 neg = 1; 190 dval = -dval; 191 } 192 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */ 193 if (expo <= 0) 194 return PyLong_FromLong(0L); 195 ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */ 196 v = _PyLong_New(ndig); 197 if (v == NULL) 198 return NULL; 199 frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1); 200 for (i = ndig; --i >= 0; ) { 201 digit bits = (digit)frac; 202 v->ob_digit[i] = bits; 203 frac = frac - (double)bits; 204 frac = ldexp(frac, PyLong_SHIFT); 205 } 206 if (neg) 207 Py_SIZE(v) = -(Py_SIZE(v)); 208 return (PyObject *)v; 209} 210 211/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define 212 * anything about what happens when a signed integer operation overflows, 213 * and some compilers think they're doing you a favor by being "clever" 214 * then. The bit pattern for the largest postive signed long is 215 * (unsigned long)LONG_MAX, and for the smallest negative signed long 216 * it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN. 217 * However, some other compilers warn about applying unary minus to an 218 * unsigned operand. Hence the weird "0-". 219 */ 220#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN) 221#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN) 222 223/* Get a C long int from a Python long or Python int object. 224 On overflow, returns -1 and sets *overflow to 1 or -1 depending 225 on the sign of the result. Otherwise *overflow is 0. 226 227 For other errors (e.g., type error), returns -1 and sets an error 228 condition. 229*/ 230 231long 232PyLong_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 328long 329PyLong_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 345int 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 363Py_ssize_t 364PyLong_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 408unsigned long 409PyLong_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 452unsigned long 453PyLong_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 480int 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 491size_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 523PyObject * 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 634int 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 769PyObject * 770PyLong_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 794void * 795PyLong_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@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 845PyObject * 846PyLong_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 888PyObject * 889PyLong_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 915PyObject * 916PyLong_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 926PyObject * 927PyLong_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 938PY_LONG_LONG 939PyLong_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 990unsigned PY_LONG_LONG 991PyLong_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 1015unsigned PY_LONG_LONG 1016PyLong_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 1049PY_LONG_LONG 1050PyLong_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 1148static int 1149convert_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 1185static 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 1190static int 1191bits_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 */ 1206static digit 1207v_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 */ 1232static digit 1233v_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 */ 1257static digit 1258v_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 */ 1275static digit 1276v_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 1297static digit 1298inplace_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 1318static PyLongObject * 1319divrem1(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 1336static PyObject * 1337long_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" */ 1454PyAPI_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 */ 1629int _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 */ 1654static PyLongObject * 1655long_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 1714PyObject * 1715PyLong_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/*** 1767Binary bases can be converted in time linear in the number of digits, because 1768Python's representation base is binary. Other bases (including decimal!) use 1769the simple quadratic-time algorithm below, complicated by some speed tricks. 1770 1771First some math: the largest integer that can be expressed in N base-B digits 1772is B**N-1. Consequently, if we have an N-digit input in base B, the worst- 1773case 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 1779The static array log_base_PyLong_BASE[base] == log(base)/log(PyLong_BASE) so 1780we can compute this quickly. A Python long with that much space is reserved 1781near the start, and the result is computed into it. 1782 1783The input string is actually treated as being in base base**i (i.e., i digits 1784are 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 1790The first of these is the largest i such that i consecutive input digits 1791must fit in a single Python digit. The second is effectively the input 1792base we're really using. 1793 1794Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base 1795convmultmax_base[base], the result is "simply" 1796 1797 (((c0*B + c1)*B + c2)*B + c3)*B + ... ))) + c_n-1 1798 1799where B = convmultmax_base[base]. 1800 1801Error analysis: as above, the number of Python digits `n` needed is worst- 1802case 1803 1804 n >= N * log(B)/log(PyLong_BASE) 1805 1806where `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 1810below. Two numeric concerns are how much space this can waste, and whether 1811the computed result can be too small. To be concrete, assume PyLong_BASE = 18122**15, which is the default (and it's unlikely anyone changes that). 1813 1814Waste isn't a problem: provided the first input digit isn't 0, the difference 1815between the worst-case input with N digits and the smallest input with N 1816digits is about a factor of B, but B is small compared to PyLong_BASE so at 1817most one allocated Python digit can remain unused on that count. If 1818N*log(B)/log(PyLong_BASE) is mathematically an exact integer, then truncating 1819that and adding 1 returns a result 1 larger than necessary. However, that 1820can't happen: whenever B is a power of 2, long_from_binary_base() is called 1821instead, and it's impossible for B**i to be an integer power of 2**15 when B 1822is not a power of 2 (i.e., it's impossible for N*log(B)/log(PyLong_BASE) to be 1823an exact integer when B is not a power of 2, since B**i has a prime factor 1824other than 2 in that case, but (2**15)**j's only prime factor is 2). 1825 1826The computed result can be too small if the true value of 1827N*log(B)/log(PyLong_BASE) is a little bit larger than an exact integer, but 1828due to roundoff errors (in computing log(B), log(PyLong_BASE), their quotient, 1829and/or multiplying that by N) yields a numeric result a little less than that 1830integer. Unfortunately, "how close can a transcendental function get to an 1831integer over some range?" questions are generally theoretically intractable. 1832Computer analysis via continued fractions is practical: expand 1833log(B)/log(PyLong_BASE) via continued fractions, giving a sequence i/j of "the 1834best" rational approximations. Then j*log(B)/log(PyLong_BASE) is 1835approximately equal to (the integer) i. This shows that we can get very close 1836to being in trouble, but very rarely. For example, 76573 is a denominator in 1837one of the continued-fraction approximations to log(10)/log(2**15), and 1838indeed: 1839 1840 >>> log(10)/log(2**15)*76573 1841 16958.000000654003 1842 1843is very close to an integer. If we were working with IEEE single-precision, 1844rounding errors could kill us. Finding worst cases in IEEE double-precision 1845requires better-than-double-precision log() functions, and Tim didn't bother. 1846Instead the code checks to see whether the allocated space is enough as each 1847new Python digit is added, and copies the whole thing to a larger long if not. 1848This should happen extremely rarely, and in fact I don't have a test case 1849that triggers it(!). Instead the code was tested by artificially allocating 1850just 1 digit at the start, so that the copying code was exercised for every 1851digit 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 1997PyObject * 1998PyLong_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 */ 2017static PyLongObject *x_divrem 2018 (PyLongObject *, PyLongObject *, PyLongObject **); 2019static PyObject *long_long(PyObject *v); 2020 2021/* Long division with remainder, top-level routine */ 2022 2023static int 2024long_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 2077static PyLongObject * 2078x_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 2215double 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 2329double 2330PyLong_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 2350static void 2351long_dealloc(PyObject *v) 2352{ 2353 Py_TYPE(v)->tp_free(v); 2354} 2355 2356static PyObject * 2357long_repr(PyObject *v) 2358{ 2359 return _PyLong_Format(v, 10, 1, 0); 2360} 2361 2362static PyObject * 2363long_str(PyObject *v) 2364{ 2365 return _PyLong_Format(v, 10, 0, 0); 2366} 2367 2368static int 2369long_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 2391static long 2392long_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 2430static PyLongObject * 2431x_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 2464static PyLongObject * 2465x_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 2517static PyObject * 2518long_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 2544static PyObject * 2545long_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 */ 2573static PyLongObject * 2574x_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*/ 2664static int 2665kmul_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 2692static 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 */ 2698static PyLongObject * 2699k_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 2868Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts 2869to start with: 2870 28711. For any integer i, i = c(i/2) + f(i/2). In particular, 2872 bsize = c(bsize/2) + f(bsize/2). 28732. shift = f(bsize/2) 28743. asize <= bsize 28754. 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 2878We allocated asize + bsize result digits, and add t3 into them at an offset 2879of shift. This leaves asize+bsize-shift allocated digit positions for t3 2880to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) = 2881asize + c(bsize/2) available digit positions. 2882 2883bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has 2884at most c(bsize/2) digits + 1 bit. 2885 2886If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2) 2887digits, and al has at most f(bsize/2) digits in any case. So ah+al has at 2888most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit. 2889 2890The 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 2894and we have asize + c(bsize/2) available digit positions. We need to show 2895this is always enough. An instance of c(bsize/2) cancels out in both, so 2896the 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, 2898then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4, 2899asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1 2900digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If 2901asize == bsize, then we're asking whether bsize digits is enough to hold 2902c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits 2903is enough to hold 2 bits. This is so if bsize >= 2, which holds because 2904bsize >= KARATSUBA_CUTOFF >= 2. 2905 2906Note that since there's always enough room for (ah+al)*(bh+bl), and that's 2907clearly >= each of ah*bh and al*bl, there's always enough room to subtract 2908ah*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 */ 2919static PyLongObject * 2920k_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 2973static PyObject * 2974long_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 */ 3013static int 3014l_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 3057static PyObject * 3058long_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 3070static PyObject * 3071long_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 3091static PyObject * 3092long_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 3353static PyObject * 3354long_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 3367static PyObject * 3368long_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) */ 3395static PyObject * 3396long_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 3590static PyObject * 3591long_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 3607static PyObject * 3608long_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 3622static PyObject * 3623long_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 3631static int 3632long_nonzero(PyLongObject *v) 3633{ 3634 return Py_SIZE(v) != 0; 3635} 3636 3637static PyObject * 3638long_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 3700static PyObject * 3701long_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 lshift_error; 3714 if (shiftby < 0) { 3715 PyErr_SetString(PyExc_ValueError, "negative shift count"); 3716 goto lshift_error; 3717 } 3718 /* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */ 3719 wordshift = shiftby / PyLong_SHIFT; 3720 remshift = shiftby - wordshift * PyLong_SHIFT; 3721 3722 oldsize = ABS(a->ob_size); 3723 newsize = oldsize + wordshift; 3724 if (remshift) 3725 ++newsize; 3726 z = _PyLong_New(newsize); 3727 if (z == NULL) 3728 goto lshift_error; 3729 if (a->ob_size < 0) 3730 z->ob_size = -(z->ob_size); 3731 for (i = 0; i < wordshift; i++) 3732 z->ob_digit[i] = 0; 3733 accum = 0; 3734 for (i = wordshift, j = 0; j < oldsize; i++, j++) { 3735 accum |= (twodigits)a->ob_digit[j] << remshift; 3736 z->ob_digit[i] = (digit)(accum & PyLong_MASK); 3737 accum >>= PyLong_SHIFT; 3738 } 3739 if (remshift) 3740 z->ob_digit[newsize-1] = (digit)accum; 3741 else 3742 assert(!accum); 3743 z = long_normalize(z); 3744 lshift_error: 3745 Py_DECREF(a); 3746 Py_DECREF(b); 3747 return (PyObject *) z; 3748} 3749 3750/* Compute two's complement of digit vector a[0:m], writing result to 3751 z[0:m]. The digit vector a need not be normalized, but should not 3752 be entirely zero. a and z may point to the same digit vector. */ 3753 3754static void 3755v_complement(digit *z, digit *a, Py_ssize_t m) 3756{ 3757 Py_ssize_t i; 3758 digit carry = 1; 3759 for (i = 0; i < m; ++i) { 3760 carry += a[i] ^ PyLong_MASK; 3761 z[i] = carry & PyLong_MASK; 3762 carry >>= PyLong_SHIFT; 3763 } 3764 assert(carry == 0); 3765} 3766 3767/* Bitwise and/xor/or operations */ 3768 3769static PyObject * 3770long_bitwise(PyLongObject *a, 3771 int op, /* '&', '|', '^' */ 3772 PyLongObject *b) 3773{ 3774 int nega, negb, negz; 3775 Py_ssize_t size_a, size_b, size_z, i; 3776 PyLongObject *z; 3777 3778 /* Bitwise operations for negative numbers operate as though 3779 on a two's complement representation. So convert arguments 3780 from sign-magnitude to two's complement, and convert the 3781 result back to sign-magnitude at the end. */ 3782 3783 /* If a is negative, replace it by its two's complement. */ 3784 size_a = ABS(Py_SIZE(a)); 3785 nega = Py_SIZE(a) < 0; 3786 if (nega) { 3787 z = _PyLong_New(size_a); 3788 if (z == NULL) 3789 return NULL; 3790 v_complement(z->ob_digit, a->ob_digit, size_a); 3791 a = z; 3792 } 3793 else 3794 /* Keep reference count consistent. */ 3795 Py_INCREF(a); 3796 3797 /* Same for b. */ 3798 size_b = ABS(Py_SIZE(b)); 3799 negb = Py_SIZE(b) < 0; 3800 if (negb) { 3801 z = _PyLong_New(size_b); 3802 if (z == NULL) { 3803 Py_DECREF(a); 3804 return NULL; 3805 } 3806 v_complement(z->ob_digit, b->ob_digit, size_b); 3807 b = z; 3808 } 3809 else 3810 Py_INCREF(b); 3811 3812 /* Swap a and b if necessary to ensure size_a >= size_b. */ 3813 if (size_a < size_b) { 3814 z = a; a = b; b = z; 3815 size_z = size_a; size_a = size_b; size_b = size_z; 3816 negz = nega; nega = negb; negb = negz; 3817 } 3818 3819 /* JRH: The original logic here was to allocate the result value (z) 3820 as the longer of the two operands. However, there are some cases 3821 where the result is guaranteed to be shorter than that: AND of two 3822 positives, OR of two negatives: use the shorter number. AND with 3823 mixed signs: use the positive number. OR with mixed signs: use the 3824 negative number. 3825 */ 3826 switch (op) { 3827 case '^': 3828 negz = nega ^ negb; 3829 size_z = size_a; 3830 break; 3831 case '&': 3832 negz = nega & negb; 3833 size_z = negb ? size_a : size_b; 3834 break; 3835 case '|': 3836 negz = nega | negb; 3837 size_z = negb ? size_b : size_a; 3838 break; 3839 default: 3840 PyErr_BadArgument(); 3841 return NULL; 3842 } 3843 3844 /* We allow an extra digit if z is negative, to make sure that 3845 the final two's complement of z doesn't overflow. */ 3846 z = _PyLong_New(size_z + negz); 3847 if (z == NULL) { 3848 Py_DECREF(a); 3849 Py_DECREF(b); 3850 return NULL; 3851 } 3852 3853 /* Compute digits for overlap of a and b. */ 3854 switch(op) { 3855 case '&': 3856 for (i = 0; i < size_b; ++i) 3857 z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i]; 3858 break; 3859 case '|': 3860 for (i = 0; i < size_b; ++i) 3861 z->ob_digit[i] = a->ob_digit[i] | b->ob_digit[i]; 3862 break; 3863 case '^': 3864 for (i = 0; i < size_b; ++i) 3865 z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i]; 3866 break; 3867 default: 3868 PyErr_BadArgument(); 3869 return NULL; 3870 } 3871 3872 /* Copy any remaining digits of a, inverting if necessary. */ 3873 if (op == '^' && negb) 3874 for (; i < size_z; ++i) 3875 z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK; 3876 else if (i < size_z) 3877 memcpy(&z->ob_digit[i], &a->ob_digit[i], 3878 (size_z-i)*sizeof(digit)); 3879 3880 /* Complement result if negative. */ 3881 if (negz) { 3882 Py_SIZE(z) = -(Py_SIZE(z)); 3883 z->ob_digit[size_z] = PyLong_MASK; 3884 v_complement(z->ob_digit, z->ob_digit, size_z+1); 3885 } 3886 3887 Py_DECREF(a); 3888 Py_DECREF(b); 3889 return (PyObject *)long_normalize(z); 3890} 3891 3892static PyObject * 3893long_and(PyObject *v, PyObject *w) 3894{ 3895 PyLongObject *a, *b; 3896 PyObject *c; 3897 CONVERT_BINOP(v, w, &a, &b); 3898 c = long_bitwise(a, '&', b); 3899 Py_DECREF(a); 3900 Py_DECREF(b); 3901 return c; 3902} 3903 3904static PyObject * 3905long_xor(PyObject *v, PyObject *w) 3906{ 3907 PyLongObject *a, *b; 3908 PyObject *c; 3909 CONVERT_BINOP(v, w, &a, &b); 3910 c = long_bitwise(a, '^', b); 3911 Py_DECREF(a); 3912 Py_DECREF(b); 3913 return c; 3914} 3915 3916static PyObject * 3917long_or(PyObject *v, PyObject *w) 3918{ 3919 PyLongObject *a, *b; 3920 PyObject *c; 3921 CONVERT_BINOP(v, w, &a, &b); 3922 c = long_bitwise(a, '|', b); 3923 Py_DECREF(a); 3924 Py_DECREF(b); 3925 return c; 3926} 3927 3928static int 3929long_coerce(PyObject **pv, PyObject **pw) 3930{ 3931 if (PyInt_Check(*pw)) { 3932 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw)); 3933 if (*pw == NULL) 3934 return -1; 3935 Py_INCREF(*pv); 3936 return 0; 3937 } 3938 else if (PyLong_Check(*pw)) { 3939 Py_INCREF(*pv); 3940 Py_INCREF(*pw); 3941 return 0; 3942 } 3943 return 1; /* Can't do it */ 3944} 3945 3946static PyObject * 3947long_long(PyObject *v) 3948{ 3949 if (PyLong_CheckExact(v)) 3950 Py_INCREF(v); 3951 else 3952 v = _PyLong_Copy((PyLongObject *)v); 3953 return v; 3954} 3955 3956static PyObject * 3957long_int(PyObject *v) 3958{ 3959 long x; 3960 x = PyLong_AsLong(v); 3961 if (PyErr_Occurred()) { 3962 if (PyErr_ExceptionMatches(PyExc_OverflowError)) { 3963 PyErr_Clear(); 3964 if (PyLong_CheckExact(v)) { 3965 Py_INCREF(v); 3966 return v; 3967 } 3968 else 3969 return _PyLong_Copy((PyLongObject *)v); 3970 } 3971 else 3972 return NULL; 3973 } 3974 return PyInt_FromLong(x); 3975} 3976 3977static PyObject * 3978long_float(PyObject *v) 3979{ 3980 double result; 3981 result = PyLong_AsDouble(v); 3982 if (result == -1.0 && PyErr_Occurred()) 3983 return NULL; 3984 return PyFloat_FromDouble(result); 3985} 3986 3987static PyObject * 3988long_oct(PyObject *v) 3989{ 3990 return _PyLong_Format(v, 8, 1, 0); 3991} 3992 3993static PyObject * 3994long_hex(PyObject *v) 3995{ 3996 return _PyLong_Format(v, 16, 1, 0); 3997} 3998 3999static PyObject * 4000long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds); 4001 4002static PyObject * 4003long_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 4004{ 4005 PyObject *x = NULL; 4006 int base = -909; /* unlikely! */ 4007 static char *kwlist[] = {"x", "base", 0}; 4008 4009 if (type != &PyLong_Type) 4010 return long_subtype_new(type, args, kwds); /* Wimp out */ 4011 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist, 4012 &x, &base)) 4013 return NULL; 4014 if (x == NULL) { 4015 if (base != -909) { 4016 PyErr_SetString(PyExc_TypeError, 4017 "long() missing string argument"); 4018 return NULL; 4019 } 4020 return PyLong_FromLong(0L); 4021 } 4022 if (base == -909) 4023 return PyNumber_Long(x); 4024 else if (PyString_Check(x)) { 4025 /* Since PyLong_FromString doesn't have a length parameter, 4026 * check here for possible NULs in the string. */ 4027 char *string = PyString_AS_STRING(x); 4028 if (strlen(string) != (size_t)PyString_Size(x)) { 4029 /* create a repr() of the input string, 4030 * just like PyLong_FromString does. */ 4031 PyObject *srepr; 4032 srepr = PyObject_Repr(x); 4033 if (srepr == NULL) 4034 return NULL; 4035 PyErr_Format(PyExc_ValueError, 4036 "invalid literal for long() with base %d: %s", 4037 base, PyString_AS_STRING(srepr)); 4038 Py_DECREF(srepr); 4039 return NULL; 4040 } 4041 return PyLong_FromString(PyString_AS_STRING(x), NULL, base); 4042 } 4043#ifdef Py_USING_UNICODE 4044 else if (PyUnicode_Check(x)) 4045 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x), 4046 PyUnicode_GET_SIZE(x), 4047 base); 4048#endif 4049 else { 4050 PyErr_SetString(PyExc_TypeError, 4051 "long() can't convert non-string with explicit base"); 4052 return NULL; 4053 } 4054} 4055 4056/* Wimpy, slow approach to tp_new calls for subtypes of long: 4057 first create a regular long from whatever arguments we got, 4058 then allocate a subtype instance and initialize it from 4059 the regular long. The regular long is then thrown away. 4060*/ 4061static PyObject * 4062long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds) 4063{ 4064 PyLongObject *tmp, *newobj; 4065 Py_ssize_t i, n; 4066 4067 assert(PyType_IsSubtype(type, &PyLong_Type)); 4068 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds); 4069 if (tmp == NULL) 4070 return NULL; 4071 assert(PyLong_Check(tmp)); 4072 n = Py_SIZE(tmp); 4073 if (n < 0) 4074 n = -n; 4075 newobj = (PyLongObject *)type->tp_alloc(type, n); 4076 if (newobj == NULL) { 4077 Py_DECREF(tmp); 4078 return NULL; 4079 } 4080 assert(PyLong_Check(newobj)); 4081 Py_SIZE(newobj) = Py_SIZE(tmp); 4082 for (i = 0; i < n; i++) 4083 newobj->ob_digit[i] = tmp->ob_digit[i]; 4084 Py_DECREF(tmp); 4085 return (PyObject *)newobj; 4086} 4087 4088static PyObject * 4089long_getnewargs(PyLongObject *v) 4090{ 4091 return Py_BuildValue("(N)", _PyLong_Copy(v)); 4092} 4093 4094static PyObject * 4095long_get0(PyLongObject *v, void *context) { 4096 return PyLong_FromLong(0L); 4097} 4098 4099static PyObject * 4100long_get1(PyLongObject *v, void *context) { 4101 return PyLong_FromLong(1L); 4102} 4103 4104static PyObject * 4105long__format__(PyObject *self, PyObject *args) 4106{ 4107 PyObject *format_spec; 4108 4109 if (!PyArg_ParseTuple(args, "O:__format__", &format_spec)) 4110 return NULL; 4111 if (PyBytes_Check(format_spec)) 4112 return _PyLong_FormatAdvanced(self, 4113 PyBytes_AS_STRING(format_spec), 4114 PyBytes_GET_SIZE(format_spec)); 4115 if (PyUnicode_Check(format_spec)) { 4116 /* Convert format_spec to a str */ 4117 PyObject *result; 4118 PyObject *str_spec = PyObject_Str(format_spec); 4119 4120 if (str_spec == NULL) 4121 return NULL; 4122 4123 result = _PyLong_FormatAdvanced(self, 4124 PyBytes_AS_STRING(str_spec), 4125 PyBytes_GET_SIZE(str_spec)); 4126 4127 Py_DECREF(str_spec); 4128 return result; 4129 } 4130 PyErr_SetString(PyExc_TypeError, "__format__ requires str or unicode"); 4131 return NULL; 4132} 4133 4134static PyObject * 4135long_sizeof(PyLongObject *v) 4136{ 4137 Py_ssize_t res; 4138 4139 res = v->ob_type->tp_basicsize + ABS(Py_SIZE(v))*sizeof(digit); 4140 return PyInt_FromSsize_t(res); 4141} 4142 4143static PyObject * 4144long_bit_length(PyLongObject *v) 4145{ 4146 PyLongObject *result, *x, *y; 4147 Py_ssize_t ndigits, msd_bits = 0; 4148 digit msd; 4149 4150 assert(v != NULL); 4151 assert(PyLong_Check(v)); 4152 4153 ndigits = ABS(Py_SIZE(v)); 4154 if (ndigits == 0) 4155 return PyInt_FromLong(0); 4156 4157 msd = v->ob_digit[ndigits-1]; 4158 while (msd >= 32) { 4159 msd_bits += 6; 4160 msd >>= 6; 4161 } 4162 msd_bits += (long)(BitLengthTable[msd]); 4163 4164 if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT) 4165 return PyInt_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits); 4166 4167 /* expression above may overflow; use Python integers instead */ 4168 result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1); 4169 if (result == NULL) 4170 return NULL; 4171 x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT); 4172 if (x == NULL) 4173 goto error; 4174 y = (PyLongObject *)long_mul(result, x); 4175 Py_DECREF(x); 4176 if (y == NULL) 4177 goto error; 4178 Py_DECREF(result); 4179 result = y; 4180 4181 x = (PyLongObject *)PyLong_FromLong((long)msd_bits); 4182 if (x == NULL) 4183 goto error; 4184 y = (PyLongObject *)long_add(result, x); 4185 Py_DECREF(x); 4186 if (y == NULL) 4187 goto error; 4188 Py_DECREF(result); 4189 result = y; 4190 4191 return (PyObject *)result; 4192 4193 error: 4194 Py_DECREF(result); 4195 return NULL; 4196} 4197 4198PyDoc_STRVAR(long_bit_length_doc, 4199"long.bit_length() -> int or long\n\ 4200\n\ 4201Number of bits necessary to represent self in binary.\n\ 4202>>> bin(37L)\n\ 4203'0b100101'\n\ 4204>>> (37L).bit_length()\n\ 42056"); 4206 4207#if 0 4208static PyObject * 4209long_is_finite(PyObject *v) 4210{ 4211 Py_RETURN_TRUE; 4212} 4213#endif 4214 4215static PyMethodDef long_methods[] = { 4216 {"conjugate", (PyCFunction)long_long, METH_NOARGS, 4217 "Returns self, the complex conjugate of any long."}, 4218 {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS, 4219 long_bit_length_doc}, 4220#if 0 4221 {"is_finite", (PyCFunction)long_is_finite, METH_NOARGS, 4222 "Returns always True."}, 4223#endif 4224 {"__trunc__", (PyCFunction)long_long, METH_NOARGS, 4225 "Truncating an Integral returns itself."}, 4226 {"__getnewargs__", (PyCFunction)long_getnewargs, METH_NOARGS}, 4227 {"__format__", (PyCFunction)long__format__, METH_VARARGS}, 4228 {"__sizeof__", (PyCFunction)long_sizeof, METH_NOARGS, 4229 "Returns size in memory, in bytes"}, 4230 {NULL, NULL} /* sentinel */ 4231}; 4232 4233static PyGetSetDef long_getset[] = { 4234 {"real", 4235 (getter)long_long, (setter)NULL, 4236 "the real part of a complex number", 4237 NULL}, 4238 {"imag", 4239 (getter)long_get0, (setter)NULL, 4240 "the imaginary part of a complex number", 4241 NULL}, 4242 {"numerator", 4243 (getter)long_long, (setter)NULL, 4244 "the numerator of a rational number in lowest terms", 4245 NULL}, 4246 {"denominator", 4247 (getter)long_get1, (setter)NULL, 4248 "the denominator of a rational number in lowest terms", 4249 NULL}, 4250 {NULL} /* Sentinel */ 4251}; 4252 4253PyDoc_STRVAR(long_doc, 4254"long(x=0) -> long\n\ 4255long(x, base=10) -> long\n\ 4256\n\ 4257Convert a number or string to a long integer, or return 0L if no arguments\n\ 4258are given. If x is floating point, the conversion truncates towards zero.\n\ 4259\n\ 4260If x is not a number or if base is given, then x must be a string or\n\ 4261Unicode object representing an integer literal in the given base. The\n\ 4262literal can be preceded by '+' or '-' and be surrounded by whitespace.\n\ 4263The base defaults to 10. Valid bases are 0 and 2-36. Base 0 means to\n\ 4264interpret the base from the string as an integer literal.\n\ 4265>>> int('0b100', base=0)\n\ 42664L"); 4267 4268static PyNumberMethods long_as_number = { 4269 (binaryfunc)long_add, /*nb_add*/ 4270 (binaryfunc)long_sub, /*nb_subtract*/ 4271 (binaryfunc)long_mul, /*nb_multiply*/ 4272 long_classic_div, /*nb_divide*/ 4273 long_mod, /*nb_remainder*/ 4274 long_divmod, /*nb_divmod*/ 4275 long_pow, /*nb_power*/ 4276 (unaryfunc)long_neg, /*nb_negative*/ 4277 (unaryfunc)long_long, /*tp_positive*/ 4278 (unaryfunc)long_abs, /*tp_absolute*/ 4279 (inquiry)long_nonzero, /*tp_nonzero*/ 4280 (unaryfunc)long_invert, /*nb_invert*/ 4281 long_lshift, /*nb_lshift*/ 4282 (binaryfunc)long_rshift, /*nb_rshift*/ 4283 long_and, /*nb_and*/ 4284 long_xor, /*nb_xor*/ 4285 long_or, /*nb_or*/ 4286 long_coerce, /*nb_coerce*/ 4287 long_int, /*nb_int*/ 4288 long_long, /*nb_long*/ 4289 long_float, /*nb_float*/ 4290 long_oct, /*nb_oct*/ 4291 long_hex, /*nb_hex*/ 4292 0, /* nb_inplace_add */ 4293 0, /* nb_inplace_subtract */ 4294 0, /* nb_inplace_multiply */ 4295 0, /* nb_inplace_divide */ 4296 0, /* nb_inplace_remainder */ 4297 0, /* nb_inplace_power */ 4298 0, /* nb_inplace_lshift */ 4299 0, /* nb_inplace_rshift */ 4300 0, /* nb_inplace_and */ 4301 0, /* nb_inplace_xor */ 4302 0, /* nb_inplace_or */ 4303 long_div, /* nb_floor_divide */ 4304 long_true_divide, /* nb_true_divide */ 4305 0, /* nb_inplace_floor_divide */ 4306 0, /* nb_inplace_true_divide */ 4307 long_long, /* nb_index */ 4308}; 4309 4310PyTypeObject PyLong_Type = { 4311 PyObject_HEAD_INIT(&PyType_Type) 4312 0, /* ob_size */ 4313 "long", /* tp_name */ 4314 offsetof(PyLongObject, ob_digit), /* tp_basicsize */ 4315 sizeof(digit), /* tp_itemsize */ 4316 long_dealloc, /* tp_dealloc */ 4317 0, /* tp_print */ 4318 0, /* tp_getattr */ 4319 0, /* tp_setattr */ 4320 (cmpfunc)long_compare, /* tp_compare */ 4321 long_repr, /* tp_repr */ 4322 &long_as_number, /* tp_as_number */ 4323 0, /* tp_as_sequence */ 4324 0, /* tp_as_mapping */ 4325 (hashfunc)long_hash, /* tp_hash */ 4326 0, /* tp_call */ 4327 long_str, /* tp_str */ 4328 PyObject_GenericGetAttr, /* tp_getattro */ 4329 0, /* tp_setattro */ 4330 0, /* tp_as_buffer */ 4331 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES | 4332 Py_TPFLAGS_BASETYPE | Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */ 4333 long_doc, /* tp_doc */ 4334 0, /* tp_traverse */ 4335 0, /* tp_clear */ 4336 0, /* tp_richcompare */ 4337 0, /* tp_weaklistoffset */ 4338 0, /* tp_iter */ 4339 0, /* tp_iternext */ 4340 long_methods, /* tp_methods */ 4341 0, /* tp_members */ 4342 long_getset, /* tp_getset */ 4343 0, /* tp_base */ 4344 0, /* tp_dict */ 4345 0, /* tp_descr_get */ 4346 0, /* tp_descr_set */ 4347 0, /* tp_dictoffset */ 4348 0, /* tp_init */ 4349 0, /* tp_alloc */ 4350 long_new, /* tp_new */ 4351 PyObject_Del, /* tp_free */ 4352}; 4353 4354static PyTypeObject Long_InfoType; 4355 4356PyDoc_STRVAR(long_info__doc__, 4357"sys.long_info\n\ 4358\n\ 4359A struct sequence that holds information about Python's\n\ 4360internal representation of integers. The attributes are read only."); 4361 4362static PyStructSequence_Field long_info_fields[] = { 4363 {"bits_per_digit", "size of a digit in bits"}, 4364 {"sizeof_digit", "size in bytes of the C type used to represent a digit"}, 4365 {NULL, NULL} 4366}; 4367 4368static PyStructSequence_Desc long_info_desc = { 4369 "sys.long_info", /* name */ 4370 long_info__doc__, /* doc */ 4371 long_info_fields, /* fields */ 4372 2 /* number of fields */ 4373}; 4374 4375PyObject * 4376PyLong_GetInfo(void) 4377{ 4378 PyObject* long_info; 4379 int field = 0; 4380 long_info = PyStructSequence_New(&Long_InfoType); 4381 if (long_info == NULL) 4382 return NULL; 4383 PyStructSequence_SET_ITEM(long_info, field++, 4384 PyInt_FromLong(PyLong_SHIFT)); 4385 PyStructSequence_SET_ITEM(long_info, field++, 4386 PyInt_FromLong(sizeof(digit))); 4387 if (PyErr_Occurred()) { 4388 Py_CLEAR(long_info); 4389 return NULL; 4390 } 4391 return long_info; 4392} 4393 4394int 4395_PyLong_Init(void) 4396{ 4397 /* initialize long_info */ 4398 if (Long_InfoType.tp_name == 0) 4399 PyStructSequence_InitType(&Long_InfoType, &long_info_desc); 4400 return 1; 4401} 4402