bigint.c

Bug Summary

File:	subcmd/unitools/bigint.c
Warning:	line 2242, column 20 The result of left shift is undefined because the right operand is >= 32, not smaller than 32, the capacity of 'BIntS'
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name bigint.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/kfp/aldor/aldor/aldor/subcmd/unitools -fcoverage-compilation-dir=/home/kfp/aldor/aldor/aldor/subcmd/unitools -resource-dir /usr/local/lib/clang/18 -D PACKAGE_NAME="aldor" -D PACKAGE_TARNAME="aldor" -D PACKAGE_VERSION="1.4.0" -D PACKAGE_STRING="aldor 1.4.0" -D PACKAGE_BUGREPORT="aldor@xinutec.org" -D PACKAGE_URL="" -D PACKAGE="aldor" -D VERSION="1.4.0" -D YYTEXT_POINTER=1 -D HAVE_STDIO_H=1 -D HAVE_STDLIB_H=1 -D HAVE_STRING_H=1 -D HAVE_INTTYPES_H=1 -D HAVE_STDINT_H=1 -D HAVE_STRINGS_H=1 -D HAVE_SYS_STAT_H=1 -D HAVE_SYS_TYPES_H=1 -D HAVE_UNISTD_H=1 -D STDC_HEADERS=1 -D HAVE_LIBREADLINE=1 -D HAVE_READLINE_READLINE_H=1 -D HAVE_READLINE_HISTORY=1 -D HAVE_READLINE_HISTORY_H=1 -D USE_GLOOP_SHELL=1 -D GENERATOR_COROUTINES=0 -D HAVE_DLFCN_H=1 -D LT_OBJDIR=".libs/" -I . -I ./../../src -I ../../src -internal-isystem /usr/local/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/14/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2026-01-15-223856-845667-1 -x c bigint.c
1/*****************************************************************************
*
* bigint.c: Big integer arithmetic.
*
* Copyright (c) 1990-2007 Aldor Software Organization Ltd (Aldor.org).
*
****************************************************************************/

9/*
* Operations of the form "bintAaaa" do not modify their arguments,
* and always allocate new values as their results. E.g., the statement
*
*      b1 = bintShift(b0, i);
*
* causes the BInt value b0 to be shifted by i bits, creating
* a new BInt value b1.
* These operations work on normalized numbers.
* I.e. When a number is small enough, it is represented immediately.
* Otherwise it is stored and Placec(b) > 0 && Placev(b)[Placec(b)-1] != 0.
*
* Operations of the form "xintAaaa" can modify their arguments or,
* if necessary, reallocate and free their input.
*
* Operations of the form "iintAaaa" do no storage allocation whatsoever
* and perform the big integer arithmetic algorithms.
*/

28#include "axlgen.h"
29#include "bigint.h"
30#include "debug.h"
31#include "store.h"
32#include "util.h"
33#include "compopt.h"

35/*
* The following symbols are used to conditionalize code in this file:
*
* BIGINT_DO_DEBUG	  -- Turns on DEBUG(bint) blocks.
* BIGINT_DEBUG_IMMED	  -- Turns on (bad) code for generalized ImmedIfCan.
* BIGINT_SHORT_IMMED	  -- Defines IInt as "short" rather than "int".
* BIGINT_USE_WHOLE_WORDS -- Turns on (incomplete) code for long bint digits.
* BIGINT_SHHH		  -- Turns off all debugging code.
*
*/


47/*
* Define BIGINT_DO_DEBUG to display debug info.
*/
50#ifdef BIGINT_DO_DEBUG
51# define bintDebug((int) 0)	true1
52#else
53# define bintDebug((int) 0)	false((int) 0)
54#endif

56#define bintDEBUGif (!((int) 0)) { } else fprintf	DEBUG_IF(bint)if (!((int) 0)) { } else	fprintf

58#ifdef FOAM_RTS
59# define dbOut stdoutstdout
60#endif

62/*****************************************************************************
*
* :: Remove linkage to String (and hence format.c etc)
*
****************************************************************************/

68localstatic String
69localStrAlloc(Length n)
70{
String  s;
s = (String) stoAlloc((unsigned) OB_String7, n + 1);
s[0] = 0;
s[n] = 0;
return s;
76}

78localstatic void
79localStrFree(String s)
80{
stoFree((Pointer) s);
82}

84/*****************************************************************************
*
* :: Integer range defintitions
*
*    Should work for 2's complement n-bit ints, for even n >= 4.
*
*****************************************************************************/


93#ifdef BIGINT_SHORT_IMMED
94typedef short		IInt;
95typedef UShort		UIInt;
96#else
97typedef long		IInt;
98typedef unsigned long	UIInt;
99#endif


102/*
* Conversion between ints and immediate BInts.
*/
105#define IsImmed(b)((long)(b) & 1)	((long)(b) &  1)
106#define MkImmed(n)((((long)(n)) << 1) | 1)	((((long)(n)) << 1) | 1)
107#define UnImmed(n)((n) >> 1)	((n) >> 1)

109#define BIntToInt(b)((IInt) ((((long) (b))) >> 1)) 	((IInt) UnImmed(ptrToLong(b))((((long) (b))) >> 1))
110#define IntToBInt(n)((BInt) ((Pointer)(((((long)(n)) << 1) | 1))))	((BInt) ptrFrLong(MkImmed(n))((Pointer)(((((long)(n)) << 1) | 1))))
111#define BIntZero((BInt) ((((long)(0)) << 1) | 1))	((BInt) MkImmed(0)((((long)(0)) << 1) | 1))
112#define BIntOne((BInt) ((((long)(1)) << 1) | 1))		((BInt) MkImmed(1)((((long)(1)) << 1) | 1))

114/*
* Fields of stored BInts.
*/
117#define Beq(a,b)((a) == (b))	((a) == (b))
118#define IsNeg(b)((b)->isNeg)	((b)->isNeg)
119#define Placec(b)((b)->placec)	((b)->placec)
120#define Placea(b)((b)->placea)	((b)->placea)
121#define Placev(b)((b)->placev)	((b)->placev)

123/*
* The minimum and maximum values of type int.
*/
126#ifndef INT_MIN(-2147483647 -1)
127# define INT_MIN(-2147483647 -1)	((IInt) ((-1)<<(bitsizeof(IInt)(8 * sizeof(IInt))-1)))
128# define INT_MAX2147483647	(- (INT_MIN(-2147483647 -1) + 1))		  /* 2's complement */
129#endif

131/*
* These are the min + max int values which are represented as immediate BInts.
* These must satisfy BIntToInt(IntToBInt(n)) == n,
*   hence the "-2" in INT_MIN_IMMED.
*/
136#define INT_LG_IMMED((8 * sizeof(IInt))-2)	(bitsizeof(IInt)(8 * sizeof(IInt))-2)
137#define INT_MIN_IMMED((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)	((((IInt) 3) << INT_LG_IMMED((8 * sizeof(IInt))-2)) + 1)
138#define INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1))	(- (long) INT_MIN_IMMED((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1))
139#define INT_IS_IMMED(n)(((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)<= (long
)(n) && (long)(n)<= (- (long) ((((IInt) 3) <<
 ((8 * sizeof(IInt))-2)) + 1)))	(INT_MIN_IMMED((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)<= (long)(n) && (long)(n)<= INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)))

141#define INT_LG_HALF(((8 * sizeof(IInt))-2)/2)	((bitsizeof(IInt)(8 * sizeof(IInt))-2)/2)
142#define INT_MAX_HALF((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1)	((((IInt) 1)<<(INT_LG_HALF(((8 * sizeof(IInt))-2)/2))) -1)
143#define INT_MIN_HALF(-((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1))	(-INT_MAX_HALF((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1))
144#define INT_IS_HALF(n)((-((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1)) <=
 (long)(n) && (long)(n)<= ((((IInt) 1)<<((((
* sizeof(IInt))-2)/2))) -1))	(INT_MIN_HALF(-((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1)) <= (long)(n) && (long)(n)<= INT_MAX_HALF((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1))

146/*
* Calculation radix.
* Must be possible to detect overflow on addition and implement double word
*   multiply and divide.
*/

152#ifdef BIGINT_DO_DEBUG
153# define BINT_LG_RADIX((8 * sizeof(BIntS)))		7
154#else
155# define BINT_LG_RADIX((8 * sizeof(BIntS)))		(bitsizeof(BIntS)(8 * sizeof(BIntS)))
156#endif
157#define BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))))		(((unsigned long) 1) << BINT_LG_RADIX((8 * sizeof(BIntS))))
			/* Might not be representable! */
159#define BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1)		(BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1)
160#define BINT_RADIX_MINUS_1((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1)	(BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1)

162/*****************************************************************************
*
* :: Double precision arithmetic macros
*
*****************************************************************************/

168typedef ULong	BIntD;		/* To contain two BInt digits. */

170#define TestGTDouble(b, h1, l1, h2, l2){ BIntS h1_ = (h1), h2_ = (h2); (b) = (h1_ > h2_) || (h1_ ==
 h2_ && (l1)>(l2)); } {		\
BIntS h1_ = (h1), h2_ = (h2);			\
(b) = (h1_ > h2_) || (h1_ == h2_ && (l1)>(l2));	\
173}

175#define TimesDouble(h, l, a, b){ BIntD t_ = (BIntD)(a)*(BIntD)(b); (h) = t_ / (((unsigned long
) 1) << ((8 * sizeof(BIntS)))); (l) = t_ % (((unsigned long
) 1) << ((8 * sizeof(BIntS)))); } {			\
BIntD t_ = (BIntD)(a)*(BIntD)(b);		\
(h) = t_ / BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));				\
(l) = t_ % BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));				\
179}

181#define DivideDouble(q, r, nh, nl, d){ BIntD n_ = (BIntD)(nh)*(BIntD)(((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) + (nl); BIntD d_ = (d); (q) = n_ / d_
; (r) = n_ % d_; } {			\
BIntD n_ = (BIntD)(nh)*(BIntD)BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) + (nl);\
BIntD d_ = (d);					\
(q)      = n_ / d_;				\
(r)	 = n_ % d_;				\
186}

188#define PlusStep(kout, r, a, b, kin){ BIntD r_ = (BIntD)(a)+(BIntD)(b)+(BIntD)(kin); BIntS k_ = (
r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof(BIntS
))))); if (k_) r_ -= (((unsigned long) 1) << ((8 * sizeof
(BIntS)))); (r) = r_; (kout) = k_; } {			\
BIntD	r_ = (BIntD)(a)+(BIntD)(b)+(BIntD)(kin);\
BIntS	k_ = (r_ >= (BIntD) BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))));	\
if (k_) r_ -= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))); 			\
(r)    = r_;					\
(kout) = k_;					\
194}

196#define MinusStep(kp1out, r, a, b, kp1in){ BIntD r_ = (BIntD)(a)+(BIntD)((((((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) - 1) - (b)))+(BIntD)(kp1in); BIntS k_
 = (r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof
(BIntS))))); if (k_) r_ -= (((unsigned long) 1) << ((8 *
 sizeof(BIntS)))); (r) = r_; (kp1out) = k_; }  		\
PlusStep(kp1out, r, a, (BINT_RADIX_MINUS_1 - (b)), kp1in){ BIntD r_ = (BIntD)(a)+(BIntD)((((((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) - 1) - (b)))+(BIntD)(kp1in); BIntS k_
 = (r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof
(BIntS))))); if (k_) r_ -= (((unsigned long) 1) << ((8 *
 sizeof(BIntS)))); (r) = r_; (kp1out) = k_; }

