Let us walk on the 3-isogeny graph
Loading...
Searching...
No Matches
int32_sort.c File Reference
#include "int32_sort.h"
#include <immintrin.h>
#include "int32_minmax_x86.c"
Include dependency graph for int32_sort.c:

Go to the source code of this file.

Macros

#define int32   int32_t
#define int32x8_load(z)
#define int32x8_store(z, i)
#define int32x8_min   _mm256_min_epi32
#define int32x8_max   _mm256_max_epi32
#define int32x8_MINMAX(a, b)

Typedefs

typedef __m256i int32x8

Functions

 __attribute__ ((noinline))
void int32_sort (int32 *x, long long n)

Macro Definition Documentation

◆ int32

#define int32   int32_t

Definition at line 2 of file int32_sort.c.

Referenced by __attribute__(), and int32_sort().

◆ int32x8_load

#define int32x8_load ( z)
Value:
_mm256_loadu_si256((__m256i *) (z))

Definition at line 8 of file int32_sort.c.

Referenced by __attribute__(), and int32_sort().

◆ int32x8_max

#define int32x8_max   _mm256_max_epi32

Definition at line 11 of file int32_sort.c.

◆ int32x8_min

#define int32x8_min   _mm256_min_epi32

Definition at line 10 of file int32_sort.c.

◆ int32x8_MINMAX

#define int32x8_MINMAX ( a,
b )
Value:
do { \
int32x8 c = int32x8_min(a,b); \
b = int32x8_max(a,b); \
a = c; \
} while(0)
int32x8
__m256i int32x8
Definition int32_sort.c:7
int32x8_max
#define int32x8_max
Definition int32_sort.c:11
int32x8_min
#define int32x8_min
Definition int32_sort.c:10
a
f a
Definition to_model.m:12

Definition at line 13 of file int32_sort.c.

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)

Referenced by __attribute__(), and int32_sort().

◆ int32x8_store

#define int32x8_store ( z,
i )
Value:
_mm256_storeu_si256((__m256i *) (z),(i))
i
for i
Definition prime_search.m:10

Definition at line 9 of file int32_sort.c.

Referenced by __attribute__(), and int32_sort().

Typedef Documentation

◆ int32x8

typedef __m256i int32x8

Definition at line 7 of file int32_sort.c.

Function Documentation

◆ __attribute__()

__attribute__ ( (noinline) )

Definition at line 20 of file int32_sort.c.

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}
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_store
#define int32x8_store(z, i)
Definition int32_sort.c:9
analyze_bench.x
dict x
Definition analyze_bench.py:83

References int32, int32_MINMAX, int32x8_load, int32x8_MINMAX, and int32x8_store.

◆ int32_sort()

void int32_sort ( int32 * x,
long long n )

Definition at line 879 of file int32_sort.c.

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}
int32
#define int32
Definition int32_sort.c:2
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
j
for j
Definition prime_search.m:12
a1
g a1
Definition to_model.m:15

References a1, a3, b4, c4, c6(), i, int32, int32_MINMAX, int32_sort, int32x8_load, int32x8_MINMAX, int32x8_store, and j.

Here is the call graph for this function: