Debian Codegraph @

crypto_core/inv3sntrup653/avx/r3_recip.c

raw
1 // 20250302 djb: port to -Wc++-compat
2 // 20240812 djb: more cryptoint usage
3 #include "crypto_core.h"
4
5 #include <immintrin.h>
6
7 #include "crypto_int8.h"
8 #define int8 crypto_int8
9 typedef int8 small;
10
11 #include "crypto_int32.h"
12 #include "crypto_int64.h"
13 #include "crypto_uint64.h"
14
15 #define p 653
16 #define ppad 768
17 #define numvec 3
18
19 typedef __m256i vec256;
20
21 /*
22 This code stores 768-coeff poly as vec256[3].
23 Order of 256 coefficients in each vec256
24 is optimized in light of costs of vector instructions:
25 0,4,...,252 in 64-bit word;
26 1,5,...,253 in 64-bit word;
27 2,6,...,254 in 64-bit word;
28 3,7,...,255 in 64-bit word.
29 */
30
31 static inline void vec256_frombits(vec256 *v,const small *b)
32 {
33 int i;
34
35 for (i = 0;i < numvec;++i) {
36 vec256 b0 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 0,1,...,31 */
37 vec256 b1 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 32,33,... */
38 vec256 b2 = _mm256_loadu_si256((vec256 *) b); b += 32;
39 vec256 b3 = _mm256_loadu_si256((vec256 *) b); b += 32;
40 vec256 b4 = _mm256_loadu_si256((vec256 *) b); b += 32;
41 vec256 b5 = _mm256_loadu_si256((vec256 *) b); b += 32;
42 vec256 b6 = _mm256_loadu_si256((vec256 *) b); b += 32;
43 vec256 b7 = _mm256_loadu_si256((vec256 *) b); b += 32;
44
45 vec256 c0 = _mm256_unpacklo_epi32(b0,b1); /* 0 1 2 3 32 33 34 35 4 5 6 7 36 37 38 39 ... 55 */
46 vec256 c1 = _mm256_unpackhi_epi32(b0,b1); /* 8 9 10 11 40 41 42 43 ... 63 */
47 vec256 c2 = _mm256_unpacklo_epi32(b2,b3);
48 vec256 c3 = _mm256_unpackhi_epi32(b2,b3);
49 vec256 c4 = _mm256_unpacklo_epi32(b4,b5);
50 vec256 c5 = _mm256_unpackhi_epi32(b4,b5);
51 vec256 c6 = _mm256_unpacklo_epi32(b6,b7);
52 vec256 c7 = _mm256_unpackhi_epi32(b6,b7);
53
54 vec256 d0 = c0 | _mm256_slli_epi32(c1,2); /* 0 8, 1 9, 2 10, 3 11, 32 40, 33 41, ..., 55 63 */
55 vec256 d2 = c2 | _mm256_slli_epi32(c3,2);
56 vec256 d4 = c4 | _mm256_slli_epi32(c5,2);
57 vec256 d6 = c6 | _mm256_slli_epi32(c7,2);
58
59 vec256 e0 = _mm256_unpacklo_epi64(d0,d2);
60 vec256 e2 = _mm256_unpackhi_epi64(d0,d2);
61 vec256 e4 = _mm256_unpacklo_epi64(d4,d6);
62 vec256 e6 = _mm256_unpackhi_epi64(d4,d6);
63
64 vec256 f0 = e0 | _mm256_slli_epi32(e2,1);
65 vec256 f4 = e4 | _mm256_slli_epi32(e6,1);
66
67 vec256 g0 = _mm256_permute2x128_si256(f0,f4,0x20);
68 vec256 g4 = _mm256_permute2x128_si256(f0,f4,0x31);
69
70 vec256 h = g0 | _mm256_slli_epi32(g4,4);
71
72 #define TRANSPOSE _mm256_set_epi8( 31,27,23,19, 30,26,22,18, 29,25,21,17, 28,24,20,16, 15,11,7,3, 14,10,6,2, 13,9,5,1, 12,8,4,0 )
73 h = _mm256_shuffle_epi8(h,TRANSPOSE);
74 h = _mm256_permute4x64_epi64(h,0xd8);
75 h = _mm256_shuffle_epi32(h,0xd8);
76
77 *v++ = h;
78 }
79 }
80
81 static inline void vec256_tobits(const vec256 *v,small *b)
82 {
83 int i;
84
85 for (i = 0;i < numvec;++i) {
86 vec256 h = *v++;
87
88 h = _mm256_shuffle_epi32(h,0xd8);
89 h = _mm256_permute4x64_epi64(h,0xd8);
90 h = _mm256_shuffle_epi8(h,TRANSPOSE);
91
92 vec256 g0 = h & _mm256_set1_epi8(15);
93 vec256 g4 = _mm256_srli_epi32(h,4) & _mm256_set1_epi8(15);
94
95 vec256 f0 = _mm256_permute2x128_si256(g0,g4,0x20);
96 vec256 f4 = _mm256_permute2x128_si256(g0,g4,0x31);
97
98 vec256 e0 = f0 & _mm256_set1_epi8(5);
99 vec256 e2 = _mm256_srli_epi32(f0,1) & _mm256_set1_epi8(5);
100 vec256 e4 = f4 & _mm256_set1_epi8(5);
101 vec256 e6 = _mm256_srli_epi32(f4,1) & _mm256_set1_epi8(5);
102
103 vec256 d0 = _mm256_unpacklo_epi32(e0,e2);
104 vec256 d2 = _mm256_unpackhi_epi32(e0,e2);
105 vec256 d4 = _mm256_unpacklo_epi32(e4,e6);
106 vec256 d6 = _mm256_unpackhi_epi32(e4,e6);
107
108 vec256 c0 = d0 & _mm256_set1_epi8(1);
109 vec256 c1 = _mm256_srli_epi32(d0,2) & _mm256_set1_epi8(1);
110 vec256 c2 = d2 & _mm256_set1_epi8(1);
111 vec256 c3 = _mm256_srli_epi32(d2,2) & _mm256_set1_epi8(1);
112 vec256 c4 = d4 & _mm256_set1_epi8(1);
113 vec256 c5 = _mm256_srli_epi32(d4,2) & _mm256_set1_epi8(1);
114 vec256 c6 = d6 & _mm256_set1_epi8(1);
115 vec256 c7 = _mm256_srli_epi32(d6,2) & _mm256_set1_epi8(1);
116
117 vec256 b0 = _mm256_unpacklo_epi64(c0,c1);
118 vec256 b1 = _mm256_unpackhi_epi64(c0,c1);
119 vec256 b2 = _mm256_unpacklo_epi64(c2,c3);
120 vec256 b3 = _mm256_unpackhi_epi64(c2,c3);
121 vec256 b4 = _mm256_unpacklo_epi64(c4,c5);
122 vec256 b5 = _mm256_unpackhi_epi64(c4,c5);
123 vec256 b6 = _mm256_unpacklo_epi64(c6,c7);
124 vec256 b7 = _mm256_unpackhi_epi64(c6,c7);
125
126 _mm256_storeu_si256((vec256 *) b,b0); b += 32;
127 _mm256_storeu_si256((vec256 *) b,b1); b += 32;
128 _mm256_storeu_si256((vec256 *) b,b2); b += 32;
129 _mm256_storeu_si256((vec256 *) b,b3); b += 32;
130 _mm256_storeu_si256((vec256 *) b,b4); b += 32;
131 _mm256_storeu_si256((vec256 *) b,b5); b += 32;
132 _mm256_storeu_si256((vec256 *) b,b6); b += 32;
133 _mm256_storeu_si256((vec256 *) b,b7); b += 32;
134 }
135 }
136
137 static void vec256_init(vec256 *G0,vec256 *G1,const small *s)
138 {
139 int i;
140 small srev[ppad+(ppad-p)];
141 small si;
142 small g0[ppad];
143 small g1[ppad];
144
145 for (i = 0;i < p;++i) srev[ppad-1-i] = s[i];
146 for (i = 0;i < ppad-p;++i) srev[i] = 0;
147 for (i = p;i < ppad;++i) srev[i+ppad-p] = 0;
148
149 for (i = 0;i < ppad;++i) {
150 si = srev[i+ppad-p];
151 g0[i] = crypto_int8_bottombit_01(si);
152 g1[i] = (si >> 1) & g0[i];
153 }
154
155 vec256_frombits(G0,g0);
156 vec256_frombits(G1,g1);
157 }
158
159 static void vec256_final(small *out,const vec256 *V0,const vec256 *V1)
160 {
161 int i;
162 small v0[ppad];
163 small v1[ppad];
164 small v[ppad];
165 small vrev[ppad+(ppad-p)];
166
167 vec256_tobits(V0,v0);
168 vec256_tobits(V1,v1);
169
170 for (i = 0;i < ppad;++i)
171 v[i] = v0[i] + 2*v1[i] - 4*(v0[i]&v1[i]);
172
173 for (i = 0;i < ppad;++i) vrev[i] = v[ppad-1-i];
174 for (i = ppad;i < ppad+(ppad-p);++i) vrev[i] = 0;
175
176 for (i = 0;i < p;++i) out[i] = vrev[i+ppad-p];
177 }
178
179 static inline void vec256_swap(vec256 *f,vec256 *g,int len,vec256 mask)
180 {
181 vec256 flip;
182 int i;
183
184 for (i = 0;i < len;++i) {
185 flip = mask & (f[i] ^ g[i]);
186 f[i] ^= flip;
187 g[i] ^= flip;
188 }
189 }
190
191 static inline void vec256_scale(vec256 *f0,vec256 *f1,const vec256 c0,const vec256 c1)
192 {
193 int i;
194
195 for (i = 0;i < numvec;++i) {
196 vec256 f0i = f0[i];
197 vec256 f1i = f1[i];
198
199 f0i &= c0;
200 f1i ^= c1;
201 f1i &= f0i;
202
203 f0[i] = f0i;
204 f1[i] = f1i;
205 }
206 }
207
208 static inline void vec256_eliminate(vec256 *f0,vec256 *f1,vec256 *g0,vec256 *g1,int len,const vec256 c0,const vec256 c1)
209 {
210 int i;
211
212 for (i = 0;i < len;++i) {
213 vec256 f0i = f0[i];
214 vec256 f1i = f1[i];
215 vec256 g0i = g0[i];
216 vec256 g1i = g1[i];
217 vec256 t;
218
219 f0i &= c0;
220 f1i ^= c1;
221 f1i &= f0i;
222
223 t = g0i ^ f0i;
224 g0[i] = t | (g1i ^ f1i);
225 g1[i] = (g1i ^ f0i) & (f1i ^ t);
226 }
227 }
228
229 static inline int vec256_bit0mask(vec256 *f)
230 {
231 return crypto_int32_bottombit_mask(_mm_cvtsi128_si32(_mm256_castsi256_si128(f[0])));
232 }
233
234 static inline void vec256_divx_1(vec256 *f)
235 {
236 vec256 f0 = f[0];
237
238 unsigned long long low0 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f0));
239
240 low0 = low0 >> 1;
241
242 f0 = _mm256_blend_epi32(f0,_mm256_set_epi64x(0,0,0,low0),0x3);
243
244 f[0] = _mm256_permute4x64_epi64(f0,0x39);
245 }
246
247 static inline void vec256_divx_2(vec256 *f)
248 {
249 vec256 f0 = f[0];
250 vec256 f1 = f[1];
251
252 unsigned long long low0 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f0));
253 unsigned long long low1 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f1));
254
255 low0 = (low0 >> 1) | crypto_uint64_shlmod(low1,63);
256 low1 = low1 >> 1;
257
258 f0 = _mm256_blend_epi32(f0,_mm256_set_epi64x(0,0,0,low0),0x3);
259 f1 = _mm256_blend_epi32(f1,_mm256_set_epi64x(0,0,0,low1),0x3);
260
261 f[0] = _mm256_permute4x64_epi64(f0,0x39);
262 f[1] = _mm256_permute4x64_epi64(f1,0x39);
263 }
264
265 static inline void vec256_divx_3(vec256 *f)
266 {
267 vec256 f0 = f[0];
268 vec256 f1 = f[1];
269 vec256 f2 = f[2];
270
271 unsigned long long low0 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f0));
272 unsigned long long low1 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f1));
273 unsigned long long low2 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f2));
274
275 low0 = (low0 >> 1) | crypto_uint64_shlmod(low1,63);
276 low1 = (low1 >> 1) | crypto_uint64_shlmod(low2,63);
277 low2 = low2 >> 1;
278
279 f0 = _mm256_blend_epi32(f0,_mm256_set_epi64x(0,0,0,low0),0x3);
280 f1 = _mm256_blend_epi32(f1,_mm256_set_epi64x(0,0,0,low1),0x3);
281 f2 = _mm256_blend_epi32(f2,_mm256_set_epi64x(0,0,0,low2),0x3);
282
283 f[0] = _mm256_permute4x64_epi64(f0,0x39);
284 f[1] = _mm256_permute4x64_epi64(f1,0x39);
285 f[2] = _mm256_permute4x64_epi64(f2,0x39);
286 }
287
288 static inline void vec256_timesx_1(vec256 *f)
289 {
290 vec256 f0 = _mm256_permute4x64_epi64(f[0],0x93);
291
292 unsigned long long low0 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f0));
293
294 low0 = low0 << 1;
295
296 f0 = _mm256_blend_epi32(f0,_mm256_set_epi64x(0,0,0,low0),0x3);
297
298 f[0] = f0;
299 }
300
301 static inline void vec256_timesx_2(vec256 *f)
302 {
303 vec256 f0 = _mm256_permute4x64_epi64(f[0],0x93);
304 vec256 f1 = _mm256_permute4x64_epi64(f[1],0x93);
305
306 unsigned long long low0 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f0));
307 unsigned long long low1 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f1));
308
309 low1 = (low1 << 1) | crypto_int64_negative_01(low0);
310 low0 = low0 << 1;
311
312 f0 = _mm256_blend_epi32(f0,_mm256_set_epi64x(0,0,0,low0),0x3);
313 f1 = _mm256_blend_epi32(f1,_mm256_set_epi64x(0,0,0,low1),0x3);
314
315 f[0] = f0;
316 f[1] = f1;
317 }
318
319 static inline void vec256_timesx_3(vec256 *f)
320 {
321 vec256 f0 = _mm256_permute4x64_epi64(f[0],0x93);
322 vec256 f1 = _mm256_permute4x64_epi64(f[1],0x93);
323 vec256 f2 = _mm256_permute4x64_epi64(f[2],0x93);
324
325 unsigned long long low0 = *(unsigned long long *) &f0;
326 unsigned long long low1 = *(unsigned long long *) &f1;
327 unsigned long long low2 = _mm_cvtsi128_si64(_mm256_castsi256_si128(f2));
328
329 low2 = (low2 << 1) | crypto_int64_negative_01(low1);
330 low1 = (low1 << 1) | crypto_int64_negative_01(low0);
331 low0 = low0 << 1;
332
333 *(unsigned long long *) &f0 = low0;
334 *(unsigned long long *) &f1 = low1;
335 f2 = _mm256_blend_epi32(f2,_mm256_set_epi64x(0,0,0,low2),0x3);
336
337 f[0] = f0;
338 f[1] = f1;
339 f[2] = f2;
340 }
341
342
343 void crypto_core(unsigned char *outbytes,const unsigned char *inbytes,const unsigned char *kbytes,const unsigned char *cbytes)
344 {
345 small *out = (small *) outbytes;
346 small *in = (small *) inbytes;
347 vec256 F0[numvec];
348 vec256 F1[numvec];
349 vec256 G0[numvec];
350 vec256 G1[numvec];
351 vec256 V0[numvec];
352 vec256 V1[numvec];
353 vec256 R0[numvec];
354 vec256 R1[numvec];
355 vec256 c0vec,c1vec;
356 int loop;
357 int c0,c1;
358 int minusdelta = -1;
359 int swapmask;
360 vec256 swapvec;
361
362 vec256_init(G0,G1,in);
363 F0[0] = _mm256_set_epi32(0,0,0,0,0,0,0,1);
364 F0[1] = _mm256_set1_epi32(0);
365 F0[2] = _mm256_set_epi32(0,0,0,0,8,0,8,0);
366 F1[0] = _mm256_set1_epi32(0);
367 F1[1] = _mm256_set1_epi32(0);
368 F1[2] = _mm256_set_epi32(0,0,0,0,8,0,8,0);
369
370 V0[0] = _mm256_set1_epi32(0);
371 V1[0] = _mm256_set1_epi32(0);
372 V0[1] = _mm256_set1_epi32(0);
373 V1[1] = _mm256_set1_epi32(0);
374 V0[2] = _mm256_set1_epi32(0);
375 V1[2] = _mm256_set1_epi32(0);
376
377 R0[0] = _mm256_set_epi32(0,0,0,0,0,0,0,1);
378 R1[0] = _mm256_set1_epi32(0);
379 R0[1] = _mm256_set1_epi32(0);
380 R1[1] = _mm256_set1_epi32(0);
381 R0[2] = _mm256_set1_epi32(0);
382 R1[2] = _mm256_set1_epi32(0);
383
384 for (loop = 256;loop > 0;--loop) {
385 vec256_timesx_1(V0);
386 vec256_timesx_1(V1);
387 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
388
389 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
390 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
391 c1 &= c0;
392
393 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
394 minusdelta -= 1;
395
396 swapvec = _mm256_set1_epi32(swapmask);
397 vec256_swap(F0,G0,3,swapvec);
398 vec256_swap(F1,G1,3,swapvec);
399
400 c0vec = _mm256_set1_epi32(c0);
401 c1vec = _mm256_set1_epi32(c1);
402
403 vec256_eliminate(F0,F1,G0,G1,3,c0vec,c1vec);
404 vec256_divx_3(G0);
405 vec256_divx_3(G1);
406
407 vec256_swap(V0,R0,1,swapvec);
408 vec256_swap(V1,R1,1,swapvec);
409 vec256_eliminate(V0,V1,R0,R1,1,c0vec,c1vec);
410 }
411
412 for (loop = 256;loop > 0;--loop) {
413 vec256_timesx_2(V0);
414 vec256_timesx_2(V1);
415 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
416
417 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
418 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
419 c1 &= c0;
420
421 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
422 minusdelta -= 1;
423
424 swapvec = _mm256_set1_epi32(swapmask);
425 vec256_swap(F0,G0,3,swapvec);
426 vec256_swap(F1,G1,3,swapvec);
427
428 c0vec = _mm256_set1_epi32(c0);
429 c1vec = _mm256_set1_epi32(c1);
430
431 vec256_eliminate(F0,F1,G0,G1,3,c0vec,c1vec);
432 vec256_divx_3(G0);
433 vec256_divx_3(G1);
434
435 vec256_swap(V0,R0,2,swapvec);
436 vec256_swap(V1,R1,2,swapvec);
437 vec256_eliminate(V0,V1,R0,R1,2,c0vec,c1vec);
438 }
439
440 for (loop = 281;loop > 0;--loop) {
441 vec256_timesx_3(V0);
442 vec256_timesx_3(V1);
443 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
444
445 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
446 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
447 c1 &= c0;
448
449 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
450 minusdelta -= 1;
451
452 swapvec = _mm256_set1_epi32(swapmask);
453 vec256_swap(F0,G0,3,swapvec);
454 vec256_swap(F1,G1,3,swapvec);
455
456 c0vec = _mm256_set1_epi32(c0);
457 c1vec = _mm256_set1_epi32(c1);
458
459 vec256_eliminate(F0,F1,G0,G1,3,c0vec,c1vec);
460 vec256_divx_3(G0);
461 vec256_divx_3(G1);
462
463 vec256_swap(V0,R0,3,swapvec);
464 vec256_swap(V1,R1,3,swapvec);
465 vec256_eliminate(V0,V1,R0,R1,3,c0vec,c1vec);
466 }
467
468 for (loop = 256;loop > 0;--loop) {
469 vec256_timesx_3(V0);
470 vec256_timesx_3(V1);
471 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
472
473 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
474 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
475 c1 &= c0;
476
477 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
478 minusdelta -= 1;
479
480 swapvec = _mm256_set1_epi32(swapmask);
481 vec256_swap(F0,G0,2,swapvec);
482 vec256_swap(F1,G1,2,swapvec);
483
484 c0vec = _mm256_set1_epi32(c0);
485 c1vec = _mm256_set1_epi32(c1);
486
487 vec256_eliminate(F0,F1,G0,G1,2,c0vec,c1vec);
488 vec256_divx_2(G0);
489 vec256_divx_2(G1);
490
491 vec256_swap(V0,R0,3,swapvec);
492 vec256_swap(V1,R1,3,swapvec);
493 vec256_eliminate(V0,V1,R0,R1,3,c0vec,c1vec);
494 }
495
496 for (loop = 256;loop > 0;--loop) {
497 vec256_timesx_3(V0);
498 vec256_timesx_3(V1);
499 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
500
501 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
502 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
503 c1 &= c0;
504
505 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
506 minusdelta -= 1;
507
508 swapvec = _mm256_set1_epi32(swapmask);
509 vec256_swap(F0,G0,1,swapvec);
510 vec256_swap(F1,G1,1,swapvec);
511
512 c0vec = _mm256_set1_epi32(c0);
513 c1vec = _mm256_set1_epi32(c1);
514
515 vec256_eliminate(F0,F1,G0,G1,1,c0vec,c1vec);
516 vec256_divx_1(G0);
517 vec256_divx_1(G1);
518
519 vec256_swap(V0,R0,3,swapvec);
520 vec256_swap(V1,R1,3,swapvec);
521 vec256_eliminate(V0,V1,R0,R1,3,c0vec,c1vec);
522 }
523
524 c0vec = _mm256_set1_epi32(vec256_bit0mask(F0));
525 c1vec = _mm256_set1_epi32(vec256_bit0mask(F1));
526 vec256_scale(V0,V1,c0vec,c1vec);
527
528 vec256_final(out,V0,V1);
529 out[p] = crypto_int32_negative_mask(minusdelta);
530 }