[Python-checkins] CVS: python/dist/src/Objects longobject.c,1.71.6.5,1.71.6.6

[Tim Peters]

Update of /cvsroot/python/python/dist/src/Objects
In directory usw-pr-cvs1:/tmp/cvs-serv4678/descr/dist/src/Objects

Modified Files:
      Tag: descr-branch
	longobject.c 
Log Message:
Merge trunk tag delta date2001-07-13 to date2001-07-15.


Index: longobject.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Objects/longobject.c,v
retrieving revision 1.71.6.5
retrieving revision 1.71.6.6
diff -C2 -r1.71.6.5 -r1.71.6.6
*** longobject.c	2001/07/14 07:47:35	1.71.6.5
--- longobject.c	2001/07/15 20:26:55	1.71.6.6
***************
*** 7,11 ****
  #include "longintrepr.h"
  
- #include <assert.h>
  #include <ctype.h>
  
--- 7,10 ----
***************
*** 16,20 ****
  static PyLongObject *mul1(PyLongObject *, wdigit);
  static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
! static PyLongObject *divrem1(PyLongObject *, wdigit, digit *);
  static PyObject *long_format(PyObject *aa, int base, int addL);
  
--- 15,19 ----
  static PyLongObject *mul1(PyLongObject *, wdigit);
  static PyLongObject *muladd1(PyLongObject *, wdigit, wdigit);
! static PyLongObject *divrem1(PyLongObject *, digit, digit *);
  static PyObject *long_format(PyObject *aa, int base, int addL);
  
***************
*** 708,711 ****
--- 707,733 ----
  }
  
+ /* Divide long pin, w/ size digits, by non-zero digit n, storing quotient
+    in pout, and returning the remainder.  pin and pout point at the LSD.
+    It's OK for pin == pout on entry, which saves oodles of mallocs/frees in
+    long_format, but that should be done with great care since longs are
+    immutable. */
+ 
+ static digit
+ inplace_divrem1(digit *pout, digit *pin, int size, digit n)
+ {
+ 	twodigits rem = 0;
+ 
+ 	assert(n > 0 && n <= MASK);
+ 	pin += size;
+ 	pout += size;
+ 	while (--size >= 0) {
+ 		digit hi;
+ 		rem = (rem << SHIFT) + *--pin;
+ 		*--pout = hi = (digit)(rem / n);
+ 		rem -= hi * n;
+ 	}
+ 	return (digit)rem;
+ }
+ 
  /* Divide a long integer by a digit, returning both the quotient
     (as function result) and the remainder (through *prem).
***************
*** 713,722 ****
  
  static PyLongObject *
! divrem1(PyLongObject *a, wdigit n, digit *prem)
  {
! 	int size = ABS(a->ob_size);
  	PyLongObject *z;
- 	int i;
- 	twodigits rem = 0;
  	
  	assert(n > 0 && n <= MASK);
--- 735,742 ----
  
  static PyLongObject *
! divrem1(PyLongObject *a, digit n, digit *prem)
  {
! 	const int size = ABS(a->ob_size);
  	PyLongObject *z;
  	
  	assert(n > 0 && n <= MASK);
***************
*** 724,733 ****
  	if (z == NULL)
  		return NULL;
! 	for (i = size; --i >= 0; ) {
! 		rem = (rem << SHIFT) + a->ob_digit[i];
! 		z->ob_digit[i] = (digit) (rem/n);
! 		rem %= n;
! 	}
! 	*prem = (digit) rem;
  	return long_normalize(z);
  }
--- 744,748 ----
  	if (z == NULL)
  		return NULL;
! 	*prem = inplace_divrem1(z->ob_digit, a->ob_digit, size, n);
  	return long_normalize(z);
  }
***************
*** 743,747 ****
  	PyStringObject *str;
  	int i;
! 	int size_a = ABS(a->ob_size);
  	char *p;
  	int bits;
--- 758,762 ----
  	PyStringObject *str;
  	int i;
! 	const int size_a = ABS(a->ob_size);
  	char *p;
  	int bits;
***************
*** 777,812 ****
  	else if ((base & (base - 1)) == 0) {
  		/* JRH: special case for power-of-2 bases */
! 		twodigits temp = a->ob_digit[0];
! 		int bitsleft = SHIFT;
! 		int rem;
! 		int last = abs(a->ob_size);
! 		int basebits = 1;
  		i = base;
  		while ((i >>= 1) > 1)
  			++basebits;
