(20 . 15)(20 . 15)
with Words;    use Words;
with Word_Ops; use Word_Ops;
with W_Mul;    use W_Mul;
with FZ_Arith; use FZ_Arith;


package body FZ_Mul is
   
   -- Comba's multiplier.
      
   -- Comba's multiplier. (CAUTION: UNBUFFERED)
   procedure FZ_Mul_Comba(X     : in  FZ;
                          Y     : in  FZ;
                          XY_Lo : out FZ;
                          XY_Hi : out FZ) is
                          XY    : out FZ) is
      
      -- Words in each multiplicand
      L : constant Word_Index := X'Length;
(39 . 11)(39 . 8)
      -- 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;
      subtype ColXY is Word_Index range 0 .. LP - 1;
      
      -- Compute the Nth (indexed from zero) column of the Product
      procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
(86 . 7)(83 . 7)
         end loop;
         
         -- We now have the Nth (indexed from zero) word of XY
         XY(N) := A0;
         XY(XY'First + N) := A0;
         
         -- Right-Shift the Accumulator by one Word width:
         A0 := A1;
(115 . 11)(112 . 163)
      -- 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;
   pragma Inline_Always(FZ_Mul_Comba);
   
   
   -- Karatsuba's Multiplier. (CAUTION: UNBUFFERED)
   procedure Mul_Karatsuba(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;
      
      -- An 'LSeg' is the same length as either multiplicand.
      subtype LSeg is FZ(1 .. L);
      
      -- 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 three L-sized variables of the product equation, i.e.:
      -- XY = LL + 2^(K*Bitness)(LL + HH + (-1^DD_Sub)*DD) + 2^(2*K*Bitness)HH
      LL, DD, HH : LSeg;
      
      -- K-sized terms of Dx * Dy = DD
      Dx, Dy     : KSeg;  -- Dx = abs(XLo - XHi) , Dy = abs(YLo - YHi)
      
      -- Subtraction borrows, signs of (XL - XH) and (YL - YH),
      Cx, Cy     : WBool; -- so that we can calculate (-1^DD_Sub)
      
      -- 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     );
      
      -- L-sized middle segment of the product XY (+/- K from the midpoint).
      XYMid      : LSeg  renames   XY( XY'First + K   ..  XY'Last - K );
      
      -- Bottom and Top L-sized halves of the product XY.
      XYLo       : LSeg  renames   XY( XY'First       ..  XY'Last - L );
      XYHi       : LSeg  renames   XY( XY'First + L   ..  XY'Last     );
      
      -- Topmost K-sized quarter segment of the product XY, or 'tail'
      XYHiHi     : KSeg  renames XYHi( XYHi'First + K .. XYHi'Last    );
      
      -- Whether the DD term is being subtracted.
      DD_Sub     : WBool;
      
      -- Carry from individual term additions.
      C          : WBool;
      
      -- Tail-Carry accumulator, for the final ripple
      TC         : Word;
      
   begin
      
      -- Recurse: LL := XL * YL
      FZ_Multiply(XLo, YLo, LL);
      
      -- Recurse: HH := XH * YH
      FZ_Multiply(XHi, YHi, HH);
      
      -- Dx := |XL - XH| , Cx := Borrow (i.e. 1 iff XL < XH)
      FZ_Sub_Abs(X => XLo, Y => XHi, Difference => Dx, Underflow => Cx);
      
      -- Dy := |YL - YH| , Cy := Borrow (i.e. 1 iff YL < YH)
      FZ_Sub_Abs(X => YLo, Y => YHi, Difference => Dy, Underflow => Cy);
      
      -- Recurse: DD := Dx * Dy
      FZ_Multiply(Dx, Dy, DD);
      
      -- Whether (XL - XH)(YL - YH) is positive, and so DD must be subtracted:
      DD_Sub := 1 - (Cx xor Cy);
      
      -- XY := LL + 2^(2 * K * Bitness) * HH
      XYLo := LL;
      XYHi := HH;
      
      -- XY += 2^(K * Bitness) * HH, but carry goes in Tail Carry accum.
      FZ_Add_D(X => XYMid, Y => HH, Overflow => TC);
      
      -- XY += 2^(K * Bitness) * LL, ...
      FZ_Add_D(X => XYMid, Y => LL, Overflow => C);
      
      -- ... but the carry goes into the Tail Carry accumulator.
      TC := TC + C;
      
      -- XY += 2^(K * Bitness) * (-1^DD_Sub) * DD
      FZ_Not_Cond_D(N => DD, Cond => DD_Sub); -- invert DD if 2s-complementing
      FZ_Add_D(OF_In    => DD_Sub,            -- ... and then must increment
               X        => XYMid,
               Y        => DD,
               Overflow => C); -- carry will go in Tail Carry accumulator
      
      -- Compute the final Tail Carry for the ripple
      TC := TC + C - DD_Sub;
      
      -- Barring a cosmic ray, 0 <= TC <= 2 .
      pragma Assert(TC <= 2);
      
      -- Ripple the Tail Carry into the tail.
      FZ_Add_D_W(X => XYHiHi, W => TC, Overflow => C);
      
      -- Barring a cosmic ray, the tail ripple will NOT overflow.
      pragma Assert(C = 0);

   end Mul_Karatsuba;
   -- CAUTION: Inlining prohibited for Mul_Karatsuba !
   
   
   -- Multiplier. (CAUTION: UNBUFFERED)
   procedure FZ_Multiply(X     : in  FZ;
                         Y     : in  FZ;
                         XY    : out FZ) is
      
      -- The length of either multiplicand
      L : constant Word_Count := X'Length;
      
   begin
      
      if L <= Karatsuba_Thresh then
         
         -- Base case:
         FZ_Mul_Comba(X, Y, XY);
         
      else
         
         -- Recursive case:
         Mul_Karatsuba(X, Y, XY);
         
      end if;
      
   end FZ_Multiply;
   pragma Inline_Always(FZ_Multiply);
   
   
   -- Multiplier. Preserves the inputs.
   procedure FZ_Mult(X     : in  FZ;
                     Y     : in  FZ;
                     XY_Lo : out FZ;
                     XY_Hi : out FZ) is
      
      -- Product buffer.
      P : FZ(1 .. 2 * X'Length);
      
   begin
      
      FZ_Multiply(X, Y, P);
      
      XY_Lo := P(P'First            .. P'First + X'Length - 1);
      XY_Hi := P(P'First + X'Length .. P'Last);
      
   end FZ_Mult;
   pragma Inline_Always(FZ_Mult);
   
end FZ_Mul;