In Binärdatei suchen

[Ares]

Hallo!

Ich suche nach einer Möglichkeit wie ich in einer Binärdatei nach bestimmten Inhalten suchen kann. Die Suche sollte natürlich möglichst effizent sein.

Die Binärdatei wird mit einem TFileStream geöffent. Nun bräuchte ich eine Funktion die ein bestimmtes Bytemuster sucht, also z.B. Seek(myStream, 0x112233), und mir dann das Offset der Fundstelle mitteil... (Ich weiß, dass Seek nicht zum Suchen benutzt wird).

Gibt es solche eine Funktion oder muss man sich das selber basteln?

Besten Dank
Ares

[marabu]

Hallo,

für den Suchvorgang musst du die Daten vom externen Speicher in den Hauptspeicher laden - es führt kein Weg daran vorbei. Wie du dann weiter suchst ist eine Frage der Komplexität deiner Suche: einfaches oder reguläres Suchmuster? Pos() und Regex() helfen dir da weiter.

Grüße vom marabu

[r2c2]

Pos und Regex finktionieren doch aber nur mit Strings, oder?

==> Daten in TFileStream laden und Byteweise vergleichen...

mfg

Chtistian

[marabu]

Hallo Christian,

sowohl das Suchmuster, als auch der Datenstrom, lassen sich in Delphi als String betrachten. Das erspart die Implementierung einer speziellen Funktion, die lediglich die Signatur der Funktion Pos() anpassen würde - intern werden schon die vom Prozessor angebotenen Instruktionen für das register-gesteuerte Suchen eines Byte-/Wort-Wertes verwendet.

Freundliche Grüße

[Ares]

Es geht um teilweise sehr große Dateien in denen ich nach bestimmte (festen) Bytemustern suchen muss. Die Muster markieren Stellen an denen bestimmte Informationen zu finden sind. Die Muster sind immer gleich, reguläre Ausdrücke sind also nicht notwendig.

Zitat:

Pos und Regex finktionieren doch aber nur mit Strings, oder?

Ich meine auch, aber ich werde es nachher mal mit Streams versuchen.

Zitat:

==> Daten in TFileStream laden und Byteweise vergleichen...

Das ist natürlich die einfachste Möglichkeit aber wohl auch das uneffizenteste was es gibt. Wie gesagt sind die Dateien teilweise sehr groß. Daher sollte die Suche so effizient wie möglich sein, z.B. mit dem Knuth-Morris-Pratt Algrorithmus.

Gibt es hierfür bereits Funktionen die das können? Weiß jemand welche Algorithmen pos() verwendet? Ist das effizient?

Gruß
Ares

[Ares]

Zitat:

Zitat von marabu

sowohl das Suchmuster, als auch der Datenstrom, lassen sich in Delphi als String betrachten. Das erspart die Implementierung einer speziellen Funktion, die lediglich die Signatur der Funktion Pos() anpassen würde - intern werden schon die vom Prozessor angebotenen Instruktionen für das register-gesteuerte Suchen eines Byte-/Wort-Wertes verwendet.

Mmh, das wäre natürlich eine Möglichkeit. Aber kann ich beliebt große Daten in einen String laden? Gibt es da keine Beschränkungen?

[r2c2]

@Marabu:
So weit so klar, aber gibt das nicht Probleme mit #0?
Oder is die CompilerMagic da wieder so schlau, dass die sich nicht dran stört? Ich meine mich dran erinner zu können, dass ich mal Probleme mit #0 hatte. Kann aber sein, dass das intern mit PChars zu tun hatte, und die kommen ja mit Sicherheit nicht (ohne weiteres) mit #0 im String klar...

@Ares:

Zitat:

Das ist natürlich die einfachste Möglichkeit aber wohl auch das uneffizenteste was es gibt. Wie gesagt sind die Dateien teilweise sehr groß. Daher sollte die Suche so effizient wie möglich sein,

Pos macht intern auch nix anderes. Ohne alles zu vergleichen, kannst du nicht suchen. Klar, man kann sowas effizient und ineffizient programmieren, aber das Prinzip ist eigentlich immer das geleiche...

