Debian Codegraph @

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