Re: Search optimisation
Posted: 06 May 2021, 08:45
Let's help each other out
https://www.autohotkey.com/boards/
https://www.autohotkey.com/boards/viewtopic.php?f=76&t=90171
That solves the issue for me.
Code: Select all
SetBatchLines, -1
filePath := "C:\Users\mi\AppData\Roaming\XnViewMP\Thumb.db"
bytes := "74 72 61"
size := ReadFile(filePath, buff)
len := CryptStringToBinary(bytes, needle, "CRYPT_STRING_HEX")
start := A_TickCount
offsets := SearchInBuff(&buff, size, &needle, len)
MsgBox,, % A_TickCount - start . "ms", % offsets
SearchInBuff(pHaystack, hstkSize, pNeedle, needleSize) {
arr := GetMax(pNeedle, needleSize)
maxByte := arr.max, offset := arr.maxIdx
prevByte := arr.prevMax, prevByteShift := arr.prevMaxIdx - offset
bool := needleSize > 1
found := "", addr := pHaystack + offset - 1, maxAddr := addr + hstkSize - needleSize + 1
while addr := DllCall("msvcrt\memchr", "Ptr", addr + 1, "Int", maxByte, "Ptr", maxAddr - addr, "Cdecl Ptr") {
( (bool ? NumGet(addr + prevByteShift, "UChar") = prevByte : true)
&& DllCall("msvcrt\memcmp", "Ptr", addr - offset, "Ptr", pNeedle, "Ptr", needleSize) = 0
&& found .= Format("{:#x}", addr - offset - pHaystack) . "`n" )
}
Return RTrim(found, "`n")
}
ReadFile(filePath, ByRef buff) {
File := FileOpen(filePath, "r")
File.Pos := 0
File.RawRead(buff, size := File.Length)
File.Close()
Return size
}
CryptStringToBinary(string, ByRef outData, formatName := "CRYPT_STRING_BASE64")
{
static formats := { CRYPT_STRING_BASE64: 0x1
, CRYPT_STRING_HEX: 0x4
, CRYPT_STRING_HEXRAW: 0xC }
fmt := formats[formatName]
chars := StrLen(string)
if !DllCall("Crypt32\CryptStringToBinary", "Str", string, "UInt", chars, "UInt", fmt
, "Ptr", 0, "UIntP", bytes, "UIntP", 0, "UIntP", 0)
throw "CryptStringToBinary failed. LastError: " . A_LastError
VarSetCapacity(outData, bytes)
DllCall("Crypt32\CryptStringToBinary", "Str", string, "UInt", chars, "UInt", fmt
, "Str", outData, "UIntP", bytes, "UIntP", 0, "UIntP", 0)
Return bytes
}
GetMax(pData, len) {
VarSetCapacity(sortedData, len, 0)
DllCall("RtlMoveMemory", "Ptr", &sortedData, "Ptr", pData, "Ptr", len)
pCmp := RegisterCallback("cmp", "C F", 2)
DllCall("msvcrt\qsort", "Ptr", &sortedData, "Ptr", len, "Ptr", 1, "Ptr", pCmp, "Cdecl")
max := NumGet(sortedData, "UChar"), (len > 1 && prevMax := NumGet(sortedData, 1, "UChar"))
Loop % len {
i := A_Index - 1
res := NumGet(pData + i, "UChar")
(res = max && maxIdx := i), (res = prevMax && prevMaxIdx := i)
}
Return {max: max, maxIdx: maxIdx, prevMax: prevMax, prevMaxIdx: prevMaxIdx}
}
cmp(a, b) {
a := NumGet(a + 0, "UChar"), b := NumGet(b + 0, "UChar")
Return a < b ? 1 : a > b ? -1 : 0
}
It only works if I put either Cdecl or Cdecl Ptr as final parameter on both memchr and memcmp in SearchInBuff (in your example it's only present on memchr).
Code: Select all
while addr := DllCall("msvcrt\memchr", "Ptr", addr + 1, "Int", maxByte, "Ptr", maxAddr - addr, "Cdecl Ptr") {
( (bool ? NumGet(addr + prevByteShift, "UChar") = prevByte : true)
&& DllCall("msvcrt\memcmp", "Ptr", addr - offset, "Ptr", pNeedle, "Ptr", needleSize, "Cdecl Int") = 0
&& found .= Format("{:#x}", addr - offset - pHaystack) . "`n" )
}
Not everyone is running Windows 10, so if you write code for distribution to others, 32-bit AHK ensures compatibility over a wider user base. I'm not saying you should use it, but there are valid reasons why others do.
Oops! I didn't read your code fully... only the part I quoted. Great idea on searching the max value.teadrinker wrote: β06 May 2021, 05:51I assumed that the byte with max value is generally encountered less frequently. At least it can be non-zero, zero generally encountered very often.Thanks! I took previous byte by value:
99.8% of all third-party DLLs were written for 32-bit, I would say..
Code: Select all
SearchInBuff(pHaystack, hstkSize, pNeedle, needleSize, overlap := false) {
arr := GetMax(pNeedle, needleSize)
maxByte := arr.max, offset := arr.maxIdx
prevByte := arr.prevMax, prevByteShift := arr.prevMaxIdx - offset
bool := needleSize > 1
found := "", addr := pHaystack + offset - 1, maxAddr := addr + hstkSize - needleSize + 1
while (maxAddr - addr > 0) && addr := DllCall("msvcrt\memchr", "Ptr", addr + 1, "Int", maxByte, "Ptr", maxAddr - addr, "Cdecl Ptr") {
( (bool ? NumGet(addr + prevByteShift, "UChar") = prevByte : true)
&& DllCall("msvcrt\memcmp", "Ptr", addr - offset, "Ptr", pNeedle, "Ptr", needleSize, "Cdecl") = 0
&& (found .= Format("{:#x}", addr - offset - pHaystack) . "`n")
&& (overlap ? true : addr += needleSize - 1) )
}
Return RTrim(found, "`n")
}
GetMax(pData, len) {
VarSetCapacity(sortedData, len, 0)
DllCall("RtlMoveMemory", "Ptr", &sortedData, "Ptr", pData, "Ptr", len)
pCmp := RegisterCallback("cmp", "C F", 2)
DllCall("msvcrt\qsort", "Ptr", &sortedData, "Ptr", len, "Ptr", 1, "Ptr", pCmp, "Cdecl")
max := NumGet(sortedData, "UChar"), (len > 1 && prevMax := NumGet(sortedData, 1, "UChar"))
Loop % len {
i := A_Index - 1
res := NumGet(pData + i, "UChar")
(res = max && maxIdx := i)
(res = prevMax && prevMaxIdx := i)
}
Return {max: max, maxIdx: maxIdx, prevMax: prevMax, prevMaxIdx: prevMaxIdx}
}
cmp(a, b) {
a := NumGet(a + 0, "UChar"), b := NumGet(b + 0, "UChar")
Return a < b ? 1 : a > b ? -1 : 0
}