Debian Codegraph @

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