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 -- -- 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;