[thirdparty/openssl.git] / crypto / bn / bn_lib.c

/* crypto/bn/bn_lib.c */
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 * All rights reserved.
 *
 * This package is an SSL implementation written
 * by Eric Young (eay@cryptsoft.com).
 * The implementation was written so as to conform with Netscapes SSL.
 * 
 * This library is free for commercial and non-commercial use as long as
 * the following conditions are aheared to.  The following conditions
 * apply to all code found in this distribution, be it the RC4, RSA,
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 * included with this distribution is covered by the same copyright terms
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 * 
 * Copyright remains Eric Young's, and as such any Copyright notices in
 * the code are not to be removed.
 * If this package is used in a product, Eric Young should be given attribution
 * as the author of the parts of the library used.
 * This can be in the form of a textual message at program startup or
 * in documentation (online or textual) provided with the package.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    "This product includes cryptographic software written by
 *     Eric Young (eay@cryptsoft.com)"
 *    The word 'cryptographic' can be left out if the rouines from the library
 *    being used are not cryptographic related :-).
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 *    the apps directory (application code) you must include an acknowledgement:
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 * 
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * 
 * The licence and distribution terms for any publically available version or
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 * copied and put under another distribution licence
 * [including the GNU Public Licence.]
 */

#include <stdio.h>
#include "cryptlib.h"
#include "bn_lcl.h"

const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT;

/* For a 32 bit machine
 * 2 -   4 ==  128
 * 3 -   8 ==  256
 * 4 -  16 ==  512
 * 5 -  32 == 1024
 * 6 -  64 == 2048
 * 7 - 128 == 4096
 * 8 - 256 == 8192
 */
OPENSSL_GLOBAL int bn_limit_bits=0;
OPENSSL_GLOBAL int bn_limit_num=8;        /* (1<<bn_limit_bits) */
OPENSSL_GLOBAL int bn_limit_bits_low=0;
OPENSSL_GLOBAL int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
OPENSSL_GLOBAL int bn_limit_bits_high=0;
OPENSSL_GLOBAL int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
OPENSSL_GLOBAL int bn_limit_bits_mont=0;
OPENSSL_GLOBAL int bn_limit_num_mont=8;   /* (1<<bn_limit_bits_mont) */

void BN_set_params(int mult, int high, int low, int mont)
	{
	if (mult >= 0)
		{
		if (mult > (sizeof(int)*8)-1)
			mult=sizeof(int)*8-1;
		bn_limit_bits=mult;
		bn_limit_num=1<<mult;
		}
	if (high >= 0)
		{
		if (high > (sizeof(int)*8)-1)
			high=sizeof(int)*8-1;
		bn_limit_bits_high=high;
		bn_limit_num_high=1<<high;
		}
	if (low >= 0)
		{
		if (low > (sizeof(int)*8)-1)
			low=sizeof(int)*8-1;
		bn_limit_bits_low=low;
		bn_limit_num_low=1<<low;
		}
	if (mont >= 0)
		{
		if (mont > (sizeof(int)*8)-1)
			mont=sizeof(int)*8-1;
		bn_limit_bits_mont=mont;
		bn_limit_num_mont=1<<mont;
		}
	}

int BN_get_params(int which)
	{
	if      (which == 0) return(bn_limit_bits);
	else if (which == 1) return(bn_limit_bits_high);
	else if (which == 2) return(bn_limit_bits_low);
	else if (which == 3) return(bn_limit_bits_mont);
	else return(0);
	}

BIGNUM *BN_value_one(void)
	{
	static BN_ULONG data_one=1L;
	static BIGNUM const_one={&data_one,1,1,0};

	return(&const_one);
	}

char *BN_options(void)
	{
	static int init=0;
	static char data[16];

	if (!init)
		{
		init++;
#ifdef BN_LLONG
		sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
			(int)sizeof(BN_ULONG)*8);
#else
		sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
			(int)sizeof(BN_ULONG)*8);
#endif
		}
	return(data);
	}

int BN_num_bits_word(BN_ULONG l)
	{
	static const char bits[256]={
		0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
		5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
		6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
		};

#if defined(SIXTY_FOUR_BIT_LONG)
	if (l & 0xffffffff00000000L)
		{
		if (l & 0xffff000000000000L)
			{
			if (l & 0xff00000000000000L)
				{
				return(bits[(int)(l>>56)]+56);
				}
			else	return(bits[(int)(l>>48)]+48);
			}
		else
			{
			if (l & 0x0000ff0000000000L)
				{
				return(bits[(int)(l>>40)]+40);
				}
			else	return(bits[(int)(l>>32)]+32);
			}
		}
	else
#else
#ifdef SIXTY_FOUR_BIT
	if (l & 0xffffffff00000000LL)
		{
		if (l & 0xffff000000000000LL)
			{
			if (l & 0xff00000000000000LL)
				{
				return(bits[(int)(l>>56)]+56);
				}
			else	return(bits[(int)(l>>48)]+48);
			}
		else
			{
			if (l & 0x0000ff0000000000LL)
				{
				return(bits[(int)(l>>40)]+40);
				}
			else	return(bits[(int)(l>>32)]+32);
			}
		}
	else
#endif
#endif
		{
#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
		if (l & 0xffff0000L)
			{
			if (l & 0xff000000L)
				return(bits[(int)(l>>24L)]+24);
			else	return(bits[(int)(l>>16L)]+16);
			}
		else
#endif
			{
#if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
			if (l & 0xff00L)
				return(bits[(int)(l>>8)]+8);
			else	
#endif
				return(bits[(int)(l   )]  );
			}
		}
	}

int BN_num_bits(BIGNUM *a)
	{
	BN_ULONG l;
	int i;

	bn_check_top(a);

	if (a->top == 0) return(0);
	l=a->d[a->top-1];
	i=(a->top-1)*BN_BITS2;
	if (l == 0)
		{
#if !defined(NO_STDIO) && !defined(WIN16)
		fprintf(stderr,"BAD TOP VALUE\n");
#endif
		abort();
		}
	return(i+BN_num_bits_word(l));
	}

