求检查数组A是否包含在数组B中的最快算法,(200分)

  • 主题发起人 主题发起人 HongYuan
  • 开始时间 开始时间
H

HongYuan

Unregistered / Unconfirmed
GUEST, unregistred user!
我现在做一个像FTP一样查找内存数据的功能,或者像殺毒软件一样查找当前进程中是否存指定字节集的数据功能,比如,查找当前进程中“8B742444803E000F84”数据的地址。

我只会笨方法,一个个字节比较,想请大伙给点办法。

for i:=0 to $FFFFFF do
begin
try
if PByte(BaseCode+i)^=$8B then
if PByte(BaseCode+i+1)^=$74 then
if PByte(BaseCode+i+2)^=$24 then
if PByte(BaseCode+i+3)^=$44 then
if PByte(BaseCode+i+4)^=$80 then
if PByte(BaseCode+i+5)^=$3E then
if PByte(BaseCode+i+6)^=$00 then
if PByte(BaseCode+i+7)^=$0F then
if PByte(BaseCode+i+8)^=$84 then
begin
moNote.Lines.Add(IntToHex(BaseCode+i,4));
PByte(BaseCode+i+8)^:=$85;
break;
end;
except

end;
 
找到一个类似问题,
http://topic.csdn.net/t/20041220/13/3660145.html#
 
23 楼QuickKeyBoard()回复于 2004-12-22 10:31:06 得分 40

这样的问题在noi教学中属于基础问题,当你要看一个元素是否在一个集合中时,利用Hash散列表的效率最高。代码我已经写好了,复杂度:5000+5000。delphi5下通过:
program AB5000;
{$APPTYPE CONSOLE}

const
MaxVal = 30000;

var
a, b: array [0..5000] of Integer;
d: array [0..MaxVal-1] of Byte;
i: Integer;

begin
// 向数组a,b中填入随机数据。
Randomize;
for i:=0 to 5000 do
begin
a := Random(MaxVal);
b := Random(MaxVAl);
end;

// 清空Hash表
FillChar(d, 30000*Sizeof(Byte), 0);
// 构造数组a的Hash表
for i:=0 to 5000 do
Inc(d[a mod MaxVal]);
// 在数组a的Hash表中查找数组b的元素
for i:=0 to 5000 do
if d[b mod MaxVal]<>0 then
Write(b, ' ');
Writeln;
Readln;
end.
 
但是不知道怎么在我这里应用起来,比如我定义数组A
const
Oldcode: array[0..8]of byte=($8B,$74,$24,$44,$80,$3E,$00,$0F,$84);

怎么在内存0E000000开始到0EFFFFFF内查找出Oldcode出现的地址。
 
const
Oldcode: array[0..8] of byte = (
$8B,$74,$24,$44,$80,$3E,$00,$0F,$84
);
var
pData: PByte;
I: Integer;
begin
pData := PByte($0E000000); { BaseCode }

for I := 0 to $FFFFFF do if CompareMem(pData, @Oldcode, Length(Oldcode)) then
begin
moNote.Lines.Add(IntToHex(Integer(pData), 4));
PByte(Integer(pData) + 8)^ := $85;
Break;
end
else Inc(pData);
end;
注意,你可能没有直接访问物理地址的权利,这些 page 可能标示为不可读
 
非常感谢LSUPER的帮助。
我刚测试了您提供的方法,仍然很慢。我找到一个delphi写的工具,用它查找相当的快,下载地址:http://www.heijnen1.demon.nl/CheatEngine54src.rar
不过未能读懂代码,不清楚它的算法。
 
for I := 0 to $FFFFFF do if CompareMem(pData, @Oldcode, Length(Oldcode)) then

这一行是不是不要for I := 0 to $FFFFFF do ,用它好像死循环。
 
procedure TScanController.firstScan;
{
first scan will gather the memory regions, open the files, and spawn scanners
}
var
currentBaseAddress: dword;
mbi : TMemoryBasicInformation;

i,j: integer;

Blocksize: dword;
currentblocksize: dword;
totalProcessMemorySize: dword;
leftfromprevious: dword;


datatype: string[6];
begin
threadcount:=GetCPUCount;
totalProcessMemorySize:=0;
{
ScanController plan:
spawn idle scanner threads , ammount=maxthreadcount in settings
enumerate all regions and split up into jobs for the threads
if scanoption=soUnknownValue make a buffer big enough to hold all the memory, and give the threads the startbase where in the buffer their first region will start
start scanner threads
}

