# Finite Field Arithmetic

```   1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
4 --                                                                          --
5 -- (C) 2019 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 --                                                                          --
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
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;
```