ffa_ch10_karatsuba.kv

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_ch1_genesis.kv      5 -- (C) 2017 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    pragma Inline_Always(FZ_Add_D);
ffa_ch10_karatsub...   46    
ffa_ch10_karatsub...   47    
ffa_ch10_karatsub...   48    -- Destructive Add: X := X + W; Overflow := Carry
ffa_ch10_karatsub...   49    procedure FZ_Add_D_W(X        : in out FZ;
ffa_ch10_karatsub...   50                         W        : in     Word;
ffa_ch10_karatsub...   51                         Overflow : out    WBool) is
ffa_ch10_karatsub...   52       Carry : Word := W;
ffa_ch10_karatsub...   53    begin
ffa_ch10_karatsub...   54       for i in X'Range loop
ffa_ch10_karatsub...   55          declare
ffa_ch10_karatsub...   56             A : constant Word := X(I);
ffa_ch10_karatsub...   57             S : constant Word := A + Carry;
ffa_ch10_karatsub...   58          begin
ffa_ch10_karatsub...   59             X(i)  := S;
ffa_ch10_karatsub...   60             Carry := W_Carry(A, 0, S);
ffa_ch10_karatsub...   61          end;
ffa_ch10_karatsub...   62       end loop;
ffa_ch10_karatsub...   63       Overflow := Carry;
ffa_ch10_karatsub...   64    end FZ_Add_D_W;
ffa_ch10_karatsub...   65    pragma Inline_Always(FZ_Add_D_W);
ffa_ch10_karatsub...   66 
ffa_ch10_karatsub...   67    
ffa_ch1_genesis.kv     68    -- Sum := X + Y; Overflow := Carry
ffa_ch1_genesis.kv     69    procedure FZ_Add(X          : in  FZ;
ffa_ch1_genesis.kv     70                     Y          : in  FZ;
ffa_ch1_genesis.kv     71                     Sum        : out FZ;
ffa_ch1_genesis.kv     72                     Overflow   : out WBool) is
ffa_ch1_genesis.kv     73       Carry : WBool := 0;
ffa_ch1_genesis.kv     74    begin
ffa_ch10_karatsub...   75       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch1_genesis.kv     76          declare
ffa_ch10_karatsub...   77             A : constant Word := X(X'First + i);
ffa_ch10_karatsub...   78             B : constant Word := Y(Y'First + i);
ffa_ch1_genesis.kv     79             S : constant Word := A + B + Carry;
ffa_ch1_genesis.kv     80          begin
ffa_ch10_karatsub...   81             Sum(Sum'First + i) := S;
ffa_ch1_genesis.kv     82             Carry  := W_Carry(A, B, S);
ffa_ch1_genesis.kv     83          end;
ffa_ch1_genesis.kv     84       end loop;
ffa_ch1_genesis.kv     85       Overflow := Carry;
ffa_ch1_genesis.kv     86    end FZ_Add;
ffa_ch1_genesis.kv     87    pragma Inline_Always(FZ_Add);
ffa_ch1_genesis.kv     88    
ffa_ch1_genesis.kv     89    
ffa_ch5_egypt.kv       90    -- Gate = 1: Sum := X + Y; Overflow := Carry
ffa_ch5_egypt.kv       91    -- Gate = 0: Sum := X;     Overflow := 0
ffa_ch5_egypt.kv       92    procedure FZ_Add_Gated_O(X          : in  FZ;
ffa_ch5_egypt.kv       93                             Y          : in  FZ;
ffa_ch5_egypt.kv       94                             Gate       : in  WBool;
ffa_ch5_egypt.kv       95                             Sum        : out FZ;
ffa_ch5_egypt.kv       96                             Overflow   : out WBool) is
ffa_ch5_egypt.kv       97       Carry : WBool := 0;
ffa_ch5_egypt.kv       98       Mask  : constant Word := 0 - Gate;
ffa_ch5_egypt.kv       99    begin
ffa_ch5_egypt.kv      100       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch5_egypt.kv      101          declare
ffa_ch5_egypt.kv      102             A : constant Word := X(X'First + i);
ffa_ch5_egypt.kv      103             B : constant Word := Y(Y'First + i) and Mask;
ffa_ch5_egypt.kv      104             S : constant Word := A + B + Carry;
ffa_ch5_egypt.kv      105          begin
ffa_ch5_egypt.kv      106             Sum(Sum'First + i) := S;
ffa_ch5_egypt.kv      107             Carry  := W_Carry(A, B, S);
ffa_ch5_egypt.kv      108          end;
ffa_ch5_egypt.kv      109       end loop;
ffa_ch5_egypt.kv      110       Overflow := Carry;
ffa_ch5_egypt.kv      111    end FZ_Add_Gated_O;
ffa_ch5_egypt.kv      112    pragma Inline_Always(FZ_Add_Gated_O);
ffa_ch5_egypt.kv      113    
ffa_ch5_egypt.kv      114    
ffa_ch5_egypt.kv      115    -- Same as FZ_Add_Gated_O, but without Overflow output
ffa_ch5_egypt.kv      116    procedure FZ_Add_Gated(X          : in  FZ;
ffa_ch5_egypt.kv      117                           Y          : in  FZ;
ffa_ch5_egypt.kv      118                           Gate       : in  WBool;
ffa_ch5_egypt.kv      119                           Sum        : out FZ) is
ffa_ch5_egypt.kv      120       Overflow : Word;
ffa_ch5_egypt.kv      121       pragma Unreferenced(Overflow);
ffa_ch5_egypt.kv      122    begin
ffa_ch5_egypt.kv      123       FZ_Add_Gated_O(X, Y, Gate, Sum, Overflow);
ffa_ch5_egypt.kv      124    end FZ_Add_Gated;
ffa_ch5_egypt.kv      125    pragma Inline_Always(FZ_Add_Gated);
ffa_ch5_egypt.kv      126    
ffa_ch5_egypt.kv      127    
ffa_ch1_genesis.kv    128    -- Difference := X - Y; Underflow := Borrow
ffa_ch1_genesis.kv    129    procedure FZ_Sub(X          : in  FZ;
ffa_ch1_genesis.kv    130                     Y          : in  FZ;
ffa_ch1_genesis.kv    131                     Difference : out FZ;
ffa_ch1_genesis.kv    132                     Underflow  : out WBool) is
ffa_ch1_genesis.kv    133       Borrow : WBool := 0;
ffa_ch1_genesis.kv    134    begin
ffa_ch1_genesis.kv    135       for i in 0 .. Word_Index(X'Length - 1) loop
ffa_ch1_genesis.kv    136          declare
ffa_ch1_genesis.kv    137             A : constant Word := X(X'First + i);
ffa_ch1_genesis.kv    138             B : constant Word := Y(Y'First + i);
ffa_ch1_genesis.kv    139             S : constant Word := A - B - Borrow;
ffa_ch1_genesis.kv    140          begin
ffa_ch1_genesis.kv    141             Difference(Difference'First + i) := S;
ffa_ch1_genesis.kv    142             Borrow := W_Borrow(A, B, S);
ffa_ch1_genesis.kv    143          end;
ffa_ch1_genesis.kv    144       end loop;
ffa_ch1_genesis.kv    145       Underflow := Borrow;
ffa_ch1_genesis.kv    146    end FZ_Sub;
ffa_ch1_genesis.kv    147    pragma Inline_Always(FZ_Sub);
ffa_ch1_genesis.kv    148    
ffa_ch10_karatsub...  149    
ffa_ch10_karatsub...  150    -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
ffa_ch10_karatsub...  151    procedure FZ_Not_Cond_D(N    : in out FZ;
ffa_ch10_karatsub...  152                            Cond : in     WBool)is
ffa_ch10_karatsub...  153       
ffa_ch10_karatsub...  154       -- The inversion mask
ffa_ch10_karatsub...  155       Inv : constant Word := 0 - Cond;
ffa_ch10_karatsub...  156       
ffa_ch10_karatsub...  157    begin
ffa_ch10_karatsub...  158       
ffa_ch10_karatsub...  159       for i in N'Range loop
ffa_ch10_karatsub...  160          
ffa_ch10_karatsub...  161          -- Invert (or, if Cond is 0, do nothing)
ffa_ch10_karatsub...  162          N(i) := N(i) xor Inv;
ffa_ch10_karatsub...  163          
ffa_ch10_karatsub...  164       end loop;
ffa_ch10_karatsub...  165       
ffa_ch10_karatsub...  166    end FZ_Not_Cond_D;
ffa_ch10_karatsub...  167    pragma Inline_Always(FZ_Not_Cond_D);
ffa_ch10_karatsub...  168    
ffa_ch10_karatsub...  169    
ffa_ch10_karatsub...  170    -- Subtractor that gets absolute value if underflowed, in const. time
ffa_ch10_karatsub...  171    procedure FZ_Sub_Abs(X          : in FZ;
ffa_ch10_karatsub...  172                         Y          : in FZ;
ffa_ch10_karatsub...  173                         Difference : out FZ;
ffa_ch10_karatsub...  174                         Underflow  : out WBool) is
ffa_ch10_karatsub...  175       
ffa_ch10_karatsub...  176       O : Word := 0;
ffa_ch10_karatsub...  177       pragma Unreferenced(O);
ffa_ch10_karatsub...  178       
ffa_ch10_karatsub...  179    begin
ffa_ch10_karatsub...  180       
ffa_ch10_karatsub...  181       -- First, we subtract normally
ffa_ch10_karatsub...  182       FZ_Sub(X, Y, Difference, Underflow);
ffa_ch10_karatsub...  183       
ffa_ch10_karatsub...  184       -- If borrow - negate,
ffa_ch10_karatsub...  185       FZ_Not_Cond_D(Difference, Underflow);
ffa_ch10_karatsub...  186       
ffa_ch10_karatsub...  187       -- ... and also increment.
ffa_ch10_karatsub...  188       FZ_Add_D_W(Difference, Underflow, O);
ffa_ch10_karatsub...  189       
ffa_ch10_karatsub...  190    end FZ_Sub_Abs;
ffa_ch10_karatsub...  191    pragma Inline_Always(FZ_Sub_Abs);
ffa_ch10_karatsub...  192    
ffa_ch10_karatsub...  193    
ffa_ch1_genesis.kv    194 end FZ_Arith;