Overclock.net banner

Assembly MIPS-32 help-reversing a string

32K views 7 replies 3 participants last post by  ColSanderz 
#1 ·
Hello,

This is an assignment for my assembly class. What I am trying to do is take a string and reverse it. I'm using the stack to reverse the string.

I'm starting to get confused with the registers and the stack, and the general flow of the program. Also, how should I go about printing the reversed string to console? Pop an item off the stack and print it?

Any tips or suggestions would be greatly appreciated.

Edit: Not sure if It matters, but I'm using QtSpim simulator.

Edit 2: I've updated post with my latest code

I get this error now

Can't expand stack segment by 8 bytes to 524288 bytes.
Use -lstack#with# > 524288

Is this error happening because I'm trying to add too much to the stack?

Code:

Code:
#Program 1 - Takes a string and reverses the string
#
# 
# Cosc 300

.data

prompt: .asciiz " Given String is =   "

str: .asciiz " aaaaBBBBccccDDDD "

ans: .asciiz " The String reversed is= "

.text
.globl main

main:

la $a0, prompt
li $v0, 4
syscall

la $a0, str
li $v0, 4
syscall

la $a0, ans
li $v0, 4
syscall

la $t1, str
li $t2, 0

Loop:

lb $t0, 0($t1)
beqz $t0, next

addi $sp, $sp, -4
sw $t0, 0($sp)

j Loop

next:

lw $t0, 0($sp)
beqz $t0, End

addi $sp, $sp, 4

li $v0, 4
move $a0, $t0
syscall

j next

End:

li $v0, 10
syscall
 
See less See more
#2 ·
Love me some assembly.

It looks like your error is caused because the loop never ends, and the program is essentially throwing a segmentation fault. It never goes to END: because $t0 is always being set to a non-null character.

Another thing i noticed was how you were stepping through your string. It tries to load the value at the string location, which is correct, but then it looks like it's trying to copy that value (which is a " "), without moving further forward in the string, and saves those values in the data segment at the -4 offsets.

Keep in mind also that stepping through your string should be done in 1 byte increments, since all of the alphabet can be represented by 1 byte.

I pasted some code below that is a slight variation on yours. Instead of saving the characters to the stack in reverse, it finds the length of the given string, and prints it backwards by stepping through the string -1 byte at a time. If you still need to save it to the stack in reverse before you print it, you can save $t0 in Loop: to the stack every time it goes through the loop.

Hope that all made sense. Goodluck!

Code:

Code:
#Program 1 - Takes a string and reverses the string
#
# 
# Cosc 300

.data

prompt: .asciiz " Given String is = "
str: .asciiz "aaaaBBBBccccDDDD"
newline: .asciiz "\n"
ans: .asciiz " The String reversed is = "

.text
.globl main

main:
la      $a0, prompt     #calling opening prompt
li      $v0, 4
syscall

la      $a0, str        #initial string
syscall

la      $a0, newline    #newline
syscall

la      $a0, ans        #initial text for reversed string
syscall

li      $t2, 0

strLen:                 #getting length of string
lb      $t0, str($t2)   #loading value
add     $t2, $t2, 1
bne     $t0, $zero, strLen
sub     $t2, $t2, 1
li      $v0, 11         #load imediate - print low-level byte

Loop:
la      $t0, str($t2)   #loading value
lb      $a0, ($t0)
syscall
sub     $t2, $t2, 1
bnez    $t2, Loop

li $v0, 10              #program done: terminating
syscall
 
#3 ·
Quote:
Originally Posted by ColSanderz View Post

