[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.]
 */

#ifndef BN_DEBUG
# undef NDEBUG /* avoid conflicting definitions */
# define NDEBUG
#endif

#include <assert.h>
#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
 */
static int bn_limit_bits=0;
static int bn_limit_num=8;        /* (1<<bn_limit_bits) */
static int bn_limit_bits_low=0;
static int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
static int bn_limit_bits_high=0;
static int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
static int bn_limit_bits_mont=0;
static 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(const BIGNUM *a)
	{
	BN_ULONG l;
	int i;

	bn_check_top(a);

	if (a->top == 0) return(0);
	l=a->d[a->top-1];
	assert(l != 0);
	i=(a->top-1)*BN_BITS2;
	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->dmax*sizeof(a->d[0]));
		if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
			OPENSSL_free(a->d);
		}
	i=BN_get_flags(a,BN_FLG_MALLOCED);
	memset(a,0,sizeof(BIGNUM));
	if (i)
		OPENSSL_free(a);
	}

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

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

BIGNUM *BN_new(void)
	{
	BIGNUM *ret;

	if ((ret=(BIGNUM *)OPENSSL_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->dmax=0;
	ret->d=NULL;
	return(ret);
	}

/* This is used both by bn_expand2() and bn_dup_expand() */
/* The caller MUST check that words > b->dmax before calling this */
static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
	{
	BN_ULONG *A,*a = NULL;
	const BN_ULONG *B;
	int i;

	bn_check_top(b);	
	if (BN_get_flags(b,BN_FLG_STATIC_DATA))
		{
		BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
		return(NULL);
		}
	a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1));
	if (A == NULL)
		{
		BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
		return(NULL);
		}
#if 1
	B=b->d;
	/* Check if the previous number needs to be copied */
	if (B != NULL)
		{
		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: /* workaround for ultrix cc: without 'case 0', the optimizer does
		         * the switch table by doing a=top&3; a--; goto jump_table[a];
		         * which fails for top== 0 */
			;
			}
		}

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

	A= &(a[b->top]);
	for (i=(words - 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=(words - 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);
#endif
		
	return(a);
	}

/* This is an internal function that can be used instead of bn_expand2()
 * when there is a need to copy BIGNUMs instead of only expanding the
 * data part, while still expanding them.
 * Especially useful when needing to expand BIGNUMs that are declared
 * 'const' and should therefore not be changed.
 * The reason to use this instead of a BN_dup() followed by a bn_expand2()
 * is memory allocation overhead.  A BN_dup() followed by a bn_expand2()
 * will allocate new memory for the BIGNUM data twice, and free it once,
 * while bn_dup_expand() makes sure allocation is made only once.
 */

BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
	{
	BIGNUM *r = NULL;

	if (words > b->dmax)
		{
		BN_ULONG *a = bn_expand_internal(b, words);

		if (a)
			{
			r = BN_new();
			if (r)
				{
				r->top = b->top;
				r->dmax = words;
				r->neg = b->neg;
				r->d = a;
				}
			else
				{
				/* r == NULL, BN_new failure */
				OPENSSL_free(a);
				}
			}
		/* If a == NULL, there was an error in allocation in
		   bn_expand_internal(), and NULL should be returned */
		}
	else
		{
		r = BN_dup(b);
		}

	return r;
	}

/* This is an internal function that should not be used in applications.
 * It ensures that 'b' has enough room for a 'words' word number number.
 * It is mostly used by the various BIGNUM routines. If there is an error,
 * NULL is returned. If not, 'b' is returned. */

BIGNUM *bn_expand2(BIGNUM *b, int words)
	{
	if (words > b->dmax)
		{
		BN_ULONG *a = bn_expand_internal(b, words);

		if (a)
			{
			if (b->d)
				OPENSSL_free(b->d);
			b->d=a;
			b->dmax=words;
			}
		else
			b = NULL;
		}
	return b;
	}

BIGNUM *BN_dup(const BIGNUM *a)
	{
	BIGNUM *r, *t;

	if (a == NULL) return NULL;

	bn_check_top(a);

	t = BN_new();
	if (t == NULL) return(NULL);
	r = BN_copy(t, a);
	/* now  r == t || r == NULL */
	if (r == NULL)
		BN_free(t);
	return r;
	}

BIGNUM *BN_copy(BIGNUM *a, const 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_expand_internal */
		}
#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_swap(BIGNUM *a, BIGNUM *b)
	{
	int flags_old_a, flags_old_b;
	BN_ULONG *tmp_d;
	int tmp_top, tmp_dmax, tmp_neg;
	
	flags_old_a = a->flags;
	flags_old_b = b->flags;

	tmp_d = a->d;
	tmp_top = a->top;
	tmp_dmax = a->dmax;
	tmp_neg = a->neg;
	
	a->d = b->d;
	a->top = b->top;
	a->dmax = b->dmax;
	a->neg = b->neg;
	
	b->d = tmp_d;
	b->top = tmp_top;
	b->dmax = tmp_dmax;
	b->neg = tmp_neg;
	
	a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
	b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
	}


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

BN_ULONG BN_get_word(const 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);
	}

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;
	ret->neg=0;
	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(const 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(const BIGNUM *a, const 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(const BIGNUM *a, const 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(const 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(const BN_ULONG *a, const 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
bbb8de09 BM	59	#ifndef BN_DEBUG
	60	# undef NDEBUG /* avoid conflicting definitions */
	61	# define NDEBUG
	62	#endif
	63
	64	#include <assert.h>
d02b48c6 RE	65	#include <stdio.h>
	66	#include "cryptlib.h"
	67	#include "bn_lcl.h"
	68
e778802f	69	const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT;
dfeab068 RE	70
	71	/* For a 32 bit machine
	72	* 2 - 4 == 128
	73	* 3 - 8 == 256
	74	* 4 - 16 == 512
	75	* 5 - 32 == 1024
	76	* 6 - 64 == 2048
	77	* 7 - 128 == 4096
	78	* 8 - 256 == 8192
	79	*/
775c63fc UM	80	static int bn_limit_bits=0;
	81	static int bn_limit_num=8; /* (1<<bn_limit_bits) */
	82	static int bn_limit_bits_low=0;
	83	static int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
	84	static int bn_limit_bits_high=0;
	85	static int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
	86	static int bn_limit_bits_mont=0;
	87	static int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
dfeab068	88
6b691a5c	89	void BN_set_params(int mult, int high, int low, int mont)
dfeab068 RE	90	{
	91	if (mult >= 0)
	92	{
	93	if (mult > (sizeof(int)*8)-1)
	94	mult=sizeof(int)*8-1;
	95	bn_limit_bits=mult;
	96	bn_limit_num=1<<mult;
	97	}
	98	if (high >= 0)
	99	{
	100	if (high > (sizeof(int)*8)-1)
	101	high=sizeof(int)*8-1;
	102	bn_limit_bits_high=high;
	103	bn_limit_num_high=1<<high;
	104	}
	105	if (low >= 0)
	106	{
	107	if (low > (sizeof(int)*8)-1)
	108	low=sizeof(int)*8-1;
	109	bn_limit_bits_low=low;
	110	bn_limit_num_low=1<<low;
	111	}
	112	if (mont >= 0)
	113	{
	114	if (mont > (sizeof(int)*8)-1)
	115	mont=sizeof(int)*8-1;
	116	bn_limit_bits_mont=mont;
	117	bn_limit_num_mont=1<<mont;
	118	}
	119	}
	120
6b691a5c	121	int BN_get_params(int which)
dfeab068 RE	122	{
	123	if (which == 0) return(bn_limit_bits);
	124	else if (which == 1) return(bn_limit_bits_high);
	125	else if (which == 2) return(bn_limit_bits_low);
	126	else if (which == 3) return(bn_limit_bits_mont);
	127	else return(0);
	128	}
d02b48c6	129
6b691a5c	130	BIGNUM *BN_value_one(void)
d02b48c6 RE	131	{
	132	static BN_ULONG data_one=1L;
	133	static BIGNUM const_one={&data_one,1,1,0};
	134
	135	return(&const_one);
	136	}
	137
6b691a5c	138	char *BN_options(void)
d02b48c6 RE	139	{
	140	static int init=0;
	141	static char data[16];
	142
	143	if (!init)
	144	{
	145	init++;
	146	#ifdef BN_LLONG
	147	sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
	148	(int)sizeof(BN_ULONG)*8);
	149	#else
	150	sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
	151	(int)sizeof(BN_ULONG)*8);
	152	#endif
	153	}
	154	return(data);
	155	}
	156
6b691a5c	157	int BN_num_bits_word(BN_ULONG l)
d02b48c6	158	{
e14d4443	159	static const char bits[256]={
d02b48c6 RE	160	0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
	161	5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
	162	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	163	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	164	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	165	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	166	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	167	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	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	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	171	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	172	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	173	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	174	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	175	8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
	176	};
	177
dfeab068	178	#if defined(SIXTY_FOUR_BIT_LONG)
d02b48c6 RE	179	if (l & 0xffffffff00000000L)
	180	{
	181	if (l & 0xffff000000000000L)
	182	{
	183	if (l & 0xff00000000000000L)
	184	{
dfeab068	185	return(bits[(int)(l>>56)]+56);
d02b48c6	186	}
dfeab068	187	else return(bits[(int)(l>>48)]+48);
d02b48c6 RE	188	}
	189	else
	190	{
	191	if (l & 0x0000ff0000000000L)
	192	{
dfeab068	193	return(bits[(int)(l>>40)]+40);
d02b48c6	194	}
dfeab068	195	else return(bits[(int)(l>>32)]+32);
d02b48c6 RE	196	}
	197	}
	198	else
	199	#else
	200	#ifdef SIXTY_FOUR_BIT
	201	if (l & 0xffffffff00000000LL)
	202	{
	203	if (l & 0xffff000000000000LL)
	204	{
	205	if (l & 0xff00000000000000LL)
	206	{
dfeab068	207	return(bits[(int)(l>>56)]+56);
d02b48c6	208	}
dfeab068	209	else return(bits[(int)(l>>48)]+48);
d02b48c6 RE	210	}
	211	else
	212	{
	213	if (l & 0x0000ff0000000000LL)
	214	{
dfeab068	215	return(bits[(int)(l>>40)]+40);
d02b48c6	216	}
dfeab068	217	else return(bits[(int)(l>>32)]+32);
d02b48c6 RE	218	}
	219	}
	220	else
	221	#endif
	222	#endif
	223	{
	224	#if defined(THIRTY_TWO_BIT) \|\| defined(SIXTY_FOUR_BIT) \|\| defined(SIXTY_FOUR_BIT_LONG)
	225	if (l & 0xffff0000L)
	226	{
	227	if (l & 0xff000000L)
dfeab068 RE	228	return(bits[(int)(l>>24L)]+24);
dfeab068 RE	229	else return(bits[(int)(l>>16L)]+16);
d02b48c6 RE	230	}
	231	else
	232	#endif
	233	{
	234	#if defined(SIXTEEN_BIT) \|\| defined(THIRTY_TWO_BIT) \|\| defined(SIXTY_FOUR_BIT) \|\| defined(SIXTY_FOUR_BIT_LONG)
	235	if (l & 0xff00L)
dfeab068	236	return(bits[(int)(l>>8)]+8);
d02b48c6 RE	237	else
d02b48c6 RE	238	#endif
dfeab068	239	return(bits[(int)(l )] );
d02b48c6 RE	240	}
	241	}
	242	}
	243
84c15db5	244	int BN_num_bits(const BIGNUM *a)
d02b48c6 RE	245	{
	246	BN_ULONG l;
	247	int i;
	248
dfeab068 RE	249	bn_check_top(a);
dfeab068 RE	250
d02b48c6 RE	251	if (a->top == 0) return(0);
d02b48c6 RE	252	l=a->d[a->top-1];
bbb8de09	253	assert(l != 0);
d02b48c6	254	i=(a->top-1)*BN_BITS2;
d02b48c6 RE	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	{
2d978cbd	265	memset(a->d,0,a->dmax*sizeof(a->d[0]));
dfeab068	266	if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
26a3a48d	267	OPENSSL_free(a->d);
d02b48c6	268	}
dfeab068	269	i=BN_get_flags(a,BN_FLG_MALLOCED);
d02b48c6	270	memset(a,0,sizeof(BIGNUM));
dfeab068	271	if (i)
26a3a48d	272	OPENSSL_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	278	if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
26a3a48d	279	OPENSSL_free(a->d);
dfeab068 RE	280	a->flags\|=BN_FLG_FREE; /* REMOVE? */
dfeab068 RE	281	if (a->flags & BN_FLG_MALLOCED)
26a3a48d	282	OPENSSL_free(a);
dfeab068 RE	283	}
dfeab068 RE	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
26a3a48d	294	if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL)
dfeab068 RE	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;
2d978cbd	302	ret->dmax=0;
dfeab068	303	ret->d=NULL;
d02b48c6	304	return(ret);
d02b48c6 RE	305	}
d02b48c6 RE	306
020fc820 RL	307	/* This is used both by bn_expand2() and bn_dup_expand() */
020fc820 RL	308	/* The caller MUST check that words > b->dmax before calling this */
a08bcccc	309	static BN_ULONG bn_expand_internal(const BIGNUM b, int words)
d02b48c6	310	{
020fc820	311	BN_ULONG A,a = NULL;
e14d4443 UM	312	const BN_ULONG *B;
e14d4443 UM	313	int i;
dfeab068	314
020fc820 RL	315	bn_check_top(b);
020fc820 RL	316	if (BN_get_flags(b,BN_FLG_STATIC_DATA))
d02b48c6	317	{
a08bcccc	318	BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
020fc820 RL	319	return(NULL);
	320	}
	321	a=A=(BN_ULONG )OPENSSL_malloc(sizeof(BN_ULONG)(words+1));
	322	if (A == NULL)
	323	{
a08bcccc	324	BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
020fc820 RL	325	return(NULL);
020fc820 RL	326	}
dfeab068	327	#if 1
020fc820 RL	328	B=b->d;
	329	/* Check if the previous number needs to be copied */
	330	if (B != NULL)
	331	{
020fc820 RL	332	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
	333	{
	334	/*
	335	* The fact that the loop is unrolled
	336	* 4-wise is a tribute to Intel. It's
	337	* the one that doesn't have enough
	338	* registers to accomodate more data.
	339	* I'd unroll it 8-wise otherwise:-)
	340	*
	341	* <appro@fy.chalmers.se>
	342	*/
	343	BN_ULONG a0,a1,a2,a3;
	344	a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
	345	A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
953937bd	346	}
020fc820	347	switch (b->top&3)
953937bd	348	{
020fc820 RL	349	case 3: A[2]=B[2];
	350	case 2: A[1]=B[1];
	351	case 1: A[0]=B[0];
a08bcccc BM	352	case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does
	353	* the switch table by doing a=top&3; a--; goto jump_table[a];
	354	* which fails for top== 0 */
	355	;
953937bd	356	}
020fc820 RL	357	}
	358
	359	/* Now need to zero any data between b->top and b->max */
03a08489	360	/* XXX Why? */
020fc820 RL	361
	362	A= &(a[b->top]);
	363	for (i=(words - b->top)>>3; i>0; i--,A+=8)
	364	{
	365	A[0]=0; A[1]=0; A[2]=0; A[3]=0;
	366	A[4]=0; A[5]=0; A[6]=0; A[7]=0;
	367	}
	368	for (i=(words - b->top)&7; i>0; i--,A++)
	369	A[0]=0;
dfeab068	370	#else
020fc820 RL	371	memset(A,0,sizeof(BN_ULONG)*(words+1));
020fc820 RL	372	memcpy(A,b->d,sizeof(b->d[0])*b->top);
dfeab068 RE	373	#endif
dfeab068 RE	374
020fc820 RL	375	return(a);
020fc820 RL	376	}
dfeab068	377
020fc820 RL	378	/* This is an internal function that can be used instead of bn_expand2()
	379	* when there is a need to copy BIGNUMs instead of only expanding the
	380	* data part, while still expanding them.
	381	* Especially useful when needing to expand BIGNUMs that are declared
	382	* 'const' and should therefore not be changed.
	383	* The reason to use this instead of a BN_dup() followed by a bn_expand2()
	384	* is memory allocation overhead. A BN_dup() followed by a bn_expand2()
	385	* will allocate new memory for the BIGNUM data twice, and free it once,
	386	* while bn_dup_expand() makes sure allocation is made only once.
	387	*/
	388
	389	BIGNUM bn_dup_expand(const BIGNUM b, int words)
	390	{
	391	BIGNUM *r = NULL;
	392
	393	if (words > b->dmax)
	394	{
a08bcccc	395	BN_ULONG *a = bn_expand_internal(b, words);
020fc820 RL	396
	397	if (a)
	398	{
	399	r = BN_new();
58f0f52e BM	400	if (r)
	401	{
	402	r->top = b->top;
	403	r->dmax = words;
	404	r->neg = b->neg;
	405	r->d = a;
	406	}
	407	else
	408	{
	409	/* r == NULL, BN_new failure */
	410	OPENSSL_free(a);
	411	}
020fc820	412	}
58f0f52e	413	/* If a == NULL, there was an error in allocation in
a08bcccc	414	bn_expand_internal(), and NULL should be returned */
020fc820 RL	415	}
	416	else
	417	{
	418	r = BN_dup(b);
	419	}
	420
	421	return r;
	422	}
	423
	424	/* This is an internal function that should not be used in applications.
	425	* It ensures that 'b' has enough room for a 'words' word number number.
	426	* It is mostly used by the various BIGNUM routines. If there is an error,
	427	* NULL is returned. If not, 'b' is returned. */
	428
	429	BIGNUM bn_expand2(BIGNUM b, int words)
	430	{
	431	if (words > b->dmax)
	432	{
a08bcccc	433	BN_ULONG *a = bn_expand_internal(b, words);
020fc820 RL	434
	435	if (a)
	436	{
a08bcccc BM	437	if (b->d)
a08bcccc BM	438	OPENSSL_free(b->d);
020fc820 RL	439	b->d=a;
	440	b->dmax=words;
	441	}
	442	else
	443	b = NULL;
d02b48c6	444	}
020fc820	445	return b;
d02b48c6 RE	446	}
d02b48c6 RE	447
84c15db5	448	BIGNUM BN_dup(const BIGNUM a)
d02b48c6	449	{
e0bf5c11	450	BIGNUM r, t;
d02b48c6	451
8d85b33e BM	452	if (a == NULL) return NULL;
8d85b33e BM	453
dfeab068 RE	454	bn_check_top(a);
dfeab068 RE	455
e0bf5c11 BM	456	t = BN_new();
	457	if (t == NULL) return(NULL);
	458	r = BN_copy(t, a);
	459	/* now r == t \|\| r == NULL */
	460	if (r == NULL)
	461	BN_free(t);
	462	return r;
d02b48c6 RE	463	}
d02b48c6 RE	464
84c15db5	465	BIGNUM BN_copy(BIGNUM a, const BIGNUM *b)
d02b48c6	466	{
58964a49	467	int i;
e14d4443 UM	468	BN_ULONG *A;
e14d4443 UM	469	const BN_ULONG *B;
58964a49	470
dfeab068 RE	471	bn_check_top(b);
dfeab068 RE	472
58964a49 RE	473	if (a == b) return(a);
	474	if (bn_wexpand(a,b->top) == NULL) return(NULL);
	475
	476	#if 1
	477	A=a->d;
	478	B=b->d;
e14d4443	479	for (i=b->top>>2; i>0; i--,A+=4,B+=4)
58964a49	480	{
e14d4443 UM	481	BN_ULONG a0,a1,a2,a3;
	482	a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
	483	A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
58964a49	484	}
e14d4443	485	switch (b->top&3)
58964a49	486	{
e14d4443 UM	487	case 3: A[2]=B[2];
	488	case 2: A[1]=B[1];
	489	case 1: A[0]=B[0];
a08bcccc	490	case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */
58964a49 RE	491	}
58964a49 RE	492	#else
d02b48c6	493	memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
58964a49 RE	494	#endif
58964a49 RE	495
d02b48c6 RE	496	/* memset(&(a->d[b->top]),0,sizeof(a->d[0])(a->max-b->top));/
d02b48c6 RE	497	a->top=b->top;
dfeab068	498	if ((a->top == 0) && (a->d != NULL))
58964a49	499	a->d[0]=0;
d02b48c6 RE	500	a->neg=b->neg;
	501	return(a);
	502	}
	503
78a0c1f1 BM	504	void BN_swap(BIGNUM a, BIGNUM b)
	505	{
	506	int flags_old_a, flags_old_b;
	507	BN_ULONG *tmp_d;
	508	int tmp_top, tmp_dmax, tmp_neg;
	509
	510	flags_old_a = a->flags;
	511	flags_old_b = b->flags;
	512
	513	tmp_d = a->d;
	514	tmp_top = a->top;
	515	tmp_dmax = a->dmax;
	516	tmp_neg = a->neg;
	517
	518	a->d = b->d;
	519	a->top = b->top;
	520	a->dmax = b->dmax;
	521	a->neg = b->neg;
	522
	523	b->d = tmp_d;
	524	b->top = tmp_top;
	525	b->dmax = tmp_dmax;
	526	b->neg = tmp_neg;
	527
	528	a->flags = (flags_old_a & BN_FLG_MALLOCED) \| (flags_old_b & BN_FLG_STATIC_DATA);
	529	b->flags = (flags_old_b & BN_FLG_MALLOCED) \| (flags_old_a & BN_FLG_STATIC_DATA);
	530	}
	531
	532
6b691a5c	533	void BN_clear(BIGNUM *a)
d02b48c6	534	{
dfeab068	535	if (a->d != NULL)
2d978cbd	536	memset(a->d,0,a->dmax*sizeof(a->d[0]));
d02b48c6 RE	537	a->top=0;
	538	a->neg=0;
	539	}
	540
020fc820	541	BN_ULONG BN_get_word(const BIGNUM *a)
d02b48c6 RE	542	{
d02b48c6 RE	543	int i,n;
dfeab068	544	BN_ULONG ret=0;
d02b48c6 RE	545
d02b48c6 RE	546	n=BN_num_bytes(a);
dfeab068	547	if (n > sizeof(BN_ULONG))
d02b48c6	548	return(BN_MASK2);
d02b48c6 RE	549	for (i=a->top-1; i>=0; i--)
	550	{
	551	#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
	552	ret<<=BN_BITS4; /* stops the compiler complaining */
	553	ret<<=BN_BITS4;
e14d4443 UM	554	#else
e14d4443 UM	555	ret=0;
d02b48c6 RE	556	#endif
	557	ret\|=a->d[i];
	558	}
	559	return(ret);
	560	}
	561