void BN_clear_free(BIGNUM *a)
	{
	int i;

	if (a == NULL) return;
	if (a->d != NULL)
		{
		memset(a->d,0,a->max*sizeof(a->d[0]));
		if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
			Free(a->d);
		}
	i=BN_get_flags(a,BN_FLG_MALLOCED);
	memset(a,0,sizeof(BIGNUM));
	if (i)
		Free(a);
	}

void BN_free(BIGNUM *a)
	{
	if (a == NULL) return;
	if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
		Free(a->d);
	a->flags|=BN_FLG_FREE; /* REMOVE? */
	if (a->flags & BN_FLG_MALLOCED)
		Free(a);
	}

void BN_init(BIGNUM *a)
	{
	memset(a,0,sizeof(BIGNUM));
	}

BIGNUM *BN_new(void)
	{
	BIGNUM *ret;

	if ((ret=(BIGNUM *)Malloc(sizeof(BIGNUM))) == NULL)
		{
		BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
		return(NULL);
		}
	ret->flags=BN_FLG_MALLOCED;
	ret->top=0;
	ret->neg=0;
	ret->max=0;
	ret->d=NULL;
	return(ret);
	}


BN_CTX *BN_CTX_new(void)
	{
	BN_CTX *ret;

	ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
	if (ret == NULL)
		{
		BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
		return(NULL);
		}

	BN_CTX_init(ret);
	ret->flags=BN_FLG_MALLOCED;
	return(ret);
	}

void BN_CTX_init(BN_CTX *ctx)
	{
	memset(ctx,0,sizeof(BN_CTX));
	ctx->tos=0;
	ctx->flags=0;
	}

void BN_CTX_free(BN_CTX *c)
	{
	int i;

	if(c == NULL)
	    return;

	for (i=0; i<BN_CTX_NUM; i++)
		BN_clear_free(&(c->bn[i]));
	if (c->flags & BN_FLG_MALLOCED)
		Free(c);
	}

BIGNUM *bn_expand2(BIGNUM *b, int words)
	{
	BN_ULONG *A,*a;
	const BN_ULONG *B;
	int i;

	bn_check_top(b);

	if (words > b->max)
		{
		bn_check_top(b);	
		if (BN_get_flags(b,BN_FLG_STATIC_DATA))
			{
			BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
			return(NULL);
			}
		a=A=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(words+1));
		if (A == NULL)
			{
			BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
			return(NULL);
			}
#if 1
		B=b->d;
		/* Check if the previous number needs to be copied */
		if (B != NULL)
			{
#if 0
			/* This lot is an unrolled loop to copy b->top 
			 * BN_ULONGs from B to A
			 */
/*
 * I have nothing against unrolling but it's usually done for
 * several reasons, namely:
 * - minimize percentage of decision making code, i.e. branches;
 * - avoid cache trashing;
 * - make it possible to schedule loads earlier;
 * Now let's examine the code below. The cornerstone of C is
 * "programmer is always right" and that's what we love it for:-)
 * For this very reason C compilers have to be paranoid when it
 * comes to data aliasing and assume the worst. Yeah, but what
 * does it mean in real life? This means that loop body below will
 * be compiled to sequence of loads immediately followed by stores
 * as compiler assumes the worst, something in A==B+1 style. As a
 * result CPU pipeline is going to starve for incoming data. Secondly
 * if A and B happen to share same cache line such code is going to
 * cause severe cache trashing. Both factors have severe impact on
 * performance of modern CPUs and this is the reason why this
 * particulare piece of code is #ifdefed away and replaced by more
 * "friendly" version found in #else section below. This comment
 * also applies to BN_copy function.
 *
 *					<appro@fy.chalmers.se>
 */
			for (i=b->top&(~7); i>0; i-=8)
				{
				A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
				A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
				A+=8;
				B+=8;
				}
			switch (b->top&7)
				{
			case 7:
				A[6]=B[6];
			case 6:
				A[5]=B[5];
			case 5:
				A[4]=B[4];
			case 4:
				A[3]=B[3];
			case 3:
				A[2]=B[2];
			case 2:
				A[1]=B[1];
			case 1:
				A[0]=B[0];
			case 0:
				/* I need the 'case 0' entry for utrix cc.
				 * If the optimiser is turned on, it does the
				 * switch table by doing
				 * a=top&7
				 * a--;
				 * goto jump_table[a];
				 * If top is 0, this makes us jump to 0xffffffc 
				 * which is rather bad :-(.
				 * eric 23-Apr-1998
				 */
				;
				}
#else
			for (i=b->top>>2; i>0; i--,A+=4,B+=4)
				{
				/*
				 * The fact that the loop is unrolled
				 * 4-wise is a tribute to Intel. It's
				 * the one that doesn't have enough
				 * registers to accomodate more data.
				 * I'd unroll it 8-wise otherwise:-)
				 *
				 *		<appro@fy.chalmers.se>
				 */
				BN_ULONG a0,a1,a2,a3;
				a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
				A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
				}
			switch (b->top&3)
				{
				case 3:	A[2]=B[2];
				case 2:	A[1]=B[1];
				case 1:	A[0]=B[0];
				case 0:	; /* ultrix cc workaround, see above */
				}
#endif
			Free(b->d);
			}

		b->d=a;
		b->max=words;

		/* Now need to zero any data between b->top and b->max */

		A= &(b->d[b->top]);
		for (i=(b->max - b->top)>>3; i>0; i--,A+=8)
			{
			A[0]=0; A[1]=0; A[2]=0; A[3]=0;
			A[4]=0; A[5]=0; A[6]=0; A[7]=0;
			}
		for (i=(b->max - b->top)&7; i>0; i--,A++)
			A[0]=0;
#else
			memset(A,0,sizeof(BN_ULONG)*(words+1));
			memcpy(A,b->d,sizeof(b->d[0])*b->top);
			b->d=a;
			b->max=words;
#endif
		
/*		memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
/*	{ int i; for (i=b->max; i<words+1; i++) p[i]=i;} */

		}
	return(b);
	}

