Wednesday, January 29, 2020

I wrote this when I got interested in assembler. Pulled from old emails.


#
# This program takes 10 integer values from user,
# inserts them into a binary tree and then prints
# the tree "inorder"
#
#
# The tree_node is like this:
#   struct tree_node {
#       int value;
#       struct tree_node *left;
#       struct tree_node *right;
#    }


.text

#-----------------------------------------------------------
#
# This function prints a given node.
# The nodes pointer is provided in $a0.
#
print_node:
    subu    $sp, $sp, 32            # space on stack
    sw      $ra, 28($sp)            # store the return address
    sw      $fp, 24($sp)            # store the current frame pointer.
    addiu    $fp, $sp, 32           # $fp to start of stack.
   
    move    $t0, $a0                # save the nodes pointer to $t0
    lw      $a0, ($t0)              # move the integer value to $a0.
    jal     print_int_with_newline  # print the integer.
    nop

    lw      $ra, 28($sp)
    lw      $fp, 24($sp)
    addiu   $sp, $sp, 32            # reclaim the stack.

    jr      $ra

#----------------------------------------------------------


# This function prints the given integer and
# then prints a new line after it.
#   $a0 - Integer to be printed.
print_int_with_newline:
    subu    $sp, $sp, 32    #minium stack frame
    sw    $ra, 28($sp)    #store the return address.
    sw    $fp, 24($sp)    #store the frame pointer.
    sw    $a0, 20($sp)    #store the argument.
    addiu    $fp, $sp, 32    #base of the frame.

    #print the integer first.
    li    $v0, 1
    syscall

    #print the new line.
    la    $a0, newline
    li    $v0, 4
    syscall

    #regenerate the previous frame.
    lw    $ra, 28($sp)
    lw    $fp, 24($sp)
    lw    $a0, 20($sp)
    addiu    $sp, $sp, 32    #reclaim the stack frame.

    jr    $ra        #return to caller.

#------------------------------------------------------------

# This function creates a new tree node, assigns a given
# value to it. Initializes it properly and returns the
# pointer to it.
#   $a0 -> Integer to be assigned in value.
#   $v0 -> on success, returns with node pointer here else zero.
#
create_tree_node:
    subu    $sp, $sp, 32
    sw      $ra, 28($sp)
    sw      $fp, 24($sp)
    addiu   $fp, $sp, 32

    move    $t0, $a0
    li      $a0, 12
    li      $v0, 9
    syscall

    beqz    $v0, out_of_memory
   
    sw      $t0, ($v0)
    sw      $zero, 4($v0)
    sw      $zero, 8($v0)

out_of_memory:
    lw      $ra, 28($sp)
    lw      $fp, 24($sp)
    addiu   $sp, $sp, 32

    jr      $ra
#---------------------------------------------------------------

#
# This function gets number of specified integers in the
# given buffer.
#
# $a0 -> Pointer to the destination buffer.
# $a1 -> number of integers to be read out.
#
get_num_integers:
    addiu   $sp, $sp, -32   # min stack.
    sw      $ra, 28($sp)    # store ra
    sw      $fp, 24($sp)    # store callers frame pointer.
    addiu   $fp, $sp, 32    # point to our frame.

    move    $t0, $a0        # destination buffer
    move    $t1, $a1        # number of integers.

read_loop:
    beqz    $t1, read_loop_exit
    addiu   $t1, $t1, -1    # decrement the count

    li      $v0, 5
    syscall

    sw      $v0, ($t0)
    addiu   $t0, $t0, 4     # point to next number(int are 4 bytes)
    b       read_loop
    nop

read_loop_exit:
    lw      $ra, 28($sp)
    lw      $fp, 24($sp)
    addiu   $sp, $sp, 32

    jr     $ra
   

#---------------------------------------------------------------
# This function adds a node to the given node. If it cannot be
# added to the current node, it calls itself recursively until
# it finds a node where it can add the given number.
#
# $a0 -> The starting node
# $a1 -> The node to add.
    .globl add_node_to_tree
add_node_to_tree:
    addiu   $sp, $sp, -32
    sw      $ra, 28($sp)
    sw      $fp, 24($sp)
    sw      $a0, 20($sp)
    sw      $a1, 16($sp)
    addiu   $fp, $sp, 32
   
    lw      $t0, ($a0)   # value of the starting current node.
    lw      $t1, ($a1)   # value of the node to add.

    bgt     $t1, $t0, is_greater
    lw      $t2, 4($a0)  #load the left pointer.
    beqz    $t2, null_left

    move    $a0, $t2     # take this left pointer start loc now.
    jal     add_node_to_tree
    nop

    b       __return_add_node_to_tree
    nop

is_greater:
    lw      $t2, 8($a0)  #load the right pointer.
    beqz    $t2, null_right

    move    $a0, $t2     # take this right pointer start loc now.
    jal     add_node_to_tree
    nop

    b       __return_add_node_to_tree
    nop


null_left: # null left means that we can add the pointer here.
    sw      $a1, 4($a0)
    b       __return_add_node_to_tree
    nop

null_right:
    sw      $a1, 8($a0)
    b       __return_add_node_to_tree
    nop

__return_add_node_to_tree:
    lw      $ra, 28($sp)
    lw      $fp, 24($sp)
    lw      $a0, 20($sp)
    lw      $a1, 16($sp)
    addiu   $sp, $sp, 32
   
    jr     $ra
   
#----------------------------------------------------------------

#
# This function prints the tree in order.
#
# $a0 -> root node.
    .globl print_inorder
print_inorder:
    addiu   $sp, $sp, -32
    sw      $ra, 28($sp)
    sw      $fp, 24($sp)
    sw      $a0, 20($sp)
    addiu   $fp, $sp, 32

    lw      $t1, 4($a0)
    beqz    $t1, print_curr

    move    $a0, $t1
    jal     print_inorder
    nop

print_curr:
    lw      $a0, 20($sp)
    lw      $t0, ($a0)
    move    $a0, $t0
    jal     print_int_with_newline
    nop

    lw      $a0, 20($sp)
    lw      $t1, 8($a0)
    beqz    $t1, __return_print_inorder

    move    $a0, $t1
    jal     print_inorder
    nop

__return_print_inorder:
    lw      $ra, 28($sp)
    lw      $fp, 24($sp)
    lw      $a0, 20($sp)
    addiu   $sp, $sp, 32

    jr      $ra
#------------------------------------------------------------------

main:
    # readout 10 integers in buffer.
    la      $a0, buffer 
    li      $a1, 10
    jal     get_num_integers
    nop

    li      $t6, 10
    la      $t8, buffer
    li      $t7, 0

tree_create_loop:
    beqz    $t6, tree_create_done
    addiu   $t6, $t6, -1
    lw      $a0, ($t8)
    jal     create_tree_node
    addiu   $t8, $t8, 4         #point to next number

    beqz    $v0, alloc_failed
    nop

    beqz    $t7, init_root
    move    $a1, $v0
    move    $a0, $t7

    jal     add_node_to_tree
    nop

    b       tree_create_loop
    nop

init_root:
    move    $t7, $v0
    b       tree_create_loop
    nop
   
   
tree_create_done:
    move    $a0, $t7
    jal     print_inorder
    nop
   
    b       exit
    nop
   
alloc_failed:
    la      $a0, OOM_Error
    li      $v0, 4
    syscall

exit:
    li      $v0, 10
    syscall

   
.data
buffer: .space 1024
OOM_Error: .asciiz "Out of memory!\n"
newline: .asciiz "\n"



No comments:

Post a Comment