Zitat:

z.B. mit dem Knuth-Morris-Pratt Algrorithmus.

Kenn ich gar nicht... gleich mal nachgucken...

Zitat:

Mmh, das wäre natürlich eine Möglichkeit. Aber kann ich beliebt große Daten in einen String laden? Gibt es da keine Beschränkungen?

Beschränkung ist 2GB = ansprechbarer RAM in nem 32Bit-System(die anderen 2GB sind fürs OS)...

//Edit: grad gemerkt, dass es noch gar keine 325Bit-Systeme gibt... :mrgreen:

mfg

Christian

[juergen]

@ Christian,
der Vollständigkeitshalber :roll:

Zitat:

Beschränkung ist 2GB = ansprechbarer RAM in nem 32Bit-System(die anderen 2GB sind fürs OS)...

Es gibt einen von MS dokumentierten Parameter für die Boot.ini -> /3GB
Das hebt die Beschränkung zumindest schonmal von 2 GB auf 3 GB, aber somit nur noch 1 GB für das OS.
Manchmal kann das hilfreich sein...

[Ares]

Öhm, ich stehe gerade etwas auf dem Schlauch. Wie kann ich den Streaminhalt in einen String einlesen?

Mein erster Versuch tut es jedenfalls schon mal nicht :-|

Delphi-Quellcode:

   stream := TFileStream.Create('MeineDatei.bin', fmOpenRead);
   stream.Read(test, 25);
   showMessage(test);

[marabu]

Die Funktion Pos() selbst wird durch einen null character im String nicht behindert:

Delphi-Quellcode:

var
  s: String;
  i: Integer;
begin
  s := '01234'#0'56789';
  ShowMessage(IntToStr(Pos('6', s))); // liefert 8
end;

Ich sage ja auch nicht, dass hier eine Stringverarbeitung vorliegt, sondern dass man durch geschicktes Agieren bestehende Funktionalität für lau nutzen kann.

Pos() implementiert den brute force Ansatz, wenn ich richtig informiert bin. Was die Suchalgorithmen angeht, so hängt sehr viel von der Länge des (einfachen) Suchmusters (synonym für substring) ab. Für kleine Zeichenketten bis zur Länge drei ist der brute force Algorithmus optimal, für größere hat sich in der Fachwelt bis dato (1994) Boyer-Moore-Horspool durchgesetzt.

Die Aussage "das Prinzip ist immer das gleiche" ist so alleine nicht richtig. Komplexe Suchverfahren bedienen sich bei ihren elementaren Schritten natürlich auch des Byte-Vergleichs, aber anstelle des simplen loop-and-compare werden da für den Laien erstaunliche Eigenschaften des Suchstrings analysiert und nutzbar gemacht.

Das Buch String Searching Algorithms von Graham A. Stephen vermittelt einen recht guten und kompakten Überblick über die Materie.

Freundliche Grüße


Einlesen in einen String-Buffer:

Delphi-Quellcode:

const
  BUFSIZE = 64 shl 10;
var
  buffer: String;
  s: Stream;
  chunk: Integer;
begin
  // ...
  chunk := Max(BUFSIZE, s.Size - s.Position);
  if chunk < Length(buffer) 
    then SetLength(buffer, chunk)
    else SetLength(buffer, BUFSIZE);
  s.Read(s[1], chunk);
  // ...
end;

Getippt und nicht getestet

[Ares]

Hallo!

Vielen Dank für das Beispiel! Ich habe es so abgeändert:

Zitat:

procedure TForm1.Button1Click(Sender: TObject);
const
BUFSIZE = 64 shl 10;
var stream: TStream;
test: string;
i: integer;

buffer: String;
chunk: Integer;
begin
stream := TFileStream.Create('D:\Datei.bin', fmOpenRead);
chunk := Max(BUFSIZE, stream.Size - stream.Position);
if chunk < Length(buffer)
then SetLength(buffer, chunk)
else SetLength(buffer, BUFSIZE);
stream.Read(buffer[1], chunk); //84068

