Streams vergleichen?

[Kedariodakon]

Wie kann man schnell zwei Streams auf gleichen Inhalt überprüfen, ohne jedes einzelne Byte zu testen?
Gibts da eine Function für?


Bye

[dizzy]

Auch eine evtl. Funktion müsste ja Byteweise (oder auf anderer Dateneinheitsbasis) in einer Schleife prüfen. Von daher... ;)

[Shaman]

Hoi

CompareMem ist für sowas gedacht.

Gruss
Shaman

[alcaeus]

Hi Kedariodakon,

du könntest den Inhalt der Streams in zwei Strings rauskopieren, und anschließend die Strings vergleichen. Dies funktioniert aber nur bei Datenmengen bis 2 GB.
Und wie dizzy schon gesagt hat, wenn du etwas vergleichen willst muss immer jedes Byte geprüft werden.
Beispiel für Vorschlag:

Delphi-Quellcode:

SetLength(String1, Stream1.Size);
Stream1.ReadBuffer(String1, Stream1.Size);
SetLength(String2, Stream2.Size);
Stream2.ReadBuffer(String2, Stream2.Size);
if String1 = String2 then
  ShowMessage('Gleich');

Ich hab den Code nicht getestet, sollte aber funktionieren.

Greetz
alcaeus

[shmia]

Zitat:

Zitat von Kedariodakon

Wie kann man schnell zwei Streams auf gleichen Inhalt überprüfen, ohne jedes einzelne Byte zu testen?

Das geht nicht. Du kannst lediglich sofort aufhören, wenn die Länge unterschiedlich ist:

Delphi-Quellcode:

if Stream1.Size <> Stream2.Size then
   Result := 1
else
begin
   result := CompareStreams(Stream1, Stream2);
end;

Beim Vergleichen der Streamdaten ist darauf zu achten, dass die Daten in genügend grosse Puffer (min. 8 kb) eingelesen
werden und der Vergleich der Puffer möglich "low-level" mittels Assembler durchgeführt wird.
Wahrscheinlich ist die Funktion CompareMem gut genug optimiert.

[Kedariodakon]

Ok ich schau mir mal CompareMem an =)

Mit Byteweise Vergleichen meinte ich eher, dass ich es nicht selber von Hand überprüfen muss...
Hab das vielleicht ein wenig dumm formuliert...


Bye

[Vjay]

Zitat:

Zitat von dizzy

Auch eine evtl. Funktion müsste ja Byteweise (oder auf anderer Dateneinheitsbasis) in einer Schleife prüfen. Von daher... ;)

Naja nicht direkt, evtl. würde es eine gute Sache sein 4 Bytes gleichzeitig zu vergleichen = 32 Bit. Aber indirekt würde somit auch jedes Byte verglichen werden, ist natürlich richtig, wie soll man sonst einen Unterschied feststellen können ^^.

[Sharky]

Hai Kedariodakon,

suche dir doch eine Funktion welche dir einen Hashwert eines Streams erzeugt (DEC) und vergleiche diese beiden dann.

P.S.: Ist nicht sogar in der CodeLibrary ein Posting zum Thema MD5-Hash?

[Thebe]

Delphi-Quellcode:

