I was looking at MSVC's strcmpi() ASM source and noticed that its test for case insensitive byte equality was a little excessive. I wrote this little snippet which I have put in my own case-insensitive comparisons and hopefully somebody else can use it.

[size=12][color=grey]; [in]  al = 1st character

; ah = 2nd character[/color]

[color=grey]; [out] ZF = 1 (match)
; ZF = 0 (no match)[/color]

cmp al, ah
jz @f
or eax, 2020h
cmp al, ah
jnz @f
sub al, 61h
sub al, 1Ah
sbb al, al
inc al
@@:[color=#A0A0A0] jz @match[/color][/size]



It could most probably be faster using a lookup table but I personally don't really want the extra size. Optimisations anyone? ;)
Posted on 2003-03-05 02:18:38 by iblis

Hi iblis,
From a quick look at the src I'd say it doesn't work as it should.
The problem is that OR .. which would make seem equal characters that aren't equal (e.g. signs).

This is a possible alternative for a ToUpper routine:


;>=P6 (CMOV instruction supported)
; LEA EBX,[EAX-'a']
; LEA ECX,[EAX-32]
; CMP EBX,BYTE 'z'+1-'a'
; CMOVC EAX,ECX


;<=P5 (no CMOV instruction)
; LEA EAX,[EAX-'a']
; CMP EAX,BYTE 'z'+1-'a'
; SBB EBX,EBX
; AND EBX,BYTE -32
; LEA EAX,[EAX+EBX+'a']
Posted on 2003-03-05 02:39:56 by Maverick
Hi Maverick,

I'm fairly certain that it works. I tested it byte for byte every 65536 combinations of them. ;)
Here, I will comment it for you all.

[size=12][color=grey]; [in]  al = 1st character

; ah = 2nd character[/color]

[color=grey]; [out] ZF = 1 (match)
; ZF = 0 (no match)[/color]

cmp al, ah [color=blue]; Immediately test for equality[/color]
jz @f [color=blue]; if (al==ah) exit with ZF=1 (match)[/color]
or eax, 2020h [color=blue]; Set 5th bit of each[/color]
cmp al, ah [color=blue]; if (al[b]!=[/b]ah) exit with ZF=0 (no match)[/color]
jnz @f [color=blue]; the only bytes left to check are[/color]
sub al, 61h [color=blue]; those with different 5th bits.[/color]
sub al, 1Ah [color=blue]; Check if 'a' <= al <= 'z'[/color]
sbb al, al [color=blue]; al = -1 if it is.[/color]
inc al [color=blue]; set ZF[/color]
@@:[color=#A0A0A0] jz @match[/color][/size]
Posted on 2003-03-05 03:51:30 by iblis
Yes, but what about non-english chars? IMHO, the lookup table is fastest and you may convert any languages chars.
Posted on 2003-03-05 03:52:56 by JohnFound

Hi ???? :)

Char 5B (hex) is "["
Char 7B (hex) is "{"

Am I wrong, or your code will consider them equal (by ORing with 20 (hex) before compare? ).
Case insensitivity, instead, requires to consider equal only alphabetic ranges (a..z with A..Z).

The last four instructions you used are clever.. but there's nothing that can be done when information has already been destroyed (by the OR instruction).. and nothing that will make the $5B and $7B seem different, once you've set the 5th bit in both.


Hi JohnFound,
on modern CPUs, look up tables can be (in a real situation) very slow, because if the cache hasn't yet be filled with the table, access to main memory will be extremely slow. If you make a test, make it proper.. because simply testing millions of chars won't be a "realistic" test, and will make things seem much better than they will then score in a real world situation.
In a real world situation you rarely compare millions of chars in a block.. but you rather execute code in between string compares, which can well trash the cache and you're back again accessing from slow system memory.

A best general solution doesn't exist. It depends on the precise context.. yet, usually, a code like the one I showed above will do, and won't trash the cache.
Posted on 2003-03-05 04:08:12 by Maverick
Hi Maverick,

[size=12]                          [color=blue];   AX:     ZF:[/color]

cmp al, ah [color=blue]; 5B:7B 0[/color]
jz @f [color=blue]; " "[/color]
or eax, 2020h [color=blue]; 7B:7B "[/color]
cmp al, ah [color=blue]; " 1[/color]
jnz @f [color=blue]; " "[/color]
sub al, 61h [color=blue]; 7B:1A 0[/color]
sub al, 1Ah [color=blue]; 7B:00 "[/color]
sbb al, al [color=blue]; 7B:00 1[/color]
inc al [color=blue]; 7B:01 0 (no match)[/color][/size]



John Found,

Like Mav said, it depends on the purpose. The ASCII table is primarily for english characters and I personally am not too interested in parsing other languages, and from the looks of it there are a lot of lower case foreign characters without an upper case counterpart.
Posted on 2003-03-05 04:31:08 by iblis

Hi iblis :)
I see.. Consider though that the routine may suffer from partial register stalls, on e.g. Pentium II / III CPU's.
Posted on 2003-03-05 06:11:31 by Maverick
iblis,