BIGNUM *BN_dup(BIGNUM *a)
	{
	BIGNUM *r;

	bn_check_top(a);

	r=BN_new();
	if (r == NULL) return(NULL);
	return((BIGNUM *)BN_copy(r,a));
	}

BIGNUM *BN_copy(BIGNUM *a, BIGNUM *b)
	{
	int i;
	BN_ULONG *A;
	const BN_ULONG *B;

	bn_check_top(b);

	if (a == b) return(a);
	if (bn_wexpand(a,b->top) == NULL) return(NULL);

#if 1
	A=a->d;
	B=b->d;
	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
		{
		BN_ULONG a0,a1,a2,a3;
		a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
		A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
		}
	switch (b->top&3)
		{
		case 3: A[2]=B[2];
		case 2: A[1]=B[1];
		case 1: A[0]=B[0];
		case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
		}
#else
	memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
#endif

/*	memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
	a->top=b->top;
	if ((a->top == 0) && (a->d != NULL))
		a->d[0]=0;
	a->neg=b->neg;
	return(a);
	}

void BN_clear(BIGNUM *a)
	{
	if (a->d != NULL)
		memset(a->d,0,a->max*sizeof(a->d[0]));
	a->top=0;
	a->neg=0;
	}

BN_ULONG BN_get_word(BIGNUM *a)
	{
	int i,n;
	BN_ULONG ret=0;

	n=BN_num_bytes(a);
	if (n > sizeof(BN_ULONG))
		return(BN_MASK2);
	for (i=a->top-1; i>=0; i--)
		{
#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
		ret<<=BN_BITS4; /* stops the compiler complaining */
		ret<<=BN_BITS4;
#else
		ret=0;
#endif
		ret|=a->d[i];
		}
	return(ret);
	}

int BN_set_word(BIGNUM *a, BN_ULONG w)
	{
	int i,n;
	if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);

	n=sizeof(BN_ULONG)/BN_BYTES;
	a->neg=0;
	a->top=0;
	a->d[0]=(BN_ULONG)w&BN_MASK2;
	if (a->d[0] != 0) a->top=1;
	for (i=1; i<n; i++)
		{
		/* the following is done instead of
		 * w>>=BN_BITS2 so compilers don't complain
		 * on builds where sizeof(long) == BN_TYPES */
#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
		w>>=BN_BITS4;
		w>>=BN_BITS4;
#else
		w=0;
#endif
		a->d[i]=(BN_ULONG)w&BN_MASK2;
		if (a->d[i] != 0) a->top=i+1;
		}
	return(1);
	}

/* ignore negative */
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
	{
	unsigned int i,m;
	unsigned int n;
	BN_ULONG l;

	if (ret == NULL) ret=BN_new();
	if (ret == NULL) return(NULL);
	l=0;
	n=len;
	if (n == 0)
		{
		ret->top=0;
		return(ret);
		}
	if (bn_expand(ret,(int)(n+2)*8) == NULL)
		return(NULL);
	i=((n-1)/BN_BYTES)+1;
	m=((n-1)%(BN_BYTES));
	ret->top=i;
	while (n-- > 0)
		{
		l=(l<<8L)| *(s++);
		if (m-- == 0)
			{
			ret->d[--i]=l;
			l=0;
			m=BN_BYTES-1;
			}
		}
	/* need to call this due to clear byte at top if avoiding
	 * having the top bit set (-ve number) */
	bn_fix_top(ret);
	return(ret);
	}

/* ignore negative */
int BN_bn2bin(BIGNUM *a, unsigned char *to)
	{
	int n,i;
	BN_ULONG l;

	n=i=BN_num_bytes(a);
	while (i-- > 0)
		{
		l=a->d[i/BN_BYTES];
		*(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
		}
	return(n);
	}

int BN_ucmp(BIGNUM *a, BIGNUM *b)
	{
	int i;
	BN_ULONG t1,t2,*ap,*bp;

	bn_check_top(a);
	bn_check_top(b);

	i=a->top-b->top;
	if (i != 0) return(i);
	ap=a->d;
	bp=b->d;
	for (i=a->top-1; i>=0; i--)
		{
		t1= ap[i];
		t2= bp[i];
		if (t1 != t2)
			return(t1 > t2?1:-1);
		}
	return(0);
	}

int BN_cmp(BIGNUM *a, BIGNUM *b)
	{
	int i;
	int gt,lt;
	BN_ULONG t1,t2;

	if ((a == NULL) || (b == NULL))
		{
		if (a != NULL)
			return(-1);
		else if (b != NULL)
			return(1);
		else
			return(0);
		}

	bn_check_top(a);
	bn_check_top(b);

	if (a->neg != b->neg)
		{
		if (a->neg)
			return(-1);
		else	return(1);
		}
	if (a->neg == 0)
		{ gt=1; lt= -1; }
	else	{ gt= -1; lt=1; }

	if (a->top > b->top) return(gt);
	if (a->top < b->top) return(lt);
	for (i=a->top-1; i>=0; i--)
		{
		t1=a->d[i];
		t2=b->d[i];
		if (t1 > t2) return(gt);
		if (t1 < t2) return(lt);
		}
	return(0);
	}

int BN_set_bit(BIGNUM *a, int n)
	{
	int i,j,k;

	i=n/BN_BITS2;
	j=n%BN_BITS2;
	if (a->top <= i)
		{
		if (bn_wexpand(a,i+1) == NULL) return(0);
		for(k=a->top; k<i+1; k++)
			a->d[k]=0;
		a->top=i+1;
		}

	a->d[i]|=(((BN_ULONG)1)<<j);
	return(1);
	}

int BN_clear_bit(BIGNUM *a, int n)
	{
	int i,j;

	i=n/BN_BITS2;
	j=n%BN_BITS2;
	if (a->top <= i) return(0);

	a->d[i]&=(~(((BN_ULONG)1)<<j));
	bn_fix_top(a);
	return(1);
	}

int BN_is_bit_set(BIGNUM *a, int n)
	{
	int i,j;

	if (n < 0) return(0);
	i=n/BN_BITS2;
	j=n%BN_BITS2;
	if (a->top <= i) return(0);
	return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
	}

int BN_mask_bits(BIGNUM *a, int n)
	{
	int b,w;

	w=n/BN_BITS2;
	b=n%BN_BITS2;
	if (w >= a->top) return(0);
	if (b == 0)
		a->top=w;
	else
		{
		a->top=w+1;
		a->d[w]&= ~(BN_MASK2<<b);
		}
	bn_fix_top(a);
	return(1);
	}

int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n)
	{
	int i;
	BN_ULONG aa,bb;

	aa=a[n-1];
	bb=b[n-1];
	if (aa != bb) return((aa > bb)?1:-1);
	for (i=n-2; i>=0; i--)
		{
		aa=a[i];
		bb=b[i];
		if (aa != bb) return((aa > bb)?1:-1);
		}
	return(0);
	}