const

        Table: array[0..255] of DWORD =
                ($00000000, $77073096, $EE0E612C, $990951BA,
                 $076DC419, $706AF48F, $E963A535, $9E6495A3,
                 $0EDB8832, $79DCB8A4, $E0D5E91E, $97D2D988,
                 $09B64C2B, $7EB17CBD, $E7B82D07, $90BF1D91,
                 $1DB71064, $6AB020F2, $F3B97148, $84BE41DE,
                 $1ADAD47D, $6DDDE4EB, $F4D4B551, $83D385C7,
                 $136C9856, $646BA8C0, $FD62F97A, $8A65C9EC,
                 $14015C4F, $63066CD9, $FA0F3D63, $8D080DF5,
                 $3B6E20C8, $4C69105E, $D56041E4, $A2677172,
                 $3C03E4D1, $4B04D447, $D20D85FD, $A50AB56B,
                 $35B5A8FA, $42B2986C, $DBBBC9D6, $ACBCF940,
                 $32D86CE3, $45DF5C75, $DCD60DCF, $ABD13D59,
                 $26D930AC, $51DE003A, $C8D75180, $BFD06116,
                 $21B4F4B5, $56B3C423, $CFBA9599, $B8BDA50F,
                 $2802B89E, $5F058808, $C60CD9B2, $B10BE924,
                 $2F6F7C87, $58684C11, $C1611DAB, $B6662D3D,

                 $76DC4190, $01DB7106, $98D220BC, $EFD5102A,
                 $71B18589, $06B6B51F, $9FBFE4A5, $E8B8D433,
                 $7807C9A2, $0F00F934, $9609A88E, $E10E9818,
                 $7F6A0DBB, $086D3D2D, $91646C97, $E6635C01,
                 $6B6B51F4, $1C6C6162, $856530D8, $F262004E,
                 $6C0695ED, $1B01A57B, $8208F4C1, $F50FC457,
                 $65B0D9C6, $12B7E950, $8BBEB8EA, $FCB9887C,
                 $62DD1DDF, $15DA2D49, $8CD37CF3, $FBD44C65,
                 $4DB26158, $3AB551CE, $A3BC0074, $D4BB30E2,
                 $4ADFA541, $3DD895D7, $A4D1C46D, $D3D6F4FB,
                 $4369E96A, $346ED9FC, $AD678846, $DA60B8D0,
                 $44042D73, $33031DE5, $AA0A4C5F, $DD0D7CC9,
                 $5005713C, $270241AA, $BE0B1010, $C90C2086,
                 $5768B525, $206F85B3, $B966D409, $CE61E49F,
                 $5EDEF90E, $29D9C998, $B0D09822, $C7D7A8B4,
                 $59B33D17, $2EB40D81, $B7BD5C3B, $C0BA6CAD,

                 $EDB88320, $9ABFB3B6, $03B6E20C, $74B1D29A,
                 $EAD54739, $9DD277AF, $04DB2615, $73DC1683,
                 $E3630B12, $94643B84, $0D6D6A3E, $7A6A5AA8,
                 $E40ECF0B, $9309FF9D, $0A00AE27, $7D079EB1,
                 $F00F9344, $8708A3D2, $1E01F268, $6906C2FE,
                 $F762575D, $806567CB, $196C3671, $6E6B06E7,
                 $FED41B76, $89D32BE0, $10DA7A5A, $67DD4ACC,
                 $F9B9DF6F, $8EBEEFF9, $17B7BE43, $60B08ED5,
                 $D6D6A3E8, $A1D1937E, $38D8C2C4, $4FDFF252,
                 $D1BB67F1, $A6BC5767, $3FB506DD, $48B2364B,
                 $D80D2BDA, $AF0A1B4C, $36034AF6, $41047A60,
                 $DF60EFC3, $A867DF55, $316E8EEF, $4669BE79,
                 $CB61B38C, $BC66831A, $256FD2A0, $5268E236,
                 $CC0C7795, $BB0B4703, $220216B9, $5505262F,
                 $C5BA3BBE, $B2BD0B28, $2BB45A92, $5CB36A04,
                 $C2D7FFA7, $B5D0CF31, $2CD99E8B, $5BDEAE1D,

                 $9B64C2B0, $EC63F226, $756AA39C, $026D930A,
                 $9C0906A9, $EB0E363F, $72076785, $05005713,
                 $95BF4A82, $E2B87A14, $7BB12BAE, $0CB61B38,
                 $92D28E9B, $E5D5BE0D, $7CDCEFB7, $0BDBDF21,
                 $86D3D2D4, $F1D4E242, $68DDB3F8, $1FDA836E,
                 $81BE16CD, $F6B9265B, $6FB077E1, $18B74777,
                 $88085AE6, $FF0F6A70, $66063BCA, $11010B5C,
                 $8F659EFF, $F862AE69, $616BFFD3, $166CCF45,
                 $A00AE278, $D70DD2EE, $4E048354, $3903B3C2,
                 $A7672661, $D06016F7, $4969474D, $3E6E77DB,
                 $AED16A4A, $D9D65ADC, $40DF0B66, $37D83BF0,
                 $A9BCAE53, $DEBB9EC5, $47B2CF7F, $30B5FFE9,
                 $BDBDF21C, $CABAC28A, $53B39330, $24B4A3A6,
                 $BAD03605, $CDD70693, $54DE5729, $23D967BF,
                 $B3667A2E, $C4614AB8, $5D681B02, $2A6F2B94,
                 $B40BBE37, $C30C8EA1, $5A05DF1B, $2D02EF8D);

procedure CalcCRC32(p: Pointer; ByteCount: cardinal; var CRCValue: cardinal);
  // The following is a little cryptic (but executes very quickly).
  // The algorithm is as follows:
  // 1. exclusive-or the input byte with the low-order byte of
  // the CRC register to get an INDEX
  // 2. shift the CRC register eight bits to the right
  // 3. exclusive-or the CRC register with the contents of Table[INDEX]
  // 4. repeat steps 1 through 3 for all bytes
var
        i: cardinal;
        q: ^BYTE;
begin
        q := p;
        for i := 0 to ByteCount - 1 do
        begin
                CRCvalue := (CRCvalue shr 8) xor
                                Table[q^ xor (CRCvalue and $000000FF)];
                Inc(q)
        end;
end;

function StreamCRC32(s: TStream; len: cardinal): cardinal;
var
        p: Pointer;
begin
                result := $8F808F80;

                GetMem(p, len);

                s.Read(p^, len);

                CalcCRC32(p, len, result);

                FreeMem(p, len);
