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 # 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
1 Answer
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.
