1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Assembly code not running - debug help

  1. Jan 6, 2012 #1
    1. The problem statement, all variables and given/known data
    Hello all,
    I need to implement iterative (non-recursive) binary search in assembly. The array has 10 elements, starting from 0x10000100, in address 0x10000004 there's the element to search for, and the answer should be put in address 0x10000008

    It should be for MIPS and I ran it in QTSpim

    2. Relevant equations
    Here's my code:
    Code (Text):
        # 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   0xblackff   # 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
         
    program:
        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, 0($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, 0($t6)      # result = $t4
        j end           # jump to end
        nop

    end:    j end           # internal loop to end the program
       

    3. The attempt at a solution
    I get those errors in the run:
    > Exception occurred at PC=0x00400000
    > Bad address in data/stack read: 0x00000000
    > Exception occurred at PC=0x0040007c
    > Bad address in data/stack read: 0x00000000

    Any ideas what could go wrong?
     
    Last edited: Jan 6, 2012
  2. jcsd
  3. Jan 6, 2012 #2

    NascentOxygen

    User Avatar

    Staff: Mentor

    I haven't looked closely at your code. You should break your program down into manageable blocks and debug it that way.

    So make the very first statement in the program an exit, to make sure something that straightforward that will run without error messages.
    program:
    j end

    If this works,
    modify to

    program:
    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 end

    and confirm that that is going to run without errors,
    and so on, cautiously building up in steps to the final code.

    In essence, building up your program by verifying each part works before adding more. This is the method of program construction you should be following, in any case. Otherwise, you type it all in, find it doesn't run, then have no idea where to start searching for the error.

    Good luck. And welcome to the trials and tribulations of programming!
     
  4. Jan 6, 2012 #3

    I like Serena

    User Avatar
    Homework Helper

    Welcome to PF, ydan87! :smile:

    Looks like an access violation, meaning you access data from a location in a memory location where you're not allowed to.

    Skimming through your code I found:
    Code (Text):
        lw $t5, 0($t3)              # $t5 = array($t3)
    However, no reference has been made yet to the memory location of "array".
     
  5. Jan 7, 2012 #4
    Thanks guys for the help and the warm welcome :)

    Ilike - I guess I should first save the address of the array somewhere, and advance through it in each iteration. Can you give me an example on how to do that exactly?

    Thanks in advnace
     
  6. Jan 7, 2012 #5

    I like Serena

    User Avatar
    Homework Helper

    I would try:
    Code (Text):
        lw $t5, array($t3)              # $t5 = array($t3)
     
  7. Jan 7, 2012 #6
    Thanks for the quick reply
    After fixing that, I get these in the run:
    > Exception occurred at PC=0x00400000
    > Bad address in data/stack read: 0x00000000
    > Exception occurred at PC=0x00400088
    > Bad address in data/stack read: 0x00000000

    I guess we have a progress here...the previous third exection was for pc 0x0040007c and now to 0x00400088 which means that the programs advanced without reciveing error for some time.

    Any ideas now?
     
  8. Jan 7, 2012 #7

    I like Serena

    User Avatar
    Homework Helper

    Well, are there any other places where you index "array" without specifying that it is "array" you are indexing?

    And perhaps you can relate the address 0x00400088 to a specific line your code?
     
  9. Jan 7, 2012 #8
    Well...not for the array. Because after I've loaded it to $t5 I just used $t5.

    However, if I may address you to the part of the code where "result" is defined. In the exit label I have this line of code:
    Code (Text):
    sw $t4, 0($t6)      # result = $t4
    Is there something wrong with that one?
     
  10. Jan 7, 2012 #9

    I like Serena

    User Avatar
    Homework Helper

    Well, I'm not going to do your work for you...
    What do you think?

    Btw, do you have a method to inspect intermediate results?
    Perhaps you can output values so you can inspect them?
    That way you can see how far your program got before crashing, and you can see if the program was on the right track.
     
  11. Jan 7, 2012 #10
    Well, you've really helped me alot thanks :), I really shouldn't have asked you do more than what you've already done.
    Can you just offer me a program of a simulator that I can do inspection of the kind you've mentioned?
     
  12. Jan 7, 2012 #11

    I like Serena

    User Avatar
    Homework Helper

    You should already have something like that at hand.
    Suppose your program finished successfully.
    How would you know the result?
     
  13. Jan 7, 2012 #12

    Mark44

    Staff: Mentor

    You said you were using QtSPIM. Besides the console window, there is a window that you can view the registers, and you can single-step through your code to watch the registers change.

    The latest version is 9.1.4, I believe.
     
  14. Jan 7, 2012 #13
    Guys, I appriciate your help very much. The thing is that I've asked for help because all the things you offer me either with the code or the program QTSpin didn't work for me, so I wanted extra pairs of eyes to take a look at this.
    I know you shouldn't do the work for me, but I really tried my best on this and that's the reason I've posted here.

    I'll appriciate any extra help in finding the bug in the code.

    For your question, Mark - I haven't seen any change in the registers while running, because the first error I get is in the first step of the code
     
  15. Jan 8, 2012 #14

    Mark44

    Staff: Mentor

    The reason for the first error is that you are not doing what you think you're doing. In your pseudocode, the first thing you do is store 0 in first.

    Your first line of MIPS code stores the value in $t0 in location 0, and you can't do that. It is not storing the value 0 in the $t0 register.

    I don't understand your code well enough to know how the first and last variables relate to the array. Is first supposed to be the first location in the array? If not, you should have a declaration in your text section to define this variable, something like this:
    Code (Text):
    first:  .word   0   # comment that describes what first is supposed to be
    Also, I don't believe you need to have all of those .data statements after the first one. The assembler will put your variables where they need to go. I could be wrong, but if not, you're doing work figuring out addresses that the computer can do much fast and more accurately.
     
  16. Jan 8, 2012 #15
    The first variable should be, at the beginning, the value 0 and then it changes according to the binary search. First is also an index I use to look in the array in that index.
    I needto have the .data statements because I am asked to put certain variables in certain addresses and also the result in a certain address and that's the reason for the statements.

    So how should the first line appear? Just switching between t0 and 0?
     
  17. Jan 8, 2012 #16

    Mark44

    Staff: Mentor

    Something like this:
    Code (Text):
        .data   0x10000000

    size:       .word   0x0000000a  # array size

        .data   0x10000004

    search:     .word   0x0000000d  # search term

        .data   0x10000008

    result:     .word   0xblackff   # result = -1

        .data   0x10000100
    first:      .word   0  # index of start of array section to be searched
    last:       .word   0  # index of end of array section to be searched

    mid:        .word   0  # index of middle element in array section to be searched

    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
         
    program:
        lw $t1, size        # load size value into $t1
        addi $t1, $t1, -1   # $t1 = size - 1, our "last" pointer
        j condition     # goto condition
     
    You should have variables defined in your data section for each variable in your pseudocode. I have added some of the variables that you omitted. Since first is initialized to 0, I don't need to have code to do this, so I can start right in with storing size - 1 in the appropriate register.
     
  18. Jan 8, 2012 #17
    Okkk i understand it now for the future :)
    Thanks alot mark
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Assembly code not running - debug help
Loading...