tree checksum vpatch file split hunks
all signers: bvt asciilifeform diana_coman
antecedents: ffa_ch12_karatsuba_redux.kv ffa_ch8_randomism.kv ffa_ch4_ffacalc.kv ffa_ch11_tuning_and_api.kv ffa_ch13_measure_and_qshifts.kv
press order:
patch:
(12 . 3)(12 . 4)
5 551091 ffa_ch12_karatsuba_redux "Karatsuba Redux."
6 551348 ffa_w_borrow_expr diana_coman Replaces expression for calculating borrow bit with more readable version that is also symmetrical to that for carry bit.
7 551516 ffa_ch13_measure_and_qshifts "Measure and Quiet Shifts."
8 555788 ffa_ch14_barrett "Barrett's Modular Reduction."
- 1E1522F2AEB7EEB67F9F420498E76E141F39197818EF5768EAB4DBDA5A34AF29253F0A48E059B9ADEE583A96D76A4321A66030774886512B0003A5C1A0722E2A(2 . 7)(2 . 7)- EE9AD64E37CFC68344AFE8F1D5DFA4683B808E7D4719B16D1B5605661C9736AE7D99631C97FCC55F03416A2DF6D717216884E34612080C3F7C887E3EA00FF903
13 ------------------------------------------------------------------------------
14 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
15 -- --
16 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
17 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
18 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
19 -- --
20 -- You do not have, nor can you ever acquire the right to use, copy or --
(17 . 9)(17 . 10)
22 ------------------------------------------------------------------------------
23 ------------------------------------------------------------------------------
24
25 See HISTORY.TXT for full chronology of changes.
26 See MANIFEST.TXT for full chronology of changes.
27
28 Project WWW: http://www.loper-os.org/?cat=49
29 ( Start with Chapter 1 : http://www.loper-os.org/?p=1913 )
30
31 Questions?
32
(2 . 7)(2 . 7)- E0AD759605B591A052D598C055ECB9C0BC4856536CDEDF2BD616D040E71A5A2B2C3B3D98781707199D1642538F1D76EB12B0E47AA159F449993116E00A95C52E
37 ------------------------------------------------------------------------------
38 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
39 -- --
40 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
41 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
42 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
43 -- --
44 -- You do not have, nor can you ever acquire the right to use, copy or --
(33 . 7)(33 . 7)
46
47 -- Fill the provided string with the text of Number-th cmdline arg
48 procedure Get_Argument(Number : in Natural;
49 Result : out String) is
50 Result : out CmdLineArg) is
51 begin
52 if Number >= Arg_Count or (not Initialized) then
53 raise Constraint_Error;
(2 . 7)(2 . 7)- FA29011671FB6E7C802D18C92D4B94C2D32BB54145A929ECE7780830ACE49582A6EA090AD4678B55A403FA5EBEC34AA091C8672CE1D060E18ED6C87D554E87E9
58 ------------------------------------------------------------------------------
59 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
60 -- --
61 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
62 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
63 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
64 -- --
65 -- You do not have, nor can you ever acquire the right to use, copy or --
(32 . 7)(32 . 7)
67 pragma Import(C, Arg_Count, "__gnat_arg_count");
68
69 procedure Get_Argument(Number : in Natural;
70 Result : out String);
71 Result : out CmdLineArg);
72
73 function Len_Arg (Arg_Num : Integer) return Integer;
74 pragma Import(C, Len_Arg, "__gnat_len_arg");
(2 . 7)(2 . 7)-
79 ------------------------------------------------------------------------------
80 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
81 -- --
82 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
83 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
84 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
85 -- --
86 -- You do not have, nor can you ever acquire the right to use, copy or --
(18 . 6)(18 . 7)
88 ------------------------------------------------------------------------------
89
90 -- Basics
91 with Version; use Version;
92 with OS; use OS;
93 with CmdLine; use CmdLine;
94
(33 . 9)(34 . 9)
96
97 procedure FFA_Calc is
98
99 Width : Positive; -- Desired FFA Width
100 Height : Positive; -- Desired Height of Stack
101 RNG : RNG_Device; -- The active RNG device.
102 Width : Positive; -- Desired FFA Width
103 Height : Positive; -- Desired Height of Stack
104 RNG : RNG_Device; -- The active RNG device.
105
106 begin
107 if Arg_Count < 3 or Arg_Count > 4 then
(449 . 13)(450 . 12)
109 when 'W' =>
110 Want(1);
111 declare
112 Measure : Word;
113 begin
114 -- Find the measure ( 0 if no 1s, or 1 .. FZBitness )
115 Measure := FFA_FZ_Measure(Stack(SP));
116 Measure : FZBit_Index := FFA_FZ_Measure(Stack(SP));
117 begin
118 -- Put on top of stack
119 FFA_FZ_Clear(Stack(SP));
120 FFA_FZ_Set_Head(Stack(SP), Measure);
121 FFA_FZ_Set_Head(Stack(SP), Word(Measure));
122 end;
123
124 -- Put the Overflow flag on the stack
(480 . 6)(480 . 18)
126 end loop;
127 Quit(0);
128
129 -- Put the FFACalc Program Version on the stack,
130 -- followed by FFA Program Version.
131 when 'V' =>
132 Push;
133 Push;
134 -- FFACalc Version:
135 FFA_FZ_Clear(Stack(SP - 1));
136 FFA_FZ_Set_Head(Stack(SP - 1), Word(FFACalc_K_Version));
137 -- FFA Version:
138 FFA_FZ_Clear(Stack(SP));
139 FFA_FZ_Set_Head(Stack(SP), Word(FFA_K_Version));
140
141 -- Square, give bottom and top halves
142 when 'S' =>
143 Want(1);
(509 . 7)(521 . 7)
145 ---------------------------------------------------------
146 when '!' | '@' | '$' | ':' | ';' | ',' |
147 'G' | 'H' | 'I' | 'J' | 'K' | 'N' |
148 'P' | 'T' | 'V' | 'X' | 'Y' =>
149 'P' | 'T' | 'X' | 'Y' =>
150
151 E("This Operator is not defined yet: " & C);
152 ---------------------------------------------------------
(0 . 0)(1 . 30)
157 ------------------------------------------------------------------------------
158 ------------------------------------------------------------------------------
159 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
160 -- --
161 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
162 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
163 -- --
164 -- You do not have, nor can you ever acquire the right to use, copy or --
165 -- distribute this software ; Should you use this software for any purpose, --
166 -- or copy and distribute it to anyone or in any manner, you are breaking --
167 -- the laws of whatever soi-disant jurisdiction, and you promise to --
168 -- continue doing so for the indefinite future. In any case, please --
169 -- always : read and understand any software ; verify any PGP signatures --
170 -- that you use - for any purpose. --
171 -- --
172 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
173 ------------------------------------------------------------------------------
174 ------------------------------------------------------------------------------
175
176 package Version is
177
178 pragma Pure;
179
180 ----------------------------------------------
181 -- Current 'deg. Kelvin' Version of FFACalc --
182 ----------------------------------------------
183 FFACalc_K_Version : constant Natural := 255;
184 ----------------------------------------------
185
186 end Version;
- 325D1B598F4588DB145A10E3C6344707C6D5BF12FE83ACCE5210E420034BBC6CFADDC3B23152F515710F467A2D4BAA08408DC8BBF5B258CD34D29E289C38998A(40 . 6)(40 . 12)-
191 pragma Pure;
192
193 ----------------------------------------------------------------------------
194 --- Current 'deg. Kelvin' Version of FFA
195 ----------------------------------------------------------------------------
196
197 FFA_K_Version : constant Natural := 255;
198
199 ----------------------------------------------------------------------------
200 --- Fundamental Types and Sizes
201 ----------------------------------------------------------------------------
202
(290 . 7)(296 . 7)
204 ----------------------------------------------------------------------------
205
206 -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
207 function FFA_FZ_Measure(N : in FZ) return Word
208 function FFA_FZ_Measure(N : in FZ) return FZBit_Index
209 renames FZ_Measr.FZ_Measure;
210
211 -- Constant-time arbitrary right-shift.
(0 . 0)(1 . 300)
216 ------------------------------------------------------------------------------
217 ------------------------------------------------------------------------------
218 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
219 -- --
220 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
221 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
222 -- --
223 -- You do not have, nor can you ever acquire the right to use, copy or --
224 -- distribute this software ; Should you use this software for any purpose, --
225 -- or copy and distribute it to anyone or in any manner, you are breaking --
226 -- the laws of whatever soi-disant jurisdiction, and you promise to --
227 -- continue doing so for the indefinite future. In any case, please --
228 -- always : read and understand any software ; verify any PGP signatures --
229 -- that you use - for any purpose. --
230 -- --
231 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
232 ------------------------------------------------------------------------------
233
234 -----------------------------------------------------------------------------
235 -- BEFORE YOU EVEN *THINK* ABOUT MODIFYING THIS PROGRAM: --
236 -----------------------------------------------------------------------------
237 -- `dMMd` +NMMMMMMMNo --
238 -- .dM++Md..oNMMMMMMmo` --
239 -- /mM+ +MmmMMMMMMNo. --
240 -- /NM+ +MMMMMMNo` / --
241 -- /Nd- `sNMMMMMy.-oohNNm` --
242 -- `yNd- -yMMMMMMMNNNMMMMs. --
243 -- hMd::. -mMMMMMdNMMMMMMm+` --
244 -- :hNs.`.:yNyyyo--/sNMMMMy` --
245 -- -o.. `.. `.sNh` --
246 -- ..`RRR EEE AA DDD !+:` --
247 -- `: R R E A A D D ! .o- --
248 -- .s RRR EEE AAAA D D ! .:` --
249 -- .. `` R R E A A D D ys. --
250 -- -h /: R R EEE A A DDD !/ :mm- --
251 -- -mm `/- THE PROOFS!!! -y sMm- --
252 -- -mNy `++` YES THAT MEANS YOU! .s. .`-Nm- --
253 -- `oNN-`:/y``:////:` `-////``-o.+. -NNo` --
254 -- `oNN: `+:::hNMMMMNyo. `smNMMMMmy`++ :NNo` --
255 -- `oNy- .: sMMMMMMMMM: -MMMMMMMMMs/s. -yNh- --
256 -- -dNy. `s. sMMMMMMMmo.----mMMMMMMMNo `.` .yMd- --
257 -- .dmo. `o` /mNNNmyo.`sNMMy.+ymNNNNh `-` .omd. --
258 -- .mN/ -o` .---. `oNMNMNs .----. -/. /Nm. --
259 -- +mN/ .hhs:.. ` .hMN-MMy ` `.-+-` /Nm+ --
260 -- +NN: :hMMMs/m`d -y- dy -`:/y :NN+ --
261 -- +Nd: /: `hMMMmm/ y:Ns::.`````.:oh-- :dNs. --
262 -- .sNh. .h+:hMMMy./- -yMMMyyod+dssMM:. `: .hMh. --
263 -- .hMy. +MNMMMMh` ` `yNMhmsNsmhNh: /` +Mh. --
264 -- -hN+ -dMMMMMNso+- :s .ymmNMmyh+- + +Nh- --
265 -- `MN+ /MMMMMMh:- :- :: : .+ +NM` --
266 -- `Md///////+mMMMMys////////sh/- -yy/////////////////////////dM` --
267 -- -ssssssssymssssssssssssssssso- .+ossssssssssssssssssssssssssss- --
268 -- --
269 --Ch. 14A: Barrett’s Modular Reduction: http://www.loper-os.org/?p=2842 --
270 --Ch. 14A-Bis: Barrett’s Physical Bounds: http://www.loper-os.org/?p=2875 --
271 -- --
272 -----------------------------------------------------------------------------
273
274 with W_Pred; use W_Pred;
275 with W_Shifts; use W_Shifts;
276 with FZ_Basic; use FZ_Basic;
277 with FZ_Shift; use FZ_Shift;
278 with FZ_Arith; use FZ_Arith;
279 with FZ_Mul; use FZ_Mul;
280 with FZ_LoMul; use FZ_LoMul;
281 with FZ_Measr; use FZ_Measr;
282 with FZ_QShft; use FZ_QShft;
283
284
285 package body FZ_Barr is
286
287 -- Prepare the precomputed Barrettoid corresponding to a given Modulus
288 procedure FZ_Make_Barrettoid(Modulus : in FZ;
289 Result : out Barretoid) is
290
291 -- Length of Modulus and Remainder
292 Lm : constant Indices := Modulus'Length;
293
294 -- Remainder register, starts as zero
295 Remainder : FZ(1 .. Lm) := (others => 0);
296
297 -- Length of Quotient, with an extra Word for top bit (if Degenerate)
298 Lq : constant Indices := (2 * Lm) + 1;
299
300 -- Valid indices into Quotient, using the above
301 subtype Quotient_Index is Word_Index range 1 .. Lq;
302
303 -- The Quotient we need, i.e. 2^(2 * ModulusBitness) / Modulus
304 Quotient : FZ(Quotient_Index);
305
306 -- Permissible 'cuts' for the Slice operation
307 subtype Divisor_Cuts is Word_Index range 2 .. Lm;
308
309 -- Current bit of Pseudo-Dividend; high bit is 1, all others 0
310 Pb : WBool := 1;
311
312 -- Performs Restoring Division on a given segment
313 procedure Slice(Index : Quotient_Index;
314 Cut : Divisor_Cuts;
315 Bits : Positive) is
316 begin
317
318 declare
319
320 -- Borrow, from comparator
321 C : WBool;
322
323 -- Left-Shift Overflow
324 LsO : WBool;
325
326 -- Current cut of Remainder register
327 Rs : FZ renames Remainder(1 .. Cut);
328
329 -- Current cut of Divisor
330 Ds : FZ renames Modulus(1 .. Cut);
331
332 -- Current Word of Quotient being made, starting from the highest
333 W : Word := 0;
334
335 -- Current bit of Quotient (inverted)
336 nQb : WBool;
337
338 begin
339
340 -- For each bit in the current Pseudo-Dividend Word:
341 for b in 1 .. Bits loop
342
343 -- Advance Rs, shifting in the current Pseudo-Dividend bit:
344 FZ_ShiftLeft_O_I(N => Rs,
345 ShiftedN => Rs,
346 Count => 1,
347 OF_In => Pb, -- Current Pseudo-Dividend bit
348 Overflow => LsO);
349
350 -- Subtract Divisor-Cut from R-Cut; Underflow goes into C:
351 FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
352
353 -- Negation of current Quotient bit
354 nQb := C and W_Not(LsO);
355
356 -- If C=1, the subtraction underflowed, and we must undo it:
357 FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
358 Gate => nQb);
359
360 -- Save the bit of Quotient that we have found:
361 W := Shift_Left(W, 1) or (1 - nQb); -- i.e. inverse of nQb
362
363 end loop;
364
365 -- We made a complete Word of the Quotient; save it:
366 Quotient(Quotient'Last + 1 - Index) := W; -- Indexed from end
367
368 end;
369
370 end Slice;
371 pragma Inline_Always(Slice);
372
373 -- Measure of the Modulus
374 ModulusMeasure : constant FZBit_Index := FZ_Measure(Modulus);
375
376 begin
377
378 -- First, process the high Word of the Pseudo-Dividend:
379 Slice(1, 2, 1); -- ... it has just one bit: a 1 at the bottom position
380
381 -- Once we ate the top 1 bit of Pseudo-Dividend, rest of its bits are 0
382 Pb := 0;
383
384 -- Process the Modulus-sized segment below the top Word:
385 for i in 2 .. Lm - 1 loop
386
387 Slice(i, i + 1, Bitness); -- stay ahead by a word to handle carry
388
389 end loop;
390
391 -- Process remaining Words:
392 for i in Lm .. Lq loop
393
394 Slice(i, Lm, Bitness);
395
396 end loop;
397
398 -- Record the Quotient (i.e. the Barrettoid proper, Bm)
399 Result.B := Quotient(Result.B'Range);
400
401 -- Record whether we have the Degenerate Case (1 iff Modulus = 1)
402 Result.Degenerate := W_NZeroP(Quotient(Lq));
403
404 -- Record a copy of the Modulus, extended with zero Word:
405 Result.ZXM(Modulus'Range) := Modulus;
406 Result.ZXM(Result.ZXM'Last) := 0;
407
408 -- Record the parameter Jm:
409 Result.J := ModulusMeasure - 1;
410
411 -- Wm - Jm
412 Result.ZSlide :=
413 FZBit_Index(Bitness * Modulus'Length) - ModulusMeasure + 1;
414
415 end FZ_Make_Barrettoid;
416
417
418 -- Reduce X using the given precomputed Barrettoid.
419 procedure FZ_Barrett_Reduce(X : in FZ;
420 Bar : in Barretoid;
421 XReduced : in out FZ) is
422
423 -- Wordness of X, the quantity being reduced
424 Xl : constant Indices := X'Length;
425
426 -- Wordness of XReduced (result), one-half of Xl, and same as of Modulus
427 Ml : constant Indices := XReduced'Length; -- i.e. # of Words in Wm.
428
429 -- The Modulus we will reduce X by
430 Modulus : FZ renames Bar.ZXM(1 .. Ml);
431
432 -- Shifted X
433 Xs : FZ(X'Range);
434
435 -- Z := Xs * Bm (has twice the length of X)
436 Z : FZ(1 .. 2 * Xl);
437
438 -- Upper 3Wm-bit segment of Z that gets shifted to form Zs
439 ZHi : FZ renames Z(Ml + 1 .. Z'Last );
440
441 -- Middle 2Wm-bit segment of Z, that gets multiplied by M to form Q
442 Zs : FZ renames Z(Z'First + Ml .. Z'Last - Ml );
443
444 -- Sub-terms of the Zs * M multiplication:
445 ZsLo : FZ renames Zs(Zs'First .. Zs'Last - Ml );
446 ZsHi : FZ renames Zs(Zs'First + Ml .. Zs'Last );
447 ZsHiM : FZ(1 .. Ml);
448
449 -- Q := Modulus * Zs, i.e. floor(X / M)*M + E*M
450 Q : FZ(1 .. Xl);
451 QHi : FZ renames Q(Q'First + Ml .. Q'Last );
452
453 -- R is made one Word longer than Modulus (see proof re: why)
454 Rl : constant Indices := Ml + 1;
455
456 -- Reduction estimate, overshot by 0, 1, or 2 multiple of Modulus
457 R : FZ(1 .. Rl);
458
459 -- Scratch for the outputs of the gated subtractions
460 S : FZ(1 .. Rl);
461
462 -- Borrow from the gated subtractions
463 C : WBool;
464
465 -- Barring cosmic ray, no underflow can take place in (4) and (5)
466 NoCarry : WZeroOrDie := 0;
467
468 begin
469
470 -- Result is initially zero (and will stay zero if Modulus = 1)
471 FZ_Clear(XReduced);
472
473 -- (1) Ns := X >> Jm
474 FZ_Quiet_ShiftRight(N => X, ShiftedN => Xs, Count => Bar.J);
475
476 -- (2) Z := X * Bm
477 FZ_Multiply_Unbuffered(X => Bar.B, Y => Xs, XY => Z);
478
479 -- (3) Zs := Z >> 2Wm - Jm (already thrown lower Wm, so only Wm - Jm now)
480 FZ_Quiet_ShiftRight(N => ZHi, ShiftedN => ZHi, Count => Bar.ZSlide);
481
482 -- (4) Q := Zs * M (this is split into three operations, see below)
483
484 -- ... first, Q := ZsLo * M,
485 FZ_Multiply_Unbuffered(ZsLo, Modulus, Q);
486
487 -- ... then, compute ZsHiM := ZsHi * M,
488 FZ_Low_Multiply_Unbuffered(ZsHi, Modulus, ZsHiM);
489
490 -- ... finally, add ZsHiM to upper half of Q.
491 FZ_Add_D(X => QHi, Y => ZsHiM, Overflow => NoCarry);
492
493 -- (5) R := X - Q (we only need Rl-sized segments of X and Q here)
494 FZ_Sub(X => X(1 .. Rl), Y => Q(1 .. Rl),
495 Difference => R, Underflow => NoCarry);
496
497 -- (6) S1 := R - M, C1 := Borrow (1st gated subtraction of Modulus)
498 FZ_Sub(X => R, Y => Bar.ZXM, Difference => S, Underflow => C);
499
500 -- (7) R := {C1=0 -> S1, C1=1 -> R}
501 FZ_Mux(X => S, Y => R, Result => R, Sel => C);
502
503 -- (8) S2 := R - M, C2 := Borrow (2nd gated subtraction of Modulus)
504 FZ_Sub(X => R, Y => Bar.ZXM, Difference => S, Underflow => C);
505
506 -- (9) R := {C2=0 -> S2, C2=1 -> R}
507 FZ_Mux(X => S, Y => R, Result => R, Sel => C);
508
509 -- (10) RFinal := {DM=0 -> R, DM=1 -> 0} (handle the degenerate case)
510 FZ_Mux(X => R(1 .. Ml), Y => XReduced, Result => XReduced,
511 Sel => Bar.Degenerate); -- If Modulus = 1, then XReduced is 0.
512
513 end FZ_Barrett_Reduce;
514
515 end FZ_Barr;
-(0 . 0)(1 . 53)
520 ------------------------------------------------------------------------------
521 ------------------------------------------------------------------------------
522 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
523 -- --
524 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
525 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
526 -- --
527 -- You do not have, nor can you ever acquire the right to use, copy or --
528 -- distribute this software ; Should you use this software for any purpose, --
529 -- or copy and distribute it to anyone or in any manner, you are breaking --
530 -- the laws of whatever soi-disant jurisdiction, and you promise to --
531 -- continue doing so for the indefinite future. In any case, please --
532 -- always : read and understand any software ; verify any PGP signatures --
533 -- that you use - for any purpose. --
534 -- --
535 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
536 ------------------------------------------------------------------------------
537 ------------------------------------------------------------------------------
538
539 with Words; use Words;
540 with FZ_Type; use FZ_Type;
541
542
543 package FZ_Barr is
544
545 pragma Pure;
546
547 -- Precomputed data for Barrett's Modular Reduction
548 type Barretoid(ZXMLength : Indices;
549 BarretoidLength : Indices) is
550 record
551 ZXM : FZ(1 .. ZXMLength); -- Zero-Extended Modulus
552 J : FZBit_Index; -- Jm
553 B : FZ(1 .. BarretoidLength); -- The Barrettoid itself
554 ZSlide : FZBit_Index; -- Amount to slide Z
555 Degenerate : WBool; -- Is it degenerate case?
556 end record;
557
558
559 -- Prepare the precomputed Barrettoid corresponding to a given Modulus
560 procedure FZ_Make_Barrettoid(Modulus : in FZ;
561 Result : out Barretoid)
562 with Pre => Result.B'Length = 2 * Modulus'Length and
563 Result.ZXM'Length = Modulus'Length + 1;
564
565
566 -- Reduce N using the given precomputed Barrettoid.
567 procedure FZ_Barrett_Reduce(X : in FZ;
568 Bar : in Barretoid;
569 XReduced : in out FZ);
570 pragma Inline_Always(FZ_Barrett_Reduce);
571
572 end FZ_Barr;
-(0 . 0)(1 . 179)
577 ------------------------------------------------------------------------------
578 ------------------------------------------------------------------------------
579 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
580 -- --
581 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
582 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
583 -- --
584 -- You do not have, nor can you ever acquire the right to use, copy or --
585 -- distribute this software ; Should you use this software for any purpose, --
586 -- or copy and distribute it to anyone or in any manner, you are breaking --
587 -- the laws of whatever soi-disant jurisdiction, and you promise to --
588 -- continue doing so for the indefinite future. In any case, please --
589 -- always : read and understand any software ; verify any PGP signatures --
590 -- that you use - for any purpose. --
591 -- --
592 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
593 ------------------------------------------------------------------------------
594 ------------------------------------------------------------------------------
595
596 with Words; use Words;
597 with Word_Ops; use Word_Ops;
598 with W_Mul; use W_Mul;
599 with FZ_Arith; use FZ_Arith;
600 with FZ_Mul; use FZ_Mul;
601
602
603 -- "Low Multiplication" computes only the bottom half of the product XY.
604 -- Presently, it is used solely in Barrett's Modular Reduction.
605
606 package body FZ_LoMul is
607
608 -- Low-Only Comba's multiplier. (CAUTION: UNBUFFERED)
609 procedure FZ_Low_Mul_Comba(X : in FZ;
610 Y : in FZ;
611 XY : out FZ) is
612
613 -- Words in each multiplicand (and also in the half-product)
614 L : constant Word_Index := X'Length;
615
616 -- 3-word Accumulator
617 A2, A1, A0 : Word := 0;
618
619 begin
620
621 -- Compute the lower half of the Product, which is all we want:
622 for N in 0 .. L - 1 loop
623
624 -- Compute the Nth (indexed from zero) column of the Half-Product
625 declare
626
627 -- The outputs of a Word multiplication
628 Lo, Hi : Word;
629
630 -- Carry for the Accumulator addition
631 C : WBool;
632
633 -- Sum for Accumulator addition
634 Sum : Word;
635
636 begin
637
638 -- For lower half of XY, will go from 0 to N
639 -- For upper half of XY, will go from N - L + 1 to L - 1
640 for j in 0 .. N loop
641
642 -- Hi:Lo := j-th Word of X * (N - j)-th Word of Y
643 Mul_Word(X(X'First + j),
644 Y(Y'First - j + N),
645 Lo, Hi);
646
647 -- Now add Hi:Lo into the Accumulator:
648
649 -- A0 += Lo; C := Carry
650 Sum := A0 + Lo;
651 C := W_Carry(A0, Lo, Sum);
652 A0 := Sum;
653
654 -- A1 += Hi + C; C := Carry
655 Sum := A1 + Hi + C;
656 C := W_Carry(A1, Hi, Sum);
657 A1 := Sum;
658
659 -- A2 += A2 + C
660 A2 := A2 + C;
661
662 end loop;
663
664 -- We now have the Nth (indexed from zero) word of XY
665 XY(XY'First + N) := A0;
666
667 -- Right-Shift the Accumulator by one Word width:
668 A0 := A1;
669 A1 := A2;
670 A2 := 0;
671 end;
672
673 end loop;
674
675 end FZ_Low_Mul_Comba;
676
677
678 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
679 procedure Low_Mul(X : in FZ;
680 Y : in FZ;
681 XY : out FZ) is
682
683 -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
684 L : constant Word_Count := X'Length;
685
686 -- K is HALF of the length of a multiplicand.
687 K : constant Word_Index := L / 2;
688
689 -- A 'KSeg' is the same length as HALF of a multiplicand.
690 subtype KSeg is FZ(1 .. K);
691
692 -- The two K-sized variables of the half-product equation:
693 LH, HL : KSeg;
694
695 -- Bottom and Top K-sized halves of the multiplicand X.
696 XLo : KSeg renames X( X'First .. X'Last - K );
697 XHi : KSeg renames X( X'First + K .. X'Last );
698
699 -- Bottom and Top K-sized halves of the multiplicand Y.
700 YLo : KSeg renames Y( Y'First .. Y'Last - K );
701 YHi : KSeg renames Y( Y'First + K .. Y'Last );
702
703 -- Top K-sized half of the half-product XY.
704 XYHi : KSeg renames XY( XY'First + K .. XY'Last );
705
706 -- Carry from individual term additions.
707 C : WBool;
708 pragma Unreferenced(C);
709
710 begin
711
712 -- Recurse to FULL-width multiplication: XY := XLo * YLo
713 FZ_Multiply_Unbuffered(XLo, YLo, XY);
714
715 -- Recurse to HALF-width multiplication: LH := XLo * YHi
716 FZ_Low_Multiply_Unbuffered(XLo, YHi, LH);
717
718 -- Recurse to HALF-width multiplication: HL := XHi * YLo
719 FZ_Low_Multiply_Unbuffered(XHi, YLo, HL);
720
721 -- XY += 2^(K * Bitness) * LH
722 FZ_Add_D(X => XYHi, Y => LH, Overflow => C);
723
724 -- XY += 2^(K * Bitness) * HL
725 FZ_Add_D(X => XYHi, Y => HL, Overflow => C);
726
727 end Low_Mul;
728 -- CAUTION: Inlining prohibited for Low_Mul !
729
730
731 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
732 procedure FZ_Low_Multiply_Unbuffered(X : in FZ;
733 Y : in FZ;
734 XY : out FZ) is
735
736 -- The length of either multiplicand
737 L : constant Word_Count := X'Length;
738
739 begin
740
741 if L <= Low_Mul_Thresh then
742
743 -- Base case:
744 FZ_Low_Mul_Comba(X, Y, XY);
745
746 else
747
748 -- Recursive case:
749 Low_Mul(X, Y, XY);
750
751 end if;
752
753 end FZ_Low_Multiply_Unbuffered;
754
755 end FZ_LoMul;
-(0 . 0)(1 . 54)
760 ------------------------------------------------------------------------------
761 ------------------------------------------------------------------------------
762 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
763 -- --
764 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
765 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
766 -- --
767 -- You do not have, nor can you ever acquire the right to use, copy or --
768 -- distribute this software ; Should you use this software for any purpose, --
769 -- or copy and distribute it to anyone or in any manner, you are breaking --
770 -- the laws of whatever soi-disant jurisdiction, and you promise to --
771 -- continue doing so for the indefinite future. In any case, please --
772 -- always : read and understand any software ; verify any PGP signatures --
773 -- that you use - for any purpose. --
774 -- --
775 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
776 ------------------------------------------------------------------------------
777 ------------------------------------------------------------------------------
778
779 with FZ_Type; use FZ_Type;
780
781
782 -- "Low Multiplication" computes only the bottom half of the product XY.
783 -- Presently, it is used solely in Barrett's Modular Reduction.
784
785 package FZ_LoMul is
786
787 pragma Pure;
788
789 -- Threshhold for Low Mul - at or below this many Words, we use Comba mult.
790 Low_Mul_Thresh : constant Indices := 8;
791
792 -- Multiply. (CAUTION: UNBUFFERED)
793 procedure FZ_Low_Multiply_Unbuffered(X : in FZ;
794 Y : in FZ;
795 XY : out FZ);
796 pragma Inline_Always(FZ_Low_Multiply_Unbuffered);
797
798 -- Comba's multiplier. (CAUTION: UNBUFFERED)
799 procedure FZ_Low_Mul_Comba(X : in FZ;
800 Y : in FZ;
801 XY : out FZ);
802 pragma Inline_Always(FZ_Low_Mul_Comba);
803
804 -- Low Multiplier. (CAUTION: UNBUFFERED)
805 procedure Low_Mul(X : in FZ;
806 Y : in FZ;
807 XY : out FZ)
808 with Pre => X'Length = Y'Length and
809 XY'Length = X'Length and
810 X'Length mod 2 = 0;
811 -- CAUTION: Inlining prohibited for Low_Mul !
812
813 end FZ_LoMul;
- 5235054F1A2FFC6F2560122D8623A3ACDD486B15F85A930CB6099622008571EC59B56A423AF2D061FC39931BF624B231425212D28BBD06E9FAEA148EBE3A5148(17 . 6)(17 . 7)- 287E4CF7A7675B8C9038D229570590B7C013E183C65BD149E08ACEC898E6829C627E3F7401637407940D31BE9102FC0BA2020D22885E9AE022D6ADA1D231EFCD
818 ------------------------------------------------------------------------------
819 ------------------------------------------------------------------------------
820
821 with Words; use Words;
822 with Word_Ops; use Word_Ops;
823 with W_Pred; use W_Pred;
824 with W_Shifts; use W_Shifts;
(25 . 7)(26 . 7)
826 package body FZ_Measr is
827
828 -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
829 function FZ_Measure(N : in FZ) return Word is
830 function FZ_Measure(N : in FZ) return FZBit_Index is
831
832 -- The result (default : 0, will remain 0 if N is in fact zero)
833 Index : Word := 0;
(54 . 14)(55 . 17)
835
836 -- Find, in constant time, eldest non-zero bit in that Word:
837 for b in 1 .. Bitness loop
838
839 -- If W is non-zero, advance the Index...
840 Index := W_Mux(Index + 1, Index, W_ZeroP(W));
841 Index := Index + W_NZeroP(W);
842
843 -- ... in either case, advance W:
844 W := Shift_Right(W, 1);
845
846 end loop;
847
848 -- If N = 0, result will be 0; otherwise: index of the eldest 1 bit.
849 return Index;
850 return FZBit_Index(Index);
851
852 end FZ_Measure;
853
(17 . 7)(17 . 6)- 84C9976AA492F507F8F21C8BBEB3B7DC671F8AA45C9479808DFFDA6B62FD23A1891F08740937D5D61B8D5FAD9DA7AD9E890AAA79059C0A1EE69096D877A93577
858 ------------------------------------------------------------------------------
859 ------------------------------------------------------------------------------
860
861 with Words; use Words;
862 with FZ_Type; use FZ_Type;
863
864
(26 . 7)(25 . 7)
866 pragma Pure;
867
868 -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
869 function FZ_Measure(N : in FZ) return Word;
870 function FZ_Measure(N : in FZ) return FZBit_Index;
871 pragma Inline_Always(FZ_Measure);
872
873 end FZ_Measr;
(2 . 7)(2 . 7)- 4D75A96582C1897F5A85DA8983033487653B0B0678D88BC3C7F895FCBB4A0A63B9019426D119CB3EDDF959856959CBBA295BC1D46AE36B0C4B7F4A6F9E2A00A7
878 ------------------------------------------------------------------------------
879 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
880 -- --
881 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
882 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
883 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
884 -- --
885 -- You do not have, nor can you ever acquire the right to use, copy or --
(17 . 17)(17 . 18)
887 ------------------------------------------------------------------------------
888 ------------------------------------------------------------------------------
889
890 with Words; use Words;
891 with W_Shifts; use W_Shifts;
892 with FZ_Basic; use FZ_Basic;
893 with FZ_Pred; use FZ_Pred;
894 with FZ_Shift; use FZ_Shift;
895 with FZ_Mul; use FZ_Mul;
896 with FZ_Sqr; use FZ_Sqr;
897 with FZ_Divis; use FZ_Divis;
898 with FZ_Barr; use FZ_Barr;
899
900
901 package body FZ_ModEx is
902
903 -- Modular Multiply: Product := X*Y mod Modulus
904 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
905 procedure FZ_Mod_Mul(X : in FZ;
906 Y : in FZ;
907 Modulus : in FZ;
(54 . 7)(55 . 7)
909 end FZ_Mod_Mul;
910
911
912 -- Modular Squaring: Product := X*X mod Modulus
913 -- (Conventional) Modular Squaring: Product := X*X mod Modulus
914 procedure FZ_Mod_Sqr(X : in FZ;
915 Modulus : in FZ;
916 Product : out FZ) is
(80 . 44)(81 . 68)
918 end FZ_Mod_Sqr;
919
920
921 -- Modular Exponent: Result := Base^Exponent mod Modulus
922 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
923 procedure FZ_Mod_Exp(Base : in FZ;
924 Exponent : in FZ;
925 Modulus : in FZ;
926 Result : out FZ) is
927
928 -- Working register for the squaring; initially is copy of Base
929 B : FZ(Base'Range) := Base;
930 -- Double-width scratch buffer for the modular operations
931 D : FZ(1 .. Base'Length * 2);
932
933 -- Copy of Exponent, for cycling through its bits
934 E : FZ(Exponent'Range) := Exponent;
935 -- Working register for the squaring; initially is copy of Base
936 B : FZ(Base'Range) := Base;
937
938 -- Register for the Mux operation
939 T : FZ(Result'Range);
940 T : FZ(Result'Range);
941
942 -- Buffer register for the Result
943 R : FZ(Result'Range);
944 R : FZ(Result'Range);
945
946 -- Space for Barrettoid
947 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
948 BarretoidLength => 2 * B'Length);
949
950 begin
951
952 -- First, pre-compute the Barretoid for the given Modulus:
953 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
954
955 -- Result := 1
956 WBool_To_FZ(1, R);
957
958 -- For each bit of R width:
959 for i in 1 .. FZ_Bitness(R) loop
960
961 -- T := Result * B mod Modulus
962 FZ_Mod_Mul(X => R, Y => B, Modulus => Modulus, Product => T);
963
964 -- Sel is the current low bit of E;
965 -- When Sel=0 -> Result := Result;
966 -- When Sel=1 -> Result := T
967 FZ_Mux(X => R, Y => T, Result => R, Sel => FZ_OddP(E));
968 -- For each Word of the Exponent:
969 for i in Exponent'Range loop
970
971 -- Advance to the next bit of E
972 FZ_ShiftRight(E, E, 1);
973 declare
974
975 -- The current Word of the Exponent
976 Wi : Word := Exponent(i);
977
978 begin
979
980 -- For each bit of Wi:
981 for j in 1 .. Bitness loop
982
983 -- T := Result * B mod Modulus
984 FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
985 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
986
987 -- Sel is the current bit of Exponent;
988 -- When Sel=0 -> Result := Result;
989 -- When Sel=1 -> Result := T
990 FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
991
992 -- Advance to the next bit of Wi (i.e. next bit of Exponent)
993 Wi := Shift_Right(Wi, 1);
994
995 -- B := B^2 mod Modulus
996 FZ_Square_Unbuffered(X => B, XX => D);
997 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
998
999 end loop;
1000
1001 -- B := B^2 mod Modulus
1002 FZ_Mod_Sqr(X => B, Modulus => Modulus, Product => B);
1003 end;
1004
1005 end loop;
1006
(2 . 7)(2 . 7)- 1A74EE33F52E9CABC886BE4C6FEFD3E861A6196B937FF207C2A711D0945424CBFB607205DB86DB8B835D813F910C4D1ABCF406FDF361AF28FA729568A059B620
1011 ------------------------------------------------------------------------------
1012 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1013 -- --
1014 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
1015 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1016 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1017 -- --
1018 -- You do not have, nor can you ever acquire the right to use, copy or --
(24 . 7)(24 . 7)
1020
1021 pragma Pure;
1022
1023 -- Modular Multiply: Product := X*Y mod Modulus
1024 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
1025 procedure FZ_Mod_Mul(X : in FZ;
1026 Y : in FZ;
1027 Modulus : in FZ;
(33 . 14)(33 . 14)
1029 Modulus'Length = X'Length and
1030 Product'Length = Modulus'Length;
1031
1032 -- Modular Square: Product := X*X mod Modulus
1033 -- (Conventional) Modular Squaring: Product := X*X mod Modulus
1034 procedure FZ_Mod_Sqr(X : in FZ;
1035 Modulus : in FZ;
1036 Product : out FZ)
1037 with Pre => Modulus'Length = X'Length and
1038 Product'Length = Modulus'Length;
1039
1040 -- Modular Exponent: Result := Base^Exponent mod Modulus
1041 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
1042 procedure FZ_Mod_Exp(Base : in FZ;
1043 Exponent : in FZ;
1044 Modulus : in FZ;
(2 . 7)(2 . 7)- 1570D6BFA1EE2A3EB93A9255B60EDE80878BD262017FE490A263A0957451EAFD218C8FC257BBABFD9E6B31FED71A0BF5C1A0EE4831A5F988779E37AD04793C39
1049 ------------------------------------------------------------------------------
1050 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1051 -- --
1052 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
1053 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1054 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1055 -- --
1056 -- You do not have, nor can you ever acquire the right to use, copy or --
(27 . 6)(27 . 7)
1058 --------------------------------------------------------------
1059
1060 -- ShiftedN := N >> Count (with Overflow Input and Output)
1061 -- WARNING: OF_in MUST be of valid bit-width for the shift!
1062 procedure FZ_ShiftRight_O_I(N : in FZ;
1063 ShiftedN : out FZ;
1064 Count : in WBit_Index;
(69 . 6)(70 . 7)
1066 --------------------------------------------------------------
1067
1068 -- ShiftedN := N << Count (with Overflow Input and Output)
1069 -- WARNING: OF_in MUST be of valid bit-width for the shift!
1070 procedure FZ_ShiftLeft_O_I(N : in FZ;
1071 ShiftedN : out FZ;
1072 Count : in WBit_Index;
(2 . 7)(2 . 7)- C2A8101914BB78150BECC64DE77A0560FA05859BC2908F14E4CE933F6D5682CFEFF4F28982E655321E6E9EE8E1E5B0B884ACF1048DB28AF0EFFFA69C493C2BCF
1077 ------------------------------------------------------------------------------
1078 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1079 -- --
1080 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
1081 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1082 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1083 -- --
1084 -- You do not have, nor can you ever acquire the right to use, copy or --
(26 . 10)(26 . 16)
1086 pragma Pure;
1087
1088 --------------------------------------------------------------
1089 -- WARNING: These ops are not precondition-shielded, and
1090 -- must never be directly exposed via the user API ( ffa.ads )
1091 --------------------------------------------------------------
1092
1093 --------------------------------------------------------------
1094 -- Shift Right
1095 --------------------------------------------------------------
1096
1097 -- ShiftedN := N >> Count (with Overflow Input and Output)
1098 -- WARNING: OF_in MUST be of valid bit-width for the shift!
1099 procedure FZ_ShiftRight_O_I(N : in FZ;
1100 ShiftedN : out FZ;
1101 Count : in WBit_Index;
(55 . 6)(61 . 7)
1103 --------------------------------------------------------------
1104
1105 -- ShiftedN := N << Count (with Overflow Input and Output)
1106 -- WARNING: OF_in MUST be of valid bit-width for the shift!
1107 procedure FZ_ShiftLeft_O_I(N : in FZ;
1108 ShiftedN : out FZ;
1109 Count : in WBit_Index;
(2 . 7)(2 . 7)
1114 ------------------------------------------------------------------------------
1115 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1116 -- --
1117 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
1118 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1119 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1120 -- --
1121 -- You do not have, nor can you ever acquire the right to use, copy or --
(39 . 6)(39 . 6)
1123 ByteBits : constant Positive := 8;
1124
1125 -- Whether we have a barrel shifter:
1126 HaveBarrelShifter : constant Boolean := True;
1127 HaveBarrelShifter : constant Boolean := True;
1128
1129 end Iron;