Debian Codegraph @

crypto_kem/460896pcf/avx/fft.c

raw
1 /*
2 This file is for implementing the Gao-Mateer FFT, see
3 http://www.math.clemson.edu/~sgao/papers/GM10.pdf
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 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_2x
13 // 20221230 djb: add linker lines
14
15 // linker define fft
16 // linker use vec128_mul_asm
17 // linker use vec256_maa_asm
18 // linker use transpose_64x256_sp_asm
19 // linker use fft_scalars_2x fft_consts
20
21 #include "fft.h"
22 #include "fft_scalars_2x.h"
23 #include "fft_consts.h"
24
25 #include "transpose.h"
26 #include "vec128_gf.h"
27 #include "vec256_gf.h"
28
29 #include <stdint.h>
30 #include "crypto_int64.h"
31
32 /* input: in, polynomial in bitsliced form */
33 /* output: in, result of applying the radix conversions on in */
34 static void radix_conversions(vec128 *in)
35 {
36 int i, j, k;
37 vec128 t;
38 uint64_t v0, v1;
39
40 const vec128 mask[5][2] =
41 {
42 {vec128_set2x(0x8888888888888888, 0x8888888888888888),
43 vec128_set2x(0x4444444444444444, 0x4444444444444444)},
44 {vec128_set2x(0xC0C0C0C0C0C0C0C0, 0xC0C0C0C0C0C0C0C0),
45 vec128_set2x(0x3030303030303030, 0x3030303030303030)},
46 {vec128_set2x(0xF000F000F000F000, 0xF000F000F000F000),
47 vec128_set2x(0x0F000F000F000F00, 0x0F000F000F000F00)},
48 {vec128_set2x(0xFF000000FF000000, 0xFF000000FF000000),
49 vec128_set2x(0x00FF000000FF0000, 0x00FF000000FF0000)},
50 {vec128_set2x(0xFFFF000000000000, 0xFFFF000000000000),
51 vec128_set2x(0x0000FFFF00000000, 0x0000FFFF00000000)}
52 };
53
54 //
55
56 for (j = 0; j <= 5; j++)
57 {
58 for (i = 0; i < GFBITS; i++)
59 {
60 v1 = vec128_extract(in[i], 1);
61 v1 ^= v1 >> 32;
62 v0 = vec128_extract(in[i], 0);
63 v0 ^= v1 << 32;
64 in[i] = vec128_set2x(v0, v1);
65 }
66
67 for (i = 0; i < GFBITS; i++)
68 for (k = 4; k >= j; k--)
69 {
70 t = vec128_and(in[i], mask[k][0]);
71 t = vec128_srl_2x(t, 1 << k);
72 in[i] = vec128_xor(in[i], t);
73
74 t = vec128_and(in[i], mask[k][1]);
75 t = vec128_srl_2x(t, 1 << k);
76 in[i] = vec128_xor(in[i], t);
77 }
78
79 if (j < 5)
80 vec128_mul(in, in, fft_scalars_2x[j]); // scaling
81 }
82 }
83
84 /* input: in, result of applying the radix conversions to the input polynomial */
85 /* output: out, evaluation results (by applying the FFT butterflies) */
86 static void butterflies(vec256 out[][ GFBITS ], vec128 *in)
87 {
88 int i, j, k, s, b;
89
90 vec128 tmp[ GFBITS ];
91 vec256 tmp0[ GFBITS ];
92 vec256 tmp1[ GFBITS ];
93 vec128 t[ GFBITS ];
94
95 union {
96 vec128 v[8][ GFBITS+1 ];
97 vec256 V[8][ (GFBITS+1)/2 ];
98 } pre;
99
100 union {
101 vec128 v[64][ 2 ];
102 vec256 V[64];
103 } buf;
104
105 uint64_t v0, v1;
106
107 uint64_t consts_ptr = 2;
108
109 const unsigned char reversal[64] =
110 {
111 0, 32, 16, 48, 8, 40, 24, 56,
112 4, 36, 20, 52, 12, 44, 28, 60,
113 2, 34, 18, 50, 10, 42, 26, 58,
114 6, 38, 22, 54, 14, 46, 30, 62,
115 1, 33, 17, 49, 9, 41, 25, 57,
116 5, 37, 21, 53, 13, 45, 29, 61,
117 3, 35, 19, 51, 11, 43, 27, 59,
118 7, 39, 23, 55, 15, 47, 31, 63
119 };
120
121 const uint16_t beta[8] = {2522, 7827, 7801, 8035, 6897, 8167, 3476, 0};
122
123 // boradcast
124
125 for (j = 0; j < GFBITS; j++)
126 t[j] = vec128_unpack_high(in[j], in[j]);
127
128 for (i = 0; i < 8; i+=2)
129 {
130 for (j = 0; j < GFBITS; j++)
131 {
132 v0 = crypto_int64_bitmod_mask(beta[i+0], j);
133 v1 = crypto_int64_bitmod_mask(beta[i+1], j);
134
135 tmp[j] = vec128_set2x(v0, v1);
136 }
137
138 vec128_mul(tmp, t, tmp);
139
140 for (j = 0; j < GFBITS; j++)
141 {
142 pre.v[i+0][j] = vec128_unpack_low(tmp[j], tmp[j]);
143 pre.v[i+1][j] = vec128_unpack_high(tmp[j], tmp[j]);
144 }
145 }
146
147 for (i = 0; i < GFBITS; i+=2)
148 {
149 if (i != GFBITS-1)
150 buf.v[0][1] = vec128_unpack_low(in[i+1], in[i+1] ^ pre.v[6][i+1]);
151 buf.v[0][0] = vec128_unpack_low(in[i+0], in[i+0] ^ pre.v[6][i+0]);
152
153 #define XOR vec256_xor
154
155 buf.V[1] = XOR(buf.V[0], pre.V[0][i/2]); buf.V[16] = XOR(buf.V[0], pre.V[4][i/2]);
156 buf.V[3] = XOR(buf.V[1], pre.V[1][i/2]); buf.V[48] = XOR(buf.V[16], pre.V[5][i/2]);
157 buf.V[49] = XOR(buf.V[48], pre.V[0][i/2]);
158 buf.V[2] = XOR(buf.V[0], pre.V[1][i/2]); buf.V[51] = XOR(buf.V[49], pre.V[1][i/2]);
159 buf.V[6] = XOR(buf.V[2], pre.V[2][i/2]); buf.V[50] = XOR(buf.V[51], pre.V[0][i/2]);
160 buf.V[7] = XOR(buf.V[6], pre.V[0][i/2]); buf.V[54] = XOR(buf.V[50], pre.V[2][i/2]);
161 buf.V[5] = XOR(buf.V[7], pre.V[1][i/2]); buf.V[55] = XOR(buf.V[54], pre.V[0][i/2]);
162 buf.V[53] = XOR(buf.V[55], pre.V[1][i/2]);
163 buf.V[4] = XOR(buf.V[0], pre.V[2][i/2]); buf.V[52] = XOR(buf.V[53], pre.V[0][i/2]);
164 buf.V[12] = XOR(buf.V[4], pre.V[3][i/2]); buf.V[60] = XOR(buf.V[52], pre.V[3][i/2]);
165 buf.V[13] = XOR(buf.V[12], pre.V[0][i/2]); buf.V[61] = XOR(buf.V[60], pre.V[0][i/2]);
166 buf.V[15] = XOR(buf.V[13], pre.V[1][i/2]); buf.V[63] = XOR(buf.V[61], pre.V[1][i/2]);
167 buf.V[14] = XOR(buf.V[15], pre.V[0][i/2]); buf.V[62] = XOR(buf.V[63], pre.V[0][i/2]);
168 buf.V[10] = XOR(buf.V[14], pre.V[2][i/2]); buf.V[58] = XOR(buf.V[62], pre.V[2][i/2]);
169 buf.V[11] = XOR(buf.V[10], pre.V[0][i/2]); buf.V[59] = XOR(buf.V[58], pre.V[0][i/2]);
170 buf.V[9] = XOR(buf.V[11], pre.V[1][i/2]); buf.V[57] = XOR(buf.V[59], pre.V[1][i/2]);
171 buf.V[56] = XOR(buf.V[57], pre.V[0][i/2]);
172 buf.V[8] = XOR(buf.V[0], pre.V[3][i/2]); buf.V[40] = XOR(buf.V[56], pre.V[4][i/2]);
173 buf.V[24] = XOR(buf.V[8], pre.V[4][i/2]); buf.V[41] = XOR(buf.V[40], pre.V[0][i/2]);
174 buf.V[25] = XOR(buf.V[24], pre.V[0][i/2]); buf.V[43] = XOR(buf.V[41], pre.V[1][i/2]);
175 buf.V[27] = XOR(buf.V[25], pre.V[1][i/2]); buf.V[42] = XOR(buf.V[43], pre.V[0][i/2]);
176 buf.V[26] = XOR(buf.V[27], pre.V[0][i/2]); buf.V[46] = XOR(buf.V[42], pre.V[2][i/2]);
177 buf.V[30] = XOR(buf.V[26], pre.V[2][i/2]); buf.V[47] = XOR(buf.V[46], pre.V[0][i/2]);
178 buf.V[31] = XOR(buf.V[30], pre.V[0][i/2]); buf.V[45] = XOR(buf.V[47], pre.V[1][i/2]);
179 buf.V[29] = XOR(buf.V[31], pre.V[1][i/2]); buf.V[44] = XOR(buf.V[45], pre.V[0][i/2]);
180 buf.V[28] = XOR(buf.V[29], pre.V[0][i/2]); buf.V[36] = XOR(buf.V[44], pre.V[3][i/2]);
181 buf.V[20] = XOR(buf.V[28], pre.V[3][i/2]); buf.V[37] = XOR(buf.V[36], pre.V[0][i/2]);
182 buf.V[21] = XOR(buf.V[20], pre.V[0][i/2]); buf.V[39] = XOR(buf.V[37], pre.V[1][i/2]);
183 buf.V[23] = XOR(buf.V[21], pre.V[1][i/2]); buf.V[38] = XOR(buf.V[39], pre.V[0][i/2]);
184 buf.V[22] = XOR(buf.V[23], pre.V[0][i/2]); buf.V[34] = XOR(buf.V[38], pre.V[2][i/2]);
185 buf.V[18] = XOR(buf.V[22], pre.V[2][i/2]); buf.V[35] = XOR(buf.V[34], pre.V[0][i/2]);
186 buf.V[19] = XOR(buf.V[18], pre.V[0][i/2]); buf.V[33] = XOR(buf.V[35], pre.V[1][i/2]);
187 buf.V[17] = XOR(buf.V[19], pre.V[1][i/2]); buf.V[32] = XOR(buf.V[33], pre.V[0][i/2]);
188
189 #undef XOR
190
191 // transpose
192
193 transpose_64x256_sp(buf.V);
194
195 for (j = 0; j < 32; j++)
196 {
197 if (i != GFBITS-1)
198 out[j][i+1] = vec256_unpack_high(buf.V[ reversal[2*j+0] ], buf.V[ reversal[2*j+1] ]);
199 out[j][i+0] = vec256_unpack_low (buf.V[ reversal[2*j+0] ], buf.V[ reversal[2*j+1] ]);
200 }
201 }
202
203 // butterflies
204
205 for (k = 0; k < 32; k+=2)
206 {
207 for (b = 0; b < GFBITS; b++) tmp0[b] = vec256_unpack_low (out[k][b], out[k+1][b]);
208 for (b = 0; b < GFBITS; b++) tmp1[b] = vec256_unpack_high (out[k][b], out[k+1][b]);
209
210 vec256_maa_asm(tmp0, tmp1, fft_consts[1]);
211
212 for (b = 0; b < GFBITS; b++) out[k][b] = vec256_unpack_low (tmp0[b], tmp1[b]);
213 for (b = 0; b < GFBITS; b++) out[k+1][b] = vec256_unpack_high (tmp0[b], tmp1[b]);
214 }
215
216 for (i = 0; i <= 4; i++)
217 {
218 s = 1 << i;
219
220 for (j = 0; j < 32; j += 2*s)
221 for (k = j; k < j+s; k++)
222 {
223 vec256_maa_asm(out[k], out[k+s], fft_consts[ consts_ptr + (k-j) ]);
224 }
225
226 consts_ptr += (1 << i);
227 }
228 }
229
230 /* input: in, polynomial in bitsliced form */
231 /* output: out, bitsliced results of evaluating in all the field elements */
232 void fft(vec256 out[][GFBITS], vec128 *in)
233 {
234 radix_conversions(in);
235 butterflies(out, in);
236 }
237