Debian Codegraph @

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