intobject.c 16.3 KB
Newer Older
1
/***********************************************************
2 3
Copyright 1991-1995 by Stichting Mathematisch Centrum, Amsterdam,
The Netherlands.
4 5 6

                        All Rights Reserved

7 8
Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
9
provided that the above copyright notice appear in all copies and that
10
both that copyright notice and this permission notice appear in
11
supporting documentation, and that the names of Stichting Mathematisch
12 13 14 15
Centrum or CWI or Corporation for National Research Initiatives or
CNRI not be used in advertising or publicity pertaining to
distribution of the software without specific, written prior
permission.
16

17 18 19 20 21 22 23 24 25 26 27 28
While CWI is the initial source for this software, a modified version
is made available by the Corporation for National Research Initiatives
(CNRI) at the Internet address ftp://ftp.python.org.

STICHTING MATHEMATISCH CENTRUM AND CNRI DISCLAIM ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH
CENTRUM OR CNRI BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
29 30 31

******************************************************************/

Guido van Rossum's avatar
Guido van Rossum committed
32 33
/* Integer object implementation */

34
#include "Python.h"
Guido van Rossum's avatar
Guido van Rossum committed
35

36
#ifdef HAVE_LIMITS_H
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
#include <limits.h>
#endif

#ifndef LONG_MAX
#define LONG_MAX 0X7FFFFFFFL
#endif

#ifndef LONG_MIN
#define LONG_MIN (-LONG_MAX-1)
#endif

#ifndef CHAR_BIT
#define CHAR_BIT 8
#endif

52
#ifndef LONG_BIT
53
#define LONG_BIT (CHAR_BIT * sizeof(long))
54
#endif
55

56
long
57
PyInt_GetMax()
58 59 60 61
{
	return LONG_MAX;	/* To initialize sys.maxint */
}

Guido van Rossum's avatar
Guido van Rossum committed
62
/* Standard Booleans */
Guido van Rossum's avatar
Guido van Rossum committed
63

64 65
PyIntObject _Py_ZeroStruct = {
	PyObject_HEAD_INIT(&PyInt_Type)
Guido van Rossum's avatar
Guido van Rossum committed
66 67
	0
};
Guido van Rossum's avatar
Guido van Rossum committed
68

69 70
PyIntObject _Py_TrueStruct = {
	PyObject_HEAD_INIT(&PyInt_Type)
Guido van Rossum's avatar
Guido van Rossum committed
71 72 73
	1
};

74
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
75 76
err_ovf(msg)
	char *msg;
Guido van Rossum's avatar
Guido van Rossum committed
77
{
78
	PyErr_SetString(PyExc_OverflowError, msg);
Guido van Rossum's avatar
Guido van Rossum committed
79 80 81
	return NULL;
}

Guido van Rossum's avatar
Guido van Rossum committed
82 83 84 85 86 87 88 89 90 91 92
/* Integers are quite normal objects, to make object handling uniform.
   (Using odd pointers to represent integers would save much space
   but require extra checks for this special case throughout the code.)
   Since, a typical Python program spends much of its time allocating
   and deallocating integers, these operations should be very fast.
   Therefore we use a dedicated allocation scheme with a much lower
   overhead (in space and time) than straight malloc(): a simple
   dedicated free list, filled when necessary with memory from malloc().
*/

#define BLOCK_SIZE	1000	/* 1K less typical malloc overhead */
93
#define N_INTOBJECTS	(BLOCK_SIZE / sizeof(PyIntObject))
Guido van Rossum's avatar
Guido van Rossum committed
94

95
static PyIntObject *
Guido van Rossum's avatar
Guido van Rossum committed
96 97
fill_free_list()
{
98 99
	PyIntObject *p, *q;
	p = PyMem_NEW(PyIntObject, N_INTOBJECTS);
Guido van Rossum's avatar
Guido van Rossum committed
100
	if (p == NULL)
101
		return (PyIntObject *)PyErr_NoMemory();
Guido van Rossum's avatar
Guido van Rossum committed
102 103
	q = p + N_INTOBJECTS;
	while (--q > p)
104 105
		*(PyIntObject **)q = q-1;
	*(PyIntObject **)q = NULL;
Guido van Rossum's avatar
Guido van Rossum committed
106 107 108
	return p + N_INTOBJECTS - 1;
}

