Page 1 of 1

## NASM - Palindromes

### #1 GunnerInc

• "Hurry up and wait"

Reputation: 918
• Posts: 2,358
• Joined: 28-March 11

Posted 25 March 2013 - 07:18 PM

POPULAR

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

The following are Palindromes:
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
mov     eax, 1
jmp     .Done

.No:
push    dword [stdout]
push    szPalNo
call    fputs
.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
```

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

ecx == 1, ebx == 3, ecx !≥ ebx

Third and final iteration

ecx = 2, ebx = 2, ecx = ebx

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
```

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
```

Get the length of entered string:
size_t strlen ( const char * str );
```    push    eax
call    strlen
```

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:
cmp     byte  [eax], 0
je      .end
cmp     byte  [eax], "A"
jb      .start
cmp     byte  [eax], "Z"
ja      .start
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:

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
```

And get users choice:
int fgetc ( FILE * stream );
```    push    dword [stdin]
call    fgetc
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
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 File(s)

Is This A Good Question/Topic? 5

## Replies To: NASM - Palindromes

### #2 Curtis Rutland

• （╯°□°）╯︵ (~ .o.)~

Reputation: 5106
• Posts: 9,283
• Joined: 08-June 10

Posted 26 March 2013 - 01:22 PM

Love the illustrations. Great tutorial.

### #3 GunnerInc

• "Hurry up and wait"

Reputation: 918
• Posts: 2,358
• 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.

### #4 GunnerInc

• "Hurry up and wait"

Reputation: 918
• Posts: 2,358
• Joined: 28-March 11

Posted 28 March 2013 - 07:58 PM

Ok, created the flowchart for CleanPal. CleanPal should make more sense now.

### #5 Imray

Reputation: 0
• 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?

### #6 GunnerInc

• "Hurry up and wait"

Reputation: 918
• Posts: 2,358
• 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.