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


package body FZ_Divis is
   
   -- Dividend is divided by Divisor, producing Quotient and Remainder.
   -- WARNING: NO div0 test here! Caller must test.
   procedure FZ_IDiv(Dividend  : in  FZ;
                     Divisor   : in  FZ;
                     Quotient  : out FZ;
                     Remainder : out FZ) is
      
      -- The working register
      QR : FZ(1 .. Dividend'Length + Divisor'Length);
      
      -- Bottom seg of Z will end up containing the Quotient; top - remainder
      Q  : FZ renames QR(1                   .. Dividend'Length); -- Quotient
      R  : FZ renames QR(Dividend'Length + 1 .. QR'Last);          -- Remainder
      
      C : WBool := 0; -- Borrow, from comparator
   begin
      Q := Dividend; -- Q begins with the Dividend
      FZ_Clear(R);   -- R begins empty
      
      -- For each bit of Dividend:
      for i in 1 .. FZ_Bitness(Dividend) loop
         
         -- Advance QR by 1 bit:
         FZ_ShiftLeft(QR, QR, 1);
         
         -- Subtract Divisor from R; Underflow goes into C
         FZ_Sub(X => R, Y => Divisor, Difference => R, Underflow => C);
         
         -- If C=1, subtraction underflowed, and then Divisor gets added back:
         FZ_Add_Gated(X => R, Y => Divisor, Gate => C, Sum => R);
         
         -- Current result-bit is equal to Not-C, i.e. 1 if Divisor 'went in'
         FZ_Or_W(Q, W_Not(C));
         
      end loop;
      
      Quotient  := Q; -- Output the Quotient.
      Remainder := R; -- Output the Remainder.
      
   end FZ_IDiv;
   pragma Inline_Always(FZ_IDiv);
   
   
   -- Exactly same thing as IDiv, but keep only the Quotient
   procedure FZ_Div(Dividend  : in  FZ;
                    Divisor   : in  FZ;
                    Quotient  : out FZ) is
      Remainder : FZ(Divisor'Range);
      pragma Unreferenced(Remainder);
   begin
      FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
   end FZ_Div;
   pragma Inline_Always(FZ_Div);
   
   
   -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
   procedure FZ_Mod(Dividend  : in FZ;
                    Divisor   : in FZ;
                    Remainder : out FZ) is
      
      -- Length of Divisor and Remainder; <= Dividend'Length
      L : constant Indices := Divisor'Length;
      
      -- Remainder register, starts as zero
      R : FZ(1 .. L) := (others => 0);
      
      -- Indices into the words of Dividend
      subtype Dividend_Index is Word_Index range Dividend'Range;
      
      -- Permissible 'cuts' for the Slice operation
      subtype Divisor_Cuts   is Word_Index range 2 .. Divisor'Length;
      
      -- Performs Restoring Division on a given segment of Dividend:Divisor
      procedure Slice(Index : Dividend_Index;
                      Cut   : Divisor_Cuts) is
      begin
         
         declare
            
            -- Borrow, from comparator
            C   : WBool;
            
            -- Left-Shift Overflow
            LsO : WBool;
            
            -- Current cut of Remainder register
            Rs  : FZ renames R(1 .. Cut);
            
            -- Current cut of Divisor
            Ds  : FZ renames Divisor(1 .. Cut);
            
            -- Current word of Dividend, starting from the highest
            W   : Word  := Dividend(Dividend'Last + 1 - Index);
            
         begin
            
            -- For each bit in the current Dividend word:
            for b in 1 .. Bitness loop
               
               -- Send top bit of current Dividend word to the bottom of W
               W := Rotate_Left(W, 1);
               
               -- Advance Rs, shifting in the current Dividend bit
               FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
                                OF_In => W and 1,
                                Overflow => LsO);
               
               -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
               FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
               
               -- If C=1, subtraction underflowed, and we must undo it:
               FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
                            Gate => C and W_Not(LsO));
               
            end loop;
            
         end;
         
      end Slice;
      
   begin
      
      -- Process bottom half of dividend:
      for i in 1 .. L - 1 loop
         
         Slice(i, i + 1); -- stay ahead by a word to handle carry
         
      end loop;
      
      -- Process top half of dividend
      for i in L .. Dividend'Length loop
         
         Slice(i, L);
         
      end loop;
      
      -- Output the Remainder.
      Remainder := R;
      
   end FZ_Mod;
   pragma Inline_Always(FZ_Mod);
   
   
end FZ_Divis;