6b691a5c	562	int BN_set_word(BIGNUM *a, BN_ULONG w)
d02b48c6 RE	563	{
d02b48c6 RE	564	int i,n;
dfeab068	565	if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
d02b48c6	566
dfeab068	567	n=sizeof(BN_ULONG)/BN_BYTES;
d02b48c6 RE	568	a->neg=0;
	569	a->top=0;
	570	a->d[0]=(BN_ULONG)w&BN_MASK2;
	571	if (a->d[0] != 0) a->top=1;
	572	for (i=1; i<n; i++)
	573	{
	574	/* the following is done instead of
	575	* w>>=BN_BITS2 so compilers don't complain
	576	* on builds where sizeof(long) == BN_TYPES */
	577	#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
	578	w>>=BN_BITS4;
	579	w>>=BN_BITS4;
e14d4443 UM	580	#else
e14d4443 UM	581	w=0;
d02b48c6 RE	582	#endif
	583	a->d[i]=(BN_ULONG)w&BN_MASK2;
	584	if (a->d[i] != 0) a->top=i+1;
	585	}
	586	return(1);
	587	}
	588
61f5b6f3	589	BIGNUM BN_bin2bn(const unsigned char s, int len, BIGNUM *ret)
d02b48c6 RE	590	{
	591	unsigned int i,m;
	592	unsigned int n;
	593	BN_ULONG l;
	594
	595	if (ret == NULL) ret=BN_new();
	596	if (ret == NULL) return(NULL);
	597	l=0;
	598	n=len;
	599	if (n == 0)
	600	{
	601	ret->top=0;
	602	return(ret);
	603	}
	604	if (bn_expand(ret,(int)(n+2)*8) == NULL)
	605	return(NULL);
	606	i=((n-1)/BN_BYTES)+1;
	607	m=((n-1)%(BN_BYTES));
91616729 BM	608	ret->top=i;
91616729 BM	609	ret->neg=0;
d02b48c6 RE	610	while (n-- > 0)
	611	{
	612	l=(l<<8L)\| *(s++);
	613	if (m-- == 0)
	614	{
	615	ret->d[--i]=l;
	616	l=0;
	617	m=BN_BYTES-1;
	618	}
	619	}
	620	/* need to call this due to clear byte at top if avoiding
	621	* having the top bit set (-ve number) */
	622	bn_fix_top(ret);
	623	return(ret);
	624	}
	625
	626	/* ignore negative */
