How can you reverse the order of words in a string using MIPS Assembly?

[SpiffyEh]

Homework Statement

The goal here is to write some MIPS functions to solve a common technical interview
question: how can you reverse the order of the words in a string? For example, reversing
the words in the string I Love Lucy would result in Lucy Love I.
A string is just an array of bytes, with each byte representing one character. The last byte
of the array is always 0, to indicate the end of the string. Also, a space is represented by
the value 32.

First write a function rev, which simply reverses bytes in an array. The arguments
passed in $a0 and $a1 are the starting address and the number of bytes to reverse.

Using the rev function, you should now be able to write revwords to reverse the
order of the words within a string.

You can implement revwords according to the following basic algorithm.
1. Call rev to completely reverse the original string. For example, I Love Lucy becomes
ycuLevoLI. Remember that strings are terminated by a 0 byte.
2. Then use rev to reverse each word in the new string—ycuLevoLI becomes Lucy Love I.
You can assume that “words” are separated by a space character, with the byte value 32.

The Attempt at a Solution

revwords isn't a function in my attempt, i put it in main for now until i get it working. I created the rev function and tested it and it works for a string. Then i went on to create the other one and that's where I'm having issues. It goes through the words and everything but the output i get is LucyLove_I_ whrere _ are spaces. I've tried to fix it where the space is still in the correct location but I cannot figure it out. The code is posted below, if anyone has any suggestions it would really help, I've spent hours trying to fix this little bug and I've lost hope.

.data

string: .asciiz "I Love Lucy"
endl: .asciiz "\n"
space: .asciiz " "

.text
.globl main

rev:

#la $s0, string
#addi $a1, $0, 7

add $t2, $0, $0 # set the counter variable to 0
srl $t0, $a1, 1 # divide the number of characters by 2
add $t1, $0, $a1 # put the number of characters into t1
addi $t1, $t1, -1 # subtract 1 from the number of characters
add $t1, $a0, $t1 # add to the beginning address to get to the end address

loop:
lb $t6, 0($a0) # load the byte into t6 (left half)
lb $t7, 0($t1) # load the byte into $t7 (right half)
sb $t6, 0($t1) # store t6 at position t1, basically swap
sb $t7, 0($a0) # store t7 at position a0, swapping
addi $a0, $a0, 1 # get the address of the next pixel by adding 1
addi $t1, $t1, -1 # get the address of the previous pixel from end by adding -1
addi $t2,$t2, 1 # increment the counter by 1
bne $t0, $t2, loop # while the counter is not equal to half the number of characters loop

jr $ra # jump back to where the function was called


main:

la $a0, string # load the address of the string into a0

addi $sp, $sp, -12 # make space on the stack for a0
sw $a0, 0($sp) # store a0
sw $ra, 4($sp) # store ra

addi $a1, $0, 11 # 11 = total number of characters
jal rev # call rev with whole string

la $a0, string # print the string and an end line
li $v0, 4
syscall
la $a0, endl
syscall

lw $a0, 0($sp) # load the string back into a0, since rev changed the variable

addi $t3, $0, 32 # t3 holds the value for a space, 32
add $s0, $a0, $0 # s0 is a0

outerLoop:
add $a1, $0, $0 # set the num of characters counter to 0
add $a0, $s0, $0 # set a0 to s0

innerLoop:
addi $a0, $a0, 1 # add 1 to the current address
addi $a1, $a1, 1 # add 1 to the counter
lb $t8, 0($a0) # load the byte at a0
beq $t8, $0, after # if it is the end jump to after
bne $t8, $t3, innerLoop # if there is not a space loop again


after:
add $s0, $a0, $0 # add a0 to s0 for storage
sub $a0, $a0, $a1 # subtract a1 from a0 to get to the beginning of the word
jal rev

add $a0, $s0, $0 # restore a0 after function call

lb $t8, 0($a0) # load the byte into t0
bne $t8, $0, outerLoop # if its not the end loop again






