bignumber.cpp

绝对好东东

	if ((t >> 32) == 0)
		return 0;
	while (--len) {
		if (++BIGLITTLE(*--num,*num++) != 0)
			return 0;
	}
	return 1;
}
#else /* no BNWORD64 */
BNWORD32
bniAdd1_32(BNWORD32 *num, unsigned len, BNWORD32 carry)
{
	ASSERT(len > 0);	/* Alternative: if (!len) return carry */

	if ((BIGLITTLE(*--num,*num++) += carry) >= carry)
		return 0;
	while (--len) {
		if (++BIGLITTLE(*--num,*num++) != 0)
			return 0;
	}
	return 1;
}
#endif
#endif/* !bniAdd1_32 */

/*
 * bniSub1_32: subtract the single-word "borrow" from the given number.
 * Used for minor decrements and propagating the borrow after
 * subtracting a shorter bignum.
 *
 * Technique: Similar to the add, above.  If there is a double-length type,
 * use that to generate the first borrow.
 * If not, after subtracting the first borrow, which may be > 1, compare
 * the difference and the *negative* of the carry.  If the subtract wraps
 * (causing a borrow out from the subtraction), the result will be at least
 * as large as -borrow.  If the result < -borrow, then no borrow out has
 * appeared and we may return immediately, except when borrow == 0.  To
 * deal with that case, use the identity that -x = ~x+1, and instead of
 * comparing < -borrow, compare for <= ~borrow.
 * Either way, if there is a borrow out, enter a loop decrementing words
 * until a non-zero word is reached.
 *
 * Note the cast of ~borrow to (BNWORD32).  If the size of an int is larger
 * than BNWORD32, C rules say the number is expanded for the arithmetic, so
 * the inversion will be done on an int and the value won't be quite what
 * is expected.
 */
#ifndef bniSub1_32	/* If defined, it's provided as an asm subroutine */
#ifdef BNWORD64
BNWORD32
bniSub1_32(BNWORD32 *num, unsigned len, BNWORD32 borrow)
{
	BNWORD64 t;
	ASSERT(len > 0);	/* Alternative: if (!len) return borrow */

	t = (BNWORD64)BIGLITTLE(*--num,*num) - borrow;
	BIGLITTLE(*num,*num++) = (BNWORD32)t;
	if ((t >> 32) == 0)
		return 0;
	while (--len) {
		if ((BIGLITTLE(*--num,*num++))-- != 0)
			return 0;
	}
	return 1;
}
#else /* no BNWORD64 */
BNWORD32
bniSub1_32(BNWORD32 *num, unsigned len, BNWORD32 borrow)
{
	ASSERT(len > 0);	/* Alternative: if (!len) return borrow */

	if ((BIGLITTLE(*--num,*num++) -= borrow) <= (BNWORD32)~borrow)
		return 0;
	while (--len) {
		if ((BIGLITTLE(*--num,*num++))-- != 0)
			return 0;
	}
	return 1;
}
#endif
#endif /* !bniSub1_32 */

/*
 * bniAddN_32: add two bignums of the same length,
 * returning the carry (0 or 1).
 * One of the building blocks, along with bniAdd1, of adding two bignums of
 * differing lengths.
 *
 * Technique: Maintain a word of carry.  If there is no double-width type,
 * use the same technique as in bniAdd1, above, to maintain the carry by
 * comparing the inputs.  Adding the carry sources is used as an OR operator;
 * at most one of the two comparisons can possibly be true.  The first can
 * only be true if carry == 1 and x, the result, is 0.  In that case the
 * second can't possibly be true.
 */
