How to properly reverse a string by replacing the memory in the adress, not creating new memory in MIPS Assembly

0

I have an assignment in my Computer Architecture class where we are supposed to complete a set of tasks. The last task is to create a subroutine that takes a string and reverses it. We're not allowed to use the original string in order to create a "new memory string". Instead, we are supposed to gradually replace the content of the original string.

My first thought was to load the leftmost and rightmost character in temporary registers and then using these to "swap" their positions. After this is done, the addresses should increment and decrease (there's two addresses, one pointing to the start of the string and one pointing to the end). Then this is going to loop until both of the addresses point to the same point, where the loop then will end.

This is the code I have for the reverse_string subroutine. $a0 is the address for the NULL-ended string. I'm not sure if the algorithm I was thinking of in my head translated into MIPS properly, I'm very new to this type of language.

reverse_string:

    #### Write your solution here ####
    beqz    $a0, rs_exit        # Check if string is NULL, exit if it is
    li  $t0, 0
    li  $t1, 0
    add $t0, $t0, $a0       # Save leftmost adress of string
    add $t1, $a0, $v0       # Save rightmost adress of string

    rs_loop:
    beq $t0, $t1, rs_exit
    lbu $t2, 0($t0)     # Save leftmost character in temporary register
    lbu $t3, 0($t1)     # Save rightmost character in temporary register
    sb  $a0, 0($t2)     # Replace rightmost character with leftmost character
    sb  $a0, 0($t3)     # Replace leftmost character with rightmost character
    addi    $t0, $t0, 1     # Increment leftmost adress by 1
    subi    $t1, $t1, 1     # Decrement rightmost by 1
    j   rs_loop

    rs_exit:
    jr  $ra

The code in main for executing reverse_string is the following:

    ##
    ### reverse_string
    ##

    li  $v0, 4
    la  $a0, STR_reverse_string
    syscall

    la  $a0, STR_str
    la  $a1, reverse_string
    jal reverse_string

    la  $a0, STR_str
    jal print_test_string

So, as mentioned previously. The expected result is that the program should print out the reversed string. Currently, I'm having errors at the following line:

sb  $a0, 0($t2)     # Replace rightmost character with leftmost character

The error:

Runtime exception at 0x004000c4: address out of range 0x0000004a

I've tried for several hours. There's several people who have successfully received help with similar problems, however they were a bit different (input from users and also they created new strings instead of replacing the contents of the original one)

I appreciate any help! Thank you.

string
assembly
replace
mips
reverse
asked on Stack Overflow Sep 17, 2019 by lemonslayer • edited Sep 18, 2019 by lemonslayer

1 Answer

2

My first thought was to ... this is going to loop until both of the addresses point to the same point...

Until the "end" pointer is equal or less than "start" pointer. For even length like "abcd" the pointers pointing at "b" and "c" are valid, but after swap and incrementing + decrementing they are still not equal, but you should end the loop. Anyway, except this detail, your idea is good.

Runtime exception at 0x004000c4: address out of range 0x0000004a

This means the sb (store byte) instruction did try to write at memory address 0x0000004a, which is not accessible (no memory there, or not enough rights for your process to write there). Which means the 0($t2) did evaluate to that address, which means the value in t2 is equal to 0x4a. You should be able to see that in debugger, when single stepping over instructions.

From there you have to back-track whole operation, how it become this value and why.


    la  $a0, STR_str
    la  $a1, reverse_string
    jal reverse_string

why a1 is set? The contract in task says that string address is passed in a0, nothing else. But anyway, that's not your code, just curious... so let's get onto your code.

beqz    $a0, rs_exit        # Check if string is NULL, exit if it is
li  $t0, 0
li  $t1, 0
add $t0, $t0, $a0       # Save leftmost adress of string
add $t1, $a0, $v0       # Save rightmost adress of string

null test is ok, you can use also addi or $zero = $0 for zero value, i.e.:

    beqz    $a0, rs_exit  # Check if string is NULL, exit if it is
    add $t0, $a0, $zero   # t0 = left pointer (start of string)
    add $t1, $a0, $v0     # t1 = start of string plus unknown value in v0

And as you can read in the second comment, you have one bug right there at beginning.

Which does imply you didn't debug your code at all, or with very limited inputs.

If the only input to routine is address of string, you have to find char-by-char where the terminating zero is stored, and use that to figure out "end" pointer. (you can for example copy a0 to a1, load byte from a1, check for zero, increment a1 and fetch again, ... until that terminating zero is found ... the address just ahead (-1) of that first zero is your "end" pointer)

Let's pretend you have correct pointers... then another part:

lbu $t2, 0($t0)     # Save leftmost character in temporary register
lbu $t3, 0($t1)     # Save rightmost character in temporary register
sb  $a0, 0($t2)     # Replace rightmost character with leftmost character
sb  $a0, 0($t3)     # Replace leftmost character with rightmost character

The first two are correct (with correct pointers). But the other two are completely wrong. the "sb" store byte has arguments "value, memory address", so you are trying to store bottom byte of string address to memory address represented by character... 0x4a is in ASCII encoding character 'J', which, as the error message points out, is not valid memory address.

You may consider yourself kinda lucky, because when programming in assembly, sometimes similar bugs actually happen to have in register wrong value, which is accessible, and some memory is overwritten which should have not been, but without crash or any sign of problem. Then much later some completely other part of code may reach for that memory, expecting something else to be stored there, and it will produce some bug. These "memory overwrite" bugs are extremely difficult to decipher and fix, as any oldschool assembly/C/C++ programmer can tell you.

So your code is very weak try to implement the idea you described.

Try to run through it with debugger (if you are using SPIM/MARS simulators, all of them have built-in debugger, not state of art one, but usable for these tiny tutorial tasks), and try to fully understand what is happening, and why those instructions do not represent your idea, and what they are actually doing in reality.

You have to learn this skill, if you want to code in assembly, assembly allows no room for mistakes or some vague interpretations, or to get working code just by "trying" things, changing source randomly. Always figure out what the code actually does, and how precisely it differs from what you want. Then fix it.

Generally assembly questions which show "no debugging" gets downvoted really quickly, because debugging is time consuming process, and just outsourcing it to SO crowd is rude ... but you have bonus point from me for stating clearly your idea, and overall providing almost complete reproducible example (you did forgot to show the string definition ... and in assembly, the way how you define data, is quite often even more important than code, so it may be you have some kind of bug also there, like not adding zero terminator to string, etc...).

Also never try to guess how the instruction works by it's name. Always study the reference manual properly, and make sure you understand everything what it says about the instruction.

You can to some weak results by guessing and trying random things in higher level languages, but it's just waste of time in assembly, even this short routine of ~20 lines already allows for millions of variations (somewhat meaningful at first sight), and only few hundreds of them are correct solution.

Now try again, and focus to stay in control all the time. If you are not sure about something, how to understand it, reread it few more times, or build short code exercising the part you are not sure about, and check in debugger what the CPU does... eventually ask on SO with explanation what you expected, and what surprised you in debugger.

answered on Stack Overflow Sep 18, 2019 by Ped7g

User contributions licensed under CC BY-SA 3.0