tree checksum vpatch file

all signers: diana_coman ben_vulpes peterl spyked asciilifeform

antecedents: ffa_ch5_egypt ffa_ch9_exodus

press order:

ffa_ch1_genesisasciilifeform ben_vulpes diana_coman peterl spyked
ffa_ch2_logicalsasciilifeform ben_vulpes diana_coman peterl spyked
ffa_ch3_shiftsasciilifeform ben_vulpes diana_coman peterl spyked
ffa_ch4_ffacalcasciilifeform ben_vulpes peterl spyked
ffa_ch5_egyptasciilifeform
ffa_ch6_simplest_rsaasciilifeform
ffa_ch7_turbo_egyptiansasciilifeform
ffa_ch8_randomismasciilifeform
ffa_ch9_exodusasciilifeform
ffa_ch10_karatsubaasciilifeform

patch:

- 34C0CC65AD5C7BE8AEB1D6BB33BA5C00C0F38B5AA90C986CD299B6C2AFF1FA45C996C4B9205511C75427B144AFE106D3DF035651AB6BF0F567BF7616E5C7F8DF
+ C61288B6ACCAEC888B1B993463FF88E7378B06E7888901B0A5319B888C0862CD491958451504F192503B7AF1E1889F7157231EEC12226B056CACAAA8D7A0B1A7
ffa/ffacalc/ffa_calc.adb
(380 . 11)(380 . 10)
5 -- Multiply, give bottom and top halves
6 when '*' =>
7 Want(2);
8 -- Ch9: Comba's algorithm
9 FZ_Mul_Comba(X => Stack(SP - 1),
10 Y => Stack(SP),
11 XY_Lo => Stack(SP - 1),
12 XY_Hi => Stack(SP));
13 FZ_Mult(X => Stack(SP - 1),
14 Y => Stack(SP),
15 XY_Lo => Stack(SP - 1),
16 XY_Hi => Stack(SP));
17
18 -- Modular Multiplication
19 when 'M' =>
- 7426E4888BF866D3E8B14A4E03A96F4C4CAE79D13F4D6BB5857AEB17B5FEBDC17656AD496C635F9123E0791BA8E18A9E83106900BF817BA582B6A36683474AD3
+ 19874C09181E37CE487FEED91FCBA612D61AC22AD0B50F811C7CB3C3183A0EA87B6F4A9A274E6F34CC086E8B1C08222F1B8DD6487A4964453A35CEEDD5D75012
ffa/libffa/fz_arith.adb
(19 . 9)(19 . 52)
24
25 with Word_Ops; use Word_Ops;
26
27
28 -- Fundamental Arithmetic operators on FZ:
29 package body FZ_Arith is
30
31 -- Destructive Add: X := X + Y; Overflow := Carry; optional OF_In
32 procedure FZ_Add_D(X : in out FZ;
33 Y : in FZ;
34 Overflow : out WBool;
35 OF_In : in WBool := 0) is
36 Carry : WBool := OF_In;
37 begin
38 for i in 0 .. Word_Index(X'Length - 1) loop
39 declare
40 A : constant Word := X(X'First + i);
41 B : constant Word := Y(Y'First + i);
42 S : constant Word := A + B + Carry;
43 begin
44 X(X'First + i) := S;
45 Carry := W_Carry(A, B, S);
46 end;
47 end loop;
48 Overflow := Carry;
49 end FZ_Add_D;
50 pragma Inline_Always(FZ_Add_D);
51
52
53 -- Destructive Add: X := X + W; Overflow := Carry
54 procedure FZ_Add_D_W(X : in out FZ;
55 W : in Word;
56 Overflow : out WBool) is
57 Carry : Word := W;
58 begin
59 for i in X'Range loop
60 declare
61 A : constant Word := X(I);
62 S : constant Word := A + Carry;
63 begin
64 X(i) := S;
65 Carry := W_Carry(A, 0, S);
66 end;
67 end loop;
68 Overflow := Carry;
69 end FZ_Add_D_W;
70 pragma Inline_Always(FZ_Add_D_W);
71
72
73 -- Sum := X + Y; Overflow := Carry
74 procedure FZ_Add(X : in FZ;
75 Y : in FZ;
(29 . 13)(72 . 13)
77 Overflow : out WBool) is
78 Carry : WBool := 0;
79 begin
80 for i in X'Range loop
81 for i in 0 .. Word_Index(X'Length - 1) loop
82 declare
83 A : constant Word := X(I);
84 B : constant Word := Y(I);
85 A : constant Word := X(X'First + i);
86 B : constant Word := Y(Y'First + i);
87 S : constant Word := A + B + Carry;
88 begin
89 Sum(i) := S;
90 Sum(Sum'First + i) := S;
91 Carry := W_Carry(A, B, S);
92 end;
93 end loop;
(103 . 4)(146 . 49)
95 end FZ_Sub;
96 pragma Inline_Always(FZ_Sub);
97
98
99 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
100 procedure FZ_Not_Cond_D(N : in out FZ;
101 Cond : in WBool)is
102
103 -- The inversion mask
104 Inv : constant Word := 0 - Cond;
105
106 begin
107
108 for i in N'Range loop
109
110 -- Invert (or, if Cond is 0, do nothing)
111 N(i) := N(i) xor Inv;
112
113 end loop;
114
115 end FZ_Not_Cond_D;
116 pragma Inline_Always(FZ_Not_Cond_D);
117
118
119 -- Subtractor that gets absolute value if underflowed, in const. time
120 procedure FZ_Sub_Abs(X : in FZ;
121 Y : in FZ;
122 Difference : out FZ;
123 Underflow : out WBool) is
124
125 O : Word := 0;
126 pragma Unreferenced(O);
127
128 begin
129
130 -- First, we subtract normally
131 FZ_Sub(X, Y, Difference, Underflow);
132
133 -- If borrow - negate,
134 FZ_Not_Cond_D(Difference, Underflow);
135
136 -- ... and also increment.
137 FZ_Add_D_W(Difference, Underflow, O);
138
139 end FZ_Sub_Abs;
140 pragma Inline_Always(FZ_Sub_Abs);
141
142
143 end FZ_Arith;
- C00BAEF0B2E192924F96D2B8091D607FC82787D4D6BC97463EDB3A6E317B0292BCB8A0B1F93BC410FECDE02A6763B785503FAB4E6BE4439B8DAD8CEC350F4882
+ FD0A8537432143E00A449C5150C1F7276F1F0A57E93C0F6041E91886135CCABAD3309F06EB3DFF01CFB47BAEAA51E4F7292F640718049877AFBD62C16EBE12A8
ffa/libffa/fz_arith.ads
(20 . 11)(20 . 24)
148 with Words; use Words;
149 with FZ_Type; use FZ_Type;
150
151
152 -- Fundamental Arithmetic operators on FZ:
153 package FZ_Arith is
154
155 pragma Pure;
156
157 -- Destructive Add: X := X + Y; Overflow := Carry; optional OF_In
158 procedure FZ_Add_D(X : in out FZ;
159 Y : in FZ;
160 Overflow : out WBool;
161 OF_In : in WBool := 0);
162 pragma Precondition(X'Length = Y'Length);
163
164 -- Destructive Add: X := X + W; Overflow := Carry
165 procedure FZ_Add_D_W(X : in out FZ;
166 W : in Word;
167 Overflow : out WBool);
168
169 -- Sum := X + Y; Overflow := Carry
170 procedure FZ_Add(X : in FZ;
171 Y : in FZ;
(55 . 4)(68 . 15)
173 Underflow : out WBool);
174 pragma Precondition(X'Length = Y'Length and X'Length = Difference'Length);
175
176 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
177 procedure FZ_Not_Cond_D(N : in out FZ;
178 Cond : in WBool);
179
180 -- Subtractor that gets absolute value if underflowed, in const. time
181 procedure FZ_Sub_Abs(X : in FZ;
182 Y : in FZ;
183 Difference : out FZ;
184 Underflow : out WBool);
185 pragma Precondition(X'Length = Y'Length and X'Length = Difference'Length);
186
187 end FZ_Arith;
- 6EA4FAA823C2AF23DAA29802E8FB41548848406A9BE106B3B31077F50CABCB6F1FB947350991BDE5F3E5E136AE79ACAC74DD6DFAB0C82C16B4265CB4E77AA02A
+ AD6C3FD9DAEAD553F950C16B4214D780797569DA01D9F18FDF77767D7CF8F70BE791E29097F805CF24442BBD0C0F4DCFA0D85CB1DC9991724C08C6C7CB3288F5
ffa/libffa/fz_modex.adb
(45 . 7)(45 . 7)
192 begin
193
194 -- XY_Lo:XY_Hi := X * Y
195 FZ_Mul_Comba(X, Y, XY_Lo, XY_Hi);
196 FZ_Mult(X, Y, XY_Lo, XY_Hi);
197
198 -- Product := XY mod M
199 FZ_Mod(XY, Modulus, Product);
- 4F546E35EF6A116FCF2033F9B6B8F339C511E40CE7FCD3723499F93ECB721F866C2794ADF82F3454D2250A76567D460E516067FF5AA85BABD998E4FE2F35BA64
+ 2EB814EDED517B295D34ECE0A09A16866FE1AC6F204403B3AA9BB53E267279A37EA5143BF120AAD6B7D001160E9BEF3C60A23E8405BC05B3403258E50A0AFAFB
ffa/libffa/fz_mul.adb
(20 . 15)(20 . 15)
204 with Words; use Words;
205 with Word_Ops; use Word_Ops;
206 with W_Mul; use W_Mul;
207 with FZ_Arith; use FZ_Arith;
208
209
210 package body FZ_Mul is
211
212 -- Comba's multiplier.
213
214 -- Comba's multiplier. (CAUTION: UNBUFFERED)
215 procedure FZ_Mul_Comba(X : in FZ;
216 Y : in FZ;
217 XY_Lo : out FZ;
218 XY_Hi : out FZ) is
219 XY : out FZ) is
220
221 -- Words in each multiplicand
222 L : constant Word_Index := X'Length;
(39 . 11)(39 . 8)
224 -- 3-word Accumulator
225 A2, A1, A0 : Word := 0;
226
227 -- Register holding Product; indexed from zero
228 XY : FZ(0 .. LP - 1);
229
230 -- Type for referring to a column of XY
231 subtype ColXY is Word_Index range XY'Range;
232 subtype ColXY is Word_Index range 0 .. LP - 1;
233
234 -- Compute the Nth (indexed from zero) column of the Product
235 procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
(86 . 7)(83 . 7)
237 end loop;
238
239 -- We now have the Nth (indexed from zero) word of XY
240 XY(N) := A0;
241 XY(XY'First + N) := A0;
242
243 -- Right-Shift the Accumulator by one Word width:
244 A0 := A1;
(115 . 11)(112 . 163)
246 -- The very last Word of the Product:
247 XY(XY'Last) := A0;
248
249 -- Output the Product's lower and upper FZs:
250 XY_Lo := XY(0 .. L - 1);
251 XY_Hi := XY(L .. XY'Last);
252
253 end FZ_Mul_Comba;
254 pragma Inline_Always(FZ_Mul_Comba);
255
256
257 -- Karatsuba's Multiplier. (CAUTION: UNBUFFERED)
258 procedure Mul_Karatsuba(X : in FZ;
259 Y : in FZ;
260 XY : out FZ) is
261
262 -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
263 L : constant Word_Count := X'Length;
264
265 -- An 'LSeg' is the same length as either multiplicand.
266 subtype LSeg is FZ(1 .. L);
267
268 -- K is HALF of the length of a multiplicand.
269 K : constant Word_Index := L / 2;
270
271 -- A 'KSeg' is the same length as HALF of a multiplicand.
272 subtype KSeg is FZ(1 .. K);
273
274 -- The three L-sized variables of the product equation, i.e.:
275 -- XY = LL + 2^(K*Bitness)(LL + HH + (-1^DD_Sub)*DD) + 2^(2*K*Bitness)HH
276 LL, DD, HH : LSeg;
277
278 -- K-sized terms of Dx * Dy = DD
279 Dx, Dy : KSeg; -- Dx = abs(XLo - XHi) , Dy = abs(YLo - YHi)
280
281 -- Subtraction borrows, signs of (XL - XH) and (YL - YH),
282 Cx, Cy : WBool; -- so that we can calculate (-1^DD_Sub)
283
284 -- Bottom and Top K-sized halves of the multiplicand X.
285 XLo : KSeg renames X( X'First .. X'Last - K );
286 XHi : KSeg renames X( X'First + K .. X'Last );
287
288 -- Bottom and Top K-sized halves of the multiplicand Y.
289 YLo : KSeg renames Y( Y'First .. Y'Last - K );
290 YHi : KSeg renames Y( Y'First + K .. Y'Last );
291
292 -- L-sized middle segment of the product XY (+/- K from the midpoint).
293 XYMid : LSeg renames XY( XY'First + K .. XY'Last - K );
294
295 -- Bottom and Top L-sized halves of the product XY.
296 XYLo : LSeg renames XY( XY'First .. XY'Last - L );
297 XYHi : LSeg renames XY( XY'First + L .. XY'Last );
298
299 -- Topmost K-sized quarter segment of the product XY, or 'tail'
300 XYHiHi : KSeg renames XYHi( XYHi'First + K .. XYHi'Last );
301
302 -- Whether the DD term is being subtracted.
303 DD_Sub : WBool;
304
305 -- Carry from individual term additions.
306 C : WBool;
307
308 -- Tail-Carry accumulator, for the final ripple
309 TC : Word;
310
311 begin
312
313 -- Recurse: LL := XL * YL
314 FZ_Multiply(XLo, YLo, LL);
315
316 -- Recurse: HH := XH * YH
317 FZ_Multiply(XHi, YHi, HH);
318
319 -- Dx := |XL - XH| , Cx := Borrow (i.e. 1 iff XL < XH)
320 FZ_Sub_Abs(X => XLo, Y => XHi, Difference => Dx, Underflow => Cx);
321
322 -- Dy := |YL - YH| , Cy := Borrow (i.e. 1 iff YL < YH)
323 FZ_Sub_Abs(X => YLo, Y => YHi, Difference => Dy, Underflow => Cy);
324
325 -- Recurse: DD := Dx * Dy
326 FZ_Multiply(Dx, Dy, DD);
327
328 -- Whether (XL - XH)(YL - YH) is positive, and so DD must be subtracted:
329 DD_Sub := 1 - (Cx xor Cy);
330
331 -- XY := LL + 2^(2 * K * Bitness) * HH
332 XYLo := LL;
333 XYHi := HH;
334
335 -- XY += 2^(K * Bitness) * HH, but carry goes in Tail Carry accum.
336 FZ_Add_D(X => XYMid, Y => HH, Overflow => TC);
337
338 -- XY += 2^(K * Bitness) * LL, ...
339 FZ_Add_D(X => XYMid, Y => LL, Overflow => C);
340
341 -- ... but the carry goes into the Tail Carry accumulator.
342 TC := TC + C;
343
344 -- XY += 2^(K * Bitness) * (-1^DD_Sub) * DD
345 FZ_Not_Cond_D(N => DD, Cond => DD_Sub); -- invert DD if 2s-complementing
346 FZ_Add_D(OF_In => DD_Sub, -- ... and then must increment
347 X => XYMid,
348 Y => DD,
349 Overflow => C); -- carry will go in Tail Carry accumulator
350
351 -- Compute the final Tail Carry for the ripple
352 TC := TC + C - DD_Sub;
353
354 -- Barring a cosmic ray, 0 <= TC <= 2 .
355 pragma Assert(TC <= 2);
356
357 -- Ripple the Tail Carry into the tail.
358 FZ_Add_D_W(X => XYHiHi, W => TC, Overflow => C);
359
360 -- Barring a cosmic ray, the tail ripple will NOT overflow.
361 pragma Assert(C = 0);
362
363 end Mul_Karatsuba;
364 -- CAUTION: Inlining prohibited for Mul_Karatsuba !
365
366
367 -- Multiplier. (CAUTION: UNBUFFERED)
368 procedure FZ_Multiply(X : in FZ;
369 Y : in FZ;
370 XY : out FZ) is
371
372 -- The length of either multiplicand
373 L : constant Word_Count := X'Length;
374
375 begin
376
377 if L <= Karatsuba_Thresh then
378
379 -- Base case:
380 FZ_Mul_Comba(X, Y, XY);
381
382 else
383
384 -- Recursive case:
385 Mul_Karatsuba(X, Y, XY);
386
387 end if;
388
389 end FZ_Multiply;
390 pragma Inline_Always(FZ_Multiply);
391
392
393 -- Multiplier. Preserves the inputs.
394 procedure FZ_Mult(X : in FZ;
395 Y : in FZ;
396 XY_Lo : out FZ;
397 XY_Hi : out FZ) is
398
399 -- Product buffer.
400 P : FZ(1 .. 2 * X'Length);
401
402 begin
403
404 FZ_Multiply(X, Y, P);
405
406 XY_Lo := P(P'First .. P'First + X'Length - 1);
407 XY_Hi := P(P'First + X'Length .. P'Last);
408
409 end FZ_Mult;
410 pragma Inline_Always(FZ_Mult);
411
412 end FZ_Mul;
- 9EBE9F3C6F07530A2C38615CE35BF36A3F75731DE816B1BD766BC9C56CD41231338DD8A9E26D095604B999E76B04679909371204E96B682793F43C542523A054
+ FF010DF51B8FD2DB2A923BCFA007A4B91B6B74642FC95BA05DEAA5241D69F42026E9C585DB34204FAB005DCAC796F1412F4BF3C3CE981B756FF96117A224EDA7
ffa/libffa/fz_mul.ads
(24 . 11)(24 . 37)
417
418 pragma Pure;
419
420 -- Comba's multiplier.
421 -- Karatsuba Threshhold - at or below this many words, we use Comba mult.
422 Karatsuba_Thresh : constant Indices := 8;
423
424 -- Multiply. (CAUTION: UNBUFFERED)
425 procedure FZ_Multiply(X : in FZ;
426 Y : in FZ;
427 XY : out FZ);
428 pragma Precondition(X'Length = Y'Length and
429 XY'Length = (X'Length + Y'Length));
430
431 -- Comba's multiplier. (CAUTION: UNBUFFERED)
432 procedure FZ_Mul_Comba(X : in FZ;
433 Y : in FZ;
434 XY_Lo : out FZ;
435 XY_Hi : out FZ);
436 XY : out FZ);
437 pragma Precondition(X'Length = Y'Length and
438 XY'Length = (X'Length + Y'Length));
439
440 -- Karatsuba's Multiplier. (CAUTION: UNBUFFERED)
441 procedure Mul_Karatsuba(X : in FZ;
442 Y : in FZ;
443 XY : out FZ);
444 pragma Precondition(X'Length = Y'Length and
445 XY'Length = (X'Length + Y'Length) and
446 X'Length mod 2 = 0);
447 -- CAUTION: Inlining prohibited for Mul_Karatsuba !
448
449 -- Multiplier. Preserves the inputs.
450 procedure FZ_Mult(X : in FZ;
451 Y : in FZ;
452 XY_Lo : out FZ;
453 XY_Hi : out FZ);
454 pragma Precondition(X'Length = Y'Length and
455 XY_Lo'Length = XY_Hi'Length and
456 XY_Lo'Length = ((X'Length + Y'Length) / 2));
- 05F22B0818B3D2E5FD0A10DEF7B16FA1A6DB2064666F966E8325714D9D6E35E56CD24D2BD416E40A043D09632ABA0389B87A63538141439A1F4FD0ACB94CE9F6
+ C0CC17A4770A9E388E193B7A1A5798A64F5A56EA37D4779EE05C34981DDE45ABC16A8AF4CCBBEAF44FDF9D00A9D8773D655AB4B8ED4E2DC185C1DC497993378F
ffa/libffa/w_mul.adb
(22 . 8)(22 . 16)
461
462 package body W_Mul is
463
464 function Mul_HalfWord_Iron(X : in HalfWord;
465 Y : in HalfWord) return Word is
466 begin
467 return X * Y;
468 end Mul_HalfWord_Iron;
469 pragma Inline_Always(Mul_HalfWord_Iron);
470
471
472 -- Multiply half-words X and Y, producing a Word-sized product
473 function Mul_HalfWord(X : in HalfWord; Y : in HalfWord) return Word is
474 function Mul_HalfWord_Soft(X : in HalfWord; Y : in HalfWord) return Word is
475
476 -- X-Slide
477 XS : Word := X;
(68 . 8)(76 . 8)
479 -- Return the Product
480 return XY;
481
482 end Mul_HalfWord;
483 pragma Inline_Always(Mul_HalfWord);
484 end Mul_HalfWord_Soft;
485 pragma Inline_Always(Mul_HalfWord_Soft);
486
487
488 -- Get the bottom half of a Word
(107 . 16)(115 . 16)
490 YH : constant HalfWord := TopHW(Y);
491
492 -- XL * YL
493 LL : constant Word := Mul_HalfWord(XL, YL);
494 LL : constant Word := Mul_HalfWord_Iron(XL, YL);
495
496 -- XL * YH
497 LH : constant Word := Mul_HalfWord(XL, YH);
498 LH : constant Word := Mul_HalfWord_Iron(XL, YH);
499
500 -- XH * YL
501 HL : constant Word := Mul_HalfWord(XH, YL);
502 HL : constant Word := Mul_HalfWord_Iron(XH, YL);
503
504 -- XH * YH
505 HH : constant Word := Mul_HalfWord(XH, YH);
506 HH : constant Word := Mul_HalfWord_Iron(XH, YH);
507
508 -- Carry
509 CL : constant Word := TopHW(TopHW(LL) + BottomHW(LH) + BottomHW(HL));
- 6ACFA49F10F59AB341D9944D9C7BC03E9597C9EC01ECA606522686A88E35BFE731F350C72E9FE284B655135FA542980CA2A343021A79CEB3869F27DB6F177844
+ B898C525749BA5A7167725FF5A14A7A04D475FBB6FCB9C2613CEAC8B74A171BD16DA3E9B3882BDB72A92E83A7FF503D20A046253082A7B07F7B32B7E1CB33309
ffa/libffa/w_mul.ads
(31 . 8)(31 . 11)
514 -- The number of bytes in a Half-Word
515 HalfByteness : constant Positive := Byteness / 2;
516
517 -- Multiply half-words X and Y, producing a Word-sized product
518 function Mul_HalfWord(X : in HalfWord; Y : in HalfWord) return Word;
519 -- Multiply half-words X and Y, producing a Word-sized product (Iron)
520 function Mul_HalfWord_Iron(X : in HalfWord; Y : in HalfWord) return Word;
521
522 -- Multiply half-words X and Y, producing a Word-sized product (Egyptian)
523 function Mul_HalfWord_Soft(X : in HalfWord; Y : in HalfWord) return Word;
524
525 -- Get the bottom half of a Word
526 function BottomHW(W : in Word) return HalfWord;
(40 . 7)(43 . 7)
528 -- Get the top half of a Word
529 function TopHW(W : in Word) return HalfWord;
530
531 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
532 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW (Iron)
533 procedure Mul_Word(X : in Word; Y : in Word; XY_LW : out Word; XY_HW : out Word);
534
535 end W_Mul;