?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
This commit was manufactured by cvs2svn to create tag
[python/dscho.git] / Objects / longobject.c
blob899c9405bf734fbfca26ad06f2e4bdba62ad54e9
1
2 /* Long (arbitrary precision) integer object implementation */
3
4 /* XXX The functional organization of this file is terrible */
5
6 #include "Python.h"
7 #include "longintrepr.h"
8
9 #include <ctype.h>
10
11 #define ABS(x) ((x) < 0 ? -(x) : (x))
12
13 /* Forward */
14 static PyLongObject *long_normalize(PyLongObject *);
15 static PyLongObject *mul1(PyLongObject *, wdigit);
16 static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
17 static PyLongObject *divrem1(PyLongObject *, digit, digit *);
18 static PyObject *long_format(PyObject *aa, int base, int addL);
19
20 static int ticker; /* XXX Could be shared with ceval? */
21
22 #define SIGCHECK(PyTryBlock) \
23 if (--ticker < 0) { \
24 ticker = 100; \
25 if (PyErr_CheckSignals()) { PyTryBlock; } \
26 }
27
28 /* Normalize (remove leading zeros from) a long int object.
29 Doesn't attempt to free the storage--in most cases, due to the nature
30 of the algorithms used, this could save at most be one word anyway. */
31
32 static PyLongObject *
33 long_normalize(register PyLongObject *v)
34 {
35 int j = ABS(v->ob_size);
36 register int i = j;
37
38 while (i > 0 && v->ob_digit[i-1] == 0)
39 --i;
40 if (i != j)
41 v->ob_size = (v->ob_size < 0) ? -(i) : i;
42 return v;
43 }
44
45 /* Allocate a new long int object with size digits.
46 Return NULL and set exception if we run out of memory. */
47
48 PyLongObject *
49 _PyLong_New(int size)
50 {
51 return PyObject_NEW_VAR(PyLongObject, &PyLong_Type, size);
52 }
53
54 PyObject *
55 _PyLong_Copy(PyLongObject *src)
56 {
57 PyLongObject *result;
58 int i;
59
60 assert(src != NULL);
61 i = src->ob_size;
62 if (i < 0)
63 i = -(i);
64 result = _PyLong_New(i);
65 if (result != NULL) {
66 result->ob_size = i;
67 while (--i >= 0)
68 result->ob_digit[i] = src->ob_digit[i];
69 }
70 return (PyObject *)result;
71 }
72
73 /* Create a new long int object from a C long int */
74
75 PyObject *
76 PyLong_FromLong(long ival)
77 {
78 PyLongObject *v;
79 unsigned long t; /* unsigned so >> doesn't propagate sign bit */
80 int ndigits = 0;
81 int negative = 0;
82
83 if (ival < 0) {
84 ival = -ival;
85 negative = 1;
86 }
87
88 /* Count the number of Python digits.
89 We used to pick 5 ("big enough for anything"), but that's a
90 waste of time and space given that 5*15 = 75 bits are rarely
91 needed. */
92 t = (unsigned long)ival;
93 while (t) {
94 ++ndigits;
95 t >>= SHIFT;
96 }
97 v = _PyLong_New(ndigits);
98 if (v != NULL) {
99 digit *p = v->ob_digit;
100 v->ob_size = negative ? -ndigits : ndigits;
101 t = (unsigned long)ival;
102 while (t) {
103 *p++ = (digit)(t & MASK);
104 t >>= SHIFT;
105 }
106 }
107 return (PyObject *)v;
108 }
109
110 /* Create a new long int object from a C unsigned long int */
111
112 PyObject *
113 PyLong_FromUnsignedLong(unsigned long ival)
114 {
115 PyLongObject *v;
116 unsigned long t;
117 int ndigits = 0;
118
119 /* Count the number of Python digits. */
120 t = (unsigned long)ival;
121 while (t) {
122 ++ndigits;
123 t >>= SHIFT;
124 }
125 v = _PyLong_New(ndigits);
126 if (v != NULL) {
127 digit *p = v->ob_digit;
128 v->ob_size = ndigits;
129 while (ival) {
130 *p++ = (digit)(ival & MASK);
131 ival >>= SHIFT;
132 }
133 }
134 return (PyObject *)v;
135 }
136
137 /* Create a new long int object from a C double */
138
139 PyObject *
140 PyLong_FromDouble(double dval)
141 {
142 PyLongObject *v;
143 double frac;
144 int i, ndig, expo, neg;
145 neg = 0;
146 if (Py_IS_INFINITY(dval)) {
147 PyErr_SetString(PyExc_OverflowError,
148 "cannot convert float infinity to long");
149 return NULL;
150 }
151 if (dval < 0.0) {
152 neg = 1;
153 dval = -dval;
154 }
155 frac = frexp(dval, &expo); /* dval = frac*2**expo; 0.0 <= frac < 1.0 */
156 if (expo <= 0)
157 return PyLong_FromLong(0L);
158 ndig = (expo-1) / SHIFT + 1; /* Number of 'digits' in result */
159 v = _PyLong_New(ndig);
160 if (v == NULL)
161 return NULL;
162 frac = ldexp(frac, (expo-1) % SHIFT + 1);
163 for (i = ndig; --i >= 0; ) {
164 long bits = (long)frac;
165 v->ob_digit[i] = (digit) bits;
166 frac = frac - (double)bits;
167 frac = ldexp(frac, SHIFT);
168 }
169 if (neg)
170 v->ob_size = -(v->ob_size);
171 return (PyObject *)v;
172 }
173
174 /* Get a C long int from a long int object.
175 Returns -1 and sets an error condition if overflow occurs. */
176
177 long
178 PyLong_AsLong(PyObject *vv)
179 {
180 /* This version by Tim Peters */
181 register PyLongObject *v;
182 unsigned long x, prev;
183 int i, sign;
184
185 if (vv == NULL || !PyLong_Check(vv)) {
186 if (vv != NULL && PyInt_Check(vv))
187 return PyInt_AsLong(vv);
188 PyErr_BadInternalCall();
189 return -1;
190 }
191 v = (PyLongObject *)vv;
192 i = v->ob_size;
193 sign = 1;
194 x = 0;
195 if (i < 0) {
196 sign = -1;
197 i = -(i);
198 }
199 while (--i >= 0) {
200 prev = x;
201 x = (x << SHIFT) + v->ob_digit[i];
202 if ((x >> SHIFT) != prev)
203 goto overflow;
204 }
205 /* Haven't lost any bits, but if the sign bit is set we're in
206 * trouble *unless* this is the min negative number. So,
207 * trouble iff sign bit set && (positive || some bit set other
208 * than the sign bit).
209 */
210 if ((long)x < 0 && (sign > 0 || (x << 1) != 0))
211 goto overflow;
212 return (long)x * sign;
213
214 overflow:
215 PyErr_SetString(PyExc_OverflowError,
216 "long int too large to convert to int");
217 return -1;
218 }
219
220 /* Get a C long int from a long int object.
221 Returns -1 and sets an error condition if overflow occurs. */
222
223 unsigned long
224 PyLong_AsUnsignedLong(PyObject *vv)
225 {
226 register PyLongObject *v;
227 unsigned long x, prev;
228 int i;
229
230 if (vv == NULL || !PyLong_Check(vv)) {
231 PyErr_BadInternalCall();
232 return (unsigned long) -1;
233 }
234 v = (PyLongObject *)vv;
235 i = v->ob_size;
236 x = 0;
237 if (i < 0) {
238 PyErr_SetString(PyExc_OverflowError,
239 "can't convert negative value to unsigned long");
240 return (unsigned long) -1;
241 }
242 while (--i >= 0) {
243 prev = x;
244 x = (x << SHIFT) + v->ob_digit[i];
245 if ((x >> SHIFT) != prev) {
246 PyErr_SetString(PyExc_OverflowError,
247 "long int too large to convert");
248 return (unsigned long) -1;
249 }
250 }
251 return x;
252 }
253
254 PyObject *
255 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
256 int little_endian, int is_signed)
257 {
258 const unsigned char* pstartbyte;/* LSB of bytes */
259 int incr; /* direction to move pstartbyte */
260 const unsigned char* pendbyte; /* MSB of bytes */
261 size_t numsignificantbytes; /* number of bytes that matter */
262 size_t ndigits; /* number of Python long digits */
263 PyLongObject* v; /* result */
264 int idigit = 0; /* next free index in v->ob_digit */
265
266 if (n == 0)
267 return PyLong_FromLong(0L);
268
269 if (little_endian) {
270 pstartbyte = bytes;
271 pendbyte = bytes + n - 1;
272 incr = 1;
273 }
274 else {
275 pstartbyte = bytes + n - 1;
276 pendbyte = bytes;
277 incr = -1;
278 }
279
280 if (is_signed)
281 is_signed = *pendbyte >= 0x80;
282
283 /* Compute numsignificantbytes. This consists of finding the most
284 significant byte. Leading 0 bytes are insignficant if the number
285 is positive, and leading 0xff bytes if negative. */
286 {
287 size_t i;
288 const unsigned char* p = pendbyte;
289 const int pincr = -incr; /* search MSB to LSB */
290 const unsigned char insignficant = is_signed ? 0xff : 0x00;
291
292 for (i = 0; i < n; ++i, p += pincr) {
293 if (*p != insignficant)
294 break;
295 }
296 numsignificantbytes = n - i;
297 /* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
298 actually has 2 significant bytes. OTOH, 0xff0001 ==
299 -0x00ffff, so we wouldn't *need* to bump it there; but we
300 do for 0xffff = -0x0001. To be safe without bothering to
301 check every case, bump it regardless. */
302 if (is_signed && numsignificantbytes < n)
303 ++numsignificantbytes;
304 }
305
306 /* How many Python long digits do we need? We have
307 8*numsignificantbytes bits, and each Python long digit has SHIFT
308 bits, so it's the ceiling of the quotient. */
309 ndigits = (numsignificantbytes * 8 + SHIFT - 1) / SHIFT;
310 if (ndigits > (size_t)INT_MAX)
311 return PyErr_NoMemory();
312 v = _PyLong_New((int)ndigits);
313 if (v == NULL)
314 return NULL;
315
316 /* Copy the bits over. The tricky parts are computing 2's-comp on
317 the fly for signed numbers, and dealing with the mismatch between
318 8-bit bytes and (probably) 15-bit Python digits.*/
319 {
320 size_t i;
321 twodigits carry = 1; /* for 2's-comp calculation */
322 twodigits accum = 0; /* sliding register */
323 unsigned int accumbits = 0; /* number of bits in accum */
324 const unsigned char* p = pstartbyte;
325
326 for (i = 0; i < numsignificantbytes; ++i, p += incr) {
327 twodigits thisbyte = *p;
328 /* Compute correction for 2's comp, if needed. */
329 if (is_signed) {
330 thisbyte = (0xff ^ thisbyte) + carry;
331 carry = thisbyte >> 8;
332 thisbyte &= 0xff;
333 }
334 /* Because we're going LSB to MSB, thisbyte is
335 more significant than what's already in accum,
336 so needs to be prepended to accum. */
337 accum |= thisbyte << accumbits;
338 accumbits += 8;
339 if (accumbits >= SHIFT) {
340 /* There's enough to fill a Python digit. */
341 assert(idigit < (int)ndigits);
342 v->ob_digit[idigit] = (digit)(accum & MASK);
343 ++idigit;
344 accum >>= SHIFT;
345 accumbits -= SHIFT;
346 assert(accumbits < SHIFT);
347 }
348 }
349 assert(accumbits < SHIFT);
350 if (accumbits) {
351 assert(idigit < (int)ndigits);
352 v->ob_digit[idigit] = (digit)accum;
353 ++idigit;
354 }
355 }
356
357 v->ob_size = is_signed ? -idigit : idigit;
358 return (PyObject *)long_normalize(v);
359 }
360
361 int
362 _PyLong_AsByteArray(PyLongObject* v,
363 unsigned char* bytes, size_t n,
364 int little_endian, int is_signed)
365 {
366 int i; /* index into v->ob_digit */
367 int ndigits; /* |v->ob_size| */
368 twodigits accum; /* sliding register */
369 unsigned int accumbits; /* # bits in accum */
370 int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
371 twodigits carry; /* for computing 2's-comp */
372 size_t j; /* # bytes filled */
373 unsigned char* p; /* pointer to next byte in bytes */
374 int pincr; /* direction to move p */
375
376 assert(v != NULL && PyLong_Check(v));
377
378 if (v->ob_size < 0) {
379 ndigits = -(v->ob_size);
380 if (!is_signed) {
381 PyErr_SetString(PyExc_TypeError,
382 "can't convert negative long to unsigned");
383 return -1;
384 }
385 do_twos_comp = 1;
386 }
387 else {
388 ndigits = v->ob_size;
389 do_twos_comp = 0;
390 }
391
392 if (little_endian) {
393 p = bytes;
394 pincr = 1;
395 }
396 else {
397 p = bytes + n - 1;
398 pincr = -1;
399 }
400
401 /* Copy over all the Python digits.
402 It's crucial that every Python digit except for the MSD contribute
403 exactly SHIFT bits to the total, so first assert that the long is
404 normalized. */
405 assert(ndigits == 0 || v->ob_digit[ndigits - 1] != 0);
406 j = 0;
407 accum = 0;
408 accumbits = 0;
409 carry = do_twos_comp ? 1 : 0;
410 for (i = 0; i < ndigits; ++i) {
411 twodigits thisdigit = v->ob_digit[i];
412 if (do_twos_comp) {
413 thisdigit = (thisdigit ^ MASK) + carry;
414 carry = thisdigit >> SHIFT;
415 thisdigit &= MASK;
416 }
417 /* Because we're going LSB to MSB, thisdigit is more
418 significant than what's already in accum, so needs to be
419 prepended to accum. */
420 accum |= thisdigit << accumbits;
421 accumbits += SHIFT;
422
423 /* The most-significant digit may be (probably is) at least
424 partly empty. */
425 if (i == ndigits - 1) {
426 /* Count # of sign bits -- they needn't be stored,
427 * although for signed conversion we need later to
428 * make sure at least one sign bit gets stored.
429 * First shift conceptual sign bit to real sign bit.
430 */
431 stwodigits s = (stwodigits)(thisdigit <<
432 (8*sizeof(stwodigits) - SHIFT));
433 unsigned int nsignbits = 0;
434 while ((s < 0) == do_twos_comp && nsignbits < SHIFT) {
435 ++nsignbits;
436 s <<= 1;
437 }
438 accumbits -= nsignbits;
439 }
440
441 /* Store as many bytes as possible. */
442 while (accumbits >= 8) {
443 if (j >= n)
444 goto Overflow;
445 ++j;
446 *p = (unsigned char)(accum & 0xff);
447 p += pincr;
448 accumbits -= 8;
449 accum >>= 8;
450 }
451 }
452
453 /* Store the straggler (if any). */
454 assert(accumbits < 8);
455 assert(carry == 0); /* else do_twos_comp and *every* digit was 0 */
456 if (accumbits > 0) {
457 if (j >= n)
458 goto Overflow;
459 ++j;
460 if (do_twos_comp) {
461 /* Fill leading bits of the byte with sign bits
462 (appropriately pretending that the long had an
463 infinite supply of sign bits). */
464 accum |= (~(twodigits)0) << accumbits;
465 }
466 *p = (unsigned char)(accum & 0xff);
467 p += pincr;
468 }
469 else if (j == n && n > 0 && is_signed) {
470 /* The main loop filled the byte array exactly, so the code
471 just above didn't get to ensure there's a sign bit, and the
472 loop below wouldn't add one either. Make sure a sign bit
473 exists. */
474 unsigned char msb = *(p - pincr);
475 int sign_bit_set = msb >= 0x80;
476 assert(accumbits == 0);
477 if (sign_bit_set == do_twos_comp)
478 return 0;
479 else
480 goto Overflow;
481 }
482
483 /* Fill remaining bytes with copies of the sign bit. */
484 {
485 unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
486 for ( ; j < n; ++j, p += pincr)
487 *p = signbyte;
488 }
489
490 return 0;
491
492 Overflow:
493 PyErr_SetString(PyExc_OverflowError, "long too big to convert");
494 return -1;
495
496 }
497
498 double
499 _PyLong_AsScaledDouble(PyObject *vv, int *exponent)
500 {
501 /* NBITS_WANTED should be > the number of bits in a double's precision,
502 but small enough so that 2**NBITS_WANTED is within the normal double
503 range. nbitsneeded is set to 1 less than that because the most-significant
504 Python digit contains at least 1 significant bit, but we don't want to
505 bother counting them (catering to the worst case cheaply).
506
507 57 is one more than VAX-D double precision; I (Tim) don't know of a double
508 format with more precision than that; it's 1 larger so that we add in at
509 least one round bit to stand in for the ignored least-significant bits.
510 */
511 #define NBITS_WANTED 57
512 PyLongObject *v;
513 double x;
514 const double multiplier = (double)(1L << SHIFT);
515 int i, sign;
516 int nbitsneeded;
517
518 if (vv == NULL || !PyLong_Check(vv)) {
519 PyErr_BadInternalCall();
520 return -1;
521 }
522 v = (PyLongObject *)vv;
523 i = v->ob_size;
524 sign = 1;
525 if (i < 0) {
526 sign = -1;
527 i = -(i);
528 }
529 else if (i == 0) {
530 *exponent = 0;
531 return 0.0;
532 }
533 --i;
534 x = (double)v->ob_digit[i];
535 nbitsneeded = NBITS_WANTED - 1;
536 /* Invariant: i Python digits remain unaccounted for. */
537 while (i > 0 && nbitsneeded > 0) {
538 --i;
539 x = x * multiplier + (double)v->ob_digit[i];
540 nbitsneeded -= SHIFT;
541 }
542 /* There are i digits we didn't shift in. Pretending they're all
543 zeroes, the true value is x * 2**(i*SHIFT). */
544 *exponent = i;
545 assert(x > 0.0);
546 return x * sign;
547 #undef NBITS_WANTED
548 }
549
550 /* Get a C double from a long int object. */
551
552 double
553 PyLong_AsDouble(PyObject *vv)
554 {
555 int e;
556 double x;
557
558 if (vv == NULL || !PyLong_Check(vv)) {
559 PyErr_BadInternalCall();
560 return -1;
561 }
562 x = _PyLong_AsScaledDouble(vv, &e);
563 if (x == -1.0 && PyErr_Occurred())
564 return -1.0;
565 if (e > INT_MAX / SHIFT)
566 goto overflow;
567 errno = 0;
568 x = ldexp(x, e * SHIFT);
569 if (Py_OVERFLOWED(x))
570 goto overflow;
571 return x;
572
573 overflow:
574 PyErr_SetString(PyExc_OverflowError,
575 "long int too large to convert to float");
576 return -1.0;
577 }
578
579 /* Create a new long (or int) object from a C pointer */
580
581 PyObject *
582 PyLong_FromVoidPtr(void *p)
583 {
584 #if SIZEOF_VOID_P <= SIZEOF_LONG
585 return PyInt_FromLong((long)p);
586 #else
587
588 #ifndef HAVE_LONG_LONG
589 # error "PyLong_FromVoidPtr: sizeof(void*) > sizeof(long), but no long long"
590 #endif
591 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
592 # error "PyLong_FromVoidPtr: sizeof(LONG_LONG) < sizeof(void*)"
593 #endif
594 /* optimize null pointers */
595 if (p == NULL)
596 return PyInt_FromLong(0);
597 return PyLong_FromLongLong((LONG_LONG)p);
598
599 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
600 }
601
602 /* Get a C pointer from a long object (or an int object in some cases) */
603
604 void *
605 PyLong_AsVoidPtr(PyObject *vv)
606 {
607 /* This function will allow int or long objects. If vv is neither,
608 then the PyLong_AsLong*() functions will raise the exception:
609 PyExc_SystemError, "bad argument to internal function"
610 */
611 #if SIZEOF_VOID_P <= SIZEOF_LONG
612 long x;
613
614 if (PyInt_Check(vv))
615 x = PyInt_AS_LONG(vv);
616 else
617 x = PyLong_AsLong(vv);
618 #else
619
620 #ifndef HAVE_LONG_LONG
621 # error "PyLong_AsVoidPtr: sizeof(void*) > sizeof(long), but no long long"
622 #endif
623 #if SIZEOF_LONG_LONG < SIZEOF_VOID_P
624 # error "PyLong_AsVoidPtr: sizeof(LONG_LONG) < sizeof(void*)"
625 #endif
626 LONG_LONG x;
627
628 if (PyInt_Check(vv))
629 x = PyInt_AS_LONG(vv);
630 else
631 x = PyLong_AsLongLong(vv);
632
633 #endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
634
635 if (x == -1 && PyErr_Occurred())
636 return NULL;
637 return (void *)x;
638 }
639
640 #ifdef HAVE_LONG_LONG
641
642 /* Initial LONG_LONG support by Chris Herborth (chrish@qnx.com), later
643 * rewritten to use the newer PyLong_{As,From}ByteArray API.
644 */
645
646 #define IS_LITTLE_ENDIAN (int)*(unsigned char*)&one
647
648 /* Create a new long int object from a C LONG_LONG int. */
649
650 PyObject *
651 PyLong_FromLongLong(LONG_LONG ival)
652 {
653 LONG_LONG bytes = ival;
654 int one = 1;
655 return _PyLong_FromByteArray(
656 (unsigned char *)&bytes,
657 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
658 }
659
660 /* Create a new long int object from a C unsigned LONG_LONG int. */
661
662 PyObject *
663 PyLong_FromUnsignedLongLong(unsigned LONG_LONG ival)
664 {
665 unsigned LONG_LONG bytes = ival;
666 int one = 1;
667 return _PyLong_FromByteArray(
668 (unsigned char *)&bytes,
669 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
670 }
671
672 /* Get a C LONG_LONG int from a long int object.
673 Return -1 and set an error if overflow occurs. */
674
675 LONG_LONG
676 PyLong_AsLongLong(PyObject *vv)
677 {
678 LONG_LONG bytes;
679 int one = 1;
680 int res;
681
682 if (vv == NULL) {
683 PyErr_BadInternalCall();
684 return -1;
685 }
686 if (!PyLong_Check(vv)) {
687 if (PyInt_Check(vv))
688 return (LONG_LONG)PyInt_AsLong(vv);
689 PyErr_BadInternalCall();
690 return -1;
691 }
692
693 res = _PyLong_AsByteArray(
694 (PyLongObject *)vv, (unsigned char *)&bytes,
695 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 1);
696
697 return res < 0 ? (LONG_LONG)res : bytes;
698 }
699
700 /* Get a C unsigned LONG_LONG int from a long int object.
701 Return -1 and set an error if overflow occurs. */
702
703 unsigned LONG_LONG
704 PyLong_AsUnsignedLongLong(PyObject *vv)
705 {
706 unsigned LONG_LONG bytes;
707 int one = 1;
708 int res;
709
710 if (vv == NULL || !PyLong_Check(vv)) {
711 PyErr_BadInternalCall();
712 return -1;
713 }
714
715 res = _PyLong_AsByteArray(
716 (PyLongObject *)vv, (unsigned char *)&bytes,
717 SIZEOF_LONG_LONG, IS_LITTLE_ENDIAN, 0);
718
719 return res < 0 ? (unsigned LONG_LONG)res : bytes;
720 }
721
722 #undef IS_LITTLE_ENDIAN
723
724 #endif /* HAVE_LONG_LONG */
725
726
727 static int
728 convert_binop(PyObject *v, PyObject *w, PyLongObject **a, PyLongObject **b) {
729 if (PyLong_Check(v)) {
730 *a = (PyLongObject *) v;
731 Py_INCREF(v);
732 }
733 else if (PyInt_Check(v)) {
734 *a = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(v));
735 }
736 else {
737 return 0;
738 }
739 if (PyLong_Check(w)) {
740 *b = (PyLongObject *) w;
741 Py_INCREF(w);
742 }
743 else if (PyInt_Check(w)) {
744 *b = (PyLongObject *) PyLong_FromLong(PyInt_AS_LONG(w));
745 }
746 else {
747 Py_DECREF(*a);
748 return 0;
749 }
750 return 1;
751 }
752
753 #define CONVERT_BINOP(v, w, a, b) \
754 if (!convert_binop(v, w, a, b)) { \
755 Py_INCREF(Py_NotImplemented); \
756 return Py_NotImplemented; \
757 }
758
759
760 /* Multiply by a single digit, ignoring the sign. */
761
762 static PyLongObject *
763 mul1(PyLongObject *a, wdigit n)
764 {
765 return muladd1(a, n, (digit)0);
766 }
767
768 /* Multiply by a single digit and add a single digit, ignoring the sign. */
769
770 static PyLongObject *
771 muladd1(PyLongObject *a, wdigit n, wdigit extra)
772 {
773 int size_a = ABS(a->ob_size);
774 PyLongObject *z = _PyLong_New(size_a+1);
775 twodigits carry = extra;
776 int i;
777
778 if (z == NULL)
779 return NULL;
780 for (i = 0; i < size_a; ++i) {
781 carry += (twodigits)a->ob_digit[i] * n;
782 z->ob_digit[i] = (digit) (carry & MASK);
783 carry >>= SHIFT;
784 }
785 z->ob_digit[i] = (digit) carry;
786 return long_normalize(z);
787 }
788
789 /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
790 in pout, and returning the remainder. pin and pout point at the LSD.
791 It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
792 long_format, but that should be done with great care since longs are
793 immutable. */
794
795 static digit
796 inplace_divrem1(digit *pout, digit *pin, int size, digit n)
797 {
798 twodigits rem = 0;
799
800 assert(n > 0 && n <= MASK);
801 pin += size;
802 pout += size;
803 while (--size >= 0) {
804 digit hi;
805 rem = (rem << SHIFT) + *--pin;
806 *--pout = hi = (digit)(rem / n);
807 rem -= hi * n;
808 }
809 return (digit)rem;
810 }
811
812 /* Divide a long integer by a digit, returning both the quotient
813 (as function result) and the remainder (through *prem).
814 The sign of a is ignored; n should not be zero. */
815
816 static PyLongObject *
817 divrem1(PyLongObject *a, digit n, digit *prem)
818 {
819 const int size = ABS(a->ob_size);
820 PyLongObject *z;
821
822 assert(n > 0 && n <= MASK);
823 z = _PyLong_New(size);
824 if (z == NULL)
825 return NULL;
826 *prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
827 return long_normalize(z);
828 }
829
830 /* Convert a long int object to a string, using a given conversion base.
831 Return a string object.
832 If base is 8 or 16, add the proper prefix '0' or '0x'. */
833
834 static PyObject *
835 long_format(PyObject *aa, int base, int addL)
836 {
837 register PyLongObject *a = (PyLongObject *)aa;
838 PyStringObject *str;
839 int i;
840 const int size_a = ABS(a->ob_size);
841 char *p;
842 int bits;
843 char sign = '\0';
844
845 if (a == NULL || !PyLong_Check(a)) {
846 PyErr_BadInternalCall();
847 return NULL;
848 }
849 assert(base >= 2 && base <= 36);
850
851 /* Compute a rough upper bound for the length of the string */
852 i = base;
853 bits = 0;
854 while (i > 1) {
855 ++bits;
856 i >>= 1;
857 }
858 i = 5 + (addL ? 1 : 0) + (size_a*SHIFT + bits-1) / bits;
859 str = (PyStringObject *) PyString_FromStringAndSize((char *)0, i);
860 if (str == NULL)
861 return NULL;
862 p = PyString_AS_STRING(str) + i;
863 *p = '\0';
864 if (addL)
865 *--p = 'L';
866 if (a->ob_size < 0)
867 sign = '-';
868
869 if (a->ob_size == 0) {
870 *--p = '0';
871 }
872 else if ((base & (base - 1)) == 0) {
873 /* JRH: special case for power-of-2 bases */
874 twodigits accum = 0;
875 int accumbits = 0; /* # of bits in accum */
876 int basebits = 1; /* # of bits in base-1 */
877 i = base;
878 while ((i >>= 1) > 1)
879 ++basebits;
880
881 for (i = 0; i < size_a; ++i) {
882 accum |= a->ob_digit[i] << accumbits;
883 accumbits += SHIFT;
884 assert(accumbits >= basebits);
885 do {
886 char digit = (char)(accum & (base - 1));
887 digit += (digit < 10) ? '0' : 'A'-10;
888 assert(p > PyString_AS_STRING(str));
889 *--p = digit;
890 accumbits -= basebits;
891 accum >>= basebits;
892 } while (i < size_a-1 ? accumbits >= basebits :
893 accum > 0);
894 }
895 }
896 else {
897 /* Not 0, and base not a power of 2. Divide repeatedly by
898 base, but for speed use the highest power of base that
899 fits in a digit. */
900 int size = size_a;
901 digit *pin = a->ob_digit;
902 PyLongObject *scratch;
903 /* powbasw <- largest power of base that fits in a digit. */
904 digit powbase = base; /* powbase == base ** power */
905 int power = 1;
906 for (;;) {
907 unsigned long newpow = powbase * (unsigned long)base;
908 if (newpow >> SHIFT) /* doesn't fit in a digit */
909 break;
910 powbase = (digit)newpow;
911 ++power;
912 }
913
914 /* Get a scratch area for repeated division. */
915 scratch = _PyLong_New(size);
916 if (scratch == NULL) {
917 Py_DECREF(str);
918 return NULL;
919 }
920
921 /* Repeatedly divide by powbase. */
922 do {
923 int ntostore = power;
924 digit rem = inplace_divrem1(scratch->ob_digit,
925 pin, size, powbase);
926 pin = scratch->ob_digit; /* no need to use a again */
927 if (pin[size - 1] == 0)
928 --size;
929 SIGCHECK({
930 Py_DECREF(scratch);
931 Py_DECREF(str);
932 return NULL;
933 })
934
935 /* Break rem into digits. */
936 assert(ntostore > 0);
937 do {
938 digit nextrem = (digit)(rem / base);
939 char c = (char)(rem - nextrem * base);
940 assert(p > PyString_AS_STRING(str));
941 c += (c < 10) ? '0' : 'A'-10;
942 *--p = c;
943 rem = nextrem;
944 --ntostore;
945 /* Termination is a bit delicate: must not
946 store leading zeroes, so must get out if
947 remaining quotient and rem are both 0. */
948 } while (ntostore && (size || rem));
949 } while (size != 0);
950 Py_DECREF(scratch);
951 }
952
953 if (base == 8) {
954 if (size_a != 0)
955 *--p = '0';
956 }
957 else if (base == 16) {
958 *--p = 'x';
959 *--p = '0';
960 }
961 else if (base != 10) {
962 *--p = '#';
963 *--p = '0' + base%10;
964 if (base > 10)
965 *--p = '0' + base/10;
966 }
967 if (sign)
968 *--p = sign;
969 if (p != PyString_AS_STRING(str)) {
970 char *q = PyString_AS_STRING(str);
971 assert(p > q);
972 do {
973 } while ((*q++ = *p++) != '\0');
974 q--;
975 _PyString_Resize((PyObject **)&str,
976 (int) (q - PyString_AS_STRING(str)));
977 }
978 return (PyObject *)str;
979 }
980
981 PyObject *
982 PyLong_FromString(char *str, char **pend, int base)
983 {
984 int sign = 1;
985 char *start, *orig_str = str;
986 PyLongObject *z;
987
988 if ((base != 0 && base < 2) || base > 36) {
989 PyErr_SetString(PyExc_ValueError,
990 "long() arg 2 must be >= 2 and <= 36");
991 return NULL;
992 }
993 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
994 str++;
995 if (*str == '+')
996 ++str;
997 else if (*str == '-') {
998 ++str;
999 sign = -1;
1000 }
1001 while (*str != '\0' && isspace(Py_CHARMASK(*str)))
1002 str++;
1003 if (base == 0) {
1004 if (str[0] != '0')
1005 base = 10;
1006 else if (str[1] == 'x' || str[1] == 'X')
1007 base = 16;
1008 else
1009 base = 8;
1010 }
1011 if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
1012 str += 2;
1013 z = _PyLong_New(0);
1014 start = str;
1015 for ( ; z != NULL; ++str) {
1016 int k = -1;
1017 PyLongObject *temp;
1018
1019 if (*str <= '9')
1020 k = *str - '0';
1021 else if (*str >= 'a')
1022 k = *str - 'a' + 10;
1023 else if (*str >= 'A')
1024 k = *str - 'A' + 10;
1025 if (k < 0 || k >= base)
1026 break;
1027 temp = muladd1(z, (digit)base, (digit)k);
1028 Py_DECREF(z);
1029 z = temp;
1030 }
1031 if (z == NULL)
1032 return NULL;
1033 if (str == start)
1034 goto onError;
1035 if (sign < 0 && z != NULL && z->ob_size != 0)
1036 z->ob_size = -(z->ob_size);
1037 if (*str == 'L' || *str == 'l')
1038 str++;
1039 while (*str && isspace(Py_CHARMASK(*str)))
1040 str++;
1041 if (*str != '\0')
1042 goto onError;
1043 if (pend)
1044 *pend = str;
1045 return (PyObject *) z;
1046
1047 onError:
1048 PyErr_Format(PyExc_ValueError,
1049 "invalid literal for long(): %.200s", orig_str);
1050 Py_XDECREF(z);
1051 return NULL;
1052 }
1053
1054 #ifdef Py_USING_UNICODE
1055 PyObject *
1056 PyLong_FromUnicode(Py_UNICODE *u, int length, int base)
1057 {
1058 char buffer[256];
1059
1060 if (length >= sizeof(buffer)) {
1061 PyErr_SetString(PyExc_ValueError,
1062 "long() literal too large to convert");
1063 return NULL;
1064 }
1065 if (PyUnicode_EncodeDecimal(u, length, buffer, NULL))
1066 return NULL;
1067
1068 return PyLong_FromString(buffer, NULL, base);
1069 }
1070 #endif
1071
1072 /* forward */
1073 static PyLongObject *x_divrem
1074 (PyLongObject *, PyLongObject *, PyLongObject **);
1075 static PyObject *long_pos(PyLongObject *);
1076 static int long_divrem(PyLongObject *, PyLongObject *,
1077 PyLongObject **, PyLongObject **);
1078
1079 /* Long division with remainder, top-level routine */
1080
1081 static int
1082 long_divrem(PyLongObject *a, PyLongObject *b,
1083 PyLongObject **pdiv, PyLongObject **prem)
1084 {
1085 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1086 PyLongObject *z;
1087
1088 if (size_b == 0) {
1089 PyErr_SetString(PyExc_ZeroDivisionError,
1090 "long division or modulo by zero");
1091 return -1;
1092 }
1093 if (size_a < size_b ||
1094 (size_a == size_b &&
1095 a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
1096 /* |a| < |b|. */
1097 *pdiv = _PyLong_New(0);
1098 Py_INCREF(a);
1099 *prem = (PyLongObject *) a;
1100 return 0;
1101 }
1102 if (size_b == 1) {
1103 digit rem = 0;
1104 z = divrem1(a, b->ob_digit[0], &rem);
1105 if (z == NULL)
1106 return -1;
1107 *prem = (PyLongObject *) PyLong_FromLong((long)rem);
1108 }
1109 else {
1110 z = x_divrem(a, b, prem);
1111 if (z == NULL)
1112 return -1;
1113 }
1114 /* Set the signs.
1115 The quotient z has the sign of a*b;
1116 the remainder r has the sign of a,
1117 so a = b*z + r. */
1118 if ((a->ob_size < 0) != (b->ob_size < 0))
1119 z->ob_size = -(z->ob_size);
1120 if (a->ob_size < 0 && (*prem)->ob_size != 0)
1121 (*prem)->ob_size = -((*prem)->ob_size);
1122 *pdiv = z;
1123 return 0;
1124 }
1125
1126 /* Unsigned long division with remainder -- the algorithm */
1127
1128 static PyLongObject *
1129 x_divrem(PyLongObject *v1, PyLongObject *w1, PyLongObject **prem)
1130 {
1131 int size_v = ABS(v1->ob_size), size_w = ABS(w1->ob_size);
1132 digit d = (digit) ((twodigits)BASE / (w1->ob_digit[size_w-1] + 1));
1133 PyLongObject *v = mul1(v1, d);
1134 PyLongObject *w = mul1(w1, d);
1135 PyLongObject *a;
1136 int j, k;
1137
1138 if (v == NULL || w == NULL) {
1139 Py_XDECREF(v);
1140 Py_XDECREF(w);
1141 return NULL;
1142 }
1143
1144 assert(size_v >= size_w && size_w > 1); /* Assert checks by div() */
1145 assert(v->ob_refcnt == 1); /* Since v will be used as accumulator! */
1146 assert(size_w == ABS(w->ob_size)); /* That's how d was calculated */
1147
1148 size_v = ABS(v->ob_size);
1149 a = _PyLong_New(size_v - size_w + 1);
1150
1151 for (j = size_v, k = a->ob_size-1; a != NULL && k >= 0; --j, --k) {
1152 digit vj = (j >= size_v) ? 0 : v->ob_digit[j];
1153 twodigits q;
1154 stwodigits carry = 0;
1155 int i;
1156
1157 SIGCHECK({
1158 Py_DECREF(a);
1159 a = NULL;
1160 break;
1161 })
1162 if (vj == w->ob_digit[size_w-1])
1163 q = MASK;
1164 else
1165 q = (((twodigits)vj << SHIFT) + v->ob_digit[j-1]) /
1166 w->ob_digit[size_w-1];
1167
1168 while (w->ob_digit[size_w-2]*q >
1169 ((
1170 ((twodigits)vj << SHIFT)
1171 + v->ob_digit[j-1]
1172 - q*w->ob_digit[size_w-1]
1173 ) << SHIFT)
1174 + v->ob_digit[j-2])
1175 --q;
1176
1177 for (i = 0; i < size_w && i+k < size_v; ++i) {
1178 twodigits z = w->ob_digit[i] * q;
1179 digit zz = (digit) (z >> SHIFT);
1180 carry += v->ob_digit[i+k] - z
1181 + ((twodigits)zz << SHIFT);
1182 v->ob_digit[i+k] = carry & MASK;
1183 carry = Py_ARITHMETIC_RIGHT_SHIFT(BASE_TWODIGITS_TYPE,
1184 carry, SHIFT);
1185 carry -= zz;
1186 }
1187
1188 if (i+k < size_v) {
1189 carry += v->ob_digit[i+k];
1190 v->ob_digit[i+k] = 0;
1191 }
1192
1193 if (carry == 0)
1194 a->ob_digit[k] = (digit) q;
1195 else {
1196 assert(carry == -1);
1197 a->ob_digit[k] = (digit) q-1;
1198 carry = 0;
1199 for (i = 0; i < size_w && i+k < size_v; ++i) {
1200 carry += v->ob_digit[i+k] + w->ob_digit[i];
1201 v->ob_digit[i+k] = carry & MASK;
1202 carry = Py_ARITHMETIC_RIGHT_SHIFT(
1203 BASE_TWODIGITS_TYPE,
1204 carry, SHIFT);
1205 }
1206 }
1207 } /* for j, k */
1208
1209 if (a == NULL)
1210 *prem = NULL;
1211 else {
1212 a = long_normalize(a);
1213 *prem = divrem1(v, d, &d);
1214 /* d receives the (unused) remainder */
1215 if (*prem == NULL) {
1216 Py_DECREF(a);
1217 a = NULL;
1218 }
1219 }
1220 Py_DECREF(v);
1221 Py_DECREF(w);
1222 return a;
1223 }
1224
1225 /* Methods */
1226
1227 static void
1228 long_dealloc(PyObject *v)
1229 {
1230 v->ob_type->tp_free(v);
1231 }
1232
1233 static PyObject *
1234 long_repr(PyObject *v)
1235 {
1236 return long_format(v, 10, 1);
1237 }
1238
1239 static PyObject *
1240 long_str(PyObject *v)
1241 {
1242 return long_format(v, 10, 0);
1243 }
1244
1245 static int
1246 long_compare(PyLongObject *a, PyLongObject *b)
1247 {
1248 int sign;
1249
1250 if (a->ob_size != b->ob_size) {
1251 if (ABS(a->ob_size) == 0 && ABS(b->ob_size) == 0)
1252 sign = 0;
1253 else
1254 sign = a->ob_size - b->ob_size;
1255 }
1256 else {
1257 int i = ABS(a->ob_size);
1258 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1259 ;
1260 if (i < 0)
1261 sign = 0;
1262 else {
1263 sign = (int)a->ob_digit[i] - (int)b->ob_digit[i];
1264 if (a->ob_size < 0)
1265 sign = -sign;
1266 }
1267 }
1268 return sign < 0 ? -1 : sign > 0 ? 1 : 0;
1269 }
1270
1271 static long
1272 long_hash(PyLongObject *v)
1273 {
1274 long x;
1275 int i, sign;
1276
1277 /* This is designed so that Python ints and longs with the
1278 same value hash to the same value, otherwise comparisons
1279 of mapping keys will turn out weird */
1280 i = v->ob_size;
1281 sign = 1;
1282 x = 0;
1283 if (i < 0) {
1284 sign = -1;
1285 i = -(i);
1286 }
1287 while (--i >= 0) {
1288 /* Force a 32-bit circular shift */
1289 x = ((x << SHIFT) & ~MASK) | ((x >> (32-SHIFT)) & MASK);
1290 x += v->ob_digit[i];
1291 }
1292 x = x * sign;
1293 if (x == -1)
1294 x = -2;
1295 return x;
1296 }
1297
1298
1299 /* Add the absolute values of two long integers. */
1300
1301 static PyLongObject *
1302 x_add(PyLongObject *a, PyLongObject *b)
1303 {
1304 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1305 PyLongObject *z;
1306 int i;
1307 digit carry = 0;
1308
1309 /* Ensure a is the larger of the two: */
1310 if (size_a < size_b) {
1311 { PyLongObject *temp = a; a = b; b = temp; }
1312 { int size_temp = size_a;
1313 size_a = size_b;
1314 size_b = size_temp; }
1315 }
1316 z = _PyLong_New(size_a+1);
1317 if (z == NULL)
1318 return NULL;
1319 for (i = 0; i < size_b; ++i) {
1320 carry += a->ob_digit[i] + b->ob_digit[i];
1321 z->ob_digit[i] = carry & MASK;
1322 carry >>= SHIFT;
1323 }
1324 for (; i < size_a; ++i) {
1325 carry += a->ob_digit[i];
1326 z->ob_digit[i] = carry & MASK;
1327 carry >>= SHIFT;
1328 }
1329 z->ob_digit[i] = carry;
1330 return long_normalize(z);
1331 }
1332
1333 /* Subtract the absolute values of two integers. */
1334
1335 static PyLongObject *
1336 x_sub(PyLongObject *a, PyLongObject *b)
1337 {
1338 int size_a = ABS(a->ob_size), size_b = ABS(b->ob_size);
1339 PyLongObject *z;
1340 int i;
1341 int sign = 1;
1342 digit borrow = 0;
1343
1344 /* Ensure a is the larger of the two: */
1345 if (size_a < size_b) {
1346 sign = -1;
1347 { PyLongObject *temp = a; a = b; b = temp; }
1348 { int size_temp = size_a;
1349 size_a = size_b;
1350 size_b = size_temp; }
1351 }
1352 else if (size_a == size_b) {
1353 /* Find highest digit where a and b differ: */
1354 i = size_a;
1355 while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
1356 ;
1357 if (i < 0)
1358 return _PyLong_New(0);
1359 if (a->ob_digit[i] < b->ob_digit[i]) {
1360 sign = -1;
1361 { PyLongObject *temp = a; a = b; b = temp; }
1362 }
1363 size_a = size_b = i+1;
1364 }
1365 z = _PyLong_New(size_a);
1366 if (z == NULL)
1367 return NULL;
1368 for (i = 0; i < size_b; ++i) {
1369 /* The following assumes unsigned arithmetic
1370 works module 2**N for some N>SHIFT. */
1371 borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
1372 z->ob_digit[i] = borrow & MASK;
1373 borrow >>= SHIFT;
1374 borrow &= 1; /* Keep only one sign bit */
1375 }
1376 for (; i < size_a; ++i) {
1377 borrow = a->ob_digit[i] - borrow;
1378 z->ob_digit[i] = borrow & MASK;
1379 borrow >>= SHIFT;
1380 borrow &= 1; /* Keep only one sign bit */
1381 }
1382 assert(borrow == 0);
1383 if (sign < 0)
1384 z->ob_size = -(z->ob_size);
1385 return long_normalize(z);
1386 }
1387
1388 static PyObject *
1389 long_add(PyLongObject *v, PyLongObject *w)
1390 {
1391 PyLongObject *a, *b, *z;
1392
1393 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1394
1395 if (a->ob_size < 0) {
1396 if (b->ob_size < 0) {
1397 z = x_add(a, b);
1398 if (z != NULL && z->ob_size != 0)
1399 z->ob_size = -(z->ob_size);
1400 }
1401 else
1402 z = x_sub(b, a);
1403 }
1404 else {
1405 if (b->ob_size < 0)
1406 z = x_sub(a, b);
1407 else
1408 z = x_add(a, b);
1409 }
1410 Py_DECREF(a);
1411 Py_DECREF(b);
1412 return (PyObject *)z;
1413 }
1414
1415 static PyObject *
1416 long_sub(PyLongObject *v, PyLongObject *w)
1417 {
1418 PyLongObject *a, *b, *z;
1419
1420 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1421
1422 if (a->ob_size < 0) {
1423 if (b->ob_size < 0)
1424 z = x_sub(a, b);
1425 else
1426 z = x_add(a, b);
1427 if (z != NULL && z->ob_size != 0)
1428 z->ob_size = -(z->ob_size);
1429 }
1430 else {
1431 if (b->ob_size < 0)
1432 z = x_add(a, b);
1433 else
1434 z = x_sub(a, b);
1435 }
1436 Py_DECREF(a);
1437 Py_DECREF(b);
1438 return (PyObject *)z;
1439 }
1440
1441 static PyObject *
1442 long_repeat(PyObject *v, PyLongObject *w)
1443 {
1444 /* sequence * long */
1445 long n = PyLong_AsLong((PyObject *) w);
1446 if (n == -1 && PyErr_Occurred())
1447 return NULL;
1448 else
1449 return (*v->ob_type->tp_as_sequence->sq_repeat)(v, n);
1450 }
1451
1452 static PyObject *
1453 long_mul(PyLongObject *v, PyLongObject *w)
1454 {
1455 PyLongObject *a, *b, *z;
1456 int size_a;
1457 int size_b;
1458 int i;
1459
1460 if (!convert_binop((PyObject *)v, (PyObject *)w, &a, &b)) {
1461 if (!PyLong_Check(v) &&
1462 v->ob_type->tp_as_sequence &&
1463 v->ob_type->tp_as_sequence->sq_repeat)
1464 return long_repeat((PyObject *)v, w);
1465 if (!PyLong_Check(w) &&
1466 w->ob_type->tp_as_sequence &&
1467 w->ob_type->tp_as_sequence->sq_repeat)
1468 return long_repeat((PyObject *)w, v);
1469 Py_INCREF(Py_NotImplemented);
1470 return Py_NotImplemented;
1471 }
1472
1473 size_a = ABS(a->ob_size);
1474 size_b = ABS(b->ob_size);
1475 if (size_a > size_b) {
1476 /* we are faster with the small object on the left */
1477 int hold_sa = size_a;
1478 PyLongObject *hold_a = a;
1479 size_a = size_b;
1480 size_b = hold_sa;
1481 a = b;
1482 b = hold_a;
1483 }
1484 z = _PyLong_New(size_a + size_b);
1485 if (z == NULL) {
1486 Py_DECREF(a);
1487 Py_DECREF(b);
1488 return NULL;
1489 }
1490 for (i = 0; i < z->ob_size; ++i)
1491 z->ob_digit[i] = 0;
1492 for (i = 0; i < size_a; ++i) {
1493 twodigits carry = 0;
1494 twodigits f = a->ob_digit[i];
1495 int j;
1496
1497 SIGCHECK({
1498 Py_DECREF(a);
1499 Py_DECREF(b);
1500 Py_DECREF(z);
1501 return NULL;
1502 })
1503 for (j = 0; j < size_b; ++j) {
1504 carry += z->ob_digit[i+j] + b->ob_digit[j] * f;
1505 z->ob_digit[i+j] = (digit) (carry & MASK);
1506 carry >>= SHIFT;
1507 }
1508 for (; carry != 0; ++j) {
1509 assert(i+j < z->ob_size);
1510 carry += z->ob_digit[i+j];
1511 z->ob_digit[i+j] = (digit) (carry & MASK);
1512 carry >>= SHIFT;
1513 }
1514 }
1515 if (a->ob_size < 0)
1516 z->ob_size = -(z->ob_size);
1517 if (b->ob_size < 0)
1518 z->ob_size = -(z->ob_size);
1519 Py_DECREF(a);
1520 Py_DECREF(b);
1521 return (PyObject *) long_normalize(z);
1522 }
1523
1524 /* The / and % operators are now defined in terms of divmod().
1525 The expression a mod b has the value a - b*floor(a/b).
1526 The long_divrem function gives the remainder after division of
1527 |a| by |b|, with the sign of a. This is also expressed
1528 as a - b*trunc(a/b), if trunc truncates towards zero.
1529 Some examples:
1530 a b a rem b a mod b
1531 13 10 3 3
1532 -13 10 -3 7
1533 13 -10 3 -7
1534 -13 -10 -3 -3
1535 So, to get from rem to mod, we have to add b if a and b
1536 have different signs. We then subtract one from the 'div'
1537 part of the outcome to keep the invariant intact. */
1538
1539 static int
1540 l_divmod(PyLongObject *v, PyLongObject *w,
1541 PyLongObject **pdiv, PyLongObject **pmod)
1542 {
1543 PyLongObject *div, *mod;
1544
1545 if (long_divrem(v, w, &div, &mod) < 0)
1546 return -1;
1547 if ((mod->ob_size < 0 && w->ob_size > 0) ||
1548 (mod->ob_size > 0 && w->ob_size < 0)) {
1549 PyLongObject *temp;
1550 PyLongObject *one;
1551 temp = (PyLongObject *) long_add(mod, w);
1552 Py_DECREF(mod);
1553 mod = temp;
1554 if (mod == NULL) {
1555 Py_DECREF(div);
1556 return -1;
1557 }
1558 one = (PyLongObject *) PyLong_FromLong(1L);
1559 if (one == NULL ||
1560 (temp = (PyLongObject *) long_sub(div, one)) == NULL) {
1561 Py_DECREF(mod);
1562 Py_DECREF(div);
1563 Py_XDECREF(one);
1564 return -1;
1565 }
1566 Py_DECREF(one);
1567 Py_DECREF(div);
1568 div = temp;
1569 }
1570 *pdiv = div;
1571 *pmod = mod;
1572 return 0;
1573 }
1574
1575 static PyObject *
1576 long_div(PyObject *v, PyObject *w)
1577 {
1578 PyLongObject *a, *b, *div, *mod;
1579
1580 CONVERT_BINOP(v, w, &a, &b);
1581
1582 if (l_divmod(a, b, &div, &mod) < 0) {
1583 Py_DECREF(a);
1584 Py_DECREF(b);
1585 return NULL;
1586 }
1587 Py_DECREF(a);
1588 Py_DECREF(b);
1589 Py_DECREF(mod);
1590 return (PyObject *)div;
1591 }
1592
1593 static PyObject *
1594 long_classic_div(PyObject *v, PyObject *w)
1595 {
1596 PyLongObject *a, *b, *div, *mod;
1597
1598 CONVERT_BINOP(v, w, &a, &b);
1599
1600 if (Py_DivisionWarningFlag &&
1601 PyErr_Warn(PyExc_DeprecationWarning, "classic long division") < 0)
1602 div = NULL;
1603 else if (l_divmod(a, b, &div, &mod) < 0)
1604 div = NULL;
1605 else
1606 Py_DECREF(mod);
1607
1608 Py_DECREF(a);
1609 Py_DECREF(b);
1610 return (PyObject *)div;
1611 }
1612
1613 static PyObject *
1614 long_true_divide(PyObject *v, PyObject *w)
1615 {
1616 PyLongObject *a, *b;
1617 double ad, bd;
1618 int aexp, bexp, failed;
1619
1620 CONVERT_BINOP(v, w, &a, &b);
1621 ad = _PyLong_AsScaledDouble((PyObject *)a, &aexp);
1622 bd = _PyLong_AsScaledDouble((PyObject *)b, &bexp);
1623 failed = (ad == -1.0 || bd == -1.0) && PyErr_Occurred();
1624 Py_DECREF(a);
1625 Py_DECREF(b);
1626 if (failed)
1627 return NULL;
1628
1629 if (bd == 0.0) {
1630 PyErr_SetString(PyExc_ZeroDivisionError,
1631 "long division or modulo by zero");
1632 return NULL;
1633 }
1634
1635 /* True value is very close to ad/bd * 2**(SHIFT*(aexp-bexp)) */
1636 ad /= bd; /* overflow/underflow impossible here */
1637 aexp -= bexp;
1638 if (aexp > INT_MAX / SHIFT)
1639 goto overflow;
1640 else if (aexp < -(INT_MAX / SHIFT))
1641 return PyFloat_FromDouble(0.0); /* underflow to 0 */
1642 errno = 0;
1643 ad = ldexp(ad, aexp * SHIFT);
1644 if (Py_OVERFLOWED(ad)) /* ignore underflow to 0.0 */
1645 goto overflow;
1646 return PyFloat_FromDouble(ad);
1647
1648 overflow:
1649 PyErr_SetString(PyExc_OverflowError,
1650 "long/long too large for a float");
1651 return NULL;
1652
1653 }
1654
1655 static PyObject *
1656 long_mod(PyObject *v, PyObject *w)
1657 {
1658 PyLongObject *a, *b, *div, *mod;
1659
1660 CONVERT_BINOP(v, w, &a, &b);
1661
1662 if (l_divmod(a, b, &div, &mod) < 0) {
1663 Py_DECREF(a);
1664 Py_DECREF(b);
1665 return NULL;
1666 }
1667 Py_DECREF(a);
1668 Py_DECREF(b);
1669 Py_DECREF(div);
1670 return (PyObject *)mod;
1671 }
1672
1673 static PyObject *
1674 long_divmod(PyObject *v, PyObject *w)
1675 {
1676 PyLongObject *a, *b, *div, *mod;
1677 PyObject *z;
1678
1679 CONVERT_BINOP(v, w, &a, &b);
1680
1681 if (l_divmod(a, b, &div, &mod) < 0) {
1682 Py_DECREF(a);
1683 Py_DECREF(b);
1684 return NULL;
1685 }
1686 z = PyTuple_New(2);
1687 if (z != NULL) {
1688 PyTuple_SetItem(z, 0, (PyObject *) div);
1689 PyTuple_SetItem(z, 1, (PyObject *) mod);
1690 }
1691 else {
1692 Py_DECREF(div);
1693 Py_DECREF(mod);
1694 }
1695 Py_DECREF(a);
1696 Py_DECREF(b);
1697 return z;
1698 }
1699
1700 static PyObject *
1701 long_pow(PyObject *v, PyObject *w, PyObject *x)
1702 {
1703 PyLongObject *a, *b;
1704 PyObject *c;
1705 PyLongObject *z, *div, *mod;
1706 int size_b, i;
1707
1708 CONVERT_BINOP(v, w, &a, &b);
1709 if (PyLong_Check(x) || Py_None == x) {
1710 c = x;
1711 Py_INCREF(x);
1712 }
1713 else if (PyInt_Check(x)) {
1714 c = PyLong_FromLong(PyInt_AS_LONG(x));
1715 }
1716 else {
1717 Py_DECREF(a);
1718 Py_DECREF(b);
1719 Py_INCREF(Py_NotImplemented);
1720 return Py_NotImplemented;
1721 }
1722
1723 if (c != Py_None && ((PyLongObject *)c)->ob_size == 0) {
1724 PyErr_SetString(PyExc_ValueError,
1725 "pow() 3rd argument cannot be 0");
1726 z = NULL;
1727 goto error;
1728 }
1729
1730 size_b = b->ob_size;
1731 if (size_b < 0) {
1732 Py_DECREF(a);
1733 Py_DECREF(b);
1734 Py_DECREF(c);
1735 if (x != Py_None) {
1736 PyErr_SetString(PyExc_TypeError, "pow() 2nd argument "
1737 "cannot be negative when 3rd argument specified");
1738 return NULL;
1739 }
1740 /* Return a float. This works because we know that
1741 this calls float_pow() which converts its
1742 arguments to double. */
1743 return PyFloat_Type.tp_as_number->nb_power(v, w, x);
1744 }
1745 z = (PyLongObject *)PyLong_FromLong(1L);
1746 for (i = 0; i < size_b; ++i) {
1747 digit bi = b->ob_digit[i];
1748 int j;
1749
1750 for (j = 0; j < SHIFT; ++j) {
1751 PyLongObject *temp;
1752
1753 if (bi & 1) {
1754 temp = (PyLongObject *)long_mul(z, a);
1755 Py_DECREF(z);
1756 if (c!=Py_None && temp!=NULL) {
1757 if (l_divmod(temp,(PyLongObject *)c,
1758 &div,&mod) < 0) {
1759 Py_DECREF(temp);
1760 z = NULL;
1761 goto error;
1762 }
1763 Py_XDECREF(div);
1764 Py_DECREF(temp);
1765 temp = mod;
1766 }
1767 z = temp;
1768 if (z == NULL)
1769 break;
1770 }
1771 bi >>= 1;
1772 if (bi == 0 && i+1 == size_b)
1773 break;
1774 temp = (PyLongObject *)long_mul(a, a);
1775 Py_DECREF(a);
1776 if (c!=Py_None && temp!=NULL) {
1777 if (l_divmod(temp, (PyLongObject *)c, &div,
1778 &mod) < 0) {
1779 Py_DECREF(temp);
1780 z = NULL;
1781 goto error;
1782 }
1783 Py_XDECREF(div);
1784 Py_DECREF(temp);
1785 temp = mod;
1786 }
1787 a = temp;
1788 if (a == NULL) {
1789 Py_DECREF(z);
1790 z = NULL;
1791 break;
1792 }
1793 }
1794 if (a == NULL || z == NULL)
1795 break;
1796 }
1797 if (c!=Py_None && z!=NULL) {
1798 if (l_divmod(z, (PyLongObject *)c, &div, &mod) < 0) {
1799 Py_DECREF(z);
1800 z = NULL;
1801 }
1802 else {
1803 Py_XDECREF(div);
1804 Py_DECREF(z);
1805 z = mod;
1806 }
1807 }
1808 error:
1809 Py_XDECREF(a);
1810 Py_DECREF(b);
1811 Py_DECREF(c);
1812 return (PyObject *)z;
1813 }
1814
1815 static PyObject *
1816 long_invert(PyLongObject *v)
1817 {
1818 /* Implement ~x as -(x+1) */
1819 PyLongObject *x;
1820 PyLongObject *w;
1821 w = (PyLongObject *)PyLong_FromLong(1L);
1822 if (w == NULL)
1823 return NULL;
1824 x = (PyLongObject *) long_add(v, w);
1825 Py_DECREF(w);
1826 if (x == NULL)
1827 return NULL;
1828 x->ob_size = -(x->ob_size);
1829 return (PyObject *)x;
1830 }
1831
1832 static PyObject *
1833 long_pos(PyLongObject *v)
1834 {
1835 if (PyLong_CheckExact(v)) {
1836 Py_INCREF(v);
1837 return (PyObject *)v;
1838 }
1839 else
1840 return _PyLong_Copy(v);
1841 }
1842
1843 static PyObject *
1844 long_neg(PyLongObject *v)
1845 {
1846 PyLongObject *z;
1847 if (v->ob_size == 0 && PyLong_CheckExact(v)) {
1848 /* -0 == 0 */
1849 Py_INCREF(v);
1850 return (PyObject *) v;
1851 }
1852 z = (PyLongObject *)_PyLong_Copy(v);
1853 if (z != NULL)
1854 z->ob_size = -(v->ob_size);
1855 return (PyObject *)z;
1856 }
1857
1858 static PyObject *
1859 long_abs(PyLongObject *v)
1860 {
1861 if (v->ob_size < 0)
1862 return long_neg(v);
1863 else
1864 return long_pos(v);
1865 }
1866
1867 static int
1868 long_nonzero(PyLongObject *v)
1869 {
1870 return ABS(v->ob_size) != 0;
1871 }
1872
1873 static PyObject *
1874 long_rshift(PyLongObject *v, PyLongObject *w)
1875 {
1876 PyLongObject *a, *b;
1877 PyLongObject *z = NULL;
1878 long shiftby;
1879 int newsize, wordshift, loshift, hishift, i, j;
1880 digit lomask, himask;
1881
1882 CONVERT_BINOP((PyObject *)v, (PyObject *)w, &a, &b);
1883
1884 if (a->ob_size < 0) {
1885 /* Right shifting negative numbers is harder */
1886 PyLongObject *a1, *a2;
1887 a1 = (PyLongObject *) long_invert(a);
1888 if (a1 == NULL)
1889 goto rshift_error;
1890 a2 = (PyLongObject *) long_rshift(a1, b);
1891 Py_DECREF(a1);
1892 if (a2 == NULL)
1893 goto rshift_error;
1894 z = (PyLongObject *) long_invert(a2);
1895 Py_DECREF(a2);
1896 }
1897 else {
1898
1899 shiftby = PyLong_AsLong((PyObject *)b);
1900 if (shiftby == -1L && PyErr_Occurred())
1901 goto rshift_error;
1902 if (shiftby < 0) {
1903 PyErr_SetString(PyExc_ValueError,
1904 "negative shift count");
1905 goto rshift_error;
1906 }
1907 wordshift = shiftby / SHIFT;
1908 newsize = ABS(a->ob_size) - wordshift;
1909 if (newsize <= 0) {
1910 z = _PyLong_New(0);
1911 Py_DECREF(a);
1912 Py_DECREF(b);
1913 return (PyObject *)z;
1914 }
1915 loshift = shiftby % SHIFT;
1916 hishift = SHIFT - loshift;
1917 lomask = ((digit)1 << hishift) - 1;
1918 himask = MASK ^ lomask;
1919 z = _PyLong_New(newsize);
1920 if (z == NULL)
1921 goto rshift_error;
1922 if (a->ob_size < 0)
1923 z->ob_size = -(z->ob_size);
1924 for (i = 0, j = wordshift; i < newsize; i++, j++) {
1925 z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
1926 if (i+1 < newsize)
1927 z->ob_digit[i] |=
1928 (a->ob_digit[j+1] << hishift) & himask;
1929 }
1930 z = long_normalize(z);
1931 }
1932 rshift_error:
1933 Py_DECREF(a);
1934 Py_DECREF(b);
1935 return (PyObject *) z;
1936
1937 }
1938
1939 static PyObject *
1940 long_lshift(PyObject *v, PyObject *w)
1941 {
1942 /* This version due to Tim Peters */
1943 PyLongObject *a, *b;
1944 PyLongObject *z = NULL;
1945 long shiftby;
1946 int oldsize, newsize, wordshift, remshift, i, j;
1947 twodigits accum;
1948
1949 CONVERT_BINOP(v, w, &a, &b);
1950
1951 shiftby = PyLong_AsLong((PyObject *)b);
1952 if (shiftby == -1L && PyErr_Occurred())
1953 goto lshift_error;
1954 if (shiftby < 0) {
1955 PyErr_SetString(PyExc_ValueError, "negative shift count");
1956 goto lshift_error;
1957 }
1958 if ((long)(int)shiftby != shiftby) {
1959 PyErr_SetString(PyExc_ValueError,
1960 "outrageous left shift count");
1961 goto lshift_error;
1962 }
1963 /* wordshift, remshift = divmod(shiftby, SHIFT) */
1964 wordshift = (int)shiftby / SHIFT;
1965 remshift = (int)shiftby - wordshift * SHIFT;
1966
1967 oldsize = ABS(a->ob_size);
1968 newsize = oldsize + wordshift;
1969 if (remshift)
1970 ++newsize;
1971 z = _PyLong_New(newsize);
1972 if (z == NULL)
1973 goto lshift_error;
1974 if (a->ob_size < 0)
1975 z->ob_size = -(z->ob_size);
1976 for (i = 0; i < wordshift; i++)
1977 z->ob_digit[i] = 0;
1978 accum = 0;
1979 for (i = wordshift, j = 0; j < oldsize; i++, j++) {
1980 accum |= a->ob_digit[j] << remshift;
1981 z->ob_digit[i] = (digit)(accum & MASK);
1982 accum >>= SHIFT;
1983 }
1984 if (remshift)
1985 z->ob_digit[newsize-1] = (digit)accum;
1986 else
1987 assert(!accum);
1988 z = long_normalize(z);
1989 lshift_error:
1990 Py_DECREF(a);
1991 Py_DECREF(b);
1992 return (PyObject *) z;
1993 }
1994
1995
1996 /* Bitwise and/xor/or operations */
1997
1998 #define MAX(x, y) ((x) < (y) ? (y) : (x))
1999 #define MIN(x, y) ((x) > (y) ? (y) : (x))
2000
2001 static PyObject *
2002 long_bitwise(PyLongObject *a,
2003 int op, /* '&', '|', '^' */
2004 PyLongObject *b)
2005 {
2006 digit maska, maskb; /* 0 or MASK */
2007 int negz;
2008 int size_a, size_b, size_z;
2009 PyLongObject *z;
2010 int i;
2011 digit diga, digb;
2012 PyObject *v;
2013
2014 if (a->ob_size < 0) {
2015 a = (PyLongObject *) long_invert(a);
2016 maska = MASK;
2017 }
2018 else {
2019 Py_INCREF(a);
2020 maska = 0;
2021 }
2022 if (b->ob_size < 0) {
2023 b = (PyLongObject *) long_invert(b);
2024 maskb = MASK;
2025 }
2026 else {
2027 Py_INCREF(b);
2028 maskb = 0;
2029 }
2030
2031 negz = 0;
2032 switch (op) {
2033 case '^':
2034 if (maska != maskb) {
2035 maska ^= MASK;
2036 negz = -1;
2037 }
2038 break;
2039 case '&':
2040 if (maska && maskb) {
2041 op = '|';
2042 maska ^= MASK;
2043 maskb ^= MASK;
2044 negz = -1;
2045 }
2046 break;
2047 case '|':
2048 if (maska || maskb) {
2049 op = '&';
2050 maska ^= MASK;
2051 maskb ^= MASK;
2052 negz = -1;
2053 }
2054 break;
2055 }
2056
2057 /* JRH: The original logic here was to allocate the result value (z)
2058 as the longer of the two operands. However, there are some cases
2059 where the result is guaranteed to be shorter than that: AND of two
2060 positives, OR of two negatives: use the shorter number. AND with
2061 mixed signs: use the positive number. OR with mixed signs: use the
2062 negative number. After the transformations above, op will be '&'
2063 iff one of these cases applies, and mask will be non-0 for operands
2064 whose length should be ignored.
2065 */
2066
2067 size_a = a->ob_size;
2068 size_b = b->ob_size;
2069 size_z = op == '&'
2070 ? (maska
2071 ? size_b
2072 : (maskb ? size_a : MIN(size_a, size_b)))
2073 : MAX(size_a, size_b);
2074 z = _PyLong_New(size_z);
2075 if (a == NULL || b == NULL || z == NULL) {
2076 Py_XDECREF(a);
2077 Py_XDECREF(b);
2078 Py_XDECREF(z);
2079 return NULL;
2080 }
2081
2082 for (i = 0; i < size_z; ++i) {
2083 diga = (i < size_a ? a->ob_digit[i] : 0) ^ maska;
2084 digb = (i < size_b ? b->ob_digit[i] : 0) ^ maskb;
2085 switch (op) {
2086 case '&': z->ob_digit[i] = diga & digb; break;
2087 case '|': z->ob_digit[i] = diga | digb; break;
2088 case '^': z->ob_digit[i] = diga ^ digb; break;
2089 }
2090 }
2091
2092 Py_DECREF(a);
2093 Py_DECREF(b);
2094 z = long_normalize(z);
2095 if (negz == 0)
2096 return (PyObject *) z;
2097 v = long_invert(z);
2098 Py_DECREF(z);
2099 return v;
2100 }
2101
2102 static PyObject *
2103 long_and(PyObject *v, PyObject *w)
2104 {
2105 PyLongObject *a, *b;
2106 PyObject *c;
2107 CONVERT_BINOP(v, w, &a, &b);
2108 c = long_bitwise(a, '&', b);
2109 Py_DECREF(a);
2110 Py_DECREF(b);
2111 return c;
2112 }
2113
2114 static PyObject *
2115 long_xor(PyObject *v, PyObject *w)
2116 {
2117 PyLongObject *a, *b;
2118 PyObject *c;
2119 CONVERT_BINOP(v, w, &a, &b);
2120 c = long_bitwise(a, '^', b);
2121 Py_DECREF(a);
2122 Py_DECREF(b);
2123 return c;
2124 }
2125
2126 static PyObject *
2127 long_or(PyObject *v, PyObject *w)
2128 {
2129 PyLongObject *a, *b;
2130 PyObject *c;
2131 CONVERT_BINOP(v, w, &a, &b);
2132 c = long_bitwise(a, '|', b);
2133 Py_DECREF(a);
2134 Py_DECREF(b);
2135 return c;
2136 }
2137
2138 static int
2139 long_coerce(PyObject **pv, PyObject **pw)
2140 {
2141 if (PyInt_Check(*pw)) {
2142 *pw = PyLong_FromLong(PyInt_AS_LONG(*pw));
2143 Py_INCREF(*pv);
2144 return 0;
2145 }
2146 else if (PyLong_Check(*pw)) {
2147 Py_INCREF(*pv);
2148 Py_INCREF(*pw);
2149 return 0;
2150 }
2151 return 1; /* Can't do it */
2152 }
2153
2154 static PyObject *
2155 long_int(PyObject *v)
2156 {
2157 long x;
2158 x = PyLong_AsLong(v);
2159 if (PyErr_Occurred())
2160 return NULL;
2161 return PyInt_FromLong(x);
2162 }
2163
2164 static PyObject *
2165 long_long(PyObject *v)
2166 {
2167 Py_INCREF(v);
2168 return v;
2169 }
2170
2171 static PyObject *
2172 long_float(PyObject *v)
2173 {
2174 double result;
2175 result = PyLong_AsDouble(v);
2176 if (result == -1.0 && PyErr_Occurred())
2177 return NULL;
2178 return PyFloat_FromDouble(result);
2179 }
2180
2181 static PyObject *
2182 long_oct(PyObject *v)
2183 {
2184 return long_format(v, 8, 1);
2185 }
2186
2187 static PyObject *
2188 long_hex(PyObject *v)
2189 {
2190 return long_format(v, 16, 1);
2191 }
2192 staticforward PyObject *
2193 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds);
2194
2195 static PyObject *
2196 long_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2197 {
2198 PyObject *x = NULL;
2199 int base = -909; /* unlikely! */
2200 static char *kwlist[] = {"x", "base", 0};
2201
2202 if (type != &PyLong_Type)
2203 return long_subtype_new(type, args, kwds); /* Wimp out */
2204 if (!PyArg_ParseTupleAndKeywords(args, kwds, "|Oi:long", kwlist,
2205 &x, &base))
2206 return NULL;
2207 if (x == NULL)
2208 return PyLong_FromLong(0L);
2209 if (base == -909)
2210 return PyNumber_Long(x);
2211 else if (PyString_Check(x))
2212 return PyLong_FromString(PyString_AS_STRING(x), NULL, base);
2213 #ifdef Py_USING_UNICODE
2214 else if (PyUnicode_Check(x))
2215 return PyLong_FromUnicode(PyUnicode_AS_UNICODE(x),
2216 PyUnicode_GET_SIZE(x),
2217 base);
2218 #endif
2219 else {
2220 PyErr_SetString(PyExc_TypeError,
2221 "long() can't convert non-string with explicit base");
2222 return NULL;
2223 }
2224 }
2225
2226 /* Wimpy, slow approach to tp_new calls for subtypes of long:
2227 first create a regular long from whatever arguments we got,
2228 then allocate a subtype instance and initialize it from
2229 the regular long. The regular long is then thrown away.
2230 */
2231 static PyObject *
2232 long_subtype_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2233 {
2234 PyLongObject *tmp, *new;
2235 int i, n;
2236
2237 assert(PyType_IsSubtype(type, &PyLong_Type));
2238 tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
2239 if (tmp == NULL)
2240 return NULL;
2241 assert(PyLong_CheckExact(tmp));
2242 n = tmp->ob_size;
2243 if (n < 0)
2244 n = -n;
2245 new = (PyLongObject *)type->tp_alloc(type, n);
2246 if (new == NULL)
2247 return NULL;
2248 assert(PyLong_Check(new));
2249 new->ob_size = tmp->ob_size;
2250 for (i = 0; i < n; i++)
2251 new->ob_digit[i] = tmp->ob_digit[i];
2252 Py_DECREF(tmp);
2253 return (PyObject *)new;
2254 }
2255
2256 static char long_doc[] =
2257 "long(x[, base]) -> integer\n\
2258 \n\
2259 Convert a string or number to a long integer, if possible. A floating\n\
2260 point argument will be truncated towards zero (this does not include a\n\
2261 string representation of a floating point number!) When converting a\n\
2262 string, use the optional base. It is an error to supply a base when\n\
2263 converting a non-string.";
2264
2265 static PyNumberMethods long_as_number = {
2266 (binaryfunc) long_add, /*nb_add*/
2267 (binaryfunc) long_sub, /*nb_subtract*/
2268 (binaryfunc) long_mul, /*nb_multiply*/
2269 (binaryfunc) long_classic_div, /*nb_divide*/
2270 (binaryfunc) long_mod, /*nb_remainder*/
2271 (binaryfunc) long_divmod, /*nb_divmod*/
2272 (ternaryfunc) long_pow, /*nb_power*/
2273 (unaryfunc) long_neg, /*nb_negative*/
2274 (unaryfunc) long_pos, /*tp_positive*/
2275 (unaryfunc) long_abs, /*tp_absolute*/
2276 (inquiry) long_nonzero, /*tp_nonzero*/
2277 (unaryfunc) long_invert, /*nb_invert*/
2278 (binaryfunc) long_lshift, /*nb_lshift*/
2279 (binaryfunc) long_rshift, /*nb_rshift*/
2280 (binaryfunc) long_and, /*nb_and*/
2281 (binaryfunc) long_xor, /*nb_xor*/
2282 (binaryfunc) long_or, /*nb_or*/
2283 (coercion) long_coerce, /*nb_coerce*/
2284 (unaryfunc) long_int, /*nb_int*/
2285 (unaryfunc) long_long, /*nb_long*/
2286 (unaryfunc) long_float, /*nb_float*/
2287 (unaryfunc) long_oct, /*nb_oct*/
2288 (unaryfunc) long_hex, /*nb_hex*/
2289 0, /* nb_inplace_add */
2290 0, /* nb_inplace_subtract */
2291 0, /* nb_inplace_multiply */
2292 0, /* nb_inplace_divide */
2293 0, /* nb_inplace_remainder */
2294 0, /* nb_inplace_power */
2295 0, /* nb_inplace_lshift */
2296 0, /* nb_inplace_rshift */
2297 0, /* nb_inplace_and */
2298 0, /* nb_inplace_xor */
2299 0, /* nb_inplace_or */
2300 (binaryfunc)long_div, /* nb_floor_divide */
2301 long_true_divide, /* nb_true_divide */
2302 0, /* nb_inplace_floor_divide */
2303 0, /* nb_inplace_true_divide */
2304 };
2305
2306 PyTypeObject PyLong_Type = {
2307 PyObject_HEAD_INIT(&PyType_Type)
2308 0, /* ob_size */
2309 "long", /* tp_name */
2310 sizeof(PyLongObject) - sizeof(digit), /* tp_basicsize */
2311 sizeof(digit), /* tp_itemsize */
2312 (destructor)long_dealloc, /* tp_dealloc */
2313 0, /* tp_print */
2314 0, /* tp_getattr */
2315 0, /* tp_setattr */
2316 (cmpfunc)long_compare, /* tp_compare */
2317 (reprfunc)long_repr, /* tp_repr */
2318 &long_as_number, /* tp_as_number */
2319 0, /* tp_as_sequence */
2320 0, /* tp_as_mapping */
2321 (hashfunc)long_hash, /* tp_hash */
2322 0, /* tp_call */
2323 (reprfunc)long_str, /* tp_str */
2324 PyObject_GenericGetAttr, /* tp_getattro */
2325 0, /* tp_setattro */
2326 0, /* tp_as_buffer */
2327 Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES |
2328 Py_TPFLAGS_BASETYPE, /* tp_flags */
2329 long_doc, /* tp_doc */
2330 0, /* tp_traverse */
2331 0, /* tp_clear */
2332 0, /* tp_richcompare */
2333 0, /* tp_weaklistoffset */
2334 0, /* tp_iter */
2335 0, /* tp_iternext */
2336 0, /* tp_methods */
2337 0, /* tp_members */
2338 0, /* tp_getset */
2339 0, /* tp_base */
2340 0, /* tp_dict */
2341 0, /* tp_descr_get */
2342 0, /* tp_descr_set */
2343 0, /* tp_dictoffset */
2344 0, /* tp_init */
2345 0, /* tp_alloc */
2346 long_new, /* tp_new */
2347 _PyObject_Del, /* tp_free */
2348 };