Debian Codegraph @

crypto_kem/6960119pcf/avx/bm.c

raw
1 #define update_asm CRYPTO_SHARED_NAMESPACE(update_asm)
2 #define _update_asm _CRYPTO_SHARED_NAMESPACE(update_asm)
3 #define vec_reduce_asm CRYPTO_SHARED_NAMESPACE(vec_reduce_asm)
4 #define _vec_reduce_asm _CRYPTO_SHARED_NAMESPACE(vec_reduce_asm)
5 /*
6 This file is for implementating the inversion-free Berlekamp-Massey algorithm
7 see https://ieeexplore.ieee.org/document/87857
8
9 For the implementation strategy, see
10 https://eprint.iacr.org/2017/793.pdf
11 */
12 // 20240805 djb: more cryptoint usage
13 // 20240530 djb: CRYPTO_ALIGN instead of ALIGN
14 // 20240508 djb: include vec{128,256}_gf.h
15 // 20240503 djb: use crypto_*_mask functions
16 // 20221231 djb: ALIGN(32) for some arrays; tnx thom wiggers
17 // 20221230 djb: add linker lines
18
19 // linker define bm
20 // linker use update_asm vec_reduce_asm
21 // linker use vec128_mul_asm
22 // linker use vec256_mul_asm
23
24 #include "bm.h"
25
26 #include "gf.h"
27 #include "vec128_gf.h"
28 #include "vec256_gf.h"
29 #include "params.h"
30 #include "crypto_uint64.h"
31
32 #include <stdint.h>
33 #include "crypto_int64.h"
34
35 extern gf vec_reduce_asm(vec128 *);
36 extern void update_asm(void *, gf, int);
37
38 static inline void vec128_cmov(vec128 out[][2], uint16_t mask)
39 {
40 int i;
41
42 vec128 v0, v1;
43
44 vec128 m0 = vec128_set1_16b( mask);
45 vec128 m1 = vec128_set1_16b(~mask);
46
47 for (i = 0; i < GFBITS; i++)
48 {
49 v0 = vec128_and(out[i][1], m0);
50 v1 = vec128_and(out[i][0], m1);
51 out[i][0] = vec128_or(v0, v1);
52 }
53 }
54
55 static inline void interleave(vec256 *in, int idx0, int idx1, vec256 *mask, int b)
56 {
57 int s = 1 << b;
58
59 vec256 x, y;
60
61 x = vec256_or(vec256_and(in[idx0], mask[0]),
62 vec256_sll_4x(vec256_and(in[idx1], mask[0]), s));
63
64 y = vec256_or(vec256_srl_4x(vec256_and(in[idx0], mask[1]), s),
65 vec256_and(in[idx1], mask[1]));
66
67 in[idx0] = x;
68 in[idx1] = y;
69 }
70
71 /* input: in, field elements in bitsliced form */
72 /* output: out, field elements in non-bitsliced form */
73 static inline void get_coefs(gf *out, vec256 *in)
74 {
75 int i, k;
76
77 vec256 mask[4][2];
78 vec256 buf[16];
79
80 for (i = 0; i < 13; i++) buf[i] = in[i];
81 for (i = 13; i < 16; i++) buf[i] = vec256_setzero();
82
83 mask[0][0] = vec256_set1_16b(0x5555);
84 mask[0][1] = vec256_set1_16b(0xAAAA);
85 mask[1][0] = vec256_set1_16b(0x3333);
86 mask[1][1] = vec256_set1_16b(0xCCCC);
87 mask[2][0] = vec256_set1_16b(0x0F0F);
88 mask[2][1] = vec256_set1_16b(0xF0F0);
89 mask[3][0] = vec256_set1_16b(0x00FF);
90 mask[3][1] = vec256_set1_16b(0xFF00);
91
92 interleave(buf, 0, 8, mask[3], 3);
93 interleave(buf, 1, 9, mask[3], 3);
94 interleave(buf, 2, 10, mask[3], 3);
95 interleave(buf, 3, 11, mask[3], 3);
96 interleave(buf, 4, 12, mask[3], 3);
97 interleave(buf, 5, 13, mask[3], 3);
98 interleave(buf, 6, 14, mask[3], 3);
99 interleave(buf, 7, 15, mask[3], 3);
100
101 interleave(buf, 0, 4, mask[2], 2);
102 interleave(buf, 1, 5, mask[2], 2);
103 interleave(buf, 2, 6, mask[2], 2);
104 interleave(buf, 3, 7, mask[2], 2);
105 interleave(buf, 8, 12, mask[2], 2);
106 interleave(buf, 9, 13, mask[2], 2);
107 interleave(buf, 10, 14, mask[2], 2);
108 interleave(buf, 11, 15, mask[2], 2);
109
110 interleave(buf, 0, 2, mask[1], 1);
111 interleave(buf, 1, 3, mask[1], 1);
112 interleave(buf, 4, 6, mask[1], 1);
113 interleave(buf, 5, 7, mask[1], 1);
114 interleave(buf, 8, 10, mask[1], 1);
115 interleave(buf, 9, 11, mask[1], 1);
116 interleave(buf, 12, 14, mask[1], 1);
117 interleave(buf, 13, 15, mask[1], 1);
118
119 interleave(buf, 0, 1, mask[0], 0);
120 interleave(buf, 2, 3, mask[0], 0);
121 interleave(buf, 4, 5, mask[0], 0);
122 interleave(buf, 6, 7, mask[0], 0);
123 interleave(buf, 8, 9, mask[0], 0);
124 interleave(buf, 10, 11, mask[0], 0);
125 interleave(buf, 12, 13, mask[0], 0);
126 interleave(buf, 14, 15, mask[0], 0);
127
128 for (i = 0; i < 16; i++)
129 for (k = 0; k < 4; k++) {
130 out[ (4*0 + k)*16 + i ] = (vec256_extract(buf[i], 0) >> (k*16)) & GFMASK;
131 out[ (4*1 + k)*16 + i ] = (vec256_extract(buf[i], 1) >> (k*16)) & GFMASK;
132 out[ (4*2 + k)*16 + i ] = (vec256_extract(buf[i], 2) >> (k*16)) & GFMASK;
133 out[ (4*3 + k)*16 + i ] = (vec256_extract(buf[i], 3) >> (k*16)) & GFMASK;
134 }
135 }
136
137 /* input: in, sequence of field elements */
138 /* output: out, minimal polynomial of in */
139 void bm(vec128 *out, vec256 *in)
140 {
141 int i;
142 uint16_t N, L;
143 uint16_t mask;
144 uint64_t one = 1;
145 uint64_t v[2];
146
147 vec128 prod[ GFBITS ];
148 vec128 interval[GFBITS];
149
150 CRYPTO_ALIGN(32) vec128 db[ GFBITS ][ 2 ];
151 CRYPTO_ALIGN(32) vec128 BC_tmp[ GFBITS ][ 2 ];
152 CRYPTO_ALIGN(32) vec128 BC[ GFBITS ][ 2 ];
153
154 gf d, b;
155 gf coefs[256];
156
157 // initialization
158
159 get_coefs(coefs, in);
160
161 BC[0][0] = vec128_set2x(0, one << 62);
162 BC[0][1] = vec128_set2x(0, one << 63);
163
164 for (i = 1; i < GFBITS; i++)
165 BC[i][0] = BC[i][1] = vec128_setzero();
166
167 b = 1;
168 L = 0;
169
170 //
171
172 for (i = 0; i < GFBITS; i++)
173 interval[i] = vec128_setzero();
174
175 for (N = 0; N < SYS_T*2; N++)
176 {
177 update_asm(interval, coefs[N], 16);
178 vec128_mul_asm(prod, interval, BC[0]+1, 32);
179
180 d = vec_reduce_asm(prod);
181
182 mask = crypto_uint64_nonzero_mask(d) & crypto_uint64_leq_mask(L*2, N);
183
184 for (i = 0; i < GFBITS; i++)
185 {
186 db[i][0] = vec128_setbits(crypto_int64_bitmod_01(d, i));
187 db[i][1] = vec128_setbits(crypto_int64_bitmod_01(b, i));
188 }
189
190 vec256_mul((vec256*) BC_tmp, (vec256*) db, (vec256*) BC);
191
192 vec128_cmov(BC, mask);
193 update_asm(BC, 0, 32);
194
195 for (i = 0; i < GFBITS; i++)
196 BC[i][1] = vec128_xor(BC_tmp[i][0], BC_tmp[i][1]);
197
198 b = (d & mask) | (b & ~mask);
199 L = ((N+1-L) & mask) | (L & ~mask);
200 }
201
202 for (i = 0; i < GFBITS; i++)
203 {
204 v[0] = vec128_extract(BC[i][1], 0);
205 v[1] = vec128_extract(BC[i][1], 1);
206
207 out[i] = vec128_set2x((v[0] >> 8) | (v[1] << 56), v[1] >> 8);
208 }
209 }
210