1/23/09

MIPS Reverse a String

MIPS example to reverse a string.

First it will be better to show how MIPS stores strings.

e.g.
the phrase "computerblog"
will be saved (address start form down to up):















??????00(zero byte)0x...b
g = 67o = 6fl = 6cb = 620x...8
r = 72e = 65t = 74u = 750x...4
p = 70m = 6do = 6fc = 630x...0


0x??????00 0x....b
0x676f6c62 0x....8
0x72657475 0x....4
0x706d6f63 0x....0

and reversed should be:
0x20736c00 0x....b
0x636f6d70 0x....8
0x75746572 0x....4
0x626c6f67 0x....0

when making syscall with 4 (li $v0,4) and $a = x00
will start printing bytes (characters) till the ending 0 (a zero byte)

Now I think it will be easier to understand the following MIPS code.
At this point it would be good to mention that it works only if the string length is even (2,4,6...2*k).
If you want it for odd length strings too you can solve it by changing the strreverse (after exiting loop if odd do another one loop) and please leave your comments.
Anw, this is the code (lines with comment *change means that it affects the table size or the strreverse function):

.data
.align 1
String: .space 14 #*change
msg1: .asciiz "Pls give a character: "
msg2: .asciiz "\n"
msg3: .asciiz "String is: "
msg4: .asciiz "\nString Reversed is: "
.text
.globl main
main:

addi $s0,$zero,13 #*change
addi $t0,$zero,0

in:
la $a0,msg2
li $v0,4
syscall

li $v0,4
la $a0,msg1
syscall
li $v0,12
syscall

add $t1,$v0,$zero
sb $t1,String($t0)
addi $t0,$t0,1
slt $t1,$s0,$t0
beq $t1,$zero,in

sb $zero,String($t0) #ending zero

la $a0,msg2
li $v0,4
syscall
la $a0,msg2
li $v0,4
syscall
la $a0,msg3
li $v0,4
syscall

la $a0,String
li $v0,4
syscall

addi $a1,$zero,14 #pass length-*change
jal stringreverse #reverse

la $a0,msg2
li $v0,4
syscall

la $a0,msg4
li $v0,4
syscall

la $a0,String
li $v0,4
syscall

li $v0,10
syscall


stringreverse:

add $t0,$a0,$zero #beginning address

add $t1,$zero,$zero #i=0
addi $t2,$a1,-1 #j=length-1

loop:

add $t3,$t0,$t1
lb $t4,0($t3) #lb String[i]

add $t5,$t0,$t2
lb $t6,0($t5) #lb String[j]

sb $t4,0($t5) #String[j]=String[i]
sb $t6,0($t3) #String[i]=String[j]

addi $t1,$t1,1 #i++
addi $t2,$t2,-1 #j--
#if i>=j break - $t1<$t2
slt $t6,$t2,$t1
beqz $t6,loop

jr $ra

#i-0;j=length-1;
# do {
# x = str[i]
# str[i]=str[j]
# str[j] = x
# i++;j--;
# } while(!(j<i))

Example of output:

Pls give a character: c
Pls give a character: o
Pls give a character: m
Pls give a character: p
Pls give a character: u
Pls give a character: t
Pls give a character: e
Pls give a character: r
Pls give a character: s
Pls give a character:
Pls give a character: b
Pls give a character: l
Pls give a character: o
Pls give a character: g

String is : computers blog

String Reversed is : golb sretupmoc

You may also want to see my post about how to reverse a file in C / C++.

I hope you find this post helpful and please leave your comments. Thank you.

6 comments:

Anonymous said...

I remember my college days when i was really having trouble with my Java subject. reading the codes gives me a hard time.LOL

little monster said...

Hi there! I learning MIPS and have used yr code at reference :D

I think there is a pb in yr reverse algorithm: $t1 and $t2 are the index.

However, in those 2 lines below:

add $t3,$t0,$t1
lb $t4,0($t3) #lb String[i]

$t1 is added $t0 to form the value which become effective address of string[i]

now if u want to move to string[i+1]; the address must be increment by 4. However, u just increment $t1 by 1 only.

Plz reply me at mnpham@csupomona.edu.

Another Computers Blog said...

Hi there!
Thank you for visiting my blog and commenting my posts. :)

I think you got smt wrong here and I'm glad you asked.

If I increase the address by 4 I won't get the next byte [ I'm using lb (load byte) above, not lw (load word) ] but the first byte of the next word. That means I 'll be getting only the 1,(1+4)=5,9,13...bytes (chars) and not all the bytes (chars) of the string.

As I (think I) explain above the code you cannot reverse the 1st word with the last one and get the correct string reversed. You must reverse it byte-byte (char-char) to have correct result.

For the above example the first 8 chars and addresses are:
c = 63 - 0x...0
o = 6f - 0x...1
m = 6d - 0x...2
p = 70 - 0x...3
u = 75 - 0x...4
t = 74 - 0x...5
e = 65 - 0x...6
r = 72 - 0x...8
and goes on.
So I must increase index by 1 and not 4.

I hope this will help you understand this example (and may smt more). If you still don't get smt I 'm expecting your next comment!

Thank you.

Anonymous said...

i know this was posted in the 2009, but anyway i wanted to say thank you becouse this helped me .

Anonymous said...

Hello! this is a great post! this is very helpfull. but instead of reading character one by one everytime, is it possible to read the whole phrase as a string and then reverse it?

Anonymous said...

U ask us to leave comments... how about u put comments in ure program so that ppl who dont know all the commands understand smth of your code!