Quick compare ?

[James Ladd]

Im wondering how I can go about using the larger registers to compare data.

For example, if I have a single character of 8 bits then I should be able to
pack 4 characters into a register of 32 bits and do compares on this.
(assuming I have 4 characters and each character is 8 bits.)

I'm not sure of the assembler to do this. Can someone give an example ?

If you can make a compare 32 bits at a time rather than 8 then it stands to reason
you could also use a bigger register to do an even bigger campare in one go.

From memory there are 64 bit registers on most Intel CPU's now. MMX I think.
So I could pack 64 bits of data into the 64 bit register and do 8 characters at a time.

I'm also not sure how to do this in assembler. Can someone give an example?

So if I have an array of characters in memory, can I just move them into a register
and then compare with the bits in the right order ?

Rgs, James.

[MichaelW]

You might take a look at the MASM32 StrLen procedure. It was adapted from an Agner Fog algorithm that uses DWORD reads to search for the terminating null. Running on my P3, this test code shows that StrLen slows down somewhat when the string is misaligned, where the alignment has only a small effect on the CRT strlen function. It also (unfairly) compares the general-purpose MASM32 StrLen InString procesure to a specialized version (that likely has errors that I failed to find in the short time I had to do this) that does DWORD reads and will work correctly only if the pattern is 4 bytes in length.

Code Select Expand


; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    include \masm32\include\masm32rt.inc
    .686
    include \masm32\macros\timers.asm
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    .data
      str1 db "This example compares the cycle counts, including the call "
           db "overhead, for the CRT strlen function and the MASM32 StrLen "
           db "proc.",0
      align 4
           db 0
      str2 db "This example compares the cycle counts, including the call "
           db "overhead, for the CRT strlen function and the MASM32 StrLen "
           db "proc.",0
    .code
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««

align 4
instring proc startpos:DWORD,lpSource:DWORD,lpPattern:DWORD

    invoke StrLen, lpSource
    mov ecx, lpSource
    mov edx, lpPattern
    mov edx, [edx]
  @@:
    sub eax, 1
    js  @F
    cmp [ecx+eax], edx
    jne @B
    inc eax
    ret
  @@:
    xor eax, eax
    ret

instring endp

; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
start:
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
    invoke StrLen, ADDR str1
    print ustr$(eax),13,10

    invoke InString, 1, ADDR str1, chr$("MASM")
    print ustr$(eax),13,10

    invoke instring, 1, ADDR str1, chr$("MASM")
    print ustr$(eax),13,10,13,10

    invoke Sleep, 3000

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke StrLen, ADDR str1
    counter_end
    print ustr$(eax)," cycles, StrLen, DWORD aligned string",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke StrLen, ADDR str2
    counter_end
    print ustr$(eax)," cycles, StrLen, misaligned string",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke crt_strlen, ADDR str1
    counter_end
    print ustr$(eax)," cycles, strlen, DWORD aligned string",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke crt_strlen, ADDR str2
    counter_end
    print ustr$(eax)," cycles, strlen, misaligned string",13,10,13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke InString, 1, ADDR str1, chr$("MASM")
    counter_end
    print ustr$(eax)," cycles, InString",13,10

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke instring, 1, ADDR str1, chr$("MASM")
    counter_end
    print ustr$(eax)," cycles, instring",13,10,13,10

    inkey "Press any key to exit..."
    exit
; «««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««««
end start


Results on my P3:

Code Select Expand


124
106
106

136 cycles, StrLen, DWORD aligned string
170 cycles, StrLen, misaligned string
181 cycles, strlen, DWORD aligned string
189 cycles, strlen, misaligned string

460 cycles, InString
204 cycles, instring


[ChrisLeslie]

James

One of the problems is when the strings to compared do not have a multiple of 4 bytes. Then there may be an incomplete dword remaining to compare. Comparing dword may then look at a "foreign" byte in the next sequence in memory. The compare routine may then require a check on each DWORD compare to see if it terminates on a dword boundary. Unfortunately, the check slows down the routine considerably so that you will not get 4 x improvement. As Michael pointed out, MASM32 StrLen has such a check adapted from Agner Fog which could be used in a string compare.

Regards

Chris

[MichaelW]

The "foreign" bytes following the source string would not be a problem unless the pattern string contained an embedded null and the null happened to fall in the same position as the terminating null on the source string. As a null-terminated string, the pattern string would not normally contain an embedded null. And to get around potential problems with the code reading past the end of the source string, you could simply use 3 null terminators.

[James Ladd]

Great responses, thanks !

What would change to compare a QWORD at a time?