Debian Codegraph @

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