Love me some assembly.
It looks like your error is caused because the loop never ends, and the program is essentially throwing a segmentation fault. It never goes to END: because $t0 is always being set to a non-null character.
Another thing i noticed was how you were stepping through your string. It tries to load the value at the string location, which is correct, but then it looks like it's trying to copy that value (which is a " "), without moving further forward in the string, and saves those values in the data segment at the -4 offsets.
Keep in mind also that stepping through your string should be done in 1 byte increments, since all of the alphabet can be represented by 1 byte.
I pasted some code below that is a slight variation on yours. Instead of saving the characters to the stack in reverse, it finds the length of the given string, and prints it backwards by stepping through the string -1 byte at a time. If you still need to save it to the stack in reverse before you print it, you can save $t0 in Loop: to the stack every time it goes through the loop.
Hope that all made sense. Goodluck!

Code:

Code:
#Program 1 - Takes a string and reverses the string
#
# 
# Cosc 300
.data
prompt: .asciiz " Given String is = "
str: .asciiz "aaaaBBBBccccDDDD"
newline: .asciiz "\n"
ans: .asciiz " The String reversed is = " 
.text
.globl main
main:
la      $a0, prompt     #calling opening prompt
li      $v0, 4
syscall
la      $a0, str        #initial string
syscall
la      $a0, newline    #newline
syscall
la      $a0, ans        #initial text for reversed string
syscall
li      $t2, 0
strLen:                 #getting length of string
lb      $t0, str($t2)   #loading value
add     $t2, $t2, 1
bne     $t0, $zero, strLen
sub     $t2, $t2, 1
li      $v0, 11         #load imediate - print low-level byte
Loop:
la      $t0, str($t2)   #loading value
lb      $a0, ($t0)
syscall
sub     $t2, $t2, 1
bnez    $t2, Loop
li $v0, 10              #program done: terminating
syscall
Hi, so if my program were to read in a string (say it was declared with .space 100) but the string length is only 10, like so

li $v0,8
la $a0, str
li $a1, 10
syscall

When I incorporated into the code you have, it prints out the reverse string that I input, everything BUT the first character. Do you perhaps know the reason why it is doing so? Thank you in advance.
 
#4 ·
Thanks for pointing that out. The reason it wasn't printing out the last character was because I accidently set it to subtract 1 from $t2 after it loaded address (la) from the string, but before the bnez statement.

Putting the following line

Code:

Code:
sub     $t2, $t2, 1
as the first statement in Loop: fixes this issue.

Here is the revised code:

Code:

Code:
#Program 1 - Takes a string and reverses the string
#
# 
# Cosc 300
.data
prompt: .asciiz " Given String is = "
str: .asciiz "aaaaBBBBccccDDDD"
newline: .asciiz "\n"
ans: .asciiz " The String reversed is = " 
.text
.globl main
main:
la      $a0, prompt     #calling opening prompt
li      $v0, 4
syscall
la      $a0, str        #initial string
syscall
la      $a0, newline    #newline
syscall
la      $a0, ans        #initial text for reversed string
syscall
li      $t2, 0
strLen:                 #getting length of string
lb      $t0, str($t2)   #loading value
add     $t2, $t2, 1
bne     $t0, $zero, strLen

li      $v0, 11         #load imediate - print low-level byte
Loop:
sub     $t2, $t2, 1     #this statement is now before the 'load address'
la      $t0, str($t2)   #loading value
lb      $a0, ($t0)
syscall
#This is where the sub statement used to be, which caused the loop to terminate too early
bnez    $t2, Loop
li      $v0, 10              #program done: terminating
syscall
Here is the output I get from the updated code with different string values, it now works with strings of all lengths.

Code:

Code:
#str: .asciiz "aaaaBBBBccccDDDDeeee"
Given String is = aaaaBBBBccccDDDDeeee
The String reversed is = eeeeDDDDccccBBBBaaaa

#---------------------------------------------------------------------------------

#str: .asciiz "aaaaBBBBccccDDDDeeeeFFFFggggHHHH"

Given String is = aaaaBBBBccccDDDDeeeeFFFFggggHHHH
The String reversed is = HHHHggggFFFFeeeeDDDDccccBBBBaaaa
Let me know if you have any more questions
thumb.gif
 
#5 ·
Ah I see.

How would you go about if you have to store the reversed string (overwrite the original) back into str

