Debian Codegraph @

crypto_kem/348864pcf/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 use of cryptoint
9 // 20240508 djb: include vec128_gf.h, vec256_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_2x
13 // 20221230 djb: add linker lines
14
15 // linker define fft_tr
16 // linker use vec_mul_asm
17 // linker use vec128_mul_asm
18 // linker use vec256_mul_asm
19 // linker use transpose_64x256_sp_asm
20 // linker use fft_scalars_2x fft_consts
21
22 #include "vec128_gf.h"
23 #include "vec256_gf.h"
24 #include "fft_tr.h"
25 #include "fft_scalars_2x.h"
26 #include "fft_consts.h"
27
28 #include "transpose.h"
29 #include "vec.h"
30
31 #include <stdint.h>
32 #include "crypto_int64.h"
33
34 static void radix_conversions_tr(vec128 in[ GFBITS ])
35 {
36 int i, j, k;
37
38 const vec128 mask[10] =
39 {
40 vec128_set2x(0x2222222222222222, 0x2222222222222222),
41 vec128_set2x(0x4444444444444444, 0x4444444444444444),
42 vec128_set2x(0x0C0C0C0C0C0C0C0C, 0x0C0C0C0C0C0C0C0C),
43 vec128_set2x(0x3030303030303030, 0x3030303030303030),
44 vec128_set2x(0x00F000F000F000F0, 0x00F000F000F000F0),
45 vec128_set2x(0x0F000F000F000F00, 0x0F000F000F000F00),
46 vec128_set2x(0x0000FF000000FF00, 0x0000FF000000FF00),
47 vec128_set2x(0x00FF000000FF0000, 0x00FF000000FF0000),
48 vec128_set2x(0x00000000FFFF0000, 0x00000000FFFF0000),
49 vec128_set2x(0x0000FFFF00000000, 0x0000FFFF00000000)
50 };
51
52 uint64_t v0, v1;
53
54 //
55
56 for (j = 5; j >= 0; j--)
57 {
58
59 if (j < 5) vec128_mul(in, in, fft_scalars_2x[j]);
60
61 for (i = 0; i < GFBITS; i++)
62 for (k = j; k <= 4; k++)
63 {
64 in[i] ^= vec128_sll_2x(in[i] & mask[2*k+0], 1 << k);
65 in[i] ^= vec128_sll_2x(in[i] & mask[2*k+1], 1 << k);
66 }
67
68 for (i = 0; i < GFBITS; i++)
69 {
70 v0 = vec128_extract(in[i], 0);
71 v1 = vec128_extract(in[i], 1);
72
73 v1 ^= v0 >> 32;
74 v1 ^= v1 << 32;
75
76 in[i] = vec128_set2x(v0, v1);
77 }
78 }
79 }
80
81 static void butterflies_tr(vec128 out[ GFBITS ], vec256 in[][ GFBITS ])
82 {
83 int i, j, k, s, b;
84
85 uint64_t tmp[ GFBITS ];
86 uint64_t pre[6][ GFBITS ];
87 uint64_t out64[2][64];
88
89 vec256 p2[ 6 ];
90 vec256 buf[64];
91 vec256 x[ GFBITS ], y[ GFBITS ];
92 vec256 tmp256[ GFBITS ];
93
94 uint64_t consts_ptr = 17;
95
96 const unsigned char reversal[64] =
97 {
98 0, 32, 16, 48, 8, 40, 24, 56,
99 4, 36, 20, 52, 12, 44, 28, 60,
100 2, 34, 18, 50, 10, 42, 26, 58,
101 6, 38, 22, 54, 14, 46, 30, 62,
102 1, 33, 17, 49, 9, 41, 25, 57,
103 5, 37, 21, 53, 13, 45, 29, 61,
104 3, 35, 19, 51, 11, 43, 27, 59,
105 7, 39, 23, 55, 15, 47, 31, 63
106 };
107
108 const uint16_t beta[6] = {8, 1300, 3408, 1354, 2341, 1154};
109
110 // butterflies
111
112 for (i = 3; i >= 0; i--)
113 {
114 s = 1 << i;
115 consts_ptr -= s;
116
117 for (j = 0; j < 16; j += 2*s)
118 {
119 for (k = j; k < j+s; k++)
120 {
121 for (b = 0; b < GFBITS; b++) in[k][b] ^= in[k+s][b];
122 vec256_mul(tmp256, in[k], fft_consts[ consts_ptr + (k-j) ]);
123 for (b = 0; b < GFBITS; b++) in[k+s][b] ^= tmp256[b];
124 }
125 }
126 }
127
128 for (i = 0; i < 16; i+=2)
129 {
130 for (b = 0; b < GFBITS; b++) x[b] = vec256_unpack_low(in[i+0][b], in[i+1][b]);
131 for (b = 0; b < GFBITS; b++) y[b] = vec256_unpack_high(in[i+0][b], in[i+1][b]);
132
133 for (b = 0; b < GFBITS; b++) x[b] ^= y[b];
134 vec256_mul(tmp256, x, fft_consts[ 1 ]);
135 for (b = 0; b < GFBITS; b++) y[b] ^= tmp256[b];
136
137 for (b = 0; b < GFBITS; b++) in[i+0][b] = vec256_unpack_low_2x(x[b], y[b]);
138 for (b = 0; b < GFBITS; b++) in[i+1][b] = vec256_unpack_high_2x(x[b], y[b]);
139 }
140
141 for (i = 0; i < 16; i+=2)
142 {
143 for (b = 0; b < GFBITS; b++) in[i+0][b] ^= in[i+1][b];
144 vec256_mul(tmp256, in[i+0], fft_consts[ 0 ]);
145 for (b = 0; b < GFBITS; b++) in[i+1][b] ^= tmp256[b];
146 }
147
148 // transpose
149
150 for (i = 0; i < GFBITS; i+=4)
151 {
152 for (j = 0; j < 64; j+=8)
153 {
154 buf[ reversal[j+0] ] = vec256_set4x(vec256_extract(in[j/4+0][i+0], 0),
155 vec256_extract(in[j/4+0][i+1], 0),
156 vec256_extract(in[j/4+0][i+2], 0),
157 vec256_extract(in[j/4+0][i+3], 0));
158 buf[ reversal[j+1] ] = vec256_set4x(vec256_extract(in[j/4+1][i+0], 0),
159 vec256_extract(in[j/4+1][i+1], 0),
160 vec256_extract(in[j/4+1][i+2], 0),
161 vec256_extract(in[j/4+1][i+3], 0));
162 buf[ reversal[j+2] ] = vec256_set4x(vec256_extract(in[j/4+0][i+0], 1),
163 vec256_extract(in[j/4+0][i+1], 1),
164 vec256_extract(in[j/4+0][i+2], 1),
165 vec256_extract(in[j/4+0][i+3], 1));
166 buf[ reversal[j+3] ] = vec256_set4x(vec256_extract(in[j/4+1][i+0], 1),
167 vec256_extract(in[j/4+1][i+1], 1),
168 vec256_extract(in[j/4+1][i+2], 1),
169 vec256_extract(in[j/4+1][i+3], 1));
170 buf[ reversal[j+4] ] = vec256_set4x(vec256_extract(in[j/4+0][i+0], 2),
171 vec256_extract(in[j/4+0][i+1], 2),
172 vec256_extract(in[j/4+0][i+2], 2),
173 vec256_extract(in[j/4+0][i+3], 2));
174 buf[ reversal[j+5] ] = vec256_set4x(vec256_extract(in[j/4+1][i+0], 2),
175 vec256_extract(in[j/4+1][i+1], 2),
176 vec256_extract(in[j/4+1][i+2], 2),
177 vec256_extract(in[j/4+1][i+3], 2));
178 buf[ reversal[j+6] ] = vec256_set4x(vec256_extract(in[j/4+0][i+0], 3),
179 vec256_extract(in[j/4+0][i+1], 3),
180 vec256_extract(in[j/4+0][i+2], 3),
181 vec256_extract(in[j/4+0][i+3], 3));
182 buf[ reversal[j+7] ] = vec256_set4x(vec256_extract(in[j/4+1][i+0], 3),
183 vec256_extract(in[j/4+1][i+1], 3),
184 vec256_extract(in[j/4+1][i+2], 3),
185 vec256_extract(in[j/4+1][i+3], 3));
186 }
187
188 transpose_64x256_sp(buf);
189
190 p2[0] = buf[32]; buf[33] = vec256_xor(buf[33], buf[32]);
191 p2[1] = buf[33]; buf[35] = vec256_xor(buf[35], buf[33]);
192 p2[0] = vec256_xor(p2[0], buf[35]); buf[34] = vec256_xor(buf[34], buf[35]);
193 p2[2] = buf[34]; buf[38] = vec256_xor(buf[38], buf[34]);
194 p2[0] = vec256_xor(p2[0], buf[38]); buf[39] = vec256_xor(buf[39], buf[38]);
195 p2[1] = vec256_xor(p2[1], buf[39]); buf[37] = vec256_xor(buf[37], buf[39]);
196 p2[0] = vec256_xor(p2[0], buf[37]); buf[36] = vec256_xor(buf[36], buf[37]);
197 p2[3] = buf[36]; buf[44] = vec256_xor(buf[44], buf[36]);
198 p2[0] = vec256_xor(p2[0], buf[44]); buf[45] = vec256_xor(buf[45], buf[44]);
199 p2[1] = vec256_xor(p2[1], buf[45]); buf[47] = vec256_xor(buf[47], buf[45]);
200 p2[0] = vec256_xor(p2[0], buf[47]); buf[46] = vec256_xor(buf[46], buf[47]);
201 p2[2] = vec256_xor(p2[2], buf[46]); buf[42] = vec256_xor(buf[42], buf[46]);
202 p2[0] = vec256_xor(p2[0], buf[42]); buf[43] = vec256_xor(buf[43], buf[42]);
203 p2[1] = vec256_xor(p2[1], buf[43]); buf[41] = vec256_xor(buf[41], buf[43]);
204 p2[0] = vec256_xor(p2[0], buf[41]); buf[40] = vec256_xor(buf[40], buf[41]);
205 p2[4] = buf[40]; buf[56] = vec256_xor(buf[56], buf[40]);
206 p2[0] = vec256_xor(p2[0], buf[56]); buf[57] = vec256_xor(buf[57], buf[56]);
207 p2[1] = vec256_xor(p2[1], buf[57]); buf[59] = vec256_xor(buf[59], buf[57]);
208 p2[0] = vec256_xor(p2[0], buf[59]); buf[58] = vec256_xor(buf[58], buf[59]);
209 p2[2] = vec256_xor(p2[2], buf[58]); buf[62] = vec256_xor(buf[62], buf[58]);
210 p2[0] = vec256_xor(p2[0], buf[62]); buf[63] = vec256_xor(buf[63], buf[62]);
211 p2[1] = vec256_xor(p2[1], buf[63]); buf[61] = vec256_xor(buf[61], buf[63]);
212 p2[0] = vec256_xor(p2[0], buf[61]); buf[60] = vec256_xor(buf[60], buf[61]);
213 p2[3] = vec256_xor(p2[3], buf[60]); buf[52] = vec256_xor(buf[52], buf[60]);
214 p2[0] = vec256_xor(p2[0], buf[52]); buf[53] = vec256_xor(buf[53], buf[52]);
215 p2[1] = vec256_xor(p2[1], buf[53]); buf[55] = vec256_xor(buf[55], buf[53]);
216 p2[0] = vec256_xor(p2[0], buf[55]); buf[54] = vec256_xor(buf[54], buf[55]);
217 p2[2] = vec256_xor(p2[2], buf[54]); buf[50] = vec256_xor(buf[50], buf[54]);
218 p2[0] = vec256_xor(p2[0], buf[50]); buf[51] = vec256_xor(buf[51], buf[50]);
219 p2[1] = vec256_xor(p2[1], buf[51]); buf[49] = vec256_xor(buf[49], buf[51]);
220 p2[0] = vec256_xor(p2[0], buf[49]); buf[48] = vec256_xor(buf[48], buf[49]);
221 p2[5] = buf[48]; buf[16] = vec256_xor(buf[16], buf[48]);
222 p2[0] = vec256_xor(p2[0], buf[16]); buf[17] = vec256_xor(buf[17], buf[16]);
223 p2[1] = vec256_xor(p2[1], buf[17]); buf[19] = vec256_xor(buf[19], buf[17]);
224 p2[0] = vec256_xor(p2[0], buf[19]); buf[18] = vec256_xor(buf[18], buf[19]);
225 p2[2] = vec256_xor(p2[2], buf[18]); buf[22] = vec256_xor(buf[22], buf[18]);
226 p2[0] = vec256_xor(p2[0], buf[22]); buf[23] = vec256_xor(buf[23], buf[22]);
227 p2[1] = vec256_xor(p2[1], buf[23]); buf[21] = vec256_xor(buf[21], buf[23]);
228 p2[0] = vec256_xor(p2[0], buf[21]); buf[20] = vec256_xor(buf[20], buf[21]);
229 p2[3] = vec256_xor(p2[3], buf[20]); buf[28] = vec256_xor(buf[28], buf[20]);
230 p2[0] = vec256_xor(p2[0], buf[28]); buf[29] = vec256_xor(buf[29], buf[28]);
231 p2[1] = vec256_xor(p2[1], buf[29]); buf[31] = vec256_xor(buf[31], buf[29]);
232 p2[0] = vec256_xor(p2[0], buf[31]); buf[30] = vec256_xor(buf[30], buf[31]);
233 p2[2] = vec256_xor(p2[2], buf[30]); buf[26] = vec256_xor(buf[26], buf[30]);
234 p2[0] = vec256_xor(p2[0], buf[26]); buf[27] = vec256_xor(buf[27], buf[26]);
235 p2[1] = vec256_xor(p2[1], buf[27]); buf[25] = vec256_xor(buf[25], buf[27]);
236 p2[0] = vec256_xor(p2[0], buf[25]); buf[24] = vec256_xor(buf[24], buf[25]);
237 p2[4] = vec256_xor(p2[4], buf[24]); buf[8] = vec256_xor(buf[8], buf[24]);
238 p2[0] = vec256_xor(p2[0], buf[8]); buf[9] = vec256_xor(buf[9], buf[8]);
239 p2[1] = vec256_xor(p2[1], buf[9]); buf[11] = vec256_xor(buf[11], buf[9]);
240 p2[0] = vec256_xor(p2[0], buf[11]); buf[10] = vec256_xor(buf[10], buf[11]);
241 p2[2] = vec256_xor(p2[2], buf[10]); buf[14] = vec256_xor(buf[14], buf[10]);
242 p2[0] = vec256_xor(p2[0], buf[14]); buf[15] = vec256_xor(buf[15], buf[14]);
243 p2[1] = vec256_xor(p2[1], buf[15]); buf[13] = vec256_xor(buf[13], buf[15]);
244 p2[0] = vec256_xor(p2[0], buf[13]); buf[12] = vec256_xor(buf[12], buf[13]);
245 p2[3] = vec256_xor(p2[3], buf[12]); buf[4] = vec256_xor(buf[4], buf[12]);
246 p2[0] = vec256_xor(p2[0], buf[4]); buf[5] = vec256_xor(buf[5], buf[4]);
247 p2[1] = vec256_xor(p2[1], buf[5]); buf[7] = vec256_xor(buf[7], buf[5]);
248 p2[0] = vec256_xor(p2[0], buf[7]); buf[6] = vec256_xor(buf[6], buf[7]);
249 p2[2] = vec256_xor(p2[2], buf[6]); buf[2] = vec256_xor(buf[2], buf[6]);
250 p2[0] = vec256_xor(p2[0], buf[2]); buf[3] = vec256_xor(buf[3], buf[2]);
251 p2[1] = vec256_xor(p2[1], buf[3]); buf[1] = vec256_xor(buf[1], buf[3]);
252
253 p2[0] = vec256_xor(p2[0], buf[1]); buf[0] = vec256_xor(buf[0], buf[1]);
254
255 for (j = 0; j < 6; j++)
256 {
257 pre[j][i+0] = vec256_extract(p2[j], 0);
258 pre[j][i+1] = vec256_extract(p2[j], 1);
259 pre[j][i+2] = vec256_extract(p2[j], 2);
260 pre[j][i+3] = vec256_extract(p2[j], 3);
261 }
262
263 out64[0][i+0] = vec256_extract(buf[0], 0);
264 out64[0][i+1] = vec256_extract(buf[0], 1);
265 out64[0][i+2] = vec256_extract(buf[0], 2);
266 out64[0][i+3] = vec256_extract(buf[0], 3);
267 }
268
269 //
270
271 for (j = 0; j < GFBITS; j++) { tmp[j] = crypto_int64_bitmod_mask(beta[0], j); }
272
273 vec_mul(out64[1], pre[0], tmp);
274
275 for (i = 1; i < 6; i++)
276 {
277 for (j = 0; j < GFBITS; j++) { tmp[j] = crypto_int64_bitmod_mask(beta[i], j); }
278
279 vec_mul(tmp, pre[i], tmp);
280 vec_add(out64[1], out64[1], tmp);
281 }
282
283 for (i = 0; i < GFBITS; i++)
284 out[i] = vec128_set2x(out64[0][i], out64[1][i]);
285 }
286
287 void fft_tr(vec128 out[GFBITS], vec256 in[][ GFBITS ])
288 {
289 butterflies_tr(out, in);
290 radix_conversions_tr(out);
291 }
292