tree checksum vpatch file split hunks
all signers: asciilifeform bvt diana_coman
antecedents: ffa_ch5_egypt.kv ffa_ch7_turbo_egyptians.kv ffa_ch8_randomism.kv
press order:
patch:
(380 . 11)(380 . 11)
5 -- Multiply, give bottom and top halves
6 when '*' =>
7 Want(2);
8 -- Ch5: slow and simple 'Egyptological' method:
9 FZ_Mul_Egyptian(X => Stack(SP - 1),
10 Y => Stack(SP),
11 XY_Lo => Stack(SP - 1),
12 XY_Hi => Stack(SP));
13 -- Ch9: Comba's algorithm
14 FZ_Mul_Comba(X => Stack(SP - 1),
15 Y => Stack(SP),
16 XY_Lo => Stack(SP - 1),
17 XY_Hi => Stack(SP));
18
19 -- Modular Multiplication
20 when 'M' =>
- 7DCF2EE0EFC97EA57C360131F2EE836775FE2D57195D454C655E74CD030E72AA6D3109E2736A04AAE0F305859DE52E29EDD38005B6249E0548950F1E91F36D4A(45 . 7)(45 . 7)
25 begin
26
27 -- XY_Lo:XY_Hi := X * Y
28 FZ_Mul_Egyptian(X, Y, XY_Lo, XY_Hi);
29 FZ_Mul_Comba(X, Y, XY_Lo, XY_Hi);
30
31 -- Product := XY mod M
32 FZ_Mod(XY, Modulus, Product);
- 20B94E2B0260DD90AEDA5E987C038348070FA29AFFF8FD41A84BDA53CF6BFC15638809387A6C9C44C6F9FCBDC28C5E5AFD7E1EFA43B0DA72F89B9C198F603670(18 . 71)(18 . 108)
37 ------------------------------------------------------------------------------
38
39 with Words; use Words;
40 with W_Shifts; use W_Shifts;
41 with FZ_Basic; use FZ_Basic;
42 with FZ_Arith; use FZ_Arith;
43 with FZ_Shift; use FZ_Shift;
44 with Word_Ops; use Word_Ops;
45 with W_Mul; use W_Mul;
46
47
48 package body FZ_Mul is
49
50 -- 'Egyptological' multiplier. XY_Lo and XY_Hi hold result of X*Y.
51 procedure FZ_Mul_Egyptian(X : in FZ;
52 Y : in FZ;
53 XY_Lo : out FZ;
54 XY_Hi : out FZ) is
55 -- Comba's multiplier.
56 procedure FZ_Mul_Comba(X : in FZ;
57 Y : in FZ;
58 XY_Lo : out FZ;
59 XY_Hi : out FZ) is
60
61 L : constant Indices := X'Length;
62 -- Words in each multiplicand
63 L : constant Word_Index := X'Length;
64
65 -- Register holding running product
66 XY : FZ(1 .. X'Length + Y'Length);
67 -- Length of Product, i.e. double the length of either multiplicand
68 LP : constant Word_Index := 2 * L;
69
70 -- X-Slide
71 XS : FZ(1 .. X'Length + Y'Length);
72 -- 3-word Accumulator
73 A2, A1, A0 : Word := 0;
74
75 -- Register holding Product; indexed from zero
76 XY : FZ(0 .. LP - 1);
77
78 -- Type for referring to a column of XY
79 subtype ColXY is Word_Index range XY'Range;
80
81 -- Compute the Nth (indexed from zero) column of the Product
82 procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
83
84 -- The outputs of a Word multiplication
85 Lo, Hi : Word;
86
87 -- Carry for the Accumulator addition
88 C : WBool;
89
90 -- Sum for Accumulator addition
91 Sum : Word;
92
93 begin
94
95 -- For lower half of XY, will go from 0 to N
96 -- For upper half of XY, will go from N - L + 1 to L - 1
97 for j in U .. V loop
98
99 -- Hi:Lo := j-th Word of X * (N - j)-th Word of Y
100 Mul_Word(X(X'First + j),
101 Y(Y'First - j + N),
102 Lo, Hi);
103
104 -- Now add Hi:Lo into the Accumulator:
105
106 -- A0 += Lo; C := Carry
107 Sum := A0 + Lo;
108 C := W_Carry(A0, Lo, Sum);
109 A0 := Sum;
110
111 -- A1 += Hi + C; C := Carry
112 Sum := A1 + Hi + C;
113 C := W_Carry(A1, Hi, Sum);
114 A1 := Sum;
115
116 -- A2 += A2 + C
117 A2 := A2 + C;
118
119 end loop;
120
121 -- We now have the Nth (indexed from zero) word of XY
122 XY(N) := A0;
123
124 -- Right-Shift the Accumulator by one Word width:
125 A0 := A1;
126 A1 := A2;
127 A2 := 0;
128
129 end Col;
130 pragma Inline_Always(Col);
131
132 begin
133 -- Product register begins empty
134 FZ_Clear(XY);
135
136 -- X-Slide initially equals X:
137 XS(1 .. X'Length) := X;
138 XS(X'Length + 1 .. XS'Last) := (others => 0);
139
140 -- For each word of Y:
141 for i in Y'Range loop
142
143 declare
144 -- Current word of Y
145 W : Word := Y(i);
146
147 -- Current cut of XY and XS. Stay ahead by a word to handle carry.
148 Cut : constant Indices := L + i;
149 XYc : FZ renames XY(1 .. Cut);
150 XSc : FZ renames XS(1 .. Cut);
151
152 begin
153 for b in 1 .. Bitness loop
154
155 -- If current Y bit is 1, X-Slide Cut is added into XY Cut
156 FZ_Add_Gated(X => XYc, Y => XSc, Sum => XYc,
157 Gate => W and 1);
158
159 -- Crank the next bit of Y into the bottom position of W
160 W := Shift_Right(W, 1);
161
162 -- X-Slide := X-Slide * 2
163 FZ_ShiftLeft(XSc, XSc, 1);
164
165 end loop;
166 end;
167 -- Compute the lower half of the Product:
168 for i in 0 .. L - 1 loop
169
170 Col(i, 0, i);
171
172 end loop;
173
174 -- Compute the upper half (sans last Word) of the Product:
175 for i in L .. LP - 2 loop
176
177 Col(i, i - L + 1, L - 1);
178
179 end loop;
180
181 -- Write out the Product's lower and upper FZs:
182 XY_Lo := XY(1 .. XY_Lo'Length);
183 XY_Hi := XY(XY_Lo'Length + 1 .. XY'Last);
184 -- The very last Word of the Product:
185 XY(XY'Last) := A0;
186
187 end FZ_Mul_Egyptian;
188 pragma Inline_Always(FZ_Mul_Egyptian);
189
190 -- Output the Product's lower and upper FZs:
191 XY_Lo := XY(0 .. L - 1);
192 XY_Hi := XY(L .. XY'Last);
193
194 end FZ_Mul_Comba;
195 pragma Inline_Always(FZ_Mul_Comba);
196
197 end FZ_Mul;
- 13FEAFDFAFEB27C76E393CE5A2A7FAC89360DCCDFDADE355CB248D66FE7B6BE202F71311136A09E729271D468D2DFDA6C2D4445C70C03A584E26FE53C458EAF0(24 . 11)(24 . 11)
202
203 pragma Pure;
204
205 -- 'Egyptological' multiplier. XY_Lo and XY_Hi hold result of X*Y.
206 procedure FZ_Mul_Egyptian(X : in FZ;
207 Y : in FZ;
208 XY_Lo : out FZ;
209 XY_Hi : out FZ);
210 -- Comba's multiplier.
211 procedure FZ_Mul_Comba(X : in FZ;
212 Y : in FZ;
213 XY_Lo : out FZ;
214 XY_Hi : out FZ);
215 pragma Precondition(X'Length = Y'Length and
216 XY_Lo'Length = XY_Hi'Length and
217 XY_Lo'Length = ((X'Length + Y'Length) / 2));
-(0 . 0)(1 . 135)
222 ------------------------------------------------------------------------------
223 ------------------------------------------------------------------------------
224 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
225 -- --
226 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
227 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
228 -- --
229 -- You do not have, nor can you ever acquire the right to use, copy or --
230 -- distribute this software ; Should you use this software for any purpose, --
231 -- or copy and distribute it to anyone or in any manner, you are breaking --
232 -- the laws of whatever soi-disant jurisdiction, and you promise to --
233 -- continue doing so for the indefinite future. In any case, please --
234 -- always : read and understand any software ; verify any PGP signatures --
235 -- that you use - for any purpose. --
236 -- --
237 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
238 ------------------------------------------------------------------------------
239 ------------------------------------------------------------------------------
240
241 with W_Shifts; use W_Shifts;
242
243
244 package body W_Mul is
245
246 -- Multiply half-words X and Y, producing a Word-sized product
247 function Mul_HalfWord(X : in HalfWord; Y : in HalfWord) return Word is
248
249 -- X-Slide
250 XS : Word := X;
251
252 -- Y-Slide
253 YS : Word := Y;
254
255 -- Gate Mask
256 GM : Word;
257
258 -- The Product
259 XY : Word := 0;
260
261 -- Performed for each bit of HalfWord's bitness:
262 procedure Bit is
263 begin
264
265 -- Compute the gate mask
266 GM := 0 - (YS and 1);
267
268 -- Perform the gated addition
269 XY := XY + (XS and GM);
270
271 -- Crank the next Y-slide bit into position
272 YS := Shift_Right(YS, 1);
273
274 -- Advance the X-slide by 1 bit
275 XS := Shift_Left(XS, 1);
276
277 end Bit;
278 pragma Inline_Always(Bit);
279
280 begin
281
282 -- For each bit of the Y-Slide (unrolled) :
283 for b in 1 .. HalfByteness loop
284
285 Bit; Bit; Bit; Bit; Bit; Bit; Bit; Bit;
286
287 end loop;
288
289 -- Return the Product
290 return XY;
291
292 end Mul_HalfWord;
293 pragma Inline_Always(Mul_HalfWord);
294
295
296 -- Get the bottom half of a Word
297 function BottomHW(W : in Word) return HalfWord is
298 begin
299 return W and (2**HalfBitness - 1);
300 end BottomHW;
301 pragma Inline_Always(BottomHW);
302
303
304 -- Get the top half of a Word
305 function TopHW(W : in Word) return HalfWord is
306 begin
307 return Shift_Right(W, HalfBitness);
308 end TopHW;
309 pragma Inline_Always(TopHW);
310
311
312 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
313 procedure Mul_Word(X : in Word;
314 Y : in Word;
315 XY_LW : out Word;
316 XY_HW : out Word) is
317
318 -- Bottom half of multiplicand X
319 XL : constant HalfWord := BottomHW(X);
320
321 -- Top half of multiplicand X
322 XH : constant HalfWord := TopHW(X);
323
324 -- Bottom half of multiplicand Y
325 YL : constant HalfWord := BottomHW(Y);
326
327 -- Top half of multiplicand Y
328 YH : constant HalfWord := TopHW(Y);
329
330 -- XL * YL
331 LL : constant Word := Mul_HalfWord(XL, YL);
332
333 -- XL * YH
334 LH : constant Word := Mul_HalfWord(XL, YH);
335
336 -- XH * YL
337 HL : constant Word := Mul_HalfWord(XH, YL);
338
339 -- XH * YH
340 HH : constant Word := Mul_HalfWord(XH, YH);
341
342 -- Carry
343 CL : constant Word := TopHW(TopHW(LL) + BottomHW(LH) + BottomHW(HL));
344
345 begin
346
347 -- Get the bottom half of the Product:
348 XY_LW := LL + Shift_Left(LH + HL, HalfBitness);
349
350 -- Get the top half of the Product:
351 XY_HW := HH + TopHW(HL) + TopHW(LH) + CL;
352
353 end Mul_Word;
354 pragma Inline_Always(Mul_Word);
355
356 end W_Mul;
-(0 . 0)(1 . 46)
361 ------------------------------------------------------------------------------
362 ------------------------------------------------------------------------------
363 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
364 -- --
365 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
366 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
367 -- --
368 -- You do not have, nor can you ever acquire the right to use, copy or --
369 -- distribute this software ; Should you use this software for any purpose, --
370 -- or copy and distribute it to anyone or in any manner, you are breaking --
371 -- the laws of whatever soi-disant jurisdiction, and you promise to --
372 -- continue doing so for the indefinite future. In any case, please --
373 -- always : read and understand any software ; verify any PGP signatures --
374 -- that you use - for any purpose. --
375 -- --
376 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
377 ------------------------------------------------------------------------------
378 ------------------------------------------------------------------------------
379
380 with Words; use Words;
381
382
383 package W_Mul is
384
385 pragma Pure;
386
387 -- The bitness of a Half-Word
388 HalfBitness : constant Positive := Bitness / 2;
389 subtype HalfWord is Word range 0 .. 2**HalfBitness;
390
391 -- The number of bytes in a Half-Word
392 HalfByteness : constant Positive := Byteness / 2;
393
394 -- Multiply half-words X and Y, producing a Word-sized product
395 function Mul_HalfWord(X : in HalfWord; Y : in HalfWord) return Word;
396
397 -- Get the bottom half of a Word
398 function BottomHW(W : in Word) return HalfWord;
399
400 -- Get the top half of a Word
401 function TopHW(W : in Word) return HalfWord;
402
403 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
404 procedure Mul_Word(X : in Word; Y : in Word; XY_LW : out Word; XY_HW : out Word);
405
406 end W_Mul;