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