bni64.c

vc环境下的pgp源码

/*
 * bni64.c - Low-level bignum routines, 64-bit version.
 *
 * Written by Colin Plumb.
 *
 * $Id: bni64.c,v 1.8 1998/05/14 19:07:23 cbertsch Exp $
 *
 * NOTE: the magic constants "64" and "128" appear in many places in this
 * file, including inside identifiers.  Because it is not possible to
 * ask "#ifdef" of a macro expansion, it is not possible to use the
 * preprocessor to conditionalize these properly.  Thus, this file is
 * intended to be edited with textual search and replace to produce
 * alternate word size versions.  Any reference to the number of bits
 * in a word must be the string "64", and that string must not appear
 * otherwise.  Any reference to twice this number must appear as "128",
 * which likewise must not appear otherwise.  Is that clear?
 *
 * Remember, when doubling the bit size replace the larger number (128)
 * first, then the smaller (64).  When halving the bit size, do the
 * opposite.  Otherwise, things will get wierd.  Also, be sure to replace
 * every instance that appears.  (:%s/foo/bar/g in vi)
 *
 * These routines work with a pointer to the least-significant end of
 * an array of WORD64s.  The BIG(x), LITTLE(y) and BIGLTTLE(x,y) macros
 * defined in bni.h (which expand to x on a big-edian machine and y on a
 * little-endian machine) are used to conditionalize the code to work
 * either way.  If you have no assembly primitives, it doesn't matter.
 * Note that on a big-endian machine, the least-significant-end pointer
 * is ONE PAST THE END.  The bytes are ptr[-1] through ptr[-len].
 * On little-endian, they are ptr[0] through ptr[len-1].  This makes
 * perfect sense if you consider pointers to point *between* bytes rather
 * than at them.
 *
 * Because the array index values are unsigned integers, ptr[-i]
 * may not work properly, since the index -i is evaluated as an unsigned,
 * and if pointers are wider, zero-extension will produce a positive
 * number rahter than the needed negative.  The expression used in this
 * code, *(ptr-i) will, however, work.  (The array syntax is equivalent
 * to *(ptr+-i), which is a pretty subtle difference.)
 *
 * Many of these routines will get very unhappy if fed zero-length inputs.
 * They use pgpAssert() to enforce this.  An higher layer of code must make
 * sure that these aren't called with zero-length inputs.
 *
 * Any of these routines can be replaced with more efficient versions
 * elsewhere, by just #defining their names.  If one of the names
 * is #defined, the C code is not compiled in and no declaration is
 * made.  Use the BNINCLUDE file to do that.  Typically, you compile
 * asm subroutines with the same name and just, e.g.
 * #define bniMulAdd1_64 bniMulAdd1_64
 *
 * If you want to write asm routines, start with bniMulAdd1_64().
 * This is the workhorse of modular exponentiation.  bniMulN1_64() is
 * also used a fair bit, although not as much and it's defined in terms
 * of bniMulAdd1_64 if that has a custom version.  bniMulSub1_64 and
 * bniDiv21_64 are used in the usual division and remainder finding.
 * (Not the Montgomery reduction used in modular exponentiation, though.)
 * Once you have bniMulAdd1_64 defined, writing the other two should
 * be pretty easy.  (Just make sure you get the sign of the subtraction
 * in bniMulSub1_64 right - it's dest = dest - source * k.)
 *
 * The only definitions that absolutely need a double-word (BNWORD128)
 * type are bniMulAdd1_64 and bniMulSub1_64; if those are provided,
 * the rest follows.  bniDiv21_64, however, is a lot slower unless you
 * have them, and bniModQ_64 takes after it.  That one is used quite a
 * bit for prime sieving.
 */

#include "pgpConfig.h"

/*
 * Some compilers complain about #if FOO if FOO isn't defined,
 * so do the ANSI-mandated thing explicitly...
 */