8623f693	627	int BN_bn2bin(const BIGNUM a, unsigned char to)
d02b48c6 RE	628	{
	629	int n,i;
	630	BN_ULONG l;
	631
	632	n=i=BN_num_bytes(a);
	633	while (i-- > 0)
	634	{
	635	l=a->d[i/BN_BYTES];
	636	(to++)=(unsigned char)(l>>(8(i%BN_BYTES)))&0xff;
	637	}
	638	return(n);
	639	}
	640
84c15db5	641	int BN_ucmp(const BIGNUM a, const BIGNUM b)
d02b48c6 RE	642	{
	643	int i;
	644	BN_ULONG t1,t2,ap,bp;
	645
dfeab068 RE	646	bn_check_top(a);
	647	bn_check_top(b);
	648
d02b48c6 RE	649	i=a->top-b->top;
	650	if (i != 0) return(i);
	651	ap=a->d;
	652	bp=b->d;
	653	for (i=a->top-1; i>=0; i--)
	654	{
	655	t1= ap[i];
	656	t2= bp[i];
	657	if (t1 != t2)
	658	return(t1 > t2?1:-1);
	659	}
	660	return(0);
	661	}
	662
84c15db5	663	int BN_cmp(const BIGNUM a, const BIGNUM b)
d02b48c6 RE	664	{
	665	int i;
	666	int gt,lt;
	667	BN_ULONG t1,t2;
	668
	669	if ((a == NULL) \|\| (b == NULL))
	670	{
	671	if (a != NULL)
	672	return(-1);
	673	else if (b != NULL)
	674	return(1);
	675	else
	676	return(0);
	677	}
dfeab068 RE	678
	679	bn_check_top(a);
	680	bn_check_top(b);
	681
d02b48c6 RE	682	if (a->neg != b->neg)
	683	{
	684	if (a->neg)
	685	return(-1);
	686	else return(1);
	687	}
	688	if (a->neg == 0)
	689	{ gt=1; lt= -1; }
	690	else { gt= -1; lt=1; }
	691
	692	if (a->top > b->top) return(gt);
	693	if (a->top < b->top) return(lt);
	694	for (i=a->top-1; i>=0; i--)
	695	{
	696	t1=a->d[i];
	697	t2=b->d[i];
	698	if (t1 > t2) return(gt);
	699	if (t1 < t2) return(lt);
	700	}
	701	return(0);
	702	}
	703
