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

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

/* I've done some timing with different table sizes.
 * The main hassle is that even with bits set at 3, this requires
 * 63 BIGNUMs to store the pre-calculated values.
 *          512   1024 
 * bits=1  75.4%  79.4%
 * bits=2  61.2%  62.4%
 * bits=3  61.3%  59.3%
 * The lack of speed improvement is also a function of the pre-calculation
 * which could be removed.
 */
#define EXP2_TABLE_BITS	2 /* 1  2  3  4  5  */
#define EXP2_TABLE_SIZE	4 /* 2  4  8 16 32  */

int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2,
	     BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
	{
	int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
	int start=1,ts=0,x,y;
	BIGNUM *d,*aa1,*aa2,*r;
	BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
	BN_MONT_CTX *mont=NULL;

	bn_check_top(a1);
	bn_check_top(p1);
	bn_check_top(a2);
	bn_check_top(p2);
	bn_check_top(m);

	if (!(m->d[0] & 1))
		{
		BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
		return(0);
		}
	bits1=BN_num_bits(p1);
	bits2=BN_num_bits(p2);
	if ((bits1 == 0) && (bits2 == 0))
		{
		BN_one(rr);
		return(1);
		}

	BN_CTX_start(ctx);
	d = BN_CTX_get(ctx);
	r = BN_CTX_get(ctx);
	if (d == NULL || r == NULL) goto err;

	bits=(bits1 > bits2)?bits1:bits2;

	/* If this is not done, things will break in the montgomery
	 * part */

	if (in_mont != NULL)
		mont=in_mont;
	else
		{
		if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
		if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
		}

	BN_init(&(val[0][0]));
	BN_init(&(val[1][1]));
	BN_init(&(val[0][1]));
	BN_init(&(val[1][0]));
	ts=1;
	if (BN_ucmp(a1,m) >= 0)
		{
		BN_mod(&(val[1][0]),a1,m,ctx);
		aa1= &(val[1][0]);
		}
	else
		aa1=a1;
	if (BN_ucmp(a2,m) >= 0)
		{
		BN_mod(&(val[0][1]),a2,m,ctx);
		aa2= &(val[0][1]);
		}
	else
		aa2=a2;
	if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
	if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
	if (!BN_mod_mul_montgomery(&(val[1][1]),
		&(val[1][0]),&(val[0][1]),mont,ctx))
		goto err;

#if 0
	if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
		window=1;
	else if (bits > 250)
		window=5;	/* max size of window */
	else if (bits >= 120)
		window=4;
	else
		window=3;
#else
	window=EXP2_TABLE_BITS;
#endif

	k=1<<window;
	for (x=0; x<k; x++)
		{
		if (x >= 2)
			{
			BN_init(&(val[x][0]));
			BN_init(&(val[x][1]));
			if (!BN_mod_mul_montgomery(&(val[x][0]),
				&(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
			if (!BN_mod_mul_montgomery(&(val[x][1]),
				&(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
			}
		for (y=2; y<k; y++)
			{
			BN_init(&(val[x][y]));
			if (!BN_mod_mul_montgomery(&(val[x][y]),
				&(val[x][y-1]),&(val[0][1]),mont,ctx))
				goto err;
			}
		}
	ts=k;

	start=1;	/* This is used to avoid multiplication etc
			 * when there is only the value '1' in the
			 * buffer. */
	xvalue=0;	/* The 'x value' of the window */
	yvalue=0;	/* The 'y value' of the window */
	wstart=bits-1;	/* The top bit of the window */
	wend=0;		/* The bottom bit of the window */

        if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
	for (;;)
		{
		xvalue=BN_is_bit_set(p1,wstart);
		yvalue=BN_is_bit_set(p2,wstart);
		if (!(xvalue || yvalue))
			{
			if (!start)
				{
				if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
					goto err;
				}
			wstart--;
			if (wstart < 0) break;
			continue;
			}
		/* We now have wstart on a 'set' bit, we now need to work out
		 * how bit a window to do.  To do this we need to scan
		 * forward until the last set bit before the end of the
		 * window */
		j=wstart;
		/* xvalue=BN_is_bit_set(p1,wstart); already set */
		/* yvalue=BN_is_bit_set(p1,wstart); already set */
		wend=0;
		for (i=1; i<window; i++)
			{
			if (wstart-i < 0) break;
			xvalue+=xvalue;
			xvalue|=BN_is_bit_set(p1,wstart-i);
			yvalue+=yvalue;
			yvalue|=BN_is_bit_set(p2,wstart-i);
			}

		/* i is the size of the current window */
		/* add the 'bytes above' */
		if (!start)
			for (j=0; j<i; j++)
				{
				if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
					goto err;
				}
		
		/* wvalue will be an odd number < 2^window */
		if (xvalue || yvalue)
			{
			if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
				mont,ctx)) goto err;
			}

		/* move the 'window' down further */
		wstart-=i;
		start=0;
		if (wstart < 0) break;
		}
	BN_from_montgomery(rr,r,mont,ctx);
	ret=1;
err:
	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
	BN_CTX_end(ctx);
	for (i=0; i<ts; i++)
		{
		for (j=0; j<ts; j++)
			{
			BN_clear_free(&(val[i][j]));
			}
		}
	return(ret);
	}
Commit	Line	Data
dfeab068 RE	1	#include <stdio.h>
	2	#include "cryptlib.h"
	3	#include "bn_lcl.h"
	4
	5	/* I've done some timing with different table sizes.
	6	* The main hassle is that even with bits set at 3, this requires
	7	* 63 BIGNUMs to store the pre-calculated values.
	8	* 512 1024
	9	* bits=1 75.4% 79.4%
	10	* bits=2 61.2% 62.4%
	11	* bits=3 61.3% 59.3%
657e60fa	12	* The lack of speed improvement is also a function of the pre-calculation
dfeab068 RE	13	* which could be removed.
	14	*/
	15	#define EXP2_TABLE_BITS 2 /* 1 2 3 4 5 */
	16	#define EXP2_TABLE_SIZE 4 /* 2 4 8 16 32 */
	17
6b691a5c UM	18	int BN_mod_exp2_mont(BIGNUM rr, BIGNUM a1, BIGNUM p1, BIGNUM a2,
6b691a5c UM	19	BIGNUM p2, BIGNUM m, BN_CTX ctx, BN_MONT_CTX in_mont)
dfeab068 RE	20	{
	21	int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
	22	int start=1,ts=0,x,y;
	23	BIGNUM d,aa1,aa2,r;
	24	BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
	25	BN_MONT_CTX *mont=NULL;
	26
	27	bn_check_top(a1);
	28	bn_check_top(p1);
	29	bn_check_top(a2);
	30	bn_check_top(p2);
	31	bn_check_top(m);
	32
	33	if (!(m->d[0] & 1))
	34	{
	35	BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
	36	return(0);
	37	}
dfeab068 RE	38	bits1=BN_num_bits(p1);
	39	bits2=BN_num_bits(p2);
	40	if ((bits1 == 0) && (bits2 == 0))
	41	{
9b141126	42	BN_one(rr);
dfeab068 RE	43	return(1);
dfeab068 RE	44	}
9b141126 UM	45
	46	BN_CTX_start(ctx);
	47	d = BN_CTX_get(ctx);
	48	r = BN_CTX_get(ctx);
	49	if (d == NULL \|\| r == NULL) goto err;
	50
dfeab068 RE	51	bits=(bits1 > bits2)?bits1:bits2;
	52
	53	/* If this is not done, things will break in the montgomery
	54	* part */
	55
	56	if (in_mont != NULL)
	57	mont=in_mont;
	58	else
	59	{
	60	if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
	61	if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
	62	}
	63
	64	BN_init(&(val[0][0]));
	65	BN_init(&(val[1][1]));
	66	BN_init(&(val[0][1]));
	67	BN_init(&(val[1][0]));
	68	ts=1;
	69	if (BN_ucmp(a1,m) >= 0)
	70	{
	71	BN_mod(&(val[1][0]),a1,m,ctx);
	72	aa1= &(val[1][0]);
	73	}
	74	else
	75	aa1=a1;
	76	if (BN_ucmp(a2,m) >= 0)
	77	{
	78	BN_mod(&(val[0][1]),a2,m,ctx);
	79	aa2= &(val[0][1]);
	80	}
	81	else
	82	aa2=a2;
	83	if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
	84	if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
	85	if (!BN_mod_mul_montgomery(&(val[1][1]),
	86	&(val[1][0]),&(val[0][1]),mont,ctx))
	87	goto err;
	88
	89	#if 0
	90	if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
	91	window=1;
	92	else if (bits > 250)
	93	window=5; /* max size of window */
	94	else if (bits >= 120)
	95	window=4;
	96	else
	97	window=3;
	98	#else
	99	window=EXP2_TABLE_BITS;
	100	#endif
	101
	102	k=1<<window;
	103	for (x=0; x<k; x++)
	104	{
	105	if (x >= 2)
	106	{
	107	BN_init(&(val[x][0]));
	108	BN_init(&(val[x][1]));
	109	if (!BN_mod_mul_montgomery(&(val[x][0]),
	110	&(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
	111	if (!BN_mod_mul_montgomery(&(val[x][1]),
	112	&(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
	113	}
	114	for (y=2; y<k; y++)
115	{
116	BN_init(&(val[x][y]));
117	if (!BN_mod_mul_montgomery(&(val[x][y]),
118	&(val[x][y-1]),&(val[0][1]),mont,ctx))
119	goto err;
120	}
121	}
122	ts=k;
123
124	start=1; /* This is used to avoid multiplication etc
125	* when there is only the value '1' in the
126	* buffer. */
127	xvalue=0; /* The 'x value' of the window */
128	yvalue=0; /* The 'y value' of the window */
129	wstart=bits-1; /* The top bit of the window */
130	wend=0; /* The bottom bit of the window */
131
132	if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
133	for (;;)
134	{
135	xvalue=BN_is_bit_set(p1,wstart);
136	yvalue=BN_is_bit_set(p2,wstart);
137	if (!(xvalue \|\| yvalue))
138	{
139	if (!start)
140	{
141	if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
142	goto err;
143	}
144	wstart--;
145	if (wstart < 0) break;
146	continue;
147	}
148	/* We now have wstart on a 'set' bit, we now need to work out
149	* how bit a window to do. To do this we need to scan
150	* forward until the last set bit before the end of the
151	* window */
152	j=wstart;
153	/* xvalue=BN_is_bit_set(p1,wstart); already set */
154	/* yvalue=BN_is_bit_set(p1,wstart); already set */
155	wend=0;
156	for (i=1; i<window; i++)
157	{
158	if (wstart-i < 0) break;
159	xvalue+=xvalue;
160	xvalue\|=BN_is_bit_set(p1,wstart-i);
161	yvalue+=yvalue;
162	yvalue\|=BN_is_bit_set(p2,wstart-i);
163	}
164
165	/* i is the size of the current window */
166	/* add the 'bytes above' */
167	if (!start)
168	for (j=0; j<i; j++)
169	{
170	if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
171	goto err;
172	}
173
174	/* wvalue will be an odd number < 2^window */
175	if (xvalue \|\| yvalue)
176	{
177	if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
178	mont,ctx)) goto err;
179	}
180
181	/* move the 'window' down further */
182	wstart-=i;
183	start=0;
184	if (wstart < 0) break;
185	}
186	BN_from_montgomery(rr,r,mont,ctx);
187	ret=1;
188	err:
189	if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
9b141126	190	BN_CTX_end(ctx);
dfeab068 RE	191	for (i=0; i<ts; i++)
	192	{
	193	for (j=0; j<ts; j++)
	194	{
	195	BN_clear_free(&(val[i][j]));
	196	}
	197	}
	198	return(ret);
	199	}