# Mips (assembly) - binary search problem - load not aligned for address of middle array element?

``````        .text
j main

binary_search:
slt \$t0, \$a2, \$a1 # if last < first, \$t0 = 1
beq \$t0, \$zero, check_mid # if first > last, proceed to return -1

addi \$v0, \$zero, -1
jr \$ra # exit with returned argument

check_mid:
# saving address to stack
addi \$sp, \$sp, -4
sw \$ra, 4(\$sp)

sub \$t1, \$a2, \$a1 # last - first
srl \$t1, \$t1, 1 # (last - first) /2

add \$t2, \$a1, \$t1 # \$t2 is referrencing the mid index of the array
lw  \$t3, 0(\$t2) # \$t3 is the mid element of the array

bne \$t3, \$a0, check_higher

add \$v0, \$t2, \$zero # \$v0 is the index of the wanted element

lw \$ra, 4(\$sp)
addi \$sp, \$sp, 4

jr \$ra # exit with returned argument

check_higher:
slt \$t0, \$t3, \$a0 # if arr[mid] < x, \$t0 is 1
bne \$t0, \$zero, check_lower

addi \$t1, \$t1, -4 # mid = mid - 4
jal binary_search # recursion call

check_lower:
addi \$t1, \$t1, 4 # mid = mid + 4
jal binary_search # recursion call

main:
addi \$a0, \$zero, 64
addi \$a1, \$zero, 0
addi \$a2, \$zero, 28
jal binary_search
``````

So this is my code so far. as far as I can see it I'm pretty much done with the code, unless I didn't take care well enough of saving/loading returning addresses from the stack, but that's not my main concern right now.

What I'm trying to figure out, is how do I reach the middle offset/element of the array? because executing this code will bring me the error: "line 39: Runtime exception at 0x00400028: fetch address not aligned on word boundary 0x0000000e" (line 39 is this line: `lw \$t3, 0(\$t2) # \$t3 is the mid element of the array`)

## 1 answer

• answered 2022-05-04 11:53

It looks like you're working with byte offsets instead of indexes for words. That's fine and good (instead of redoing left-shifting every time you use the address), but it means that a right shift won't truncate to a word offset, it can shift a bit into the byte-within-word part of the address, the low 2 bytes. Unlike in C if you did `mid = (hi-lo)>>1;` which would simply shift a bit out the bottom of the value.

`srl \$t1, \$t1, 1` can thus produce an odd halfword address, instead of truncating down to an aligned word address.

You could `and` with `-4`, i.e. `0xfffffffc` to clear those address bits after shifting, but MIPS can't do that in one instruction because `andi` zero-extends its immediate. If your array really is known to be smaller than 64KiB and at a very low address close to zero (so the `0x0000000e` you tried to deref wasn't also a separate bug of getting adding a small offset to a NULL pointer), you could `andi` with `0x0000fffc` to truncate an address. Or do that on an offset before adding it to an actual address if you're working with offsets instead of actual pointers.

Of course you could just `li \$t9, -4` once before your loop and use that, but you're using recursion instead of a more efficient loop. So I guess you don't care about efficiency anyway and could just do an extra `li` right before you want to `and`. (`addiu` can materialize a `-4` in one instruction, unlike `ori`.)

Or the other way would be to right shift the bits you want to discard all the way out of the register, and then to a left shift to bring you data back to where you want it. `mid = ((hi-lo)>>3) << 1;`

Also you have other bugs, like falling off the bottom of your function after the `jal binary_search` in `check_lower:` returns. You either need to reload `\$ra` and return in those paths, or optimize the tail-call into a `j` or `b` after reloading `\$ra`, not `jal` / reload `\$ra` / `jr \$ra`.

Same for the `jal` in `check_higher:`; you don't want to fall through into `check_lower`, that would end up checking both sides for O(N) total runtime, not O(log N).

But those are all things you should debug by single-stepping with a debugger, and separate from the interesting indexing problem of right-shift creating an odd-halfword address when doing binary search in asm with word addresses or byte offsets.