-
+ B4DF4BE19361F59AE40B0E80F90E1317FD28F95F32C7F6CE98C3D028679E5F6F2B90C2749E03CE029BF924BCFAFB953226EE8173D48490E86E600E7989AA6344
ffa/libffa/fz_lomul.adb

(0 . 0)(1 . 179)
------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
--                                                                          --
-- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org )                      --
-- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
--                                                                          --
-- You do not have, nor can you ever acquire the right to use, copy or      --
-- distribute this software ; Should you use this software for any purpose, --
-- or copy and distribute it to anyone or in any manner, you are breaking   --
-- the laws of whatever soi-disant jurisdiction, and you promise to         --
-- continue doing so for the indefinite future. In any case, please         --
-- always : read and understand any software ; verify any PGP signatures    --
-- that you use - for any purpose.                                          --
--                                                                          --
-- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
------------------------------------------------------------------------------
------------------------------------------------------------------------------

with Words;    use Words;
with Word_Ops; use Word_Ops;
with W_Mul;    use W_Mul;
with FZ_Arith; use FZ_Arith;
with FZ_Mul;   use FZ_Mul;


-- "Low Multiplication" computes only the bottom half of the product XY.
-- Presently, it is used solely in Barrett's Modular Reduction.

package body FZ_LoMul is
      
   -- Low-Only Comba's multiplier. (CAUTION: UNBUFFERED)
   procedure FZ_Low_Mul_Comba(X     : in  FZ;
                              Y     : in  FZ;
                              XY    : out FZ) is
      
      -- Words in each multiplicand (and also in the half-product)
      L : constant Word_Index := X'Length;
      
      -- 3-word Accumulator
      A2, A1, A0 : Word := 0;
      
   begin
      
      -- Compute the lower half of the Product, which is all we want:
      for N in 0 .. L - 1 loop
         
         -- Compute the Nth (indexed from zero) column of the Half-Product
         declare
            
            -- The outputs of a Word multiplication
            Lo, Hi : Word;
            
            -- Carry for the Accumulator addition
            C      : WBool;
            
            -- Sum for Accumulator addition
            Sum    : Word;
            
         begin
            
            -- For lower half of XY, will go from 0 to N
            -- For upper half of XY, will go from N - L + 1 to L - 1
            for j in 0 .. N loop
               
               -- Hi:Lo := j-th Word of X  *  (N - j)-th Word of Y
               Mul_Word(X(X'First + j),
                        Y(Y'First - j + N),
                        Lo, Hi);
               
               -- Now add Hi:Lo into the Accumulator:
               
               -- A0 += Lo; C := Carry
               Sum := A0 + Lo;
               C   := W_Carry(A0, Lo, Sum);
               A0  := Sum;
               
               -- A1 += Hi + C; C := Carry
               Sum := A1 + Hi + C;
               C   := W_Carry(A1, Hi, Sum);
               A1  := Sum;
               
               -- A2 += A2 + C
               A2  := A2 + C;
               
            end loop;
            
            -- We now have the Nth (indexed from zero) word of XY
            XY(XY'First + N) := A0;
            
            -- Right-Shift the Accumulator by one Word width:
            A0 := A1;
            A1 := A2;
            A2 := 0;
         end;
         
      end loop;
      
   end FZ_Low_Mul_Comba;
   
   
   -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
   procedure Low_Mul(X  : in  FZ;
                     Y  : in  FZ;
                     XY : out FZ) is
      
      -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
      L : constant Word_Count := X'Length;
      
      -- K is HALF of the length of a multiplicand.
      K : constant Word_Index := L / 2;
      
      -- A 'KSeg' is the same length as HALF of a multiplicand.
      subtype KSeg is FZ(1 .. K);
      
      -- The two K-sized variables of the half-product equation:
      LH, HL : KSeg;
      
      -- Bottom and Top K-sized halves of the multiplicand X.
      XLo        : KSeg  renames    X(  X'First       ..   X'Last - K );
      XHi        : KSeg  renames    X(  X'First + K   ..   X'Last     );
      
      -- Bottom and Top K-sized halves of the multiplicand Y.
      YLo        : KSeg  renames    Y(  Y'First       ..   Y'Last - K );
      YHi        : KSeg  renames    Y(  Y'First + K   ..   Y'Last     );
      
      -- Top K-sized half of the half-product XY.
      XYHi       : KSeg  renames   XY( XY'First + K   ..  XY'Last     );
      
      -- Carry from individual term additions.
      C          : WBool;
      pragma Unreferenced(C);
      
   begin
      
      -- Recurse to FULL-width multiplication: XY := XLo * YLo
      FZ_Multiply_Unbuffered(XLo, YLo, XY);
      
      -- Recurse to HALF-width multiplication: LH := XLo * YHi
      FZ_Low_Multiply_Unbuffered(XLo, YHi, LH);
      
      -- Recurse to HALF-width multiplication: HL := XHi * YLo
      FZ_Low_Multiply_Unbuffered(XHi, YLo, HL);
      
      -- XY += 2^(K * Bitness) * LH
      FZ_Add_D(X => XYHi, Y => LH, Overflow => C);
      
      -- XY += 2^(K * Bitness) * HL
      FZ_Add_D(X => XYHi, Y => HL, Overflow => C);
      
   end Low_Mul;
   -- CAUTION: Inlining prohibited for Low_Mul !
   
   
   -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
   procedure FZ_Low_Multiply_Unbuffered(X     : in  FZ;
                                        Y     : in  FZ;
                                        XY    : out FZ) is
      
      -- The length of either multiplicand
      L : constant Word_Count := X'Length;
      
   begin
      
      if L <= Low_Mul_Thresh then
         
         -- Base case:
         FZ_Low_Mul_Comba(X, Y, XY);
         
      else
         
         -- Recursive case:
         Low_Mul(X, Y, XY);
         
      end if;
      
   end FZ_Low_Multiply_Unbuffered;
   
end FZ_LoMul;