Reading a string backwards and saving it(string reversal with a twist)

Question

I'm new here but i'll do my best to follow the guidelines. Please note that I've only just started with MiPS and MARS so if I'm doing something stupid then let me know how to fix it so that i can improve.

I'm currently working on a school assignment for my long-distance assembly course where i have to reverse a string. The catch is that i can't create a new string, instead i have to modify the existing one.

I figured why would i try to find the first+n/last-n characters in a string when I can just walk backwards from the last character in the string to the first character of the string. I managed to read and print the string backwards but now I'm stuck and could really use a nudge in the right direction.

If you run this code then the string "dlroW olleH" will be printed and the program will exit, so far so good(I hope). My question is:

How do i save the string in reverse format to the original label "str"?

I began writing some code but it's unfinished, see the "reverse" label for the part that my question is related to. Here is my code so far: Note that i cannot use any libraries, I have to do this by hand so to speak.

SEE EDIT BELOW

.data
str: .asciiz "Hello World"
str_msg1: .asciiz "String: "
str_msg2: .asciiz "String lenght: "
str_msg3: .asciiz "String reversed: "
str_nl: .asciiz "\n"
strLen: .space 8

.text

# Printing the original string
la $a0,str_msg1
li $v0,4
syscall
la $a0,str
li $v0,4
syscall
la $a0,str_nl
li $v0,4
syscall

#Get the lenght of the string
la $a0,str
getLen:
    lb $t0,0($a0)
    beqz $t0,printLen
    addi $t1,$t1,1
    addi $a0,$a0,1
    j getLen

#saves and prints the lenght of the string
printLen:
    sb $t1,strLen
    la $a0,str_msg2
    li $v0,4
    syscall
    lb $a0,strLen
    li $v0, 1
    syscall
    la $a0,str_nl
    li $v0,4
    syscall

here is the interesting part:

reverse:
    addi $t0,$zero,0 #zeroing the t registers to clear them for the next part.
    addi $t1,$zero,0
    addi $t2,$zero,0

    la $a1,str             #contains the adress of the string
    lb $a2,strLen          #contains the lenght of the string 
    add $a1,$a1,$a2          #adds the lenght of the string to the adress meaning it now stores the last position of the string
    add $t0,$a2,$zero    #counter initiated to lengt of the string
    loop:
        subi $a1,$a1,1  #decrement the adress since we dont want the null terminator string
        beqz $t0,exit      #if the counter variable is zero we have gone over the entire range of the strings index,then exit
        subi $t0,$t0,1  #decrement the counter since if we are here then we have not reached the end yet
                          #<temporary print statement below is for debugging purposes>
        lb $a0,0($a1)   #loads the first byte from the adress stored at $a1 which will be the string in decending order
        li $v0,11         #print character syscall
        syscall
        j loop
# Exit the program
exit:
    li $v0,10
    syscall

Thank you for taking the time to read my question. Cheers!

EDIT

So I may have figured out an answer and i thought i should post it so that others can read it and maybe it can be improved. I'm technically skirting what's allowed for this assignment but in the end the original string is changed to a reversed format so i think it should be okay. I did this by creating a buffer (strBuffer .space 255) and i copied the string in reverse to this buffer and then stored it at the address of the original string. It seems to work and I'm ecstatic!

My altered code looks like this:

reverse:
    addi $t0,$zero,0 #zeroing all the t registers to clear them for the next part.
    addi $t1,$zero,0
    addi $t2,$zero,0
    addi $t3,$zero,0
    addi $t4,$zero,0
    la $a1,str      
    lb $a2,strLen       
    add $a1,$a1,$a2     
    add $t0,$a2,$zero   
    la $t3, strBuffer #here is the new buffer
    loop:
        subi $a1,$a1,1  
        beqz $t0,exit   
        subi $t0,$t0,1  
        lb $t4,0($a1)     # i load the string backwards byte by byte
        sb $t4,0($t3)     # i store it in the string buffer
        addi $t3,$t3,1     # i increment the memory adress of the buffer so that i can save the bytes one after the other
        j loop
exit:                      #I know my labels have to be changed but i will clean it later
la $a0,str_msg3           #print a leading message
li $v0,4
syscall
la $t8,strBuffer           #load the adress of the buffer and the string
la $t9, str
loop2:
    lb $t7,0($t8)          #load the first byte of the buffer
    beqz $t7,exit2         #check if its null 
    sb $t7,0($t9)          #store the byte in the strings adress at the first index
    addi $t8,$t8,1         #incrementing the adresses 
    addi $t9,$t9,1
    j loop2
exit2:                     #printing the result
la $a0,str
li $v0,4
syscall
li $v0,10
syscall

I've been at this for over 6 hours now so please forgive my lack of proper style and indentation. It seems to work and from what i can tell of the MARS data segment display, the string gets reversed.

cheers

Answer 1

Wow, thanks for all the great help! I reviewed my code after at decent nights sleep and boy did it look messy. I rewrote the whole thing after reading your responses and it works :D (see code at the bottom)

I would like to direct a massive thank you to @Ped7g and @PeterCordes for posting so many comments telling me what i could improve and some things I should think about when working with MiPS. Thank you, I learned something today.

.data 
str: .asciiz "ThE qUiCk BrOwN fOx JuMpS oVeR tHe LaZy DoG"
str_msg1: .asciiz "Original string: "
str_msg2: .asciiz "Reversed string: "
str_nl: .asciiz "\n"
str_len: .word 0

