1 // See LICENSE for license details.
3 //**************************************************************************
5 //--------------------------------------------------------------------------
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.
20 //--------------------------------------------------------------------------
21 // Input/Reference Data
23 #define type unsigned int
27 #define BASE (1 << LOG_BASE)
30 # define fetch_add(ptr, inc) __sync_fetch_and_add(ptr, inc)
32 # define fetch_add(ptr, inc) ((*(ptr) += (inc)) - (inc))
35 void sort(size_t n
, type
* arrIn
, type
* scratchIn
)
39 size_t *bucket
= buckets
;
41 type
*arr
= arrIn
, *scratch
= scratchIn
, *p
;
44 while (log_exp
< CHAR_BIT
* sizeof(type
))
46 for (b
= bucket
; b
< bucket
+ BASE
; b
++)
49 for (p
= arr
; p
< &arr
[n
-3]; p
+= 4)
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);
60 for ( ; p
< &arr
[n
]; p
++)
61 bucket
[(*p
>> log_exp
) % BASE
]++;
63 size_t prev
= bucket
[0];
64 prev
+= fetch_add(&bucket
[1], prev
);
65 for (b
= &bucket
[2]; b
< bucket
+ BASE
; b
+= 2)
67 prev
+= fetch_add(&b
[0], prev
);
68 prev
+= fetch_add(&b
[1], prev
);
70 static_assert(BASE
% 2 == 0);
72 for (p
= &arr
[n
-1]; p
>= &arr
[3]; p
-= 4)
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);
91 for ( ; p
>= &arr
[0]; p
--)
92 scratch
[--bucket
[(*p
>> log_exp
) % BASE
]] = *p
;
101 memcpy(arr
, scratch
, n
*sizeof(type
));
104 //--------------------------------------------------------------------------
107 int main( int argc
, char* argv
[] )
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
);
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
))
123 sort(DATA_SIZE
, input_data
, scratch
);
126 // Print out the results
127 printArray( "test", DATA_SIZE
, input_data
);
130 return verify( DATA_SIZE
, input_data
, verify_data
);