Two fast algos with PCMPISTRI

[lingo]

Two fast algos with PCMPISTRI 

Code Select Expand


.const
EQUAL_ANY          equ 0000b
RANGES             equ 0100b
EQUAL_EACH         equ 1000b
EQUAL_ORDERED      equ 1100b
NEGATIVE_POLARITY  equ 010000b
BYTE_MASK          equ 1000000b

.code
align 16   
InstrLingo          proc        haystack:DWORD,needle:DWORD
                    mov         ecx,  haystack            ; ecx = haystack, edx = needle
                    push        esi
                    mov         edx,  needle
                    push        edi
                    mov         eax,  ecx
                    movdqu      xmm2, oword ptr[edx]        ; load 1st 16 bytes of needle
                    pxor        xmm3, xmm3
@Loop:                                    ; find the first possible match of 16-byte fragment in haystack       
                    pcmpistri    xmm2, oword ptr[eax], EQUAL_ORDERED
                    lea          eax, [eax+16]
                    ja           @Loop
                    lea          eax, [eax+ecx-16]            ; save the possible match start
                    mov          edi, edx
                    mov          esi, eax
                    jnc          @NotFound
                    sub          edi, eax
@@:                                    ; compare the strings
                    movdqu       xmm1, oword ptr [esi + edi]
                    pcmpistrm    xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK ; mask out invalid bytes in the haystack
                    movdqu       xmm4, oword ptr[esi]
                    pand         xmm4, xmm0
                    pcmpistri    xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
                    lea          esi, [esi+16]
                    ja           @b
                    jnc          @Found
                    add          eax,1                  ; continue searching from the next byte
                    jmp          @Loop
@NotFound:
                    xor          eax, eax
@Found:
                    pop          edi
                    pop          esi
                    ret
InstrLingo          endp

StrLen_Lingo        proc       lpStr:DWORD
                    mov        eax,  lpStr
                    pxor       xmm1, xmm1
                    pcmpistri  xmm1, oword ptr [eax], EQUAL_EACH   
                    jz         @End
                    mov        edx,  eax
                    and        eax,  -16
@@:
                    pcmpistri  xmm1, oword ptr [eax+16], EQUAL_EACH   
                    lea        eax,  [eax+16]
                    jnz        @b
                    sub        ecx,  edx
                    add        eax,  ecx
                    ret       
@End: 
                     mov       eax,  ecx
                     ret       
StrLen_Lingo         endp   



[jj2007]

And here are the original sources by Peter Kankowski, December 2008:

Code Select Expand

strlen_sse42:
  ; ecx = string
  mov eax, -16
  mov edx, ecx
  pxor xmm0, xmm0

STRLEN_LOOP:
    add eax, 16
    PcmpIstrI xmm0, dqword[edx + eax], EQUAL_EACH
    jnz STRLEN_LOOP

  add eax, ecx
  ret

Code Select Expand

strstr_sse42:
  ; ecx = haystack, edx = needle

  push esi
  push edi
  MovDqU xmm2, dqword[edx] ; load the first 16 bytes of neddle
  Pxor xmm3, xmm3
  lea eax, [ecx - 16]

  ; find the first possible match of 16-byte fragment in haystack
STRSTR_MAIN_LOOP:
    add eax, 16
    PcmpIstrI xmm2, dqword[eax], EQUAL_ORDERED
    ja STRSTR_MAIN_LOOP

  jnc STRSTR_NOT_FOUND

  add eax, ecx ; save the possible match start
  mov edi, edx
  mov esi, eax
  sub edi, esi
  sub esi, 16

  ; compare the strings
@@:
    add esi, 16
    MovDqU    xmm1, dqword[esi + edi]
    ; mask out invalid bytes in the haystack
    PcmpIstrM xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK
    MovDqU xmm4, dqword[esi]
    PAnd xmm4, xmm0
    PcmpIstrI xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
    ja @B

  jnc STRSTR_FOUND

  ; continue searching from the next byte
  sub eax, 15
  jmp STRSTR_MAIN_LOOP

