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 Peter Cordes

    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.

How many English words
do you know?
Test your English vocabulary size, and measure
how many words do you know
Online Test
Powered by Examplum