PureBasic Forums - English

Code: Select all

Procedure.q FindString_SSE42_64Bit(pStr1, pStr2, 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 

Base$ = "This is a simple string for testing several find procedures ~ the results will show, if any of the tested functions are faster than the internal FindString() function"
Find$ = "Find"

Pos = 1

FindSSE42 = FindString_SSE42_64Bit(@Base$, @Find$, Pos)
SSE42$ = "Found String at Position : " + Str(FindSSE42)

PB$ = "Test with PB : " + Str(FindString(Base$, Find$, Pos))

MessageRequester("FindString with SSE4.2", SSE42$ + #LFCR$ + PB$)

Code: Select all

Procedure.q ReplaceString_SSE42_64Bit(pStr1, pStr2, pStr3, StartPos)
  !mov rax,r9                               ;need RAX for return-value ProcedureReturn, R9=StartPos 
  !cmp rax,1
  !jge @f
  !mov rax,1                                ;or End or Error
!@@:
  !mov r8,rcx                               ;need RCX for return-value PCMPISTRI, RCX=pStr1
  !add r8,rax                               ;rax=StartPos
  !movdqu xmm0,[rdx]                        ;first max.16 Bytes of Find$, RDX=pStr2
  !movdqa xmm1,xmm0                         ;for Length Find$ <=16
  !xor r10,r10
  !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
  !xor r10,r10
!@@:
  !add r10,16
  !add r9,16                                ;next 16 Bytes of Base$
  !movdqu xmm1,[rdx+r10]                    ;next 16 Bytes of Old$
  !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 Found?
!Find$End:
  !or rcx,rcx                               ;RCX Zero? Conventional
  !jnz Search
!Found:
  !add rax,rcx                              ;RAX=Start-Position Old$
  !pxor xmm0,xmm0
  !pcmpistri xmm0,xmm1,00001000b            ;for Length Old$
  !add rcx,r10
  !add rcx,rdx
  !sub rcx,[p.v_pStr2]                      ;RCX=Length Old$
  !mov r8,[p.v_pStr1]                       ;Base$
  !add r8,rax
  !mov r9,[p.v_pStr3]                       ;New$
!Again:
  !mov r11,[r8]
  !mov rdx,[r9]
  ;this part is not optimal... Schau´n ´mer mal! :-)
  !cmp rcx,7
  !ja @f
  !shl rcx,3
  !shr r11,cl  ;Base$
  !shl r11,cl
  !shr rcx,3
  !mov r10,8
  !sub r10,rcx
  !mov rcx,r10
  !shl rcx,3
  !shl rdx,cl  ;New$
  !shr rdx,cl
  !or rdx,r11
  !mov [r8],rdx
  !jmp Found?
!@@:
  !mov [r8],rdx
  !add r8,8
  !add r9,8
  !sub rcx,8
  !jmp Again
!Found?:
 ProcedureReturn                            ;rax 
EndProcedure 

Base$ = "Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2B: PCMPxSTRx instructions perform arithmetic comparisons between all possible pairs of bytes or words, one from each packed input source operand. The boolean results of those comparisons are then aggregated in order to produce meaningful results. The Imm8 Control Byte is used to affect the interpretation of individual input elements as well as control the arithmetic comparisons used and the specific aggregation scheme."
Old$ = "meaningful results"
New$ = "XXXXXXXXXXXXXXXXXX"

Pos = 1                                     ;Start-Position 

OK = ReplaceString_SSE42_64Bit(@Base$, @Old$, @New$, Pos)  ;OK is a goodie! You can check for success

If OK
  MessageRequester("ReplaceString with SSE4.2", Base$)
 Else 
  MessageRequester("ReplaceString with SSE4.2", "Nothing for replace !")
EndIf

Code: Select all

;QuickSearch Algorithm (Blitzes Findstring)
; mback2k - Updated: Sun Nov 16, 2008 (Unicode support) 
;        http://www.purebasic.fr/english/viewtopic.php?p=267475#p267475

; pdwyer - Last Updated: Mon Nov 12, 2007 
;        http://www.purebasic.fr/english/viewtopic.php?p=218258#p218258

Structure MemoryArray
  Byte.b[0]
EndStructure

Procedure.l QuickSearch(StartPos, *MainMem, MainLen, *FindMem, FindLen)
  Protected MainArrayLoop, EndSearchPos, *MainByteArray.MemoryArray, *FindByteArray.MemoryArray
  
  *MainByteArray = *MainMem
  *FindByteArray = *FindMem
;   StartPos =- 1
  
  ; Build BadChr Array
  Protected Dim BadChar(255)
  
  ; set all alphabet to max shift pos (length of find string plus 1)
  For i = 0 To 255
    BadChar(i)  =  FindLen + 1
  Next
  
  ;Update chars that are in the find string to their position from the end.
  For i = 0 To FindLen -1
    BadChar(*FindByteArray\Byte[i]) = FindLen - i   
  Next     
  
  MainArrayLoop = StartPos
  EndSearchPos = MainLen - (FindLen -1)
  
  While MainArrayLoop <= EndSearchPos
    
    If CompareMemory(*MainMem + MainArrayLoop, *FindMem, FindLen) = 1
      FoundPos = MainArrayLoop + 1
      Break
    EndIf
    
    ;Didn't find the string so shift as per the table.
    MainArrayLoop + BadChar(*MainByteArray.MemoryArray\Byte[MainArrayLoop + FindLen])
    
  Wend  

  ProcedureReturn FoundPos 
  
EndProcedure

Procedure QuickStringSearch(StartPos, String$, StringToFind$)
  
  CompilerIf #PB_Compiler_Unicode
;         ProcedureReturn QuickSearch(StartPos, @String$, StringByteLength(String$), @StringToFind$, StringByteLength(StringToFind$))/2+1
            ValReturn.l = QuickSearch(StartPos*2, @String$, StringByteLength(String$), @StringToFind$, StringByteLength(StringToFind$))
            If ValReturn : ValReturn / 2+1 : EndIf
            ProcedureReturn ValReturn
        
  CompilerElse
    ProcedureReturn QuickSearch(StartPos, @String$, Len(String$), @StringToFind$, Len(StringToFind$))
  CompilerEndIf

EndProcedure

Debug QuickStringSearch(1, "ABCDEF34637347347", "7")
Debug QuickStringSearch(1, "ABCDEF34637347347", "F")
Debug QuickStringSearch(1, "ABCDEF34637347347", "BC")