199#define TimesStep(kout, r, a, b, c, kin){ BIntD t_ = (BIntD)(a)*(BIntD)(b)+(BIntD)(c)+(BIntD)(kin); (
r) = t_ % (((unsigned long) 1) << ((8 * sizeof(BIntS)))
); (kout) = t_ / (((unsigned long) 1) << ((8 * sizeof(BIntS
)))); } {		\
BIntD	t_ = (BIntD)(a)*(BIntD)(b)+(BIntD)(c)+(BIntD)(kin);	\
(r)    = t_ % BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));			\
(kout) = t_ / BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));			\
203}



207/*****************************************************************************
*
* :: Related machine integer operations
*
*****************************************************************************/

213/*
* The length of n, in bits. I.e. cieling(lg(abs(n))).
* Define the bit length of zero to be one bit.
*/
217Length
218uintLength(unsigned long u)
219{
register Length i;
register UIInt  p;

/* Eventually the unsigned quantity p is bigger than u = abs(n). */
/* At each stage of the loop, any u < p can fit in i bits. */
for (i = 1, p = 2; ; i += 1, p <<= 1)
if (!p || u < p) break;
return i;
228}

230Length
231intLength(long n)
232{
return uintLength((n < 0) ? -n : n);
234}


237Bool
238uintBit(unsigned long si, Length ix)
239{
return (ix < bitsizeof(UIInt)(8 * sizeof(UIInt))) && ( ((ULong)si) & (1L<<ix)) != 0;
241}

243Bool
244intBit(long si, Length ix)
245{
return uintBit((si < 0) ? -si : si, ix);
247}

249/****************************************************************************
*
* :: Input/output
*
****************************************************************************/

255int
256bintPrint(FILE *fout, BInt b)
257{
int	cc;
String	s;

if (IsImmed(b)((long)(b) & 1)) return fprintf(fout, "%ld", BIntToInt(b)((IInt) ((((long) (b))) >> 1)));

s  = bintToString(b);
cc = fprintf(fout, "%s", s);
localStrFree(s);

return cc;
268}

270void
271bintPrintDb(BInt b)
272{
bintPrint(dbOut, b);
fprintf(dbOut, "\n");
275}

277int
278bintPrint16(FILE *fout, BInt b)
279{
int	i, cc;

if (IsImmed(b)((long)(b) & 1)) return fprintf(fout, "0x%lx", BIntToInt(b)((IInt) ((((long) (b))) >> 1)));

cc  = fprintf(fout, IsNeg(b)((b)->isNeg) ? "-" : "+");
cc += fprintf(fout, "0x");

for (i = Placec(b)((b)->placec) - 1; i >= 0; i--)
cc += fprintf(fout, "%0*x.",
	      (int) QUO_ROUND_UP(BINT_LG_RADIX,4)((((8 * sizeof(BIntS)))) % (4) ? (((8 * sizeof(BIntS))))/(4) +
: (((8 * sizeof(BIntS))))/(4)),
	      Placev(b)((b)->placev)[i]);

return cc;
293}

295/*
* +0b[3/4]10,10100,00110.
*
* [3/4] -- 3 of 4 allocated places are used
*/

301int
302bintPrint2(FILE *fout, BInt b)
303{
int	i, n, cc = 0;

if (bintIsNeg(b)) cc += fprintf(fout, "-");

cc += fprintf(fout, "0b");

if (IsImmed(b)((long)(b) & 1))
cc += fprintf(fout, "[0/0]");
else
cc += fprintf(fout, "[%d/%d]", (int) Placec(b)((b)->placec), (int) Placea(b)((b)->placea));

n = bintLength(b);

for (i = n-1; i >= 0; i--)
cc += fprintf(fout, bintBit(b, i) ? "1" : "0");

return cc;
321}

323/*
* Overestimate the size of a base 10 string representation for b,
* by dividing by 3 (not log(10)/log(2) > 3.32).
* +3   for signs, \0, etc.
* +dio for temp leading zeros.
*/

330int
331bintStringSize(BInt b)
332{
IInt	dio;
ULong	rio;

if (IsImmed(b)((long)(b) & 1)) return INT_LG_IMMED((8 * sizeof(IInt))-2);

/*
* Determine power of output radix for divisions.
* This is the largest power of 10 < BINT_RADIX.
*/
for (rio = 10, dio = 1; 10*rio <= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))); rio *= 10, dio++)
;
return bintLength(b)/3+3+dio;
345}


348/*
* Compute a base 10 string representation of b.
* The string representation includes a terminating \0 character.
*/
352String
353bintIntoString(String s, BInt b)
354{
Bool	isNeg;
IInt	digEst, i, j, dio;
ULong	rio;
BIntS	r;

if (IsImmed(b)((long)(b) & 1)) {
sprintf(s, "%ld", BIntToInt(b)((IInt) ((((long) (b))) >> 1)));
return s;
}

/*
* Determine power of output radix for divisions.
* This is the largest power of 10 < BINT_RADIX.
*/
for (rio = 10, dio = 1; 10*rio <= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))); rio *= 10, dio++)
;

/*
* Make copy for in-place divisions.
*/
b      = bintCopy(b);
isNeg  = IsNeg(b)((b)->isNeg);

digEst = bintStringSize(b);
i      = digEst;
s[--i] = 0;

while (Placec(b)((b)->placec) > 0) {
iintDivideS(b, &r, b, (BIntS) rio);
for (j = 0; j < dio; j++) {
	s[--i] = '0' + r % 10;
	r /= 10;
}
}

while (s[i] == '0') i++;	/* Cd have leading zeros. */
if (s[i] == 0) s[--i] = '0';	/* Ensure at least one digit. */
if (isNeg) s[--i] = '-';	/* Put on sign. */

/*
* Move text to the beginning of the string.
*/
assert(i >= 0)do { if (!(i >= 0)) _do_assert(("i >= 0"),"bigint.c",397
); } while (0);
if (i > 0) for (j = 0; i < digEst; i++, j++) s[j] = s[i];

bintFree(b);

return s;
403}


406/*
* Compute a base 10 string representation of b.
* The string representation includes a terminating \0 character.
*/
410String
411bintToString(BInt b)
412{
IInt	digEst = bintStringSize(b);
String	s      = localStrAlloc(digEst);

bintIntoString(s, b);

return s;
419}

421/*
* Convert from the textual representation of an Aldor number into a big
* integer. This function may be invoked (indirectly) by convert()$Machine
* and cannot assume base 10.
*
* General Aldor integer format is RRrWW
*
*    RR  is the radix part (2-36)
*    'r' is the radix character.
*    WW  is the whole part ([0-9A-Z]+).
*/
432BInt
433bintFrString(String s)
434{
return bintRadixScanFrString(s, NULL((void*)0));
436}

438#define fiRadixChar('r')	('r')
439#define fiPlusChar('+')	('+')
440#define fiMinusChar('-')	('-')

442/* Scan a big integer with possible radix specification */
443BInt
444bintRadixScanFrString(String num, String *pEnd)
445{
Bool	isNeg = false((int) 0);
String	rpos = (String)NULL((void*)0);
String	end;
long	radix = 10;
BInt	retval;
Length	rlen, ndigs, bpd;
IInt	dim, dio;
UIInt    ires;
IInt	l, l0, n;
ULong	rim, rio, nbits;
ULong	maxi;


/* Skip over leading whitespace */
while (isspace(*num)((*__ctype_b_loc ())[(int) ((*num))] & (unsigned short int
) _ISspace))
num++;


/* Deal with the sign (if any) */
if ((*num == fiPlusChar('+')) || (*num == fiMinusChar('-')))
{
isNeg = (*num == fiMinusChar('-')) ? true1 : false((int) 0);
num++;
}


/*
* Locate the end of the string: start by skipping over
* the leading part (which must be in base 10). This
* might be the radix or it might be the whole part.
*/
for (end = num; isdigit(*end)((*__ctype_b_loc ())[(int) ((*end))] & (unsigned short int
) _ISdigit); end++);


/* Is there a radix marker? */
if (*end == fiRadixChar('r'))
{
/* Yes - note its position */
rpos = end;
end++;


/* Skip past the whole part */
for (;isdigit(*end)((*__ctype_b_loc ())[(int) ((*end))] & (unsigned short int
) _ISdigit) || isupper(*end)((*__ctype_b_loc ())[(int) ((*end))] & (unsigned short int
) _ISupper);end++);
}
else
{
/* NOOOOOOOOOOOOOOO!!!!!!!!!!!!!! */
/* Skip past the decimal whole part */
for (;isdigit(*end)((*__ctype_b_loc ())[(int) ((*end))] & (unsigned short int
) _ISdigit);end++);
}


/* Did the caller want to know where the number ends? */
if (pEnd) *pEnd = end;


/* There must be something before the radix marker */
if (rpos == num)
return IntToBInt((long) 0)((BInt) ((Pointer)(((((long)((long) 0)) << 1) | 1)))); /* Bad number */


/* Extract the radix (if any) */
if (rpos)
{
/* Extract the radix as a (small) decimal integer */
rlen  = rpos - num;
radix = ulongSmallIntFrString(num, rlen, 10);


/* Valid radix: 2-36 inclusive */
if (errno(*__errno_location ()) || (radix < 2) || (radix > 36))
	return IntToBInt((long) 0)((BInt) ((Pointer)(((((long)((long) 0)) << 1) | 1))));


/* Move to the start of the whole part */
num = rpos + 1;
}


/*
* Determine the largest power `rim' of the input radix that
* can be used for immediate representation. We want `rim' such
* that (INT_MAX_IMMED/radix < rim <= INT_MAX_IMMED). We can
* not check whether (radix*rim <= INT_MAX_IMMED) because the
* LHS may overflow for large `radix'. Instead we `rim' such
* that (INT_MAX_IMMED/(radix^2) < rim <= INT_MAX_IMMED/radix).
* This means that for all radix, (radix*rim <= INT_MAX_IMMED).
*/
maxi = INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)) / radix;
for (
rim = radix, dim = 1;
radix*rim <= maxi;
rim *= radix, dim++
);


/* Now satisfy (INT_MAX_IMMED/radix < rim <= INT_MAX_IMMED) */
rim *= radix, dim++;


/*
* Determine the largest power `rio' of input radix for
* multiplications s.t. (BINT_RADIX/radix <= rio < BINT_RADIX).
*/
maxi = BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) / radix;
for (
rio = radix, dio = 1;
radix*rio < maxi;
rio *= radix, dio++
);


/* Now satisfy (BINT_RADIX/radix <= rio < BINT_RADIX) */
rio *= radix, dio++;


/*
* Convert the whole part using the specified base. First we
* need to estimate the number of bits needed for the result.
*/
bpd   = (ULong)(log((double)radix)/log(2.0)) + 1;
ndigs = (Length)(end - num);
nbits = ndigs*bpd;


/* If safe, compute as a C integer. */
if (nbits <= INT_LG_IMMED((8 * sizeof(IInt))-2))
{
/* Scan the small immediate integer */
ires = ulongSmallIntFrString(num, ndigs, radix);


/*
 * Return the immediate result. If the number
 * contained invalid characters then the result
 * will be invalid. Check errno if required.
 */
if (isNeg) ires = -ires;
return IntToBInt(ires)((BInt) ((Pointer)(((((long)(ires)) << 1) | 1))));
}


/* Allocate enough store for the result */
retval = bintAlloc(nbits);


/*
* Convert radix by interpreting string as a poly in radix
* `rio' and evaluating using Horner's rule. This means that
* we convert the number in chunks that will fit into an
* immediate integer. Start with a chunk big enough to ensure
* that the remaining chunks are all `dio' digits long.
*/
l0 = ndigs % dio;
for (n = 0, l = l0; l > 0; l--)
{
IInt dig;

dig = (*num <= '9') ? (*num - '0') : (*num - 'A') + 10;
n   = radix*n + dig;
num++;
}
retval = xintCopyInI(retval, n);


