Objects/longobject.c

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