Debian Codegraph @

crypto_kem/348864f/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 vec256_gf.h
10 // 20221230 djb: split these arrays into separate .c files
11 // 20221230 djb: rename powers array as fft_powers
12 // 20221230 djb: rename consts array as fft_consts
13 // 20221230 djb: rename s array as fft_scalars
14 // 20221230 djb: add linker lines
15
16 // linker define fft
17 // linker use vec_mul_asm
18 // linker use vec256_mul_asm
19 // linker use fft_scalars fft_consts fft_powers
20
21 #include "fft.h"
22 #include "fft_scalars.h"
23 #include "fft_consts.h"
24 #include "fft_powers.h"
25
26 #include "vec256_gf.h"
27 #include "vec.h"
28 #include "crypto_int64.h"
29
30 /* input: in, polynomial in bitsliced form */
31 /* output: in, result of applying the radix conversions on in */
32 static void radix_conversions(uint64_t *in)
33 {
34 int i, j, k;
35
36 const uint64_t mask[5][2] =
37 {
38 {0x8888888888888888, 0x4444444444444444},
39 {0xC0C0C0C0C0C0C0C0, 0x3030303030303030},
40 {0xF000F000F000F000, 0x0F000F000F000F00},
41 {0xFF000000FF000000, 0x00FF000000FF0000},
42 {0xFFFF000000000000, 0x0000FFFF00000000}
43 };
44
45 //
46
47 for (j = 0; j <= 4; j++)
48 {
49 for (i = 0; i < GFBITS; i++)
50 for (k = 4; k >= j; k--)
51 {
52 in[i] ^= (in[i] & mask[k][0]) >> (1 << k);
53 in[i] ^= (in[i] & mask[k][1]) >> (1 << k);
54 }
55
56 vec_mul(in, in, fft_scalars[j]); // scaling
57 }
58 }
59
60 /* input: in, result of applying the radix conversions to the input polynomial */
61 /* output: out, evaluation results (by applying the FFT butterflies) */
62 static void butterflies(vec256 out[][ GFBITS ], uint64_t *in)
63 {
64 int i, j, k, s, b;
65
66 uint64_t t0, t1, t2, t3;
67
68 uint64_t consts_ptr = 0;
69
70 const unsigned char reversal[64] =
71 {
72 0, 32, 16, 48, 8, 40, 24, 56,
73 4, 36, 20, 52, 12, 44, 28, 60,
74 2, 34, 18, 50, 10, 42, 26, 58,
75 6, 38, 22, 54, 14, 46, 30, 62,
76 1, 33, 17, 49, 9, 41, 25, 57,
77 5, 37, 21, 53, 13, 45, 29, 61,
78 3, 35, 19, 51, 11, 43, 27, 59,
79 7, 39, 23, 55, 15, 47, 31, 63
80 };
81
82 // boradcast
83
84 vec256 tmp256[ GFBITS ];
85 vec256 x[ GFBITS ], y[ GFBITS ];
86
87 for (j = 0; j < 64; j+=8)
88 for (i = 0; i < GFBITS; i++)
89 {
90 t0 = crypto_int64_bitmod_mask(in[i], reversal[j+0]);
91 t1 = crypto_int64_bitmod_mask(in[i], reversal[j+2]);
92 t2 = crypto_int64_bitmod_mask(in[i], reversal[j+4]);
93 t3 = crypto_int64_bitmod_mask(in[i], reversal[j+6]);
94
95 out[j/4+0][i] = vec256_set4x(t0, t1, t2, t3);
96
97 t0 = crypto_int64_bitmod_mask(in[i], reversal[j+1]);
98 t1 = crypto_int64_bitmod_mask(in[i], reversal[j+3]);
99 t2 = crypto_int64_bitmod_mask(in[i], reversal[j+5]);
100 t3 = crypto_int64_bitmod_mask(in[i], reversal[j+7]);
101
102 out[j/4+1][i] = vec256_set4x(t0, t1, t2, t3);
103 }
104
105 //
106
107 for (i = 0; i < 16; i+=2)
108 {
109 vec256_mul(tmp256, out[i+1], fft_consts[ 0 ]);
110
111 for (b = 0; b < GFBITS; b++) out[i+0][b] ^= tmp256[b];
112 for (b = 0; b < GFBITS; b++) out[i+1][b] ^= out[i+0][b];
113 }
114
115 for (i = 0; i < 16; i+=2)
116 {
117 for (b = 0; b < GFBITS; b++) x[b] = vec256_unpack_low_2x(out[i+0][b], out[i+1][b]);
118 for (b = 0; b < GFBITS; b++) y[b] = vec256_unpack_high_2x(out[i+0][b], out[i+1][b]);
119
120 vec256_mul(tmp256, y, fft_consts[ 1 ]);
121
122 for (b = 0; b < GFBITS; b++) x[b] ^= tmp256[b];
123 for (b = 0; b < GFBITS; b++) y[b] ^= x[b];
124
125 for (b = 0; b < GFBITS; b++) out[i+0][b] = vec256_unpack_low(x[b], y[b]);
126 for (b = 0; b < GFBITS; b++) out[i+1][b] = vec256_unpack_high(x[b], y[b]);
127 }
128
129 consts_ptr = 2;
130
131 for (i = 0; i <= 3; i++)
132 {
133 s = 1 << i;
134
135 for (j = 0; j < 16; j += 2*s)
136 {
137 for (k = j; k < j+s; k++)
138 {
139 vec256_mul(tmp256, out[k+s], fft_consts[ consts_ptr + (k-j) ]);
140
141 for (b = 0; b < GFBITS; b++) out[k][b] ^= tmp256[b];
142 for (b = 0; b < GFBITS; b++) out[k+s][b] ^= out[k][b];
143 }
144 }
145
146 consts_ptr += s;
147 }
148
149 // adding the part contributed by x^64
150
151 for (i = 0; i < 16; i++)
152 for (b = 0; b < GFBITS; b++)
153 out[i][b] = vec256_xor(out[i][b], fft_powers[i][b]);
154 }
155
156 void fft(vec256 out[][ GFBITS ], uint64_t *in)
157 {
158 radix_conversions(in);
159 butterflies(out, in);
160 }
161