Hi there,
I need to implement in assembly mips an iterative binary search method.
Here's my code:
# this program implements binary search
# the equivalent pseudo code is the following:
# first = 0
# last = size -1
# while (last - first > 1) {
# mid = (last-first)/2 + first
# if A[mid] == val
# break;
# if A[mid] > val
# last = mid;
# continue
# else
# first = mid;
# continue;
# }
#-----------------------------------------------------
.data 0x10000000
size: .word 0x0000000a # array size
.data 0x10000004
search: .word 0x0000000d # search term
.data 0x10000008
result: .word 0xffffffff # result = -1
.data 0x10000100
array: .word 0x00000001 # the array
.word 0x00000005
.word 0x00000007
.word 0x00000009
.word 0x0000000b
.word 0x0000000d
.word 0x00000010
.word 0x00004000
.word 0x00050000
.word 0x00700000
.text 0x0400000
main:
sw $t0, 0 # $t0 = 0, that's our "first" pointer
sw $t1, size # $t1 - size
addi $t1, $t1, -1 # $t1 = size - 1, our "last" pointer
j condition # goto condition
nop
condition:
sub $t2, $t1, $t0 # $t2 = last - first
bgt $t2, 1, while # if ($t2 > 1) goto while
nop
j exit # if not, goto exit
nop
while:
div $t3, $t2, 2 # $t3 = (last - first) / 2
add $t3, $t3, $t0 # $t3 = t3 + first
lw $t5, array($t3) # $t5 = array($t3)
lw $t6, result # $t6 = result
beq $t6, $t5, found # if value found, goto found
nop
bgt $t5, $t6, isGreater # if array[$t3] > result, goto isGreater
nop
addi $t0, $t3, 0 # else, first = mid
j condition # check the condition and start over the loop
found:
sw $t3, result # result = $t3
j exit # goto exit
nop
isGreater:
addi $t1, $t3, 0 # else, last = mid
j condition # check the condition and start over the loop
exit: sw $t4, 4($t6) # result = $t4
j end # jump to end
nop
end: j end # internal loop to end the program
however when I try to run it I get errors of bad data.
Any ideas?
It looks like there are some errors in your code. For example, in the while loop, you are using the wrong register for the result. You should be using $t4 instead of $t6. Also, in the isGreater section, you are using the wrong register for the last pointer. You should be using $t1 instead of $t3. Additionally, you should be using the sw instruction to store the result in the result variable instead of the sw instruction in the exit section. Finally, you should be using the bne instruction instead of the beq instruction in the found section.
I hope this helps!
Based on the code you provided, it seems there are a few issues that could be causing the "bad data" errors:
1. Memory allocation for data: In MIPS assembly, data should be allocated using the `.data` directive followed by a label. In your code, you are allocating memory using `$t0` and `$t1` registers instead of labels. Update the data section as follows:
```assembly
.data
size: .word 0x0000000a # array size
search: .word 0x0000000d # search term
result: .word 0xffffffff # result = -1
array: .word 0x00000001 # the array
.word ...
```
2. Loading values from memory: When loading values from memory, you should use the `lw` instruction with the correct syntax. For example, instead of `lw $t5, array($t3)`, you should use `lw $t5, ($t3)`. Update the relevant instructions accordingly:
```assembly
...
while:
...
lw $t5, ($t3) # Load value from array[$t3]
...
```
3. Storing values to memory: Similarly, when storing values to memory, the correct syntax is `sw $t4, result` instead of `sw $t4, 4($t6)`. Update the relevant instruction:
```assembly
...
exit:
sw $t3, result # Store $t3 to result
...
```
These changes should resolve the "bad data" errors. Make sure to assemble and run your code again to see if the errors have been resolved.
Based on the provided code, there are a few issues that may be causing the "bad data" errors. Here are some possible reasons and their solutions:
1. Incorrect addressing of the data section: Make sure to use relative addressing to access the data section correctly. In MIPS assembly, you can use the `$gp` (global pointer) or the `$s7` register as a base address for the data section. Modify the code to use appropriate relative addressing for accessing the data variables.
2. Incorrect usage of the `.data` directive: The `.data` directive should only be used once at the beginning of the data section to specify the start address. Remove subsequent `.data` directives before declaring the individual data variables.
3. Incorrect addressing of the array elements: When loading from or storing to memory, use the correct addressing mode. For example, instead of using `array($t3)`, use `array($t3)` or `array($t3)` to access the array elements correctly.
4. Insufficient space allocated for variables: Ensure that you have allocated enough space for all the declared variables. Double-check the sizes specified in the `.data` section and make sure they match the actual requirements.
5. Undefined or uninitialized registers: Check for any unintended usages or uninitialized values in registers. Make sure that all registers used in the code are properly initialized before use.
6. Missing or incorrect branching instructions: Verify that the branching instructions (`beq`, `bgt`, `j`, etc.) are correctly used and have appropriate conditions specified. Make sure they are branching to the correct labels.
It is important to note that the provided code snippet is incomplete, and there might be additional issues that cannot be identified without the complete program. To debug further, you can try to isolate specific parts of the code and test them step by step to identify the specific errors and fix them accordingly.
Remember to refer to MIPS assembly language documentation and instruction set architecture to ensure the correct usage of instructions and addressing modes.