Commit	Line	Data
d02b48c6	1	/* crypto/bn/bn_lib.c */
58964a49	2	/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
d02b48c6 RE	3	* All rights reserved.
	4	*
	5	* This package is an SSL implementation written
	6	* by Eric Young (eay@cryptsoft.com).
	7	* The implementation was written so as to conform with Netscapes SSL.
	8	*
	9	* This library is free for commercial and non-commercial use as long as
	10	* the following conditions are aheared to. The following conditions
	11	* apply to all code found in this distribution, be it the RC4, RSA,
	12	* lhash, DES, etc., code; not just the SSL code. The SSL documentation
	13	* included with this distribution is covered by the same copyright terms
	14	* except that the holder is Tim Hudson (tjh@cryptsoft.com).
	15	*
	16	* Copyright remains Eric Young's, and as such any Copyright notices in
	17	* the code are not to be removed.
	18	* If this package is used in a product, Eric Young should be given attribution
	19	* as the author of the parts of the library used.
	20	* This can be in the form of a textual message at program startup or
	21	* in documentation (online or textual) provided with the package.
	22	*
	23	* Redistribution and use in source and binary forms, with or without
	24	* modification, are permitted provided that the following conditions
	25	* are met:
	26	* 1. Redistributions of source code must retain the copyright
	27	* notice, this list of conditions and the following disclaimer.
	28	* 2. Redistributions in binary form must reproduce the above copyright
	29	* notice, this list of conditions and the following disclaimer in the
	30	* documentation and/or other materials provided with the distribution.
	31	* 3. All advertising materials mentioning features or use of this software
	32	* must display the following acknowledgement:
	33	* "This product includes cryptographic software written by
	34	* Eric Young (eay@cryptsoft.com)"
	35	* The word 'cryptographic' can be left out if the rouines from the library
	36	* being used are not cryptographic related :-).
	37	* 4. If you include any Windows specific code (or a derivative thereof) from
	38	* the apps directory (application code) you must include an acknowledgement:
	39	* "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
	40	*
	41	* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
	42	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	43	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	44	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	45	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	46	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	47	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	48	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	49	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	50	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	51	* SUCH DAMAGE.
	52	*
	53	* The licence and distribution terms for any publically available version or
	54	* derivative of this code cannot be changed. i.e. this code cannot simply be
	55	* copied and put under another distribution licence
	56	* [including the GNU Public Licence.]
	57	*/
	58
	59	#include <stdio.h>
	60	#include "cryptlib.h"
	61	#include "bn_lcl.h"
	62
e778802f	63	const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT;
dfeab068 RE	64
	65	/* For a 32 bit machine
	66	* 2 - 4 == 128
	67	* 3 - 8 == 256
	68	* 4 - 16 == 512
	69	* 5 - 32 == 1024
	70	* 6 - 64 == 2048
	71	* 7 - 128 == 4096
	72	* 8 - 256 == 8192
	73	*/
7f0dae32 BM	74	OPENSSL_GLOBAL int bn_limit_bits=0;
	75	OPENSSL_GLOBAL int bn_limit_num=8; /* (1<<bn_limit_bits) */
	76	OPENSSL_GLOBAL int bn_limit_bits_low=0;
	77	OPENSSL_GLOBAL int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
	78	OPENSSL_GLOBAL int bn_limit_bits_high=0;
	79	OPENSSL_GLOBAL int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
	80	OPENSSL_GLOBAL int bn_limit_bits_mont=0;
	81	OPENSSL_GLOBAL int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
dfeab068	82
6b691a5c	83	void BN_set_params(int mult, int high, int low, int mont)
dfeab068 RE	84	{
	85	if (mult >= 0)
	86	{
	87	if (mult > (sizeof(int)*8)-1)
	88	mult=sizeof(int)*8-1;
	89	bn_limit_bits=mult;
	90	bn_limit_num=1<<mult;
	91	}
	92	if (high >= 0)
	93	{
	94	if (high > (sizeof(int)*8)-1)
	95	high=sizeof(int)*8-1;
	96	bn_limit_bits_high=high;
	97	bn_limit_num_high=1<<high;
	98	}
	99	if (low >= 0)
	100	{
	101	if (low > (sizeof(int)*8)-1)
	102	low=sizeof(int)*8-1;
	103	bn_limit_bits_low=low;
	104	bn_limit_num_low=1<<low;
	105	}
	106	if (mont >= 0)
	107	{
	108	if (mont > (sizeof(int)*8)-1)
	109	mont=sizeof(int)*8-1;
	110	bn_limit_bits_mont=mont;
	111	bn_limit_num_mont=1<<mont;
	112	}
	113	}
	114
6b691a5c	115	int BN_get_params(int which)
dfeab068 RE	116	{
	117	if (which == 0) return(bn_limit_bits);
	118	else if (which == 1) return(bn_limit_bits_high);
	119	else if (which == 2) return(bn_limit_bits_low);
	120	else if (which == 3) return(bn_limit_bits_mont);
	121	else return(0);
	122	}