#ifndef NO_ASSERT_H
#define NO_ASSERT_H 0
#endif
#ifndef NO_STRING_H
#define NO_STRING_H 0
#endif
#ifndef HAVE_STRINGS_H
#define HAVE_STRINGS_H 0
#endif
#ifndef NEED_MEMORY_H
#define NEED_MEMORY_H 0
#endif

#if !NO_STRING_H
#include <string.h>	/* For memcpy */
#elif HAVE_STRINGS_H
#include <strings.h>
#endif
#if NEED_MEMORY_H
#include <memory.h>
#endif

#include "bni.h"
#include "bni64.h"
#include "bnimem.h"
#include "bnlegal.h"

#include "bnkludge.h"
#include "pgpDebug.h"

#ifndef BNWORD64
#error 64-bit bignum library requires a 64-bit data type
#endif

/* Make sure the copyright notice gets included */
volatile const char * volatile const bniCopyright_64 = bnCopyright;

/* If this is defined, include bnYield() calls */
#if BNYIELD
extern int (*bnYield)(void);	/* From bn.c */
#endif

/*
 * Most of the multiply (and Montgomery reduce) routines use an outer
 * loop that iterates over one of the operands - a so-called operand
 * scanning approach.  One big advantage of this is that the assembly
 * support routines are simpler.  The loops can be rearranged to have
 * an outer loop that iterates over the product, a so-called product
 * scanning approach.  This has the advantage of writing less data
 * and doing fewer adds to memory, so is supposedly faster.  Some
 * code has been written using a product-scanning approach, but
 * it appears to be slower, so it is turned off by default.  Some
 * experimentation would be appreciated.
 *
 * (The code is also annoying to get right and not very well commented,
 * one of my pet peeves about math libraries.  I'm sorry.)
 */
#ifndef PRODUCT_SCAN
#define PRODUCT_SCAN 0
#endif

/*
 * Copy an array of words.  <Marvin mode on>  Thrilling, isn't it? </Marvin>
 * This is a good example of how the byte offsets and BIGLITTLE() macros work.
 * Another alternative would have been
 * memcpy(dest BIG(-len), src BIG(-len), len*sizeof(BNWORD64)), but I find that
 * putting operators into conditional macros is confusing.
 */
#ifndef bniCopy_64
void
bniCopy_64(BNWORD64 *dest, BNWORD64 const *src, unsigned len)
{
	memcpy(BIGLITTLE(dest-len,dest), BIGLITTLE(src-len,src),
	       len * sizeof(*src));
}
#endif /* !bniCopy_64 */

/*
 * Fill n words with zero.  This does it manually rather than calling
 * memset because it can assume alignment to make things faster while
 * memset can't.  Note how big-endian numbers are naturally addressed
 * using predecrement, while little-endian is postincrement.
 */
#ifndef bniZero_64
void
bniZero_64(BNWORD64 *num, unsigned len)
{
	while (len--)
		BIGLITTLE(*--num,*num++) = 0;
}
#endif /* !bniZero_64 */

/*
 * Negate an array of words.
 * Negation is subtraction from zero.  Negating low-order words
 * entails doing nothing until a non-zero word is hit.  Once that
 * is negated, a borrow is generated and never dies until the end
 * of the number is hit.  Negation with borrow, -x-1, is the same as ~x.
 * Repeat that until the end of the number.
 *
 * Doesn't return borrow out because that's pretty useless - it's
 * always set unless the input is 0, which is easy to notice in
 * normalized form.
 */
#ifndef bniNeg_64
void
bniNeg_64(BNWORD64 *num, unsigned len)
{
	pgpAssert(len);

	/* Skip low-order zero words */
	while (BIGLITTLE(*--num,*num) == 0) {
		if (!--len)
			return;
		LITTLE(num++;)
	}
	/* Negate the lowest-order non-zero word */
	*num = -*num;
	/* Complement all the higher-order words */
	while (--len) {
		BIGLITTLE(--num,++num);
		*num = ~*num;
	}
}
#endif /* !bniNeg_64 */


