Assembly MIPS: Checking if a string is palindromic or not

Question

Palindromic is a string that can be read both ways. like "radar", "wow" etc.

From C we know that we can check a given string with a "for" loop and an "if" expression:

for(i=0; i<length; i++)
   if(str[i] == str[length-i-1])
      printf("Palindromic");
   else
      print("Non Palindromic");

so that way we can reach to the center of the string by both sides.

This code requires that we have counted the characters to know the length of the string.

On MIPS, this "for" loop seems quite complex.

Here's where I got myself:

.data
str: .space 20
isntpal: .asciiz "it is not palindromic!"
ispal: .asciiz "it is palindromic!"

.text
.globl main
main:

add $t0, $zero, $zero   #t0 = i counter for the loops
add $t1, $zero, $zero   #t1 = j counter for length of the string

li  $v0, 8          #gets(str)
la  $a0, str
la  $a1, 20
syscall

length:
    lb  $s0, str($t0)  #load each character to s0

    beq $s0, '\0', NEXTCHECK 

    add $t0, $t0, 1 #i++ to scan all the characters of the string

    add $t1, $t1, 1 #j++ for the total length of the string

j length

NEXTCHECK:


add $t0, $zero, $zero   #clean the t0 register from the length loop


pal: 
    sub $t4, $t1, $t0   #length - i - 1
    sub $t4, $t4, 1 

    lb  $s0, str($t0)   #str[i]
    lb  $s1, str($t4)   #str[length-i-1]

    slt $t3, $t0, $t1       #for(i=0; i<length; i++)
    beq $t3, $zero, EXIT

    add $t0, $t0, 1         #i++

    beq $s0, $s1, ELSE      #if (str[i] == str[length-i-1])


    li  $v0, 4          #printf("It is palindromic");
    la  $a0, ispal
    syscall
    j EXIT


    ELSE:

    li  $v0, 4              #else printf("It is not palindromic");
    la  $a0, isntpal
    syscall

    j EXIT

j pal

EXIT:

li  $v0, 10
syscall

I have a problem understanding where i should have the EXIT and ELSE labels, and I think this is why it always returns that the string is palindromic, even if it isn't.

What is the correct way to put the labels?

Does it need more than one label?

There's no need for `i` to go all the way to `length-1`. Have two pointers, where one starts at `str` and the other at `str+length-1`. Then read a pair of characters using those two pointers, and compare the characters. If the characters are not equal the string is not a palindrome. If the characters are equal you increment the first pointer and decrement the second. If the first pointer now is greater than the second the string is a palindrome and you're done, otherwise you keep going. — Michael, Nov 14 '16 at 11:44
if the first pointer is greater than *or equal to* second pointer, it is palindrome - for odd length strings this will exit 1 char earlier, not testing `(str[middle] == str[middle])`. — Ped7g, Nov 14 '16 at 11:45
@Michael that sounds more complicated and my brain is close to toasted. — Coursal, Nov 14 '16 at 12:07
Clean your algorithm steps in abstract level first, check for example your `length` calculation, you have identical values $t0 and $t1, the whole loop. One you use as index, other as length counter. If you would look at it first on some higher level, you would maybe realize they are equal, and only one of them is needed. By similar way you can produce shorter asm programs. If you just write down the first idea you get, you can end up with lot of duplicated code, like the display of string at end of your code. If you set `a0` to wanted string, you can use single code path to display it and exit — Ped7g, Nov 14 '16 at 12:34
And neither me, nor Michael, pointed out to you your C example is wrong (reports "woaw" as palindrome + not palindrome). Because it was probably too obvious for us. But now I see your asm implementation has the same problem. So it's probably worth to point it out. If you have some nice C++ IDE around with debugger, try your code with different inputs to see what's the problem of it. And also try my version from answer to see how it works first in C. — Ped7g, Nov 14 '16 at 12:38
I duplicated my code so that I don't mistake any register with another. I'm a newbee as far as anyone can tell, and your surely helpful answer and comments fly above my head. I never though of using strings, I didn't even know how to use them in mips. I just want the programme to show with a message if the string is a palindrome or not. — Coursal, Nov 14 '16 at 12:42
So keep re-reading any lessons/tutorials you have plus our comments, until you can point out some particular thing which is unclear to you, or till it will start to make sense. It's difficult to point you what you need, as for example I take for granted: you understand what is computer memory/address, what is byte/word, how to debug your code, how CPU works (deterministic state machine), what is CPU register and that you understand C/C++ code/comments, etc... Learning programming takes time, especially getting experience to be at least mediocre at it. — Ped7g, Nov 14 '16 at 12:55

score 1 · Accepted Answer · edited May 23 '17 at 10:32

Correct and efficient C version:

bool is_palindrome(const char * str, const size_t length) {
    const char * frontptr = str;            // front pointer: points at the very first character of string
    const char * backptr = str + length-1;  // back pointer: points at the very last character of string
    while (frontptr < backptr) {            // while front pointer points ahead of back pointer
        if (*frontptr != *backptr) return false;    // characters differ => not a palindrome
        ++frontptr;     // move front pointer at next character in string
        --backptr;      // move back pointer at "next" character toward start of string
    }
    // front pointer points at/beyond back pointer
    // all chars were compared (except middle one for odd length string, which is "palindromic" always)
    // and all were equal, thus the input string is a palindrome, if this point is reached
    return true;
}

This C code is written intentionally in a way, which should make it very straightforward for conversion to ASM (like 1-2 instructions per C line).

How to load a value from memory, if you know it's address (pointer in C):

la   $a0,some_address   # a0 = address (pointer)
lb   $t0,($a0)          # t0 = byte loaded from memory at a0

How to increment/decrement pointers in ASM: you add to the current value of pointer the size of the element pointed at.

With ASCII string the elements are single bytes, so to move one character forth/back you have to add +1/-1 to the pointer, like:

addi $a0,$a0,1    # ++byte_ptr
addi $a1,$a1,-1   # --byte_ptr

If you would work with word array, you would want to do +-4 to move the pointer one element forth/back.

And learn how to use "procedures" in MIPS ASM, so you can create some generic universal "get string length" code, and then re-use it later by simple copy/paste (unless you create eventually some library of your own).

Also the palindrome test can be done as separate procedure, if you follow the C++ example.

The in the main you would have a bit simpler code to maintain + debug + reason about:

# input string
# prepare arguments for get_length
# call get_length
# process result and prepare arguments for is_palindrome
# call is_palindrome
# set a0 to one of the two result strings based on return value
# display string
# exit

May be a bit longer on total number of instructions, as you will have additional jal and jr $ra lines, but it will allow you to focus on shorter and simpler parts of code while writing/debugging.

Assembly MIPS: Checking if a string is palindromic or not

1 Answers1

Linked