Effecient Byte-Muster-Suche in Matlab-Speicherabbild

Question

Ich habe große Binärdateien (2 + GB), die mit einem Sync-Muster (0xDEADBEEF) gefolgt von einem Datenblock einer festen Größe angeordnet sind. Beispiel:

0xDE AD BE EF ... 96 bytes of data 
0xDE AD BE EF ... 96 bytes of data 
... repeat ... 

Ich brauche die Offsets zu Beginn jedes Paket zu suchen. Im Idealfall wäre dies nur [1:packetSize:fileSize] Es gibt jedoch andere Daten, die eingestreut werden können, Header usw., also muss ich die Datei nach dem Synchronisierungsmuster suchen.

Ich verwende den folgenden Code, der auf Loren from Mathworks findPattern2 basiert, aber ein wenig geändert, um eine Speicherzuordnung zu verwenden.

function pattLoc = findPattern(fileName, bytePattern) 
%Mem Map file 
m = memmapfile(fileName); 
% Find candidate locations match the first element in the pattern. 
pattLoc = find(m.data==bytePattern(1)); 
%Remove start values that are too close to the end to possibly match 
len = numel(bytePattern); 
endVals = pattLoc+len-1; 
pattLoc(endVals>length(m.data)) = []; 
% loop over elements of Sync Pattern to check possible location validity. 
for pattval = 2:len 
    % check viable locations in array 
    locs = bytePattern(pattval) == m.data(pattLoc+pattval-1);  
    pattLoc(~locs) = []; % delete false ones from indices 
end 

Das funktioniert ziemlich gut. Ich denke jedoch, dass es Raum für Verbesserungen geben könnte. Zuerst weiß ich, dass meine Muster nicht näher als (100 in diesem Beispiel) sein können, aber möglicherweise weiter auseinander liegen. Es scheint, als ob ich diese Informationen irgendwie verwenden könnte, um die Suche zu beschleunigen. Zweitens verwendet die anfängliche Suche in Zeile 5 eine find zur numerischen Indexierung anstelle von logisch. Diese Linie dauert fast doppelt so lang wie sie logisch ist. Ich habe jedoch versucht, diese Funktion nur mit logischer Indizierung zu überarbeiten und kläglich gescheitert. Das Problem tritt innerhalb der Schleife auf und verfolgt die verschachtelte Indizierung mit logischen Daten, ohne mehr Funde zu verwenden oder mehr Daten zu prüfen, als erforderlich sind.

Also jede Hilfe, die dies beschleunigen würde geschätzt. Unten ist ein Code, der eine einfache Beispiel-Binärdatei erstellt, mit der bei Bedarf gearbeitet werden kann.

function genSampleFile(numPackets) 
pattern = hex2dec({'DE','AD','BE','EF'}); 
fileName = 'testFile.bin'; 
fid = fopen(fileName,'w+'); 
for f = 1:numPackets 
    fwrite(fid,[pattern; uint8(rand(96,1)*255)],'uint8'); 
end 
fclose(fid); 

eine Datei mit 10 Millionen Pakete Suche nahm die folgenden:

>> genSampleFile(10000000); %Warning Makes 950+MB file 
>> tic;pattLoc = findPattern(fileName, pattern);toc 
Elapsed time is 4.608321 seconds. 

Answer 1

Sie können mit findstr sofort Schub bekommen, oder besser noch strfind statt find:

pattLoc = strfind(m.data, bytePattern) 

Diese beseitigt die Notwendigkeit für weitere Schleifen. Sie müssen nur ein paar Dinge in dem zurückgegebenen Array von Indizes bereinigen.

Sie möchten Dinge entfernen, die näher als 100 Byte bis zum Ende sind, nicht näher als 4 Byte bis zum Ende, also len = 100 statt len = length(bytePattern).

Um Elemente herauszufiltern, die näher als 100 Bytes voneinander entfernt sind, verwenden diff auf der Liste der Indizes:

pattLoc[diff(pattLoc) < 100] = [] 

Dies sollte Ihr Code, indem sie sich mehr auf builtins, die viel im Allgemeinen beschleunigen mehr effizient als Schleifen.