Page 1 of 1

NASM - Palindromes

#1 GunnerInc  Icon User is offline

  • "Hurry up and wait"
  • member icon




Reputation: 858
  • View blog
  • Posts: 2,279
  • Joined: 28-March 11

Post icon  Posted 25 March 2013 - 07:18 PM

This tutorial will show how to detect if text is a Palindrome

The following are Palindromes:
Madam
3/10/2013
313
A man, a plan, a canal -- Panama

How to check for a Palindrome? We will use functions from the C library so we can use basically the same code on Linux and Windows. I will include 2 zip files - 1 for Linux and the other for Windows to show the difference. The Windows version calls one extra function at the beginning - ___p__iob to get the stdout stream and stdin stream.

The following are the steps we will take:
  • Get text from user to check.
  • Convert all characters to lowercase (this is to make life easier, you could convert to all uppercase if wanted.)
  • Sanitize the text by removing anything that is not "0" - "9", "A" - "Z", and "a" - "z"
  • Finally, show if it is a palindrome.


IsPalindrome:
    push    ebp
    mov     ebp, esp
    
    mov     ecx, 0
    mov     ebx, [ebp + 12]
    mov     esi, [ebp + 8]
    dec     ebx

.CheckIt:
    mov     al, byte [esi + ecx]   
    mov     dl, byte [esi + ebx]
    cmp     al, dl
    jne     .No

    inc     ecx
    dec     ebx
    cmp     ecx, ebx
    jna     .CheckIt

    push    dword [stdout]  
    push    szPalYes
    call    fputs
    add     esp, 4 * 2
    mov     eax, 1
    jmp     .Done

.No:
    push    dword [stdout] 
    push    szPalNo
    call    fputs
    add     esp, 4 * 2
.Done:    

    leave
    ret     4 * 2


IsPalindrome takes two arguments - Pointer to string to check, and the string length.
ecx, will be our forward index into the string and ebx is the backward index in the string.
So, when we enter the procedure, we set ecx to zero and ebx to string length - 1

Let's take "madam" as an example:
First iteration:
.CheckIt:
    mov     al, byte [esi + ecx]   
    mov     dl, byte [esi + ebx]
    cmp     al, dl
    jne     .No

    inc     ecx
    dec     ebx
    cmp     ecx, ebx
    jna     .CheckIt

Attached Image
ecx == 0, ebx == 4, ecx !≥ ebx
First we move the character at index 0 in our pointer into al, then index 4 into dl.
Compare the values, and if not the same, it is not a Palindrome.
If it is, we increment our forward index and decrement our backwards index, then we compare our indexes, if our forward index is !≥ our backwards index, we are not at the middle of the string and repeat the loop. We do this check because once we get to the middle of the string, and all bytes match, there is no need to go through the whole string.

Second iteration
Attached Image
ecx == 1, ebx == 3, ecx !≥ ebx

Third and final iteration
Attached Image
ecx = 2, ebx = 2, ecx = ebx

Another palindrome is "Madam I'm Adam", let's try one that is almost a Palindrome: "Madam I am Adam"
Attached Image

First, lets print out a prompt:
"Enter text to check if Palindromic (127 chars max): "
int fputs ( const char * str, FILE * stream );
    push    dword [stdout]                  
    push    szPrompt                    
    call    fputs 
    add     esp, 4 * 2 

Next, lets get the text to test into a buffer:
char * fgets ( char * str, int num, FILE * stream );
    push    dword [stdin] 
    push    INPUT_MAX
    push    lpPalInput
    call    fgets
    add     esp, 4 * 3

Get the length of entered string:
size_t strlen ( const char * str );
    push    eax
    call    strlen
    add     esp, 4

fgets adds the newline character (ASCII 10) to our buffer, lets remove it by taking the length returned from strlen - 1 and add a NULL:
    dec     eax
    mov     byte [lpPalInput + eax], 0

Let's adjust the string length to not include the NULL and save the new length to the stack for when we call CleanPal
    dec     eax
    push    eax   

Now, we can work on the entered string. To make life easier, when we compare bytes, we will convert the string to lowercase.
ToLower takes 1 parameter - pointer to NULL terminated string to convert.
    push    lpPalInput
    call    ToLower

;~ #########################################  
;~ ToLower
;~ Purpose:    Converts string to lowercase
;~ Input:      [esp + 4] = pointer to null terminated string to convert
;~ Returns:    nothing
;~ #########################################  
ToLower:
    mov     eax, [esp + 4]
    dec     eax

.start:
    add     eax,  1
    cmp     byte  [eax], 0
    je      .end
    cmp     byte  [eax], "A"
    jb      .start
    cmp     byte  [eax], "Z"
    ja      .start
    add     byte  [eax], 32
    jmp     .start
    
.end:
    ret     4

All ToLower does, is loop through the string byte by byte, and if the value is between "A - Z" (65 - 90) it adds 32 to the value, anything else, it skips and repeats the loop until we reach a NULL.