/* Now deal with the other chunks */
for (ndigs -= l0; ndigs > 0; ndigs -= dio)
{
for (n = 0, l = dio; l > 0; l--)
{
	IInt dig;

	dig = (*num <= '9') ? (*num - '0') : (*num - 'A') + 10;
	n   = radix*n + dig;
	num++;
}
iintTimesPlusS(retval, retval, (BIntS) rio, (BIntS) n);
}


/* Deal with any negation */
IsNeg(retval)((retval)->isNeg) = isNeg;


/* Try to make it an immediate integer is possible */
return xintImmedIfCan(retval);
633}


636/* Convert a base 10 string representation to a big integer. */
637BInt
638bintScanFrString(String s, String *end)
639{
String	t;
BInt	b;
Bool	isNeg = false((int) 0);
Length	ndig;
IInt	dim, dio;
ULong	rim, rio;
IInt	l, l0, n;

/*
* Determine rim: power of input radix for immediate representation.
*   This is the largest power of 10 <= INT_MAX_IMMED.
* Determine rio: power of input radix for multiplications.
*   This is the largest power of 10 < BINT_RADIX.
*/
for (rim = 10, dim = 1; 10*rim <= INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)); rim *= 10, dim++)
;
      /*
* BUG -------------------------+
       *                              V
*/
for (rio = 10, dio = 1; 10*rio <= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));    rio *= 10, dio++)
;

/*
* Find beginning and end of number.
* Don't use strlen, since there may be trailing text.
*/
while (isspace(*s)((*__ctype_b_loc ())[(int) ((*s))] & (unsigned short int)
 _ISspace))
s++;
if (*s == '-') {
isNeg = true1;
s++;
}
while (*s == '0')
s++;
for (t = s; isdigit(*t)((*__ctype_b_loc ())[(int) ((*t))] & (unsigned short int)
 _ISdigit); t++)
;
ndig = t-s;

if (end) *end = t;
/*
* If safe, compute as a C integer.
*/
if (ndig <= dim) {
for (n = 0; s != t; s++) n = 10*n + *s - '0';
if (isNeg) n = -n;
return IntToBInt(n)((BInt) ((Pointer)(((((long)(n)) << 1) | 1))));
}

/*
* Over-estimate number of bits by multiplying by 4, rather than
* log(10)/log(2) < 3.322.
*/
b = bintAlloc(4*ndig);

/*
* Convert radix by interpreting string as a poly in radix "rio"
* and evaluating using Horner's rule.
*/
l0 = ndig % dio;
for (n = 0, l = l0; l > 0; l--) n = 10*n + *s++ - '0';
b = xintCopyInI(b, n);

for (ndig -= l0; ndig > 0; ndig -= dio) {
for (n = 0, l = dio; l > 0; l--) n = 10*n + *s++ - '0';
iintTimesPlusS(b, b, (BIntS) rio, (BIntS) n);
}

IsNeg(b)((b)->isNeg) = isNeg;

b = xintImmedIfCan(b);

return b;
713}


716/****************************************************************************
*
* :: Basic Allocation
*
****************************************************************************/

722BInt
723bintAllocPlaces(Length placea)
724{
BInt 	b;
b = (BInt) stoAlloc(OB_BInt2, fullsizeof(*b, placea, Placev(b)[0])(sizeof(*b) + (placea) * sizeof(((b)->placev)[0]) - 10 * sizeof
(((b)->placev)[0])));
Placea(b)((b)->placea) = placea;
Placec(b)((b)->placec) = placea;
IsNeg(b)((b)->isNeg)  = false((int) 0);

return b;
732}

734BInt
735bintAlloc(Length bitc)
736{
return bintAllocPlaces(QUO_ROUND_UP(bitc, BINT_LG_RADIX)((bitc) % (((8 * sizeof(BIntS)))) ? (bitc)/(((8 * sizeof(BIntS
)))) + 1 : (bitc)/(((8 * sizeof(BIntS))))));
738}

740void
741bintFree(BInt b)
742{
if (IsImmed(b)((long)(b) & 1)) return;

stoFree((Pointer) b);
746}

748BInt
749bintNew(long n)
750{
if (INT_IS_IMMED(n)(((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)<= (long
)(n) && (long)(n)<= (- (long) ((((IInt) 3) <<
 ((8 * sizeof(IInt))-2)) + 1)))) return IntToBInt(n)((BInt) ((Pointer)(((((long)(n)) << 1) | 1))));

return xintStoreI(n);
754}

756BInt
757bintCopy(BInt bo)
758{
BInt	bn;
Length	i, c;

if (IsImmed(bo)((long)(bo) & 1)) return bo;

c  = Placec(bo)((bo)->placec);
bn = bintAllocPlaces(c);

for (i = 0; i < c; i++) Placev(bn)((bn)->placev)[i] = Placev(bo)((bo)->placev)[i];
IsNeg(bn)((bn)->isNeg) = IsNeg(bo)((bo)->isNeg);

return bn;
771}

773BInt
774bintFrPlacev(Bool isNeg, Length placec, BIntS *data)
775{
BInt	bint;
int	i;

bint = bintAllocPlaces(placec);
IsNeg(bint)((bint)->isNeg) = isNeg;

for (i = placec - 1; i >= 0 && data[i] == 0; i--) ;

Placec(bint)((bint)->placec) = i+1;

for (; i >= 0; i--)
Placev(bint)((bint)->placev)[i] = data[i];
return xintImmedIfCan(bint);
789}

791#if (U16sPerUNotAsLong2 == 1)
792BInt
793bintFrPlacevS(Bool isNeg, Length placec, U16 *data)
794{
return bintFrPlacev(isNeg, placec, (BIntS*) data);
796}

798void
799bintToPlacevS(BInt b, int *psize, U16 **pdata)
800{
*psize = b->placec;
*pdata = b->placev;
803}

805void
806bintReleasePlacevS(U16 *pdata)
807{
808}
809#endif

811#if (U16sPerUNotAsLong2 == 2)
812BInt
813bintFrPlacevS(Bool isNeg, Length placec, U16 *data)
814{
BInt  bint;
BIntS *bint_data;  
int   newc, i;

if (placec & 1)
bint_data = (BIntS*) data;
else
bint_data = (BIntS*) stoAlloc(OB_Other0, sizeof(BIntS) * (placec + 1));
newc = (placec+1)/2;
for (i = 0; i < newc-1; i++) 
bint_data[i] = data[2*i] + (data[2*i+1] << bitsizeof(U16)(8 * sizeof(U16)));
bint_data[i] = (placec & 1) ? 
data[2*i] :
data[2*i] + (data[2*i+1] << bitsizeof(U16)(8 * sizeof(U16)));

bint = bintFrPlacev(isNeg, newc, bint_data);

if (!(placec & 1))
stoFree(bint_data);
return bint;
835}

837void
838bintToPlacevS(BInt b, int *psize, U16 **pdata)
839{
BInt   oldb;
U16    *data;	
int    placec;
int    i;

oldb = b;
b = xintStore(b);
placec = b->placec;

data = (U16*) stoAlloc(OB_Other0, 2*placec*sizeof(U16));

for (i=0; i < placec; i++) {
data[2*i]   =  b->placev[i] & 0x0000FFFF;
data[2*i+1] = (b->placev[i] & 0xFFFF0000) >> 16;
}

if (data[2*placec - 1] == 0)
*psize = 2*placec - 1;
else 
*psize = 2*placec;
*pdata = data;

if (oldb != b) 
bintFree(b);
864}

866void
867bintReleasePlacevS(U16 *data)
868{
stoFree(data);
870}
871#endif

873/****************************************************************************
*
* :: Small integers
*
****************************************************************************/

879Bool
880bintIsSmall(BInt b)
881{
return IsImmed(b)((long)(b) & 1);
883}

885long
886bintSmall(BInt b)
887{
return BIntToInt(b)((IInt) ((((long) (b))) >> 1));
889}


892/****************************************************************************
*
* :: General arithmetic
*
****************************************************************************/
897localstatic BInt 	bintModi	(BInt, unsigned long);
898localstatic ULong 	bintToULong	(BInt);

900/*
* Special values
*/
903BInt	bint0 = BIntZero((BInt) ((((long)(0)) << 1) | 1));
904BInt	bint1 = BIntOne((BInt) ((((long)(1)) << 1) | 1));

906/*
* b < 0 ?
*/
909Bool
910bintIsNeg(BInt b)
911{
if (IsImmed(b)((long)(b) & 1))	return BIntToInt(b)((IInt) ((((long) (b))) >> 1)) < 0;

return IsNeg(b)((b)->isNeg);
915}

917/*
* b == 0 ?
*/
920Bool
921bintIsZero(BInt b)
922{
return IsImmed(b)((long)(b) & 1) && BIntToInt(b)((IInt) ((((long) (b))) >> 1)) == 0;
924}

926/*
* b > 0 ?
*/
929Bool
930bintIsPos(BInt b)
931{
if (IsImmed(b)((long)(b) & 1))	return BIntToInt(b)((IInt) ((((long) (b))) >> 1)) > 0;

return Placec(b)((b)->placec) > 0 && !IsNeg(b)((b)->isNeg);
935}

937/*
* a == b ?
*/
940Bool
941bintEQ(BInt a, BInt b)
942{
Bool	aImmed, bImmed;
IInt	i, c;

if (Beq(a,b)((a) == (b))) return true1;

aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed    && bImmed)    return BIntToInt(a)((IInt) ((((long) (a))) >> 1)) == BIntToInt(b)((IInt) ((((long) (b))) >> 1));
if (aImmed    != bImmed)    return false((int) 0);
if (IsNeg(a)((a)->isNeg)  != IsNeg(b)((b)->isNeg))  return false((int) 0);
if (Placec(a)((a)->placec) != Placec(b)((b)->placec)) return false((int) 0);

c = Placec(a)((a)->placec);

for (i = 0; i < c; i++)
if (Placev(a)((a)->placev)[i] != Placev(b)((b)->placev)[i]) return false((int) 0);
return true1;
961}

963/*
* a < b ?
*/
966Bool
967bintLT(BInt a, BInt b)
968{
Bool	aImmed, bImmed;
IInt	i, c;

if (Beq(a,b)((a) == (b))) return false((int) 0);

aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed && bImmed)      return BIntToInt(a)((IInt) ((((long) (a))) >> 1)) < BIntToInt(b)((IInt) ((((long) (b))) >> 1));
if (aImmed)	           return !IsNeg(b)((b)->isNeg);
if (bImmed)	           return IsNeg(a)((a)->isNeg);
if (IsNeg(a)((a)->isNeg) != IsNeg(b)((b)->isNeg))  return IsNeg(a)((a)->isNeg) && !IsNeg(b)((b)->isNeg);

if (IsNeg(a)((a)->isNeg)) {
if (Placec(a)((a)->placec)!= Placec(b)((b)->placec)) return Placec(a)((a)->placec) > Placec(b)((b)->placec);
c = Placec(a)((a)->placec);
for (i = c-1; i >= 0; i--) {
	if (Placev(a)((a)->placev)[i] == Placev(b)((b)->placev)[i]) continue;
	return Placev(a)((a)->placev)[i] > Placev(b)((b)->placev)[i];
}
return false((int) 0);
}
else {
if (Placec(a)((a)->placec)!= Placec(b)((b)->placec)) return Placec(a)((a)->placec) < Placec(b)((b)->placec);
c = Placec(a)((a)->placec);
for (i = c-1; i >= 0; i--) {
	if (Placev(a)((a)->placev)[i] == Placev(b)((b)->placev)[i]) continue;
	return Placev(a)((a)->placev)[i] < Placev(b)((b)->placev)[i];
}
return false((int) 0);
}
1000}

