summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_mul.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_mul.c')
-rw-r--r--src/lib/libcrypto/bn/bn_mul.c423
1 files changed, 1 insertions, 422 deletions
diff --git a/src/lib/libcrypto/bn/bn_mul.c b/src/lib/libcrypto/bn/bn_mul.c
index fe3f29617f..118e8cddc5 100644
--- a/src/lib/libcrypto/bn/bn_mul.c
+++ b/src/lib/libcrypto/bn/bn_mul.c
@@ -1,4 +1,4 @@
1/* $OpenBSD: bn_mul.c,v 1.36 2023/03/30 14:28:56 tb Exp $ */ 1/* $OpenBSD: bn_mul.c,v 1.37 2023/04/19 10:51:22 jsing Exp $ */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -313,323 +313,8 @@ bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
313 } 313 }
314} 314}
315 315
316#ifdef BN_RECURSION
317/* Karatsuba recursive multiplication algorithm
318 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */
319
320/* r is 2*n2 words in size,
321 * a and b are both n2 words in size.
322 * n2 must be a power of 2.
323 * We multiply and return the result.
324 * t must be 2*n2 words in size
325 * We calculate
326 * a[0]*b[0]
327 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
328 * a[1]*b[1]
329 */
330/* dnX may not be positive, but n2/2+dnX has to be */
331void
332bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, int dna,
333 int dnb, BN_ULONG *t)
334{
335 int n = n2 / 2, c1, c2;
336 int tna = n + dna, tnb = n + dnb;
337 unsigned int neg, zero;
338 BN_ULONG ln, lo, *p;
339
340# ifdef BN_MUL_COMBA
341# if 0
342 if (n2 == 4) {
343 bn_mul_comba4(r, a, b);
344 return;
345 }
346# endif
347 /* Only call bn_mul_comba 8 if n2 == 8 and the
348 * two arrays are complete [steve]
349 */
350 if (n2 == 8 && dna == 0 && dnb == 0) {
351 bn_mul_comba8(r, a, b);
352 return;
353 }
354# endif /* BN_MUL_COMBA */
355 /* Else do normal multiply */
356 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
357 bn_mul_normal(r, a, n2 + dna, b, n2 + dnb);
358 if ((dna + dnb) < 0)
359 memset(&r[2*n2 + dna + dnb], 0,
360 sizeof(BN_ULONG) * -(dna + dnb));
361 return;
362 }
363 /* r=(a[0]-a[1])*(b[1]-b[0]) */
364 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
365 c2 = bn_cmp_part_words(&(b[n]), b,tnb, tnb - n);
366 zero = neg = 0;
367 switch (c1 * 3 + c2) {
368 case -4:
369 bn_sub(t, n, &a[n], tna, a, n); /* - */
370 bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
371 break;
372 case -3:
373 zero = 1;
374 break;
375 case -2:
376 bn_sub(t, n, &a[n], tna, a, n); /* - */
377 bn_sub(&t[n], n, &b[n], tnb, b, n); /* + */
378 neg = 1;
379 break;
380 case -1:
381 case 0:
382 case 1:
383 zero = 1;
384 break;
385 case 2:
386 bn_sub(t, n, a, n, &a[n], tna); /* + */
387 bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
388 neg = 1;
389 break;
390 case 3:
391 zero = 1;
392 break;
393 case 4:
394 bn_sub(t, n, a, n, &a[n], tna);
395 bn_sub(&t[n], n, &b[n], tnb, b, n);
396 break;
397 }
398
399# ifdef BN_MUL_COMBA
400 if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take
401 extra args to do this well */
402 {
403 if (!zero)
404 bn_mul_comba4(&(t[n2]), t, &(t[n]));
405 else
406 memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG));
407
408 bn_mul_comba4(r, a, b);
409 bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
410 } else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could
411 take extra args to do this
412 well */
413 {
414 if (!zero)
415 bn_mul_comba8(&(t[n2]), t, &(t[n]));
416 else
417 memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG));
418
419 bn_mul_comba8(r, a, b);
420 bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
421 } else
422# endif /* BN_MUL_COMBA */
423 {
424 p = &(t[n2 * 2]);
425 if (!zero)
426 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
427 else
428 memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG));
429 bn_mul_recursive(r, a, b, n, 0, 0, p);
430 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p);
431 }
432
433 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
434 * r[10] holds (a[0]*b[0])
435 * r[32] holds (b[1]*b[1])
436 */
437
438 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
439
440 if (neg) /* if t[32] is negative */
441 {
442 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
443 } else {
444 /* Might have a carry */
445 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
446 }
447
448 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
449 * r[10] holds (a[0]*b[0])
450 * r[32] holds (b[1]*b[1])
451 * c1 holds the carry bits
452 */
453 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
454 if (c1) {
455 p = &(r[n + n2]);
456 lo= *p;
457 ln = (lo + c1) & BN_MASK2;
458 *p = ln;
459
460 /* The overflow will stop before we over write
461 * words we should not overwrite */
462 if (ln < (BN_ULONG)c1) {
463 do {
464 p++;
465 lo= *p;
466 ln = (lo + 1) & BN_MASK2;
467 *p = ln;
468 } while (ln == 0);
469 }
470 }
471}
472
473/* n+tn is the word length
474 * t needs to be n*4 is size, as does r */
475/* tnX may not be negative but less than n */
476void
477bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, int tna,
478 int tnb, BN_ULONG *t)
479{
480 int i, j, n2 = n * 2;
481 int c1, c2, neg;
482 BN_ULONG ln, lo, *p;
483
484 if (n < 8) {
485 bn_mul_normal(r, a, n + tna, b, n + tnb);
486 return;
487 }
488
489 /* r=(a[0]-a[1])*(b[1]-b[0]) */
490 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna);
491 c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n);
492 neg = 0;
493 switch (c1 * 3 + c2) {
494 case -4:
495 bn_sub(t, n, &a[n], tna, a, n); /* - */
496 bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
497 break;
498 case -3:
499 /* break; */
500 case -2:
501 bn_sub(t, n, &a[n], tna, a, n); /* - */
502 bn_sub(&t[n], n, &b[n], tnb, b, n); /* + */
503 neg = 1;
504 break;
505 case -1:
506 case 0:
507 case 1:
508 /* break; */
509 case 2:
510 bn_sub(t, n, a, n, &a[n], tna); /* + */
511 bn_sub(&t[n], n, b, n, &b[n], tnb); /* - */
512 neg = 1;
513 break;
514 case 3:
515 /* break; */
516 case 4:
517 bn_sub(t, n, a, n, &a[n], tna);
518 bn_sub(&t[n], n, &b[n], tnb, b, n);
519 break;
520 }
521 /* The zero case isn't yet implemented here. The speedup
522 would probably be negligible. */
523# if 0
524 if (n == 4) {
525 bn_mul_comba4(&(t[n2]), t, &(t[n]));
526 bn_mul_comba4(r, a, b);
527 bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
528 memset(&(r[n2 + tn * 2]), 0, sizeof(BN_ULONG) * (n2 - tn * 2));
529 } else
530# endif
531 if (n == 8) {
532 bn_mul_comba8(&(t[n2]), t, &(t[n]));
533 bn_mul_comba8(r, a, b);
534 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb);
535 memset(&(r[n2 + tna + tnb]), 0,
536 sizeof(BN_ULONG) * (n2 - tna - tnb));
537 } else {
538 p = &(t[n2*2]);
539 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p);
540 bn_mul_recursive(r, a, b, n, 0, 0, p);
541 i = n / 2;
542 /* If there is only a bottom half to the number,
543 * just do it */
544 if (tna > tnb)
545 j = tna - i;
546 else
547 j = tnb - i;
548 if (j == 0) {
549 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]),
550 i, tna - i, tnb - i, p);
551 memset(&(r[n2 + i * 2]), 0,
552 sizeof(BN_ULONG) * (n2 - i * 2));
553 }
554 else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */
555 {
556 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]),
557 i, tna - i, tnb - i, p);
558 memset(&(r[n2 + tna + tnb]), 0,
559 sizeof(BN_ULONG) * (n2 - tna - tnb));
560 }
561 else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
562 {
563 memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2);
564 if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL &&
565 tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) {
566 bn_mul_normal(&(r[n2]), &(a[n]), tna,
567 &(b[n]), tnb);
568 } else {
569 for (;;) {
570 i /= 2;
571 /* these simplified conditions work
572 * exclusively because difference
573 * between tna and tnb is 1 or 0 */
574 if (i < tna || i < tnb) {
575 bn_mul_part_recursive(&(r[n2]),
576 &(a[n]), &(b[n]), i,
577 tna - i, tnb - i, p);
578 break;
579 } else if (i == tna || i == tnb) {
580 bn_mul_recursive(&(r[n2]),
581 &(a[n]), &(b[n]), i,
582 tna - i, tnb - i, p);
583 break;
584 }
585 }
586 }
587 }
588 }
589
590 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
591 * r[10] holds (a[0]*b[0])
592 * r[32] holds (b[1]*b[1])
593 */
594
595 c1 = (int)(bn_add_words(t, r,&(r[n2]), n2));
596
597 if (neg) /* if t[32] is negative */
598 {
599 c1 -= (int)(bn_sub_words(&(t[n2]), t,&(t[n2]), n2));
600 } else {
601 /* Might have a carry */
602 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
603 }
604
605 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
606 * r[10] holds (a[0]*b[0])
607 * r[32] holds (b[1]*b[1])
608 * c1 holds the carry bits
609 */
610 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
611 if (c1) {
612 p = &(r[n + n2]);
613 lo= *p;
614 ln = (lo + c1)&BN_MASK2;
615 *p = ln;
616
617 /* The overflow will stop before we over write
618 * words we should not overwrite */
619 if (ln < (BN_ULONG)c1) {
620 do {
621 p++;
622 lo= *p;
623 ln = (lo + 1) & BN_MASK2;
624 *p = ln;
625 } while (ln == 0);
626 }
627 }
628}
629#endif /* BN_RECURSION */
630 316
631#ifndef HAVE_BN_MUL 317#ifndef HAVE_BN_MUL
632#ifndef BN_RECURSION
633int 318int
634bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx) 319bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
635{ 320{
@@ -638,112 +323,6 @@ bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
638 return 1; 323 return 1;
639} 324}
640 325
641#else /* BN_RECURSION */
642int
643bn_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, int rn, BN_CTX *ctx)
644{
645 BIGNUM *t = NULL;
646 int al, bl, i, k;
647 int j = 0;
648 int ret = 0;
649
650 BN_CTX_start(ctx);
651
652 al = a->top;
653 bl = b->top;
654
655 i = al - bl;
656
657 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
658 if (i >= -1 && i <= 1) {
659 /* Find out the power of two lower or equal
660 to the longest of the two numbers */
661 if (i >= 0) {
662 j = BN_num_bits_word((BN_ULONG)al);
663 }
664 if (i == -1) {
665 j = BN_num_bits_word((BN_ULONG)bl);
666 }
667 j = 1 << (j - 1);
668 assert(j <= al || j <= bl);
669 k = j + j;
670 if ((t = BN_CTX_get(ctx)) == NULL)
671 goto err;
672 if (al > j || bl > j) {
673 if (!bn_wexpand(t, k * 4))
674 goto err;
675 if (!bn_wexpand(r, k * 4))
676 goto err;
677 bn_mul_part_recursive(r->d, a->d, b->d,
678 j, al - j, bl - j, t->d);
679 }
680 else /* al <= j || bl <= j */
681 {
682 if (!bn_wexpand(t, k * 2))
683 goto err;
684 if (!bn_wexpand(r, k * 2))
685 goto err;
686 bn_mul_recursive(r->d, a->d, b->d,
687 j, al - j, bl - j, t->d);
688 }
689 r->top = rn;
690 goto end;
691 }
692#if 0
693 if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA)) {
694 BIGNUM *tmp_bn = (BIGNUM *)b;
695 if (!bn_wexpand(tmp_bn, al))
696 goto err;
697 tmp_bn->d[bl] = 0;
698 bl++;
699 i--;
700 } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
701 BIGNUM *tmp_bn = (BIGNUM *)a;
702 if (!bn_wexpand(tmp_bn, bl))
703 goto err;
704 tmp_bn->d[al] = 0;
705 al++;
706 i++;
707 }
708 if (i == 0) {
709 /* symmetric and > 4 */
710 /* 16 or larger */
711 j = BN_num_bits_word((BN_ULONG)al);
712 j = 1 << (j - 1);
713 k = j + j;
714 if ((t = BN_CTX_get(ctx)) == NULL)
715 goto err;
716 if (al == j) /* exact multiple */
717 {
718 if (!bn_wexpand(t, k * 2))
719 goto err;
720 if (!bn_wexpand(r, k * 2))
721 goto err;
722 bn_mul_recursive(r->d, a->d, b->d, al, t->d);
723 } else {
724 if (!bn_wexpand(t, k * 4))
725 goto err;
726 if (!bn_wexpand(r, k * 4))
727 goto err;
728 bn_mul_part_recursive(r->d, a->d, b->d,
729 al - j, j, t->d);
730 }
731 r->top = top;
732 goto end;
733 }
734#endif
735 }
736
737 bn_mul_normal(r->d, a->d, al, b->d, bl);
738
739 end:
740 ret = 1;
741 err:
742 BN_CTX_end(ctx);
743
744 return ret;
745}
746#endif /* BN_RECURSION */
747#endif /* HAVE_BN_MUL */ 326#endif /* HAVE_BN_MUL */
748 327
749int 328int
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-21 02:41:00 +0000