109
static PyIntObject *free_list = NULL;
110 111 112 113 114 115 116 117 118 119 120 121
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS		100
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS		1
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* References to small integers are saved in this array so that they
   can be shared.
   The integers that are saved are those in the range
   -NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
122
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
123 124 125 126
#endif
#ifdef COUNT_ALLOCS
int quick_int_allocs, quick_neg_int_allocs;
#endif
Guido van Rossum's avatar
Guido van Rossum committed
127

128 129
PyObject *
PyInt_FromLong(ival)
Guido van Rossum's avatar
Guido van Rossum committed
130 131
	long ival;
{
132
	register PyIntObject *v;
133 134 135
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS &&
	    (v = small_ints[ival + NSMALLNEGINTS]) != NULL) {
136
		Py_INCREF(v);
137 138 139 140 141 142
#ifdef COUNT_ALLOCS
		if (ival >= 0)
			quick_int_allocs++;
		else
			quick_neg_int_allocs++;
#endif
143
		return (PyObject *) v;
144 145
	}
#endif
Guido van Rossum's avatar
Guido van Rossum committed
146 147 148
	if (free_list == NULL) {
		if ((free_list = fill_free_list()) == NULL)
			return NULL;
Guido van Rossum's avatar
Guido van Rossum committed
149
	}
Guido van Rossum's avatar
Guido van Rossum committed
150
	v = free_list;
151 152
	free_list = *(PyIntObject **)free_list;
	v->ob_type = &PyInt_Type;
Guido van Rossum's avatar
Guido van Rossum committed
153
	v->ob_ival = ival;
154
	_Py_NewReference(v);
155 156 157
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
		/* save this one for a following allocation */
158
		Py_INCREF(v);
159 160 161
		small_ints[ival + NSMALLNEGINTS] = v;
	}
#endif
162
	return (PyObject *) v;
Guido van Rossum's avatar
Guido van Rossum committed
163 164 165 166
}

static void
int_dealloc(v)
167
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
168
{
169
	*(PyIntObject **)v = free_list;
Guido van Rossum's avatar
Guido van Rossum committed
170
	free_list = v;
Guido van Rossum's avatar
Guido van Rossum committed
171 172 173
}

long
174 175
PyInt_AsLong(op)
	register PyObject *op;
Guido van Rossum's avatar
Guido van Rossum committed
176
{
177 178
	PyNumberMethods *nb;
	PyIntObject *io;
179 180
	long val;
	
181 182
	if (op && PyInt_Check(op))
		return PyInt_AS_LONG((PyIntObject*) op);
183 184 185
	
	if (op == NULL || (nb = op->ob_type->tp_as_number) == NULL ||
	    nb->nb_int == NULL) {
186
		PyErr_BadArgument();
Guido van Rossum's avatar
Guido van Rossum committed
187 188
		return -1;
	}
189
	
190
	io = (PyIntObject*) (*nb->nb_int) (op);
191 192
	if (io == NULL)
		return -1;
193 194 195
	if (!PyInt_Check(io)) {
		PyErr_SetString(PyExc_TypeError,
				"nb_int should return int object");
196 197 198
		return -1;
	}
	
199 200
	val = PyInt_AS_LONG(io);
	Py_DECREF(io);
201 202
	
	return val;
Guido van Rossum's avatar
Guido van Rossum committed
203 204 205 206
}

/* Methods */

Guido van Rossum's avatar
Guido van Rossum committed
207
/* ARGSUSED */
208
static int
Guido van Rossum's avatar
Guido van Rossum committed
209
int_print(v, fp, flags)
210
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
211
	FILE *fp;
Guido van Rossum's avatar
Guido van Rossum committed
212
	int flags; /* Not used but required by interface */
Guido van Rossum's avatar
Guido van Rossum committed
213 214
{
	fprintf(fp, "%ld", v->ob_ival);
215
	return 0;
Guido van Rossum's avatar
Guido van Rossum committed
216 217
}

