raw
ffa_ch14_barrett.kv     1 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv 2 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv 3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
ffa_ch14_barrett.kv 4 -- --
ffa_ch15_gcd.kv 5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) --
ffa_ch14_barrett.kv 6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
ffa_ch14_barrett.kv 7 -- --
ffa_ch14_barrett.kv 8 -- You do not have, nor can you ever acquire the right to use, copy or --
ffa_ch14_barrett.kv 9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch14_barrett.kv 10 -- or copy and distribute it to anyone or in any manner, you are breaking --
ffa_ch14_barrett.kv 11 -- the laws of whatever soi-disant jurisdiction, and you promise to --
ffa_ch14_barrett.kv 12 -- continue doing so for the indefinite future. In any case, please --
ffa_ch14_barrett.kv 13 -- always : read and understand any software ; verify any PGP signatures --
ffa_ch14_barrett.kv 14 -- that you use - for any purpose. --
ffa_ch14_barrett.kv 15 -- --
ffa_ch14_barrett.kv 16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm . --
ffa_ch14_barrett.kv 17 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv 18 ------------------------------------------------------------------------------
ffa_ch14_barrett.kv 19
ffa_ch14_barrett.kv 20 with Words; use Words;
ffa_ch14_barrett.kv 21 with Word_Ops; use Word_Ops;
ffa_ch14_barrett.kv 22 with W_Mul; use W_Mul;
ffa_ch14_barrett.kv 23 with FZ_Arith; use FZ_Arith;
ffa_ch14_barrett.kv 24 with FZ_Mul; use FZ_Mul;
ffa_ch14_barrett.kv 25
ffa_ch14_barrett.kv 26
ffa_ch14_barrett.kv 27 -- "Low Multiplication" computes only the bottom half of the product XY.
ffa_ch14_barrett.kv 28 -- Presently, it is used solely in Barrett's Modular Reduction.
ffa_ch14_barrett.kv 29
ffa_ch14_barrett.kv 30 package body FZ_LoMul is
ffa_ch14_barrett.kv 31
ffa_ch14_barrett.kv 32 -- Low-Only Comba's multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv 33 procedure FZ_Low_Mul_Comba(X : in FZ;
ffa_ch14_barrett.kv 34 Y : in FZ;
ffa_ch14_barrett.kv 35 XY : out FZ) is
ffa_ch14_barrett.kv 36
ffa_ch14_barrett.kv 37 -- Words in each multiplicand (and also in the half-product)
ffa_ch14_barrett.kv 38 L : constant Word_Index := X'Length;
ffa_ch14_barrett.kv 39
ffa_ch14_barrett.kv 40 -- 3-word Accumulator
ffa_ch14_barrett.kv 41 A2, A1, A0 : Word := 0;
ffa_ch14_barrett.kv 42
ffa_ch14_barrett.kv 43 begin
ffa_ch14_barrett.kv 44
ffa_ch14_barrett.kv 45 -- Compute the lower half of the Product, which is all we want:
ffa_ch14_barrett.kv 46 for N in 0 .. L - 1 loop
ffa_ch14_barrett.kv 47
ffa_ch14_barrett.kv 48 -- Compute the Nth (indexed from zero) column of the Half-Product
ffa_ch14_barrett.kv 49 declare
ffa_ch14_barrett.kv 50
ffa_ch14_barrett.kv 51 -- The outputs of a Word multiplication
ffa_ch14_barrett.kv 52 Lo, Hi : Word;
ffa_ch14_barrett.kv 53
ffa_ch14_barrett.kv 54 -- Carry for the Accumulator addition
ffa_ch14_barrett.kv 55 C : WBool;
ffa_ch14_barrett.kv 56
ffa_ch14_barrett.kv 57 -- Sum for Accumulator addition
ffa_ch14_barrett.kv 58 Sum : Word;
ffa_ch14_barrett.kv 59
ffa_ch14_barrett.kv 60 begin
ffa_ch14_barrett.kv 61
ffa_ch14_barrett.kv 62 -- For lower half of XY, will go from 0 to N
ffa_ch14_barrett.kv 63 -- For upper half of XY, will go from N - L + 1 to L - 1
ffa_ch14_barrett.kv 64 for j in 0 .. N loop
ffa_ch14_barrett.kv 65
ffa_ch14_barrett.kv 66 -- Hi:Lo := j-th Word of X * (N - j)-th Word of Y
ffa_ch14_barrett.kv 67 Mul_Word(X(X'First + j),
ffa_ch14_barrett.kv 68 Y(Y'First - j + N),
ffa_ch14_barrett.kv 69 Lo, Hi);
ffa_ch14_barrett.kv 70
ffa_ch14_barrett.kv 71 -- Now add Hi:Lo into the Accumulator:
ffa_ch14_barrett.kv 72
ffa_ch14_barrett.kv 73 -- A0 += Lo; C := Carry
ffa_ch14_barrett.kv 74 Sum := A0 + Lo;
ffa_ch14_barrett.kv 75 C := W_Carry(A0, Lo, Sum);
ffa_ch14_barrett.kv 76 A0 := Sum;
ffa_ch14_barrett.kv 77
ffa_ch14_barrett.kv 78 -- A1 += Hi + C; C := Carry
ffa_ch14_barrett.kv 79 Sum := A1 + Hi + C;
ffa_ch14_barrett.kv 80 C := W_Carry(A1, Hi, Sum);
ffa_ch14_barrett.kv 81 A1 := Sum;
ffa_ch14_barrett.kv 82
ffa_ch14_barrett.kv 83 -- A2 += A2 + C
ffa_ch14_barrett.kv 84 A2 := A2 + C;
ffa_ch14_barrett.kv 85
ffa_ch14_barrett.kv 86 end loop;
ffa_ch14_barrett.kv 87
ffa_ch14_barrett.kv 88 -- We now have the Nth (indexed from zero) word of XY
ffa_ch14_barrett.kv 89 XY(XY'First + N) := A0;
ffa_ch14_barrett.kv 90
ffa_ch14_barrett.kv 91 -- Right-Shift the Accumulator by one Word width:
ffa_ch14_barrett.kv 92 A0 := A1;
ffa_ch14_barrett.kv 93 A1 := A2;
ffa_ch14_barrett.kv 94 A2 := 0;
ffa_ch14_barrett.kv 95 end;
ffa_ch14_barrett.kv 96
ffa_ch14_barrett.kv 97 end loop;
ffa_ch14_barrett.kv 98
ffa_ch14_barrett.kv 99 end FZ_Low_Mul_Comba;
ffa_ch14_barrett.kv 100
ffa_ch14_barrett.kv 101
ffa_ch14_barrett.kv 102 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv 103 procedure Low_Mul(X : in FZ;
ffa_ch14_barrett.kv 104 Y : in FZ;
ffa_ch14_barrett.kv 105 XY : out FZ) is
ffa_ch14_barrett.kv 106
ffa_ch14_barrett.kv 107 -- L is the wordness of a multiplicand. Guaranteed to be a power of two.
ffa_ch14_barrett.kv 108 L : constant Word_Count := X'Length;
ffa_ch14_barrett.kv 109
ffa_ch14_barrett.kv 110 -- K is HALF of the length of a multiplicand.
ffa_ch14_barrett.kv 111 K : constant Word_Index := L / 2;
ffa_ch14_barrett.kv 112
ffa_ch14_barrett.kv 113 -- A 'KSeg' is the same length as HALF of a multiplicand.
ffa_ch14_barrett.kv 114 subtype KSeg is FZ(1 .. K);
ffa_ch14_barrett.kv 115
ffa_ch14_barrett.kv 116 -- The two K-sized variables of the half-product equation:
ffa_ch14_barrett.kv 117 LH, HL : KSeg;
ffa_ch14_barrett.kv 118
ffa_ch14_barrett.kv 119 -- Bottom and Top K-sized halves of the multiplicand X.
ffa_ch14_barrett.kv 120 XLo : KSeg renames X( X'First .. X'Last - K );
ffa_ch14_barrett.kv 121 XHi : KSeg renames X( X'First + K .. X'Last );
ffa_ch14_barrett.kv 122
ffa_ch14_barrett.kv 123 -- Bottom and Top K-sized halves of the multiplicand Y.
ffa_ch14_barrett.kv 124 YLo : KSeg renames Y( Y'First .. Y'Last - K );
ffa_ch14_barrett.kv 125 YHi : KSeg renames Y( Y'First + K .. Y'Last );
ffa_ch14_barrett.kv 126
ffa_ch14_barrett.kv 127 -- Top K-sized half of the half-product XY.
ffa_ch14_barrett.kv 128 XYHi : KSeg renames XY( XY'First + K .. XY'Last );
ffa_ch14_barrett.kv 129
ffa_ch14_barrett.kv 130 -- Carry from individual term additions.
ffa_ch14_barrett.kv 131 C : WBool;
ffa_ch14_barrett.kv 132 pragma Unreferenced(C);
ffa_ch14_barrett.kv 133
ffa_ch14_barrett.kv 134 begin
ffa_ch14_barrett.kv 135
ffa_ch14_barrett.kv 136 -- Recurse to FULL-width multiplication: XY := XLo * YLo
ffa_ch14_barrett.kv 137 FZ_Multiply_Unbuffered(XLo, YLo, XY);
ffa_ch14_barrett.kv 138
ffa_ch14_barrett.kv 139 -- Recurse to HALF-width multiplication: LH := XLo * YHi
ffa_ch14_barrett.kv 140 FZ_Low_Multiply_Unbuffered(XLo, YHi, LH);
ffa_ch14_barrett.kv 141
ffa_ch14_barrett.kv 142 -- Recurse to HALF-width multiplication: HL := XHi * YLo
ffa_ch14_barrett.kv 143 FZ_Low_Multiply_Unbuffered(XHi, YLo, HL);
ffa_ch14_barrett.kv 144
ffa_ch14_barrett.kv 145 -- XY += 2^(K * Bitness) * LH
ffa_ch14_barrett.kv 146 FZ_Add_D(X => XYHi, Y => LH, Overflow => C);
ffa_ch14_barrett.kv 147
ffa_ch14_barrett.kv 148 -- XY += 2^(K * Bitness) * HL
ffa_ch14_barrett.kv 149 FZ_Add_D(X => XYHi, Y => HL, Overflow => C);
ffa_ch14_barrett.kv 150
ffa_ch14_barrett.kv 151 end Low_Mul;
ffa_ch14_barrett.kv 152 -- CAUTION: Inlining prohibited for Low_Mul !
ffa_ch14_barrett.kv 153
ffa_ch14_barrett.kv 154
ffa_ch14_barrett.kv 155 -- Low-Only Multiplier. (CAUTION: UNBUFFERED)
ffa_ch14_barrett.kv 156 procedure FZ_Low_Multiply_Unbuffered(X : in FZ;
ffa_ch14_barrett.kv 157 Y : in FZ;
ffa_ch14_barrett.kv 158 XY : out FZ) is
ffa_ch14_barrett.kv 159
ffa_ch14_barrett.kv 160 -- The length of either multiplicand
ffa_ch14_barrett.kv 161 L : constant Word_Count := X'Length;
ffa_ch14_barrett.kv 162
ffa_ch14_barrett.kv 163 begin
ffa_ch14_barrett.kv 164
ffa_ch14_barrett.kv 165 if L <= Low_Mul_Thresh then
ffa_ch14_barrett.kv 166
ffa_ch14_barrett.kv 167 -- Base case:
ffa_ch14_barrett.kv 168 FZ_Low_Mul_Comba(X, Y, XY);
ffa_ch14_barrett.kv 169
ffa_ch14_barrett.kv 170 else
ffa_ch14_barrett.kv 171
ffa_ch14_barrett.kv 172 -- Recursive case:
ffa_ch14_barrett.kv 173 Low_Mul(X, Y, XY);
ffa_ch14_barrett.kv 174
ffa_ch14_barrett.kv 175 end if;
ffa_ch14_barrett.kv 176
ffa_ch14_barrett.kv 177 end FZ_Low_Multiply_Unbuffered;
ffa_ch14_barrett.kv 178
ffa_ch15_gcd.kv 179
ffa_ch15_gcd.kv 180 -- Low-Only Multiplier. Preserves the inputs.
ffa_ch15_gcd.kv 181 procedure FZ_Low_Multiply_Buffered(X : in FZ;
ffa_ch15_gcd.kv 182 Y : in FZ;
ffa_ch15_gcd.kv 183 XY : out FZ) is
ffa_ch15_gcd.kv 184
ffa_ch15_gcd.kv 185 -- Product buffer.
ffa_ch15_gcd.kv 186 P : FZ(1 .. X'Length);
ffa_ch15_gcd.kv 187
ffa_ch15_gcd.kv 188 begin
ffa_ch15_gcd.kv 189
ffa_ch15_gcd.kv 190 FZ_Low_Multiply_Unbuffered(X, Y, P);
ffa_ch15_gcd.kv 191
ffa_ch15_gcd.kv 192 XY := P;
ffa_ch15_gcd.kv 193
ffa_ch15_gcd.kv 194 end FZ_Low_Multiply_Buffered;
ffa_ch15_gcd.kv 195
ffa_ch14_barrett.kv 196 end FZ_LoMul;