raw
ffa_ch1_genesis.kv      1 ------------------------------------------------------------------------------
ffa_ch1_genesis.kv      2 ------------------------------------------------------------------------------
ffa_ch1_genesis.kv      3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch1_genesis.kv      4 --                                                                          --
ffa_ch15_gcd.kv         5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch1_genesis.kv      6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch1_genesis.kv      7 --                                                                          --
ffa_ch1_genesis.kv      8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch1_genesis.kv      9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch1_genesis.kv     10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch1_genesis.kv     11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch1_genesis.kv     12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch1_genesis.kv     13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch1_genesis.kv     14 -- that you use - for any purpose.                                          --
ffa_ch1_genesis.kv     15 --                                                                          --
ffa_ch1_genesis.kv     16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch1_genesis.kv     17 ------------------------------------------------------------------------------
ffa_ch1_genesis.kv     18 ------------------------------------------------------------------------------
ffa_ch1_genesis.kv     19 
ffa_ch1_genesis.kv     20 with Word_Ops; use Word_Ops;
ffa_ch1_genesis.kv     21 
ffa_ch10_karatsub...   22 
ffa_ch1_genesis.kv     23 -- Fundamental Arithmetic operators on FZ:
ffa_ch1_genesis.kv     24 package body FZ_Arith is
ffa_ch1_genesis.kv     25    
ffa_ch10_karatsub...   26    -- Destructive Add: X := X + Y; Overflow := Carry; optional OF_In
ffa_ch10_karatsub...   27    procedure FZ_Add_D(X          : in out FZ;
ffa_ch10_karatsub...   28                       Y          : in     FZ;
ffa_ch10_karatsub...   29                       Overflow   : out    WBool;
ffa_ch10_karatsub...   30                       OF_In      : in     WBool := 0) is
ffa_ch10_karatsub...   31       Carry : WBool := OF_In;
ffa_ch10_karatsub...   32    begin
ffa_ch10_karatsub...   33       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch10_karatsub...   34          declare
ffa_ch10_karatsub...   35             A : constant Word := X(X'First + i);
ffa_ch10_karatsub...   36             B : constant Word := Y(Y'First + i);
ffa_ch10_karatsub...   37             S : constant Word := A + B + Carry;
ffa_ch10_karatsub...   38          begin
ffa_ch10_karatsub...   39             X(X'First + i) := S;
ffa_ch10_karatsub...   40             Carry          := W_Carry(A, B, S);
ffa_ch10_karatsub...   41          end;
ffa_ch10_karatsub...   42       end loop;
ffa_ch10_karatsub...   43       Overflow := Carry;
ffa_ch10_karatsub...   44    end FZ_Add_D;
ffa_ch10_karatsub...   45    
ffa_ch10_karatsub...   46    
ffa_ch10_karatsub...   47    -- Destructive Add: X := X + W; Overflow := Carry
ffa_ch10_karatsub...   48    procedure FZ_Add_D_W(X        : in out FZ;
ffa_ch10_karatsub...   49                         W        : in     Word;
ffa_ch10_karatsub...   50                         Overflow : out    WBool) is
ffa_ch10_karatsub...   51       Carry : Word := W;
ffa_ch10_karatsub...   52    begin
ffa_ch10_karatsub...   53       for i in X'Range loop
ffa_ch10_karatsub...   54          declare
ffa_ch10_karatsub...   55             A : constant Word := X(I);
ffa_ch10_karatsub...   56             S : constant Word := A + Carry;
ffa_ch10_karatsub...   57          begin
ffa_ch10_karatsub...   58             X(i)  := S;
ffa_ch10_karatsub...   59             Carry := W_Carry(A, 0, S);
ffa_ch10_karatsub...   60          end;
ffa_ch10_karatsub...   61       end loop;
ffa_ch10_karatsub...   62       Overflow := Carry;
ffa_ch10_karatsub...   63    end FZ_Add_D_W;
ffa_ch10_karatsub...   64 
ffa_ch10_karatsub...   65    
ffa_ch1_genesis.kv     66    -- Sum := X + Y; Overflow := Carry
ffa_ch1_genesis.kv     67    procedure FZ_Add(X          : in  FZ;
ffa_ch1_genesis.kv     68                     Y          : in  FZ;
ffa_ch1_genesis.kv     69                     Sum        : out FZ;
ffa_ch1_genesis.kv     70                     Overflow   : out WBool) is
ffa_ch1_genesis.kv     71       Carry : WBool := 0;
ffa_ch1_genesis.kv     72    begin
ffa_ch10_karatsub...   73       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch1_genesis.kv     74          declare
ffa_ch10_karatsub...   75             A : constant Word := X(X'First + i);
ffa_ch10_karatsub...   76             B : constant Word := Y(Y'First + i);
ffa_ch1_genesis.kv     77             S : constant Word := A + B + Carry;
ffa_ch1_genesis.kv     78          begin
ffa_ch10_karatsub...   79             Sum(Sum'First + i) := S;
ffa_ch1_genesis.kv     80             Carry  := W_Carry(A, B, S);
ffa_ch1_genesis.kv     81          end;
ffa_ch1_genesis.kv     82       end loop;
ffa_ch1_genesis.kv     83       Overflow := Carry;
ffa_ch1_genesis.kv     84    end FZ_Add;
ffa_ch1_genesis.kv     85    
ffa_ch1_genesis.kv     86    
ffa_ch5_egypt.kv       87    -- Gate = 1: Sum := X + Y; Overflow := Carry
ffa_ch5_egypt.kv       88    -- Gate = 0: Sum := X;     Overflow := 0
ffa_ch5_egypt.kv       89    procedure FZ_Add_Gated_O(X          : in  FZ;
ffa_ch5_egypt.kv       90                             Y          : in  FZ;
ffa_ch5_egypt.kv       91                             Gate       : in  WBool;
ffa_ch5_egypt.kv       92                             Sum        : out FZ;
ffa_ch5_egypt.kv       93                             Overflow   : out WBool) is
ffa_ch5_egypt.kv       94       Carry : WBool := 0;
ffa_ch5_egypt.kv       95       Mask  : constant Word := 0 - Gate;
ffa_ch5_egypt.kv       96    begin
ffa_ch5_egypt.kv       97       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch5_egypt.kv       98          declare
ffa_ch5_egypt.kv       99             A : constant Word := X(X'First + i);
ffa_ch5_egypt.kv      100             B : constant Word := Y(Y'First + i) and Mask;
ffa_ch5_egypt.kv      101             S : constant Word := A + B + Carry;
ffa_ch5_egypt.kv      102          begin
ffa_ch5_egypt.kv      103             Sum(Sum'First + i) := S;
ffa_ch5_egypt.kv      104             Carry  := W_Carry(A, B, S);
ffa_ch5_egypt.kv      105          end;
ffa_ch5_egypt.kv      106       end loop;
ffa_ch5_egypt.kv      107       Overflow := Carry;
ffa_ch5_egypt.kv      108    end FZ_Add_Gated_O;
ffa_ch5_egypt.kv      109    
ffa_ch5_egypt.kv      110    
ffa_ch5_egypt.kv      111    -- Same as FZ_Add_Gated_O, but without Overflow output
ffa_ch5_egypt.kv      112    procedure FZ_Add_Gated(X          : in  FZ;
ffa_ch5_egypt.kv      113                           Y          : in  FZ;
ffa_ch5_egypt.kv      114                           Gate       : in  WBool;
ffa_ch5_egypt.kv      115                           Sum        : out FZ) is
ffa_ch5_egypt.kv      116       Overflow : Word;
ffa_ch5_egypt.kv      117       pragma Unreferenced(Overflow);
ffa_ch5_egypt.kv      118    begin
ffa_ch5_egypt.kv      119       FZ_Add_Gated_O(X, Y, Gate, Sum, Overflow);
ffa_ch5_egypt.kv      120    end FZ_Add_Gated;
ffa_ch5_egypt.kv      121    
ffa_ch5_egypt.kv      122    
ffa_ch12_karatsub...  123    -- Destructive Sub: X := X - Y; Underflow := Borrow
ffa_ch12_karatsub...  124    procedure FZ_Sub_D(X          : in out FZ;
ffa_ch12_karatsub...  125                       Y          : in     FZ;
ffa_ch12_karatsub...  126                       Underflow  : out    WBool) is
ffa_ch12_karatsub...  127       Borrow : WBool := 0;
ffa_ch12_karatsub...  128    begin
ffa_ch12_karatsub...  129       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch12_karatsub...  130          declare
ffa_ch12_karatsub...  131             A : constant Word := X(X'First + i);
ffa_ch12_karatsub...  132             B : constant Word := Y(Y'First + i);
ffa_ch12_karatsub...  133             S : constant Word := A - B - Borrow;
ffa_ch12_karatsub...  134          begin
ffa_ch12_karatsub...  135             X(X'First + i) := S;
ffa_ch12_karatsub...  136             Borrow         := W_Borrow(A, B, S);
ffa_ch12_karatsub...  137          end;
ffa_ch12_karatsub...  138       end loop;
ffa_ch12_karatsub...  139       Underflow := Borrow;
ffa_ch12_karatsub...  140    end FZ_Sub_D;
ffa_ch12_karatsub...  141    
ffa_ch12_karatsub...  142    
ffa_ch1_genesis.kv    143    -- Difference := X - Y; Underflow := Borrow
ffa_ch1_genesis.kv    144    procedure FZ_Sub(X          : in  FZ;
ffa_ch1_genesis.kv    145                     Y          : in  FZ;
ffa_ch1_genesis.kv    146                     Difference : out FZ;
ffa_ch1_genesis.kv    147                     Underflow  : out WBool) is
ffa_ch1_genesis.kv    148       Borrow : WBool := 0;
ffa_ch1_genesis.kv    149    begin
ffa_ch1_genesis.kv    150       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch1_genesis.kv    151          declare
ffa_ch1_genesis.kv    152             A : constant Word := X(X'First + i);
ffa_ch1_genesis.kv    153             B : constant Word := Y(Y'First + i);
ffa_ch1_genesis.kv    154             S : constant Word := A - B - Borrow;
ffa_ch1_genesis.kv    155          begin
ffa_ch1_genesis.kv    156             Difference(Difference'First + i) := S;
ffa_ch1_genesis.kv    157             Borrow := W_Borrow(A, B, S);
ffa_ch1_genesis.kv    158          end;
ffa_ch1_genesis.kv    159       end loop;
ffa_ch1_genesis.kv    160       Underflow := Borrow;
ffa_ch1_genesis.kv    161    end FZ_Sub;
ffa_ch1_genesis.kv    162    
ffa_ch10_karatsub...  163    
ffa_ch16_miller_r...  164    -- Difference := X - W; Underflow := Borrow
ffa_ch16_miller_r...  165    procedure FZ_Sub_W(X          : in  FZ;
ffa_ch16_miller_r...  166                       W          : in  Word;
ffa_ch16_miller_r...  167                       Difference : out FZ;
ffa_ch16_miller_r...  168                       Underflow  : out WBool) is
ffa_ch16_miller_r...  169       Borrow : Word := W;
ffa_ch16_miller_r...  170    begin
ffa_ch16_miller_r...  171       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch16_miller_r...  172          declare
ffa_ch16_miller_r...  173             A : constant Word := X(X'First + i);
ffa_ch16_miller_r...  174             S : constant Word := A - Borrow;
ffa_ch16_miller_r...  175          begin
ffa_ch16_miller_r...  176             Difference(Difference'First + i) := S;
ffa_ch16_miller_r...  177             Borrow := W_Borrow(A, 0, S);
ffa_ch16_miller_r...  178          end;
ffa_ch16_miller_r...  179       end loop;
ffa_ch16_miller_r...  180       Underflow := Borrow;
ffa_ch16_miller_r...  181    end FZ_Sub_W;
ffa_ch16_miller_r...  182    
ffa_ch16_miller_r...  183    
ffa_ch10_karatsub...  184    -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
ffa_ch10_karatsub...  185    procedure FZ_Not_Cond_D(N    : in out FZ;
ffa_ch10_karatsub...  186                            Cond : in     WBool)is
ffa_ch10_karatsub...  187       
ffa_ch10_karatsub...  188       -- The inversion mask
ffa_ch10_karatsub...  189       Inv : constant Word := 0 - Cond;
ffa_ch10_karatsub...  190       
ffa_ch10_karatsub...  191    begin
ffa_ch10_karatsub...  192       
ffa_ch10_karatsub...  193       for i in N'Range loop
ffa_ch10_karatsub...  194          
ffa_ch10_karatsub...  195          -- Invert (or, if Cond is 0, do nothing)
ffa_ch10_karatsub...  196          N(i) := N(i) xor Inv;
ffa_ch10_karatsub...  197          
ffa_ch10_karatsub...  198       end loop;
ffa_ch10_karatsub...  199       
ffa_ch10_karatsub...  200    end FZ_Not_Cond_D;
ffa_ch10_karatsub...  201    
ffa_ch10_karatsub...  202    
ffa_ch10_karatsub...  203    -- Subtractor that gets absolute value if underflowed, in const. time
ffa_ch10_karatsub...  204    procedure FZ_Sub_Abs(X          : in FZ;
ffa_ch10_karatsub...  205                         Y          : in FZ;
ffa_ch10_karatsub...  206                         Difference : out FZ;
ffa_ch10_karatsub...  207                         Underflow  : out WBool) is
ffa_ch10_karatsub...  208       
ffa_ch10_karatsub...  209       O : Word := 0;
ffa_ch10_karatsub...  210       pragma Unreferenced(O);
ffa_ch10_karatsub...  211       
ffa_ch10_karatsub...  212    begin
ffa_ch10_karatsub...  213       
ffa_ch10_karatsub...  214       -- First, we subtract normally
ffa_ch10_karatsub...  215       FZ_Sub(X, Y, Difference, Underflow);
ffa_ch10_karatsub...  216       
ffa_ch10_karatsub...  217       -- If borrow - negate,
ffa_ch10_karatsub...  218       FZ_Not_Cond_D(Difference, Underflow);
ffa_ch10_karatsub...  219       
ffa_ch10_karatsub...  220       -- ... and also increment.
ffa_ch10_karatsub...  221       FZ_Add_D_W(Difference, Underflow, O);
ffa_ch10_karatsub...  222       
ffa_ch10_karatsub...  223    end FZ_Sub_Abs;
ffa_ch10_karatsub...  224    
ffa_ch10_karatsub...  225    
ffa_ch1_genesis.kv    226 end FZ_Arith;