d02b48c6	123
6b691a5c	124	BIGNUM *BN_value_one(void)
d02b48c6 RE	125	{
	126	static BN_ULONG data_one=1L;
	127	static BIGNUM const_one={&data_one,1,1,0};
	128
	129	return(&const_one);
	130	}
	131
6b691a5c	132	char *BN_options(void)
d02b48c6 RE	133	{
	134	static int init=0;
	135	static char data[16];
	136
	137	if (!init)
	138	{
	139	init++;
	140	#ifdef BN_LLONG
	141	sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
	142	(int)sizeof(BN_ULONG)*8);
	143	#else
	144	sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
	145	(int)sizeof(BN_ULONG)*8);
	146	#endif
	147	}
	148	return(data);
	149	}
	150
6b691a5c	151	int BN_num_bits_word(BN_ULONG l)
d02b48c6	152	{
e14d4443	153	static const char bits[256]={
d02b48c6 RE	154	0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
	155	5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
	156	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	157	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	158	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	159	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	160	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	161	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	162	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	163	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	164	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	165	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	166	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	167	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	168	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	169	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	170	};
	171
dfeab068	172	#if defined(SIXTY_FOUR_BIT_LONG)
d02b48c6 RE	173	if (l & 0xffffffff00000000L)
	174	{
	175	if (l & 0xffff000000000000L)
	176	{
	177	if (l & 0xff00000000000000L)
	178	{
dfeab068	179	return(bits[(int)(l>>56)]+56);
d02b48c6	180	}
dfeab068	181	else return(bits[(int)(l>>48)]+48);
d02b48c6 RE	182	}
	183	else
	184	{
	185	if (l & 0x0000ff0000000000L)
	186	{
dfeab068	187	return(bits[(int)(l>>40)]+40);
d02b48c6	188	}
dfeab068	189	else return(bits[(int)(l>>32)]+32);
d02b48c6 RE	190	}
	191	}
	192	else
	193	#else
	194	#ifdef SIXTY_FOUR_BIT
	195	if (l & 0xffffffff00000000LL)
	196	{
	197	if (l & 0xffff000000000000LL)
	198	{
	199	if (l & 0xff00000000000000LL)
	200	{
dfeab068	201	return(bits[(int)(l>>56)]+56);
d02b48c6	202	}
dfeab068	203	else return(bits[(int)(l>>48)]+48);
d02b48c6 RE	204	}
	205	else
	206	{
	207	if (l & 0x0000ff0000000000LL)
	208	{
dfeab068	209	return(bits[(int)(l>>40)]+40);
d02b48c6	210	}
dfeab068	211	else return(bits[(int)(l>>32)]+32);
d02b48c6 RE	212	}
	213	}
	214	else
	215	#endif
	216	#endif
	217	{
	218	#if defined(THIRTY_TWO_BIT) \|\| defined(SIXTY_FOUR_BIT) \|\| defined(SIXTY_FOUR_BIT_LONG)
	219	if (l & 0xffff0000L)
	220	{
	221	if (l & 0xff000000L)
dfeab068 RE	222	return(bits[(int)(l>>24L)]+24);
dfeab068 RE	223	else return(bits[(int)(l>>16L)]+16);
d02b48c6 RE	224	}
	225	else
	226	#endif
	227	{
	228	#if defined(SIXTEEN_BIT) \|\| defined(THIRTY_TWO_BIT) \|\| defined(SIXTY_FOUR_BIT) \|\| defined(SIXTY_FOUR_BIT_LONG)
	229	if (l & 0xff00L)
dfeab068	230	return(bits[(int)(l>>8)]+8);
d02b48c6 RE	231	else
d02b48c6 RE	232	#endif
dfeab068	233	return(bits[(int)(l )] );
d02b48c6 RE	234	}
	235	}
	236	}
	237
6b691a5c	238	int BN_num_bits(BIGNUM *a)
d02b48c6 RE	239	{
	240	BN_ULONG l;
	241	int i;
	242
dfeab068 RE	243	bn_check_top(a);
dfeab068 RE	244
d02b48c6 RE	245	if (a->top == 0) return(0);
	246	l=a->d[a->top-1];
	247	i=(a->top-1)*BN_BITS2;
	248	if (l == 0)
	249	{
58964a49	250	#if !defined(NO_STDIO) && !defined(WIN16)
d02b48c6 RE	251	fprintf(stderr,"BAD TOP VALUE\n");
	252	#endif
	253	abort();
	254	}
	255	return(i+BN_num_bits_word(l));
	256	}
	257
6b691a5c	258	void BN_clear_free(BIGNUM *a)
d02b48c6	259	{
dfeab068 RE	260	int i;
dfeab068 RE	261
d02b48c6 RE	262	if (a == NULL) return;
	263	if (a->d != NULL)
	264	{
	265	memset(a->d,0,a->max*sizeof(a->d[0]));
dfeab068 RE	266	if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
dfeab068 RE	267	Free(a->d);
d02b48c6	268	}
dfeab068	269	i=BN_get_flags(a,BN_FLG_MALLOCED);
d02b48c6	270	memset(a,0,sizeof(BIGNUM));
dfeab068 RE	271	if (i)
dfeab068 RE	272	Free(a);
d02b48c6 RE	273	}
d02b48c6 RE	274
6b691a5c	275	void BN_free(BIGNUM *a)
d02b48c6 RE	276	{
d02b48c6 RE	277	if (a == NULL) return;
dfeab068 RE	278	if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
	279	Free(a->d);
	280	a->flags\|=BN_FLG_FREE; /* REMOVE? */
	281	if (a->flags & BN_FLG_MALLOCED)
	282	Free(a);
	283	}
	284
