Finite Field Arithmetic

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    
  73    -- Exactly same thing as IDiv, but keep only the Quotient
  74    procedure FZ_Div(Dividend  : in  FZ;
  75                     Divisor   : in  FZ;
  76                     Quotient  : out FZ) is
  77       Remainder : FZ(Divisor'Range);
  78       pragma Unreferenced(Remainder);
  79    begin
  80       FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
  81    end FZ_Div;
  82    
  83    
  84    -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
  85    procedure FZ_Mod(Dividend  : in FZ;
  86                     Divisor   : in FZ;
  87                     Remainder : out FZ) is
  88       
  89       -- Length of Divisor and Remainder; <= Dividend'Length
  90       L : constant Indices := Divisor'Length;
  91       
  92       -- Remainder register, starts as zero
  93       R : FZ(1 .. L) := (others => 0);
  94       
  95       -- Indices into the words of Dividend
  96       subtype Dividend_Index is Word_Index range Dividend'Range;
  97       
  98       -- Permissible 'cuts' for the Slice operation
  99       subtype Divisor_Cuts   is Word_Index range 2 .. Divisor'Length;
 100       
 101       -- Performs Restoring Division on a given segment of Dividend:Divisor
 102       procedure Slice(Index : Dividend_Index;
 103                       Cut   : Divisor_Cuts) is
 104          
 105          -- Borrow, from comparator
 106          C   : WBool;
 107          
 108          -- Left-Shift Overflow
 109          LsO : WBool;
 110          
 111          -- Current cut of Remainder register
 112          Rs  : FZ renames R(1 .. Cut);
 113          
 114          -- Current cut of Divisor
 115          Ds  : FZ renames Divisor(1 .. Cut);
 116          
 117          -- Current word of Dividend, starting from the highest
 118          W   : Word  := Dividend(Dividend'Last + 1 - Index);
 119          
 120       begin
 121          
 122          -- For each bit in the current Dividend word:
 123          for b in 1 .. Bitness loop
 124             
 125             -- Send top bit of current Dividend word to the bottom of W
 126             W := Rotate_Left(W, 1);
 127             
 128             -- Advance Rs, shifting in the current Dividend bit
 129             FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
 130                              OF_In => W and 1,
 131                              Overflow => LsO);
 132             
 133             -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
 134             FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
 135             
 136             -- If C=1, subtraction underflowed, and we must undo it:
 137             FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
 138                          Gate => C and W_Not(LsO));
 139             
 140          end loop;
 141          
 142       end Slice;
 143       
 144    begin
 145       
 146       -- Process bottom half of dividend:
 147       for i in 1 .. L - 1 loop
 148          
 149          Slice(i, i + 1); -- stay ahead by a word to handle carry
 150          
 151       end loop;
 152       
 153       -- Process top half of dividend
 154       for i in L .. Dividend'Length loop
 155          
 156          Slice(i, L);
 157          
 158       end loop;
 159       
 160       -- Output the Remainder.
 161       Remainder := R;
 162       
 163    end FZ_Mod;
 164    
 165 end FZ_Divis;