Debian Codegraph @

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