File : w_mul.adb
1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
4 -- --
5 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
7 -- --
8 -- You do not have, nor can you ever acquire the right to use, copy or --
9 -- distribute this software ; Should you use this software for any purpose, --
10 -- or copy and distribute it to anyone or in any manner, you are breaking --
11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
12 -- continue doing so for the indefinite future. In any case, please --
13 -- always : read and understand any software ; verify any PGP signatures --
14 -- that you use - for any purpose. --
15 -- --
16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
17 ------------------------------------------------------------------------------
18 ------------------------------------------------------------------------------
19
20 with W_Shifts; use W_Shifts;
21
22
23 package body W_Mul is
24
25 function Mul_HalfWord_Iron(X : in HalfWord;
26 Y : in HalfWord) return Word is
27 begin
28 return X * Y;
29 end Mul_HalfWord_Iron;
30
31
32 -- Multiply half-words X and Y, producing a Word-sized product
33 function Mul_HalfWord_Soft(X : in HalfWord; Y : in HalfWord) return Word is
34
35 -- X-Slide
36 XS : Word := X;
37
38 -- Y-Slide
39 YS : Word := Y;
40
41 -- Gate Mask
42 GM : Word;
43
44 -- The Product
45 XY : Word := 0;
46
47 -- Performed for each bit of HalfWord's bitness:
48 procedure Bit is
49 begin
50
51 -- Compute the gate mask
52 GM := 0 - (YS and 1);
53
54 -- Perform the gated addition
55 XY := XY + (XS and GM);
56
57 -- Crank the next Y-slide bit into position
58 YS := Shift_Right(YS, 1);
59
60 -- Advance the X-slide by 1 bit
61 XS := Shift_Left(XS, 1);
62
63 end Bit;
64
65 begin
66
67 -- For each bit of the Y-Slide (unrolled) :
68 for b in 1 .. HalfByteness loop
69
70 Bit; Bit; Bit; Bit; Bit; Bit; Bit; Bit;
71
72 end loop;
73
74 -- Return the Product
75 return XY;
76
77 end Mul_HalfWord_Soft;
78
79
80 -- Get the bottom half of a Word
81 function BottomHW(W : in Word) return HalfWord is
82 begin
83 return W and (2**HalfBitness - 1);
84 end BottomHW;
85
86
87 -- Get the top half of a Word
88 function TopHW(W : in Word) return HalfWord is
89 begin
90 return Shift_Right(W, HalfBitness);
91 end TopHW;
92
93
94 -- Carry out X*Y mult, return lower word XY_LW and upper word XY_HW.
95 procedure Mul_Word(X : in Word;
96 Y : in Word;
97 XY_LW : out Word;
98 XY_HW : out Word) is
99
100 -- Bottom half of multiplicand X
101 XL : constant HalfWord := BottomHW(X);
102
103 -- Top half of multiplicand X
104 XH : constant HalfWord := TopHW(X);
105
106 -- Bottom half of multiplicand Y
107 YL : constant HalfWord := BottomHW(Y);
108
109 -- Top half of multiplicand Y
110 YH : constant HalfWord := TopHW(Y);
111
112 -- XL * YL
113 LL : constant Word := Mul_HalfWord_Iron(XL, YL);
114
115 -- XL * YH
116 LH : constant Word := Mul_HalfWord_Iron(XL, YH);
117
118 -- XH * YL
119 HL : constant Word := Mul_HalfWord_Iron(XH, YL);
120
121 -- XH * YH
122 HH : constant Word := Mul_HalfWord_Iron(XH, YH);
123
124 -- Carry
125 CL : constant Word := TopHW(TopHW(LL) + BottomHW(LH) + BottomHW(HL));
126
127 begin
128
129 -- Get the bottom half of the Product:
130 XY_LW := LL + Shift_Left(LH + HL, HalfBitness);
131
132 -- Get the top half of the Product:
133 XY_HW := HH + TopHW(HL) + TopHW(LH) + CL;
134
135 end Mul_Word;
136
137 ---------------------------------------------------------------------------
138 -- LET A CURSE FALL FOREVER on the authors of GCC, and on the Ada committee,
139 -- neither of whom saw it fit to decree a primitive which returns both
140 -- upper and lower halves of an iron MUL instruction's result. Consequently,
141 -- portable Mul_Word demands ~four~ MULs (and several additions and shifts);
142 -- while portable Sqr_Word demands ~three~ MULs (and likewise adds/shifts.)
143 -- If it were not for their idiocy, BOTH routines would weigh 1 CPU instr.!
144 ---------------------------------------------------------------------------
145
146 -- Carry out X*X squaring, return lower word XX_LW and upper word XX_HW.
147 procedure Sqr_Word(X : in Word;
148 XX_LW : out Word;
149 XX_HW : out Word) is
150
151 -- Bottom half of multiplicand X
152 XL : constant HalfWord := BottomHW(X);
153
154 -- Top half of multiplicand X
155 XH : constant HalfWord := TopHW(X);
156
157 -- XL^2
158 LL : constant Word := Mul_HalfWord_Iron(XL, XL);
159
160 -- XL * XH
161 LH : constant Word := Mul_HalfWord_Iron(XL, XH);
162
163 -- XH^2
164 HH : constant Word := Mul_HalfWord_Iron(XH, XH);
165
166 -- Carry
167 CL : constant Word := TopHW(TopHW(LL) + Shift_Left(BottomHW(LH), 1));
168
169 begin
170
171 -- Get the bottom half of the Product:
172 XX_LW := LL + Shift_Left(LH, HalfBitness + 1);
173
174 -- Get the top half of the Product:
175 XX_HW := HH + Shift_Left(TopHW(LH), 1) + CL;
176
177 end Sqr_Word;
178
179 end W_Mul;