end;

Solche Fehlerkorrekturen wie "Stream auch groß genug?" "Stream nicht an Pos -1?" etc. hab ich hier nicht eingebaut, musst Du Dich drum kümmern. Auch das der Stream wieder "zurückgespult" wird, muss Du noch bedenken (Man glaubt gar nich wieviele Fehler durch so ein Schwachsinn entstehen können*g*). Ich schreibe erst vom Stream in einen Buffer und führe die CRC Routine mit dem Buffer aus, weil nicht alle Streams z.b. FileStream per Pointer erreichbar sind.

Die CalcCRC32 Prozedur samt Konstanten Tabelle hab ich vom swissdelphicenter.ch

[shmia]

Einen Hashwert für jeden Stream zu ermitteln macht wenig Sinn, da zum Ermitteln des Hashwertes sowieso
der gesamte Stream gelesen werden muss!!!

Es gibt wirklich nur eine einzige saubere Möglichkeit:
Beide Streams blockweise in den Speicher lesen und jeweils beide Blöcke miteinander vergleichen.
Würde man den Stream komplett in einen String einlesen, würde bei grossen Streams der Hauptspeicher unnötig stark
beansprucht!
Deshalb:

Delphi-Quellcode:

{**************************************************************************
 * NAME:    CompareStreams
 * DESC:    Vergleicht den Inhalt 2er Streams
 * PARAMS:  2 Streams
 * RESULT:  True => Inhalt gleich, False => Inhalt verschieden
 *************************************************************************}
function CompareStreams(const A, B : TStream): Boolean;
const
   BUFSIZE = 8196;
var
   bufA, bufB : string;
   r : Integer;
begin
   if A.Size <> B.Size then
      Result := False
   else
   begin
      A.Position := 0;
      B.Position := 0;

      SetLength(bufA, BUFSIZE);
      SetLength(bufB, BUFSIZE);

      while A.Position < A.Size do
      begin
         r := A.Size - A.Position;
         if r > BUFSIZE then
            r := BUFSIZE;
         A.ReadBuffer(bufA[1], r);
         B.ReadBuffer(bufB[1], r);

         if not CompareMem(PChar(bufA), PChar(bufB), r) then
         begin
            Result := False;
            Exit;
         end;
      end;
      Result := True;
   end;
end;

[Sharky]

Zitat:

Zitat von shmia

Einen Hashwert für jeden Stream zu ermitteln macht wenig Sinn, da zum Ermitteln des Hashwertes sowieso
der gesamte Stream gelesen werden muss!!!

Hai shmia,

dein Argument greift aber nur wenn es sich dabei um Dateien handelt. Kedariodakon hat ja nur danach gefragt zwei Streams zu vergleichen. Ergo müssen die beiden ja schon im Speicher sein :stupid:

[Kedariodakon]

Es handelte sich um Datein, welche auch hätten etwas größer sein können :)
Konnte sie aber nun schön vergleichen...

Bye

[negaH]

Ich vermute mal das dein Vergleich nicht bei ZWEI Streams/Dateien bleibt, d.h. das du später zB. 10 Dateien untereinander auf Gleichheit überprüfen willst.
Dann nehme eine Hash-Funktion wie du sie im DEC hast. Erzeuge zu jeder Datei einen Hash und füge diesen in eine sortierte Liste ein. Bei 10 Dateien muss damit auch jede Datei nur einmal readonly eingelesen werden um deren Hash zu erzeugen. Dies ist mit zb. einem MD4 Hash ca. 250Mb/sec schnell. Bei einem Direktvergleich der Dateiinhalte würde man im schlechtesten Falle 10*9 komplette Dateivergleiche benötigen. Also viel mehr an Speicher/Dateioperation. Eine Hashfunkton hat im Gegensatz zu einer einfachen 32Bit CRC auch mit ca. 128Bit Prüfsumme eine weit weit geringere Gefahr von Kollisionen. D.h. wenn man eine CRC benutzt so ist die Wahrscheinlichkeit das zwei unterschiedliche Dateien denoch die gleiche CRC besitzen viel viel größer als bei einer Hashfunktion. Das Verhältnis dabei ist 1 zu 2^96.

Wichtig ist auch noch ein spezielles Verhalten ALLER Dateisysteme. Das Positionieren mit dem Dateizeiger -> Stream.Position und AUCH die Abfrage des Dateizeigers mit if Stream.Position ... then, ist um einiges langsammer als das lineare und sequentielle Lesen einer Datei. Es ist also sehr wichtig beim Einlesen der Daten aus einer Datei die Größe der Datei und die aktuelle Positon in die Datei in lokalen Variablen zu halten, statt sie mit Stream.Size oder Stream.Positon permanent live abzufragen. Der Performance-Unterschied kann 200-300% ausmachen !!


Gruß Hagen