findstring replacement

Bare metal programming in PureBasic, for experienced users
User avatar
idle
Always Here
Always Here
Posts: 5050
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

findstring replacement

Post by idle »

IdleSundayQuickSearch: an x64 parallel version of Quick Search (D M Sunday)
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 
Windows 11, Manjaro, Raspberry Pi OS
Image