kernelthread.com

MIPS Assembly

The Towers of Hanoi in MIPS Assembly language.

Quoted from MIPS Technologies' home page:

Did you know...?
If you have a digital cable set-top box, chances are it's MIPS-based.
If you have a video game console, it's probably MIPS-based.
Your email very likely travels through a MIPS-based Cisco router.
Your company's laser printers are probably powered by 64-bit MIPS-based processors.

# # The Towers Of Hanoi # MIPS Assembly Language # Copyright (C) 1998 Amit Singh. All Rights Reserved. # http://hanoi.kernelthread.com # # Tested under the SPIM MIPS simulator # The code is somewhat verbose - I was a chirpy youngster # when I wrote this many years back ... see the comments # (blush) Hey, this assembler code even contains a little # history of Hanoi! # -- Unabridged from here on -- .data #-------------------------------------------------------------- # A lot of 'text' has been used ... # This is an effort to achive user friendliness ... # author: .asciiz "\tAuthored by Amit Singh\n" c1: .asciiz "\n\tThis program tries to do what one can\n" c2: .asciiz "\tdo with ease in a high level language.\n" c3: .asciiz "\tBut, to be competent (in terms of ease) with\n" c4: .asciiz "\ta HLL is a requirement that is almost\n" c5: .asciiz "\talways NOT there while using assembly language.\n" c6: .asciiz "\tAssembly language is generally meant for\n" c7: .asciiz "\tcode that has to be very fast and / or it is\n" c8: .asciiz "\tnot possible to write the code in a HLL. This\n" c9: .asciiz "\tprogram tries issues like bailing out on / handling\n" c10: .asciiz "\tbad input, a (primitive) user interface, menus (!)\n" c11: .asciiz "\timplementing stacks, handling memory & in a nutshell\n" c12: .asciiz "\ttries to emulate the HLLs. Please do note that\n" c13: .asciiz "\tthis is * Unstructured Programming * at work ...!!\n\n" copyr: .asciiz "\t### SPIM_Hanoi DEMO (C) 1996 Amit Singh %\n" endmsg: .asciiz "quitting...\n" err_msg: .asciiz "SPIM_Hanoi> This number should be > 0 and <= " h00: .asciiz "\t 0x1: Show the history behind Towers of Hanoi\n" h01: .asciiz "\t 0x2: Show the concepts demonstrated by this program\n" h02: .asciiz "\t 0x3: Quit Immediately\n" h03: .asciiz "\t 0x4: Proceed to the program right away (the default)\n" h04: .asciiz "\n\tEnter a number (1/2/3) or simply press enter : " h1: .asciiz "# The Towers Of Hanoi : the history behind the puzzle. #\n" h2: .asciiz "# The puzzle is called `Towers of Hanoi' because an early #\n" h3: .asciiz "# popular presentation wove a fanciful legend around it. #\n" h4: .asciiz "# According to this myth, uttered long before the Vietnam #\n" h5: .asciiz "# war, there is a Buddhist monastery at Hanoi which #\n" h6: .asciiz "# contains a large room with three time-worn posts in it #\n" h7: .asciiz "# surrounded by 21 golden disks. Monks, acting out the #\n" h8: .asciiz "# command of an ancient prophecy, have been moving these #\n" h9: .asciiz "# disks, in accordance with the rules of the puzzle, once #\n" h10: .asciiz "# every day since the monastry was founded over a thousand #\n" h11: .asciiz "# years ago. They are said to believe that when the last #\n" h12: .asciiz "# move of the puzzle is completed world will end in a clap #\n" h13: .asciiz "# of thunder. Fortunately, they are nowhere even close to #\n" h14: .asciiz "# being done ... #\n" h15: .asciiz "# Information courtesy Damon Anton Permezel #\n" howmany: .asciiz "\nSPIM_Hanoi> How many disks (be reasonable) ? " newl: .asciiz "\n" menutitle:.asciiz "\n\t\t\tO P T I O N S\n" over_msg: .asciiz "\t\tSPIM_Hanoi> Overflow .. Too many disks ..\n" quit_1msg:.asciiz "\nSPIM_Hanoi> All the disks transferred ! (What??)\n" quit_2msg:.asciiz "quitting...\n" row: .asciiz "#--------------------------------------------\n" title: .asciiz "\n\tThe Towers Of Hanoi (MIPS asm)\n" to_1msg: .asciiz "\tmoved top disk from Tower " to_2msg: .asciiz " -> " under_msg:.asciiz "SPIM_Hanoi> Underflow .. Too few disks ..\n" .text .globl main # main: move $s0,$ra # Return address li $v1,5 # Limit on the maximum # number of disks #------display titles etc-------# li $v0,4 # Print string la $a0,title # Show the title syscall # la $a0,copyr # Yes, a (what!) copyright syscall # la $a0,author # Modesty ... syscall # menu_on: la $a0,menutitle # a'la Microsoft Windows ! syscall # la $a0,h00 # Want to know the story ? syscall # la $a0,h01 # Options galore ! syscall # la $a0,h02 # syscall # la $a0,h03 # Defaults too ... syscall # la $a0,h04 # syscall # li $v0,5 # Get the response syscall # beq $v0,1,showhist # beq $v0,2,showconcept # beq $v0,3,quit # j noshow showhist: li $v0,4 # Begin printing the la $a0,row # history stuff ... syscall # #----------------lots and lots of strings---------------- la $a0,h1 syscall la $a0,row syscall la $a0,h2 syscall la $a0,h3 syscall la $a0,h4 syscall la $a0,h5 syscall la $a0,h6 syscall la $a0,h7 syscall la $a0,h8 syscall la $a0,h9 syscall la $a0,h10 syscall la $a0,h11 syscall la $a0,h12 syscall la $a0,row syscall la $a0,h13 syscall la $a0,row syscall la $a0,newl syscall j menu_on showconcept: li $v0,4 la $a0,row syscall la $a0,c1 syscall la $a0,c2 syscall la $a0,c3 syscall la $a0,c4 syscall la $a0,c5 syscall la $a0,c6 syscall la $a0,c7 syscall la $a0,c8 syscall la $a0,c9 syscall la $a0,c10 syscall la $a0,c11 syscall la $a0,c12 syscall la $a0,c13 syscall j menu_on #----------------exhausted all the strings--------------- noshow: #------read input---------------# li $v0,4 # Begin the serious stuff la $a0,howmany # Query for number of disks syscall # li $v0,5 # Read Integer syscall # #------data out of bounds-------# bgt $v0,$v1,overflow # error_check ble $v0,$zero,underflow # error_check #------the 's' registers--------# li $s1,1 # Boolean Variable li $s2,0x10000000 # Stack start address li $s3,0 # Stack top move $s4,$v0 # holds 'howmany disks' li $s5,1 # 'from' Tower li $s6,3 # 'to' Tower li $s7,2 # 'intermediate' Tower #------initialization ends------# li $v0,4 # la $a0,newl # syscall # simulate: beq $s4,1,continue # High Level language simulator bne $s4,1,next # continue: li $v0,4 # la $a0,to_1msg # syscall # li $v0,1 # move $a0,$s5 # syscall # li $v0,4 # la $a0,to_2msg # syscall # li $v0,1 # move $a0,$s6 # syscall # li $v0,4 # la $a0,newl # syscall # beq $s3,$zero,und_true # bne $s3,$zero,und_false # und_true: li $s1,1 # j sub_next # und_false: li $s1,0 # sub $s3,$s3,1 # move $t1,$s3 # mul $t1,$t1,16 # beq $s3,0,inadd_4 # bne $s3,0,iadd_4 # iadd_4: addi $t1,$t1,4 # inadd_4: add $t1,$t1,$s2 # lw $s4,($t1) # addi $t1,$t1,4 # lw $s5,($t1) # addi $t1,$t1,4 # lw $s6,($t1) # addi $t1,$t1,4 # lw $s7,($t1) # sub_next: beq $s1,1,first_call # bne $s1,1,second_call # next: mul $t1,$s3,16 # Calculate stack address beq $s3,0,nadd_4 # Do we have to add 4 ? No bne $s3,0,add_4 # We have to add 4 add_4: addi $t1,$t1,4 # j skip # nadd_4: j skip # skip: addi $s3,$s3,1 # add $t1,$t1,$s2 # sw $s4,($t1) # addi $t1,$t1,4 # sw $s5,($t1) # addi $t1,$t1,4 # sw $s6,($t1) # addi $t1,$t1,4 # sw $s7,($t1) # move $t6,$s6 # sub $s4,$s4,1 # move $s6,$s7 # move $s7,$t6 # j simulate # second_call: li $v0,4 # Time to give some output la $a0,to_1msg # Print steps ... syscall # li $v0,1 # move $a0,$s5 # syscall # li $v0,4 # la $a0,to_2msg # still printing steps ... syscall # li $v0,1 # move $a0,$s6 # syscall # li $v0,4 # la $a0,newl # printing done ... syscall # move $t4,$s4 # Update registers ... move $t5,$s5 # $t4, $t5, $t6 provide move $t6,$s6 # temporary storage here ... move $t7,$s7 # sub $t4,$t4,1 # Silly jugglery ... move $s4,$t4 # Move a number here ... move $s5,$t7 # Another there ... move $s7,$t5 # We are through ... j simulate # Back to where we came from first_call: li $v0,4 # Print string la $a0,quit_1msg # syscall # j done # overflow: li $v0,4 # Print string la $a0,over_msg # error string syscall # j call_err_msg # Exit .. error underflow: li $v0,4 # la $a0,under_msg # Error string syscall # j call_err_msg # Exit .. error call_err_msg: la $a0,err_msg # syscall # li $v0,1 # move $a0,$v1 # syscall # li $v0,4 # la $a0,newl # syscall # j quit # done: j quit # Enough ... quit: li $v0,4 la $a0,quit_2msg # Quit with decency syscall # move $ra,$s0 # Return address jr $31 # That's all

Download

hanoi.spi