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?
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.
