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;