52685

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?

Answer1:

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

<hr />

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 <hr />

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.

<hr />

And learn how to use <a href="https://stackoverflow.com/a/5563572/4271923" rel="nofollow">"procedures" in MIPS ASM</a>, 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.

Recommend

  • How to clone the content of a tab to the rest of the tabs Jquery
  • subtraction of time in two different lines in a text file using python
  • filename of memory mapped libraries osx
  • LINQ error: The null value cannot be assigned to a member with type System.Int32 which is a non-null
  • What causes amqp.node to get ECONNRESET from a RabbitMQ server?
  • The script does not work in IE. How can I fix it?
  • How to use case/esac in process substitution?
  • Excel changes conditional formatting formula
  • Matlab FFT and FFTW
  • How to perform a left join in SQLALchemy?
  • Dynamically load images from project folder - Windows Phone 7
  • About multiple inheritance and ambiguity
  • PHP: Convert single-quoted string into double-quoted
  • Forward slash in last argument causes path to directory of batch file (“%~dp0”) to change
  • how to execute 50 parallel methods 500 times per second effectively?
  • Pasting URLs That Have Been Scraped From a Webpage
  • Pass pointer array to function
  • Function calling incorrect values
  • How can I filter REST calls results based on Roles and current user context in Loopback (server side
  • Is there a way to get the process ID of a console program I've just started in the background?
  • TCameraComponent and TVideoCaptureDevice do not initialize in Win32
  • cordova build android throws error on Ubuntu 12.04
  • ASP.NET MVC - Detect Time Spent on Page
  • Excel 2007: Format of email address from Outlook 2007
  • How to debug Shell command after customization
  • How to make stdcall from Go
  • pygame.init() shows as undefined variable after installing Pygame
  • Curried UDF - Pyspark
  • Pythons argparse default value doesn't work
  • How to repeat sections of a SQL query across UNIONs? (DRY in SQL)
  • Are there any issues with placing image as background on an extended JFrame?
  • jersey/tomcat Description The origin server did not find a current representation for the target res
  • Java making confirming exit
  • Magento get URL before current
  • Ubuntu and bcrypt
  • Using JRuby with Rails 3.2
  • Code in Job's Script Block after Start-Process Does not Execute
  • Installing iPhone App to iPhone
  • Obtain ObjectIdHex value from mgo query
  • How to model a transition system with SPIN