Brians Blog

.data

dim:
#.word 2
#.word 3
#.word 4
.word 5
#.word 10

matrix:
#2x2-Martrix; solution = -2
#.word 3, 4, 5, 6
#3x3-Matrixx; solution = 4
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2
#4x4-Matrix; solution = -19
#.word 3, 4, 5, 9, 4, 9, 1, 2, 2, 1, 3, 5, 7, 9, 3, 5
#solution = 0
.word 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
#.word -2, 1, 1, -2, -1, -1, -1, 3, -2, -3, 0, -1, -1, -4, -5, -5, 3, 2, -4, 1, 1, 1, 0, 3, 2, 0, 3, 3, 2, 0, 2, -3, 0, -1, 4, -1, -2, -3, 0, -1, 2, -3, -3, -5, -3, -5, -3, -1, -5, 3, 0, -5, 0, -5, -5, -1,  2,  1, -4, -1, -5, -4,  1,  1, -4,  2,  3,  4, -3, -1, 1, -2,  0, -3,  1, -5,  4,  3, -1, -4, -5,  2, -5, -2, -3, -3,  3, -2,  1, -3, 1, -1, -3,  2,  0, -5,  3,  2,  3, -5

det:    .asciiz "Die Determinante ist: "
###############################################################################

.text

main:
###################################
###################################
#Hier soll das Programm stehen
#Das Ergebnis muss am Ende in $s6 stehen.

    addi    $s7, $0, 0x10040000 # initialize default heap pointer
 
    la      $a0, matrix
    lw      $a1, dim
    jal     calcDet
    addi    $s6, $v0, 0

    j       ende

###################################
# Calculates the determinante of a NxN matrix.
# expects:  adress of array with N^2 elements in $a0
#           dimension of matrix in $a1
# returns det. of given matrix in $v0
###################################
# Documentation
# $a0   -> matrix
# $a1   -> dim
# ----------------
# $s0   -> sum of det. of matrixes
calcDet:
    # if
    slti    $t0, $a1, 2         # if $a1(=dim) < 2
    beq     $0, $t0, calcDetIf  # jump to the if part
                                # if $t0 == $t1(=1) or
                                # if 2 < dim
    # else
    lw      $v0, 0($a0)
    jr      $ra                 # jump back to caller

calcDetIf:                      # The if part
    # reduce maxtrix and call recursive for each
    # reduced matrix
    addi    $sp, $sp, -4        # get some space on stack
    sw      $ra, 0($sp)         # store return adress in stack
   
    addi    $s0, $0, 0          # initialize $s0 (sum) with 0
    addi    $t0, $0, 0          # initialize $t0 (i) with 0
   
calcDetLoop:                    # loop over all sub-matrixes
    beq     $t0, $a1, calcDetLoopDone
                                # while $t0(=i) != $a1(=dim)

    addi    $sp, $sp, -16       # get some space on stack
    sw      $s0, 0($sp)         # store sum
    sw      $t0, 4($sp)         # store $t0 (i)
    sw      $a0, 8($sp)         # store $a0
    sw      $a1, 12($sp)        # store $a1

                                # dont need to copy any adress
                                # in $a0 because its already there
                                # dont need to copy any dimension
                                # of matrix in $a1 because its already there
    addi    $a2, $t0, 0         # copy i into $a2
    jal     reduceMatrix        # jump to reduceMatrix
   
    addi    $a0, $v0, 0         # copy result adress of reduceMatrix
                                # into argument register for recursive call
    sub     $a1, $a1, 1         # $a1 = dim - 1
    jal     calcDet             # call myself recursively
   
    lw      $a1, 12($sp)        # load $a1
    lw      $a0, 8($sp)         # load $a0
    lw      $t0, 4($sp)         # load $t0 (i)
    lw      $s0, 0($sp)         # load sum
    addi    $sp, $sp, 16        # clean up the stack

    addi    $t2, $0, 1          # initialise pow(er) with 1
    and     $t1, $t0, 1         # $t1 = $t0 & 0x00000001
    beq     $t1, $0, calcDetLoopJump
                                # skip one line, if $t0 % 2 = 1
    addi    $t2, $0, -1         # set power to -1
calcDetLoopJump:               

    addi    $t1, $0, 4          # $t1 = 4 (because one word = 4 bytes)
    mult    $t0, $t1            # i * $t1(=4)
    mflo    $t3                 # get result in $t3
    add     $t3, $a0, $t3       # add calulated offset to start adress of matrix
    lw      $t3, 0($t3)         # load value at calulated adress

    mult    $t2, $t3            # power * (i-th element in matrx (always in first row))
    mflo    $t4                 # get result in $t4
    mult    $t4, $v0            # multiply calcDet-result with calculated stuff
    mflo    $t4                 # get result in $t4
    add     $s0, $s0, $t4       # add to sum

    addi    $t0, $t0, 1         # $t0++ or i++

    j       calcDetLoop


calcDetLoopDone:                # loop finished, calculated all matrixes
    addi    $v0, $s0, 0         # copy sum into return register

    lw      $ra, 0($sp)         # load return adress from stack
    addi    $sp, $sp, 4         # get some space on stack

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


