benchmarks/towers/towers_main.c

   1 //**************************************************************************
   2 // Towers of Hanoi benchmark
   3 //--------------------------------------------------------------------------
   4 //
   5 // Towers of Hanoi is a classic puzzle problem. The game consists of
   6 // three pegs and a set of discs. Each disc is a different size, and
   7 // initially all of the discs are on the left most peg with the smallest
   8 // disc on top and the largest disc on the bottom. The goal is to move all
   9 // of the discs onto the right most peg. The catch is that you are only
  10 // allowed to move one disc at a time and you can never place a larger
  11 // disc on top of a smaller disc.
  12 //
  13 // This implementation starts with NUM_DISC discs and uses a recursive
  14 // algorithm to sovel the puzzle.  The smips-gcc toolchain does not support
  15 // system calls so printf's can only be used on a host system, not on the
  16 // smips processor simulator itself. You should not change anything except
  17 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
  18
  19 int ncores = 1;
  20 #include "util.h"
  21
  22 //--------------------------------------------------------------------------
  23 // Macros
  24
  25 // Set HOST_DEBUG to 1 if you are going to compile this for a host
  26 // machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
  27 // to 0 if you are compiling with the smips-gcc toolchain.
  28
  29 #ifndef HOST_DEBUG
  30 #define HOST_DEBUG 0
  31 #endif
  32
  33 // Set PREALLOCATE to 1 if you want to preallocate the benchmark
  34 // function before starting stats. If you have instruction/data
  35 // caches and you don't want to count the overhead of misses, then
  36 // you will need to use preallocation.
  37
  38 #ifndef PREALLOCATE
  39 #define PREALLOCATE 0
  40 #endif
  41
  42 // Set SET_STATS to 1 if you want to carve out the piece that actually
  43 // does the computation.
  44
  45 #ifndef SET_STATS
  46 #define SET_STATS 0
  47 #endif
  48
  49 // This is the number of discs in the puzzle.
  50
  51 #define NUM_DISCS  7
  52
  53 //--------------------------------------------------------------------------
  54 // Helper functions
  55
  56 void setStats( int enable )
  57 {
  58 #if ( !HOST_DEBUG && SET_STATS )
  59   asm( "mtpcr %0, cr10" : : "r" (enable) );
  60 #endif
  61 }
  62
  63 //--------------------------------------------------------------------------
  64 // List data structure and functions
  65
  66 struct Node
  67 {
  68   int val;
  69   struct Node* next;
  70 };
  71
  72 struct List
  73 {
  74   int size;
  75   struct Node* head;
  76 };
  77
  78 struct List g_nodeFreeList;
  79 struct Node g_nodePool[NUM_DISCS];
  80
  81 int list_getSize( struct List* list )
  82 {
  83   return list->size;
  84 }
  85
  86 void list_init( struct List* list )
  87 {
  88   list->size = 0;
  89   list->head = 0;
  90 }
  91
  92 void list_push( struct List* list, int val )
  93 {
  94   struct Node* newNode;
  95
  96   // Pop the next free node off the free list
  97   newNode = g_nodeFreeList.head;
  98   g_nodeFreeList.head = g_nodeFreeList.head->next;
  99
 100   // Push the new node onto the given list
 101   newNode->next = list->head;
 102   list->head = newNode;
 103
 104   // Assign the value
 105   list->head->val = val;
 106
 107   // Increment size
 108   list->size++;
 109
 110 }
 111
 112 int list_pop( struct List* list )
 113 {
 114   struct Node* freedNode;
 115   int val;
 116
 117   // Get the value from the->head of given list
 118   val = list->head->val;
 119
 120   // Pop the head node off the given list
 121   freedNode = list->head;
 122   list->head = list->head->next;
 123
 124   // Push the freed node onto the free list
 125   freedNode->next = g_nodeFreeList.head;
 126   g_nodeFreeList.head = freedNode;
 127
 128   // Decrement size
 129   list->size--;
 130
 131   return val;
 132 }
 133
 134 void list_clear( struct List* list )
 135 {
 136   while ( list_getSize(list) > 0 )
 137     list_pop(list);
 138 }
 139
 140 //--------------------------------------------------------------------------
 141 // Tower data structure and functions
 142
 143 struct Towers
 144 {
 145   int numDiscs;
 146   int numMoves;
 147   struct List pegA;
 148   struct List pegB;
 149   struct List pegC;
 150 };
 151
 152 void towers_init( struct Towers* this, int n )
 153 {
 154   int i;
 155
 156   this->numDiscs = n;
 157   this->numMoves = 0;
 158
 159   list_init( &(this->pegA) );
 160   list_init( &(this->pegB) );
 161   list_init( &(this->pegC) );
 162
 163   for ( i = 0; i < n; i++ )
 164     list_push( &(this->pegA), n-i );
 165
 166 }
 167
 168 void towers_clear( struct Towers* this )
 169 {
 170
 171   list_clear( &(this->pegA) );
 172   list_clear( &(this->pegB) );
 173   list_clear( &(this->pegC) );
 174
 175   towers_init( this, this->numDiscs );
 176
 177 }
 178
 179 #if HOST_DEBUG
 180 void towers_print( struct Towers* this )
 181 {
 182   struct Node* ptr;
 183   int i, numElements;
 184
 185   printf( "  pegA: " );
 186   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegA))); i++ )
 187     printf( ". " );
 188   for ( ptr = this->pegA.head; ptr != 0; ptr = ptr->next )
 189     printf( "%d ", ptr->val );
 190
 191   printf( "  pegB: " );
 192   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegB))); i++ )
 193     printf( ". " );
 194   for ( ptr = this->pegB.head; ptr != 0; ptr = ptr->next )
 195     printf( "%d ", ptr->val );
 196
 197   printf( "  pegC: " );
 198   for ( i = 0; i < ((this->numDiscs)-list_getSize(&(this->pegC))); i++ )
 199     printf( ". " );
 200   for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next )
 201     printf( "%d ", ptr->val );
 202
 203   printf( "\n" );
 204 }
 205 #endif
 206
 207 void towers_solve_h( struct Towers* this, int n,
 208                      struct List* startPeg,
 209                      struct List* tempPeg,
 210                      struct List* destPeg )
 211 {
 212   int val;
 213
 214   if ( n == 1 ) {
 215 #if HOST_DEBUG
 216     towers_print(this);
 217 #endif
 218     val = list_pop(startPeg);
 219     list_push(destPeg,val);
 220     this->numMoves++;
 221   }
 222   else {
 223     towers_solve_h( this, n-1, startPeg, destPeg,  tempPeg );
 224     towers_solve_h( this, 1,   startPeg, tempPeg,  destPeg );
 225     towers_solve_h( this, n-1, tempPeg,  startPeg, destPeg );
 226   }
 227
 228 }
 229
 230 void towers_solve( struct Towers* this )
 231 {
 232   towers_solve_h( this, this->numDiscs, &(this->pegA), &(this->pegB), &(this->pegC) );
 233 }
 234
 235 int towers_verify( struct Towers* this )
 236 {
 237   struct Node* ptr;
 238   int numDiscs = 0;
 239
 240   if ( list_getSize(&this->pegA) != 0 ) {
 241 #if HOST_DEBUG
 242     printf( "ERROR: Peg A is not empty!\n" );
 243 #endif
 244     return 2;
 245   }
 246
 247   if ( list_getSize(&this->pegB) != 0 ) {
 248 #if HOST_DEBUG
 249     printf( "ERROR: Peg B is not empty!\n" );
 250 #endif
 251     return 3;
 252   }
 253
 254   if ( list_getSize(&this->pegC) != this->numDiscs ) {
 255 #if HOST_DEBUG
 256     printf( " ERROR: Expected %d discs but found only %d discs!\n", \
 257             this->numDiscs, list_getSize(&this->pegC) );
 258 #endif
 259     return 4;
 260   }
 261
 262   for ( ptr = this->pegC.head; ptr != 0; ptr = ptr->next ) {
 263     numDiscs++;
 264     if ( ptr->val != numDiscs ) {
 265 #if HOST_DEBUG
 266       printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
 267               numDiscs, ptr->val );
 268 #endif
 269       return 5;
 270     }
 271   }
 272
 273   if ( this->numMoves != ((1 << this->numDiscs) - 1) ) {
 274 #if HOST_DEBUG
 275     printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
 276             ((1 << this->numDiscs) - 1), this->numMoves );
 277 #endif
 278     return 6;
 279   }
 280
 281   return 1;
 282 }
 283
 284 //--------------------------------------------------------------------------
 285 // Main
 286
 287 int main( int argc, char* argv[] )
 288 {
 289   struct Towers towers;
 290   int i;
 291
 292   // Initialize free list
 293
 294   list_init( &g_nodeFreeList );
 295   g_nodeFreeList.head = &(g_nodePool[0]);
 296   g_nodeFreeList.size = NUM_DISCS;
 297   g_nodePool[NUM_DISCS-1].next = 0;
 298   g_nodePool[NUM_DISCS-1].val = 99;
 299   for ( i = 0; i < (NUM_DISCS-1); i++ ) {
 300     g_nodePool[i].next = &(g_nodePool[i+1]);
 301     g_nodePool[i].val = i;
 302   }
 303
 304   towers_init( &towers, NUM_DISCS );
 305
 306   // If needed we preallocate everything in the caches
 307
 308 #if PREALLOCATE
 309   towers_solve( &towers );
 310 #endif
 311
 312   // Solve it
 313
 314   towers_clear( &towers );
 315   setStats(1);
 316   towers_solve( &towers );
 317   setStats(0);
 318
 319   // Print out the results
 320
 321 #if HOST_DEBUG
 322   towers_print( &towers );
 323 #endif
 324
 325   // Check the results
 326
 327   finishTest( towers_verify( &towers ) );
 328
 329 }
 330