/*
 * bniAdd1_64: add the single-word "carry" to the given number.
 * Used for minor increments and propagating the carry after
 * adding in a shorter bignum.
 *
 * Technique: If we have a double-width word, presumably the compiler
 * can add using its carry in inline code, so we just use a larger
 * accumulator to compute the carry from the first addition.
 * If not, it's more complex.  After adding the first carry, which may
 * be > 1, compare the sum and the carry.  If the sum wraps (causing a
 * carry out from the addition), the result will be less than each of the
 * inputs, since the wrap subtracts a number (2^64) which is larger than
 * the other input can possibly be.  If the sum is >= the carry input,
 * return success immediately.
 * In either case, if there is a carry, enter a loop incrementing words
 * until one does not wrap.  Since we are adding 1 each time, the wrap
 * will be to 0 and we can test for equality.
 */
#ifndef bniAdd1_64	/* If defined, it's provided as an asm subroutine */
#ifdef BNWORD128
BNWORD64
bniAdd1_64(BNWORD64 *num, unsigned len, BNWORD64 carry)
{
	BNWORD128 t;
	pgpAssert(len > 0);	/* Alternative: if (!len) return carry */

	t = (BNWORD128)BIGLITTLE(*--num,*num) + carry;
	BIGLITTLE(*num,*num++) = (BNWORD64)t;
	if ((t >> 64) == 0)
		return 0;
	while (--len) {
		if (++BIGLITTLE(*--num,*num++) != 0)
			return 0;
	}
	return 1;
}
#else /* no BNWORD128 */
BNWORD64
bniAdd1_64(BNWORD64 *num, unsigned len, BNWORD64 carry)
{
	pgpAssert(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_64 */

/*
 * bniSub1_64: 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 (BNWORD64).  If the size of an int is larger
 * than BNWORD64, 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_64	/* If defined, it's provided as an asm subroutine */
#ifdef BNWORD128
BNWORD64
bniSub1_64(BNWORD64 *num, unsigned len, BNWORD64 borrow)
{
	BNWORD128 t;
	pgpAssert(len > 0);	/* Alternative: if (!len) return borrow */

	t = (BNWORD128)BIGLITTLE(*--num,*num) - borrow;
	BIGLITTLE(*num,*num++) = (BNWORD64)t;
	if ((t >> 64) == 0)
		return 0;
	while (--len) {
		if ((BIGLITTLE(*--num,*num++))-- != 0)
			return 0;
	}
	return 1;
}
#else /* no BNWORD128 */
BNWORD64
bniSub1_64(BNWORD64 *num, unsigned len, BNWORD64 borrow)
{
	pgpAssert(len > 0);	/* Alternative: if (!len) return borrow */

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

/*
 * bniAddN_64: 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_64
#ifdef BNWORD128
BNWORD64
bniAddN_64(BNWORD64 *num1, BNWORD64 const *num2, unsigned len)
{
	BNWORD128 t;

	pgpAssert(len > 0);

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

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

	pgpAssert(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_64 */

/*
 * bniSubN_64: 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, (BNWORD64)-(t>>64) is subtracted, rather than
 * adding t>>64, because the shift would need to sign-extend and that's
 * not guaranteed to happen in ANSI C, even with signed types.
 */
#ifndef bniSubN_64
#ifdef BNWORD128
BNWORD64
bniSubN_64(BNWORD64 *num1, BNWORD64 const *num2, unsigned len)
{
	BNWORD128 t;

	pgpAssert(len > 0);

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

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

	return -(BNWORD64)(t>>64);
}
#else
BNWORD64
bniSubN_64(BNWORD64 *num1, BNWORD64 const *num2, unsigned len)
{
	BNWORD64 x, borrow = 0;

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

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

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

#ifndef bniCmp_64
/*
 * bniCmp_64: 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