Objects/longobject.c

   1
   2 /* Long (arbitrary precision) integer object implementation */
   3
   4 /* XXX The functional organization of this file is terrible */
   5
   6 #include "Python.h"
   7 #include "longintrepr.h"
   8
   9 #include <assert.h>
  10 #include <ctype.h>
  11
  12 #define ABS(x) ((x) < 0 ? -(x) : (x))
  13
  14 /* Forward */
  15 static PyLongObject *long_normalize(PyLongObject *);
  16 static PyLongObject *mul1(PyLongObject *, wdigit);
  17 static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
  18 static PyLongObject *divrem1(PyLongObject *, wdigit, digit *);
  19 static PyObject *long_format(PyObject *aa, int base, int addL);
  20
  21 static int ticker;      /* XXX Could be shared with ceval? */
  22
  23 #define SIGCHECK(PyTryBlock) \
  24         if (--ticker < 0) { \
  25                 ticker = 100; \
  26                 if (PyErr_CheckSignals()) { PyTryBlock; } \
  27         }
  28
  29 /* Normalize (remove leading zeros from) a long int object.
  30    Doesn't attempt to free the storage--in most cases, due to the nature
  31    of the algorithms used, this could save at most be one word anyway. */
  32
  33 static PyLongObject *
  34 long_normalize(register PyLongObject *v)
  35 {
  36         int j = ABS(v->ob_size);
  37         register int i = j;
  38
  39         while (i > 0 && v->ob_digit[i-1] == 0)
  40                 --i;
  41         if (i != j)
  42                 v->ob_size = (v->ob_size < 0) ? -(i) : i;
  43         return v;
  44 }
  45
  46 /* Allocate a new long int object with size digits.
  47    Return NULL and set exception if we run out of memory. */
  48
  49 PyLongObject *
  50 _PyLong_New(int size)
  51 {
  52         return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
  53 }
  54
  55 /* Create a new long int object from a C long int */
  56
  57 PyObject *
  58 PyLong_FromLong(long ival)
  59 {
  60         /* Assume a C long fits in at most 5 'digits' */
  61         /* Works on both 32- and 64-bit machines */
  62         PyLongObject *v = _PyLong_New(5);
  63         if (v != NULL) {
  64                 unsigned long t = ival;
  65                 int i;
  66                 if (ival < 0) {
  67                         t = -ival;
  68                         v->ob_size = -(v->ob_size);
  69                 }
  70                 for (i = 0; i < 5; i++) {
  71                         v->ob_digit[i] = (digit) (t & MASK);
  72                         t >>= SHIFT;
  73                 }
  74                 v = long_normalize(v);
  75         }
  76         return (PyObject *)v;
  77 }
  78
  79 /* Create a new long int object from a C unsigned long int */
  80
  81 PyObject *
  82 PyLong_FromUnsignedLong(unsigned long ival)
  83 {
  84         /* Assume a C long fits in at most 5 'digits' */
  85         /* Works on both 32- and 64-bit machines */
  86         PyLongObject *v = _PyLong_New(5);
  87         if (v != NULL) {
  88                 unsigned long t = ival;
  89                 int i;
  90                 for (i = 0; i < 5; i++) {
  91                         v->ob_digit[i] = (digit) (t & MASK);
  92                         t >>= SHIFT;
  93                 }
  94                 v = long_normalize(v);
  95         }
  96         return (PyObject *)v;
  97 }
  98
  99 /* Create a new long int object from a C double */
 100
 101 PyObject *
 102 PyLong_FromDouble(double dval)
 103 {
 104         PyLongObject *v;
 105         double frac;
 106         int i, ndig, expo, neg;
 107         neg = 0;
 108         if (Py_IS_INFINITY(dval)) {
 109                 PyErr_SetString(PyExc_OverflowError,
 110                         "cannot convert float infinity to long");
 111                 return NULL;
 112         }
 113         if (dval < 0.0) {
 114                 neg = 1;
 115                 dval = -dval;
 116         }
 117         frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
 118         if (expo <= 0)
 119                 return PyLong_FromLong(0L);
 120         ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
 121         v = _PyLong_New(ndig);
 122         if (v == NULL)
 123                 return NULL;
 124         frac = ldexp(frac, (expo-1) % SHIFT + 1);
 125         for (i = ndig; --i >= 0; ) {
 126                 long bits = (long)frac;
 127                 v->ob_digit[i] = (digit) bits;
 128                 frac = frac - (double)bits;
 129                 frac = ldexp(frac, SHIFT);
 130         }
 131         if (neg)
 132                 v->ob_size = -(v->ob_size);
 133         return (PyObject *)v;
 134 }
 135
 136 /* Get a C long int from a long int object.
 137    Returns -1 and sets an error condition if overflow occurs. */
 138
 139 long
 140 PyLong_AsLong(PyObject *vv)
 141 {
 142         /* This version by Tim Peters */
 143         register PyLongObject *v;
 144         unsigned long x, prev;
 145         int i, sign;
 146
 147         if (vv == NULL || !PyLong_Check(vv)) {
 148                 PyErr_BadInternalCall();
 149                 return -1;
 150         }
 151         v = (PyLongObject *)vv;
 152         i = v->ob_size;
 153         sign = 1;
 154         x = 0;
 155         if (i < 0) {
 156                 sign = -1;
 157                 i = -(i);
 158         }
 159         while (--i >= 0) {
 160                 prev = x;
 161                 x = (x << SHIFT) + v->ob_digit[i];
 162                 if ((x >> SHIFT) != prev)
 163                         goto overflow;
 164         }
 165         /* Haven't lost any bits, but if the sign bit is set we're in
 166          * trouble *unless* this is the min negative number.  So,
 167          * trouble iff sign bit set && (positive || some bit set other
 168          * than the sign bit).
 169          */
 170         if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
 171                 goto overflow;
 172         return (long)x * sign;
 173
 174  overflow:
 175         PyErr_SetString(PyExc_OverflowError,
 176                         "long int too large to convert");
 177         return -1;
 178 }
 179
 180 /* Get a C long int from a long int object.
 181    Returns -1 and sets an error condition if overflow occurs. */
 182
 183 unsigned long
 184 PyLong_AsUnsignedLong(PyObject *vv)
 185 {
 186         register PyLongObject *v;
 187         unsigned long x, prev;
 188         int i;
 189
 190         if (vv == NULL || !PyLong_Check(vv)) {
 191                 PyErr_BadInternalCall();
 192                 return (unsigned long) -1;
 193         }
 194         v = (PyLongObject *)vv;
 195         i = v->ob_size;
 196         x = 0;
 197         if (i < 0) {
 198                 PyErr_SetString(PyExc_OverflowError,
 199                            "can't convert negative value to unsigned long");
 200                 return (unsigned long) -1;
 201         }
 202         while (--i >= 0) {
 203                 prev = x;
 204                 x = (x << SHIFT) + v->ob_digit[i];
 205                 if ((x >> SHIFT) != prev) {
 206                         PyErr_SetString(PyExc_OverflowError,
 207                                 "long int too large to convert");
 208                         return (unsigned long) -1;
 209                 }
 210         }
 211         return x;
 212 }
 213
 214 /* Get a C double from a long int object. */
 215
 216 double
 217 PyLong_AsDouble(PyObject *vv)
 218 {
 219         register PyLongObject *v;
 220         double x;
 221         double multiplier = (double) (1L << SHIFT);
 222         int i, sign;
 223
 224         if (vv == NULL || !PyLong_Check(vv)) {
 225                 PyErr_BadInternalCall();
 226                 return -1;
 227         }
 228         v = (PyLongObject *)vv;
 229         i = v->ob_size;
 230         sign = 1;
 231         x = 0.0;
 232         if (i < 0) {
 233                 sign = -1;
 234                 i = -(i);
 235         }
 236         while (--i >= 0) {
 237                 x = x*multiplier + (double)v->ob_digit[i];
 238         }
 239         return x * sign;
 240 }
 241
 242 /* Create a new long (or int) object from a C pointer */
 243
 244 PyObject *
 245 PyLong_FromVoidPtr(void *p)
 246 {
 247 #if SIZEOF_VOID_P == SIZEOF_LONG
 248         return PyInt_FromLong((long)p);
 249 #else
 250         /* optimize null pointers */
 251         if ( p == NULL )
 252                 return PyInt_FromLong(0);
 253
 254         /* we can assume that HAVE_LONG_LONG is true. if not, then the
 255            configuration process should have bailed (having big pointers
 256            without long longs seems non-sensical) */
 257         return PyLong_FromLongLong((LONG_LONG)p);
 258 #endif /* SIZEOF_VOID_P == SIZEOF_LONG */
 259 }
 260
 261 /* Get a C pointer from a long object (or an int object in some cases) */
 262
 263 void *
 264 PyLong_AsVoidPtr(PyObject *vv)
 265 {
 266         /* This function will allow int or long objects. If vv is neither,
 267            then the PyLong_AsLong*() functions will raise the exception:
 268            PyExc_SystemError, "bad argument to internal function"
 269         */
 270
 271 #if SIZEOF_VOID_P == SIZEOF_LONG
 272         long x;
 273
 274         if ( PyInt_Check(vv) )
 275                 x = PyInt_AS_LONG(vv);
 276         else
 277                 x = PyLong_AsLong(vv);
 278 #else
 279         /* we can assume that HAVE_LONG_LONG is true. if not, then the
 280            configuration process should have bailed (having big pointers
 281            without long longs seems non-sensical) */
 282         LONG_LONG x;
 283
 284         if ( PyInt_Check(vv) )
 285                 x = PyInt_AS_LONG(vv);
 286         else
 287                 x = PyLong_AsLongLong(vv);
 288 #endif /* SIZEOF_VOID_P == SIZEOF_LONG */
 289
 290         if (x == -1 && PyErr_Occurred())
 291                 return NULL;
 292         return (void *)x;
 293 }
 294
 295 #ifdef HAVE_LONG_LONG
 296 /*
 297  * LONG_LONG support by Chris Herborth (chrish@qnx.com)
 298  *
 299  * For better or worse :-), I tried to follow the coding style already
 300  * here.
 301  */
 302
 303 /* Create a new long int object from a C LONG_LONG int */
 304
 305 PyObject *
 306 PyLong_FromLongLong(LONG_LONG ival)
 307 {
 308 #if SIZEOF_LONG_LONG == SIZEOF_LONG
 309         /* In case the compiler is faking it. */
 310         return PyLong_FromLong( (long)ival );
 311 #else
 312         if ((LONG_LONG)LONG_MIN <= ival && ival <= (LONG_LONG)LONG_MAX) {
 313                 return PyLong_FromLong( (long)ival );
 314         }
 315         else if (0 <= ival && ival <= (unsigned LONG_LONG)ULONG_MAX) {
 316                 return PyLong_FromUnsignedLong( (unsigned long)ival );
 317         }
 318         else {
 319                 /* Assume a C LONG_LONG fits in at most 10 'digits'.
 320                  * Should be OK if we're assuming long fits in 5.
 321                  */
 322                 PyLongObject *v = _PyLong_New(10);
 323
 324                 if (v != NULL) {
 325                         unsigned LONG_LONG t = ival;
 326                         int i;
 327                         if (ival < 0) {
 328                                 t = -ival;
 329                                 v->ob_size = -(v->ob_size);
 330                         }
 331
 332                         for (i = 0; i < 10; i++) {
 333                                 v->ob_digit[i] = (digit) (t & MASK);
 334                                 t >>= SHIFT;
 335                         }
 336
 337                         v = long_normalize(v);
 338                 }
 339
 340                 return (PyObject *)v;
 341         }
 342 #endif
 343 }
 344
 345 /* Create a new long int object from a C unsigned LONG_LONG int */
 346 PyObject *
 347 PyLong_FromUnsignedLongLong(unsigned LONG_LONG ival)
 348 {
 349 #if SIZEOF_LONG_LONG == SIZEOF_LONG
 350         /* In case the compiler is faking it. */
 351         return PyLong_FromUnsignedLong( (unsigned long)ival );
 352 #else
 353         if( ival <= (unsigned LONG_LONG)ULONG_MAX ) {
 354                 return PyLong_FromUnsignedLong( (unsigned long)ival );
 355         }
 356         else {
 357                 /* Assume a C long fits in at most 10 'digits'. */
 358                 PyLongObject *v = _PyLong_New(10);
 359
 360                 if (v != NULL) {
 361                         unsigned LONG_LONG t = ival;
 362                         int i;
 363                         for (i = 0; i < 10; i++) {
 364                                 v->ob_digit[i] = (digit) (t & MASK);
 365                                 t >>= SHIFT;
 366                         }
 367
 368                         v = long_normalize(v);
 369                 }
 370
 371                 return (PyObject *)v;
 372         }
 373 #endif
 374 }
 375
 376 /* Get a C LONG_LONG int from a long int object.
 377    Returns -1 and sets an error condition if overflow occurs. */
 378
 379 LONG_LONG
 380 PyLong_AsLongLong(PyObject *vv)
 381 {
 382 #if SIZEOF_LONG_LONG == SIZEOF_LONG
 383         /* In case the compiler is faking it. */
 384         return (LONG_LONG)PyLong_AsLong( vv );
 385 #else
 386         register PyLongObject *v;
 387         LONG_LONG x, prev;
 388         int i, sign;
 389
 390         if (vv == NULL || !PyLong_Check(vv)) {
 391                 PyErr_BadInternalCall();
 392                 return -1;
 393         }
 394
 395         v = (PyLongObject *)vv;
 396         i = v->ob_size;
 397         sign = 1;
 398         x = 0;
 399
 400         if (i < 0) {
 401                 sign = -1;
 402                 i = -(i);
 403         }
 404
 405         while (--i >= 0) {
 406                 prev = x;
 407                 x = (x << SHIFT) + v->ob_digit[i];
 408                 if ((x >> SHIFT) != prev) {
 409                         PyErr_SetString(PyExc_OverflowError,
 410                                 "long int too long to convert");
 411                         return -1;
 412                 }
 413         }
 414
 415         return x * sign;
 416 #endif
 417 }
 418
 419 unsigned LONG_LONG
 420 PyLong_AsUnsignedLongLong(PyObject *vv)
 421 {
 422 #if SIZEOF_LONG_LONG == 4
 423         /* In case the compiler is faking it. */
 424         return (unsigned LONG_LONG)PyLong_AsUnsignedLong( vv );
 425 #else
 426         register PyLongObject *v;
 427         unsigned LONG_LONG x, prev;
 428         int i;
 429
 430         if (vv == NULL || !PyLong_Check(vv)) {
 431                 PyErr_BadInternalCall();
 432                 return (unsigned LONG_LONG) -1;
 433         }
 434
 435         v = (PyLongObject *)vv;
 436         i = v->ob_size;
 437         x = 0;
 438
 439         if (i < 0) {
 440                 PyErr_SetString(PyExc_OverflowError,
 441                            "can't convert negative value to unsigned long");
 442                 return (unsigned LONG_LONG) -1;
 443         }
 444
 445         while (--i >= 0) {
 446                 prev = x;
 447                 x = (x << SHIFT) + v->ob_digit[i];
 448                 if ((x >> SHIFT) != prev) {
 449                         PyErr_SetString(PyExc_OverflowError,
 450                                 "long int too long to convert");
 451                         return (unsigned LONG_LONG) -1;
 452                 }
 453         }
 454
 455         return x;
 456 #endif
 457 }
 458 #endif /* HAVE_LONG_LONG */
 459
 460
 461 static int
 462 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
 463         if (PyLong_Check(v)) {
 464                 *a = (PyLongObject *) v;
 465                 Py_INCREF(v);
 466         }
 467         else if (PyInt_Check(v)) {
 468                 *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
 469         }
 470         else {
 471                 return 0;
 472         }
 473         if (PyLong_Check(w)) {
 474                 *b = (PyLongObject *) w;
 475                 Py_INCREF(w);
 476         }
 477         else if (PyInt_Check(w)) {
 478                 *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
 479         }
 480         else {
 481                 Py_DECREF(*a);
 482                 return 0;
 483         }
 484         return 1;
 485 }
 486
 487 #define CONVERT_BINOP(v, w, a, b) \
 488         if (!convert_binop(v, w, a, b)) { \
 489                 Py_INCREF(Py_NotImplemented); \
 490                 return Py_NotImplemented; \
 491         }
 492
 493
 494 /* Multiply by a single digit, ignoring the sign. */
 495
 496 static PyLongObject *
 497 mul1(PyLongObject *a, wdigit n)
 498 {
 499         return muladd1(a, n, (digit)0);
 500 }
 501
 502 /* Multiply by a single digit and add a single digit, ignoring the sign. */
 503
 504 static PyLongObject *
 505 muladd1(PyLongObject *a, wdigit n, wdigit extra)
 506 {
 507         int size_a = ABS(a->ob_size);
 508         PyLongObject *z = _PyLong_New(size_a+1);
 509         twodigits carry = extra;
 510         int i;
 511
 512         if (z == NULL)
 513                 return NULL;
 514         for (i = 0; i < size_a; ++i) {
 515                 carry += (twodigits)a->ob_digit[i] * n;
 516                 z->ob_digit[i] = (digit) (carry & MASK);
 517                 carry >>= SHIFT;
 518         }
 519         z->ob_digit[i] = (digit) carry;
 520         return long_normalize(z);
 521 }
 522
 523 /* Divide a long integer by a digit, returning both the quotient
 524    (as function result) and the remainder (through *prem).
 525    The sign of a is ignored; n should not be zero. */
 526
 527 static PyLongObject *
 528 divrem1(PyLongObject *a, wdigit n, digit *prem)
 529 {
 530         int size = ABS(a->ob_size);
 531         PyLongObject *z;
 532         int i;
 533         twodigits rem = 0;
 534
 535         assert(n > 0 && n <= MASK);
 536         z = _PyLong_New(size);
 537         if (z == NULL)
 538                 return NULL;
 539         for (i = size; --i >= 0; ) {
 540                 rem = (rem << SHIFT) + a->ob_digit[i];
 541                 z->ob_digit[i] = (digit) (rem/n);
 542                 rem %= n;
 543         }
 544         *prem = (digit) rem;
 545         return long_normalize(z);
 546 }
 547
 548 /* Convert a long int object to a string, using a given conversion base.
 549    Return a string object.
 550    If base is 8 or 16, add the proper prefix '0' or '0x'. */
 551
 552 static PyObject *
 553 long_format(PyObject *aa, int base, int addL)
 554 {
 555         register PyLongObject *a = (PyLongObject *)aa;
 556         PyStringObject *str;
 557         int i;
 558         int size_a = ABS(a->ob_size);
 559         char *p;
 560         int bits;
 561         char sign = '\0';
 562
 563         if (a == NULL || !PyLong_Check(a)) {
 564                 PyErr_BadInternalCall();
 565                 return NULL;
 566         }
 567         assert(base >= 2 && base <= 36);
 568
 569         /* Compute a rough upper bound for the length of the string */
 570         i = base;
 571         bits = 0;
 572         while (i > 1) {
 573                 ++bits;
 574                 i >>= 1;
 575         }
 576         i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
 577         str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
 578         if (str == NULL)
 579                 return NULL;
 580         p = PyString_AS_STRING(str) + i;
 581         *p = '\0';
 582         if (addL)
 583                 *--p = 'L';
 584         if (a->ob_size < 0)
 585                 sign = '-';
 586
 587         if (a->ob_size == 0) {
 588                 *--p = '0';
 589         }
 590         else if ((base & (base - 1)) == 0) {
 591                 /* JRH: special case for power-of-2 bases */
 592                 twodigits temp = a->ob_digit[0];
 593                 int bitsleft = SHIFT;
 594                 int rem;
 595                 int last = abs(a->ob_size);
 596                 int basebits = 1;
 597                 i = base;
 598                 while ((i >>= 1) > 1)
 599                         ++basebits;
 600
 601                 i = 0;
 602                 for (;;) {
 603                         while (bitsleft >= basebits) {
 604                                 if ((temp == 0) && (i >= last - 1)) break;
 605                                 rem = temp & (base - 1);
 606                                 if (rem < 10)
 607                                         rem += '0';
 608                                 else
 609                                         rem += 'A' - 10;
 610                                 assert(p > PyString_AS_STRING(str));
 611                                 *--p = (char) rem;
 612                                 bitsleft -= basebits;
 613                                 temp >>= basebits;
 614                         }
 615                         if (++i >= last) {
 616                                 if (temp == 0) break;
 617                                 bitsleft = 99;
 618                                 /* loop again to pick up final digits */
 619                         }
 620                         else {
 621                                 temp = (a->ob_digit[i] << bitsleft) | temp;
 622                                 bitsleft += SHIFT;
 623                         }
 624                 }
 625         }
 626         else {
 627                 Py_INCREF(a);
 628                 do {
 629                         digit rem;
 630                         PyLongObject *temp = divrem1(a, (digit)base, &rem);
 631                         if (temp == NULL) {
 632                                 Py_DECREF(a);
 633                                 Py_DECREF(str);
 634                                 return NULL;
 635                         }
 636                         if (rem < 10)
 637                                 rem += '0';
 638                         else
 639                                 rem += 'A'-10;
 640                         assert(p > PyString_AS_STRING(str));
 641                         *--p = (char) rem;
 642                         Py_DECREF(a);
 643                         a = temp;
 644                         SIGCHECK({
 645                                 Py_DECREF(a);
 646                                 Py_DECREF(str);
 647                                 return NULL;
 648                         })
 649                 } while (ABS(a->ob_size) != 0);
 650                 Py_DECREF(a);
 651         }
 652
 653         if (base == 8) {
 654                 if (size_a != 0)
 655                         *--p = '0';
 656         }
 657         else if (base == 16) {
 658                 *--p = 'x';
 659                 *--p = '0';
 660         }
 661         else if (base != 10) {
 662                 *--p = '#';
 663                 *--p = '0' + base%10;
 664                 if (base > 10)
 665                         *--p = '0' + base/10;
 666         }
 667         if (sign)
 668                 *--p = sign;
 669         if (p != PyString_AS_STRING(str)) {
 670                 char *q = PyString_AS_STRING(str);
 671                 assert(p > q);
 672                 do {
 673                 } while ((*q++ = *p++) != '\0');
 674                 q--;
 675                 _PyString_Resize((PyObject **)&str,
 676                                  (int) (q - PyString_AS_STRING(str)));
 677         }
 678         return (PyObject *)str;
 679 }
 680
 681 PyObject *
 682 PyLong_FromString(char *str, char **pend, int base)
 683 {
 684         int sign = 1;
 685         char *start, *orig_str = str;
 686         PyLongObject *z;
 687
 688         if ((base != 0 && base < 2) || base > 36) {
 689                 PyErr_SetString(PyExc_ValueError,
 690                                 "long() arg 2 must be >= 2 and <= 36");
 691                 return NULL;
 692         }
 693         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
 694                 str++;
 695         if (*str == '+')
 696                 ++str;
 697         else if (*str == '-') {
 698                 ++str;
 699                 sign = -1;
 700         }
 701         while (*str != '\0' && isspace(Py_CHARMASK(*str)))
 702                 str++;
 703         if (base == 0) {
 704                 if (str[0] != '0')
 705                         base = 10;
 706                 else if (str[1] == 'x' || str[1] == 'X')
 707                         base = 16;
 708                 else
 709                         base = 8;
 710         }
 711         if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
 712                 str += 2;
 713         z = _PyLong_New(0);
 714         start = str;
 715         for ( ; z != NULL; ++str) {
 716                 int k = -1;
 717                 PyLongObject *temp;
 718
 719                 if (*str <= '9')
 720                         k = *str - '0';
 721                 else if (*str >= 'a')
 722                         k = *str - 'a' + 10;
 723                 else if (*str >= 'A')
 724                         k = *str - 'A' + 10;
 725                 if (k < 0 || k >= base)
 726                         break;
 727                 temp = muladd1(z, (digit)base, (digit)k);
 728                 Py_DECREF(z);
 729                 z = temp;
 730         }
 731         if (z == NULL)
 732                 return NULL;
 733         if (str == start)
 734                 goto onError;
 735         if (sign < 0 && z != NULL && z->ob_size != 0)
 736                 z->ob_size = -(z->ob_size);
 737         if (*str == 'L' || *str == 'l')
 738                 str++;
 739         while (*str && isspace(Py_CHARMASK(*str)))
 740                 str++;
 741         if (*str != '\0')
 742                 goto onError;
 743         if (pend)
 744                 *pend = str;
 745         return (PyObject *) z;
 746
 747  onError:
 748         PyErr_Format(PyExc_ValueError,
 749                      "invalid literal for long(): %.200s", orig_str);
 750         Py_XDECREF(z);
 751         return NULL;
 752 }
 753
 754 PyObject *
 755 PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
 756 {
 757         char buffer[256];
 758
 759         if (length >= sizeof(buffer)) {
 760                 PyErr_SetString(PyExc_ValueError,
 761                                 "long() literal too large to convert");
 762                 return NULL;
 763         }
 764         if (PyUnicode_EncodeDecimal(u, length, buffer, NULL))
 765                 return NULL;
 766
 767         return PyLong_FromString(buffer, NULL, base);
 768 }
 769
 770 /* forward */
 771 static PyLongObject *x_divrem
 772         (PyLongObject *, PyLongObject *, PyLongObject **);
 773 static PyObject *long_pos(PyLongObject *);
 774 static int long_divrem(PyLongObject *, PyLongObject *,
 775         PyLongObject **, PyLongObject **);
 776
 777 /* Long division with remainder, top-level routine */
 778
 779 static int
 780 long_divrem(PyLongObject *a, PyLongObject *b,
 781             PyLongObject **pdiv, PyLongObject **prem)
 782 {
 783         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
 784         PyLongObject *z;
 785
 786         if (size_b == 0) {
 787                 PyErr_SetString(PyExc_ZeroDivisionError,
 788                                 "long division or modulo by zero");
 789                 return -1;
 790         }
 791         if (size_a < size_b ||
 792             (size_a == size_b &&
 793              a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
 794                 /* |a| < |b|. */
 795                 *pdiv = _PyLong_New(0);
 796                 Py_INCREF(a);
 797                 *prem = (PyLongObject *) a;
 798                 return 0;
 799         }
 800         if (size_b == 1) {
 801                 digit rem = 0;
 802                 z = divrem1(a, b->ob_digit[0], &rem);
 803                 if (z == NULL)
 804                         return -1;
 805                 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
 806         }
 807         else {
 808                 z = x_divrem(a, b, prem);
 809                 if (z == NULL)
 810                         return -1;
 811         }
 812         /* Set the signs.
 813            The quotient z has the sign of a*b;
 814            the remainder r has the sign of a,
 815            so a = b*z + r. */
 816         if ((a->ob_size < 0) != (b->ob_size < 0))
 817                 z->ob_size = -(z->ob_size);
 818         if (a->ob_size < 0 && (*prem)->ob_size != 0)
 819                 (*prem)->ob_size = -((*prem)->ob_size);
 820         *pdiv = z;
 821         return 0;
 822 }
 823
 824 /* Unsigned long division with remainder -- the algorithm */
 825
 826 static PyLongObject *
 827 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
 828 {
 829         int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size);
 830         digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
 831         PyLongObject *v = mul1(v1, d);
 832         PyLongObject *w = mul1(w1, d);
 833         PyLongObject *a;
 834         int j, k;
 835
 836         if (v == NULL || w == NULL) {
 837                 Py_XDECREF(v);
 838                 Py_XDECREF(w);
 839                 return NULL;
 840         }
 841
 842         assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
 843         assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
 844         assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */
 845
 846         size_v = ABS(v->ob_size);
 847         a = _PyLong_New(size_v - size_w + 1);
 848
 849         for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) {
 850                 digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
 851                 twodigits q;
 852                 stwodigits carry = 0;
 853                 int i;
 854
 855                 SIGCHECK({
 856                         Py_DECREF(a);
 857                         a = NULL;
 858                         break;
 859                 })
 860                 if (vj == w->ob_digit[size_w-1])
 861                         q = MASK;
 862                 else
 863                         q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
 864                                 w->ob_digit[size_w-1];
 865
 866                 while (w->ob_digit[size_w-2]*q >
 867                                 ((
 868                                         ((twodigits)vj << SHIFT)
 869                                         + v->ob_digit[j-1]
 870                                         - q*w->ob_digit[size_w-1]
 871                                                                 ) << SHIFT)
 872                                 + v->ob_digit[j-2])
 873                         --q;
 874
 875                 for (i = 0; i < size_w && i+k < size_v; ++i) {
 876                         twodigits z = w->ob_digit[i] * q;
 877                         digit zz = (digit) (z >> SHIFT);
 878                         carry += v->ob_digit[i+k] - z
 879                                 + ((twodigits)zz << SHIFT);
 880                         v->ob_digit[i+k] = carry & MASK;
 881                         carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
 882                                                           carry, SHIFT);
 883                         carry -= zz;
 884                 }
 885
 886                 if (i+k < size_v) {
 887                         carry += v->ob_digit[i+k];
 888                         v->ob_digit[i+k] = 0;
 889                 }
 890
 891                 if (carry == 0)
 892                         a->ob_digit[k] = (digit) q;
 893                 else {
 894                         assert(carry == -1);
 895                         a->ob_digit[k] = (digit) q-1;
 896                         carry = 0;
 897                         for (i = 0; i < size_w && i+k < size_v; ++i) {
 898                                 carry += v->ob_digit[i+k] + w->ob_digit[i];
 899                                 v->ob_digit[i+k] = carry & MASK;
 900                                 carry = Py_ARITHMETIC_RIGHT_SHIFT(
 901                                                 BASE_TWODIGITS_TYPE,
 902                                                 carry, SHIFT);
 903                         }
 904                 }
 905         } /* for j, k */
 906
 907         if (a == NULL)
 908                 *prem = NULL;
 909         else {
 910                 a = long_normalize(a);
 911                 *prem = divrem1(v, d, &d);
 912                 /* d receives the (unused) remainder */
 913                 if (*prem == NULL) {
 914                         Py_DECREF(a);
 915                         a = NULL;
 916                 }
 917         }
 918         Py_DECREF(v);
 919         Py_DECREF(w);
 920         return a;
 921 }
 922
 923 /* Methods */
 924
 925 static void
 926 long_dealloc(PyObject *v)
 927 {
 928         PyObject_DEL(v);
 929 }
 930
 931 static PyObject *
 932 long_repr(PyObject *v)
 933 {
 934         return long_format(v, 10, 1);
 935 }
 936
 937 static PyObject *
 938 long_str(PyObject *v)
 939 {
 940         return long_format(v, 10, 0);
 941 }
 942
 943 static int
 944 long_compare(PyLongObject *a, PyLongObject *b)
 945 {
 946         int sign;
 947
 948         if (a->ob_size != b->ob_size) {
 949                 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0)
 950                         sign = 0;
 951                 else
 952                         sign = a->ob_size - b->ob_size;
 953         }
 954         else {
 955                 int i = ABS(a->ob_size);
 956                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
 957                         ;
 958                 if (i < 0)
 959                         sign = 0;
 960                 else {
 961                         sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
 962                         if (a->ob_size < 0)
 963                                 sign = -sign;
 964                 }
 965         }
 966         return sign < 0 ? -1 : sign > 0 ? 1 : 0;
 967 }
 968
 969 static long
 970 long_hash(PyLongObject *v)
 971 {
 972         long x;
 973         int i, sign;
 974
 975         /* This is designed so that Python ints and longs with the
 976            same value hash to the same value, otherwise comparisons
 977            of mapping keys will turn out weird */
 978         i = v->ob_size;
 979         sign = 1;
 980         x = 0;
 981         if (i < 0) {
 982                 sign = -1;
 983                 i = -(i);
 984         }
 985         while (--i >= 0) {
 986                 /* Force a 32-bit circular shift */
 987                 x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK);
 988                 x += v->ob_digit[i];
 989         }
 990         x = x * sign;
 991         if (x == -1)
 992                 x = -2;
 993         return x;
 994 }
 995
 996
 997 /* Add the absolute values of two long integers. */
 998
 999 static PyLongObject *