for i := 1 to 10 do begin
test1 := test1 + IntToHex(ord(buffer[i]),2) + ' ';
end;

showMessage(test);

stream.Free;
end;

Was genau hat es mit der Zuteilung von chunk auf sich? Ich durchschaue leider nicht ganz, wofür das gut ist.

Ich habe folgende beobachtung gemacht:
Wenn ich das Programm so laufen lasse, werde mir mit showMessage wunderbar die ersten 10 Byte angezeigt (E0 32 98 00 00 00 00 00 00 00). Aber: Es sind die falschen! Wenn ich mir die Datei mit einem Hex-Editor anschaue kommt diese Bytefolge nirgendwo vor, besonders nicht am Dateianfang.

Wenn "stream.Read(buffer[1], chunk);" durch "stream.Read(buffer[1], ZAHL);" ersetze und mit verschiedenen Werten für ZAHL rumprobiere bekomme ich das Ergebnis:
ZAHL = 1 bis 84068 --> Es werden die korrekten Bytes angezeigt (D2 18 B4...)
ZAHL = 84068 bis 84072 --> Es kommt zu einer Exception
ZAHL = 84073 oder größer --> Das falsche Ergebnis wird angezeigt.

Das Ergebnis kann ich nicht wirklich deuten? Wie kommen die Zahlen zustande? Wo könnte der Fehler liegen?

Besten Dank!
Ares

[marabu]

Hallo,

wenn deine Dateien doch riesig groß sind, dann möchtest du sie sicher portionsweise verarbeiten - chunk (maximal 64KB) ist die Portionsgröße und mein Code gehört in eine Schleife. Solange mindestens 64KB Restdaten gelesen werden können, wird der einmal allozierte Buffer benutzt, fällt der Rest unterhalb diese Größe, dann wird der Buffer redimensioniert.

Deine Experimente kann ich anhand deiner Angaben nicht so gut kommentieren, da müsstest du wirklich den richtigen Code zeigen. Ist allerdings der Buffer nach wie 64KB groß und du liest deutlich größere Mengen ein, dann überschreibst du angrenzende Speicherbereiche und das Ergebnis muss dich nicht wundern.

Freundliche Grüße

[Hawkeye219]

Hallo Ares,

versuche es mal mit dieser Änderung:

Delphi-Quellcode:

// chunk := Max(BUFSIZE, s.Size - s.Position);
chunk := Min(BUFSIZE, s.Size - s.Position);  // Min() statt Max()
SetLength(buffer, chunk);
s.Read(buffer[1], chunk);

Ein kleiner Fehler, der aber sehr schnell passiert. Man möchte eine maximale Puffergröße angeben, muß aber dazu die Funktion Min() benutzen. Die Fallunterscheidung habe ich entfernt - sie wird meiner Meinung nach nicht mehr benötigt.

Noch ein Hinweis: wenn der Suchstring mehrere Bytes enthält, befindet er sich eventuell nur zum Teil in einem Puffer und wird dann im nächsten fortgesetzt. Diesen Sonderfall mußt du bei der Untersuchung des Pufferinhalts berücksichtigen. Wie man so etwas prinzipiell angehen kann, findest du in diesem Thread.

Gruß Hawkeye

[marabu]

Hallo Hawkeye,

danke für die Korrektur - ich ahnte, dass mein disclaimer nötig war ...

Freundliche Grüße

[Christian Seehase]

Moin Jürgen,

als Vervollständigung der Vervollständigung ;-)

Zitat:

Zitat von juergen

Es gibt einen von MS dokumentierten Parameter für die Boot.ini -> /3GB
Das hebt die Beschränkung zumindest schonmal von 2 GB auf 3 GB, aber somit nur noch 1 GB für das OS.
Manchmal kann das hilfreich sein...

Vorausgesetzt die Anwendung ist so compiliert, dass sie das auch nutzen kann (was, AFAIK, mit Delphi nicht geht)