#ifndef bniAddN_32
#ifdef BNWORD64
BNWORD32
bniAddN_32(BNWORD32 *num1, BNWORD32 const *num2, unsigned len)
{
	BNWORD64 t;

	ASSERT(len > 0);

	t = (BNWORD64)BIGLITTLE(*--num1,*num1) + BIGLITTLE(*--num2,*num2++);
	BIGLITTLE(*num1,*num1++) = (BNWORD32)t;
	while (--len) {
		t = (BNWORD64)BIGLITTLE(*--num1,*num1) +
		    (BNWORD64)BIGLITTLE(*--num2,*num2++) + (t >> 32);
		BIGLITTLE(*num1,*num1++) = (BNWORD32)t;
	}

	return (BNWORD32)(t>>32);
}
#else /* no BNWORD64 */
BNWORD32
bniAddN_32(BNWORD32 *num1, BNWORD32 const *num2, unsigned len)
{
	BNWORD32 x, carry = 0;

	ASSERT(len > 0);	/* Alternative: change loop to test at start */

	do {
		x = BIGLITTLE(*--num2,*num2++);
		carry = (x += carry) < carry;
		carry += (BIGLITTLE(*--num1,*num1++) += x) < x;
	} while (--len);

	return carry;
}
#endif
#endif /* !bniAddN_32 */

/*
 * bniSubN_32: add two bignums of the same length,
 * returning the carry (0 or 1).
 * One of the building blocks, along with subn1, of subtracting two bignums of
 * differing lengths.
 *
 * Technique: If no double-width type is availble, maintain a word of borrow.
 * First, add the borrow to the subtrahend (did you have to learn all those
 * awful words in elementary school, too?), and if it overflows, set the
 * borrow again.  Then subtract the modified subtrahend from the next word
 * of input, using the same technique as in subn1, above.
 * Adding the borrows is used as an OR operator; at most one of the two
 * comparisons can possibly be true.  The first can only be true if
 * borrow == 1 and x, the result, is 0.  In that case the second can't
 * possibly be true.
 *
 * In the double-word case, (BNWORD32)-(t>>32) is subtracted, rather than
 * adding t>>32, because the shift would need to sign-extend and that's
 * not guaranteed to happen in ANSI C, even with signed types.
 */
#ifndef bniSubN_32
#ifdef BNWORD64
BNWORD32
bniSubN_32(BNWORD32 *num1, BNWORD32 const *num2, unsigned len)
{
	BNWORD64 t;

	ASSERT(len > 0);

	t = (BNWORD64)BIGLITTLE(*--num1,*num1) - BIGLITTLE(*--num2,*num2++);
	BIGLITTLE(*num1,*num1++) = (BNWORD32)t;

	while (--len) {
		t = (BNWORD64)BIGLITTLE(*--num1,*num1) -
		    (BNWORD64)BIGLITTLE(*--num2,*num2++) -
		    (BNWORD32)-(t >> 32);
		BIGLITTLE(*num1,*num1++) = (BNWORD32)t;
	}

	return -(BNWORD32)(t>>32);
}
#else
BNWORD32
bniSubN_32(BNWORD32 *num1, BNWORD32 const *num2, unsigned len)
{
	BNWORD32 x, borrow = 0;

	ASSERT(len > 0);	/* Alternative: change loop to test at start */

	do {
		x = BIGLITTLE(*--num2,*num2++);
		borrow = (x += borrow) < borrow;
		borrow += (BIGLITTLE(*--num1,*num1++) -= x) > (BNWORD32)~x;
	} while (--len);

	return borrow;
}
#endif
#endif /* !bniSubN_32 */

#ifndef bniCmp_32
/*
 * bniCmp_32: compare two bignums of equal length, returning the sign of
 * num1 - num2. (-1, 0 or +1).
 * 
 * Technique: Change the little-endian pointers to big-endian pointers
 * and compare from the most-significant end until a difference if found.
 * When it is, figure out the sign of the difference and return it.
 */
int
bniCmp_32(BNWORD32 const *num1, BNWORD32 const *num2, unsigned len)
{
	BIGLITTLE(num1 -= len, num1 += len);
	BIGLITTLE(num2 -= len, num2 += len);

	while (len--) {
		if (BIGLITTLE(*num1++ != *num2++, *--num1 != *--num2)) {
			if (BIGLITTLE(num1[-1] < num2[-1], *num1 < *num2))
				return -1;
			else
				return 1;
		}
	}
	return 0;
}
#endif /* !bniCmp_32 */

