File : fz_divis.adb


   1 ------------------------------------------------------------------------------
   2 ------------------------------------------------------------------------------
   3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
   4 --                                                                          --
   5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
   6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
   7 --                                                                          --
   8 -- You do not have, nor can you ever acquire the right to use, copy or      --
   9 -- distribute this software ; Should you use this software for any purpose, --
  10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
  11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
  12 -- continue doing so for the indefinite future. In any case, please         --
  13 -- always : read and understand any software ; verify any PGP signatures    --
  14 -- that you use - for any purpose.                                          --
  15 --                                                                          --
  16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
  17 ------------------------------------------------------------------------------
  18 ------------------------------------------------------------------------------
  19 
  20 with Words;    use Words;
  21 with W_Pred;   use W_Pred;
  22 with W_Shifts; use W_Shifts;
  23 with FZ_Basic; use FZ_Basic;
  24 with FZ_Arith; use FZ_Arith;
  25 with FZ_BitOp; use FZ_BitOp;
  26 with FZ_Shift; use FZ_Shift;
  27 
  28 
  29 package body FZ_Divis is
  30    
  31    -- Dividend is divided by Divisor, producing Quotient and Remainder.
  32    -- WARNING: NO div0 test here! Caller must test.
  33    procedure FZ_IDiv(Dividend  : in  FZ;
  34                      Divisor   : in  FZ;
  35                      Quotient  : out FZ;
  36                      Remainder : out FZ) is
  37       
  38       -- The working register
  39       QR : FZ(1 .. Dividend'Length + Divisor'Length);
  40       
  41       -- Bottom seg of Z will end up containing the Quotient; top - remainder
  42       Q  : FZ renames QR(1                   .. Dividend'Length); -- Quotient
  43       R  : FZ renames QR(Dividend'Length + 1 .. QR'Last);          -- Remainder
  44       
  45       C : WBool := 0; -- Borrow, from comparator
  46    begin
  47       Q := Dividend; -- Q begins with the Dividend
  48       FZ_Clear(R);   -- R begins empty
  49       
  50       -- For each bit of Dividend:
  51       for i in 1 .. FZ_Bitness(Dividend) loop
  52          
  53          -- Advance QR by 1 bit:
  54          FZ_ShiftLeft(QR, QR, 1);
  55          
  56          -- Subtract Divisor from R; Underflow goes into C
  57          FZ_Sub(X => R, Y => Divisor, Difference => R, Underflow => C);
  58          
  59          -- If C=1, subtraction underflowed, and then Divisor gets added back:
  60          FZ_Add_Gated(X => R, Y => Divisor, Gate => C, Sum => R);
  61          
  62          -- Current result-bit is equal to Not-C, i.e. 1 if Divisor 'went in'
  63          FZ_Or_W(Q, W_Not(C));
  64          
  65       end loop;
  66       
  67       Quotient  := Q; -- Output the Quotient.
  68       Remainder := R; -- Output the Remainder.
  69       
  70    end FZ_IDiv;
  71    
  72    -- Exactly same thing as IDiv, but keep only the Quotient
  73    procedure FZ_Div(Dividend  : in  FZ;
  74                     Divisor   : in  FZ;
  75                     Quotient  : out FZ) is
  76       Remainder : FZ(Divisor'Range);
  77       pragma Unreferenced(Remainder);
  78    begin
  79       FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
  80    end FZ_Div;
  81    
  82    -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
  83    procedure FZ_Mod(Dividend  : in FZ;
  84                     Divisor   : in FZ;
  85                     Remainder : out FZ) is
  86       
  87       -- Length of Divisor and Remainder; <= Dividend'Length
  88       L : constant Indices := Divisor'Length;
  89       
  90       -- Remainder register, starts as zero
  91       R : FZ(1 .. L) := (others => 0);
  92       
  93       -- Indices into the words of Dividend
  94       subtype Dividend_Index is Word_Index range Dividend'Range;
  95       
  96       -- Permissible 'cuts' for the Slice operation
  97       subtype Divisor_Cuts   is Word_Index range 2 .. Divisor'Length;
  98       
  99       -- Performs Restoring Division on a given segment of Dividend:Divisor
 100       procedure Slice(Index : Dividend_Index;
 101                       Cut   : Divisor_Cuts) is
 102       begin
 103          
 104          declare
 105             
 106             -- Borrow, from comparator
 107             C   : WBool;
 108             
 109             -- Left-Shift Overflow
 110             LsO : WBool;
 111             
 112             -- Current cut of Remainder register
 113             Rs  : FZ renames R(1 .. Cut);
 114             
 115             -- Current cut of Divisor
 116             Ds  : FZ renames Divisor(1 .. Cut);
 117             
 118             -- Current word of Dividend, starting from the highest
 119             W   : Word  := Dividend(Dividend'Last + 1 - Index);
 120             
 121          begin
 122             
 123             -- For each bit in the current Dividend word:
 124             for b in 1 .. Bitness loop
 125                
 126                -- Send top bit of current Dividend word to the bottom of W
 127                W := Rotate_Left(W, 1);
 128                
 129                -- Advance Rs, shifting in the current Dividend bit
 130                FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
 131                                 OF_In => W and 1,
 132                                 Overflow => LsO);
 133                
 134                -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
 135                FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
 136                
 137                -- If C=1, subtraction underflowed, and we must undo it:
 138                FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
 139                             Gate => C and W_Not(LsO));
 140                
 141             end loop;
 142             
 143          end;
 144          
 145       end Slice;
 146       
 147    begin
 148       
 149       -- Process bottom half of dividend:
 150       for i in 1 .. L - 1 loop
 151          
 152          Slice(i, i + 1); -- stay ahead by a word to handle carry
 153          
 154       end loop;
 155       
 156       -- Process top half of dividend
 157       for i in L .. Dividend'Length loop
 158          
 159          Slice(i, L);
 160          
 161       end loop;
 162       
 163       -- Output the Remainder.
 164       Remainder := R;
 165       
 166    end FZ_Mod;
 167    
 168 end FZ_Divis;