.text
main:
#print original string
    la $a0,str_msg1     #leading text
    li $v0,4
    syscall
    la $a0,str              #original string
    li $v0,4
    syscall
    la $a0,str_nl           #new Line
    li $v0, 4
    syscall

#get lenght
    add $t0,$zero,$zero     #initialize registers when needed
    add $a0,$zero,$zero
    add $a1,$zero,$zero
    la $a0,str            #loads the adress of the string into two registers
    la $a1,str      
    getLen:
        lb $t0,0($a0)       #load first byte
        beqz $t0,saveLen  #check if byte is null and if so, goto saveLen
        addi $a0,$a0,1  #if not then increment the adress and keep going
        j getLen          #jump back to start of this loop
    saveLen:
        subu $t0,$a0,$a1  #len = adress of null terminator - str adress
        sw $t0,str_len

#reverse the string
    add $t0,$zero,$zero     #will hold the adress of the beginning of str
    add $t1,$zero,$zero     #will hold the adress of the end of str
    add $t2,$zero,$zero     #swap 1 
    add $t3,$zero,$zero     #swap 2 
    revString:
        #find the index of the last character before the end of the string
        la $t0,str             #loads the adress of the start of the string
        lw $t1,str_len         #loads the lenght of the string
        addu $t1,$t0,$t1      #now t1 is pointing to the null terminator
        subi $t1,$t1,1      #now t1 is pointing to the last character
        loop:
            lb $t2,0($t0)       #load the first character
            lb $t3,0($t1)       #load the last character
            ble $t1,$t0,printRev    #check to see when we reach the middle of the string
            sb $t3,0($t0)       #store the last letter at the beginning of the string
            sb $t2,0($t1)       #store the first letter at the end of the string
            addi $t0,$t0      #then increment/decrement the adress registers 
            subi $t1,$t1,1    #and loop until we reach the middle
            j loop

#print the reversed version of the text
    printRev:
    add $a0,$zero,$zero    #initialize the a0 registry
    la $a0,str_msg2      #leading text
    li $v0,4
    syscall
    la $a0,str          #reversed string
    li $v0,4
    syscall
    li $v0,10           #exit prorgram
    syscall

P.S. BTW, I like how you managed to print out the reversed string without reversing it, that shows you have probably solid basic grasp of what is going on and how that computer box works ...

Thanks man, that was nice to read :) I feel a bit better about myself now. Still, after asking questions on sites like this I'm always reminded of how much i still don't know.

Fortunately there are people like you who take the time to pass along their experience and advice. Kudos man!

Answer 2

Reverse in place algorithm suggestion:

Have two registers r1,r2 point to first/last character of string.
while (r1 < r2) {
    swap_chars_at_addresses(r1, r2);
    ++r1;
    --r2;
}

Some comments about your original code:

strLen: .space 8

You reserve 8 bytes for strLen, but then in code you use it as byte variable, which will limit your code only to 127 character long strings at max (while byte can be of 0..255 range, the lb by default does sign-extend the value, so to reach full 255 limit you would have to treat that byte as unsigned value).

I would strongly suggest to set this up as:

strLen: .word 0

And then to use sw/lw to treat it as 32b signed integer value, as you have that word value available, and it makes more sense in pointer arithmetic. Also there's zero risk in MARS/SPIM that somebody will manage to give you input string with more than 2³¹ characters and make the length value overflow into negative numbers, as there's not enough memory on the virtual MIPS machine in MARS/SPIM to have such big string. While giving you 128 character long string is not that difficult (then your old code will go crazy)...

#Get the lenght of the string

It's spelled "length" (I know MARS/SPIM don't have spellchecker, but your web browser probably has).

la $a0,str
getLen:
    lb $t0,0($a0)
    beqz $t0,printLen
    addi $t1,$t1,1
    addi $a0,$a0,1
    j getLen

You didn't initialize t1, so you are just lucky enough the MARS/SPIM does zero the registers before executing your code and it didn't modify them inside the syscall calls.

But this is still fragile way of programming, rather initialize all relevant registers and keep the relevant instructions as compact (near each other) as possible (i.e. initialize right ahead of getLen, not right after start of code before printing prompts).

Also if you will take a look at that code, there's .. += 1; twice. That should feel like unnecessary redundancy. And indeed you can avoid that:

la $a0,str
move $a1,$a0 # have str address also in a1
getLen:
    lb   $t0,0($a0)
    beqz $t0,getLenFinish
    addi $a0,$a0,1
    j getLen            # loop is one instruction shorter = may be faster
getLenFinish:
    subu $t0, $a0, $a1  # length = address of 0-terminator - str address
    sw   $t0,strLen     # store the calculated length into memory

Now setting up those "r1, r2" from my comment would be as simple as this:

    # set t1 and t2 to point to first and last character of string
    la    $t1,str
    lw    $t2,strLen
    addu  $t2, $t1, $t2   #t2 = address of zero terminator
    subi  $t2, $t2, 1     #t2 = adr of last char (or out of bounds)
    # for empty string t2 is out of bounds now and shouldn't be dereferenced
    # And my algorithm was designed as "while (r1 < r2)" = false => no problem

And that's where I will stop, as only so much was fun to comment on...

P.S. BTW, I like how you managed to print out the reversed string without reversing it, that shows you have probably solid basic grasp of what is going on and how that computer box works. Many other MIPS questions feel like the author doesn't even have idea that "string" is series of byte values stored in memory, and that you actually can read it backwards.