218
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
219
int_repr(v)
220
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
221 222 223
{
	char buf[20];
	sprintf(buf, "%ld", v->ob_ival);
224
	return PyString_FromString(buf);
Guido van Rossum's avatar
Guido van Rossum committed
225 226 227
}

static int
Guido van Rossum's avatar
Guido van Rossum committed
228
int_compare(v, w)
229
	PyIntObject *v, *w;
Guido van Rossum's avatar
Guido van Rossum committed
230 231 232 233 234 235
{
	register long i = v->ob_ival;
	register long j = w->ob_ival;
	return (i < j) ? -1 : (i > j) ? 1 : 0;
}

236 237
static long
int_hash(v)
238
	PyIntObject *v;
239
{
240 241
	/* XXX If this is changed, you also need to change the way
	   Python's long, float and complex types are hashed. */
242 243 244 245 246 247
	long x = v -> ob_ival;
	if (x == -1)
		x = -2;
	return x;
}

248
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
249
int_add(v, w)
250 251
	PyIntObject *v;
	PyIntObject *w;
Guido van Rossum's avatar
Guido van Rossum committed
252 253 254
{
	register long a, b, x;
	a = v->ob_ival;
255
	b = w->ob_ival;
Guido van Rossum's avatar
Guido van Rossum committed
256
	x = a + b;
Guido van Rossum's avatar
Guido van Rossum committed
257
	if ((x^a) < 0 && (x^b) < 0)
Guido van Rossum's avatar
Guido van Rossum committed
258
		return err_ovf("integer addition");
259
	return PyInt_FromLong(x);
Guido van Rossum's avatar
Guido van Rossum committed
260 261
}

262
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
263
int_sub(v, w)
264 265
	PyIntObject *v;
	PyIntObject *w;
Guido van Rossum's avatar
Guido van Rossum committed
266 267 268
{
	register long a, b, x;
	a = v->ob_ival;
269
	b = w->ob_ival;
Guido van Rossum's avatar
Guido van Rossum committed
270
	x = a - b;
Guido van Rossum's avatar
Guido van Rossum committed
271
	if ((x^a) < 0 && (x^~b) < 0)
Guido van Rossum's avatar
Guido van Rossum committed
272
		return err_ovf("integer subtraction");
273
	return PyInt_FromLong(x);
Guido van Rossum's avatar
Guido van Rossum committed
274 275
}

276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
/*
Integer overflow checking used to be done using a double, but on 64
bit machines (where both long and double are 64 bit) this fails
because the double doesn't have enouvg precision.  John Tromp suggests
the following algorithm:

Suppose again we normalize a and b to be nonnegative.
Let ah and al (bh and bl) be the high and low 32 bits of a (b, resp.).
Now we test ah and bh against zero and get essentially 3 possible outcomes.

1) both ah and bh > 0 : then report overflow

2) both ah and bh = 0 : then compute a*b and report overflow if it comes out
                        negative

3) ah > 0 and bh = 0  : compute ah*bl and report overflow if it's >= 2^31
                        compute al*bl and report overflow if it's negative
                        add (ah*bl)<<32 to al*bl and report overflow if
                        it's negative

In case of no overflow the result is then negated if necessary.

The majority of cases will be 2), in which case this method is the same as
what I suggested before. If multiplication is expensive enough, then the
other method is faster on case 3), but also more work to program, so I
guess the above is the preferred solution.

*/

305
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
306
int_mul(v, w)
307 308
	PyIntObject *v;
	PyIntObject *w;