/*
 * mul32_ppmmaa(ph,pl,x,y,a,b) is an optional routine that
 * computes (ph,pl) = x * y + a + b.  mul32_ppmma and mul32_ppmm
 * are simpler versions.  If you want to be lazy, all of these
 * can be defined in terms of the others, so here we create any
 * that have not been defined in terms of the ones that have been.
 */

/* Define ones with fewer a's in terms of ones with more a's */
#if !defined(mul32_ppmma) && defined(mul32_ppmmaa)
#define mul32_ppmma(ph,pl,x,y,a) mul32_ppmmaa(ph,pl,x,y,a,0)
#endif

#if !defined(mul32_ppmm) && defined(mul32_ppmma)
#define mul32_ppmm(ph,pl,x,y) mul32_ppmma(ph,pl,x,y,0)
#endif

/*
 * Use this definition to test the mul32_ppmm-based operations on machines
 * that do not provide mul32_ppmm.  Change the final "0" to a "1" to
 * enable it.
 */
#if !defined(mul32_ppmm) && defined(BNWORD64) && 0	/* Debugging */
#define mul32_ppmm(ph,pl,x,y) \
	({BNWORD64 _ = (BNWORD64)(x)*(y); (pl) = _; (ph) = _>>32;})
#endif

#if defined(mul32_ppmm) && !defined(mul32_ppmma)
#define mul32_ppmma(ph,pl,x,y,a) \
	(mul32_ppmm(ph,pl,x,y), (ph) += ((pl) += (a)) < (a))
#endif

#if defined(mul32_ppmma) && !defined(mul32_ppmmaa)
#define mul32_ppmmaa(ph,pl,x,y,a,b) \
	(mul32_ppmma(ph,pl,x,y,a), (ph) += ((pl) += (b)) < (b))
#endif

/*
 * bniMulN1_32: Multiply an n-word input by a 1-word input and store the
 * n+1-word product.  This uses either the mul32_ppmm and mul32_ppmma
 * macros, or C multiplication with the BNWORD64 type.  This uses mul32_ppmma
 * if available, assuming you won't bother defining it unless you can do
 * better than the normal multiplication.
 */
#ifndef bniMulN1_32
#ifdef bniMulAdd1_32	/* If we have this asm primitive, use it. */
void
bniMulN1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	bniZero_32(out, len);
	BIGLITTLE(*(out-len),*(out+len)) = bniMulAdd1_32(out, in, len, k);
}
#elif defined(mul32_ppmm)
void
bniMulN1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD32 prod, carry, carryin;

	ASSERT(len > 0);

	BIG(--out;--in;);
	mul32_ppmm(carry, *out, *in, k);
	LITTLE(out++;in++;)

	while (--len) {
		BIG(--out;--in;)
		carryin = carry;
		mul32_ppmma(carry, *out, *in, k, carryin);
		LITTLE(out++;in++;)
	}
	BIGLITTLE(*--out,*out) = carry;
}
#elif defined(BNWORD64)
void
bniMulN1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD64 p;

	ASSERT(len > 0);

	p = (BNWORD64)BIGLITTLE(*--in,*in++) * k;
	BIGLITTLE(*--out,*out++) = (BNWORD32)p;

	while (--len) {
		p = (BNWORD64)BIGLITTLE(*--in,*in++) * k + (BNWORD32)(p >> 32);
		BIGLITTLE(*--out,*out++) = (BNWORD32)p;
	}
	BIGLITTLE(*--out,*out) = (BNWORD32)(p >> 32);
}
#else
#error No 32x32 -> 64 multiply available for 32-bit bignum package
#endif
#endif /* bniMulN1_32 */

/*
 * bniMulAdd1_32: Multiply an n-word input by a 1-word input and add the
 * low n words of the product to the destination.  *Returns the n+1st word
 * of the product.*  (That turns out to be more convenient than adding
 * it into the destination and dealing with a possible unit carry out
 * of *that*.)  This uses either the mul32_ppmma and mul32_ppmmaa macros,
 * or C multiplication with the BNWORD64 type.
 *
 * If you're going to write assembly primitives, this is the one to
 * start with.  It is by far the most commonly called function.
 */
