summaryrefslogtreecommitdiff
path: root/src/lib/libssl/src/crypto/bn/bn_lib.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libssl/src/crypto/bn/bn_lib.c')
-rw-r--r--src/lib/libssl/src/crypto/bn/bn_lib.c336
1 files changed, 196 insertions, 140 deletions
diff --git a/src/lib/libssl/src/crypto/bn/bn_lib.c b/src/lib/libssl/src/crypto/bn/bn_lib.c
index 7767d65170..a016cb7f53 100644
--- a/src/lib/libssl/src/crypto/bn/bn_lib.c
+++ b/src/lib/libssl/src/crypto/bn/bn_lib.c
@@ -128,7 +128,7 @@ int BN_get_params(int which)
128 else return(0); 128 else return(0);
129 } 129 }
130 130
131BIGNUM *BN_value_one(void) 131const BIGNUM *BN_value_one(void)
132 { 132 {
133 static BN_ULONG data_one=1L; 133 static BN_ULONG data_one=1L;
134 static BIGNUM const_one={&data_one,1,1,0}; 134 static BIGNUM const_one={&data_one,1,1,0};
@@ -305,172 +305,168 @@ BIGNUM *BN_new(void)
305 return(ret); 305 return(ret);
306 } 306 }
307 307
308/* This is an internal function that should not be used in applications. 308/* This is used both by bn_expand2() and bn_dup_expand() */
309 * It ensures that 'b' has enough room for a 'words' word number number. 309/* The caller MUST check that words > b->dmax before calling this */
310 * It is mostly used by the various BIGNUM routines. If there is an error, 310static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
311 * NULL is returned. If not, 'b' is returned. */
312
313BIGNUM *bn_expand2(BIGNUM *b, int words)
314 { 311 {
315 BN_ULONG *A,*a; 312 BN_ULONG *A,*a = NULL;
316 const BN_ULONG *B; 313 const BN_ULONG *B;
317 int i; 314 int i;
318 315
319 bn_check_top(b); 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 }
320 321
321 if (words > b->dmax) 322 bn_check_top(b);
323 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
322 { 324 {
323 if (words > (INT_MAX/(4*BN_BITS2))) 325 BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
324 { 326 return(NULL);
325 BNerr(BN_F_BN_EXPAND2,BN_R_BIGNUM_TOO_LONG); 327 }
326 return NULL; 328 a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1));
327 } 329 if (A == NULL)
328 330 {
329 bn_check_top(b); 331 BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
330 if (BN_get_flags(b,BN_FLG_STATIC_DATA)) 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)
331 { 340 {
332 BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 341 /*
333 return(NULL); 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;
334 } 353 }
335 a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); 354 switch (b->top&3)
336 if (A == NULL)
337 { 355 {
338 BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); 356 case 3: A[2]=B[2];
339 return(NULL); 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 ;
340 } 363 }
341#if 1 364 }
342 B=b->d; 365
343 /* Check if the previous number needs to be copied */ 366 /* Now need to zero any data between b->top and b->max */
344 if (B != NULL) 367 /* XXX Why? */
345 { 368
346#if 0 369 A= &(a[b->top]);
347 /* This lot is an unrolled loop to copy b->top 370 for (i=(words - b->top)>>3; i>0; i--,A+=8)
348 * BN_ULONGs from B to A 371 {
349 */ 372 A[0]=0; A[1]=0; A[2]=0; A[3]=0;
350/* 373 A[4]=0; A[5]=0; A[6]=0; A[7]=0;
351 * I have nothing against unrolling but it's usually done for 374 }
352 * several reasons, namely: 375 for (i=(words - b->top)&7; i>0; i--,A++)
353 * - minimize percentage of decision making code, i.e. branches; 376 A[0]=0;
354 * - avoid cache trashing;
355 * - make it possible to schedule loads earlier;
356 * Now let's examine the code below. The cornerstone of C is
357 * "programmer is always right" and that's what we love it for:-)
358 * For this very reason C compilers have to be paranoid when it
359 * comes to data aliasing and assume the worst. Yeah, but what
360 * does it mean in real life? This means that loop body below will
361 * be compiled to sequence of loads immediately followed by stores
362 * as compiler assumes the worst, something in A==B+1 style. As a
363 * result CPU pipeline is going to starve for incoming data. Secondly
364 * if A and B happen to share same cache line such code is going to
365 * cause severe cache trashing. Both factors have severe impact on
366 * performance of modern CPUs and this is the reason why this
367 * particular piece of code is #ifdefed away and replaced by more
368 * "friendly" version found in #else section below. This comment
369 * also applies to BN_copy function.
370 *
371 * <appro@fy.chalmers.se>
372 */
373 for (i=b->top&(~7); i>0; i-=8)
374 {
375 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
376 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
377 A+=8;
378 B+=8;
379 }
380 switch (b->top&7)
381 {
382 case 7:
383 A[6]=B[6];
384 case 6:
385 A[5]=B[5];
386 case 5:
387 A[4]=B[4];
388 case 4:
389 A[3]=B[3];
390 case 3:
391 A[2]=B[2];
392 case 2:
393 A[1]=B[1];
394 case 1:
395 A[0]=B[0];
396 case 0:
397 /* I need the 'case 0' entry for utrix cc.
398 * If the optimizer is turned on, it does the
399 * switch table by doing
400 * a=top&7
401 * a--;
402 * goto jump_table[a];
403 * If top is 0, this makes us jump to 0xffffffc
404 * which is rather bad :-(.
405 * eric 23-Apr-1998
406 */
407 ;
408 }
409#else 377#else
410 for (i=b->top>>2; i>0; i--,A+=4,B+=4) 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
396BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
397 {
398 BIGNUM *r = NULL;
399
400 if (words > b->dmax)
401 {
402 BN_ULONG *a = bn_expand_internal(b, words);
403
404 if (a)
405 {
406 r = BN_new();
407 if (r)
411 { 408 {
412 /* 409 r->top = b->top;
413 * The fact that the loop is unrolled 410 r->dmax = words;
414 * 4-wise is a tribute to Intel. It's 411 r->neg = b->neg;
415 * the one that doesn't have enough 412 r->d = a;
416 * registers to accomodate more data.
417 * I'd unroll it 8-wise otherwise:-)
418 *
419 * <appro@fy.chalmers.se>
420 */
421 BN_ULONG a0,a1,a2,a3;
422 a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
423 A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
424 } 413 }
425 switch (b->top&3) 414 else
426 { 415 {
427 case 3: A[2]=B[2]; 416 /* r == NULL, BN_new failure */
428 case 2: A[1]=B[1]; 417 OPENSSL_free(a);
429 case 1: A[0]=B[0];
430 case 0: ; /* ultrix cc workaround, see above */
431 } 418 }
432#endif
433 OPENSSL_free(b->d);
434 } 419 }
420 /* If a == NULL, there was an error in allocation in
421 bn_expand_internal(), and NULL should be returned */
422 }
423 else
424 {
425 r = BN_dup(b);
426 }
435 427
436 b->d=a; 428 return r;
437 b->dmax=words; 429 }
430
431/* This is an internal function that should not be used in applications.
432 * It ensures that 'b' has enough room for a 'words' word number number.
433 * It is mostly used by the various BIGNUM routines. If there is an error,
434 * NULL is returned. If not, 'b' is returned. */
438 435
439 /* Now need to zero any data between b->top and b->max */ 436BIGNUM *bn_expand2(BIGNUM *b, int words)
437 {
438 if (words > b->dmax)
439 {
440 BN_ULONG *a = bn_expand_internal(b, words);
440 441
441 A= &(b->d[b->top]); 442 if (a)
442 for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
443 { 443 {
444 A[0]=0; A[1]=0; A[2]=0; A[3]=0; 444 if (b->d)
445 A[4]=0; A[5]=0; A[6]=0; A[7]=0; 445 OPENSSL_free(b->d);
446 }
447 for (i=(b->dmax - b->top)&7; i>0; i--,A++)
448 A[0]=0;
449#else
450 memset(A,0,sizeof(BN_ULONG)*(words+1));
451 memcpy(A,b->d,sizeof(b->d[0])*b->top);
452 b->d=a; 446 b->d=a;
453 b->max=words; 447 b->dmax=words;
454#endif 448 }
455 449 else
456/* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */ 450 b = NULL;
457/* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
458
459 } 451 }
460 return(b); 452 return b;
461 } 453 }
462 454
463BIGNUM *BN_dup(const BIGNUM *a) 455BIGNUM *BN_dup(const BIGNUM *a)
464 { 456 {
465 BIGNUM *r; 457 BIGNUM *r, *t;
466 458
467 if (a == NULL) return NULL; 459 if (a == NULL) return NULL;
468 460
469 bn_check_top(a); 461 bn_check_top(a);
470 462
471 r=BN_new(); 463 t = BN_new();
472 if (r == NULL) return(NULL); 464 if (t == NULL) return(NULL);
473 return((BIGNUM *)BN_copy(r,a)); 465 r = BN_copy(t, a);
466 /* now r == t || r == NULL */
467 if (r == NULL)
468 BN_free(t);
469 return r;
474 } 470 }
475 471
476BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 472BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
@@ -498,7 +494,7 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
498 case 3: A[2]=B[2]; 494 case 3: A[2]=B[2];
499 case 2: A[1]=B[1]; 495 case 2: A[1]=B[1];
500 case 1: A[0]=B[0]; 496 case 1: A[0]=B[0];
501 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */ 497 case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */
502 } 498 }
503#else 499#else
504 memcpy(a->d,b->d,sizeof(b->d[0])*b->top); 500 memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
@@ -512,6 +508,35 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
512 return(a); 508 return(a);
513 } 509 }
514 510
511void BN_swap(BIGNUM *a, BIGNUM *b)
512 {
513 int flags_old_a, flags_old_b;
514 BN_ULONG *tmp_d;
515 int tmp_top, tmp_dmax, tmp_neg;
516
517 flags_old_a = a->flags;
518 flags_old_b = b->flags;
519
520 tmp_d = a->d;
521 tmp_top = a->top;
522 tmp_dmax = a->dmax;
523 tmp_neg = a->neg;
524
525 a->d = b->d;
526 a->top = b->top;
527 a->dmax = b->dmax;
528 a->neg = b->neg;
529
530 b->d = tmp_d;
531 b->top = tmp_top;
532 b->dmax = tmp_dmax;
533 b->neg = tmp_neg;
534
535 a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
536 b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
537 }
538
539
515void BN_clear(BIGNUM *a) 540void BN_clear(BIGNUM *a)
516 { 541 {
517 if (a->d != NULL) 542 if (a->d != NULL)
@@ -520,7 +545,7 @@ void BN_clear(BIGNUM *a)
520 a->neg=0; 545 a->neg=0;
521 } 546 }
522 547
523BN_ULONG BN_get_word(BIGNUM *a) 548BN_ULONG BN_get_word(const BIGNUM *a)
524 { 549 {
525 int i,n; 550 int i,n;
526 BN_ULONG ret=0; 551 BN_ULONG ret=0;
@@ -568,7 +593,6 @@ int BN_set_word(BIGNUM *a, BN_ULONG w)
568 return(1); 593 return(1);
569 } 594 }
570 595
571/* ignore negative */
572BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 596BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
573 { 597 {
574 unsigned int i,m; 598 unsigned int i,m;
@@ -589,6 +613,7 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
589 i=((n-1)/BN_BYTES)+1; 613 i=((n-1)/BN_BYTES)+1;
590 m=((n-1)%(BN_BYTES)); 614 m=((n-1)%(BN_BYTES));
591 ret->top=i; 615 ret->top=i;
616 ret->neg=0;
592 while (n-- > 0) 617 while (n-- > 0)
593 { 618 {
594 l=(l<<8L)| *(s++); 619 l=(l<<8L)| *(s++);
@@ -743,7 +768,7 @@ int BN_mask_bits(BIGNUM *a, int n)
743 return(1); 768 return(1);
744 } 769 }
745 770
746int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n) 771int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
747 { 772 {
748 int i; 773 int i;
749 BN_ULONG aa,bb; 774 BN_ULONG aa,bb;
@@ -760,3 +785,34 @@ int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n)
760 return(0); 785 return(0);
761 } 786 }
762 787
788/* Here follows a specialised variants of bn_cmp_words(). It has the
789 property of performing the operation on arrays of different sizes.
790 The sizes of those arrays is expressed through cl, which is the
791 common length ( basicall, min(len(a),len(b)) ), and dl, which is the
792 delta between the two lengths, calculated as len(a)-len(b).
793 All lengths are the number of BN_ULONGs... */
794
795int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
796 int cl, int dl)
797 {
798 int n,i;
799 n = cl-1;
800
801 if (dl < 0)
802 {
803 for (i=dl; i<0; i++)
804 {
805 if (b[n-i] != 0)
806 return -1; /* a < b */
807 }
808 }
809 if (dl > 0)
810 {
811 for (i=dl; i>0; i--)
812 {
813 if (a[n+i] != 0)
814 return 1; /* a > b */
815 }
816 }
817 return bn_cmp_words(a,b,cl);
818 }
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 03:29:22 +0000