bni16.c

著名的加密软件的应用于电子邮件中

#endif /* !bniSubN_16 */

#ifndef bniCmp_16
/*
* bniCmp_16: 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_16(BNWORD16 const *num1, BNWORD16 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_16 */

/*
* mul16_ppmmaa(ph,pl,x,y,a,b) is an optional routine that
* computes (ph,pl) = x * y + a + b. mul16_ppmma and mul16_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(mul16_ppmma) && defined(mul16_ppmmaa)
#define mul16_ppmma(ph,pl,x,y,a) mul16_ppmmaa(ph,pl,x,y,a,0)
#endif

#if !defined(mul16_ppmm) && defined(mul16_ppmma)
#define mul16_ppmm(ph,pl,x,y) mul16_ppmma(ph,pl,x,y,0)
#endif

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

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

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

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

		pgpAssert(len > 0);

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

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

		pgpAssert(len > 0);

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

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

/*
* bniMulAdd1_16: 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 mul16_ppmma and mul16_ppmmaa macros,
* or C multiplication with the BNWORD32 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_16
#if defined(mul16_ppmm)
BNWORD16
bniMulAdd1_16(BNWORD16 *out, BNWORD16 const *in, unsigned len, BNWORD16 k)
	{
			BNWORD16 prod, carry, carryin;

		pgpAssert(len > 0);

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

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

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

			pgpAssert(len > 0);

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

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

			return (BNWORD16)(p >> 16);
	}
#else
#error No 16x16 -> 32 multiply available for 16-bit bignum package
#endif
#endif /* bniMulAdd1_16 */

/*
* bniMulSub1_16: 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 mul16_ppmm and mul16_ppmma macros, or
* C multiplication with the BNWORD32 type.
*
* This is rather uglier than adding, but fortunately it's only used in
* division which is not used too heavily.
	*/
#ifndef bniMulSub1_16
#if defined(mul16_ppmm)
BNWORD16
bniMulSub1_16(BNWORD16 *out, BNWORD16 const *in, unsigned len, BNWORD16 k)
	{
			BNWORD16 prod, carry, carryin;

			pgpAssert(len > 0);

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

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

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

			pgpAssert(len > 0);

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

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

return carry;
}
#else
#error No 16x16 -> 32 multiply available for 16-bit bignum package
#endif
#endif /* !bniMulSub1_16 */

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

			pgpAssert(shift > 0);
			pgpAssert(shift < 16);

			carry = 0;
			while (len--) {
					BIG(--num;)
					x = *num;
					*num = (x<<shift) | carry;
					LITTLE(num++;)
					carry = x >> (16-shift);
		}
			return carry;
	}

#endif /* !bniLshift_16 */
/*
* An optimized version of the above, for shifts of 1.
* Some machines can use add-with-carry tricks for this.
*/
#ifndef bniDouble_16
BNWORD16
bniDouble_16(BNWORD16 *num, unsigned len)
{
BNWORD16 x, carry;

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

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

			pgpAssert(shift > 0);
			pgpAssert(shift < 16);

BIGLITTLE(num -= len, num += len);

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

/*
* Multiply two numbers of the given lengths. prod and num2 may overlap,
* provided that the low len1 bits of prod are free. (This corresponds
* nicely to the place the result is returned from bniMontReduce_16.)
*
* TODO: Use Karatsuba multiply. The overlap constraints may have
* to get rewhacked.
*/
#ifndef bniMul_16
void
bniMul_16(BNWORD16 *prod, BNWORD16 const *num1, unsigned len1,
		BNWORD16 const *num2, unsigned len2)
	{
			/* Special case of zero */
			if (!len1 || !len2) {
				 bniZero_16(prod, len1+len2);
				 return;
			}

			/* Multiply first word */
			bniMulN1_16(prod, num1, len1, BIGLITTLE(*--num2,*num2++));

			/*
			* Add in subsequent words, storing the most significant word,
			* which is new each time.
			*/
			while (--len2) {
					BIGLITTLE(--prod,prod++);
					BIGLITTLE(*(prod-len1-1),*(prod+len1)) =
							bniMulAdd1_16(prod, num1, len1,
									BIGLITTLE(*--num2,*num2++));
			}
}
#endif /* !bniMul_16 */

/*
* bniMulX_16 is a square multiply - both inputs are the same length.
* It's normally just a macro wrapper around the general multiply,
* but might be implementable in assembly more efficiently (such as
* when product scanning).
*/
#ifndef bniMulX_16
#if defined(BNWORD32) && PRODUCT_SCAN
/*
* Test code to see whether product scanning is any faster. It seems
* to make the C code slower, so PRODUCT_SCAN is not defined.
*/
static void
bniMulX_16(BNWORD16 *prod, BNWORD16 const *num1, BNWORD16 const *num2,
			unsigned len)
	{
			BNWORD32 x, y;
			BNWORD16 const *p1, *p2;
			unsigned carry;
			unsigned i, j;

			/* Special case of zero */
			if (!len)
				 return;

			x = (BNWORD32)BIGLITTLE(num1[-1] * num2[-1], num1[0] * num2[0]);
			BIGLITTLE(*--prod, *prod++) = (BNWORD16)x;
			x >>= 16;

			for (i = 1; i < len; i++) {
				 carry = 0;
				 p1 = num1;
				 p2 = BIGLITTLE(num2-i-1,num2+i+1);
				 for (j = 0; j <= i; j++) {
							BIG(y = (BNWORD32)*--p1 * *p2++;)
							LITTLE(y = (BNWORD32)*p1++ * *--p2;)
							x += y;
							carry += (x < y);
					}
					BIGLITTLE(*--prod,*prod++) = (BNWORD16)x;
					x = (x >> 16) | (BNWORD32)carry << 16;
			}
			for (i = 1; i < len; i++) {
					carry = 0;
					p1 = BIGLITTLE(num1-i,num1+i);
					p2 = BIGLITTLE(num2-len,num2+len);
					for (j = i; j < len; j++) {
							BIG(y = (BNWORD32)*--p1 * *p2++;)
							LITTLE(y = (BNWORD32)*p1++ * *--p2;)
							x += y;
							carry += (x < y);
					}
					BIGLITTLE(*--prod,*prod++) = (BNWORD16)x;
					x = (x >> 16) | (BNWORD32)carry << 16;
			}
		
			BIGLITTLE(*--prod,*prod) = (BNWORD16)x;
	}
#else /* !defined(BNWORD32) || !PRODUCT_SCAN */
/* Default trivial macro definition */
#define bniMulX_16(prod, num1, num2, len) bniMul_16(prod, num1, len, num2, len)
#endif /* !defined(BNWORD32) || !PRODUCT_SCAN */
#endif /* !lbmMulX_16 */

#if !defined(bniMontMul_16) && defined(BNWORD32) && PRODUCT_SCAN
/*
* Test code for product-scanning multiply. This seems to slow the C
* code down rather than speed it up.
* This does a multiply and Montgomery reduction together, using the
* same loops. The outer loop scans across the product, twice.
* The first pass computes the low half of the product and the
* Montgomery multipliers. These are stored in the product array,
* which contains no data as of yet. x and carry add up the columns
* and propagate carries forward.
*
* The second half multiplies the upper half, adding in the modulus