Tidy up, including;
[openssl.git] / crypto / bn / bn_lib.c
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 "cryptlib.h"
68 #include "bn_lcl.h"
69
70 const 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  */
83 static int bn_limit_bits=0;
84 static int bn_limit_num=8;        /* (1<<bn_limit_bits) */
85 static int bn_limit_bits_low=0;
86 static int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
87 static int bn_limit_bits_high=0;
88 static int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
89 static int bn_limit_bits_mont=0;
90 static int bn_limit_num_mont=8;   /* (1<<bn_limit_bits_mont) */
91
92 void 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
124 int 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
134 const BIGNUM *BN_value_one(void)
135         {
136         static BN_ULONG data_one=1L;
137         static BIGNUM const_one={&data_one,1,1,0,BN_FLG_STATIC_DATA};
138
139         return(&const_one);
140         }
141
142 char *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
161 int BN_num_bits_word(BN_ULONG l)
162         {
163         static const 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(SIXTEEN_BIT) || 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
248 int 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
257 void 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
275 void 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
292 void BN_init(BIGNUM *a)
293         {
294         memset(a,0,sizeof(BIGNUM));
295         bn_check_top(a);
296         }
297
298 BIGNUM *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 */
318 static 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
394 BIGNUM *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
445 BIGNUM *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
479 BIGNUM *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
497 BIGNUM *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
534 BIGNUM *BN_ncopy(BIGNUM *a, const BIGNUM *b, size_t n)
535         {
536         int i, min;
537         BN_ULONG *A;
538         const BN_ULONG *B;
539
540         bn_check_top(b);
541         if (a == b)
542                 return a;
543
544         min = (b->top < (int)n)? b->top: (int)n;
545         if (!min)
546                 {
547                 BN_zero(a);
548                 return a;
549                 }
550         if (bn_wexpand(a, min) == NULL)
551                 return NULL;
552
553         A=a->d;
554         B=b->d;
555         for (i=min>>2; i>0; i--, A+=4, B+=4)
556                 {
557                 BN_ULONG a0,a1,a2,a3;
558                 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
559                 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
560                 }
561         switch (min&3)
562                 {
563                 case 3: A[2]=B[2];
564                 case 2: A[1]=B[1];
565                 case 1: A[0]=B[0];
566                 case 0: ;
567                 }
568         a->top = min;
569         a->neg = b->neg;
570         bn_correct_top(a);
571         return(a);
572         }
573
574 void BN_swap(BIGNUM *a, BIGNUM *b)
575         {
576         int flags_old_a, flags_old_b;
577         BN_ULONG *tmp_d;
578         int tmp_top, tmp_dmax, tmp_neg;
579         
580         bn_check_top(a);
581         bn_check_top(b);
582
583         flags_old_a = a->flags;
584         flags_old_b = b->flags;
585
586         tmp_d = a->d;
587         tmp_top = a->top;
588         tmp_dmax = a->dmax;
589         tmp_neg = a->neg;
590         
591         a->d = b->d;
592         a->top = b->top;
593         a->dmax = b->dmax;
594         a->neg = b->neg;
595         
596         b->d = tmp_d;
597         b->top = tmp_top;
598         b->dmax = tmp_dmax;
599         b->neg = tmp_neg;
600         
601         a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
602         b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
603         bn_check_top(a);
604         bn_check_top(b);
605         }
606
607 void BN_clear(BIGNUM *a)
608         {
609         bn_check_top(a);
610         if (a->d != NULL)
611                 memset(a->d,0,a->dmax*sizeof(a->d[0]));
612         a->top=0;
613         a->neg=0;
614         }
615
616 BN_ULONG BN_get_word(const BIGNUM *a)
617         {
618         if (a->top > 1)
619                 return BN_MASK2;
620         else if (a->top == 1)
621                 return a->d[0];
622         /* a->top == 0 */
623         return 0;
624         }
625
626 int BN_set_word(BIGNUM *a, BN_ULONG w)
627         {
628         bn_check_top(a);
629         if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0);
630         a->neg = 0;
631         a->d[0] = w;
632         a->top = (w ? 1 : 0);
633         bn_check_top(a);
634         return(1);
635         }
636
637 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
638         {
639         unsigned int i,m;
640         unsigned int n;
641         BN_ULONG l;
642         BIGNUM  *bn = NULL;
643
644         if (ret == NULL)
645                 ret = bn = BN_new();
646         if (ret == NULL) return(NULL);
647         bn_check_top(ret);
648         l=0;
649         n=len;
650         if (n == 0)
651                 {
652                 ret->top=0;
653                 return(ret);
654                 }
655         i=((n-1)/BN_BYTES)+1;
656         m=((n-1)%(BN_BYTES));
657         if (bn_wexpand(ret, (int)i) == NULL)
658                 {
659                 if (bn) BN_free(bn);
660                 return NULL;
661                 }
662         ret->top=i;
663         ret->neg=0;
664         while (n--)
665                 {
666                 l=(l<<8L)| *(s++);
667                 if (m-- == 0)
668                         {
669                         ret->d[--i]=l;
670                         l=0;
671                         m=BN_BYTES-1;
672                         }
673                 }
674         /* need to call this due to clear byte at top if avoiding
675          * having the top bit set (-ve number) */
676         bn_correct_top(ret);
677         return(ret);
678         }
679
680 /* ignore negative */
681 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
682         {
683         int n,i;
684         BN_ULONG l;
685
686         bn_check_top(a);
687         n=i=BN_num_bytes(a);
688         while (i--)
689                 {
690                 l=a->d[i/BN_BYTES];
691                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
692                 }
693         return(n);
694         }
695
696 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
697         {
698         int i;
699         BN_ULONG t1,t2,*ap,*bp;
700
701         bn_check_top(a);
702         bn_check_top(b);
703
704         i=a->top-b->top;
705         if (i != 0) return(i);
706         ap=a->d;
707         bp=b->d;
708         for (i=a->top-1; i>=0; i--)
709                 {
710                 t1= ap[i];
711                 t2= bp[i];
712                 if (t1 != t2)
713                         return((t1 > t2) ? 1 : -1);
714                 }
715         return(0);
716         }
717
718 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
719         {
720         int i;
721         int gt,lt;
722         BN_ULONG t1,t2;
723
724         if ((a == NULL) || (b == NULL))
725                 {
726                 if (a != NULL)
727                         return(-1);
728                 else if (b != NULL)
729                         return(1);
730                 else
731                         return(0);
732                 }
733
734         bn_check_top(a);
735         bn_check_top(b);
736
737         if (a->neg != b->neg)
738                 {
739                 if (a->neg)
740                         return(-1);
741                 else    return(1);
742                 }
743         if (a->neg == 0)
744                 { gt=1; lt= -1; }
745         else    { gt= -1; lt=1; }
746
747         if (a->top > b->top) return(gt);
748         if (a->top < b->top) return(lt);
749         for (i=a->top-1; i>=0; i--)
750                 {
751                 t1=a->d[i];
752                 t2=b->d[i];
753                 if (t1 > t2) return(gt);
754                 if (t1 < t2) return(lt);
755                 }
756         return(0);
757         }
758
759 int BN_set_bit(BIGNUM *a, int n)
760         {
761         int i,j,k;
762
763         if (n < 0)
764                 return 0;
765
766         i=n/BN_BITS2;
767         j=n%BN_BITS2;
768         if (a->top <= i)
769                 {
770                 if (bn_wexpand(a,i+1) == NULL) return(0);
771                 for(k=a->top; k<i+1; k++)
772                         a->d[k]=0;
773                 a->top=i+1;
774                 }
775
776         a->d[i]|=(((BN_ULONG)1)<<j);
777         bn_check_top(a);
778         return(1);
779         }
780
781 int BN_clear_bit(BIGNUM *a, int n)
782         {
783         int i,j;
784
785         bn_check_top(a);
786         if (n < 0) return 0;
787
788         i=n/BN_BITS2;
789         j=n%BN_BITS2;
790         if (a->top <= i) return(0);
791
792         a->d[i]&=(~(((BN_ULONG)1)<<j));
793         bn_correct_top(a);
794         return(1);
795         }
796
797 int BN_is_bit_set(const BIGNUM *a, int n)
798         {
799         int i,j;
800
801         bn_check_top(a);
802         if (n < 0) return 0;
803         i=n/BN_BITS2;
804         j=n%BN_BITS2;
805         if (a->top <= i) return 0;
806         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
807         }
808
809 int BN_mask_bits(BIGNUM *a, int n)
810         {
811         int b,w;
812
813         bn_check_top(a);
814         if (n < 0) return 0;
815
816         w=n/BN_BITS2;
817         b=n%BN_BITS2;
818         if (w >= a->top) return 0;
819         if (b == 0)
820                 a->top=w;
821         else
822                 {
823                 a->top=w+1;
824                 a->d[w]&= ~(BN_MASK2<<b);
825                 }
826         bn_correct_top(a);
827         return(1);
828         }
829
830 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
831         {
832         int i;
833         BN_ULONG aa,bb;
834
835         aa=a[n-1];
836         bb=b[n-1];
837         if (aa != bb) return((aa > bb)?1:-1);
838         for (i=n-2; i>=0; i--)
839                 {
840                 aa=a[i];
841                 bb=b[i];
842                 if (aa != bb) return((aa > bb)?1:-1);
843                 }
844         return(0);
845         }
846
847 /* Here follows a specialised variants of bn_cmp_words().  It has the
848    property of performing the operation on arrays of different sizes.
849    The sizes of those arrays is expressed through cl, which is the
850    common length ( basicall, min(len(a),len(b)) ), and dl, which is the
851    delta between the two lengths, calculated as len(a)-len(b).
852    All lengths are the number of BN_ULONGs...  */
853
854 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
855         int cl, int dl)
856         {
857         int n,i;
858         n = cl-1;
859
860         if (dl < 0)
861                 {
862                 for (i=dl; i<0; i++)
863                         {
864                         if (b[n-i] != 0)
865                                 return -1; /* a < b */
866                         }
867                 }
868         if (dl > 0)
869                 {
870                 for (i=dl; i>0; i--)
871                         {
872                         if (a[n+i] != 0)
873                                 return 1; /* a > b */
874                         }
875                 }
876         return bn_cmp_words(a,b,cl);
877         }