How to find the minimum value of an array in MIPS
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
user3467226
Updated on June 21, 2022Comments
-
user3467226 almost 2 years
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-
user4759923 almost 8 yearsWhy are you programming in assembly?
-
Craig Estey almost 8 yearsYour title says you want the min value of the array, but your code is structured to get the max value [along with some bugs]. Which value do you want (min=-128 or max=256)? -
user3467226 almost 8 yearsohhh, I am trying to get the min. What did I do to get the max instead of min?
-
Craig Estey almost 8 yearsI've been prepping an answer, which I'll post soon that will annotate such things [and the 4 other bugs I found] and I'll provide a fixed version. However, a simple
sltdoesn't handle negative numbers too well because it treats the numbers as unsigned. Are you required to do negative values? -
user3467226 almost 8 yearsyes, negatives are vital as I need to learn how to treat them in MIPS. so you are saying that slt is treating -128 as 128 ?
-
Craig Estey almost 8 yearsOops, my bad.
sltis the signed version [there is ansltufor unsigned]. I'm just not [yet] getting the expected result, so keep your fingers crossed ...
-
-
user3467226 almost 8 yearsthanks that helped a lot, but lw $t1,($s2) doesnt work because lw will only work on pointers?