6b691a5c	285	void BN_init(BIGNUM *a)
dfeab068 RE	286	{
dfeab068 RE	287	memset(a,0,sizeof(BIGNUM));
d02b48c6 RE	288	}
d02b48c6 RE	289
6b691a5c	290	BIGNUM *BN_new(void)
d02b48c6 RE	291	{
d02b48c6 RE	292	BIGNUM *ret;
d02b48c6	293
dfeab068 RE	294	if ((ret=(BIGNUM *)Malloc(sizeof(BIGNUM))) == NULL)
	295	{
	296	BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
	297	return(NULL);
	298	}
	299	ret->flags=BN_FLG_MALLOCED;
d02b48c6 RE	300	ret->top=0;
d02b48c6 RE	301	ret->neg=0;
dfeab068 RE	302	ret->max=0;
dfeab068 RE	303	ret->d=NULL;
d02b48c6	304	return(ret);
d02b48c6 RE	305	}
d02b48c6 RE	306
dfeab068	307
6b691a5c	308	BN_CTX *BN_CTX_new(void)
d02b48c6 RE	309	{
d02b48c6 RE	310	BN_CTX *ret;
d02b48c6 RE	311
d02b48c6 RE	312	ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
dfeab068	313	if (ret == NULL)
d02b48c6	314	{
dfeab068 RE	315	BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
dfeab068 RE	316	return(NULL);
d02b48c6 RE	317	}
d02b48c6 RE	318
dfeab068 RE	319	BN_CTX_init(ret);
dfeab068 RE	320	ret->flags=BN_FLG_MALLOCED;
d02b48c6	321	return(ret);
dfeab068 RE	322	}
dfeab068 RE	323
6b691a5c	324	void BN_CTX_init(BN_CTX *ctx)
dfeab068 RE	325	{
	326	memset(ctx,0,sizeof(BN_CTX));
	327	ctx->tos=0;
	328	ctx->flags=0;
d02b48c6 RE	329	}
d02b48c6 RE	330
6b691a5c	331	void BN_CTX_free(BN_CTX *c)
d02b48c6 RE	332	{
	333	int i;
	334
e03ddfae BL	335	if(c == NULL)
	336	return;
	337
d02b48c6	338	for (i=0; i<BN_CTX_NUM; i++)
dfeab068 RE	339	BN_clear_free(&(c->bn[i]));
	340	if (c->flags & BN_FLG_MALLOCED)
	341	Free(c);
d02b48c6 RE	342	}
d02b48c6 RE	343
6b691a5c	344	BIGNUM bn_expand2(BIGNUM b, int words)
d02b48c6	345	{
e14d4443 UM	346	BN_ULONG A,a;
	347	const BN_ULONG *B;
	348	int i;
dfeab068 RE	349
dfeab068 RE	350	bn_check_top(b);
d02b48c6	351
58964a49	352	if (words > b->max)
d02b48c6	353	{
dfeab068 RE	354	bn_check_top(b);
	355	if (BN_get_flags(b,BN_FLG_STATIC_DATA))
	356	{
	357	BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
	358	return(NULL);
	359	}
	360	a=A=(BN_ULONG )Malloc(sizeof(BN_ULONG)(words+1));
	361	if (A == NULL)
d02b48c6 RE	362	{
	363	BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
	364	return(NULL);
	365	}
dfeab068 RE	366	#if 1
dfeab068 RE	367	B=b->d;
953937bd	368	/* Check if the previous number needs to be copied */
dfeab068 RE	369	if (B != NULL)
dfeab068 RE	370	{
e14d4443	371	#if 0
953937bd DSH	372	/* This lot is an unrolled loop to copy b->top
	373	* BN_ULONGs from B to A
	374	*/
e14d4443 UM	375	/*
	376	* I have nothing against unrolling but it's usually done for
	377	* several reasons, namely:
	378	* - minimize percentage of decision making code, i.e. branches;
	379	* - avoid cache trashing;
	380	* - make it possible to schedule loads earlier;
	381	* Now let's examine the code below. The cornerstone of C is
	382	* "programmer is always right" and that's what we love it for:-)
	383	* For this very reason C compilers have to be paranoid when it
	384	* comes to data aliasing and assume the worst. Yeah, but what
	385	* does it mean in real life? This means that loop body below will
	386	* be compiled to sequence of loads immediately followed by stores
	387	* as compiler assumes the worst, something in A==B+1 style. As a
	388	* result CPU pipeline is going to starve for incoming data. Secondly
	389	* if A and B happen to share same cache line such code is going to
	390	* cause severe cache trashing. Both factors have severe impact on
	391	* performance of modern CPUs and this is the reason why this
	392	* particulare piece of code is #ifdefed away and replaced by more
	393	* "friendly" version found in #else section below. This comment
	394	* also applies to BN_copy function.
	395	*
	396	* <appro@fy.chalmers.se>
	397	*/
dfeab068 RE	398	for (i=b->top&(~7); i>0; i-=8)
	399	{
	400	A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
	401	A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
	402	A+=8;
	403	B+=8;
	404	}
	405	switch (b->top&7)
	406	{
	407	case 7:
	408	A[6]=B[6];
	409	case 6:
	410	A[5]=B[5];
	411	case 5:
	412	A[4]=B[4];
	413	case 4:
	414	A[3]=B[3];
	415	case 3:
	416	A[2]=B[2];
	417	case 2:
	418	A[1]=B[1];
	419	case 1:
	420	A[0]=B[0];
	421	case 0:
	422	/* I need the 'case 0' entry for utrix cc.
	423	* If the optimiser is turned on, it does the
	424	* switch table by doing
	425	* a=top&7
	426	* a--;
	427	* goto jump_table[a];
	428	* If top is 0, this makes us jump to 0xffffffc
	429	* which is rather bad :-(.
	430	* eric 23-Apr-1998
	431	*/
	432	;
	433	}
e14d4443 UM	434	#else
	435	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
	436	{
	437	/*
	438	* The fact that the loop is unrolled
	439	* 4-wise is a tribute to Intel. It's
	440	* the one that doesn't have enough
	441	* registers to accomodate more data.
	442	* I'd unroll it 8-wise otherwise:-)
	443	*
	444	* <appro@fy.chalmers.se>
	445	*/
	446	BN_ULONG a0,a1,a2,a3;
	447	a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
	448	A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
	449	}
	450	switch (b->top&3)
	451	{
	452	case 3: A[2]=B[2];
	453	case 2: A[1]=B[1];
	454	case 1: A[0]=B[0];
	455	case 0: ; /* ultrix cc workaround, see above */
	456	}
	457	#endif
953937bd DSH	458	Free(b->d);
	459	}
	460
	461	b->d=a;
	462	b->max=words;
	463
	464	/* Now need to zero any data between b->top and b->max */
	465
e14d4443 UM	466	A= &(b->d[b->top]);
e14d4443 UM	467	for (i=(b->max - b->top)>>3; i>0; i--,A+=8)
953937bd	468	{
e14d4443 UM	469	A[0]=0; A[1]=0; A[2]=0; A[3]=0;
e14d4443 UM	470	A[4]=0; A[5]=0; A[6]=0; A[7]=0;
953937bd	471	}
e14d4443 UM	472	for (i=(b->max - b->top)&7; i>0; i--,A++)
e14d4443 UM	473	A[0]=0;
dfeab068	474	#else
e14d4443 UM	475	memset(A,0,sizeof(BN_ULONG)*(words+1));
	476	memcpy(A,b->d,sizeof(b->d[0])*b->top);
	477	b->d=a;
	478	b->max=words;
dfeab068 RE	479	#endif
	480
	481	/* memset(&(p[b->max]),0,((words+1)-b->max)sizeof(BN_ULONG)); /
	482	/* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
dfeab068	483
d02b48c6 RE	484	}
	485	return(b);
	486	}
	487
6b691a5c	488	BIGNUM BN_dup(BIGNUM a)
d02b48c6 RE	489	{
	490	BIGNUM *r;
	491
dfeab068 RE	492	bn_check_top(a);
dfeab068 RE	493
d02b48c6 RE	494	r=BN_new();
	495	if (r == NULL) return(NULL);
	496	return((BIGNUM *)BN_copy(r,a));
	497	}
	498
6b691a5c	499	BIGNUM BN_copy(BIGNUM a, BIGNUM *b)
d02b48c6	500	{
58964a49	501	int i;
e14d4443 UM	502	BN_ULONG *A;
e14d4443 UM	503	const BN_ULONG *B;
58964a49	504
dfeab068 RE	505	bn_check_top(b);
dfeab068 RE	506
58964a49 RE	507	if (a == b) return(a);
	508	if (bn_wexpand(a,b->top) == NULL) return(NULL);
	509
	510	#if 1
	511	A=a->d;
	512	B=b->d;
e14d4443	513	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
58964a49	514	{
e14d4443 UM	515	BN_ULONG a0,a1,a2,a3;
	516	a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
	517	A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
58964a49	518	}
e14d4443	519	switch (b->top&3)
58964a49	520	{
e14d4443 UM	521	case 3: A[2]=B[2];
	522	case 2: A[1]=B[1];
	523	case 1: A[0]=B[0];
	524	case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
58964a49 RE	525	}
58964a49 RE	526	#else
d02b48c6	527	memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
58964a49 RE	528	#endif
58964a49 RE	529
d02b48c6 RE	530	/* memset(&(a->d[b->top]),0,sizeof(a->d[0])(a->max-b->top));/
d02b48c6 RE	531	a->top=b->top;
dfeab068	532	if ((a->top == 0) && (a->d != NULL))
58964a49	533	a->d[0]=0;
d02b48c6 RE	534	a->neg=b->neg;
	535	return(a);
	536	}
	537
6b691a5c	538	void BN_clear(BIGNUM *a)
d02b48c6	539	{
dfeab068 RE	540	if (a->d != NULL)
dfeab068 RE	541	memset(a->d,0,a->max*sizeof(a->d[0]));
d02b48c6 RE	542	a->top=0;
	543	a->neg=0;
	544	}
	545
6b691a5c	546	BN_ULONG BN_get_word(BIGNUM *a)
d02b48c6 RE	547	{
d02b48c6 RE	548	int i,n;
dfeab068	549	BN_ULONG ret=0;
d02b48c6 RE	550
d02b48c6 RE	551	n=BN_num_bytes(a);
dfeab068	552	if (n > sizeof(BN_ULONG))
d02b48c6	553	return(BN_MASK2);
d02b48c6 RE	554	for (i=a->top-1; i>=0; i--)
	555	{
	556	#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
	557	ret<<=BN_BITS4; /* stops the compiler complaining */
	558	ret<<=BN_BITS4;
e14d4443 UM	559	#else
e14d4443 UM	560	ret=0;
d02b48c6 RE	561	#endif
	562	ret\|=a->d[i];
	563	}
	564	return(ret);
	565	}
	566