Next, we "Sanitize" the inputed string. This will remove all characters that are not "0 - 9", "A - Z", and "a - z".
CleanPal takes 2 parameters - Pointer to string to clean, and the length.
    push    lpPalInput
    call    CleanPal

You might be asking, why am I passing only 1 parameter? Well, right before we called ToLower, we pushed the string length that was in eax onto the stack. That value is still there, so we will use it.
;~ #########################################  
;~ CleanPal
;~ Purpose:    Sanitize string. Removes chars not "0 - 9", "A - Z", "a - z"
;~ Input:      [esp + 4] = pointer to string to clean
;~             [esp + 8] = string length
;~ Returns:    ecx = Sanitized string length
;~ ######################################### 
CleanPal:
    mov     esi, [esp + 4]
    mov     edx, [esp + 8]
    mov     ebx, 0
    mov     ecx, 0    
    
.Do:
    movzx   eax, byte [esi + ebx]
    
    push    ecx
    push    eax
    
    push    eax
    call    IsValidChar
    test    eax, eax
    jz      .Next

    pop     eax
    pop     ecx

    mov     byte [esi + ecx], al
    inc     ecx
    jmp     .Good
    
.Next:
    pop     eax
    pop     ecx

.Good:    
    inc     ebx
    
    dec     edx
    jns     .Do

    mov     byte [esi + ecx], 0
    dec     ecx
    
    ret     8


CleanPal, loops through the string, takes the character and checks to see if it is a valid character, if it is, move to the left if the previous character is invalid.
Let's use the date: 9/9/9 as an example. This is what CleanPal does:
Attached Image
After all that is done, we now can check if it is a valid palindrome and print yes if it is, or no if it is not.

Print "Check another? (y/n): ":
    push    dword [stdout]                  
    push    szPromptAgain                    
    call    fputs 
    add     esp, 4 * 2 

And get users choice:
int fgetc ( FILE * stream );
    push    dword [stdin]
    call    fgetc
    add     esp, 4     
    cmp     al, "Y"
    je      .GoAgain
    cmp     al, "y"
    jne     .Done

If the user enters either "Y" or "y" we will jump back to the beginning of the program and start the process all over again. But first, we need to remove the newline character from the stream:
.GoAgain:
    push    dword [stdin]
    call    fgetc
    add     esp, 4 
    cmp     al, 10
    jne     .GoAgain
    jmp     main


Hope that explains how to test for a Palindrome. Modify it, learn from it, and have fun!

Unfortunately, I could not upload a tar.gz, so I zipped it in Linux. Included in both zips, are a bunch of Palindrome sentences to test with.
Attached Image

Attached File(s)



Is This A Good Question/Topic? 4
  • +

Replies To: NASM - Palindromes

#2 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4450
  • View blog
  • Posts: 7,748
  • Joined: 08-June 10

Posted 26 March 2013 - 01:22 PM

Love the illustrations. Great tutorial.
Was This Post Helpful? 0
  • +
  • -

#3 GunnerInc  Icon User is offline

  • "Hurry up and wait"
  • member icon




Reputation: 858
  • View blog
  • Posts: 2,279
  • Joined: 28-March 11

Posted 27 March 2013 - 06:42 PM

Thanks, as they say "A picture is worth a thousand words". I felt images would help convey what is going on. I rushed the last images for CleanPal, once I get a chance I will make a new one.
Was This Post Helpful? 0
  • +
  • -

#4 GunnerInc  Icon User is offline

  • "Hurry up and wait"
  • member icon




Reputation: 858
  • View blog
  • Posts: 2,279
  • Joined: 28-March 11

Posted 28 March 2013 - 07:58 PM

Ok, created the flowchart for CleanPal. CleanPal should make more sense now.
Was This Post Helpful? 0
  • +
  • -

#5 Imray  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 23-April 13

Posted 23 April 2013 - 09:33 PM

It doesn't explain where the string is stored (is it in esi?).
Also, can you explain why you are adding 12 and 8 to ebp?
Was This Post Helpful? 0
  • +
  • -

#6 GunnerInc  Icon User is offline

  • "Hurry up and wait"
  • member icon




Reputation: 858
  • View blog
  • Posts: 2,279
  • Joined: 28-March 11

Posted 24 April 2013 - 07:00 PM

Hmm, no post? Guess I forgot to hit post last night... oh well...

Quote

It doesn't explain where the string is stored (is it in esi?

I use a buffer called lpPalInput in the .bss section which will hold the inputed string. eSi is used as a source register, so the functions IsPalindrome and CleanPal, I use esi to hold a pointer to the buffer.

Quote

Also, can you explain why you are adding 12 and 8 to ebp

I think you meant esp?
It has to do with x86 Calling Conventions. The functions that I call - fputs, fgetc, fputs, etc... use the CDECL calling convention which says the caller must adjust the stack after the call. You do this by adding the number of bytes pushed onto the stack for the call to esp after the call. I personally use add esp, 4 * NUM_OF_PARAMETERS_PUSHED. In x86 the stack is DWORD aligned, 4 bytes per parameter, hence the 4.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1