1000 x_add(PyLongObject *a, PyLongObject *b)
1001 {
1002         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1003         PyLongObject *z;
1004         int i;
1005         digit carry = 0;
1006
1007         /* Ensure a is the larger of the two: */
1008         if (size_a < size_b) {
1009                 { PyLongObject *temp = a; a = b; b = temp; }
1010                 { int size_temp = size_a;
1011                   size_a = size_b;
1012                   size_b = size_temp; }
1013         }
1014         z = _PyLong_New(size_a+1);
1015         if (z == NULL)
1016                 return NULL;
1017         for (i = 0; i < size_b; ++i) {
1018                 carry += a->ob_digit[i] + b->ob_digit[i];
1019                 z->ob_digit[i] = carry & MASK;
1020                 carry >>= SHIFT;
1021         }
1022         for (; i < size_a; ++i) {
1023                 carry += a->ob_digit[i];
1024                 z->ob_digit[i] = carry & MASK;
1025                 carry >>= SHIFT;
1026         }
1027         z->ob_digit[i] = carry;
1028         return long_normalize(z);
1029 }
1030
1031 /* Subtract the absolute values of two integers. */
1032
1033 static PyLongObject *
1034 x_sub(PyLongObject *a, PyLongObject *b)
1035 {
1036         int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1037         PyLongObject *z;
1038         int i;
1039         int sign = 1;
1040         digit borrow = 0;
1041
1042         /* Ensure a is the larger of the two: */
1043         if (size_a < size_b) {
1044                 sign = -1;
1045                 { PyLongObject *temp = a; a = b; b = temp; }
1046                 { int size_temp = size_a;
1047                   size_a = size_b;
1048                   size_b = size_temp; }
1049         }
1050         else if (size_a == size_b) {
1051                 /* Find highest digit where a and b differ: */
1052                 i = size_a;
1053                 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1054                         ;
1055                 if (i < 0)
1056                         return _PyLong_New(0);
1057                 if (a->ob_digit[i] < b->ob_digit[i]) {
1058                         sign = -1;
1059                         { PyLongObject *temp = a; a = b; b = temp; }
1060                 }
1061                 size_a = size_b = i+1;
1062         }
1063         z = _PyLong_New(size_a);
1064         if (z == NULL)
1065                 return NULL;
1066         for (i = 0; i < size_b; ++i) {
1067                 /* The following assumes unsigned arithmetic
1068                    works module 2**N for some N>SHIFT. */
1069                 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
1070                 z->ob_digit[i] = borrow & MASK;
1071                 borrow >>= SHIFT;
1072                 borrow &= 1; /* Keep only one sign bit */
1073         }
1074         for (; i < size_a; ++i) {
1075                 borrow = a->ob_digit[i] - borrow;
1076                 z->ob_digit[i] = borrow & MASK;
1077                 borrow >>= SHIFT;
1078                 borrow &= 1; /* Keep only one sign bit */
1079         }
1080         assert(borrow == 0);
1081         if (sign < 0)
1082                 z->ob_size = -(z->ob_size);
1083         return long_normalize(z);
1084 }
1085
1086 static PyObject *
1087 long_add(PyLongObject *v, PyLongObject *w)
1088 {
1089         PyLongObject *a, *b, *z;
1090
1091         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1092
1093         if (a->ob_size < 0) {
1094                 if (b->ob_size < 0) {
1095                         z = x_add(a, b);
1096                         if (z != NULL && z->ob_size != 0)
1097                                 z->ob_size = -(z->ob_size);
1098                 }
1099                 else
1100                         z = x_sub(b, a);
1101         }
1102         else {
1103                 if (b->ob_size < 0)
1104                         z = x_sub(a, b);
1105                 else
1106                         z = x_add(a, b);
1107         }
1108         Py_DECREF(a);
1109         Py_DECREF(b);
1110         return (PyObject *)z;
1111 }
1112
1113 static PyObject *
1114 long_sub(PyLongObject *v, PyLongObject *w)
1115 {
1116         PyLongObject *a, *b, *z;
1117
1118         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1119
1120         if (a->ob_size < 0) {
1121                 if (b->ob_size < 0)
1122                         z = x_sub(a, b);
1123                 else
1124                         z = x_add(a, b);
1125                 if (z != NULL && z->ob_size != 0)
1126                         z->ob_size = -(z->ob_size);
1127         }
1128         else {
1129                 if (b->ob_size < 0)
1130                         z = x_add(a, b);
1131                 else
1132                         z = x_sub(a, b);
1133         }
1134         Py_DECREF(a);
1135         Py_DECREF(b);
1136         return (PyObject *)z;
1137 }
1138
1139 static PyObject *
1140 long_repeat(PyObject *v, PyLongObject *w)
1141 {
1142         /* sequence * long */
1143         long n = PyLong_AsLong((PyObject *) w);
1144         if (n == -1 && PyErr_Occurred())
1145                 return NULL;
1146         else
1147                 return (*v->ob_type->tp_as_sequence->sq_repeat)(v, n);
1148 }
1149
1150 static PyObject *
1151 long_mul(PyLongObject *v, PyLongObject *w)
1152 {
1153         PyLongObject *a, *b, *z;
1154         int size_a;
1155         int size_b;
1156         int i;
1157
1158         if (v->ob_type->tp_as_sequence &&
1159                         v->ob_type->tp_as_sequence->sq_repeat) {
1160                 return long_repeat((PyObject *)v, w);
1161         }
1162         else if (w->ob_type->tp_as_sequence &&
1163                         w->ob_type->tp_as_sequence->sq_repeat) {
1164                 return long_repeat((PyObject *)w, v);
1165         }
1166
1167         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1168
1169         size_a = ABS(a->ob_size);
1170         size_b = ABS(b->ob_size);
1171         if (size_a > size_b) {
1172                 /* we are faster with the small object on the left */
1173                 int hold_sa = size_a;
1174                 PyLongObject *hold_a = a;
1175                 size_a = size_b;
1176                 size_b = hold_sa;
1177                 a = b;
1178                 b = hold_a;
1179         }
1180         z = _PyLong_New(size_a + size_b);
1181         if (z == NULL) {
1182                 Py_DECREF(a);
1183                 Py_DECREF(b);
1184                 return NULL;
1185         }
1186         for (i = 0; i < z->ob_size; ++i)
1187                 z->ob_digit[i] = 0;
1188         for (i = 0; i < size_a; ++i) {
1189                 twodigits carry = 0;
1190                 twodigits f = a->ob_digit[i];
1191                 int j;
1192
1193                 SIGCHECK({
1194                         Py_DECREF(a);
1195                         Py_DECREF(b);
1196                         Py_DECREF(z);
1197                         return NULL;
1198                 })
1199                 for (j = 0; j < size_b; ++j) {
1200                         carry += z->ob_digit[i+j] + b->ob_digit[j] * f;
1201                         z->ob_digit[i+j] = (digit) (carry & MASK);
1202                         carry >>= SHIFT;
1203                 }
1204                 for (; carry != 0; ++j) {
1205                         assert(i+j < z->ob_size);
1206                         carry += z->ob_digit[i+j];
1207                         z->ob_digit[i+j] = (digit) (carry & MASK);
1208                         carry >>= SHIFT;
1209                 }
1210         }
1211         if (a->ob_size < 0)
1212                 z->ob_size = -(z->ob_size);
1213         if (b->ob_size < 0)
1214                 z->ob_size = -(z->ob_size);
1215         Py_DECREF(a);
1216         Py_DECREF(b);
1217         return (PyObject *) long_normalize(z);
1218 }
1219
1220 /* The / and % operators are now defined in terms of divmod().
1221    The expression a mod b has the value a - b*floor(a/b).
1222    The long_divrem function gives the remainder after division of
1223    |a| by |b|, with the sign of a.  This is also expressed
1224    as a - b*trunc(a/b), if trunc truncates towards zero.
1225    Some examples:
1226          a       b      a rem b         a mod b
1227          13      10      3               3
1228         -13      10     -3               7
1229          13     -10      3              -7
1230         -13     -10     -3              -3
1231    So, to get from rem to mod, we have to add b if a and b
1232    have different signs.  We then subtract one from the 'div'
1233    part of the outcome to keep the invariant intact. */
1234
1235 static int
1236 l_divmod(PyLongObject *v, PyLongObject *w,
1237          PyLongObject **pdiv, PyLongObject **pmod)
1238 {
1239         PyLongObject *div, *mod;
1240
1241         if (long_divrem(v, w, &div, &mod) < 0)
1242                 return -1;
1243         if ((mod->ob_size < 0 && w->ob_size > 0) ||
1244             (mod->ob_size > 0 && w->ob_size < 0)) {
1245                 PyLongObject *temp;
1246                 PyLongObject *one;
1247                 temp = (PyLongObject *) long_add(mod, w);
1248                 Py_DECREF(mod);
1249                 mod = temp;
1250                 if (mod == NULL) {
1251                         Py_DECREF(div);
1252                         return -1;
1253                 }
1254                 one = (PyLongObject *) PyLong_FromLong(1L);
1255                 if (one == NULL ||
1256                     (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
1257                         Py_DECREF(mod);
1258                         Py_DECREF(div);
1259                         Py_XDECREF(one);
1260                         return -1;
1261                 }
1262                 Py_DECREF(one);
1263                 Py_DECREF(div);
1264                 div = temp;
1265         }
1266         *pdiv = div;
1267         *pmod = mod;
1268         return 0;
1269 }
1270
1271 static PyObject *
1272 long_div(PyObject *v, PyObject *w)
1273 {
1274         PyLongObject *a, *b, *div, *mod;
1275
1276         CONVERT_BINOP(v, w, &a, &b);
1277
1278         if (l_divmod(a, b, &div, &mod) < 0) {
1279                 Py_DECREF(a);
1280                 Py_DECREF(b);
1281                 return NULL;
1282         }
1283         Py_DECREF(a);
1284         Py_DECREF(b);
1285         Py_DECREF(mod);
1286         return (PyObject *)div;
1287 }
1288
1289 static PyObject *
1290 long_mod(PyObject *v, PyObject *w)
1291 {
1292         PyLongObject *a, *b, *div, *mod;
1293
1294         CONVERT_BINOP(v, w, &a, &b);
1295
1296         if (l_divmod(a, b, &div, &mod) < 0) {
1297                 Py_DECREF(a);
1298                 Py_DECREF(b);
1299                 return NULL;
1300         }
1301         Py_DECREF(a);
1302         Py_DECREF(b);
1303         Py_DECREF(div);
1304         return (PyObject *)mod;
1305 }
1306
1307 static PyObject *
1308 long_divmod(PyObject *v, PyObject *w)
1309 {
1310         PyLongObject *a, *b, *div, *mod;
1311         PyObject *z;
1312
1313         CONVERT_BINOP(v, w, &a, &b);
1314
1315         if (l_divmod(a, b, &div, &mod) < 0) {
1316                 Py_DECREF(a);
1317                 Py_DECREF(b);
1318                 return NULL;
1319         }
1320         z = PyTuple_New(2);
1321         if (z != NULL) {
1322                 PyTuple_SetItem(z, 0, (PyObject *) div);
1323                 PyTuple_SetItem(z, 1, (PyObject *) mod);
1324         }
1325         else {
1326                 Py_DECREF(div);
1327                 Py_DECREF(mod);
1328         }
1329         Py_DECREF(a);
1330         Py_DECREF(b);
1331         return z;
1332 }
1333
1334 static PyObject *
1335 long_pow(PyObject *v, PyObject *w, PyObject *x)
1336 {
1337         PyLongObject *a, *b;
1338         PyObject *c;
1339         PyLongObject *z, *div, *mod;
1340         int size_b, i;
1341
1342         CONVERT_BINOP(v, w, &a, &b);
1343         if (PyLong_Check(x) || Py_None == x) {
1344                 c = x;
1345                 Py_INCREF(x);
1346         }
1347         else if (PyInt_Check(x)) {
1348                 c = PyLong_FromLong(PyInt_AS_LONG(x));
1349         }
1350         else {
1351                 Py_DECREF(a);
1352                 Py_DECREF(b);
1353                 Py_INCREF(Py_NotImplemented);
1354                 return Py_NotImplemented;
1355         }
1356
1357         size_b = b->ob_size;
1358         if (size_b < 0) {
1359                 if (a->ob_size)
1360                         PyErr_SetString(PyExc_ValueError,
1361                                         "long integer to a negative power");
1362                 else
1363                         PyErr_SetString(PyExc_ZeroDivisionError,
1364                                         "zero to a negative power");
1365                 z = NULL;
1366                 goto error;
1367         }
1368         z = (PyLongObject *)PyLong_FromLong(1L);
1369         for (i = 0; i < size_b; ++i) {
1370                 digit bi = b->ob_digit[i];
1371                 int j;
1372
1373                 for (j = 0; j < SHIFT; ++j) {
1374                         PyLongObject *temp;
1375
1376                         if (bi & 1) {
1377                                 temp = (PyLongObject *)long_mul(z, a);
1378                                 Py_DECREF(z);
1379                                 if (c!=Py_None && temp!=NULL) {
1380                                         if (l_divmod(temp,(PyLongObject *)c,
1381                                                         &div,&mod) < 0) {
1382                                                 Py_DECREF(temp);
1383                                                 z = NULL;
1384                                                 goto error;
1385                                         }
1386                                         Py_XDECREF(div);
1387                                         Py_DECREF(temp);
1388                                         temp = mod;
1389                                 }
1390                                 z = temp;
1391                                 if (z == NULL)
1392                                         break;
1393                         }
1394                         bi >>= 1;
1395                         if (bi == 0 && i+1 == size_b)
1396                                 break;
1397                         temp = (PyLongObject *)long_mul(a, a);
1398                         Py_DECREF(a);
1399                         if (c!=Py_None && temp!=NULL) {
1400                                 if (l_divmod(temp, (PyLongObject *)c, &div,
1401                                                         &mod) < 0) {
1402                                         Py_DECREF(temp);
1403                                         z = NULL;
1404                                         goto error;
1405                                 }
1406                                 Py_XDECREF(div);
1407                                 Py_DECREF(temp);
1408                                 temp = mod;
1409                         }
1410                         a = temp;
1411                         if (a == NULL) {
1412                                 Py_DECREF(z);
1413                                 z = NULL;
1414                                 break;
1415                         }
1416                 }
1417                 if (a == NULL || z == NULL)
1418                         break;
1419         }
1420         if (c!=Py_None && z!=NULL) {
1421                 if (l_divmod(z, (PyLongObject *)c, &div, &mod) < 0) {
1422                         Py_DECREF(z);
1423                         z = NULL;
1424                 }
1425                 else {
1426                         Py_XDECREF(div);
1427                         Py_DECREF(z);
1428                         z = mod;
1429                 }
1430         }
1431   error:
1432         Py_XDECREF(a);
1433         Py_DECREF(b);
1434         Py_DECREF(c);
1435         return (PyObject *)z;
1436 }
1437
1438 static PyObject *
1439 long_invert(PyLongObject *v)
1440 {
1441         /* Implement ~x as -(x+1) */
1442         PyLongObject *x;
1443         PyLongObject *w;
1444         w = (PyLongObject *)PyLong_FromLong(1L);
1445         if (w == NULL)
1446                 return NULL;
1447         x = (PyLongObject *) long_add(v, w);
1448         Py_DECREF(w);
1449         if (x == NULL)
1450                 return NULL;
1451         if (x->ob_size != 0)
1452                 x->ob_size = -(x->ob_size);
1453         return (PyObject *)x;
1454 }
1455
1456 static PyObject *
1457 long_pos(PyLongObject *v)
1458 {
1459         Py_INCREF(v);
1460         return (PyObject *)v;
1461 }
1462
1463 static PyObject *
1464 long_neg(PyLongObject *v)
1465 {
1466         PyLongObject *z;
1467         int i, n;
1468         n = ABS(v->ob_size);
1469         if (n == 0) {
1470                 /* -0 == 0 */
1471                 Py_INCREF(v);
1472                 return (PyObject *) v;
1473         }
1474         z = _PyLong_New(ABS(n));
1475         if (z == NULL)
1476                 return NULL;
1477         for (i = 0; i < n; i++)
1478                 z->ob_digit[i] = v->ob_digit[i];
1479         z->ob_size = -(v->ob_size);
1480         return (PyObject *)z;
1481 }
1482
1483 static PyObject *
1484 long_abs(PyLongObject *v)
1485 {
1486         if (v->ob_size < 0)
1487                 return long_neg(v);
1488         else {
1489                 Py_INCREF(v);
1490                 return (PyObject *)v;
1491         }
1492 }
1493
1494 static int
1495 long_nonzero(PyLongObject *v)
1496 {
1497         return ABS(v->ob_size) != 0;
1498 }
1499
1500 static PyObject *
1501 long_rshift(PyLongObject *v, PyLongObject *w)
1502 {
1503         PyLongObject *a, *b;
1504         PyLongObject *z = NULL;
1505         long shiftby;
1506         int newsize, wordshift, loshift, hishift, i, j;
1507         digit lomask, himask;
1508
1509         CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1510
1511         if (a->ob_size < 0) {
1512                 /* Right shifting negative numbers is harder */
1513                 PyLongObject *a1, *a2;
1514                 a1 = (PyLongObject *) long_invert(a);
1515                 if (a1 == NULL)
1516                         goto rshift_error;
1517                 a2 = (PyLongObject *) long_rshift(a1, b);
1518                 Py_DECREF(a1);
1519                 if (a2 == NULL)
1520                         goto rshift_error;
1521                 z = (PyLongObject *) long_invert(a2);
1522                 Py_DECREF(a2);
1523         }
1524         else {
1525
1526                 shiftby = PyLong_AsLong((PyObject *)b);
1527                 if (shiftby == -1L && PyErr_Occurred())
1528                         goto rshift_error;
1529                 if (shiftby < 0) {
1530                         PyErr_SetString(PyExc_ValueError,
1531                                         "negative shift count");
1532                         goto rshift_error;
1533                 }
1534                 wordshift = shiftby / SHIFT;
1535                 newsize = ABS(a->ob_size) - wordshift;
1536                 if (newsize <= 0) {
1537                         z = _PyLong_New(0);
1538                         Py_DECREF(a);
1539                         Py_DECREF(b);
1540                         return (PyObject *)z;
1541                 }
1542                 loshift = shiftby % SHIFT;
1543                 hishift = SHIFT - loshift;
1544                 lomask = ((digit)1 << hishift) - 1;
1545                 himask = MASK ^ lomask;
1546                 z = _PyLong_New(newsize);
1547                 if (z == NULL)
1548                         goto rshift_error;
1549                 if (a->ob_size < 0)
1550                         z->ob_size = -(z->ob_size);
1551                 for (i = 0, j = wordshift; i < newsize; i++, j++) {
1552                         z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
1553                         if (i+1 < newsize)
1554                                 z->ob_digit[i] |=
1555                                   (a->ob_digit[j+1] << hishift) & himask;
1556                 }
1557                 z = long_normalize(z);
1558         }
1559 rshift_error:
1560         Py_DECREF(a);
1561         Py_DECREF(b);
1562         return (PyObject *) z;
1563
1564 }
1565
1566 static PyObject *
1567 long_lshift(PyObject *v, PyObject *w)
1568 {
1569         /* This version due to Tim Peters */
1570         PyLongObject *a, *b;
1571         PyLongObject *z = NULL;
1572         long shiftby;
1573         int oldsize, newsize, wordshift, remshift, i, j;
1574         twodigits accum;
1575
1576         CONVERT_BINOP(v, w, &a, &b);
1577
1578         shiftby = PyLong_AsLong((PyObject *)b);
1579         if (shiftby == -1L && PyErr_Occurred())
1580                 goto lshift_error;
1581         if (shiftby < 0) {
1582                 PyErr_SetString(PyExc_ValueError, "negative shift count");
1583                 goto lshift_error;
1584         }
1585         if ((long)(int)shiftby != shiftby) {
1586                 PyErr_SetString(PyExc_ValueError,
1587                                 "outrageous left shift count");
1588                 goto lshift_error;
1589         }
1590         /* wordshift, remshift = divmod(shiftby, SHIFT) */
1591         wordshift = (int)shiftby / SHIFT;
1592         remshift  = (int)shiftby - wordshift * SHIFT;
1593
1594         oldsize = ABS(a->ob_size);
1595         newsize = oldsize + wordshift;
1596         if (remshift)
1597                 ++newsize;
1598         z = _PyLong_New(newsize);
1599         if (z == NULL)
1600                 goto lshift_error;
1601         if (a->ob_size < 0)
1602                 z->ob_size = -(z->ob_size);
1603         for (i = 0; i < wordshift; i++)
1604                 z->ob_digit[i] = 0;
1605         accum = 0;
1606         for (i = wordshift, j = 0; j < oldsize; i++, j++) {
1607                 accum |= a->ob_digit[j] << remshift;
1608                 z->ob_digit[i] = (digit)(accum & MASK);
1609                 accum >>= SHIFT;
1610         }
1611         if (remshift)
1612                 z->ob_digit[newsize-1] = (digit)accum;
1613         else
1614                 assert(!accum);
1615         z = long_normalize(z);
1616 lshift_error:
1617         Py_DECREF(a);
1618         Py_DECREF(b);
1619         return (PyObject *) z;
1620 }
1621
1622
1623 /* Bitwise and/xor/or operations */
1624
1625 #define MAX(x, y) ((x) < (y) ? (y) : (x))
1626 #define MIN(x, y) ((x) > (y) ? (y) : (x))
1627
1628 static PyObject *
1629 long_bitwise(PyLongObject *a,
1630              int op,  /* '&', '|', '^' */
1631              PyLongObject *b)
1632 {
1633         digit maska, maskb; /* 0 or MASK */
1634         int negz;
1635         int size_a, size_b, size_z;
1636         PyLongObject *z;
1637         int i;
1638         digit diga, digb;
1639         PyObject *v;
1640
1641         if (a->ob_size < 0) {
1642                 a = (PyLongObject *) long_invert(a);
1643                 maska = MASK;
1644         }
1645         else {
1646                 Py_INCREF(a);
1647                 maska = 0;
1648         }
1649         if (b->ob_size < 0) {
1650                 b = (PyLongObject *) long_invert(b);
1651                 maskb = MASK;
1652         }
1653         else {
1654                 Py_INCREF(b);
1655                 maskb = 0;
1656         }
1657
1658         negz = 0;
1659         switch (op) {
1660         case '^':
1661                 if (maska != maskb) {
1662                         maska ^= MASK;
1663                         negz = -1;
1664                 }
1665                 break;
1666         case '&':
1667                 if (maska && maskb) {
1668                         op = '|';
1669                         maska ^= MASK;
1670                         maskb ^= MASK;
1671                         negz = -1;
1672                 }
1673                 break;
1674         case '|':
1675                 if (maska || maskb) {
1676                         op = '&';
1677                         maska ^= MASK;
1678                         maskb ^= MASK;
1679                         negz = -1;
1680                 }
1681                 break;
1682         }
1683
1684         /* JRH: The original logic here was to allocate the result value (z)
1685            as the longer of the two operands.  However, there are some cases
1686            where the result is guaranteed to be shorter than that: AND of two
1687            positives, OR of two negatives: use the shorter number.  AND with
1688            mixed signs: use the positive number.  OR with mixed signs: use the
1689            negative number.  After the transformations above, op will be '&'
1690            iff one of these cases applies, and mask will be non-0 for operands
1691            whose length should be ignored.
1692         */
1693
1694         size_a = a->ob_size;
1695         size_b = b->ob_size;
1696         size_z = op == '&'
1697                 ? (maska
1698                    ? size_b
1699                    : (maskb ? size_a : MIN(size_a, size_b)))
1700                 : MAX(size_a, size_b);
1701         z = _PyLong_New(size_z);
1702         if (a == NULL || b == NULL || z == NULL) {
1703                 Py_XDECREF(a);
1704                 Py_XDECREF(b);
1705                 Py_XDECREF(z);
1706                 return NULL;
1707         }
1708
1709         for (i = 0; i < size_z; ++i) {
1710                 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
1711                 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
1712                 switch (op) {
1713                 case '&': z->ob_digit[i] = diga & digb; break;
1714                 case '|': z->ob_digit[i] = diga | digb; break;
1715                 case '^': z->ob_digit[i] = diga ^ digb; break;
1716                 }
1717         }
1718
1719         Py_DECREF(a);
1720         Py_DECREF(b);
1721         z = long_normalize(z);
1722         if (negz == 0)
1723                 return (PyObject *) z;
1724         v = long_invert(z);
1725         Py_DECREF(z);
1726         return v;
1727 }
1728
1729 static PyObject *
1730 long_and(PyObject *v, PyObject *w)
1731 {
1732         PyLongObject *a, *b;
1733         PyObject *c;
1734         CONVERT_BINOP(v, w, &a, &b);
1735         c = long_bitwise(a, '&', b);
1736         Py_DECREF(a);
1737         Py_DECREF(b);
1738         return c;
1739 }
1740
1741 static PyObject *
1742 long_xor(PyObject *v, PyObject *w)
1743 {
1744         PyLongObject *a, *b;
1745         PyObject *c;
1746         CONVERT_BINOP(v, w, &a, &b);
1747         c = long_bitwise(a, '^', b);
1748         Py_DECREF(a);
1749         Py_DECREF(b);
1750         return c;
1751 }
1752
1753 static PyObject *
1754 long_or(PyObject *v, PyObject *w)
1755 {
1756         PyLongObject *a, *b;
1757         PyObject *c;
1758         CONVERT_BINOP(v, w, &a, &b);
1759         c = long_bitwise(a, '|', b);
1760         Py_DECREF(a);
1761         Py_DECREF(b);
1762         return c;
1763 }
1764
1765 static int
1766 long_coerce(PyObject **pv, PyObject **pw)
1767 {
1768         if (PyInt_Check(*pw)) {
1769                 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
1770                 Py_INCREF(*pv);
1771                 return 0;
1772         }
1773         return 1; /* Can't do it */
1774 }
1775
1776 static PyObject *
1777 long_int(PyObject *v)
1778 {
1779         long x;
1780         x = PyLong_AsLong(v);
1781         if (PyErr_Occurred())
1782                 return NULL;
1783         return PyInt_FromLong(x);
1784 }
1785
1786 static PyObject *
1787 long_long(PyObject *v)
1788 {
1789         Py_INCREF(v);
1790         return v;
1791 }
1792
1793 static PyObject *
1794 long_float(PyObject *v)
1795 {
1796         double result;
1797         PyFPE_START_PROTECT("long_float", return 0)
1798         result = PyLong_AsDouble(v);
1799         PyFPE_END_PROTECT(result)
1800         return PyFloat_FromDouble(result);
1801 }
1802
1803 static PyObject *
1804 long_oct(PyObject *v)
1805 {
1806         return long_format(v, 8, 1);
1807 }
1808
1809 static PyObject *
1810 long_hex(PyObject *v)
1811 {
1812         return long_format(v, 16, 1);
1813 }
1814
1815 static PyNumberMethods long_as_number = {
1816         (binaryfunc)    long_add,       /*nb_add*/
1817         (binaryfunc)    long_sub,       /*nb_subtract*/
1818         (binaryfunc)    long_mul,       /*nb_multiply*/
1819         (binaryfunc)    long_div,       /*nb_divide*/
1820         (binaryfunc)    long_mod,       /*nb_remainder*/
1821         (binaryfunc)    long_divmod,    /*nb_divmod*/
1822         (ternaryfunc)   long_pow,       /*nb_power*/
1823         (unaryfunc)     long_neg,       /*nb_negative*/
1824         (unaryfunc)     long_pos,       /*tp_positive*/
1825         (unaryfunc)     long_abs,       /*tp_absolute*/
1826         (inquiry)       long_nonzero,   /*tp_nonzero*/
1827         (unaryfunc)     long_invert,    /*nb_invert*/
1828         (binaryfunc)    long_lshift,    /*nb_lshift*/
1829         (binaryfunc)    long_rshift,    /*nb_rshift*/
1830         (binaryfunc)    long_and,       /*nb_and*/
1831         (binaryfunc)    long_xor,       /*nb_xor*/
1832         (binaryfunc)    long_or,        /*nb_or*/
1833         (coercion)      long_coerce,    /*nb_coerce*/
1834         (unaryfunc)     long_int,       /*nb_int*/
1835         (unaryfunc)     long_long,      /*nb_long*/
1836         (unaryfunc)     long_float,     /*nb_float*/
1837         (unaryfunc)     long_oct,       /*nb_oct*/
1838         (unaryfunc)     long_hex,       /*nb_hex*/
1839         0,                              /*nb_inplace_add*/
1840         0,                              /*nb_inplace_subtract*/
1841         0,                              /*nb_inplace_multiply*/
1842         0,                              /*nb_inplace_divide*/
1843         0,                              /*nb_inplace_remainder*/
1844         0,                              /*nb_inplace_power*/
1845         0,                              /*nb_inplace_lshift*/
1846         0,                              /*nb_inplace_rshift*/
1847         0,                              /*nb_inplace_and*/
1848         0,                              /*nb_inplace_xor*/
1849         0,                              /*nb_inplace_or*/
1850 };
1851
1852 PyTypeObject PyLong_Type = {
1853         PyObject_HEAD_INIT(&PyType_Type)
1854         0,
1855         "long int",
1856         sizeof(PyLongObject) - sizeof(digit),
1857         sizeof(digit),
1858         (destructor)long_dealloc,       /*tp_dealloc*/
1859         0,                              /*tp_print*/
1860         0,                              /*tp_getattr*/
1861         0,                              /*tp_setattr*/
1862         (cmpfunc)long_compare,          /*tp_compare*/
1863         (reprfunc)long_repr,            /*tp_repr*/
1864         &long_as_number,                /*tp_as_number*/
1865         0,                              /*tp_as_sequence*/
1866         0,                              /*tp_as_mapping*/
1867         (hashfunc)long_hash,            /*tp_hash*/
1868         0,                              /*tp_call*/
1869         (reprfunc)long_str,             /*tp_str*/
1870         0,                              /*tp_getattro*/
1871         0,                              /*tp_setattro*/
1872         0,                              /*tp_as_buffer*/
1873         Py_TPFLAGS_CHECKTYPES           /*tp_flags*/
1874 };