Python code coverage for Objects/longobject.c

#	count	content
1	n/a	/* Long (arbitrary precision) integer object implementation */
2	n/a
3	n/a	/* XXX The functional organization of this file is terrible */
4	n/a
5	n/a	#include "Python.h"
6	n/a	#include "longintrepr.h"
7	n/a
8	n/a	#include <float.h>
9	n/a	#include <ctype.h>
10	n/a	#include <stddef.h>
11	n/a
12	n/a	#include "clinic/longobject.c.h"
13	n/a	/*[clinic input]
14	n/a	class int "PyObject *" "&PyLong_Type"
15	n/a	[clinic start generated code]*/
16	n/a	/[clinic end generated code: output=da39a3ee5e6b4b0d input=ec0275e3422a36e3]/
17	n/a
18	n/a	#ifndef NSMALLPOSINTS
19	n/a	#define NSMALLPOSINTS 257
20	n/a	#endif
21	n/a	#ifndef NSMALLNEGINTS
22	n/a	#define NSMALLNEGINTS 5
23	n/a	#endif
24	n/a
25	n/a	_Py_IDENTIFIER(little);
26	n/a	_Py_IDENTIFIER(big);
27	n/a
28	n/a	/* convert a PyLong of size 1, 0 or -1 to an sdigit */
29	n/a	#define MEDIUM_VALUE(x) (assert(-1 <= Py_SIZE(x) && Py_SIZE(x) <= 1), \
30	n/a	Py_SIZE(x) < 0 ? -(sdigit)(x)->ob_digit[0] : \
31	n/a	(Py_SIZE(x) == 0 ? (sdigit)0 : \
32	n/a	(sdigit)(x)->ob_digit[0]))
33	n/a
34	n/a	#if NSMALLNEGINTS + NSMALLPOSINTS > 0
35	n/a	/* Small integers are preallocated in this array so that they
36	n/a	can be shared.
37	n/a	The integers that are preallocated are those in the range
38	n/a	-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
39	n/a	*/
40	n/a	static PyLongObject small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
41	n/a	#ifdef COUNT_ALLOCS
42	n/a	Py_ssize_t quick_int_allocs, quick_neg_int_allocs;
43	n/a	#endif
44	n/a
45	n/a	static PyObject *
46	n/a	get_small_int(sdigit ival)
47	n/a	{
48	n/a	PyObject *v;
49	n/a	assert(-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS);
50	n/a	v = (PyObject *)&small_ints[ival + NSMALLNEGINTS];
51	n/a	Py_INCREF(v);
52	n/a	#ifdef COUNT_ALLOCS
53	n/a	if (ival >= 0)
54	n/a	quick_int_allocs++;
55	n/a	else
56	n/a	quick_neg_int_allocs++;
57	n/a	#endif
58	n/a	return v;
59	n/a	}
60	n/a	#define CHECK_SMALL_INT(ival) \
61	n/a	do if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) { \
62	n/a	return get_small_int((sdigit)ival); \
63	n/a	} while(0)
64	n/a
65	n/a	static PyLongObject *
66	n/a	maybe_small_long(PyLongObject *v)
67	n/a	{
68	n/a	if (v && Py_ABS(Py_SIZE(v)) <= 1) {
69	n/a	sdigit ival = MEDIUM_VALUE(v);
70	n/a	if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
71	n/a	Py_DECREF(v);
72	n/a	return (PyLongObject *)get_small_int(ival);
73	n/a	}
74	n/a	}
75	n/a	return v;
76	n/a	}
77	n/a	#else
78	n/a	#define CHECK_SMALL_INT(ival)
79	n/a	#define maybe_small_long(val) (val)
80	n/a	#endif
81	n/a
82	n/a	/* If a freshly-allocated int is already shared, it must
83	n/a	be a small integer, so negating it must go to PyLong_FromLong */
84	n/a	Py_LOCAL_INLINE(void)
85	n/a	_PyLong_Negate(PyLongObject **x_p)
86	n/a	{
87	n/a	PyLongObject *x;
88	n/a
89	n/a	x = (PyLongObject )x_p;
90	n/a	if (Py_REFCNT(x) == 1) {
91	n/a	Py_SIZE(x) = -Py_SIZE(x);
92	n/a	return;
93	n/a	}
94	n/a
95	n/a	x_p = (PyLongObject )PyLong_FromLong(-MEDIUM_VALUE(x));
96	n/a	Py_DECREF(x);
97	n/a	}
98	n/a
99	n/a	/* For int multiplication, use the O(N**2) school algorithm unless
100	n/a	* both operands contain more than KARATSUBA_CUTOFF digits (this
101	n/a	* being an internal Python int digit, in base BASE).
102	n/a	*/
103	n/a	#define KARATSUBA_CUTOFF 70
104	n/a	#define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
105	n/a
106	n/a	/* For exponentiation, use the binary left-to-right algorithm
107	n/a	* unless the exponent contains more than FIVEARY_CUTOFF digits.
108	n/a	* In that case, do 5 bits at a time. The potential drawback is that
109	n/a	* a table of 2**5 intermediate results is computed.
110	n/a	*/
111	n/a	#define FIVEARY_CUTOFF 8
112	n/a
113	n/a	#define SIGCHECK(PyTryBlock) \
114	n/a	do { \
115	n/a	if (PyErr_CheckSignals()) PyTryBlock \
116	n/a	} while(0)
117	n/a
118	n/a	/* Normalize (remove leading zeros from) an int object.
119	n/a	Doesn't attempt to free the storage--in most cases, due to the nature
120	n/a	of the algorithms used, this could save at most be one word anyway. */
121	n/a
122	n/a	static PyLongObject *
123	n/a	long_normalize(PyLongObject *v)
124	n/a	{
125	n/a	Py_ssize_t j = Py_ABS(Py_SIZE(v));
126	n/a	Py_ssize_t i = j;
127	n/a
128	n/a	while (i > 0 && v->ob_digit[i-1] == 0)
129	n/a	--i;
130	n/a	if (i != j)
131	n/a	Py_SIZE(v) = (Py_SIZE(v) < 0) ? -(i) : i;
132	n/a	return v;
133	n/a	}
134	n/a
135	n/a	/* _PyLong_FromNbInt: Convert the given object to a PyLongObject
136	n/a	using the nb_int slot, if available. Raise TypeError if either the
137	n/a	nb_int slot is not available or the result of the call to nb_int
138	n/a	returns something not of type int.
139	n/a	*/
140	n/a	PyLongObject *
141	n/a	_PyLong_FromNbInt(PyObject *integral)
142	n/a	{
143	n/a	PyNumberMethods *nb;
144	n/a	PyObject *result;
145	n/a
146	n/a	/* Fast path for the case that we already have an int. */
147	n/a	if (PyLong_CheckExact(integral)) {
148	n/a	Py_INCREF(integral);
149	n/a	return (PyLongObject *)integral;
150	n/a	}
151	n/a
152	n/a	nb = Py_TYPE(integral)->tp_as_number;
153	n/a	if (nb == NULL \|\| nb->nb_int == NULL) {
154	n/a	PyErr_Format(PyExc_TypeError,
155	n/a	"an integer is required (got type %.200s)",
156	n/a	Py_TYPE(integral)->tp_name);
157	n/a	return NULL;
158	n/a	}
159	n/a
160	n/a	/* Convert using the nb_int slot, which should return something
161	n/a	of exact type int. */
162	n/a	result = nb->nb_int(integral);
163	n/a	if (!result \|\| PyLong_CheckExact(result))
164	n/a	return (PyLongObject *)result;
165	n/a	if (!PyLong_Check(result)) {
166	n/a	PyErr_Format(PyExc_TypeError,
167	n/a	"__int__ returned non-int (type %.200s)",
168	n/a	result->ob_type->tp_name);
169	n/a	Py_DECREF(result);
170	n/a	return NULL;
171	n/a	}
172	n/a	/* Issue #17576: warn if 'result' not of exact type int. */
173	n/a	if (PyErr_WarnFormat(PyExc_DeprecationWarning, 1,
174	n/a	"__int__ returned non-int (type %.200s). "
175	n/a	"The ability to return an instance of a strict subclass of int "
176	n/a	"is deprecated, and may be removed in a future version of Python.",
177	n/a	result->ob_type->tp_name)) {
178	n/a	Py_DECREF(result);
179	n/a	return NULL;
180	n/a	}
181	n/a	return (PyLongObject *)result;
182	n/a	}
183	n/a
184	n/a
185	n/a	/* Allocate a new int object with size digits.
186	n/a	Return NULL and set exception if we run out of memory. */
187	n/a
188	n/a	#define MAX_LONG_DIGITS \
189	n/a	((PY_SSIZE_T_MAX - offsetof(PyLongObject, ob_digit))/sizeof(digit))
190	n/a
191	n/a	PyLongObject *
192	n/a	_PyLong_New(Py_ssize_t size)
193	n/a	{
194	n/a	PyLongObject *result;
195	n/a	/* Number of bytes needed is: offsetof(PyLongObject, ob_digit) +
196	n/a	sizeof(digit)*size. Previous incarnations of this code used
197	n/a	sizeof(PyVarObject) instead of the offsetof, but this risks being
198	n/a	incorrect in the presence of padding between the PyVarObject header
199	n/a	and the digits. */
200	n/a	if (size > (Py_ssize_t)MAX_LONG_DIGITS) {
201	n/a	PyErr_SetString(PyExc_OverflowError,
202	n/a	"too many digits in integer");
203	n/a	return NULL;
204	n/a	}
205	n/a	result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
206	n/a	size*sizeof(digit));
207	n/a	if (!result) {
208	n/a	PyErr_NoMemory();
209	n/a	return NULL;
210	n/a	}
211	n/a	return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
212	n/a	}
213	n/a
214	n/a	PyObject *
215	n/a	_PyLong_Copy(PyLongObject *src)
216	n/a	{
217	n/a	PyLongObject *result;
218	n/a	Py_ssize_t i;
219	n/a
220	n/a	assert(src != NULL);
221	n/a	i = Py_SIZE(src);
222	n/a	if (i < 0)
223	n/a	i = -(i);
224	n/a	if (i < 2) {
225	n/a	sdigit ival = MEDIUM_VALUE(src);
226	n/a	CHECK_SMALL_INT(ival);
227	n/a	}
228	n/a	result = _PyLong_New(i);
229	n/a	if (result != NULL) {
230	n/a	Py_SIZE(result) = Py_SIZE(src);
231	n/a	while (--i >= 0)
232	n/a	result->ob_digit[i] = src->ob_digit[i];
233	n/a	}
234	n/a	return (PyObject *)result;
235	n/a	}
236	n/a
237	n/a	/* Create a new int object from a C long int */
238	n/a
239	n/a	PyObject *
240	n/a	PyLong_FromLong(long ival)
241	n/a	{
242	n/a	PyLongObject *v;
243	n/a	unsigned long abs_ival;
244	n/a	unsigned long t; /* unsigned so >> doesn't propagate sign bit */
245	n/a	int ndigits = 0;
246	n/a	int sign;
247	n/a
248	n/a	CHECK_SMALL_INT(ival);
249	n/a
250	n/a	if (ival < 0) {
251	n/a	/* negate: can't write this as abs_ival = -ival since that
252	n/a	invokes undefined behaviour when ival is LONG_MIN */
253	n/a	abs_ival = 0U-(unsigned long)ival;
254	n/a	sign = -1;
255	n/a	}
256	n/a	else {
257	n/a	abs_ival = (unsigned long)ival;
258	n/a	sign = ival == 0 ? 0 : 1;
259	n/a	}
260	n/a
261	n/a	/* Fast path for single-digit ints */
262	n/a	if (!(abs_ival >> PyLong_SHIFT)) {
263	n/a	v = _PyLong_New(1);
264	n/a	if (v) {
265	n/a	Py_SIZE(v) = sign;
266	n/a	v->ob_digit[0] = Py_SAFE_DOWNCAST(
267	n/a	abs_ival, unsigned long, digit);
268	n/a	}
269	n/a	return (PyObject*)v;
270	n/a	}
271	n/a
272	n/a	#if PyLong_SHIFT==15
273	n/a	/* 2 digits */
274	n/a	if (!(abs_ival >> 2*PyLong_SHIFT)) {
275	n/a	v = _PyLong_New(2);
276	n/a	if (v) {
277	n/a	Py_SIZE(v) = 2*sign;
278	n/a	v->ob_digit[0] = Py_SAFE_DOWNCAST(
279	n/a	abs_ival & PyLong_MASK, unsigned long, digit);
280	n/a	v->ob_digit[1] = Py_SAFE_DOWNCAST(
281	n/a	abs_ival >> PyLong_SHIFT, unsigned long, digit);
282	n/a	}
283	n/a	return (PyObject*)v;
284	n/a	}
285	n/a	#endif
286	n/a
287	n/a	/* Larger numbers: loop to determine number of digits */
288	n/a	t = abs_ival;
289	n/a	while (t) {
290	n/a	++ndigits;
291	n/a	t >>= PyLong_SHIFT;
292	n/a	}
293	n/a	v = _PyLong_New(ndigits);
294	n/a	if (v != NULL) {
295	n/a	digit *p = v->ob_digit;
296	n/a	Py_SIZE(v) = ndigits*sign;
297	n/a	t = abs_ival;
298	n/a	while (t) {
299	n/a	*p++ = Py_SAFE_DOWNCAST(
300	n/a	t & PyLong_MASK, unsigned long, digit);
301	n/a	t >>= PyLong_SHIFT;
302	n/a	}
303	n/a	}
304	n/a	return (PyObject *)v;
305	n/a	}
306	n/a
307	n/a	/* Create a new int object from a C unsigned long int */
308	n/a
309	n/a	PyObject *
310	n/a	PyLong_FromUnsignedLong(unsigned long ival)
311	n/a	{
312	n/a	PyLongObject *v;
313	n/a	unsigned long t;
314	n/a	int ndigits = 0;
315	n/a
316	n/a	if (ival < PyLong_BASE)
317	n/a	return PyLong_FromLong(ival);
318	n/a	/* Count the number of Python digits. */
319	n/a	t = (unsigned long)ival;
320	n/a	while (t) {
321	n/a	++ndigits;
322	n/a	t >>= PyLong_SHIFT;
323	n/a	}
324	n/a	v = _PyLong_New(ndigits);
325	n/a	if (v != NULL) {
326	n/a	digit *p = v->ob_digit;
327	n/a	while (ival) {
328	n/a	*p++ = (digit)(ival & PyLong_MASK);
329	n/a	ival >>= PyLong_SHIFT;
330	n/a	}
331	n/a	}
332	n/a	return (PyObject *)v;
333	n/a	}
334	n/a
335	n/a	/* Create a new int object from a C double */
336	n/a
337	n/a	PyObject *
338	n/a	PyLong_FromDouble(double dval)
339	n/a	{
340	n/a	PyLongObject *v;
341	n/a	double frac;
342	n/a	int i, ndig, expo, neg;
343	n/a	neg = 0;
344	n/a	if (Py_IS_INFINITY(dval)) {
345	n/a	PyErr_SetString(PyExc_OverflowError,
346	n/a	"cannot convert float infinity to integer");
347	n/a	return NULL;
348	n/a	}
349	n/a	if (Py_IS_NAN(dval)) {
350	n/a	PyErr_SetString(PyExc_ValueError,
351	n/a	"cannot convert float NaN to integer");
352	n/a	return NULL;
353	n/a	}
354	n/a	if (dval < 0.0) {
355	n/a	neg = 1;
356	n/a	dval = -dval;
357	n/a	}
358	n/a	frac = frexp(dval, &expo); /* dval = frac2expo; 0.0 <= frac < 1.0 /
359	n/a	if (expo <= 0)
360	n/a	return PyLong_FromLong(0L);
361	n/a	ndig = (expo-1) / PyLong_SHIFT + 1; /* Number of 'digits' in result */
362	n/a	v = _PyLong_New(ndig);
363	n/a	if (v == NULL)
364	n/a	return NULL;
365	n/a	frac = ldexp(frac, (expo-1) % PyLong_SHIFT + 1);
366	n/a	for (i = ndig; --i >= 0; ) {
367	n/a	digit bits = (digit)frac;
368	n/a	v->ob_digit[i] = bits;
369	n/a	frac = frac - (double)bits;
370	n/a	frac = ldexp(frac, PyLong_SHIFT);
371	n/a	}
372	n/a	if (neg)
373	n/a	Py_SIZE(v) = -(Py_SIZE(v));
374	n/a	return (PyObject *)v;
375	n/a	}
376	n/a
377	n/a	/* Checking for overflow in PyLong_AsLong is a PITA since C doesn't define
378	n/a	* anything about what happens when a signed integer operation overflows,
379	n/a	* and some compilers think they're doing you a favor by being "clever"
380	n/a	* then. The bit pattern for the largest positive signed long is
381	n/a	* (unsigned long)LONG_MAX, and for the smallest negative signed long
382	n/a	* it is abs(LONG_MIN), which we could write -(unsigned long)LONG_MIN.
383	n/a	* However, some other compilers warn about applying unary minus to an
384	n/a	* unsigned operand. Hence the weird "0-".
385	n/a	*/
386	n/a	#define PY_ABS_LONG_MIN (0-(unsigned long)LONG_MIN)
387	n/a	#define PY_ABS_SSIZE_T_MIN (0-(size_t)PY_SSIZE_T_MIN)
388	n/a
389	n/a	/* Get a C long int from an int object or any object that has an __int__
390	n/a	method.
391	n/a
392	n/a	On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
393	n/a	the result. Otherwise *overflow is 0.
394	n/a
395	n/a	For other errors (e.g., TypeError), return -1 and set an error condition.
396	n/a	In this case *overflow will be 0.
397	n/a	*/
398	n/a
399	n/a	long
400	n/a	PyLong_AsLongAndOverflow(PyObject vv, int overflow)
401	n/a	{
402	n/a	/* This version by Tim Peters */
403	n/a	PyLongObject *v;
404	n/a	unsigned long x, prev;
405	n/a	long res;
406	n/a	Py_ssize_t i;
407	n/a	int sign;
408	n/a	int do_decref = 0; /* if nb_int was called */
409	n/a
410	n/a	*overflow = 0;
411	n/a	if (vv == NULL) {
412	n/a	PyErr_BadInternalCall();
413	n/a	return -1;
414	n/a	}
415	n/a
416	n/a	if (PyLong_Check(vv)) {
417	n/a	v = (PyLongObject *)vv;
418	n/a	}
419	n/a	else {
420	n/a	v = _PyLong_FromNbInt(vv);
421	n/a	if (v == NULL)
422	n/a	return -1;
423	n/a	do_decref = 1;
424	n/a	}
425	n/a
426	n/a	res = -1;
427	n/a	i = Py_SIZE(v);
428	n/a
429	n/a	switch (i) {
430	n/a	case -1:
431	n/a	res = -(sdigit)v->ob_digit[0];
432	n/a	break;
433	n/a	case 0:
434	n/a	res = 0;
435	n/a	break;
436	n/a	case 1:
437	n/a	res = v->ob_digit[0];
438	n/a	break;
439	n/a	default:
440	n/a	sign = 1;
441	n/a	x = 0;
442	n/a	if (i < 0) {
443	n/a	sign = -1;
444	n/a	i = -(i);
445	n/a	}
446	n/a	while (--i >= 0) {
447	n/a	prev = x;
448	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
449	n/a	if ((x >> PyLong_SHIFT) != prev) {
450	n/a	*overflow = sign;
451	n/a	goto exit;
452	n/a	}
453	n/a	}
454	n/a	/* Haven't lost any bits, but casting to long requires extra
455	n/a	* care (see comment above).
456	n/a	*/
457	n/a	if (x <= (unsigned long)LONG_MAX) {
458	n/a	res = (long)x * sign;
459	n/a	}
460	n/a	else if (sign < 0 && x == PY_ABS_LONG_MIN) {
461	n/a	res = LONG_MIN;
462	n/a	}
463	n/a	else {
464	n/a	*overflow = sign;
465	n/a	/* res is already set to -1 */
466	n/a	}
467	n/a	}
468	n/a	exit:
469	n/a	if (do_decref) {
470	n/a	Py_DECREF(v);
471	n/a	}
472	n/a	return res;
473	n/a	}
474	n/a
475	n/a	/* Get a C long int from an int object or any object that has an __int__
476	n/a	method. Return -1 and set an error if overflow occurs. */
477	n/a
478	n/a	long
479	n/a	PyLong_AsLong(PyObject *obj)
480	n/a	{
481	n/a	int overflow;
482	n/a	long result = PyLong_AsLongAndOverflow(obj, &overflow);
483	n/a	if (overflow) {
484	n/a	/* XXX: could be cute and give a different
485	n/a	message for overflow == -1 */
486	n/a	PyErr_SetString(PyExc_OverflowError,
487	n/a	"Python int too large to convert to C long");
488	n/a	}
489	n/a	return result;
490	n/a	}
491	n/a
492	n/a	/* Get a C int from an int object or any object that has an __int__
493	n/a	method. Return -1 and set an error if overflow occurs. */
494	n/a
495	n/a	int
496	n/a	_PyLong_AsInt(PyObject *obj)
497	n/a	{
498	n/a	int overflow;
499	n/a	long result = PyLong_AsLongAndOverflow(obj, &overflow);
500	n/a	if (overflow \|\| result > INT_MAX \|\| result < INT_MIN) {
501	n/a	/* XXX: could be cute and give a different
502	n/a	message for overflow == -1 */
503	n/a	PyErr_SetString(PyExc_OverflowError,
504	n/a	"Python int too large to convert to C int");
505	n/a	return -1;
506	n/a	}
507	n/a	return (int)result;
508	n/a	}
509	n/a
510	n/a	/* Get a Py_ssize_t from an int object.
511	n/a	Returns -1 and sets an error condition if overflow occurs. */
512	n/a
513	n/a	Py_ssize_t
514	n/a	PyLong_AsSsize_t(PyObject *vv) {
515	n/a	PyLongObject *v;
516	n/a	size_t x, prev;
517	n/a	Py_ssize_t i;
518	n/a	int sign;
519	n/a
520	n/a	if (vv == NULL) {
521	n/a	PyErr_BadInternalCall();
522	n/a	return -1;
523	n/a	}
524	n/a	if (!PyLong_Check(vv)) {
525	n/a	PyErr_SetString(PyExc_TypeError, "an integer is required");
526	n/a	return -1;
527	n/a	}
528	n/a
529	n/a	v = (PyLongObject *)vv;
530	n/a	i = Py_SIZE(v);
531	n/a	switch (i) {
532	n/a	case -1: return -(sdigit)v->ob_digit[0];
533	n/a	case 0: return 0;
534	n/a	case 1: return v->ob_digit[0];
535	n/a	}
536	n/a	sign = 1;
537	n/a	x = 0;
538	n/a	if (i < 0) {
539	n/a	sign = -1;
540	n/a	i = -(i);
541	n/a	}
542	n/a	while (--i >= 0) {
543	n/a	prev = x;
544	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
545	n/a	if ((x >> PyLong_SHIFT) != prev)
546	n/a	goto overflow;
547	n/a	}
548	n/a	/* Haven't lost any bits, but casting to a signed type requires
549	n/a	* extra care (see comment above).
550	n/a	*/
551	n/a	if (x <= (size_t)PY_SSIZE_T_MAX) {
552	n/a	return (Py_ssize_t)x * sign;
553	n/a	}
554	n/a	else if (sign < 0 && x == PY_ABS_SSIZE_T_MIN) {
555	n/a	return PY_SSIZE_T_MIN;
556	n/a	}
557	n/a	/* else overflow */
558	n/a
559	n/a	overflow:
560	n/a	PyErr_SetString(PyExc_OverflowError,
561	n/a	"Python int too large to convert to C ssize_t");
562	n/a	return -1;
563	n/a	}
564	n/a
565	n/a	/* Get a C unsigned long int from an int object.
566	n/a	Returns -1 and sets an error condition if overflow occurs. */
567	n/a
568	n/a	unsigned long
569	n/a	PyLong_AsUnsignedLong(PyObject *vv)
570	n/a	{
571	n/a	PyLongObject *v;
572	n/a	unsigned long x, prev;
573	n/a	Py_ssize_t i;
574	n/a
575	n/a	if (vv == NULL) {
576	n/a	PyErr_BadInternalCall();
577	n/a	return (unsigned long)-1;
578	n/a	}
579	n/a	if (!PyLong_Check(vv)) {
580	n/a	PyErr_SetString(PyExc_TypeError, "an integer is required");
581	n/a	return (unsigned long)-1;
582	n/a	}
583	n/a
584	n/a	v = (PyLongObject *)vv;
585	n/a	i = Py_SIZE(v);
586	n/a	x = 0;
587	n/a	if (i < 0) {
588	n/a	PyErr_SetString(PyExc_OverflowError,
589	n/a	"can't convert negative value to unsigned int");
590	n/a	return (unsigned long) -1;
591	n/a	}
592	n/a	switch (i) {
593	n/a	case 0: return 0;
594	n/a	case 1: return v->ob_digit[0];
595	n/a	}
596	n/a	while (--i >= 0) {
597	n/a	prev = x;
598	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
599	n/a	if ((x >> PyLong_SHIFT) != prev) {
600	n/a	PyErr_SetString(PyExc_OverflowError,
601	n/a	"Python int too large to convert "
602	n/a	"to C unsigned long");
603	n/a	return (unsigned long) -1;
604	n/a	}
605	n/a	}
606	n/a	return x;
607	n/a	}
608	n/a
609	n/a	/* Get a C size_t from an int object. Returns (size_t)-1 and sets
610	n/a	an error condition if overflow occurs. */
611	n/a
612	n/a	size_t
613	n/a	PyLong_AsSize_t(PyObject *vv)
614	n/a	{
615	n/a	PyLongObject *v;
616	n/a	size_t x, prev;
617	n/a	Py_ssize_t i;
618	n/a
619	n/a	if (vv == NULL) {
620	n/a	PyErr_BadInternalCall();
621	n/a	return (size_t) -1;
622	n/a	}
623	n/a	if (!PyLong_Check(vv)) {
624	n/a	PyErr_SetString(PyExc_TypeError, "an integer is required");
625	n/a	return (size_t)-1;
626	n/a	}
627	n/a
628	n/a	v = (PyLongObject *)vv;
629	n/a	i = Py_SIZE(v);
630	n/a	x = 0;
631	n/a	if (i < 0) {
632	n/a	PyErr_SetString(PyExc_OverflowError,
633	n/a	"can't convert negative value to size_t");
634	n/a	return (size_t) -1;
635	n/a	}
636	n/a	switch (i) {
637	n/a	case 0: return 0;
638	n/a	case 1: return v->ob_digit[0];
639	n/a	}
640	n/a	while (--i >= 0) {
641	n/a	prev = x;
642	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
643	n/a	if ((x >> PyLong_SHIFT) != prev) {
644	n/a	PyErr_SetString(PyExc_OverflowError,
645	n/a	"Python int too large to convert to C size_t");
646	n/a	return (size_t) -1;
647	n/a	}
648	n/a	}
649	n/a	return x;
650	n/a	}
651	n/a
652	n/a	/* Get a C unsigned long int from an int object, ignoring the high bits.
653	n/a	Returns -1 and sets an error condition if an error occurs. */
654	n/a
655	n/a	static unsigned long
656	n/a	_PyLong_AsUnsignedLongMask(PyObject *vv)
657	n/a	{
658	n/a	PyLongObject *v;
659	n/a	unsigned long x;
660	n/a	Py_ssize_t i;
661	n/a	int sign;
662	n/a
663	n/a	if (vv == NULL \|\| !PyLong_Check(vv)) {
664	n/a	PyErr_BadInternalCall();
665	n/a	return (unsigned long) -1;
666	n/a	}
667	n/a	v = (PyLongObject *)vv;
668	n/a	i = Py_SIZE(v);
669	n/a	switch (i) {
670	n/a	case 0: return 0;
671	n/a	case 1: return v->ob_digit[0];
672	n/a	}
673	n/a	sign = 1;
674	n/a	x = 0;
675	n/a	if (i < 0) {
676	n/a	sign = -1;
677	n/a	i = -i;
678	n/a	}
679	n/a	while (--i >= 0) {
680	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
681	n/a	}
682	n/a	return x * sign;
683	n/a	}
684	n/a
685	n/a	unsigned long
686	n/a	PyLong_AsUnsignedLongMask(PyObject *op)
687	n/a	{
688	n/a	PyLongObject *lo;
689	n/a	unsigned long val;
690	n/a
691	n/a	if (op == NULL) {
692	n/a	PyErr_BadInternalCall();
693	n/a	return (unsigned long)-1;
694	n/a	}
695	n/a
696	n/a	if (PyLong_Check(op)) {
697	n/a	return _PyLong_AsUnsignedLongMask(op);
698	n/a	}
699	n/a
700	n/a	lo = _PyLong_FromNbInt(op);
701	n/a	if (lo == NULL)
702	n/a	return (unsigned long)-1;
703	n/a
704	n/a	val = _PyLong_AsUnsignedLongMask((PyObject *)lo);
705	n/a	Py_DECREF(lo);
706	n/a	return val;
707	n/a	}
708	n/a
709	n/a	int
710	n/a	_PyLong_Sign(PyObject *vv)
711	n/a	{
712	n/a	PyLongObject v = (PyLongObject )vv;
713	n/a
714	n/a	assert(v != NULL);
715	n/a	assert(PyLong_Check(v));
716	n/a
717	n/a	return Py_SIZE(v) == 0 ? 0 : (Py_SIZE(v) < 0 ? -1 : 1);
718	n/a	}
719	n/a
720	n/a	/* bits_in_digit(d) returns the unique integer k such that 2**(k-1) <= d <
721	n/a	2*k if d is nonzero, else 0. /
722	n/a
723	n/a	static const unsigned char BitLengthTable[32] = {
724	n/a	0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
725	n/a	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
726	n/a	};
727	n/a
728	n/a	static int
729	n/a	bits_in_digit(digit d)
730	n/a	{
731	n/a	int d_bits = 0;
732	n/a	while (d >= 32) {
733	n/a	d_bits += 6;
734	n/a	d >>= 6;
735	n/a	}
736	n/a	d_bits += (int)BitLengthTable[d];
737	n/a	return d_bits;
738	n/a	}
739	n/a
740	n/a	size_t
741	n/a	_PyLong_NumBits(PyObject *vv)
742	n/a	{
743	n/a	PyLongObject v = (PyLongObject )vv;
744	n/a	size_t result = 0;
745	n/a	Py_ssize_t ndigits;
746	n/a	int msd_bits;
747	n/a
748	n/a	assert(v != NULL);
749	n/a	assert(PyLong_Check(v));
750	n/a	ndigits = Py_ABS(Py_SIZE(v));
751	n/a	assert(ndigits == 0 \|\| v->ob_digit[ndigits - 1] != 0);
752	n/a	if (ndigits > 0) {
753	n/a	digit msd = v->ob_digit[ndigits - 1];
754	n/a	if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
755	n/a	goto Overflow;
756	n/a	result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
757	n/a	msd_bits = bits_in_digit(msd);
758	n/a	if (SIZE_MAX - msd_bits < result)
759	n/a	goto Overflow;
760	n/a	result += msd_bits;
761	n/a	}
762	n/a	return result;
763	n/a
764	n/a	Overflow:
765	n/a	PyErr_SetString(PyExc_OverflowError, "int has too many bits "
766	n/a	"to express in a platform size_t");
767	n/a	return (size_t)-1;
768	n/a	}
769	n/a
770	n/a	PyObject *
771	n/a	_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
772	n/a	int little_endian, int is_signed)
773	n/a	{
774	n/a	const unsigned char* pstartbyte; /* LSB of bytes */
775	n/a	int incr; /* direction to move pstartbyte */
776	n/a	const unsigned char* pendbyte; /* MSB of bytes */
777	n/a	size_t numsignificantbytes; /* number of bytes that matter */
778	n/a	Py_ssize_t ndigits; /* number of Python int digits */
779	n/a	PyLongObject* v; /* result */
780	n/a	Py_ssize_t idigit = 0; /* next free index in v->ob_digit */
781	n/a
782	n/a	if (n == 0)
783	n/a	return PyLong_FromLong(0L);
784	n/a
785	n/a	if (little_endian) {
786	n/a	pstartbyte = bytes;
787	n/a	pendbyte = bytes + n - 1;
788	n/a	incr = 1;
789	n/a	}
790	n/a	else {
791	n/a	pstartbyte = bytes + n - 1;
792	n/a	pendbyte = bytes;
793	n/a	incr = -1;
794	n/a	}
795	n/a
796	n/a	if (is_signed)
797	n/a	is_signed = *pendbyte >= 0x80;
798	n/a
799	n/a	/* Compute numsignificantbytes. This consists of finding the most
800	n/a	significant byte. Leading 0 bytes are insignificant if the number
801	n/a	is positive, and leading 0xff bytes if negative. */
802	n/a	{
803	n/a	size_t i;
804	n/a	const unsigned char* p = pendbyte;
805	n/a	const int pincr = -incr; /* search MSB to LSB */
806	n/a	const unsigned char insignificant = is_signed ? 0xff : 0x00;
807	n/a
808	n/a	for (i = 0; i < n; ++i, p += pincr) {
809	n/a	if (*p != insignificant)
810	n/a	break;
811	n/a	}
812	n/a	numsignificantbytes = n - i;
813	n/a	/* 2's-comp is a bit tricky here, e.g. 0xff00 == -0x0100, so
814	n/a	actually has 2 significant bytes. OTOH, 0xff0001 ==
815	n/a	-0x00ffff, so we wouldn't need to bump it there; but we
816	n/a	do for 0xffff = -0x0001. To be safe without bothering to
817	n/a	check every case, bump it regardless. */
818	n/a	if (is_signed && numsignificantbytes < n)
819	n/a	++numsignificantbytes;
820	n/a	}
821	n/a
822	n/a	/* How many Python int digits do we need? We have
823	n/a	8*numsignificantbytes bits, and each Python int digit has
824	n/a	PyLong_SHIFT bits, so it's the ceiling of the quotient. */
825	n/a	/* catch overflow before it happens */
826	n/a	if (numsignificantbytes > (PY_SSIZE_T_MAX - PyLong_SHIFT) / 8) {
827	n/a	PyErr_SetString(PyExc_OverflowError,
828	n/a	"byte array too long to convert to int");
829	n/a	return NULL;
830	n/a	}
831	n/a	ndigits = (numsignificantbytes * 8 + PyLong_SHIFT - 1) / PyLong_SHIFT;
832	n/a	v = _PyLong_New(ndigits);
833	n/a	if (v == NULL)
834	n/a	return NULL;
835	n/a
836	n/a	/* Copy the bits over. The tricky parts are computing 2's-comp on
837	n/a	the fly for signed numbers, and dealing with the mismatch between
838	n/a	8-bit bytes and (probably) 15-bit Python digits.*/
839	n/a	{
840	n/a	size_t i;
841	n/a	twodigits carry = 1; /* for 2's-comp calculation */
842	n/a	twodigits accum = 0; /* sliding register */
843	n/a	unsigned int accumbits = 0; /* number of bits in accum */
844	n/a	const unsigned char* p = pstartbyte;
845	n/a
846	n/a	for (i = 0; i < numsignificantbytes; ++i, p += incr) {
847	n/a	twodigits thisbyte = *p;
848	n/a	/* Compute correction for 2's comp, if needed. */
849	n/a	if (is_signed) {
850	n/a	thisbyte = (0xff ^ thisbyte) + carry;
851	n/a	carry = thisbyte >> 8;
852	n/a	thisbyte &= 0xff;
853	n/a	}
854	n/a	/* Because we're going LSB to MSB, thisbyte is
855	n/a	more significant than what's already in accum,
856	n/a	so needs to be prepended to accum. */
857	n/a	accum \|= (twodigits)thisbyte << accumbits;
858	n/a	accumbits += 8;
859	n/a	if (accumbits >= PyLong_SHIFT) {
860	n/a	/* There's enough to fill a Python digit. */
861	n/a	assert(idigit < ndigits);
862	n/a	v->ob_digit[idigit] = (digit)(accum & PyLong_MASK);
863	n/a	++idigit;
864	n/a	accum >>= PyLong_SHIFT;
865	n/a	accumbits -= PyLong_SHIFT;
866	n/a	assert(accumbits < PyLong_SHIFT);
867	n/a	}
868	n/a	}
869	n/a	assert(accumbits < PyLong_SHIFT);
870	n/a	if (accumbits) {
871	n/a	assert(idigit < ndigits);
872	n/a	v->ob_digit[idigit] = (digit)accum;
873	n/a	++idigit;
874	n/a	}
875	n/a	}
876	n/a
877	n/a	Py_SIZE(v) = is_signed ? -idigit : idigit;
878	n/a	return (PyObject *)long_normalize(v);
879	n/a	}
880	n/a
881	n/a	int
882	n/a	_PyLong_AsByteArray(PyLongObject* v,
883	n/a	unsigned char* bytes, size_t n,
884	n/a	int little_endian, int is_signed)
885	n/a	{
886	n/a	Py_ssize_t i; /* index into v->ob_digit */
887	n/a	Py_ssize_t ndigits; /* \|v->ob_size\| */
888	n/a	twodigits accum; /* sliding register */
889	n/a	unsigned int accumbits; /* # bits in accum */
890	n/a	int do_twos_comp; /* store 2's-comp? is_signed and v < 0 */
891	n/a	digit carry; /* for computing 2's-comp */
892	n/a	size_t j; /* # bytes filled */
893	n/a	unsigned char* p; /* pointer to next byte in bytes */
894	n/a	int pincr; /* direction to move p */
895	n/a
896	n/a	assert(v != NULL && PyLong_Check(v));
897	n/a
898	n/a	if (Py_SIZE(v) < 0) {
899	n/a	ndigits = -(Py_SIZE(v));
900	n/a	if (!is_signed) {
901	n/a	PyErr_SetString(PyExc_OverflowError,
902	n/a	"can't convert negative int to unsigned");
903	n/a	return -1;
904	n/a	}
905	n/a	do_twos_comp = 1;
906	n/a	}
907	n/a	else {
908	n/a	ndigits = Py_SIZE(v);
909	n/a	do_twos_comp = 0;
910	n/a	}
911	n/a
912	n/a	if (little_endian) {
913	n/a	p = bytes;
914	n/a	pincr = 1;
915	n/a	}
916	n/a	else {
917	n/a	p = bytes + n - 1;
918	n/a	pincr = -1;
919	n/a	}
920	n/a
921	n/a	/* Copy over all the Python digits.
922	n/a	It's crucial that every Python digit except for the MSD contribute
923	n/a	exactly PyLong_SHIFT bits to the total, so first assert that the int is
924	n/a	normalized. */
925	n/a	assert(ndigits == 0 \|\| v->ob_digit[ndigits - 1] != 0);
926	n/a	j = 0;
927	n/a	accum = 0;
928	n/a	accumbits = 0;
929	n/a	carry = do_twos_comp ? 1 : 0;
930	n/a	for (i = 0; i < ndigits; ++i) {
931	n/a	digit thisdigit = v->ob_digit[i];
932	n/a	if (do_twos_comp) {
933	n/a	thisdigit = (thisdigit ^ PyLong_MASK) + carry;
934	n/a	carry = thisdigit >> PyLong_SHIFT;
935	n/a	thisdigit &= PyLong_MASK;
936	n/a	}
937	n/a	/* Because we're going LSB to MSB, thisdigit is more
938	n/a	significant than what's already in accum, so needs to be
939	n/a	prepended to accum. */
940	n/a	accum \|= (twodigits)thisdigit << accumbits;
941	n/a
942	n/a	/* The most-significant digit may be (probably is) at least
943	n/a	partly empty. */
944	n/a	if (i == ndigits - 1) {
945	n/a	/* Count # of sign bits -- they needn't be stored,
946	n/a	* although for signed conversion we need later to
947	n/a	* make sure at least one sign bit gets stored. */
948	n/a	digit s = do_twos_comp ? thisdigit ^ PyLong_MASK : thisdigit;
949	n/a	while (s != 0) {
950	n/a	s >>= 1;
951	n/a	accumbits++;
952	n/a	}
953	n/a	}
954	n/a	else
955	n/a	accumbits += PyLong_SHIFT;
956	n/a
957	n/a	/* Store as many bytes as possible. */
958	n/a	while (accumbits >= 8) {
959	n/a	if (j >= n)
960	n/a	goto Overflow;
961	n/a	++j;
962	n/a	*p = (unsigned char)(accum & 0xff);
963	n/a	p += pincr;
964	n/a	accumbits -= 8;
965	n/a	accum >>= 8;
966	n/a	}
967	n/a	}
968	n/a
969	n/a	/* Store the straggler (if any). */
970	n/a	assert(accumbits < 8);
971	n/a	assert(carry == 0); /* else do_twos_comp and every digit was 0 */
972	n/a	if (accumbits > 0) {
973	n/a	if (j >= n)
974	n/a	goto Overflow;
975	n/a	++j;
976	n/a	if (do_twos_comp) {
977	n/a	/* Fill leading bits of the byte with sign bits
978	n/a	(appropriately pretending that the int had an
979	n/a	infinite supply of sign bits). */
980	n/a	accum \|= (~(twodigits)0) << accumbits;
981	n/a	}
982	n/a	*p = (unsigned char)(accum & 0xff);
983	n/a	p += pincr;
984	n/a	}
985	n/a	else if (j == n && n > 0 && is_signed) {
986	n/a	/* The main loop filled the byte array exactly, so the code
987	n/a	just above didn't get to ensure there's a sign bit, and the
988	n/a	loop below wouldn't add one either. Make sure a sign bit
989	n/a	exists. */
990	n/a	unsigned char msb = *(p - pincr);
991	n/a	int sign_bit_set = msb >= 0x80;
992	n/a	assert(accumbits == 0);
993	n/a	if (sign_bit_set == do_twos_comp)
994	n/a	return 0;
995	n/a	else
996	n/a	goto Overflow;
997	n/a	}
998	n/a
999	n/a	/* Fill remaining bytes with copies of the sign bit. */
1000	n/a	{
1001	n/a	unsigned char signbyte = do_twos_comp ? 0xffU : 0U;
1002	n/a	for ( ; j < n; ++j, p += pincr)
1003	n/a	*p = signbyte;
1004	n/a	}
1005	n/a
1006	n/a	return 0;
1007	n/a
1008	n/a	Overflow:
1009	n/a	PyErr_SetString(PyExc_OverflowError, "int too big to convert");
1010	n/a	return -1;
1011	n/a
1012	n/a	}
1013	n/a
1014	n/a	/* Create a new int object from a C pointer */
1015	n/a
1016	n/a	PyObject *
1017	n/a	PyLong_FromVoidPtr(void *p)
1018	n/a	{
1019	n/a	#if SIZEOF_VOID_P <= SIZEOF_LONG
1020	n/a	return PyLong_FromUnsignedLong((unsigned long)(uintptr_t)p);
1021	n/a	#else
1022	n/a
1023	n/a	#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
1024	n/a	# error "PyLong_FromVoidPtr: sizeof(long long) < sizeof(void*)"
1025	n/a	#endif
1026	n/a	return PyLong_FromUnsignedLongLong((unsigned long long)(uintptr_t)p);
1027	n/a	#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
1028	n/a
1029	n/a	}
1030	n/a
1031	n/a	/* Get a C pointer from an int object. */
1032	n/a
1033	n/a	void *
1034	n/a	PyLong_AsVoidPtr(PyObject *vv)
1035	n/a	{
1036	n/a	#if SIZEOF_VOID_P <= SIZEOF_LONG
1037	n/a	long x;
1038	n/a
1039	n/a	if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1040	n/a	x = PyLong_AsLong(vv);
1041	n/a	else
1042	n/a	x = PyLong_AsUnsignedLong(vv);
1043	n/a	#else
1044	n/a
1045	n/a	#if SIZEOF_LONG_LONG < SIZEOF_VOID_P
1046	n/a	# error "PyLong_AsVoidPtr: sizeof(long long) < sizeof(void*)"
1047	n/a	#endif
1048	n/a	long long x;
1049	n/a
1050	n/a	if (PyLong_Check(vv) && _PyLong_Sign(vv) < 0)
1051	n/a	x = PyLong_AsLongLong(vv);
1052	n/a	else
1053	n/a	x = PyLong_AsUnsignedLongLong(vv);
1054	n/a
1055	n/a	#endif /* SIZEOF_VOID_P <= SIZEOF_LONG */
1056	n/a
1057	n/a	if (x == -1 && PyErr_Occurred())
1058	n/a	return NULL;
1059	n/a	return (void *)x;
1060	n/a	}
1061	n/a
1062	n/a	/* Initial long long support by Chris Herborth (chrish@qnx.com), later
1063	n/a	* rewritten to use the newer PyLong_{As,From}ByteArray API.
1064	n/a	*/
1065	n/a
1066	n/a	#define PY_ABS_LLONG_MIN (0-(unsigned long long)PY_LLONG_MIN)
1067	n/a
1068	n/a	/* Create a new int object from a C long long int. */
1069	n/a
1070	n/a	PyObject *
1071	n/a	PyLong_FromLongLong(long long ival)
1072	n/a	{
1073	n/a	PyLongObject *v;
1074	n/a	unsigned long long abs_ival;
1075	n/a	unsigned long long t; /* unsigned so >> doesn't propagate sign bit */
1076	n/a	int ndigits = 0;
1077	n/a	int negative = 0;
1078	n/a
1079	n/a	CHECK_SMALL_INT(ival);
1080	n/a	if (ival < 0) {
1081	n/a	/* avoid signed overflow on negation; see comments
1082	n/a	in PyLong_FromLong above. */
1083	n/a	abs_ival = (unsigned long long)(-1-ival) + 1;
1084	n/a	negative = 1;
1085	n/a	}
1086	n/a	else {
1087	n/a	abs_ival = (unsigned long long)ival;
1088	n/a	}
1089	n/a
1090	n/a	/* Count the number of Python digits.
1091	n/a	We used to pick 5 ("big enough for anything"), but that's a
1092	n/a	waste of time and space given that 5*15 = 75 bits are rarely
1093	n/a	needed. */
1094	n/a	t = abs_ival;
1095	n/a	while (t) {
1096	n/a	++ndigits;
1097	n/a	t >>= PyLong_SHIFT;
1098	n/a	}
1099	n/a	v = _PyLong_New(ndigits);
1100	n/a	if (v != NULL) {
1101	n/a	digit *p = v->ob_digit;
1102	n/a	Py_SIZE(v) = negative ? -ndigits : ndigits;
1103	n/a	t = abs_ival;
1104	n/a	while (t) {
1105	n/a	*p++ = (digit)(t & PyLong_MASK);
1106	n/a	t >>= PyLong_SHIFT;
1107	n/a	}
1108	n/a	}
1109	n/a	return (PyObject *)v;
1110	n/a	}
1111	n/a
1112	n/a	/* Create a new int object from a C unsigned long long int. */
1113	n/a
1114	n/a	PyObject *
1115	n/a	PyLong_FromUnsignedLongLong(unsigned long long ival)
1116	n/a	{
1117	n/a	PyLongObject *v;
1118	n/a	unsigned long long t;
1119	n/a	int ndigits = 0;
1120	n/a
1121	n/a	if (ival < PyLong_BASE)
1122	n/a	return PyLong_FromLong((long)ival);
1123	n/a	/* Count the number of Python digits. */
1124	n/a	t = (unsigned long long)ival;
1125	n/a	while (t) {
1126	n/a	++ndigits;
1127	n/a	t >>= PyLong_SHIFT;
1128	n/a	}
1129	n/a	v = _PyLong_New(ndigits);
1130	n/a	if (v != NULL) {
1131	n/a	digit *p = v->ob_digit;
1132	n/a	while (ival) {
1133	n/a	*p++ = (digit)(ival & PyLong_MASK);
1134	n/a	ival >>= PyLong_SHIFT;
1135	n/a	}
1136	n/a	}
1137	n/a	return (PyObject *)v;
1138	n/a	}
1139	n/a
1140	n/a	/* Create a new int object from a C Py_ssize_t. */
1141	n/a
1142	n/a	PyObject *
1143	n/a	PyLong_FromSsize_t(Py_ssize_t ival)
1144	n/a	{
1145	n/a	PyLongObject *v;
1146	n/a	size_t abs_ival;
1147	n/a	size_t t; /* unsigned so >> doesn't propagate sign bit */
1148	n/a	int ndigits = 0;
1149	n/a	int negative = 0;
1150	n/a
1151	n/a	CHECK_SMALL_INT(ival);
1152	n/a	if (ival < 0) {
1153	n/a	/* avoid signed overflow when ival = SIZE_T_MIN */
1154	n/a	abs_ival = (size_t)(-1-ival)+1;
1155	n/a	negative = 1;
1156	n/a	}
1157	n/a	else {
1158	n/a	abs_ival = (size_t)ival;
1159	n/a	}
1160	n/a
1161	n/a	/* Count the number of Python digits. */
1162	n/a	t = abs_ival;
1163	n/a	while (t) {
1164	n/a	++ndigits;
1165	n/a	t >>= PyLong_SHIFT;
1166	n/a	}
1167	n/a	v = _PyLong_New(ndigits);
1168	n/a	if (v != NULL) {
1169	n/a	digit *p = v->ob_digit;
1170	n/a	Py_SIZE(v) = negative ? -ndigits : ndigits;
1171	n/a	t = abs_ival;
1172	n/a	while (t) {
1173	n/a	*p++ = (digit)(t & PyLong_MASK);
1174	n/a	t >>= PyLong_SHIFT;
1175	n/a	}
1176	n/a	}
1177	n/a	return (PyObject *)v;
1178	n/a	}
1179	n/a
1180	n/a	/* Create a new int object from a C size_t. */
1181	n/a
1182	n/a	PyObject *
1183	n/a	PyLong_FromSize_t(size_t ival)
1184	n/a	{
1185	n/a	PyLongObject *v;
1186	n/a	size_t t;
1187	n/a	int ndigits = 0;
1188	n/a
1189	n/a	if (ival < PyLong_BASE)
1190	n/a	return PyLong_FromLong((long)ival);
1191	n/a	/* Count the number of Python digits. */
1192	n/a	t = ival;
1193	n/a	while (t) {
1194	n/a	++ndigits;
1195	n/a	t >>= PyLong_SHIFT;
1196	n/a	}
1197	n/a	v = _PyLong_New(ndigits);
1198	n/a	if (v != NULL) {
1199	n/a	digit *p = v->ob_digit;
1200	n/a	Py_SIZE(v) = ndigits;
1201	n/a	while (ival) {
1202	n/a	*p++ = (digit)(ival & PyLong_MASK);
1203	n/a	ival >>= PyLong_SHIFT;
1204	n/a	}
1205	n/a	}
1206	n/a	return (PyObject *)v;
1207	n/a	}
1208	n/a
1209	n/a	/* Get a C long long int from an int object or any object that has an
1210	n/a	__int__ method. Return -1 and set an error if overflow occurs. */
1211	n/a
1212	n/a	long long
1213	n/a	PyLong_AsLongLong(PyObject *vv)
1214	n/a	{
1215	n/a	PyLongObject *v;
1216	n/a	long long bytes;
1217	n/a	int res;
1218	n/a	int do_decref = 0; /* if nb_int was called */
1219	n/a
1220	n/a	if (vv == NULL) {
1221	n/a	PyErr_BadInternalCall();
1222	n/a	return -1;
1223	n/a	}
1224	n/a
1225	n/a	if (PyLong_Check(vv)) {
1226	n/a	v = (PyLongObject *)vv;
1227	n/a	}
1228	n/a	else {
1229	n/a	v = _PyLong_FromNbInt(vv);
1230	n/a	if (v == NULL)
1231	n/a	return -1;
1232	n/a	do_decref = 1;
1233	n/a	}
1234	n/a
1235	n/a	res = 0;
1236	n/a	switch(Py_SIZE(v)) {
1237	n/a	case -1:
1238	n/a	bytes = -(sdigit)v->ob_digit[0];
1239	n/a	break;
1240	n/a	case 0:
1241	n/a	bytes = 0;
1242	n/a	break;
1243	n/a	case 1:
1244	n/a	bytes = v->ob_digit[0];
1245	n/a	break;
1246	n/a	default:
1247	n/a	res = _PyLong_AsByteArray((PyLongObject )v, (unsigned char )&bytes,
1248	n/a	SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 1);
1249	n/a	}
1250	n/a	if (do_decref) {
1251	n/a	Py_DECREF(v);
1252	n/a	}
1253	n/a
1254	n/a	/* Plan 9 can't handle long long in ? : expressions */
1255	n/a	if (res < 0)
1256	n/a	return (long long)-1;
1257	n/a	else
1258	n/a	return bytes;
1259	n/a	}
1260	n/a
1261	n/a	/* Get a C unsigned long long int from an int object.
1262	n/a	Return -1 and set an error if overflow occurs. */
1263	n/a
1264	n/a	unsigned long long
1265	n/a	PyLong_AsUnsignedLongLong(PyObject *vv)
1266	n/a	{
1267	n/a	PyLongObject *v;
1268	n/a	unsigned long long bytes;
1269	n/a	int res;
1270	n/a
1271	n/a	if (vv == NULL) {
1272	n/a	PyErr_BadInternalCall();
1273	n/a	return (unsigned long long)-1;
1274	n/a	}
1275	n/a	if (!PyLong_Check(vv)) {
1276	n/a	PyErr_SetString(PyExc_TypeError, "an integer is required");
1277	n/a	return (unsigned long long)-1;
1278	n/a	}
1279	n/a
1280	n/a	v = (PyLongObject*)vv;
1281	n/a	switch(Py_SIZE(v)) {
1282	n/a	case 0: return 0;
1283	n/a	case 1: return v->ob_digit[0];
1284	n/a	}
1285	n/a
1286	n/a	res = _PyLong_AsByteArray((PyLongObject )vv, (unsigned char )&bytes,
1287	n/a	SIZEOF_LONG_LONG, PY_LITTLE_ENDIAN, 0);
1288	n/a
1289	n/a	/* Plan 9 can't handle long long in ? : expressions */
1290	n/a	if (res < 0)
1291	n/a	return (unsigned long long)res;
1292	n/a	else
1293	n/a	return bytes;
1294	n/a	}
1295	n/a
1296	n/a	/* Get a C unsigned long int from an int object, ignoring the high bits.
1297	n/a	Returns -1 and sets an error condition if an error occurs. */
1298	n/a
1299	n/a	static unsigned long long
1300	n/a	_PyLong_AsUnsignedLongLongMask(PyObject *vv)
1301	n/a	{
1302	n/a	PyLongObject *v;
1303	n/a	unsigned long long x;
1304	n/a	Py_ssize_t i;
1305	n/a	int sign;
1306	n/a
1307	n/a	if (vv == NULL \|\| !PyLong_Check(vv)) {
1308	n/a	PyErr_BadInternalCall();
1309	n/a	return (unsigned long) -1;
1310	n/a	}
1311	n/a	v = (PyLongObject *)vv;
1312	n/a	switch(Py_SIZE(v)) {
1313	n/a	case 0: return 0;
1314	n/a	case 1: return v->ob_digit[0];
1315	n/a	}
1316	n/a	i = Py_SIZE(v);
1317	n/a	sign = 1;
1318	n/a	x = 0;
1319	n/a	if (i < 0) {
1320	n/a	sign = -1;
1321	n/a	i = -i;
1322	n/a	}
1323	n/a	while (--i >= 0) {
1324	n/a	x = (x << PyLong_SHIFT) \| v->ob_digit[i];
1325	n/a	}
1326	n/a	return x * sign;
1327	n/a	}
1328	n/a
1329	n/a	unsigned long long
1330	n/a	PyLong_AsUnsignedLongLongMask(PyObject *op)
1331	n/a	{
1332	n/a	PyLongObject *lo;
1333	n/a	unsigned long long val;
1334	n/a
1335	n/a	if (op == NULL) {
1336	n/a	PyErr_BadInternalCall();
1337	n/a	return (unsigned long)-1;
1338	n/a	}
1339	n/a
1340	n/a	if (PyLong_Check(op)) {
1341	n/a	return _PyLong_AsUnsignedLongLongMask(op);
1342	n/a	}
1343	n/a
1344	n/a	lo = _PyLong_FromNbInt(op);
1345	n/a	if (lo == NULL)
1346	n/a	return (unsigned long long)-1;
1347	n/a
1348	n/a	val = _PyLong_AsUnsignedLongLongMask((PyObject *)lo);
1349	n/a	Py_DECREF(lo);
1350	n/a	return val;
1351	n/a	}
1352	n/a
1353	n/a	/* Get a C long long int from an int object or any object that has an
1354	n/a	__int__ method.
1355	n/a
1356	n/a	On overflow, return -1 and set *overflow to 1 or -1 depending on the sign of
1357	n/a	the result. Otherwise *overflow is 0.
1358	n/a
1359	n/a	For other errors (e.g., TypeError), return -1 and set an error condition.
1360	n/a	In this case *overflow will be 0.
1361	n/a	*/
1362	n/a
1363	n/a	long long
1364	n/a	PyLong_AsLongLongAndOverflow(PyObject vv, int overflow)
1365	n/a	{
1366	n/a	/* This version by Tim Peters */
1367	n/a	PyLongObject *v;
1368	n/a	unsigned long long x, prev;
1369	n/a	long long res;
1370	n/a	Py_ssize_t i;
1371	n/a	int sign;
1372	n/a	int do_decref = 0; /* if nb_int was called */
1373	n/a
1374	n/a	*overflow = 0;
1375	n/a	if (vv == NULL) {
1376	n/a	PyErr_BadInternalCall();
1377	n/a	return -1;
1378	n/a	}
1379	n/a
1380	n/a	if (PyLong_Check(vv)) {
1381	n/a	v = (PyLongObject *)vv;
1382	n/a	}
1383	n/a	else {
1384	n/a	v = _PyLong_FromNbInt(vv);
1385	n/a	if (v == NULL)
1386	n/a	return -1;
1387	n/a	do_decref = 1;
1388	n/a	}
1389	n/a
1390	n/a	res = -1;
1391	n/a	i = Py_SIZE(v);
1392	n/a
1393	n/a	switch (i) {
1394	n/a	case -1:
1395	n/a	res = -(sdigit)v->ob_digit[0];
1396	n/a	break;
1397	n/a	case 0:
1398	n/a	res = 0;
1399	n/a	break;
1400	n/a	case 1:
1401	n/a	res = v->ob_digit[0];
1402	n/a	break;
1403	n/a	default:
1404	n/a	sign = 1;
1405	n/a	x = 0;
1406	n/a	if (i < 0) {
1407	n/a	sign = -1;
1408	n/a	i = -(i);
1409	n/a	}
1410	n/a	while (--i >= 0) {
1411	n/a	prev = x;
1412	n/a	x = (x << PyLong_SHIFT) + v->ob_digit[i];
1413	n/a	if ((x >> PyLong_SHIFT) != prev) {
1414	n/a	*overflow = sign;
1415	n/a	goto exit;
1416	n/a	}
1417	n/a	}
1418	n/a	/* Haven't lost any bits, but casting to long requires extra
1419	n/a	* care (see comment above).
1420	n/a	*/
1421	n/a	if (x <= (unsigned long long)PY_LLONG_MAX) {
1422	n/a	res = (long long)x * sign;
1423	n/a	}
1424	n/a	else if (sign < 0 && x == PY_ABS_LLONG_MIN) {
1425	n/a	res = PY_LLONG_MIN;
1426	n/a	}
1427	n/a	else {
1428	n/a	*overflow = sign;
1429	n/a	/* res is already set to -1 */
1430	n/a	}
1431	n/a	}
1432	n/a	exit:
1433	n/a	if (do_decref) {
1434	n/a	Py_DECREF(v);
1435	n/a	}
1436	n/a	return res;
1437	n/a	}
1438	n/a
1439	n/a	#define CHECK_BINOP(v,w) \
1440	n/a	do { \
1441	n/a	if (!PyLong_Check(v) \|\| !PyLong_Check(w)) \
1442	n/a	Py_RETURN_NOTIMPLEMENTED; \
1443	n/a	} while(0)
1444	n/a
1445	n/a	/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1446	n/a	* is modified in place, by adding y to it. Carries are propagated as far as
1447	n/a	* x[m-1], and the remaining carry (0 or 1) is returned.
1448	n/a	*/
1449	n/a	static digit
1450	n/a	v_iadd(digit x, Py_ssize_t m, digit y, Py_ssize_t n)
1451	n/a	{
1452	n/a	Py_ssize_t i;
1453	n/a	digit carry = 0;
1454	n/a
1455	n/a	assert(m >= n);
1456	n/a	for (i = 0; i < n; ++i) {
1457	n/a	carry += x[i] + y[i];
1458	n/a	x[i] = carry & PyLong_MASK;
1459	n/a	carry >>= PyLong_SHIFT;
1460	n/a	assert((carry & 1) == carry);
1461	n/a	}
1462	n/a	for (; carry && i < m; ++i) {
1463	n/a	carry += x[i];
1464	n/a	x[i] = carry & PyLong_MASK;
1465	n/a	carry >>= PyLong_SHIFT;
1466	n/a	assert((carry & 1) == carry);
1467	n/a	}
1468	n/a	return carry;
1469	n/a	}
1470	n/a
1471	n/a	/* x[0:m] and y[0:n] are digit vectors, LSD first, m >= n required. x[0:n]
1472	n/a	* is modified in place, by subtracting y from it. Borrows are propagated as
1473	n/a	* far as x[m-1], and the remaining borrow (0 or 1) is returned.
1474	n/a	*/
1475	n/a	static digit
1476	n/a	v_isub(digit x, Py_ssize_t m, digit y, Py_ssize_t n)
1477	n/a	{
1478	n/a	Py_ssize_t i;
1479	n/a	digit borrow = 0;
1480	n/a
1481	n/a	assert(m >= n);
1482	n/a	for (i = 0; i < n; ++i) {
1483	n/a	borrow = x[i] - y[i] - borrow;
1484	n/a	x[i] = borrow & PyLong_MASK;
1485	n/a	borrow >>= PyLong_SHIFT;
1486	n/a	borrow &= 1; /* keep only 1 sign bit */
1487	n/a	}
1488	n/a	for (; borrow && i < m; ++i) {
1489	n/a	borrow = x[i] - borrow;
1490	n/a	x[i] = borrow & PyLong_MASK;
1491	n/a	borrow >>= PyLong_SHIFT;
1492	n/a	borrow &= 1;
1493	n/a	}
1494	n/a	return borrow;
1495	n/a	}
1496	n/a
1497	n/a	/* Shift digit vector a[0:m] d bits left, with 0 <= d < PyLong_SHIFT. Put
1498	n/a	* result in z[0:m], and return the d bits shifted out of the top.
1499	n/a	*/
1500	n/a	static digit
1501	n/a	v_lshift(digit z, digit a, Py_ssize_t m, int d)
1502	n/a	{
1503	n/a	Py_ssize_t i;
1504	n/a	digit carry = 0;
1505	n/a
1506	n/a	assert(0 <= d && d < PyLong_SHIFT);
1507	n/a	for (i=0; i < m; i++) {
1508	n/a	twodigits acc = (twodigits)a[i] << d \| carry;
1509	n/a	z[i] = (digit)acc & PyLong_MASK;
1510	n/a	carry = (digit)(acc >> PyLong_SHIFT);
1511	n/a	}
1512	n/a	return carry;
1513	n/a	}
1514	n/a
1515	n/a	/* Shift digit vector a[0:m] d bits right, with 0 <= d < PyLong_SHIFT. Put
1516	n/a	* result in z[0:m], and return the d bits shifted out of the bottom.
1517	n/a	*/
1518	n/a	static digit
1519	n/a	v_rshift(digit z, digit a, Py_ssize_t m, int d)
1520	n/a	{
1521	n/a	Py_ssize_t i;
1522	n/a	digit carry = 0;
1523	n/a	digit mask = ((digit)1 << d) - 1U;
1524	n/a
1525	n/a	assert(0 <= d && d < PyLong_SHIFT);
1526	n/a	for (i=m; i-- > 0;) {
1527	n/a	twodigits acc = (twodigits)carry << PyLong_SHIFT \| a[i];
1528	n/a	carry = (digit)acc & mask;
1529	n/a	z[i] = (digit)(acc >> d);
1530	n/a	}
1531	n/a	return carry;
1532	n/a	}
1533	n/a
1534	n/a	/* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
1535	n/a	in pout, and returning the remainder. pin and pout point at the LSD.
1536	n/a	It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
1537	n/a	_PyLong_Format, but that should be done with great care since ints are
1538	n/a	immutable. */
1539	n/a
1540	n/a	static digit
1541	n/a	inplace_divrem1(digit pout, digit pin, Py_ssize_t size, digit n)
1542	n/a	{
1543	n/a	twodigits rem = 0;
1544	n/a
1545	n/a	assert(n > 0 && n <= PyLong_MASK);
1546	n/a	pin += size;
1547	n/a	pout += size;
1548	n/a	while (--size >= 0) {
1549	n/a	digit hi;
1550	n/a	rem = (rem << PyLong_SHIFT) \| *--pin;
1551	n/a	*--pout = hi = (digit)(rem / n);
1552	n/a	rem -= (twodigits)hi * n;
1553	n/a	}
1554	n/a	return (digit)rem;
1555	n/a	}
1556	n/a
1557	n/a	/* Divide an integer by a digit, returning both the quotient
1558	n/a	(as function result) and the remainder (through *prem).
1559	n/a	The sign of a is ignored; n should not be zero. */
1560	n/a
1561	n/a	static PyLongObject *
1562	n/a	divrem1(PyLongObject a, digit n, digit prem)
1563	n/a	{
1564	n/a	const Py_ssize_t size = Py_ABS(Py_SIZE(a));
1565	n/a	PyLongObject *z;
1566	n/a
1567	n/a	assert(n > 0 && n <= PyLong_MASK);
1568	n/a	z = _PyLong_New(size);
1569	n/a	if (z == NULL)
1570	n/a	return NULL;
1571	n/a	*prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
1572	n/a	return long_normalize(z);
1573	n/a	}
1574	n/a
1575	n/a	/* Convert an integer to a base 10 string. Returns a new non-shared
1576	n/a	string. (Return value is non-shared so that callers can modify the
1577	n/a	returned value if necessary.) */
1578	n/a
1579	n/a	static int
1580	n/a	long_to_decimal_string_internal(PyObject *aa,
1581	n/a	PyObject **p_output,
1582	n/a	_PyUnicodeWriter *writer,
1583	n/a	_PyBytesWriter *bytes_writer,
1584	n/a	char **bytes_str)
1585	n/a	{
1586	n/a	PyLongObject scratch, a;
1587	n/a	PyObject *str = NULL;
1588	n/a	Py_ssize_t size, strlen, size_a, i, j;
1589	n/a	digit pout, pin, rem, tenpow;
1590	n/a	int negative;
1591	n/a	int d;
1592	n/a	enum PyUnicode_Kind kind;
1593	n/a
1594	n/a	a = (PyLongObject *)aa;
1595	n/a	if (a == NULL \|\| !PyLong_Check(a)) {
1596	n/a	PyErr_BadInternalCall();
1597	n/a	return -1;
1598	n/a	}
1599	n/a	size_a = Py_ABS(Py_SIZE(a));
1600	n/a	negative = Py_SIZE(a) < 0;
1601	n/a
1602	n/a	/* quick and dirty upper bound for the number of digits
1603	n/a	required to express a in base _PyLong_DECIMAL_BASE:
1604	n/a
1605	n/a	#digits = 1 + floor(log2(a) / log2(_PyLong_DECIMAL_BASE))
1606	n/a
1607	n/a	But log2(a) < size_a * PyLong_SHIFT, and
1608	n/a	log2(_PyLong_DECIMAL_BASE) = log2(10) * _PyLong_DECIMAL_SHIFT
1609	n/a	> 3.3 * _PyLong_DECIMAL_SHIFT
1610	n/a
1611	n/a	size_a * PyLong_SHIFT / (3.3 * _PyLong_DECIMAL_SHIFT) =
1612	n/a	size_a + size_a / d < size_a + size_a / floor(d),
1613	n/a	where d = (3.3 * _PyLong_DECIMAL_SHIFT) /
1614	n/a	(PyLong_SHIFT - 3.3 * _PyLong_DECIMAL_SHIFT)
1615	n/a	*/
1616	n/a	d = (33 * _PyLong_DECIMAL_SHIFT) /
1617	n/a	(10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT);
1618	n/a	assert(size_a < PY_SSIZE_T_MAX/2);
1619	n/a	size = 1 + size_a + size_a / d;
1620	n/a	scratch = _PyLong_New(size);
1621	n/a	if (scratch == NULL)
1622	n/a	return -1;
1623	n/a
1624	n/a	/* convert array of base _PyLong_BASE digits in pin to an array of
1625	n/a	base _PyLong_DECIMAL_BASE digits in pout, following Knuth (TAOCP,
1626	n/a	Volume 2 (3rd edn), section 4.4, Method 1b). */
1627	n/a	pin = a->ob_digit;
1628	n/a	pout = scratch->ob_digit;
1629	n/a	size = 0;
1630	n/a	for (i = size_a; --i >= 0; ) {
1631	n/a	digit hi = pin[i];
1632	n/a	for (j = 0; j < size; j++) {
1633	n/a	twodigits z = (twodigits)pout[j] << PyLong_SHIFT \| hi;
1634	n/a	hi = (digit)(z / _PyLong_DECIMAL_BASE);
1635	n/a	pout[j] = (digit)(z - (twodigits)hi *
1636	n/a	_PyLong_DECIMAL_BASE);
1637	n/a	}
1638	n/a	while (hi) {
1639	n/a	pout[size++] = hi % _PyLong_DECIMAL_BASE;
1640	n/a	hi /= _PyLong_DECIMAL_BASE;
1641	n/a	}
1642	n/a	/* check for keyboard interrupt */
1643	n/a	SIGCHECK({
1644	n/a	Py_DECREF(scratch);
1645	n/a	return -1;
1646	n/a	});
1647	n/a	}
1648	n/a	/* pout should have at least one digit, so that the case when a = 0
1649	n/a	works correctly */
1650	n/a	if (size == 0)
1651	n/a	pout[size++] = 0;
1652	n/a
1653	n/a	/* calculate exact length of output string, and allocate */
1654	n/a	strlen = negative + 1 + (size - 1) * _PyLong_DECIMAL_SHIFT;
1655	n/a	tenpow = 10;
1656	n/a	rem = pout[size-1];
1657	n/a	while (rem >= tenpow) {
1658	n/a	tenpow *= 10;
1659	n/a	strlen++;
1660	n/a	}
1661	n/a	if (writer) {
1662	n/a	if (_PyUnicodeWriter_Prepare(writer, strlen, '9') == -1) {
1663	n/a	Py_DECREF(scratch);
1664	n/a	return -1;
1665	n/a	}
1666	n/a	kind = writer->kind;
1667	n/a	}
1668	n/a	else if (bytes_writer) {
1669	n/a	bytes_str = _PyBytesWriter_Prepare(bytes_writer, bytes_str, strlen);
1670	n/a	if (*bytes_str == NULL) {
1671	n/a	Py_DECREF(scratch);
1672	n/a	return -1;
1673	n/a	}
1674	n/a	}
1675	n/a	else {
1676	n/a	str = PyUnicode_New(strlen, '9');
1677	n/a	if (str == NULL) {
1678	n/a	Py_DECREF(scratch);
1679	n/a	return -1;
1680	n/a	}
1681	n/a	kind = PyUnicode_KIND(str);
1682	n/a	}
1683	n/a
1684	n/a	#define WRITE_DIGITS(p) \
1685	n/a	do { \
1686	n/a	/* pout[0] through pout[size-2] contribute exactly \
1687	n/a	_PyLong_DECIMAL_SHIFT digits each */ \
1688	n/a	for (i=0; i < size - 1; i++) { \
1689	n/a	rem = pout[i]; \
1690	n/a	for (j = 0; j < _PyLong_DECIMAL_SHIFT; j++) { \
1691	n/a	*--p = '0' + rem % 10; \
1692	n/a	rem /= 10; \
1693	n/a	} \
1694	n/a	} \
1695	n/a	/* pout[size-1]: always produce at least one decimal digit */ \
1696	n/a	rem = pout[i]; \
1697	n/a	do { \
1698	n/a	*--p = '0' + rem % 10; \
1699	n/a	rem /= 10; \
1700	n/a	} while (rem != 0); \
1701	n/a	\
1702	n/a	/* and sign */ \
1703	n/a	if (negative) \
1704	n/a	*--p = '-'; \
1705	n/a	} while (0)
1706	n/a
1707	n/a	#define WRITE_UNICODE_DIGITS(TYPE) \
1708	n/a	do { \
1709	n/a	if (writer) \
1710	n/a	p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + strlen; \
1711	n/a	else \
1712	n/a	p = (TYPE*)PyUnicode_DATA(str) + strlen; \
1713	n/a	\
1714	n/a	WRITE_DIGITS(p); \
1715	n/a	\
1716	n/a	/* check we've counted correctly */ \
1717	n/a	if (writer) \
1718	n/a	assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
1719	n/a	else \
1720	n/a	assert(p == (TYPE*)PyUnicode_DATA(str)); \
1721	n/a	} while (0)
1722	n/a
1723	n/a	/* fill the string right-to-left */
1724	n/a	if (bytes_writer) {
1725	n/a	char p = bytes_str + strlen;
1726	n/a	WRITE_DIGITS(p);
1727	n/a	assert(p == *bytes_str);
1728	n/a	}
1729	n/a	else if (kind == PyUnicode_1BYTE_KIND) {
1730	n/a	Py_UCS1 *p;
1731	n/a	WRITE_UNICODE_DIGITS(Py_UCS1);
1732	n/a	}
1733	n/a	else if (kind == PyUnicode_2BYTE_KIND) {
1734	n/a	Py_UCS2 *p;
1735	n/a	WRITE_UNICODE_DIGITS(Py_UCS2);
1736	n/a	}
1737	n/a	else {
1738	n/a	Py_UCS4 *p;
1739	n/a	assert (kind == PyUnicode_4BYTE_KIND);
1740	n/a	WRITE_UNICODE_DIGITS(Py_UCS4);
1741	n/a	}
1742	n/a	#undef WRITE_DIGITS
1743	n/a	#undef WRITE_UNICODE_DIGITS
1744	n/a
1745	n/a	Py_DECREF(scratch);
1746	n/a	if (writer) {
1747	n/a	writer->pos += strlen;
1748	n/a	}
1749	n/a	else if (bytes_writer) {
1750	n/a	(*bytes_str) += strlen;
1751	n/a	}
1752	n/a	else {
1753	n/a	assert(_PyUnicode_CheckConsistency(str, 1));
1754	n/a	p_output = (PyObject )str;
1755	n/a	}
1756	n/a	return 0;
1757	n/a	}
1758	n/a
1759	n/a	static PyObject *
1760	n/a	long_to_decimal_string(PyObject *aa)
1761	n/a	{
1762	n/a	PyObject *v;
1763	n/a	if (long_to_decimal_string_internal(aa, &v, NULL, NULL, NULL) == -1)
1764	n/a	return NULL;
1765	n/a	return v;
1766	n/a	}
1767	n/a
1768	n/a	/* Convert an int object to a string, using a given conversion base,
1769	n/a	which should be one of 2, 8 or 16. Return a string object.
1770	n/a	If base is 2, 8 or 16, add the proper prefix '0b', '0o' or '0x'
1771	n/a	if alternate is nonzero. */
1772	n/a
1773	n/a	static int
1774	n/a	long_format_binary(PyObject *aa, int base, int alternate,
1775	n/a	PyObject *p_output, _PyUnicodeWriter writer,
1776	n/a	_PyBytesWriter bytes_writer, char *bytes_str)
1777	n/a	{
1778	n/a	PyLongObject a = (PyLongObject )aa;
1779	n/a	PyObject *v = NULL;
1780	n/a	Py_ssize_t sz;
1781	n/a	Py_ssize_t size_a;
1782	n/a	enum PyUnicode_Kind kind;
1783	n/a	int negative;
1784	n/a	int bits;
1785	n/a
1786	n/a	assert(base == 2 \|\| base == 8 \|\| base == 16);
1787	n/a	if (a == NULL \|\| !PyLong_Check(a)) {
1788	n/a	PyErr_BadInternalCall();
1789	n/a	return -1;
1790	n/a	}
1791	n/a	size_a = Py_ABS(Py_SIZE(a));
1792	n/a	negative = Py_SIZE(a) < 0;
1793	n/a
1794	n/a	/* Compute a rough upper bound for the length of the string */
1795	n/a	switch (base) {
1796	n/a	case 16:
1797	n/a	bits = 4;
1798	n/a	break;
1799	n/a	case 8:
1800	n/a	bits = 3;
1801	n/a	break;
1802	n/a	case 2:
1803	n/a	bits = 1;
1804	n/a	break;
1805	n/a	default:
1806	n/a	assert(0); /* shouldn't ever get here */
1807	n/a	bits = 0; /* to silence gcc warning */
1808	n/a	}
1809	n/a
1810	n/a	/* Compute exact length 'sz' of output string. */
1811	n/a	if (size_a == 0) {
1812	n/a	sz = 1;
1813	n/a	}
1814	n/a	else {
1815	n/a	Py_ssize_t size_a_in_bits;
1816	n/a	/* Ensure overflow doesn't occur during computation of sz. */
1817	n/a	if (size_a > (PY_SSIZE_T_MAX - 3) / PyLong_SHIFT) {
1818	n/a	PyErr_SetString(PyExc_OverflowError,
1819	n/a	"int too large to format");
1820	n/a	return -1;
1821	n/a	}
1822	n/a	size_a_in_bits = (size_a - 1) * PyLong_SHIFT +
1823	n/a	bits_in_digit(a->ob_digit[size_a - 1]);
1824	n/a	/* Allow 1 character for a '-' sign. */
1825	n/a	sz = negative + (size_a_in_bits + (bits - 1)) / bits;
1826	n/a	}
1827	n/a	if (alternate) {
1828	n/a	/* 2 characters for prefix */
1829	n/a	sz += 2;
1830	n/a	}
1831	n/a
1832	n/a	if (writer) {
1833	n/a	if (_PyUnicodeWriter_Prepare(writer, sz, 'x') == -1)
1834	n/a	return -1;
1835	n/a	kind = writer->kind;
1836	n/a	}
1837	n/a	else if (bytes_writer) {
1838	n/a	bytes_str = _PyBytesWriter_Prepare(bytes_writer, bytes_str, sz);
1839	n/a	if (*bytes_str == NULL)
1840	n/a	return -1;
1841	n/a	}
1842	n/a	else {
1843	n/a	v = PyUnicode_New(sz, 'x');
1844	n/a	if (v == NULL)
1845	n/a	return -1;
1846	n/a	kind = PyUnicode_KIND(v);
1847	n/a	}
1848	n/a
1849	n/a	#define WRITE_DIGITS(p) \
1850	n/a	do { \
1851	n/a	if (size_a == 0) { \
1852	n/a	*--p = '0'; \
1853	n/a	} \
1854	n/a	else { \
1855	n/a	/* JRH: special case for power-of-2 bases */ \
1856	n/a	twodigits accum = 0; \
1857	n/a	int accumbits = 0; /* # of bits in accum */ \
1858	n/a	Py_ssize_t i; \
1859	n/a	for (i = 0; i < size_a; ++i) { \
1860	n/a	accum \|= (twodigits)a->ob_digit[i] << accumbits; \
1861	n/a	accumbits += PyLong_SHIFT; \
1862	n/a	assert(accumbits >= bits); \
1863	n/a	do { \
1864	n/a	char cdigit; \
1865	n/a	cdigit = (char)(accum & (base - 1)); \
1866	n/a	cdigit += (cdigit < 10) ? '0' : 'a'-10; \
1867	n/a	*--p = cdigit; \
1868	n/a	accumbits -= bits; \
1869	n/a	accum >>= bits; \
1870	n/a	} while (i < size_a-1 ? accumbits >= bits : accum > 0); \
1871	n/a	} \
1872	n/a	} \
1873	n/a	\
1874	n/a	if (alternate) { \
1875	n/a	if (base == 16) \
1876	n/a	*--p = 'x'; \
1877	n/a	else if (base == 8) \
1878	n/a	*--p = 'o'; \
1879	n/a	else /* (base == 2) */ \
1880	n/a	*--p = 'b'; \
1881	n/a	*--p = '0'; \
1882	n/a	} \
1883	n/a	if (negative) \
1884	n/a	*--p = '-'; \
1885	n/a	} while (0)
1886	n/a
1887	n/a	#define WRITE_UNICODE_DIGITS(TYPE) \
1888	n/a	do { \
1889	n/a	if (writer) \
1890	n/a	p = (TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos + sz; \
1891	n/a	else \
1892	n/a	p = (TYPE*)PyUnicode_DATA(v) + sz; \
1893	n/a	\
1894	n/a	WRITE_DIGITS(p); \
1895	n/a	\
1896	n/a	if (writer) \
1897	n/a	assert(p == ((TYPE*)PyUnicode_DATA(writer->buffer) + writer->pos)); \
1898	n/a	else \
1899	n/a	assert(p == (TYPE*)PyUnicode_DATA(v)); \
1900	n/a	} while (0)
1901	n/a
1902	n/a	if (bytes_writer) {
1903	n/a	char p = bytes_str + sz;
1904	n/a	WRITE_DIGITS(p);
1905	n/a	assert(p == *bytes_str);
1906	n/a	}
1907	n/a	else if (kind == PyUnicode_1BYTE_KIND) {
1908	n/a	Py_UCS1 *p;
1909	n/a	WRITE_UNICODE_DIGITS(Py_UCS1);
1910	n/a	}
1911	n/a	else if (kind == PyUnicode_2BYTE_KIND) {
1912	n/a	Py_UCS2 *p;
1913	n/a	WRITE_UNICODE_DIGITS(Py_UCS2);
1914	n/a	}
1915	n/a	else {
1916	n/a	Py_UCS4 *p;
1917	n/a	assert (kind == PyUnicode_4BYTE_KIND);
1918	n/a	WRITE_UNICODE_DIGITS(Py_UCS4);
1919	n/a	}
1920	n/a	#undef WRITE_DIGITS
1921	n/a	#undef WRITE_UNICODE_DIGITS
1922	n/a
1923	n/a	if (writer) {
1924	n/a	writer->pos += sz;
1925	n/a	}
1926	n/a	else if (bytes_writer) {
1927	n/a	(*bytes_str) += sz;
1928	n/a	}
1929	n/a	else {
1930	n/a	assert(_PyUnicode_CheckConsistency(v, 1));
1931	n/a	*p_output = v;
1932	n/a	}
1933	n/a	return 0;
1934	n/a	}
1935	n/a
1936	n/a	PyObject *
1937	n/a	_PyLong_Format(PyObject *obj, int base)
1938	n/a	{
1939	n/a	PyObject *str;
1940	n/a	int err;
1941	n/a	if (base == 10)
1942	n/a	err = long_to_decimal_string_internal(obj, &str, NULL, NULL, NULL);
1943	n/a	else
1944	n/a	err = long_format_binary(obj, base, 1, &str, NULL, NULL, NULL);
1945	n/a	if (err == -1)
1946	n/a	return NULL;
1947	n/a	return str;
1948	n/a	}
1949	n/a
1950	n/a	int
1951	n/a	_PyLong_FormatWriter(_PyUnicodeWriter *writer,
1952	n/a	PyObject *obj,
1953	n/a	int base, int alternate)
1954	n/a	{
1955	n/a	if (base == 10)
1956	n/a	return long_to_decimal_string_internal(obj, NULL, writer,
1957	n/a	NULL, NULL);
1958	n/a	else
1959	n/a	return long_format_binary(obj, base, alternate, NULL, writer,
1960	n/a	NULL, NULL);
1961	n/a	}
1962	n/a
1963	n/a	char*
1964	n/a	_PyLong_FormatBytesWriter(_PyBytesWriter writer, char str,
1965	n/a	PyObject *obj,
1966	n/a	int base, int alternate)
1967	n/a	{
1968	n/a	char *str2;
1969	n/a	int res;
1970	n/a	str2 = str;
1971	n/a	if (base == 10)
1972	n/a	res = long_to_decimal_string_internal(obj, NULL, NULL,
1973	n/a	writer, &str2);
1974	n/a	else
1975	n/a	res = long_format_binary(obj, base, alternate, NULL, NULL,
1976	n/a	writer, &str2);
1977	n/a	if (res < 0)
1978	n/a	return NULL;
1979	n/a	assert(str2 != NULL);
1980	n/a	return str2;
1981	n/a	}
1982	n/a
1983	n/a	/* Table of digit values for 8-bit string -> integer conversion.
1984	n/a	* '0' maps to 0, ..., '9' maps to 9.
1985	n/a	* 'a' and 'A' map to 10, ..., 'z' and 'Z' map to 35.
1986	n/a	* All other indices map to 37.
1987	n/a	* Note that when converting a base B string, a char c is a legitimate
1988	n/a	* base B digit iff _PyLong_DigitValue[Py_CHARPyLong_MASK(c)] < B.
1989	n/a	*/
1990	n/a	unsigned char _PyLong_DigitValue[256] = {
1991	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1992	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1993	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
1994	n/a	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 37, 37, 37, 37, 37, 37,
1995	n/a	37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1996	n/a	25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1997	n/a	37, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
1998	n/a	25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 37, 37, 37, 37, 37,
1999	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2000	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2001	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2002	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2003	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2004	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2005	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2006	n/a	37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2007	n/a	};
2008	n/a
2009	n/a	/* *str points to the first digit in a string of base `base` digits. base
2010	n/a	* is a power of 2 (2, 4, 8, 16, or 32). *str is set to point to the first
2011	n/a	* non-digit (which may be *str!). A normalized int is returned.
2012	n/a	* The point to this routine is that it takes time linear in the number of
2013	n/a	* string characters.
2014	n/a	*
2015	n/a	* Return values:
2016	n/a	* -1 on syntax error (exception needs to be set, *res is untouched)
2017	n/a	* 0 else (exception may be set, in that case *res is set to NULL)
2018	n/a	*/
2019	n/a	static int
2020	n/a	long_from_binary_base(const char str, int base, PyLongObject res)
2021	n/a	{
2022	n/a	const char p = str;
2023	n/a	const char *start = p;
2024	n/a	char prev = 0;
2025	n/a	int digits = 0;
2026	n/a	int bits_per_char;
2027	n/a	Py_ssize_t n;
2028	n/a	PyLongObject *z;
2029	n/a	twodigits accum;
2030	n/a	int bits_in_accum;
2031	n/a	digit *pdigit;
2032	n/a
2033	n/a	assert(base >= 2 && base <= 32 && (base & (base - 1)) == 0);
2034	n/a	n = base;
2035	n/a	for (bits_per_char = -1; n; ++bits_per_char) {
2036	n/a	n >>= 1;
2037	n/a	}
2038	n/a	/* count digits and set p to end-of-string */
2039	n/a	while (_PyLong_DigitValue[Py_CHARMASK(p)] < base \|\| p == '_') {
2040	n/a	if (*p == '_') {
2041	n/a	if (prev == '_') {
2042	n/a	*str = p - 1;
2043	n/a	return -1;
2044	n/a	}
2045	n/a	} else {
2046	n/a	++digits;
2047	n/a	}
2048	n/a	prev = *p;
2049	n/a	++p;
2050	n/a	}
2051	n/a	if (prev == '_') {
2052	n/a	/* Trailing underscore not allowed. */
2053	n/a	*str = p - 1;
2054	n/a	return -1;
2055	n/a	}
2056	n/a
2057	n/a	*str = p;
2058	n/a	/* n <- # of Python digits needed, = ceiling(n/PyLong_SHIFT). */
2059	n/a	n = digits * bits_per_char + PyLong_SHIFT - 1;
2060	n/a	if (n / bits_per_char < p - start) {
2061	n/a	PyErr_SetString(PyExc_ValueError,
2062	n/a	"int string too large to convert");
2063	n/a	*res = NULL;
2064	n/a	return 0;
2065	n/a	}
2066	n/a	n = n / PyLong_SHIFT;
2067	n/a	z = _PyLong_New(n);
2068	n/a	if (z == NULL) {
2069	n/a	*res = NULL;
2070	n/a	return 0;
2071	n/a	}
2072	n/a	/* Read string from right, and fill in int from left; i.e.,
2073	n/a	* from least to most significant in both.
2074	n/a	*/
2075	n/a	accum = 0;
2076	n/a	bits_in_accum = 0;
2077	n/a	pdigit = z->ob_digit;
2078	n/a	while (--p >= start) {
2079	n/a	int k;
2080	n/a	if (*p == '_') {
2081	n/a	continue;
2082	n/a	}
2083	n/a	k = (int)_PyLong_DigitValue[Py_CHARMASK(*p)];
2084	n/a	assert(k >= 0 && k < base);
2085	n/a	accum \|= (twodigits)k << bits_in_accum;
2086	n/a	bits_in_accum += bits_per_char;
2087	n/a	if (bits_in_accum >= PyLong_SHIFT) {
2088	n/a	*pdigit++ = (digit)(accum & PyLong_MASK);
2089	n/a	assert(pdigit - z->ob_digit <= n);
2090	n/a	accum >>= PyLong_SHIFT;
2091	n/a	bits_in_accum -= PyLong_SHIFT;
2092	n/a	assert(bits_in_accum < PyLong_SHIFT);
2093	n/a	}
2094	n/a	}
2095	n/a	if (bits_in_accum) {
2096	n/a	assert(bits_in_accum <= PyLong_SHIFT);
2097	n/a	*pdigit++ = (digit)accum;
2098	n/a	assert(pdigit - z->ob_digit <= n);
2099	n/a	}
2100	n/a	while (pdigit - z->ob_digit < n)
2101	n/a	*pdigit++ = 0;
2102	n/a	*res = long_normalize(z);
2103	n/a	return 0;
2104	n/a	}
2105	n/a
2106	n/a	/* Parses an int from a bytestring. Leading and trailing whitespace will be
2107	n/a	* ignored.
2108	n/a	*
2109	n/a	* If successful, a PyLong object will be returned and 'pend' will be pointing
2110	n/a	* to the first unused byte unless it's NULL.
2111	n/a	*
2112	n/a	* If unsuccessful, NULL will be returned.
2113	n/a	*/
2114	n/a	PyObject *
2115	n/a	PyLong_FromString(const char str, char *pend, int base)
2116	n/a	{
2117	n/a	int sign = 1, error_if_nonzero = 0;
2118	n/a	const char start, orig_str = str;
2119	n/a	PyLongObject *z = NULL;
2120	n/a	PyObject *strobj;
2121	n/a	Py_ssize_t slen;
2122	n/a
2123	n/a	if ((base != 0 && base < 2) \|\| base > 36) {
2124	n/a	PyErr_SetString(PyExc_ValueError,
2125	n/a	"int() arg 2 must be >= 2 and <= 36");
2126	n/a	return NULL;
2127	n/a	}
2128	n/a	while (str != '\0' && Py_ISSPACE(Py_CHARMASK(str))) {
2129	n/a	str++;
2130	n/a	}
2131	n/a	if (*str == '+') {
2132	n/a	++str;
2133	n/a	}
2134	n/a	else if (*str == '-') {
2135	n/a	++str;
2136	n/a	sign = -1;
2137	n/a	}
2138	n/a	if (base == 0) {
2139	n/a	if (str[0] != '0') {
2140	n/a	base = 10;
2141	n/a	}
2142	n/a	else if (str[1] == 'x' \|\| str[1] == 'X') {
2143	n/a	base = 16;
2144	n/a	}
2145	n/a	else if (str[1] == 'o' \|\| str[1] == 'O') {
2146	n/a	base = 8;
2147	n/a	}
2148	n/a	else if (str[1] == 'b' \|\| str[1] == 'B') {
2149	n/a	base = 2;
2150	n/a	}
2151	n/a	else {
2152	n/a	/* "old" (C-style) octal literal, now invalid.
2153	n/a	it might still be zero though */
2154	n/a	error_if_nonzero = 1;
2155	n/a	base = 10;
2156	n/a	}
2157	n/a	}
2158	n/a	if (str[0] == '0' &&
2159	n/a	((base == 16 && (str[1] == 'x' \|\| str[1] == 'X')) \|\|
2160	n/a	(base == 8 && (str[1] == 'o' \|\| str[1] == 'O')) \|\|
2161	n/a	(base == 2 && (str[1] == 'b' \|\| str[1] == 'B')))) {
2162	n/a	str += 2;
2163	n/a	/* One underscore allowed here. */
2164	n/a	if (*str == '_') {
2165	n/a	++str;
2166	n/a	}
2167	n/a	}
2168	n/a	if (str[0] == '_') {
2169	n/a	/* May not start with underscores. */
2170	n/a	goto onError;
2171	n/a	}
2172	n/a
2173	n/a	start = str;
2174	n/a	if ((base & (base - 1)) == 0) {
2175	n/a	int res = long_from_binary_base(&str, base, &z);
2176	n/a	if (res < 0) {
2177	n/a	/* Syntax error. */
2178	n/a	goto onError;
2179	n/a	}
2180	n/a	}
2181	n/a	else {
2182	n/a	/***
2183	n/a	Binary bases can be converted in time linear in the number of digits, because
2184	n/a	Python's representation base is binary. Other bases (including decimal!) use
2185	n/a	the simple quadratic-time algorithm below, complicated by some speed tricks.
2186	n/a
2187	n/a	First some math: the largest integer that can be expressed in N base-B digits
2188	n/a	is B**N-1. Consequently, if we have an N-digit input in base B, the worst-
2189	n/a	case number of Python digits needed to hold it is the smallest integer n s.t.
2190	n/a
2191	n/a	BASEn-1 >= BN-1 [or, adding 1 to both sides]
2192	n/a	BASEn >= BN [taking logs to base BASE]
2193	n/a	n >= log(B*N)/log(BASE) = N log(B)/log(BASE)
2194	n/a
2195	n/a	The static array log_base_BASE[base] == log(base)/log(BASE) so we can compute
2196	n/a	this quickly. A Python int with that much space is reserved near the start,
2197	n/a	and the result is computed into it.
2198	n/a
2199	n/a	The input string is actually treated as being in base base**i (i.e., i digits
2200	n/a	are processed at a time), where two more static arrays hold:
2201	n/a
2202	n/a	convwidth_base[base] = the largest integer i such that base**i <= BASE
2203	n/a	convmultmax_base[base] = base ** convwidth_base[base]
2204	n/a
2205	n/a	The first of these is the largest i such that i consecutive input digits
2206	n/a	must fit in a single Python digit. The second is effectively the input
2207	n/a	base we're really using.
2208	n/a
2209	n/a	Viewing the input as a sequence <c0, c1, ..., c_n-1> of digits in base
2210	n/a	convmultmax_base[base], the result is "simply"
2211	n/a
2212	n/a	(((c0B + c1)B + c2)B + c3)B + ... ))) + c_n-1
2213	n/a
2214	n/a	where B = convmultmax_base[base].
2215	n/a
2216	n/a	Error analysis: as above, the number of Python digits `n` needed is worst-
2217	n/a	case
2218	n/a
2219	n/a	n >= N * log(B)/log(BASE)
2220	n/a
2221	n/a	where `N` is the number of input digits in base `B`. This is computed via
2222	n/a
2223	n/a	size_z = (Py_ssize_t)((scan - str) * log_base_BASE[base]) + 1;
2224	n/a
2225	n/a	below. Two numeric concerns are how much space this can waste, and whether
2226	n/a	the computed result can be too small. To be concrete, assume BASE = 2**15,
2227	n/a	which is the default (and it's unlikely anyone changes that).
2228	n/a
2229	n/a	Waste isn't a problem: provided the first input digit isn't 0, the difference
2230	n/a	between the worst-case input with N digits and the smallest input with N
2231	n/a	digits is about a factor of B, but B is small compared to BASE so at most
2232	n/a	one allocated Python digit can remain unused on that count. If
2233	n/a	N*log(B)/log(BASE) is mathematically an exact integer, then truncating that
2234	n/a	and adding 1 returns a result 1 larger than necessary. However, that can't
2235	n/a	happen: whenever B is a power of 2, long_from_binary_base() is called
2236	n/a	instead, and it's impossible for Bi to be an integer power of 215 when
2237	n/a	B is not a power of 2 (i.e., it's impossible for N*log(B)/log(BASE) to be
2238	n/a	an exact integer when B is not a power of 2, since B**i has a prime factor
2239	n/a	other than 2 in that case, but (215)j's only prime factor is 2).
2240	n/a
2241	n/a	The computed result can be too small if the true value of N*log(B)/log(BASE)
2242	n/a	is a little bit larger than an exact integer, but due to roundoff errors (in
2243	n/a	computing log(B), log(BASE), their quotient, and/or multiplying that by N)
2244	n/a	yields a numeric result a little less than that integer. Unfortunately, "how
2245	n/a	close can a transcendental function get to an integer over some range?"
2246	n/a	questions are generally theoretically intractable. Computer analysis via
2247	n/a	continued fractions is practical: expand log(B)/log(BASE) via continued
2248	n/a	fractions, giving a sequence i/j of "the best" rational approximations. Then
2249	n/a	j*log(B)/log(BASE) is approximately equal to (the integer) i. This shows that
2250	n/a	we can get very close to being in trouble, but very rarely. For example,
2251	n/a	76573 is a denominator in one of the continued-fraction approximations to
2252	n/a	log(10)/log(2**15), and indeed:
2253	n/a
2254	n/a	>>> log(10)/log(2*15)76573
2255	n/a	16958.000000654003
2256	n/a
2257	n/a	is very close to an integer. If we were working with IEEE single-precision,
2258	n/a	rounding errors could kill us. Finding worst cases in IEEE double-precision
2259	n/a	requires better-than-double-precision log() functions, and Tim didn't bother.
2260	n/a	Instead the code checks to see whether the allocated space is enough as each
2261	n/a	new Python digit is added, and copies the whole thing to a larger int if not.
2262	n/a	This should happen extremely rarely, and in fact I don't have a test case
2263	n/a	that triggers it(!). Instead the code was tested by artificially allocating
2264	n/a	just 1 digit at the start, so that the copying code was exercised for every
2265	n/a	digit beyond the first.
2266	n/a	***/
2267	n/a	twodigits c; /* current input character */
2268	n/a	Py_ssize_t size_z;
2269	n/a	int digits = 0;
2270	n/a	int i;
2271	n/a	int convwidth;
2272	n/a	twodigits convmultmax, convmult;
2273	n/a	digit pz, pzstop;
2274	n/a	const char scan, lastdigit;
2275	n/a	char prev = 0;
2276	n/a
2277	n/a	static double log_base_BASE[37] = {0.0e0,};
2278	n/a	static int convwidth_base[37] = {0,};
2279	n/a	static twodigits convmultmax_base[37] = {0,};
2280	n/a
2281	n/a	if (log_base_BASE[base] == 0.0) {
2282	n/a	twodigits convmax = base;
2283	n/a	int i = 1;
2284	n/a
2285	n/a	log_base_BASE[base] = (log((double)base) /
2286	n/a	log((double)PyLong_BASE));
2287	n/a	for (;;) {
2288	n/a	twodigits next = convmax * base;
2289	n/a	if (next > PyLong_BASE) {
2290	n/a	break;
2291	n/a	}
2292	n/a	convmax = next;
2293	n/a	++i;
2294	n/a	}
2295	n/a	convmultmax_base[base] = convmax;
2296	n/a	assert(i > 0);
2297	n/a	convwidth_base[base] = i;
2298	n/a	}
2299	n/a
2300	n/a	/* Find length of the string of numeric characters. */
2301	n/a	scan = str;
2302	n/a	lastdigit = str;
2303	n/a
2304	n/a	while (_PyLong_DigitValue[Py_CHARMASK(scan)] < base \|\| scan == '_') {
2305	n/a	if (*scan == '_') {
2306	n/a	if (prev == '_') {
2307	n/a	/* Only one underscore allowed. */
2308	n/a	str = lastdigit + 1;
2309	n/a	goto onError;
2310	n/a	}
2311	n/a	}
2312	n/a	else {
2313	n/a	++digits;
2314	n/a	lastdigit = scan;
2315	n/a	}
2316	n/a	prev = *scan;
2317	n/a	++scan;
2318	n/a	}
2319	n/a	if (prev == '_') {
2320	n/a	/* Trailing underscore not allowed. */
2321	n/a	/* Set error pointer to first underscore. */
2322	n/a	str = lastdigit + 1;
2323	n/a	goto onError;
2324	n/a	}
2325	n/a
2326	n/a	/* Create an int object that can contain the largest possible
2327	n/a	* integer with this base and length. Note that there's no
2328	n/a	* need to initialize z->ob_digit -- no slot is read up before
2329	n/a	* being stored into.
2330	n/a	*/
2331	n/a	size_z = (Py_ssize_t)(digits * log_base_BASE[base]) + 1;
2332	n/a	/* Uncomment next line to test exceedingly rare copy code */
2333	n/a	/* size_z = 1; */
2334	n/a	assert(size_z > 0);
2335	n/a	z = _PyLong_New(size_z);
2336	n/a	if (z == NULL) {
2337	n/a	return NULL;
2338	n/a	}
2339	n/a	Py_SIZE(z) = 0;
2340	n/a
2341	n/a	/* `convwidth` consecutive input digits are treated as a single
2342	n/a	* digit in base `convmultmax`.
2343	n/a	*/
2344	n/a	convwidth = convwidth_base[base];
2345	n/a	convmultmax = convmultmax_base[base];
2346	n/a
2347	n/a	/* Work ;-) */
2348	n/a	while (str < scan) {
2349	n/a	if (*str == '_') {
2350	n/a	str++;
2351	n/a	continue;
2352	n/a	}
2353	n/a	/* grab up to convwidth digits from the input string */
2354	n/a	c = (digit)_PyLong_DigitValue[Py_CHARMASK(*str++)];
2355	n/a	for (i = 1; i < convwidth && str != scan; ++str) {
2356	n/a	if (*str == '_') {
2357	n/a	continue;
2358	n/a	}
2359	n/a	i++;
2360	n/a	c = (twodigits)(c * base +
2361	n/a	(int)_PyLong_DigitValue[Py_CHARMASK(*str)]);
2362	n/a	assert(c < PyLong_BASE);
2363	n/a	}
2364	n/a
2365	n/a	convmult = convmultmax;
2366	n/a	/* Calculate the shift only if we couldn't get
2367	n/a	* convwidth digits.
2368	n/a	*/
2369	n/a	if (i != convwidth) {
2370	n/a	convmult = base;
2371	n/a	for ( ; i > 1; --i) {
2372	n/a	convmult *= base;
2373	n/a	}
2374	n/a	}
2375	n/a
2376	n/a	/* Multiply z by convmult, and add c. */
2377	n/a	pz = z->ob_digit;
2378	n/a	pzstop = pz + Py_SIZE(z);
2379	n/a	for (; pz < pzstop; ++pz) {
2380	n/a	c += (twodigits)pz convmult;
2381	n/a	*pz = (digit)(c & PyLong_MASK);
2382	n/a	c >>= PyLong_SHIFT;
2383	n/a	}
2384	n/a	/* carry off the current end? */
2385	n/a	if (c) {
2386	n/a	assert(c < PyLong_BASE);
2387	n/a	if (Py_SIZE(z) < size_z) {
2388	n/a	*pz = (digit)c;
2389	n/a	++Py_SIZE(z);
2390	n/a	}
2391	n/a	else {
2392	n/a	PyLongObject *tmp;
2393	n/a	/* Extremely rare. Get more space. */
2394	n/a	assert(Py_SIZE(z) == size_z);
2395	n/a	tmp = _PyLong_New(size_z + 1);
2396	n/a	if (tmp == NULL) {
2397	n/a	Py_DECREF(z);
2398	n/a	return NULL;
2399	n/a	}
2400	n/a	memcpy(tmp->ob_digit,
2401	n/a	z->ob_digit,
2402	n/a	sizeof(digit) * size_z);
2403	n/a	Py_DECREF(z);
2404	n/a	z = tmp;
2405	n/a	z->ob_digit[size_z] = (digit)c;
2406	n/a	++size_z;
2407	n/a	}
2408	n/a	}
2409	n/a	}
2410	n/a	}
2411	n/a	if (z == NULL) {
2412	n/a	return NULL;
2413	n/a	}
2414	n/a	if (error_if_nonzero) {
2415	n/a	/* reset the base to 0, else the exception message
2416	n/a	doesn't make too much sense */
2417	n/a	base = 0;
2418	n/a	if (Py_SIZE(z) != 0) {
2419	n/a	goto onError;
2420	n/a	}
2421	n/a	/* there might still be other problems, therefore base
2422	n/a	remains zero here for the same reason */
2423	n/a	}
2424	n/a	if (str == start) {
2425	n/a	goto onError;
2426	n/a	}
2427	n/a	if (sign < 0) {
2428	n/a	Py_SIZE(z) = -(Py_SIZE(z));
2429	n/a	}
2430	n/a	while (str && Py_ISSPACE(Py_CHARMASK(str))) {
2431	n/a	str++;
2432	n/a	}
2433	n/a	if (*str != '\0') {
2434	n/a	goto onError;
2435	n/a	}
2436	n/a	long_normalize(z);
2437	n/a	z = maybe_small_long(z);
2438	n/a	if (z == NULL) {
2439	n/a	return NULL;
2440	n/a	}
2441	n/a	if (pend != NULL) {
2442	n/a	pend = (char )str;
2443	n/a	}
2444	n/a	return (PyObject *) z;
2445	n/a
2446	n/a	onError:
2447	n/a	if (pend != NULL) {
2448	n/a	pend = (char )str;
2449	n/a	}
2450	n/a	Py_XDECREF(z);
2451	n/a	slen = strlen(orig_str) < 200 ? strlen(orig_str) : 200;
2452	n/a	strobj = PyUnicode_FromStringAndSize(orig_str, slen);
2453	n/a	if (strobj == NULL) {
2454	n/a	return NULL;
2455	n/a	}
2456	n/a	PyErr_Format(PyExc_ValueError,
2457	n/a	"invalid literal for int() with base %d: %.200R",
2458	n/a	base, strobj);
2459	n/a	Py_DECREF(strobj);
2460	n/a	return NULL;
2461	n/a	}
2462	n/a
2463	n/a	/* Since PyLong_FromString doesn't have a length parameter,
2464	n/a	* check here for possible NULs in the string.
2465	n/a	*
2466	n/a	* Reports an invalid literal as a bytes object.
2467	n/a	*/
2468	n/a	PyObject *
2469	n/a	_PyLong_FromBytes(const char *s, Py_ssize_t len, int base)
2470	n/a	{
2471	n/a	PyObject result, strobj;
2472	n/a	char *end = NULL;
2473	n/a
2474	n/a	result = PyLong_FromString(s, &end, base);
2475	n/a	if (end == NULL \|\| (result != NULL && end == s + len))
2476	n/a	return result;
2477	n/a	Py_XDECREF(result);
2478	n/a	strobj = PyBytes_FromStringAndSize(s, Py_MIN(len, 200));
2479	n/a	if (strobj != NULL) {
2480	n/a	PyErr_Format(PyExc_ValueError,
2481	n/a	"invalid literal for int() with base %d: %.200R",
2482	n/a	base, strobj);
2483	n/a	Py_DECREF(strobj);
2484	n/a	}
2485	n/a	return NULL;
2486	n/a	}
2487	n/a
2488	n/a	PyObject *
2489	n/a	PyLong_FromUnicode(Py_UNICODE *u, Py_ssize_t length, int base)
2490	n/a	{
2491	n/a	PyObject v, unicode = PyUnicode_FromWideChar(u, length);
2492	n/a	if (unicode == NULL)
2493	n/a	return NULL;
2494	n/a	v = PyLong_FromUnicodeObject(unicode, base);
2495	n/a	Py_DECREF(unicode);
2496	n/a	return v;
2497	n/a	}
2498	n/a
2499	n/a	PyObject *
2500	n/a	PyLong_FromUnicodeObject(PyObject *u, int base)
2501	n/a	{
2502	n/a	PyObject result, asciidig;
2503	n/a	const char *buffer;
2504	n/a	char *end = NULL;
2505	n/a	Py_ssize_t buflen;
2506	n/a
2507	n/a	asciidig = _PyUnicode_TransformDecimalAndSpaceToASCII(u);
2508	n/a	if (asciidig == NULL)
2509	n/a	return NULL;
2510	n/a	buffer = PyUnicode_AsUTF8AndSize(asciidig, &buflen);
2511	n/a	if (buffer == NULL) {
2512	n/a	Py_DECREF(asciidig);
2513	n/a	if (!PyErr_ExceptionMatches(PyExc_UnicodeEncodeError))
2514	n/a	return NULL;
2515	n/a	}
2516	n/a	else {
2517	n/a	result = PyLong_FromString(buffer, &end, base);
2518	n/a	if (end == NULL \|\| (result != NULL && end == buffer + buflen)) {
2519	n/a	Py_DECREF(asciidig);
2520	n/a	return result;
2521	n/a	}
2522	n/a	Py_DECREF(asciidig);
2523	n/a	Py_XDECREF(result);
2524	n/a	}
2525	n/a	PyErr_Format(PyExc_ValueError,
2526	n/a	"invalid literal for int() with base %d: %.200R",
2527	n/a	base, u);
2528	n/a	return NULL;
2529	n/a	}
2530	n/a
2531	n/a	/* forward */
2532	n/a	static PyLongObject *x_divrem
2533	n/a	(PyLongObject , PyLongObject , PyLongObject **);
2534	n/a	static PyObject long_long(PyObject v);
2535	n/a
2536	n/a	/* Int division with remainder, top-level routine */
2537	n/a
2538	n/a	static int
2539	n/a	long_divrem(PyLongObject a, PyLongObject b,
2540	n/a	PyLongObject pdiv, PyLongObject prem)
2541	n/a	{
2542	n/a	Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
2543	n/a	PyLongObject *z;
2544	n/a
2545	n/a	if (size_b == 0) {
2546	n/a	PyErr_SetString(PyExc_ZeroDivisionError,
2547	n/a	"integer division or modulo by zero");
2548	n/a	return -1;
2549	n/a	}
2550	n/a	if (size_a < size_b \|\|
2551	n/a	(size_a == size_b &&
2552	n/a	a->ob_digit[size_a-1] < b->ob_digit[size_b-1])) {
2553	n/a	/* \|a\| < \|b\|. */
2554	n/a	pdiv = (PyLongObject)PyLong_FromLong(0);
2555	n/a	if (*pdiv == NULL)
2556	n/a	return -1;
2557	n/a	prem = (PyLongObject )long_long((PyObject *)a);
2558	n/a	if (*prem == NULL) {
2559	n/a	Py_CLEAR(*pdiv);
2560	n/a	return -1;
2561	n/a	}
2562	n/a	return 0;
2563	n/a	}
2564	n/a	if (size_b == 1) {
2565	n/a	digit rem = 0;
2566	n/a	z = divrem1(a, b->ob_digit[0], &rem);
2567	n/a	if (z == NULL)
2568	n/a	return -1;
2569	n/a	prem = (PyLongObject ) PyLong_FromLong((long)rem);
2570	n/a	if (*prem == NULL) {
2571	n/a	Py_DECREF(z);
2572	n/a	return -1;
2573	n/a	}
2574	n/a	}
2575	n/a	else {
2576	n/a	z = x_divrem(a, b, prem);
2577	n/a	if (z == NULL)
2578	n/a	return -1;
2579	n/a	}
2580	n/a	/* Set the signs.
2581	n/a	The quotient z has the sign of a*b;
2582	n/a	the remainder r has the sign of a,
2583	n/a	so a = bz + r. /
2584	n/a	if ((Py_SIZE(a) < 0) != (Py_SIZE(b) < 0)) {
2585	n/a	_PyLong_Negate(&z);
2586	n/a	if (z == NULL) {
2587	n/a	Py_CLEAR(*prem);
2588	n/a	return -1;
2589	n/a	}
2590	n/a	}
2591	n/a	if (Py_SIZE(a) < 0 && Py_SIZE(*prem) != 0) {
2592	n/a	_PyLong_Negate(prem);
2593	n/a	if (*prem == NULL) {
2594	n/a	Py_DECREF(z);
2595	n/a	Py_CLEAR(*prem);
2596	n/a	return -1;
2597	n/a	}
2598	n/a	}
2599	n/a	*pdiv = maybe_small_long(z);
2600	n/a	return 0;
2601	n/a	}
2602	n/a
2603	n/a	/* Unsigned int division with remainder -- the algorithm. The arguments v1
2604	n/a	and w1 should satisfy 2 <= Py_ABS(Py_SIZE(w1)) <= Py_ABS(Py_SIZE(v1)). */
2605	n/a
2606	n/a	static PyLongObject *
2607	n/a	x_divrem(PyLongObject v1, PyLongObject w1, PyLongObject **prem)
2608	n/a	{
2609	n/a	PyLongObject v, w, *a;
2610	n/a	Py_ssize_t i, k, size_v, size_w;
2611	n/a	int d;
2612	n/a	digit wm1, wm2, carry, q, r, vtop, v0, vk, w0, ak;
2613	n/a	twodigits vv;
2614	n/a	sdigit zhi;
2615	n/a	stwodigits z;
2616	n/a
2617	n/a	/* We follow Knuth [The Art of Computer Programming, Vol. 2 (3rd
2618	n/a	edn.), section 4.3.1, Algorithm D], except that we don't explicitly
2619	n/a	handle the special case when the initial estimate q for a quotient
2620	n/a	digit is >= PyLong_BASE: the max value for q is PyLong_BASE+1, and
2621	n/a	that won't overflow a digit. */
2622	n/a
2623	n/a	/* allocate space; w will also be used to hold the final remainder */
2624	n/a	size_v = Py_ABS(Py_SIZE(v1));
2625	n/a	size_w = Py_ABS(Py_SIZE(w1));
2626	n/a	assert(size_v >= size_w && size_w >= 2); /* Assert checks by div() */
2627	n/a	v = _PyLong_New(size_v+1);
2628	n/a	if (v == NULL) {
2629	n/a	*prem = NULL;
2630	n/a	return NULL;
2631	n/a	}
2632	n/a	w = _PyLong_New(size_w);
2633	n/a	if (w == NULL) {
2634	n/a	Py_DECREF(v);
2635	n/a	*prem = NULL;
2636	n/a	return NULL;
2637	n/a	}
2638	n/a
2639	n/a	/* normalize: shift w1 left so that its top digit is >= PyLong_BASE/2.
2640	n/a	shift v1 left by the same amount. Results go into w and v. */
2641	n/a	d = PyLong_SHIFT - bits_in_digit(w1->ob_digit[size_w-1]);
2642	n/a	carry = v_lshift(w->ob_digit, w1->ob_digit, size_w, d);
2643	n/a	assert(carry == 0);
2644	n/a	carry = v_lshift(v->ob_digit, v1->ob_digit, size_v, d);
2645	n/a	if (carry != 0 \|\| v->ob_digit[size_v-1] >= w->ob_digit[size_w-1]) {
2646	n/a	v->ob_digit[size_v] = carry;
2647	n/a	size_v++;
2648	n/a	}
2649	n/a
2650	n/a	/* Now v->ob_digit[size_v-1] < w->ob_digit[size_w-1], so quotient has
2651	n/a	at most (and usually exactly) k = size_v - size_w digits. */
2652	n/a	k = size_v - size_w;
2653	n/a	assert(k >= 0);
2654	n/a	a = _PyLong_New(k);
2655	n/a	if (a == NULL) {
2656	n/a	Py_DECREF(w);
2657	n/a	Py_DECREF(v);
2658	n/a	*prem = NULL;
2659	n/a	return NULL;
2660	n/a	}
2661	n/a	v0 = v->ob_digit;
2662	n/a	w0 = w->ob_digit;
2663	n/a	wm1 = w0[size_w-1];
2664	n/a	wm2 = w0[size_w-2];
2665	n/a	for (vk = v0+k, ak = a->ob_digit + k; vk-- > v0;) {
2666	n/a	/* inner loop: divide vk[0:size_w+1] by w0[0:size_w], giving
2667	n/a	single-digit quotient q, remainder in vk[0:size_w]. */
2668	n/a
2669	n/a	SIGCHECK({
2670	n/a	Py_DECREF(a);
2671	n/a	Py_DECREF(w);
2672	n/a	Py_DECREF(v);
2673	n/a	*prem = NULL;
2674	n/a	return NULL;
2675	n/a	});
2676	n/a
2677	n/a	/* estimate quotient digit q; may overestimate by 1 (rare) */
2678	n/a	vtop = vk[size_w];
2679	n/a	assert(vtop <= wm1);
2680	n/a	vv = ((twodigits)vtop << PyLong_SHIFT) \| vk[size_w-1];
2681	n/a	q = (digit)(vv / wm1);
2682	n/a	r = (digit)(vv - (twodigits)wm1 * q); /* r = vv % wm1 */
2683	n/a	while ((twodigits)wm2 * q > (((twodigits)r << PyLong_SHIFT)
2684	n/a	\| vk[size_w-2])) {
2685	n/a	--q;
2686	n/a	r += wm1;
2687	n/a	if (r >= PyLong_BASE)
2688	n/a	break;
2689	n/a	}
2690	n/a	assert(q <= PyLong_BASE);
2691	n/a
2692	n/a	/* subtract qw0[0:size_w] from vk[0:size_w+1] /
2693	n/a	zhi = 0;
2694	n/a	for (i = 0; i < size_w; ++i) {
2695	n/a	/* invariants: -PyLong_BASE <= -q <= zhi <= 0;
2696	n/a	-PyLong_BASE * q <= z < PyLong_BASE */
2697	n/a	z = (sdigit)vk[i] + zhi -
2698	n/a	(stwodigits)q * (stwodigits)w0[i];
2699	n/a	vk[i] = (digit)z & PyLong_MASK;
2700	n/a	zhi = (sdigit)Py_ARITHMETIC_RIGHT_SHIFT(stwodigits,
2701	n/a	z, PyLong_SHIFT);
2702	n/a	}
2703	n/a
2704	n/a	/* add w back if q was too large (this branch taken rarely) */
2705	n/a	assert((sdigit)vtop + zhi == -1 \|\| (sdigit)vtop + zhi == 0);
2706	n/a	if ((sdigit)vtop + zhi < 0) {
2707	n/a	carry = 0;
2708	n/a	for (i = 0; i < size_w; ++i) {
2709	n/a	carry += vk[i] + w0[i];
2710	n/a	vk[i] = carry & PyLong_MASK;
2711	n/a	carry >>= PyLong_SHIFT;
2712	n/a	}
2713	n/a	--q;
2714	n/a	}
2715	n/a
2716	n/a	/* store quotient digit */
2717	n/a	assert(q < PyLong_BASE);
2718	n/a	*--ak = q;
2719	n/a	}
2720	n/a
2721	n/a	/* unshift remainder; we reuse w to store the result */
2722	n/a	carry = v_rshift(w0, v0, size_w, d);
2723	n/a	assert(carry==0);
2724	n/a	Py_DECREF(v);
2725	n/a
2726	n/a	*prem = long_normalize(w);
2727	n/a	return long_normalize(a);
2728	n/a	}
2729	n/a
2730	n/a	/* For a nonzero PyLong a, express a in the form x * 2**e, with 0.5 <=
2731	n/a	abs(x) < 1.0 and e >= 0; return x and put e in *e. Here x is
2732	n/a	rounded to DBL_MANT_DIG significant bits using round-half-to-even.
2733	n/a	If a == 0, return 0.0 and set *e = 0. If the resulting exponent
2734	n/a	e is larger than PY_SSIZE_T_MAX, raise OverflowError and return
2735	n/a	-1.0. */
2736	n/a
2737	n/a	/* attempt to define 2.0*DBL_MANT_DIG as a compile-time constant /
2738	n/a	#if DBL_MANT_DIG == 53
2739	n/a	#define EXP2_DBL_MANT_DIG 9007199254740992.0
2740	n/a	#else
2741	n/a	#define EXP2_DBL_MANT_DIG (ldexp(1.0, DBL_MANT_DIG))
2742	n/a	#endif
2743	n/a
2744	n/a	double
2745	n/a	_PyLong_Frexp(PyLongObject a, Py_ssize_t e)
2746	n/a	{
2747	n/a	Py_ssize_t a_size, a_bits, shift_digits, shift_bits, x_size;
2748	n/a	/* See below for why x_digits is always large enough. */
2749	n/a	digit rem, x_digits[2 + (DBL_MANT_DIG + 1) / PyLong_SHIFT];
2750	n/a	double dx;
2751	n/a	/* Correction term for round-half-to-even rounding. For a digit x,
2752	n/a	"x + half_even_correction[x & 7]" gives x rounded to the nearest
2753	n/a	multiple of 4, rounding ties to a multiple of 8. */
2754	n/a	static const int half_even_correction[8] = {0, -1, -2, 1, 0, -1, 2, 1};
2755	n/a
2756	n/a	a_size = Py_ABS(Py_SIZE(a));
2757	n/a	if (a_size == 0) {
2758	n/a	/* Special case for 0: significand 0.0, exponent 0. */
2759	n/a	*e = 0;
2760	n/a	return 0.0;
2761	n/a	}
2762	n/a	a_bits = bits_in_digit(a->ob_digit[a_size-1]);
2763	n/a	/* The following is an overflow-free version of the check
2764	n/a	"if ((a_size - 1) * PyLong_SHIFT + a_bits > PY_SSIZE_T_MAX) ..." */
2765	n/a	if (a_size >= (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 &&
2766	n/a	(a_size > (PY_SSIZE_T_MAX - 1) / PyLong_SHIFT + 1 \|\|
2767	n/a	a_bits > (PY_SSIZE_T_MAX - 1) % PyLong_SHIFT + 1))
2768	n/a	goto overflow;
2769	n/a	a_bits = (a_size - 1) * PyLong_SHIFT + a_bits;
2770	n/a
2771	n/a	/* Shift the first DBL_MANT_DIG + 2 bits of a into x_digits[0:x_size]
2772	n/a	(shifting left if a_bits <= DBL_MANT_DIG + 2).
2773	n/a
2774	n/a	Number of digits needed for result: write // for floor division.
2775	n/a	Then if shifting left, we end up using
2776	n/a
2777	n/a	1 + a_size + (DBL_MANT_DIG + 2 - a_bits) // PyLong_SHIFT
2778	n/a
2779	n/a	digits. If shifting right, we use
2780	n/a
2781	n/a	a_size - (a_bits - DBL_MANT_DIG - 2) // PyLong_SHIFT
2782	n/a
2783	n/a	digits. Using a_size = 1 + (a_bits - 1) // PyLong_SHIFT along with
2784	n/a	the inequalities
2785	n/a
2786	n/a	m // PyLong_SHIFT + n // PyLong_SHIFT <= (m + n) // PyLong_SHIFT
2787	n/a	m // PyLong_SHIFT - n // PyLong_SHIFT <=
2788	n/a	1 + (m - n - 1) // PyLong_SHIFT,
2789	n/a
2790	n/a	valid for any integers m and n, we find that x_size satisfies
2791	n/a
2792	n/a	x_size <= 2 + (DBL_MANT_DIG + 1) // PyLong_SHIFT
2793	n/a
2794	n/a	in both cases.
2795	n/a	*/
2796	n/a	if (a_bits <= DBL_MANT_DIG + 2) {
2797	n/a	shift_digits = (DBL_MANT_DIG + 2 - a_bits) / PyLong_SHIFT;
2798	n/a	shift_bits = (DBL_MANT_DIG + 2 - a_bits) % PyLong_SHIFT;
2799	n/a	x_size = 0;
2800	n/a	while (x_size < shift_digits)
2801	n/a	x_digits[x_size++] = 0;
2802	n/a	rem = v_lshift(x_digits + x_size, a->ob_digit, a_size,
2803	n/a	(int)shift_bits);
2804	n/a	x_size += a_size;
2805	n/a	x_digits[x_size++] = rem;
2806	n/a	}
2807	n/a	else {
2808	n/a	shift_digits = (a_bits - DBL_MANT_DIG - 2) / PyLong_SHIFT;
2809	n/a	shift_bits = (a_bits - DBL_MANT_DIG - 2) % PyLong_SHIFT;
2810	n/a	rem = v_rshift(x_digits, a->ob_digit + shift_digits,
2811	n/a	a_size - shift_digits, (int)shift_bits);
2812	n/a	x_size = a_size - shift_digits;
2813	n/a	/* For correct rounding below, we need the least significant
2814	n/a	bit of x to be 'sticky' for this shift: if any of the bits
2815	n/a	shifted out was nonzero, we set the least significant bit
2816	n/a	of x. */
2817	n/a	if (rem)
2818	n/a	x_digits[0] \|= 1;
2819	n/a	else
2820	n/a	while (shift_digits > 0)
2821	n/a	if (a->ob_digit[--shift_digits]) {
2822	n/a	x_digits[0] \|= 1;
2823	n/a	break;
2824	n/a	}
2825	n/a	}
2826	n/a	assert(1 <= x_size && x_size <= (Py_ssize_t)Py_ARRAY_LENGTH(x_digits));
2827	n/a
2828	n/a	/* Round, and convert to double. */
2829	n/a	x_digits[0] += half_even_correction[x_digits[0] & 7];
2830	n/a	dx = x_digits[--x_size];
2831	n/a	while (x_size > 0)
2832	n/a	dx = dx * PyLong_BASE + x_digits[--x_size];
2833	n/a
2834	n/a	/* Rescale; make correction if result is 1.0. */
2835	n/a	dx /= 4.0 * EXP2_DBL_MANT_DIG;
2836	n/a	if (dx == 1.0) {
2837	n/a	if (a_bits == PY_SSIZE_T_MAX)
2838	n/a	goto overflow;
2839	n/a	dx = 0.5;
2840	n/a	a_bits += 1;
2841	n/a	}
2842	n/a
2843	n/a	*e = a_bits;
2844	n/a	return Py_SIZE(a) < 0 ? -dx : dx;
2845	n/a
2846	n/a	overflow:
2847	n/a	/* exponent > PY_SSIZE_T_MAX */
2848	n/a	PyErr_SetString(PyExc_OverflowError,
2849	n/a	"huge integer: number of bits overflows a Py_ssize_t");
2850	n/a	*e = 0;
2851	n/a	return -1.0;
2852	n/a	}
2853	n/a
2854	n/a	/* Get a C double from an int object. Rounds to the nearest double,
2855	n/a	using the round-half-to-even rule in the case of a tie. */
2856	n/a
2857	n/a	double
2858	n/a	PyLong_AsDouble(PyObject *v)
2859	n/a	{
2860	n/a	Py_ssize_t exponent;
2861	n/a	double x;
2862	n/a
2863	n/a	if (v == NULL) {
2864	n/a	PyErr_BadInternalCall();
2865	n/a	return -1.0;
2866	n/a	}
2867	n/a	if (!PyLong_Check(v)) {
2868	n/a	PyErr_SetString(PyExc_TypeError, "an integer is required");
2869	n/a	return -1.0;
2870	n/a	}
2871	n/a	if (Py_ABS(Py_SIZE(v)) <= 1) {
2872	n/a	/* Fast path; single digit long (31 bits) will cast safely
2873	n/a	to double. This improves performance of FP/long operations
2874	n/a	by 20%.
2875	n/a	*/
2876	n/a	return (double)MEDIUM_VALUE((PyLongObject *)v);
2877	n/a	}
2878	n/a	x = _PyLong_Frexp((PyLongObject *)v, &exponent);
2879	n/a	if ((x == -1.0 && PyErr_Occurred()) \|\| exponent > DBL_MAX_EXP) {
2880	n/a	PyErr_SetString(PyExc_OverflowError,
2881	n/a	"int too large to convert to float");
2882	n/a	return -1.0;
2883	n/a	}
2884	n/a	return ldexp(x, (int)exponent);
2885	n/a	}
2886	n/a
2887	n/a	/* Methods */
2888	n/a
2889	n/a	static void
2890	n/a	long_dealloc(PyObject *v)
2891	n/a	{
2892	n/a	Py_TYPE(v)->tp_free(v);
2893	n/a	}
2894	n/a
2895	n/a	static int
2896	n/a	long_compare(PyLongObject a, PyLongObject b)
2897	n/a	{
2898	n/a	Py_ssize_t sign;
2899	n/a
2900	n/a	if (Py_SIZE(a) != Py_SIZE(b)) {
2901	n/a	sign = Py_SIZE(a) - Py_SIZE(b);
2902	n/a	}
2903	n/a	else {
2904	n/a	Py_ssize_t i = Py_ABS(Py_SIZE(a));
2905	n/a	while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
2906	n/a	;
2907	n/a	if (i < 0)
2908	n/a	sign = 0;
2909	n/a	else {
2910	n/a	sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
2911	n/a	if (Py_SIZE(a) < 0)
2912	n/a	sign = -sign;
2913	n/a	}
2914	n/a	}
2915	n/a	return sign < 0 ? -1 : sign > 0 ? 1 : 0;
2916	n/a	}
2917	n/a
2918	n/a	#define TEST_COND(cond) \
2919	n/a	((cond) ? Py_True : Py_False)
2920	n/a
2921	n/a	static PyObject *
2922	n/a	long_richcompare(PyObject self, PyObject other, int op)
2923	n/a	{
2924	n/a	int result;
2925	n/a	PyObject *v;
2926	n/a	CHECK_BINOP(self, other);
2927	n/a	if (self == other)
2928	n/a	result = 0;
2929	n/a	else
2930	n/a	result = long_compare((PyLongObject)self, (PyLongObject)other);
2931	n/a	/* Convert the return value to a Boolean */
2932	n/a	switch (op) {
2933	n/a	case Py_EQ:
2934	n/a	v = TEST_COND(result == 0);
2935	n/a	break;
2936	n/a	case Py_NE:
2937	n/a	v = TEST_COND(result != 0);
2938	n/a	break;
2939	n/a	case Py_LE:
2940	n/a	v = TEST_COND(result <= 0);
2941	n/a	break;
2942	n/a	case Py_GE:
2943	n/a	v = TEST_COND(result >= 0);
2944	n/a	break;
2945	n/a	case Py_LT:
2946	n/a	v = TEST_COND(result == -1);
2947	n/a	break;
2948	n/a	case Py_GT:
2949	n/a	v = TEST_COND(result == 1);
2950	n/a	break;
2951	n/a	default:
2952	n/a	PyErr_BadArgument();
2953	n/a	return NULL;
2954	n/a	}
2955	n/a	Py_INCREF(v);
2956	n/a	return v;
2957	n/a	}
2958	n/a
2959	n/a	static Py_hash_t
2960	n/a	long_hash(PyLongObject *v)
2961	n/a	{
2962	n/a	Py_uhash_t x;
2963	n/a	Py_ssize_t i;
2964	n/a	int sign;
2965	n/a
2966	n/a	i = Py_SIZE(v);
2967	n/a	switch(i) {
2968	n/a	case -1: return v->ob_digit[0]==1 ? -2 : -(sdigit)v->ob_digit[0];
2969	n/a	case 0: return 0;
2970	n/a	case 1: return v->ob_digit[0];
2971	n/a	}
2972	n/a	sign = 1;
2973	n/a	x = 0;
2974	n/a	if (i < 0) {
2975	n/a	sign = -1;
2976	n/a	i = -(i);
2977	n/a	}
2978	n/a	while (--i >= 0) {
2979	n/a	/* Here x is a quantity in the range [0, _PyHASH_MODULUS); we
2980	n/a	want to compute x * 2**PyLong_SHIFT + v->ob_digit[i] modulo
2981	n/a	_PyHASH_MODULUS.
2982	n/a
2983	n/a	The computation of x * 2**PyLong_SHIFT % _PyHASH_MODULUS
2984	n/a	amounts to a rotation of the bits of x. To see this, write
2985	n/a
2986	n/a	x * 2*PyLong_SHIFT = y 2**_PyHASH_BITS + z
2987	n/a
2988	n/a	where y = x >> (_PyHASH_BITS - PyLong_SHIFT) gives the top
2989	n/a	PyLong_SHIFT bits of x (those that are shifted out of the
2990	n/a	original _PyHASH_BITS bits, and z = (x << PyLong_SHIFT) &
2991	n/a	_PyHASH_MODULUS gives the bottom _PyHASH_BITS - PyLong_SHIFT
2992	n/a	bits of x, shifted up. Then since 2**_PyHASH_BITS is
2993	n/a	congruent to 1 modulo _PyHASH_MODULUS, y2*_PyHASH_BITS is
2994	n/a	congruent to y modulo _PyHASH_MODULUS. So
2995	n/a
2996	n/a	x * 2**PyLong_SHIFT = y + z (mod _PyHASH_MODULUS).
2997	n/a
2998	n/a	The right-hand side is just the result of rotating the
2999	n/a	_PyHASH_BITS bits of x left by PyLong_SHIFT places; since
3000	n/a	not all _PyHASH_BITS bits of x are 1s, the same is true
3001	n/a	after rotation, so 0 <= y+z < _PyHASH_MODULUS and y + z is
3002	n/a	the reduction of x2*PyLong_SHIFT modulo
3003	n/a	_PyHASH_MODULUS. */
3004	n/a	x = ((x << PyLong_SHIFT) & _PyHASH_MODULUS) \|
3005	n/a	(x >> (_PyHASH_BITS - PyLong_SHIFT));
3006	n/a	x += v->ob_digit[i];
3007	n/a	if (x >= _PyHASH_MODULUS)
3008	n/a	x -= _PyHASH_MODULUS;
3009	n/a	}
3010	n/a	x = x * sign;
3011	n/a	if (x == (Py_uhash_t)-1)
3012	n/a	x = (Py_uhash_t)-2;
3013	n/a	return (Py_hash_t)x;
3014	n/a	}
3015	n/a
3016	n/a
3017	n/a	/* Add the absolute values of two integers. */
3018	n/a
3019	n/a	static PyLongObject *
3020	n/a	x_add(PyLongObject a, PyLongObject b)
3021	n/a	{
3022	n/a	Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
3023	n/a	PyLongObject *z;
3024	n/a	Py_ssize_t i;
3025	n/a	digit carry = 0;
3026	n/a
3027	n/a	/* Ensure a is the larger of the two: */
3028	n/a	if (size_a < size_b) {
3029	n/a	{ PyLongObject *temp = a; a = b; b = temp; }
3030	n/a	{ Py_ssize_t size_temp = size_a;
3031	n/a	size_a = size_b;
3032	n/a	size_b = size_temp; }
3033	n/a	}
3034	n/a	z = _PyLong_New(size_a+1);
3035	n/a	if (z == NULL)
3036	n/a	return NULL;
3037	n/a	for (i = 0; i < size_b; ++i) {
3038	n/a	carry += a->ob_digit[i] + b->ob_digit[i];
3039	n/a	z->ob_digit[i] = carry & PyLong_MASK;
3040	n/a	carry >>= PyLong_SHIFT;
3041	n/a	}
3042	n/a	for (; i < size_a; ++i) {
3043	n/a	carry += a->ob_digit[i];
3044	n/a	z->ob_digit[i] = carry & PyLong_MASK;
3045	n/a	carry >>= PyLong_SHIFT;
3046	n/a	}
3047	n/a	z->ob_digit[i] = carry;
3048	n/a	return long_normalize(z);
3049	n/a	}
3050	n/a
3051	n/a	/* Subtract the absolute values of two integers. */
3052	n/a
3053	n/a	static PyLongObject *
3054	n/a	x_sub(PyLongObject a, PyLongObject b)
3055	n/a	{
3056	n/a	Py_ssize_t size_a = Py_ABS(Py_SIZE(a)), size_b = Py_ABS(Py_SIZE(b));
3057	n/a	PyLongObject *z;
3058	n/a	Py_ssize_t i;
3059	n/a	int sign = 1;
3060	n/a	digit borrow = 0;
3061	n/a
3062	n/a	/* Ensure a is the larger of the two: */
3063	n/a	if (size_a < size_b) {
3064	n/a	sign = -1;
3065	n/a	{ PyLongObject *temp = a; a = b; b = temp; }
3066	n/a	{ Py_ssize_t size_temp = size_a;
3067	n/a	size_a = size_b;
3068	n/a	size_b = size_temp; }
3069	n/a	}
3070	n/a	else if (size_a == size_b) {
3071	n/a	/* Find highest digit where a and b differ: */
3072	n/a	i = size_a;
3073	n/a	while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i])
3074	n/a	;
3075	n/a	if (i < 0)
3076	n/a	return (PyLongObject *)PyLong_FromLong(0);
3077	n/a	if (a->ob_digit[i] < b->ob_digit[i]) {
3078	n/a	sign = -1;
3079	n/a	{ PyLongObject *temp = a; a = b; b = temp; }
3080	n/a	}
3081	n/a	size_a = size_b = i+1;
3082	n/a	}
3083	n/a	z = _PyLong_New(size_a);
3084	n/a	if (z == NULL)
3085	n/a	return NULL;
3086	n/a	for (i = 0; i < size_b; ++i) {
3087	n/a	/* The following assumes unsigned arithmetic
3088	n/a	works module 2*N for some N>PyLong_SHIFT. /
3089	n/a	borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
3090	n/a	z->ob_digit[i] = borrow & PyLong_MASK;
3091	n/a	borrow >>= PyLong_SHIFT;
3092	n/a	borrow &= 1; /* Keep only one sign bit */
3093	n/a	}
3094	n/a	for (; i < size_a; ++i) {
3095	n/a	borrow = a->ob_digit[i] - borrow;
3096	n/a	z->ob_digit[i] = borrow & PyLong_MASK;
3097	n/a	borrow >>= PyLong_SHIFT;
3098	n/a	borrow &= 1; /* Keep only one sign bit */
3099	n/a	}
3100	n/a	assert(borrow == 0);
3101	n/a	if (sign < 0) {
3102	n/a	Py_SIZE(z) = -Py_SIZE(z);
3103	n/a	}
3104	n/a	return long_normalize(z);
3105	n/a	}
3106	n/a
3107	n/a	static PyObject *
3108	n/a	long_add(PyLongObject a, PyLongObject b)
3109	n/a	{
3110	n/a	PyLongObject *z;
3111	n/a
3112	n/a	CHECK_BINOP(a, b);
3113	n/a
3114	n/a	if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3115	n/a	return PyLong_FromLong(MEDIUM_VALUE(a) + MEDIUM_VALUE(b));
3116	n/a	}
3117	n/a	if (Py_SIZE(a) < 0) {
3118	n/a	if (Py_SIZE(b) < 0) {
3119	n/a	z = x_add(a, b);
3120	n/a	if (z != NULL) {
3121	n/a	/* x_add received at least one multiple-digit int,
3122	n/a	and thus z must be a multiple-digit int.
3123	n/a	That also means z is not an element of
3124	n/a	small_ints, so negating it in-place is safe. */
3125	n/a	assert(Py_REFCNT(z) == 1);
3126	n/a	Py_SIZE(z) = -(Py_SIZE(z));
3127	n/a	}
3128	n/a	}
3129	n/a	else
3130	n/a	z = x_sub(b, a);
3131	n/a	}
3132	n/a	else {
3133	n/a	if (Py_SIZE(b) < 0)
3134	n/a	z = x_sub(a, b);
3135	n/a	else
3136	n/a	z = x_add(a, b);
3137	n/a	}
3138	n/a	return (PyObject *)z;
3139	n/a	}
3140	n/a
3141	n/a	static PyObject *
3142	n/a	long_sub(PyLongObject a, PyLongObject b)
3143	n/a	{
3144	n/a	PyLongObject *z;
3145	n/a
3146	n/a	CHECK_BINOP(a, b);
3147	n/a
3148	n/a	if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3149	n/a	return PyLong_FromLong(MEDIUM_VALUE(a) - MEDIUM_VALUE(b));
3150	n/a	}
3151	n/a	if (Py_SIZE(a) < 0) {
3152	n/a	if (Py_SIZE(b) < 0)
3153	n/a	z = x_sub(a, b);
3154	n/a	else
3155	n/a	z = x_add(a, b);
3156	n/a	if (z != NULL) {
3157	n/a	assert(Py_SIZE(z) == 0 \|\| Py_REFCNT(z) == 1);
3158	n/a	Py_SIZE(z) = -(Py_SIZE(z));
3159	n/a	}
3160	n/a	}
3161	n/a	else {
3162	n/a	if (Py_SIZE(b) < 0)
3163	n/a	z = x_add(a, b);
3164	n/a	else
3165	n/a	z = x_sub(a, b);
3166	n/a	}
3167	n/a	return (PyObject *)z;
3168	n/a	}
3169	n/a
3170	n/a	/* Grade school multiplication, ignoring the signs.
3171	n/a	* Returns the absolute value of the product, or NULL if error.
3172	n/a	*/
3173	n/a	static PyLongObject *
3174	n/a	x_mul(PyLongObject a, PyLongObject b)
3175	n/a	{
3176	n/a	PyLongObject *z;
3177	n/a	Py_ssize_t size_a = Py_ABS(Py_SIZE(a));
3178	n/a	Py_ssize_t size_b = Py_ABS(Py_SIZE(b));
3179	n/a	Py_ssize_t i;
3180	n/a
3181	n/a	z = _PyLong_New(size_a + size_b);
3182	n/a	if (z == NULL)
3183	n/a	return NULL;
3184	n/a
3185	n/a	memset(z->ob_digit, 0, Py_SIZE(z) * sizeof(digit));
3186	n/a	if (a == b) {
3187	n/a	/* Efficient squaring per HAC, Algorithm 14.16:
3188	n/a	* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
3189	n/a	* Gives slightly less than a 2x speedup when a == b,
3190	n/a	* via exploiting that each entry in the multiplication
3191	n/a	* pyramid appears twice (except for the size_a squares).
3192	n/a	*/
3193	n/a	for (i = 0; i < size_a; ++i) {
3194	n/a	twodigits carry;
3195	n/a	twodigits f = a->ob_digit[i];
3196	n/a	digit *pz = z->ob_digit + (i << 1);
3197	n/a	digit *pa = a->ob_digit + i + 1;
3198	n/a	digit *paend = a->ob_digit + size_a;
3199	n/a
3200	n/a	SIGCHECK({
3201	n/a	Py_DECREF(z);
3202	n/a	return NULL;
3203	n/a	});
3204	n/a
3205	n/a	carry = pz + f f;
3206	n/a	*pz++ = (digit)(carry & PyLong_MASK);
3207	n/a	carry >>= PyLong_SHIFT;
3208	n/a	assert(carry <= PyLong_MASK);
3209	n/a
3210	n/a	/* Now f is added in twice in each column of the
3211	n/a	* pyramid it appears. Same as adding f<<1 once.
3212	n/a	*/
3213	n/a	f <<= 1;
3214	n/a	while (pa < paend) {
3215	n/a	carry += pz + pa++ * f;
3216	n/a	*pz++ = (digit)(carry & PyLong_MASK);
3217	n/a	carry >>= PyLong_SHIFT;
3218	n/a	assert(carry <= (PyLong_MASK << 1));
3219	n/a	}
3220	n/a	if (carry) {
3221	n/a	carry += *pz;
3222	n/a	*pz++ = (digit)(carry & PyLong_MASK);
3223	n/a	carry >>= PyLong_SHIFT;
3224	n/a	}
3225	n/a	if (carry)
3226	n/a	*pz += (digit)(carry & PyLong_MASK);
3227	n/a	assert((carry >> PyLong_SHIFT) == 0);
3228	n/a	}
3229	n/a	}
3230	n/a	else { /* a is not the same as b -- gradeschool int mult */
3231	n/a	for (i = 0; i < size_a; ++i) {
3232	n/a	twodigits carry = 0;
3233	n/a	twodigits f = a->ob_digit[i];
3234	n/a	digit *pz = z->ob_digit + i;
3235	n/a	digit *pb = b->ob_digit;
3236	n/a	digit *pbend = b->ob_digit + size_b;
3237	n/a
3238	n/a	SIGCHECK({
3239	n/a	Py_DECREF(z);
3240	n/a	return NULL;
3241	n/a	});
3242	n/a
3243	n/a	while (pb < pbend) {
3244	n/a	carry += pz + pb++ * f;
3245	n/a	*pz++ = (digit)(carry & PyLong_MASK);
3246	n/a	carry >>= PyLong_SHIFT;
3247	n/a	assert(carry <= PyLong_MASK);
3248	n/a	}
3249	n/a	if (carry)
3250	n/a	*pz += (digit)(carry & PyLong_MASK);
3251	n/a	assert((carry >> PyLong_SHIFT) == 0);
3252	n/a	}
3253	n/a	}
3254	n/a	return long_normalize(z);
3255	n/a	}
3256	n/a
3257	n/a	/* A helper for Karatsuba multiplication (k_mul).
3258	n/a	Takes an int "n" and an integer "size" representing the place to
3259	n/a	split, and sets low and high such that abs(n) == (high << size) + low,
3260	n/a	viewing the shift as being by digits. The sign bit is ignored, and
3261	n/a	the return values are >= 0.
3262	n/a	Returns 0 on success, -1 on failure.
3263	n/a	*/
3264	n/a	static int
3265	n/a	kmul_split(PyLongObject *n,
3266	n/a	Py_ssize_t size,
3267	n/a	PyLongObject **high,
3268	n/a	PyLongObject **low)
3269	n/a	{
3270	n/a	PyLongObject hi, lo;
3271	n/a	Py_ssize_t size_lo, size_hi;
3272	n/a	const Py_ssize_t size_n = Py_ABS(Py_SIZE(n));
3273	n/a
3274	n/a	size_lo = Py_MIN(size_n, size);
3275	n/a	size_hi = size_n - size_lo;
3276	n/a
3277	n/a	if ((hi = _PyLong_New(size_hi)) == NULL)
3278	n/a	return -1;
3279	n/a	if ((lo = _PyLong_New(size_lo)) == NULL) {
3280	n/a	Py_DECREF(hi);
3281	n/a	return -1;
3282	n/a	}
3283	n/a
3284	n/a	memcpy(lo->ob_digit, n->ob_digit, size_lo * sizeof(digit));
3285	n/a	memcpy(hi->ob_digit, n->ob_digit + size_lo, size_hi * sizeof(digit));
3286	n/a
3287	n/a	*high = long_normalize(hi);
3288	n/a	*low = long_normalize(lo);
3289	n/a	return 0;
3290	n/a	}
3291	n/a
3292	n/a	static PyLongObject k_lopsided_mul(PyLongObject a, PyLongObject *b);
3293	n/a
3294	n/a	/* Karatsuba multiplication. Ignores the input signs, and returns the
3295	n/a	* absolute value of the product (or NULL if error).
3296	n/a	* See Knuth Vol. 2 Chapter 4.3.3 (Pp. 294-295).
3297	n/a	*/
3298	n/a	static PyLongObject *
3299	n/a	k_mul(PyLongObject a, PyLongObject b)
3300	n/a	{
3301	n/a	Py_ssize_t asize = Py_ABS(Py_SIZE(a));
3302	n/a	Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
3303	n/a	PyLongObject *ah = NULL;
3304	n/a	PyLongObject *al = NULL;
3305	n/a	PyLongObject *bh = NULL;
3306	n/a	PyLongObject *bl = NULL;
3307	n/a	PyLongObject *ret = NULL;
3308	n/a	PyLongObject t1, t2, *t3;
3309	n/a	Py_ssize_t shift; /* the number of digits we split off */
3310	n/a	Py_ssize_t i;
3311	n/a
3312	n/a	/* (ahX+al)(bhX+bl) = ahbhXX + (ahbl + albh)X + al*bl
3313	n/a	* Let k = (ah+al)(bh+bl) = ahbl + albh + ahbh + al*bl
3314	n/a	* Then the original product is
3315	n/a	* ahbhXX + (k - ahbh - albl)X + al*bl
3316	n/a	* By picking X to be a power of 2, "*X" is just shifting, and it's
3317	n/a	* been reduced to 3 multiplies on numbers half the size.
3318	n/a	*/
3319	n/a
3320	n/a	/* We want to split based on the larger number; fiddle so that b
3321	n/a	* is largest.
3322	n/a	*/
3323	n/a	if (asize > bsize) {
3324	n/a	t1 = a;
3325	n/a	a = b;
3326	n/a	b = t1;
3327	n/a
3328	n/a	i = asize;
3329	n/a	asize = bsize;
3330	n/a	bsize = i;
3331	n/a	}
3332	n/a
3333	n/a	/* Use gradeschool math when either number is too small. */
3334	n/a	i = a == b ? KARATSUBA_SQUARE_CUTOFF : KARATSUBA_CUTOFF;
3335	n/a	if (asize <= i) {
3336	n/a	if (asize == 0)
3337	n/a	return (PyLongObject *)PyLong_FromLong(0);
3338	n/a	else
3339	n/a	return x_mul(a, b);
3340	n/a	}
3341	n/a
3342	n/a	/* If a is small compared to b, splitting on b gives a degenerate
3343	n/a	* case with ah==0, and Karatsuba may be (even much) less efficient
3344	n/a	* than "grade school" then. However, we can still win, by viewing
3345	n/a	* b as a string of "big digits", each of width a->ob_size. That
3346	n/a	* leads to a sequence of balanced calls to k_mul.
3347	n/a	*/
3348	n/a	if (2 * asize <= bsize)
3349	n/a	return k_lopsided_mul(a, b);
3350	n/a
3351	n/a	/* Split a & b into hi & lo pieces. */
3352	n/a	shift = bsize >> 1;
3353	n/a	if (kmul_split(a, shift, &ah, &al) < 0) goto fail;
3354	n/a	assert(Py_SIZE(ah) > 0); /* the split isn't degenerate */
3355	n/a
3356	n/a	if (a == b) {
3357	n/a	bh = ah;
3358	n/a	bl = al;
3359	n/a	Py_INCREF(bh);
3360	n/a	Py_INCREF(bl);
3361	n/a	}
3362	n/a	else if (kmul_split(b, shift, &bh, &bl) < 0) goto fail;
3363	n/a
3364	n/a	/* The plan:
3365	n/a	* 1. Allocate result space (asize + bsize digits: that's always
3366	n/a	* enough).
3367	n/a	* 2. Compute ahbh, and copy into result at 2shift.
3368	n/a	* 3. Compute al*bl, and copy into result at 0. Note that this
3369	n/a	* can't overlap with #2.
3370	n/a	* 4. Subtract al*bl from the result, starting at shift. This may
3371	n/a	* underflow (borrow out of the high digit), but we don't care:
3372	n/a	* we're effectively doing unsigned arithmetic mod
3373	n/a	* BASE*(sizea + sizeb), and so long as the final* result fits,
3374	n/a	* borrows and carries out of the high digit can be ignored.
3375	n/a	* 5. Subtract ah*bh from the result, starting at shift.
3376	n/a	* 6. Compute (ah+al)*(bh+bl), and add it into the result starting
3377	n/a	* at shift.
3378	n/a	*/
3379	n/a
3380	n/a	/* 1. Allocate result space. */
3381	n/a	ret = _PyLong_New(asize + bsize);
3382	n/a	if (ret == NULL) goto fail;
3383	n/a	#ifdef Py_DEBUG
3384	n/a	/* Fill with trash, to catch reference to uninitialized digits. */
3385	n/a	memset(ret->ob_digit, 0xDF, Py_SIZE(ret) * sizeof(digit));
3386	n/a	#endif
3387	n/a
3388	n/a	/* 2. t1 <- ahbh, and copy into high digits of result. /
3389	n/a	if ((t1 = k_mul(ah, bh)) == NULL) goto fail;
3390	n/a	assert(Py_SIZE(t1) >= 0);
3391	n/a	assert(2*shift + Py_SIZE(t1) <= Py_SIZE(ret));
3392	n/a	memcpy(ret->ob_digit + 2*shift, t1->ob_digit,
3393	n/a	Py_SIZE(t1) * sizeof(digit));
3394	n/a
3395	n/a	/* Zero-out the digits higher than the ahbh copy. /
3396	n/a	i = Py_SIZE(ret) - 2*shift - Py_SIZE(t1);
3397	n/a	if (i)
3398	n/a	memset(ret->ob_digit + 2*shift + Py_SIZE(t1), 0,
3399	n/a	i * sizeof(digit));
3400	n/a
3401	n/a	/* 3. t2 <- albl, and copy into the low digits. /
3402	n/a	if ((t2 = k_mul(al, bl)) == NULL) {
3403	n/a	Py_DECREF(t1);
3404	n/a	goto fail;
3405	n/a	}
3406	n/a	assert(Py_SIZE(t2) >= 0);
3407	n/a	assert(Py_SIZE(t2) <= 2shift); / no overlap with high digits */
3408	n/a	memcpy(ret->ob_digit, t2->ob_digit, Py_SIZE(t2) * sizeof(digit));
3409	n/a
3410	n/a	/* Zero out remaining digits. */
3411	n/a	i = 2shift - Py_SIZE(t2); / number of uninitialized digits */
3412	n/a	if (i)
3413	n/a	memset(ret->ob_digit + Py_SIZE(t2), 0, i * sizeof(digit));
3414	n/a
3415	n/a	/* 4 & 5. Subtract ahbh (t1) and albl (t2). We do al*bl first
3416	n/a	* because it's fresher in cache.
3417	n/a	*/
3418	n/a	i = Py_SIZE(ret) - shift; /* # digits after shift */
3419	n/a	(void)v_isub(ret->ob_digit + shift, i, t2->ob_digit, Py_SIZE(t2));
3420	n/a	Py_DECREF(t2);
3421	n/a
3422	n/a	(void)v_isub(ret->ob_digit + shift, i, t1->ob_digit, Py_SIZE(t1));
3423	n/a	Py_DECREF(t1);
3424	n/a
3425	n/a	/* 6. t3 <- (ah+al)(bh+bl), and add into result. */
3426	n/a	if ((t1 = x_add(ah, al)) == NULL) goto fail;
3427	n/a	Py_DECREF(ah);
3428	n/a	Py_DECREF(al);
3429	n/a	ah = al = NULL;
3430	n/a
3431	n/a	if (a == b) {
3432	n/a	t2 = t1;
3433	n/a	Py_INCREF(t2);
3434	n/a	}
3435	n/a	else if ((t2 = x_add(bh, bl)) == NULL) {
3436	n/a	Py_DECREF(t1);
3437	n/a	goto fail;
3438	n/a	}
3439	n/a	Py_DECREF(bh);
3440	n/a	Py_DECREF(bl);
3441	n/a	bh = bl = NULL;
3442	n/a
3443	n/a	t3 = k_mul(t1, t2);
3444	n/a	Py_DECREF(t1);
3445	n/a	Py_DECREF(t2);
3446	n/a	if (t3 == NULL) goto fail;
3447	n/a	assert(Py_SIZE(t3) >= 0);
3448	n/a
3449	n/a	/* Add t3. It's not obvious why we can't run out of room here.
3450	n/a	* See the (*) comment after this function.
3451	n/a	*/
3452	n/a	(void)v_iadd(ret->ob_digit + shift, i, t3->ob_digit, Py_SIZE(t3));
3453	n/a	Py_DECREF(t3);
3454	n/a
3455	n/a	return long_normalize(ret);
3456	n/a
3457	n/a	fail:
3458	n/a	Py_XDECREF(ret);
3459	n/a	Py_XDECREF(ah);
3460	n/a	Py_XDECREF(al);
3461	n/a	Py_XDECREF(bh);
3462	n/a	Py_XDECREF(bl);
3463	n/a	return NULL;
3464	n/a	}
3465	n/a
3466	n/a	/* (*) Why adding t3 can't "run out of room" above.
3467	n/a
3468	n/a	Let f(x) mean the floor of x and c(x) mean the ceiling of x. Some facts
3469	n/a	to start with:
3470	n/a
3471	n/a	1. For any integer i, i = c(i/2) + f(i/2). In particular,
3472	n/a	bsize = c(bsize/2) + f(bsize/2).
3473	n/a	2. shift = f(bsize/2)
3474	n/a	3. asize <= bsize
3475	n/a	4. Since we call k_lopsided_mul if asize2 <= bsize, asize2 > bsize in this
3476	n/a	routine, so asize > bsize/2 >= f(bsize/2) in this routine.
3477	n/a
3478	n/a	We allocated asize + bsize result digits, and add t3 into them at an offset
3479	n/a	of shift. This leaves asize+bsize-shift allocated digit positions for t3
3480	n/a	to fit into, = (by #1 and #2) asize + f(bsize/2) + c(bsize/2) - f(bsize/2) =
3481	n/a	asize + c(bsize/2) available digit positions.
3482	n/a
3483	n/a	bh has c(bsize/2) digits, and bl at most f(size/2) digits. So bh+hl has
3484	n/a	at most c(bsize/2) digits + 1 bit.
3485	n/a
3486	n/a	If asize == bsize, ah has c(bsize/2) digits, else ah has at most f(bsize/2)
3487	n/a	digits, and al has at most f(bsize/2) digits in any case. So ah+al has at
3488	n/a	most (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 1 bit.
3489	n/a
3490	n/a	The product (ah+al)*(bh+bl) therefore has at most
3491	n/a
3492	n/a	c(bsize/2) + (asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits
3493	n/a
3494	n/a	and we have asize + c(bsize/2) available digit positions. We need to show
3495	n/a	this is always enough. An instance of c(bsize/2) cancels out in both, so
3496	n/a	the question reduces to whether asize digits is enough to hold
3497	n/a	(asize == bsize ? c(bsize/2) : f(bsize/2)) digits + 2 bits. If asize < bsize,
3498	n/a	then we're asking whether asize digits >= f(bsize/2) digits + 2 bits. By #4,
3499	n/a	asize is at least f(bsize/2)+1 digits, so this in turn reduces to whether 1
3500	n/a	digit is enough to hold 2 bits. This is so since PyLong_SHIFT=15 >= 2. If
3501	n/a	asize == bsize, then we're asking whether bsize digits is enough to hold
3502	n/a	c(bsize/2) digits + 2 bits, or equivalently (by #1) whether f(bsize/2) digits
3503	n/a	is enough to hold 2 bits. This is so if bsize >= 2, which holds because
3504	n/a	bsize >= KARATSUBA_CUTOFF >= 2.
3505	n/a
3506	n/a	Note that since there's always enough room for (ah+al)*(bh+bl), and that's
3507	n/a	clearly >= each of ahbh and albl, there's always enough room to subtract
3508	n/a	ahbh and albl too.
3509	n/a	*/
3510	n/a
3511	n/a	/* b has at least twice the digits of a, and a is big enough that Karatsuba
3512	n/a	* would pay off if the inputs had balanced sizes. View b as a sequence
3513	n/a	* of slices, each with a->ob_size digits, and multiply the slices by a,
3514	n/a	* one at a time. This gives k_mul balanced inputs to work with, and is
3515	n/a	* also cache-friendly (we compute one double-width slice of the result
3516	n/a	* at a time, then move on, never backtracking except for the helpful
3517	n/a	* single-width slice overlap between successive partial sums).
3518	n/a	*/
3519	n/a	static PyLongObject *
3520	n/a	k_lopsided_mul(PyLongObject a, PyLongObject b)
3521	n/a	{
3522	n/a	const Py_ssize_t asize = Py_ABS(Py_SIZE(a));
3523	n/a	Py_ssize_t bsize = Py_ABS(Py_SIZE(b));
3524	n/a	Py_ssize_t nbdone; /* # of b digits already multiplied */
3525	n/a	PyLongObject *ret;
3526	n/a	PyLongObject *bslice = NULL;
3527	n/a
3528	n/a	assert(asize > KARATSUBA_CUTOFF);
3529	n/a	assert(2 * asize <= bsize);
3530	n/a
3531	n/a	/* Allocate result space, and zero it out. */
3532	n/a	ret = _PyLong_New(asize + bsize);
3533	n/a	if (ret == NULL)
3534	n/a	return NULL;
3535	n/a	memset(ret->ob_digit, 0, Py_SIZE(ret) * sizeof(digit));
3536	n/a
3537	n/a	/* Successive slices of b are copied into bslice. */
3538	n/a	bslice = _PyLong_New(asize);
3539	n/a	if (bslice == NULL)
3540	n/a	goto fail;
3541	n/a
3542	n/a	nbdone = 0;
3543	n/a	while (bsize > 0) {
3544	n/a	PyLongObject *product;
3545	n/a	const Py_ssize_t nbtouse = Py_MIN(bsize, asize);
3546	n/a
3547	n/a	/* Multiply the next slice of b by a. */
3548	n/a	memcpy(bslice->ob_digit, b->ob_digit + nbdone,
3549	n/a	nbtouse * sizeof(digit));
3550	n/a	Py_SIZE(bslice) = nbtouse;
3551	n/a	product = k_mul(a, bslice);
3552	n/a	if (product == NULL)
3553	n/a	goto fail;
3554	n/a
3555	n/a	/* Add into result. */
3556	n/a	(void)v_iadd(ret->ob_digit + nbdone, Py_SIZE(ret) - nbdone,
3557	n/a	product->ob_digit, Py_SIZE(product));
3558	n/a	Py_DECREF(product);
3559	n/a
3560	n/a	bsize -= nbtouse;
3561	n/a	nbdone += nbtouse;
3562	n/a	}
3563	n/a
3564	n/a	Py_DECREF(bslice);
3565	n/a	return long_normalize(ret);
3566	n/a
3567	n/a	fail:
3568	n/a	Py_DECREF(ret);
3569	n/a	Py_XDECREF(bslice);
3570	n/a	return NULL;
3571	n/a	}
3572	n/a
3573	n/a	static PyObject *
3574	n/a	long_mul(PyLongObject a, PyLongObject b)
3575	n/a	{
3576	n/a	PyLongObject *z;
3577	n/a
3578	n/a	CHECK_BINOP(a, b);
3579	n/a
3580	n/a	/* fast path for single-digit multiplication */
3581	n/a	if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
3582	n/a	stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
3583	n/a	return PyLong_FromLongLong((long long)v);
3584	n/a	}
3585	n/a
3586	n/a	z = k_mul(a, b);
3587	n/a	/* Negate if exactly one of the inputs is negative. */
3588	n/a	if (((Py_SIZE(a) ^ Py_SIZE(b)) < 0) && z) {
3589	n/a	_PyLong_Negate(&z);
3590	n/a	if (z == NULL)
3591	n/a	return NULL;
3592	n/a	}
3593	n/a	return (PyObject *)z;
3594	n/a	}
3595	n/a
3596	n/a	/* Fast modulo division for single-digit longs. */
3597	n/a	static PyObject *
3598	n/a	fast_mod(PyLongObject a, PyLongObject b)
3599	n/a	{
3600	n/a	sdigit left = a->ob_digit[0];
3601	n/a	sdigit right = b->ob_digit[0];
3602	n/a	sdigit mod;
3603	n/a
3604	n/a	assert(Py_ABS(Py_SIZE(a)) == 1);
3605	n/a	assert(Py_ABS(Py_SIZE(b)) == 1);
3606	n/a
3607	n/a	if (Py_SIZE(a) == Py_SIZE(b)) {
3608	n/a	/* 'a' and 'b' have the same sign. */
3609	n/a	mod = left % right;
3610	n/a	}
3611	n/a	else {
3612	n/a	/* Either 'a' or 'b' is negative. */
3613	n/a	mod = right - 1 - (left - 1) % right;
3614	n/a	}
3615	n/a
3616	n/a	return PyLong_FromLong(mod * (sdigit)Py_SIZE(b));
3617	n/a	}
3618	n/a
3619	n/a	/* Fast floor division for single-digit longs. */
3620	n/a	static PyObject *
3621	n/a	fast_floor_div(PyLongObject a, PyLongObject b)
3622	n/a	{
3623	n/a	sdigit left = a->ob_digit[0];
3624	n/a	sdigit right = b->ob_digit[0];
3625	n/a	sdigit div;
3626	n/a
3627	n/a	assert(Py_ABS(Py_SIZE(a)) == 1);
3628	n/a	assert(Py_ABS(Py_SIZE(b)) == 1);
3629	n/a
3630	n/a	if (Py_SIZE(a) == Py_SIZE(b)) {
3631	n/a	/* 'a' and 'b' have the same sign. */
3632	n/a	div = left / right;
3633	n/a	}
3634	n/a	else {
3635	n/a	/* Either 'a' or 'b' is negative. */
3636	n/a	div = -1 - (left - 1) / right;
3637	n/a	}
3638	n/a
3639	n/a	return PyLong_FromLong(div);
3640	n/a	}
3641	n/a
3642	n/a	/* The / and % operators are now defined in terms of divmod().
3643	n/a	The expression a mod b has the value a - b*floor(a/b).
3644	n/a	The long_divrem function gives the remainder after division of
3645	n/a	\|a\| by \|b\|, with the sign of a. This is also expressed
3646	n/a	as a - b*trunc(a/b), if trunc truncates towards zero.
3647	n/a	Some examples:
3648	n/a	a b a rem b a mod b
3649	n/a	13 10 3 3
3650	n/a	-13 10 -3 7
3651	n/a	13 -10 3 -7
3652	n/a	-13 -10 -3 -3
3653	n/a	So, to get from rem to mod, we have to add b if a and b
3654	n/a	have different signs. We then subtract one from the 'div'
3655	n/a	part of the outcome to keep the invariant intact. */
3656	n/a
3657	n/a	/* Compute
3658	n/a	* pdiv, pmod = divmod(v, w)
3659	n/a	* NULL can be passed for pdiv or pmod, in which case that part of
3660	n/a	* the result is simply thrown away. The caller owns a reference to
3661	n/a	* each of these it requests (does not pass NULL for).
3662	n/a	*/
3663	n/a	static int
3664	n/a	l_divmod(PyLongObject v, PyLongObject w,
3665	n/a	PyLongObject pdiv, PyLongObject pmod)
3666	n/a	{
3667	n/a	PyLongObject div, mod;
3668	n/a
3669	n/a	if (Py_ABS(Py_SIZE(v)) == 1 && Py_ABS(Py_SIZE(w)) == 1) {
3670	n/a	/* Fast path for single-digit longs */
3671	n/a	div = NULL;
3672	n/a	if (pdiv != NULL) {
3673	n/a	div = (PyLongObject *)fast_floor_div(v, w);
3674	n/a	if (div == NULL) {
3675	n/a	return -1;
3676	n/a	}
3677	n/a	}
3678	n/a	if (pmod != NULL) {
3679	n/a	mod = (PyLongObject *)fast_mod(v, w);
3680	n/a	if (mod == NULL) {
3681	n/a	Py_XDECREF(div);
3682	n/a	return -1;
3683	n/a	}
3684	n/a	*pmod = mod;
3685	n/a	}
3686	n/a	if (pdiv != NULL) {
3687	n/a	/* We only want to set `pdiv` when `pmod` is
3688	n/a	set successfully. */
3689	n/a	*pdiv = div;
3690	n/a	}
3691	n/a	return 0;
3692	n/a	}
3693	n/a	if (long_divrem(v, w, &div, &mod) < 0)
3694	n/a	return -1;
3695	n/a	if ((Py_SIZE(mod) < 0 && Py_SIZE(w) > 0) \|\|
3696	n/a	(Py_SIZE(mod) > 0 && Py_SIZE(w) < 0)) {
3697	n/a	PyLongObject *temp;
3698	n/a	PyLongObject *one;
3699	n/a	temp = (PyLongObject *) long_add(mod, w);
3700	n/a	Py_DECREF(mod);
3701	n/a	mod = temp;
3702	n/a	if (mod == NULL) {
3703	n/a	Py_DECREF(div);
3704	n/a	return -1;
3705	n/a	}
3706	n/a	one = (PyLongObject *) PyLong_FromLong(1L);
3707	n/a	if (one == NULL \|\|
3708	n/a	(temp = (PyLongObject *) long_sub(div, one)) == NULL) {
3709	n/a	Py_DECREF(mod);
3710	n/a	Py_DECREF(div);
3711	n/a	Py_XDECREF(one);
3712	n/a	return -1;
3713	n/a	}
3714	n/a	Py_DECREF(one);
3715	n/a	Py_DECREF(div);
3716	n/a	div = temp;
3717	n/a	}
3718	n/a	if (pdiv != NULL)
3719	n/a	*pdiv = div;
3720	n/a	else
3721	n/a	Py_DECREF(div);
3722	n/a
3723	n/a	if (pmod != NULL)
3724	n/a	*pmod = mod;
3725	n/a	else
3726	n/a	Py_DECREF(mod);
3727	n/a
3728	n/a	return 0;
3729	n/a	}
3730	n/a
3731	n/a	static PyObject *
3732	n/a	long_div(PyObject a, PyObject b)
3733	n/a	{
3734	n/a	PyLongObject *div;
3735	n/a
3736	n/a	CHECK_BINOP(a, b);
3737	n/a
3738	n/a	if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
3739	n/a	return fast_floor_div((PyLongObject)a, (PyLongObject)b);
3740	n/a	}
3741	n/a
3742	n/a	if (l_divmod((PyLongObject)a, (PyLongObject)b, &div, NULL) < 0)
3743	n/a	div = NULL;
3744	n/a	return (PyObject *)div;
3745	n/a	}
3746	n/a
3747	n/a	/* PyLong/PyLong -> float, with correctly rounded result. */
3748	n/a
3749	n/a	#define MANT_DIG_DIGITS (DBL_MANT_DIG / PyLong_SHIFT)
3750	n/a	#define MANT_DIG_BITS (DBL_MANT_DIG % PyLong_SHIFT)
3751	n/a
3752	n/a	static PyObject *
3753	n/a	long_true_divide(PyObject v, PyObject w)
3754	n/a	{
3755	n/a	PyLongObject a, b, *x;
3756	n/a	Py_ssize_t a_size, b_size, shift, extra_bits, diff, x_size, x_bits;
3757	n/a	digit mask, low;
3758	n/a	int inexact, negate, a_is_small, b_is_small;
3759	n/a	double dx, result;
3760	n/a
3761	n/a	CHECK_BINOP(v, w);
3762	n/a	a = (PyLongObject *)v;
3763	n/a	b = (PyLongObject *)w;
3764	n/a
3765	n/a	/*
3766	n/a	Method in a nutshell:
3767	n/a
3768	n/a	0. reduce to case a, b > 0; filter out obvious underflow/overflow
3769	n/a	1. choose a suitable integer 'shift'
3770	n/a	2. use integer arithmetic to compute x = floor(2*-shifta/b)
3771	n/a	3. adjust x for correct rounding
3772	n/a	4. convert x to a double dx with the same value
3773	n/a	5. return ldexp(dx, shift).
3774	n/a
3775	n/a	In more detail:
3776	n/a
3777	n/a	0. For any a, a/0 raises ZeroDivisionError; for nonzero b, 0/b
3778	n/a	returns either 0.0 or -0.0, depending on the sign of b. For a and
3779	n/a	b both nonzero, ignore signs of a and b, and add the sign back in
3780	n/a	at the end. Now write a_bits and b_bits for the bit lengths of a
3781	n/a	and b respectively (that is, a_bits = 1 + floor(log_2(a)); likewise
3782	n/a	for b). Then
3783	n/a
3784	n/a	2(a_bits - b_bits - 1) < a/b < 2(a_bits - b_bits + 1).
3785	n/a
3786	n/a	So if a_bits - b_bits > DBL_MAX_EXP then a/b > 2**DBL_MAX_EXP and
3787	n/a	so overflows. Similarly, if a_bits - b_bits < DBL_MIN_EXP -
3788	n/a	DBL_MANT_DIG - 1 then a/b underflows to 0. With these cases out of
3789	n/a	the way, we can assume that
3790	n/a
3791	n/a	DBL_MIN_EXP - DBL_MANT_DIG - 1 <= a_bits - b_bits <= DBL_MAX_EXP.
3792	n/a
3793	n/a	1. The integer 'shift' is chosen so that x has the right number of
3794	n/a	bits for a double, plus two or three extra bits that will be used
3795	n/a	in the rounding decisions. Writing a_bits and b_bits for the
3796	n/a	number of significant bits in a and b respectively, a
3797	n/a	straightforward formula for shift is:
3798	n/a
3799	n/a	shift = a_bits - b_bits - DBL_MANT_DIG - 2
3800	n/a
3801	n/a	This is fine in the usual case, but if a/b is smaller than the
3802	n/a	smallest normal float then it can lead to double rounding on an
3803	n/a	IEEE 754 platform, giving incorrectly rounded results. So we
3804	n/a	adjust the formula slightly. The actual formula used is:
3805	n/a
3806	n/a	shift = MAX(a_bits - b_bits, DBL_MIN_EXP) - DBL_MANT_DIG - 2
3807	n/a
3808	n/a	2. The quantity x is computed by first shifting a (left -shift bits
3809	n/a	if shift <= 0, right shift bits if shift > 0) and then dividing by
3810	n/a	b. For both the shift and the division, we keep track of whether
3811	n/a	the result is inexact, in a flag 'inexact'; this information is
3812	n/a	needed at the rounding stage.
3813	n/a
3814	n/a	With the choice of shift above, together with our assumption that
3815	n/a	a_bits - b_bits >= DBL_MIN_EXP - DBL_MANT_DIG - 1, it follows
3816	n/a	that x >= 1.
3817	n/a
3818	n/a	3. Now x * 2*shift <= a/b < (x+1) 2**shift. We want to replace
3819	n/a	this with an exactly representable float of the form
3820	n/a
3821	n/a	round(x/2*extra_bits) 2**(extra_bits+shift).
3822	n/a
3823	n/a	For float representability, we need x/2**extra_bits <
3824	n/a	2**DBL_MANT_DIG and extra_bits + shift >= DBL_MIN_EXP -
3825	n/a	DBL_MANT_DIG. This translates to the condition:
3826	n/a
3827	n/a	extra_bits >= MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG
3828	n/a
3829	n/a	To round, we just modify the bottom digit of x in-place; this can
3830	n/a	end up giving a digit with value > PyLONG_MASK, but that's not a
3831	n/a	problem since digits can hold values up to 2*PyLONG_MASK+1.
3832	n/a
3833	n/a	With the original choices for shift above, extra_bits will always
3834	n/a	be 2 or 3. Then rounding under the round-half-to-even rule, we
3835	n/a	round up iff the most significant of the extra bits is 1, and
3836	n/a	either: (a) the computation of x in step 2 had an inexact result,
3837	n/a	or (b) at least one other of the extra bits is 1, or (c) the least
3838	n/a	significant bit of x (above those to be rounded) is 1.
3839	n/a
3840	n/a	4. Conversion to a double is straightforward; all floating-point
3841	n/a	operations involved in the conversion are exact, so there's no
3842	n/a	danger of rounding errors.
3843	n/a
3844	n/a	5. Use ldexp(x, shift) to compute x2*shift, the final result.
3845	n/a	The result will always be exactly representable as a double, except
3846	n/a	in the case that it overflows. To avoid dependence on the exact
3847	n/a	behaviour of ldexp on overflow, we check for overflow before
3848	n/a	applying ldexp. The result of ldexp is adjusted for sign before
3849	n/a	returning.
3850	n/a	*/
3851	n/a
3852	n/a	/* Reduce to case where a and b are both positive. */
3853	n/a	a_size = Py_ABS(Py_SIZE(a));
3854	n/a	b_size = Py_ABS(Py_SIZE(b));
3855	n/a	negate = (Py_SIZE(a) < 0) ^ (Py_SIZE(b) < 0);
3856	n/a	if (b_size == 0) {
3857	n/a	PyErr_SetString(PyExc_ZeroDivisionError,
3858	n/a	"division by zero");
3859	n/a	goto error;
3860	n/a	}
3861	n/a	if (a_size == 0)
3862	n/a	goto underflow_or_zero;
3863	n/a
3864	n/a	/* Fast path for a and b small (exactly representable in a double).
3865	n/a	Relies on floating-point division being correctly rounded; results
3866	n/a	may be subject to double rounding on x86 machines that operate with
3867	n/a	the x87 FPU set to 64-bit precision. */
3868	n/a	a_is_small = a_size <= MANT_DIG_DIGITS \|\|
3869	n/a	(a_size == MANT_DIG_DIGITS+1 &&
3870	n/a	a->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3871	n/a	b_is_small = b_size <= MANT_DIG_DIGITS \|\|
3872	n/a	(b_size == MANT_DIG_DIGITS+1 &&
3873	n/a	b->ob_digit[MANT_DIG_DIGITS] >> MANT_DIG_BITS == 0);
3874	n/a	if (a_is_small && b_is_small) {
3875	n/a	double da, db;
3876	n/a	da = a->ob_digit[--a_size];
3877	n/a	while (a_size > 0)
3878	n/a	da = da * PyLong_BASE + a->ob_digit[--a_size];
3879	n/a	db = b->ob_digit[--b_size];
3880	n/a	while (b_size > 0)
3881	n/a	db = db * PyLong_BASE + b->ob_digit[--b_size];
3882	n/a	result = da / db;
3883	n/a	goto success;
3884	n/a	}
3885	n/a
3886	n/a	/* Catch obvious cases of underflow and overflow */
3887	n/a	diff = a_size - b_size;
3888	n/a	if (diff > PY_SSIZE_T_MAX/PyLong_SHIFT - 1)
3889	n/a	/* Extreme overflow */
3890	n/a	goto overflow;
3891	n/a	else if (diff < 1 - PY_SSIZE_T_MAX/PyLong_SHIFT)
3892	n/a	/* Extreme underflow */
3893	n/a	goto underflow_or_zero;
3894	n/a	/* Next line is now safe from overflowing a Py_ssize_t */
3895	n/a	diff = diff * PyLong_SHIFT + bits_in_digit(a->ob_digit[a_size - 1]) -
3896	n/a	bits_in_digit(b->ob_digit[b_size - 1]);
3897	n/a	/* Now diff = a_bits - b_bits. */
3898	n/a	if (diff > DBL_MAX_EXP)
3899	n/a	goto overflow;
3900	n/a	else if (diff < DBL_MIN_EXP - DBL_MANT_DIG - 1)
3901	n/a	goto underflow_or_zero;
3902	n/a
3903	n/a	/* Choose value for shift; see comments for step 1 above. */
3904	n/a	shift = Py_MAX(diff, DBL_MIN_EXP) - DBL_MANT_DIG - 2;
3905	n/a
3906	n/a	inexact = 0;
3907	n/a
3908	n/a	/* x = abs(a * 2*-shift) /
3909	n/a	if (shift <= 0) {
3910	n/a	Py_ssize_t i, shift_digits = -shift / PyLong_SHIFT;
3911	n/a	digit rem;
3912	n/a	/* x = a << -shift */
3913	n/a	if (a_size >= PY_SSIZE_T_MAX - 1 - shift_digits) {
3914	n/a	/* In practice, it's probably impossible to end up
3915	n/a	here. Both a and b would have to be enormous,
3916	n/a	using close to SIZE_T_MAX bytes of memory each. */
3917	n/a	PyErr_SetString(PyExc_OverflowError,
3918	n/a	"intermediate overflow during division");
3919	n/a	goto error;
3920	n/a	}
3921	n/a	x = _PyLong_New(a_size + shift_digits + 1);
3922	n/a	if (x == NULL)
3923	n/a	goto error;
3924	n/a	for (i = 0; i < shift_digits; i++)
3925	n/a	x->ob_digit[i] = 0;
3926	n/a	rem = v_lshift(x->ob_digit + shift_digits, a->ob_digit,
3927	n/a	a_size, -shift % PyLong_SHIFT);
3928	n/a	x->ob_digit[a_size + shift_digits] = rem;
3929	n/a	}
3930	n/a	else {
3931	n/a	Py_ssize_t shift_digits = shift / PyLong_SHIFT;
3932	n/a	digit rem;
3933	n/a	/* x = a >> shift */
3934	n/a	assert(a_size >= shift_digits);
3935	n/a	x = _PyLong_New(a_size - shift_digits);
3936	n/a	if (x == NULL)
3937	n/a	goto error;
3938	n/a	rem = v_rshift(x->ob_digit, a->ob_digit + shift_digits,
3939	n/a	a_size - shift_digits, shift % PyLong_SHIFT);
3940	n/a	/* set inexact if any of the bits shifted out is nonzero */
3941	n/a	if (rem)
3942	n/a	inexact = 1;
3943	n/a	while (!inexact && shift_digits > 0)
3944	n/a	if (a->ob_digit[--shift_digits])
3945	n/a	inexact = 1;
3946	n/a	}
3947	n/a	long_normalize(x);
3948	n/a	x_size = Py_SIZE(x);
3949	n/a
3950	n/a	/* x //= b. If the remainder is nonzero, set inexact. We own the only
3951	n/a	reference to x, so it's safe to modify it in-place. */
3952	n/a	if (b_size == 1) {
3953	n/a	digit rem = inplace_divrem1(x->ob_digit, x->ob_digit, x_size,
3954	n/a	b->ob_digit[0]);
3955	n/a	long_normalize(x);
3956	n/a	if (rem)
3957	n/a	inexact = 1;
3958	n/a	}
3959	n/a	else {
3960	n/a	PyLongObject div, rem;
3961	n/a	div = x_divrem(x, b, &rem);
3962	n/a	Py_DECREF(x);
3963	n/a	x = div;
3964	n/a	if (x == NULL)
3965	n/a	goto error;
3966	n/a	if (Py_SIZE(rem))
3967	n/a	inexact = 1;
3968	n/a	Py_DECREF(rem);
3969	n/a	}
3970	n/a	x_size = Py_ABS(Py_SIZE(x));
3971	n/a	assert(x_size > 0); /* result of division is never zero */
3972	n/a	x_bits = (x_size-1)*PyLong_SHIFT+bits_in_digit(x->ob_digit[x_size-1]);
3973	n/a
3974	n/a	/* The number of extra bits that have to be rounded away. */
3975	n/a	extra_bits = Py_MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
3976	n/a	assert(extra_bits == 2 \|\| extra_bits == 3);
3977	n/a
3978	n/a	/* Round by directly modifying the low digit of x. */
3979	n/a	mask = (digit)1 << (extra_bits - 1);
3980	n/a	low = x->ob_digit[0] \| inexact;
3981	n/a	if ((low & mask) && (low & (3U*mask-1U)))
3982	n/a	low += mask;
3983	n/a	x->ob_digit[0] = low & ~(2U*mask-1U);
3984	n/a
3985	n/a	/* Convert x to a double dx; the conversion is exact. */
3986	n/a	dx = x->ob_digit[--x_size];
3987	n/a	while (x_size > 0)
3988	n/a	dx = dx * PyLong_BASE + x->ob_digit[--x_size];
3989	n/a	Py_DECREF(x);
3990	n/a
3991	n/a	/* Check whether ldexp result will overflow a double. */
3992	n/a	if (shift + x_bits >= DBL_MAX_EXP &&
3993	n/a	(shift + x_bits > DBL_MAX_EXP \|\| dx == ldexp(1.0, (int)x_bits)))
3994	n/a	goto overflow;
3995	n/a	result = ldexp(dx, (int)shift);
3996	n/a
3997	n/a	success:
3998	n/a	return PyFloat_FromDouble(negate ? -result : result);
3999	n/a
4000	n/a	underflow_or_zero:
4001	n/a	return PyFloat_FromDouble(negate ? -0.0 : 0.0);
4002	n/a
4003	n/a	overflow:
4004	n/a	PyErr_SetString(PyExc_OverflowError,
4005	n/a	"integer division result too large for a float");
4006	n/a	error:
4007	n/a	return NULL;
4008	n/a	}
4009	n/a
4010	n/a	static PyObject *
4011	n/a	long_mod(PyObject a, PyObject b)
4012	n/a	{
4013	n/a	PyLongObject *mod;
4014	n/a
4015	n/a	CHECK_BINOP(a, b);
4016	n/a
4017	n/a	if (Py_ABS(Py_SIZE(a)) == 1 && Py_ABS(Py_SIZE(b)) == 1) {
4018	n/a	return fast_mod((PyLongObject)a, (PyLongObject)b);
4019	n/a	}
4020	n/a
4021	n/a	if (l_divmod((PyLongObject)a, (PyLongObject)b, NULL, &mod) < 0)
4022	n/a	mod = NULL;
4023	n/a	return (PyObject *)mod;
4024	n/a	}
4025	n/a
4026	n/a	static PyObject *
4027	n/a	long_divmod(PyObject a, PyObject b)
4028	n/a	{
4029	n/a	PyLongObject div, mod;
4030	n/a	PyObject *z;
4031	n/a
4032	n/a	CHECK_BINOP(a, b);
4033	n/a
4034	n/a	if (l_divmod((PyLongObject)a, (PyLongObject)b, &div, &mod) < 0) {
4035	n/a	return NULL;
4036	n/a	}
4037	n/a	z = PyTuple_New(2);
4038	n/a	if (z != NULL) {
4039	n/a	PyTuple_SetItem(z, 0, (PyObject *) div);
4040	n/a	PyTuple_SetItem(z, 1, (PyObject *) mod);
4041	n/a	}
4042	n/a	else {
4043	n/a	Py_DECREF(div);
4044	n/a	Py_DECREF(mod);
4045	n/a	}
4046	n/a	return z;
4047	n/a	}
4048	n/a
4049	n/a	/* pow(v, w, x) */
4050	n/a	static PyObject *
4051	n/a	long_pow(PyObject v, PyObject w, PyObject *x)
4052	n/a	{
4053	n/a	PyLongObject a, b, c; / a,b,c = v,w,x */
4054	n/a	int negativeOutput = 0; /* if x<0 return negative output */
4055	n/a
4056	n/a	PyLongObject z = NULL; / accumulated result */
4057	n/a	Py_ssize_t i, j, k; /* counters */
4058	n/a	PyLongObject *temp = NULL;
4059	n/a
4060	n/a	/* 5-ary values. If the exponent is large enough, table is
4061	n/a	* precomputed so that table[i] == a**i % c for i in range(32).
4062	n/a	*/
4063	n/a	PyLongObject *table[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
4064	n/a	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
4065	n/a
4066	n/a	/* a, b, c = v, w, x */
4067	n/a	CHECK_BINOP(v, w);
4068	n/a	a = (PyLongObject*)v; Py_INCREF(a);
4069	n/a	b = (PyLongObject*)w; Py_INCREF(b);
4070	n/a	if (PyLong_Check(x)) {
4071	n/a	c = (PyLongObject *)x;
4072	n/a	Py_INCREF(x);
4073	n/a	}
4074	n/a	else if (x == Py_None)
4075	n/a	c = NULL;
4076	n/a	else {
4077	n/a	Py_DECREF(a);
4078	n/a	Py_DECREF(b);
4079	n/a	Py_RETURN_NOTIMPLEMENTED;
4080	n/a	}
4081	n/a
4082	n/a	if (Py_SIZE(b) < 0) { /* if exponent is negative */
4083	n/a	if (c) {
4084	n/a	PyErr_SetString(PyExc_ValueError, "pow() 2nd argument "
4085	n/a	"cannot be negative when 3rd argument specified");
4086	n/a	goto Error;
4087	n/a	}
4088	n/a	else {
4089	n/a	/* else return a float. This works because we know
4090	n/a	that this calls float_pow() which converts its
4091	n/a	arguments to double. */
4092	n/a	Py_DECREF(a);
4093	n/a	Py_DECREF(b);
4094	n/a	return PyFloat_Type.tp_as_number->nb_power(v, w, x);
4095	n/a	}
4096	n/a	}
4097	n/a
4098	n/a	if (c) {
4099	n/a	/* if modulus == 0:
4100	n/a	raise ValueError() */
4101	n/a	if (Py_SIZE(c) == 0) {
4102	n/a	PyErr_SetString(PyExc_ValueError,
4103	n/a	"pow() 3rd argument cannot be 0");
4104	n/a	goto Error;
4105	n/a	}
4106	n/a
4107	n/a	/* if modulus < 0:
4108	n/a	negativeOutput = True
4109	n/a	modulus = -modulus */
4110	n/a	if (Py_SIZE(c) < 0) {
4111	n/a	negativeOutput = 1;
4112	n/a	temp = (PyLongObject *)_PyLong_Copy(c);
4113	n/a	if (temp == NULL)
4114	n/a	goto Error;
4115	n/a	Py_DECREF(c);
4116	n/a	c = temp;
4117	n/a	temp = NULL;
4118	n/a	_PyLong_Negate(&c);
4119	n/a	if (c == NULL)
4120	n/a	goto Error;
4121	n/a	}
4122	n/a
4123	n/a	/* if modulus == 1:
4124	n/a	return 0 */
4125	n/a	if ((Py_SIZE(c) == 1) && (c->ob_digit[0] == 1)) {
4126	n/a	z = (PyLongObject *)PyLong_FromLong(0L);
4127	n/a	goto Done;
4128	n/a	}
4129	n/a
4130	n/a	/* Reduce base by modulus in some cases:
4131	n/a	1. If base < 0. Forcing the base non-negative makes things easier.
4132	n/a	2. If base is obviously larger than the modulus. The "small
4133	n/a	exponent" case later can multiply directly by base repeatedly,
4134	n/a	while the "large exponent" case multiplies directly by base 31
4135	n/a	times. It can be unboundedly faster to multiply by
4136	n/a	base % modulus instead.
4137	n/a	We could _always_ do this reduction, but l_divmod() isn't cheap,
4138	n/a	so we only do it when it buys something. */
4139	n/a	if (Py_SIZE(a) < 0 \|\| Py_SIZE(a) > Py_SIZE(c)) {
4140	n/a	if (l_divmod(a, c, NULL, &temp) < 0)
4141	n/a	goto Error;
4142	n/a	Py_DECREF(a);
4143	n/a	a = temp;
4144	n/a	temp = NULL;
4145	n/a	}
4146	n/a	}
4147	n/a
4148	n/a	/* At this point a, b, and c are guaranteed non-negative UNLESS
4149	n/a	c is NULL, in which case a may be negative. */
4150	n/a
4151	n/a	z = (PyLongObject *)PyLong_FromLong(1L);
4152	n/a	if (z == NULL)
4153	n/a	goto Error;
4154	n/a
4155	n/a	/* Perform a modular reduction, X = X % c, but leave X alone if c
4156	n/a	* is NULL.
4157	n/a	*/
4158	n/a	#define REDUCE(X) \
4159	n/a	do { \
4160	n/a	if (c != NULL) { \
4161	n/a	if (l_divmod(X, c, NULL, &temp) < 0) \
4162	n/a	goto Error; \
4163	n/a	Py_XDECREF(X); \
4164	n/a	X = temp; \
4165	n/a	temp = NULL; \
4166	n/a	} \
4167	n/a	} while(0)
4168	n/a
4169	n/a	/* Multiply two values, then reduce the result:
4170	n/a	result = XY % c. If c is NULL, skip the mod. /
4171	n/a	#define MULT(X, Y, result) \
4172	n/a	do { \
4173	n/a	temp = (PyLongObject *)long_mul(X, Y); \
4174	n/a	if (temp == NULL) \
4175	n/a	goto Error; \
4176	n/a	Py_XDECREF(result); \
4177	n/a	result = temp; \
4178	n/a	temp = NULL; \
4179	n/a	REDUCE(result); \
4180	n/a	} while(0)
4181	n/a
4182	n/a	if (Py_SIZE(b) <= FIVEARY_CUTOFF) {
4183	n/a	/* Left-to-right binary exponentiation (HAC Algorithm 14.79) */
4184	n/a	/* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */
4185	n/a	for (i = Py_SIZE(b) - 1; i >= 0; --i) {
4186	n/a	digit bi = b->ob_digit[i];
4187	n/a
4188	n/a	for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) {
4189	n/a	MULT(z, z, z);
4190	n/a	if (bi & j)
4191	n/a	MULT(z, a, z);
4192	n/a	}
4193	n/a	}
4194	n/a	}
4195	n/a	else {
4196	n/a	/* Left-to-right 5-ary exponentiation (HAC Algorithm 14.82) */
4197	n/a	Py_INCREF(z); /* still holds 1L */
4198	n/a	table[0] = z;
4199	n/a	for (i = 1; i < 32; ++i)
4200	n/a	MULT(table[i-1], a, table[i]);
4201	n/a
4202	n/a	for (i = Py_SIZE(b) - 1; i >= 0; --i) {
4203	n/a	const digit bi = b->ob_digit[i];
4204	n/a
4205	n/a	for (j = PyLong_SHIFT - 5; j >= 0; j -= 5) {
4206	n/a	const int index = (bi >> j) & 0x1f;
4207	n/a	for (k = 0; k < 5; ++k)
4208	n/a	MULT(z, z, z);
4209	n/a	if (index)
4210	n/a	MULT(z, table[index], z);
4211	n/a	}
4212	n/a	}
4213	n/a	}
4214	n/a
4215	n/a	if (negativeOutput && (Py_SIZE(z) != 0)) {
4216	n/a	temp = (PyLongObject *)long_sub(z, c);
4217	n/a	if (temp == NULL)
4218	n/a	goto Error;
4219	n/a	Py_DECREF(z);
4220	n/a	z = temp;
4221	n/a	temp = NULL;
4222	n/a	}
4223	n/a	goto Done;
4224	n/a
4225	n/a	Error:
4226	n/a	Py_CLEAR(z);
4227	n/a	/* fall through */
4228	n/a	Done:
4229	n/a	if (Py_SIZE(b) > FIVEARY_CUTOFF) {
4230	n/a	for (i = 0; i < 32; ++i)
4231	n/a	Py_XDECREF(table[i]);
4232	n/a	}
4233	n/a	Py_DECREF(a);
4234	n/a	Py_DECREF(b);
4235	n/a	Py_XDECREF(c);
4236	n/a	Py_XDECREF(temp);
4237	n/a	return (PyObject *)z;
4238	n/a	}
4239	n/a
4240	n/a	static PyObject *
4241	n/a	long_invert(PyLongObject *v)
4242	n/a	{
4243	n/a	/* Implement ~x as -(x+1) */
4244	n/a	PyLongObject *x;
4245	n/a	PyLongObject *w;
4246	n/a	if (Py_ABS(Py_SIZE(v)) <=1)
4247	n/a	return PyLong_FromLong(-(MEDIUM_VALUE(v)+1));
4248	n/a	w = (PyLongObject *)PyLong_FromLong(1L);
4249	n/a	if (w == NULL)
4250	n/a	return NULL;
4251	n/a	x = (PyLongObject *) long_add(v, w);
4252	n/a	Py_DECREF(w);
4253	n/a	if (x == NULL)
4254	n/a	return NULL;
4255	n/a	_PyLong_Negate(&x);
4256	n/a	/* No need for maybe_small_long here, since any small
4257	n/a	longs will have been caught in the Py_SIZE <= 1 fast path. */
4258	n/a	return (PyObject *)x;
4259	n/a	}
4260	n/a
4261	n/a	static PyObject *
4262	n/a	long_neg(PyLongObject *v)
4263	n/a	{
4264	n/a	PyLongObject *z;
4265	n/a	if (Py_ABS(Py_SIZE(v)) <= 1)
4266	n/a	return PyLong_FromLong(-MEDIUM_VALUE(v));
4267	n/a	z = (PyLongObject *)_PyLong_Copy(v);
4268	n/a	if (z != NULL)
4269	n/a	Py_SIZE(z) = -(Py_SIZE(v));
4270	n/a	return (PyObject *)z;
4271	n/a	}
4272	n/a
4273	n/a	static PyObject *
4274	n/a	long_abs(PyLongObject *v)
4275	n/a	{
4276	n/a	if (Py_SIZE(v) < 0)
4277	n/a	return long_neg(v);
4278	n/a	else
4279	n/a	return long_long((PyObject *)v);
4280	n/a	}
4281	n/a
4282	n/a	static int
4283	n/a	long_bool(PyLongObject *v)
4284	n/a	{
4285	n/a	return Py_SIZE(v) != 0;
4286	n/a	}
4287	n/a
4288	n/a	static PyObject *
4289	n/a	long_rshift(PyLongObject a, PyLongObject b)
4290	n/a	{
4291	n/a	PyLongObject *z = NULL;
4292	n/a	Py_ssize_t shiftby, newsize, wordshift, loshift, hishift, i, j;
4293	n/a	digit lomask, himask;
4294	n/a
4295	n/a	CHECK_BINOP(a, b);
4296	n/a
4297	n/a	if (Py_SIZE(a) < 0) {
4298	n/a	/* Right shifting negative numbers is harder */
4299	n/a	PyLongObject a1, a2;
4300	n/a	a1 = (PyLongObject *) long_invert(a);
4301	n/a	if (a1 == NULL)
4302	n/a	return NULL;
4303	n/a	a2 = (PyLongObject *) long_rshift(a1, b);
4304	n/a	Py_DECREF(a1);
4305	n/a	if (a2 == NULL)
4306	n/a	return NULL;
4307	n/a	z = (PyLongObject *) long_invert(a2);
4308	n/a	Py_DECREF(a2);
4309	n/a	}
4310	n/a	else {
4311	n/a	shiftby = PyLong_AsSsize_t((PyObject *)b);
4312	n/a	if (shiftby == -1L && PyErr_Occurred())
4313	n/a	return NULL;
4314	n/a	if (shiftby < 0) {
4315	n/a	PyErr_SetString(PyExc_ValueError,
4316	n/a	"negative shift count");
4317	n/a	return NULL;
4318	n/a	}
4319	n/a	wordshift = shiftby / PyLong_SHIFT;
4320	n/a	newsize = Py_ABS(Py_SIZE(a)) - wordshift;
4321	n/a	if (newsize <= 0)
4322	n/a	return PyLong_FromLong(0);
4323	n/a	loshift = shiftby % PyLong_SHIFT;
4324	n/a	hishift = PyLong_SHIFT - loshift;
4325	n/a	lomask = ((digit)1 << hishift) - 1;
4326	n/a	himask = PyLong_MASK ^ lomask;
4327	n/a	z = _PyLong_New(newsize);
4328	n/a	if (z == NULL)
4329	n/a	return NULL;
4330	n/a	for (i = 0, j = wordshift; i < newsize; i++, j++) {
4331	n/a	z->ob_digit[i] = (a->ob_digit[j] >> loshift) & lomask;
4332	n/a	if (i+1 < newsize)
4333	n/a	z->ob_digit[i] \|= (a->ob_digit[j+1] << hishift) & himask;
4334	n/a	}
4335	n/a	z = maybe_small_long(long_normalize(z));
4336	n/a	}
4337	n/a	return (PyObject *)z;
4338	n/a	}
4339	n/a
4340	n/a	static PyObject *
4341	n/a	long_lshift(PyObject v, PyObject w)
4342	n/a	{
4343	n/a	/* This version due to Tim Peters */
4344	n/a	PyLongObject a = (PyLongObject)v;
4345	n/a	PyLongObject b = (PyLongObject)w;
4346	n/a	PyLongObject *z = NULL;
4347	n/a	Py_ssize_t shiftby, oldsize, newsize, wordshift, remshift, i, j;
4348	n/a	twodigits accum;
4349	n/a
4350	n/a	CHECK_BINOP(a, b);
4351	n/a
4352	n/a	shiftby = PyLong_AsSsize_t((PyObject *)b);
4353	n/a	if (shiftby == -1L && PyErr_Occurred())
4354	n/a	return NULL;
4355	n/a	if (shiftby < 0) {
4356	n/a	PyErr_SetString(PyExc_ValueError, "negative shift count");
4357	n/a	return NULL;
4358	n/a	}
4359	n/a
4360	n/a	if (Py_SIZE(a) == 0) {
4361	n/a	return PyLong_FromLong(0);
4362	n/a	}
4363	n/a
4364	n/a	/* wordshift, remshift = divmod(shiftby, PyLong_SHIFT) */
4365	n/a	wordshift = shiftby / PyLong_SHIFT;
4366	n/a	remshift = shiftby - wordshift * PyLong_SHIFT;
4367	n/a
4368	n/a	oldsize = Py_ABS(Py_SIZE(a));
4369	n/a	newsize = oldsize + wordshift;
4370	n/a	if (remshift)
4371	n/a	++newsize;
4372	n/a	z = _PyLong_New(newsize);
4373	n/a	if (z == NULL)
4374	n/a	return NULL;
4375	n/a	if (Py_SIZE(a) < 0) {
4376	n/a	assert(Py_REFCNT(z) == 1);
4377	n/a	Py_SIZE(z) = -Py_SIZE(z);
4378	n/a	}
4379	n/a	for (i = 0; i < wordshift; i++)
4380	n/a	z->ob_digit[i] = 0;
4381	n/a	accum = 0;
4382	n/a	for (i = wordshift, j = 0; j < oldsize; i++, j++) {
4383	n/a	accum \|= (twodigits)a->ob_digit[j] << remshift;
4384	n/a	z->ob_digit[i] = (digit)(accum & PyLong_MASK);
4385	n/a	accum >>= PyLong_SHIFT;
4386	n/a	}
4387	n/a	if (remshift)
4388	n/a	z->ob_digit[newsize-1] = (digit)accum;
4389	n/a	else
4390	n/a	assert(!accum);
4391	n/a	z = long_normalize(z);
4392	n/a	return (PyObject *) maybe_small_long(z);
4393	n/a	}
4394	n/a
4395	n/a	/* Compute two's complement of digit vector a[0:m], writing result to
4396	n/a	z[0:m]. The digit vector a need not be normalized, but should not
4397	n/a	be entirely zero. a and z may point to the same digit vector. */
4398	n/a
4399	n/a	static void
4400	n/a	v_complement(digit z, digit a, Py_ssize_t m)
4401	n/a	{
4402	n/a	Py_ssize_t i;
4403	n/a	digit carry = 1;
4404	n/a	for (i = 0; i < m; ++i) {
4405	n/a	carry += a[i] ^ PyLong_MASK;
4406	n/a	z[i] = carry & PyLong_MASK;
4407	n/a	carry >>= PyLong_SHIFT;
4408	n/a	}
4409	n/a	assert(carry == 0);
4410	n/a	}
4411	n/a
4412	n/a	/* Bitwise and/xor/or operations */
4413	n/a
4414	n/a	static PyObject *
4415	n/a	long_bitwise(PyLongObject *a,
4416	n/a	char op, /* '&', '\|', '^' */
4417	n/a	PyLongObject *b)
4418	n/a	{
4419	n/a	int nega, negb, negz;
4420	n/a	Py_ssize_t size_a, size_b, size_z, i;
4421	n/a	PyLongObject *z;
4422	n/a
4423	n/a	/* Bitwise operations for negative numbers operate as though
4424	n/a	on a two's complement representation. So convert arguments
4425	n/a	from sign-magnitude to two's complement, and convert the
4426	n/a	result back to sign-magnitude at the end. */
4427	n/a
4428	n/a	/* If a is negative, replace it by its two's complement. */
4429	n/a	size_a = Py_ABS(Py_SIZE(a));
4430	n/a	nega = Py_SIZE(a) < 0;
4431	n/a	if (nega) {
4432	n/a	z = _PyLong_New(size_a);
4433	n/a	if (z == NULL)
4434	n/a	return NULL;
4435	n/a	v_complement(z->ob_digit, a->ob_digit, size_a);
4436	n/a	a = z;
4437	n/a	}
4438	n/a	else
4439	n/a	/* Keep reference count consistent. */
4440	n/a	Py_INCREF(a);
4441	n/a
4442	n/a	/* Same for b. */
4443	n/a	size_b = Py_ABS(Py_SIZE(b));
4444	n/a	negb = Py_SIZE(b) < 0;
4445	n/a	if (negb) {
4446	n/a	z = _PyLong_New(size_b);
4447	n/a	if (z == NULL) {
4448	n/a	Py_DECREF(a);
4449	n/a	return NULL;
4450	n/a	}
4451	n/a	v_complement(z->ob_digit, b->ob_digit, size_b);
4452	n/a	b = z;
4453	n/a	}
4454	n/a	else
4455	n/a	Py_INCREF(b);
4456	n/a
4457	n/a	/* Swap a and b if necessary to ensure size_a >= size_b. */
4458	n/a	if (size_a < size_b) {
4459	n/a	z = a; a = b; b = z;
4460	n/a	size_z = size_a; size_a = size_b; size_b = size_z;
4461	n/a	negz = nega; nega = negb; negb = negz;
4462	n/a	}
4463	n/a
4464	n/a	/* JRH: The original logic here was to allocate the result value (z)
4465	n/a	as the longer of the two operands. However, there are some cases
4466	n/a	where the result is guaranteed to be shorter than that: AND of two
4467	n/a	positives, OR of two negatives: use the shorter number. AND with
4468	n/a	mixed signs: use the positive number. OR with mixed signs: use the
4469	n/a	negative number.
4470	n/a	*/
4471	n/a	switch (op) {
4472	n/a	case '^':
4473	n/a	negz = nega ^ negb;
4474	n/a	size_z = size_a;
4475	n/a	break;
4476	n/a	case '&':
4477	n/a	negz = nega & negb;
4478	n/a	size_z = negb ? size_a : size_b;
4479	n/a	break;
4480	n/a	case '\|':
4481	n/a	negz = nega \| negb;
4482	n/a	size_z = negb ? size_b : size_a;
4483	n/a	break;
4484	n/a	default:
4485	n/a	PyErr_BadArgument();
4486	n/a	return NULL;
4487	n/a	}
4488	n/a
4489	n/a	/* We allow an extra digit if z is negative, to make sure that
4490	n/a	the final two's complement of z doesn't overflow. */
4491	n/a	z = _PyLong_New(size_z + negz);
4492	n/a	if (z == NULL) {
4493	n/a	Py_DECREF(a);
4494	n/a	Py_DECREF(b);
4495	n/a	return NULL;
4496	n/a	}
4497	n/a
4498	n/a	/* Compute digits for overlap of a and b. */
4499	n/a	switch(op) {
4500	n/a	case '&':
4501	n/a	for (i = 0; i < size_b; ++i)
4502	n/a	z->ob_digit[i] = a->ob_digit[i] & b->ob_digit[i];
4503	n/a	break;
4504	n/a	case '\|':
4505	n/a	for (i = 0; i < size_b; ++i)
4506	n/a	z->ob_digit[i] = a->ob_digit[i] \| b->ob_digit[i];
4507	n/a	break;
4508	n/a	case '^':
4509	n/a	for (i = 0; i < size_b; ++i)
4510	n/a	z->ob_digit[i] = a->ob_digit[i] ^ b->ob_digit[i];
4511	n/a	break;
4512	n/a	default:
4513	n/a	PyErr_BadArgument();
4514	n/a	return NULL;
4515	n/a	}
4516	n/a
4517	n/a	/* Copy any remaining digits of a, inverting if necessary. */
4518	n/a	if (op == '^' && negb)
4519	n/a	for (; i < size_z; ++i)
4520	n/a	z->ob_digit[i] = a->ob_digit[i] ^ PyLong_MASK;
4521	n/a	else if (i < size_z)
4522	n/a	memcpy(&z->ob_digit[i], &a->ob_digit[i],
4523	n/a	(size_z-i)*sizeof(digit));
4524	n/a
4525	n/a	/* Complement result if negative. */
4526	n/a	if (negz) {
4527	n/a	Py_SIZE(z) = -(Py_SIZE(z));
4528	n/a	z->ob_digit[size_z] = PyLong_MASK;
4529	n/a	v_complement(z->ob_digit, z->ob_digit, size_z+1);
4530	n/a	}
4531	n/a
4532	n/a	Py_DECREF(a);
4533	n/a	Py_DECREF(b);
4534	n/a	return (PyObject *)maybe_small_long(long_normalize(z));
4535	n/a	}
4536	n/a
4537	n/a	static PyObject *
4538	n/a	long_and(PyObject a, PyObject b)
4539	n/a	{
4540	n/a	PyObject *c;
4541	n/a	CHECK_BINOP(a, b);
4542	n/a	c = long_bitwise((PyLongObject)a, '&', (PyLongObject)b);
4543	n/a	return c;
4544	n/a	}
4545	n/a
4546	n/a	static PyObject *
4547	n/a	long_xor(PyObject a, PyObject b)
4548	n/a	{
4549	n/a	PyObject *c;
4550	n/a	CHECK_BINOP(a, b);
4551	n/a	c = long_bitwise((PyLongObject)a, '^', (PyLongObject)b);
4552	n/a	return c;
4553	n/a	}
4554	n/a
4555	n/a	static PyObject *
4556	n/a	long_or(PyObject a, PyObject b)
4557	n/a	{
4558	n/a	PyObject *c;
4559	n/a	CHECK_BINOP(a, b);
4560	n/a	c = long_bitwise((PyLongObject)a, '\|', (PyLongObject)b);
4561	n/a	return c;
4562	n/a	}
4563	n/a
4564	n/a	static PyObject *
4565	n/a	long_long(PyObject *v)
4566	n/a	{
4567	n/a	if (PyLong_CheckExact(v))
4568	n/a	Py_INCREF(v);
4569	n/a	else
4570	n/a	v = _PyLong_Copy((PyLongObject *)v);
4571	n/a	return v;
4572	n/a	}
4573	n/a
4574	n/a	PyObject *
4575	n/a	_PyLong_GCD(PyObject aarg, PyObject barg)
4576	n/a	{
4577	n/a	PyLongObject a, b, c = NULL, d = NULL, *r;
4578	n/a	stwodigits x, y, q, s, t, c_carry, d_carry;
4579	n/a	stwodigits A, B, C, D, T;
4580	n/a	int nbits, k;
4581	n/a	Py_ssize_t size_a, size_b, alloc_a, alloc_b;
4582	n/a	digit a_digit, b_digit, c_digit, d_digit, a_end, b_end;
4583	n/a
4584	n/a	a = (PyLongObject *)aarg;
4585	n/a	b = (PyLongObject *)barg;
4586	n/a	size_a = Py_SIZE(a);
4587	n/a	size_b = Py_SIZE(b);
4588	n/a	if (-2 <= size_a && size_a <= 2 && -2 <= size_b && size_b <= 2) {
4589	n/a	Py_INCREF(a);
4590	n/a	Py_INCREF(b);
4591	n/a	goto simple;
4592	n/a	}
4593	n/a
4594	n/a	/* Initial reduction: make sure that 0 <= b <= a. */
4595	n/a	a = (PyLongObject *)long_abs(a);
4596	n/a	if (a == NULL)
4597	n/a	return NULL;
4598	n/a	b = (PyLongObject *)long_abs(b);
4599	n/a	if (b == NULL) {
4600	n/a	Py_DECREF(a);
4601	n/a	return NULL;
4602	n/a	}
4603	n/a	if (long_compare(a, b) < 0) {
4604	n/a	r = a;
4605	n/a	a = b;
4606	n/a	b = r;
4607	n/a	}
4608	n/a	/* We now own references to a and b */
4609	n/a
4610	n/a	alloc_a = Py_SIZE(a);
4611	n/a	alloc_b = Py_SIZE(b);
4612	n/a	/* reduce until a fits into 2 digits */
4613	n/a	while ((size_a = Py_SIZE(a)) > 2) {
4614	n/a	nbits = bits_in_digit(a->ob_digit[size_a-1]);
4615	n/a	/* extract top 2*PyLong_SHIFT bits of a into x, along with
4616	n/a	corresponding bits of b into y */
4617	n/a	size_b = Py_SIZE(b);
4618	n/a	assert(size_b <= size_a);
4619	n/a	if (size_b == 0) {
4620	n/a	if (size_a < alloc_a) {
4621	n/a	r = (PyLongObject *)_PyLong_Copy(a);
4622	n/a	Py_DECREF(a);
4623	n/a	}
4624	n/a	else
4625	n/a	r = a;
4626	n/a	Py_DECREF(b);
4627	n/a	Py_XDECREF(c);
4628	n/a	Py_XDECREF(d);
4629	n/a	return (PyObject *)r;
4630	n/a	}
4631	n/a	x = (((twodigits)a->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits)) \|
4632	n/a	((twodigits)a->ob_digit[size_a-2] << (PyLong_SHIFT-nbits)) \|
4633	n/a	(a->ob_digit[size_a-3] >> nbits));
4634	n/a
4635	n/a	y = ((size_b >= size_a - 2 ? b->ob_digit[size_a-3] >> nbits : 0) \|
4636	n/a	(size_b >= size_a - 1 ? (twodigits)b->ob_digit[size_a-2] << (PyLong_SHIFT-nbits) : 0) \|
4637	n/a	(size_b >= size_a ? (twodigits)b->ob_digit[size_a-1] << (2*PyLong_SHIFT-nbits) : 0));
4638	n/a
4639	n/a	/* inner loop of Lehmer's algorithm; A, B, C, D never grow
4640	n/a	larger than PyLong_MASK during the algorithm. */
4641	n/a	A = 1; B = 0; C = 0; D = 1;
4642	n/a	for (k=0;; k++) {
4643	n/a	if (y-C == 0)
4644	n/a	break;
4645	n/a	q = (x+(A-1))/(y-C);
4646	n/a	s = B+q*D;
4647	n/a	t = x-q*y;
4648	n/a	if (s > t)
4649	n/a	break;
4650	n/a	x = y; y = t;
4651	n/a	t = A+q*C; A = D; B = C; C = s; D = t;
4652	n/a	}
4653	n/a
4654	n/a	if (k == 0) {
4655	n/a	/* no progress; do a Euclidean step */
4656	n/a	if (l_divmod(a, b, NULL, &r) < 0)
4657	n/a	goto error;
4658	n/a	Py_DECREF(a);
4659	n/a	a = b;
4660	n/a	b = r;
4661	n/a	alloc_a = alloc_b;
4662	n/a	alloc_b = Py_SIZE(b);
4663	n/a	continue;
4664	n/a	}
4665	n/a
4666	n/a	/*
4667	n/a	a, b = Ab-Ba, Da-Cb if k is odd
4668	n/a	a, b = Aa-Bb, Db-Ca if k is even
4669	n/a	*/
4670	n/a	if (k&1) {
4671	n/a	T = -A; A = -B; B = T;
4672	n/a	T = -C; C = -D; D = T;
4673	n/a	}
4674	n/a	if (c != NULL)
4675	n/a	Py_SIZE(c) = size_a;
4676	n/a	else if (Py_REFCNT(a) == 1) {
4677	n/a	Py_INCREF(a);
4678	n/a	c = a;
4679	n/a	}
4680	n/a	else {
4681	n/a	alloc_a = size_a;
4682	n/a	c = _PyLong_New(size_a);
4683	n/a	if (c == NULL)
4684	n/a	goto error;
4685	n/a	}
4686	n/a
4687	n/a	if (d != NULL)
4688	n/a	Py_SIZE(d) = size_a;
4689	n/a	else if (Py_REFCNT(b) == 1 && size_a <= alloc_b) {
4690	n/a	Py_INCREF(b);
4691	n/a	d = b;
4692	n/a	Py_SIZE(d) = size_a;
4693	n/a	}
4694	n/a	else {
4695	n/a	alloc_b = size_a;
4696	n/a	d = _PyLong_New(size_a);
4697	n/a	if (d == NULL)
4698	n/a	goto error;
4699	n/a	}
4700	n/a	a_end = a->ob_digit + size_a;
4701	n/a	b_end = b->ob_digit + size_b;
4702	n/a
4703	n/a	/* compute new a and new b in parallel */
4704	n/a	a_digit = a->ob_digit;
4705	n/a	b_digit = b->ob_digit;
4706	n/a	c_digit = c->ob_digit;
4707	n/a	d_digit = d->ob_digit;
4708	n/a	c_carry = 0;
4709	n/a	d_carry = 0;
4710	n/a	while (b_digit < b_end) {
4711	n/a	c_carry += (A * a_digit) - (B *b_digit);
4712	n/a	d_carry += (D * b_digit++) - (C *a_digit++);
4713	n/a	*c_digit++ = (digit)(c_carry & PyLong_MASK);
4714	n/a	*d_digit++ = (digit)(d_carry & PyLong_MASK);
4715	n/a	c_carry >>= PyLong_SHIFT;
4716	n/a	d_carry >>= PyLong_SHIFT;
4717	n/a	}
4718	n/a	while (a_digit < a_end) {
4719	n/a	c_carry += A * *a_digit;
4720	n/a	d_carry -= C * *a_digit++;
4721	n/a	*c_digit++ = (digit)(c_carry & PyLong_MASK);
4722	n/a	*d_digit++ = (digit)(d_carry & PyLong_MASK);
4723	n/a	c_carry >>= PyLong_SHIFT;
4724	n/a	d_carry >>= PyLong_SHIFT;
4725	n/a	}
4726	n/a	assert(c_carry == 0);
4727	n/a	assert(d_carry == 0);
4728	n/a
4729	n/a	Py_INCREF(c);
4730	n/a	Py_INCREF(d);
4731	n/a	Py_DECREF(a);
4732	n/a	Py_DECREF(b);
4733	n/a	a = long_normalize(c);
4734	n/a	b = long_normalize(d);
4735	n/a	}
4736	n/a	Py_XDECREF(c);
4737	n/a	Py_XDECREF(d);
4738	n/a
4739	n/a	simple:
4740	n/a	assert(Py_REFCNT(a) > 0);
4741	n/a	assert(Py_REFCNT(b) > 0);
4742	n/a	/* Issue #24999: use two shifts instead of ">> 2*PyLong_SHIFT" to avoid
4743	n/a	undefined behaviour when LONG_MAX type is smaller than 60 bits */
4744	n/a	#if LONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4745	n/a	/* a fits into a long, so b must too */
4746	n/a	x = PyLong_AsLong((PyObject *)a);
4747	n/a	y = PyLong_AsLong((PyObject *)b);
4748	n/a	#elif PY_LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4749	n/a	x = PyLong_AsLongLong((PyObject *)a);
4750	n/a	y = PyLong_AsLongLong((PyObject *)b);
4751	n/a	#else
4752	n/a	# error "_PyLong_GCD"
4753	n/a	#endif
4754	n/a	x = Py_ABS(x);
4755	n/a	y = Py_ABS(y);
4756	n/a	Py_DECREF(a);
4757	n/a	Py_DECREF(b);
4758	n/a
4759	n/a	/* usual Euclidean algorithm for longs */
4760	n/a	while (y != 0) {
4761	n/a	t = y;
4762	n/a	y = x % y;
4763	n/a	x = t;
4764	n/a	}
4765	n/a	#if LONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4766	n/a	return PyLong_FromLong(x);
4767	n/a	#elif PY_LLONG_MAX >> PyLong_SHIFT >> PyLong_SHIFT
4768	n/a	return PyLong_FromLongLong(x);
4769	n/a	#else
4770	n/a	# error "_PyLong_GCD"
4771	n/a	#endif
4772	n/a
4773	n/a	error:
4774	n/a	Py_DECREF(a);
4775	n/a	Py_DECREF(b);
4776	n/a	Py_XDECREF(c);
4777	n/a	Py_XDECREF(d);
4778	n/a	return NULL;
4779	n/a	}
4780	n/a
4781	n/a	static PyObject *
4782	n/a	long_float(PyObject *v)
4783	n/a	{
4784	n/a	double result;
4785	n/a	result = PyLong_AsDouble(v);
4786	n/a	if (result == -1.0 && PyErr_Occurred())
4787	n/a	return NULL;
4788	n/a	return PyFloat_FromDouble(result);
4789	n/a	}
4790	n/a
4791	n/a	static PyObject *
4792	n/a	long_subtype_new(PyTypeObject type, PyObject args, PyObject *kwds);
4793	n/a
4794	n/a	static PyObject *
4795	n/a	long_new(PyTypeObject type, PyObject args, PyObject *kwds)
4796	n/a	{
4797	n/a	PyObject obase = NULL, x = NULL;
4798	n/a	Py_ssize_t base;
4799	n/a	static char *kwlist[] = {"x", "base", 0};
4800	n/a
4801	n/a	if (type != &PyLong_Type)
4802	n/a	return long_subtype_new(type, args, kwds); /* Wimp out */
4803	n/a	if (!PyArg_ParseTupleAndKeywords(args, kwds, "\|OO:int", kwlist,
4804	n/a	&x, &obase))
4805	n/a	return NULL;
4806	n/a	if (x == NULL) {
4807	n/a	if (obase != NULL) {
4808	n/a	PyErr_SetString(PyExc_TypeError,
4809	n/a	"int() missing string argument");
4810	n/a	return NULL;
4811	n/a	}
4812	n/a	return PyLong_FromLong(0L);
4813	n/a	}
4814	n/a	if (obase == NULL)
4815	n/a	return PyNumber_Long(x);
4816	n/a
4817	n/a	base = PyNumber_AsSsize_t(obase, NULL);
4818	n/a	if (base == -1 && PyErr_Occurred())
4819	n/a	return NULL;
4820	n/a	if ((base != 0 && base < 2) \|\| base > 36) {
4821	n/a	PyErr_SetString(PyExc_ValueError,
4822	n/a	"int() base must be >= 2 and <= 36");
4823	n/a	return NULL;
4824	n/a	}
4825	n/a
4826	n/a	if (PyUnicode_Check(x))
4827	n/a	return PyLong_FromUnicodeObject(x, (int)base);
4828	n/a	else if (PyByteArray_Check(x) \|\| PyBytes_Check(x)) {
4829	n/a	char *string;
4830	n/a	if (PyByteArray_Check(x))
4831	n/a	string = PyByteArray_AS_STRING(x);
4832	n/a	else
4833	n/a	string = PyBytes_AS_STRING(x);
4834	n/a	return _PyLong_FromBytes(string, Py_SIZE(x), (int)base);
4835	n/a	}
4836	n/a	else {
4837	n/a	PyErr_SetString(PyExc_TypeError,
4838	n/a	"int() can't convert non-string with explicit base");
4839	n/a	return NULL;
4840	n/a	}
4841	n/a	}
4842	n/a
4843	n/a	/* Wimpy, slow approach to tp_new calls for subtypes of int:
4844	n/a	first create a regular int from whatever arguments we got,
4845	n/a	then allocate a subtype instance and initialize it from
4846	n/a	the regular int. The regular int is then thrown away.
4847	n/a	*/
4848	n/a	static PyObject *
4849	n/a	long_subtype_new(PyTypeObject type, PyObject args, PyObject *kwds)
4850	n/a	{
4851	n/a	PyLongObject tmp, newobj;
4852	n/a	Py_ssize_t i, n;
4853	n/a
4854	n/a	assert(PyType_IsSubtype(type, &PyLong_Type));
4855	n/a	tmp = (PyLongObject *)long_new(&PyLong_Type, args, kwds);
4856	n/a	if (tmp == NULL)
4857	n/a	return NULL;
4858	n/a	assert(PyLong_Check(tmp));
4859	n/a	n = Py_SIZE(tmp);
4860	n/a	if (n < 0)
4861	n/a	n = -n;
4862	n/a	newobj = (PyLongObject *)type->tp_alloc(type, n);
4863	n/a	if (newobj == NULL) {
4864	n/a	Py_DECREF(tmp);
4865	n/a	return NULL;
4866	n/a	}
4867	n/a	assert(PyLong_Check(newobj));
4868	n/a	Py_SIZE(newobj) = Py_SIZE(tmp);
4869	n/a	for (i = 0; i < n; i++)
4870	n/a	newobj->ob_digit[i] = tmp->ob_digit[i];
4871	n/a	Py_DECREF(tmp);
4872	n/a	return (PyObject *)newobj;
4873	n/a	}
4874	n/a
4875	n/a	/*[clinic input]
4876	n/a	int.__getnewargs__
4877	n/a	[clinic start generated code]*/
4878	n/a
4879	n/a	static PyObject *
4880	n/a	int___getnewargs___impl(PyObject *self)
4881	n/a	/[clinic end generated code: output=839a49de3f00b61b input=5904770ab1fb8c75]/
4882	n/a	{
4883	n/a	return Py_BuildValue("(N)", _PyLong_Copy((PyLongObject *)self));
4884	n/a	}
4885	n/a
4886	n/a	static PyObject *
4887	n/a	long_get0(PyLongObject v, void context) {
4888	n/a	return PyLong_FromLong(0L);
4889	n/a	}
4890	n/a
4891	n/a	static PyObject *
4892	n/a	long_get1(PyLongObject v, void context) {
4893	n/a	return PyLong_FromLong(1L);
4894	n/a	}
4895	n/a
4896	n/a	/*[clinic input]
4897	n/a	int.__format__
4898	n/a
4899	n/a	format_spec: unicode
4900	n/a	/
4901	n/a	[clinic start generated code]*/
4902	n/a
4903	n/a	static PyObject *
4904	n/a	int___format___impl(PyObject self, PyObject format_spec)
4905	n/a	/[clinic end generated code: output=b4929dee9ae18689 input=e31944a9b3e428b7]/
4906	n/a	{
4907	n/a	_PyUnicodeWriter writer;
4908	n/a	int ret;
4909	n/a
4910	n/a	_PyUnicodeWriter_Init(&writer);
4911	n/a	ret = _PyLong_FormatAdvancedWriter(
4912	n/a	&writer,
4913	n/a	self,
4914	n/a	format_spec, 0, PyUnicode_GET_LENGTH(format_spec));
4915	n/a	if (ret == -1) {
4916	n/a	_PyUnicodeWriter_Dealloc(&writer);
4917	n/a	return NULL;
4918	n/a	}
4919	n/a	return _PyUnicodeWriter_Finish(&writer);
4920	n/a	}
4921	n/a
4922	n/a	/* Return a pair (q, r) such that a = b * q + r, and
4923	n/a	abs(r) <= abs(b)/2, with equality possible only if q is even.
4924	n/a	In other words, q == a / b, rounded to the nearest integer using
4925	n/a	round-half-to-even. */
4926	n/a
4927	n/a	PyObject *
4928	n/a	_PyLong_DivmodNear(PyObject a, PyObject b)
4929	n/a	{
4930	n/a	PyLongObject quo = NULL, rem = NULL;
4931	n/a	PyObject one = NULL, twice_rem, result, temp;
4932	n/a	int cmp, quo_is_odd, quo_is_neg;
4933	n/a
4934	n/a	/* Equivalent Python code:
4935	n/a
4936	n/a	def divmod_near(a, b):
4937	n/a	q, r = divmod(a, b)
4938	n/a	# round up if either r / b > 0.5, or r / b == 0.5 and q is odd.
4939	n/a	# The expression r / b > 0.5 is equivalent to 2 * r > b if b is
4940	n/a	# positive, 2 * r < b if b negative.
4941	n/a	greater_than_half = 2r > b if b > 0 else 2r < b
4942	n/a	exactly_half = 2*r == b
4943	n/a	if greater_than_half or exactly_half and q % 2 == 1:
4944	n/a	q += 1
4945	n/a	r -= b
4946	n/a	return q, r
4947	n/a
4948	n/a	*/
4949	n/a	if (!PyLong_Check(a) \|\| !PyLong_Check(b)) {
4950	n/a	PyErr_SetString(PyExc_TypeError,
4951	n/a	"non-integer arguments in division");
4952	n/a	return NULL;
4953	n/a	}
4954	n/a
4955	n/a	/* Do a and b have different signs? If so, quotient is negative. */
4956	n/a	quo_is_neg = (Py_SIZE(a) < 0) != (Py_SIZE(b) < 0);
4957	n/a
4958	n/a	one = PyLong_FromLong(1L);
4959	n/a	if (one == NULL)
4960	n/a	return NULL;
4961	n/a
4962	n/a	if (long_divrem((PyLongObject)a, (PyLongObject)b, &quo, &rem) < 0)
4963	n/a	goto error;
4964	n/a
4965	n/a	/* compare twice the remainder with the divisor, to see
4966	n/a	if we need to adjust the quotient and remainder */
4967	n/a	twice_rem = long_lshift((PyObject *)rem, one);
4968	n/a	if (twice_rem == NULL)
4969	n/a	goto error;
4970	n/a	if (quo_is_neg) {
4971	n/a	temp = long_neg((PyLongObject*)twice_rem);
4972	n/a	Py_DECREF(twice_rem);
4973	n/a	twice_rem = temp;
4974	n/a	if (twice_rem == NULL)
4975	n/a	goto error;
4976	n/a	}
4977	n/a	cmp = long_compare((PyLongObject )twice_rem, (PyLongObject )b);
4978	n/a	Py_DECREF(twice_rem);
4979	n/a
4980	n/a	quo_is_odd = Py_SIZE(quo) != 0 && ((quo->ob_digit[0] & 1) != 0);
4981	n/a	if ((Py_SIZE(b) < 0 ? cmp < 0 : cmp > 0) \|\| (cmp == 0 && quo_is_odd)) {
4982	n/a	/* fix up quotient */
4983	n/a	if (quo_is_neg)
4984	n/a	temp = long_sub(quo, (PyLongObject *)one);
4985	n/a	else
4986	n/a	temp = long_add(quo, (PyLongObject *)one);
4987	n/a	Py_DECREF(quo);
4988	n/a	quo = (PyLongObject *)temp;
4989	n/a	if (quo == NULL)
4990	n/a	goto error;
4991	n/a	/* and remainder */
4992	n/a	if (quo_is_neg)
4993	n/a	temp = long_add(rem, (PyLongObject *)b);
4994	n/a	else
4995	n/a	temp = long_sub(rem, (PyLongObject *)b);
4996	n/a	Py_DECREF(rem);
4997	n/a	rem = (PyLongObject *)temp;
4998	n/a	if (rem == NULL)
4999	n/a	goto error;
5000	n/a	}
5001	n/a
5002	n/a	result = PyTuple_New(2);
5003	n/a	if (result == NULL)
5004	n/a	goto error;
5005	n/a
5006	n/a	/* PyTuple_SET_ITEM steals references */
5007	n/a	PyTuple_SET_ITEM(result, 0, (PyObject *)quo);
5008	n/a	PyTuple_SET_ITEM(result, 1, (PyObject *)rem);
5009	n/a	Py_DECREF(one);
5010	n/a	return result;
5011	n/a
5012	n/a	error:
5013	n/a	Py_XDECREF(quo);
5014	n/a	Py_XDECREF(rem);
5015	n/a	Py_XDECREF(one);
5016	n/a	return NULL;
5017	n/a	}
5018	n/a
5019	n/a	static PyObject *
5020	n/a	long_round(PyObject self, PyObject args)
5021	n/a	{
5022	n/a	PyObject o_ndigits=NULL, temp, result, ndigits;
5023	n/a
5024	n/a	/* To round an integer m to the nearest 10**n (n positive), we make use of
5025	n/a	* the divmod_near operation, defined by:
5026	n/a	*
5027	n/a	* divmod_near(a, b) = (q, r)
5028	n/a	*
5029	n/a	* where q is the nearest integer to the quotient a / b (the
5030	n/a	* nearest even integer in the case of a tie) and r == a - q * b.
5031	n/a	* Hence q * b = a - r is the nearest multiple of b to a,
5032	n/a	* preferring even multiples in the case of a tie.
5033	n/a	*
5034	n/a	* So the nearest multiple of 10**n to m is:
5035	n/a	*
5036	n/a	* m - divmod_near(m, 10**n)[1].
5037	n/a	*/
5038	n/a	if (!PyArg_ParseTuple(args, "\|O", &o_ndigits))
5039	n/a	return NULL;
5040	n/a	if (o_ndigits == NULL)
5041	n/a	return long_long(self);
5042	n/a
5043	n/a	ndigits = PyNumber_Index(o_ndigits);
5044	n/a	if (ndigits == NULL)
5045	n/a	return NULL;
5046	n/a
5047	n/a	/* if ndigits >= 0 then no rounding is necessary; return self unchanged */
5048	n/a	if (Py_SIZE(ndigits) >= 0) {
5049	n/a	Py_DECREF(ndigits);
5050	n/a	return long_long(self);
5051	n/a	}
5052	n/a
5053	n/a	/* result = self - divmod_near(self, 10 ** -ndigits)[1] */
5054	n/a	temp = long_neg((PyLongObject*)ndigits);
5055	n/a	Py_DECREF(ndigits);
5056	n/a	ndigits = temp;
5057	n/a	if (ndigits == NULL)
5058	n/a	return NULL;
5059	n/a
5060	n/a	result = PyLong_FromLong(10L);
5061	n/a	if (result == NULL) {
5062	n/a	Py_DECREF(ndigits);
5063	n/a	return NULL;
5064	n/a	}
5065	n/a
5066	n/a	temp = long_pow(result, ndigits, Py_None);
5067	n/a	Py_DECREF(ndigits);
5068	n/a	Py_DECREF(result);
5069	n/a	result = temp;
5070	n/a	if (result == NULL)
5071	n/a	return NULL;
5072	n/a
5073	n/a	temp = _PyLong_DivmodNear(self, result);
5074	n/a	Py_DECREF(result);
5075	n/a	result = temp;
5076	n/a	if (result == NULL)
5077	n/a	return NULL;
5078	n/a
5079	n/a	temp = long_sub((PyLongObject *)self,
5080	n/a	(PyLongObject *)PyTuple_GET_ITEM(result, 1));
5081	n/a	Py_DECREF(result);
5082	n/a	result = temp;
5083	n/a
5084	n/a	return result;
5085	n/a	}
5086	n/a
5087	n/a	/*[clinic input]
5088	n/a	int.__sizeof__ -> Py_ssize_t
5089	n/a
5090	n/a	Returns size in memory, in bytes.
5091	n/a	[clinic start generated code]*/
5092	n/a
5093	n/a	static Py_ssize_t
5094	n/a	int___sizeof___impl(PyObject *self)
5095	n/a	/[clinic end generated code: output=3303f008eaa6a0a5 input=9b51620c76fc4507]/
5096	n/a	{
5097	n/a	Py_ssize_t res;
5098	n/a
5099	n/a	res = offsetof(PyLongObject, ob_digit) + Py_ABS(Py_SIZE(self))*sizeof(digit);
5100	n/a	return res;
5101	n/a	}
5102	n/a
5103	n/a	/*[clinic input]
5104	n/a	int.bit_length
5105	n/a
5106	n/a	Number of bits necessary to represent self in binary.
5107	n/a
5108	n/a	>>> bin(37)
5109	n/a	'0b100101'
5110	n/a	>>> (37).bit_length()
5111	n/a	6
5112	n/a	[clinic start generated code]*/
5113	n/a
5114	n/a	static PyObject *
5115	n/a	int_bit_length_impl(PyObject *self)
5116	n/a	/[clinic end generated code: output=fc1977c9353d6a59 input=e4eb7a587e849a32]/
5117	n/a	{
5118	n/a	PyLongObject result, x, *y;
5119	n/a	Py_ssize_t ndigits;
5120	n/a	int msd_bits;
5121	n/a	digit msd;
5122	n/a
5123	n/a	assert(self != NULL);
5124	n/a	assert(PyLong_Check(self));
5125	n/a
5126	n/a	ndigits = Py_ABS(Py_SIZE(self));
5127	n/a	if (ndigits == 0)
5128	n/a	return PyLong_FromLong(0);
5129	n/a
5130	n/a	msd = ((PyLongObject *)self)->ob_digit[ndigits-1];
5131	n/a	msd_bits = bits_in_digit(msd);
5132	n/a
5133	n/a	if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
5134	n/a	return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
5135	n/a
5136	n/a	/* expression above may overflow; use Python integers instead */
5137	n/a	result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
5138	n/a	if (result == NULL)
5139	n/a	return NULL;
5140	n/a	x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
5141	n/a	if (x == NULL)
5142	n/a	goto error;
5143	n/a	y = (PyLongObject *)long_mul(result, x);
5144	n/a	Py_DECREF(x);
5145	n/a	if (y == NULL)
5146	n/a	goto error;
5147	n/a	Py_DECREF(result);
5148	n/a	result = y;
5149	n/a
5150	n/a	x = (PyLongObject *)PyLong_FromLong((long)msd_bits);
5151	n/a	if (x == NULL)
5152	n/a	goto error;
5153	n/a	y = (PyLongObject *)long_add(result, x);
5154	n/a	Py_DECREF(x);
5155	n/a	if (y == NULL)
5156	n/a	goto error;
5157	n/a	Py_DECREF(result);
5158	n/a	result = y;
5159	n/a
5160	n/a	return (PyObject *)result;
5161	n/a
5162	n/a	error:
5163	n/a	Py_DECREF(result);
5164	n/a	return NULL;
5165	n/a	}
5166	n/a
5167	n/a	#if 0
5168	n/a	static PyObject *
5169	n/a	long_is_finite(PyObject *v)
5170	n/a	{
5171	n/a	Py_RETURN_TRUE;
5172	n/a	}
5173	n/a	#endif
5174	n/a
5175	n/a	/*[clinic input]
5176	n/a	int.to_bytes
5177	n/a
5178	n/a	length: Py_ssize_t
5179	n/a	Length of bytes object to use. An OverflowError is raised if the
5180	n/a	integer is not representable with the given number of bytes.
5181	n/a	byteorder: unicode
5182	n/a	The byte order used to represent the integer. If byteorder is 'big',
5183	n/a	the most significant byte is at the beginning of the byte array. If
5184	n/a	byteorder is 'little', the most significant byte is at the end of the
5185	n/a	byte array. To request the native byte order of the host system, use
5186	n/a	`sys.byteorder' as the byte order value.
5187	n/a	*
5188	n/a	signed as is_signed: bool = False
5189	n/a	Determines whether two's complement is used to represent the integer.
5190	n/a	If signed is False and a negative integer is given, an OverflowError
5191	n/a	is raised.
5192	n/a
5193	n/a	Return an array of bytes representing an integer.
5194	n/a	[clinic start generated code]*/
5195	n/a
5196	n/a	static PyObject *
5197	n/a	int_to_bytes_impl(PyObject self, Py_ssize_t length, PyObject byteorder,
5198	n/a	int is_signed)
5199	n/a	/[clinic end generated code: output=89c801df114050a3 input=ddac63f4c7bf414c]/
5200	n/a	{
5201	n/a	int little_endian;
5202	n/a	PyObject *bytes;
5203	n/a
5204	n/a	if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_little))
5205	n/a	little_endian = 1;
5206	n/a	else if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_big))
5207	n/a	little_endian = 0;
5208	n/a	else {
5209	n/a	PyErr_SetString(PyExc_ValueError,
5210	n/a	"byteorder must be either 'little' or 'big'");
5211	n/a	return NULL;
5212	n/a	}
5213	n/a
5214	n/a	if (length < 0) {
5215	n/a	PyErr_SetString(PyExc_ValueError,
5216	n/a	"length argument must be non-negative");
5217	n/a	return NULL;
5218	n/a	}
5219	n/a
5220	n/a	bytes = PyBytes_FromStringAndSize(NULL, length);
5221	n/a	if (bytes == NULL)
5222	n/a	return NULL;
5223	n/a
5224	n/a	if (_PyLong_AsByteArray((PyLongObject *)self,
5225	n/a	(unsigned char *)PyBytes_AS_STRING(bytes),
5226	n/a	length, little_endian, is_signed) < 0) {
5227	n/a	Py_DECREF(bytes);
5228	n/a	return NULL;
5229	n/a	}
5230	n/a
5231	n/a	return bytes;
5232	n/a	}
5233	n/a
5234	n/a	/*[clinic input]
5235	n/a	@classmethod
5236	n/a	int.from_bytes
5237	n/a
5238	n/a	bytes as bytes_obj: object
5239	n/a	Holds the array of bytes to convert. The argument must either
5240	n/a	support the buffer protocol or be an iterable object producing bytes.
5241	n/a	Bytes and bytearray are examples of built-in objects that support the
5242	n/a	buffer protocol.
5243	n/a	byteorder: unicode
5244	n/a	The byte order used to represent the integer. If byteorder is 'big',
5245	n/a	the most significant byte is at the beginning of the byte array. If
5246	n/a	byteorder is 'little', the most significant byte is at the end of the
5247	n/a	byte array. To request the native byte order of the host system, use
5248	n/a	`sys.byteorder' as the byte order value.
5249	n/a	*
5250	n/a	signed as is_signed: bool = False
5251	n/a	Indicates whether two's complement is used to represent the integer.
5252	n/a
5253	n/a	Return the integer represented by the given array of bytes.
5254	n/a	[clinic start generated code]*/
5255	n/a
5256	n/a	static PyObject *
5257	n/a	int_from_bytes_impl(PyTypeObject type, PyObject bytes_obj,
5258	n/a	PyObject *byteorder, int is_signed)
5259	n/a	/[clinic end generated code: output=efc5d68e31f9314f input=cdf98332b6a821b0]/
5260	n/a	{
5261	n/a	int little_endian;
5262	n/a	PyObject long_obj, bytes;
5263	n/a
5264	n/a	if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_little))
5265	n/a	little_endian = 1;
5266	n/a	else if (_PyUnicode_EqualToASCIIId(byteorder, &PyId_big))
5267	n/a	little_endian = 0;
5268	n/a	else {
5269	n/a	PyErr_SetString(PyExc_ValueError,
5270	n/a	"byteorder must be either 'little' or 'big'");
5271	n/a	return NULL;
5272	n/a	}
5273	n/a
5274	n/a	bytes = PyObject_Bytes(bytes_obj);
5275	n/a	if (bytes == NULL)
5276	n/a	return NULL;
5277	n/a
5278	n/a	long_obj = _PyLong_FromByteArray(
5279	n/a	(unsigned char *)PyBytes_AS_STRING(bytes), Py_SIZE(bytes),
5280	n/a	little_endian, is_signed);
5281	n/a	Py_DECREF(bytes);
5282	n/a
5283	n/a	if (type != &PyLong_Type) {
5284	n/a	Py_SETREF(long_obj, PyObject_CallFunctionObjArgs((PyObject *)type,
5285	n/a	long_obj, NULL));
5286	n/a	}
5287	n/a
5288	n/a	return long_obj;
5289	n/a	}
5290	n/a
5291	n/a	static PyMethodDef long_methods[] = {
5292	n/a	{"conjugate", (PyCFunction)long_long, METH_NOARGS,
5293	n/a	"Returns self, the complex conjugate of any int."},
5294	n/a	INT_BIT_LENGTH_METHODDEF
5295	n/a	#if 0
5296	n/a	{"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
5297	n/a	"Returns always True."},
5298	n/a	#endif
5299	n/a	INT_TO_BYTES_METHODDEF
5300	n/a	INT_FROM_BYTES_METHODDEF
5301	n/a	{"__trunc__", (PyCFunction)long_long, METH_NOARGS,
5302	n/a	"Truncating an Integral returns itself."},
5303	n/a	{"__floor__", (PyCFunction)long_long, METH_NOARGS,
5304	n/a	"Flooring an Integral returns itself."},
5305	n/a	{"__ceil__", (PyCFunction)long_long, METH_NOARGS,
5306	n/a	"Ceiling of an Integral returns itself."},
5307	n/a	{"__round__", (PyCFunction)long_round, METH_VARARGS,
5308	n/a	"Rounding an Integral returns itself.\n"
5309	n/a	"Rounding with an ndigits argument also returns an integer."},
5310	n/a	INT___GETNEWARGS___METHODDEF
5311	n/a	INT___FORMAT___METHODDEF
5312	n/a	INT___SIZEOF___METHODDEF
5313	n/a	{NULL, NULL} /* sentinel */
5314	n/a	};
5315	n/a
5316	n/a	static PyGetSetDef long_getset[] = {
5317	n/a	{"real",
5318	n/a	(getter)long_long, (setter)NULL,
5319	n/a	"the real part of a complex number",
5320	n/a	NULL},
5321	n/a	{"imag",
5322	n/a	(getter)long_get0, (setter)NULL,
5323	n/a	"the imaginary part of a complex number",
5324	n/a	NULL},
5325	n/a	{"numerator",
5326	n/a	(getter)long_long, (setter)NULL,
5327	n/a	"the numerator of a rational number in lowest terms",
5328	n/a	NULL},
5329	n/a	{"denominator",
5330	n/a	(getter)long_get1, (setter)NULL,
5331	n/a	"the denominator of a rational number in lowest terms",
5332	n/a	NULL},
5333	n/a	{NULL} /* Sentinel */
5334	n/a	};
5335	n/a
5336	n/a	PyDoc_STRVAR(long_doc,
5337	n/a	"int(x=0) -> integer\n\
5338	n/a	int(x, base=10) -> integer\n\
5339	n/a	\n\
5340	n/a	Convert a number or string to an integer, or return 0 if no arguments\n\
5341	n/a	are given. If x is a number, return x.__int__(). For floating point\n\
5342	n/a	numbers, this truncates towards zero.\n\
5343	n/a	\n\
5344	n/a	If x is not a number or if base is given, then x must be a string,\n\
5345	n/a	bytes, or bytearray instance representing an integer literal in the\n\
5346	n/a	given base. The literal can be preceded by '+' or '-' and be surrounded\n\
5347	n/a	by whitespace. The base defaults to 10. Valid bases are 0 and 2-36.\n\
5348	n/a	Base 0 means to interpret the base from the string as an integer literal.\n\
5349	n/a	>>> int('0b100', base=0)\n\
5350	n/a	4");
5351	n/a
5352	n/a	static PyNumberMethods long_as_number = {
5353	n/a	(binaryfunc)long_add, /nb_add/
5354	n/a	(binaryfunc)long_sub, /nb_subtract/
5355	n/a	(binaryfunc)long_mul, /nb_multiply/
5356	n/a	long_mod, /nb_remainder/
5357	n/a	long_divmod, /nb_divmod/
5358	n/a	long_pow, /nb_power/
5359	n/a	(unaryfunc)long_neg, /nb_negative/
5360	n/a	(unaryfunc)long_long, /tp_positive/
5361	n/a	(unaryfunc)long_abs, /tp_absolute/
5362	n/a	(inquiry)long_bool, /tp_bool/
5363	n/a	(unaryfunc)long_invert, /nb_invert/
5364	n/a	long_lshift, /nb_lshift/
5365	n/a	(binaryfunc)long_rshift, /nb_rshift/
5366	n/a	long_and, /nb_and/
5367	n/a	long_xor, /nb_xor/
5368	n/a	long_or, /nb_or/
5369	n/a	long_long, /nb_int/
5370	n/a	0, /nb_reserved/
5371	n/a	long_float, /nb_float/
5372	n/a	0, /* nb_inplace_add */
5373	n/a	0, /* nb_inplace_subtract */
5374	n/a	0, /* nb_inplace_multiply */
5375	n/a	0, /* nb_inplace_remainder */
5376	n/a	0, /* nb_inplace_power */
5377	n/a	0, /* nb_inplace_lshift */
5378	n/a	0, /* nb_inplace_rshift */
5379	n/a	0, /* nb_inplace_and */
5380	n/a	0, /* nb_inplace_xor */
5381	n/a	0, /* nb_inplace_or */
5382	n/a	long_div, /* nb_floor_divide */
5383	n/a	long_true_divide, /* nb_true_divide */
5384	n/a	0, /* nb_inplace_floor_divide */
5385	n/a	0, /* nb_inplace_true_divide */
5386	n/a	long_long, /* nb_index */
5387	n/a	};
5388	n/a
5389	n/a	PyTypeObject PyLong_Type = {
5390	n/a	PyVarObject_HEAD_INIT(&PyType_Type, 0)
5391	n/a	"int", /* tp_name */
5392	n/a	offsetof(PyLongObject, ob_digit), /* tp_basicsize */
5393	n/a	sizeof(digit), /* tp_itemsize */
5394	n/a	long_dealloc, /* tp_dealloc */
5395	n/a	0, /* tp_print */
5396	n/a	0, /* tp_getattr */
5397	n/a	0, /* tp_setattr */
5398	n/a	0, /* tp_reserved */
5399	n/a	long_to_decimal_string, /* tp_repr */
5400	n/a	&long_as_number, /* tp_as_number */
5401	n/a	0, /* tp_as_sequence */
5402	n/a	0, /* tp_as_mapping */
5403	n/a	(hashfunc)long_hash, /* tp_hash */
5404	n/a	0, /* tp_call */
5405	n/a	long_to_decimal_string, /* tp_str */
5406	n/a	PyObject_GenericGetAttr, /* tp_getattro */
5407	n/a	0, /* tp_setattro */
5408	n/a	0, /* tp_as_buffer */
5409	n/a	Py_TPFLAGS_DEFAULT \| Py_TPFLAGS_BASETYPE \|
5410	n/a	Py_TPFLAGS_LONG_SUBCLASS, /* tp_flags */
5411	n/a	long_doc, /* tp_doc */
5412	n/a	0, /* tp_traverse */
5413	n/a	0, /* tp_clear */
5414	n/a	long_richcompare, /* tp_richcompare */
5415	n/a	0, /* tp_weaklistoffset */
5416	n/a	0, /* tp_iter */
5417	n/a	0, /* tp_iternext */
5418	n/a	long_methods, /* tp_methods */
5419	n/a	0, /* tp_members */
5420	n/a	long_getset, /* tp_getset */
5421	n/a	0, /* tp_base */
5422	n/a	0, /* tp_dict */
5423	n/a	0, /* tp_descr_get */
5424	n/a	0, /* tp_descr_set */
5425	n/a	0, /* tp_dictoffset */
5426	n/a	0, /* tp_init */
5427	n/a	0, /* tp_alloc */
5428	n/a	long_new, /* tp_new */
5429	n/a	PyObject_Del, /* tp_free */
5430	n/a	};
5431	n/a
5432	n/a	static PyTypeObject Int_InfoType;
5433	n/a
5434	n/a	PyDoc_STRVAR(int_info__doc__,
5435	n/a	"sys.int_info\n\
5436	n/a	\n\
5437	n/a	A struct sequence that holds information about Python's\n\
5438	n/a	internal representation of integers. The attributes are read only.");
5439	n/a
5440	n/a	static PyStructSequence_Field int_info_fields[] = {
5441	n/a	{"bits_per_digit", "size of a digit in bits"},
5442	n/a	{"sizeof_digit", "size in bytes of the C type used to represent a digit"},
5443	n/a	{NULL, NULL}
5444	n/a	};
5445	n/a
5446	n/a	static PyStructSequence_Desc int_info_desc = {
5447	n/a	"sys.int_info", /* name */
5448	n/a	int_info__doc__, /* doc */
5449	n/a	int_info_fields, /* fields */
5450	n/a	2 /* number of fields */
5451	n/a	};
5452	n/a
5453	n/a	PyObject *
5454	n/a	PyLong_GetInfo(void)
5455	n/a	{
5456	n/a	PyObject* int_info;
5457	n/a	int field = 0;
5458	n/a	int_info = PyStructSequence_New(&Int_InfoType);
5459	n/a	if (int_info == NULL)
5460	n/a	return NULL;
5461	n/a	PyStructSequence_SET_ITEM(int_info, field++,
5462	n/a	PyLong_FromLong(PyLong_SHIFT));
5463	n/a	PyStructSequence_SET_ITEM(int_info, field++,
5464	n/a	PyLong_FromLong(sizeof(digit)));
5465	n/a	if (PyErr_Occurred()) {
5466	n/a	Py_CLEAR(int_info);
5467	n/a	return NULL;
5468	n/a	}
5469	n/a	return int_info;
5470	n/a	}
5471	n/a
5472	n/a	int
5473	n/a	_PyLong_Init(void)
5474	n/a	{
5475	n/a	#if NSMALLNEGINTS + NSMALLPOSINTS > 0
5476	n/a	int ival, size;
5477	n/a	PyLongObject *v = small_ints;
5478	n/a
5479	n/a	for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++, v++) {
5480	n/a	size = (ival < 0) ? -1 : ((ival == 0) ? 0 : 1);
5481	n/a	if (Py_TYPE(v) == &PyLong_Type) {
5482	n/a	/* The element is already initialized, most likely
5483	n/a	* the Python interpreter was initialized before.
5484	n/a	*/
5485	n/a	Py_ssize_t refcnt;
5486	n/a	PyObject* op = (PyObject*)v;
5487	n/a
5488	n/a	refcnt = Py_REFCNT(op) < 0 ? 0 : Py_REFCNT(op);
5489	n/a	_Py_NewReference(op);
5490	n/a	/* _Py_NewReference sets the ref count to 1 but
5491	n/a	* the ref count might be larger. Set the refcnt
5492	n/a	* to the original refcnt + 1 */
5493	n/a	Py_REFCNT(op) = refcnt + 1;
5494	n/a	assert(Py_SIZE(op) == size);
5495	n/a	assert(v->ob_digit[0] == (digit)abs(ival));
5496	n/a	}
5497	n/a	else {
5498	n/a	(void)PyObject_INIT(v, &PyLong_Type);
5499	n/a	}
5500	n/a	Py_SIZE(v) = size;
5501	n/a	v->ob_digit[0] = (digit)abs(ival);
5502	n/a	}
5503	n/a	#endif
5504	n/a	/* initialize int_info */
5505	n/a	if (Int_InfoType.tp_name == NULL) {
5506	n/a	if (PyStructSequence_InitType2(&Int_InfoType, &int_info_desc) < 0)
5507	n/a	return 0;
5508	n/a	}
5509	n/a
5510	n/a	return 1;
5511	n/a	}
5512	n/a
5513	n/a	void
5514	n/a	PyLong_Fini(void)
5515	n/a	{
5516	n/a	/* Integers are currently statically allocated. Py_DECREF is not
5517	n/a	needed, but Python must forget about the reference or multiple
5518	n/a	reinitializations will fail. */
5519	n/a	#if NSMALLNEGINTS + NSMALLPOSINTS > 0
5520	n/a	int i;
5521	n/a	PyLongObject *v = small_ints;
5522	n/a	for (i = 0; i < NSMALLNEGINTS + NSMALLPOSINTS; i++, v++) {
5523	n/a	_Py_DEC_REFTOTAL;
5524	n/a	_Py_ForgetReference((PyObject*)v);
5525	n/a	}
5526	n/a	#endif
5527	n/a	}