pseudocode

str = abcdefg

find the str length
reverse the string
str internally will now be gfedcba
then print

la $a0, str
li $v0, 8
syscall // should displays gfedcba

I thought my professor just wanted to do like what you did, but instead he wants us to overwrite our string with its reversed string. Sorry for asking because we really haven't learn much about MIPS programming :|

What I have so far:

Code:

Code:
.data
mystring: .space 100     #maximum of 100 character..well 99 & 1 space I guess.
newline: .asciiz "\n"
space: .asciiz " "

.text

main:
li $v0,8
la $a0, mystring
li $a1, 10            # I only read 9 character and a space even though the max is 100. 
                          #Prof. wanted that extra space in declaration. 
syscall
la $a0, newline
li $v0, 4    
syscall
la $a0, mystring
move $t0, $a0
li $t2,9

loop:         # loop to display the ascii decimal of the character
lb $a0, 0($t0)
li $v0,1
syscall
la $a0, space
li $v0, 4
syscall
addi $t2, $t2, -1
addi $t0, $t0, 1
bnez $t2, loop
la $a0, newline
li $v0, 4    
syscall

jal calcRev

la $a0, mystring
li $v0, 4
syscall

li $v0, 10
syscall

calcRev:
la $a0, mystring   
move $t1, $a0   #beginning addess of the string
li $t2, 0        #leftmost index
addi $t3, $a1, -1 #rightmost index
loopRev:        
add $t4, $t1, $t2
lb $t5, 0($t4) #load character beginning from left-end
add $t6, $t1, $t3
lb $t7, 0($t6) #load character beginning from right-end
sb $t5, 0($t6) #store left-end byte to right-end
sb $t7, 0($t4) #opposite of the above instruction
addi $t2, $t2, 1
addi $t3, $t3, -1
slt $t7, $t3, $t2   #if $t3 < $t2, $t7 = 0. else $t7 = 1
beqz $t7, loopRev 
jr $ra
Not sure why my program doesn't print out the supposedly reverse string after going through loopRev. Any idea why? Thanks in advance.
 
#6 ·
The code is actually very close. If you step through the code, you'll see that the reversed string is inserted at an offset (0x10010004) from the actual start location of the original string (0x10010000), so 4 bytes. All you have to do is add the offset to your load address statement at the very end so it looks like this:

Code:

Code:
la $a0, mystring($t3) #load string with offset given
li $v0, 4
syscall
It has been a while since I've done MIPS, but the following code should work in most cases. If it doesn't, you might try replacing the load address statement with another loop that prints each character as it reads it up to 10 or whichever number you set. I will take a look again in a bit and update the code

Code:

Code:
.data
mystring: .space 100     #maximum of 100 character..well 99 & 1 space I guess.
newline: .asciiz "\n"
space: .asciiz " "

.text

main:
li $v0,8
la $a0, mystring
li $a1, 10              # I only read 9 character and a space even though the max is 100. 
                        #Prof. wanted that extra space in declaration. 
syscall
la $a0, newline
li $v0, 4               #print function
syscall

la $a0, mystring        
move $t0, $a0
li $t2,9

loop:         # loop to display the ascii decimal of the character

lb $a0, 0($t0)
li $v0, 1       #print an integer - the ascii decimal
syscall
la $a0, space
li $v0, 4       #print string - " "
syscall

addi $t2, $t2, -1
addi $t0, $t0, 1
bnez $t2, loop  #when $t2 != 0, branch to loop

la $a0, newline
syscall         #printing a new line

jal calcRev

la $a0, mystring($t3) #load string with offset given
li $v0, 4
syscall

li $v0, 10
syscall

calcRev:
la      $a0, mystring   
move    $t1, $a0   #beginning addess of the string
li      $t2, 0        #leftmost index
addi    $t3, $a1, -1 #rightmost index

loopRev:        
add     $t4, $t1, $t2
lb      $t5, 0($t4) #load character beginning from left-end

