I assume Wilberts original code is SwarmiSearchSSE2() which does work.
Its just amazing what Wilbert and Helle can do.
Code: Select all
EnableExplicit
Global TestString.s
Global Signature.s
Global Index.i
Global T1.q, R1.i, *A1
Global T2.q, R2.i, *A2
Global L1.i, L2.i
Procedure.q FindString_SSE42_64Bit(pStr1, pStr2, StartPos)
!mov rcx,[p.v_pStr1]
!mov rdx,[p.v_pStr2]
!mov rax,[p.v_StartPos]
!mov rax,r8 ;need RAX for return-value ProcedureReturn, R8=StartPos
!cmp rax,1
!jge @f
!mov rax,1 ;or End or Error
!@@:
!mov r8,rcx ;need RCX for return-value PCMPISTRI, RCX=pStr1
!sub r8,1
!add r8,rax ;rax=StartPos
!movdqu xmm0,[rdx] ;first max.16 Bytes of Find$, RDX=pStr2
!xor rcx,rcx
!Search:
!add rax,rcx
!add r8,rcx
!pcmpistri xmm0,dqword[r8],00001100b ;Least Significant Index, Positive Polarity (IntRes2=IntRes1), Equal Ordered, Unsigned Bytes (=No Unicode)
!jz Base$End ;Zero-Flag is set if found end of Base$
!js Find$End ;Sign-Flag is set if found end of Find$
!jrcxz @f ;jump if RCX is zero
!jmp Search
!@@:
!movdqa xmm1,xmm0 ;save xmm0
!mov r9,r8
!mov r10,rdx
!@@:
!add r10,16
!add r9,16 ;next 16 Bytes of Base$
!movdqu xmm1,[r10] ;next 16 Bytes of Find$
!pcmpistri xmm1,dqword[r9],00001100b ;compare the strings
!jz Base$End
!js Find$End
!jrcxz @b
!jmp Search
!Base$End:
!cmp rcx,16
!jne Found
!xor rax,rax
!jmp NoFound
!Find$End:
!or rcx,rcx ;RCX Zero? Conventional
!jnz Search
!Found:
!add rax,rcx
!NoFound:
ProcedureReturn ;rax
EndProcedure
Procedure SwarmiSearchSSE2(*haystack,len,*needle,lenN,pos=0);Result is wrong by 1 Character!
;Swarmi search SSE2 bit parallel search algorithm for for 1 to 16 byte needles
;performs ~ 1:1 With booyer moore And other variants For a 16 byte needle With a 0-255 alphabet range
;efficiency increases with parallelism. 2:1 for 8 byte needle, 4:1 for 4 byte needle, 8:1 for 2 byte needle and 16:1 1 byte needle
Protected offset
!align 32
DataSection
!m16:
!dq 0xffffffffffffffff
!dq 0xffffffffffffffff
!dq 0xffffffffffffffff
!dq 0xffffffffffffff
!dq 0xffffffffffffffff
!dq 0xffffffffffff
!dq 0xffffffffffffffff
!dq 0xffffffffff
!dq 0xffffffffffffffff
!dq 0xffffffff
!dq 0xffffffffffffffff
!dq 0xffffff
!dq 0xffffffffffffffff
!dq 0xffff
!dq 0xffffffffffffffff
!dq 0xff
!dq 0xffffffffffffffff
!dq 0x0
!dq 0xffffffffffffff
!dq 0x0
!dq 0xffffffffffff
!dq 0x0
!dq 0xffffffffff
!dq 0x0
!dq 0xffffffff
!dq 0x0
!dq 0xffffff
!dq 0x0
!dq 0xfff
!dq 0x0
!dq 0xff
!dq 0x0
EndDataSection
!mov rcx,16
!sub rcx,[p.v_lenN]
!imul rcx,16
!lea r8, [m16]
!movdqu xmm8, [r8+rcx] ;load trailing byte mask
!mov r9, [p.p_needle] ;build First char mask eg "a0a0a0a0a0a0a0"
!movzx eax,byte [r9]
!movd xmm7, eax
!punpcklbw xmm7, xmm7
!punpcklwd xmm7, xmm7
!pshufd xmm7, xmm7, 0 ;FirstCharMask
!mov r8,[p.p_haystack] ;align haysack
!mov rax,r8
!and rax ,15
!mov [p.v_offset],rax ;store offset
!sub r8,rax
!movdqu xmm5,[r9] ;store needle
!mov r14,[p.v_len]
!mov r13,[p.v_pos]
!sub r13,16
!Swarmi_While_Len:
!cmp r13, r14
!jge Swarmi_Wend
!add r13,16
!movdqa xmm0,[r8+r13] ;Get Haystack and check against mask chars"
!pcmpeqb xmm0,xmm7 ;FirstCharMask
!pmovmskb eax,xmm0
!cmp eax,0
!je Swarmi_While_Len
!mov r11,r13 ;current position
!Swarmi_Redo:
!bsf rdx,rax ;if there was a match rax holds 1 at the byte positions where a match is found in mask
!btr rax,rdx
!add r11,rdx ;align the haystack step forward x bytes
!movdqu xmm0,[r8+r11] ;haystack
!pcmpeqb xmm0,xmm5 ;check equal haystack vs needle
!pandn xmm0,xmm8
!pmovmskb edx,xmm0
!cmp edx,0
!je Swarmi_Found
!Swarmi_Test_Redo:
!cmp eax,0 ;test if any remaining positions to process
!jne Swarmi_Redo ;
!jmp Swarmi_While_Len
!Swarmi_Found:
!cmp r13,r14
!jge Swarmi_Wend
!mov rax, r11
!sub rax,[p.v_offset]
ProcedureReturn
!Swarmi_Wend:
!mov rax, -1
ProcedureReturn
EndProcedure
Procedure.i LocStrA(*Input,*Signature);Ascii
!mov rcx,[p.p_Input]
!mov rdx,[p.p_Signature]
!xor rax,rax
!mov r10,rcx
!cmp byte[rdx],0h
!je LocStr_Return
!LocStr_Loop:
!cmp byte[rcx],0h
!je LocStr_Return
!mov bl,byte[rcx]
!cmp bl,byte[rdx]
!jne LocStr_Next
!lea r8,[rcx+1h]
!lea r9,[rdx+1h]
!LocStr_Match:
!cmp byte[r9],0h
!je LocStr_Result
!cmp byte[r8],0h
!je LocStr_Next
!mov bl,byte[r8]
!cmp bl,byte[r9]
!jne LocStr_Next
!inc r8
!inc r9
!jmp LocStr_Match
!LocStr_Result:
!sub rcx,r10
!lea rax,[rcx+1h]
!jmp LocStr_Return
!LocStr_Next:
!inc rcx
!jmp LocStr_Loop
!LocStr_Return:
ProcedureReturn
EndProcedure
#Tries = 2e2
TestString = Space(1000000) + "8!#"
Signature = "8!"
*A1 = Ascii(TestString)
*A2 = Ascii(Signature)
L1 = Len(TestString)
L2 = Len(Signature)
T1 = ElapsedMilliseconds()
For Index = 1 To #Tries;10000000
;L1 = Len(TestString);<- needs to be here unless u only work with known strings!
;L2 = Len(Signature)
R1 = SwarmiSearchSSE2(*A1,L1,*A2,L2)
Next
T1 = ElapsedMilliseconds() - T1
T2 = ElapsedMilliseconds()
For Index = 1 To #Tries;10000000
R2 = FindString_SSE42_64Bit(*A1,*A2,0);LocStrA(*A1,*A2);LocStrA(*A1,*A2)
Next
T2 = ElapsedMilliseconds() - T2
MessageRequester("Result",
"T1: " + Str(T1) + #CR$ + "R1: " + Str(R1) + #CR$ + #CR$ +
"T2: " + Str(T2) + #CR$ + "R2: " + Str(R2))
End
