Binär ersetzen / binäre Suche

[blackdrake]

Hallo.

Ich möchte ein gewissen Binär-Suchmuster (mit enthaltenen 00h's) durch ein anderes Suchmuster der selben Länge in einer Datei ersetzen. Ich habe unter Google und hier in der Suche keine Funktion gefunden, die eine binäre Suche innerhalb einer Datei bzw. eines Streams durchführt. Da ich ein Muster mit der Länge x Byte durch ein Muster der Länge x Byte ersetzen möchte, besteht die Problematik nicht unbedingt beim Ersetzen, sondern bei dem Aufsuchen der Position(en) innerhalb des Streams. Hat jemand eine Idee, wie ich eine binäre Suche realisieren kann?

Gruß
blackdrake

[oki]

Hi,

Suche nach einem Char? Das entspricht doch 00h bis FFh. Also denke ich, wenn man für den String ein einzelnes Char angiebt sollte s doch klappen. Hab ich aber so nicht getestet.

Ähm, oder doch? Hatte letztens #13 und #10 suchen und ersetzen lassen. Das sollte doch klappen. Die frage ist, ob man die Daten aus dem Stream in eine StringList bekommt.

Gruß oki

[blackdrake]

Hallo.

StringList? Wäre nicht sinnvoll, da die Datei zu 95% aus binären Zeichen besteht. Ich müsste die Datei in einen Stream laden. Und das Problem liegt darin, ein binäres Muster (sagen wir mal #00 #01 #02 #03 #04) zu suchen und zu ersetzen. Ich habe aber keine Ahnung, wie ich die Vorkommen dieses Musters innerhalb eines binären Streams ermitteln kann.

Gruß
blackdrake

[oki]

ok, ich dachte du suchst die Übereinstimmung eines Bytes. Das wäre dann wie ein Char und mit StringReplace könnte mann es in einer Stringlist bearbeiten.

Dann denke ich, kannst du den Stream byte-weise lesen. erste Vorkommen 00h, merken, nächster muss 01h sein, wenn nicht Merker löschen ....

Ist der komplette Sucheintrag vorhanden, ersetzen. Das kann dann alles in einem Temp-Stream erfolgen.

Gruß oki

[blackdrake]

Hallo oki.

Danke für den Tipp. Erscheint zwar logisch, jedoch wäre diese Lösung

a) nicht dynamisch (da kein beliebiges Such/Ersatz-Muster angegeben werden kann. Jedoch ist mein Beispiel statisch)
b) ziemlich langsam, da die Datei ca. 1 MB groß ist.

Wenn man eine 1 MB große Datei byteweiße abgehen und die vorrangehenden Bytes auf das Suchmuster überprüfen würde, wäre das sehr uneffektiv. Gibt es keine bessere Lösung (z.B. eine solche, wie sie in Hex-Editoren bei der Ersatz-Funktion angewandt wird)? Die Methode des byteweisen Abtastens des Streams würde ich nur anwenden, wenn sich keine bessere Methode anbieten würde.

Gruß
blackdrake

[oki]

Hi,

also was besseres fällt mir nicht ein. Dann muß wohl jemand anders ran. Assembler ist vielleicht ne Lösung.

Gruß oki

[Christian Seehase]

Moin Daniel,

lies die Datei doch mittels TFileStream in einen String ein, und ersetzte die Zeichen mit StringReplace.
Das müsste eigentlich funktionieren, und 1MB ist ja nun nicht sooo gross.

[blackdrake]

Hallo.

Funktioniert leider nicht.

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  x: TFileStream;
  s: string;
begin
  x := TFileStream.Create('test.xyz', fmOpenReadWrite or fmShareDenyWrite);
  try
    x.Position := 0;
    setlength(s, x.Size-1);
    x.Read(s[1], x.Size-1);

    s := StringReplace(s, #$0E, #$7D, [rfReplaceAll]);

    x.Position := 0;
    x.Write(s[1], length(s))
  finally
    x.free;
  end;

  close;
end;

Es funktioniert, wenn ich eine Zeichenkette vom Anfang suche und ersetze. Wenn ich jedoch etwas suchen und ersetzen will, was vom Dateianfang durch ein Null-Byte (#00h) getrennt ist, passiert nichts.

12 34 56 0E 78 00 12 00 ... -> 12 34 56 7D 78 00 12 00 (OK)
12 34 56 88 78 00 0E 00 ... -> 12 34 56 88 78 00 0E 00 (Fehler)

Scheinbar arbeitet StringReplace() intern mit PChar's, was dazu führen könnte, dass #00h's als Schlussbegrenzung angesehen werden. Dadurch ist StringReplace() scheinbar nicht Binary-Safe, obwohl Strings von Grund auf Binary-Safe sind. Oder hab ich was falsch gemacht?

Gruß
blackdrake

[SirThornberry]

sowas wird byteweise gemacht.
Wenn du beispielsweise nach
12 34 56 0E 78 00 12 00
suchst gehst du byteweise alles durch bis du
12
gefunden hast.
Wenn du ein 12 gefunden hast schaust du ob danach ein 34, dann ein 56 etc. kommt. Wenn dann irgendwas nicht mehr stimmt musst du an der stelle wo du die 12 (erstes zeichen) gefunden hast wieder nach der nächsten 12 suchen.

Soviel zur Theorie. Die Praxis sollte jeder Programmierer selbst hinnbekommen.

[Christian Seehase]

Moin Daniel,

ich hab' mal in die Sourcen geschaut.
Leider verwendet StringReplace AnsiPos, das wiederum AnsiStrPos und somit, wie Du schon sagtest, PChar, verwendet :wall:

In Deinem Falle müsste das aber mit Pos und PosEx lösbar sein.

[marabu]

Moin,

Zitat:

Zitat von blackdrake

Ich möchte ein gewissen Binär-Suchmuster (mit enthaltenen 00h's) durch ein anderes Suchmuster der selben Länge in einer Datei ersetzen.

du könntest die Funktion PatchString() als Ausgangspunkt für deine eigenen Bemühungen verwenden.

Grüße vom marabu

[Reinhard Kern]

Zitat:

Zitat von blackdrake

Hallo oki.

Danke für den Tipp. Erscheint zwar logisch, jedoch wäre diese Lösung

a) nicht dynamisch (da kein beliebiges Such/Ersatz-Muster angegeben werden kann. Jedoch ist mein Beispiel statisch)
b) ziemlich langsam, da die Datei ca. 1 MB groß ist.

Wenn man eine 1 MB große Datei byteweiße abgehen und die vorrangehenden Bytes auf das Suchmuster überprüfen würde, wäre das sehr uneffektiv. Gibt es keine bessere Lösung (z.B. eine solche, wie sie in Hex-Editoren bei der Ersatz-Funktion angewandt wird)? Die Methode des byteweisen Abtastens des Streams würde ich nur anwenden, wenn sich keine bessere Methode anbieten würde.

Gruß
blackdrake

Hallo,

das ist eine kapitale Fehleinschätzung. Eine Datei seriell zu lesen und dabei auf Muster zu untersuchen ist grundsätzlich die schnellste Methode. Jede unnötige Verkomplizierung durch VCL-Komponenten macht die Sache nur langsamer, ganz besonders die hier für fast alles empfohlene Methode, erst mal die ganze Datei in eine TStringList einzulesen, die praktisch immer und in diesem Fall ganz besonders blödsinnig ist, weil es sich ja nicht einmal um Text handelt. Nebenbei bemerkt, das Einlesen in eine TStringList muss ja selbst eine Mustererkennung durchführen nach CR-LF, und dann das Gnaze nochmal nach der gesuchten Folge - wer behauptet, dass das durch irgendeine Borland-Zauberei schneller geht als 1 mal direkt, glaubt sicher auch an Weihnachtsmann und Osterhase.

Also lesen und prüfen, ob das nächste Zeichen gleich dem ersten des Vergleichsarrays ist, wenn ja, ist das nächste gleiche dem 2. usw. bis die Länge des Vergleichs erreicht ist, wenn nicht, dann weitersuchen wie zuvor nach dem ersten Zeichen.

Es gibt noch Optimierungen, v.a. für lange Vergleiche, dazu gab es einen c't-Artikel, aber bei so geringen Programmierkenntnissen sollte man sich auf die einfachste Form beschränken.

Gruss Reinhard

[Gausi]

Wenn die zu durchsuchenden Daten größer werden, und der Suchstring auch mehr als ein halbes Dutzend Zeichen lang ist, könnte man den Boyer-Moore-Algorithmus darauf ansetzen. Da das Alphabet hier recht groß ist, dürfte die Bad-Character-Regel (die recht einfach zu implementieren ist), voll zuschlagen und eine deutliche Verschnellerung der Suche bewirken.
Bei sehr kurzen Suchmustern dürfte sich der Aufwand allerdings nicht lohnen.

[oki]

imho sollte dann mein Vorschlag mit dem byteweisen Vergleich bei kurzen Elementen gar nicht so schlecht sein. Flexibilität sollte eigentlich nicht das Problem sein. Das kann man ja mit einer kleinen Function erledigen können.

Delphi-Quellcode:

type TByteArr = Array of Byte;
Procedure ReplaceBytes(Buffer : Pointer; SercheBytes, NewBytes : TByteArr);

Buffer ist hier jetzt mal der Dummy für das Datenfile in dem ersetzt wird.

Gruß oki

[blackdrake]

Hallo.

Vielen Dank für euere Antworten.

Ich dachte, dass es uneffizient sei, eine Datei byteweise abzugehen, da ich es mit dem pixelweisen abgehen eines TImages verglich. Bei einem Projekt ging ich ein großes Bild pixelweise ab, was dazu führte, dass man den Fortschritt regelrecht mitanzusehen konnte, während man Kaffee aufkochte.

In meinem Projekt möchte ich nur kleine Muster ersetzen und die Performance ist nicht so wichtig, da die Dateien eher klein sind.

Die Funktion PatchString(), die Pos verwendet, hat mir sehr weitergeholfen. Es gab jedoch damit 3 Probleme:

a) Es wurde nur das erste Vorkommen ersetzt
b) Die Ersetzung geschah nach dem Vorkommnis und hat das Vorkommnis somit nicht ersetzt.
c) Verkürzungen und Verlängerungen (wenn Länge des Suchmusters ungleich der Länge des Ersatzmusters ist) sind nicht möglich

Ich habe deswegen folgende Funktion aus gebastelt, die ReplaceString() durch eine Binary-Safe-Funktion ersetzt und sie bei der CodeLib vorgeschlagen:
http://www.delphipraxis.net/internal...t.php?p=778431

Gruß
blackdrake

[oki]

und warum nun auf einmal mit Strings? Sollte doch Byte-Array sein. :gruebel:

gruß oki

[blackdrake]

Hallo.

Nein, kein Byte-Array, ein Binärmuster. Und ein String ist ja nichts anderes als ein max. 4 GB großes, dynamsiches ByteArray.

Gruß
blackdrake