Debian Codegraph @

crypto_kem/8192128pcf/vec/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 // 20221230 djb: split these arrays into separate .c files
10 // 20221230 djb: rename consts array as fft_consts
11 // 20221230 djb: rename s array as fft_scalars_4x
12 // 20221230 djb: add linker lines
13
14 // linker define fft_tr
15 // linker use vec_mul
16 // linker use fft_scalars_4x fft_consts
17
18 #include "fft_tr.h"
19 #include "fft_scalars_4x.h"
20 #include "fft_consts.h"
21
22 #include "transpose.h"
23
24 #include <stdint.h>
25 #include "crypto_int64.h"
26
27 static void radix_conversions_tr(vec in[][ GFBITS ])
28 {
29 int i, j, k;
30
31 const vec mask[6][2] =
32 {
33 {0x2222222222222222, 0x4444444444444444},
34 {0x0C0C0C0C0C0C0C0C, 0x3030303030303030},
35 {0x00F000F000F000F0, 0x0F000F000F000F00},
36 {0x0000FF000000FF00, 0x00FF000000FF0000},
37 {0x00000000FFFF0000, 0x0000FFFF00000000},
38 {0xFFFFFFFF00000000, 0x00000000FFFFFFFF}
39 };
40
41 //
42
43 for (j = 6; j >= 0; j--)
44 {
45 if (j < 6)
46 {
47 vec_mul(in[0], in[0], fft_scalars_4x[j][0]); // scaling
48 vec_mul(in[1], in[1], fft_scalars_4x[j][1]); // scaling
49 vec_mul(in[2], in[2], fft_scalars_4x[j][2]); // scaling
50 vec_mul(in[3], in[3], fft_scalars_4x[j][3]); // scaling
51 }
52
53 for (k = j; k <= 4; k++)
54 for (i = 0; i < GFBITS; i++)
55 {
56 in[0][i] ^= (in[0][i] & mask[k][0]) << (1 << k);
57 in[0][i] ^= (in[0][i] & mask[k][1]) << (1 << k);
58 in[1][i] ^= (in[1][i] & mask[k][0]) << (1 << k);
59 in[1][i] ^= (in[1][i] & mask[k][1]) << (1 << k);
60 in[2][i] ^= (in[2][i] & mask[k][0]) << (1 << k);
61 in[2][i] ^= (in[2][i] & mask[k][1]) << (1 << k);
62 in[3][i] ^= (in[3][i] & mask[k][0]) << (1 << k);
63 in[3][i] ^= (in[3][i] & mask[k][1]) << (1 << k);
64 }
65
66 if (j <= 5)
67 for (i = 0; i < GFBITS; i++)
68 {
69 in[1][i] ^= in[0][i] >> 32;
70 in[1][i] ^= in[1][i] << 32;
71
72 in[3][i] ^= in[2][i] >> 32;
73 in[3][i] ^= in[3][i] << 32;
74 }
75
76 for (i = 0; i < GFBITS; i++)
77 in[3][i] ^= in[2][i] ^= in[1][i];
78 }
79 }
80
81 static void butterflies_tr(vec out[][ GFBITS ], vec in[][ GFBITS ])
82 {
83 int i, j, k, s, b;
84
85 vec tmp[ GFBITS ];
86 vec pre[6][2][ GFBITS ];
87 vec buf[2][64];
88
89 uint64_t consts_ptr = 128;
90
91 const unsigned char reversal[128] =
92 {
93 0, 64, 32, 96, 16, 80, 48, 112,
94 8, 72, 40, 104, 24, 88, 56, 120,
95 4, 68, 36, 100, 20, 84, 52, 116,
96 12, 76, 44, 108, 28, 92, 60, 124,
97 2, 66, 34, 98, 18, 82, 50, 114,
98 10, 74, 42, 106, 26, 90, 58, 122,
99 6, 70, 38, 102, 22, 86, 54, 118,
100 14, 78, 46, 110, 30, 94, 62, 126,
101 1, 65, 33, 97, 17, 81, 49, 113,
102 9, 73, 41, 105, 25, 89, 57, 121,
103 5, 69, 37, 101, 21, 85, 53, 117,
104 13, 77, 45, 109, 29, 93, 61, 125,
105 3, 67, 35, 99, 19, 83, 51, 115,
106 11, 75, 43, 107, 27, 91, 59, 123,
107 7, 71, 39, 103, 23, 87, 55, 119,
108 15, 79, 47, 111, 31, 95, 63, 127
109 };
110
111 const uint16_t beta[6] = {5246, 5306, 6039, 6685, 4905, 6755};
112
113 //
114
115 for (i = 6; i >= 0; i--)
116 {
117 s = 1 << i;
118 consts_ptr -= s;
119
120 for (j = 0; j < 128; j += 2*s)
121 for (k = j; k < j+s; k++)
122 {
123 for (b = 0; b < GFBITS; b++) in[k][b] ^= in[k+s][b];
124
125 vec_mul(tmp, in[k], fft_consts[ consts_ptr + (k-j) ]);
126
127 for (b = 0; b < GFBITS; b++) in[k+s][b] ^= tmp[b];
128 }
129 }
130
131 for (i = 0; i < GFBITS; i++)
132 {
133 for (k = 0; k < 128; k++)
134 (&buf[0][0])[ k ] = in[ reversal[k] ][i];
135
136 transpose_64x64(buf[0], buf[0]);
137 transpose_64x64(buf[1], buf[1]);
138
139 for (k = 0; k < 2; k++)
140 {
141 pre[0][k][i] = buf[k][32]; buf[k][33] ^= buf[k][32];
142 pre[1][k][i] = buf[k][33]; buf[k][35] ^= buf[k][33];
143 pre[0][k][i] ^= buf[k][35]; buf[k][34] ^= buf[k][35];
144 pre[2][k][i] = buf[k][34]; buf[k][38] ^= buf[k][34];
145 pre[0][k][i] ^= buf[k][38]; buf[k][39] ^= buf[k][38];
146 pre[1][k][i] ^= buf[k][39]; buf[k][37] ^= buf[k][39];
147 pre[0][k][i] ^= buf[k][37]; buf[k][36] ^= buf[k][37];
148 pre[3][k][i] = buf[k][36]; buf[k][44] ^= buf[k][36];
149 pre[0][k][i] ^= buf[k][44]; buf[k][45] ^= buf[k][44];
150 pre[1][k][i] ^= buf[k][45]; buf[k][47] ^= buf[k][45];
151 pre[0][k][i] ^= buf[k][47]; buf[k][46] ^= buf[k][47];
152 pre[2][k][i] ^= buf[k][46]; buf[k][42] ^= buf[k][46];
153 pre[0][k][i] ^= buf[k][42]; buf[k][43] ^= buf[k][42];
154 pre[1][k][i] ^= buf[k][43]; buf[k][41] ^= buf[k][43];
155 pre[0][k][i] ^= buf[k][41]; buf[k][40] ^= buf[k][41];
156 pre[4][k][i] = buf[k][40]; buf[k][56] ^= buf[k][40];
157 pre[0][k][i] ^= buf[k][56]; buf[k][57] ^= buf[k][56];
158 pre[1][k][i] ^= buf[k][57]; buf[k][59] ^= buf[k][57];
159 pre[0][k][i] ^= buf[k][59]; buf[k][58] ^= buf[k][59];
160 pre[2][k][i] ^= buf[k][58]; buf[k][62] ^= buf[k][58];
161 pre[0][k][i] ^= buf[k][62]; buf[k][63] ^= buf[k][62];
162 pre[1][k][i] ^= buf[k][63]; buf[k][61] ^= buf[k][63];
163 pre[0][k][i] ^= buf[k][61]; buf[k][60] ^= buf[k][61];
164 pre[3][k][i] ^= buf[k][60]; buf[k][52] ^= buf[k][60];
165 pre[0][k][i] ^= buf[k][52]; buf[k][53] ^= buf[k][52];
166 pre[1][k][i] ^= buf[k][53]; buf[k][55] ^= buf[k][53];
167 pre[0][k][i] ^= buf[k][55]; buf[k][54] ^= buf[k][55];
168 pre[2][k][i] ^= buf[k][54]; buf[k][50] ^= buf[k][54];
169 pre[0][k][i] ^= buf[k][50]; buf[k][51] ^= buf[k][50];
170 pre[1][k][i] ^= buf[k][51]; buf[k][49] ^= buf[k][51];
171 pre[0][k][i] ^= buf[k][49]; buf[k][48] ^= buf[k][49];
172 pre[5][k][i] = buf[k][48]; buf[k][16] ^= buf[k][48];
173 pre[0][k][i] ^= buf[k][16]; buf[k][17] ^= buf[k][16];
174 pre[1][k][i] ^= buf[k][17]; buf[k][19] ^= buf[k][17];
175 pre[0][k][i] ^= buf[k][19]; buf[k][18] ^= buf[k][19];
176 pre[2][k][i] ^= buf[k][18]; buf[k][22] ^= buf[k][18];
177 pre[0][k][i] ^= buf[k][22]; buf[k][23] ^= buf[k][22];
178 pre[1][k][i] ^= buf[k][23]; buf[k][21] ^= buf[k][23];
179 pre[0][k][i] ^= buf[k][21]; buf[k][20] ^= buf[k][21];
180 pre[3][k][i] ^= buf[k][20]; buf[k][28] ^= buf[k][20];
181 pre[0][k][i] ^= buf[k][28]; buf[k][29] ^= buf[k][28];
182 pre[1][k][i] ^= buf[k][29]; buf[k][31] ^= buf[k][29];
183 pre[0][k][i] ^= buf[k][31]; buf[k][30] ^= buf[k][31];
184 pre[2][k][i] ^= buf[k][30]; buf[k][26] ^= buf[k][30];
185 pre[0][k][i] ^= buf[k][26]; buf[k][27] ^= buf[k][26];
186 pre[1][k][i] ^= buf[k][27]; buf[k][25] ^= buf[k][27];
187 pre[0][k][i] ^= buf[k][25]; buf[k][24] ^= buf[k][25];
188 pre[4][k][i] ^= buf[k][24]; buf[k][8] ^= buf[k][24];
189 pre[0][k][i] ^= buf[k][8]; buf[k][9] ^= buf[k][8];
190 pre[1][k][i] ^= buf[k][9]; buf[k][11] ^= buf[k][9];
191 pre[0][k][i] ^= buf[k][11]; buf[k][10] ^= buf[k][11];
192 pre[2][k][i] ^= buf[k][10]; buf[k][14] ^= buf[k][10];
193 pre[0][k][i] ^= buf[k][14]; buf[k][15] ^= buf[k][14];
194 pre[1][k][i] ^= buf[k][15]; buf[k][13] ^= buf[k][15];
195 pre[0][k][i] ^= buf[k][13]; buf[k][12] ^= buf[k][13];
196 pre[3][k][i] ^= buf[k][12]; buf[k][4] ^= buf[k][12];
197 pre[0][k][i] ^= buf[k][4]; buf[k][5] ^= buf[k][4];
198 pre[1][k][i] ^= buf[k][5]; buf[k][7] ^= buf[k][5];
199 pre[0][k][i] ^= buf[k][7]; buf[k][6] ^= buf[k][7];
200 pre[2][k][i] ^= buf[k][6]; buf[k][2] ^= buf[k][6];
201 pre[0][k][i] ^= buf[k][2]; buf[k][3] ^= buf[k][2];
202 pre[1][k][i] ^= buf[k][3]; buf[k][1] ^= buf[k][3];
203
204 pre[0][k][i] ^= buf[k][1]; out[k][i] = buf[k][0] ^ buf[k][1];
205 }
206 }
207
208 for (j = 0; j < GFBITS; j++) tmp[j] = vec_setbits(crypto_int64_bitmod_01(beta[0], j));
209
210 vec_mul(out[2], pre[0][0], tmp);
211 vec_mul(out[3], pre[0][1], tmp);
212
213 for (i = 1; i < 6; i++)
214 {
215 for (j = 0; j < GFBITS; j++) tmp[j] = vec_setbits(crypto_int64_bitmod_01(beta[i], j));
216
217 vec_mul(pre[i][0], pre[i][0], tmp);
218 vec_mul(pre[i][1], pre[i][1], tmp);
219
220 for (b = 0; b < GFBITS; b++)
221 {
222 out[2][b] ^= pre[i][0][b];
223 out[3][b] ^= pre[i][1][b];
224 }
225 }
226
227 }
228
229 void fft_tr(vec out[][GFBITS], vec in[][ GFBITS ])
230 {
231 butterflies_tr(out, in);
232
233 radix_conversions_tr(out);
234 }
235