Debian Codegraph @

crypto_kem/6688128f/vec/bm.c

raw
1 /*
2 This file is for implementating the inversion-free Berlekamp-Massey algorithm
3 see https://ieeexplore.ieee.org/document/87857
4
5 For the implementation strategy, see
6 https://eprint.iacr.org/2017/793.pdf
7 */
8 // 20240805 djb: more use of cryptoint
9 // 20240503 djb: use crypto_*_mask functions
10 // 20221230 djb: add linker lines
11
12 // linker define bm
13 // linker use vec_mul
14 // linker use gf_inv
15 // linker use gf_mul2
16
17 #include "bm.h"
18
19 #include "gf.h"
20 #include "crypto_uint64.h"
21 #include "crypto_int64.h"
22
23 static inline void vec_cmov(vec * out, vec * in, uint16_t mask)
24 {
25 int i;
26
27 vec m0, m1;
28
29 m0 = vec_set1_16b(mask);
30 m1 = ~m0;
31
32 for (i = 0; i < GFBITS; i++)
33 {
34 out[i] = (in[i] & m0) | (out[i] & m1);
35 out[i] = (in[i] & m0) | (out[i] & m1);
36 }
37 }
38
39 static inline void interleave(vec *in, int idx0, int idx1, vec *mask, int b)
40 {
41 int s = 1 << b;
42
43 vec x, y;
44
45 x = (in[idx0] & mask[0]) | ((in[idx1] & mask[0]) << s);
46 y = ((in[idx0] & mask[1]) >> s) | (in[idx1] & mask[1]);
47
48 in[idx0] = x;
49 in[idx1] = y;
50 }
51
52 /* input: in, field elements in bitsliced form */
53 /* output: out, field elements in non-bitsliced form */
54 static inline void get_coefs(gf *out, vec *in)
55 {
56 int i, k;
57
58 vec mask[4][2];
59 vec buf[16];
60
61 for (i = 0; i < 13; i++) buf[i] = in[i];
62 for (i = 13; i < 16; i++) buf[i] = 0;
63
64 mask[0][0] = vec_set1_16b(0x5555);
65 mask[0][1] = vec_set1_16b(0xAAAA);
66 mask[1][0] = vec_set1_16b(0x3333);
67 mask[1][1] = vec_set1_16b(0xCCCC);
68 mask[2][0] = vec_set1_16b(0x0F0F);
69 mask[2][1] = vec_set1_16b(0xF0F0);
70 mask[3][0] = vec_set1_16b(0x00FF);
71 mask[3][1] = vec_set1_16b(0xFF00);
72
73 interleave(buf, 0, 8, mask[3], 3);
74 interleave(buf, 1, 9, mask[3], 3);
75 interleave(buf, 2, 10, mask[3], 3);
76 interleave(buf, 3, 11, mask[3], 3);
77 interleave(buf, 4, 12, mask[3], 3);
78 interleave(buf, 5, 13, mask[3], 3);
79 interleave(buf, 6, 14, mask[3], 3);
80 interleave(buf, 7, 15, mask[3], 3);
81
82 interleave(buf, 0, 4, mask[2], 2);
83 interleave(buf, 1, 5, mask[2], 2);
84 interleave(buf, 2, 6, mask[2], 2);
85 interleave(buf, 3, 7, mask[2], 2);
86 interleave(buf, 8, 12, mask[2], 2);
87 interleave(buf, 9, 13, mask[2], 2);
88 interleave(buf, 10, 14, mask[2], 2);
89 interleave(buf, 11, 15, mask[2], 2);
90
91 interleave(buf, 0, 2, mask[1], 1);
92 interleave(buf, 1, 3, mask[1], 1);
93 interleave(buf, 4, 6, mask[1], 1);
94 interleave(buf, 5, 7, mask[1], 1);
95 interleave(buf, 8, 10, mask[1], 1);
96 interleave(buf, 9, 11, mask[1], 1);
97 interleave(buf, 12, 14, mask[1], 1);
98 interleave(buf, 13, 15, mask[1], 1);
99
100 interleave(buf, 0, 1, mask[0], 0);
101 interleave(buf, 2, 3, mask[0], 0);
102 interleave(buf, 4, 5, mask[0], 0);
103 interleave(buf, 6, 7, mask[0], 0);
104 interleave(buf, 8, 9, mask[0], 0);
105 interleave(buf, 10, 11, mask[0], 0);
106 interleave(buf, 12, 13, mask[0], 0);
107 interleave(buf, 14, 15, mask[0], 0);
108
109 for (i = 0; i < 16; i++)
110 for (k = 0; k < 4; k++)
111 out[ k*16 + i ] = (buf[i] >> (k*16)) & GFMASK;
112 }
113
114 static void update(vec in[][GFBITS], const gf e)
115 {
116 int i;
117 vec tmp;
118
119 for (i = 0; i < GFBITS; i++)
120 {
121 tmp = crypto_int64_bitmod_01(e, i);
122
123 in[0][i] = (in[0][i] >> 1) | (in[1][i] << 63);
124 in[1][i] = (in[1][i] >> 1) | (tmp << 63);
125 }
126 }
127
128 static inline gf vec_reduce(vec in[][GFBITS])
129 {
130 int i;
131 vec tmp;
132 gf ret = 0;
133
134 for (i = GFBITS-1; i >= 0; i--)
135 {
136 tmp = in[0][i] ^ in[1][i];
137
138 tmp ^= tmp >> 32;
139 tmp ^= tmp >> 16;
140 tmp ^= tmp >> 8;
141 tmp ^= tmp >> 4;
142 tmp ^= tmp >> 2;
143 tmp ^= tmp >> 1;
144
145 ret <<= 1;
146 ret |= crypto_int64_bottombit_01(tmp);
147 }
148
149 return ret;
150 }
151
152 /* input: in, sequence of field elements */
153 /* output: out, minimal polynomial of in */
154 void bm(vec out[][ GFBITS ], vec in[][ GFBITS ])
155 {
156 int i;
157 uint16_t N, L;
158 uint16_t mask;
159 uint64_t one = 1, t;
160
161 vec prod[2][GFBITS];
162 vec interval[2][GFBITS];
163 vec dd[2][GFBITS], bb[2][GFBITS];
164 vec B[2][GFBITS], C[2][GFBITS];
165 vec B_tmp[2][GFBITS], C_tmp[2][GFBITS];
166 vec v[GFBITS];
167
168 gf d, b, c0 = 1;
169 gf coefs[256];
170
171 // initialization
172
173 get_coefs(&coefs[ 0], in[0]);
174 get_coefs(&coefs[ 64], in[1]);
175 get_coefs(&coefs[128], in[2]);
176 get_coefs(&coefs[192], in[3]);
177
178 C[0][0] = 0;
179 C[1][0] = 0;
180 B[0][0] = 0;
181 B[1][0] = one << 63;
182
183 for (i = 1; i < GFBITS; i++)
184 C[0][i] = C[1][i] = B[0][i] = B[1][i] = 0;
185
186 b = 1;
187 L = 0;
188
189 //
190
191 for (i = 0; i < GFBITS; i++)
192 interval[0][i] = interval[1][i] = 0;
193
194 for (N = 0; N < 256; N++)
195 {
196 vec_mul(prod[0], C[0], interval[0]);
197 vec_mul(prod[1], C[1], interval[1]);
198 update(interval, coefs[N]);
199 d = vec_reduce(prod);
200
201 t = gf_mul2(c0, coefs[N], b);
202 d ^= t & 0xFFFFFFFF;
203
204 mask = crypto_uint64_nonzero_mask(d) & crypto_uint64_leq_mask(L*2, N);
205
206 for (i = 0; i < GFBITS; i++)
207 {
208 dd[0][i] = dd[1][i] = vec_setbits(crypto_int64_bitmod_01(d, i));
209 bb[0][i] = bb[1][i] = vec_setbits(crypto_int64_bitmod_01(b, i));
210 }
211
212 vec_mul(B_tmp[0], dd[0], B[0]);
213 vec_mul(B_tmp[1], dd[1], B[1]);
214 vec_mul(C_tmp[0], bb[0], C[0]);
215 vec_mul(C_tmp[1], bb[1], C[1]);
216
217 vec_cmov(B[0], C[0], mask);
218 vec_cmov(B[1], C[1], mask);
219 update(B, c0 & mask);
220
221 for (i = 0; i < GFBITS; i++)
222 {
223 C[0][i] = B_tmp[0][i] ^ C_tmp[0][i];
224 C[1][i] = B_tmp[1][i] ^ C_tmp[1][i];
225 }
226
227 c0 = t >> 32;
228 b = (d & mask) | (b & ~mask);
229 L = ((N+1-L) & mask) | (L & ~mask);
230 }
231
232 c0 = gf_inv(c0);
233
234 for (i = 0; i < GFBITS; i++)
235 v[i] = vec_setbits(crypto_int64_bitmod_01(c0, i));
236
237 vec_mul(out[0], C[0], v);
238 vec_mul(out[1], C[1], v);
239 }
240