| 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 |
|