1002/*
* a > b ?
*/
1005Bool
1006bintGT(BInt a, BInt b)
1007{
Bool	aImmed, bImmed;
IInt	i, c;

if (Beq(a,b)((a) == (b))) return false((int) 0);

aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed && bImmed)      return BIntToInt(a)((IInt) ((((long) (a))) >> 1)) > BIntToInt(b)((IInt) ((((long) (b))) >> 1));
if (aImmed)	           return IsNeg(b)((b)->isNeg);
if (bImmed)	           return !IsNeg(a)((a)->isNeg);
if (IsNeg(a)((a)->isNeg) != IsNeg(b)((b)->isNeg))  return !IsNeg(a)((a)->isNeg) && IsNeg(b)((b)->isNeg);

if (IsNeg(a)((a)->isNeg)) {
if (Placec(a)((a)->placec)!= Placec(b)((b)->placec)) return Placec(a)((a)->placec) < Placec(b)((b)->placec);
c = Placec(a)((a)->placec);
for (i = c-1; i >= 0; i--) {
	if (Placev(a)((a)->placev)[i] == Placev(b)((b)->placev)[i]) continue;
	return Placev(a)((a)->placev)[i] < Placev(b)((b)->placev)[i];
}
return false((int) 0);
}
else {
if (Placec(a)((a)->placec)!= Placec(b)((b)->placec)) return Placec(a)((a)->placec) > Placec(b)((b)->placec);
c = Placec(a)((a)->placec);
for (i = c-1; i >= 0; i--) {
	if (Placev(a)((a)->placev)[i] == Placev(b)((b)->placev)[i]) continue;
	return Placev(a)((a)->placev)[i] > Placev(b)((b)->placev)[i];
}
return false((int) 0);
}
1039}

1041/*
* Form a new value equal to the absolute value of a.
*/
1044BInt
1045bintAbs(BInt a)
1046{
BInt	r;

if (IsImmed(a)((long)(a) & 1)) {
r = (BIntToInt(a)((IInt) ((((long) (a))) >> 1)) < 0) ? bintNew(-BIntToInt(a)((IInt) ((((long) (a))) >> 1))) : a;
}
else {
r = bintCopy(a);
IsNeg(r)((r)->isNeg) = false((int) 0);
}
return r;
1057}

1059/*
* Form a new value equal to -a.
*/
1062BInt
1063bintNegate(BInt a)
1064{
BInt 	r;

if (IsImmed(a)((long)(a) & 1)) return IntToBInt(-BIntToInt(a))((BInt) ((Pointer)(((((long)(-((IInt) ((((long) (a))) >>
 1)))) << 1) | 1))));

r = bintCopy(a);
IsNeg(r)((r)->isNeg) = !IsNeg(r)((r)->isNeg);
return r;
1072}

1074#define BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); } \
{ if (IsImmed(r)((long)(r) & 1)) (r) = IntToBInt(-BIntToInt(r))((BInt) ((Pointer)(((((long)(-((IInt) ((((long) (r))) >>
 1)))) << 1) | 1)))); else IsNeg(r)((r)->isNeg) = !IsNeg(r)((r)->isNeg); }

1077/*
* Add a and b to produce a newly allocated result.
*/
1080BInt
1081bintPlus(BInt a, BInt b)
1082{
BInt	r;
Bool	aImmed, bImmed, rImmed, aNeg, bNeg;
IInt	abitc, bbitc, rbitc;

/* Small integer case. */
aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed && bImmed) {
IInt     ai = BIntToInt(a)((IInt) ((((long) (a))) >> 1));
IInt	 bi = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
IInt	 ki, ri;
PlusStep(ki,ri, ai, bi, int0){ BIntD r_ = (BIntD)(ai)+(BIntD)(bi)+(BIntD)(((int) 0)); BIntS
 k_ = (r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof
(BIntS))))); if (k_) r_ -= (((unsigned long) 1) << ((8 *
 sizeof(BIntS)))); (ri) = r_; (ki) = k_; };
if (ki == 0 && INT_IS_IMMED(ri)(((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)<= (long
)(ri) && (long)(ri)<= (- (long) ((((IInt) 3) <<
 ((8 * sizeof(IInt))-2)) + 1)))) return IntToBInt(ri)((BInt) ((Pointer)(((((long)(ri)) << 1) | 1))));
}

if (aImmed) a = xintStore(a);
if (bImmed) b = xintStore(b);

aNeg   = bintIsNeg(a);
bNeg   = bintIsNeg(b);

if (aNeg && bNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintPlus(a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else if (aNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
r = bintMinus(b, a);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
}
else if (bNeg) {
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintMinus(a, b);
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
}
else {
/* General case. */
abitc = bintLength(a);
bbitc = bintLength(b);

if (abitc < bbitc) {
	r = a; rbitc = abitc; rImmed = aImmed;
	a = b; abitc = bbitc; aImmed = bImmed;
	b = r; bbitc = rbitc; bImmed = rImmed;
}

rbitc = abitc + 1; /* +1 for potential carry */

r = bintAlloc(rbitc);

iintPlus(r, a, b);

r = xintImmedIfCan(r);
}

if (aImmed) bintFree(a);
if (bImmed) bintFree(b);
return r;
1144}

1146/*
* Subtract b from a to produce a newly allocated result.
*/
1149BInt
1150bintMinus(BInt a, BInt b)
1151{
BInt	r;
Bool	aImmed, bImmed, rImmed, aNeg, bNeg, rNeg;

/* Small integer case. */
aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed && bImmed) {
IInt     ai = BIntToInt(a)((IInt) ((((long) (a))) >> 1));
IInt	 bi = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
IInt	 ri = ai - bi;
if (INT_IS_IMMED(ri)(((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)<= (long
)(ri) && (long)(ri)<= (- (long) ((((IInt) 3) <<
 ((8 * sizeof(IInt))-2)) + 1)))) return IntToBInt(ri)((BInt) ((Pointer)(((((long)(ri)) << 1) | 1))));
}

if (aImmed) a = xintStore(a);
if (bImmed) b = xintStore(b);

aNeg   = bintIsNeg(a);
bNeg   = bintIsNeg(b);

if (aNeg && bNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintMinus(b, a);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
}
else if (aNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
r = bintPlus(a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else if (bNeg) {
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintPlus(a, b);
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
}
else {
/* General case. */

/* If a < b, compute -(b-a). */
rNeg = bintLT(a, b);
if (rNeg) {
	r = a; rImmed = aImmed;
	a = b; aImmed = bImmed;
	b = r; bImmed = rImmed;
}

r = bintAllocPlaces(Placec(a)((a)->placec));

iintMinus(r, a, b);
IsNeg(r)((r)->isNeg) = rNeg;

r = xintImmedIfCan(r);
}

if (aImmed) bintFree(a);
if (bImmed) bintFree(b);

return r;
1211}

1213/*
* Multiply a and b to produce a newly allocated result.
*/
1216BInt
1217bintTimes(BInt a, BInt b)
1218{
BInt	r;
Bool	aImmed, bImmed, aNeg, bNeg;
IInt	ac, bc, rc;

/* Small integer case. */
aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed && bImmed) {
IInt     ai = BIntToInt(a)((IInt) ((((long) (a))) >> 1));
IInt	 bi = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
if (INT_IS_HALF(ai)((-((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1)) <=
 (long)(ai) && (long)(ai)<= ((((IInt) 1)<<((
((8 * sizeof(IInt))-2)/2))) -1)) && INT_IS_HALF(bi)((-((((IInt) 1)<<((((8 * sizeof(IInt))-2)/2))) -1)) <=
 (long)(bi) && (long)(bi)<= ((((IInt) 1)<<((
((8 * sizeof(IInt))-2)/2))) -1))) return bintNew(ai*bi);
}
if (aImmed) {
IInt      ai = BIntToInt(a)((IInt) ((((long) (a))) >> 1));
if (ai == 0)	return IntToBInt(int0)((BInt) ((Pointer)(((((long)(((int) 0))) << 1) | 1))));
if (ai == 1)	return bintCopy(b);
if (ai ==-1)	return bintNegate(b);
}
if (bImmed) {
IInt      bi = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
if (bi == 0)	return IntToBInt(int0)((BInt) ((Pointer)(((((long)(((int) 0))) << 1) | 1))));
if (bi == 1)	return bintCopy(a);
if (bi ==-1)	return bintNegate(a);
}

if (aImmed) a = xintStore(a);
if (bImmed) b = xintStore(b);

aNeg   = bintIsNeg(a);
bNeg   = bintIsNeg(b);

if (aNeg && bNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintTimes(a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
}
else if (aNeg) {
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
r = bintTimes(a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else if (bNeg) {
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
r = bintTimes(a, b);
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else {
/* General case. */

ac = Placec(a)((a)->placec);
bc = Placec(b)((b)->placec);
rc = ac + bc;

r = bintAllocPlaces(rc);

iintTimes(r, a, b);

r = xintImmedIfCan(r);
}

if (aImmed) bintFree(a);
if (bImmed) bintFree(b);

return r;
1286}


1289/*
* Divide a by b to produce a newly allocated quotient as the result.
* If the pointer pr != 0, then a newly allocated remainder is returned via it.
*/
1293BInt
1294bintDivide(BInt *pr, BInt a, BInt b)
1295{
BInt	q, r;
Bool	aImmed, bImmed, aNeg, bNeg;
IInt	n, m;

/* Small integer case not yet handled. */
aImmed = IsImmed(a)((long)(a) & 1);
bImmed = IsImmed(b)((long)(b) & 1);

if (aImmed) a = xintStore(a);
if (bImmed) b = xintStore(b);

aNeg   = bintIsNeg(a);
bNeg   = bintIsNeg(b);

if (aNeg && bNeg) {
/* (q,r) = divide(-a,-b);  if (r != 0) {q++; r = b-r;} */
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
q = bintDivide(&r, a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); }; if (!Beq(a,b)((a) == (b))) BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };

BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else if (aNeg) {
/* (q,r) = divide(-a,b); q = -q-1; r = b-r; */
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };
q = bintDivide(&r, a, b);
BINT_NEGATE(a){ if (((long)(a) & 1)) (a) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (a))) >> 1)))) << 1) | 1))));
 else ((a)->isNeg) = !((a)->isNeg); };

BINT_NEGATE(q){ if (((long)(q) & 1)) (q) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (q))) >> 1)))) << 1) | 1))));
 else ((q)->isNeg) = !((q)->isNeg); };
BINT_NEGATE(r){ if (((long)(r) & 1)) (r) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (r))) >> 1)))) << 1) | 1))));
 else ((r)->isNeg) = !((r)->isNeg); };
}
else if (bNeg) {
/* (q,r) = divide(a,-b); q = -q; */
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };
q = bintDivide(&r, a, b);
BINT_NEGATE(b){ if (((long)(b) & 1)) (b) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (b))) >> 1)))) << 1) | 1))));
 else ((b)->isNeg) = !((b)->isNeg); };

