Objects/longobject.c

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