6b691a5c	704	int BN_set_bit(BIGNUM *a, int n)
d02b48c6	705	{
dfeab068	706	int i,j,k;
d02b48c6 RE	707
	708	i=n/BN_BITS2;
	709	j=n%BN_BITS2;
58964a49 RE	710	if (a->top <= i)
58964a49 RE	711	{
dfeab068 RE	712	if (bn_wexpand(a,i+1) == NULL) return(0);
	713	for(k=a->top; k<i+1; k++)
	714	a->d[k]=0;
58964a49 RE	715	a->top=i+1;
58964a49 RE	716	}
d02b48c6	717
e14d4443	718	a->d[i]\|=(((BN_ULONG)1)<<j);
d02b48c6 RE	719	return(1);
	720	}
	721
6b691a5c	722	int BN_clear_bit(BIGNUM *a, int n)
d02b48c6 RE	723	{
	724	int i,j;
	725
	726	i=n/BN_BITS2;
	727	j=n%BN_BITS2;
	728	if (a->top <= i) return(0);
	729
e14d4443	730	a->d[i]&=(~(((BN_ULONG)1)<<j));
dfeab068	731	bn_fix_top(a);
d02b48c6 RE	732	return(1);
	733	}
	734
84c15db5	735	int BN_is_bit_set(const BIGNUM *a, int n)
d02b48c6 RE	736	{
	737	int i,j;
	738
	739	if (n < 0) return(0);
	740	i=n/BN_BITS2;
	741	j=n%BN_BITS2;
	742	if (a->top <= i) return(0);
	743	return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
	744	}
	745
6b691a5c	746	int BN_mask_bits(BIGNUM *a, int n)
d02b48c6 RE	747	{
	748	int b,w;
	749
	750	w=n/BN_BITS2;
	751	b=n%BN_BITS2;
	752	if (w >= a->top) return(0);
	753	if (b == 0)
	754	a->top=w;
	755	else
	756	{
	757	a->top=w+1;
	758	a->d[w]&= ~(BN_MASK2<<b);
d02b48c6	759	}
dfeab068	760	bn_fix_top(a);
d02b48c6 RE	761	return(1);
d02b48c6 RE	762	}
dfeab068	763
cbd48ba6	764	int bn_cmp_words(const BN_ULONG a, const BN_ULONG b, int n)
dfeab068 RE	765	{
	766	int i;
	767	BN_ULONG aa,bb;
	768
	769	aa=a[n-1];
	770	bb=b[n-1];
	771	if (aa != bb) return((aa > bb)?1:-1);
	772	for (i=n-2; i>=0; i--)
	773	{
	774	aa=a[i];
	775	bb=b[i];
	776	if (aa != bb) return((aa > bb)?1:-1);
	777	}
	778	return(0);
	779	}