tree checksum vpatch file split hunks
all signers: asciilifeform bvt diana_coman
antecedents: ffa_ch6_simplest_rsa.kv ffa_ch7_turbo_egyptians.kv ffa_ch3_shifts.kv ffa_ch5_egypt.kv ffa_ch8_randomism.kv ffa_ch1_genesis.kv ffa_ch4_ffacalc.kv ffa_ch10_karatsuba.kv ffa_ch2_logicals.kv
press order:
patch:
(0 . 0)(1 . 47)
5 ###############
6 ### HISTORY ###
7 ###############
8
9 "Chapter 1: Genesis."
10 ffa_ch1_genesis.vpatch
11 http://www.loper-os.org/?p=1913
12
13 "Chapter 2: Logical and Bitwise Operations."
14 ffa_ch2_logicals.vpatch
15 http://www.loper-os.org/?p=2026
16
17 "Chapter 3: Shifts."
18 ffa_ch3_shifts.vpatch
19 http://www.loper-os.org/?p=2032
20
21 "Chapter 4: Interlude: FFACalc."
22 ffa_ch4_ffacalc.vpatch
23 http://www.loper-os.org/?p=2051
24
25 "Chapter 5: "Egyptological" Multiplication and Division."
26 ffa_ch5_egypt.vpatch
27 http://www.loper-os.org/?p=2071
28
29 "Chapter 6: "Geological" RSA."
30 ffa_ch6_simplest_rsa.vpatch
31 http://www.loper-os.org/?p=2105
32
33 "Chapter 7: "Turbo Egyptians.""
34 ffa_ch7_turbo_egyptians.vpatch
35 http://www.loper-os.org/?p=2118
36
37 "Chapter 8: Interlude: Randomism."
38 ffa_ch8_randomism.vpatch
39 http://www.loper-os.org/?p=2175
40
41 "Chapter 9: "Exodus from Egypt" with Comba’s Algorithm."
42 ffa_ch9_exodus.vpatch
43 http://www.loper-os.org/?p=2186
44
45 "Chapter 10: Introducing Karatsuba’s Multiplication."
46 ffa_ch10_karatsuba.vpatch
47 http://www.loper-os.org/?p=2238
48
49 "Chapter 11: Tuning and Unified API."
50 ffa_ch11_tuning_and_api.vpatch
51 ### YOU ARE HERE ###
- 88D2C0487E367264F3B1F041CE0C0F95656350824F39B69C86168F45DF4F8E4C1626D44C49AA2434460EC62B399867E5E11225383E26F7421A33D51BCA0B3524(17 . 9)(17 . 9)
56 ------------------------------------------------------------------------------
57 ------------------------------------------------------------------------------
58
59 See contents of 'demo'.
60 See HISTORY.TXT for full chronology of changes.
61
62 See also project WWW: http://www.loper-os.org/?cat=49
63 Project WWW: http://www.loper-os.org/?cat=49
64
65 Questions?
66
- CA1DED1102A88D8097CAFD58FCA38F21C1B8500B936868DD036FA2446F78FC467A2C90058504CB04AF542E5925A3270F34A0B96B38DEB584868F52D608D6B460(22 . 22)(22 . 10)- 9721DA8826DA76AA03974927E9869B598A1F8CE3C8DBA308343C08AE7D27124A9BA65AEE35AFDB704ED5EEE3EC319CB036ECC97266388C833A458DD889A9A1F1
71 with CmdLine; use CmdLine;
72
73 -- FFA
74 with FZ_Lim; use FZ_Lim;
75 with Words; use Words;
76 with W_Pred; use W_Pred;
77 with FZ_Type; use FZ_Type;
78 with FZ_Basic; use FZ_Basic;
79 with FZ_Arith; use FZ_Arith;
80 with FZ_Cmp; use FZ_Cmp;
81 with FZ_Pred; use FZ_Pred;
82 with FZ_BitOp; use FZ_BitOp;
83 with FZ_Shift; use FZ_Shift;
84 with FZ_Divis; use FZ_Divis;
85 with FZ_Mul; use FZ_Mul;
86 with FZ_ModEx; use FZ_ModEx;
87 with FFA; use FFA;
88
89 -- For Output
90 with FFA_IO; use FFA_IO;
91 -- For the intrinsic equality operator on Words
92 use type FFA.Word;
93
94 -- For RNG:
95 with FFA_RNG; use FFA_RNG;
(89 . 8)(77 . 8)
97 end;
98
99 -- Test if proposed Width is permissible:
100 if not FZ_Valid_Bitness_P(Width) then
101 Eggog("Invalid Width: " & FZ_Validity_Rule_Doc);
102 if not FFA_FZ_Valid_Bitness_P(Width) then
103 Eggog("Invalid Width: " & FFA_Validity_Rule_Doc);
104 end if;
105
106 -- The Calculator itself:
(128 . 7)(116 . 7)
108 begin
109 -- Clear the stack
110 for i in Stack'Range loop
111 FZ_Clear(Stack(i));
112 FFA_FZ_Clear(Stack(i));
113 end loop;
114 -- Set SP to bottom
115 SP := Stack_Positions'First;
(158 . 7)(146 . 7)
117 -- Discard the top of the stack
118 procedure Drop is
119 begin
120 FZ_Clear(Stack(SP));
121 FFA_FZ_Clear(Stack(SP));
122 SP := SP - 1;
123 end Drop;
124
(175 . 33)(163 . 40)
126 -- Ensure that a divisor is not zero
127 procedure MustNotZero(D : in FZ) is
128 begin
129 if FZ_ZeroP(D) = 1 then
130 if FFA_FZ_ZeroP(D) = 1 then
131 E("Division by Zero!");
132 end if;
133 end MustNotZero;
134
135
136 -- Slide a new hex digit into the FZ on top of stack
137 procedure Ins_Hex_Digit(N : in out FZ;
138 D : in Nibble) is
139 Overflow : Word := 0;
140 procedure Ins_Hex_Digit(Digit : in Nibble) is
141 Overflow : WBool := 0;
142 begin
143 -- Make room in this FZ for one additional hex digit
144 FZ_ShiftLeft_O(N => N,
145 ShiftedN => N,
146 Count => 4,
147 Overflow => Overflow);
148
149 -- Insert the given nibble, and detect any overflow:
150 FFA_FZ_Insert_Bottom_Nibble(N => Stack(SP),
151 D => Digit,
152 Overflow => Overflow);
153
154 -- Constants which exceed the Width are forbidden:
155 if W_NZeroP(Overflow) = 1 then
156 if Overflow = 1 then
157 E("Constant Exceeds Bitness!");
158 end if;
159
160 -- Set the new digit
161 FZ_Or_W(N, D);
162 end;
163
164
165 -- Emit an ASCII representation of N to the terminal
166 procedure Print_FZ(N : in FZ) is
167 S : String(1 .. FFA_FZ_ASCII_Length(N)); -- Mandatorily, exact size
168 begin
169 FFA_FZ_To_Hex_String(N, S); -- Convert N to ASCII hex
170 Write_String(S); -- Print the result to stdout
171 Write_Newline; -- Print newline, for clarity.
172 end Print_FZ;
173
174
175 -- Execute a Normal Op
176 procedure Op_Normal(C : in Character) is
177
(234 . 7)(229 . 7)
179 -- Enter a ~taken~ Conditional branch:
180 when '{' =>
181 Want(1);
182 if FZ_ZeroP(Stack(SP)) = 1 then
183 if FFA_FZ_ZeroP(Stack(SP)) = 1 then
184 CondLevel := 1;
185 end if;
186 Drop;
(243 . 7)(238 . 7)
188 -- ... we push a 0, to suppress the 'else' clause
189 when '}' =>
190 Push;
191 WBool_To_FZ(0, Stack(SP));
192 FFA_WBool_To_FZ(0, Stack(SP));
193
194 ----------------
195 -- Immediates --
(254 . 18)(249 . 15)
197
198 when '0' .. '9' =>
199 Want(1);
200 Ins_Hex_Digit(Stack(SP),
201 Character'Pos(C) - Character'Pos('0'));
202 Ins_Hex_Digit(Character'Pos(C) - Character'Pos('0'));
203
204 when 'A' .. 'F' =>
205 Want(1);
206 Ins_Hex_Digit(Stack(SP),
207 10 + Character'Pos(C) - Character'Pos('A'));
208 Ins_Hex_Digit(10 + Character'Pos(C) - Character'Pos('A'));
209
210 when 'a' .. 'f' =>
211 Want(1);
212 Ins_Hex_Digit(Stack(SP),
213 10 + Character'Pos(C) - Character'Pos('a'));
214 Ins_Hex_Digit(10 + Character'Pos(C) - Character'Pos('a'));
215
216 ------------------
217 -- Stack Motion --
(274 . 7)(266 . 7)
219 -- Push a 0 onto the stack
220 when '.' =>
221 Push;
222 FZ_Clear(Stack(SP));
223 FFA_FZ_Clear(Stack(SP));
224
225 -- Dup
226 when '"' =>
(290 . 7)(282 . 7)
228 -- Swap
229 when ''' =>
230 Want(2);
231 FZ_Swap(Stack(SP), Stack(SP - 1));
232 FFA_FZ_Swap(Stack(SP), Stack(SP - 1));
233
234 -- Over
235 when '`' =>
(305 . 25)(297 . 25)
237 -- Equality
238 when '=' =>
239 Want(2);
240 WBool_To_FZ(FZ_Eqp(X => Stack(SP),
241 Y => Stack(SP - 1)),
242 Stack(SP - 1));
243 FFA_WBool_To_FZ(FFA_FZ_EqP(X => Stack(SP),
244 Y => Stack(SP - 1)),
245 Stack(SP - 1));
246 Drop;
247
248 -- Less-Than
249 when '<' =>
250 Want(2);
251 WBool_To_FZ(FZ_LessThanP(X => Stack(SP - 1),
252 Y => Stack(SP)),
253 Stack(SP - 1));
254 FFA_WBool_To_FZ(FFA_FZ_LessThanP(X => Stack(SP - 1),
255 Y => Stack(SP)),
256 Stack(SP - 1));
257 Drop;
258
259 -- Greater-Than
260 when '>' =>
261 Want(2);
262 WBool_To_FZ(FZ_GreaterThanP(X => Stack(SP - 1),
263 Y => Stack(SP)),
264 Stack(SP - 1));
265 FFA_WBool_To_FZ(FFA_FZ_GreaterThanP(X => Stack(SP - 1),
266 Y => Stack(SP)),
267 Stack(SP - 1));
268 Drop;
269
270 ----------------
(333 . 66)(325 . 66)
272 -- Subtract
273 when '-' =>
274 Want(2);
275 FZ_Sub(X => Stack(SP - 1),
276 Y => Stack(SP),
277 Difference => Stack(SP - 1),
278 Underflow => F);
279 Flag := W_NZeroP(F);
280 FFA_FZ_Subtract(X => Stack(SP - 1),
281 Y => Stack(SP),
282 Difference => Stack(SP - 1),
283 Underflow => F);
284 Flag := FFA_Word_NZeroP(F);
285 Drop;
286
287 -- Add
288 when '+' =>
289 Want(2);
290 FZ_Add(X => Stack(SP - 1),
291 Y => Stack(SP),
292 Sum => Stack(SP - 1),
293 Overflow => F);
294 Flag := W_NZeroP(F);
295 FFA_FZ_Add(X => Stack(SP - 1),
296 Y => Stack(SP),
297 Sum => Stack(SP - 1),
298 Overflow => F);
299 Flag := FFA_Word_NZeroP(F);
300 Drop;
301
302 -- Divide and give Quotient and Remainder
303 when '\' =>
304 Want(2);
305 MustNotZero(Stack(SP));
306 FZ_IDiv(Dividend => Stack(SP - 1),
307 Divisor => Stack(SP),
308 Quotient => Stack(SP - 1),
309 Remainder => Stack(SP));
310 FFA_FZ_IDiv(Dividend => Stack(SP - 1),
311 Divisor => Stack(SP),
312 Quotient => Stack(SP - 1),
313 Remainder => Stack(SP));
314
315 -- Divide and give Quotient only
316 when '/' =>
317 Want(2);
318 MustNotZero(Stack(SP));
319 FZ_Div(Dividend => Stack(SP - 1),
320 Divisor => Stack(SP),
321 Quotient => Stack(SP - 1));
322 FFA_FZ_Div(Dividend => Stack(SP - 1),
323 Divisor => Stack(SP),
324 Quotient => Stack(SP - 1));
325 Drop;
326
327 -- Divide and give Remainder only
328 when '%' =>
329 Want(2);
330 MustNotZero(Stack(SP));
331 FZ_Mod(Dividend => Stack(SP - 1),
332 Divisor => Stack(SP),
333 Remainder => Stack(SP - 1));
334 FFA_FZ_Mod(Dividend => Stack(SP - 1),
335 Divisor => Stack(SP),
336 Remainder => Stack(SP - 1));
337 Drop;
338
339 -- Multiply, give bottom and top halves
340 when '*' =>
341 Want(2);
342 FZ_Mult(X => Stack(SP - 1),
343 Y => Stack(SP),
344 XY_Lo => Stack(SP - 1),
345 XY_Hi => Stack(SP));
346 FFA_FZ_Multiply(X => Stack(SP - 1),
347 Y => Stack(SP),
348 XY_Lo => Stack(SP - 1),
349 XY_Hi => Stack(SP));
350
351 -- Modular Multiplication
352 when 'M' =>
353 Want(3);
354 MustNotZero(Stack(SP));
355 FZ_Mod_Mul(X => Stack(SP - 2),
356 Y => Stack(SP - 1),
357 Modulus => Stack(SP),
358 Product => Stack(SP - 2));
359 FFA_FZ_Modular_Multiply(X => Stack(SP - 2),
360 Y => Stack(SP - 1),
361 Modulus => Stack(SP),
362 Product => Stack(SP - 2));
363 Drop;
364 Drop;
365
(400 . 10)(392 . 10)
367 when 'X' =>
368 Want(3);
369 MustNotZero(Stack(SP));
370 FZ_Mod_Exp(Base => Stack(SP - 2),
371 Exponent => Stack(SP - 1),
372 Modulus => Stack(SP),
373 Result => Stack(SP - 2));
374 FFA_FZ_Modular_Exponentiate(Base => Stack(SP - 2),
375 Exponent => Stack(SP - 1),
376 Modulus => Stack(SP),
377 Result => Stack(SP - 2));
378 Drop;
379 Drop;
380
(414 . 31)(406 . 31)
382 -- Bitwise-And
383 when '&' =>
384 Want(2);
385 FZ_And(X => Stack(SP - 1),
386 Y => Stack(SP),
387 Result => Stack(SP - 1));
388 FFA_FZ_And(X => Stack(SP - 1),
389 Y => Stack(SP),
390 Result => Stack(SP - 1));
391 Drop;
392
393 -- Bitwise-Or
394 when '|' =>
395 Want(2);
396 FZ_Or(X => Stack(SP - 1),
397 Y => Stack(SP),
398 Result => Stack(SP - 1));
399 FFA_FZ_Or(X => Stack(SP - 1),
400 Y => Stack(SP),
401 Result => Stack(SP - 1));
402 Drop;
403
404 -- Bitwise-Xor
405 when '^' =>
406 Want(2);
407 FZ_Xor(X => Stack(SP - 1),
408 Y => Stack(SP),
409 Result => Stack(SP - 1));
410 FFA_FZ_Xor(X => Stack(SP - 1),
411 Y => Stack(SP),
412 Result => Stack(SP - 1));
413 Drop;
414
415 -- Bitwise-Not (1s-Complement)
416 when '~' =>
417 Want(1);
418 FZ_Not(Stack(SP), Stack(SP));
419 FFA_FZ_Not(Stack(SP), Stack(SP));
420
421 -----------
422 -- Other --
(447 . 28)(439 . 28)
424 -- Push a FZ of RNGolade onto the stack
425 when '?' =>
426 Push;
427 FZ_Clear(Stack(SP));
428 FFA_FZ_Clear(Stack(SP));
429 FZ_Random(RNG, Stack(SP));
430
431 -- mUx
432 when 'U' =>
433 Want(3);
434 FZ_Mux(X => Stack(SP - 2),
435 Y => Stack(SP - 1),
436 Result => Stack(SP - 2),
437 Sel => FZ_NZeroP(Stack(SP)));
438 FFA_FZ_Mux(X => Stack(SP - 2),
439 Y => Stack(SP - 1),
440 Result => Stack(SP - 2),
441 Sel => FFA_FZ_NZeroP(Stack(SP)));
442 Drop;
443 Drop;
444
445 -- Put the Overflow flag on the stack
446 when 'O' =>
447 Push;
448 WBool_To_FZ(Flag, Stack(SP));
449 FFA_WBool_To_FZ(Flag, Stack(SP));
450
451 -- Print the FZ on the top of the stack
452 when '#' =>
453 Want(1);
454 Dump(Stack(SP));
455 Print_FZ(Stack(SP));
456 Drop;
457
458 -- Zap (reset)
(478 . 7)(470 . 7)
460 -- Quit with Stack Trace
461 when 'Q' =>
462 for I in reverse Stack'First + 1 .. SP loop
463 Dump(Stack(I));
464 Print_FZ(Stack(I));
465 end loop;
466 Quit(0);
467
(537 . 7)(529 . 7)
469 -- we push a 1 to trigger the possible 'else' clause:
470 if CondLevel = 0 then
471 Push;
472 WBool_To_FZ(1, Stack(SP));
473 FFA_WBool_To_FZ(1, Stack(SP));
474 end if;
475
476 when '{' => -- Add a nesting level:
(39 . 10)(39 . 11)- 0AF3B0F9472F5C3AA25C62E3038E27DBB016BFA0451A28A86ACFC52CF7B31BD3E51067BF679C5331BEEA94419D92DBCE45351BB00143F2865D07E44E86C5168C
481 when "release" =>
482 for Switches ("Ada")
483 use ("-O2", "-fdump-scos", "-gnata", "-fstack-check",
484 "-gnatyd", "-gnatym",
485 "-fdata-sections", "-ffunction-sections");
486 end case;
487 end Compiler;
488
489
490 package Binder is
491 case Mode is
492 when "debug" =>
(61 . 8)(62 . 7)
494 use ();
495 when "release" =>
496 for Switches ("Ada")
497 use ("-Wl,--gc-sections",
498 "-static");
499 use ("-Wl,--gc-sections", "-static");
500 end case;
501 end Linker;
502
(1 . 65)(0 . 0)
507 ------------------------------------------------------------------------------
508 ------------------------------------------------------------------------------
509 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
510 -- --
511 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
512 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
513 -- --
514 -- You do not have, nor can you ever acquire the right to use, copy or --
515 -- distribute this software ; Should you use this software for any purpose, --
516 -- or copy and distribute it to anyone or in any manner, you are breaking --
517 -- the laws of whatever soi-disant jurisdiction, and you promise to --
518 -- continue doing so for the indefinite future. In any case, please --
519 -- always : read and understand any software ; verify any PGP signatures --
520 -- that you use - for any purpose. --
521 -- --
522 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
523 ------------------------------------------------------------------------------
524 ------------------------------------------------------------------------------
525
526 with OS; use OS;
527
528
529 with Words; use Words;
530 with W_Shifts; use W_Shifts;
531 with FZ_Type; use FZ_Type;
532
533
534 package body FFA_IO is
535
536 -- Obtain the WChars corresponding to the given Word
537 function W_To_WChars(N : Word) return WChars is
538 H : constant array(0 .. 15) of Character := "0123456789ABCDEF";
539 W : Word := N;
540 Result : WChars;
541 begin
542 for b in WChars'Range loop -- From bottom to top:
543 Result(B) := H(Natural(W and 16#F#)); -- Get current nibble.
544 W := Shift_Right(W, 4); -- Get the next nibble.
545 end loop;
546 return Result;
547 end W_To_WChars;
548
549
550 -- Display a hex representation of W to stdout
551 procedure Dump(W : in Word) is
552 T : WChars := W_To_WChars(W);
553 begin
554 for i in reverse T'Range loop
555 Write_Char(T(i));
556 end loop;
557 end Dump;
558
559
560 -- Display a hex representation of N to stdout
561 procedure Dump(N : in FZ) is
562 begin
563 for i in reverse N'Range loop
564 Dump(N(i));
565 end loop;
566
567 -- Newline, for clarity.
568 Write_Newline;
569 end Dump;
570
571 end FFA_IO;
- DE4FF4DFC81DF4A4FEBC2B5A1C359DF912969821FB3790D51D78EED6352FA52D03EB70A9226EF896CEE16DCFC40AB2FACB9FD49D54110FB86F3FEBD8CAF29E64(1 . 37)(0 . 0)
576 ------------------------------------------------------------------------------
577 ------------------------------------------------------------------------------
578 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
579 -- --
580 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
581 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
582 -- --
583 -- You do not have, nor can you ever acquire the right to use, copy or --
584 -- distribute this software ; Should you use this software for any purpose, --
585 -- or copy and distribute it to anyone or in any manner, you are breaking --
586 -- the laws of whatever soi-disant jurisdiction, and you promise to --
587 -- continue doing so for the indefinite future. In any case, please --
588 -- always : read and understand any software ; verify any PGP signatures --
589 -- that you use - for any purpose. --
590 -- --
591 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
592 ------------------------------------------------------------------------------
593 ------------------------------------------------------------------------------
594
595 with Words; use Words;
596 with FZ_Type; use FZ_Type;
597
598 package FFA_IO is
599
600 -- Character representation of a Word
601 type WChars is array(1 .. 2 * Byteness) of Character;
602
603 -- Obtain the WChars corresponding to the given Word
604 function W_To_WChars(N : Word) return WChars;
605
606 -- Display a hex representation of W to stdout
607 procedure Dump(W : in Word);
608
609 -- Display a hex representation of N to stdout
610 procedure Dump(N : in FZ);
611
612 end FFA_IO;
- 190C221CD6DA728EEC4414F6ADB513310049DB129F571C47368F67BD399EEEEA5ED6E72DF6DC4427D418C1B6C50715946A94BBD622736AFDA4DC4117AD916DF3(17 . 9)(17 . 8)
617 ------------------------------------------------------------------------------
618 ------------------------------------------------------------------------------
619
620 with OS; use OS;
621
622 with FZ_Type; use FZ_Type;
623 with OS; use OS;
624 with FFA; use FFA;
625
626
627 package body FFA_RNG is
- 3CDEA9E53BC0897151E3EB45166AC209388C4704D212DD40E2EAFEFE2850F56128559E9F5BA33D696F0CC45D41685428A6FF4265890C86D49266E5C90BD3FE8E(19 . 8)(19 . 8)
632
633 with Ada.Sequential_IO;
634
635 with Words; use Words;
636 with FZ_Type; use FZ_Type;
637 with FFA; use FFA;
638 use type FFA.Word;
639
640
641 package FFA_RNG is
- 0D869ED1DF92233694F2909B5E1F747E2D6A10BB249295DB47A6A06291ADFFBC091A29B025175FB99ADADBDA319408EF11A95BE26FBD0A92CEACEDDEE0A03B36(49 . 6)(49 . 15)
646 end Write_Newline;
647
648
649 -- Send a String to the TTY.
650 procedure Write_String(S : in String) is
651 begin
652 for i in S'Range loop
653 Write_Char(S(i));
654 end loop;
655 end Write_String;
656
657
658 -- Exit with an error condition report.
659 procedure Eggog(M : String) is
660 begin
- A07E5C21C783DA495725BD3FFDBF6903B9B309CA4B13D31675B11C22359EE2C9D1DB6A9690109075030A02779EB3EBD9D4C9E4F69354651C0C097F11BD5C38BD(32 . 6)(32 . 9)
665 -- Send a Newline to the TTY.
666 procedure Write_Newline;
667
668 -- Send a String to the TTY.
669 procedure Write_String(S : in String);
670
671 -- Exit with an error condition report.
672 procedure Eggog(M : String);
673
-(0 . 0)(1 . 110)
678 ------------------------------------------------------------------------------
679 ------------------------------------------------------------------------------
680 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
681 -- --
682 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
683 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
684 -- --
685 -- You do not have, nor can you ever acquire the right to use, copy or --
686 -- distribute this software ; Should you use this software for any purpose, --
687 -- or copy and distribute it to anyone or in any manner, you are breaking --
688 -- the laws of whatever soi-disant jurisdiction, and you promise to --
689 -- continue doing so for the indefinite future. In any case, please --
690 -- always : read and understand any software ; verify any PGP signatures --
691 -- that you use - for any purpose. --
692 -- --
693 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
694 ------------------------------------------------------------------------------
695 ------------------------------------------------------------------------------
696
697 with FZ_Arith;
698 with FZ_Shift;
699 with FZ_Mul;
700
701
702 -- Wrapper bodies for routines that we inline, but must enforce preconditions
703 -- on when called by FFA user.
704 package body FFA is
705
706 ----------------------------------------------------------------------------
707 --- FZ Basics
708 ----------------------------------------------------------------------------
709
710 -- Exchange X and Y
711 procedure FFA_FZ_Swap(X : in out FZ; Y : in out FZ) is
712 begin
713 FZ_Basic.FZ_Swap(X => X, Y => Y);
714 end FFA_FZ_Swap;
715
716 -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y
717 procedure FFA_FZ_Mux(X : in FZ; Y : in FZ;
718 Result : out FZ; Sel : in WBool) is
719 begin
720 FZ_Basic.FZ_Mux(X => X, Y => Y, Result => Result, Sel => Sel);
721 end FFA_FZ_Mux;
722
723 ----------------------------------------------------------------------------
724 --- Bitwise Operations on FZ
725 ----------------------------------------------------------------------------
726
727 -- Result := X & Y
728 procedure FFA_FZ_And(X : in FZ; Y : in FZ; Result : out FZ) is
729 begin
730 FZ_BitOp.FZ_And(X => X, Y => Y, Result => Result);
731 end FFA_FZ_And;
732
733 -- Result := X | Y
734 procedure FFA_FZ_Or(X : in FZ; Y : in FZ; Result : out FZ) is
735 begin
736 FZ_BitOp.FZ_Or(X => X, Y => Y, Result => Result);
737 end FFA_FZ_Or;
738
739 -- Result := X ^ Y
740 procedure FFA_FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ) is
741 begin
742 FZ_BitOp.FZ_Xor(X => X, Y => Y, Result => Result);
743 end FFA_FZ_Xor;
744
745 -- NotN := ~N ('ones complement')
746 procedure FFA_FZ_Not(N : in FZ; NotN : out FZ) is
747 begin
748 FZ_BitOp.FZ_Not(N => N, NotN => NotN);
749 end FFA_FZ_Not;
750
751 ----------------------------------------------------------------------------
752 --- Arithmetic on FZ
753 ----------------------------------------------------------------------------
754
755 -- Sum := X + Y; Overflow := Carry
756 procedure FFA_FZ_Add(X : in FZ;
757 Y : in FZ;
758 Sum : out FZ;
759 Overflow : out WBool) is
760 begin
761 FZ_Arith.FZ_Add(X => X, Y => Y, Sum => Sum, Overflow => Overflow);
762 end FFA_FZ_Add;
763
764 -- Difference := X - Y; Underflow := Borrow
765 procedure FFA_FZ_Subtract(X : in FZ;
766 Y : in FZ;
767 Difference : out FZ;
768 Underflow : out WBool) is
769 begin
770 FZ_Arith.FZ_Sub(X => X, Y => Y, Difference => Difference,
771 Underflow => Underflow);
772 end FFA_FZ_Subtract;
773
774 ----------------------------------------------------------------------------
775 --- Multiplication on FZ
776 ----------------------------------------------------------------------------
777
778 procedure FFA_FZ_Multiply(X : in FZ;
779 Y : in FZ;
780 XY_Lo : out FZ;
781 XY_Hi : out FZ) is
782 begin
783 FZ_Mul.FZ_Multiply_Buffered(X => X, Y => Y,
784 XY_Lo => XY_Lo, XY_Hi => XY_Hi);
785 end FFA_FZ_Multiply;
786
787 end FFA;
-(0 . 0)(1 . 277)
792 ------------------------------------------------------------------------------
793 ------------------------------------------------------------------------------
794 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
795 -- --
796 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
797 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
798 -- --
799 -- You do not have, nor can you ever acquire the right to use, copy or --
800 -- distribute this software ; Should you use this software for any purpose, --
801 -- or copy and distribute it to anyone or in any manner, you are breaking --
802 -- the laws of whatever soi-disant jurisdiction, and you promise to --
803 -- continue doing so for the indefinite future. In any case, please --
804 -- always : read and understand any software ; verify any PGP signatures --
805 -- that you use - for any purpose. --
806 -- --
807 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
808 ------------------------------------------------------------------------------
809 ------------------------------------------------------------------------------
810
811 with Words; use Words;
812 with FZ_Type; use FZ_Type;
813
814 with W_Pred;
815
816 with FZ_Lim;
817 with FZ_Basic;
818 with FZ_IO;
819 with FZ_Cmp;
820 with FZ_Pred;
821 with FZ_BitOp;
822 with FZ_Divis;
823 with FZ_ModEx;
824
825
826 -- FFA Exports
827 package FFA is
828
829 pragma Pure;
830
831 ----------------------------------------------------------------------------
832 --- Fundamental Types and Sizes
833 ----------------------------------------------------------------------------
834
835 subtype Word is Words.Word;
836 subtype WBool is Words.WBool;
837
838 subtype Nibble is Words.Nibble;
839
840 subtype FZ is FZ_Type.FZ;
841 subtype Indices is FZ_Type.Indices;
842
843 subtype Char_Count is FZ_IO.Char_Count;
844
845 Bitness : Positive renames Words.Bitness;
846
847 ----------------------------------------------------------------------------
848 --- Word Predicates
849 ----------------------------------------------------------------------------
850
851 -- Return 1 if N is equal to 0; otherwise return 0.
852 function FFA_Word_ZeroP(N : in Word) return WBool
853 renames W_Pred.W_ZeroP;
854
855 -- Return 1 if N is unequal to 0; otherwise return 0.
856 function FFA_Word_NZeroP(N : in Word) return WBool
857 renames W_Pred.W_NZeroP;
858
859 -- Return WBool-complement of N.
860 function FFA_Word_Not(N : in WBool) return WBool
861 renames W_Pred.W_Not;
862
863 -- Return 1 if N is odd; otherwise return 0.
864 function FFA_Word_OddP(N : in Word) return WBool
865 renames W_Pred.W_OddP;
866
867 -- Return 1 if A is equal to B ; otherwise return 0.
868 function FFA_Word_EqP(A : in Word; B : in Word) return WBool
869 renames W_Pred.W_EqP;
870
871 ----------------------------------------------------------------------------
872 --- FZ Limits
873 ----------------------------------------------------------------------------
874
875 FFA_Validity_Rule_Doc : String renames FZ_Lim.FZ_Validity_Rule_Doc;
876
877 -- Determine if a proposed FFA Bitness is valid.
878 function FFA_FZ_Valid_Bitness_P(B : in Positive) return Boolean
879 renames FZ_Lim.FZ_Valid_Bitness_P;
880
881 ----------------------------------------------------------------------------
882 --- FZ Basics
883 ----------------------------------------------------------------------------
884
885 -- Determine the Bitness of N
886 function FFA_FZ_Bitness(N : in FZ) return Bit_Count
887 renames FZ_Basic.FZ_Bitness;
888
889 -- N := 0
890 procedure FFA_FZ_Clear(N : out FZ)
891 renames FZ_Basic.FZ_Clear;
892
893 -- Set given FZ to a given truth value
894 procedure FFA_WBool_To_FZ(V : in WBool; N : out FZ)
895 renames FZ_Basic.WBool_To_FZ;
896
897 -- First Word of N := Source
898 procedure FFA_FZ_Set_Head(N : out FZ; Source : in Word)
899 renames FZ_Basic.FZ_Set_Head;
900
901 -- First Word of N
902 function FFA_FZ_Get_Head(N : in FZ) return Word
903 renames FZ_Basic.FZ_Get_Head;
904
905 -- Exchange X and Y
906 procedure FFA_FZ_Swap(X : in out FZ; Y : in out FZ)
907 with Pre => X'Length = Y'Length;
908
909 -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y
910 procedure FFA_FZ_Mux(X : in FZ; Y : in FZ; Result : out FZ; Sel : in WBool)
911 with Pre => X'Length = Y'Length and X'Length = Result'Length;
912
913 ----------------------------------------------------------------------------
914 --- FZ IO Operations
915 ----------------------------------------------------------------------------
916
917 -- Expand FZ N by nibble D, and determine whether this operation overflowed
918 procedure FFA_FZ_Insert_Bottom_Nibble(N : in out FZ;
919 D : in Nibble;
920 Overflow : out WBool)
921 renames FZ_IO.FZ_Insert_Bottom_Nibble;
922
923 -- Determine the number of ASCII characters required to represent N
924 function FFA_FZ_ASCII_Length(N : in FZ) return Char_Count
925 renames FZ_IO.FZ_ASCII_Length;
926
927 -- Write an ASCII hex representation of N into existing string buffer S
928 procedure FFA_FZ_To_Hex_String(N : in FZ; S : out String)
929 renames FZ_IO.FZ_To_Hex_String;
930
931 ----------------------------------------------------------------------------
932 --- Comparison Predicate Operations on FZ
933 ----------------------------------------------------------------------------
934
935 -- 1 iff X == Y (branch-free); else 0
936 function FFA_FZ_EqP(X : in FZ; Y: in FZ) return WBool
937 renames FZ_Cmp.FZ_EqP;
938
939 -- 1 iff X < Y (branch-free); else 0
940 function FFA_FZ_LessThanP(X : in FZ; Y : in FZ) return WBool
941 renames FZ_Cmp.FZ_LessThanP;
942
943 -- 1 iff X > Y (branch-free); else 0
944 function FFA_FZ_GreaterThanP(X : in FZ; Y : in FZ) return WBool
945 renames FZ_Cmp.FZ_GreaterThanP;
946
947 ----------------------------------------------------------------------------
948 --- Fundamental Predicate Operations on FZ
949 ----------------------------------------------------------------------------
950
951 -- 1 iff N == 0 (branch-free); else 0
952 function FFA_FZ_ZeroP(N : in FZ) return WBool
953 renames FZ_Pred.FZ_ZeroP;
954
955 -- 1 iff N != 0 (branch-free); else 0
956 function FFA_FZ_NZeroP(N : in FZ) return WBool
957 renames FZ_Pred.FZ_NZeroP;
958
959 -- 1 iff N is odd
960 function FFA_FZ_OddP(N : in FZ) return WBool
961 renames FZ_Pred.FZ_OddP;
962
963 ----------------------------------------------------------------------------
964 --- Bitwise Operations on FZ
965 ----------------------------------------------------------------------------
966
967 -- Result := X & Y
968 procedure FFA_FZ_And(X : in FZ; Y : in FZ; Result : out FZ)
969 with Pre => X'Length = Y'Length and X'Length = Result'Length;
970
971 -- N := N & W, W is a Word
972 procedure FFA_FZ_And_W(N : in out FZ; W : in Word)
973 renames FZ_BitOp.FZ_And_W;
974
975 -- Result := X | Y
976 procedure FFA_FZ_Or(X : in FZ; Y : in FZ; Result : out FZ)
977 with Pre => X'Length = Y'Length and X'Length = Result'Length;
978
979 -- N := N | W, W is a Word
980 procedure FFA_FZ_Or_W(N : in out FZ; W : in Word)
981 renames FZ_BitOp.FZ_Or_W;
982
983 -- Result := X ^ Y
984 procedure FFA_FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ)
985 with Pre => X'Length = Y'Length and X'Length = Result'Length;
986
987 -- N := N ^ W, W is a Word
988 procedure FFA_FZ_Xor_W(N : in out FZ; W : in Word)
989 renames FZ_BitOp.FZ_Xor_W;
990
991 -- NotN := ~N ('ones complement')
992 procedure FFA_FZ_Not(N : in FZ; NotN : out FZ)
993 with Pre => N'Length = NotN'Length;
994
995 ----------------------------------------------------------------------------
996 --- Basic Arithmetic on FZ
997 ----------------------------------------------------------------------------
998
999 -- Sum := X + Y; Overflow := Carry
1000 procedure FFA_FZ_Add(X : in FZ;
1001 Y : in FZ;
1002 Sum : out FZ;
1003 Overflow : out WBool)
1004 with Pre => X'Length = Y'Length and X'Length = Sum'Length;
1005
1006 -- Difference := X - Y; Underflow := Borrow
1007 procedure FFA_FZ_Subtract(X : in FZ;
1008 Y : in FZ;
1009 Difference : out FZ;
1010 Underflow : out WBool)
1011 with Pre => X'Length = Y'Length and X'Length = Difference'Length;
1012
1013 ----------------------------------------------------------------------------
1014 --- Division on FZ
1015 ----------------------------------------------------------------------------
1016
1017 -- Dividend is divided by Divisor, producing Quotient and Remainder.
1018 -- WARNING: NO div0 test here! Caller must test.
1019 procedure FFA_FZ_IDiv(Dividend : in FZ;
1020 Divisor : in FZ;
1021 Quotient : out FZ;
1022 Remainder : out FZ)
1023 renames FZ_Divis.FZ_IDiv;
1024
1025 -- Exactly same thing as IDiv, but keep only the Quotient
1026 procedure FFA_FZ_Div(Dividend : in FZ;
1027 Divisor : in FZ;
1028 Quotient : out FZ)
1029 renames FZ_Divis.FZ_Div;
1030
1031 -- Modulus.
1032 procedure FFA_FZ_Mod(Dividend : in FZ;
1033 Divisor : in FZ;
1034 Remainder : out FZ)
1035 renames FZ_Divis.FZ_Mod;
1036
1037 ----------------------------------------------------------------------------
1038 --- Multiplication on FZ
1039 ----------------------------------------------------------------------------
1040
1041 -- Multiplier. Preserves the inputs.
1042 procedure FFA_FZ_Multiply(X : in FZ;
1043 Y : in FZ;
1044 XY_Lo : out FZ;
1045 XY_Hi : out FZ)
1046 with Pre => X'Length = Y'Length and
1047 XY_Lo'Length = XY_Hi'Length and
1048 XY_Lo'Length = ((X'Length + Y'Length) / 2);
1049
1050 ----------------------------------------------------------------------------
1051 --- Modular Operations on FZ
1052 ----------------------------------------------------------------------------
1053
1054 -- Modular Multiply: Product := X*Y mod Modulus
1055 procedure FFA_FZ_Modular_Multiply(X : in FZ;
1056 Y : in FZ;
1057 Modulus : in FZ;
1058 Product : out FZ)
1059 renames FZ_ModEx.FZ_Mod_Mul;
1060
1061 -- Modular Exponent: Result := Base^Exponent mod Modulus
1062 procedure FFA_FZ_Modular_Exponentiate(Base : in FZ;
1063 Exponent : in FZ;
1064 Modulus : in FZ;
1065 Result : out FZ)
1066 renames FZ_ModEx.FZ_Mod_Exp;
1067
1068 end FFA;
- 92D0220A48F6753FB699220DB8EBA867B4F4354291C3E4EBD6B3048982524E93F82356D40B8BF2371F7C6768545FE2EE0E531EBD70144CBD8213A6D8C84E727E(54 . 7)(54 . 8)
1073 when "release" =>
1074 for Switches ("Ada")
1075 use ("-O2", "-fdump-scos", "-gnata", "-fstack-check",
1076 "-fdata-sections", "-ffunction-sections",
1077 "-gnatyd", "-gnatym",
1078 "-fdata-sections", "-ffunction-sections", "-gnatwr", "-gnatw.d",
1079 "-gnatec=" & FFA'Project_Dir & "restrict.adc");
1080 end case;
1081 end Compiler;
- A207AFCFF3ED13797843CA0F376E2E78404E8A2D695E06F4C8C1D3346FDAFB75B6BD507AEEB85CFD93D9CFF955FCD312C60BAFA2AA869EAB10500BBD6CB800EE(42 . 7)(42 . 6)- 438A4D222ED5F2FDFF3F3E4B5E5B5E1BC0017635F455658FE655F9706D77516468DBF3F9086C5BB0EA4E1911F68D6FDB858E0C3C276586028E24654704869428
1086 end loop;
1087 Overflow := Carry;
1088 end FZ_Add_D;
1089 pragma Inline_Always(FZ_Add_D);
1090
1091
1092 -- Destructive Add: X := X + W; Overflow := Carry
(62 . 7)(61 . 6)
1094 end loop;
1095 Overflow := Carry;
1096 end FZ_Add_D_W;
1097 pragma Inline_Always(FZ_Add_D_W);
1098
1099
1100 -- Sum := X + Y; Overflow := Carry
(84 . 7)(82 . 6)
1102 end loop;
1103 Overflow := Carry;
1104 end FZ_Add;
1105 pragma Inline_Always(FZ_Add);
1106
1107
1108 -- Gate = 1: Sum := X + Y; Overflow := Carry
(109 . 7)(106 . 6)
1110 end loop;
1111 Overflow := Carry;
1112 end FZ_Add_Gated_O;
1113 pragma Inline_Always(FZ_Add_Gated_O);
1114
1115
1116 -- Same as FZ_Add_Gated_O, but without Overflow output
(122 . 7)(118 . 6)
1118 begin
1119 FZ_Add_Gated_O(X, Y, Gate, Sum, Overflow);
1120 end FZ_Add_Gated;
1121 pragma Inline_Always(FZ_Add_Gated);
1122
1123
1124 -- Difference := X - Y; Underflow := Borrow
(144 . 7)(139 . 6)
1126 end loop;
1127 Underflow := Borrow;
1128 end FZ_Sub;
1129 pragma Inline_Always(FZ_Sub);
1130
1131
1132 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
(164 . 7)(158 . 6)
1134 end loop;
1135
1136 end FZ_Not_Cond_D;
1137 pragma Inline_Always(FZ_Not_Cond_D);
1138
1139
1140 -- Subtractor that gets absolute value if underflowed, in const. time
(188 . 7)(181 . 6)
1142 FZ_Add_D_W(Difference, Underflow, O);
1143
1144 end FZ_Sub_Abs;
1145 pragma Inline_Always(FZ_Sub_Abs);
1146
1147
1148 end FZ_Arith;
(31 . 19)(31 . 20)- 868D35F9327D08B5CBEC9F573FBFD453BD3639E2B1CB93BA0C8264591C396E920883132037716798AB607A3CB0AC6A95AD819D8B39180693BD2B768B666AC6EE
1153 Y : in FZ;
1154 Overflow : out WBool;
1155 OF_In : in WBool := 0);
1156 pragma Precondition(X'Length = Y'Length);
1157 pragma Inline_Always(FZ_Add_D);
1158
1159 -- Destructive Add: X := X + W; Overflow := Carry
1160 procedure FZ_Add_D_W(X : in out FZ;
1161 W : in Word;
1162 Overflow : out WBool);
1163 pragma Inline_Always(FZ_Add_D_W);
1164
1165 -- Sum := X + Y; Overflow := Carry
1166 procedure FZ_Add(X : in FZ;
1167 Y : in FZ;
1168 Sum : out FZ;
1169 Overflow : out WBool);
1170 pragma Precondition(X'Length = Y'Length and X'Length = Sum'Length);
1171 pragma Inline_Always(FZ_Add);
1172
1173 -- Gate = 1: Sum := X + Y; Overflow := Carry
1174 -- Gate = 0: Sum := X; Overflow := 0
(52 . 31)(53 . 32)
1176 Gate : in WBool;
1177 Sum : out FZ;
1178 Overflow : out WBool);
1179 pragma Precondition(X'Length = Y'Length and X'Length = Sum'Length);
1180 pragma Inline_Always(FZ_Add_Gated_O);
1181
1182 -- Same as FZ_Add_Gated_O, but without Overflow output
1183 procedure FZ_Add_Gated(X : in FZ;
1184 Y : in FZ;
1185 Gate : in WBool;
1186 Sum : out FZ);
1187 pragma Precondition(X'Length = Y'Length and X'Length = Sum'Length);
1188 pragma Inline_Always(FZ_Add_Gated);
1189
1190 -- Difference := X - Y; Underflow := Borrow
1191 procedure FZ_Sub(X : in FZ;
1192 Y : in FZ;
1193 Difference : out FZ;
1194 Underflow : out WBool);
1195 pragma Precondition(X'Length = Y'Length and X'Length = Difference'Length);
1196 pragma Inline_Always(FZ_Sub);
1197
1198 -- Destructive: If Cond is 1, NotN := ~N; otherwise NotN := N.
1199 procedure FZ_Not_Cond_D(N : in out FZ;
1200 Cond : in WBool);
1201 pragma Inline_Always(FZ_Not_Cond_D);
1202
1203 -- Subtractor that gets absolute value if underflowed, in const. time
1204 procedure FZ_Sub_Abs(X : in FZ;
1205 Y : in FZ;
1206 Difference : out FZ;
1207 Underflow : out WBool);
1208 pragma Precondition(X'Length = Y'Length and X'Length = Difference'Length);
1209 pragma Inline_Always(FZ_Sub_Abs);
1210
1211 end FZ_Arith;
(31 . 7)(31 . 6)- C03435B8B09D144BE64C1E1FFF0AA4626693D28AE15D30EF59293F215A8B135A24B28030E22835599775D117FB181E44FA9178423AACF1F641EFAC0392DC6AB1
1216 begin
1217 return N'Length * Words.Bitness;
1218 end FZ_Bitness;
1219 pragma Inline_Always(FZ_Bitness);
1220
1221
1222 -- N := 0
(39 . 7)(38 . 6)
1224 begin
1225 N := (others => 0);
1226 end FZ_Clear;
1227 pragma Inline_Always(FZ_Clear);
1228
1229
1230 -- Set given FZ to a given truth value
(48 . 7)(46 . 6)
1232 FZ_Clear(N);
1233 FZ_Set_Head(N, V);
1234 end WBool_To_FZ;
1235 pragma Inline_Always(WBool_To_FZ);
1236
1237
1238 -- First word of N := Source
(56 . 7)(53 . 6)
1240 begin
1241 N(N'First) := Source;
1242 end FZ_Set_Head;
1243 pragma Inline_Always(FZ_Set_Head);
1244
1245
1246 -- First word of N
(64 . 7)(60 . 6)
1248 begin
1249 return N(N'First);
1250 end FZ_Get_Head;
1251 pragma Inline_Always(FZ_Get_Head);
1252
1253
1254 -- Exchange X and Y
(75 . 7)(70 . 6)
1256 X := Y;
1257 Y := T;
1258 end FZ_Swap;
1259 pragma Inline_Always(FZ_Swap);
1260
1261
1262 -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y
(85 . 6)(79 . 5)
1264 Result(i) := W_Mux(X(i), Y(i), Sel);
1265 end loop;
1266 end FZ_Mux;
1267 pragma Inline_Always(FZ_Mux);
1268
1269 end FZ_Basic;
(17 . 7)(17 . 7)- E392C4D077A2D9169133060244FB84669A4C990CEEA872AEF112A85421F233478363BC4D560547D5D53FDDB689C1BE3427497CD1B59401CFB3F4F3F7834A2021
1274 ------------------------------------------------------------------------------
1275 ------------------------------------------------------------------------------
1276
1277 with Words; use Words;
1278 with Words; use Words;
1279 with FZ_Type; use FZ_Type;
1280
1281
(27 . 25)(27 . 30)
1283
1284 -- Determine the Bitness of N
1285 function FZ_Bitness(N : in FZ) return Bit_Count;
1286 pragma Inline_Always(FZ_Bitness);
1287
1288 -- N := 0
1289 procedure FZ_Clear(N : out FZ);
1290 pragma Inline_Always(FZ_Clear);
1291
1292 -- Set given FZ to a given truth value
1293 procedure WBool_To_FZ(V : in WBool; N : out FZ);
1294 pragma Inline_Always(WBool_To_FZ);
1295
1296 -- First word of N := Source
1297 procedure FZ_Set_Head(N : out FZ; Source : in Word);
1298 pragma Inline_Always(FZ_Set_Head);
1299
1300 -- First word of N
1301 function FZ_Get_Head(N : in FZ) return Word;
1302 pragma Inline_Always(FZ_Get_Head);
1303
1304 -- Exchange X and Y
1305 procedure FZ_Swap(X : in out FZ; Y : in out FZ);
1306 pragma Precondition(X'Length = Y'Length);
1307 pragma Inline_Always(FZ_Swap);
1308
1309 -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y
1310 procedure FZ_Mux(X : in FZ; Y : in FZ; Result : out FZ; Sel : in WBool);
1311 pragma Precondition(X'Length = Y'Length and X'Length = Result'Length);
1312 pragma Inline_Always(FZ_Mux);
1313
1314 end FZ_Basic;
(26 . 7)(26 . 6)- 6C169EA38EFA2E6E30DB85131AB64CF5E71BCABCDFA4722B2F019C8BEBB1CABB5A2D8FC192703607B2A129CF54E36C2D136A68C3F6B13792CE138BCEE6B6BE52
1319 Result(i) := X(i) and Y(i);
1320 end loop;
1321 end FZ_And;
1322 pragma Inline_Always(FZ_And);
1323
1324
1325 -- N := N & W, W is a word
(34 . 7)(33 . 6)
1327 begin
1328 N(N'First) := N(N'First) and W;
1329 end FZ_And_W;
1330 pragma Inline_Always(FZ_And_W);
1331
1332
1333 -- Result := X | Y
(44 . 7)(42 . 6)
1335 Result(i) := X(i) or Y(i);
1336 end loop;
1337 end FZ_Or;
1338 pragma Inline_Always(FZ_Or);
1339
1340
1341 -- N := N | W, W is a word
(52 . 7)(49 . 6)
1343 begin
1344 N(N'First) := N(N'First) or W;
1345 end FZ_Or_W;
1346 pragma Inline_Always(FZ_Or_W);
1347
1348
1349 -- Result := X ^ Y
(62 . 7)(58 . 6)
1351 Result(i) := X(i) xor Y(i);
1352 end loop;
1353 end FZ_Xor;
1354 pragma Inline_Always(FZ_Xor);
1355
1356
1357 -- N := N ^ W, W is a word
(70 . 7)(65 . 6)
1359 begin
1360 N(N'First) := N(N'First) xor W;
1361 end FZ_Xor_W;
1362 pragma Inline_Always(FZ_Xor_W);
1363
1364
1365 -- NotN := ~N
(81 . 6)(75 . 5)
1367 NotN(i) := not N(i);
1368 end loop;
1369 end FZ_Not;
1370 pragma Inline_Always(FZ_Not);
1371
1372 end FZ_BitOp;
(27 . 27)(27 . 30)
1377
1378 -- Result := X & Y
1379 procedure FZ_And(X : in FZ; Y : in FZ; Result : out FZ);
1380 pragma Precondition(X'Length = Y'Length and X'Length = Result'Length);
1381 pragma Inline_Always(FZ_And);
1382
1383 -- N := N & W, W is a word
1384 procedure FZ_And_W(N : in out FZ; W : in Word);
1385 pragma Inline_Always(FZ_And_W);
1386
1387 -- Result := X | Y
1388 procedure FZ_Or(X : in FZ; Y : in FZ; Result : out FZ);
1389 pragma Precondition(X'Length = Y'Length and X'Length = Result'Length);
1390 pragma Inline_Always(FZ_Or);
1391
1392 -- N := N | W, W is a word
1393 procedure FZ_Or_W(N : in out FZ; W : in Word);
1394 pragma Inline_Always(FZ_Or_W);
1395
1396 -- Result := X ^ Y
1397 procedure FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ);
1398 pragma Precondition(X'Length = Y'Length and X'Length = Result'Length);
1399 pragma Inline_Always(FZ_Xor);
1400
1401 -- N := N ^ W, W is a word
1402 procedure FZ_Xor_W(N : in out FZ; W : in Word);
1403 pragma Inline_Always(FZ_Xor_W);
1404
1405 -- NotN := ~N
1406 procedure FZ_Not(N : in FZ; NotN : out FZ);
1407 pragma Precondition(N'Length = NotN'Length);
1408 pragma Inline_Always(FZ_Not);
1409
1410 end FZ_BitOp;
- 7BC2AC9CD0D23497E2E2DE528D4CBEFCBEC274B511B2642369218BB8A00F3663B32F70040BEDFCB5A1F8CE2D5B9A026A10AE106FD2C370D1369188122FCB7BE9(36 . 7)(36 . 6)- 9E52F3E150784CBFFB8E31B93FA3EDB380EDB86FB0106F1D34CF1A66964C1A1CA44514695B061FD40B4B1F37023CD131021D65C59295ED09C5265789F386CA73
1415 end loop;
1416 return A;
1417 end FZ_EqP;
1418 pragma Inline_Always(FZ_EqP);
1419
1420
1421 -- 1 iff X < Y (branch-free); else 0
(47 . 7)(46 . 6)
1423 FZ_Sub(X, Y, Scratch, Borrow);
1424 return Borrow;
1425 end FZ_LessThanP;
1426 pragma Inline_Always(FZ_LessThanP);
1427
1428
1429 -- 1 iff X > Y (branch-free); else 0
(58 . 6)(56 . 5)
1431 FZ_Sub(Y, X, Scratch, Borrow);
1432 return Borrow;
1433 end FZ_GreaterThanP;
1434 pragma Inline_Always(FZ_GreaterThanP);
1435
1436 end FZ_Cmp;
(30 . 15)(30 . 15)
1441 -------------------------------------------
1442
1443 -- 1 iff X == Y (branch-free); else 0
1444 function FZ_EqP(X : in FZ; Y: in FZ) return WBool;
1445 pragma Precondition(X'Length = Y'Length);
1446 function FZ_EqP(X : in FZ; Y: in FZ) return WBool
1447 with Pre => X'Length = Y'Length;
1448
1449 -- 1 iff X < Y (branch-free); else 0
1450 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool;
1451 pragma Precondition(X'Length = Y'Length);
1452 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool
1453 with Pre => X'Length = Y'Length;
1454
1455 -- 1 iff X > Y (branch-free); else 0
1456 function FZ_GreaterThanP(X : in FZ; Y : in FZ) return WBool;
1457 pragma Precondition(X'Length = Y'Length);
1458 function FZ_GreaterThanP(X : in FZ; Y : in FZ) return WBool
1459 with Pre => X'Length = Y'Length;
1460
1461 end FZ_Cmp;
- 0934AF47E0703889B29836CA23503EDDFBDEDF1548FB43315E76A2651C88D9F5742A1D957A2A6D6052AC77F2E260D380131149289F30EA11DCE018A9C0342285(68 . 8)(68 . 6)- BA309013077BBF7E96260BB5F45AB8AE14AA3A520265D1EC7880E7C8F4DB24BA8628766465BA214D9F63BC02E44E7588B6ECC26E2CB376C6D2C7B85ED5314882
1466 Remainder := R; -- Output the Remainder.
1467
1468 end FZ_IDiv;
1469 pragma Inline_Always(FZ_IDiv);
1470
1471
1472 -- Exactly same thing as IDiv, but keep only the Quotient
1473 procedure FZ_Div(Dividend : in FZ;
(80 . 8)(78 . 6)
1475 begin
1476 FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
1477 end FZ_Div;
1478 pragma Inline_Always(FZ_Div);
1479
1480
1481 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
1482 procedure FZ_Mod(Dividend : in FZ;
(168 . 7)(164 . 5)
1484 Remainder := R;
1485
1486 end FZ_Mod;
1487 pragma Inline_Always(FZ_Mod);
1488
1489
1490 end FZ_Divis;
(29 . 23)(29 . 23)
1495 procedure FZ_IDiv(Dividend : in FZ;
1496 Divisor : in FZ;
1497 Quotient : out FZ;
1498 Remainder : out FZ);
1499 pragma Precondition(Dividend'Length = Divisor'Length and
1500 Quotient'Length = Remainder'Length and
1501 Dividend'Length = Quotient'Length);
1502 Remainder : out FZ)
1503 with Pre => Dividend'Length = Divisor'Length and
1504 Quotient'Length = Remainder'Length and
1505 Dividend'Length = Quotient'Length;
1506
1507 -- Exactly same thing as IDiv, but keep only the Quotient
1508 procedure FZ_Div(Dividend : in FZ;
1509 Divisor : in FZ;
1510 Quotient : out FZ);
1511 pragma Precondition(Dividend'Length = Divisor'Length and
1512 Dividend'Length = Quotient'Length);
1513 Quotient : out FZ)
1514 with Pre => Dividend'Length = Divisor'Length and
1515 Dividend'Length = Quotient'Length;
1516
1517 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
1518 procedure FZ_Mod(Dividend : in FZ;
1519 Divisor : in FZ;
1520 Remainder : out FZ);
1521 pragma Precondition(Dividend'Length >= Divisor'Length and
1522 Divisor'Length = Remainder'Length);
1523 Remainder : out FZ)
1524 with Pre => Dividend'Length >= Divisor'Length and
1525 Divisor'Length = Remainder'Length;
1526
1527 end FZ_Divis;
-(0 . 0)(1 . 108)
1532 ------------------------------------------------------------------------------
1533 ------------------------------------------------------------------------------
1534 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1535 -- --
1536 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1537 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1538 -- --
1539 -- You do not have, nor can you ever acquire the right to use, copy or --
1540 -- distribute this software ; Should you use this software for any purpose, --
1541 -- or copy and distribute it to anyone or in any manner, you are breaking --
1542 -- the laws of whatever soi-disant jurisdiction, and you promise to --
1543 -- continue doing so for the indefinite future. In any case, please --
1544 -- always : read and understand any software ; verify any PGP signatures --
1545 -- that you use - for any purpose. --
1546 -- --
1547 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
1548 ------------------------------------------------------------------------------
1549 ------------------------------------------------------------------------------
1550
1551 with W_Pred; use W_Pred;
1552 with W_Shifts; use W_Shifts;
1553 with FZ_BitOp; use FZ_BitOp;
1554 with FZ_Shift; use FZ_Shift;
1555
1556
1557 package body FZ_IO is
1558
1559 -- Expand FZ N by nibble D, and determine whether this operation overflowed
1560 procedure FZ_Insert_Bottom_Nibble(N : in out FZ;
1561 D : in Nibble;
1562 Overflow : out WBool) is
1563
1564 -- The overflow, if any, from shifting N in-place leftward by 4 bits
1565 Shifted_N_Overflow : Word := 0;
1566
1567 begin
1568 -- Make room in N for one additional hex digit (i.e. multiply N by 16)
1569 FZ_ShiftLeft_O(N => N,
1570 ShiftedN => N,
1571 Count => 4,
1572 Overflow => Shifted_N_Overflow);
1573
1574 -- Place the new digit into the now-vacated four bits at the bottom of N.
1575 FZ_Or_W(N, D);
1576
1577 -- Record whether the above operation overflowed N:
1578 Overflow := W_NZeroP(Shifted_N_Overflow);
1579
1580 end FZ_Insert_Bottom_Nibble;
1581
1582
1583 -- Determine the number of ASCII characters required to represent N
1584 function FZ_ASCII_Length(N : in FZ) return Char_Count is
1585 begin
1586 return N'Length * Nibbleness;
1587 end FZ_ASCII_Length;
1588
1589
1590 -- Write an ASCII hex representation of N into existing string buffer S
1591 procedure FZ_To_Hex_String(N : in FZ; S : out String) is
1592
1593 -- Indices into the string S (note, String always indexes from 1)
1594 subtype SiRange is Natural range S'First .. S'Last;
1595
1596 -- Position of current character in S being written
1597 Si : SiRange; -- Walks from 1 to the string length of S
1598
1599 begin
1600
1601 -- Step through all indices of N, regardless of how it was indexed:
1602 for i in 0 .. Word_Index(N'Length - 1) loop
1603 declare
1604
1605 -- Index of current Word, walks from ~top~ Word of N to ~bottom~
1606 Wi : constant Word_Index := N'Last - i;
1607
1608 -- Currently-selected Word of N
1609 W : Word := N(Wi);
1610
1611 begin
1612
1613 -- For each nibble in the Word:
1614 for j in 1 .. Nibbleness loop
1615
1616 -- Current position in S that is to be written
1617 Si := (Natural(i) * Nibbleness) + j;
1618
1619 -- Rotate the top nibble of W into the bottom nibble.
1620 W := Rotate_Left(W, 4);
1621
1622 -- Write the ASCII representation of the bottom nibble.
1623 S(Si) := HexDigs(Natural(W and 16#F#));
1624
1625 end loop;
1626
1627 -- Barring cosmic ray, W will have rotated to its initial value
1628 pragma Assert(W = N(Wi));
1629
1630 end;
1631
1632 end loop;
1633
1634 -- Barring cosmic ray, the last char written was to the final pos in S,
1635 pragma Assert(Si = SiRange'Last); -- as S is mandatorily exactly-sized.
1636
1637 end FZ_To_Hex_String;
1638
1639 end FZ_IO;
-(0 . 0)(1 . 49)
1644 ------------------------------------------------------------------------------
1645 ------------------------------------------------------------------------------
1646 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
1647 -- --
1648 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
1649 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
1650 -- --
1651 -- You do not have, nor can you ever acquire the right to use, copy or --
1652 -- distribute this software ; Should you use this software for any purpose, --
1653 -- or copy and distribute it to anyone or in any manner, you are breaking --
1654 -- the laws of whatever soi-disant jurisdiction, and you promise to --
1655 -- continue doing so for the indefinite future. In any case, please --
1656 -- always : read and understand any software ; verify any PGP signatures --
1657 -- that you use - for any purpose. --
1658 -- --
1659 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
1660 ------------------------------------------------------------------------------
1661 ------------------------------------------------------------------------------
1662
1663 with Words; use Words;
1664 with FZ_Type; use FZ_Type;
1665 with FZ_Lim; use FZ_Lim;
1666
1667
1668 package FZ_IO is
1669
1670 pragma Pure;
1671
1672 -- Expand FZ N by nibble D, and determine whether this operation overflowed
1673 procedure FZ_Insert_Bottom_Nibble(N : in out FZ;
1674 D : in Nibble;
1675 Overflow : out WBool);
1676
1677 -- A count of ASCII chars representing a humanized FZ:
1678 subtype Char_Count is
1679 Positive range Nibbleness * FZ_Minimal_Wordness .. Positive'Last;
1680
1681 -- Determine the number of ASCII characters required to represent N
1682 function FZ_ASCII_Length(N : in FZ) return Char_Count;
1683 pragma Inline_Always(FZ_ASCII_Length);
1684
1685 -- Hex Digits (currently used only in FZ_To_Hex_String)
1686 HexDigs : constant array(0 .. 15) of Character := "0123456789ABCDEF";
1687
1688 -- Write an ASCII hex representation of N into existing string buffer S
1689 procedure FZ_To_Hex_String(N : in FZ; S : out String)
1690 with Pre => S'Length = FZ_ASCII_Length(N);
1691
1692 end FZ_IO;
- A447E0654CEF6958CB6C0B03094FE8B900B6EC0CDA812355565C1972051973398C8390D968EAF5719D8B0B97D4D5F0B0D503E906645E020C97D479169429F332(17 . 11)(17 . 16)
1697 ------------------------------------------------------------------------------
1698 ------------------------------------------------------------------------------
1699
1700 with Words; use Words;
1701
1702
1703 package FZ_Lim is
1704
1705 pragma Pure;
1706
1707 FZ_Minimal_Bitness : constant Positive := 256;
1708 FZ_Minimal_Bitness : constant Positive := 256;
1709
1710 FZ_Minimal_Wordness : constant Positive := FZ_Minimal_Bitness / Bitness;
1711
1712 FZ_Validity_Rule_Doc : constant String
1713 := "Must be greater than or equal to 256, and a power of 2.";
- 1C3D48C34543B5C044B9713E23D424C02ECF8BF9B914F3504B3BB2C50EA610865A4343164A6E22256EA80E6FB9A386EBCF13E67F1DF76B954C2114B91E22B01D(45 . 13)(45 . 12)- 7271E109FDFAD61859FABD2CCCACA71A7BAF037467E29DB9B82FF29ECF68FFAEAC3EBEBDFF7AF690087ACC97F3106A4C1F74ECB82E0D46A206A3318A71018315
1718 begin
1719
1720 -- XY_Lo:XY_Hi := X * Y
1721 FZ_Mult(X, Y, XY_Lo, XY_Hi);
1722 FZ_Multiply_Buffered(X, Y, XY_Lo, XY_Hi);
1723
1724 -- Product := XY mod M
1725 FZ_Mod(XY, Modulus, Product);
1726
1727 end FZ_Mod_Mul;
1728 pragma Inline_Always(FZ_Mod_Mul);
1729
1730
1731 -- Modular Exponent: Result := Base^Exponent mod Modulus
(99 . 6)(98 . 5)
1733 Result := R;
1734
1735 end FZ_Mod_Exp;
1736 pragma Inline_Always(FZ_Mod_Exp);
1737
1738 end FZ_ModEx;
(28 . 18)(28 . 18)
1743 procedure FZ_Mod_Mul(X : in FZ;
1744 Y : in FZ;
1745 Modulus : in FZ;
1746 Product : out FZ);
1747 pragma Precondition(X'Length = Y'Length and
1748 Modulus'Length = X'Length and
1749 Product'Length = Modulus'Length);
1750 Product : out FZ)
1751 with Pre => X'Length = Y'Length and
1752 Modulus'Length = X'Length and
1753 Product'Length = Modulus'Length;
1754
1755 -- Modular Exponent: Result := Base^Exponent mod Modulus
1756 procedure FZ_Mod_Exp(Base : in FZ;
1757 Exponent : in FZ;
1758 Modulus : in FZ;
1759 Result : out FZ);
1760 pragma Precondition(Base'Length = Exponent'Length and
1761 Base'Length = Result'Length and
1762 Base'Length = Modulus'Length);
1763 Result : out FZ) with
1764 Pre => Base'Length = Exponent'Length and
1765 Base'Length = Result'Length and
1766 Base'Length = Modulus'Length;
1767
1768 end FZ_ModEx;
- 98A9315BADAC1530D96E214873BE3EFCED853C4A1D922CA1D707D93E62993ADDFFE906A64525204C9FB83B38C9AC04A170711D8D10D33D3EE2699953DDED18B9(113 . 7)(113 . 6)- 79E6526E650E729CE3925E841085F515E2D57F4B1B629AF5F39F9A0EEF61AAA30A4C67BFC40D222FB4919B22BCBD62D238F2CA36500163AA02D40A8F8FA5672B
1773 XY(XY'Last) := A0;
1774
1775 end FZ_Mul_Comba;
1776 pragma Inline_Always(FZ_Mul_Comba);
1777
1778
1779 -- Karatsuba's Multiplier. (CAUTION: UNBUFFERED)
(173 . 10)(172 . 10)
1781 begin
1782
1783 -- Recurse: LL := XL * YL
1784 FZ_Multiply(XLo, YLo, LL);
1785 FZ_Multiply_Unbuffered(XLo, YLo, LL);
1786
1787 -- Recurse: HH := XH * YH
1788 FZ_Multiply(XHi, YHi, HH);
1789 FZ_Multiply_Unbuffered(XHi, YHi, HH);
1790
1791 -- Dx := |XL - XH| , Cx := Borrow (i.e. 1 iff XL < XH)
1792 FZ_Sub_Abs(X => XLo, Y => XHi, Difference => Dx, Underflow => Cx);
(185 . 7)(184 . 7)
1794 FZ_Sub_Abs(X => YLo, Y => YHi, Difference => Dy, Underflow => Cy);
1795
1796 -- Recurse: DD := Dx * Dy
1797 FZ_Multiply(Dx, Dy, DD);
1798 FZ_Multiply_Unbuffered(Dx, Dy, DD);
1799
1800 -- Whether (XL - XH)(YL - YH) is positive, and so DD must be subtracted:
1801 DD_Sub := 1 - (Cx xor Cy);
(227 . 9)(226 . 9)
1803
1804
1805 -- Multiplier. (CAUTION: UNBUFFERED)
1806 procedure FZ_Multiply(X : in FZ;
1807 Y : in FZ;
1808 XY : out FZ) is
1809 procedure FZ_Multiply_Unbuffered(X : in FZ;
1810 Y : in FZ;
1811 XY : out FZ) is
1812
1813 -- The length of either multiplicand
1814 L : constant Word_Count := X'Length;
(248 . 27)(247 . 25)
1816
1817 end if;
1818
1819 end FZ_Multiply;
1820 pragma Inline_Always(FZ_Multiply);
1821 end FZ_Multiply_Unbuffered;
1822
1823
1824 -- Multiplier. Preserves the inputs.
1825 procedure FZ_Mult(X : in FZ;
1826 Y : in FZ;
1827 XY_Lo : out FZ;
1828 XY_Hi : out FZ) is
1829 procedure FZ_Multiply_Buffered(X : in FZ;
1830 Y : in FZ;
1831 XY_Lo : out FZ;
1832 XY_Hi : out FZ) is
1833
1834 -- Product buffer.
1835 P : FZ(1 .. 2 * X'Length);
1836
1837 begin
1838
1839 FZ_Multiply(X, Y, P);
1840 FZ_Multiply_Unbuffered(X, Y, P);
1841
1842 XY_Lo := P(P'First .. P'First + X'Length - 1);
1843 XY_Hi := P(P'First + X'Length .. P'Last);
1844
1845 end FZ_Mult;
1846 pragma Inline_Always(FZ_Mult);
1847 end FZ_Multiply_Buffered;
1848
1849 end FZ_Mul;
(24 . 39)(24 . 35)
1854
1855 pragma Pure;
1856
1857 -- Karatsuba Threshhold - at or below this many words, we use Comba mult.
1858 -- Karatsuba Threshhold - at or below this many Words, we use Comba mult.
1859 Karatsuba_Thresh : constant Indices := 8;
1860
1861 -- Multiply. (CAUTION: UNBUFFERED)
1862 procedure FZ_Multiply(X : in FZ;
1863 Y : in FZ;
1864 XY : out FZ);
1865 pragma Precondition(X'Length = Y'Length and
1866 XY'Length = (X'Length + Y'Length));
1867 procedure FZ_Multiply_Unbuffered(X : in FZ;
1868 Y : in FZ;
1869 XY : out FZ);
1870 pragma Inline_Always(FZ_Multiply_Unbuffered);
1871
1872 -- Comba's multiplier. (CAUTION: UNBUFFERED)
1873 procedure FZ_Mul_Comba(X : in FZ;
1874 Y : in FZ;
1875 XY : out FZ);
1876 pragma Precondition(X'Length = Y'Length and
1877 XY'Length = (X'Length + Y'Length));
1878 pragma Inline_Always(FZ_Mul_Comba);
1879
1880 -- Karatsuba's Multiplier. (CAUTION: UNBUFFERED)
1881 procedure Mul_Karatsuba(X : in FZ;
1882 Y : in FZ;
1883 XY : out FZ);
1884 pragma Precondition(X'Length = Y'Length and
1885 XY'Length = (X'Length + Y'Length) and
1886 X'Length mod 2 = 0);
1887 XY : out FZ)
1888 with Pre => X'Length = Y'Length and
1889 XY'Length = (X'Length + Y'Length) and
1890 X'Length mod 2 = 0;
1891 -- CAUTION: Inlining prohibited for Mul_Karatsuba !
1892
1893 -- Multiplier. Preserves the inputs.
1894 procedure FZ_Mult(X : in FZ;
1895 Y : in FZ;
1896 XY_Lo : out FZ;
1897 XY_Hi : out FZ);
1898 pragma Precondition(X'Length = Y'Length and
1899 XY_Lo'Length = XY_Hi'Length and
1900 XY_Lo'Length = ((X'Length + Y'Length) / 2));
1901 procedure FZ_Multiply_Buffered(X : in FZ;
1902 Y : in FZ;
1903 XY_Lo : out FZ;
1904 XY_Hi : out FZ);
1905 pragma Inline_Always(FZ_Multiply_Buffered);
1906
1907 end FZ_Mul;
- 512C0F2246AD097087F88A96449FC5A9122F70D069081ECC6A058D17B152EA908F34C834D10F696467CD9321ED656556EC4F62EFB0CB37D7307AE15EDD2CD4A9(35 . 7)(35 . 6)- C2CC1622F1B54EC8BD19FA3BA7E5FB70C78E5E0E5072F308EBBFD8DFCC8F479D6CCCC6C7D0DCF1FF0310C035E5FF4CA790C3B5F9C181978F536C605BF6F53C63
1912 end loop;
1913 return A;
1914 end FZ_ZeroP;
1915 pragma Inline_Always(FZ_ZeroP);
1916
1917
1918 -- 1 iff N != 0 (branch-free); else 0
(43 . 7)(42 . 6)
1920 begin
1921 return 1 xor FZ_ZeroP(N);
1922 end FZ_NZeroP;
1923 pragma Inline_Always(FZ_NZeroP);
1924
1925
1926 -- 1 iff N is odd
(51 . 6)(49 . 5)
1928 begin
1929 return W_OddP(N(N'First));
1930 end FZ_OddP;
1931 pragma Inline_Always(FZ_OddP);
1932
1933 end FZ_Pred;
(31 . 11)(31 . 14)
1938
1939 -- 1 iff N == 0 (branch-free); else 0
1940 function FZ_ZeroP(N : in FZ) return WBool;
1941 pragma Inline_Always(FZ_ZeroP);
1942
1943 -- 1 iff N != 0 (branch-free); else 0
1944 function FZ_NZeroP(N : in FZ) return WBool;
1945 pragma Inline_Always(FZ_NZeroP);
1946
1947 -- 1 iff N is odd
1948 function FZ_OddP(N : in FZ) return WBool;
1949 pragma Inline_Always(FZ_OddP);
1950
1951 end FZ_Pred;
- C8D53B2A0E90EC081C6E0BDB4D1DE6FCF02ABA4AB34D1EB83271DF34CC3CB1FBB29B103551335477314F2A5DB544B91943CCAAE1DCA05676AA096420D59F9D84(42 . 7)(42 . 6)- 28A09B8F85E67C25816A78E1EED67A34FFFDDE6A8F2879736FE1B6C6A00ABF037D6C7A09AD85EB8CC3C13AB9F01C2D8FA7C97821EA649F0A292E1CF591B81323
1956 end loop;
1957 Overflow := Carry;
1958 end FZ_ShiftRight_O_I;
1959 pragma Inline_Always(FZ_ShiftRight_O_I);
1960
1961
1962 -- ShiftedN := N >> Count (with Overflow Output only)
(53 . 7)(52 . 6)
1964 begin
1965 FZ_ShiftRight_O_I(N, ShiftedN, Count, Overflow, 0);
1966 end FZ_ShiftRight_O;
1967 pragma Inline_Always(FZ_ShiftRight_O);
1968
1969
1970 -- ShiftedN := N >> Count (no Overflow output or input)
(65 . 7)(63 . 6)
1972 begin
1973 FZ_ShiftRight_O_I(N, ShiftedN, Count, Overflow, 0);
1974 end FZ_ShiftRight;
1975 pragma Inline_Always(FZ_ShiftRight);
1976
1977 --------------------------------------------------------------
1978 -- Shift Left
(87 . 7)(84 . 6)
1980 end loop;
1981 Overflow := Carry;
1982 end FZ_ShiftLeft_O_I;
1983 pragma Inline_Always(FZ_ShiftLeft_O_I);
1984
1985
1986 -- ShiftedN := N << Count (with Overflow Output only)
(98 . 7)(94 . 6)
1988 begin
1989 FZ_ShiftLeft_O_I(N, ShiftedN, Count, Overflow, 0);
1990 end FZ_ShiftLeft_O;
1991 pragma Inline_Always(FZ_ShiftLeft_O);
1992
1993
1994 -- ShiftedN := N << Count (no Overflow output or input)
(110 . 6)(105 . 5)
1996 begin
1997 FZ_ShiftLeft_O_I(N, ShiftedN, Count, Overflow, 0);
1998 end FZ_ShiftLeft;
1999 pragma Inline_Always(FZ_ShiftLeft);
2000
2001 end FZ_Shift;
(35 . 20)(35 . 20)- 9E7DB7601C084048496D7D67FAD5B7EFDB69490BA98785A33F041CF6497EBD954AC8A539CF1C0F22CBB538BBAF8C544E6772205A541646AC22EB0DA31883643C
2006 Count : in WBit_Index;
2007 Overflow : out Word;
2008 OF_in : in Word);
2009 pragma Precondition(N'Length = ShiftedN'Length);
2010 pragma Inline_Always(FZ_ShiftRight_O_I);
2011
2012 -- ShiftedN := N >> Count (with Overflow Output only)
2013 procedure FZ_ShiftRight_O(N : in FZ;
2014 ShiftedN : out FZ;
2015 Count : in WBit_Index;
2016 Overflow : out Word);
2017 pragma Precondition(N'Length = ShiftedN'Length);
2018 pragma Inline_Always(FZ_ShiftRight_O);
2019
2020 -- ShiftedN := N >> Count (no Overflow output or input)
2021 procedure FZ_ShiftRight(N : in FZ;
2022 ShiftedN : out FZ;
2023 Count : in WBit_Index);
2024 pragma Precondition(N'Length = ShiftedN'Length);
2025 pragma Inline_Always(FZ_ShiftRight);
2026
2027 --------------------------------------------------------------
2028 -- Shift Left
(60 . 19)(60 . 19)
2030 Count : in WBit_Index;
2031 Overflow : out Word;
2032 OF_in : in Word);
2033 pragma Precondition(N'Length = ShiftedN'Length);
2034 pragma Inline_Always(FZ_ShiftLeft_O_I);
2035
2036 -- ShiftedN := N << Count (with Overflow Output only)
2037 procedure FZ_ShiftLeft_O(N : in FZ;
2038 ShiftedN : out FZ;
2039 Count : in WBit_Index;
2040 Overflow : out Word);
2041 pragma Precondition(N'Length = ShiftedN'Length);
2042 pragma Inline_Always(FZ_ShiftLeft_O);
2043
2044 -- ShiftedN := N << Count (no Overflow output or input)
2045 procedure FZ_ShiftLeft(N : in FZ;
2046 ShiftedN : out FZ;
2047 Count : in WBit_Index);
2048 pragma Precondition(N'Length = ShiftedN'Length);
2049 pragma Inline_Always(FZ_ShiftLeft);
2050
2051 end FZ_Shift;
(27 . 7)(27 . 6)- 0B95A8D43DF2253DD2677A8D52DADB5673A6089FF5C745FE57FA46C58CB1FBA62681973DB9EE76AE7828C9BB4DF98378F2DA8928097F787825E025D5C5665335
2056 begin
2057 return X * Y;
2058 end Mul_HalfWord_Iron;
2059 pragma Inline_Always(Mul_HalfWord_Iron);
2060
2061
2062 -- Multiply half-words X and Y, producing a Word-sized product
(62 . 7)(61 . 6)
2064 XS := Shift_Left(XS, 1);
2065
2066 end Bit;
2067 pragma Inline_Always(Bit);
2068
2069 begin
2070
(77 . 7)(75 . 6)
2072 return XY;
2073
2074 end Mul_HalfWord_Soft;
2075 pragma Inline_Always(Mul_HalfWord_Soft);
2076
2077
2078 -- Get the bottom half of a Word
(85 . 7)(82 . 6)
2080 begin
2081 return W and (2**HalfBitness - 1);
2082 end BottomHW;
2083 pragma Inline_Always(BottomHW);
2084
2085
2086 -- Get the top half of a Word
(93 . 7)(89 . 6)
2088 begin
2089 return Shift_Right(W, HalfBitness);
2090 end TopHW;
2091 pragma Inline_Always(TopHW);
2092
2093
2094 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
(138 . 6)(133 . 5)
2096 XY_HW := HH + TopHW(HL) + TopHW(LH) + CL;
2097
2098 end Mul_Word;
2099 pragma Inline_Always(Mul_Word);
2100
2101 end W_Mul;
(33 . 17)(33 . 23)
2106
2107 -- Multiply half-words X and Y, producing a Word-sized product (Iron)
2108 function Mul_HalfWord_Iron(X : in HalfWord; Y : in HalfWord) return Word;
2109 pragma Inline_Always(Mul_HalfWord_Iron);
2110
2111 -- Multiply half-words X and Y, producing a Word-sized product (Egyptian)
2112 function Mul_HalfWord_Soft(X : in HalfWord; Y : in HalfWord) return Word;
2113 pragma Inline_Always(Mul_HalfWord_Soft);
2114
2115 -- Get the bottom half of a Word
2116 function BottomHW(W : in Word) return HalfWord;
2117 pragma Inline_Always(BottomHW);
2118
2119 -- Get the top half of a Word
2120 function TopHW(W : in Word) return HalfWord;
2121 pragma Inline_Always(TopHW);
2122
2123 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW (Iron)
2124 procedure Mul_Word(X : in Word; Y : in Word; XY_LW : out Word; XY_HW : out Word);
2125 procedure Mul_Word(X : in Word; Y : in Word;
2126 XY_LW : out Word; XY_HW : out Word);
2127 pragma Inline_Always(Mul_Word);
2128
2129 end W_Mul;
- 793FD672FABC06AC1F852BFC681A23F845B8C7560A8601F1F1239ED07065A94E70B1E9402664D16D87449A5FF5C81420F7D5E0EEBC95D84C3373576DF66A7C0A(27 . 7)(27 . 6)- F367B121A5FD6FBA68F6046A9329AC6EC98272A2728F38DDD75C52F348834AD811F20D88AEAC38B24D07B1CE9C042A736554A6C7FB1F6AD7A264B2A09126F7EA
2134 begin
2135 return W_Borrow(N, 1, N - 1);
2136 end W_ZeroP;
2137 pragma Inline_Always(W_ZeroP);
2138
2139
2140 -- Return 1 if N is unequal to 0; otherwise return 0.
(35 . 7)(34 . 6)
2142 begin
2143 return 1 xor W_ZeroP(N);
2144 end W_NZeroP;
2145 pragma Inline_Always(W_NZeroP);
2146
2147
2148 -- Return WBool-complement of N.
(43 . 7)(41 . 6)
2150 begin
2151 return 1 xor N;
2152 end W_Not;
2153 pragma Inline_Always(W_Not);
2154
2155
2156 -- Return 1 if N is odd; otherwise return 0.
(51 . 7)(48 . 6)
2158 begin
2159 return 1 and N;
2160 end W_OddP;
2161 pragma Inline_Always(W_OddP);
2162
2163
2164 -- Return 1 if A is equal to B ; otherwise return 0.
(59 . 6)(55 . 5)
2166 begin
2167 return W_ZeroP(A xor B);
2168 end W_EqP;
2169 pragma Inline_Always(W_EqP);
2170
2171 end W_Pred;
(26 . 17)(26 . 22)
2176
2177 -- Return 1 if N is equal to 0; otherwise return 0.
2178 function W_ZeroP(N : in Word) return WBool;
2179 pragma Inline_Always(W_ZeroP);
2180
2181 -- Return 1 if N is unequal to 0; otherwise return 0.
2182 function W_NZeroP(N : in Word) return WBool;
2183 pragma Inline_Always(W_NZeroP);
2184
2185 -- Return WBool-complement of N.
2186 function W_Not(N : in WBool) return WBool;
2187 pragma Inline_Always(W_Not);
2188
2189 -- Return 1 if N is odd; otherwise return 0.
2190 function W_OddP(N : in Word) return WBool;
2191 pragma Inline_Always(W_OddP);
2192
2193 -- Return 1 if A is equal to B ; otherwise return 0.
2194 function W_EqP(A : in Word; B : in Word) return WBool;
2195 pragma Inline_Always(W_EqP);
2196
2197 end W_Pred;
- 531BBAA56146A75CF0632ABD688C4FB260DE0F3BCBA9C841A6F4868D3B8A3769FE05C42C5E290A1C573425F5583647EE2C41F6FE24E428B66C745ED52467DCE6(36 . 23)(36 . 27)
2202 Amount : Natural)
2203 return Word;
2204 pragma Import(Intrinsic, Shift_Left);
2205 pragma Inline_Always(Shift_Left);
2206
2207 function Shift_Right
2208 (Value : Word;
2209 Amount : Natural)
2210 return Word;
2211 pragma Import(Intrinsic, Shift_Right);
2212 pragma Inline_Always(Shift_Right);
2213
2214 function Rotate_Left
2215 (Value : Word;
2216 Amount : Natural)
2217 return Word;
2218 pragma Import(Intrinsic, Rotate_Left);
2219 pragma Inline_Always(Rotate_Left);
2220
2221 function Rotate_Right
2222 (Value : Word;
2223 Amount : Natural)
2224 return Word;
2225 pragma Import(Intrinsic, Rotate_Right);
2226 pragma Inline_Always(Rotate_Right);
2227
2228 end W_Shifts;
- 0431D4E5164D5119F81331E3A7EF2F69A397D4A35655274D79A809B69CD10324BEFF9359194A503DBC5AB085B2214E96AFEE97DB984E6625233BB975D9407FAB(39 . 7)(39 . 6)- EEDC4547993ABF2B50486519D32D6AC22A798F2ACF8959AD80F5877BE406B1D02CEA313F7A1B718F029011B31A5DB36C5472E99ED3C4C837B17C613D915BA4CF
2233 return WBool(Shift_Right((A and B) or ((A or B) and (not S)),
2234 Bitness - 1));
2235 end W_Carry;
2236 pragma Inline_Always(W_Carry);
2237
2238
2239 -- Find the Borrow, from a subtraction where it is known that A - B == D:
(49 . 7)(48 . 6)
2241 return WBool(Shift_Right(((not A) and B) or (((not A) or B) and D),
2242 Bitness - 1));
2243 end W_Borrow;
2244 pragma Inline_Always(W_Borrow);
2245
2246 -- A+B+C is the output bit of 1-bit adder; C is carry-in;
2247 -- A-B-C is the output bit of 1-bit subber; C is borrow-in.
(86 . 6)(84 . 5)
2249 begin
2250 return B xor ((Sel - 1) and (A xor B));
2251 end W_Mux;
2252 pragma Inline_Always(W_Mux);
2253
2254 end Word_Ops;
(27 . 13)(27 . 16)
2259 -- Branch-free calculation of 'carry' from a machine-word addition.
2260 function W_Carry(A : in Word; B : in Word; S : in Word)
2261 return WBool;
2262 pragma Inline_Always(W_Carry);
2263
2264 -- Branch-free calculation of 'borrow' from a machine-word subtraction.
2265 function W_Borrow(A : in Word; B : in Word; D : in Word)
2266 return WBool;
2267 pragma Inline_Always(W_Borrow);
2268
2269 -- Without any branching: if Sel == 0, return A; if Sel == 1, return B.
2270 function W_Mux(A : in Word; B : in Word; Sel : in WBool)
2271 return Word;
2272 pragma Inline_Always(W_Mux);
2273
2274 end Word_Ops;
- 2223DA25C192F8BAB7A0924518AB9543A66D1793B86C2CA37A0B9E1E59162B8358DBBCE6442811EC4813FB215E25890FDA740679E32B6B2E5B6FD0FB71036DBC(33 . 6)(33 . 9)
2279 -- The Word width, expressed in ~bytes~:
2280 Byteness : constant Positive := Bitness / Iron.ByteBits;
2281
2282 -- Nibbles per Word:
2283 Nibbleness : constant Positive := Byteness * 2;
2284
2285 -- What kind of words to use. Must be machine-word or smaller.
2286 type Word is mod 2**Bitness;
2287 for Word'Size use Bitness;