#ifndef bniMulAdd1_32
#if defined(mul32_ppmm)
BNWORD32
bniMulAdd1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD32 prod, carry, carryin;

	ASSERT(len > 0);

	BIG(--out;--in;);
	carryin = *out;
	mul32_ppmma(carry, *out, *in, k, carryin);
	LITTLE(out++;in++;)

	while (--len) {
		BIG(--out;--in;);
		carryin = carry;
		mul32_ppmmaa(carry, prod, *in, k, carryin, *out);
		*out = prod;
		LITTLE(out++;in++;)
	}

	return carry;
}
#elif defined(BNWORD64)
BNWORD32
bniMulAdd1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD64 p;

	ASSERT(len > 0);

	p = (BNWORD64)BIGLITTLE(*--in,*in++) * k + BIGLITTLE(*--out,*out);
	BIGLITTLE(*out,*out++) = (BNWORD32)p;

	while (--len) {
		p = (BNWORD64)BIGLITTLE(*--in,*in++) * k +
		    (BNWORD32)(p >> 32) + BIGLITTLE(*--out,*out);
		BIGLITTLE(*out,*out++) = (BNWORD32)p;
	}

	return (BNWORD32)(p >> 32);
}
#else
#error No 32x32 -> 64 multiply available for 32-bit bignum package
#endif
#endif /* bniMulAdd1_32 */

/*
 * bniMulSub1_32: Multiply an n-word input by a 1-word input and subtract the
 * n-word product from the destination.  Returns the n+1st word of the product.
 * This uses either the mul32_ppmm and mul32_ppmma macros, or
 * C multiplication with the BNWORD64 type.
 *
 * This is rather uglier than adding, but fortunately it's only used in
 * division which is not used too heavily.
 */
#ifndef bniMulSub1_32
#if defined(mul32_ppmm)
BNWORD32
bniMulSub1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD32 prod, carry, carryin;

	ASSERT(len > 0);

	BIG(--in;)
	mul32_ppmm(carry, prod, *in, k);
	LITTLE(in++;)
	carry += (BIGLITTLE(*--out,*out++) -= prod) > (BNWORD32)~prod;

	while (--len) {
		BIG(--in;);
		carryin = carry;
		mul32_ppmma(carry, prod, *in, k, carryin);
		LITTLE(in++;)
		carry += (BIGLITTLE(*--out,*out++) -= prod) > (BNWORD32)~prod;
	}

	return carry;
}
#elif defined(BNWORD64)
BNWORD32
bniMulSub1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
{
	BNWORD64 p;
	BNWORD32 carry, t;

	ASSERT(len > 0);

	p = (BNWORD64)BIGLITTLE(*--in,*in++) * k;
	t = BIGLITTLE(*--out,*out);
	carry = (BNWORD32)(p>>32) +
			((BIGLITTLE(*out,*out++)=t-(BNWORD32)p) > t);

	while (--len) {
		p = (BNWORD64)BIGLITTLE(*--in,*in++) * k + carry;
		t = BIGLITTLE(*--out,*out);
		carry = (BNWORD32)(p>>32) +
			( (BIGLITTLE(*out,*out++)=t-(BNWORD32)p) > t );
	}

	return carry;
}
#else
#error No 32x32 -> 64 multiply available for 32-bit bignum package
#endif
#endif /* !bniMulSub1_32 */

/*
 * Shift n words left "shift" bits.  0 < shift < 32.  Returns the
 * carry, any bits shifted off the left-hand side (0 <= carry < 2^shift).
 */
#ifndef bniLshift_32
BNWORD32
bniLshift_32(BNWORD32 *num, unsigned len, unsigned shift)
{
	BNWORD32 x, carry;

	ASSERT(shift > 0);
	ASSERT(shift < 32);

	carry = 0;
	while (len--) {
		BIG(--num;)
		x = *num;
		*num = (x<<shift) | carry;
		LITTLE(num++;)
		carry = x >> (32-shift);
	}
	return carry;
}
#endif /* !bniLshift_32 */