Find a Pattern in Memory

[Maya]

Good morning,
My code below, takes too much time when dealing with big memory size.
Any assistance will be much appreciated.

Code: Select all

Procedure FindMe(sPattern.s)
  sPatternLength.i = Len(sPattern)
  hModule.i        = GetModuleHandle_(0)
  StartAddress.i   = hModule
  EndAddress.i     = hModule + 17276688     ; <-- big memory size
  Buffer.s         = Space(sPatternLength)
  
  For MemoryAddress.i = StartAddress To  EndAddress Step 1
    ReadProcessMemory_(GetCurrentProcess_() , MemoryAddress, @Buffer, sPatternLength, 0)
    
    For i = 0 To sPatternLength/2 -1 Step 1
      bufferByte.s   = RSet(Hex(PeekA(@buffer+i)), 2,"0")
      sPatternByte.s = Mid(sPattern, j+1, 2)
      
      If bufferByte = sPatternByte
        fPattern.s = fPattern + bufferByte
        j=j+2
        
        If fPattern = sPattern
          Debug "You did it!"
          End
        EndIf
        
      Else
        j=0
        fPattern  = ""
        Break
      EndIf
      
    Next
  Next
  
EndProcedure

FindMe("1234")

[AZJIO]

viewtopic.php?p=525097#p525097
IsDigital viewtopic.php?p=583353#p583353 - see how to enumerate characters in memory
viewtopic.php?t=79183 - see enumeration with nested loop
without using string functions

[Little John]

Code: Select all

Structure ByteArray
   byte.b[0]
EndStructure


Procedure.i QuickSearch (*mainMem.ByteArray, mainSize.i, *findMem.ByteArray, findSize.i, startOff.i=0)
   ; -- Simplification of the Boyer-Moore algorithm;
   ;    searches for a sequence of bytes in memory (not for characters)
   ; in : *mainMem: pointer to memory area where to search
   ;      mainSize: size of memory area where to search (bytes)
   ;      *findMem: pointer to byte sequence to search for
   ;      findSize: number of bytes to search for
   ;      startOff: offset in 'mainMem', where the search begins (bytes)
   ; out: return value: offset in 'mainMem', where 'findMem' was found (bytes);
   ;                    -1 if not found
   ; Note: The first offset is 0 (not 1)!
   ;
   ; after <http://www-igm.univ-mlv.fr/~lecroq/string/node19.html#SECTION00190>, 31.8.2008
   ; (translated from C to PureBasic by Little John)
   Protected i.i, diff.i
   Protected Dim badByte.i(255)
   
   ; Preprocessing
   For i = 0 To 255
      badByte(i) = findSize + 1
   Next
   For i = 0 To findSize - 1
      badByte(*findMem\byte[i] & #FF) = findSize - i
   Next
   
   ; Searching
   diff = mainSize - findSize
   While startOff <= diff
      If CompareMemory(*mainMem + startOff, *findMem, findSize) = 1
         ProcedureReturn startOff
      EndIf
      startOff + badByte(*mainMem\byte[startOff + findSize] & #FF)  ; shift
   Wend
   
   ProcedureReturn -1                                               ; not found
EndProcedure

[AZJIO]

Updated the code. Using the primary comparison (If *s\b = *f\b), this began to work one and a half times faster, since it does not run a nested loop on each character.

Code: Select all

EnableExplicit

Procedure BinSearch(*s.Byte, LenS, *f.Byte, LenF)
	Protected i, j, isFind, *f0.Byte, *s0.Byte
	Protected *t.Byte ; test

	If Not LenS Or Not LenF
		ProcedureReturn 0
	EndIf

	*f0 = *f
	*s0 = *s

	For i = 1 To LenS - LenF + 1
		*f = *f0
		isFind = 1

		If *s\b = *f\b
			*f + 1
			*s + 1
			For j = 0 To LenF - 2
				If *s\b <> *f\b
					isFind = 0
					*s - j
					Break
				EndIf
				*f + 1
				*s + 1
			Next
		
			If isFind
				Debug "======"
				*s - LenF
				*t = *s + 1
				; 			Debug Chr(*s\b + *t\b << 8) ; Unicode
				Debug Chr(*s\b) ; Ascii
				Debug "======"
				ProcedureReturn *s - *s0
				; Break
			EndIf
		EndIf

		*s + 1
	Next

	ProcedureReturn -1
EndProcedure


Define String$, Find$, PosB, *pAsciiF, *pAsciiS
String$ = "This is a test string"
Find$ = "test"
; Find$ = "string"
; Find$ = "is"
; Find$ = "This"
; Find$ = "no"
PosB =  BinSearch(@String$, StringByteLength(String$), @Find$, StringByteLength(Find$))
Debug "byte = " + Str(PosB)
Debug "position = " + Str(PosB / 2) + " (Unicode)"

*pAsciiS = Ascii(String$)
*pAsciiF = Ascii(Find$)
; Debug MemorySize(*pAsciiS)
; Debug MemorySize(*pAsciiF)
PosB =  BinSearch(*pAsciiS, MemorySize(*pAsciiS) - 1, *pAsciiF, MemorySize(*pAsciiF) - 1)
FreeMemory(*pAsciiS)
FreeMemory(*pAsciiF)
Debug "position/byte = " + Str(PosB) + " (Ascii)"

But the "FindData" module is 7-10 times faster than everyone else

[Maya]

Thank you dears, for the great assistance.
Anybody can amend my code to make it faster?

[AZJIO]

Anybody can amend my code to make it faster?

You need to get rid of the string functions RSet(), Hex(), Mid(). There is no other way

Code: Select all

Define PosB
Define Process, StartAddress, hModule, EndAddress, sPattern.s
hModule = GetModuleHandle_(0)
StartAddress = hModule
EndAddress = hModule + 17276688     ; <-- big memory size
; Process = GetCurrentProcess_()

sPattern = "1234"
PosB =  BinSearch(StartAddress, EndAddress - StartAddress, @sPattern, StringByteLength(sPattern))
Debug "byte = " + Str(PosB)
Debug "position = " + Str(PosB / 2) + " (Unicode)"

[Maya]

Good Evening AZJIO,
"BinSearch" is not recognized in PureBasic!

[AZJIO]

Take it from my previous post