Guido van Rossum's avatar
Guido van Rossum committed
309
{
310 311 312
	long a, b, ah, bh, x, y;
	int s = 1;

Guido van Rossum's avatar
Guido van Rossum committed
313
	a = v->ob_ival;
314
	b = w->ob_ival;
315 316 317 318 319 320 321 322 323
	ah = a >> (LONG_BIT/2);
	bh = b >> (LONG_BIT/2);

	/* Quick test for common case: two small positive ints */

	if (ah == 0 && bh == 0) {
		x = a*b;
		if (x < 0)
			goto bad;
324
		return PyInt_FromLong(x);
325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
	}

	/* Arrange that a >= b >= 0 */

	if (a < 0) {
		a = -a;
		if (a < 0) {
			/* Largest negative */
			if (b == 0 || b == 1) {
				x = a*b;
				goto ok;
			}
			else
				goto bad;
		}
		s = -s;
		ah = a >> (LONG_BIT/2);
	}
	if (b < 0) {
		b = -b;
		if (b < 0) {
			/* Largest negative */
347
			if (a == 0 || (a == 1 && s == 1)) {
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369
				x = a*b;
				goto ok;
			}
			else
				goto bad;
		}
		s = -s;
		bh = b >> (LONG_BIT/2);
	}

	/* 1) both ah and bh > 0 : then report overflow */

	if (ah != 0 && bh != 0)
		goto bad;

	/* 2) both ah and bh = 0 : then compute a*b and report
				   overflow if it comes out negative */

	if (ah == 0 && bh == 0) {
		x = a*b;
		if (x < 0)
			goto bad;
370
		return PyInt_FromLong(x*s);
371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
	}

	if (a < b) {
		/* Swap */
		x = a;
		a = b;
		b = x;
		ah = bh;
		/* bh not used beyond this point */
	}

	/* 3) ah > 0 and bh = 0  : compute ah*bl and report overflow if
				   it's >= 2^31
                        compute al*bl and report overflow if it's negative
                        add (ah*bl)<<32 to al*bl and report overflow if
                        it's negative
			(NB b == bl in this case, and we make a = al) */

	y = ah*b;
390
	if (y >= (1L << (LONG_BIT/2 - 1)))
391 392 393 394 395
		goto bad;
	a &= (1L << (LONG_BIT/2)) - 1;
	x = a*b;
	if (x < 0)
		goto bad;
396
	x += y << (LONG_BIT/2);
397 398 399
	if (x < 0)
		goto bad;
 ok:
400
	return PyInt_FromLong(x * s);
401 402 403

 bad:
	return err_ovf("integer multiplication");
Guido van Rossum's avatar
Guido van Rossum committed
404 405
}

406 407
static int
i_divmod(x, y, p_xdivy, p_xmody)
408
	register PyIntObject *x, *y;
409
	long *p_xdivy, *p_xmody;
Guido van Rossum's avatar
Guido van Rossum committed
410
{
411 412 413 414 415
	long xi = x->ob_ival;
	long yi = y->ob_ival;
	long xdivy, xmody;
	
	if (yi == 0) {
416 417
		PyErr_SetString(PyExc_ZeroDivisionError,
				"integer division or modulo");
418
		return -1;
Guido van Rossum's avatar
Guido van Rossum committed
419
	}
420 421 422
	if (yi < 0) {
		if (xi < 0)
			xdivy = -xi / -yi;
423
		else
424
			xdivy = - (xi / -yi);
425 426
	}
	else {
427 428
		if (xi < 0)
			xdivy = - (-xi / yi);
429
		else
430
			xdivy = xi / yi;
431
	}
432
	xmody = xi - xdivy*yi;
433
	if ((xmody < 0 && yi > 0) || (xmody > 0 && yi < 0)) {
434 435 436 437 438 439
		xmody += yi;
		xdivy -= 1;
	}
	*p_xdivy = xdivy;
	*p_xmody = xmody;
	return 0;
Guido van Rossum's avatar
Guido van Rossum committed
440 441
}

442
static PyObject *
443
int_div(x, y)
444 445
	PyIntObject *x;
	PyIntObject *y;
Guido van Rossum's avatar
Guido van Rossum committed
446
{
447 448
	long d, m;
	if (i_divmod(x, y, &d, &m) < 0)
Guido van Rossum's avatar
Guido van Rossum committed
449
		return NULL;
450
	return PyInt_FromLong(d);
451 452
}

453
static PyObject *
454
int_mod(x, y)
455 456
	PyIntObject *x;
	PyIntObject *y;
