[Gelöst] Anwenden von CRC-Hashfunktion

[Dee]

Hallo Leute.

Ich entwickle gerade ein Programm, womit man Datei-Duplikate erkennen soll. Ich verwende dazu einen Hash-Algo, der die Prüfsummen der Dateien erstellt. Ich habe das schon mit MD5 probiert. Das Problem: Je größer die Dateien sind, desto länger dauert die Brechnung. Wenn ich die Prüfsumme einer Datei mit circa 1,5 GB mit MD5 berechnen lasse, dauert das länger als eine Minute.

Darum habe ich mich etwas umgesehen und nach einen schnelleren Hash-Algo umgesehen. Da bin ich auf CRC gestoßen. Nur ist mein Problem, dass ich nicht weiß, wie ich diese Funktion nutzen soll. Zwar gibt es in der Unit crc ein kleines Beispiel, aber anfangen kann ich damit nichts.

Könnte mir jemand erklären, wie ich die Funktion verwenden muss, damit ich einen Hashwert einer Datei erhalte?

Code: Alles auswählen

function crc32(crc: cardinal; buf: Pbyte; len: cardinal): cardinal;
 
{  Update a running crc with the bytes buf[0..len-1] and return the updated
   crc. If buf is NULL, this function returns the required initial value
   for the crc. Pre- and post-conditioning (one's complement) is performed
   within this function so it shouldn't be done by the application.
   Usage example:
 
    var
      crc : cardinal;
    begin
      crc := crc32(0, nil, 0);
 
      while (read_buffer(buffer, length) <> EOF) do
        crc := crc32(crc, buffer, length);
 
      if (crc <> original_crc) then error();
    end;
 
}

MfG

-- Dee

[Warf]

Das beispiel ist doch ziemlich eindeutig, du nimmst einen Stream, ließt einen Teil in den Buffer, und nutzt dann crc32 um den Hash zu updaten.
mal vielleicht ein verständlicheres Beispiel

Code: Alles auswählen

Function crcMyFile(FileName: String): Cardinal;
var Len: Integer;
  buff: array[0..127] of byte;
begin
  Result := crc32(0, nil, 0); //Grund Hash von leeren Bytes erstellen
  With TFileStream.Create(FileName, fmOpenRead) do  //Datei öffnen
  begin
    try
      repeat
        len = Read(buff, 128);  // 128 Byte aus datei Lesen
        Result := crc32(Result, @buff, len); // Hash Updaten
      until len<128; // Solange lesen bis EOF
    finally
      Free;
    end;
  end;
end;

[Dee]

Wenn man in Zeile 10 das "=" zu einem ":=", dann funktioniert es.

Ich bedanke mich. Nun hoffe ich, dass dieser Hash-Algo auch schneller ist.

MfG

-- Dee

[Socke]

Ich entwickle gerade ein Programm, womit man Datei-Duplikate erkennen soll. [...] Da bin ich auf CRC gestoßen.

Mit CRC kannst du keine Duplikate erkennen (false positive), vgl. http://de.wikipedia.org/wiki/Zyklische_ ... %C3%BCfung. Du kannst vielmehr nur bei unterschiedlichem CRC-Wert ein Duplikat aussschließen.

[mschnell]

Ich entwickle gerade ein Programm, womit man Datei-Duplikate erkennen soll. Ich verwende dazu einen Hash-Algo, der die Prüfsummen der Dateien erstellt. Ich habe das schon mit MD5 probiert. Das Problem: Je größer die Dateien sind, desto länger dauert die Brechnung. Wenn ich die Prüfsumme einer Datei mit circa 1,5 GB mit MD5 berechnen lasse, dauert das länger als eine Minute.

Im Prinzip ist MD5 eine Art CRC mit 128 Bit.

Die Rechenzeit für CRC und MD5 hängt stark von der Programmierung ab. Bei CRC (egal wie viele Bits) nimmt man meist eine 256 Einträge große Tabelle von n-Bit Werten, mit der jeweils ein Byte in die Summe einbezogen wird.

Bei "normalen" CRC-Anwenungen ist 8, 16 oder 32 Bit üblich. Es spricht aber prinzipiell nichts dagegen, mehr CRC Bits zu berechnen. Natürlich dauert die CRC - Berechnung umso länger, wenn das CRC mehr Bits hat als die Rechner-Architektur.

Generell kannst Du weder bei CRC noch bei MD5 ausschließen, dass zwei unterschiedliche Dateien dieselbe Checksumme haben.

-Michael

[Dee]

Mag sein, dass man nicht 100%ig bestimmten kann, ob Datei-Duplikate vorliegen, aber wenn man mindestens zwei Hash-Algos verwendet, dann sollten sich doch die Kollisionen ausschließen können, oder?

Mein Test hat ergeben, dass CRC32 doppelt so schnell ist, wie MD5, was vermutlich daran liegt, weil MD5 eine größe Zahl (16 Byte) generiert als CRC32 (4 Byte). Aber wenn so wäre, dann müsste CRC32 eine 8 Byte große Zahl generieren. Also hängt das wohl nicht zusammen.

-- Dee

[mschnell]

Auf einem 64 Bit System sollte ein 64 Bit CRC nicht deutlich länger dauern als ein 32 Bit CRC.

Hier findest Du sinnvolle 64-Bit Polynome: http://de.wikipedia.org/wiki/Zyklische_ ... %C3%BCfung

-Michael

[Dee]

Ich habe mich dazu entschlossen, das Berechnen der Prüfsummen mit einer anderen Methode zu ersetzen, weil das Berechnen der Prüfsummen bei sehr großen Dateien viel Zeit kostet und keine zuverlässige Erkennung bietet. Die Dateien werden nun auf Byte-Ebene verglichen.

Ich bedanke mich, für eure Beiträge.

-- Dee