Debian Codegraph @

crypto_core/inv3sntrup653/avx/r3_recipgen.py

raw
1 #!/usr/bin/env python3
2
3 import re
4 import sys
5 from math import ceil
6
7 p = int(sys.argv[1])
8 numvec = ceil(p/256)
9 ppad = 256*numvec
10
11 # see comment below about order of coefficients
12 f = [-1,-1] + [0]*(p-2) + [1]
13 f = list(reversed(f))
14 while len(f)%256: f += [0]
15 f0 = []
16 for j in range(len(f)//256):
17 for i in range(4):
18 for k in range(64):
19 f0 += [f[j*256+i+k*4]]
20 f1 = [1 if f0i<0 else 0 for f0i in f0]
21 f0 = [f0i&1 for f0i in f0]
22
23 # ---------- utility functions
24
25 out = """\
26 // 20250302 djb: port to -Wc++-compat
27 // 20240812 djb: more cryptoint usage
28 #include "crypto_core.h"
29
30 #include <immintrin.h>
31
32 #include "crypto_int8.h"
33 #define int8 crypto_int8
34 typedef int8 small;
35
36 #include "crypto_int32.h"
37 #include "crypto_int64.h"
38 #include "crypto_uint64.h"
39
40 #define p P
41 #define ppad PPAD
42 #define numvec NUMVEC
43
44 typedef __m256i vec256;
45
46 /*
47 This code stores PPAD-coeff poly as vec256[NUMVEC].
48 Order of 256 coefficients in each vec256
49 is optimized in light of costs of vector instructions:
50 0,4,...,252 in 64-bit word;
51 1,5,...,253 in 64-bit word;
52 2,6,...,254 in 64-bit word;
53 3,7,...,255 in 64-bit word.
54 */
55
56 static inline void vec256_frombits(vec256 *v,const small *b)
57 {
58 int i;
59
60 for (i = 0;i < numvec;++i) {
61 vec256 b0 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 0,1,...,31 */
62 vec256 b1 = _mm256_loadu_si256((vec256 *) b); b += 32; /* 32,33,... */
63 vec256 b2 = _mm256_loadu_si256((vec256 *) b); b += 32;
64 vec256 b3 = _mm256_loadu_si256((vec256 *) b); b += 32;
65 vec256 b4 = _mm256_loadu_si256((vec256 *) b); b += 32;
66 vec256 b5 = _mm256_loadu_si256((vec256 *) b); b += 32;
67 vec256 b6 = _mm256_loadu_si256((vec256 *) b); b += 32;
68 vec256 b7 = _mm256_loadu_si256((vec256 *) b); b += 32;
69
70 vec256 c0 = _mm256_unpacklo_epi32(b0,b1); /* 0 1 2 3 32 33 34 35 4 5 6 7 36 37 38 39 ... 55 */
71 vec256 c1 = _mm256_unpackhi_epi32(b0,b1); /* 8 9 10 11 40 41 42 43 ... 63 */
72 vec256 c2 = _mm256_unpacklo_epi32(b2,b3);
73 vec256 c3 = _mm256_unpackhi_epi32(b2,b3);
74 vec256 c4 = _mm256_unpacklo_epi32(b4,b5);
75 vec256 c5 = _mm256_unpackhi_epi32(b4,b5);
76 vec256 c6 = _mm256_unpacklo_epi32(b6,b7);
77 vec256 c7 = _mm256_unpackhi_epi32(b6,b7);
78
79 vec256 d0 = c0 | _mm256_slli_epi32(c1,2); /* 0 8, 1 9, 2 10, 3 11, 32 40, 33 41, ..., 55 63 */
80 vec256 d2 = c2 | _mm256_slli_epi32(c3,2);
81 vec256 d4 = c4 | _mm256_slli_epi32(c5,2);
82 vec256 d6 = c6 | _mm256_slli_epi32(c7,2);
83
84 vec256 e0 = _mm256_unpacklo_epi64(d0,d2);
85 vec256 e2 = _mm256_unpackhi_epi64(d0,d2);
86 vec256 e4 = _mm256_unpacklo_epi64(d4,d6);
87 vec256 e6 = _mm256_unpackhi_epi64(d4,d6);
88
89 vec256 f0 = e0 | _mm256_slli_epi32(e2,1);
90 vec256 f4 = e4 | _mm256_slli_epi32(e6,1);
91
92 vec256 g0 = _mm256_permute2x128_si256(f0,f4,0x20);
93 vec256 g4 = _mm256_permute2x128_si256(f0,f4,0x31);
94
95 vec256 h = g0 | _mm256_slli_epi32(g4,4);
96
97 #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 )
98 h = _mm256_shuffle_epi8(h,TRANSPOSE);
99 h = _mm256_permute4x64_epi64(h,0xd8);
100 h = _mm256_shuffle_epi32(h,0xd8);
101
102 *v++ = h;
103 }
104 }
105
106 static inline void vec256_tobits(const vec256 *v,small *b)
107 {
108 int i;
109
110 for (i = 0;i < numvec;++i) {
111 vec256 h = *v++;
112
113 h = _mm256_shuffle_epi32(h,0xd8);
114 h = _mm256_permute4x64_epi64(h,0xd8);
115 h = _mm256_shuffle_epi8(h,TRANSPOSE);
116
117 vec256 g0 = h & _mm256_set1_epi8(15);
118 vec256 g4 = _mm256_srli_epi32(h,4) & _mm256_set1_epi8(15);
119
120 vec256 f0 = _mm256_permute2x128_si256(g0,g4,0x20);
121 vec256 f4 = _mm256_permute2x128_si256(g0,g4,0x31);
122
123 vec256 e0 = f0 & _mm256_set1_epi8(5);
124 vec256 e2 = _mm256_srli_epi32(f0,1) & _mm256_set1_epi8(5);
125 vec256 e4 = f4 & _mm256_set1_epi8(5);
126 vec256 e6 = _mm256_srli_epi32(f4,1) & _mm256_set1_epi8(5);
127
128 vec256 d0 = _mm256_unpacklo_epi32(e0,e2);
129 vec256 d2 = _mm256_unpackhi_epi32(e0,e2);
130 vec256 d4 = _mm256_unpacklo_epi32(e4,e6);
131 vec256 d6 = _mm256_unpackhi_epi32(e4,e6);
132
133 vec256 c0 = d0 & _mm256_set1_epi8(1);
134 vec256 c1 = _mm256_srli_epi32(d0,2) & _mm256_set1_epi8(1);
135 vec256 c2 = d2 & _mm256_set1_epi8(1);
136 vec256 c3 = _mm256_srli_epi32(d2,2) & _mm256_set1_epi8(1);
137 vec256 c4 = d4 & _mm256_set1_epi8(1);
138 vec256 c5 = _mm256_srli_epi32(d4,2) & _mm256_set1_epi8(1);
139 vec256 c6 = d6 & _mm256_set1_epi8(1);
140 vec256 c7 = _mm256_srli_epi32(d6,2) & _mm256_set1_epi8(1);
141
142 vec256 b0 = _mm256_unpacklo_epi64(c0,c1);
143 vec256 b1 = _mm256_unpackhi_epi64(c0,c1);
144 vec256 b2 = _mm256_unpacklo_epi64(c2,c3);
145 vec256 b3 = _mm256_unpackhi_epi64(c2,c3);
146 vec256 b4 = _mm256_unpacklo_epi64(c4,c5);
147 vec256 b5 = _mm256_unpackhi_epi64(c4,c5);
148 vec256 b6 = _mm256_unpacklo_epi64(c6,c7);
149 vec256 b7 = _mm256_unpackhi_epi64(c6,c7);
150
151 _mm256_storeu_si256((vec256 *) b,b0); b += 32;
152 _mm256_storeu_si256((vec256 *) b,b1); b += 32;
153 _mm256_storeu_si256((vec256 *) b,b2); b += 32;
154 _mm256_storeu_si256((vec256 *) b,b3); b += 32;
155 _mm256_storeu_si256((vec256 *) b,b4); b += 32;
156 _mm256_storeu_si256((vec256 *) b,b5); b += 32;
157 _mm256_storeu_si256((vec256 *) b,b6); b += 32;
158 _mm256_storeu_si256((vec256 *) b,b7); b += 32;
159 }
160 }
161
162 static void vec256_init(vec256 *G0,vec256 *G1,const small *s)
163 {
164 int i;
165 small srev[ppad+(ppad-p)];
166 small si;
167 small g0[ppad];
168 small g1[ppad];
169
170 for (i = 0;i < p;++i) srev[ppad-1-i] = s[i];
171 for (i = 0;i < ppad-p;++i) srev[i] = 0;
172 for (i = p;i < ppad;++i) srev[i+ppad-p] = 0;
173
174 for (i = 0;i < ppad;++i) {
175 si = srev[i+ppad-p];
176 g0[i] = crypto_int8_bottombit_01(si);
177 g1[i] = (si >> 1) & g0[i];
178 }
179
180 vec256_frombits(G0,g0);
181 vec256_frombits(G1,g1);
182 }
183
184 static void vec256_final(small *out,const vec256 *V0,const vec256 *V1)
185 {
186 int i;
187 small v0[ppad];
188 small v1[ppad];
189 small v[ppad];
190 small vrev[ppad+(ppad-p)];
191
192 vec256_tobits(V0,v0);
193 vec256_tobits(V1,v1);
194
195 for (i = 0;i < ppad;++i)
196 v[i] = v0[i] + 2*v1[i] - 4*(v0[i]&v1[i]);
197
198 for (i = 0;i < ppad;++i) vrev[i] = v[ppad-1-i];
199 for (i = ppad;i < ppad+(ppad-p);++i) vrev[i] = 0;
200
201 for (i = 0;i < p;++i) out[i] = vrev[i+ppad-p];
202 }
203
204 static inline void vec256_swap(vec256 *f,vec256 *g,int len,vec256 mask)
205 {
206 vec256 flip;
207 int i;
208
209 for (i = 0;i < len;++i) {
210 flip = mask & (f[i] ^ g[i]);
211 f[i] ^= flip;
212 g[i] ^= flip;
213 }
214 }
215
216 static inline void vec256_scale(vec256 *f0,vec256 *f1,const vec256 c0,const vec256 c1)
217 {
218 int i;
219
220 for (i = 0;i < numvec;++i) {
221 vec256 f0i = f0[i];
222 vec256 f1i = f1[i];
223
224 f0i &= c0;
225 f1i ^= c1;
226 f1i &= f0i;
227
228 f0[i] = f0i;
229 f1[i] = f1i;
230 }
231 }
232
233 static inline void vec256_eliminate(vec256 *f0,vec256 *f1,vec256 *g0,vec256 *g1,int len,const vec256 c0,const vec256 c1)
234 {
235 int i;
236
237 for (i = 0;i < len;++i) {
238 vec256 f0i = f0[i];
239 vec256 f1i = f1[i];
240 vec256 g0i = g0[i];
241 vec256 g1i = g1[i];
242 vec256 t;
243
244 f0i &= c0;
245 f1i ^= c1;
246 f1i &= f0i;
247
248 t = g0i ^ f0i;
249 g0[i] = t | (g1i ^ f1i);
250 g1[i] = (g1i ^ f0i) & (f1i ^ t);
251 }
252 }
253
254 static inline int vec256_bit0mask(vec256 *f)
255 {
256 return crypto_int32_bottombit_mask(_mm_cvtsi128_si32(_mm256_castsi256_si128(f[0])));
257 }
258
259 """
260
261 # ---------- divx
262
263 for j in range(1,numvec+1):
264 out += 'static inline void vec256_divx_%d(vec256 *f)\n' % j
265 out += '{\n'
266 for i in range(j):
267 out += ' vec256 f%d = f[%d];\n' % (i,i)
268 out += '\n'
269 for i in range(j):
270 out += ' unsigned long long low%d = _mm_cvtsi128_si64(_mm256_castsi256_si128(f%d));\n' % (i,i)
271 out += '\n'
272 for i in range(j):
273 if i == j-1:
274 out += ' low%d = low%d >> 1;\n' % (i,i)
275 else:
276 out += ' low%d = (low%d >> 1) | crypto_uint64_shlmod(low%d,63);\n' % (i,i,i+1)
277 out += '\n'
278 for i in range(j):
279 out += ' f%d = _mm256_blend_epi32(f%d,_mm256_set_epi64x(0,0,0,low%d),0x3);\n' % (i,i,i)
280 out += '\n'
281 for i in range(j):
282 out += ' f[%d] = _mm256_permute4x64_epi64(f%d,0x39);\n' % (i,i)
283 out += '}\n'
284 out += '\n'
285
286 # ----------
287
288 for j in range(1,numvec+1):
289 out += 'static inline void vec256_timesx_%d(vec256 *f)\n' % j
290 out += '{\n'
291 for i in range(j):
292 out += ' vec256 f%d = _mm256_permute4x64_epi64(f[%d],0x93);\n' % (i,i)
293 out += '\n'
294 for i in range(j):
295 if (j,i) in [(3,0),(3,1)]: # XXX: search through subsets for optimal timings
296 out += ' unsigned long long low%d = *(unsigned long long *) &f%d;\n' % (i,i)
297 else:
298 out += ' unsigned long long low%d = _mm_cvtsi128_si64(_mm256_castsi256_si128(f%d));\n' % (i,i)
299 out += '\n'
300 for i in reversed(range(j)):
301 if i == 0:
302 out += ' low%d = low%d << 1;\n' % (i,i)
303 else:
304 out += ' low%d = (low%d << 1) | crypto_int64_negative_01(low%d);\n' % (i,i,i-1)
305 out += '\n'
306 for i in range(j):
307 if (j,i) in [(3,0),(3,1)]: # XXX: search through subsets for optimal timings
308 out += ' *(unsigned long long *) &f%d = low%d;\n' % (i,i)
309 else:
310 out += ' f%d = _mm256_blend_epi32(f%d,_mm256_set_epi64x(0,0,0,low%d),0x3);\n' % (i,i,i)
311 out += '\n'
312 for i in range(j):
313 out += ' f[%d] = f%d;\n' % (i,i)
314 out += '}\n'
315 out += '\n'
316
317 # ---------- reciprocal initialization
318
319 out += """
320 void crypto_core(unsigned char *outbytes,const unsigned char *inbytes,const unsigned char *kbytes,const unsigned char *cbytes)
321 {
322 small *out = (small *) outbytes;
323 small *in = (small *) inbytes;
324 vec256 F0[numvec];
325 vec256 F1[numvec];
326 vec256 G0[numvec];
327 vec256 G1[numvec];
328 vec256 V0[numvec];
329 vec256 V1[numvec];
330 vec256 R0[numvec];
331 vec256 R1[numvec];
332 vec256 c0vec,c1vec;
333 int loop;
334 int c0,c1;
335 int minusdelta = -1;
336 int swapmask;
337 vec256 swapvec;
338
339 vec256_init(G0,G1,in);
340 """
341
342 for name,bits in [('F0',f0),('F1',f1)]:
343 for j in range(len(bits)//256):
344 u = []
345 for k in range(j*256,j*256+256,32):
346 u = [sum(bits[k+i]<<i for i in range(32))] + u
347 if u == [0]*8:
348 out += ' %s[%d] = _mm256_set1_epi32(0);\n' % (name,j)
349 else:
350 u = ','.join(str(uk if uk < 2**31 else uk-2**32) for uk in u)
351 out += ' %s[%d] = _mm256_set_epi32(%s);\n' % (name,j,u)
352
353 out += '\n'
354 for i in range(numvec):
355 out += ' V0[%d] = _mm256_set1_epi32(0);\n' % i
356 out += ' V1[%d] = _mm256_set1_epi32(0);\n' % i
357
358 out += '\n'
359 for i in range(numvec):
360 if i == 0:
361 out += ' R0[%d] = _mm256_set_epi32(0,0,0,0,0,0,0,1);\n' % i
362 else:
363 out += ' R0[%d] = _mm256_set1_epi32(0);\n' % i
364 out += ' R1[%d] = _mm256_set1_epi32(0);\n' % i
365
366 # ---------- reciprocal main loop
367
368 vvecgvec = []
369 for loop in range(2*p-1):
370 vvec = min(numvec,1+loop//256)
371 gvec = min(numvec,1+(2*p-2-loop)//256)
372 vvecgvec += [(vvec,gvec)]
373
374 while len(vvecgvec) > 0:
375 vvec,gvec = vvecgvec[0]
376 loops = 1
377 while loops < len(vvecgvec) and vvecgvec[loops] == (vvec,gvec):
378 loops += 1
379
380 out += """
381 for (loop = %d;loop > 0;--loop) {
382 vec256_timesx_%d(V0);
383 vec256_timesx_%d(V1);
384 swapmask = crypto_int32_negative_mask(minusdelta) & vec256_bit0mask(G0);
385
386 c0 = vec256_bit0mask(F0) & vec256_bit0mask(G0);
387 c1 = vec256_bit0mask(F1) ^ vec256_bit0mask(G1);
388 c1 &= c0;
389
390 minusdelta ^= swapmask & (minusdelta ^ -minusdelta);
391 minusdelta -= 1;
392
393 swapvec = _mm256_set1_epi32(swapmask);
394 vec256_swap(F0,G0,%d,swapvec);
395 vec256_swap(F1,G1,%d,swapvec);
396
397 c0vec = _mm256_set1_epi32(c0);
398 c1vec = _mm256_set1_epi32(c1);
399
400 vec256_eliminate(F0,F1,G0,G1,%d,c0vec,c1vec);
401 vec256_divx_%d(G0);
402 vec256_divx_%d(G1);
403
404 vec256_swap(V0,R0,%d,swapvec);
405 vec256_swap(V1,R1,%d,swapvec);
406 vec256_eliminate(V0,V1,R0,R1,%d,c0vec,c1vec);
407 }
408 """ % (loops,vvec,vvec,gvec,gvec,gvec,gvec,gvec,vvec,vvec,vvec)
409
410 vvecgvec = vvecgvec[loops:]
411
412 # ---------- reciprocal finalization
413
414 out += """
415 c0vec = _mm256_set1_epi32(vec256_bit0mask(F0));
416 c1vec = _mm256_set1_epi32(vec256_bit0mask(F1));
417 vec256_scale(V0,V1,c0vec,c1vec);
418
419 vec256_final(out,V0,V1);
420 out[p] = crypto_int32_negative_mask(minusdelta);
421 }\
422 """
423
424 out = re.sub(r'\bP\b',str(p),out)
425 out = re.sub(r'\bPPAD\b',str(ppad),out)
426 out = re.sub(r'\bNUMVEC\b',str(numvec),out)
427
428 print(out)