BINT_NEGATE(q){ if (((long)(q) & 1)) (q) = ((BInt) ((Pointer)(((((long)
(-((IInt) ((((long) (q))) >> 1)))) << 1) | 1))));
 else ((q)->isNeg) = !((q)->isNeg); };
}
else {
/* General case. */

n = Placec(b)((b)->placec);
m = Placec(a)((a)->placec) - n; if (m < 0) m = 0;

q = bintAllocPlaces(m+1);
r = bintAllocPlaces(n+m+1);

iintDivide(q, r, a, b);	/*!! Should shrink r here. */

q = xintImmedIfCan(q);
r = xintImmedIfCan(r);
}

if (aImmed) bintFree(a);
if (bImmed) bintFree(b);

if (pr) *pr = r; else bintFree(r);
return q;
1355}

1357BInt
1358bintMod(BInt a, BInt b)
1359{
BInt r, q;
Bool neg;
/*
* Compute a mod b via horner's rule if b fits into a single word,
* use bintDivide o/wise.
*/
neg = bintIsNeg(a);
if (neg)
a = bintNegate(a);

if (bintIsNeg(b))
b = bintNegate(b);

if (IsImmed(b)((long)(b) & 1)) {
r = bintModi(a, (ULong) BIntToInt(b)((IInt) ((((long) (b))) >> 1)));
} 
else if (bintLength(b) < bitsizeof(ULong)(8 * sizeof(ULong))) {
/* Can't handle 32 bit divisors as yet! */
r = bintModi(a, bintToULong(b));
}
else {
q = bintDivide(&r, (BInt) a, (BInt) b);
bintFree(q);
}
if (neg)
r = xintNegate(r);

return r;
1388}

1390localstatic BInt
1391bintModi(BInt a, ULong b)
1392{
ULong   d    = 1L << bitsizeof(BIntS)(8 * sizeof(BIntS));
ULong  r;
ULong acc;
int   i;

assert(!bintIsNeg(a))do { if (!(!bintIsNeg(a))) _do_assert(("!bintIsNeg(a)"),"bigint.c"
,1398); } while (0);

if (IsImmed(a)((long)(a) & 1)) {
return bintNew(BIntToInt(a)((IInt) ((((long) (a))) >> 1)) % b);
}

if (b < d) {
d = d % b;
i = Placec(a)((a)->placec) - 1;
acc = Placev(a)((a)->placev)[i] % b;
i--;
while (i>=0) {
	long tmp;
	/* acc = acc mod* d mod+ a[i] */
	acc = (acc * d) % b;
	tmp = acc - b + Placev(a)((a)->placev)[i] % b;
	if (tmp < 0) tmp += b; 
	acc = tmp;
	i--;
}
}
else {
/* b larger than 1 halfword */
i = Placec(a)((a)->placec) - 1;
acc = Placev(a)((a)->placev)[i];
i--;
while (i>=0) {
	/* acc = acc mod* d mod+ a[i] */
	ULong hi, lo, rem;
	long  tmp;
	/*xxTimesDouble(&hi, &lo, acc, d);*/
	hi = acc >> bitsizeof(BIntS)(8 * sizeof(BIntS));
	lo = acc << bitsizeof(BIntS)(8 * sizeof(BIntS));
	rem = xxModDouble(hi, lo, b);
	tmp = (rem - (long) b) + Placev(a)((a)->placev)[i];
	if (tmp < 0) 
		tmp += b;
	acc = tmp;
	i--;
}
}
r = acc;
return bintNew(r);
1441}

1443localstatic ULong
1444bintToULong(BInt b)
1445{
ULong res;
if (bintIsSmall(b))
return bintSmall(b);

res = (ULong) Placev(b)((b)->placev)[0] + ( ((ULong) Placev(b)((b)->placev)[1]) << bitsizeof(BIntS)(8 * sizeof(BIntS)));

return res;
1453}

1455/*
* The length of b, in bits. I.e. cieling(lg(abs(b))).
* Define the bit length of zero to be one bit.
*/
1459Length
1460bintLength(BInt b)
1461{
Length res;
if (IsImmed(b)((long)(b) & 1)) return intLength(BIntToInt(b)((IInt) ((((long) (b))) >> 1)));
res = BINT_LG_RADIX((8 * sizeof(BIntS)))*(Placec(b)((b)->placec)-1) + uintLength(Placev(b)((b)->placev)[Placec(b)((b)->placec)-1]);
return res;
1466}


1469/*
* Extract the ix-th bit of b.  I.e. the coef of 2**ix.
* !! This should handle negative numbers.
*/
1473Bool
1474bintBit(BInt b, Length ix)
1475{
Length	cq, cr;

if (IsImmed(b)((long)(b) & 1)) return intBit(BIntToInt(b)((IInt) ((((long) (b))) >> 1)), ix);

cq = ix / BINT_LG_RADIX((8 * sizeof(BIntS)));
cr = ix % BINT_LG_RADIX((8 * sizeof(BIntS)));

return (cq < Placec(b)((b)->placec)) && (Placev(b)((b)->placev)[cq] & (1<<cr)) != 0;
1484}

1486/*
* Shift b by n bits.  I.e. compute b*2**n.
*/
1489BInt
1490bintShift(BInt b, int n)
1491{
BInt	r;
IInt	bbitc, rbitc;
Bool	bImmed;

bImmed = IsImmed(b)((long)(b) & 1);
bbitc  = bintLength(b);
rbitc  = bbitc + n;

if (b == bint0) return bint0;
2
←
Assuming 'b' is not equal to 'bint0'→
if (bbitc == 0 || rbitc <= 0)
3
←
Assuming 'bbitc' is not equal to 0→
4
←
Assuming 'rbitc' is > 0→
return IntToBInt(int0)((BInt) ((Pointer)(((((long)(((int) 0))) << 1) | 1))));
if (bImmed && rbitc <= INT_LG_IMMED((8 * sizeof(IInt))-2)) {
5
←
Assuming 'bImmed' is 0→
IInt      i = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
UIInt     u = (i > 0) ? i : -i;
u = (n > 0) ? u << n : u >> -n;
return IntToBInt((i > 0) ? u : -(IInt)u)((BInt) ((Pointer)(((((long)((i > 0) ? u : -(IInt)u)) <<
 1) | 1))));
}
if (bImmed5.1
'bImmed' is 0
) b = xintStore(b);
6
←
Taking false branch→
r = bintAlloc(rbitc);

iintShift(r, b, n);
7
←
Calling 'iintShift'→

if (bImmed) bintFree(b);
if (rbitc <= INT_LG_IMMED((8 * sizeof(IInt))-2)) r = xintImmedIfCan(r);

return r;
1518}

1520BInt
1521bintShiftRem(BInt b, int n)
1522{
BInt r;
int  i, top;
/* Returns lowest `n' bits from b. */

if (IsImmed(b)((long)(b) & 1)) {
IInt x = BIntToInt(b)((IInt) ((((long) (b))) >> 1));
return IntToBInt(x & ((1 << n) - 1))((BInt) ((Pointer)(((((long)(x & ((1 << n) - 1))) <<
 1) | 1))));
}

r = bintAlloc(n);

for (i=0; i<Placea(r)((r)->placea) - 1; i++) Placev(r)((r)->placev)[i] = Placev(b)((b)->placev)[i];
top = n - BINT_LG_RADIX((8 * sizeof(BIntS)))*(Placec(r)((r)->placec) - 1);
Placev(r)((r)->placev)[i] = Placev(b)((b)->placev)[i] & ((1<< top) - 1);

return xintImmedIfCan(r);
1539}

1541/****************************************************************************
*
* :: Low-level, fine control allocation
*
****************************************************************************/

1547/*
* Allocate a new, stored integer value.
*/
1550BInt
1551xintStoreI(long n)
1552{
BInt	b;
ULong	u;
IInt	a;

u = (n < 0) ? -n : n;
for (a = 1; ; a += 1, u >>= BINT_LG_RADIX((8 * sizeof(BIntS))))
if( u < BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) ) break;
b = bintAllocPlaces(a);
return xintCopyInI(b, n);
1562}

1564/*
* Convert b to a stored representation.
*/
1567BInt
1568xintStore(BInt b)
1569{
if (IsImmed(b)((long)(b) & 1)) return xintStoreI(BIntToInt(b)((IInt) ((((long) (b))) >> 1)));

return b;
1573}

1575/*
* Convert b to an immeditate (non-stored) representation, if possible.
*/
1578BInt
1579xintImmedIfCan(BInt b)
1580{
Length	pb;
ULong	u = 0;

if (IsImmed(b)((long)(b) & 1)) return b;

pb = Placec(b)((b)->placec);

/* Special case all 32-bit cases */
if (pb == 0)
return IntToBInt(int0)((BInt) ((Pointer)(((((long)(((int) 0))) << 1) | 1))));
if (pb == 1 || pb == 2) {
if (pb == 1)
	u = Placev(b)((b)->placev)[0];
else
	u = ((BIntD)(Placev(b)((b)->placev)[1]) << BINT_LG_RADIX((8 * sizeof(BIntS))))
	  + Placev(b)((b)->placev)[0];
if (IsNeg(b)((b)->isNeg))
	return u > -(long)INT_MIN_IMMED((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)
	       ? b : (BInt) ptrFrLong(MkImmed(-(IInt)u))((Pointer)(((((long)(-(IInt)u)) << 1) | 1)));
else
	return u > INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1))
	       ? b : (BInt) ptrFrLong(MkImmed(u))((Pointer)(((((long)(u)) << 1) | 1)));
}


/* For cases where 2*sizeof(BIntS) < sizeof(BInt) 	*/
if (pb*BINT_LG_RADIX((8 * sizeof(BIntS))) <= bitsizeof(IInt)(8 * sizeof(IInt))) {
int 	i;
for (i = pb - 1; i>= 0; i--)
	u = (u << BINT_LG_RADIX((8 * sizeof(BIntS)))) + Placev(b)((b)->placev)[i];
if (IsNeg(b)((b)->isNeg))
        return (u > -INT_MIN_IMMED((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1)) ? b 
		: (BInt) ptrFrLong(MkImmed(-u))((Pointer)(((((long)(-u)) << 1) | 1)));
else
        return (u > INT_MAX_IMMED(- (long) ((((IInt) 3) << ((8 * sizeof(IInt))-2)) + 1))) ? b 
		: (BInt) ptrFrLong(MkImmed(u))((Pointer)(((((long)(u)) << 1) | 1)));
}

return b;
1620}

1622/*
* Place integer value n into stored BInt b.
* If b is not big enough, then it is reallocated.
*/
1626BInt
1627xintCopyInI(BInt b, long n)
1628{
ULong u, ut;
IInt	i, c, a;
assert(!IsImmed(b))do { if (!(!((long)(b) & 1))) _do_assert(("!IsImmed(b)"),
"bigint.c",1631); } while (0);

u = (n<0)? -n : n;
c = Placea(b)((b)->placea);

/* Quick test for usual case. */
if (u < BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS)))) && c > 0) {
Placev(b)((b)->placev)[0] = u;
Placec(b)((b)->placec)    = 1;
IsNeg(b)((b)->isNeg) = (n < 0);
return b;
}

/* Multi-word case */
ut = u; for (a = 0; ut != 0; a++) ut /= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));

if (a > c) {
bintFree(b);
b = bintAllocPlaces(a);
c = a;
}
for (i = 0; u != 0 && i < c; i++) {
Placev(b)((b)->placev)[i] = u % BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));
u            = u / BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))));
}
Placec(b)((b)->placec)     = i;

IsNeg(b)((b)->isNeg) = (n < 0);
return b;
1660}


