dc536424069473284b2324338d9ddee521fa1671
[riscv-tests.git] / benchmarks / rsort / rsort.c
1 // See LICENSE for license details.
2
3 //**************************************************************************
4 // Quicksort benchmark
5 //--------------------------------------------------------------------------
6 //
7 // This benchmark uses quicksort to sort an array of integers. The
8 // implementation is largely adapted from Numerical Recipes for C. The
9 // input data (and reference data) should be generated using the
10 // qsort_gendata.pl perl script and dumped to a file named
11 // dataset1.h The smips-gcc toolchain does not support system calls
12 // so printf's can only be used on a host system, not on the smips
13 // processor simulator itself. You should not change anything except
14 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
15
16 #include "util.h"
17 #include <string.h>
18 #include <limits.h>
19
20 //--------------------------------------------------------------------------
21 // Input/Reference Data
22
23 #define type unsigned int
24 #include "dataset1.h"
25
26 #define LOG_BASE 8
27 #define BASE (1 << LOG_BASE)
28
29 #if 0
30 # define fetch_add(ptr, inc) __sync_fetch_and_add(ptr, inc)
31 #else
32 # define fetch_add(ptr, inc) ((*(ptr) += (inc)) - (inc))
33 #endif
34
35 void sort(size_t n, type* arrIn, type* scratchIn)
36 {
37 size_t log_exp = 0;
38 size_t buckets[BASE];
39 size_t *bucket = buckets;
40 asm("":"+r"(bucket));
41 type *arr = arrIn, *scratch = scratchIn, *p;
42 size_t *b;
43
44 while (log_exp < CHAR_BIT * sizeof(type))
45 {
46 for (b = bucket; b < bucket + BASE; b++)
47 *b = 0;
48
49 for (p = arr; p < &arr[n-3]; p += 4)
50 {
51 type a0 = p[0];
52 type a1 = p[1];
53 type a2 = p[2];
54 type a3 = p[3];
55 fetch_add(&bucket[(a0 >> log_exp) % BASE], 1);
56 fetch_add(&bucket[(a1 >> log_exp) % BASE], 1);
57 fetch_add(&bucket[(a2 >> log_exp) % BASE], 1);
58 fetch_add(&bucket[(a3 >> log_exp) % BASE], 1);
59 }
60 for ( ; p < &arr[n]; p++)
61 bucket[(*p >> log_exp) % BASE]++;
62
63 size_t prev = bucket[0];
64 prev += fetch_add(&bucket[1], prev);
65 for (b = &bucket[2]; b < bucket + BASE; b += 2)
66 {
67 prev += fetch_add(&b[0], prev);
68 prev += fetch_add(&b[1], prev);
69 }
70 static_assert(BASE % 2 == 0);
71
72 for (p = &arr[n-1]; p >= &arr[3]; p -= 4)
73 {
74 type a0 = p[-0];
75 type a1 = p[-1];
76 type a2 = p[-2];
77 type a3 = p[-3];
78 size_t* pb0 = &bucket[(a0 >> log_exp) % BASE];
79 size_t* pb1 = &bucket[(a1 >> log_exp) % BASE];
80 size_t* pb2 = &bucket[(a2 >> log_exp) % BASE];
81 size_t* pb3 = &bucket[(a3 >> log_exp) % BASE];
82 type* s0 = scratch + fetch_add(pb0, -1);
83 type* s1 = scratch + fetch_add(pb1, -1);
84 type* s2 = scratch + fetch_add(pb2, -1);
85 type* s3 = scratch + fetch_add(pb3, -1);
86 s0[-1] = a0;
87 s1[-1] = a1;
88 s2[-1] = a2;
89 s3[-1] = a3;
90 }
91 for ( ; p >= &arr[0]; p--)
92 scratch[--bucket[(*p >> log_exp) % BASE]] = *p;
93
94 type* tmp = arr;
95 arr = scratch;
96 scratch = tmp;
97
98 log_exp += LOG_BASE;
99 }
100 if (arr != arrIn)
101 memcpy(arr, scratch, n*sizeof(type));
102 }
103
104 //--------------------------------------------------------------------------
105 // Main
106
107 int main( int argc, char* argv[] )
108 {
109 static type scratch[DATA_SIZE];
110 // Output the input array
111 printArray( "input", DATA_SIZE, input_data );
112 printArray( "verify", DATA_SIZE, verify_data );
113
114 #if PREALLOCATE
115 // If needed we preallocate everything in the caches
116 sort(DATA_SIZE, verify_data, scratch);
117 if (verify(DATA_SIZE, input_data, input_data))
118 return 1;
119 #endif
120
121 // Do the sort
122 setStats(1);
123 sort(DATA_SIZE, input_data, scratch);
124 setStats(0);
125
126 // Print out the results
127 printArray( "test", DATA_SIZE, input_data );
128
129 // Check the results
130 return verify( DATA_SIZE, input_data, verify_data );
131 }