Finite Field Arithmetic

fz_arith.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 Word_Ops; use Word_Ops;
  21 
  22 
  23 -- Fundamental Arithmetic operators on FZ:
  24 package body FZ_Arith is
  25    
  26    -- Destructive Add: X := X + Y; Overflow := Carry; optional OF_In
  27    procedure FZ_Add_D(X          : in out FZ;
  28                       Y          : in     FZ;
  29                       Overflow   : out    WBool;
  30                       OF_In      : in     WBool := 0) is
  31       Carry : WBool := OF_In;
  32    begin
  33       for i in 0 .. Word_Index(X'Length - 1) loop
  34          declare
  35             A : constant Word := X(X'First + i);
  36             B : constant Word := Y(Y'First + i);
  37             S : constant Word := A + B + Carry;
  38          begin
  39             X(X'First + i) := S;
  40             Carry          := W_Carry(A, B, S);
  41          end;
  42       end loop;
  43       Overflow := Carry;
  44    end FZ_Add_D;
  45    
  46    
  47    -- Destructive Add: X := X + W; Overflow := Carry
  48    procedure FZ_Add_D_W(X        : in out FZ;
  49                         W        : in     Word;
  50                         Overflow : out    WBool) is
  51       Carry : Word := W;
  52    begin
  53       for i in X'Range loop
  54          declare
  55             A : constant Word := X(I);
  56             S : constant Word := A + Carry;
  57          begin
  58             X(i)  := S;
  59             Carry := W_Carry(A, 0, S);
  60          end;
  61       end loop;
  62       Overflow := Carry;
  63    end FZ_Add_D_W;
  64 
  65    
  66    -- Sum := X + Y; Overflow := Carry
  67    procedure FZ_Add(X          : in  FZ;
  68                     Y          : in  FZ;
  69                     Sum        : out FZ;
  70                     Overflow   : out WBool) is
  71       Carry : WBool := 0;
  72    begin
  73       for i in 0 .. Word_Index(X'Length - 1) loop
  74          declare
  75             A : constant Word := X(X'First + i);
  76             B : constant Word := Y(Y'First + i);
  77             S : constant Word := A + B + Carry;
  78          begin
  79             Sum(Sum'First + i) := S;
  80             Carry  := W_Carry(A, B, S);
  81          end;
  82       end loop;
  83       Overflow := Carry;
  84    end FZ_Add;
  85    
  86    
  87    -- Gate = 1: Sum := X + Y; Overflow := Carry
  88    -- Gate = 0: Sum := X;     Overflow := 0
  89    procedure FZ_Add_Gated_O(X          : in  FZ;
  90                             Y          : in  FZ;
  91                             Gate       : in  WBool;
  92                             Sum        : out FZ;
  93                             Overflow   : out WBool) is
  94       Carry : WBool := 0;
  95       Mask  : constant Word := 0 - Gate;
  96    begin
  97       for i in 0 .. Word_Index(X'Length - 1) loop
  98          declare
  99             A : constant Word := X(X'First + i);
 100             B : constant Word := Y(Y'First + i) and Mask;
 101             S : constant Word := A + B + Carry;
 102          begin
 103             Sum(Sum'First + i) := S;
 104             Carry  := W_Carry(A, B, S);
 105          end;
 106       end loop;
 107       Overflow := Carry;
 108    end FZ_Add_Gated_O;
 109    
 110    
 111    -- Same as FZ_Add_Gated_O, but without Overflow output
 112    procedure FZ_Add_Gated(X          : in  FZ;
 113                           Y          : in  FZ;
 114                           Gate       : in  WBool;
 115                           Sum        : out FZ) is
 116       Overflow : Word;
 117       pragma Unreferenced(Overflow);
 118    begin
 119       FZ_Add_Gated_O(X, Y, Gate, Sum, Overflow);
 120    end FZ_Add_Gated;
 121    
 122    
 123    -- Destructive Sub: X := X - Y; Underflow := Borrow
 124    procedure FZ_Sub_D(X          : in out FZ;
 125                       Y          : in     FZ;
 126                       Underflow  : out    WBool) is
 127       Borrow : WBool := 0;
 128    begin
 129       for i in 0 .. Word_Index(X'Length - 1) loop
 130          declare
 131             A : constant Word := X(X'First + i);
 132             B : constant Word := Y(Y'First + i);
 133             S : constant Word := A - B - Borrow;
 134          begin
 135             X(X'First + i) := S;
 136             Borrow         := W_Borrow(A, B, S);
 137          end;
 138       end loop;
 139       Underflow := Borrow;
 140    end FZ_Sub_D;
 141    
 142    
 143    -- Difference := X - Y; Underflow := Borrow
 144    procedure FZ_Sub(X          : in  FZ;
 145                     Y          : in  FZ;
 146                     Difference : out FZ;
 147                     Underflow  : out WBool) is
 148       Borrow : WBool := 0;
 149    begin
 150       for i in 0 .. Word_Index(X'Length - 1) loop
 151          declare
 152             A : constant Word := X(X'First + i);
 153             B : constant Word := Y(Y'First + i);
 154             S : constant Word := A - B - Borrow;
 155          begin
 156             Difference(Difference'First + i) := S;
 157             Borrow := W_Borrow(A, B, S);
 158          end;
 159       end loop;
 160       Underflow := Borrow;
 161    end FZ_Sub;
 162    
 163    
 164    -- Difference := X - W; Underflow := Borrow
 165    procedure FZ_Sub_W(X          : in  FZ;
 166                       W          : in  Word;
 167                       Difference : out FZ;
 168                       Underflow  : out WBool) is
 169       Borrow : Word := W;
 170    begin
 171       for i in 0 .. Word_Index(X'Length - 1) loop
 172          declare
 173             A : constant Word := X(X'First + i);
 174             S : constant Word := A - Borrow;
 175          begin
 176             Difference(Difference'First + i) := S;
 177             Borrow := W_Borrow(A, 0, S);
 178          end;
 179       end loop;
 180       Underflow := Borrow;
 181    end FZ_Sub_W;
 182    
 183    
 184    -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
 185    procedure FZ_Not_Cond_D(N    : in out FZ;
 186                            Cond : in     WBool)is
 187       
 188       -- The inversion mask
 189       Inv : constant Word := 0 - Cond;
 190       
 191    begin
 192       
 193       for i in N'Range loop
 194          
 195          -- Invert (or, if Cond is 0, do nothing)
 196          N(i) := N(i) xor Inv;
 197          
 198       end loop;
 199       
 200    end FZ_Not_Cond_D;
 201    
 202    
 203    -- Subtractor that gets absolute value if underflowed, in const. time
 204    procedure FZ_Sub_Abs(X          : in FZ;
 205                         Y          : in FZ;
 206                         Difference : out FZ;
 207                         Underflow  : out WBool) is
 208       
 209       O : Word := 0;
 210       pragma Unreferenced(O);
 211       
 212    begin
 213       
 214       -- First, we subtract normally
 215       FZ_Sub(X, Y, Difference, Underflow);
 216       
 217       -- If borrow - negate,
 218       FZ_Not_Cond_D(Difference, Underflow);
 219       
 220       -- ... and also increment.
 221       FZ_Add_D_W(Difference, Underflow, O);
 222       
 223    end FZ_Sub_Abs;
 224    
 225    
 226 end FZ_Arith;