I expected something like:


cmp eax, ecx
jz @match
or eax, 20h
or ecx, 20h
sub ecx, eax
jxx @greater
lea eax, [eax-61h]
jxx @less
mov ecx, eax
sub eax, 1Ah
sbb eax, eax
jxx @match
.....
.....
@match: xor eax, eax
ret

@less: or eax, -1
ret
@greater:
ret


Regards,
Lingo
Posted on 2003-03-06 14:29:28 by lingo12
Lingo, very nice.

I forgot how strcmpi() returns greater/less-than values. Very useful to have if you want to emulate strcmpi() behavior verbosely. :alright:

Why use ecx, though? It would seem to me that in the middle of some string routine the less registers you destroy checking for equality the better.
Posted on 2003-03-06 16:36:30 by iblis


;al char 1 , dl char 2 (upper bits in edx eax zeroed
.data
casetbl equ $
cr=0
rept 128
if (cr gt 60h) and (cr lt 7Bh)
db cr and (not 20h)
else
db cr
endif
cr=cr+1
endm
.code
.........
mov al,casettbl[eax]
cmp casetbl[edx],al
jne @notmatch
Posted on 2003-03-06 20:48:11 by The Svin
The advantage of using a table based system is you can just pass it a character array which can be tailored to any language that uses the 256 byte character set.

I think this can be done for a Boyer Moore matching algo as well if you don't mind coding the table dynamically for the pattern being searched for.

Regards,

hutch@movsd.com
Posted on 2003-03-07 00:48:09 by hutch--
Ascii strcmpi() defaults to English-only case matching unless you change the locale. It does not use a table-lookup, it just converts both chars to uppercase and tests for equality. If you switch to a different locale, then it calls toUpper() instead of doing the comparison in the loop.

The english characters are suitable for my purposes because I'm writing a very simplistic HTML parser. I'm not aware of any HTML elements that use anything but english characters.

But certainly, if you are writing a text-editor or something like that, you'll want to be able to handle other characters as well as unicode.
Posted on 2003-03-07 20:09:10 by iblis
iblis,
could you please use a different shade of green for your comments, the one you have used above is very bright
Posted on 2003-03-07 23:25:50 by clippy
Green?

Take a look at the page source, comments are {color=grey} and {color=blue}
Posted on 2003-03-08 05:43:41 by iblis
Its also showing up in that headache green color for me, i looked at the source and it said <font color="grey">... Weird, must be an IE thing

Posted on 2003-03-08 06:45:28 by BubbaFate
Thanks Bubba,

I hadn't realized IE can't tell the difference between green and grey. Does #808080 work?

Testing testing...

?
Posted on 2003-03-08 22:19:14 by iblis
yes..
Posted on 2003-03-08 23:34:42 by roticv