tree checksum vpatch file split hunks
all signers: asciilifeform bvt diana_coman
antecedents: ffa_ch6_simplest_rsa.kv ffa_ch5_egypt.kv
press order:
patch:
(19 . 6)(19 . 7)- CF9E5BBCD7DD4DF94DD9A95F52B631CB5C9D29EB6EC7EEEC1ED40E06B7A80019F55206D3C3C0E210BC5A056E12203360C9F51EC2FE060542805A1BE2E68949A9
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;
(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(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(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