add     $t6, $t1, $t3
lb      $t7, 0($t6) #load character beginning from right-end

sb      $t5, 0($t6) #store left-end byte to right-end
sb      $t7, 0($t4) #opposite of the above instruction
addi    $t2, $t2, 1
addi    $t3, $t3, -1
slt     $t7, $t3, $t2   #if $t3 < $t2, $t7 = 0. else $t7 = 1
beqz    $t7, loopRev

jr      $ra

#--------OUTPUT----------------

#jimmy

#106 105 109 109 121 10 0 0 0

#ymmij
#-- program is finished running --
I'm not sure how your professor grades, but just a word of warning... this code closely resembles code from a blog that can be found through google. I would advise writing the code yourself next time instead of just modifying it. Or, you can do as I did, and only take the bits and pieces that don't make sense. If you didn't copy it, sorry - code looks good otherwise.
thumb.gif
 
#7 ·
Oh I see. I'll keep that offset in mind. I have another problem and it would be really great if you can look over to see where I made an error in my program. This program uses the same string input as my earlier code, but I'm suppose to count the character frequency in the string.

Code:

Code:
.data
mystring: .space 200
frequency: .space 108  #only counts the 26 lowercase character + space
newline: .asciiz "\n"
space: .asciiz " "

.text

main:
li $v0,8
la $a0, mystring
li $a1, 10
syscall
la $a0, newline
li $v0, 4    
syscall
la $t1, frequency #address of the frequency array
la $a0, mystring #address of string
move $t0, $a0
li $t2,9 #counter

loopCount:
lb $a0, 0($t0)   #load first byte in the string
move $t3, $a0  #move that ascii decimal to $t3
sub $t3, $t3, 65 #subtracts 65 to get the index in the frequency array (ie. index 0 = a, 1 = b, etc)
li $t4, 0 
mul $t4, $t3, 4  #location in frequency array, multiple of 4 since it's an integer
add $t1, $t1, $t4 #offset the address of the frequency to index $t3
lw $a0, 0($t1) #load the integer 
move $t5, $a0  #move integer to $t5
add $t5, $t5, 1  #increment
sw $t5, 0($t1) #store back into frequency array
sub $t1, $t1, $t4 #set the address back to the beginning 
add $t2, $t2, -1 #decrement counter
bgtz $t2, loopCount

la $t1, frequency
li $t2,26

loopPrint:  #prints out all the value in the frequency array, except the last one (space)
lw $a0, 0($t1)
li $v0, 1
syscall
la $a0, space
li $v0, 4
syscall
add $t2, $t2, -1
add $t1, $t1, 4
bgtz $t2, loopPrint

la $a0, newline
li $v0, 4
syscall
li $v0, 10
syscall

print:
li $v0, 1
syscall
la $a0, space
li $v0, 4
syscall
b loopPrint
I input in for example the string "ahfggffdfd" and gets a bunch of zeros in my output.
 
#8 ·
I noticed that after I posted. Would have been able to look at it immediately, but needed to get to work lol. The best way I can think of to fix this is to iterate through the string, one byte at a time and print the character until you reach the 10 that you set in the beginning.

I replaced the print string statment with the following, and it now works fine with strings of all length.

Code:

Code:
#--- code here ---

jal calcRev
#-----------------------------------
la      $a0, mystring #load string with offset given - the last jump goes here
move    $t1, $a0

Looper:                 #Looper iterates through the memory allocated for the string and prints
lb      $a0, 0($t1)     #one byte at a time
li      $v0, 11         #load low level byte
syscall
add     $t1, $t1, 1     #add one to pointer position
ble     $t1, $t0, Looper#if $t1 is <= $t0, branch to Looper

li $v0, 10
syscall
#-----------------------------------
calcRev:

#---- code here ---

jr      $ra #last line it that jumps to the code above
 
This is an older thread, you may not receive a response, and could be reviving an old thread. Please consider creating a new thread.
Top