Debian Codegraph @

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