###################################
# Extracts _one_ (N-1) matrix from a
# NxN matrix. The argument
# $a2 says which (N-1) matrix should
# be returned.
# expects:  adress of array with N^2 elements in $a0
#           dimension of matrix in $a1
#           index of the smaller matrix (0-based) in $a2
# returns adress of (N-1) matrix in $v0
###################################
# Documentation
# $a0   -> matrix
# $a1   -> dim
# $a2   -> index of matrix that should be returned
# ----------------
# $s0   -> dim - 1
# $s1   -> counter for the current position in the SOURCE matrix
# $s2   -> counter for the current position in the TARGET matrix
reduceMatrix:
    addi    $s0, $a1, -1        # $s0 = dim - 1
    mult    $s0, $s0            # $s0*$s0 or
                                # (N-1)^2 or (dim-1)^2
                                # is also the size of the
                                # new matrix
    mflo    $t1                 # get result into $t1
                                # $t1 contains now the number of words required
    addi    $s1, $a0, 0         # copy start adress of source matrix in $s1
    addi    $s2, $s7, 0         # save current position of heap pointer in $s2
    addi    $v0, $s7, 0         # copy target array adress in return register
    addi    $t0, $0, 4          # set $t0 = 4
    mult    $t1, $t0            # multiply $t0(=4) * $t1(=(dim-1)^2)
                                # -> amount of necessary bytes
    mflo    $t0                 # copy result in $t0
    add     $s7, $s7, $t0       # get (N-1)^2 space of heap

    addi    $t0, $0, 4          # set $t0 = 4
    mult    $a1, $t0            # $a1(=dim)*$t0(=4)
                                # number of bytes that must be skipped to
                                # skip the first row of source matrix
    mflo    $t0
    add     $s1, $s1, $t0       # skip dim-elements or
                                # skip the first row of source matrix
    addi    $t0, $s0, 0         # initialize counter for loop 1; used as i
    add     $t2, $t0, $a2       # $t2 = $t0 + $a2 or
                                # $t2 = i + index
reduceMatrixLoop1:              # loop 1
    beq     $t2, $t0, reduceMatrixLoop1Done
                                # while index != i

    lw      $t1, 0($s1)         # load next entry from source matrix in $t1
    sw      $t1, 0($s2)         # store the entry in the target matrix
    addi    $s1, $s1, 4         # increase pointer $s1 = $s1 + 4
    addi    $s2, $s2, 4         # increase pointer $s2 = $s2 + 4

    addi    $t0, $t0, 1         # $t0 = $t0 + 1 or
                                # $t0++ (i++)
    j       reduceMatrixLoop1   # jump up to the beginning of the loop
reduceMatrixLoop1Done:          # endloop 1
reduceMatrixLoop2:              # loop 2
    mult    $a1, $a1
    mflo    $t1
    beq     $t0, $t1, reduceMatrixLoop2Done
                                # while i < dim^2

    addi    $s1, $s1, 4         # skip one element in SOURCE matrix
    addi    $t0, $t0, 1         # $t0 = $t0 + 1 or
                                # $t0++ or i++
   
    mult    $a1, $a1            # $a1^2 or dim^2
    mflo    $t2                 # get the result in $t2
    sub     $t2, $t2, 1         # sub 1 from $t2, because I want to compare
                                # it with $t0 (0-based) or
                                # (dim^2)-1
    sub     $t2, $t2, $t0       # $t2-$t0 or (dim^2)-1-i
    # if
    slt     $t3, $t2, $s0       # (dim^2)-1-i < dim-1 or
                                # if $t3 == 1, you reached the last
                                # row and already skipped
    beq     $t3, $0, reduceMatrixLoop2Else
                                # jumps, if (dim-1)^2 - i < dim - 1 is false
                                # in human words: if the programm
                                # is NOT in the last row of the source matrix
    # if case
    # copy the last elements of source into target and exit function! :)
    mult    $a1, $a1            # dim^2
    mflo    $t2                 # get result in $t2
reduceMatrixLoop2Loop1:
    beq     $t2, $t0, reduceMatrixLoop2Done
                                # jump if dim^2-1 == i or jump if
                                # end of source matrix is reached
   
    lw      $t1, 0($s1)         # load next entry from source matrix in $t1
    sw      $t1, 0($s2)         # store the entry in the target matrix
    addi    $s1, $s1, 4         # increase pointer $s1 = $s1 + 4
    addi    $s2, $s2, 4         # increase pointer $s2 = $s2 + 4

    addi    $t0, $t0, 1         # $t0 = $t0 + 1 or
                                # $t0++ or i++
    j       reduceMatrixLoop2Loop1
                                # jump up again, because its a loop!

    j       reduceMatrixLoop2Endif
                                # leave if case
                                # never used because if loop is finished
                                # it will jump to the end of the function

reduceMatrixLoop2Else:          # else case
    # copy dim - 1 elements
    add     $t2, $t0, $s0       # $t2 = $t0(=i) + $s0(=dim-1)
reduceMatrixLoop2ElseLoop:
    beq     $t2, $t0, reduceMatrixLoop2
                                # if $t2 = $t0 jump to main loop

    lw      $t1, 0($s1)         # load next entry from source matrix in $t1
    sw      $t1, 0($s2)         # store the entry in the target matrix
    addi    $s1, $s1, 4         # increase pointer $s1 = $s1 + 4
    addi    $s2, $s2, 4         # increase pointer $s2 = $s2 + 4
   
    addi    $t0, $t0, 1         # $t0 = $t0 + 1 or
                                # $t0++ or i++
    j       reduceMatrixLoop2ElseLoop
                                # jump up to the beginning of the loop

reduceMatrixLoop2Endif:         # endif


    addi    $t0, $t0, 1         # $t0 = $t0 + 1 or
                                # $t0++ or i++
    j       reduceMatrixLoop2   # jump up to the beginning of the loop
reduceMatrixLoop2Done:          # endloop 2
    jr      $ra                 # jump to caller function
                                # return value ($v0) is set at beginning
                                # of this function
###################################

###################################
###################################

ende:
#Ausgabe

la $a0 det
li $v0 4
syscall

move $a0, $s6
li $v0, 1
syscall

###################################
#Ende
li $v0, 10
syscall