1 #include "int32_sort.h"
2 #define int32 int32_t
3
4 #include <immintrin.h>
5
6 // compatibility for __m256i_u
7 #include "compat.h"
8
9 typedef __m256i int32x8;
10 #define int32x8_load(z) _mm256_loadu_si256((__m256i_u *) (z))
11 #define int32x8_store(z,i) _mm256_storeu_si256((__m256i_u *) (z),(i))
12 #define int32x8_min _mm256_min_epi32
13 #define int32x8_max _mm256_max_epi32
14
15 #define int32x8_MINMAX(a,b) \
16 do { \
17 int32x8 c = int32x8_min(a, b); \
18 (b) = int32x8_max(a,b); \
19 (a) = c; \
20 } while(0)
21
int32_MINMAX(int32 * a,int32 * b)22 static inline void int32_MINMAX(int32 *a, int32 *b) {
23 int32 ab = *b ^ *a;
24 int32 c = *b - *a;
25 c ^= ab & (c ^ *b);
26 c >>= 31;
27 c &= ab;
28 *a ^= c;
29 *b ^= c;
30 }
31
minmax_vector(int32 * x,int32 * y,size_t n)32 static void minmax_vector(int32 *x, int32 *y, size_t n) {
33 if (n < 8) {
34 while (n > 0) {
35 int32_MINMAX(x, y);
36 ++x;
37 ++y;
38 --n;
39 }
40 return;
41 }
42 if (n & 7) {
43 int32x8 x0 = int32x8_load(x + n - 8);
44 int32x8 y0 = int32x8_load(y + n - 8);
45 int32x8_MINMAX(x0, y0);
46 int32x8_store(x + n - 8, x0);
47 int32x8_store(y + n - 8, y0);
48 n &= ~7;
49 }
50 do {
51 int32x8 x0 = int32x8_load(x);
52 int32x8 y0 = int32x8_load(y);
53 int32x8_MINMAX(x0, y0);
54 int32x8_store(x, x0);
55 int32x8_store(y, y0);
56 x += 8;
57 y += 8;
58 n -= 8;
59 } while (n);
60 }
61
62 /* stages 8,4,2,1 of size-16 bitonic merging */
merge16_finish(int32 * x,int32x8 x0,int32x8 x1,int flagdown)63 static void merge16_finish(int32 *x, int32x8 x0, int32x8 x1, int flagdown) {
64 int32x8 b0, b1, c0, c1, mask;
65
66 int32x8_MINMAX(x0, x1);
67
68 b0 = _mm256_permute2x128_si256(x0, x1, 0x20); /* A0123B0123 */
69 b1 = _mm256_permute2x128_si256(x0, x1, 0x31); /* A4567B4567 */
70
71 int32x8_MINMAX(b0, b1);
72
73 c0 = _mm256_unpacklo_epi64(b0, b1); /* A0145B0145 */
74 c1 = _mm256_unpackhi_epi64(b0, b1); /* A2367B2367 */
75
76 int32x8_MINMAX(c0, c1);
77
78 b0 = _mm256_unpacklo_epi32(c0, c1); /* A0213B0213 */
79 b1 = _mm256_unpackhi_epi32(c0, c1); /* A4657B4657 */
80
81 c0 = _mm256_unpacklo_epi64(b0, b1); /* A0246B0246 */
82 c1 = _mm256_unpackhi_epi64(b0, b1); /* A1357B1357 */
83
84 int32x8_MINMAX(c0, c1);
85
86 b0 = _mm256_unpacklo_epi32(c0, c1); /* A0123B0123 */
87 b1 = _mm256_unpackhi_epi32(c0, c1); /* A4567B4567 */
88
89 x0 = _mm256_permute2x128_si256(b0, b1, 0x20); /* A01234567 */
90 x1 = _mm256_permute2x128_si256(b0, b1, 0x31); /* A01234567 */
91
92 if (flagdown) {
93 mask = _mm256_set1_epi32(-1);
94 x0 ^= mask;
95 x1 ^= mask;
96 }
97
98 int32x8_store(&x[0], x0);
99 int32x8_store(&x[8], x1);
100 }
101
102 /* stages 64,32 of bitonic merging; n is multiple of 128 */
int32_twostages_32(int32 * x,size_t n)103 static void int32_twostages_32(int32 *x, size_t n) {
104 size_t i;
105
106 while (n > 0) {
107 for (i = 0; i < 32; i += 8) {
108 int32x8 x0 = int32x8_load(&x[i]);
109 int32x8 x1 = int32x8_load(&x[i + 32]);
110 int32x8 x2 = int32x8_load(&x[i + 64]);
111 int32x8 x3 = int32x8_load(&x[i + 96]);
112
113 int32x8_MINMAX(x0, x2);
114 int32x8_MINMAX(x1, x3);
115 int32x8_MINMAX(x0, x1);
116 int32x8_MINMAX(x2, x3);
117
118 int32x8_store(&x[i], x0);
119 int32x8_store(&x[i + 32], x1);
120 int32x8_store(&x[i + 64], x2);
121 int32x8_store(&x[i + 96], x3);
122 }
123 x += 128;
124 n -= 128;
125 }
126 }
127
128 /* stages 4q,2q,q of bitonic merging */
int32_threestages(int32 * x,size_t n,size_t q)129 static size_t int32_threestages(int32 *x, size_t n, size_t q) {
130 size_t k, i;
131
132 for (k = 0; k + 8 * q <= n; k += 8 * q) {
133 for (i = k; i < k + q; i += 8) {
134 int32x8 x0 = int32x8_load(&x[i]);
135 int32x8 x1 = int32x8_load(&x[i + q]);
136 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
137 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
138 int32x8 x4 = int32x8_load(&x[i + 4 * q]);
139 int32x8 x5 = int32x8_load(&x[i + 5 * q]);
140 int32x8 x6 = int32x8_load(&x[i + 6 * q]);
141 int32x8 x7 = int32x8_load(&x[i + 7 * q]);
142
143 int32x8_MINMAX(x0, x4);
144 int32x8_MINMAX(x1, x5);
145 int32x8_MINMAX(x2, x6);
146 int32x8_MINMAX(x3, x7);
147 int32x8_MINMAX(x0, x2);
148 int32x8_MINMAX(x1, x3);
149 int32x8_MINMAX(x4, x6);
150 int32x8_MINMAX(x5, x7);
151 int32x8_MINMAX(x0, x1);
152 int32x8_MINMAX(x2, x3);
153 int32x8_MINMAX(x4, x5);
154 int32x8_MINMAX(x6, x7);
155
156 int32x8_store(&x[i], x0);
157 int32x8_store(&x[i + q], x1);
158 int32x8_store(&x[i + 2 * q], x2);
159 int32x8_store(&x[i + 3 * q], x3);
160 int32x8_store(&x[i + 4 * q], x4);
161 int32x8_store(&x[i + 5 * q], x5);
162 int32x8_store(&x[i + 6 * q], x6);
163 int32x8_store(&x[i + 7 * q], x7);
164 }
165 }
166
167 return k;
168 }
169
170 /* n is a power of 2; n >= 8; if n == 8 then flagdown */
171 // NOLINTNEXTLINE(google-readability-function-size)
int32_sort_2power(int32 * x,size_t n,int flagdown)172 static void int32_sort_2power(int32 *x, size_t n, int flagdown) {
173 size_t p, q, i, j, k;
174 int32x8 mask;
175
176 if (n == 8) {
177 int32 x0 = x[0];
178 int32 x1 = x[1];
179 int32 x2 = x[2];
180 int32 x3 = x[3];
181 int32 x4 = x[4];
182 int32 x5 = x[5];
183 int32 x6 = x[6];
184 int32 x7 = x[7];
185
186 /* odd-even sort instead of bitonic sort */
187
188 int32_MINMAX(&x1, &x0);
189 int32_MINMAX(&x3, &x2);
190 int32_MINMAX(&x2, &x0);
191 int32_MINMAX(&x3, &x1);
192 int32_MINMAX(&x2, &x1);
193
194 int32_MINMAX(&x5, &x4);
195 int32_MINMAX(&x7, &x6);
196 int32_MINMAX(&x6, &x4);
197 int32_MINMAX(&x7, &x5);
198 int32_MINMAX(&x6, &x5);
199
200 int32_MINMAX(&x4, &x0);
201 int32_MINMAX(&x6, &x2);
202 int32_MINMAX(&x4, &x2);
203
204 int32_MINMAX(&x5, &x1);
205 int32_MINMAX(&x7, &x3);
206 int32_MINMAX(&x5, &x3);
207
208 int32_MINMAX(&x2, &x1);
209 int32_MINMAX(&x4, &x3);
210 int32_MINMAX(&x6, &x5);
211
212 x[0] = x0;
213 x[1] = x1;
214 x[2] = x2;
215 x[3] = x3;
216 x[4] = x4;
217 x[5] = x5;
218 x[6] = x6;
219 x[7] = x7;
220 return;
221 }
222
223 if (n == 16) {
224 int32x8 x0, x1, b0, b1, c0, c1;
225
226 x0 = int32x8_load(&x[0]);
227 x1 = int32x8_load(&x[8]);
228
229 mask = _mm256_set_epi32(0, 0, -1, -1, 0, 0, -1, -1);
230
231 x0 ^= mask; /* A01234567 */
232 x1 ^= mask; /* B01234567 */
233
234 b0 = _mm256_unpacklo_epi32(x0, x1); /* AB0AB1AB4AB5 */
235 b1 = _mm256_unpackhi_epi32(x0, x1); /* AB2AB3AB6AB7 */
236
237 c0 = _mm256_unpacklo_epi64(b0, b1); /* AB0AB2AB4AB6 */
238 c1 = _mm256_unpackhi_epi64(b0, b1); /* AB1AB3AB5AB7 */
239
240 int32x8_MINMAX(c0, c1);
241
242 mask = _mm256_set_epi32(0, 0, -1, -1, -1, -1, 0, 0);
243 c0 ^= mask;
244 c1 ^= mask;
245
246 b0 = _mm256_unpacklo_epi32(c0, c1); /* A01B01A45B45 */
247 b1 = _mm256_unpackhi_epi32(c0, c1); /* A23B23A67B67 */
248
249 int32x8_MINMAX(b0, b1);
250
251 x0 = _mm256_unpacklo_epi64(b0, b1); /* A01234567 */
252 x1 = _mm256_unpackhi_epi64(b0, b1); /* B01234567 */
253
254 b0 = _mm256_unpacklo_epi32(x0, x1); /* AB0AB1AB4AB5 */
255 b1 = _mm256_unpackhi_epi32(x0, x1); /* AB2AB3AB6AB7 */
256
257 c0 = _mm256_unpacklo_epi64(b0, b1); /* AB0AB2AB4AB6 */
258 c1 = _mm256_unpackhi_epi64(b0, b1); /* AB1AB3AB5AB7 */
259
260 int32x8_MINMAX(c0, c1);
261
262 b0 = _mm256_unpacklo_epi32(c0, c1); /* A01B01A45B45 */
263 b1 = _mm256_unpackhi_epi32(c0, c1); /* A23B23A67B67 */
264
265 b0 ^= mask;
266 b1 ^= mask;
267
268 c0 = _mm256_permute2x128_si256(b0, b1, 0x20); /* A01B01A23B23 */
269 c1 = _mm256_permute2x128_si256(b0, b1, 0x31); /* A45B45A67B67 */
270
271 int32x8_MINMAX(c0, c1);
272
273 b0 = _mm256_permute2x128_si256(c0, c1, 0x20); /* A01B01A45B45 */
274 b1 = _mm256_permute2x128_si256(c0, c1, 0x31); /* A23B23A67B67 */
275
276 int32x8_MINMAX(b0, b1);
277
278 x0 = _mm256_unpacklo_epi64(b0, b1); /* A01234567 */
279 x1 = _mm256_unpackhi_epi64(b0, b1); /* B01234567 */
280
281 b0 = _mm256_unpacklo_epi32(x0, x1); /* AB0AB1AB4AB5 */
282 b1 = _mm256_unpackhi_epi32(x0, x1); /* AB2AB3AB6AB7 */
283
284 c0 = _mm256_unpacklo_epi64(b0, b1); /* AB0AB2AB4AB6 */
285 c1 = _mm256_unpackhi_epi64(b0, b1); /* AB1AB3AB5AB7 */
286
287 int32x8_MINMAX(c0, c1);
288
289 b0 = _mm256_unpacklo_epi32(c0, c1); /* A01B01A45B45 */
290 b1 = _mm256_unpackhi_epi32(c0, c1); /* A23B23A67B67 */
291
292 x0 = _mm256_unpacklo_epi64(b0, b1); /* A01234567 */
293 x1 = _mm256_unpackhi_epi64(b0, b1); /* B01234567 */
294
295 mask = _mm256_set1_epi32(-1);
296 if (flagdown) {
297 x1 ^= mask;
298 } else {
299 x0 ^= mask;
300 }
301
302 merge16_finish(x, x0, x1, flagdown);
303 return;
304 }
305
306 if (n == 32) {
307 int32x8 x0, x1, x2, x3;
308
309 int32_sort_2power(x, 16, 1);
310 int32_sort_2power(x + 16, 16, 0);
311
312 x0 = int32x8_load(&x[0]);
313 x1 = int32x8_load(&x[8]);
314 x2 = int32x8_load(&x[16]);
315 x3 = int32x8_load(&x[24]);
316
317 if (flagdown) {
318 mask = _mm256_set1_epi32(-1);
319 x0 ^= mask;
320 x1 ^= mask;
321 x2 ^= mask;
322 x3 ^= mask;
323 }
324
325 int32x8_MINMAX(x0, x2);
326 int32x8_MINMAX(x1, x3);
327
328 merge16_finish(x, x0, x1, flagdown);
329 merge16_finish(x + 16, x2, x3, flagdown);
330 return;
331 }
332
333 p = n >> 3;
334 for (i = 0; i < p; i += 8) {
335 int32x8 x0 = int32x8_load(&x[i]);
336 int32x8 x2 = int32x8_load(&x[i + 2 * p]);
337 int32x8 x4 = int32x8_load(&x[i + 4 * p]);
338 int32x8 x6 = int32x8_load(&x[i + 6 * p]);
339
340 /* odd-even stage instead of bitonic stage */
341
342 int32x8_MINMAX(x4, x0);
343 int32x8_MINMAX(x6, x2);
344 int32x8_MINMAX(x2, x0);
345 int32x8_MINMAX(x6, x4);
346 int32x8_MINMAX(x2, x4);
347
348 int32x8_store(&x[i], x0);
349 int32x8_store(&x[i + 2 * p], x2);
350 int32x8_store(&x[i + 4 * p], x4);
351 int32x8_store(&x[i + 6 * p], x6);
352
353 int32x8 x1 = int32x8_load(&x[i + p]);
354 int32x8 x3 = int32x8_load(&x[i + 3 * p]);
355 int32x8 x5 = int32x8_load(&x[i + 5 * p]);
356 int32x8 x7 = int32x8_load(&x[i + 7 * p]);
357
358 int32x8_MINMAX(x1, x5);
359 int32x8_MINMAX(x3, x7);
360 int32x8_MINMAX(x1, x3);
361 int32x8_MINMAX(x5, x7);
362 int32x8_MINMAX(x5, x3);
363
364 int32x8_store(&x[i + p], x1);
365 int32x8_store(&x[i + 3 * p], x3);
366 int32x8_store(&x[i + 5 * p], x5);
367 int32x8_store(&x[i + 7 * p], x7);
368 }
369
370 if (n >= 128) {
371 int flip, flipflip;
372
373 mask = _mm256_set1_epi32(-1);
374
375 for (j = 0; j < n; j += 32) {
376 int32x8 x0 = int32x8_load(&x[j]);
377 int32x8 x1 = int32x8_load(&x[j + 16]);
378 x0 ^= mask;
379 x1 ^= mask;
380 int32x8_store(&x[j], x0);
381 int32x8_store(&x[j + 16], x1);
382 }
383
384 p = 8;
385 for (;;) { /* for p in [8, 16, ..., n/16] */
386 q = p >> 1;
387 while (q >= 128) {
388 int32_threestages(x, n, q >> 2);
389 q >>= 3;
390 }
391 if (q == 64) {
392 int32_twostages_32(x, n);
393 q = 16;
394 }
395 if (q == 32) {
396 q = 8;
397 for (k = 0; k < n; k += 8 * q) {
398 for (i = k; i < k + q; i += 8) {
399 int32x8 x0 = int32x8_load(&x[i]);
400 int32x8 x1 = int32x8_load(&x[i + q]);
401 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
402 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
403 int32x8 x4 = int32x8_load(&x[i + 4 * q]);
404 int32x8 x5 = int32x8_load(&x[i + 5 * q]);
405 int32x8 x6 = int32x8_load(&x[i + 6 * q]);
406 int32x8 x7 = int32x8_load(&x[i + 7 * q]);
407
408 int32x8_MINMAX(x0, x4);
409 int32x8_MINMAX(x1, x5);
410 int32x8_MINMAX(x2, x6);
411 int32x8_MINMAX(x3, x7);
412 int32x8_MINMAX(x0, x2);
413 int32x8_MINMAX(x1, x3);
414 int32x8_MINMAX(x4, x6);
415 int32x8_MINMAX(x5, x7);
416 int32x8_MINMAX(x0, x1);
417 int32x8_MINMAX(x2, x3);
418 int32x8_MINMAX(x4, x5);
419 int32x8_MINMAX(x6, x7);
420
421 int32x8_store(&x[i], x0);
422 int32x8_store(&x[i + q], x1);
423 int32x8_store(&x[i + 2 * q], x2);
424 int32x8_store(&x[i + 3 * q], x3);
425 int32x8_store(&x[i + 4 * q], x4);
426 int32x8_store(&x[i + 5 * q], x5);
427 int32x8_store(&x[i + 6 * q], x6);
428 int32x8_store(&x[i + 7 * q], x7);
429 }
430 }
431 q = 4;
432 }
433 if (q == 16) {
434 q = 8;
435 for (k = 0; k < n; k += 4 * q) {
436 for (i = k; i < k + q; i += 8) {
437 int32x8 x0 = int32x8_load(&x[i]);
438 int32x8 x1 = int32x8_load(&x[i + q]);
439 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
440 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
441
442 int32x8_MINMAX(x0, x2);
443 int32x8_MINMAX(x1, x3);
444 int32x8_MINMAX(x0, x1);
445 int32x8_MINMAX(x2, x3);
446
447 int32x8_store(&x[i], x0);
448 int32x8_store(&x[i + q], x1);
449 int32x8_store(&x[i + 2 * q], x2);
450 int32x8_store(&x[i + 3 * q], x3);
451 }
452 }
453 q = 4;
454 }
455 if (q == 8) {
456 for (k = 0; k < n; k += q + q) {
457 int32x8 x0 = int32x8_load(&x[k]);
458 int32x8 x1 = int32x8_load(&x[k + q]);
459
460 int32x8_MINMAX(x0, x1);
461
462 int32x8_store(&x[k], x0);
463 int32x8_store(&x[k + q], x1);
464 }
465 }
466
467 q = n >> 3;
468 flip = 0;
469 if (p << 1 == q) {
470 flip = 1;
471 }
472 flipflip = 1 - flip;
473 for (j = 0; j < q; j += p + p) {
474 for (k = j; k < j + p + p; k += p) {
475 for (i = k; i < k + p; i += 8) {
476 int32x8 x0 = int32x8_load(&x[i]);
477 int32x8 x1 = int32x8_load(&x[i + q]);
478 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
479 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
480 int32x8 x4 = int32x8_load(&x[i + 4 * q]);
481 int32x8 x5 = int32x8_load(&x[i + 5 * q]);
482 int32x8 x6 = int32x8_load(&x[i + 6 * q]);
483 int32x8 x7 = int32x8_load(&x[i + 7 * q]);
484
485 int32x8_MINMAX(x0, x1);
486 int32x8_MINMAX(x2, x3);
487 int32x8_MINMAX(x4, x5);
488 int32x8_MINMAX(x6, x7);
489 int32x8_MINMAX(x0, x2);
490 int32x8_MINMAX(x1, x3);
491 int32x8_MINMAX(x4, x6);
492 int32x8_MINMAX(x5, x7);
493 int32x8_MINMAX(x0, x4);
494 int32x8_MINMAX(x1, x5);
495 int32x8_MINMAX(x2, x6);
496 int32x8_MINMAX(x3, x7);
497
498 if (flip) {
499 x0 ^= mask;
500 x1 ^= mask;
501 x2 ^= mask;
502 x3 ^= mask;
503 x4 ^= mask;
504 x5 ^= mask;
505 x6 ^= mask;
506 x7 ^= mask;
507 }
508
509 int32x8_store(&x[i], x0);
510 int32x8_store(&x[i + q], x1);
511 int32x8_store(&x[i + 2 * q], x2);
512 int32x8_store(&x[i + 3 * q], x3);
513 int32x8_store(&x[i + 4 * q], x4);
514 int32x8_store(&x[i + 5 * q], x5);
515 int32x8_store(&x[i + 6 * q], x6);
516 int32x8_store(&x[i + 7 * q], x7);
517 }
518 flip ^= 1;
519 }
520 flip ^= flipflip;
521 }
522
523 if (p << 4 == n) {
524 break;
525 }
526 p <<= 1;
527 }
528 }
529
530 for (p = 4; p >= 1; p >>= 1) {
531 int32 *z = x;
532 int32 *target = x + n;
533 if (p == 4) {
534 mask = _mm256_set_epi32(0, 0, 0, 0, -1, -1, -1, -1);
535 while (z != target) {
536 int32x8 x0 = int32x8_load(&z[0]);
537 int32x8 x1 = int32x8_load(&z[8]);
538 x0 ^= mask;
539 x1 ^= mask;
540 int32x8_store(&z[0], x0);
541 int32x8_store(&z[8], x1);
542 z += 16;
543 }
544 } else if (p == 2) {
545 mask = _mm256_set_epi32(0, 0, -1, -1, -1, -1, 0, 0);
546 while (z != target) {
547 int32x8 x0 = int32x8_load(&z[0]);
548 int32x8 x1 = int32x8_load(&z[8]);
549 x0 ^= mask;
550 x1 ^= mask;
551 int32x8 b0 = _mm256_permute2x128_si256(x0, x1, 0x20);
552 int32x8 b1 = _mm256_permute2x128_si256(x0, x1, 0x31);
553 int32x8_MINMAX(b0, b1);
554 int32x8 c0 = _mm256_permute2x128_si256(b0, b1, 0x20);
555 int32x8 c1 = _mm256_permute2x128_si256(b0, b1, 0x31);
556 int32x8_store(&z[0], c0);
557 int32x8_store(&z[8], c1);
558 z += 16;
559 }
560 } else { /* p == 1 */
561 mask = _mm256_set_epi32(0, -1, -1, 0, 0, -1, -1, 0);
562 while (z != target) {
563 int32x8 x0 = int32x8_load(&z[0]);
564 int32x8 x1 = int32x8_load(&z[8]);
565 x0 ^= mask;
566 x1 ^= mask;
567 int32x8 b0 = _mm256_permute2x128_si256(x0, x1, 0x20); /* A0123B0123 */
568 int32x8 b1 = _mm256_permute2x128_si256(x0, x1, 0x31); /* A4567B4567 */
569 int32x8 c0 = _mm256_unpacklo_epi64(b0, b1); /* A0145B0145 */
570 int32x8 c1 = _mm256_unpackhi_epi64(b0, b1); /* A2367B2367 */
571 int32x8_MINMAX(c0, c1);
572 int32x8 d0 = _mm256_unpacklo_epi64(c0, c1); /* A0123B0123 */
573 int32x8 d1 = _mm256_unpackhi_epi64(c0, c1); /* A4567B4567 */
574 int32x8_MINMAX(d0, d1);
575 int32x8 e0 = _mm256_permute2x128_si256(d0, d1, 0x20);
576 int32x8 e1 = _mm256_permute2x128_si256(d0, d1, 0x31);
577 int32x8_store(&z[0], e0);
578 int32x8_store(&z[8], e1);
579 z += 16;
580 }
581 }
582
583 q = n >> 4;
584 while (q >= 128 || q == 32) {
585 int32_threestages(x, n, q >> 2);
586 q >>= 3;
587 }
588 while (q >= 16) {
589 q >>= 1;
590 for (j = 0; j < n; j += 4 * q) {
591 for (k = j; k < j + q; k += 8) {
592 int32x8 x0 = int32x8_load(&x[k]);
593 int32x8 x1 = int32x8_load(&x[k + q]);
594 int32x8 x2 = int32x8_load(&x[k + 2 * q]);
595 int32x8 x3 = int32x8_load(&x[k + 3 * q]);
596
597 int32x8_MINMAX(x0, x2);
598 int32x8_MINMAX(x1, x3);
599 int32x8_MINMAX(x0, x1);
600 int32x8_MINMAX(x2, x3);
601
602 int32x8_store(&x[k], x0);
603 int32x8_store(&x[k + q], x1);
604 int32x8_store(&x[k + 2 * q], x2);
605 int32x8_store(&x[k + 3 * q], x3);
606 }
607 }
608 q >>= 1;
609 }
610 if (q == 8) {
611 for (j = 0; j < n; j += 2 * q) {
612 int32x8 x0 = int32x8_load(&x[j]);
613 int32x8 x1 = int32x8_load(&x[j + q]);
614
615 int32x8_MINMAX(x0, x1);
616
617 int32x8_store(&x[j], x0);
618 int32x8_store(&x[j + q], x1);
619 }
620 }
621
622 q = n >> 3;
623 for (k = 0; k < q; k += 8) {
624 int32x8 x0 = int32x8_load(&x[k]);
625 int32x8 x1 = int32x8_load(&x[k + q]);
626 int32x8 x2 = int32x8_load(&x[k + 2 * q]);
627 int32x8 x3 = int32x8_load(&x[k + 3 * q]);
628 int32x8 x4 = int32x8_load(&x[k + 4 * q]);
629 int32x8 x5 = int32x8_load(&x[k + 5 * q]);
630 int32x8 x6 = int32x8_load(&x[k + 6 * q]);
631 int32x8 x7 = int32x8_load(&x[k + 7 * q]);
632
633 int32x8_MINMAX(x0, x1);
634 int32x8_MINMAX(x2, x3);
635 int32x8_MINMAX(x4, x5);
636 int32x8_MINMAX(x6, x7);
637 int32x8_MINMAX(x0, x2);
638 int32x8_MINMAX(x1, x3);
639 int32x8_MINMAX(x4, x6);
640 int32x8_MINMAX(x5, x7);
641 int32x8_MINMAX(x0, x4);
642 int32x8_MINMAX(x1, x5);
643 int32x8_MINMAX(x2, x6);
644 int32x8_MINMAX(x3, x7);
645
646 int32x8_store(&x[k], x0);
647 int32x8_store(&x[k + q], x1);
648 int32x8_store(&x[k + 2 * q], x2);
649 int32x8_store(&x[k + 3 * q], x3);
650 int32x8_store(&x[k + 4 * q], x4);
651 int32x8_store(&x[k + 5 * q], x5);
652 int32x8_store(&x[k + 6 * q], x6);
653 int32x8_store(&x[k + 7 * q], x7);
654 }
655 }
656
657 /* everything is still masked with _mm256_set_epi32(0,-1,0,-1,0,-1,0,-1); */
658 mask = _mm256_set1_epi32(-1);
659
660 for (i = 0; i < n; i += 64) {
661 int32x8 a0 = int32x8_load(&x[i]);
662 int32x8 a1 = int32x8_load(&x[i + 8]);
663 int32x8 a2 = int32x8_load(&x[i + 16]);
664 int32x8 a3 = int32x8_load(&x[i + 24]);
665 int32x8 a4 = int32x8_load(&x[i + 32]);
666 int32x8 a5 = int32x8_load(&x[i + 40]);
667 int32x8 a6 = int32x8_load(&x[i + 48]);
668 int32x8 a7 = int32x8_load(&x[i + 56]);
669
670 int32x8 b0 = _mm256_unpacklo_epi32(a0, a1); /* AB0AB1AB4AB5 */
671 int32x8 b1 = _mm256_unpackhi_epi32(a0, a1); /* AB2AB3AB6AB7 */
672 int32x8 b2 = _mm256_unpacklo_epi32(a2, a3); /* CD0CD1CD4CD5 */
673 int32x8 b3 = _mm256_unpackhi_epi32(a2, a3); /* CD2CD3CD6CD7 */
674 int32x8 b4 = _mm256_unpacklo_epi32(a4, a5); /* EF0EF1EF4EF5 */
675 int32x8 b5 = _mm256_unpackhi_epi32(a4, a5); /* EF2EF3EF6EF7 */
676 int32x8 b6 = _mm256_unpacklo_epi32(a6, a7); /* GH0GH1GH4GH5 */
677 int32x8 b7 = _mm256_unpackhi_epi32(a6, a7); /* GH2GH3GH6GH7 */
678
679 int32x8 c0 = _mm256_unpacklo_epi64(b0, b2); /* ABCD0ABCD4 */
680 int32x8 c1 = _mm256_unpacklo_epi64(b1, b3); /* ABCD2ABCD6 */
681 int32x8 c2 = _mm256_unpackhi_epi64(b0, b2); /* ABCD1ABCD5 */
682 int32x8 c3 = _mm256_unpackhi_epi64(b1, b3); /* ABCD3ABCD7 */
683 int32x8 c4 = _mm256_unpacklo_epi64(b4, b6); /* EFGH0EFGH4 */
684 int32x8 c5 = _mm256_unpacklo_epi64(b5, b7); /* EFGH2EFGH6 */
685 int32x8 c6 = _mm256_unpackhi_epi64(b4, b6); /* EFGH1EFGH5 */
686 int32x8 c7 = _mm256_unpackhi_epi64(b5, b7); /* EFGH3EFGH7 */
687
688 if (flagdown) {
689 c2 ^= mask;
690 c3 ^= mask;
691 c6 ^= mask;
692 c7 ^= mask;
693 } else {
694 c0 ^= mask;
695 c1 ^= mask;
696 c4 ^= mask;
697 c5 ^= mask;
698 }
699
700 int32x8 d0 = _mm256_permute2x128_si256(c0, c4, 0x20); /* ABCDEFGH0 */
701 int32x8 d1 = _mm256_permute2x128_si256(c2, c6, 0x20); /* ABCDEFGH1 */
702 int32x8 d2 = _mm256_permute2x128_si256(c1, c5, 0x20); /* ABCDEFGH2 */
703 int32x8 d3 = _mm256_permute2x128_si256(c3, c7, 0x20); /* ABCDEFGH5 */
704 int32x8 d4 = _mm256_permute2x128_si256(c0, c4, 0x31); /* ABCDEFGH4 */
705 int32x8 d5 = _mm256_permute2x128_si256(c2, c6, 0x31); /* ABCDEFGH3 */
706 int32x8 d6 = _mm256_permute2x128_si256(c1, c5, 0x31); /* ABCDEFGH6 */
707 int32x8 d7 = _mm256_permute2x128_si256(c3, c7, 0x31); /* ABCDEFGH7 */
708
709 int32x8_MINMAX(d0, d1);
710 int32x8_MINMAX(d2, d3);
711 int32x8_MINMAX(d4, d5);
712 int32x8_MINMAX(d6, d7);
713 int32x8_MINMAX(d0, d2);
714 int32x8_MINMAX(d1, d3);
715 int32x8_MINMAX(d4, d6);
716 int32x8_MINMAX(d5, d7);
717 int32x8_MINMAX(d0, d4);
718 int32x8_MINMAX(d1, d5);
719 int32x8_MINMAX(d2, d6);
720 int32x8_MINMAX(d3, d7);
721
722 int32x8 e0 = _mm256_unpacklo_epi32(d0, d1);
723 int32x8 e1 = _mm256_unpackhi_epi32(d0, d1);
724 int32x8 e2 = _mm256_unpacklo_epi32(d2, d3);
725 int32x8 e3 = _mm256_unpackhi_epi32(d2, d3);
726 int32x8 e4 = _mm256_unpacklo_epi32(d4, d5);
727 int32x8 e5 = _mm256_unpackhi_epi32(d4, d5);
728 int32x8 e6 = _mm256_unpacklo_epi32(d6, d7);
729 int32x8 e7 = _mm256_unpackhi_epi32(d6, d7);
730
731 int32x8 f0 = _mm256_unpacklo_epi64(e0, e2);
732 int32x8 f1 = _mm256_unpacklo_epi64(e1, e3);
733 int32x8 f2 = _mm256_unpackhi_epi64(e0, e2);
734 int32x8 f3 = _mm256_unpackhi_epi64(e1, e3);
735 int32x8 f4 = _mm256_unpacklo_epi64(e4, e6);
736 int32x8 f5 = _mm256_unpacklo_epi64(e5, e7);
737 int32x8 f6 = _mm256_unpackhi_epi64(e4, e6);
738 int32x8 f7 = _mm256_unpackhi_epi64(e5, e7);
739
740 int32x8 g0 = _mm256_permute2x128_si256(f0, f4, 0x20);
741 int32x8 g1 = _mm256_permute2x128_si256(f2, f6, 0x20);
742 int32x8 g2 = _mm256_permute2x128_si256(f1, f5, 0x20);
743 int32x8 g3 = _mm256_permute2x128_si256(f3, f7, 0x20);
744 int32x8 g4 = _mm256_permute2x128_si256(f0, f4, 0x31);
745 int32x8 g5 = _mm256_permute2x128_si256(f2, f6, 0x31);
746 int32x8 g6 = _mm256_permute2x128_si256(f1, f5, 0x31);
747 int32x8 g7 = _mm256_permute2x128_si256(f3, f7, 0x31);
748
749 int32x8_store(&x[i], g0);
750 int32x8_store(&x[i + 8], g1);
751 int32x8_store(&x[i + 16], g2);
752 int32x8_store(&x[i + 24], g3);
753 int32x8_store(&x[i + 32], g4);
754 int32x8_store(&x[i + 40], g5);
755 int32x8_store(&x[i + 48], g6);
756 int32x8_store(&x[i + 56], g7);
757 }
758
759 q = n >> 4;
760 while (q >= 128 || q == 32) {
761 q >>= 2;
762 for (j = 0; j < n; j += 8 * q) {
763 for (i = j; i < j + q; i += 8) {
764 int32x8 x0 = int32x8_load(&x[i]);
765 int32x8 x1 = int32x8_load(&x[i + q]);
766 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
767 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
768 int32x8 x4 = int32x8_load(&x[i + 4 * q]);
769 int32x8 x5 = int32x8_load(&x[i + 5 * q]);
770 int32x8 x6 = int32x8_load(&x[i + 6 * q]);
771 int32x8 x7 = int32x8_load(&x[i + 7 * q]);
772 int32x8_MINMAX(x0, x4);
773 int32x8_MINMAX(x1, x5);
774 int32x8_MINMAX(x2, x6);
775 int32x8_MINMAX(x3, x7);
776 int32x8_MINMAX(x0, x2);
777 int32x8_MINMAX(x1, x3);
778 int32x8_MINMAX(x4, x6);
779 int32x8_MINMAX(x5, x7);
780 int32x8_MINMAX(x0, x1);
781 int32x8_MINMAX(x2, x3);
782 int32x8_MINMAX(x4, x5);
783 int32x8_MINMAX(x6, x7);
784 int32x8_store(&x[i], x0);
785 int32x8_store(&x[i + q], x1);
786 int32x8_store(&x[i + 2 * q], x2);
787 int32x8_store(&x[i + 3 * q], x3);
788 int32x8_store(&x[i + 4 * q], x4);
789 int32x8_store(&x[i + 5 * q], x5);
790 int32x8_store(&x[i + 6 * q], x6);
791 int32x8_store(&x[i + 7 * q], x7);
792 }
793 }
794 q >>= 1;
795 }
796 while (q >= 16) {
797 q >>= 1;
798 for (j = 0; j < n; j += 4 * q) {
799 for (i = j; i < j + q; i += 8) {
800 int32x8 x0 = int32x8_load(&x[i]);
801 int32x8 x1 = int32x8_load(&x[i + q]);
802 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
803 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
804 int32x8_MINMAX(x0, x2);
805 int32x8_MINMAX(x1, x3);
806 int32x8_MINMAX(x0, x1);
807 int32x8_MINMAX(x2, x3);
808 int32x8_store(&x[i], x0);
809 int32x8_store(&x[i + q], x1);
810 int32x8_store(&x[i + 2 * q], x2);
811 int32x8_store(&x[i + 3 * q], x3);
812 }
813 }
814 q >>= 1;
815 }
816 if (q == 8) {
817 for (j = 0; j < n; j += q + q) {
818 int32x8 x0 = int32x8_load(&x[j]);
819 int32x8 x1 = int32x8_load(&x[j + q]);
820 int32x8_MINMAX(x0, x1);
821 int32x8_store(&x[j], x0);
822 int32x8_store(&x[j + q], x1);
823 }
824 }
825
826 q = n >> 3;
827 for (i = 0; i < q; i += 8) {
828 int32x8 x0 = int32x8_load(&x[i]);
829 int32x8 x1 = int32x8_load(&x[i + q]);
830 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
831 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
832 int32x8 x4 = int32x8_load(&x[i + 4 * q]);
833 int32x8 x5 = int32x8_load(&x[i + 5 * q]);
834 int32x8 x6 = int32x8_load(&x[i + 6 * q]);
835 int32x8 x7 = int32x8_load(&x[i + 7 * q]);
836
837 int32x8_MINMAX(x0, x1);
838 int32x8_MINMAX(x2, x3);
839 int32x8_MINMAX(x4, x5);
840 int32x8_MINMAX(x6, x7);
841 int32x8_MINMAX(x0, x2);
842 int32x8_MINMAX(x1, x3);
843 int32x8_MINMAX(x4, x6);
844 int32x8_MINMAX(x5, x7);
845 int32x8_MINMAX(x0, x4);
846 int32x8_MINMAX(x1, x5);
847 int32x8_MINMAX(x2, x6);
848 int32x8_MINMAX(x3, x7);
849
850 int32x8 b0 = _mm256_unpacklo_epi32(x0, x4); /* AE0AE1AE4AE5 */
851 int32x8 b1 = _mm256_unpackhi_epi32(x0, x4); /* AE2AE3AE6AE7 */
852 int32x8 b2 = _mm256_unpacklo_epi32(x1, x5); /* BF0BF1BF4BF5 */
853 int32x8 b3 = _mm256_unpackhi_epi32(x1, x5); /* BF2BF3BF6BF7 */
854 int32x8 b4 = _mm256_unpacklo_epi32(x2, x6); /* CG0CG1CG4CG5 */
855 int32x8 b5 = _mm256_unpackhi_epi32(x2, x6); /* CG2CG3CG6CG7 */
856 int32x8 b6 = _mm256_unpacklo_epi32(x3, x7); /* DH0DH1DH4DH5 */
857 int32x8 b7 = _mm256_unpackhi_epi32(x3, x7); /* DH2DH3DH6DH7 */
858
859 int32x8 c0 = _mm256_unpacklo_epi64(b0, b4); /* AECG0AECG4 */
860 int32x8 c1 = _mm256_unpacklo_epi64(b1, b5); /* AECG2AECG6 */
861 int32x8 c2 = _mm256_unpackhi_epi64(b0, b4); /* AECG1AECG5 */
862 int32x8 c3 = _mm256_unpackhi_epi64(b1, b5); /* AECG3AECG7 */
863 int32x8 c4 = _mm256_unpacklo_epi64(b2, b6); /* BFDH0BFDH4 */
864 int32x8 c5 = _mm256_unpacklo_epi64(b3, b7); /* BFDH2BFDH6 */
865 int32x8 c6 = _mm256_unpackhi_epi64(b2, b6); /* BFDH1BFDH5 */
866 int32x8 c7 = _mm256_unpackhi_epi64(b3, b7); /* BFDH3BFDH7 */
867
868 int32x8 d0 = _mm256_permute2x128_si256(c0, c4, 0x20); /* AECGBFDH0 */
869 int32x8 d1 = _mm256_permute2x128_si256(c1, c5, 0x20); /* AECGBFDH2 */
870 int32x8 d2 = _mm256_permute2x128_si256(c2, c6, 0x20); /* AECGBFDH1 */
871 int32x8 d3 = _mm256_permute2x128_si256(c3, c7, 0x20); /* AECGBFDH3 */
872 int32x8 d4 = _mm256_permute2x128_si256(c0, c4, 0x31); /* AECGBFDH4 */
873 int32x8 d5 = _mm256_permute2x128_si256(c1, c5, 0x31); /* AECGBFDH6 */
874 int32x8 d6 = _mm256_permute2x128_si256(c2, c6, 0x31); /* AECGBFDH5 */
875 int32x8 d7 = _mm256_permute2x128_si256(c3, c7, 0x31); /* AECGBFDH7 */
876
877 if (flagdown) {
878 d0 ^= mask;
879 d1 ^= mask;
880 d2 ^= mask;
881 d3 ^= mask;
882 d4 ^= mask;
883 d5 ^= mask;
884 d6 ^= mask;
885 d7 ^= mask;
886 }
887
888 int32x8_store(&x[i], d0);
889 int32x8_store(&x[i + q], d4);
890 int32x8_store(&x[i + 2 * q], d1);
891 int32x8_store(&x[i + 3 * q], d5);
892 int32x8_store(&x[i + 4 * q], d2);
893 int32x8_store(&x[i + 5 * q], d6);
894 int32x8_store(&x[i + 6 * q], d3);
895 int32x8_store(&x[i + 7 * q], d7);
896 }
897 }
898
PQCLEAN_MCELIECE460896F_AVX_int32_sort(int32 * x,size_t n)899 void PQCLEAN_MCELIECE460896F_AVX_int32_sort(int32 *x, size_t n) {
900 size_t q, i, j;
901
902 if (n <= 8) {
903 if (n == 8) {
904 int32_MINMAX(&x[0], &x[1]);
905 int32_MINMAX(&x[1], &x[2]);
906 int32_MINMAX(&x[2], &x[3]);
907 int32_MINMAX(&x[3], &x[4]);
908 int32_MINMAX(&x[4], &x[5]);
909 int32_MINMAX(&x[5], &x[6]);
910 int32_MINMAX(&x[6], &x[7]);
911 }
912 if (n >= 7) {
913 int32_MINMAX(&x[0], &x[1]);
914 int32_MINMAX(&x[1], &x[2]);
915 int32_MINMAX(&x[2], &x[3]);
916 int32_MINMAX(&x[3], &x[4]);
917 int32_MINMAX(&x[4], &x[5]);
918 int32_MINMAX(&x[5], &x[6]);
919 }
920 if (n >= 6) {
921 int32_MINMAX(&x[0], &x[1]);
922 int32_MINMAX(&x[1], &x[2]);
923 int32_MINMAX(&x[2], &x[3]);
924 int32_MINMAX(&x[3], &x[4]);
925 int32_MINMAX(&x[4], &x[5]);
926 }
927 if (n >= 5) {
928 int32_MINMAX(&x[0], &x[1]);
929 int32_MINMAX(&x[1], &x[2]);
930 int32_MINMAX(&x[2], &x[3]);
931 int32_MINMAX(&x[3], &x[4]);
932 }
933 if (n >= 4) {
934 int32_MINMAX(&x[0], &x[1]);
935 int32_MINMAX(&x[1], &x[2]);
936 int32_MINMAX(&x[2], &x[3]);
937 }
938 if (n >= 3) {
939 int32_MINMAX(&x[0], &x[1]);
940 int32_MINMAX(&x[1], &x[2]);
941 }
942 if (n >= 2) {
943 int32_MINMAX(&x[0], &x[1]);
944 }
945 return;
946 }
947
948 if (!(n & (n - 1))) {
949 int32_sort_2power(x, n, 0);
950 return;
951 }
952
953 q = 8;
954 while (q < n - q) {
955 q += q;
956 }
957 /* n > q >= 8 */
958
959 if (q <= 128) { /* n <= 256 */
960 int32x8 y[32];
961 for (i = q >> 3; i < q >> 2; ++i) {
962 y[i] = _mm256_set1_epi32(0x7fffffff);
963 }
964 for (i = 0; i < n; ++i) {
965 ((int32 *)y)[i] = x[i];
966 }
967 int32_sort_2power((int32 *) y, 2 * q, 0);
968 for (i = 0; i < n; ++i) {
969 x[i] = ((int32 *) y)[i];
970 }
971 return;
972 }
973
974 int32_sort_2power(x, q, 1);
975 PQCLEAN_MCELIECE460896F_AVX_int32_sort(x + q, n - q);
976
977 while (q >= 64) {
978 q >>= 2;
979 j = int32_threestages(x, n, q);
980 minmax_vector(x + j, x + j + 4 * q, n - 4 * q - j);
981 if (j + 4 * q <= n) {
982 for (i = j; i < j + q; i += 8) {
983 int32x8 x0 = int32x8_load(&x[i]);
984 int32x8 x1 = int32x8_load(&x[i + q]);
985 int32x8 x2 = int32x8_load(&x[i + 2 * q]);
986 int32x8 x3 = int32x8_load(&x[i + 3 * q]);
987 int32x8_MINMAX(x0, x2);
988 int32x8_MINMAX(x1, x3);
989 int32x8_MINMAX(x0, x1);
990 int32x8_MINMAX(x2, x3);
991 int32x8_store(&x[i], x0);
992 int32x8_store(&x[i + q], x1);
993 int32x8_store(&x[i + 2 * q], x2);
994 int32x8_store(&x[i + 3 * q], x3);
995 }
996 j += 4 * q;
997 }
998 minmax_vector(x + j, x + j + 2 * q, n - 2 * q - j);
999 if (j + 2 * q <= n) {
1000 for (i = j; i < j + q; i += 8) {
1001 int32x8 x0 = int32x8_load(&x[i]);
1002 int32x8 x1 = int32x8_load(&x[i + q]);
1003 int32x8_MINMAX(x0, x1);
1004 int32x8_store(&x[i], x0);
1005 int32x8_store(&x[i + q], x1);
1006 }
1007 j += 2 * q;
1008 }
1009 minmax_vector(x + j, x + j + q, n - q - j);
1010 q >>= 1;
1011 }
1012 if (q == 32) {
1013 j = 0;
1014 for (; j + 64 <= n; j += 64) {
1015 int32x8 x0 = int32x8_load(&x[j]);
1016 int32x8 x1 = int32x8_load(&x[j + 8]);
1017 int32x8 x2 = int32x8_load(&x[j + 16]);
1018 int32x8 x3 = int32x8_load(&x[j + 24]);
1019 int32x8 x4 = int32x8_load(&x[j + 32]);
1020 int32x8 x5 = int32x8_load(&x[j + 40]);
1021 int32x8 x6 = int32x8_load(&x[j + 48]);
1022 int32x8 x7 = int32x8_load(&x[j + 56]);
1023 int32x8_MINMAX(x0, x4);
1024 int32x8_MINMAX(x1, x5);
1025 int32x8_MINMAX(x2, x6);
1026 int32x8_MINMAX(x3, x7);
1027 int32x8_MINMAX(x0, x2);
1028 int32x8_MINMAX(x1, x3);
1029 int32x8_MINMAX(x4, x6);
1030 int32x8_MINMAX(x5, x7);
1031 int32x8_MINMAX(x0, x1);
1032 int32x8_MINMAX(x2, x3);
1033 int32x8_MINMAX(x4, x5);
1034 int32x8_MINMAX(x6, x7);
1035 int32x8 a0 = _mm256_permute2x128_si256(x0, x1, 0x20);
1036 int32x8 a1 = _mm256_permute2x128_si256(x0, x1, 0x31);
1037 int32x8 a2 = _mm256_permute2x128_si256(x2, x3, 0x20);
1038 int32x8 a3 = _mm256_permute2x128_si256(x2, x3, 0x31);
1039 int32x8 a4 = _mm256_permute2x128_si256(x4, x5, 0x20);
1040 int32x8 a5 = _mm256_permute2x128_si256(x4, x5, 0x31);
1041 int32x8 a6 = _mm256_permute2x128_si256(x6, x7, 0x20);
1042 int32x8 a7 = _mm256_permute2x128_si256(x6, x7, 0x31);
1043 int32x8_MINMAX(a0, a1);
1044 int32x8_MINMAX(a2, a3);
1045 int32x8_MINMAX(a4, a5);
1046 int32x8_MINMAX(a6, a7);
1047 int32x8 b0 = _mm256_permute2x128_si256(a0, a1, 0x20);
1048 int32x8 b1 = _mm256_permute2x128_si256(a0, a1, 0x31);
1049 int32x8 b2 = _mm256_permute2x128_si256(a2, a3, 0x20);
1050 int32x8 b3 = _mm256_permute2x128_si256(a2, a3, 0x31);
1051 int32x8 b4 = _mm256_permute2x128_si256(a4, a5, 0x20);
1052 int32x8 b5 = _mm256_permute2x128_si256(a4, a5, 0x31);
1053 int32x8 b6 = _mm256_permute2x128_si256(a6, a7, 0x20);
1054 int32x8 b7 = _mm256_permute2x128_si256(a6, a7, 0x31);
1055 int32x8 c0 = _mm256_unpacklo_epi64(b0, b1);
1056 int32x8 c1 = _mm256_unpackhi_epi64(b0, b1);
1057 int32x8 c2 = _mm256_unpacklo_epi64(b2, b3);
1058 int32x8 c3 = _mm256_unpackhi_epi64(b2, b3);
1059 int32x8 c4 = _mm256_unpacklo_epi64(b4, b5);
1060 int32x8 c5 = _mm256_unpackhi_epi64(b4, b5);
1061 int32x8 c6 = _mm256_unpacklo_epi64(b6, b7);
1062 int32x8 c7 = _mm256_unpackhi_epi64(b6, b7);
1063 int32x8_MINMAX(c0, c1);
1064 int32x8_MINMAX(c2, c3);
1065 int32x8_MINMAX(c4, c5);
1066 int32x8_MINMAX(c6, c7);
1067 int32x8 d0 = _mm256_unpacklo_epi32(c0, c1);
1068 int32x8 d1 = _mm256_unpackhi_epi32(c0, c1);
1069 int32x8 d2 = _mm256_unpacklo_epi32(c2, c3);
1070 int32x8 d3 = _mm256_unpackhi_epi32(c2, c3);
1071 int32x8 d4 = _mm256_unpacklo_epi32(c4, c5);
1072 int32x8 d5 = _mm256_unpackhi_epi32(c4, c5);
1073 int32x8 d6 = _mm256_unpacklo_epi32(c6, c7);
1074 int32x8 d7 = _mm256_unpackhi_epi32(c6, c7);
1075 int32x8 e0 = _mm256_unpacklo_epi64(d0, d1);
1076 int32x8 e1 = _mm256_unpackhi_epi64(d0, d1);
1077 int32x8 e2 = _mm256_unpacklo_epi64(d2, d3);
1078 int32x8 e3 = _mm256_unpackhi_epi64(d2, d3);
1079 int32x8 e4 = _mm256_unpacklo_epi64(d4, d5);
1080 int32x8 e5 = _mm256_unpackhi_epi64(d4, d5);
1081 int32x8 e6 = _mm256_unpacklo_epi64(d6, d7);
1082 int32x8 e7 = _mm256_unpackhi_epi64(d6, d7);
1083 int32x8_MINMAX(e0, e1);
1084 int32x8_MINMAX(e2, e3);
1085 int32x8_MINMAX(e4, e5);
1086 int32x8_MINMAX(e6, e7);
1087 int32x8 f0 = _mm256_unpacklo_epi32(e0, e1);
1088 int32x8 f1 = _mm256_unpackhi_epi32(e0, e1);
1089 int32x8 f2 = _mm256_unpacklo_epi32(e2, e3);
1090 int32x8 f3 = _mm256_unpackhi_epi32(e2, e3);
1091 int32x8 f4 = _mm256_unpacklo_epi32(e4, e5);
1092 int32x8 f5 = _mm256_unpackhi_epi32(e4, e5);
1093 int32x8 f6 = _mm256_unpacklo_epi32(e6, e7);
1094 int32x8 f7 = _mm256_unpackhi_epi32(e6, e7);
1095 int32x8_store(&x[j], f0);
1096 int32x8_store(&x[j + 8], f1);
1097 int32x8_store(&x[j + 16], f2);
1098 int32x8_store(&x[j + 24], f3);
1099 int32x8_store(&x[j + 32], f4);
1100 int32x8_store(&x[j + 40], f5);
1101 int32x8_store(&x[j + 48], f6);
1102 int32x8_store(&x[j + 56], f7);
1103 }
1104 minmax_vector(x + j, x + j + 32, n - 32 - j);
1105 goto continue16;
1106 }
1107 if (q == 16) {
1108 j = 0;
1109 continue16:
1110 for (; j + 32 <= n; j += 32) {
1111 int32x8 x0 = int32x8_load(&x[j]);
1112 int32x8 x1 = int32x8_load(&x[j + 8]);
1113 int32x8 x2 = int32x8_load(&x[j + 16]);
1114 int32x8 x3 = int32x8_load(&x[j + 24]);
1115 int32x8_MINMAX(x0, x2);
1116 int32x8_MINMAX(x1, x3);
1117 int32x8_MINMAX(x0, x1);
1118 int32x8_MINMAX(x2, x3);
1119 int32x8 a0 = _mm256_permute2x128_si256(x0, x1, 0x20);
1120 int32x8 a1 = _mm256_permute2x128_si256(x0, x1, 0x31);
1121 int32x8 a2 = _mm256_permute2x128_si256(x2, x3, 0x20);
1122 int32x8 a3 = _mm256_permute2x128_si256(x2, x3, 0x31);
1123 int32x8_MINMAX(a0, a1);
1124 int32x8_MINMAX(a2, a3);
1125 int32x8 b0 = _mm256_permute2x128_si256(a0, a1, 0x20);
1126 int32x8 b1 = _mm256_permute2x128_si256(a0, a1, 0x31);
1127 int32x8 b2 = _mm256_permute2x128_si256(a2, a3, 0x20);
1128 int32x8 b3 = _mm256_permute2x128_si256(a2, a3, 0x31);
1129 int32x8 c0 = _mm256_unpacklo_epi64(b0, b1);
1130 int32x8 c1 = _mm256_unpackhi_epi64(b0, b1);
1131 int32x8 c2 = _mm256_unpacklo_epi64(b2, b3);
1132 int32x8 c3 = _mm256_unpackhi_epi64(b2, b3);
1133 int32x8_MINMAX(c0, c1);
1134 int32x8_MINMAX(c2, c3);
1135 int32x8 d0 = _mm256_unpacklo_epi32(c0, c1);
1136 int32x8 d1 = _mm256_unpackhi_epi32(c0, c1);
1137 int32x8 d2 = _mm256_unpacklo_epi32(c2, c3);
1138 int32x8 d3 = _mm256_unpackhi_epi32(c2, c3);
1139 int32x8 e0 = _mm256_unpacklo_epi64(d0, d1);
1140 int32x8 e1 = _mm256_unpackhi_epi64(d0, d1);
1141 int32x8 e2 = _mm256_unpacklo_epi64(d2, d3);
1142 int32x8 e3 = _mm256_unpackhi_epi64(d2, d3);
1143 int32x8_MINMAX(e0, e1);
1144 int32x8_MINMAX(e2, e3);
1145 int32x8 f0 = _mm256_unpacklo_epi32(e0, e1);
1146 int32x8 f1 = _mm256_unpackhi_epi32(e0, e1);
1147 int32x8 f2 = _mm256_unpacklo_epi32(e2, e3);
1148 int32x8 f3 = _mm256_unpackhi_epi32(e2, e3);
1149 int32x8_store(&x[j], f0);
1150 int32x8_store(&x[j + 8], f1);
1151 int32x8_store(&x[j + 16], f2);
1152 int32x8_store(&x[j + 24], f3);
1153 }
1154 minmax_vector(x + j, x + j + 16, n - 16 - j);
1155 goto continue8;
1156 }
1157 /* q == 8 */
1158 j = 0;
1159 continue8:
1160 for (; j + 16 <= n; j += 16) {
1161 int32x8 x0 = int32x8_load(&x[j]);
1162 int32x8 x1 = int32x8_load(&x[j + 8]);
1163 int32x8_MINMAX(x0, x1);
1164 int32x8_store(&x[j], x0);
1165 int32x8_store(&x[j + 8], x1);
1166 int32x8 a0 = _mm256_permute2x128_si256(x0, x1, 0x20); /* x0123y0123 */
1167 int32x8 a1 = _mm256_permute2x128_si256(x0, x1, 0x31); /* x4567y4567 */
1168 int32x8_MINMAX(a0, a1);
1169 int32x8 b0 = _mm256_permute2x128_si256(a0, a1, 0x20); /* x01234567 */
1170 int32x8 b1 = _mm256_permute2x128_si256(a0, a1, 0x31); /* y01234567 */
1171 int32x8 c0 = _mm256_unpacklo_epi64(b0, b1); /* x01y01x45y45 */
1172 int32x8 c1 = _mm256_unpackhi_epi64(b0, b1); /* x23y23x67y67 */
1173 int32x8_MINMAX(c0, c1);
1174 int32x8 d0 = _mm256_unpacklo_epi32(c0, c1); /* x02x13x46x57 */
1175 int32x8 d1 = _mm256_unpackhi_epi32(c0, c1); /* y02y13y46y57 */
1176 int32x8 e0 = _mm256_unpacklo_epi64(d0, d1); /* x02y02x46y46 */
1177 int32x8 e1 = _mm256_unpackhi_epi64(d0, d1); /* x13y13x57y57 */
1178 int32x8_MINMAX(e0, e1);
1179 int32x8 f0 = _mm256_unpacklo_epi32(e0, e1); /* x01234567 */
1180 int32x8 f1 = _mm256_unpackhi_epi32(e0, e1); /* y01234567 */
1181 int32x8_store(&x[j], f0);
1182 int32x8_store(&x[j + 8], f1);
1183 }
1184 minmax_vector(x + j, x + j + 8, n - 8 - j);
1185 if (j + 8 <= n) {
1186 int32_MINMAX(&x[j], &x[j + 4]);
1187 int32_MINMAX(&x[j + 1], &x[j + 5]);
1188 int32_MINMAX(&x[j + 2], &x[j + 6]);
1189 int32_MINMAX(&x[j + 3], &x[j + 7]);
1190 int32_MINMAX(&x[j], &x[j + 2]);
1191 int32_MINMAX(&x[j + 1], &x[j + 3]);
1192 int32_MINMAX(&x[j], &x[j + 1]);
1193 int32_MINMAX(&x[j + 2], &x[j + 3]);
1194 int32_MINMAX(&x[j + 4], &x[j + 6]);
1195 int32_MINMAX(&x[j + 5], &x[j + 7]);
1196 int32_MINMAX(&x[j + 4], &x[j + 5]);
1197 int32_MINMAX(&x[j + 6], &x[j + 7]);
1198 j += 8;
1199 }
1200 minmax_vector(x + j, x + j + 4, n - 4 - j);
1201 if (j + 4 <= n) {
1202 int32_MINMAX(&x[j], &x[j + 2]);
1203 int32_MINMAX(&x[j + 1], &x[j + 3]);
1204 int32_MINMAX(&x[j], &x[j + 1]);
1205 int32_MINMAX(&x[j + 2], &x[j + 3]);
1206 j += 4;
1207 }
1208 if (j + 3 <= n) {
1209 int32_MINMAX(&x[j], &x[j + 2]);
1210 }
1211 if (j + 2 <= n) {
1212 int32_MINMAX(&x[j], &x[j + 1]);
1213 }
1214 }
1215