6b691a5c	567	int BN_set_word(BIGNUM *a, BN_ULONG w)
d02b48c6 RE	568	{
d02b48c6 RE	569	int i,n;
dfeab068	570	if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
d02b48c6	571
dfeab068	572	n=sizeof(BN_ULONG)/BN_BYTES;
d02b48c6 RE	573	a->neg=0;
	574	a->top=0;
	575	a->d[0]=(BN_ULONG)w&BN_MASK2;
	576	if (a->d[0] != 0) a->top=1;
	577	for (i=1; i<n; i++)
	578	{
	579	/* the following is done instead of
	580	* w>>=BN_BITS2 so compilers don't complain
	581	* on builds where sizeof(long) == BN_TYPES */
	582	#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
	583	w>>=BN_BITS4;
	584	w>>=BN_BITS4;
e14d4443 UM	585	#else
e14d4443 UM	586	w=0;
d02b48c6 RE	587	#endif
	588	a->d[i]=(BN_ULONG)w&BN_MASK2;
	589	if (a->d[i] != 0) a->top=i+1;
	590	}
	591	return(1);
	592	}
	593
	594	/* ignore negative */
61f5b6f3	595	BIGNUM BN_bin2bn(const unsigned char s, int len, BIGNUM *ret)
d02b48c6 RE	596	{
	597	unsigned int i,m;
	598	unsigned int n;
	599	BN_ULONG l;
	600
	601	if (ret == NULL) ret=BN_new();
	602	if (ret == NULL) return(NULL);
	603	l=0;
	604	n=len;
	605	if (n == 0)
	606	{
	607	ret->top=0;
	608	return(ret);
	609	}
	610	if (bn_expand(ret,(int)(n+2)*8) == NULL)
	611	return(NULL);
	612	i=((n-1)/BN_BYTES)+1;
	613	m=((n-1)%(BN_BYTES));
	614	ret->top=i;
	615	while (n-- > 0)
	616	{
	617	l=(l<<8L)\| *(s++);
	618	if (m-- == 0)
	619	{
	620	ret->d[--i]=l;
	621	l=0;
	622	m=BN_BYTES-1;
	623	}
	624	}
	625	/* need to call this due to clear byte at top if avoiding
	626	* having the top bit set (-ve number) */
	627	bn_fix_top(ret);
	628	return(ret);
	629	}
	630
	631	/* ignore negative */