457 458 459 460
{
	long d, m;
	if (i_divmod(x, y, &d, &m) < 0)
		return NULL;
461
	return PyInt_FromLong(m);
Guido van Rossum's avatar
Guido van Rossum committed
462 463
}

464
static PyObject *
465
int_divmod(x, y)
466 467
	PyIntObject *x;
	PyIntObject *y;
468
{
469 470
	long d, m;
	if (i_divmod(x, y, &d, &m) < 0)
471
		return NULL;
472
	return Py_BuildValue("(ll)", d, m);
473 474
}

475
static PyObject *
476
int_pow(v, w, z)
477 478 479
	PyIntObject *v;
	PyIntObject *w;
	PyIntObject *z;
Guido van Rossum's avatar
Guido van Rossum committed
480
{
481
#if 1
482
	register long iv, iw, iz=0, ix, temp, prev;
483 484 485
	iv = v->ob_ival;
	iw = w->ob_ival;
	if (iw < 0) {
486 487
		PyErr_SetString(PyExc_ValueError,
				"integer to the negative power");
488 489
		return NULL;
	}
490
 	if ((PyObject *)z != Py_None) {
491
		iz = z->ob_ival;
492
		if (iz == 0) {
493 494
			PyErr_SetString(PyExc_ValueError,
					"pow(x, y, z) with z==0");
495 496
			return NULL;
		}
497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
	}
	/*
	 * XXX: The original exponentiation code stopped looping
	 * when temp hit zero; this code will continue onwards
	 * unnecessarily, but at least it won't cause any errors.
	 * Hopefully the speed improvement from the fast exponentiation
	 * will compensate for the slight inefficiency.
	 * XXX: Better handling of overflows is desperately needed.
	 */
 	temp = iv;
	ix = 1;
	while (iw > 0) {
	 	prev = ix;	/* Save value for overflow check */
	 	if (iw & 1) {	
		 	ix = ix*temp;
			if (temp == 0)
				break; /* Avoid ix / 0 */
			if (ix / temp != prev)
				return err_ovf("integer pow()");
		}
	 	iw >>= 1;	/* Shift exponent down by 1 bit */
	        if (iw==0) break;
	 	prev = temp;
	 	temp *= temp;	/* Square the value of temp */
	 	if (prev!=0 && temp/prev!=prev)
			return err_ovf("integer pow()");
523
	 	if (iz) {
524 525 526 527 528
			/* If we did a multiplication, perform a modulo */
		 	ix = ix % iz;
		 	temp = temp % iz;
		}
	}
529
	if (iz) {
530
	 	PyObject *t1, *t2;
531
	 	long int div, mod;
532 533
	 	t1=PyInt_FromLong(ix); 
		t2=PyInt_FromLong(iz);
534
	 	if (t1==NULL || t2==NULL ||
535 536 537 538 539
	 		i_divmod((PyIntObject *)t1,
				 (PyIntObject *)t2, &div, &mod)<0)
		{
		 	Py_XDECREF(t1);
		 	Py_XDECREF(t2);
540 541
			return(NULL);
		}
542 543
		Py_DECREF(t1);
		Py_DECREF(t2);
544 545
	 	ix=mod;
	}
546
	return PyInt_FromLong(ix);
547
#else
Guido van Rossum's avatar
Guido van Rossum committed
548 549
	register long iv, iw, ix;
	iv = v->ob_ival;
550
	iw = w->ob_ival;
551
	if (iw < 0) {
552 553
		PyErr_SetString(PyExc_ValueError,
				"integer to the negative power");
554 555
		return NULL;
	}
556 557 558
	if ((PyObject *)z != Py_None) {
		PyErr_SetString(PyExc_TypeError,
				"pow(int, int, int) not yet supported");
559 560
		return NULL;
	}
Guido van Rossum's avatar
Guido van Rossum committed
561
	ix = 1;
562 563
	while (--iw >= 0) {
		long prev = ix;
Guido van Rossum's avatar
Guido van Rossum committed
564
		ix = ix * iv;
565 566 567
		if (iv == 0)
			break; /* 0 to some power -- avoid ix / 0 */
		if (ix / iv != prev)
Guido van Rossum's avatar
Guido van Rossum committed
568
			return err_ovf("integer pow()");
Guido van Rossum's avatar
Guido van Rossum committed
569
	}
570
	return PyInt_FromLong(ix);
571 572
#endif
}				
Guido van Rossum's avatar
Guido van Rossum committed
573

