title: Palindrome Checker in Mips
body: <p>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:</p>
  
  <blockquote>
    <p>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”</p>
  </blockquote>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <pre><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 #########    
  </code></pre>
  
  <p>So this is my code:</p>
  
  <pre><code># My working c++ code
  # int arrayLen ( char s[]) {
  #    int counter = 0;
  #    while(s[counter] != '\0'){
  #        if (s[counter] &gt; 64 &amp;&amp; s[counter] &lt; 91)
  #            s[counter] = s[counter] + 32;
  #        counter++;
  #    }
  #    return counter;
  # }
  #
  # int palindrom(char s[]){
  #    int i;
  #    int l = arrayLen(s);
  #    for(i=0;i&lt;=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 &gt; 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   
  </code></pre>
  
  <p>And this is where my code stop and the .data section of the test code follows: </p>
  
  <pre><code>    .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
  </code></pre>
  
  <p>My brain hurts from learning this stuff. Some direction to why it doesn't work would be appreciated, thanks :D</p>