← Back to branch summary

~andersk/ubuntu/oneiric/openssl/spurious-reboot

« back to all changes in this revision

Viewing changes to crypto/bn/bn_lib.c

  • Committer: Bazaar Package Importer
  • Author(s): Christoph Martin
  • Date: 2004-05-24 17:02:29 UTC
  • Revision ID: james.westby@ubuntu.com-20040524170229-ixlo08bbbly0xied
Tags: upstream-0.9.7d
Import upstream version 0.9.7d

Show diffs side-by-side

added added

removed removed

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