574
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
575
int_neg(v)
576
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
577 578 579 580
{
	register long a, x;
	a = v->ob_ival;
	x = -a;
Guido van Rossum's avatar
Guido van Rossum committed
581
	if (a < 0 && x < 0)
Guido van Rossum's avatar
Guido van Rossum committed
582
		return err_ovf("integer negation");
583
	return PyInt_FromLong(x);
Guido van Rossum's avatar
Guido van Rossum committed
584 585
}

586
static PyObject *
Guido van Rossum's avatar
Guido van Rossum committed
587
int_pos(v)
588
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
589
{
590 591
	Py_INCREF(v);
	return (PyObject *)v;
Guido van Rossum's avatar
Guido van Rossum committed
592 593
}

594
static PyObject *
595
int_abs(v)
596
	PyIntObject *v;
597 598 599 600 601 602 603
{
	if (v->ob_ival >= 0)
		return int_pos(v);
	else
		return int_neg(v);
}

Guido van Rossum's avatar
Guido van Rossum committed
604 605
static int
int_nonzero(v)
606
	PyIntObject *v;
Guido van Rossum's avatar
Guido van Rossum committed
607 608 609 610
{
	return v->ob_ival != 0;
}

611
static PyObject *
612
int_invert(v)
613
	PyIntObject *v;
614
{
615
	return PyInt_FromLong(~v->ob_ival);
616 617
}

618
static PyObject *
619
int_lshift(v, w)
620 621
	PyIntObject *v;
	PyIntObject *w;
622 623 624
{
	register long a, b;
	a = v->ob_ival;
625
	b = w->ob_ival;
626
	if (b < 0) {
627
		PyErr_SetString(PyExc_ValueError, "negative shift count");
628 629 630
		return NULL;
	}
	if (a == 0 || b == 0) {
631 632
		Py_INCREF(v);
		return (PyObject *) v;
633
	}
634
	if (b >= LONG_BIT) {
635
		return PyInt_FromLong(0L);
636 637
	}
	a = (unsigned long)a << b;
638
	return PyInt_FromLong(a);
639 640
}

641
static PyObject *
642
int_rshift(v, w)
643 644
	PyIntObject *v;
	PyIntObject *w;
645 646 647
{
	register long a, b;
	a = v->ob_ival;
648
	b = w->ob_ival;
649
	if (b < 0) {
650
		PyErr_SetString(PyExc_ValueError, "negative shift count");
651 652 653
		return NULL;
	}
	if (a == 0 || b == 0) {
654 655
		Py_INCREF(v);
		return (PyObject *) v;
656
	}
657
	if (b >= LONG_BIT) {
658 659 660 661 662 663 664 665 666 667 668
		if (a < 0)
			a = -1;
		else
			a = 0;
	}
	else {
		if (a < 0)
			a = ~( ~(unsigned long)a >> b );
		else
			a = (unsigned long)a >> b;
	}
669
	return PyInt_FromLong(a);
670 671
}

672
static PyObject *
673
int_and(v, w)
674 675
	PyIntObject *v;
	PyIntObject *w;
676 677 678
{
	register long a, b;
	a = v->ob_ival;
679
	b = w->ob_ival;
680
	return PyInt_FromLong(a & b);
681 682
}

683
static PyObject *
684
int_xor(v, w)
685 686
	PyIntObject *v;
	PyIntObject *w;
687 688 689
{
	register long a, b;
	a = v->ob_ival;
690
	b = w->ob_ival;
691
	return PyInt_FromLong(a ^ b);
692 693
}

694
static PyObject *
695
int_or(v, w)
696 697
	PyIntObject *v;
	PyIntObject *w;
698 699 700
{
	register long a, b;
	a = v->ob_ival;
701
	b = w->ob_ival;
702
	return PyInt_FromLong(a | b);
703 704
}

