1 /*
2 This file is for the Gao-Mateer FFT
3 sse http://www.math.clemson.edu/~sgao/papers/GM10.pdf
4 */
5
6 #include "fft.h"
7
8 #include "transpose.h"
9
10 #include <stdint.h>
11
12 /* input: in, polynomial in bitsliced form */
13 /* output: in, result of applying the radix conversions on in */
radix_conversions(vec in[][GFBITS])14 static void radix_conversions(vec in[][GFBITS]) {
15 int i, j, k;
16
17 const vec mask[5][2] = {
18 {0x8888888888888888, 0x4444444444444444},
19 {0xC0C0C0C0C0C0C0C0, 0x3030303030303030},
20 {0xF000F000F000F000, 0x0F000F000F000F00},
21 {0xFF000000FF000000, 0x00FF000000FF0000},
22 {0xFFFF000000000000, 0x0000FFFF00000000}
23 };
24
25 const vec s[5][2][GFBITS] = {
26 #include "scalars_2x.inc"
27 };
28
29 for (j = 0; j <= 5; j++) {
30 for (i = 0; i < GFBITS; i++) {
31 in[1][i] ^= in[1][i] >> 32;
32 in[0][i] ^= in[1][i] << 32;
33 }
34
35 for (i = 0; i < GFBITS; i++) {
36 for (k = 4; k >= j; k--) {
37 in[0][i] ^= (in[0][i] & mask[k][0]) >> (1 << k);
38 in[0][i] ^= (in[0][i] & mask[k][1]) >> (1 << k);
39 in[1][i] ^= (in[1][i] & mask[k][0]) >> (1 << k);
40 in[1][i] ^= (in[1][i] & mask[k][1]) >> (1 << k);
41 }
42 }
43
44 if (j < 5) {
45 PQCLEAN_MCELIECE8192128F_VEC_vec_mul(in[0], in[0], s[j][0]);
46 PQCLEAN_MCELIECE8192128F_VEC_vec_mul(in[1], in[1], s[j][1]);
47 }
48 }
49 }
50
51 /* input: in, result of applying the radix conversions to the input polynomial */
52 /* output: out, evaluation results (by applying the FFT butterflies) */
butterflies(vec out[][GFBITS],vec in[][GFBITS])53 static void butterflies(vec out[][ GFBITS ], vec in[][ GFBITS ]) {
54 int i, j, k, s, b;
55
56 vec tmp[ GFBITS ];
57 vec pre[8][ GFBITS ];
58 vec buf[128];
59
60 uint64_t consts_ptr = 2;
61
62 const vec consts[ 128 ][ GFBITS ] = {
63 #include "consts.inc"
64 };
65
66 const vec powers[ 128 ][ GFBITS ] = {
67 #include "powers.inc"
68 };
69
70 const unsigned char reversal[128] = {
71 0, 64, 32, 96, 16, 80, 48, 112,
72 8, 72, 40, 104, 24, 88, 56, 120,
73 4, 68, 36, 100, 20, 84, 52, 116,
74 12, 76, 44, 108, 28, 92, 60, 124,
75 2, 66, 34, 98, 18, 82, 50, 114,
76 10, 74, 42, 106, 26, 90, 58, 122,
77 6, 70, 38, 102, 22, 86, 54, 118,
78 14, 78, 46, 110, 30, 94, 62, 126,
79 1, 65, 33, 97, 17, 81, 49, 113,
80 9, 73, 41, 105, 25, 89, 57, 121,
81 5, 69, 37, 101, 21, 85, 53, 117,
82 13, 77, 45, 109, 29, 93, 61, 125,
83 3, 67, 35, 99, 19, 83, 51, 115,
84 11, 75, 43, 107, 27, 91, 59, 123,
85 7, 71, 39, 103, 23, 87, 55, 119,
86 15, 79, 47, 111, 31, 95, 63, 127
87 };
88
89 const uint16_t beta[7] = {2522, 7827, 7801, 8035, 6897, 8167, 3476};
90
91 //
92
93 for (i = 0; i < 7; i++) {
94 for (j = 0; j < GFBITS; j++) {
95 pre[i][j] = (beta[i] >> j) & 1;
96 pre[i][j] = -pre[i][j];
97 }
98
99 PQCLEAN_MCELIECE8192128F_VEC_vec_mul(pre[i], in[1], pre[i]);
100 }
101
102 for (i = 0; i < GFBITS; i++) {
103 buf[0] = in[0][i];
104
105 buf[1] = buf[0] ^ pre[0][i];
106 buf[32] = in[0][i] ^ pre[5][i];
107 buf[3] = buf[1] ^ pre[1][i];
108 buf[96] = buf[32] ^ pre[6][i];
109 buf[97] = buf[96] ^ pre[0][i];
110 buf[2] = in[0][i] ^ pre[1][i];
111 buf[99] = buf[97] ^ pre[1][i];
112 buf[6] = buf[2] ^ pre[2][i];
113 buf[98] = buf[99] ^ pre[0][i];
114 buf[7] = buf[6] ^ pre[0][i];
115 buf[102] = buf[98] ^ pre[2][i];
116 buf[5] = buf[7] ^ pre[1][i];
117 buf[103] = buf[102] ^ pre[0][i];
118 buf[101] = buf[103] ^ pre[1][i];
119 buf[4] = in[0][i] ^ pre[2][i];
120 buf[100] = buf[101] ^ pre[0][i];
121 buf[12] = buf[4] ^ pre[3][i];
122 buf[108] = buf[100] ^ pre[3][i];
123 buf[13] = buf[12] ^ pre[0][i];
124 buf[109] = buf[108] ^ pre[0][i];
125 buf[15] = buf[13] ^ pre[1][i];
126 buf[111] = buf[109] ^ pre[1][i];
127 buf[14] = buf[15] ^ pre[0][i];
128 buf[110] = buf[111] ^ pre[0][i];
129 buf[10] = buf[14] ^ pre[2][i];
130 buf[106] = buf[110] ^ pre[2][i];
131 buf[11] = buf[10] ^ pre[0][i];
132 buf[107] = buf[106] ^ pre[0][i];
133 buf[9] = buf[11] ^ pre[1][i];
134 buf[105] = buf[107] ^ pre[1][i];
135 buf[104] = buf[105] ^ pre[0][i];
136 buf[8] = in[0][i] ^ pre[3][i];
137 buf[120] = buf[104] ^ pre[4][i];
138 buf[24] = buf[8] ^ pre[4][i];
139 buf[121] = buf[120] ^ pre[0][i];
140 buf[25] = buf[24] ^ pre[0][i];
141 buf[123] = buf[121] ^ pre[1][i];
142 buf[27] = buf[25] ^ pre[1][i];
143 buf[122] = buf[123] ^ pre[0][i];
144 buf[26] = buf[27] ^ pre[0][i];
145 buf[126] = buf[122] ^ pre[2][i];
146 buf[30] = buf[26] ^ pre[2][i];
147 buf[127] = buf[126] ^ pre[0][i];
148 buf[31] = buf[30] ^ pre[0][i];
149 buf[125] = buf[127] ^ pre[1][i];
150 buf[29] = buf[31] ^ pre[1][i];
151 buf[124] = buf[125] ^ pre[0][i];
152 buf[28] = buf[29] ^ pre[0][i];
153 buf[116] = buf[124] ^ pre[3][i];
154 buf[20] = buf[28] ^ pre[3][i];
155 buf[117] = buf[116] ^ pre[0][i];
156 buf[21] = buf[20] ^ pre[0][i];
157 buf[119] = buf[117] ^ pre[1][i];
158 buf[23] = buf[21] ^ pre[1][i];
159 buf[118] = buf[119] ^ pre[0][i];
160 buf[22] = buf[23] ^ pre[0][i];
161 buf[114] = buf[118] ^ pre[2][i];
162 buf[18] = buf[22] ^ pre[2][i];
163 buf[115] = buf[114] ^ pre[0][i];
164 buf[19] = buf[18] ^ pre[0][i];
165 buf[113] = buf[115] ^ pre[1][i];
166 buf[17] = buf[19] ^ pre[1][i];
167 buf[112] = buf[113] ^ pre[0][i];
168 buf[80] = buf[112] ^ pre[5][i];
169 buf[16] = in[0][i] ^ pre[4][i];
170 buf[81] = buf[80] ^ pre[0][i];
171 buf[48] = buf[16] ^ pre[5][i];
172 buf[83] = buf[81] ^ pre[1][i];
173 buf[49] = buf[48] ^ pre[0][i];
174 buf[82] = buf[83] ^ pre[0][i];
175 buf[51] = buf[49] ^ pre[1][i];
176 buf[86] = buf[82] ^ pre[2][i];
177 buf[50] = buf[51] ^ pre[0][i];
178 buf[87] = buf[86] ^ pre[0][i];
179 buf[54] = buf[50] ^ pre[2][i];
180 buf[85] = buf[87] ^ pre[1][i];
181 buf[55] = buf[54] ^ pre[0][i];
182 buf[84] = buf[85] ^ pre[0][i];
183 buf[53] = buf[55] ^ pre[1][i];
184 buf[92] = buf[84] ^ pre[3][i];
185 buf[52] = buf[53] ^ pre[0][i];
186 buf[93] = buf[92] ^ pre[0][i];
187 buf[60] = buf[52] ^ pre[3][i];
188 buf[95] = buf[93] ^ pre[1][i];
189 buf[61] = buf[60] ^ pre[0][i];
190 buf[94] = buf[95] ^ pre[0][i];
191 buf[63] = buf[61] ^ pre[1][i];
192 buf[90] = buf[94] ^ pre[2][i];
193 buf[62] = buf[63] ^ pre[0][i];
194 buf[91] = buf[90] ^ pre[0][i];
195 buf[58] = buf[62] ^ pre[2][i];
196 buf[89] = buf[91] ^ pre[1][i];
197 buf[59] = buf[58] ^ pre[0][i];
198 buf[88] = buf[89] ^ pre[0][i];
199 buf[57] = buf[59] ^ pre[1][i];
200 buf[72] = buf[88] ^ pre[4][i];
201 buf[56] = buf[57] ^ pre[0][i];
202 buf[73] = buf[72] ^ pre[0][i];
203 buf[40] = buf[56] ^ pre[4][i];
204 buf[75] = buf[73] ^ pre[1][i];
205 buf[41] = buf[40] ^ pre[0][i];
206 buf[74] = buf[75] ^ pre[0][i];
207 buf[43] = buf[41] ^ pre[1][i];
208 buf[78] = buf[74] ^ pre[2][i];
209 buf[42] = buf[43] ^ pre[0][i];
210 buf[79] = buf[78] ^ pre[0][i];
211 buf[46] = buf[42] ^ pre[2][i];
212 buf[77] = buf[79] ^ pre[1][i];
213 buf[47] = buf[46] ^ pre[0][i];
214 buf[76] = buf[77] ^ pre[0][i];
215 buf[45] = buf[47] ^ pre[1][i];
216 buf[68] = buf[76] ^ pre[3][i];
217 buf[44] = buf[45] ^ pre[0][i];
218 buf[69] = buf[68] ^ pre[0][i];
219 buf[36] = buf[44] ^ pre[3][i];
220 buf[71] = buf[69] ^ pre[1][i];
221 buf[37] = buf[36] ^ pre[0][i];
222 buf[70] = buf[71] ^ pre[0][i];
223 buf[39] = buf[37] ^ pre[1][i];
224 buf[66] = buf[70] ^ pre[2][i];
225 buf[38] = buf[39] ^ pre[0][i];
226 buf[67] = buf[66] ^ pre[0][i];
227 buf[34] = buf[38] ^ pre[2][i];
228 buf[65] = buf[67] ^ pre[1][i];
229 buf[35] = buf[34] ^ pre[0][i];
230 buf[33] = buf[35] ^ pre[1][i];
231 buf[64] = in[0][i] ^ pre[6][i];
232
233 PQCLEAN_MCELIECE8192128F_VEC_transpose_64x64(buf + 0, buf + 0);
234 PQCLEAN_MCELIECE8192128F_VEC_transpose_64x64(buf + 64, buf + 64);
235
236 for (j = 0; j < 128; j++) {
237 out[ reversal[j] ][i] = buf[j];
238 }
239 }
240
241 for (i = 1; i <= 6; i++) {
242 s = 1 << i;
243
244 for (j = 0; j < 128; j += 2 * s) {
245 for (k = j; k < j + s; k++) {
246 PQCLEAN_MCELIECE8192128F_VEC_vec_mul(tmp, out[k + s], consts[ consts_ptr + (k - j) ]);
247
248 for (b = 0; b < GFBITS; b++) {
249 out[k ][b] ^= tmp[b];
250 }
251 for (b = 0; b < GFBITS; b++) {
252 out[k + s][b] ^= out[k][b];
253 }
254 }
255 }
256
257 consts_ptr += (uint64_t)1 << i;
258 }
259
260 // adding the part contributed by x^128
261
262 for (i = 0; i < 128; i++) {
263 for (b = 0; b < GFBITS; b++) {
264 out[i][b] ^= powers[i][b];
265 }
266 }
267 }
268
269 /* input: in, polynomial in bitsliced form */
270 /* output: out, bitsliced results of evaluating in all the field elements */
PQCLEAN_MCELIECE8192128F_VEC_fft(vec out[][GFBITS],vec in[][GFBITS])271 void PQCLEAN_MCELIECE8192128F_VEC_fft(vec out[][GFBITS], vec in[][GFBITS]) {
272 radix_conversions(in);
273 butterflies(out, in);
274 }
275