+// See LICENSE for license details.
+
//**************************************************************************
// Towers of Hanoi benchmark
//--------------------------------------------------------------------------
// disc on top of a smaller disc.
//
// This implementation starts with NUM_DISC discs and uses a recursive
-// algorithm to sovel the puzzle. 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.
-
-//--------------------------------------------------------------------------
-// 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.
+// algorithm to sovel the puzzle.
-#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"
// This is the number of discs in the puzzle.
#define NUM_DISCS 7
-//--------------------------------------------------------------------------
-// Helper functions
-
-void finishTest( int toHostValue )
-{
-#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
-}
-
//--------------------------------------------------------------------------
// List data structure and functions
}
-#if HOST_DEBUG
-void towers_print( struct Towers* this )
-{
- struct Node* ptr;
- int i, numElements;
-
- printf( " pegA: " );
- for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegA))); i++ )
- printf( ". " );
- for ( ptr = this->pegA.head; ptr != 0; ptr = ptr->next )
- printf( "%d ", ptr->val );
-
- printf( " pegB: " );
- for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegB))); i++ )
- printf( ". " );
- for ( ptr = this->pegB.head; ptr != 0; ptr = ptr->next )
- printf( "%d ", ptr->val );
-
- printf( " pegC: " );
- for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegC))); i++ )
- printf( ". " );
- for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next )
- printf( "%d ", ptr->val );
-
- printf( "\n" );
-}
-#endif
-
void towers_solve_h( struct Towers* this, int n,
struct List* startPeg,
struct List* tempPeg,
int val;
if ( n == 1 ) {
-#if HOST_DEBUG
- towers_print(this);
-#endif
val = list_pop(startPeg);
list_push(destPeg,val);
this->numMoves++;
int numDiscs = 0;
if ( list_getSize(&this->pegA) != 0 ) {
-#if HOST_DEBUG
- printf( "ERROR: Peg A is not empty!\n" );
-#endif
return 2;
}
if ( list_getSize(&this->pegB) != 0 ) {
-#if HOST_DEBUG
- printf( "ERROR: Peg B is not empty!\n" );
-#endif
return 3;
}
if ( list_getSize(&this->pegC) != this->numDiscs ) {
-#if HOST_DEBUG
- printf( " ERROR: Expected %d discs but found only %d discs!\n", \
- this->numDiscs, list_getSize(&this->pegC) );
-#endif
return 4;
}
for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next ) {
numDiscs++;
if ( ptr->val != numDiscs ) {
-#if HOST_DEBUG
- printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
- numDiscs, ptr->val );
-#endif
return 5;
}
}
if ( this->numMoves != ((1 << this->numDiscs) - 1) ) {
-#if HOST_DEBUG
- printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
- ((1 << this->numDiscs) - 1), this->numMoves );
-#endif
return 6;
}
- return 1;
+ return 0;
}
//--------------------------------------------------------------------------
towers_solve( &towers );
setStats(0);
- // Print out the results
-
-#if HOST_DEBUG
- towers_print( &towers );
-#endif
-
// Check the results
-
- finishTest( towers_verify( &towers ) );
-
+ return towers_verify( &towers );
}