OpenWrt – Blame information for rev 4

Subversion Repositories:
Rev:
Rev Author Line No. Line
4 office 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 <stdio.h>
66 #include <stdlib.h>
67 #include <string.h>
68 #include "bn_lcl.h"
69  
70 const char *BN_version="Big Number";
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 int BN_num_bits_word(BN_ULONG l)
91 {
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,
109 };
110  
111 #if defined(SIXTY_FOUR_BIT_LONG)
112 if (l & 0xffffffff00000000L)
113 {
114 if (l & 0xffff000000000000L)
115 {
116 if (l & 0xff00000000000000L)
117 {
118 return(bits[(int)(l>>56)]+56);
119 }
120 else return(bits[(int)(l>>48)]+48);
121 }
122 else
123 {
124 if (l & 0x0000ff0000000000L)
125 {
126 return(bits[(int)(l>>40)]+40);
127 }
128 else return(bits[(int)(l>>32)]+32);
129 }
130 }
131 else
132 #else
133 #ifdef SIXTY_FOUR_BIT
134 if (l & 0xffffffff00000000LL)
135 {
136 if (l & 0xffff000000000000LL)
137 {
138 if (l & 0xff00000000000000LL)
139 {
140 return(bits[(int)(l>>56)]+56);
141 }
142 else return(bits[(int)(l>>48)]+48);
143 }
144 else
145 {
146 if (l & 0x0000ff0000000000LL)
147 {
148 return(bits[(int)(l>>40)]+40);
149 }
150 else return(bits[(int)(l>>32)]+32);
151 }
152 }
153 else
154 #endif
155 #endif
156 {
157 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
158 if (l & 0xffff0000L)
159 {
160 if (l & 0xff000000L)
161 return(bits[(int)(l>>24L)]+24);
162 else return(bits[(int)(l>>16L)]+16);
163 }
164 else
165 #endif
166 {
167 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
168 if (l & 0xff00L)
169 return(bits[(int)(l>>8)]+8);
170 else
171 #endif
172 return(bits[(int)(l )] );
173 }
174 }
175 }
176  
177 int BN_num_bits(const BIGNUM *a)
178 {
179 BN_ULONG l;
180 int i;
181  
182 bn_check_top(a);
183  
184 if (a->top == 0) return(0);
185 l=a->d[a->top-1];
186 assert(l != 0);
187 i=(a->top-1)*BN_BITS2;
188 return(i+BN_num_bits_word(l));
189 }
190  
191 void BN_clear_free(BIGNUM *a)
192 {
193 int i;
194  
195 if (a == NULL) return;
196 if (a->d != NULL)
197 {
198 memset(a->d,0,a->dmax*sizeof(a->d[0]));
199 if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
200 free(a->d);
201 }
202 i=BN_get_flags(a,BN_FLG_MALLOCED);
203 memset(a,0,sizeof(BIGNUM));
204 if (i)
205 free(a);
206 }
207  
208 void BN_free(BIGNUM *a)
209 {
210 if (a == NULL) return;
211 if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
212 free(a->d);
213 a->flags|=BN_FLG_FREE; /* REMOVE? */
214 if (a->flags & BN_FLG_MALLOCED)
215 free(a);
216 }
217  
218 void BN_init(BIGNUM *a)
219 {
220 memset(a,0,sizeof(BIGNUM));
221 }
222  
223 BIGNUM *BN_new(void)
224 {
225 BIGNUM *ret;
226  
227 if ((ret=(BIGNUM *)malloc(sizeof(BIGNUM))) == NULL)
228 {
229 return(NULL);
230 }
231 ret->flags=BN_FLG_MALLOCED;
232 ret->top=0;
233 ret->neg=0;
234 ret->dmax=0;
235 ret->d=NULL;
236 return(ret);
237 }
238  
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. */
243  
244 BIGNUM *bn_expand2(BIGNUM *b, int words)
245 {
246 BN_ULONG *A,*a;
247 const BN_ULONG *B;
248 int i;
249  
250 bn_check_top(b);
251  
252 if (words > b->dmax)
253 {
254 bn_check_top(b);
255 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
256 {
257 return(NULL);
258 }
259 a=A=(BN_ULONG *)malloc(sizeof(BN_ULONG)*(words+1));
260 if (A == NULL)
261 {
262 return(NULL);
263 }
264 #if 1
265 B=b->d;
266 /* Check if the previous number needs to be copied */
267 if (B != NULL)
268 {
269 #if 0
270 /* This lot is an unrolled loop to copy b->top
271 * BN_ULONGs from B to A
272 */
273 /*
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.
293 *
294 * <appro@fy.chalmers.se>
295 */
296 for (i=b->top&(~7); i>0; i-=8)
297 {
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];
300 A+=8;
301 B+=8;
302 }
303 switch (b->top&7)
304 {
305 case 7:
306 A[6]=B[6];
307 case 6:
308 A[5]=B[5];
309 case 5:
310 A[4]=B[4];
311 case 4:
312 A[3]=B[3];
313 case 3:
314 A[2]=B[2];
315 case 2:
316 A[1]=B[1];
317 case 1:
318 A[0]=B[0];
319 case 0:
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
323 * a=top&7
324 * a--;
325 * goto jump_table[a];
326 * If top is 0, this makes us jump to 0xffffffc
327 * which is rather bad :-(.
328 * eric 23-Apr-1998
329 */
330 ;
331 }
332 #else
333 for (i=b->top>>2; i>0; i--,A+=4,B+=4)
334 {
335 /*
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:-)
341 *
342 * <appro@fy.chalmers.se>
343 */
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;
347 }
348 switch (b->top&3)
349 {
350 case 3: A[2]=B[2];
351 case 2: A[1]=B[1];
352 case 1: A[0]=B[0];
353 case 0: ; /* ultrix cc workaround, see above */
354 }
355 #endif
356 free(b->d);
357 }
358  
359 b->d=a;
360 b->dmax=words;
361  
362 /* Now need to zero any data between b->top and b->max */
363  
364 A= &(b->d[b->top]);
365 for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
366 {
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;
369 }
370 for (i=(b->dmax - b->top)&7; i>0; i--,A++)
371 A[0]=0;
372 #else
373 memset(A,0,sizeof(BN_ULONG)*(words+1));
374 memcpy(A,b->d,sizeof(b->d[0])*b->top);
375 b->d=a;
376 b->max=words;
377 #endif
378  
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;} */
381  
382 }
383 return(b);
384 }
385  
386 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
387 {
388 int i;
389 BN_ULONG *A;
390 const BN_ULONG *B;
391  
392 bn_check_top(b);
393  
394 if (a == b) return(a);
395 if (bn_wexpand(a,b->top) == NULL) return(NULL);
396  
397 #if 1
398 A=a->d;
399 B=b->d;
400 for (i=b->top>>2; i>0; i--,A+=4,B+=4)
401 {
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;
405 }
406 switch (b->top&3)
407 {
408 case 3: A[2]=B[2];
409 case 2: A[1]=B[1];
410 case 1: A[0]=B[0];
411 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
412 }
413 #else
414 memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
415 #endif
416  
417 /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
418 a->top=b->top;
419 if ((a->top == 0) && (a->d != NULL))
420 a->d[0]=0;
421 a->neg=b->neg;
422 return(a);
423 }
424  
425 int BN_set_word(BIGNUM *a, BN_ULONG w)
426 {
427 int i,n;
428 if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
429  
430 n=sizeof(BN_ULONG)/BN_BYTES;
431 a->neg=0;
432 a->top=0;
433 a->d[0]=(BN_ULONG)w&BN_MASK2;
434 if (a->d[0] != 0) a->top=1;
435 for (i=1; i<n; i++)
436 {
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 */
441 w>>=BN_BITS4;
442 w>>=BN_BITS4;
443 #else
444 w=0;
445 #endif
446 a->d[i]=(BN_ULONG)w&BN_MASK2;
447 if (a->d[i] != 0) a->top=i+1;
448 }
449 return(1);
450 }
451  
452 /* ignore negative */
453 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
454 {
455 unsigned int i,m;
456 unsigned int n;
457 BN_ULONG l;
458  
459 if (ret == NULL) ret=BN_new();
460 if (ret == NULL) return(NULL);
461 l=0;
462 n=len;
463 if (n == 0)
464 {
465 ret->top=0;
466 return(ret);
467 }
468 if (bn_expand(ret,(int)(n+2)*8) == NULL)
469 return(NULL);
470 i=((n-1)/BN_BYTES)+1;
471 m=((n-1)%(BN_BYTES));
472 ret->top=i;
473 while (n-- > 0)
474 {
475 l=(l<<8L)| *(s++);
476 if (m-- == 0)
477 {
478 ret->d[--i]=l;
479 l=0;
480 m=BN_BYTES-1;
481 }
482 }
483 /* need to call this due to clear byte at top if avoiding
484 * having the top bit set (-ve number) */
485 bn_fix_top(ret);
486 return(ret);
487 }
488  
489 /* ignore negative */
490 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
491 {
492 int n,i;
493 BN_ULONG l;
494  
495 n=i=BN_num_bytes(a);
496 while (i-- > 0)
497 {
498 l=a->d[i/BN_BYTES];
499 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
500 }
501 return(n);
502 }
503  
504 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
505 {
506 int i;
507 BN_ULONG t1,t2,*ap,*bp;
508  
509 bn_check_top(a);
510 bn_check_top(b);
511  
512 i=a->top-b->top;
513 if (i != 0) return(i);
514 ap=a->d;
515 bp=b->d;
516 for (i=a->top-1; i>=0; i--)
517 {
518 t1= ap[i];
519 t2= bp[i];
520 if (t1 != t2)
521 return(t1 > t2?1:-1);
522 }
523 return(0);
524 }
525  
526 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
527 {
528 int i;
529 int gt,lt;
530 BN_ULONG t1,t2;
531  
532 if ((a == NULL) || (b == NULL))
533 {
534 if (a != NULL)
535 return(-1);
536 else if (b != NULL)
537 return(1);
538 else
539 return(0);
540 }
541  
542 bn_check_top(a);
543 bn_check_top(b);
544  
545 if (a->neg != b->neg)
546 {
547 if (a->neg)
548 return(-1);
549 else return(1);
550 }
551 if (a->neg == 0)
552 { gt=1; lt= -1; }
553 else { gt= -1; lt=1; }
554  
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--)
558 {
559 t1=a->d[i];
560 t2=b->d[i];
561 if (t1 > t2) return(gt);
562 if (t1 < t2) return(lt);
563 }
564 return(0);
565 }
566  
567 int BN_is_bit_set(const BIGNUM *a, int n)
568 {
569 int i,j;
570  
571 if (n < 0) return(0);
572 i=n/BN_BITS2;
573 j=n%BN_BITS2;
574 if (a->top <= i) return(0);
575 return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
576 }