# Program: Bubble sort
# Language: MIPS Assembly (32-bit)
# Arguments: 5 unordered numbers stored in $2 ~ $6 reg
# Author: brant-ruan
# Date: 2016-03-10
# IDE: MARS 4.5
# P.S.
#   This program is one of my homework and the number of assembly instructions allowed is just 31.
#   If I can use all the instructions of MIPS, optimizations will be considered.
#   (E.g. The index() function should have been not necessary)
# Minds:
#   It is not a good idea to store numbers from reg to mem. However, if using reg to sort directly,
#   the program will be ridiculous for the regs can't be indexed as an array(Can they ?).
#  My friend told me another brilliant idea that there's no need to swap $2 and $3, you can just store them to mem in the right order!!! Thanks!
######################################################################################################
.data
.word
array:  0, 0, 0, 0, 0
.text
# initialize $2 ~ $6
    xor $2, $2, $2
    xor $3, $3, $3
    xor $4, $4, $4
    xor $5, $5, $5
    xor $6, $6, $6
    add $2, $2, 7
    add $3, $3, 4
    add $4, $4, 8
    add $5, $5, 13
    add $6, $6, 2
# store values to be sorted into mem
    sw $2, array+0
    sw $3, array+4
    sw $4, array+8
    sw $5, array+12
    sw $6, array+16

    xor $5, $5, $5  # i
    xor $6, $6, $6  # j
    xor $7, $7, $7  # max_num
    add $7, $7, 4   # max_num = 5 - 1 (the number of elements minus 1)
    j begin
###############################################################################
# Sort procedure
sort:
    # prototype: sort($2, $3)
    # if $2 > $3 then swap($2, $3) else return
    slt $4, $3, $2  # $4 is flag
    beq $4, 0, sort_ret_src
    xor $2, $2, $3
    xor $3, $2, $3
    xor $2, $2, $3
sort_ret_src:
    j sort_ret_dst
###############################################################################
# Generate index procedure
index:
    # For the data-type is word, we should generate 4*j as index
    # prototype: index($12)
    # if $30 is 0, store valid index in $9 and return to load_0, else store in $11 and return to load_1
    xor $31, $31, $31     # count
    xor $29, $29, $29     # valid index which will be returned
multiply:
    beq $12, $31, ret     # if count == $12, return
    add $29, $29, 4       #  $29 += 4
    add $31, $31, 1       #  count++
    j multiply
ret:
    beq $30, 1, ret_1     # judge return where
ret_0:
    xor $9, $9, $9
    add $9, $9, $29
    j load_0
ret_1:
    xor $11, $11, $11
    add $11, $11, $29
    j load_1
###############################################################################
begin:
    beq $5, $7, end     # if i == max_num, go to end
    xor $10, $10, $10
    add $10, $6, 1      # $10 is j+1
    xor $12, $12, $12   # $12 is parameter of 'index' function
    add $12, $12, $6    # deliver $6 (j) to $12
    xor $30, $30, $30   # tell index() to return to load_0
    j index
load_0:
    lw  $2, array($9)   # load array[j] to $2 ($9 is index of j)
    xor $12, $12, $12
    add $12, $12, $10   # deliver $10 (j+1) to $12
    xor $30, $30, $30
    add $30, $30, 1     # tell index() to return to load_1
    j index
load_1:
    lw  $3, array($11)  # load array[j+1] to $3 ($11 is index of j+1)
    j sort
sort_ret_dst:
    sw  $2, array($9)   # store $2 into array[j]
    sw  $3, array($11)  # store $3 into array[j+1]
    add $6, $6, 1       # j++
    sub $8, $7, $5      # $8 is (max_num - i)
    bne $6, $8, next    # if j < max_num-i, go to next
    add $5, $5, 1       # i++
    xor $6, $6, $6      # j = 0
next:
    j begin
end:
# reload sorted array to $2 ~ $6
    lw $2, array+0
    lw $3, array+4
    lw $4, array+8
    lw $5, array+12
    lw $6, array+16