------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
--                                                                          --
-- (C) 2017 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;


package body FZ_Mul is
   
   -- Comba's multiplier.
   procedure FZ_Mul_Comba(X     : in  FZ;
                          Y     : in  FZ;
                          XY_Lo : out FZ;
                          XY_Hi : out FZ) is

      -- Words in each multiplicand
      L : constant Word_Index := X'Length;

      -- Length of Product, i.e. double the length of either multiplicand
      LP : constant Word_Index := 2 * L;

      -- Register holding Product; indexed from zero
      XY : FZ(0 .. LP - 1);

      procedure Asm_Comba(X      : in  FZ;
                          Y      : in  FZ;
                          XY     : out FZ;
                          X_Size : in  Word_Count);
      pragma Import (C, Asm_Comba, "x86_64_comba");
   begin
      Asm_Comba(X, Y, XY, L);
      XY_Lo := XY(0 .. L - 1);
      XY_Hi := XY(L .. XY'Last);
   end FZ_Mul_Comba;

   -- Comba's multiplier.
   procedure FZ_Mul_Comba_C(X     : in  FZ;
                            Y     : in  FZ;
                            XY_Lo : out FZ;
                            XY_Hi : out FZ) is
      
      -- Words in each multiplicand
      L : constant Word_Index := X'Length;
      
      -- Length of Product, i.e. double the length of either multiplicand
      LP : constant Word_Index := 2 * L;
      
      -- 3-word Accumulator
      A2, A1, A0 : Word := 0;
      
      -- Register holding Product; indexed from zero
      XY : FZ(0 .. LP - 1);
      
      -- Type for referring to a column of XY
      subtype ColXY is Word_Index range XY'Range;
      
      -- Compute the Nth (indexed from zero) column of the Product
      procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
         
         -- 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 U .. V 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(N) := A0;
         
         -- Right-Shift the Accumulator by one Word width:
         A0 := A1;
         A1 := A2;
         A2 := 0;
         
      end Col;
      pragma Inline_Always(Col);
      
   begin
      
      -- Compute the lower half of the Product:
      for i in 0 .. L - 1 loop
         
         Col(i, 0, i);
         
      end loop;
      
      -- Compute the upper half (sans last Word) of the Product:
      for i in L .. LP - 2 loop
         
         Col(i, i - L + 1, L - 1);
         
      end loop;
      
      -- The very last Word of the Product:
      XY(XY'Last) := A0;
      
      -- Output the Product's lower and upper FZs:
      XY_Lo := XY(0 .. L - 1);
      XY_Hi := XY(L .. XY'Last);
      
   end FZ_Mul_Comba_C;
   pragma Inline_Always(FZ_Mul_Comba);
   
end FZ_Mul;