CODEWITHSUNDEEP
arraysloopsfor-loopmipscpu-registers
user3467226
user3467226

Reputation: 81

How to find the minimum value of an array in MIPS

here is my code, I am having trouble getting the correct output. Where am I going wrong?I set min originally to zero, then check if the array is less than or equal to this value and then if it is I jump to a label and make the value of min to be the value of the array, then jump back to iterating the array.

xyz:    .word   -8, 16, -32, 64, -128, 256 

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2  
#   int total   $s3
#   
    .text
    .globl  main
main:
    la  $s0, xyz                # p = foo
    addi    $s1, $s0, 24        # end = p + 6
    add $s3, $zero, $zero       # total = 0 
    add     $s2, $zero, $zero   # min = 0
L1:
    beq $s0, $s1, L2    # if (p == end) goto L2
    lw  $t0, ($s0)      # $t0 = *p
    lw  $t1, ($s2)      # $t1 = min
    slt $t2, $t1, $t0       # check if min is less than p
    add $s3, $s3, $t0       # total += $t0
    bne     $t2, $zero, L3      # if min is less than p, go to L3 
    addi    $s0, $s0, 4     # p++
    j   L1
L2:     
    add $v0, $zero, $zero   # return value from main = 0
    jr  $ra

L3:
    move    $s2, $t0
    j   L1

Upvotes: 6

Views: 13617

Answers (1)

Craig Estey
Craig Estey

Reputation: 33601

Okay, I found several bugs. I've created three versions and I added output syscalls so you can see results [please pardon the gratuitous style cleanup]:

Here is your original code with annotations for the bugs:

    .data
xyz:        .word       -8,16,-32,64,-128,256

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    # NOTE/BUG: to find minimum, you want to init this to the first array
    # element
    # also, initializing with a minimum value (e.g. 0), or more correctly, the
    # largest possible negative number (e.g. 0x80000000) implies a search for
    # maximum
    add     $s2,$zero,$zero         # min = 0

L1:
    beq     $s0,$s1,L2              # if (p == end) goto L2
    lw      $t0,($s0)               # $t0 = *p

    # NOTE/BUG: s2 is a register variable that contains "min" (e.g. int min)
    # and is _not_ a pointer to a "min" variable in memory (e.g. int *min)
    lw      $t1,($s2)               # $t1 = min

    # NOTE/BUG: the the check should be reversed:
    slt     $t2,$t1,$t0             # check if min is less than p
    add     $s3,$s3,$t0             # total += $t0

    bne     $t2,$zero,L3            # if min is less than p, go to L3

    # NOTE/BUG: this pointer increment is out of place (i.e. it does not
    # get incremented if there is a jump to L3)
    # this won't affect the min value, but it will double count the value in
    # the total
    addi    $s0,$s0,4               # p++
    j       L1

L2:
    add     $v0,$zero,$zero         # return value from main = 0
    jr      $ra

L3:
    move    $s2,$t0
    j       L1

Here is a fixed version:

    .data
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    lw      $s2,0($s0)              # min = xyz[0]

L1:
    beq     $s0,$s1,L2              # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    slt     $t2,$t0,$s2             # *p < min?
    bne     $t2,$zero,L3            # yes, fly

    j       L1

L2:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    move    $a0,$s2                 # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall

L3:
    move    $s2,$t0                 # set new/better min value
    j       L1

Here is a slightly more cleaned up version where I reversed the sense of a branch and was able to tighten up the loop a bit. Also, I changed the labels to be more descriptive of role/function:

    .data
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int min     $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    lw      $s2,0($s0)              # min = xyz[0]

main_loop:
    beq     $s0,$s1,main_done       # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    slt     $t2,$s2,$t0             # *p < min?
    bne     $t2,$zero,main_loop     # no, loop

    move    $s2,$t0                 # set new/better min value
    j       main_loop

main_done:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    move    $a0,$s2                 # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall

UPDATE:

thanks that helped a lot, but lw $t1,($s2) doesnt work because lw will only work on pointers?

Right. Notice how you were using s3 to hold total. That's how the code used s2 to hold min. I did this [partly] because of the top comment:

#   int min     $s2

To use the lw, the top comment should have been:

#   int *min    $s2

To use s2 in the original way for this, you'd need something like:

min:    .word    0

And, you'd need (before the loop start):

la    $s2,min

And, you'd have to lw and sw to it, which would only slow things down. So, you'd need to add an extra lw and an extra sw in addition to what's already there.

mips has a lot of registers [its forte]. So, it speeds things up to keep automatic, function scoped variables in them.

However, for completeness, here's a version that allows the lw as you were using it. Notice the extra memory accesses. It's a lot like C code compiled with -O0:

    .data
min:        .word       0
xyz:        .word       -8,16,-32,64,-128,256
msg_min:    .asciiz     "min: "
msg_tot:    .asciiz     " total: "
msg_nl:     .asciiz     "\n"

# int main(void)
#
# local variable    register
#   int *p      $s0
#   int *end    $s1
#   int *min    $s2
#   int total   $s3
#
    .text
    .globl  main

main:
    la      $s0,xyz                 # p = foo
    addi    $s1,$s0,24              # end = p + 6
    add     $s3,$zero,$zero         # total = 0

    la      $s2,min                 # point to min
    lw      $t4,0($s0)              # fetch xyz[0]
    sw      $t4,0($s2)              # store in min

main_loop:
    beq     $s0,$s1,main_done       # if (p == end) goto L2

    lw      $t0,0($s0)              # $t0 = *p
    addi    $s0,$s0,4               # p++

    add     $s3,$s3,$t0             # total += $t0

    lw      $t4,0($s2)              # fetch min
    slt     $t2,$t4,$t0             # *p < min?
    bne     $t2,$zero,main_loop     # no, loop

    sw      $t0,0($s2)              # store new/better min value
    j       main_loop

main_done:
    li      $v0,4
    la      $a0,msg_min
    syscall

    li      $v0,1
    lw      $a0,0($s2)              # get min value
    syscall

    li      $v0,4
    la      $a0,msg_tot
    syscall

    li      $v0,1
    move    $a0,$s3                 # get total value
    syscall

    li      $v0,4
    la      $a0,msg_nl
    syscall

    # exit program
    li      $v0,10
    syscall

Upvotes: 8

Related Questions