//determine the size in bytes for this variable. If one is provided.
//also fill in the fastscan alignment as well





//else it's ignored and never used


setlength(memRegion,16);
memRegionPos:=0;

if (startaddress mod 8)>0 then //align on a 8 byte base
startaddress:=startaddress-(startaddress mod 8);

currentBaseAddress:=startaddress;
while (Virtualqueryex(processhandle,pointer(currentBaseAddress),mbi,sizeof(mbi))<>0) and (currentBaseAddress<stopaddress) and ((currentBaseAddress+mbi.RegionSize)>currentBaseAddress) do //last check is done to see if it wasn't a 64-bit overflow.
begin
if (not (not scan_mem_private and (mbi.type_9=mem_private))) and (not (not scan_mem_image and (mbi.type_9=mem_image))) and (not (not scan_mem_mapped and (mbi.type_9=mem_mapped))) and (mbi.State=mem_commit) and ((mbi.Protect and page_guard)=0) and ((mbi.protect and page_noaccess)=0) then //look if it is commited
begin
if //no cache check
(Skip_PAGE_NOCACHE and ((mbi.AllocationProtect and PAGE_NOCACHE)=PAGE_NOCACHE))
or
//no readonly check
((not readonly) and (not ((((mbi.AllocationProtect) and (page_readonly or page_execute_read))=0) and
(((mbi.Protect) and (page_readonly or PAGE_EXECUTE_READ))=0))))
then
begin
//skip it
currentBaseAddress:=dword(mbi.BaseAddress)+mbi.RegionSize;
continue;
end;

//still here, so valid
try
if memRegionPos>0 then
begin
//check if it can be appended to the previous region
if memRegion[memRegionPos-1].BaseAddress+memRegion[memRegionPos].MemorySize=dword(mbi.baseaddress) then //yes, append
begin
//yes, so append
memRegion[memRegionPos-1].MemorySize:=memRegion[memRegionPos-1].MemorySize+mbi.RegionSize;
continue;
end;
end;

//still here, so a new region
memRegion[memRegionPos].BaseAddress:=dword(mbi.baseaddress); //just remember this location
memRegion[memRegionPos].MemorySize:=mbi.RegionSize;
memRegion[memRegionPos].startaddress:=pointer(totalProcessMemorySize); //starts from 0, for unknown scans

inc(memRegionPos);
if (memRegionPos mod 16)=0 then //add another 16 to it
setlength(memRegion,length(memRegion)+16);

finally
inc(totalProcessMemorySize,mbi.RegionSize); //add this size to the total

end;
end;


currentBaseAddress:=dword(mbi.baseaddress)+mbi.RegionSize;
end;

totalAddresses:=totalProcessMemorySize;

if memRegionPos=0 then raise exception.Create('No readable memory found');


//if soUnknown, make a buffer where it can store all the 'previous' memory
if scanOption=soUnknownValue then
begin
//extra check to make sure the previous scan was cleared
if OwningMemScan.previousMemoryBuffer<>nil then virtualfree(OwningMemScan.previousMemoryBuffer,0,MEM_RELEASE);

OwningMemScan.previousMemoryBuffer:=VirtualAlloc(nil,totalProcessMemorySize, MEM_COMMIT or MEM_TOP_DOWN, PAGE_READWRITE); //top down to try to prevent memory fragmentation
end;


//split up into seperate workloads
Blocksize:=totalProcessMemorySize div threadcount;
Blocksize:=blocksize-(blocksize mod 4096); //lastblock gets the missing bytes




scannersCS.Enter; //block access by the mainthread on the scanners object, could scanner[14] has not yet been created when doing a progress request
try
setlength(scanners,threadcount);
j:=0; //start at memregion 0
leftfromprevious:=0;


for i:=0 to threadcount-1 do
begin
scanners:=tscanner.Create(true);
scanners.scannernr:=i;
scanners.OwningScanController:=self;

scanners._startregion:=j;
scanners.startaddress:=memRegion[j].BaseAddress+leftfromprevious;

scanners.maxregionsize:=0;

if i=(threadcount-1) then
begin
scanners.stopaddress:=stopaddress;
scanners._stopregion:=memregionpos-1;

if scanOption<>soUnknownValue then
begin
//define maxregionsize
while j<memregionpos do
begin
if scanners.maxregionsize<memregion[j].MemorySize then
scanners.maxregionsize:=memregion[j].MemorySize;
inc(j);
end;
end;
end
else
begin
currentblocksize:=0;
inc(currentblocksize,memregion[j].MemorySize+leftfromprevious);
inc(j);

