(18 . 71)(18 . 108)
------------------------------------------------------------------------------

with Words;    use Words;
with W_Shifts; use W_Shifts;
with FZ_Basic; use FZ_Basic;
with FZ_Arith; use FZ_Arith;
with FZ_Shift; use FZ_Shift;
with Word_Ops; use Word_Ops;
with W_Mul;    use W_Mul;


package body FZ_Mul is
   
   -- 'Egyptological' multiplier. XY_Lo and XY_Hi hold result of X*Y.
   procedure FZ_Mul_Egyptian(X     : in  FZ;
                             Y     : in  FZ;
                             XY_Lo : out FZ;
                             XY_Hi : out FZ) is
   -- Comba's multiplier.
   procedure FZ_Mul_Comba(X     : in  FZ;
                          Y     : in  FZ;
                          XY_Lo : out FZ;
                          XY_Hi : out FZ) is
      
      L : constant Indices := X'Length;
      -- Words in each multiplicand
      L : constant Word_Index := X'Length;
      
      -- Register holding running product
      XY : FZ(1 .. X'Length + Y'Length);
      -- Length of Product, i.e. double the length of either multiplicand
      LP : constant Word_Index := 2 * L;
      
      -- X-Slide
      XS : FZ(1 .. X'Length + Y'Length);
      -- 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
      -- Product register begins empty
      FZ_Clear(XY);
      
      -- X-Slide initially equals X:
      XS(1            .. X'Length) := X;
      XS(X'Length + 1 .. XS'Last)  := (others => 0);
      
      -- For each word of Y:
      for i in Y'Range loop
         
         declare
            -- Current word of Y
            W : Word  := Y(i);
            
            -- Current cut of XY and XS. Stay ahead by a word to handle carry.
            Cut : constant Indices := L + i;
            XYc : FZ renames XY(1 .. Cut);
            XSc : FZ renames XS(1 .. Cut);
            
         begin
            for b in 1 .. Bitness loop
               
               -- If current Y bit is 1, X-Slide Cut is added into XY Cut
               FZ_Add_Gated(X    => XYc, Y => XSc, Sum => XYc,
                            Gate => W and 1);
               
               -- Crank the next bit of Y into the bottom position of W
               W := Shift_Right(W, 1);
               
               -- X-Slide := X-Slide * 2
               FZ_ShiftLeft(XSc, XSc, 1);
               
            end loop;
         end;
      -- 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;
      
      -- Write out the Product's lower and upper FZs:
      XY_Lo := XY(1                .. XY_Lo'Length);
      XY_Hi := XY(XY_Lo'Length + 1 .. XY'Last);
      -- The very last Word of the Product:
      XY(XY'Last) := A0;
      
   end FZ_Mul_Egyptian;
   pragma Inline_Always(FZ_Mul_Egyptian);

      -- Output the Product's lower and upper FZs:
      XY_Lo := XY(0 .. L - 1);
      XY_Hi := XY(L .. XY'Last);
      
   end FZ_Mul_Comba;
   pragma Inline_Always(FZ_Mul_Comba);
   
end FZ_Mul;