la $a0, string
li $v0, 4
syscall

 

[Mark44]

Homework Statement

The goal here is to write some MIPS functions to solve a common technical interview
question: how can you reverse the order of the words in a string? For example, reversing
the words in the string I Love Lucy would result in Lucy Love I.
A string is just an array of bytes, with each byte representing one character. The last byte
of the array is always 0, to indicate the end of the string. Also, a space is represented by
the value 32.

First write a function rev, which simply reverses bytes in an array. The arguments
passed in $a0 and $a1 are the starting address and the number of bytes to reverse.

Using the rev function, you should now be able to write revwords to reverse the
order of the words within a string.

You can implement revwords according to the following basic algorithm.
1. Call rev to completely reverse the original string. For example, I Love Lucy becomes
ycuLevoLI. Remember that strings are terminated by a 0 byte.
2. Then use rev to reverse each word in the new string—ycuLevoLI becomes Lucy Love I.
You can assume that “words” are separated by a space character, with the byte value 32.

The Attempt at a Solution

revwords isn't a function in my attempt, i put it in main for now until i get it working. I created the rev function and tested it and it works for a string. Then i went on to create the other one and that's where I'm having issues. It goes through the words and everything but the output i get is LucyLove_I_ whrere _ are spaces. I've tried to fix it where the space is still in the correct location but I cannot figure it out. The code is posted below, if anyone has any suggestions it would really help, I've spent hours trying to fix this little bug and I've lost hope.

I put your code inside [ code] [ /code] tags (w/o leading space).

.data

string: .asciiz "I Love Lucy"
endl: .asciiz "\n"
space: .asciiz "  "

.text
.globl main

rev:

#la $s0, string
#addi $a1, $0, 7

	add $t2, $0, $0		# set the counter variable to 0
	srl $t0, $a1, 1		# divide the number of characters by 2
	add $t1, $0, $a1 	# put the number of characters into t1
	addi $t1, $t1, -1	# subtract 1 from the number of characters
	add $t1, $a0, $t1 	# add to the beginning address to get to the end address

loop:
	lb $t6, 0($a0) 		# load the byte into t6 (left half) 
	lb $t7, 0($t1) 		# load the byte into $t7 (right half)
	sb $t6, 0($t1) 		# store t6 at position t1, basically swap
	sb $t7, 0($a0) 		# store t7 at position a0, swapping
	addi $a0, $a0, 1 	# get the address of the next pixel by adding 1
	addi $t1, $t1, -1 	# get the address of the previous pixel from end by adding -1
	addi $t2,$t2, 1 	# increment the counter by 1
	bne $t0, $t2, loop 	# while the counter is not equal to half the number of characters loop

	jr $ra			# jump back to where the function was called


main: 

	la $a0, string		# load the address of the string into a0

	addi $sp, $sp, -12	# make space on the stack for a0
	sw $a0, 0($sp)		# store a0
	sw $ra, 4($sp)		# store ra

	addi $a1, $0, 11	# 11 = total number of characters
	jal rev			# call rev with whole string

	la $a0, string		# print the string and an end line
	li $v0, 4
	syscall
	la $a0, endl
	syscall

	lw $a0, 0($sp)		# load the string back into a0, since rev changed the variable

	addi $t3, $0, 32	# t3 holds the value for a space, 32
	add $s0, $a0, $0	# s0 is a0

outerLoop:
	add $a1, $0, $0		# set the num of characters counter to 0
	add $a0, $s0, $0	# set a0 to s0

innerLoop:
	addi $a0, $a0, 1	# add 1 to the current address
	addi $a1, $a1, 1	# add 1 to the counter
	lb $t8, 0($a0)		# load the byte at a0
	beq $t8, $0, after	# if it is the end jump to after
	bne $t8, $t3, innerLoop	# if there is not a space loop again	

		