705
static PyObject *
706
int_int(v)
707
	PyIntObject *v;
708
{
709 710
	Py_INCREF(v);
	return (PyObject *)v;
711 712
}

713
static PyObject *
714
int_long(v)
715
	PyIntObject *v;
716
{
717
	return PyLong_FromLong((v -> ob_ival));
718 719
}

720
static PyObject *
721
int_float(v)
722
	PyIntObject *v;
723
{
724
	return PyFloat_FromDouble((double)(v -> ob_ival));
725 726
}

727
static PyObject *
728
int_oct(v)
729
	PyIntObject *v;
730
{
731
	char buf[100];
732
	long x = v -> ob_ival;
733 734 735
	if (x == 0)
		strcpy(buf, "0");
	else
736
		sprintf(buf, "0%lo", x);
737
	return PyString_FromString(buf);
738 739
}

740
static PyObject *
741
int_hex(v)
742
	PyIntObject *v;
743
{
744
	char buf[100];
745
	long x = v -> ob_ival;
746
	sprintf(buf, "0x%lx", x);
747
	return PyString_FromString(buf);
748 749
}

750
static PyNumberMethods int_as_number = {
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767
	(binaryfunc)int_add, /*nb_add*/
	(binaryfunc)int_sub, /*nb_subtract*/
	(binaryfunc)int_mul, /*nb_multiply*/
	(binaryfunc)int_div, /*nb_divide*/
	(binaryfunc)int_mod, /*nb_remainder*/
	(binaryfunc)int_divmod, /*nb_divmod*/
	(ternaryfunc)int_pow, /*nb_power*/
	(unaryfunc)int_neg, /*nb_negative*/
	(unaryfunc)int_pos, /*nb_positive*/
	(unaryfunc)int_abs, /*nb_absolute*/
	(inquiry)int_nonzero, /*nb_nonzero*/
	(unaryfunc)int_invert, /*nb_invert*/
	(binaryfunc)int_lshift, /*nb_lshift*/
	(binaryfunc)int_rshift, /*nb_rshift*/
	(binaryfunc)int_and, /*nb_and*/
	(binaryfunc)int_xor, /*nb_xor*/
	(binaryfunc)int_or, /*nb_or*/
768
	0,		/*nb_coerce*/
769 770 771 772 773
	(unaryfunc)int_int, /*nb_int*/
	(unaryfunc)int_long, /*nb_long*/
	(unaryfunc)int_float, /*nb_float*/
	(unaryfunc)int_oct, /*nb_oct*/
	(unaryfunc)int_hex, /*nb_hex*/
Guido van Rossum's avatar
Guido van Rossum committed
774 775
};

776 777
PyTypeObject PyInt_Type = {
	PyObject_HEAD_INIT(&PyType_Type)
Guido van Rossum's avatar
Guido van Rossum committed
778 779
	0,
	"int",
780
	sizeof(PyIntObject),
Guido van Rossum's avatar
Guido van Rossum committed
781
	0,
782 783
	(destructor)int_dealloc, /*tp_dealloc*/
	(printfunc)int_print, /*tp_print*/
Guido van Rossum's avatar
Guido van Rossum committed
784 785
	0,		/*tp_getattr*/
	0,		/*tp_setattr*/
786 787
	(cmpfunc)int_compare, /*tp_compare*/
	(reprfunc)int_repr, /*tp_repr*/
Guido van Rossum's avatar
Guido van Rossum committed
788 789 790
	&int_as_number,	/*tp_as_number*/
	0,		/*tp_as_sequence*/
	0,		/*tp_as_mapping*/
791
	(hashfunc)int_hash, /*tp_hash*/
Guido van Rossum's avatar
Guido van Rossum committed
792
};
793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809

void
PyInt_Fini()
{
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
	int i;
	PyIntObject **p;

	i = NSMALLNEGINTS + NSMALLPOSINTS;
	p = small_ints;
	while (--i >= 0) {
		Py_XDECREF(*p);
		*p++ = NULL;
	}
#endif
	/* XXX Alas, the free list is not easily and safely freeable */
}