- 20B94E2B0260DD90AEDA5E987C038348070FA29AFFF8FD41A84BDA53CF6BFC15638809387A6C9C44C6F9FCBDC28C5E5AFD7E1EFA43B0DA72F89B9C198F603670+ 5CB9ECB938F842B7C34CA7EDF99FB92502986D7F660B223659C9B19C6008A24C3BE6DE8135DB37E29E7FF278A451B68C61F6B57D8E404372DCD3FD6D4320EA0Affa/libffa/fz_mul.adb(18 . 71)(18 . 108)
37 ------------------------------------------------------------------------------
38
39 with Words; use Words;
40 with W_Shifts; use W_Shifts;
41 with FZ_Basic; use FZ_Basic;
42 with FZ_Arith; use FZ_Arith;
43 with FZ_Shift; use FZ_Shift;
44 with Word_Ops; use Word_Ops;
45 with W_Mul; use W_Mul;
46
47
48 package body FZ_Mul is
49
50 -- 'Egyptological' multiplier. XY_Lo and XY_Hi hold result of X*Y.
51 procedure FZ_Mul_Egyptian(X : in FZ;
52 Y : in FZ;
53 XY_Lo : out FZ;
54 XY_Hi : out FZ) is
55 -- Comba's multiplier.
56 procedure FZ_Mul_Comba(X : in FZ;
57 Y : in FZ;
58 XY_Lo : out FZ;
59 XY_Hi : out FZ) is
60
61 L : constant Indices := X'Length;
62 -- Words in each multiplicand
63 L : constant Word_Index := X'Length;
64
65 -- Register holding running product
66 XY : FZ(1 .. X'Length + Y'Length);
67 -- Length of Product, i.e. double the length of either multiplicand
68 LP : constant Word_Index := 2 * L;
69
70 -- X-Slide
71 XS : FZ(1 .. X'Length + Y'Length);
72 -- 3-word Accumulator
73 A2, A1, A0 : Word := 0;
74
75 -- Register holding Product; indexed from zero
76 XY : FZ(0 .. LP - 1);
77
78 -- Type for referring to a column of XY
79 subtype ColXY is Word_Index range XY'Range;
80
81 -- Compute the Nth (indexed from zero) column of the Product
82 procedure Col(N : in ColXY; U : in ColXY; V : in ColXY) is
83
84 -- The outputs of a Word multiplication
85 Lo, Hi : Word;
86
87 -- Carry for the Accumulator addition
88 C : WBool;
89
90 -- Sum for Accumulator addition
91 Sum : Word;
92
93 begin
94
95 -- For lower half of XY, will go from 0 to N
96 -- For upper half of XY, will go from N - L + 1 to L - 1
97 for j in U .. V loop
98
99 -- Hi:Lo := j-th Word of X * (N - j)-th Word of Y
100 Mul_Word(X(X'First + j),
101 Y(Y'First - j + N),
102 Lo, Hi);
103
104 -- Now add Hi:Lo into the Accumulator:
105
106 -- A0 += Lo; C := Carry
107 Sum := A0 + Lo;
108 C := W_Carry(A0, Lo, Sum);
109 A0 := Sum;
110
111 -- A1 += Hi + C; C := Carry
112 Sum := A1 + Hi + C;
113 C := W_Carry(A1, Hi, Sum);
114 A1 := Sum;
115
116 -- A2 += A2 + C
117 A2 := A2 + C;
118
119 end loop;
120
121 -- We now have the Nth (indexed from zero) word of XY
122 XY(N) := A0;
123
124 -- Right-Shift the Accumulator by one Word width:
125 A0 := A1;
126 A1 := A2;
127 A2 := 0;
128
129 end Col;
130 pragma Inline_Always(Col);
131
132 begin
133 -- Product register begins empty
134 FZ_Clear(XY);
135
136 -- X-Slide initially equals X:
137 XS(1 .. X'Length) := X;
138 XS(X'Length + 1 .. XS'Last) := (others => 0);
139
140 -- For each word of Y:
141 for i in Y'Range loop
142
143 declare
144 -- Current word of Y
145 W : Word := Y(i);
146
147 -- Current cut of XY and XS. Stay ahead by a word to handle carry.
148 Cut : constant Indices := L + i;
149 XYc : FZ renames XY(1 .. Cut);
150 XSc : FZ renames XS(1 .. Cut);
151
152 begin
153 for b in 1 .. Bitness loop
154
155 -- If current Y bit is 1, X-Slide Cut is added into XY Cut
156 FZ_Add_Gated(X => XYc, Y => XSc, Sum => XYc,
157 Gate => W and 1);
158
159 -- Crank the next bit of Y into the bottom position of W
160 W := Shift_Right(W, 1);
161
162 -- X-Slide := X-Slide * 2
163 FZ_ShiftLeft(XSc, XSc, 1);
164
165 end loop;
166 end;
167 -- Compute the lower half of the Product:
168 for i in 0 .. L - 1 loop
169
170 Col(i, 0, i);
171
172 end loop;
173
174 -- Compute the upper half (sans last Word) of the Product:
175 for i in L .. LP - 2 loop
176
177 Col(i, i - L + 1, L - 1);
178
179 end loop;
180
181 -- Write out the Product's lower and upper FZs:
182 XY_Lo := XY(1 .. XY_Lo'Length);
183 XY_Hi := XY(XY_Lo'Length + 1 .. XY'Last);
184 -- The very last Word of the Product:
185 XY(XY'Last) := A0;
186
187 end FZ_Mul_Egyptian;
188 pragma Inline_Always(FZ_Mul_Egyptian);
189
190 -- Output the Product's lower and upper FZs:
191 XY_Lo := XY(0 .. L - 1);
192 XY_Hi := XY(L .. XY'Last);
193
194 end FZ_Mul_Comba;
195 pragma Inline_Always(FZ_Mul_Comba);
196
197 end FZ_Mul;