STRSTR_NOT_FOUND:
  xor eax, eax

STRSTR_FOUND:
  pop edi
  pop esi
  ret

Two fast algos with PCMPISTRI 

Code Select Expand


.const
EQUAL_ANY          equ 0000b
RANGES             equ 0100b
EQUAL_EACH         equ 1000b
EQUAL_ORDERED      equ 1100b
NEGATIVE_POLARITY  equ 010000b
BYTE_MASK          equ 1000000b

.code
align 16   
InstrLingo          proc        haystack:DWORD,needle:DWORD
                    mov         ecx,  haystack            ; ecx = haystack, edx = needle
                    push        esi
                    mov         edx,  needle
                    push        edi
                    mov         eax,  ecx
                    movdqu      xmm2, oword ptr[edx]        ; load 1st 16 bytes of needle
                    pxor        xmm3, xmm3
@Loop:                                    ; find the first possible match of 16-byte fragment in haystack       
                    pcmpistri    xmm2, oword ptr[eax], EQUAL_ORDERED
                    lea          eax, [eax+16]
                    ja           @Loop
                    lea          eax, [eax+ecx-16]            ; save the possible match start
                    mov          edi, edx
                    mov          esi, eax
                    jnc          @NotFound
                    sub          edi, eax
@@:                                    ; compare the strings
                    movdqu       xmm1, oword ptr [esi + edi]
                    pcmpistrm    xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK ; mask out invalid bytes in the haystack
                    movdqu       xmm4, oword ptr[esi]
                    pand         xmm4, xmm0
                    pcmpistri    xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
                    lea          esi, [esi+16]
                    ja           @b
                    jnc          @Found
                    add          eax,1                  ; continue searching from the next byte
                    jmp          @Loop
@NotFound:
                    xor          eax, eax
@Found:
                    pop          edi
                    pop          esi
                    ret
InstrLingo          endp

StrLen_Lingo        proc       lpStr:DWORD
                    mov        eax,  lpStr
                    pxor       xmm1, xmm1
                    pcmpistri  xmm1, oword ptr [eax], EQUAL_EACH   
                    jz         @End
                    mov        edx,  eax
                    and        eax,  -16
@@:
                    pcmpistri  xmm1, oword ptr [eax+16], EQUAL_EACH   
                    lea        eax,  [eax+16]
                    jnz        @b
                    sub        ecx,  edx
                    add        eax,  ecx
                    ret       
@End: 
                     mov       eax,  ecx
                     ret       
StrLen_Lingo         endp   



[lingo]

Thank you JJ,

I like his StrLen algo and modified it a little bit in my way:

Code Select Expand

StrLen_Lingo2     proc  lpStr:dword
        mov       eax,  lpStr        ; eax = string
        pxor      xmm0, xmm0
@@:
        pcmpistri xmm0, oword ptr[eax],EQUAL_EACH
        lea       eax,  [eax+16]
        jnz       @b
        sub       eax,  lpStr
        lea       eax,  [eax+ecx-16]
        ret
StrLen_Lingo2     endp


[Caché GB]

Thanks JJ for the link to the original source.

At the link (replied 5 years ago), Randall Hyde notes the MMU page boundary problem.
To make Peter Kankowski's code MASM compliant, change all the "dqword[" to "oword ptr["

dqword equ <oword ptr>


I ported these algos to x64 and removed the nonvolatile Registers for the purpose of timing them.
With a haystack of 207 bytes and the needle (7 bytes long) at byte 63, called 100 million (counter = 100000000) times

Intel(R) Core(TM) i7-10875H CPU @ 2.30GHz

Proc size  Lingo      = 84 bytes
Proc size  Kankowski  = 87 bytes

InstrLingos:      0.512102 s
strstr_Kankowski:  0.520384 s

Lingo