after:
	add $s0, $a0, $0	# add a0 to s0 for storage
	sub $a0, $a0, $a1	# subtract a1 from a0 to get to the beginning of the word
	jal rev	

	add $a0, $s0, $0	# restore a0 after function call

	lb $t8, 0($a0)		# load the byte into t0
	bne $t8, $0, outerLoop	# if its not the end loop again






la $a0, string
li $v0, 4
syscall

What I would do is find out why, when the string is reversed, the spaces are in the wrong place. After being reversed, the string should be ycuL_evoL_I(null). Note that you don't want to reverse the position of the null character - it should still be at the end.

If you're getting LucyLove_I_, something is wrong. Are you getting this on the first pass, where you reverse all the characters? Or is it happening on the second pass, where you reverse the characters in each word?

 

[SpiffyEh]

I have it printing after the first pass and i get ycuL_evoL_I which is why I'm lost. It seems to reverse it right, I think there's something wrong with my second loop that sends it each piece of the string. And thank you for putting it in those tags, i'll be sure to do that next time.

 

[Mark44]

I don't know the MIPS instruction set, so I can't help you much with the details of the code.

I would suggest trying your code with a simpler string consisting of only two words. The first part of your code should still reverse the whole string, and maybe having just one space in the string will help you figure out why the word reversal part isn't working correctly.

One comment on your code is that you are commenting nearly all the lines of code, which is a good thing. Assembly code is arcane enough that there should be lots of comments. An improvement you could make to your comments is to say what's happening rather than restate what the code is doing. In addition to comments on individual lines, it's useful to have a comment for a block of code, saying what that block is doing. E.g., in the loop (shown below) goes through the string swapping pairs of characters at a time until it reaches the middle of the string.

  add $t2, $0, $0	# set the counter variable to 0
  srl $t0, $a1, 1     # divide the number of characters by 2
  add $t1, $0, $a1 	# put the number of characters into t1
  addi $t1, $t1, -1	# subtract 1 from the number of characters
  add $t1, $a0, $t1 # add to the beginning address to get to the end address

loop:
  lb $t6, 0($a0) 	# load the byte into t6 (left half) 
  lb $t7, 0($t1) 	# load the byte into $t7 (right half)
  sb $t6, 0($t1) 	# store t6 at position t1, basically swap
  sb $t7, 0($a0) 	# store t7 at position a0, swapping
  addi $a0, $a0, 1 	# get the address of the next pixel by adding 1
  addi $t1, $t1, -1 	# get the address of the previous pixel from end by adding -1

The first two lines of the loop have comments that are not as informative as they could be. For example, you are using t6 to hold a character from the left half of the string, and t7 to hold the corresponding character from the right half of the string. If the string is abcdef, the first time through the loop t6 holds a and t7 holds f. The two characters are swapped, yielding the string fbcdea. Subsequent passes through the loop store the nth character and the len - nth character and swap them, so that you eventually end up with fedcba.

The last two comments are very misleading, talking about pixels rather than characters in the string.

Several lines have comments that merely restate the obvious without saying why they are doing it.

  add $s0, $a0, $0	# s0 is a0

  add $s0, $a0, $0	# s0 is a0

Again, it's good that you are providing profuse comments, but what does a0 + 0 represent, and why are you storing it in s0? That would be very helpful information.

Finally, what is your algorithm for taking a string that has been reversed (such as ycuL_evoL_I) and reversing the words in it. It seems to me that you would want to find out where the spaces are located, and call rev on the first substring (ycuL), skip over the space, call rev on the 2nd substring (evoL), skip over the space, and call rev on the 3rd substring (I). I can't follow your code and comments will enough to see what you are doing in outerloop and innerloop.

 

[SpiffyEh]

Thank you for all the tips. Sorry about the comments, I had them just so that I knew what was what, I usually change them before submitting any code. I really should've made it more clear. I went back and re wrote the function 2 days later and now it works fine.

 

[Mark44]

Good. I hope my tips were helpful.