6b691a5c	632	int BN_bn2bin(BIGNUM a, unsigned char to)
d02b48c6 RE	633	{
	634	int n,i;
	635	BN_ULONG l;
	636
	637	n=i=BN_num_bytes(a);
	638	while (i-- > 0)
	639	{
	640	l=a->d[i/BN_BYTES];
	641	(to++)=(unsigned char)(l>>(8(i%BN_BYTES)))&0xff;
	642	}
	643	return(n);
	644	}
	645
6b691a5c	646	int BN_ucmp(BIGNUM a, BIGNUM b)
d02b48c6 RE	647	{
	648	int i;
	649	BN_ULONG t1,t2,ap,bp;
	650
dfeab068 RE	651	bn_check_top(a);
	652	bn_check_top(b);
	653
d02b48c6 RE	654	i=a->top-b->top;
	655	if (i != 0) return(i);
	656	ap=a->d;
	657	bp=b->d;
	658	for (i=a->top-1; i>=0; i--)
	659	{
	660	t1= ap[i];
	661	t2= bp[i];
	662	if (t1 != t2)
	663	return(t1 > t2?1:-1);
	664	}
	665	return(0);
	666	}
	667
6b691a5c	668	int BN_cmp(BIGNUM a, BIGNUM b)
d02b48c6 RE	669	{
	670	int i;
	671	int gt,lt;
	672	BN_ULONG t1,t2;
	673
	674	if ((a == NULL) \|\| (b == NULL))
	675	{
	676	if (a != NULL)
	677	return(-1);
	678	else if (b != NULL)
	679	return(1);
	680	else
	681	return(0);
	682	}
dfeab068 RE	683
	684	bn_check_top(a);
	685	bn_check_top(b);
	686
d02b48c6 RE	687	if (a->neg != b->neg)
	688	{
	689	if (a->neg)
	690	return(-1);
	691	else return(1);
	692	}
	693	if (a->neg == 0)
	694	{ gt=1; lt= -1; }
	695	else { gt= -1; lt=1; }
	696
	697	if (a->top > b->top) return(gt);
	698	if (a->top < b->top) return(lt);
	699	for (i=a->top-1; i>=0; i--)
	700	{
	701	t1=a->d[i];
	702	t2=b->d[i];
	703	if (t1 > t2) return(gt);
	704	if (t1 < t2) return(lt);
	705	}
	706	return(0);
	707	}
	708
6b691a5c	709	int BN_set_bit(BIGNUM *a, int n)
d02b48c6	710	{
dfeab068	711	int i,j,k;
d02b48c6 RE	712
	713	i=n/BN_BITS2;
	714	j=n%BN_BITS2;
58964a49 RE	715	if (a->top <= i)
58964a49 RE	716	{
dfeab068 RE	717	if (bn_wexpand(a,i+1) == NULL) return(0);
	718	for(k=a->top; k<i+1; k++)
	719	a->d[k]=0;
58964a49 RE	720	a->top=i+1;
58964a49 RE	721	}
d02b48c6	722
e14d4443	723	a->d[i]\|=(((BN_ULONG)1)<<j);
d02b48c6 RE	724	return(1);
	725	}
	726
6b691a5c	727	int BN_clear_bit(BIGNUM *a, int n)
d02b48c6 RE	728	{
	729	int i,j;
	730
	731	i=n/BN_BITS2;
	732	j=n%BN_BITS2;
	733	if (a->top <= i) return(0);
	734
e14d4443	735	a->d[i]&=(~(((BN_ULONG)1)<<j));
dfeab068	736	bn_fix_top(a);
d02b48c6 RE	737	return(1);
	738	}
	739
6b691a5c	740	int BN_is_bit_set(BIGNUM *a, int n)
d02b48c6 RE	741	{
	742	int i,j;
	743
	744	if (n < 0) return(0);
	745	i=n/BN_BITS2;
	746	j=n%BN_BITS2;
	747	if (a->top <= i) return(0);
	748	return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
	749	}
	750
6b691a5c	751	int BN_mask_bits(BIGNUM *a, int n)
d02b48c6 RE	752	{
	753	int b,w;
	754
	755	w=n/BN_BITS2;
	756	b=n%BN_BITS2;
	757	if (w >= a->top) return(0);
	758	if (b == 0)
	759	a->top=w;
	760	else
	761	{
	762	a->top=w+1;
	763	a->d[w]&= ~(BN_MASK2<<b);
d02b48c6	764	}
dfeab068	765	bn_fix_top(a);
d02b48c6 RE	766	return(1);
d02b48c6 RE	767	}
dfeab068	768
6b691a5c	769	int bn_cmp_words(BN_ULONG a, BN_ULONG b, int n)
dfeab068 RE	770	{
	771	int i;
	772	BN_ULONG aa,bb;
	773
	774	aa=a[n-1];
	775	bb=b[n-1];
	776	if (aa != bb) return((aa > bb)?1:-1);
	777	for (i=n-2; i>=0; i--)
	778	{
	779	aa=a[i];
	780	bb=b[i];
	781	if (aa != bb) return((aa > bb)?1:-1);
	782	}
	783	return(0);
	784	}
	785