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