It is currently Wed Jan 27, 2021 4:47 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 1 post ] 
Author Message
 Post subject: findstring replacement
PostPosted: Mon Jun 29, 2015 11:29 am 
Offline
Addict
Addict
User avatar

Joined: Fri Sep 21, 2007 5:52 am
Posts: 3556
Location: New Zealand
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:
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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 1 post ] 

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye