check for palindromic string

[beginthreadex]

I needed to create a validator for a palindromic string of /[a-z]*/ and thought to explore doing the function in NASM. I'm looking for some source review to give me some ideas on how this might be better syntax. Please, let me know:

Code: [Select]

global _start

section .data

err_zero: db "the search string empty", 10, 0
err_zero_len: equ $-err_zero

pure_pal: db "the search string is 1 character. it is be definition a pal", 10, 0
pure_pal_len: equ $-pure_pal

is_pal: db "the string is a pal", 10, 0
is_pal_len: equ $-is_pal

is_not_pal: db "the string is not a pal", 10, 0
is_not_pal_len: equ $-is_not_pal

pal: db "thomas"
pal_len: equ $-pal

section .text

_start:
mov ecx, pal_len ;get the length of the potential pal
cmp ecx, 1 ;compare to 1
ja long_test ;if char count > 1 goto the loop test
je of_course ;if only 1 char then goto "of_course"

empty_pal: ;fall through: empty pal string
mov edx, err_zero_len
mov ecx, err_zero
mov ebx, 1
mov eax, 4
int 0x80
jmp endend

of_course: ;of course it's a pal. just 1 char
mov edx, pure_pal_len
mov ecx, pure_pal
mov ebx, 1
mov eax, 4
int 0x80
jmp endend

long_test: ;start of the long loop test

mov ecx, pal_len ;get the count of chars in the pal
xor edx, edx ;clear out the bit flags
xor eax, eax ;clear out the total count

loop: ;begin of loop
dec ecx ;decrease the index array because we are base zero

movzx esi, byte [pal + ecx] ;get the ansi number of the character
sub esi, 97 ;reduce the string value to be inside the alphabet flags
btc edx, esi ;bit swap just that bit
jnc missmatch ;if the return of the swap was 0 then we have a missmatch
dec eax ;else -- we matched and should decrease the missmatch count
jmp next ;attempt the next char if possible
missmatch: ;we have a missmatch detected
inc eax ;increase the missmatch count

next:
jecxz out ;compare the index loop to 0 to see if we are at the start
jmp loop ;go to the next character

out:
cmp eax, 1 ;see how the total count compares to 1
ja notpal ;only if there are more than 1 should we know it's not a pal
mov edx, is_pal_len
mov ecx, is_pal
mov ebx, 1
mov eax, 4
int 0x80
jmp endend
notpal: ;oops, it's not a pal
mov edx, is_not_pal_len
mov ecx, is_not_pal
mov ebx, 1
mov eax, 4
int 0x80

endend: ;exit the application
xor ebx, ebx
mov eax, 1
int 0x80


[gammac]

Hi, test this string: "abab"

[beginthreadex]

The string "abab" works fine and reports that it has the potential for a palindromic result. By itself it's not palindromic but rearranged it could be; which is what I was going for.

Gammac, my use of the movzx to get the char number then sub the 97 to get it inside the bit range ... is there a better way to do that? I'd like to make sure I'm using the best techniques as I'm learning.

[gammac]

Sorry, I'm not sure what you are going for? Are you going for an algorithm that makes an palindromic out of a bunch of letters like "abab"?

If you are going for a test algorithm, then you have to implement a second test. I would think, If that will be done, then you see that the first check was unnecessary.

EDIT: I think you will see that for both cases.

[beginthreadex]

I'm trying to take a string of lower case chars and test to see if they could be potentially arranged in a way that would result in a palindromic string. I don't care what the palindromic strings are, just that it's possible. It's working exactly as I expected by confirming if a string COULD be palindromic if it were rearranged. There's no need for the arrangement though. The goal is completed, I was hoping for more of feedback on my use of grammar and syntax and see if there was something wrong or ugly that I was doing.

I've been reading other people's posts and see that the "%macro" can clean up code so I've adjusted my source to look like this (:

Code: [Select]

global _start

section .data

err_zero: db "the search string empty", 10, 0
err_zero_len: equ $-err_zero
pure_pal: db "the search string is 1 character. it is be definition a pal", 10, 0
pure_pal_len: equ $-pure_pal
is_pal: db "the string is a pal", 10, 0
is_pal_len: equ $-is_pal
is_not_pal: db "the string is not a pal", 10, 0
is_not_pal_len: equ $-is_not_pal
pal: db "abab"
pal_len: equ $-pal

%macro _stdout 2
mov ecx, %1
mov edx, %2
mov ebx, 1
mov eax, 4
int 0x80
%endmacro

section .text
_start:
mov ecx, pal_len ;get the length of the potential pal
cmp ecx, 1 ;compare to 1
ja long_test ;if char count > 1 goto the loop test
je of_course ;if only 1 char then goto "of_course"

empty_pal: ;fall through: empty pal string
_stdout err_zero, err_zero_len
jmp endend

of_course: ;of course it's a pal. just 1 char
_stdout pure_pal, pure_pal_len
jmp endend

long_test: ;start of the long loop test

mov ecx, pal_len ;get the count of chars in the pal
xor edx, edx ;clear out the bit flags
xor eax, eax ;clear out the total count

loop: ;begin of loop
dec ecx ;decrease the index array because we are base zero

movzx esi, byte [pal + ecx] ;get the ansi number of the character
sub esi, 97 ;reduce the string value to be inside the alphabet flags
btc edx, esi ;bit swap just that bit
jnc missmatch ;if the return of the swap was 0 then we have a missmatch
dec eax ;else -- we matched and should decrease the missmatch count
jmp next ;attempt the next char if possible
missmatch: ;we have a missmatch detected
inc eax ;increase the missmatch count

next:
jecxz out ;compare the index loop to 0 to see if we are at the start
jmp loop ;go to the next character

out:
cmp eax, 1 ;see how the total count compares to 1
ja notpal ;only if there are more than 1 should we know it's not a pal
_stdout is_pal, is_pal_len
jmp endend
notpal: ;oops, it's not a pal
_stdout is_not_pal, is_not_pal_len

endend: ;exit the application
xor ebx, ebx
mov eax, 1
int 0x80


[gammac]

OK, last try.

Are you looking for an answer like that:

Not tested but it should work, hopefully.

Code: [Select]

_start:
mov ecx, pal_len
cmp ecx, 1
jc .empty_string
jz .one_byte_string

mov esi, pal
xor eax, eax
xor edx, edx

.lbl lodsb
sub eax, 97
btc edx, eax
loop .lbl

bsf ecx, edx
jz .pot_pal

bsr eax, edx
cmp eax, ecx
jnz .not_pot_pal

.pot_pal

;print "could be aranged as palindromic string"

jmp .exit

.empty_string

;print "you gave me an empty string"

jmp .exit

.one_byte_string

;print "one byte string is per definition a pal"

jmp .exit

.not_pot_pal

;print "not a potential palindromic string"

.exit

; your exit code

EDIT: ... now it should work.

[beginthreadex]

I'm not super familiar with some of those ops so I need a bit of time to look them up. I need to find what flags are set during operations because what you've provided is a little "magically" to me right now. Let me review and compare and make another comment later. Overall ... thank you!!

[beginthreadex]

gammac, there were certainly some things I needed to look up. First was the "jc" versus "jb" ... and I have that resolved. Next was the "lodsb" and "loop". Now my documentation states that the "loop" is only effective if within 128 bytes of the jump label. How can you count to make sure this happens so you don't blow the loop op?

Oh, I tried and tried to find an instruction that would give me a count of the bits in a long without success. I really like your use of bsf and bsr to test if more than 1 bit was set. It's not that you care about the number you just need to know that the flag is singleton or does not exist ... brilliant.

With such small code I guess I shouldn't be too concerned about pipelining or stalls. While I wasn't able to understand your source initially I do now. Thanks. Now I need to find some more puzzle things to keep my self-study going. 

[gammac]

Now my documentation states that the "loop" is only effective if within 128 bytes of the jump label. How can you count to make sure this happens so you don't blow the loop op?

nasm throws an error.