------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- 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 W_Shifts; use W_Shifts;
with FZ_Basic; use FZ_Basic;
with FZ_Arith; use FZ_Arith;
with FZ_Shift; use FZ_Shift;


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
      
      L : constant Indices := X'Length;
      
      -- Register holding running product
      XY : FZ(1 .. X'Length + Y'Length);
      
      -- X-Slide
      XS : FZ(1 .. X'Length + Y'Length);
      
   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;
         
      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);
      
   end FZ_Mul_Egyptian;
   pragma Inline_Always(FZ_Mul_Egyptian);

end FZ_Mul;