File : fz_qshft.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 Iron; use Iron;
21 with Word_Ops; use Word_Ops;
22 with W_Pred; use W_Pred;
23 with W_Shifts; use W_Shifts;
24 with FZ_Basic; use FZ_Basic;
25 with FZ_Shift; use FZ_Shift;
26
27
28 package body FZ_QShft is
29
30 -- Constant-time subword shift, for where there is no barrel shifter
31 procedure FZ_Quiet_ShiftRight_SubW_Soft(N : in FZ;
32 ShiftedN : in out FZ;
33 Count : in WBit_Index) is
34 Nw : constant Word := Word(Count);
35 nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
36 Ni : Word := 0; -- Current word
37 C : Word := 0; -- Current carry
38 S : Positive; -- Current shiftness level
39 B : Word; -- Quantity of shift (bitwalked over)
40 CB : Word; -- Quantity of carry counter-shift (bitwalked over)
41 St : Word; -- Temporary word shift candidate
42 Ct : Word; -- Temporary carry counter-shift candidate
43 begin
44 for i in reverse N'Range loop
45 Ni := N(i);
46 ShiftedN(i) := C;
47 C := W_Mux(Ni, 0, nC);
48 S := 1;
49 B := Nw;
50 CB := Word(Bitness) - B;
51 -- For each shift level (of the subword shiftvalue width) :
52 for j in 1 .. BitnessLog2 loop
53 -- Shift and mux the current word
54 St := Shift_Right(Ni, S);
55 Ni := W_Mux(Ni, St, B and 1);
56 -- Shift and mux the current carry
57 Ct := Shift_Left(C, S);
58 C := W_Mux(C, Ct, CB and 1);
59 -- Go to the next shiftness level
60 S := S * 2;
61 B := Shift_Right(B, 1);
62 CB := Shift_Right(CB, 1);
63 end loop;
64 -- Slide in the carry from the previous shift
65 ShiftedN(i) := ShiftedN(i) or Ni;
66 end loop;
67 end FZ_Quiet_ShiftRight_SubW_Soft;
68
69
70 -- Constant-time subword shift, for where there is no barrel shifter
71 procedure FZ_Quiet_ShiftLeft_SubW_Soft(N : in FZ;
72 ShiftedN : in out FZ;
73 Count : in WBit_Index) is
74 Nw : constant Word := Word(Count);
75 nC : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
76 Ni : Word := 0; -- Current word
77 C : Word := 0; -- Current carry
78 S : Positive; -- Current shiftness level
79 B : Word; -- Quantity of shift (bitwalked over)
80 CB : Word; -- Quantity of carry counter-shift (bitwalked over)
81 St : Word; -- Temporary word shift candidate
82 Ct : Word; -- Temporary carry counter-shift candidate
83 begin
84 for i in N'Range loop
85 Ni := N(i);
86 ShiftedN(i) := C;
87 C := W_Mux(Ni, 0, nC);
88 S := 1;
89 B := Nw;
90 CB := Word(Bitness) - B;
91 -- For each shift level (of the subword shiftvalue width) :
92 for j in 1 .. BitnessLog2 loop
93 -- Shift and mux the current word
94 St := Shift_Left(Ni, S);
95 Ni := W_Mux(Ni, St, B and 1);
96 -- Shift and mux the current carry
97 Ct := Shift_Right(C, S);
98 C := W_Mux(C, Ct, CB and 1);
99 -- Go to the next shiftness level
100 S := S * 2;
101 B := Shift_Right(B, 1);
102 CB := Shift_Right(CB, 1);
103 end loop;
104 -- Slide in the carry from the previous shift
105 ShiftedN(i) := ShiftedN(i) or Ni;
106 end loop;
107 end FZ_Quiet_ShiftLeft_SubW_Soft;
108
109
110 -- Constant-time arbitrary Right-Shift.
111 procedure FZ_Quiet_ShiftRight(N : in FZ;
112 ShiftedN : in out FZ;
113 Count : in FZBit_Index) is
114
115 -- Total number of bit positions to shift by
116 C : constant Word := Word(Count);
117
118 -- Number of sub-Word bit positions to shift by
119 Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1));
120
121 -- The Bitness of N's Length
122 Wb : constant Positive := FZ_Bitness_Log2(N);
123
124 -- Number of whole-Word bitnesses to shift by
125 Words : Word := Shift_Right(C, BitnessLog2);
126
127 -- Current 'shiftness level'
128 S : Indices := 1;
129
130 begin
131
132 -- Subword shift first:
133 if HaveBarrelShifter then
134 -- If permitted, use iron shifter:
135 FZ_ShiftRight(N, ShiftedN, Bits);
136 else
137 -- Otherwise, use the soft subword shifter:
138 FZ_Quiet_ShiftRight_SubW_Soft(N, ShiftedN, Bits);
139 end if;
140
141 -- Then whole-Word shift:
142 for i in 1 .. Wb loop
143
144 declare
145
146 -- Current bit of Words
147 WordsBit : constant WBool := Words and 1;
148
149 begin
150
151 -- Shift at the current shiftness
152 for i in ShiftedN'First .. ShiftedN'Last - S loop
153 ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i + S), WordsBit);
154 end loop;
155
156 -- Fill the emptiness
157 for i in ShiftedN'Last - S + 1 .. ShiftedN'Last loop
158 ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit);
159 end loop;
160
161 -- Go to the next shiftness level
162 S := S * 2;
163 Words := Shift_Right(Words, 1);
164
165 end;
166
167 end loop;
168
169 end FZ_Quiet_ShiftRight;
170
171
172 -- Constant-time arbitrary Left-Shift.
173 procedure FZ_Quiet_ShiftLeft(N : in FZ;
174 ShiftedN : in out FZ;
175 Count : in FZBit_Index) is
176
177 -- Total number of bit positions to shift by
178 C : constant Word := Word(Count);
179
180 -- Number of sub-Word bit positions to shift by
181 Bits : constant Natural := Natural(C and (2**BitnessLog2 - 1));
182
183 -- The Bitness of N's Length
184 Wb : constant Positive := FZ_Bitness_Log2(N);
185
186 -- Number of whole-Word bitnesses to shift by
187 Words : Word := Shift_Right(C, BitnessLog2);
188
189 -- Current 'shiftness level'
190 S : Indices := 1;
191
192 begin
193
194 -- Subword shift first:
195 if HaveBarrelShifter then
196 -- If permitted, use iron shifter:
197 FZ_ShiftLeft(N, ShiftedN, Bits);
198 else
199 -- Otherwise, use the soft subword shifter:
200 FZ_Quiet_ShiftLeft_SubW_Soft(N, ShiftedN, Bits);
201 end if;
202
203 -- Then whole-Word shift:
204 for i in 1 .. Wb loop
205
206 declare
207
208 -- Current bit of Words
209 WordsBit : constant WBool := Words and 1;
210
211 begin
212
213 -- Shift at the current shiftness
214 for i in reverse ShiftedN'First + S .. ShiftedN'Last loop
215 ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i - S), WordsBit);
216 end loop;
217
218 -- Fill the emptiness
219 for i in ShiftedN'First .. ShiftedN'First + S - 1 loop
220 ShiftedN(i) := W_Mux(ShiftedN(i), 0, WordsBit);
221 end loop;
222
223 -- Go to the next shiftness level
224 S := S * 2;
225 Words := Shift_Right(Words, 1);
226
227 end;
228
229 end loop;
230
231 end FZ_Quiet_ShiftLeft;
232
233 end FZ_QShft;