tree checksum vpatch file split hunks

all signers: asciilifeform diana_coman

antecedents: ffa_ch6_simplest_rsa.kv ffa_ch5_egypt.kv

press order:

ffa_ch1_genesis.kvasciilifeform diana_coman
ffa_ch2_logicals.kvasciilifeform diana_coman
ffa_ch3_shifts.kvasciilifeform diana_coman
ffa_ch4_ffacalc.kvasciilifeform diana_coman
ffa_ch5_egypt.kvasciilifeform diana_coman
ffa_ch6_simplest_rsa.kvasciilifeform diana_coman
ffa_ch7_turbo_egyptians.kvasciilifeform diana_coman

patch:

- 449D20BE8CE3646757DCD06D68BAF7FC83A5B32C085B5D617D30500C7EB4377CAA2E74B3679C2751F5277660B5E9C8C2955608C696B3268C7D294CAFFA99E442
+ 0934AF47E0703889B29836CA23503EDDFBDEDF1548FB43315E76A2651C88D9F5742A1D957A2A6D6052AC77F2E260D380131149289F30EA11DCE018A9C0342285
ffa/libffa/fz_divis.adb
(19 . 6)(19 . 7)
5
6 with Words; use Words;
7 with W_Pred; use W_Pred;
8 with W_Shifts; use W_Shifts;
9 with FZ_Basic; use FZ_Basic;
10 with FZ_Arith; use FZ_Arith;
11 with FZ_BitOp; use FZ_BitOp;
(82 . 15)(83 . 92)
13 pragma Inline_Always(FZ_Div);
14
15
16 -- Exactly same thing as IDiv, but keep only the Remainder
17 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
18 procedure FZ_Mod(Dividend : in FZ;
19 Divisor : in FZ;
20 Remainder : out FZ) is
21 Quotient : FZ(Dividend'Range);
22 pragma Unreferenced(Quotient);
23
24 -- Length of Divisor and Remainder; <= Dividend'Length
25 L : constant Indices := Divisor'Length;
26
27 -- Remainder register, starts as zero
28 R : FZ(1 .. L) := (others => 0);
29
30 -- Indices into the words of Dividend
31 subtype Dividend_Index is Word_Index range Dividend'Range;
32
33 -- Permissible 'cuts' for the Slice operation
34 subtype Divisor_Cuts is Word_Index range 2 .. Divisor'Length;
35
36 -- Performs Restoring Division on a given segment of Dividend:Divisor
37 procedure Slice(Index : Dividend_Index;
38 Cut : Divisor_Cuts) is
39 begin
40
41 declare
42
43 -- Borrow, from comparator
44 C : WBool;
45
46 -- Left-Shift Overflow
47 LsO : WBool;
48
49 -- Current cut of Remainder register
50 Rs : FZ renames R(1 .. Cut);
51
52 -- Current cut of Divisor
53 Ds : FZ renames Divisor(1 .. Cut);
54
55 -- Current word of Dividend, starting from the highest
56 W : Word := Dividend(Dividend'Last + 1 - Index);
57
58 begin
59
60 -- For each bit in the current Dividend word:
61 for b in 1 .. Bitness loop
62
63 -- Send top bit of current Dividend word to the bottom of W
64 W := Rotate_Left(W, 1);
65
66 -- Advance Rs, shifting in the current Dividend bit
67 FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
68 OF_In => W and 1,
69 Overflow => LsO);
70
71 -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
72 FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
73
74 -- If C=1, subtraction underflowed, and we must undo it:
75 FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
76 Gate => C and W_Not(LsO));
77
78 end loop;
79
80 end;
81
82 end Slice;
83
84 begin
85 FZ_IDiv(Dividend, Divisor, Quotient, Remainder);
86
87 -- Process bottom half of dividend:
88 for i in 1 .. L - 1 loop
89
90 Slice(i, i + 1); -- stay ahead by a word to handle carry
91
92 end loop;
93
94 -- Process top half of dividend
95 for i in L .. Dividend'Length loop
96
97 Slice(i, L);
98
99 end loop;
100
101 -- Output the Remainder.
102 Remainder := R;
103
104 end FZ_Mod;
105 pragma Inline_Always(FZ_Mod);
106
107
108 end FZ_Divis;
- CF9E5BBCD7DD4DF94DD9A95F52B631CB5C9D29EB6EC7EEEC1ED40E06B7A80019F55206D3C3C0E210BC5A056E12203360C9F51EC2FE060542805A1BE2E68949A9
+ BA309013077BBF7E96260BB5F45AB8AE14AA3A520265D1EC7880E7C8F4DB24BA8628766465BA214D9F63BC02E44E7588B6ECC26E2CB376C6D2C7B85ED5314882
ffa/libffa/fz_divis.ads
(41 . 11)(41 . 11)
113 pragma Precondition(Dividend'Length = Divisor'Length and
114 Dividend'Length = Quotient'Length);
115
116 -- Exactly same thing as IDiv, but keep only the Remainder
117 -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
118 procedure FZ_Mod(Dividend : in FZ;
119 Divisor : in FZ;
120 Remainder : out FZ);
121 pragma Precondition(Dividend'Length = Divisor'Length and
122 Dividend'Length = Remainder'Length);
123 pragma Precondition(Dividend'Length >= Divisor'Length and
124 Divisor'Length = Remainder'Length);
125
126 end FZ_Divis;
- 3236467E5470CA5B3B1384473445491EE52C0151D36A450CA1B9E496A9FE53A5AFE490B065FCDDD7A6E7DC6BBBDD902643B7C3BC4CFE5984F84E69AE5D8A7B2E
+ B9880001CD7A0ADC289E3F1EBC71B48EFF6CB1079EEB5A21BF32A81BA4E0E0F3F9917FFFDD02E0C1AC2F06553610FA0F396408680C411C8DB3B6A80A8E1E978D
ffa/libffa/fz_modex.adb
(42 . 22)(42 . 14)
131 XY_Lo : FZ renames XY(1 .. L);
132 XY_Hi : FZ renames XY(L + 1 .. XY'Last);
133
134 -- A zero-padded double-wide copy of Modulus, to satisfy Ch.5's FZ_Mod
135 M : FZ(XY'Range);
136
137 begin
138 -- Place the Modulus in a double-width M, as FZ_Mod currently demands
139 M(Modulus'Range) := Modulus;
140 M(L + 1 .. M'Last) := (others => 0);
141
142 -- XY_Lo:XY_Hi := X * Y
143 FZ_Mul_Egyptian(X, Y, XY_Lo, XY_Hi);
144
145 -- XY := XY mod M
146 FZ_Mod(XY, M, XY);
147 -- Product := XY mod M
148 FZ_Mod(XY, Modulus, Product);
149
150 -- The bottom half of XY is our modular product; top half is always 0
151 Product := XY_Lo;
152 end FZ_Mod_Mul;
153 pragma Inline_Always(FZ_Mod_Mul);
154
- 81335CBF5970684E89C61B7A37BFF32F747027A72251D88F2980D21E52D41B88D05503613E11404D55BE9C5DEA3170A7A069CDD32FC4DF64500164BCEE844AF9
+ 20B94E2B0260DD90AEDA5E987C038348070FA29AFFF8FD41A84BDA53CF6BFC15638809387A6C9C44C6F9FCBDC28C5E5AFD7E1EFA43B0DA72F89B9C198F603670
ffa/libffa/fz_mul.adb
(18 . 8)(18 . 8)
159 ------------------------------------------------------------------------------
160
161 with Words; use Words;
162 with W_Shifts; use W_Shifts;
163 with FZ_Basic; use FZ_Basic;
164 with FZ_Pred; use FZ_Pred;
165 with FZ_Arith; use FZ_Arith;
166 with FZ_Shift; use FZ_Shift;
167
(32 . 15)(32 . 14)
169 XY_Lo : out FZ;
170 XY_Hi : out FZ) is
171
172 L : constant Indices := X'Length;
173
174 -- Register holding running product
175 XY : FZ(1 .. X'Length + Y'Length);
176
177 -- X-Slide
178 XS : FZ(1 .. X'Length + Y'Length);
179
180 -- Y-Slide
181 YS : FZ(Y'Range) := Y;
182
183 begin
184 -- Product register begins empty
185 FZ_Clear(XY);
(49 . 18)(48 . 33)
187 XS(1 .. X'Length) := X;
188 XS(X'Length + 1 .. XS'Last) := (others => 0);
189
190 -- For each bit of Y:
191 for i in 1 .. FZ_Bitness(Y) loop
192
193 -- If lowest bit of Y-Slide is 1, X-Slide is added into XY
194 FZ_Add_Gated(X => XY, Y => XS, Sum => XY,
195 Gate => FZ_OddP(YS));
196
197 -- X-Slide := X-Slide * 2
198 FZ_ShiftLeft(XS, XS, 1);
199 -- For each word of Y:
200 for i in Y'Range loop
201
202 -- Y-Slide := Y-Slide / 2
203 FZ_ShiftRight(YS, YS, 1);
204 declare
205 -- Current word of Y
206 W : Word := Y(i);
207
208 -- Current cut of XY and XS. Stay ahead by a word to handle carry.
209 Cut : constant Indices := L + i;
210 XYc : FZ renames XY(1 .. Cut);
211 XSc : FZ renames XS(1 .. Cut);
212
213 begin
214 for b in 1 .. Bitness loop
215
216 -- If current Y bit is 1, X-Slide Cut is added into XY Cut
217 FZ_Add_Gated(X => XYc, Y => XSc, Sum => XYc,
218 Gate => W and 1);
219
220 -- Crank the next bit of Y into the bottom position of W
221 W := Shift_Right(W, 1);
222
223 -- X-Slide := X-Slide * 2
224 FZ_ShiftLeft(XSc, XSc, 1);
225
226 end loop;
227 end;
228
229 end loop;
230