File : 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 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
165 procedure FZ_Not_Cond_D(N : in out FZ;
166 Cond : in WBool)is
167
168 -- The inversion mask
169 Inv : constant Word := 0 - Cond;
170
171 begin
172
173 for i in N'Range loop
174
175 -- Invert (or, if Cond is 0, do nothing)
176 N(i) := N(i) xor Inv;
177
178 end loop;
179
180 end FZ_Not_Cond_D;
181
182
183 -- Subtractor that gets absolute value if underflowed, in const. time
184 procedure FZ_Sub_Abs(X : in FZ;
185 Y : in FZ;
186 Difference : out FZ;
187 Underflow : out WBool) is
188
189 O : Word := 0;
190 pragma Unreferenced(O);
191
192 begin
193
194 -- First, we subtract normally
195 FZ_Sub(X, Y, Difference, Underflow);
196
197 -- If borrow - negate,
198 FZ_Not_Cond_D(Difference, Underflow);
199
200 -- ... and also increment.
201 FZ_Add_D_W(Difference, Underflow, O);
202
203 end FZ_Sub_Abs;
204
205
206 end FZ_Arith;