! 		
! 		i = 0;
! 		for (;;) {
! 			while (bitsleft >= basebits) {
! 				if ((temp == 0) && (i >= last - 1)) break;
! 				rem = temp & (base - 1);
! 				if (rem < 10)
! 					rem += '0';
! 				else
! 					rem += 'A' - 10;
  				assert(p > PyString_AS_STRING(str));
! 				*--p = (char) rem;
! 				bitsleft -= basebits;
! 				temp >>= basebits;
! 			}
! 			if (++i >= last) {
! 				if (temp == 0) break;
! 				bitsleft = 99;
! 				/* loop again to pick up final digits */
! 			}
! 			else {
! 				temp = (a->ob_digit[i] << bitsleft) | temp;
! 				bitsleft += SHIFT;
! 			}
  		}
  	}
--- 792,815 ----
  	else if ((base & (base - 1)) == 0) {
  		/* JRH: special case for power-of-2 bases */
! 		twodigits accum = 0;
! 		int accumbits = 0;	/* # of bits in accum */
! 		int basebits = 1;	/* # of bits in base-1 */
  		i = base;
  		while ((i >>= 1) > 1)
  			++basebits;
! 
! 		for (i = 0; i < size_a; ++i) {
! 			accum |= a->ob_digit[i] << accumbits;
! 			accumbits += SHIFT;
! 			assert(accumbits >= basebits);
! 			do {
! 				char digit = (char)(accum & (base - 1));
! 				digit += (digit < 10) ? '0' : 'A'-10;
  				assert(p > PyString_AS_STRING(str));
! 				*--p = digit;
! 				accumbits -= basebits;
! 				accum >>= basebits;
! 			} while (i < size_a-1 ? accumbits >= basebits :
! 					 	accum > 0);
  		}
  	}
***************
*** 815,818 ****
--- 818,825 ----
  		   base, but for speed use the highest power of base that
  		   fits in a digit. */
+ 		int size = size_a;
+ 		digit *pin = a->ob_digit;
+ 		PyLongObject *scratch;
+ 		/* powbasw <- largest power of base that fits in a digit. */
  		digit powbase = base;  /* powbase == base ** power */
  		int power = 1;
***************
*** 823,845 ****
  			powbase = (digit)newpow;
  			++power;
  		}
! 		
! 		Py_INCREF(a);
  		do {
  			int ntostore = power;
! 			digit rem;
! 			PyLongObject *temp = divrem1(a, powbase, &rem);
! 			Py_DECREF(a);
! 			if (temp == NULL) {
! 				Py_DECREF(str);
! 				return NULL;
! 			}
! 			a = temp;
  			SIGCHECK({
! 				Py_DECREF(a);
  				Py_DECREF(str);
  				return NULL;
  			})
! 			while (--ntostore >= 0) {
  				digit nextrem = (digit)(rem / base);
  				char c = (char)(rem - nextrem * base);
--- 830,859 ----
  			powbase = (digit)newpow;
  			++power;
+ 		}
+ 
+ 		/* Get a scratch area for repeated division. */
+ 		scratch = _PyLong_New(size);
+ 		if (scratch == NULL) {
+ 			Py_DECREF(str);
+ 			return NULL;
  		}
! 
! 		/* Repeatedly divide by powbase. */
  		do {
  			int ntostore = power;
! 			digit rem = inplace_divrem1(scratch->ob_digit,
! 						     pin, size, powbase);
! 			pin = scratch->ob_digit; /* no need to use a again */
! 			if (pin[size - 1] == 0)
! 				--size;
  			SIGCHECK({
! 				Py_DECREF(scratch);
  				Py_DECREF(str);
  				return NULL;
  			})
! 
! 			/* Break rem into digits. */
! 			assert(ntostore > 0);
! 			do {
  				digit nextrem = (digit)(rem / base);
  				char c = (char)(rem - nextrem * base);
***************
*** 848,856 ****
  				*--p = c;
  				rem = nextrem;
! 				if (a->ob_size == 0 && rem == 0)
! 					break;  /* skip leading zeroes */
! 			}
! 		} while (ABS(a->ob_size) != 0);
! 		Py_DECREF(a);
  	}
  
--- 862,872 ----
  				*--p = c;
  				rem = nextrem;
! 				--ntostore;
! 				/* Termination is a bit delicate:  must not
! 				   store leading zeroes, so must get out if
! 				   remaining quotient and rem are both 0. */
! 			} while (ntostore && (size || rem));
! 		} while (size != 0);
! 		Py_DECREF(scratch);
  	}