-
+ B4DF4BE19361F59AE40B0E80F90E1317FD28F95F32C7F6CE98C3D028679E5F6F2B90C2749E03CE029BF924BCFAFB953226EE8173D48490E86E600E7989AA6344
ffa/libffa/fz_lomul.adb
(0 . 0)(1 . 179)
577 ------------------------------------------------------------------------------
578 ------------------------------------------------------------------------------
579 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
580 -- --
581 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
582 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
583 -- --
584 -- You do not have, nor can you ever acquire the right to use, copy or --
585 -- distribute this software ; Should you use this software for any purpose, --
586 -- or copy and distribute it to anyone or in any manner, you are breaking --
587 -- the laws of whatever soi-disant jurisdiction, and you promise to --
588 -- continue doing so for the indefinite future. In any case, please --
589 -- always : read and understand any software ; verify any PGP signatures --
590 -- that you use - for any purpose. --
591 -- --
592 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
593 ------------------------------------------------------------------------------
594 ------------------------------------------------------------------------------
595
596 with Words; use Words;
597 with Word_Ops; use Word_Ops;
598 with W_Mul; use W_Mul;
599 with FZ_Arith; use FZ_Arith;
600 with FZ_Mul; use FZ_Mul;
601
602
603 -- "Low Multiplication" computes only the bottom half of the product XY.
604 -- Presently, it is used solely in Barrett's Modular Reduction.
605
606 package body FZ_LoMul is
607
608 -- Low-Only Comba's multiplier. (CAUTION: UNBUFFERED)
609 procedure FZ_Low_Mul_Comba(X : in FZ;
610 Y : in FZ;
611 XY : out FZ) is
612
613 -- Words in each multiplicand (and also in the half-product)
614 L : constant Word_Index := X'Length;
615
616 -- 3-word Accumulator
617 A2, A1, A0 : Word := 0;
618
619 begin
620
621 -- Compute the lower half of the Product, which is all we want:
622 for N in 0 .. L - 1 loop
623
624 -- Compute the Nth (indexed from zero) column of the Half-Product
625 declare
626
627 -- The outputs of a Word multiplication
628 Lo, Hi : Word;
629
630 -- Carry for the Accumulator addition
631 C : WBool;
632
633 -- Sum for Accumulator addition
634 Sum : Word;
635
636 begin
637
638 -- For lower half of XY, will go from 0 to N
639 -- For upper half of XY, will go from N - L + 1 to L - 1
640 for j in 0 .. N loop
641
642 -- Hi:Lo := j-th Word of X * (N - j)-th Word of Y
643 Mul_Word(X(X'First + j),
644 Y(Y'First - j + N),
645 Lo, Hi);
646
647 -- Now add Hi:Lo into the Accumulator:
648
649 -- A0 += Lo; C := Carry
650 Sum := A0 + Lo;
651 C := W_Carry(A0, Lo, Sum);
652 A0 := Sum;
653
654 -- A1 += Hi + C; C := Carry
655 Sum := A1 + Hi + C;
656 C := W_Carry(A1, Hi, Sum);
657 A1 := Sum;
658
659 -- A2 += A2 + C
660 A2 := A2 + C;
661
662 end loop;
663
664 -- We now have the Nth (indexed from zero) word of XY
665 XY(XY'First + N) := A0;
666
667 -- Right-Shift the Accumulator by one Word width:
668 A0 := A1;
669 A1 := A2;
670 A2 := 0;
671 end;
672
673 end loop;
674
675 end FZ_Low_Mul_Comba;
676
677
678 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
679 procedure Low_Mul(X : in FZ;
680 Y : in FZ;
681 XY : out FZ) is
682
683 -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
684 L : constant Word_Count := X'Length;
685
686 -- K is HALF of the length of a multiplicand.
687 K : constant Word_Index := L / 2;
688
689 -- A 'KSeg' is the same length as HALF of a multiplicand.
690 subtype KSeg is FZ(1 .. K);
691
692 -- The two K-sized variables of the half-product equation:
693 LH, HL : KSeg;
694
695 -- Bottom and Top K-sized halves of the multiplicand X.
696 XLo : KSeg renames X( X'First .. X'Last - K );
697 XHi : KSeg renames X( X'First + K .. X'Last );
698
699 -- Bottom and Top K-sized halves of the multiplicand Y.
700 YLo : KSeg renames Y( Y'First .. Y'Last - K );
701 YHi : KSeg renames Y( Y'First + K .. Y'Last );
702
703 -- Top K-sized half of the half-product XY.
704 XYHi : KSeg renames XY( XY'First + K .. XY'Last );
705
706 -- Carry from individual term additions.
707 C : WBool;
708 pragma Unreferenced(C);
709
710 begin
711
712 -- Recurse to FULL-width multiplication: XY := XLo * YLo
713 FZ_Multiply_Unbuffered(XLo, YLo, XY);
714
715 -- Recurse to HALF-width multiplication: LH := XLo * YHi
716 FZ_Low_Multiply_Unbuffered(XLo, YHi, LH);
717
718 -- Recurse to HALF-width multiplication: HL := XHi * YLo
719 FZ_Low_Multiply_Unbuffered(XHi, YLo, HL);
720
721 -- XY += 2^(K * Bitness) * LH
722 FZ_Add_D(X => XYHi, Y => LH, Overflow => C);
723
724 -- XY += 2^(K * Bitness) * HL
725 FZ_Add_D(X => XYHi, Y => HL, Overflow => C);
726
727 end Low_Mul;
728 -- CAUTION: Inlining prohibited for Low_Mul !
729
730
731 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
732 procedure FZ_Low_Multiply_Unbuffered(X : in FZ;
733 Y : in FZ;
734 XY : out FZ) is
735
736 -- The length of either multiplicand
737 L : constant Word_Count := X'Length;
738
739 begin
740
741 if L <= Low_Mul_Thresh then
742
743 -- Base case:
744 FZ_Low_Mul_Comba(X, Y, XY);
745
746 else
747
748 -- Recursive case:
749 Low_Mul(X, Y, XY);
750
751 end if;
752
753 end FZ_Low_Multiply_Unbuffered;
754
755 end FZ_LoMul;