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