while (currentblocksize<blocksize) and (j<memregionpos) do
begin
if scanOption<>soUnknownValue then //not a unknown initial value scan, so it doesn't need overlap
begin
if scanners.maxregionsize<memregion[j].MemorySize+variablesize then
scanners.maxregionsize:=memregion[j].MemorySize+variablesize;
end;

inc(currentblocksize,memregion[j].MemorySize);
inc(j);
end;
dec(j);

scanners._stopregion:=j;
scanners.stopaddress:=memregion[j].BaseAddress+memregion[j].MemorySize;

leftfromprevious:=currentblocksize-blocksize;
dec(scanners.stopaddress,leftfromprevious);

if leftfromprevious<=0 then inc(j); //nothing left in this region
end;

if scanners.maxregionsize>buffersize then
scanners.maxregionsize:=buffersize;

//now configure the scanner thread with the same info this thread got, with some extra info
scanners.scanType:=scanType; //stFirstScan obviously
scanners.scanoption:=scanoption;
scanners.variableType:=VariableType;
scanners.roundingtype:=roundingtype;
scanners.fastscan:=fastscan;
scanners.scanValue1:=scanvalue1; //usual scanvalue
scanners.scanValue2:=scanValue2; //2nd value for between scan
scanners.readonly:=readonly;
scanners.unicode:=unicode;
scanners.caseSensitive:=caseSensitive;
scanners.hexadecimal:=hexadecimal;
scanners.binaryStringAsDecimal:=binaryStringAsDecimal;

scanners.fastscanalignsize:=fastscanalignsize;
scanners.variablesize:=variablesize;
scanners.customscanscript:=customscanscript;
scanners.customscantype:=customscantype;

if i=0 then //first thread gets the header part
begin
if scanoption=soUnknownValue then
datatype:='REGION'
else
datatype:='NORMAL';

scanners.AddressFile.WriteBuffer(datatype,sizeof(datatype));
end;

end;
finally
scannersCS.Leave;
end;

//all threads are created, so start them
for i:=0 to length(scanners)-1 do
scanners.Resume;

//prepare the result files
try

OwningMemScan.found:=0;
//and now we wait
for i:=0 to threadcount-1 do
begin
repeat
WaitForSingleObject(scanners.Handle,25); //25ms, an eternity for a cpu
synchronize(updategui);
until scanners.isdone;


if scanners.haserror then
begin
OwningMemScan.found:=0;
haserror:=true;
errorstring:=scanners.errorstring;
break;
end;

inc(OwningMemScan.found,scanners.totalfound);
end;

synchronize(updategui);
if haserror then
begin
OwningMemScan.found:=0;
//synchronize(errorpopup);
exit;
end;

//all threads are done
//combine all results and write them too the AddressFile and MemoryFile



if scanOption=soUnknownValue then
begin
//read the scanner memregions and adapt this memregion to it

//first find out how many regions it got
memRegionPos:=0;
for i:=0 to threadcount-1 do
inc(memRegionPos,scanners.memRegionPos);

setlength(OwningMemScan.memRegion,memRegionPos); //setting the size accordingly (max, can end up smaller due to appending)

OwningMemScan.memRegionPos:=0;
for i:=0 to threadcount-1 do
begin
for j:=0 to scanners.memRegionPos-1 do
begin
inc(OwningMemScan.found,scanners.memregions[j].MemorySize);

if OwningMemScan.memregionpos>0 then
begin
if OwningMemScan.memregion[OwningMemScan.memregionpos-1].BaseAddress+OwningMemScan.memregion[OwningMemScan.memregionpos-1].MemorySize=scanners.memregions[j].BaseAddress then
begin
//append
inc(OwningMemScan.memregion[OwningMemScan.memregionpos-1].MemorySize,scanners.memregions[j].MemorySize);
continue;
end;
end;

//new one
OwningMemScan.memregion[OwningMemScan.memregionpos]:=scanners.memregions[j];
inc(OwningMemScan.memregionpos);
end;

end;

if fastscan then //divide by alignsize of fastscan
OwningMemScan.found:=OwningMemScan.found div fastscanalignsize;

savescannerresults:=true;
end
else
begin
savescannerresults:=true;
end;

finally
end;



end;
 
你查找一下KMP算法吧。
 
这不就是子串查找吗?看看PosEx代码,改改参数就完了。
 
后退
顶部