Debian Codegraph @

crypto_kem/348864f/vec/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 // 20221230 djb: split these arrays into separate .c files
10 // 20221230 djb: rename powers array as fft_powers
11 // 20221230 djb: rename consts array as fft_consts
12 // 20221230 djb: rename s array as fft_scalars
13 // 20221230 djb: add linker lines
14
15 // linker define fft
16 // linker use vec_mul
17 // linker use fft_scalars fft_consts fft_powers
18
19 #include "fft.h"
20 #include "fft_scalars.h"
21 #include "fft_consts.h"
22 #include "fft_powers.h"
23 #include "vec.h"
24 #include "crypto_int64.h"
25
26 /* input: in, polynomial in bitsliced form */
27 /* output: in, result of applying the radix conversions on in */
28 static void radix_conversions(uint64_t *in)
29 {
30 int i, j, k;
31
32 const uint64_t mask[5][2] =
33 {
34 {0x8888888888888888, 0x4444444444444444},
35 {0xC0C0C0C0C0C0C0C0, 0x3030303030303030},
36 {0xF000F000F000F000, 0x0F000F000F000F00},
37 {0xFF000000FF000000, 0x00FF000000FF0000},
38 {0xFFFF000000000000, 0x0000FFFF00000000}
39 };
40
41 //
42
43 for (j = 0; j <= 4; j++)
44 {
45 for (i = 0; i < GFBITS; i++)
46 for (k = 4; k >= j; k--)
47 {
48 in[i] ^= (in[i] & mask[k][0]) >> (1 << k);
49 in[i] ^= (in[i] & mask[k][1]) >> (1 << k);
50 }
51
52 vec_mul(in, in, fft_scalars[j]); // scaling
53 }
54 }
55
56 /* input: in, result of applying the radix conversions to the input polynomial */
57 /* output: out, evaluation results (by applying the FFT butterflies) */
58 static void butterflies(uint64_t out[][ GFBITS ], uint64_t *in)
59 {
60 int i, j, k, s, b;
61
62 uint64_t tmp[ GFBITS ];
63 uint64_t consts_ptr = 0;
64
65 const unsigned char reversal[64] =
66 {
67 0, 32, 16, 48, 8, 40, 24, 56,
68 4, 36, 20, 52, 12, 44, 28, 60,
69 2, 34, 18, 50, 10, 42, 26, 58,
70 6, 38, 22, 54, 14, 46, 30, 62,
71 1, 33, 17, 49, 9, 41, 25, 57,
72 5, 37, 21, 53, 13, 45, 29, 61,
73 3, 35, 19, 51, 11, 43, 27, 59,
74 7, 39, 23, 55, 15, 47, 31, 63
75 };
76
77 // boradcast
78
79 for (j = 0; j < 64; j++)
80 for (i = 0; i < GFBITS; i++)
81 {
82 out[j][i] = crypto_int64_bitmod_mask(in[i], reversal[j]);
83 }
84
85 // butterflies
86
87 for (i = 0; i <= 5; i++)
88 {
89 s = 1 << i;
90
91 for (j = 0; j < 64; j += 2*s)
92 {
93 for (k = j; k < j+s; k++)
94 {
95 vec_mul(tmp, out[k+s], fft_consts[ consts_ptr + (k-j) ]);
96
97 for (b = 0; b < GFBITS; b++) out[k][b] ^= tmp[b];
98 for (b = 0; b < GFBITS; b++) out[k+s][b] ^= out[k][b];
99 }
100 }
101
102 consts_ptr += (1 << i);
103 }
104
105 //
106
107 // adding the part contributed by x^64
108
109 for (i = 0; i < 64; i++)
110 for (b = 0; b < GFBITS; b++)
111 out[i][b] ^= fft_powers[i][b];
112
113 }
114
115 void fft(vec out[][ GFBITS ], vec *in)
116 {
117 radix_conversions(in);
118 butterflies(out, in);
119 }
120