Search In Memory

[NikitaOdnorob98]

Please tell me fast code for the search of bytes in memory. Only to work with ASCII, and Unicode. Thanks in advance.

[wilbert]

If you only need to work with ASCII and Unicode strings, can't you simply use FindString ?

[NikitaOdnorob98]

Mem1: 43 6F 00 AC C1 31 00 76 99 FF
Mem2: 6F 00 AC C1
FindString isn't working because the zero symbol there

[STARGÅTE]

Code: Select all

Structure CharacterArray
	C.c[0]
EndStructure

Procedure FindMemory(*Memory.CharacterArray, Length, *Search.CharacterArray, SearchLength)
	Protected I.i, J.i
	Length - SearchLength
	While I < Length
		Repeat
			While J < SearchLength
				If *Memory\C[I+J] <> *Search\C[J]
					Break 2
				EndIf
				J + 1
			Wend
			ProcedureReturn I
		ForEver
		I + 1
	Wend
	ProcedureReturn -1
EndProcedure


Debug FindMemory(?Memory, 11, ?Search, 4)

Debug FindMemory(?Memory, 11, ?Search2, 1)


DataSection
	Memory:
	Data.c 'H', 'e', 'l', 'l', 'o', 0, 'W', 'o', 'r', 'l', 'd'
	Search:
	Data.c 'l', 'o', 0, 'W'
	Search2:
	Data.c 'w'
EndDataSection

[Danilo]

With pattern support "xxxx???xxxx":
- Help Converting FindPattern Functions

[infratec]

Old thread I know

But I just needed this and ...
found a bug.
The reset of the search counter was missing.

Code: Select all

J = 0

Corrected version:

Code: Select all

Structure CharacterArray
   C.c[0]
EndStructure

Procedure FindMemory(*Memory.CharacterArray, Length, *Search.CharacterArray, SearchLength)
   Protected I.i, J.i
   Length - SearchLength
   While I < Length
      Repeat
         While J < SearchLength
            If *Memory\C[I+J] <> *Search\C[J]
               J = 0
               Break 2
            EndIf
            J + 1
         Wend
         ProcedureReturn I
      ForEver
      I + 1
   Wend
   ProcedureReturn -1
EndProcedure

[NicTheQuick]

As I know the fastest algorithm to search for pattern in a text once is the Boyer–Moore string-search algorithm
If you want to search for the same pattern P in several texts this should be the fastest algorithm: Knuth–Morris–Pratt algorithm
Of course this will also work with binary data.

[wilbert]

As I know the fastest algorithm to search for pattern in a text once is the Boyer–Moore string-search algorithm

This module I posted a few years ago does support BM
viewtopic.php?f=12&t=62519
but it's not exactly the same purpose as the code in this thread.
The code in this thread searches for characters while the code in the module I referred to searches for bytes.
When using BM with unicode, I guess you will need a pretty big lookup table; don't know if that would slow it down much.

[skywalk]

Old thread I know

But I just needed this and ...

I used PB's CompareMemoryString() for the added features of case and encoding.

Code: Select all

Procedure.i SF_ToMem(Unicode$, Enc.i=#PB_Ascii)
  ; Useful as 1 function with Enc parameter vs multiple functions; Ascii(), Unicode().
  Protected *b = AllocateMemory(StringByteLength(Unicode$) + SizeOf(character))
  PokeS(*b, Unicode$, -1, Enc)  ;|#PB_String_NoZero)  ; Not dropping trailing Zero.
  ProcedureReturn *b
EndProcedure
Procedure.i FindStringMem(*String, LenStr.i, Srch$, UseCase.i=#PB_String_CaseSensitive, Enc.i=#PB_Unicode)
  ; REV:  140905, skywalk
  ;       Return byte location(0-based) of Srch$ in *String.
  ;       Useful to search an Ascii string in Unicode app(default as of v5.4).
  Protected.i lenSrch = Len(Srch$)
  Protected.i lenChar
  Protected.i *Srch = SF_ToMem(srch$, Enc)
  If Enc = #PB_Unicode  ; 2 bytes/char
    lenChar = 2
  Else                  ; #PB_Ascii = 1 bytes/char, #PB_UTF8 = variable bytes/char
    lenChar = 1
  EndIf
  If *Srch
    Protected.i *pos = *String
    lenStr * lenchar + *String
    While *pos <= lenStr
      If CompareMemoryString(*pos, *Srch, UseCase, lenSrch, Enc) = #PB_String_Equal
        ProcedureReturn *pos - *String
      EndIf 
      *pos + lenChar
    Wend
    FreeMemory(*Srch)
  Else
    ProcedureReturn 0
  EndIf
EndProcedure
CompilerIf 1  ;-! TRY FindStringMem()
  Define.s haystack$, needle$
  Define.i lenhaystack, posmem, *haystack
  Debug "-- FindStringMem() --"
  Debug "-- Unicode --"
  haystack$ = "ABCDEF"+"|"+"GHIJKLMNO" + "|" + "123"  ; '|' is placeholder for #Null.
  lenhaystack = Len(haystack$)                        ; Remember len of this string. Adding #Null's will "shorten" it by 1st Null appearance.
  *haystack = SF_ToMem(haystack$, #PB_Unicode)        ; Convert string to mem. Note this = Unicode.
  ShowMemoryViewer(*haystack, 512)                    ; Show it in debugger
  needle$ = "123"                                     ; Do not mix Unicode and Ascii strings! Here we search for a Unicode string.
  posmem = FindStringMem(*haystack, lenhaystack, needle$, #PB_String_NoCase, #PB_Unicode)
  Debug PeekS(*haystack + posmem, Len(needle$))
  Debug "-- Ascii --"
  *haystack = SF_ToMem(haystack$, #PB_Ascii)          ; Convert string to mem. Note this = Ascii.
  ShowMemoryViewer(*haystack, 512)                    ; Show it in debugger
  needle$ = "GHI"                                     ; Do not mix Unicode and Ascii strings! Here we search for a Unicode string.
  posmem = FindStringMem(*haystack, lenhaystack, needle$, #PB_String_NoCase, #PB_Ascii)
  Debug PeekS(*haystack + posmem, Len(needle$), #PB_Ascii)
CompilerEndIf