1 //**************************************************************************
2 // Towers of Hanoi benchmark
3 //--------------------------------------------------------------------------
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.
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.
19 //--------------------------------------------------------------------------
22 // Set HOST_DEBUG to 1 if you are going to compile this for a host
23 // machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
24 // to 0 if you are compiling with the smips-gcc toolchain.
30 // Set PREALLOCATE to 1 if you want to preallocate the benchmark
31 // function before starting stats. If you have instruction/data
32 // caches and you don't want to count the overhead of misses, then
33 // you will need to use preallocation.
39 // Set SET_STATS to 1 if you want to carve out the piece that actually
40 // does the computation.
46 // This is the number of discs in the puzzle.
50 //--------------------------------------------------------------------------
53 void finishTest( int toHostValue
)
56 if ( toHostValue
== 1 )
57 printf( "*** PASSED ***\n" );
59 printf( "*** FAILED *** (tohost = %d)\n", toHostValue
);
62 asm( "mtpcr %0, tohost" : : "r" (toHostValue
) );
67 void setStats( int enable
)
69 #if ( !HOST_DEBUG && SET_STATS )
70 asm( "mtpcr %0, cr10" : : "r" (enable
) );
74 //--------------------------------------------------------------------------
75 // List data structure and functions
89 struct List g_nodeFreeList
;
90 struct Node g_nodePool
[NUM_DISCS
];
92 int list_getSize( struct List
* list
)
97 void list_init( struct List
* list
)
103 void list_push( struct List
* list
, int val
)
105 struct Node
* newNode
;
107 // Pop the next free node off the free list
108 newNode
= g_nodeFreeList
.head
;
109 g_nodeFreeList
.head
= g_nodeFreeList
.head
->next
;
111 // Push the new node onto the given list
112 newNode
->next
= list
->head
;
113 list
->head
= newNode
;
116 list
->head
->val
= val
;
123 int list_pop( struct List
* list
)
125 struct Node
* freedNode
;
128 // Get the value from the->head of given list
129 val
= list
->head
->val
;
131 // Pop the head node off the given list
132 freedNode
= list
->head
;
133 list
->head
= list
->head
->next
;
135 // Push the freed node onto the free list
136 freedNode
->next
= g_nodeFreeList
.head
;
137 g_nodeFreeList
.head
= freedNode
;
145 void list_clear( struct List
* list
)
147 while ( list_getSize(list
) > 0 )
151 //--------------------------------------------------------------------------
152 // Tower data structure and functions
163 void towers_init( struct Towers
* this, int n
)
170 list_init( &(this->pegA
) );
171 list_init( &(this->pegB
) );
172 list_init( &(this->pegC
) );
174 for ( i
= 0; i
< n
; i
++ )
175 list_push( &(this->pegA
), n
-i
);
179 void towers_clear( struct Towers
* this )
182 list_clear( &(this->pegA
) );
183 list_clear( &(this->pegB
) );
184 list_clear( &(this->pegC
) );
186 towers_init( this, this->numDiscs
);
191 void towers_print( struct Towers
* this )
197 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegA
))); i
++ )
199 for ( ptr
= this->pegA
.head
; ptr
!= 0; ptr
= ptr
->next
)
200 printf( "%d ", ptr
->val
);
203 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegB
))); i
++ )
205 for ( ptr
= this->pegB
.head
; ptr
!= 0; ptr
= ptr
->next
)
206 printf( "%d ", ptr
->val
);
209 for ( i
= 0; i
< ((this->numDiscs
)-list_getSize(&(this->pegC
))); i
++ )
211 for ( ptr
= this->pegC
.head
; ptr
!= 0; ptr
= ptr
->next
)
212 printf( "%d ", ptr
->val
);
218 void towers_solve_h( struct Towers
* this, int n
,
219 struct List
* startPeg
,
220 struct List
* tempPeg
,
221 struct List
* destPeg
)
229 val
= list_pop(startPeg
);
230 list_push(destPeg
,val
);
234 towers_solve_h( this, n
-1, startPeg
, destPeg
, tempPeg
);
235 towers_solve_h( this, 1, startPeg
, tempPeg
, destPeg
);
236 towers_solve_h( this, n
-1, tempPeg
, startPeg
, destPeg
);
241 void towers_solve( struct Towers
* this )
243 towers_solve_h( this, this->numDiscs
, &(this->pegA
), &(this->pegB
), &(this->pegC
) );
246 int towers_verify( struct Towers
* this )
251 if ( list_getSize(&this->pegA
) != 0 ) {
253 printf( "ERROR: Peg A is not empty!\n" );
258 if ( list_getSize(&this->pegB
) != 0 ) {
260 printf( "ERROR: Peg B is not empty!\n" );
265 if ( list_getSize(&this->pegC
) != this->numDiscs
) {
267 printf( " ERROR: Expected %d discs but found only %d discs!\n", \
268 this->numDiscs
, list_getSize(&this->pegC
) );
273 for ( ptr
= this->pegC
.head
; ptr
!= 0; ptr
= ptr
->next
) {
275 if ( ptr
->val
!= numDiscs
) {
277 printf( " ERROR: Expecting disc %d on peg C but found disc %d instead!\n", \
278 numDiscs
, ptr
->val
);
284 if ( this->numMoves
!= ((1 << this->numDiscs
) - 1) ) {
286 printf( " ERROR: Expecting %d num moves but found %d instead!\n", \
287 ((1 << this->numDiscs
) - 1), this->numMoves
);
295 //--------------------------------------------------------------------------
298 int main( int argc
, char* argv
[] )
300 struct Towers towers
;
303 // Initialize free list
305 list_init( &g_nodeFreeList
);
306 g_nodeFreeList
.head
= &(g_nodePool
[0]);
307 g_nodeFreeList
.size
= NUM_DISCS
;
308 g_nodePool
[NUM_DISCS
-1].next
= 0;
309 g_nodePool
[NUM_DISCS
-1].val
= 99;
310 for ( i
= 0; i
< (NUM_DISCS
-1); i
++ ) {
311 g_nodePool
[i
].next
= &(g_nodePool
[i
+1]);
312 g_nodePool
[i
].val
= i
;
315 towers_init( &towers
, NUM_DISCS
);
317 // If needed we preallocate everything in the caches
320 towers_solve( &towers
);
325 towers_clear( &towers
);
327 towers_solve( &towers
);
330 // Print out the results
333 towers_print( &towers
);
338 finishTest( towers_verify( &towers
) );