Reputation: 5
Palindrome Checker in Mips
I'm taking a computer organization class that teaches the low level functions of computers through MIPS Assembly. One problem on a homework is a palindrome checker. Here it is:
Write a MIPS function (called “palindrome”) that returns 1 if the input string is a palindrome and returns 0 otherwise. The address of the string will be passed in $a0 and the value should be returned in $v0. Here a string is a palindrome if it reads the same in forward or backward direction (including white spaces, punctuation marks, and so on, but is case insensitive (i.e., „A‟ and „a‟ are considered to be the same)). Note the string is ended with „\0‟ (C/C++ convention). You need to test your program using “test_palindrome.s”
I wrote a simple c++ program to solve the problem, including a basic tolower function. I then manually translated it to mips. I've gotten it to run, but checking the palindrome test strings with the my c++ program against the mips program, I don't get the same result.
To test the mips functions, I'm using a program the professor provided. It says none of them are palindromes. Here is the MIPS code, there is a commented section showing my original c++ code.
# Program to test if a palindrome function works properly or not
# Written by Xiuwen Liu for CDA 3100 - Homework #3, problem #2
# Register usage
# $s7 - save $ra
# $s2 - current address of the string to be tested
# $s3 - the next of the last string to be tested
# $a0 - for function parameter / syscall parameter
# $v0 - syscall number / function return value
.text
.globl main
main:
addu $s7, $ra, $zero, # Save the ra
la $s2, test_str # Load the starting address of the array
la $s3, is_pali_msg, # the next of last address
pali_test_loop:
lw $a0, 0($s2) # $a0 is the address of the string
li $v0, 4 # system call to print a string
syscall # print string
li $v0, 4 # print a new line
la $a0, newline
li $v0, 4
syscall
lw $a0, 0($s2) # $a0 is the address of the string
jal palindrome # call palindrome
beq $v0, $zero, pali_no #if $v0 is 0, it is not a palindrome
li $v0, 4 #it is a palindrome
la $a0, is_pali_msg
syscall
j pali_test_end
pali_no: #it is not a palindrome
li $v0, 4
la $a0, not_pali_msg
syscall
pali_test_end:
li $v0, 4
la $a0, newline
syscall
addiu $s2, $s2, 4
lw $a0, 0($s2)
beq $a0, $s3, pali_done
j pali_test_loop
pali_done:
li $v0, 10
syscall
addu $ra, $zero, $s7 #restore $ra since the function calles
#another function
jr $ra
add $zero, $zero, $zero
add $zero, $zero, $zero
########## End of main function #########
So this is my code:
# My working c++ code
# int arrayLen ( char s[]) {
# int counter = 0;
# while(s[counter] != '\0'){
# if (s[counter] > 64 && s[counter] < 91)
# s[counter] = s[counter] + 32;
# counter++;
# }
# return counter;
# }
#
# int palindrom(char s[]){
# int i;
# int l = arrayLen(s);
# for(i=0;i<=l/2;i++)
# if(s[i]!=s[l-i-1]) return 0;
# return 1;
# }
palindrome:
addu $s4, $ra, $zero # save $ra
jal arrayLen # get string length and set to lowercase
move $t0, $zero # i = 0
move $t1, $v1 # l = arrayLen(s)
srl $t2, $t1, 1 # divide l by 2
palinFor:
bgt $t0, $t2, palinForExit # end for loop when i > l/2
sub $t3, $t1, $t0 # l - i
addi $t3, $t3, -1 # l - i - 1
add $t4, $a0, $t0 # s[i]
add $t5, $a0, $t3 # s[l-i-1]
addi $t0, $t0, 1 # i++
lbu $t4, ($t4) # load s[i]
lbu $t5, ($t5) # load s[l-i-1]
sne $t6, $t4, $t5 # if not equal, set $t6 to 1
beq $t6, 1, palinForExit # leave loop if not equal
j palinFor # loop again
palinForExit:
sne $v0, $t6, $zero # set return value: 0 for not palindrome, 1 for palindrome
addu $ra, $zero, $s4 # restore $ra
jr $ra # return to function caller
arrayLen:
li $t0, 0 # counter = 0
sll $t1, $t0, 2 # counter * 4
add $t1, $t1, $a0 # address of s[counter] in $t1
lbu $t2, ($t1) # load s[counter]
while:
beq $t2, 0, whileEnd # skip to end of while loop if s[counter] == \0
blt $t2, 64, breakIf # skip if not uppercase range
bgt $t2, 91, breakIf # skip if not uppercase range
addi $t2, $t2, 32 # add 32 to make character lowercase
sw $t2, ($t1) # save change to memory
breakIf:
addi $t0, $t0, 1 # counter++
whileEnd:
move $v1, $t0 # return value of arrayLen is counter
jr $ra # return to function caller
And this is where my code stop and the .data section of the test code follows:
.data
#The following examples were copied from
# http://en.wikipedia.org/wiki/Palindrome
pali1:
.asciiz "Socorram me subi no on ibus em Marrocos" #Brazilian Portuguese
pali2:
.asciiz "Ein Neger mit Gazelle zagtim Regen nie" #German
pali3:
.asciiz "stressed desserts"
pali4:
.asciiz "palindromes"
pali5:
.asciiz "tattarrattat"
is_pali_msg:
.asciiz " The string is a palindrome."
not_pali_msg:
.asciiz " The string is not a palindrome."
newline:
.asciiz "\n"
test_str:
.word pali1, pali2, pali3, pali4, pali5, is_pali_msg
My brain hurts from learning this stuff. Some direction to why it doesn't work would be appreciated, thanks :D
Upvotes: 0
Views: 18884
Answers (1)
Reputation: 78
try this:
.text
strlen:
# ------------
# arguments:
# a0 = string
# ------------
li $v0, 0 #set return value to 0
strlen_loop:
lb $t0, 0($a0) #load byte from beginning of the string
beq $t0, $0, strlen_exit #when character value is 0 we have
#reached the end of the string
addi $a0, $a0, 1 #shift pointer to string one space right
addi $v0, $v0, 1 #increment return value by one
j strlen_loop
strlen_exit:
# ------------
# returns:
# INTEGER (string length)
# ------------
jr $ra #return
palindrom:
# ------------
# arguments:
# a0 = string
# ------------
sub $sp, $sp, 8 #allocate memory on stack
sw $ra 0($sp) #save return address
sw $a0 4($sp) #save argumrnt value
jal strlen #call strlen
move $t0, $v0 #save result
lw $a0 4($sp) #load argument
move $t1, $a0 #save its value to t1
li $t2, 1 #set counter to 1
li $v0, 1 #prepare return value
div $t3, $t0, 2 #calculate string length / 2
addi $t3, $t3, 1 #add one more in case of even number
palindrom_loop:
bge $t2, $t3 palindrom_exit #when counter reaches half of the string length - exit
lb $t4, 0($a0) #get character from beginning
sub $t5, $t0, $t2 #subtract counter from the string length
add $t6, $t5, $t1 #add index from the end of the string to start address
lb $t7, 0($t6) #get corresponding character from the end of the string
beq $t4, $t7, palindrom_continue #check to determine are the characters exact match
li $v0, 0 #if not return 0, immediately
j palindrom_exit
palindrom_continue:
addi $a0, $a0, 1 #shift pointer to string one space right
addi $t2, $t2, 1 #increment counter by one
j palindrom_loop
palindrom_exit:
# ------------
# returns:
# TRUE (1) or FALSE (0)
# ------------
lw $ra 0($sp) #load return address
addi $sp, $sp, 8 #free stack
jr $ra #return
main:
#entry point
la $a0, str #load string
jal palindrom #call palindrom
move $a0, $v0 #set a0 to palindrom return value
li $v0, 1 #set 1 to v0 - as this is system call for print int
syscall #make the call
li $v0, 10 #set 10 to v0 - as this is system call for exit program
syscall #make the call
.data
str: .asciiz "thiispalindrome_emordnilapsiiht"
The approach is to get character from beginning and the corresponding character from the end of the string. If they are exact match, continue execution by the time when counter reaches half of the string length. If any pair of characters are found different, stop execution immediately and return FALSE.
One more thing, I haven't implemented part where upper case letters are not different from the lower case letters. But it isn't hard. You can add it yourself. The idea is to test each loaded character if it's ascii is between A (65) and Z (90). If so you'll add 32 to ascii value and you'll get lower case letter.
Upvotes: 4
Related Questions
- Check palindrome using mips assembly
- Checking if the user's input is a palindrome
- Palindrome Generation in MIPS
- check whether string is a palindrome - assembly language
- 8086 masm program for palindrome checking
- Asm program to check for a palindrome
- Code to test if string is palindrome - MIPS
- MIPS Palindrome Check
- Palindrome Checker
- Palindrome Checker in C