Debian Codegraph @

crypto_kem/6688128pcf/avx/fft_tr.c

raw
1 /*
2 This file is for transpose of the Gao-Mateer FFT
3 Functions with names ending with _tr are (roughly) the transpose of the corresponding functions in fft.c
4
5 For the implementation strategy, see
6 https://eprint.iacr.org/2017/793.pdf
7 */
8 // 20240805 djb: more cryptoint usage
9 // 20240508 djb: include vec{128,256}_gf.h
10 // 20221230 djb: split these arrays into separate .c files
11 // 20221230 djb: rename consts array as fft_consts
12 // 20221230 djb: rename s array as fft_scalars_4x
13 // 20221230 djb: add linker lines
14
15 // linker define fft_tr
16 // linker use vec128_mul_asm
17 // linker use vec256_mul_asm
18 // linker use vec256_ama_asm
19 // linker use transpose_64x256_sp_asm
20 // linker use fft_scalars_4x fft_consts
21
22 #include "vec128_gf.h"
23 #include "vec256_gf.h"
24 #include "fft_tr.h"
25 #include "fft_scalars_4x.h"
26 #include "fft_consts.h"
27
28 #include "transpose.h"
29
30 #include <stdint.h>
31 #include "crypto_int64.h"
32
33 static void radix_conversions_tr(vec256 *in)
34 {
35 int i, j, k;
36 vec256 t;
37 uint64_t v[4];
38
39 const vec256 mask[6][2] =
40 {
41 {vec256_set4x(0x2222222222222222, 0x2222222222222222, 0x2222222222222222, 0x2222222222222222),
42 vec256_set4x(0x4444444444444444, 0x4444444444444444, 0x4444444444444444, 0x4444444444444444)},
43 {vec256_set4x(0x0C0C0C0C0C0C0C0C, 0x0C0C0C0C0C0C0C0C, 0x0C0C0C0C0C0C0C0C, 0x0C0C0C0C0C0C0C0C),
44 vec256_set4x(0x3030303030303030, 0x3030303030303030, 0x3030303030303030, 0x3030303030303030)},
45 {vec256_set4x(0x00F000F000F000F0, 0x00F000F000F000F0, 0x00F000F000F000F0, 0x00F000F000F000F0),
46 vec256_set4x(0x0F000F000F000F00, 0x0F000F000F000F00, 0x0F000F000F000F00, 0x0F000F000F000F00)},
47 {vec256_set4x(0x0000FF000000FF00, 0x0000FF000000FF00, 0x0000FF000000FF00, 0x0000FF000000FF00),
48 vec256_set4x(0x00FF000000FF0000, 0x00FF000000FF0000, 0x00FF000000FF0000, 0x00FF000000FF0000)},
49 {vec256_set4x(0x00000000FFFF0000, 0x00000000FFFF0000, 0x00000000FFFF0000, 0x00000000FFFF0000),
50 vec256_set4x(0x0000FFFF00000000, 0x0000FFFF00000000, 0x0000FFFF00000000, 0x0000FFFF00000000)},
51 {vec256_set4x(0xFFFFFFFF00000000, 0xFFFFFFFF00000000, 0xFFFFFFFF00000000, 0xFFFFFFFF00000000),
52 vec256_set4x(0x00000000FFFFFFFF, 0x00000000FFFFFFFF, 0x00000000FFFFFFFF, 0x00000000FFFFFFFF)}
53 };
54
55 //
56
57 for (j = 6; j >= 0; j--)
58 {
59 if (j < 6)
60 {
61 vec256_mul(in, in, fft_scalars_4x[j]); // scaling
62 }
63
64 for (k = j; k <= 4; k++)
65 for (i = 0; i < GFBITS; i++)
66 {
67 t = vec256_and(in[i], mask[k][0]);
68 t = vec256_sll_4x(t, 1 << k);
69 in[i] = vec256_xor(in[i], t);
70
71 t = vec256_and(in[i], mask[k][1]);
72 t = vec256_sll_4x(t, 1 << k);
73 in[i] = vec256_xor(in[i], t);
74 }
75
76 if (j <= 5)
77 for (i = 0; i < GFBITS; i++)
78 {
79 v[0] = vec256_extract(in[i], 0);
80 v[1] = vec256_extract(in[i], 1);
81 v[2] = vec256_extract(in[i], 2);
82 v[3] = vec256_extract(in[i], 3);
83
84 v[1] ^= v[0] >> 32;
85 v[1] ^= v[1] << 32;
86 v[3] ^= v[2] >> 32;
87 v[3] ^= v[3] << 32;
88
89 in[i] = vec256_set4x(v[0], v[1], v[2], v[3]);
90 }
91
92 for (i = 0; i < GFBITS; i++)
93 {
94 v[0] = vec256_extract(in[i], 0);
95 v[1] = vec256_extract(in[i], 1);
96 v[2] = vec256_extract(in[i], 2);
97 v[3] = vec256_extract(in[i], 3);
98
99 v[2] ^= v[1];
100 v[3] ^= v[2];
101
102 in[i] = vec256_set4x(v[0], v[1], v[2], v[3]);
103 }
104
105 }
106 }
107
108 static void butterflies_tr(vec256 *out, vec256 in[][ GFBITS ])
109 {
110 int i, j, k, s, b;
111
112 vec256 t0[ GFBITS ];
113 vec256 t1[ GFBITS ];
114 vec256 t;
115
116 vec128 out128[ GFBITS ][ 2 ];
117 vec128 tmp[ GFBITS ];
118
119 union {
120 vec128 v[6][ GFBITS+1 ];
121 vec256 V[6][ (GFBITS+1)/2 ];
122 } pre;
123
124 union {
125 vec128 v[64][ 2 ];
126 vec256 V[64];
127 } buf;
128
129 uint64_t v[4];
130 uint64_t consts_ptr = 33;
131
132 const unsigned char reversal[] =
133 {
134 0, 32, 16, 48, 8, 40, 24, 56,
135 4, 36, 20, 52, 12, 44, 28, 60,
136 2, 34, 18, 50, 10, 42, 26, 58,
137 6, 38, 22, 54, 14, 46, 30, 62,
138 1, 33, 17, 49, 9, 41, 25, 57,
139 5, 37, 21, 53, 13, 45, 29, 61,
140 3, 35, 19, 51, 11, 43, 27, 59,
141 7, 39, 23, 55, 15, 47, 31, 63
142 };
143
144 const uint16_t beta[6] = {5246, 5306, 6039, 6685, 4905, 6755};
145
146 // butterflies
147
148 for (i = 4; i >= 0; i--)
149 {
150 s = 1 << i;
151 consts_ptr -= s;
152
153 for (j = 0; j < 32; j += 2*s)
154 for (k = j; k < j+s; k++)
155 {
156 vec256_ama_asm(in[k], in[k+s], fft_consts[ consts_ptr + (k-j) ]);
157 }
158
159 }
160
161 for (k = 0; k < 32; k+=2)
162 {
163 for (b = 0; b < GFBITS; b++) t0[b] = vec256_unpack_low(in[k][b], in[k+1][b]);
164 for (b = 0; b < GFBITS; b++) t1[b] = vec256_unpack_high(in[k][b], in[k+1][b]);
165
166 vec256_ama_asm(t0, t1, fft_consts[1]);
167
168 for (b = 0; b < GFBITS; b++) in[k][b] = vec256_unpack_low(t0[b], t1[b]);
169 for (b = 0; b < GFBITS; b++) in[k+1][b] = vec256_unpack_high(t0[b], t1[b]);
170
171 for (b = 0; b < GFBITS; b++) t0[b] = vec256_unpack_low_2x(in[k][b], in[k+1][b]);
172 for (b = 0; b < GFBITS; b++) t1[b] = vec256_unpack_high_2x(in[k][b], in[k+1][b]);
173
174 vec256_ama_asm(t0, t1, fft_consts[0]);
175
176 for (b = 0; b < GFBITS; b++) in[k+0][b] = vec256_unpack_low_2x(t0[b], t1[b]);
177 for (b = 0; b < GFBITS; b++) in[k+1][b] = vec256_unpack_high_2x(t0[b], t1[b]);
178 }
179
180
181 // boradcast
182
183 for (i = 0; i < GFBITS; i+=2)
184 {
185 // transpose
186
187 for (k = 0; k < 32; k++)
188 {
189 if (i != GFBITS-1) {
190 buf.v[ reversal[2*k+0] ][1] = vec256_extract2x(in[ k ][i+1], 0);
191 buf.v[ reversal[2*k+1] ][1] = vec256_extract2x(in[ k ][i+1], 1);
192 }
193
194 buf.v[ reversal[2*k+0] ][0] = vec256_extract2x(in[ k ][i+0], 0);
195 buf.v[ reversal[2*k+1] ][0] = vec256_extract2x(in[ k ][i+0], 1);
196 }
197
198 transpose_64x256_sp(buf.V);
199
200 //
201
202 #define XOR vec256_xor
203
204 pre.V[0][i/2] = buf.V[32]; buf.V[33] = XOR(buf.V[33], buf.V[32]);
205 pre.V[1][i/2] = buf.V[33]; buf.V[35] = XOR(buf.V[35], buf.V[33]);
206 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[35]); buf.V[34] = XOR(buf.V[34], buf.V[35]);
207 pre.V[2][i/2] = buf.V[34]; buf.V[38] = XOR(buf.V[38], buf.V[34]);
208 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[38]); buf.V[39] = XOR(buf.V[39], buf.V[38]);
209 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[39]); buf.V[37] = XOR(buf.V[37], buf.V[39]);
210 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[37]); buf.V[36] = XOR(buf.V[36], buf.V[37]);
211 pre.V[3][i/2] = buf.V[36]; buf.V[44] = XOR(buf.V[44], buf.V[36]);
212 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[44]); buf.V[45] = XOR(buf.V[45], buf.V[44]);
213 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[45]); buf.V[47] = XOR(buf.V[47], buf.V[45]);
214 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[47]); buf.V[46] = XOR(buf.V[46], buf.V[47]);
215 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[46]); buf.V[42] = XOR(buf.V[42], buf.V[46]);
216 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[42]); buf.V[43] = XOR(buf.V[43], buf.V[42]);
217 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[43]); buf.V[41] = XOR(buf.V[41], buf.V[43]);
218 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[41]); buf.V[40] = XOR(buf.V[40], buf.V[41]);
219 pre.V[4][i/2] = buf.V[40]; buf.V[56] = XOR(buf.V[56], buf.V[40]);
220 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[56]); buf.V[57] = XOR(buf.V[57], buf.V[56]);
221 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[57]); buf.V[59] = XOR(buf.V[59], buf.V[57]);
222 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[59]); buf.V[58] = XOR(buf.V[58], buf.V[59]);
223 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[58]); buf.V[62] = XOR(buf.V[62], buf.V[58]);
224 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[62]); buf.V[63] = XOR(buf.V[63], buf.V[62]);
225 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[63]); buf.V[61] = XOR(buf.V[61], buf.V[63]);
226 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[61]); buf.V[60] = XOR(buf.V[60], buf.V[61]);
227 pre.V[3][i/2] = XOR(pre.V[3][i/2], buf.V[60]); buf.V[52] = XOR(buf.V[52], buf.V[60]);
228 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[52]); buf.V[53] = XOR(buf.V[53], buf.V[52]);
229 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[53]); buf.V[55] = XOR(buf.V[55], buf.V[53]);
230 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[55]); buf.V[54] = XOR(buf.V[54], buf.V[55]);
231 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[54]); buf.V[50] = XOR(buf.V[50], buf.V[54]);
232 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[50]); buf.V[51] = XOR(buf.V[51], buf.V[50]);
233 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[51]); buf.V[49] = XOR(buf.V[49], buf.V[51]);
234 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[49]); buf.V[48] = XOR(buf.V[48], buf.V[49]);
235 pre.V[5][i/2] = buf.V[48]; buf.V[16] = XOR(buf.V[16], buf.V[48]);
236 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[16]); buf.V[17] = XOR(buf.V[17], buf.V[16]);
237 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[17]); buf.V[19] = XOR(buf.V[19], buf.V[17]);
238 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[19]); buf.V[18] = XOR(buf.V[18], buf.V[19]);
239 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[18]); buf.V[22] = XOR(buf.V[22], buf.V[18]);
240 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[22]); buf.V[23] = XOR(buf.V[23], buf.V[22]);
241 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[23]); buf.V[21] = XOR(buf.V[21], buf.V[23]);
242 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[21]); buf.V[20] = XOR(buf.V[20], buf.V[21]);
243 pre.V[3][i/2] = XOR(pre.V[3][i/2], buf.V[20]); buf.V[28] = XOR(buf.V[28], buf.V[20]);
244 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[28]); buf.V[29] = XOR(buf.V[29], buf.V[28]);
245 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[29]); buf.V[31] = XOR(buf.V[31], buf.V[29]);
246 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[31]); buf.V[30] = XOR(buf.V[30], buf.V[31]);
247 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[30]); buf.V[26] = XOR(buf.V[26], buf.V[30]);
248 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[26]); buf.V[27] = XOR(buf.V[27], buf.V[26]);
249 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[27]); buf.V[25] = XOR(buf.V[25], buf.V[27]);
250 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[25]); buf.V[24] = XOR(buf.V[24], buf.V[25]);
251 pre.V[4][i/2] = XOR(pre.V[4][i/2], buf.V[24]); buf.V[8] = XOR(buf.V[8], buf.V[24]);
252 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[8]); buf.V[9] = XOR(buf.V[9], buf.V[8]);
253 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[9]); buf.V[11] = XOR(buf.V[11], buf.V[9]);
254 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[11]); buf.V[10] = XOR(buf.V[10], buf.V[11]);
255 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[10]); buf.V[14] = XOR(buf.V[14], buf.V[10]);
256 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[14]); buf.V[15] = XOR(buf.V[15], buf.V[14]);
257 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[15]); buf.V[13] = XOR(buf.V[13], buf.V[15]);
258 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[13]); buf.V[12] = XOR(buf.V[12], buf.V[13]);
259 pre.V[3][i/2] = XOR(pre.V[3][i/2], buf.V[12]); buf.V[4] = XOR(buf.V[4], buf.V[12]);
260 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[4]); buf.V[5] = XOR(buf.V[5], buf.V[4]);
261 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[5]); buf.V[7] = XOR(buf.V[7], buf.V[5]);
262 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[7]); buf.V[6] = XOR(buf.V[6], buf.V[7]);
263 pre.V[2][i/2] = XOR(pre.V[2][i/2], buf.V[6]); buf.V[2] = XOR(buf.V[2], buf.V[6]);
264 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[2]); buf.V[3] = XOR(buf.V[3], buf.V[2]);
265 pre.V[1][i/2] = XOR(pre.V[1][i/2], buf.V[3]); buf.V[1] = XOR(buf.V[1], buf.V[3]);
266
267 pre.V[0][i/2] = XOR(pre.V[0][i/2], buf.V[1]); t = XOR(buf.V[0], buf.V[1]);
268
269 if (i != GFBITS-1)
270 out128[i+1][0] = vec256_extract2x(t, 1);
271 out128[i+0][0] = vec256_extract2x(t, 0);
272 #undef XOR
273
274 }
275
276 //
277
278 for (j = 0; j < GFBITS; j++) tmp[j] = vec128_setbits(crypto_int64_bitmod_01(beta[0], j));
279
280 vec128_mul(tmp, pre.v[0], tmp);
281
282 for (b = 0; b < GFBITS; b++) out128[b][1] = tmp[b];
283
284 for (i = 1; i < 6; i++)
285 {
286 for (j = 0; j < GFBITS; j++) tmp[j] = vec128_setbits(crypto_int64_bitmod_01(beta[i], j));
287
288 vec128_mul(tmp, pre.v[i], tmp);
289
290 for (b = 0; b < GFBITS; b++) out128[b][1] = vec128_xor(out128[b][1], tmp[b]);
291 }
292
293 for (b = 0; b < GFBITS; b++)
294 {
295 v[0] = vec128_extract(out128[b][0], 0);
296 v[1] = vec128_extract(out128[b][0], 1);
297 v[2] = vec128_extract(out128[b][1], 0);
298 v[3] = vec128_extract(out128[b][1], 1);
299
300 out[b] = vec256_set4x(v[0], v[1], v[2], v[3]);
301 }
302 }
303
304 void fft_tr(vec256 *out, vec256 in[][ GFBITS ])
305 {
306 butterflies_tr(out, in);
307 radix_conversions_tr(out);
308 }
309