// processor simulator itself. You should not change anything except
// the HOST_DEBUG and PREALLOCATE macros for your timing run.
-//--------------------------------------------------------------------------
-// Macros
-
-// Set HOST_DEBUG to 1 if you are going to compile this for a host
-// machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
-// to 0 if you are compiling with the smips-gcc toolchain.
-
-#ifndef HOST_DEBUG
-#define HOST_DEBUG 0
-#endif
-
-// Set PREALLOCATE to 1 if you want to preallocate the benchmark
-// function before starting stats. If you have instruction/data
-// caches and you don't want to count the overhead of misses, then
-// you will need to use preallocation.
-
-#ifndef PREALLOCATE
-#define PREALLOCATE 0
-#endif
-
-// Set SET_STATS to 1 if you want to carve out the piece that actually
-// does the computation.
-
-#ifndef SET_STATS
-#define SET_STATS 0
-#endif
+#include "util.h"
+#include <string.h>
+#include <assert.h>
// The INSERTION_THRESHOLD is the size of the subarray when the
// algorithm switches to using an insertion sort instead of
// quick sort.
-#define INSERTION_THRESHOLD 7
+#define INSERTION_THRESHOLD 10
// NSTACK is the required auxiliary storage.
// It must be at least 2*lg(DATA_SIZE)
#define NSTACK 50
-// Swap macro for swapping two values.
-
-#define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
-
//--------------------------------------------------------------------------
// Input/Reference Data
+#define type int
#include "dataset1.h"
+// Swap macro for swapping two values.
+
+#define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
+#define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
+
//--------------------------------------------------------------------------
-// Helper functions
+// Quicksort function
-int verify( int n, int test[], int correct[] )
+static void insertion_sort(size_t n, type arr[])
{
- int i;
- for ( i = 0; i < n; i++ ) {
- if ( test[i] != correct[i] ) {
- return 2;
+ type *i, *j;
+ type value;
+ for (i = arr+1; i < arr+n; i++)
+ {
+ value = *i;
+ j = i;
+ while (value < *(j-1))
+ {
+ *j = *(j-1);
+ if (--j == arr)
+ break;
}
+ *j = value;
}
- return 1;
-}
-
-#if HOST_DEBUG
-void printArray( char name[], int n, int arr[] )
-{
- int i;
- printf( " %10s :", name );
- for ( i = 0; i < n; i++ )
- printf( " %3d ", arr[i] );
- printf( "\n" );
}
-#endif
-void finishTest( int toHostValue )
+static void selection_sort(size_t n, type arr[])
{
-#if HOST_DEBUG
- if ( toHostValue == 1 )
- printf( "*** PASSED ***\n" );
- else
- printf( "*** FAILED *** (tohost = %d)\n", toHostValue );
- exit(0);
-#else
- asm( "mtpcr %0, tohost" : : "r" (toHostValue) );
- while ( 1 ) { }
-#endif
-}
-
-void setStats( int enable )
-{
-#if ( !HOST_DEBUG && SET_STATS )
- asm( "mtpcr %0, cr10" : : "r" (enable) );
-#endif
+ for (type* i = arr; i < arr+n-1; i++)
+ for (type* j = i+1; j < arr+n; j++)
+ SWAP_IF_GREATER(*i, *j);
}
-//--------------------------------------------------------------------------
-// Quicksort function
-
-void sort( int n, int arr[] )
+void sort(size_t n, type arr[])
{
- int i,j,k;
- int ir = n;
- int l = 1;
- int jstack = 0;
- int a, temp;
-
- int istack[NSTACK];
-
- for (;;) {
+ type* ir = arr+n;
+ type* l = arr+1;
+ type* stack[NSTACK];
+ type** stackp = stack;
+ for (;;)
+ {
#if HOST_DEBUG
printArray( "", n, arr );
#endif
// Insertion sort when subarray small enough.
- if ( ir-l < INSERTION_THRESHOLD ) {
-
- for ( j = l+1; j <= ir; j++ ) {
- a = arr[j-1];
- for ( i = j-1; i >= l; i-- ) {
- if ( arr[i-1] <= a ) break;
- arr[i] = arr[i-1];
- }
- arr[i] = a;
- }
+ if ( ir-l < INSERTION_THRESHOLD )
+ {
+ insertion_sort(ir - l + 1, l - 1);
- if ( jstack == 0 ) break;
+ if ( stackp == stack ) break;
// Pop stack and begin a new round of partitioning.
- ir = istack[jstack--];
- l = istack[jstack--];
-
+ ir = *stackp--;
+ l = *stackp--;
}
- else {
-
+ else
+ {
// Choose median of left, center, and right elements as
// partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
-
- k = (l+ir) >> 1;
- SWAP(arr[k-1],arr[l])
- if ( arr[l-1] > arr[ir-1] ) {
- SWAP(arr[l-1],arr[ir-1])
- }
- if ( arr[l] > arr[ir-1] ) {
- SWAP(arr[l],arr[ir-1])
- }
- if ( arr[l-1] > arr[l] ) {
- SWAP(arr[l-1],arr[l])
- }
+ SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
+ SWAP_IF_GREATER(l[-1], ir[-1]);
+ SWAP_IF_GREATER(l[0], ir[-1]);
+ SWAP_IF_GREATER(l[-1], l[0]);
// Initialize pointers for partitioning.
- i = l+1;
- j = ir;
+ type* i = l+1;
+ type* j = ir;
// Partitioning element.
- a = arr[l];
+ type a = l[0];
- for (;;) { // Beginning of innermost loop.
- do i++; while (arr[i-1] < a); // Scan up to find element > a.
- do j--; while (arr[j-1] > a); // Scan down to find element < a.
- if (j < i) break; // Pointers crossed. Partitioning complete.
- SWAP(arr[i-1],arr[j-1]); // Exchange elements.
- } // End of innermost loop.
+ for (;;) { // Beginning of innermost loop.
+ while (*i++ < a); // Scan up to find element > a.
+ while (*(j-- - 2) > a); // Scan down to find element < a.
+ if (j < i) break; // Pointers crossed. Partitioning complete.
+ SWAP(i[-1], j[-1]); // Exchange elements.
+ } // End of innermost loop.
// Insert partitioning element.
- arr[l] = arr[j-1];
- arr[j-1] = a;
- jstack += 2;
+ l[0] = j[-1];
+ j[-1] = a;
+ stackp += 2;
// Push pointers to larger subarray on stack,
// process smaller subarray immediately.
#if HOST_DEBUG
- if ( jstack > NSTACK ) { printf("NSTACK too small in sort.\n"); exit(1); }
+ assert(stackp < stack+NSTACK);
#endif
- if ( ir-i+1 >= j-l ) {
- istack[jstack] = ir;
- istack[jstack-1] = i;
+ if ( ir-i+1 >= j-l )
+ {
+ stackp[0] = ir;
+ stackp[-1] = i;
ir = j-1;
}
- else {
- istack[jstack] = j-1;
- istack[jstack-1] = l;
+ else
+ {
+ stackp[0] = j-1;
+ stackp[-1] = l;
l = i;
}
}
-
}
-
}
//--------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
-
// Output the input array
-
-#if HOST_DEBUG
printArray( "input", DATA_SIZE, input_data );
printArray( "verify", DATA_SIZE, verify_data );
-#endif
-
- // If needed we preallocate everything in the caches
#if PREALLOCATE
- sort( DATA_SIZE, input_data );
+ // If needed we preallocate everything in the caches
+ sort(DATA_SIZE, verify_data);
+ if (verify(DATA_SIZE, input_data, input_data))
+ return 1;
#endif
// Do the sort
-
setStats(1);
sort( DATA_SIZE, input_data );
setStats(0);
// Print out the results
-
-#if HOST_DEBUG
printArray( "test", DATA_SIZE, input_data );
-#endif
// Check the results
-
- finishTest(verify( DATA_SIZE, input_data, verify_data ));
-
+ return verify( DATA_SIZE, input_data, verify_data );
}
projects / riscv-tests.git / blobdiff