Code Select Expand

.const

  EQUAL_ANY            equ 0000b
  RANGES               equ 0100y
  EQUAL_EACH           equ 1000y
  EQUAL_ORDERED        equ 1100y
  NEGATIVE_POLARITY    equ 010000y
  BYTE_MASK            equ 1000000y
.data

ProcSizeLingo          dd InstrLingoLen - InstrLingo

.code

align 16   
InstrLingo proc ; haystack:qword, needle:qword

          ; rcx = & haystack
          ; rdx = & needle

            mov  rax,  rcx
        movdqu  xmm2, oword ptr[rdx]                                    ; load 1st 16 bytes of needle
          pxor  xmm3, xmm3
@Loop:                                                                    ; find the first possible match of 16-byte fragment in haystack     
      pcmpistri  xmm2, oword ptr[rax], EQUAL_ORDERED
            lea  rax, [rax+16]
             ja  @Loop
            lea  rax, [rax+rcx-16]                                        ; save the possible match start
            mov  r9, rdx
            mov  r8, rax
            jnc  @NotFound
            sub  r9, rax
@@:                                                                      ; compare the strings
         movdqu  xmm1, oword ptr[r8+r9]
      pcmpistrm  xmm3, xmm1, (EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK) ; mask out invalid bytes in the haystack
         movdqu  xmm4, oword ptr[r8]
           pand  xmm4, xmm0
      pcmpistri  xmm1, xmm4, (EQUAL_EACH + NEGATIVE_POLARITY)
            lea  r8, [r8+16]
             ja  @b
            jnc  @Found
            add  rax, 1                                                  ; continue searching from the next byte
            jmp  @Loop
@NotFound:
            xor  rax, rax
@Found:   
            ret

InstrLingo endp
InstrLingoLen:


Peter Kankowski

Code Select Expand

.const

  EQUAL_ANY            equ 0000y
  RANGES               equ 0100y
  EQUAL_EACH           equ 1000y
  EQUAL_ORDERED        equ 1100y
  NEGATIVE_POLARITY    equ 010000y
  BYTE_MASK            equ 1000000y

.data

ProcSizeKankowskiLen    dd strstr_KankowskiLen - strstr_Kankowski

.code

align 16
strstr_Kankowski proc ; haystack:qword, needle:qword

          ; rcx = & haystack
          ; rdx = & needle

         movdqu  xmm2, oword ptr[rdx]                                    ; load the first 16 bytes of neddle
           pxor  xmm3, xmm3
            lea  rax, [rcx-16]

STRSTR_MAIN_LOOP:                                                        ; find the first possible match of 16-byte fragment in haystack
            add  rax, 16
      pcmpistri  xmm2, oword ptr[rax], EQUAL_ORDERED
             ja  STRSTR_MAIN_LOOP
            jnc  STRSTR_NOT_FOUND

            add  rax, rcx                                                ; save the possible match start
            mov  r9, rdx
            mov  r8, rax
            sub  r9, r8
            sub  r8, 16
@@:                                                                      ; compare the strings
            add  r8, 16
         movdqu  xmm1, oword ptr[r8+r9]

      pcmpistrm  xmm3, xmm1, (EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK) ; mask out invalid bytes in the haystack
         movdqu  xmm4, oword ptr[r8]
           pand  xmm4, xmm0
      pcmpistri  xmm1, xmm4, (EQUAL_EACH + NEGATIVE_POLARITY)
             ja  @B
            jnc  STRSTR_FOUND

            sub  rax, 15    ; continue searching from the next byte
            jmp  STRSTR_MAIN_LOOP

STRSTR_NOT_FOUND:
            xor  rax, rax

STRSTR_FOUND:

            ret

strstr_Kankowski endp
strstr_KankowskiLen:


OK JJ, now I know how you reply so fast.

Check the forum for new posts
https://masm32.com/board/index.php?topic=9237.0

By the way, do you ever sleep?