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