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