Debian Codegraph @

crypto_core/multsntrup953/avx/mult1024.c

raw
1 // 20240812 djb: more cryptoint usage
2 #include "ntt.h"
3 #include <immintrin.h>
4 #include "crypto_int8.h"
5
6 typedef int8_t int8;
7 typedef int16_t int16;
8
9 #define int16x16 __m256i
10 #define load_x16(p) _mm256_loadu_si256((int16x16 *) (p))
11 #define store_x16(p,v) _mm256_storeu_si256((int16x16 *) (p),(v))
12 #define const_x16 _mm256_set1_epi16
13 #define add_x16 _mm256_add_epi16
14 #define sub_x16 _mm256_sub_epi16
15 #define mullo_x16 _mm256_mullo_epi16
16 #define mulhi_x16 _mm256_mulhi_epi16
17 #define mulhrs_x16 _mm256_mulhrs_epi16
18 #define signmask_x16(x) _mm256_srai_epi16((x),15)
19
20 static inline int16x16 squeeze_6343_x16(int16x16 x)
21 {
22 return sub_x16(x,mullo_x16(mulhrs_x16(x,const_x16(5)),const_x16(6343)));
23 }
24
25 static inline int16x16 squeeze_7681_x16(int16x16 x)
26 {
27 return sub_x16(x,mullo_x16(mulhrs_x16(x,const_x16(4)),const_x16(7681)));
28 }
29
30 static inline int16x16 squeeze_10753_x16(int16x16 x)
31 {
32 return sub_x16(x,mullo_x16(mulhrs_x16(x,const_x16(3)),const_x16(10753)));
33 }
34
35 static inline int16x16 mulmod_6343_x16(int16x16 x,int16x16 y)
36 {
37 int16x16 yqinv = mullo_x16(y,const_x16(10487)); /* XXX: precompute */
38 int16x16 b = mulhi_x16(x,y);
39 int16x16 d = mullo_x16(x,yqinv);
40 int16x16 e = mulhi_x16(d,const_x16(6343));
41 return sub_x16(b,e);
42 }
43
44 static inline int16x16 mulmod_7681_x16(int16x16 x,int16x16 y)
45 {
46 int16x16 yqinv = mullo_x16(y,const_x16(-7679)); /* XXX: precompute */
47 int16x16 b = mulhi_x16(x,y);
48 int16x16 d = mullo_x16(x,yqinv);
49 int16x16 e = mulhi_x16(d,const_x16(7681));
50 return sub_x16(b,e);
51 }
52
53 static inline int16x16 mulmod_10753_x16(int16x16 x,int16x16 y)
54 {
55 int16x16 yqinv = mullo_x16(y,const_x16(-10751)); /* XXX: precompute */
56 int16x16 b = mulhi_x16(x,y);
57 int16x16 d = mullo_x16(x,yqinv);
58 int16x16 e = mulhi_x16(d,const_x16(10753));
59 return sub_x16(b,e);
60 }
61
62 static void stride(int16 fpad[4][512],const int16 f[1024])
63 {
64 int16x16 f0,f1,f2,f3,g0,g1,g2,g3;
65 int i,j;
66
67 for (j = 0;j < 256;j += 16) {
68 f0 = load_x16(&f[0]);
69 f1 = load_x16(&f[16]);
70 f2 = load_x16(&f[32]);
71 f3 = load_x16(&f[48]);
72 f += 64;
73
74 g0 = _mm256_permute2x128_si256(f0,f2,0x20);
75 g1 = _mm256_permute2x128_si256(f0,f2,0x31);
76 g2 = _mm256_permute2x128_si256(f1,f3,0x20);
77 g3 = _mm256_permute2x128_si256(f1,f3,0x31);
78 f0 = _mm256_unpacklo_epi16(g0,g1);
79 f1 = _mm256_unpackhi_epi16(g0,g1);
80 f2 = _mm256_unpacklo_epi16(g2,g3);
81 f3 = _mm256_unpackhi_epi16(g2,g3);
82 g0 = _mm256_unpacklo_epi16(f0,f1);
83 g1 = _mm256_unpackhi_epi16(f0,f1);
84 g2 = _mm256_unpacklo_epi16(f2,f3);
85 g3 = _mm256_unpackhi_epi16(f2,f3);
86 f0 = _mm256_unpacklo_epi64(g0,g2);
87 f1 = _mm256_unpackhi_epi64(g0,g2);
88 f2 = _mm256_unpacklo_epi64(g1,g3);
89 f3 = _mm256_unpackhi_epi64(g1,g3);
90
91 store_x16(&fpad[0][j],f0);
92 store_x16(&fpad[1][j],f1);
93 store_x16(&fpad[2][j],f2);
94 store_x16(&fpad[3][j],f3);
95 }
96
97 for (i = 0;i < 4;++i)
98 for (j = 256;j < 512;++j)
99 fpad[i][j] = 0;
100 }
101
102 static void unstride(int16 f[2048],const int16 fpad[4][512])
103 {
104 int16x16 f0,f1,f2,f3,g0,g1,g2,g3,h0,h1,h2,h3;
105 int j;
106
107 for (j = 0;j < 512;j += 16) {
108 f0 = load_x16(&fpad[0][j]);
109 f1 = load_x16(&fpad[1][j]);
110 f2 = load_x16(&fpad[2][j]);
111 f3 = load_x16(&fpad[3][j]);
112
113 g2 = _mm256_unpacklo_epi16(f2,f3);
114 g3 = _mm256_unpackhi_epi16(f2,f3);
115 g0 = _mm256_unpacklo_epi16(f0,f1);
116 h0 = _mm256_unpacklo_epi32(g0,g2);
117 h1 = _mm256_unpackhi_epi32(g0,g2);
118 g1 = _mm256_unpackhi_epi16(f0,f1);
119 h2 = _mm256_unpacklo_epi32(g1,g3);
120 h3 = _mm256_unpackhi_epi32(g1,g3);
121 f1 = _mm256_permute2x128_si256(h2,h3,0x20);
122 f3 = _mm256_permute2x128_si256(h2,h3,0x31);
123 f0 = _mm256_permute2x128_si256(h0,h1,0x20);
124 f2 = _mm256_permute2x128_si256(h0,h1,0x31);
125
126 store_x16(&f[0],f0);
127 store_x16(&f[16],f1);
128 store_x16(&f[32],f2);
129 store_x16(&f[48],f3);
130 f += 64;
131 }
132 }
133
134 #define ALIGNED __attribute((aligned(512)))
135
136 static const ALIGNED int16 y_7681[512] = {
137 #include "precomp7681.inc"
138 } ;
139 static const ALIGNED int16 y_10753[512] = {
140 #include "precomp10753.inc"
141 } ;
142 /*
143 can also compute these on the fly, and share storage,
144 at expense of 2 NTTs on top of the 24 NTTs below:
145 ...
146 for (i = 0;i < 512;++i) y_7681[i] = 0;
147 y_7681[1] = -3593;
148 ntt512_7681(y_7681,1);
149 ...
150 for (i = 0;i < 512;++i) y_10753[i] = 0;
151 y_10753[1] = 1018;
152 ntt512_10753(y_10753,1);
153 */
154
155 static void mult1024(int16 h[2048],const int16 f[1024],const int16 g[1024])
156 {
157 ALIGNED int16 fgpad[8][512];
158 #define fpad fgpad
159 #define gpad (fgpad+4)
160 #define hpad fpad
161 ALIGNED int16 h_7681[2048];
162 ALIGNED int16 h_10753[2048];
163 int i;
164
165 stride(fpad,f);
166 stride(gpad,g);
167
168 ntt512_7681(fgpad[0],8);
169
170 for (i = 0;i < 512;i += 16) {
171 int16x16 f0 = squeeze_7681_x16(load_x16(&fpad[0][i]));
172 int16x16 f1 = squeeze_7681_x16(load_x16(&fpad[1][i]));
173 int16x16 f2 = squeeze_7681_x16(load_x16(&fpad[2][i]));
174 int16x16 f3 = squeeze_7681_x16(load_x16(&fpad[3][i]));
175 int16x16 g0 = squeeze_7681_x16(load_x16(&gpad[0][i]));
176 int16x16 g1 = squeeze_7681_x16(load_x16(&gpad[1][i]));
177 int16x16 g2 = squeeze_7681_x16(load_x16(&gpad[2][i]));
178 int16x16 g3 = squeeze_7681_x16(load_x16(&gpad[3][i]));
179 int16x16 d0 = mulmod_7681_x16(f0,g0);
180 int16x16 d1 = mulmod_7681_x16(f1,g1);
181 int16x16 d2 = mulmod_7681_x16(f2,g2);
182 int16x16 d3 = mulmod_7681_x16(f3,g3);
183 int16x16 d0d1 = add_x16(d0,d1);
184 int16x16 d0d1d2 = add_x16(d0d1,d2);
185 int16x16 d0d1d2d3 = squeeze_7681_x16(add_x16(d0d1d2,d3));
186 int16x16 d2d3 = add_x16(d2,d3);
187 int16x16 d1d2d3 = add_x16(d1,d2d3);
188 int16x16 e01 = mulmod_7681_x16(sub_x16(f0,f1),sub_x16(g0,g1));
189 int16x16 e02 = mulmod_7681_x16(sub_x16(f0,f2),sub_x16(g0,g2));
190 int16x16 e03 = mulmod_7681_x16(sub_x16(f0,f3),sub_x16(g0,g3));
191 int16x16 e12 = mulmod_7681_x16(sub_x16(f1,f2),sub_x16(g1,g2));
192 int16x16 e13 = mulmod_7681_x16(sub_x16(f1,f3),sub_x16(g1,g3));
193 int16x16 e23 = mulmod_7681_x16(sub_x16(f2,f3),sub_x16(g2,g3));
194 int16x16 h0 = d0;
195 int16x16 h1 = sub_x16(d0d1,e01);
196 int16x16 h2 = sub_x16(d0d1d2,e02);
197 int16x16 h3 = sub_x16(d0d1d2d3,add_x16(e12,e03));
198 int16x16 h4 = sub_x16(d1d2d3,e13);
199 int16x16 h5 = sub_x16(d2d3,e23);
200 int16x16 h6 = d3;
201 int16x16 twist = load_x16(&y_7681[i]);
202 h4 = mulmod_7681_x16(h4,twist);
203 h5 = mulmod_7681_x16(h5,twist);
204 h6 = mulmod_7681_x16(h6,twist);
205 h0 = add_x16(h0,h4);
206 h1 = add_x16(h1,h5);
207 h2 = add_x16(h2,h6);
208 store_x16(&hpad[0][i],squeeze_7681_x16(h0));
209 store_x16(&hpad[1][i],squeeze_7681_x16(h1));
210 store_x16(&hpad[2][i],squeeze_7681_x16(h2));
211 store_x16(&hpad[3][i],squeeze_7681_x16(h3));
212 }
213
214 invntt512_7681(hpad[0],4);
215 unstride(h_7681,hpad);
216
217 stride(fpad,f);
218 stride(gpad,g);
219
220 ntt512_10753(fgpad[0],8);
221
222 for (i = 0;i < 512;i += 16) {
223 int16x16 f0 = squeeze_10753_x16(load_x16(&fpad[0][i]));
224 int16x16 f1 = squeeze_10753_x16(load_x16(&fpad[1][i]));
225 int16x16 f2 = squeeze_10753_x16(load_x16(&fpad[2][i]));
226 int16x16 f3 = squeeze_10753_x16(load_x16(&fpad[3][i]));
227 int16x16 g0 = squeeze_10753_x16(load_x16(&gpad[0][i]));
228 int16x16 g1 = squeeze_10753_x16(load_x16(&gpad[1][i]));
229 int16x16 g2 = squeeze_10753_x16(load_x16(&gpad[2][i]));
230 int16x16 g3 = squeeze_10753_x16(load_x16(&gpad[3][i]));
231 int16x16 d0 = mulmod_10753_x16(f0,g0);
232 int16x16 d1 = mulmod_10753_x16(f1,g1);
233 int16x16 d2 = mulmod_10753_x16(f2,g2);
234 int16x16 d3 = mulmod_10753_x16(f3,g3);
235 int16x16 d0d1 = add_x16(d0,d1);
236 int16x16 d0d1d2 = add_x16(d0d1,d2);
237 int16x16 d0d1d2d3 = squeeze_10753_x16(add_x16(d0d1d2,d3));
238 int16x16 d2d3 = add_x16(d2,d3);
239 int16x16 d1d2d3 = add_x16(d1,d2d3);
240 int16x16 e01 = mulmod_10753_x16(sub_x16(f0,f1),sub_x16(g0,g1));
241 int16x16 e02 = mulmod_10753_x16(sub_x16(f0,f2),sub_x16(g0,g2));
242 int16x16 e03 = mulmod_10753_x16(sub_x16(f0,f3),sub_x16(g0,g3));
243 int16x16 e12 = mulmod_10753_x16(sub_x16(f1,f2),sub_x16(g1,g2));
244 int16x16 e13 = mulmod_10753_x16(sub_x16(f1,f3),sub_x16(g1,g3));
245 int16x16 e23 = mulmod_10753_x16(sub_x16(f2,f3),sub_x16(g2,g3));
246 int16x16 h0 = d0;
247 int16x16 h1 = sub_x16(d0d1,e01);
248 int16x16 h2 = sub_x16(d0d1d2,e02);
249 int16x16 h3 = sub_x16(d0d1d2d3,add_x16(e12,e03));
250 int16x16 h4 = sub_x16(d1d2d3,e13);
251 int16x16 h5 = sub_x16(d2d3,e23);
252 int16x16 h6 = d3;
253 int16x16 twist = load_x16(&y_10753[i]);
254 h4 = mulmod_10753_x16(h4,twist);
255 h5 = mulmod_10753_x16(h5,twist);
256 h6 = mulmod_10753_x16(h6,twist);
257 h0 = add_x16(h0,h4);
258 h1 = add_x16(h1,h5);
259 h2 = add_x16(h2,h6);
260 store_x16(&hpad[0][i],squeeze_10753_x16(h0));
261 store_x16(&hpad[1][i],squeeze_10753_x16(h1));
262 store_x16(&hpad[2][i],squeeze_10753_x16(h2));
263 store_x16(&hpad[3][i],squeeze_10753_x16(h3));
264 }
265
266 invntt512_10753(hpad[0],4);
267 unstride(h_10753,hpad);
268
269 for (i = 0;i < 2048;i += 16) {
270 int16x16 u1 = load_x16(&h_10753[i]);
271 int16x16 u2 = load_x16(&h_7681[i]);
272 int16x16 t;
273 u1 = mulmod_10753_x16(u1,const_x16(1268));
274 u2 = mulmod_7681_x16(u2,const_x16(956));
275 t = mulmod_7681_x16(sub_x16(u2,u1),const_x16(-2539));
276 t = add_x16(u1,mulmod_6343_x16(t,const_x16(1308)));
277 store_x16(&h[i],t);
278 }
279 }
280
281 #include "crypto_core.h"
282 #include "crypto_decode_953xint16.h"
283 #define crypto_decode_pxint16 crypto_decode_953xint16
284 #include "crypto_encode_953xint16.h"
285 #define crypto_encode_pxint16 crypto_encode_953xint16
286
287 #define p 953
288 #define q 6343
289
290 static inline int16x16 freeze_6343_x16(int16x16 x)
291 {
292 int16x16 mask, xq;
293 x = add_x16(x,const_x16(q)&signmask_x16(x));
294 mask = signmask_x16(sub_x16(x,const_x16((q+1)/2)));
295 xq = sub_x16(x,const_x16(q));
296 x = _mm256_blendv_epi8(xq,x,mask);
297 return x;
298 }
299
300 void crypto_core(unsigned char *outbytes,const unsigned char *inbytes,const unsigned char *kbytes,const unsigned char *cbytes)
301 {
302 ALIGNED int16 f[1024];
303 ALIGNED int16 g[1024];
304 ALIGNED int16 fg[2048];
305 #define h f
306 int i;
307 int16x16 x;
308
309 x = const_x16(0);
310 for (i = p&~15;i < 1024;i += 16) store_x16(&f[i],x);
311 for (i = p&~15;i < 1024;i += 16) store_x16(&g[i],x);
312
313 crypto_decode_pxint16(f,inbytes);
314
315 for (i = 0;i < 1024;i += 16) {
316 x = load_x16(&f[i]);
317 x = freeze_6343_x16(squeeze_6343_x16(x));
318 store_x16(&f[i],x);
319 }
320 for (i = 0;i < p;++i) {
321 int8 gi = kbytes[i];
322 int8 gi0 = crypto_int8_bottombit_01(gi);
323 g[i] = gi0-(gi&(gi0<<1));
324 }
325
326 mult1024(fg,f,g);
327
328 fg[0] -= fg[p-1];
329 for (i = 0;i < 1024;i += 16) {
330 int16x16 fgi = load_x16(&fg[i]);
331 int16x16 fgip = load_x16(&fg[i + p]);
332 int16x16 fgip1 = load_x16(&fg[i + p - 1]);
333 x = add_x16(fgi,add_x16(fgip,fgip1));
334 x = freeze_6343_x16(squeeze_6343_x16(x));
335 store_x16(&h[i],x);
336 }
337
338 crypto_encode_pxint16(outbytes,h);
339 }