1 //**************************************************************************
3 //--------------------------------------------------------------------------
5 // This benchmark uses quicksort to sort an array of integers. The
6 // implementation is largely adapted from Numerical Recipes for C. The
7 // input data (and reference data) should be generated using the
8 // qsort_gendata.pl perl script and dumped to a file named
9 // dataset1.h The smips-gcc toolchain does not support system calls
10 // so printf's can only be used on a host system, not on the smips
11 // processor simulator itself. You should not change anything except
12 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
17 //--------------------------------------------------------------------------
20 // Set HOST_DEBUG to 1 if you are going to compile this for a host
21 // machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
22 // to 0 if you are compiling with the smips-gcc toolchain.
28 // Set PREALLOCATE to 1 if you want to preallocate the benchmark
29 // function before starting stats. If you have instruction/data
30 // caches and you don't want to count the overhead of misses, then
31 // you will need to use preallocation.
37 // Set SET_STATS to 1 if you want to carve out the piece that actually
38 // does the computation.
44 // The INSERTION_THRESHOLD is the size of the subarray when the
45 // algorithm switches to using an insertion sort instead of
48 #define INSERTION_THRESHOLD 7
50 // NSTACK is the required auxiliary storage.
51 // It must be at least 2*lg(DATA_SIZE)
55 // Swap macro for swapping two values.
57 #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
59 //--------------------------------------------------------------------------
60 // Input/Reference Data
64 //--------------------------------------------------------------------------
67 int verify( int n
, int test
[], int correct
[] )
70 for ( i
= 0; i
< n
; i
++ ) {
71 if ( test
[i
] != correct
[i
] ) {
79 void printArray( char name
[], int n
, int arr
[] )
82 printf( " %10s :", name
);
83 for ( i
= 0; i
< n
; i
++ )
84 printf( " %3d ", arr
[i
] );
89 void setStats( int enable
)
91 #if ( !HOST_DEBUG && SET_STATS )
92 asm( "mtpcr %0, cr10" : : "r" (enable
) );
96 //--------------------------------------------------------------------------
99 void sort( int n
, int arr
[] )
112 printArray( "", n
, arr
);
115 // Insertion sort when subarray small enough.
116 if ( ir
-l
< INSERTION_THRESHOLD
) {
118 for ( j
= l
+1; j
<= ir
; j
++ ) {
120 for ( i
= j
-1; i
>= l
; i
-- ) {
121 if ( arr
[i
-1] <= a
) break;
127 if ( jstack
== 0 ) break;
129 // Pop stack and begin a new round of partitioning.
130 ir
= istack
[jstack
--];
131 l
= istack
[jstack
--];
136 // Choose median of left, center, and right elements as
137 // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
140 SWAP(arr
[k
-1],arr
[l
])
141 if ( arr
[l
-1] > arr
[ir
-1] ) {
142 SWAP(arr
[l
-1],arr
[ir
-1])
144 if ( arr
[l
] > arr
[ir
-1] ) {
145 SWAP(arr
[l
],arr
[ir
-1])
147 if ( arr
[l
-1] > arr
[l
] ) {
148 SWAP(arr
[l
-1],arr
[l
])
151 // Initialize pointers for partitioning.
155 // Partitioning element.
158 for (;;) { // Beginning of innermost loop.
159 do i
++; while (arr
[i
-1] < a
); // Scan up to find element > a.
160 do j
--; while (arr
[j
-1] > a
); // Scan down to find element < a.
161 if (j
< i
) break; // Pointers crossed. Partitioning complete.
162 SWAP(arr
[i
-1],arr
[j
-1]); // Exchange elements.
163 } // End of innermost loop.
165 // Insert partitioning element.
170 // Push pointers to larger subarray on stack,
171 // process smaller subarray immediately.
174 if ( jstack
> NSTACK
) { printf("NSTACK too small in sort.\n"); exit(1); }
177 if ( ir
-i
+1 >= j
-l
) {
179 istack
[jstack
-1] = i
;
183 istack
[jstack
] = j
-1;
184 istack
[jstack
-1] = l
;
193 //--------------------------------------------------------------------------
196 int main( int argc
, char* argv
[] )
199 // Output the input array
202 printArray( "input", DATA_SIZE
, input_data
);
203 printArray( "verify", DATA_SIZE
, verify_data
);
206 // If needed we preallocate everything in the caches
209 sort( DATA_SIZE
, input_data
);
215 sort( DATA_SIZE
, input_data
);
218 // Print out the results
221 printArray( "test", DATA_SIZE
, input_data
);
226 finishTest(verify( DATA_SIZE
, input_data
, verify_data
));