http://www.iti.fh-flensburg.de/lang/alg ... ndayen.htm
Thanks for the tips wilbert.,
It's x64 only and supports Memory, Ascii, Unicode, UTF8
worst case O(nm) and an average of O(n/|Sigma|)
Code: Select all
Structure SkipTable
a.a[256]
EndStructure
Procedure IdleSundayQuickSearch(*haystack,len,*needle,nlen,pos=0)
;An x64 Parallel version of Quick Search (D M Sunday)
;http://www.dmi.unict.it/~faro/smart/algorithms.php?algorithm=QS&code=qs
Protected SkipTable.SkipTable
!mov r8,[p.p_needle]
!lea r9, [p.v_SkipTable]
!mov r10,[p.v_nlen]
!dec r10
!xor rcx,rcx
!for1:
!cmp r10, rcx
!jl next1
!movzx rdx, byte [r8+rcx]
!mov [r9+rdx],byte cl
!inc rcx
!jmp for1
!next1:
!movzx ecx,byte [p.v_nlen]
!and ecx,7
!mov r8,rcx
!mov r9, -1
!neg ecx
!and ecx, 7
!shl ecx, 3
!shr r9, cl
!cmp r8,0
!jnz notzero
!xor r9,r9
!notzero:
!mov rdx,[p.v_nlen]
!cmp rdx,7
!jle else_modn
!mov rdx,[p.v_nlen]
!sub rdx,r8;
!mov r15,rdx
!mov rax,[p.p_needle]
!mov rax,[rax+r15]
!mov rdx,r9
!and rax, rdx
!mov r10,rax
!jmp end_modn
!else_modn:
!mov rax,[p.p_needle]
!mov rax,[rax]
!mov rdx,r9
!and rax, rdx
!mov r10,rax
!xor r15,r15
!end_modn:
!mov rax,[p.v_nlen]
!sub rax,1
!sub [p.v_len],rax
!mov rcx, [p.v_pos]
!mov r11, [p.p_haystack]
!mov r12, [p.p_needle]
!lea r8,[p.v_SkipTable]
!whilelen1:
!cmp rcx, [p.v_len]
!jge wend1
!xor r13,r13
!xor r14,r14
!while_n3:
!cmp r13,r15
!jge wend_n3
!mov rax,[r11+rcx]
!mov rdx,[r12+r13]
!xor rax,rdx
!add r14,rax
!cmp r14,0
!jz end_sum
!mov rax,r15
!sub rax,r13
!add rcx,rax
!jmp skip
!end_sum:
!add rcx,8
!add r13,8
!jmp while_n3
!wend_n3:
!mov rax,[r11+rcx]
!and rax, r9
!xor rax, r10
!add r14,rax
!cmp rax,0
!jnz skip
!sub rcx,r15
!mov rax,rcx
!jmp found
!skip:
!mov rax,[p.v_nlen]
!sub rax,r15
!add rcx, rax
!movzx rdx,byte [r11+rcx]
!movzx rax,byte [r8+rdx]
!sub rcx,rax
!jmp whilelen1
!wend1:
!mov rax,-1;
!found:
ProcedureReturn
EndProcedure
iterations = 4096
haystack.s=""
For a = 0 To iterations
If a = iterations ;/ 2 +1
MessageRequester("test","pos " + Str(Len(haystack)) + " its " + Str(iterations))
haystack + "BANNANAS COOL BANNANAS COOL"
Else
haystack + Chr(Random(126,32))
EndIf
Next
len = Len(haystack) * SizeOf(Character)
needle.s = "BANNANAS COOL BANNANAS COOL"
nlen = Len(needle) * SizeOf(Character)
Debug len
st=ElapsedMilliseconds()
For a = 0 To 50000
;pos = IdleSundayQuickSearch(@haystack,Len(haystack)*SizeOf(Character),@needle,Len(needle)*SizeOf(Character))
pos = IdleSundayQuickSearch(@haystack,Len,@needle,nlen)
Next
et = ElapsedMilliseconds()
For a = 0 To 50000
pos1 = FindString(haystack,needle)
Next
et1 = ElapsedMilliseconds()
If pos <> -1
MessageRequester("test", "IdleSundayQuickSearch " + Str(et-st) + #CRLF$ + "findstring " + Str(et1-et) + " " + Str(pos) + " " + PeekS(@haystack+pos,nlen))
Else
MessageRequester("test","not found")
EndIf