1 /* crypto/bn/bn_lib.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
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.
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).
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.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
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)"
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
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.]
60 # undef NDEBUG /* avoid conflicting definitions */
70 const char *BN_version
="Big Number";
72 /* For a 32 bit machine
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) */
90 int BN_num_bits_word(BN_ULONG l
)
92 static const char bits
[256]={
93 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
94 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
95 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
96 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
97 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
98 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
99 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
100 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
101 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
102 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
103 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
107 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
108 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
111 #if defined(SIXTY_FOUR_BIT_LONG)
112 if (l
& 0xffffffff00000000L
)
114 if (l
& 0xffff000000000000L
)
116 if (l
& 0xff00000000000000L
)
118 return(bits
[(int)(l
>>56)]+56);
120 else return(bits
[(int)(l
>>48)]+48);
124 if (l
& 0x0000ff0000000000L
)
126 return(bits
[(int)(l
>>40)]+40);
128 else return(bits
[(int)(l
>>32)]+32);
133 #ifdef SIXTY_FOUR_BIT
134 if (l
& 0xffffffff00000000LL
)
136 if (l
& 0xffff000000000000LL
)
138 if (l
& 0xff00000000000000LL
)
140 return(bits
[(int)(l
>>56)]+56);
142 else return(bits
[(int)(l
>>48)]+48);
146 if (l
& 0x0000ff0000000000LL
)
148 return(bits
[(int)(l
>>40)]+40);
150 else return(bits
[(int)(l
>>32)]+32);
157 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
161 return(bits
[(int)(l
>>24L)]+24);
162 else return(bits
[(int)(l
>>16L)]+16);
167 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
169 return(bits
[(int)(l
>>8)]+8);
172 return(bits
[(int)(l
)] );
177 int BN_num_bits(const BIGNUM
*a
)
184 if (a
->top
== 0) return(0);
187 i
=(a
->top
-1)*BN_BITS2
;
188 return(i
+BN_num_bits_word(l
));
191 void BN_clear_free(BIGNUM
*a
)
195 if (a
== NULL
) return;
198 memset(a
->d
,0,a
->dmax
*sizeof(a
->d
[0]));
199 if (!(BN_get_flags(a
,BN_FLG_STATIC_DATA
)))
202 i
=BN_get_flags(a
,BN_FLG_MALLOCED
);
203 memset(a
,0,sizeof(BIGNUM
));
208 void BN_free(BIGNUM
*a
)
210 if (a
== NULL
) return;
211 if ((a
->d
!= NULL
) && !(BN_get_flags(a
,BN_FLG_STATIC_DATA
)))
213 a
->flags
|=BN_FLG_FREE
; /* REMOVE? */
214 if (a
->flags
& BN_FLG_MALLOCED
)
218 void BN_init(BIGNUM
*a
)
220 memset(a
,0,sizeof(BIGNUM
));
227 if ((ret
=(BIGNUM
*)malloc(sizeof(BIGNUM
))) == NULL
)
231 ret
->flags
=BN_FLG_MALLOCED
;
239 /* This is an internal function that should not be used in applications.
240 * It ensures that 'b' has enough room for a 'words' word number number.
241 * It is mostly used by the various BIGNUM routines. If there is an error,
242 * NULL is returned. If not, 'b' is returned. */
244 BIGNUM
*bn_expand2(BIGNUM
*b
, int words
)
255 if (BN_get_flags(b
,BN_FLG_STATIC_DATA
))
259 a
=A
=(BN_ULONG
*)malloc(sizeof(BN_ULONG
)*(words
+1));
266 /* Check if the previous number needs to be copied */
270 /* This lot is an unrolled loop to copy b->top
271 * BN_ULONGs from B to A
274 * I have nothing against unrolling but it's usually done for
275 * several reasons, namely:
276 * - minimize percentage of decision making code, i.e. branches;
277 * - avoid cache trashing;
278 * - make it possible to schedule loads earlier;
279 * Now let's examine the code below. The cornerstone of C is
280 * "programmer is always right" and that's what we love it for:-)
281 * For this very reason C compilers have to be paranoid when it
282 * comes to data aliasing and assume the worst. Yeah, but what
283 * does it mean in real life? This means that loop body below will
284 * be compiled to sequence of loads immediately followed by stores
285 * as compiler assumes the worst, something in A==B+1 style. As a
286 * result CPU pipeline is going to starve for incoming data. Secondly
287 * if A and B happen to share same cache line such code is going to
288 * cause severe cache trashing. Both factors have severe impact on
289 * performance of modern CPUs and this is the reason why this
290 * particular piece of code is #ifdefed away and replaced by more
291 * "friendly" version found in #else section below. This comment
292 * also applies to BN_copy function.
294 * <appro@fy.chalmers.se>
296 for (i
=b
->top
&(~7); i
>0; i
-=8)
298 A
[0]=B
[0]; A
[1]=B
[1]; A
[2]=B
[2]; A
[3]=B
[3];
299 A
[4]=B
[4]; A
[5]=B
[5]; A
[6]=B
[6]; A
[7]=B
[7];
320 /* I need the 'case 0' entry for utrix cc.
321 * If the optimizer is turned on, it does the
322 * switch table by doing
325 * goto jump_table[a];
326 * If top is 0, this makes us jump to 0xffffffc
327 * which is rather bad :-(.
333 for (i
=b
->top
>>2; i
>0; i
--,A
+=4,B
+=4)
336 * The fact that the loop is unrolled
337 * 4-wise is a tribute to Intel. It's
338 * the one that doesn't have enough
339 * registers to accomodate more data.
340 * I'd unroll it 8-wise otherwise:-)
342 * <appro@fy.chalmers.se>
344 BN_ULONG a0
,a1
,a2
,a3
;
345 a0
=B
[0]; a1
=B
[1]; a2
=B
[2]; a3
=B
[3];
346 A
[0]=a0
; A
[1]=a1
; A
[2]=a2
; A
[3]=a3
;
353 case 0: ; /* ultrix cc workaround, see above */
362 /* Now need to zero any data between b->top and b->max */
365 for (i
=(b
->dmax
- b
->top
)>>3; i
>0; i
--,A
+=8)
367 A
[0]=0; A
[1]=0; A
[2]=0; A
[3]=0;
368 A
[4]=0; A
[5]=0; A
[6]=0; A
[7]=0;
370 for (i
=(b
->dmax
- b
->top
)&7; i
>0; i
--,A
++)
373 memset(A
,0,sizeof(BN_ULONG
)*(words
+1));
374 memcpy(A
,b
->d
,sizeof(b
->d
[0])*b
->top
);
379 /* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
380 /* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
386 BIGNUM
*BN_copy(BIGNUM
*a
, const BIGNUM
*b
)
394 if (a
== b
) return(a
);
395 if (bn_wexpand(a
,b
->top
) == NULL
) return(NULL
);
400 for (i
=b
->top
>>2; i
>0; i
--,A
+=4,B
+=4)
402 BN_ULONG a0
,a1
,a2
,a3
;
403 a0
=B
[0]; a1
=B
[1]; a2
=B
[2]; a3
=B
[3];
404 A
[0]=a0
; A
[1]=a1
; A
[2]=a2
; A
[3]=a3
;
411 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
414 memcpy(a
->d
,b
->d
,sizeof(b
->d
[0])*b
->top
);
417 /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
419 if ((a
->top
== 0) && (a
->d
!= NULL
))
425 int BN_set_word(BIGNUM
*a
, BN_ULONG w
)
428 if (bn_expand(a
,sizeof(BN_ULONG
)*8) == NULL
) return(0);
430 n
=sizeof(BN_ULONG
)/BN_BYTES
;
433 a
->d
[0]=(BN_ULONG
)w
&BN_MASK2
;
434 if (a
->d
[0] != 0) a
->top
=1;
437 /* the following is done instead of
438 * w>>=BN_BITS2 so compilers don't complain
439 * on builds where sizeof(long) == BN_TYPES */
440 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
446 a
->d
[i
]=(BN_ULONG
)w
&BN_MASK2
;
447 if (a
->d
[i
] != 0) a
->top
=i
+1;
452 /* ignore negative */
453 BIGNUM
*BN_bin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
459 if (ret
== NULL
) ret
=BN_new();
460 if (ret
== NULL
) return(NULL
);
468 if (bn_expand(ret
,(int)(n
+2)*8) == NULL
)
470 i
=((n
-1)/BN_BYTES
)+1;
471 m
=((n
-1)%(BN_BYTES
));
483 /* need to call this due to clear byte at top if avoiding
484 * having the top bit set (-ve number) */
489 /* ignore negative */
490 int BN_bn2bin(const BIGNUM
*a
, unsigned char *to
)
499 *(to
++)=(unsigned char)(l
>>(8*(i
%BN_BYTES
)))&0xff;
504 int BN_ucmp(const BIGNUM
*a
, const BIGNUM
*b
)
507 BN_ULONG t1
,t2
,*ap
,*bp
;
513 if (i
!= 0) return(i
);
516 for (i
=a
->top
-1; i
>=0; i
--)
521 return(t1
> t2
?1:-1);
526 int BN_cmp(const BIGNUM
*a
, const BIGNUM
*b
)
532 if ((a
== NULL
) || (b
== NULL
))
545 if (a
->neg
!= b
->neg
)
553 else { gt
= -1; lt
=1; }
555 if (a
->top
> b
->top
) return(gt
);
556 if (a
->top
< b
->top
) return(lt
);
557 for (i
=a
->top
-1; i
>=0; i
--)
561 if (t1
> t2
) return(gt
);
562 if (t1
< t2
) return(lt
);
567 int BN_is_bit_set(const BIGNUM
*a
, int n
)
571 if (n
< 0) return(0);
574 if (a
->top
<= i
) return(0);
575 return((a
->d
[i
]&(((BN_ULONG
)1)<<j
))?1:0);
This page took 0.064856 seconds and 5 git commands to generate.