diff options
Diffstat (limited to 'benchmarks')
| -rw-r--r-- | benchmarks/Makefile | 1 | ||||
| -rw-r--r-- | benchmarks/common/syscalls.c | 3 | ||||
| -rw-r--r-- | benchmarks/common/util.h | 2 | ||||
| -rw-r--r-- | benchmarks/rsort/bmark.mk | 30 | ||||
| -rw-r--r-- | benchmarks/rsort/dataset1.h | 217 | ||||
| -rw-r--r-- | benchmarks/rsort/rsort.c | 123 |
6 files changed, 374 insertions, 2 deletions
diff --git a/benchmarks/Makefile b/benchmarks/Makefile index 8f580a4..175cf99 100644 --- a/benchmarks/Makefile +++ b/benchmarks/Makefile @@ -18,6 +18,7 @@ instbasedir = $(UCB_VLSI_HOME)/install bmarks = \ median \ qsort \ + rsort \ towers \ vvadd \ multiply \ diff --git a/benchmarks/common/syscalls.c b/benchmarks/common/syscalls.c index fbbb880..a168ebf 100644 --- a/benchmarks/common/syscalls.c +++ b/benchmarks/common/syscalls.c @@ -4,10 +4,9 @@ #include <stdio.h> #include <limits.h> #include <machine/syscall.h> -#include "encoding.h" +#include "util.h" #define SYS_stats 1234 -#define static_assert(cond) switch(0) { case 0: case !!(long)(cond): ; } static long handle_frontend_syscall(long which, long arg0, long arg1, long arg2) { diff --git a/benchmarks/common/util.h b/benchmarks/common/util.h index ea06530..7c2a048 100644 --- a/benchmarks/common/util.h +++ b/benchmarks/common/util.h @@ -31,6 +31,8 @@ static void setStats(int enable) {} extern void setStats(int enable); #endif +#define static_assert(cond) switch(0) { case 0: case !!(long)(cond): ; } + static void printArray(const char name[], int n, const int arr[]) { #if HOST_DEBUG diff --git a/benchmarks/rsort/bmark.mk b/benchmarks/rsort/bmark.mk new file mode 100644 index 0000000..0fa713c --- /dev/null +++ b/benchmarks/rsort/bmark.mk @@ -0,0 +1,30 @@ +#======================================================================= +# UCB CS250 Makefile fragment for benchmarks +#----------------------------------------------------------------------- +# +# Each benchmark directory should have its own fragment which +# essentially lists what the source files are and how to link them +# into an riscv and/or host executable. All variables should include +# the benchmark name as a prefix so that they are unique. +# + +rsort_c_src = \ + rsort.c \ + syscalls.c \ + +rsort_riscv_src = \ + crt.S \ + +rsort_c_objs = $(patsubst %.c, %.o, $(rsort_c_src)) +rsort_riscv_objs = $(patsubst %.S, %.o, $(rsort_riscv_src)) + +rsort_host_bin = rsort.host +$(rsort_host_bin) : $(rsort_c_src) + $(HOST_COMP) $^ -o $(rsort_host_bin) + +rsort_riscv_bin = rsort.riscv +$(rsort_riscv_bin) : $(rsort_c_objs) $(rsort_riscv_objs) + $(RISCV_LINK) $(rsort_c_objs) $(rsort_riscv_objs) -o $(rsort_riscv_bin) $(RISCV_LINK_OPTS) + +junk += $(rsort_c_objs) $(rsort_riscv_objs) \ + $(rsort_host_bin) $(rsort_riscv_bin) diff --git a/benchmarks/rsort/dataset1.h b/benchmarks/rsort/dataset1.h new file mode 100644 index 0000000..25e8231 --- /dev/null +++ b/benchmarks/rsort/dataset1.h @@ -0,0 +1,217 @@ + +#define DATA_SIZE 2048 + +type input_data[DATA_SIZE] = +{ + 89400484, 976015092, 1792756324, 721524505, 1214379246, 3794415, 402845420, 2126940990, 1611680320, 786566648, 754215794, 1231249235, 284658041, 137796456, 2041942843, 329767814, 1255524953, 465119445, 1731949250, 301663421, + 1335861008, 452888789, 14125900, 1231149357, 2002881120, 730845665, 1913581092, 1275331596, 843738737, 1931282005, 1492488573, 490920543, 2066865713, 25885333, 238278880, 1898582764, 250731366, 1612593993, 637659983, 1388759892, + 916073297, 1075762632, 675549432, 937987129, 1417415680, 1508705426, 1663890071, 1746476698, 686797873, 2109530615, 1459500136, 324215873, 1881253854, 1496277718, 810387144, 1212974417, 1020037994, 585169793, 2017191527, 556328195, + 1160036198, 1391095995, 1223583276, 1094283114, 436580096, 190215907, 603159718, 1513255537, 1631935240, 1440145706, 1303736105, 806638567, 1100041120, 1185825535, 1414141069, 2014090929, 419476096, 1273955724, 175753599, 1223475486, + 574236644, 2046759770, 492507266, 1721767511, 726141970, 1256152080, 2029909894, 1382429941, 1939683211, 791188057, 519699747, 1051184301, 1962689485, 706913763, 1776471922, 672906535, 2005817027, 1274190723, 2119425672, 835063788, + 421198539, 1169327477, 2064145552, 1396662140, 1218522465, 2105638337, 754247044, 2143968639, 1395289708, 1750443194, 1412540552, 170281493, 389233190, 448284065, 240618723, 2145930822, 1846605728, 1353999206, 140536987, 1821559709, + 619972089, 1514278798, 750919339, 2143343312, 304427548, 545066288, 1946004194, 1538069400, 1904770864, 924541465, 567779677, 893302687, 1239665569, 1157666831, 2105814934, 1505475223, 1636203720, 9736243, 518073650, 1063743848, + 1029176122, 215018112, 1073871430, 1858933377, 866478506, 1491477359, 477407584, 895562064, 954441852, 638167485, 1550159640, 614612685, 1453397990, 1334857284, 683536723, 168771888, 481561285, 755798022, 2016161810, 1162679490, + 619428858, 1390306889, 256860662, 365275089, 1322281086, 1134185180, 1302724177, 621921213, 837554186, 1711761015, 754896618, 1723143470, 978247260, 1548804416, 598016845, 1631405417, 790929190, 1602517354, 770957259, 198186681, + 1256015513, 2126029304, 135012885, 583112200, 2118203528, 1834388383, 866964848, 1695191950, 745183293, 1143511498, 1112731797, 478721193, 1202162389, 991159735, 1952364329, 519344323, 1667102296, 770412991, 548632788, 714042223, + 1674045273, 1471598258, 1286989824, 1590771096, 308832070, 959354209, 72802865, 670621648, 269167950, 1598436917, 2023498746, 1198213061, 2006856683, 1029832956, 1719009954, 1198254803, 1188748563, 1989240516, 927524181, 1711765426, + 1394929399, 769005536, 2047006719, 1915435344, 618681206, 1431814151, 42021322, 1106678970, 107160610, 1199317660, 185592115, 1870214195, 205008108, 1834318089, 948686793, 946311527, 1262399341, 131405125, 1321897861, 1459138745, + 821481684, 852388468, 603907009, 20643769, 1737931879, 37141933, 2088576982, 366700722, 1761289401, 625991894, 741078359, 817417567, 969305448, 1152416171, 1101933540, 399456957, 2074896270, 1971484382, 747592875, 1160333307, + 1738353358, 2113434968, 1896952705, 1908093581, 1155544307, 117766047, 2034767768, 1316120929, 1507433029, 2045407567, 765386206, 1031625002, 1220915309, 325667019, 1916602098, 16411608, 47463938, 1379995885, 1221108420, 721046824, + 1431492783, 1569479928, 909415369, 204514903, 933673987, 1565700239, 341674967, 602907378, 5309142, 849489374, 180599971, 1480437960, 532467027, 1958396887, 106223060, 1025117441, 935689637, 1752088215, 1704561346, 1568395337, + 1868289345, 569949159, 1045658065, 274746405, 890461390, 507848158, 793505636, 460893030, 1179525294, 388855203, 1113693824, 13887419, 1909681194, 1082499152, 1466632447, 1281443423, 612289854, 373305330, 568652142, 1383640563, + 1073695485, 745777837, 624939139, 1289308008, 1928550562, 148113917, 462743614, 1826880531, 1571598133, 1415390230, 1480273562, 1331593955, 540006359, 261556590, 1690167792, 283430575, 1194709162, 1781233744, 649754857, 1434046375, + 1135793759, 932423857, 1170759710, 1048943084, 692845661, 1620562432, 2036750157, 270410557, 617995659, 1347284277, 1771614266, 30992839, 655445946, 22762734, 1695617313, 867628573, 1577034674, 227870124, 2063408339, 1512163910, + 787913688, 1758748737, 1553547892, 2072440819, 632611704, 873623623, 2097057488, 1879635915, 1404727477, 1840896199, 1609955669, 186112992, 196401930, 130001148, 814302898, 1420810050, 226906236, 1435859758, 221330186, 329049266, + 820933470, 260792255, 1401058771, 210908782, 1774652096, 886978116, 1807085904, 508041515, 767233910, 26687179, 318750634, 910677024, 117260224, 2074840378, 301350822, 464795711, 2053899162, 1335298265, 737518341, 777433215, + 1147341731, 1981481446, 1628389501, 1537459540, 1121432739, 1392162662, 1800522575, 644293952, 1273223611, 1906345724, 28256901, 1467376771, 372465453, 78348530, 135678410, 1061864942, 260267972, 1184561748, 287497702, 1154842325, + 1629914848, 2084953915, 799717076, 1382484003, 2045821218, 933603111, 84924801, 892939912, 279252402, 651750790, 238566180, 942977997, 1822612008, 1849675857, 939497524, 436630343, 549253917, 1028937430, 579174666, 2124749673, + 880456526, 1451442832, 1350653461, 1546104436, 858045289, 2129513521, 1181191604, 727587915, 1619598456, 969076419, 1212628403, 1361078114, 368541415, 333906659, 41714278, 1390274260, 1563717683, 973769771, 1078197595, 918378387, + 1672192305, 1094531762, 92620223, 2125958841, 1620803320, 915948205, 174965839, 27377406, 435236973, 1038830638, 1834161399, 305750851, 330474090, 730422541, 1634445325, 840106059, 767880329, 109526756, 2027814180, 367923081, + 1983379601, 1293091635, 705851791, 226723092, 1067775613, 2082760612, 951663731, 260670135, 1111213862, 1891630185, 1379259015, 176024101, 594814862, 1870859970, 1689946986, 1290969161, 244975305, 1296857499, 1811088032, 1873900475, + 1949896838, 1907793490, 592006699, 1312471120, 509744705, 869853078, 70894786, 503368137, 1686479103, 1602967659, 1214950832, 1131661227, 768185796, 592234826, 1727583308, 949222447, 1760851607, 487888229, 1614780688, 1618378831, + 602368560, 2028116487, 183679578, 1561251584, 986240059, 1525451290, 977907387, 432609664, 1528031307, 116766659, 987761406, 1630293700, 90063199, 114202152, 543952312, 855107605, 812328969, 88823122, 1092881031, 304131252, + 1505022272, 894769708, 1849495275, 1607515830, 1032748996, 472872107, 1593359038, 1027760887, 1074205225, 1657001479, 1524491858, 387061281, 107095939, 1038018856, 798445606, 1486594282, 1878434988, 1558695709, 2033003588, 373226849, + 2133066804, 399991238, 1132597050, 1965358941, 1551661799, 3522194, 935939763, 2070467093, 500734709, 533101409, 1068798385, 998931662, 1500102591, 779093898, 66579049, 1121960111, 749415493, 502323961, 538932155, 259768753, + 753296935, 87897457, 539429964, 1675300017, 1232992084, 420106224, 1685350721, 346598567, 1610244183, 1597506096, 1079859867, 944382193, 1770497338, 764935753, 1776794410, 866854601, 365854486, 304211060, 344860208, 1361012693, + 1450892344, 622170346, 70003859, 1681866717, 435288306, 687941098, 308700094, 1367731096, 1834285819, 255226842, 193873940, 1833603743, 848402819, 152273285, 231181585, 1754447491, 1838218199, 834410115, 229905664, 2052321529, + 338532526, 77482422, 12937811, 35859252, 1645969422, 1501181424, 438711458, 1496078411, 419109342, 1455756978, 1234944834, 1287171290, 470090505, 1900162831, 1130850177, 1772760484, 381571915, 1605369007, 514914429, 994291574, + 1502557594, 1099847920, 1627355806, 1148699143, 1519017268, 946489895, 106595511, 921573402, 181567810, 1575380740, 1719573683, 1561730727, 1920182565, 1510133268, 1102603775, 1175885101, 802730854, 185979744, 1058937717, 1716853034, + 31596852, 462857778, 1335652095, 47036070, 178901145, 1399673078, 222529745, 128036841, 1708126014, 923768127, 1980923963, 1413860940, 1382551511, 208160226, 1892370478, 2091626028, 1793190956, 1417601340, 515811664, 2076612603, + 993525189, 1127173529, 245334962, 134453363, 1206302514, 1344125357, 1139159604, 651536866, 22136821, 1536213818, 2143324534, 879878312, 1944679691, 119285206, 832081018, 1566878909, 876130333, 656954306, 226726100, 937976428, + 1202009920, 1938258683, 2014129292, 1274436639, 1102423908, 1485740112, 879552408, 1712269139, 650513248, 1068587688, 434850545, 382422699, 919736727, 2022291557, 1319798607, 2139976479, 772059719, 1033910502, 1120963974, 340231765, + 1471131758, 1767380006, 47452797, 1313871880, 399114073, 1462921857, 671848647, 31574181, 230340298, 239990424, 590690783, 1714295540, 833019845, 398244682, 522160389, 900852, 1045627895, 1545555937, 226986415, 208433088, + 1502480836, 1611500622, 1933923245, 1588715179, 1655277291, 1749972876, 1386258142, 935490932, 173822937, 702380578, 348131466, 81402251, 875481479, 72939206, 2033828953, 1302272656, 64795664, 2010549018, 1652108025, 58217952, + 1871684562, 190536346, 244709448, 949010757, 320137025, 729474445, 133790520, 740536012, 316479300, 1191513656, 1802197319, 785398708, 1816641611, 2052328978, 930367387, 1374125186, 303845878, 852835634, 454359988, 2131761201, + 1757028186, 536063430, 1765354961, 726869128, 1209784819, 1790557628, 783427298, 2094085507, 1323798820, 846127236, 1065481253, 572240371, 1745543275, 1011417836, 1970797151, 748527394, 343119399, 723323690, 925975225, 901789102, + 1726987516, 535828217, 387611445, 464171383, 1170510314, 1166227930, 1807172811, 1942089394, 985305323, 1368235387, 1691486500, 1568900638, 1876255297, 1249183285, 1710305778, 1763785295, 1733366374, 1444076976, 1629633514, 2105321510, + 225091211, 898893218, 863551327, 1441811554, 546340809, 1977865396, 2116495484, 1221726287, 293109484, 1601617797, 1568176414, 1424797596, 1256372950, 298799048, 1708002892, 829450571, 891710357, 1994402695, 1136264020, 372280769, + 1520667645, 983043723, 1191079043, 680172541, 813511681, 395360213, 1648575360, 1026342885, 2100497812, 422047044, 509116230, 859612092, 2037182006, 895080280, 494367164, 1732028080, 355614494, 2141591317, 1087251698, 580692625, + 225934851, 1581062145, 1515262458, 1497680539, 1711718534, 1774796872, 301673313, 1136356724, 653050943, 109035776, 1709823304, 1340949553, 1365423458, 1155459206, 1203897636, 188016786, 256210446, 633075975, 19227407, 1864952910, + 1143853106, 237020443, 1750197960, 856837002, 80321564, 1679324299, 1257507406, 1390040163, 1590461855, 806384435, 1331383316, 2027828650, 1649392096, 1928309762, 1027758817, 1267173039, 123889599, 95752736, 2060969286, 619461174, + 1686215900, 1817156134, 2118821565, 1596821127, 1800186189, 212821393, 661318748, 1123331233, 146002907, 953877041, 1771924274, 929351822, 2142357746, 356638683, 1610539590, 2001056977, 368889391, 62209567, 1775608361, 992410365, + 1336108161, 696448050, 333820982, 585804640, 1775805177, 809604334, 93191015, 732444124, 1492071476, 1930662128, 174082258, 340442582, 507936866, 362748128, 1607204293, 953383750, 1599876594, 416457166, 571635069, 1356847855, + 267174620, 2011827638, 1572212863, 589049769, 2024853642, 1680251429, 914906004, 398911194, 795915364, 1332467446, 688483428, 628445699, 578787063, 2006320950, 1167207852, 336213879, 1640952769, 1778544166, 1617229086, 190807078, + 1968608155, 2122852959, 31153367, 1353144470, 2196420, 1395155215, 1948121717, 69118708, 2140091269, 2530146, 1740778973, 1601247294, 1205895814, 858150908, 1878253960, 1967705762, 2090543533, 1702425249, 622114437, 1192155877, + 1095403694, 2115445751, 1201124879, 1140728569, 2085323316, 1291025252, 871908043, 863647665, 1245819051, 1468486929, 631022494, 1161580432, 539942311, 1943137808, 1826628136, 259775677, 277497333, 2140756121, 973493986, 1121800211, + 1539560507, 1337406065, 186178768, 482917205, 1459100749, 1924603748, 390743779, 1140008063, 517767440, 1764436465, 722260205, 1400929335, 1706528514, 486165509, 1379460673, 206653795, 3159407, 565150174, 688338919, 1223572435, + 2122262571, 513009937, 1390656632, 271906847, 1622692876, 1313115559, 2061144988, 411864717, 437710825, 513582947, 305489695, 1713188647, 387273799, 1901537567, 644842409, 1231932661, 356672421, 232170581, 1636860706, 302219842, + 2094591332, 1697686200, 1390477985, 1833543700, 1203377492, 50968578, 1332379148, 1514582723, 909273561, 1914809801, 560663378, 1032914339, 1216475831, 113462155, 1165446977, 800591831, 1058677375, 432102601, 2131797509, 1175004233, + 1602827413, 878884686, 446372159, 257728183, 800661980, 1387864976, 2004770236, 999229412, 1428223489, 175843632, 74887898, 630393584, 1147793249, 112648605, 1028529524, 1891904961, 1953919896, 481563348, 436476038, 1601134240, + 72319656, 1581118537, 460420451, 1904576737, 786297537, 359735266, 1918354829, 4031164, 1679777458, 1144017176, 1462192184, 690865719, 1515933932, 363508800, 1480324438, 1044088643, 2036061488, 218671081, 830595166, 381933797, + 108346070, 92271196, 217762975, 1522316172, 1021014457, 1407094080, 857894203, 1968623233, 1459620801, 1345014111, 709651138, 520511102, 2048560397, 1768795266, 1013901419, 1709697877, 1026380990, 1377995642, 1560142576, 542609105, + 1534330971, 528024121, 2015847175, 325324443, 1137511396, 1883999260, 1871060346, 715940689, 167653495, 1292049996, 1172290275, 2018336444, 1951228823, 1666074170, 1834852613, 854475547, 308857120, 502558280, 2105718728, 1624653209, + 514214340, 976063110, 227427283, 912381406, 785989696, 451448729, 212046016, 2068743361, 117280545, 1936668087, 210748671, 1984152603, 945948973, 1409001936, 1644353864, 1139018167, 678475375, 1279061703, 723930558, 195379046, + 1498554338, 999346398, 1665914525, 1473735214, 1561422777, 151416112, 697817760, 1622758049, 607761482, 69889880, 1152335090, 1063657548, 1338090388, 55461678, 1278053582, 837024327, 1914764659, 1049475248, 161502390, 80404202, + 624714335, 879380479, 1066787659, 1375470750, 1561212123, 59384706, 966363087, 2044016080, 1178086274, 1159745061, 291298358, 173062659, 1385675177, 652078020, 1802327778, 1555660285, 623909040, 1579725218, 1649344003, 270814499, + 350182379, 1188076819, 893957771, 534384094, 1057003814, 230634042, 2117880007, 778834747, 250859482, 104637677, 1328272543, 1869264274, 1847908587, 311127477, 506466155, 1808237662, 607471900, 1558244592, 1228817775, 720339756, + 1963053072, 1011473945, 1204992245, 566166447, 419053054, 737377568, 520329478, 1740099311, 1682700783, 1455316979, 2118805956, 729509794, 1565610678, 722347551, 739596391, 882282387, 926200942, 999899279, 1318032594, 122124863, + 1633512617, 1269707634, 380070610, 1043920511, 665601851, 873976891, 717911282, 2135673182, 761851297, 1604330946, 666624765, 513561613, 1504023310, 1128895624, 99511825, 722919148, 1047336724, 550532376, 1082864732, 289686472, + 216557804, 1174587016, 845698678, 1554106660, 577410402, 790256415, 675663963, 2029133999, 161450336, 228960529, 743745539, 1352833750, 2123379476, 852338021, 1291070368, 448708980, 1953450944, 923478775, 827496819, 1126017956, + 197964832, 281317274, 1171925835, 764902582, 595717488, 2129930580, 1437147036, 1447469119, 755554593, 2130879949, 1835203128, 1547662666, 1855359256, 965490116, 672323245, 182598318, 216435361, 1324723894, 1144669754, 454438520, + 1220523503, 1520886946, 1797641070, 1585050246, 797060176, 1821482472, 2128078174, 973367349, 991874801, 679519053, 1961647235, 2094159153, 391321675, 1604357658, 576906032, 1712341869, 344515114, 1122768484, 1659079595, 1328885292, + 48775768, 247448424, 1836119534, 1564061243, 1386366954, 485818381, 37017340, 356546370, 1675494182, 430093707, 1959222232, 1784682542, 1839063567, 1596042792, 295666215, 403378386, 2114587535, 1515528736, 1541546082, 1444048519, + 1215103809, 1687941280, 1546057655, 1905279500, 544899032, 2069178089, 1688652157, 1414160501, 332201519, 631936923, 423299667, 1332937015, 545602285, 310273032, 960982228, 372501343, 1933532372, 1711569347, 11476473, 155845605, + 700725671, 1457464894, 1325083914, 172109594, 664387510, 1705378439, 376781122, 1472567100, 343682568, 1370528050, 265363198, 2079492652, 1803183394, 519194709, 1538391713, 1931493432, 1183464058, 1489699243, 495097609, 801046035, + 177100916, 1292413659, 1348373925, 1550525411, 697685269, 856621012, 1992941115, 1189141368, 221661515, 156760399, 38620214, 375863194, 2078528215, 2103236982, 341987235, 698660475, 381094614, 1201152163, 1275500498, 398211404, + 801610475, 1087556673, 846650758, 1848681194, 1287830283, 1400070607, 1603428054, 1233022905, 810516965, 690710531, 1860435620, 750631050, 1271370220, 860360715, 1189323192, 1913926325, 946425090, 1815408878, 743572345, 1902501708, + 1276205250, 2005653265, 624614472, 2108439398, 1952177514, 964348374, 1171051384, 2126963607, 812288356, 108628319, 980702956, 714456194, 1678967663, 1935271536, 236851791, 1541132933, 1066014062, 1607628402, 1926717418, 954942098, + 1733982669, 14239125, 1506716966, 848141854, 1178260876, 614222093, 731606176, 1512135729, 63244522, 968848252, 1783943137, 1402735006, 1355391150, 1659137391, 1173889730, 1042942541, 1318900244, 1149113346, 2090025563, 1201659316, + 250022739, 1035075488, 674580901, 1090386021, 1943651015, 934048997, 2087660971, 738682048, 1305071296, 91177380, 1708106609, 1685880008, 364589031, 1860839427, 1927367009, 906899219, 1090443335, 892574149, 1969729134, 1874026715, + 927045887, 1159898528, 730296520, 349249331, 317980803, 225908941, 483348027, 1035956563, 241537930, 1279981214, 1247518755, 247447060, 1793747608, 752388169, 288054543, 2073482870, 2039012903, 617768643, 433412593, 499898207, + 1050512245, 331284679, 851322111, 1294873695, 1715379173, 1159675637, 1029338154, 2027445678, 1653332243, 1874855959, 1234157881, 260674360, 1042790263, 1401980800, 730090881, 1745393357, 1550721460, 1607677838, 969500483, 778702716, + 1765830270, 731763278, 1600023202, 1957728250, 690983, 444361278, 1278777407, 1231639101, 597427397, 1087245613, 258177907, 2093472294, 1462778368, 2067100479, 1628387880, 762564955, 1194041213, 1348361229, 1822279764, 1826590258, + 1112056034, 2088786920, 815110420, 1957877704, 1087195269, 881982271, 1945110368, 1656527154, 529233847, 137046551, 522408049, 1880577483, 847255974, 851716534, 925604268, 1037521069, 461527795, 1332620900, 525605961, 1389787451, + 1127911377, 1198857033, 859385989, 706825946, 371790550, 145611377, 655200896, 1900613055, 1333790305, 1101722351, 1278794420, 2089981667, 1150780072, 13180701, 1502266386, 1103013140, 343038558, 1897907456, 1612609979, 1209991461, + 1740783613, 1643991754, 977454680, 787842886, 163362230, 1087742330, 200253206, 1691676526, 360632817, 1787338655, 35595330, 822635252, 1834254978, 1372169786, 1063768444, 973490494, 697866347, 156498369, 169293723, 180549009, + 112035400, 127867199, 241711645, 2004664325, 23288667, 1997381015, 736455241, 1986921372, 1570645300, 2067499753, 1463269859, 148527979, 618168829, 1715279374, 2066440075, 2118433006, 198233440, 1835860030, 1345873587, 1902595458, + 1961619988, 1291438802, 1325008187, 836983022, 1849657867, 500376868, 1599565995, 1705905941, 1600493361, 386733714, 1028820236, 1663100626, 1322696419, 1482983072, 1092382563, 1667679197, 1965855212, 1063839036, 1742032331, 300191208, + 620497725, 503895325, 2094864173, 928179911, 277942057, 1677449797, 1249086623, 799527371, 1180063064, 48311975, 1866094167, 1405763119, 2109851473, 1594621666, 580464203, 1752598186, 1339293088, 922186026, 1403771494, 299505702, + 1345987999, 1298200648, 2128826472, 677220745, 831273447, 741184696, 696188251, 1912065710, 1016469330, 682018288, 353946286, 559509624, 515414188, 1852181952, 407771887, 812094461, 1859683061, 1100089300, 498702377, 653626077, + 765701205, 150878039, 328551896, 77104822, 1775331228, 1835977906, 706357381, 1240287664, 839507573, 1054066034, 1823053058, 701959731, 82879528, 652404808, 866097476, 926939064, 1326017288, 1747861289, 1173840088, 1524006589, + 443704960, 835506582, 5363460, 2068343250, 1683915700, 2080735477, 1913489530, 951256529, 1752318678, 105384223, 1788389051, 1787391786, 1430821640, 540952308, 882484999, 690806365, 202502890, 1593837351, 530093821, 385878401, + 907401151, 378912543, 454746323, 251514112, 1451277631, 1125822965, 21289266, 1642884452, 804368379, 2048205721, 917508270, 1514792012, 139494505, 1143168018, 115016418, 1730333306, 1630776459, 50748643, 1745247524, 1313640711, + 1076198976, 1820281480, 941471466, 806673335, 722162727, 1837280287, 705508794, 2088955494, 510497580, 51692325, 893597382, 1373978529, 1007042224, 685006165, 1471461419, 1555325521, 1215063385, 1424859828, 657251271, 1391827090, + 965562483, 604275115, 1285258674, 341475746, 294191106, 633240394, 1897691227, 1904243956, 823532901, 1577955754, 2016464961, 1862876260, 577384103, 1012611702, 247243083, 636485510, 1952805989, 1447876480, 108021700, 1016615447, + 2047769687, 943871886, 787537653, 12744598, 853545598, 334037304, 553373537, 1089408490, 497867498, 2038925801, 1434633879, 1290629443, 75922980, 957037315, 2130252471, 477317888, 952824381, 1686570783, 459340678, 751885764, + 836307572, 2027909489, 28791588, 322748588, 1335236478, 787106123, 113580144, 954915740, 1317077622, 1299667896, 2009244921, 1548588723, 2049698913, 732388681, 1781891230, 2090684129, 993786972, 1959292396, 1336513734, 691093904, + 1746904676, 935573751, 1123555638, 108413311, 1445352642, 169726789, 123352211, 1635952299, 673775121, 2042861943, 757787251, 512494446, 119656942, 58159196, 2090570016, 486181025, 1619641914, 432990571, 894937325, 379470588, + 1890938638, 1886317932, 1858637614, 969358207, 1230449468, 1890889527, 351741654, 214725897, 1550012286, 308005013, 26292400, 68067591, 1383307838, 1746273091, 1090104632, 1658037573, 2081544705, 1133473813, 1680294422, 1050373352, + 1806061681, 1713475126, 520699193, 417568373, 1355086853, 631399565, 1742434188, 2077667592, 1709019727, 594054971, 937081176, 742185643, 1904514273, 887841601, 1288684086, 424587711, 1497926365, 829844031, 1384314543, 250129297, + 200083737, 693737559, 1527022962, 1462501905, 1687540458, 1156824624, 241481265, 1190890142, 1250360726, 2064308502, 27563032, 1880483834, 1984143440, 104727360, 1324123626, 1089710430, 1403206383, 1930880552, 773197243, 1160186023, + 562994480, 1065136414, 502237764, 1642338733, 1310177444, 1730721241, 1475638246, 615734453, 1160537912, 928836931, 253898558, 1799210492, 1205522527, 413058646, 1589194592, 1774218355, 43955934, 1673314595, 683393460, 1260859787, + 2098829619, 772503535, 1232567659, 758174758, 831270563, 1605294199, 1660678300, 24379565, 1426483935, 1611558740, 1085326591, 12849216, 455856722, 878692218, 1910978116, 1382893830, 1950124297, 950009818, 904287249, 791384486, + 1584408128, 210098472, 1110387095, 364620240, 53868166, 772251062, 472745168, 1133910514, 1715402379, 1445225855, 1541125975, 149171217, 972058766, 1893095488, 1487620835, 640835502, 1470285405, 646688705, 988431201, 703130341, + 1753125385, 1985895474, 696002734, 1783233173, 1317201705, 1755204784, 532132334, 1069450170, 249700039, 524320231, 757959820, 2109052886, 604977130, 1971654864, 1588222158, 1533496974, 623670976, 1405668251, 1955436051, 1082881617, + 1387039848, 874153641, 1345378476, 1168465459, 2005021017, 234039217, 473318229, 654912216, 1473166451, 997649666, 801824335, 2052343947, 1883168929, 185658088, 1389954587, 1725541486, 885873448, 958774566, 2054212564, 60536525, + 1427504270, 1160285859, 1827651881, 1408805003, 1684018729, 61716770, 844057079, 1011596733, 1521350211, 1581801257, 907554175, 2022973269, 1125104871, 1312064004, 1466679625, 970194422, 80900939, 1445279202, 335456148, 510478312, + 92860378, 1646704157, 1650899832, 1533447203, 268087516, 880688023, 1180525723, 1868151949, 1750955971, 401446720, 540093580, 1022861633, 461442838, 1222554291, 456462271, 94760711, 1231111410, 2145073408, 1932108837, 300618464, + 2055783490, 980863365, 1308872551, 1010427073, 1399854717, 1217804021, 934700736, 878744414 +}; + +type verify_data[DATA_SIZE] = +{ + 690983, 900852, 2196420, 2530146, 3159407, 3522194, 3794415, 4031164, 5309142, 5363460, 9736243, 11476473, 12744598, 12849216, 12937811, 13180701, 13887419, 14125900, 14239125, 16411608, + 19227407, 20643769, 21289266, 22136821, 22762734, 23288667, 24379565, 25885333, 26292400, 26687179, 27377406, 27563032, 28256901, 28791588, 30992839, 31153367, 31574181, 31596852, 35595330, 35859252, + 37017340, 37141933, 38620214, 41714278, 42021322, 43955934, 47036070, 47452797, 47463938, 48311975, 48775768, 50748643, 50968578, 51692325, 53868166, 55461678, 58159196, 58217952, 59384706, 60536525, + 61716770, 62209567, 63244522, 64795664, 66579049, 68067591, 69118708, 69889880, 70003859, 70894786, 72319656, 72802865, 72939206, 74887898, 75922980, 77104822, 77482422, 78348530, 80321564, 80404202, + 80900939, 81402251, 82879528, 84924801, 87897457, 88823122, 89400484, 90063199, 91177380, 92271196, 92620223, 92860378, 93191015, 94760711, 95752736, 99511825, 104637677, 104727360, 105384223, 106223060, + 106595511, 107095939, 107160610, 108021700, 108346070, 108413311, 108628319, 109035776, 109526756, 112035400, 112648605, 113462155, 113580144, 114202152, 115016418, 116766659, 117260224, 117280545, 117766047, 119285206, + 119656942, 122124863, 123352211, 123889599, 127867199, 128036841, 130001148, 131405125, 133790520, 134453363, 135012885, 135678410, 137046551, 137796456, 139494505, 140536987, 145611377, 146002907, 148113917, 148527979, + 149171217, 150878039, 151416112, 152273285, 155845605, 156498369, 156760399, 161450336, 161502390, 163362230, 167653495, 168771888, 169293723, 169726789, 170281493, 172109594, 173062659, 173822937, 174082258, 174965839, + 175753599, 175843632, 176024101, 177100916, 178901145, 180549009, 180599971, 181567810, 182598318, 183679578, 185592115, 185658088, 185979744, 186112992, 186178768, 188016786, 190215907, 190536346, 190807078, 193873940, + 195379046, 196401930, 197964832, 198186681, 198233440, 200083737, 200253206, 202502890, 204514903, 205008108, 206653795, 208160226, 208433088, 210098472, 210748671, 210908782, 212046016, 212821393, 214725897, 215018112, + 216435361, 216557804, 217762975, 218671081, 221330186, 221661515, 222529745, 225091211, 225908941, 225934851, 226723092, 226726100, 226906236, 226986415, 227427283, 227870124, 228960529, 229905664, 230340298, 230634042, + 231181585, 232170581, 234039217, 236851791, 237020443, 238278880, 238566180, 239990424, 240618723, 241481265, 241537930, 241711645, 244709448, 244975305, 245334962, 247243083, 247447060, 247448424, 249700039, 250022739, + 250129297, 250731366, 250859482, 251514112, 253898558, 255226842, 256210446, 256860662, 257728183, 258177907, 259768753, 259775677, 260267972, 260670135, 260674360, 260792255, 261556590, 265363198, 267174620, 268087516, + 269167950, 270410557, 270814499, 271906847, 274746405, 277497333, 277942057, 279252402, 281317274, 283430575, 284658041, 287497702, 288054543, 289686472, 291298358, 293109484, 294191106, 295666215, 298799048, 299505702, + 300191208, 300618464, 301350822, 301663421, 301673313, 302219842, 303845878, 304131252, 304211060, 304427548, 305489695, 305750851, 308005013, 308700094, 308832070, 308857120, 310273032, 311127477, 316479300, 317980803, + 318750634, 320137025, 322748588, 324215873, 325324443, 325667019, 328551896, 329049266, 329767814, 330474090, 331284679, 332201519, 333820982, 333906659, 334037304, 335456148, 336213879, 338532526, 340231765, 340442582, + 341475746, 341674967, 341987235, 343038558, 343119399, 343682568, 344515114, 344860208, 346598567, 348131466, 349249331, 350182379, 351741654, 353946286, 355614494, 356546370, 356638683, 356672421, 359735266, 360632817, + 362748128, 363508800, 364589031, 364620240, 365275089, 365854486, 366700722, 367923081, 368541415, 368889391, 371790550, 372280769, 372465453, 372501343, 373226849, 373305330, 375863194, 376781122, 378912543, 379470588, + 380070610, 381094614, 381571915, 381933797, 382422699, 385878401, 386733714, 387061281, 387273799, 387611445, 388855203, 389233190, 390743779, 391321675, 395360213, 398211404, 398244682, 398911194, 399114073, 399456957, + 399991238, 401446720, 402845420, 403378386, 407771887, 411864717, 413058646, 416457166, 417568373, 419053054, 419109342, 419476096, 420106224, 421198539, 422047044, 423299667, 424587711, 430093707, 432102601, 432609664, + 432990571, 433412593, 434850545, 435236973, 435288306, 436476038, 436580096, 436630343, 437710825, 438711458, 443704960, 444361278, 446372159, 448284065, 448708980, 451448729, 452888789, 454359988, 454438520, 454746323, + 455856722, 456462271, 459340678, 460420451, 460893030, 461442838, 461527795, 462743614, 462857778, 464171383, 464795711, 465119445, 470090505, 472745168, 472872107, 473318229, 477317888, 477407584, 478721193, 481561285, + 481563348, 482917205, 483348027, 485818381, 486165509, 486181025, 487888229, 490920543, 492507266, 494367164, 495097609, 497867498, 498702377, 499898207, 500376868, 500734709, 502237764, 502323961, 502558280, 503368137, + 503895325, 506466155, 507848158, 507936866, 508041515, 509116230, 509744705, 510478312, 510497580, 512494446, 513009937, 513561613, 513582947, 514214340, 514914429, 515414188, 515811664, 517767440, 518073650, 519194709, + 519344323, 519699747, 520329478, 520511102, 520699193, 522160389, 522408049, 524320231, 525605961, 528024121, 529233847, 530093821, 532132334, 532467027, 533101409, 534384094, 535828217, 536063430, 538932155, 539429964, + 539942311, 540006359, 540093580, 540952308, 542609105, 543952312, 544899032, 545066288, 545602285, 546340809, 548632788, 549253917, 550532376, 553373537, 556328195, 559509624, 560663378, 562994480, 565150174, 566166447, + 567779677, 568652142, 569949159, 571635069, 572240371, 574236644, 576906032, 577384103, 577410402, 578787063, 579174666, 580464203, 580692625, 583112200, 585169793, 585804640, 589049769, 590690783, 592006699, 592234826, + 594054971, 594814862, 595717488, 597427397, 598016845, 602368560, 602907378, 603159718, 603907009, 604275115, 604977130, 607471900, 607761482, 612289854, 614222093, 614612685, 615734453, 617768643, 617995659, 618168829, + 618681206, 619428858, 619461174, 619972089, 620497725, 621921213, 622114437, 622170346, 623670976, 623909040, 624614472, 624714335, 624939139, 625991894, 628445699, 630393584, 631022494, 631399565, 631936923, 632611704, + 633075975, 633240394, 636485510, 637659983, 638167485, 640835502, 644293952, 644842409, 646688705, 649754857, 650513248, 651536866, 651750790, 652078020, 652404808, 653050943, 653626077, 654912216, 655200896, 655445946, + 656954306, 657251271, 661318748, 664387510, 665601851, 666624765, 670621648, 671848647, 672323245, 672906535, 673775121, 674580901, 675549432, 675663963, 677220745, 678475375, 679519053, 680172541, 682018288, 683393460, + 683536723, 685006165, 686797873, 687941098, 688338919, 688483428, 690710531, 690806365, 690865719, 691093904, 692845661, 693737559, 696002734, 696188251, 696448050, 697685269, 697817760, 697866347, 698660475, 700725671, + 701959731, 702380578, 703130341, 705508794, 705851791, 706357381, 706825946, 706913763, 709651138, 714042223, 714456194, 715940689, 717911282, 720339756, 721046824, 721524505, 722162727, 722260205, 722347551, 722919148, + 723323690, 723930558, 726141970, 726869128, 727587915, 729474445, 729509794, 730090881, 730296520, 730422541, 730845665, 731606176, 731763278, 732388681, 732444124, 736455241, 737377568, 737518341, 738682048, 739596391, + 740536012, 741078359, 741184696, 742185643, 743572345, 743745539, 745183293, 745777837, 747592875, 748527394, 749415493, 750631050, 750919339, 751885764, 752388169, 753296935, 754215794, 754247044, 754896618, 755554593, + 755798022, 757787251, 757959820, 758174758, 761851297, 762564955, 764902582, 764935753, 765386206, 765701205, 767233910, 767880329, 768185796, 769005536, 770412991, 770957259, 772059719, 772251062, 772503535, 773197243, + 777433215, 778702716, 778834747, 779093898, 783427298, 785398708, 785989696, 786297537, 786566648, 787106123, 787537653, 787842886, 787913688, 790256415, 790929190, 791188057, 791384486, 793505636, 795915364, 797060176, + 798445606, 799527371, 799717076, 800591831, 800661980, 801046035, 801610475, 801824335, 802730854, 804368379, 806384435, 806638567, 806673335, 809604334, 810387144, 810516965, 812094461, 812288356, 812328969, 813511681, + 814302898, 815110420, 817417567, 820933470, 821481684, 822635252, 823532901, 827496819, 829450571, 829844031, 830595166, 831270563, 831273447, 832081018, 833019845, 834410115, 835063788, 835506582, 836307572, 836983022, + 837024327, 837554186, 839507573, 840106059, 843738737, 844057079, 845698678, 846127236, 846650758, 847255974, 848141854, 848402819, 849489374, 851322111, 851716534, 852338021, 852388468, 852835634, 853545598, 854475547, + 855107605, 856621012, 856837002, 857894203, 858045289, 858150908, 859385989, 859612092, 860360715, 863551327, 863647665, 866097476, 866478506, 866854601, 866964848, 867628573, 869853078, 871908043, 873623623, 873976891, + 874153641, 875481479, 876130333, 878692218, 878744414, 878884686, 879380479, 879552408, 879878312, 880456526, 880688023, 881982271, 882282387, 882484999, 885873448, 886978116, 887841601, 890461390, 891710357, 892574149, + 892939912, 893302687, 893597382, 893957771, 894769708, 894937325, 895080280, 895562064, 898893218, 901789102, 904287249, 906899219, 907401151, 907554175, 909273561, 909415369, 910677024, 912381406, 914906004, 915948205, + 916073297, 917508270, 918378387, 919736727, 921573402, 922186026, 923478775, 923768127, 924541465, 925604268, 925975225, 926200942, 926939064, 927045887, 927524181, 928179911, 928836931, 929351822, 930367387, 932423857, + 933603111, 933673987, 934048997, 934700736, 935490932, 935573751, 935689637, 935939763, 937081176, 937976428, 937987129, 939497524, 941471466, 942977997, 943871886, 944382193, 945948973, 946311527, 946425090, 946489895, + 948686793, 949010757, 949222447, 950009818, 951256529, 951663731, 952824381, 953383750, 953877041, 954441852, 954915740, 954942098, 957037315, 958774566, 959354209, 960982228, 964348374, 965490116, 965562483, 966363087, + 968848252, 969076419, 969305448, 969358207, 969500483, 970194422, 972058766, 973367349, 973490494, 973493986, 973769771, 976015092, 976063110, 977454680, 977907387, 978247260, 980702956, 980863365, 983043723, 985305323, + 986240059, 987761406, 988431201, 991159735, 991874801, 992410365, 993525189, 993786972, 994291574, 997649666, 998931662, 999229412, 999346398, 999899279, 1007042224, 1010427073, 1011417836, 1011473945, 1011596733, 1012611702, + 1013901419, 1016469330, 1016615447, 1020037994, 1021014457, 1022861633, 1025117441, 1026342885, 1026380990, 1027758817, 1027760887, 1028529524, 1028820236, 1028937430, 1029176122, 1029338154, 1029832956, 1031625002, 1032748996, 1032914339, + 1033910502, 1035075488, 1035956563, 1037521069, 1038018856, 1038830638, 1042790263, 1042942541, 1043920511, 1044088643, 1045627895, 1045658065, 1047336724, 1048943084, 1049475248, 1050373352, 1050512245, 1051184301, 1054066034, 1057003814, + 1058677375, 1058937717, 1061864942, 1063657548, 1063743848, 1063768444, 1063839036, 1065136414, 1065481253, 1066014062, 1066787659, 1067775613, 1068587688, 1068798385, 1069450170, 1073695485, 1073871430, 1074205225, 1075762632, 1076198976, + 1078197595, 1079859867, 1082499152, 1082864732, 1082881617, 1085326591, 1087195269, 1087245613, 1087251698, 1087556673, 1087742330, 1089408490, 1089710430, 1090104632, 1090386021, 1090443335, 1092382563, 1092881031, 1094283114, 1094531762, + 1095403694, 1099847920, 1100041120, 1100089300, 1101722351, 1101933540, 1102423908, 1102603775, 1103013140, 1106678970, 1110387095, 1111213862, 1112056034, 1112731797, 1113693824, 1120963974, 1121432739, 1121800211, 1121960111, 1122768484, + 1123331233, 1123555638, 1125104871, 1125822965, 1126017956, 1127173529, 1127911377, 1128895624, 1130850177, 1131661227, 1132597050, 1133473813, 1133910514, 1134185180, 1135793759, 1136264020, 1136356724, 1137511396, 1139018167, 1139159604, + 1140008063, 1140728569, 1143168018, 1143511498, 1143853106, 1144017176, 1144669754, 1147341731, 1147793249, 1148699143, 1149113346, 1150780072, 1152335090, 1152416171, 1154842325, 1155459206, 1155544307, 1156824624, 1157666831, 1159675637, + 1159745061, 1159898528, 1160036198, 1160186023, 1160285859, 1160333307, 1160537912, 1161580432, 1162679490, 1165446977, 1166227930, 1167207852, 1168465459, 1169327477, 1170510314, 1170759710, 1171051384, 1171925835, 1172290275, 1173840088, + 1173889730, 1174587016, 1175004233, 1175885101, 1178086274, 1178260876, 1179525294, 1180063064, 1180525723, 1181191604, 1183464058, 1184561748, 1185825535, 1188076819, 1188748563, 1189141368, 1189323192, 1190890142, 1191079043, 1191513656, + 1192155877, 1194041213, 1194709162, 1198213061, 1198254803, 1198857033, 1199317660, 1201124879, 1201152163, 1201659316, 1202009920, 1202162389, 1203377492, 1203897636, 1204992245, 1205522527, 1205895814, 1206302514, 1209784819, 1209991461, + 1212628403, 1212974417, 1214379246, 1214950832, 1215063385, 1215103809, 1216475831, 1217804021, 1218522465, 1220523503, 1220915309, 1221108420, 1221726287, 1222554291, 1223475486, 1223572435, 1223583276, 1228817775, 1230449468, 1231111410, + 1231149357, 1231249235, 1231639101, 1231932661, 1232567659, 1232992084, 1233022905, 1234157881, 1234944834, 1239665569, 1240287664, 1245819051, 1247518755, 1249086623, 1249183285, 1250360726, 1255524953, 1256015513, 1256152080, 1256372950, + 1257507406, 1260859787, 1262399341, 1267173039, 1269707634, 1271370220, 1273223611, 1273955724, 1274190723, 1274436639, 1275331596, 1275500498, 1276205250, 1278053582, 1278777407, 1278794420, 1279061703, 1279981214, 1281443423, 1285258674, + 1286989824, 1287171290, 1287830283, 1288684086, 1289308008, 1290629443, 1290969161, 1291025252, 1291070368, 1291438802, 1292049996, 1292413659, 1293091635, 1294873695, 1296857499, 1298200648, 1299667896, 1302272656, 1302724177, 1303736105, + 1305071296, 1308872551, 1310177444, 1312064004, 1312471120, 1313115559, 1313640711, 1313871880, 1316120929, 1317077622, 1317201705, 1318032594, 1318900244, 1319798607, 1321897861, 1322281086, 1322696419, 1323798820, 1324123626, 1324723894, + 1325008187, 1325083914, 1326017288, 1328272543, 1328885292, 1331383316, 1331593955, 1332379148, 1332467446, 1332620900, 1332937015, 1333790305, 1334857284, 1335236478, 1335298265, 1335652095, 1335861008, 1336108161, 1336513734, 1337406065, + 1338090388, 1339293088, 1340949553, 1344125357, 1345014111, 1345378476, 1345873587, 1345987999, 1347284277, 1348361229, 1348373925, 1350653461, 1352833750, 1353144470, 1353999206, 1355086853, 1355391150, 1356847855, 1361012693, 1361078114, + 1365423458, 1367731096, 1368235387, 1370528050, 1372169786, 1373978529, 1374125186, 1375470750, 1377995642, 1379259015, 1379460673, 1379995885, 1382429941, 1382484003, 1382551511, 1382893830, 1383307838, 1383640563, 1384314543, 1385675177, + 1386258142, 1386366954, 1387039848, 1387864976, 1388759892, 1389787451, 1389954587, 1390040163, 1390274260, 1390306889, 1390477985, 1390656632, 1391095995, 1391827090, 1392162662, 1394929399, 1395155215, 1395289708, 1396662140, 1399673078, + 1399854717, 1400070607, 1400929335, 1401058771, 1401980800, 1402735006, 1403206383, 1403771494, 1404727477, 1405668251, 1405763119, 1407094080, 1408805003, 1409001936, 1412540552, 1413860940, 1414141069, 1414160501, 1415390230, 1417415680, + 1417601340, 1420810050, 1424797596, 1424859828, 1426483935, 1427504270, 1428223489, 1430821640, 1431492783, 1431814151, 1434046375, 1434633879, 1435859758, 1437147036, 1440145706, 1441811554, 1444048519, 1444076976, 1445225855, 1445279202, + 1445352642, 1447469119, 1447876480, 1450892344, 1451277631, 1451442832, 1453397990, 1455316979, 1455756978, 1457464894, 1459100749, 1459138745, 1459500136, 1459620801, 1462192184, 1462501905, 1462778368, 1462921857, 1463269859, 1466632447, + 1466679625, 1467376771, 1468486929, 1470285405, 1471131758, 1471461419, 1471598258, 1472567100, 1473166451, 1473735214, 1475638246, 1480273562, 1480324438, 1480437960, 1482983072, 1485740112, 1486594282, 1487620835, 1489699243, 1491477359, + 1492071476, 1492488573, 1496078411, 1496277718, 1497680539, 1497926365, 1498554338, 1500102591, 1501181424, 1502266386, 1502480836, 1502557594, 1504023310, 1505022272, 1505475223, 1506716966, 1507433029, 1508705426, 1510133268, 1512135729, + 1512163910, 1513255537, 1514278798, 1514582723, 1514792012, 1515262458, 1515528736, 1515933932, 1519017268, 1520667645, 1520886946, 1521350211, 1522316172, 1524006589, 1524491858, 1525451290, 1527022962, 1528031307, 1533447203, 1533496974, + 1534330971, 1536213818, 1537459540, 1538069400, 1538391713, 1539560507, 1541125975, 1541132933, 1541546082, 1545555937, 1546057655, 1546104436, 1547662666, 1548588723, 1548804416, 1550012286, 1550159640, 1550525411, 1550721460, 1551661799, + 1553547892, 1554106660, 1555325521, 1555660285, 1558244592, 1558695709, 1560142576, 1561212123, 1561251584, 1561422777, 1561730727, 1563717683, 1564061243, 1565610678, 1565700239, 1566878909, 1568176414, 1568395337, 1568900638, 1569479928, + 1570645300, 1571598133, 1572212863, 1575380740, 1577034674, 1577955754, 1579725218, 1581062145, 1581118537, 1581801257, 1584408128, 1585050246, 1588222158, 1588715179, 1589194592, 1590461855, 1590771096, 1593359038, 1593837351, 1594621666, + 1596042792, 1596821127, 1597506096, 1598436917, 1599565995, 1599876594, 1600023202, 1600493361, 1601134240, 1601247294, 1601617797, 1602517354, 1602827413, 1602967659, 1603428054, 1604330946, 1604357658, 1605294199, 1605369007, 1607204293, + 1607515830, 1607628402, 1607677838, 1609955669, 1610244183, 1610539590, 1611500622, 1611558740, 1611680320, 1612593993, 1612609979, 1614780688, 1617229086, 1618378831, 1619598456, 1619641914, 1620562432, 1620803320, 1622692876, 1622758049, + 1624653209, 1627355806, 1628387880, 1628389501, 1629633514, 1629914848, 1630293700, 1630776459, 1631405417, 1631935240, 1633512617, 1634445325, 1635952299, 1636203720, 1636860706, 1640952769, 1642338733, 1642884452, 1643991754, 1644353864, + 1645969422, 1646704157, 1648575360, 1649344003, 1649392096, 1650899832, 1652108025, 1653332243, 1655277291, 1656527154, 1657001479, 1658037573, 1659079595, 1659137391, 1660678300, 1663100626, 1663890071, 1665914525, 1666074170, 1667102296, + 1667679197, 1672192305, 1673314595, 1674045273, 1675300017, 1675494182, 1677449797, 1678967663, 1679324299, 1679777458, 1680251429, 1680294422, 1681866717, 1682700783, 1683915700, 1684018729, 1685350721, 1685880008, 1686215900, 1686479103, + 1686570783, 1687540458, 1687941280, 1688652157, 1689946986, 1690167792, 1691486500, 1691676526, 1695191950, 1695617313, 1697686200, 1702425249, 1704561346, 1705378439, 1705905941, 1706528514, 1708002892, 1708106609, 1708126014, 1709019727, + 1709697877, 1709823304, 1710305778, 1711569347, 1711718534, 1711761015, 1711765426, 1712269139, 1712341869, 1713188647, 1713475126, 1714295540, 1715279374, 1715379173, 1715402379, 1716853034, 1719009954, 1719573683, 1721767511, 1723143470, + 1725541486, 1726987516, 1727583308, 1730333306, 1730721241, 1731949250, 1732028080, 1733366374, 1733982669, 1737931879, 1738353358, 1740099311, 1740778973, 1740783613, 1742032331, 1742434188, 1745247524, 1745393357, 1745543275, 1746273091, + 1746476698, 1746904676, 1747861289, 1749972876, 1750197960, 1750443194, 1750955971, 1752088215, 1752318678, 1752598186, 1753125385, 1754447491, 1755204784, 1757028186, 1758748737, 1760851607, 1761289401, 1763785295, 1764436465, 1765354961, + 1765830270, 1767380006, 1768795266, 1770497338, 1771614266, 1771924274, 1772760484, 1774218355, 1774652096, 1774796872, 1775331228, 1775608361, 1775805177, 1776471922, 1776794410, 1778544166, 1781233744, 1781891230, 1783233173, 1783943137, + 1784682542, 1787338655, 1787391786, 1788389051, 1790557628, 1792756324, 1793190956, 1793747608, 1797641070, 1799210492, 1800186189, 1800522575, 1802197319, 1802327778, 1803183394, 1806061681, 1807085904, 1807172811, 1808237662, 1811088032, + 1815408878, 1816641611, 1817156134, 1820281480, 1821482472, 1821559709, 1822279764, 1822612008, 1823053058, 1826590258, 1826628136, 1826880531, 1827651881, 1833543700, 1833603743, 1834161399, 1834254978, 1834285819, 1834318089, 1834388383, + 1834852613, 1835203128, 1835860030, 1835977906, 1836119534, 1837280287, 1838218199, 1839063567, 1840896199, 1846605728, 1847908587, 1848681194, 1849495275, 1849657867, 1849675857, 1852181952, 1855359256, 1858637614, 1858933377, 1859683061, + 1860435620, 1860839427, 1862876260, 1864952910, 1866094167, 1868151949, 1868289345, 1869264274, 1870214195, 1870859970, 1871060346, 1871684562, 1873900475, 1874026715, 1874855959, 1876255297, 1878253960, 1878434988, 1879635915, 1880483834, + 1880577483, 1881253854, 1883168929, 1883999260, 1886317932, 1890889527, 1890938638, 1891630185, 1891904961, 1892370478, 1893095488, 1896952705, 1897691227, 1897907456, 1898582764, 1900162831, 1900613055, 1901537567, 1902501708, 1902595458, + 1904243956, 1904514273, 1904576737, 1904770864, 1905279500, 1906345724, 1907793490, 1908093581, 1909681194, 1910978116, 1912065710, 1913489530, 1913581092, 1913926325, 1914764659, 1914809801, 1915435344, 1916602098, 1918354829, 1920182565, + 1924603748, 1926717418, 1927367009, 1928309762, 1928550562, 1930662128, 1930880552, 1931282005, 1931493432, 1932108837, 1933532372, 1933923245, 1935271536, 1936668087, 1938258683, 1939683211, 1942089394, 1943137808, 1943651015, 1944679691, + 1945110368, 1946004194, 1948121717, 1949896838, 1950124297, 1951228823, 1952177514, 1952364329, 1952805989, 1953450944, 1953919896, 1955436051, 1957728250, 1957877704, 1958396887, 1959222232, 1959292396, 1961619988, 1961647235, 1962689485, + 1963053072, 1965358941, 1965855212, 1967705762, 1968608155, 1968623233, 1969729134, 1970797151, 1971484382, 1971654864, 1977865396, 1980923963, 1981481446, 1983379601, 1984143440, 1984152603, 1985895474, 1986921372, 1989240516, 1992941115, + 1994402695, 1997381015, 2001056977, 2002881120, 2004664325, 2004770236, 2005021017, 2005653265, 2005817027, 2006320950, 2006856683, 2009244921, 2010549018, 2011827638, 2014090929, 2014129292, 2015847175, 2016161810, 2016464961, 2017191527, + 2018336444, 2022291557, 2022973269, 2023498746, 2024853642, 2027445678, 2027814180, 2027828650, 2027909489, 2028116487, 2029133999, 2029909894, 2033003588, 2033828953, 2034767768, 2036061488, 2036750157, 2037182006, 2038925801, 2039012903, + 2041942843, 2042861943, 2044016080, 2045407567, 2045821218, 2046759770, 2047006719, 2047769687, 2048205721, 2048560397, 2049698913, 2052321529, 2052328978, 2052343947, 2053899162, 2054212564, 2055783490, 2060969286, 2061144988, 2063408339, + 2064145552, 2064308502, 2066440075, 2066865713, 2067100479, 2067499753, 2068343250, 2068743361, 2069178089, 2070467093, 2072440819, 2073482870, 2074840378, 2074896270, 2076612603, 2077667592, 2078528215, 2079492652, 2080735477, 2081544705, + 2082760612, 2084953915, 2085323316, 2087660971, 2088576982, 2088786920, 2088955494, 2089981667, 2090025563, 2090543533, 2090570016, 2090684129, 2091626028, 2093472294, 2094085507, 2094159153, 2094591332, 2094864173, 2097057488, 2098829619, + 2100497812, 2103236982, 2105321510, 2105638337, 2105718728, 2105814934, 2108439398, 2109052886, 2109530615, 2109851473, 2113434968, 2114587535, 2115445751, 2116495484, 2117880007, 2118203528, 2118433006, 2118805956, 2118821565, 2119425672, + 2122262571, 2122852959, 2123379476, 2124749673, 2125958841, 2126029304, 2126940990, 2126963607, 2128078174, 2128826472, 2129513521, 2129930580, 2130252471, 2130879949, 2131761201, 2131797509, 2133066804, 2135673182, 2139976479, 2140091269, + 2140756121, 2141591317, 2142357746, 2143324534, 2143343312, 2143968639, 2145073408, 2145930822 +}; + diff --git a/benchmarks/rsort/rsort.c b/benchmarks/rsort/rsort.c new file mode 100644 index 0000000..e67f876 --- /dev/null +++ b/benchmarks/rsort/rsort.c @@ -0,0 +1,123 @@ +//************************************************************************** +// Quicksort benchmark +//-------------------------------------------------------------------------- +// +// This benchmark uses quicksort to sort an array of integers. The +// implementation is largely adapted from Numerical Recipes for C. The +// input data (and reference data) should be generated using the +// qsort_gendata.pl perl script and dumped to a file named +// dataset1.h The smips-gcc toolchain does not support system calls +// so printf's can only be used on a host system, not on the smips +// processor simulator itself. You should not change anything except +// the HOST_DEBUG and PREALLOCATE macros for your timing run. + +#include "util.h" +#include <string.h> +#include <limits.h> + +//-------------------------------------------------------------------------- +// Input/Reference Data + +#define type unsigned int +#include "dataset1.h" + +#define LOG_BASE 8 +#define BASE (1 << LOG_BASE) + +void sort(size_t n, type* arrIn, type* scratchIn) +{ + size_t log_exp = 0; + size_t buckets[BASE]; + size_t *bucket = buckets; + asm("":"+r"(bucket)); + type *arr = arrIn, *scratch = scratchIn, *p; + size_t *b; + + while (log_exp < CHAR_BIT * sizeof(type)) + { + for (b = bucket; b < bucket + BASE; b++) + *b = 0; + + for (p = arr; p < &arr[n-3]; p += 4) + { + type a0 = p[0]; + type a1 = p[1]; + type a2 = p[2]; + type a3 = p[3]; + __sync_fetch_and_add(&bucket[(a0 >> log_exp) % BASE], 1); + __sync_fetch_and_add(&bucket[(a1 >> log_exp) % BASE], 1); + __sync_fetch_and_add(&bucket[(a2 >> log_exp) % BASE], 1); + __sync_fetch_and_add(&bucket[(a3 >> log_exp) % BASE], 1); + } + for ( ; p < &arr[n]; p++) + bucket[(*p >> log_exp) % BASE]++; + + size_t prev = bucket[0]; + prev += __sync_fetch_and_add(&bucket[1], prev); + for (b = &bucket[2]; b < bucket + BASE; b += 2) + { + prev += __sync_fetch_and_add(&b[0], prev); + prev += __sync_fetch_and_add(&b[1], prev); + } + static_assert(BASE % 2 == 0); + + for (p = &arr[n-1]; p >= &arr[3]; p -= 4) + { + type a0 = p[-0]; + type a1 = p[-1]; + type a2 = p[-2]; + type a3 = p[-3]; + size_t* pb0 = &bucket[(a0 >> log_exp) % BASE]; + size_t* pb1 = &bucket[(a1 >> log_exp) % BASE]; + size_t* pb2 = &bucket[(a2 >> log_exp) % BASE]; + size_t* pb3 = &bucket[(a3 >> log_exp) % BASE]; + type* s0 = scratch + __sync_fetch_and_add(pb0, -1); + type* s1 = scratch + __sync_fetch_and_add(pb1, -1); + type* s2 = scratch + __sync_fetch_and_add(pb2, -1); + type* s3 = scratch + __sync_fetch_and_add(pb3, -1); + s0[-1] = a0; + s1[-1] = a1; + s2[-1] = a2; + s3[-1] = a3; + } + for ( ; p >= &arr[0]; p--) + scratch[--bucket[(*p >> log_exp) % BASE]] = *p; + + type* tmp = arr; + arr = scratch; + scratch = tmp; + + log_exp += LOG_BASE; + } + if (arr != arrIn) + memcpy(arr, scratch, n*sizeof(type)); +} + +//-------------------------------------------------------------------------- +// Main + +int main( int argc, char* argv[] ) +{ + static type scratch[DATA_SIZE]; + // Output the input array + printArray( "input", DATA_SIZE, input_data ); + printArray( "verify", DATA_SIZE, verify_data ); + +#if PREALLOCATE + // If needed we preallocate everything in the caches + sort(DATA_SIZE, verify_data, scratch); + if (verify(DATA_SIZE, input_data, input_data)) + return 1; +#endif + + // Do the sort + setStats(1); + sort(DATA_SIZE, input_data, scratch); + setStats(0); + + // Print out the results + printArray( "test", DATA_SIZE, input_data ); + + // Check the results + return verify( DATA_SIZE, input_data, verify_data ); +} |