1663/*
* Ensure b can contain at least bitc bits.
*/
1666BInt
1667xintNeeds(BInt b, Length bitc)
1668{
BInt	bn;
Length	i, c;

if (IsImmed(b)((long)(b) & 1)) {
 if (bitc <= INT_LG_IMMED((8 * sizeof(IInt))-2))
	return b;
else
	return xintCopyInI(bintAlloc(bitc), BIntToInt(b)((IInt) ((((long) (b))) >> 1)));
}

if (Placea(b)((b)->placea)*BINT_LG_RADIX((8 * sizeof(BIntS))) >= bitc) return b;

bn = bintAlloc(bitc);
c  = Placec(b)((b)->placec);
for (i = 0; i < c; i++) Placev(bn)((bn)->placev)[i] = Placev(b)((b)->placev)[i];
Placec(bn)((bn)->placec) = Placec(b)((b)->placec);
IsNeg(bn)((bn)->isNeg)  = IsNeg(b)((b)->isNeg);
bintFree(b);

return bn;
1689}


1692/*
* Operations which free their operands.
*/
1695int
1696xintPrint(FILE *fout, BInt a)
1697{
int cc = bintPrint(fout, a);
bintFree(a);
return cc;
1701}

1703int
1704xintPrint2(FILE *fout, BInt a)
1705{
int cc = bintPrint2(fout, a);
bintFree(a);
return cc;
1709}

1711int
1712xintPrint16(FILE *fout, BInt a)
1713{
int cc = bintPrint16(fout, a);
bintFree(a);
return cc;
1717}

1719BInt
1720xintNegate(BInt a)
1721{
BInt r = bintNegate(a);
bintFree(a);
return r;
1725}

1727BInt
1728xintPlus(BInt a, BInt b)
1729{
BInt r = bintPlus(a, b);
bintFree(a);
bintFree(b);
return r;
1734}

1736BInt
1737xintMinus(BInt a, BInt b)
1738{
BInt r = bintMinus(a, b);
bintFree(a);
bintFree(b);
return r;
1743}

1745BInt
1746xintTimes(BInt a, BInt b)
1747{
BInt r = bintTimes(a, b);
bintFree(a);
bintFree(b);
return r;
1752}

1754BInt
1755xintDivide(BInt *pr, BInt a, BInt b)
1756{
BInt q = bintDivide(pr, a, b);
bintFree(a);
bintFree(b);
return q;
1761}

1763BInt
1764xintShift(BInt a, int n)
1765{
BInt r = bintShift(a, n);
1
Calling 'bintShift'→
bintFree(a);
return r;
1769}

1771/*****************************************************************************
*
* :: Low-level, non-allocating operations
*
* Arithmetic is done with the macros PlusStep, TimesDouble, etc.
*
****************************************************************************/

1779/*
* Place the value abs(a) in r.
*/
1782void
1783iintAbs(BInt r, BInt a)
1784{
IInt	i, c;

assert(!IsImmed(r) && !IsImmed(a) && Placea(r)>=Placec(a))do { if (!(!((long)(r) & 1) && !((long)(a) & 1
) && ((r)->placea)>=((a)->placec))) _do_assert
(("!IsImmed(r) && !IsImmed(a) && Placea(r)>=Placec(a)"
),"bigint.c",1787); } while (0);

IsNeg(r)((r)->isNeg) = false((int) 0);

if (Beq(r,a)((r) == (a))) return;

c = Placec(a)((a)->placec);

for (i = 0; i < c; i++) Placev(r)((r)->placev)[i] = Placev(a)((a)->placev)[i];
Placec(r)((r)->placec) = Placec(a)((a)->placec);
1797}

1799/*
* Place the value -a in r.
*/
1802void
1803iintNegate(BInt r, BInt a)
1804{
IInt	i, c;

assert(!IsImmed(r) && !IsImmed(a) && Placea(r)>=Placec(a))do { if (!(!((long)(r) & 1) && !((long)(a) & 1
) && ((r)->placea)>=((a)->placec))) _do_assert
(("!IsImmed(r) && !IsImmed(a) && Placea(r)>=Placec(a)"
),"bigint.c",1807); } while (0);

IsNeg(r)((r)->isNeg) = !IsNeg(a)((a)->isNeg);

if (Beq(r,a)((r) == (a))) return;

c = Placec(a)((a)->placec);

for (i = 0; i < c; i++) Placev(r)((r)->placev)[i] = Placev(a)((a)->placev)[i];
Placec(r)((r)->placec) = Placec(a)((a)->placec);
1817}

1819/*
* Add non-negative integers a and b and place result in preallocated r.
* It is assumed that a is greater than b.
* The result r, can be an alias for a or b.
*/
1824void
1825iintPlus(BInt r, BInt a, BInt b)
1826{
BIntS	s, k;		/* k = 0 or 1 */
IInt	i, ac, bc;

assert(!IsImmed(a) && !IsImmed(b))do { if (!(!((long)(a) & 1) && !((long)(b) & 1
))) _do_assert(("!IsImmed(a) && !IsImmed(b)"),"bigint.c"
,1830); } while (0);
assert(!IsNeg(a) && !IsNeg(b))do { if (!(!((a)->isNeg) && !((b)->isNeg))) _do_assert
(("!IsNeg(a) && !IsNeg(b)"),"bigint.c",1831); } while
 (0);
assert(Placec(a) >= Placec(b))do { if (!(((a)->placec) >= ((b)->placec))) _do_assert
(("Placec(a) >= Placec(b)"),"bigint.c",1832); } while (0);
assert(!IsImmed(r) && Placea(r) >= Placec(a))do { if (!(!((long)(r) & 1) && ((r)->placea) >=
 ((a)->placec))) _do_assert(("!IsImmed(r) && Placea(r) >= Placec(a)"
),"bigint.c",1833); } while (0);

ac = Placec(a)((a)->placec);
bc = Placec(b)((b)->placec);

k = 0;

for (i = 0; i < bc; i++) {
PlusStep(k, s, Placev(a)[i], Placev(b)[i], k){ BIntD r_ = (BIntD)(((a)->placev)[i])+(BIntD)(((b)->placev
)[i])+(BIntD)(k); BIntS k_ = (r_ >= (BIntD) (((unsigned long
) 1) << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (s) = r_; (k) = k_
; };
Placev(r)((r)->placev)[i] = s;
}

for ( ; i < ac && k; i++) {
PlusStep(k, s, Placev(a)[i], int0, k){ BIntD r_ = (BIntD)(((a)->placev)[i])+(BIntD)(((int) 0))+
(BIntD)(k); BIntS k_ = (r_ >= (BIntD) (((unsigned long) 1)
 << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((unsigned long
) 1) << ((8 * sizeof(BIntS)))); (s) = r_; (k) = k_; };
Placev(r)((r)->placev)[i] = s;
}

if (!k && Beq(r,a)((r) == (a))) return;

for ( ; i < ac; i++) {
Placev(r)((r)->placev)[i] = Placev(a)((a)->placev)[i];
}

if (k)
Placev(r)((r)->placev)[i++] = k;

Placec(r)((r)->placec) = i;
1860}

1862/*
* Subtract non-negative integers a and b and place result in preallocated r.
* It is assumed that a >= b >= 0.
* The result r, can be an alias for a or b.
*
* This is Algorithm S of Knuth Volume 2, Section 4.3.1.
*/
1869void
1870iintMinus(BInt r, BInt a, BInt b)
1871{
BIntS	s, kp1;		/* kp1 = k+1. k = 0 or -1 */
IInt	i, ac, bc;

assert(!IsImmed(a) && !IsImmed(b))do { if (!(!((long)(a) & 1) && !((long)(b) & 1
))) _do_assert(("!IsImmed(a) && !IsImmed(b)"),"bigint.c"
,1875); } while (0);
assert(!IsNeg(a) && !IsNeg(b))do { if (!(!((a)->isNeg) && !((b)->isNeg))) _do_assert
(("!IsNeg(a) && !IsNeg(b)"),"bigint.c",1876); } while
 (0);
assert(Placec(a) >= Placec(b))do { if (!(((a)->placec) >= ((b)->placec))) _do_assert
(("Placec(a) >= Placec(b)"),"bigint.c",1877); } while (0);
assert(!IsImmed(r) && Placea(r) >= Placec(a))do { if (!(!((long)(r) & 1) && ((r)->placea) >=
 ((a)->placec))) _do_assert(("!IsImmed(r) && Placea(r) >= Placec(a)"
),"bigint.c",1878); } while (0);

ac = Placec(a)((a)->placec);
bc = Placec(b)((b)->placec);

kp1 = 1;

for (i = 0; i < bc; i++) {
MinusStep(kp1, s, Placev(a)[i], Placev(b)[i], kp1){ BIntD r_ = (BIntD)(((a)->placev)[i])+(BIntD)((((((unsigned
 long) 1) << ((8 * sizeof(BIntS)))) - 1) - (((b)->placev
)[i])))+(BIntD)(kp1); BIntS k_ = (r_ >= (BIntD) (((unsigned
 long) 1) << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((
unsigned long) 1) << ((8 * sizeof(BIntS)))); (s) = r_; (
kp1) = k_; };
Placev(r)((r)->placev)[i] = s;
}

for ( ; i < ac && kp1 == 0; i++) {
MinusStep(kp1, s, Placev(a)[i], int0, kp1){ BIntD r_ = (BIntD)(((a)->placev)[i])+(BIntD)((((((unsigned
 long) 1) << ((8 * sizeof(BIntS)))) - 1) - (((int) 0)))
)+(BIntD)(kp1); BIntS k_ = (r_ >= (BIntD) (((unsigned long
) 1) << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (s) = r_; (kp1) = k_
; };
Placev(r)((r)->placev)[i] = s;
}

if (kp1 == 1 && Beq(r,a)((r) == (a))) goto normalize;

for ( ; i < ac; i++) {
Placev(r)((r)->placev)[i] = Placev(a)((a)->placev)[i];
}

assert(kp1 == 1)do { if (!(kp1 == 1)) _do_assert(("kp1 == 1"),"bigint.c",1901
); } while (0);

1903normalize:
for (i = Placec(a)((a)->placec) - 1; i >= 0; i--)
if (Placev(r)((r)->placev)[i] != 0) break;
Placec(r)((r)->placec) = i+1;
1907}

1909/*
* Multiply non-negative integers a and b and place result in preallocated r.
* The result r, cannot be an alias for a or b.
*/
1913void
1914iintTimes(BInt r, BInt a, BInt b)
1915{
IInt	i, j, ac, bc;
BIntS	k, ai, bj;

assert(!IsImmed(a) && !IsImmed(b))do { if (!(!((long)(a) & 1) && !((long)(b) & 1
))) _do_assert(("!IsImmed(a) && !IsImmed(b)"),"bigint.c"
,1919); } while (0);
assert(!IsNeg(a) && !IsNeg(b))do { if (!(!((a)->isNeg) && !((b)->isNeg))) _do_assert
(("!IsNeg(a) && !IsNeg(b)"),"bigint.c",1920); } while
 (0);
assert(!IsImmed(r) && Placea(r) >= Placec(a)+Placec(b))do { if (!(!((long)(r) & 1) && ((r)->placea) >=
 ((a)->placec)+((b)->placec))) _do_assert(("!IsImmed(r) && Placea(r) >= Placec(a)+Placec(b)"
),"bigint.c",1921); } while (0);

ac = Placec(a)((a)->placec);
bc = Placec(b)((b)->placec);

/* Make a be the longer number to minimize loop cost. */
if (ac < bc) {
BInt x;
IInt  xc;
x = a;	xc = ac;
a = b; 	ac = bc;
b = x;	bc = xc;
}

for (i = 0; i < ac; i++) Placev(r)((r)->placev)[i] = 0;

for (j = 0; j < bc; j++) {
bj  = Placev(b)((b)->placev)[j];
k   = 0;
if (bj != 0) {
	for (i = 0; i < ac; i++) {
		ai = Placev(a)((a)->placev)[i];
		TimesStep(k, Placev(r)[i+j],{ BIntD t_ = (BIntD)(ai)*(BIntD)(bj)+(BIntD)(((r)->placev)
[i+j])+(BIntD)(k); (((r)->placev)[i+j]) = t_ % (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (k) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); }
			  ai, bj, Placev(r)[i+j], k){ BIntD t_ = (BIntD)(ai)*(BIntD)(bj)+(BIntD)(((r)->placev)
[i+j])+(BIntD)(k); (((r)->placev)[i+j]) = t_ % (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (k) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); };
	}
}
Placev(r)((r)->placev)[ac+j] = k;
}
while (Placec(r)((r)->placec) > 0 && Placev(r)((r)->placev)[Placec(r)((r)->placec)-1] == 0) Placec(r)((r)->placec)--;
1950}


1953/*
* Divide the non-negative numbers a and b and place the quotient and
* remainder in the preallocated structures q and r.
*
* The output structure, q, must have space for m+1 digits.
* The output structure, r, must have space for n+m+1 digits
* (unless n = 1 or a < b), even though at most n will be used for output.
*
* The output q may not be an alias for an input.
* The output r can be an alias for the input a.
*
* This is Algorithm D of Knuth Vol 2, Section 4.3.1.
* Note: we index the digits n-1..0 rather than 1..n.
*/

1968/*
* Convert to Knuth's notation.
*/
1971#define KtoI(ki)(n - (ki))	(n   - (ki))
1972#define KtoJu(kj)(nm - (kj))	(nm  - (kj))
1973#define KtoJq(kj)(m - (kj))	(m   - (kj))
1974#define DB		/*Debug*/

1976void
1977iintDivide(BInt q, BInt r, BInt u, BInt v)
1978{
IInt	n, m, nm;
IInt	i;
IInt	ki, kj, kjj;		/* Knuths i + j. */
BIntS	d, qhat, rhat;
BIntS	v1, v2, uj0, uj1, uj2; 	/* Knuth's v1,v2, uj,uj+1,uj+2 */
BIntS	k, kk, vi, ujj, uh, ul;

assert(!IsImmed(u) && !IsImmed(v))do { if (!(!((long)(u) & 1) && !((long)(v) & 1
))) _do_assert(("!IsImmed(u) && !IsImmed(v)"),"bigint.c"
,1986); } while (0);
assert(!IsImmed(q) && !IsImmed(r))do { if (!(!((long)(q) & 1) && !((long)(r) & 1
))) _do_assert(("!IsImmed(q) && !IsImmed(r)"),"bigint.c"
,1987); } while (0);
assert(Placea(r) > Placec(u))do { if (!(((r)->placea) > ((u)->placec))) _do_assert
(("Placea(r) > Placec(u)"),"bigint.c",1988); } while (0);
assert(Placev(v)[Placec(v)-1] != 0)do { if (!(((v)->placev)[((v)->placec)-1] != 0)) _do_assert
(("Placev(v)[Placec(v)-1] != 0"),"bigint.c",1989); } while (0
);
assert(q != r && q != u && q != v && r != v)do { if (!(q != r && q != u && q != v &&
 r != v)) _do_assert(("q != r && q != u && q != v && r != v"
),"bigint.c",1990); } while (0);

n = Placec(v)((v)->placec);
m = Placec(u)((u)->placec) - n;
nm = n + m;

/* Copy u into r as an in-place work area. */
if (r != u) {
for (i = 0; i < nm; i++) Placev(r)((r)->placev)[i] = Placev(u)((u)->placev)[i];
Placec(r)((r)->placec) = nm;
u = r;
}

/* Trivial case: v has 1 digit. */
if (n == 1) {
iintDivideS(q, &rhat, u, Placev(v)((v)->placev)[0]);
Placev(u)((u)->placev)[0] = rhat;
Placec(u)((u)->placec) = 1;
return;
}

/* Trivial case: u < v => q = 0, r = u. */
if (bintLT(u,v)) {
Placec(q)((q)->placec) = 0;
return;
}

/*
* D1. Normalize: choose d which results in v[n-1] >= BINT_RADIX/2.
*/
v1= Placev(v)((v)->placev)[KtoI(1)(n - (1))];
if (v1 >= BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))))/2) {
bintDEBUGif (!((int) 0)) { } else fprintf(dbOut, "**** d = 1 ****\n");
d = 1;
}
else {
d = BINT_RADIX(((unsigned long) 1) << ((8 * sizeof(BIntS))))/(v1 + 1);
iintTimesS(u, u, d);
iintTimesS(v, v, d);	/* Guaranteed ptr u != v */
}
v1= Placev(v)((v)->placev)[KtoI(1)(n - (1))];
v2= Placev(v)((v)->placev)[KtoI(2)(n - (2))];
if (Placec(u)((u)->placec) == nm) {
Placev(u)((u)->placev)[Placec(u)((u)->placec)++] = 0;
}
assert(Placec(u) == nm+1)do { if (!(((u)->placec) == nm+1)) _do_assert(("Placec(u) == nm+1"
),"bigint.c",2035); } while (0);
assert(Placec(v) == n)do { if (!(((v)->placec) == n)) _do_assert(("Placec(v) == n"
),"bigint.c",2036); } while (0);

/*
* D2-D7. Each iter, divide u[kj..kj+n] by v[1..n] to get a digit of q.
*/
for (kj = 0; kj <= m; kj++) {
/*
 * D3. Compute qhat.
 */
uj0 = Placev(u)((u)->placev)[KtoJu(kj)(nm - (kj))];
uj1 = Placev(u)((u)->placev)[KtoJu(kj+1)(nm - (kj+1))];
uj2 = Placev(u)((u)->placev)[KtoJu(kj+2)(nm - (kj+2))];

if (uj0 == v1) {
	bintDEBUGif (!((int) 0)) { } else fprintf(dbOut, "**** uj0 == v1 ****\n");
	qhat = BINT_RADIX_MINUS_1((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
	rhat = uj1;
	PlusStep(k, rhat, rhat, v1, int0){ BIntD r_ = (BIntD)(rhat)+(BIntD)(v1)+(BIntD)(((int) 0)); BIntS
 k_ = (r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof
(BIntS))))); if (k_) r_ -= (((unsigned long) 1) << ((8 *
 sizeof(BIntS)))); (rhat) = r_; (k) = k_; };
	
}
else {
	DivideDouble(qhat, rhat, uj0, uj1, v1){ BIntD n_ = (BIntD)(uj0)*(BIntD)(((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) + (uj1); BIntD d_ = (v1); (qhat) = n_
 / d_; (rhat) = n_ % d_; };
	k = 0;
}
if (!k) {
	BIntS	v2qhh, v2qhl;
	Bool	isGT;
	for (i = 1; ; i++) {
		/* Loop shd be evaluated no more than twice. */
		if (DEBUG(bint)((int) 0)) {
			if (i == 2)
				fprintf(dbOut, "**** 2 ****\n");
		}
		assert(i <= 2)do { if (!(i <= 2)) _do_assert(("i <= 2"),"bigint.c",2069
); } while (0);
		/*
		 * This test could be speeded up by doing
		 * unsigned long arithmetic and a comparison
		 * when BINT_LG_RADIX <= bitsizeof(long).
		 * However by writing it this way, this code
		 * could handle a long-sized radix.
		 */
		TimesDouble (v2qhh,v2qhl, v2, qhat){ BIntD t_ = (BIntD)(v2)*(BIntD)(qhat); (v2qhh) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (v2qhl) = t_ % (((
unsigned long) 1) << ((8 * sizeof(BIntS)))); };
		TestGTDouble(isGT, v2qhh,v2qhl, rhat,uj2){ BIntS h1_ = (v2qhh), h2_ = (rhat); (isGT) = (h1_ > h2_) ||
 (h1_ == h2_ && (v2qhl)>(uj2)); };

		if (!isGT) break;

		qhat--;
		PlusStep(k, rhat, rhat, v1, int0){ BIntD r_ = (BIntD)(rhat)+(BIntD)(v1)+(BIntD)(((int) 0)); BIntS
 k_ = (r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof
(BIntS))))); if (k_) r_ -= (((unsigned long) 1) << ((8 *
 sizeof(BIntS)))); (rhat) = r_; (k) = k_; };
		if (k) break;
	}
}
if (DEBUG(bint)((int) 0)) {
	if (k)
		fprintf(dbOut, "**** rhat ov ****\n");
}

/*
 * D4. Multiply and subtract: u[kj..kj+n] -= qhat * (0,v[1..n])
	 */

k = 0;

for (ki = n, kjj = kj+n; ki >= 0; ki--, kjj--) {
	vi  = (ki == 0) ? 0 : Placev(v)((v)->placev)[KtoI(ki)(n - (ki))];
	ujj = Placev(u)((u)->placev)[KtoJu(kjj)(nm - (kjj))];

	TimesDouble(uh, ul, qhat, vi){ BIntD t_ = (BIntD)(qhat)*(BIntD)(vi); (uh) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (ul) = t_ % (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); };

	MinusStep(kk, ujj, ujj, ul, 1){ BIntD r_ = (BIntD)(ujj)+(BIntD)((((((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) - 1) - (ul)))+(BIntD)(1); BIntS k_ = (
r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof(BIntS
))))); if (k_) r_ -= (((unsigned long) 1) << ((8 * sizeof
(BIntS)))); (ujj) = r_; (kk) = k_; };
	uh += !kk;

	MinusStep(kk, ujj, ujj,  k, 1){ BIntD r_ = (BIntD)(ujj)+(BIntD)((((((unsigned long) 1) <<
 ((8 * sizeof(BIntS)))) - 1) - (k)))+(BIntD)(1); BIntS k_ = (
r_ >= (BIntD) (((unsigned long) 1) << ((8 * sizeof(BIntS
))))); if (k_) r_ -= (((unsigned long) 1) << ((8 * sizeof
(BIntS)))); (ujj) = r_; (kk) = k_; };
	uh += !kk;

	Placev(u)((u)->placev)[KtoJu(kjj)(nm - (kjj))] = ujj;
	k = uh;
}

/*
 * D5. Set quotient digit and test remainder.
 */
Placev(q)((q)->placev)[KtoJq(kj)(m - (kj))] = qhat;	/* I.e. Knuth's q[j] */

if (k != 0) {
	/*
	 * D6. Add back: u[kj..kj+n] += (0,v[1..n])
	 */
	bintDEBUGif (!((int) 0)) { } else fprintf(dbOut, "**** Add Back %d ****\n", k);
	Placev(q)((q)->placev)[KtoJq(kj)(m - (kj))]--;
	k = 0;

	for (ki = n, kjj = kj+n; ki >= 0; ki--, kjj--) {
		vi  = (ki == 0) ? 0 : Placev(v)((v)->placev)[KtoI(ki)(n - (ki))];

		PlusStep(k,  Placev(u)[KtoJu(kjj)],{ BIntD r_ = (BIntD)(vi)+(BIntD)(((u)->placev)[(nm - (kjj)
)])+(BIntD)(k); BIntS k_ = (r_ >= (BIntD) (((unsigned long
) 1) << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (((u)->placev)[
(nm - (kjj))]) = r_; (k) = k_; }
			 vi, Placev(u)[KtoJu(kjj)], k){ BIntD r_ = (BIntD)(vi)+(BIntD)(((u)->placev)[(nm - (kjj)
)])+(BIntD)(k); BIntS k_ = (r_ >= (BIntD) (((unsigned long
) 1) << ((8 * sizeof(BIntS))))); if (k_) r_ -= (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (((u)->placev)[
(nm - (kjj))]) = r_; (k) = k_; };
	}
}
}

/*
* D8. Unnormalize: u /= d
*/
Placec(u)((u)->placec) = n;
iintDivideS(u, NULL((void*)0), u, d);
iintDivideS(v, NULL((void*)0), v, d);	/* Return v to original state. */

/* Set place counts to not see leading zeros. */
for (i = Placec(q)((q)->placec)-1; i >= 0; i--)
if (Placev(q)((q)->placev)[i] != 0) break;
Placec(q)((q)->placec) = i+1;

for (i = Placec(u)((u)->placec)-1; i >= 0; i--)
if (Placev(u)((u)->placev)[i] != 0) break;
Placec(u)((u)->placec) = i+1;
2151}

2153/*
* iintShift(r, b, n)
*    Shift b by n bits into r;
*    The result, r, can be an alias for the argument b.
*	
* Examples:
*    BINT_LG_RADIX = 4
*    n    -- number of bits shifted by
*    bitc -- bit count of result
*    c    -- number of places
*    z    -- number of zero bits in leading place
*    up   -- whether position of bits in first place is further up
*    q    -- upward rel offset of first place (not including chopped zeros)
*    q0   -- upward rel offset of first place (including phantom chopped zeros)
*    h    -- upward  rel offset of bits from previous place
*    k    -- downard rel offset of bits within place
*
*                             n bitc  c  z  up q q0  h  k
*      .ooaa.bbbb.0000.0000.  8   14  4  2  n  2  2  4  0
*      .0ooa.abbb.b000.0000.  7   13  4  3  n  2  2  3  1
*           .aabb.bb00.0000.  6   12  3  0  y  1  2  2  2
*           .oaab.bbb0.0000.  5   11  3  1  y  1  2  1  3
*           .ooaa.bbbb.0000.  4   10  3  2  n  1  1  4  0
*           .0ooa.abbb.b000.  3    9  3  3  n  1  1  3  1
*                .aabb.bb00.  2    8  2  0  y  0  1  2  2
*                .oaab.bbb0.  1    7  2  1  y  0  1  1  3
*                .ooaa.bbbb.  0    6  2  2  n  0  0  4  0
*                .0ooa.abbb. -1    5  2  3  n  0  0  3  1
*                     .aabb. -2    4  1  0  y -1  0  1  2
*                     .oaab. -3    3  1  1  y -1  0  3  1
*                     .ooaa. -4    2  1  2  n -1 -1  4  0
*                     .0ooa. -5    1  1  3  n -1 -1  3  1
*                          . -6    0  0  0  y -2 -1  2  2
*/

2188void
2189iintShift(BInt r, BInt b, int n)
2190{
IInt	q, q0, h, k;
IInt	rbitc, rc, rz;
IInt	bbitc, bc, bz;
Bool	up;
IInt	i, j, x0, x1;
BIntS	*rp, *bp;

assert(!IsImmed(r) && !IsImmed(b))do { if (!(!((long)(r) & 1) && !((long)(b) & 1
))) _do_assert(("!IsImmed(r) && !IsImmed(b)"),"bigint.c"
,2198); } while (0);
8
←
Assuming the condition is false→
9
←
Taking true branch→
10
←
Loop condition is false.  Exiting loop→

bbitc = bintLength(b);
bc    = Placec(b)((b)->placec);
bz    = bc * BINT_LG_RADIX((8 * sizeof(BIntS))) - bbitc;
bp    = Placev(b)((b)->placev);

rbitc = bbitc + n;
rc    = QUO_ROUND_UP(rbitc, BINT_LG_RADIX)((rbitc) % (((8 * sizeof(BIntS)))) ? (rbitc)/(((8 * sizeof(BIntS
)))) + 1 : (rbitc)/(((8 * sizeof(BIntS)))));
11
←
Assuming the condition is false→
12
←
'?' condition is false→
rz    = rc * BINT_LG_RADIX((8 * sizeof(BIntS))) - rbitc;
rp    = Placev(r)((r)->placev);

assert(Placea(r) >= rc)do { if (!(((r)->placea) >= rc)) _do_assert(("Placea(r) >= rc"
),"bigint.c",2210); } while (0);
13
←
Assuming 'rc' is <= field 'placea'→
14
←
Taking false branch→
15
←
Loop condition is false.  Exiting loop→
Placec(r)((r)->placec) = rc;
IsNeg(r)((r)->isNeg)  = IsNeg(b)((b)->isNeg);

up = (rz <= bz);
16
←
Assuming 'rz' is > 'bz'→
q  = rc - bc;
q0 = q + up;
h  = q0 * BINT_LG_RADIX((8 * sizeof(BIntS))) - n;
k  = BINT_LG_RADIX((8 * sizeof(BIntS))) - h;
17
←
Value assigned to 'k'→
x0 = 0;			/* for lint */

/*
* Copy in the direction which allows in-place operation.
*
* Each place's value is temporarily held in x0 until
* it is certain that the original value of that place
* will not be needed.
*/

/*
* Would you believe that some compiler have trouble with x<<32 
* MIPS cc on IRIX64 with -64 
*/
if (h == BINT_LG_RADIX((8 * sizeof(BIntS)))) h=0;
18
←
Assuming the condition is false→
19
←
Taking false branch→
if (n < 0) {
20
←
Assuming 'n' is < 0→
21
←
Taking true branch→
/* Copy from lo to hi. */
bp -= q0;
i   = 0;
j   = 0;

if (rc > 1) {
22
←
Assuming 'rc' is > 1→
	x0  = h ? bp[i] >> h : 0;
23
←
Taking true branch→
24
←
Assuming 'h' is 0→
25
←
'?' condition is false→
	x0 |= bp[++i]   << k;
26
←
The result of left shift is undefined because the right operand is >= 32, not smaller than 32, the capacity of 'BIntS'
}
while (i < rc-1) {
	x1  = x0;
	x0  = h ? bp[i] >> h : 0 ;
	x0 |= bp[++i]   << k;

	rp[j++] = x1 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
}
if (rc > 1)
	rp[j++] = x0 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
if (up) {
	x0  = h ? bp[i] >> h : 0;
	x0 |= bp[++i]   << k;
}
else {
	x0  = h ? bp[i]   >> h : 0;
}
rp[j++] = x0 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
}
else if (n > 0) {
/* Copy from hi to lo. */
i = bc - 1;
j = rc - 1;

if (up) {
	x0  = bp[i--] << k;
	x0 |= h ? bp[i]   >> h : 0;
}
else {
	x0  = h ? bp[i]   >> h : 0;
}
while (i > 0) {
	x1  = x0;
	x0  = bp[i--] << k;
	x0 |= h ? bp[i]  >> h : 0;

	rp[j--] = x1 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
}
if (i == 0) {
	x1 = x0;
	x0 = bp[0] << k;
	rp[j--] = x1 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);
}
rp[j--] = x0 & BINT_RADIX_MASK((((unsigned long) 1) << ((8 * sizeof(BIntS)))) - 1);

while (j >= 0) rp[j--] = 0;
}
else /* n == 0 */ {
for (i = 0; i < rc; i++) rp[i] = bp[i];
}
2293}

2295/*
* iintTimesS(r, a, b)
*
* Place the value a*b into r.
* The result, r, can be an alias for the input a.
*/
2301void
2302iintTimesS(BInt r, BInt a, BIntS b)
2303{
IInt	n, j;
BIntS	c;

assert(!IsImmed(r) && !IsImmed(a))do { if (!(!((long)(r) & 1) && !((long)(a) & 1
))) _do_assert(("!IsImmed(r) && !IsImmed(a)"),"bigint.c"
,2307); } while (0);
assert(Placea(r) >= Placea(a))do { if (!(((r)->placea) >= ((a)->placea))) _do_assert
(("Placea(r) >= Placea(a)"),"bigint.c",2308); } while (0);

/* !!! xintCopyInI may reallocate */
if (b == 0) { xintCopyInI(r, int0((int) 0)); return; }

n = Placec(a)((a)->placec);
c = 0;

for (j = 0; j < n; j++)
TimesStep(c, Placev(r)[j], Placev(a)[j], b, c, int0){ BIntD t_ = (BIntD)(((a)->placev)[j])*(BIntD)(b)+(BIntD)(
c)+(BIntD)(((int) 0)); (((r)->placev)[j]) = t_ % (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (c) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); };

if (c) Placev(r)((r)->placev)[j++] = c;
Placec(r)((r)->placec) = j;
2321}

2323/*
* iintTimesPlusS(r, a, b, c)
*
* Place the value a*b + c into r.
* The result, r, can be an alias for the input a.
*/
2329void
2330iintTimesPlusS(BInt r, BInt a, BIntS b, BIntS c)
2331{
IInt	n, j;

assert(!IsImmed(r) && !IsImmed(a))do { if (!(!((long)(r) & 1) && !((long)(a) & 1
))) _do_assert(("!IsImmed(r) && !IsImmed(a)"),"bigint.c"
,2334); } while (0);
assert(Placea(r) >= Placea(a))do { if (!(((r)->placea) >= ((a)->placea))) _do_assert
(("Placea(r) >= Placea(a)"),"bigint.c",2335); } while (0);

/* !!! xintCopyInI may reallocate */
if (b == 0) { xintCopyInI(r, c); return; }

n = Placec(a)((a)->placec);

for (j = 0; j < n; j++)
TimesStep(c, Placev(r)[j], Placev(a)[j], b, c, int0){ BIntD t_ = (BIntD)(((a)->placev)[j])*(BIntD)(b)+(BIntD)(
c)+(BIntD)(((int) 0)); (((r)->placev)[j]) = t_ % (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); (c) = t_ / (((unsigned
 long) 1) << ((8 * sizeof(BIntS)))); };

if (c) Placev(r)((r)->placev)[j++] = c;
Placec(r)((r)->placec) = j;
2347}

2349/*
* iintDivideS(q, &r, a, b)
*
* This divides the positive multiprecision number a by the half precision
* number b, 0 < b < BINT_RADIX.
*
* The quotient is placed in q and the remainder in r.
* If q == u, then the operation is done in-place.
*
* The result, q, can be an alias for a.
*/
2360void
2361iintDivideS(BInt q, BIntS *pr, BInt a, BIntS b)
2362{
IInt	n, j;
BIntS	r;

assert(!IsImmed(q) && !IsImmed(a))do { if (!(!((long)(q) & 1) && !((long)(a) & 1
))) _do_assert(("!IsImmed(q) && !IsImmed(a)"),"bigint.c"
,2366); } while (0);
2367#ifndef BIGINT_SHHHH
if (Placea(q)((q)->placea) < Placec(a)((a)->placec))
printf("This is it guys.\n");
2370#endif
assert(Placea(q) >= Placec(a))do { if (!(((q)->placea) >= ((a)->placec))) _do_assert
(("Placea(q) >= Placec(a)"),"bigint.c",2371); } while (0);

n = Placec(a)((a)->placec);
r = 0;
for (j = n-1; j >= 0; j--)
DivideDouble(Placev(q)[j], r,  r, Placev(a)[j],  b){ BIntD n_ = (BIntD)(r)*(BIntD)(((unsigned long) 1) << (
(8 * sizeof(BIntS)))) + (((a)->placev)[j]); BIntD d_ = (b)
; (((q)->placev)[j]) = n_ / d_; (r) = n_ % d_; };

Placec(q)((q)->placec) = (Placev(q)((q)->placev)[n-1] == 0) ? n-1 : n;
if (pr) *pr = r;
2380}
