Muss jedes einzelne Byte gelesen werden, um zu überprüfen, ob eine kopierte Datei mit dem Original identisch ist?

Ich habe kürzlich von einem Programm namens Total Commander erfahren. Es ist ein Windows Explorer-Ersatz und hat seine eigenen Sachen zum Kopieren von Dateien. Um zu überprüfen, ob die Dateien identisch sind, wird anstelle einer CRC-Berechnung buchstäblich jedes einzelne Byte einzeln sowohl auf dem Original als auch auf der Kopie überprüft.

Meine Frage ist: Ist das notwendig? Kann CRC oder eine andere solche Technik schief gehen? Sollten Sie als Programmierer versuchen, dieses perfekte, aber langsame System zu implementieren, oder ist es zu extrem?

Um CRCs (oder besser sha1sums) für beide Dateien zu berechnen, muss ohnehin jedes Byte gelesen werden. Wenn Sie einen byteweisen Vergleich durchführen, können Sie den Vorgang abbrechen, sobald Sie eine Nichtübereinstimmung feststellen - und Sie müssen sich keine Gedanken über zwei verschiedene Dateien machen, die zufällig dieselbe Prüfsumme haben (obwohl dies für sha1sum auf jeden Fall unwahrscheinlich ist). . Wenn Sie also den Vergleich lokal durchführen, ist ein byteweiser Vergleich mindestens so schnell wie ein Prüfsummenvergleich (es sei denn, Sie haben die Prüfsummen bereits berechnet).

Andererseits sind Prüfsummenvergleiche nützlich, wenn Sie Dateien vergleichen, die sich nicht auf demselben Computer befinden. Die Prüfsummen können lokal berechnet werden und Sie müssen nicht den gesamten Inhalt über das Netzwerk übertragen.

Auch hybride Ansätze sind möglich. Beispielsweise können Sie Prüfsummen für die beiden Dateien auf einmal berechnen und vergleichen, um zu vermeiden, dass die gesamten Dateien gelesen werden ( sofern sie sich unterscheiden) und gleichzeitig die gesamte Datei über das Netzwerk übertragen wird. Das rsync-Protokoll macht so etwas.

Beachten Sie, dass die Verwendung eines einfachen CRC eine faire Chance für eine Kollision bietet, wie Dave Rager in seiner Antwort erwähnt hat. Verwenden Sie mindestens sha1sum oder sogar etwas Neueres. (Versuchen Sie nicht, Ihren eigenen Hashalgorithmus zu erfinden. Die Leute, die sha1sum entwickelt haben, wissen weit mehr über dieses Zeug als wir beide.)

Was die Wahrscheinlichkeit von Kollisionen angeht, müssen Sie sich, wenn Sie einen anständigen Hash wie sha1sum verwenden, so gut wie keine Sorgen machen, es sei denn, jemand erstellt absichtlich und teuer Dateien, deren sha1sums kollidieren (das Erzeugen solcher Kollisionen war nicht möglich, als ich dies zum ersten Mal schrieb , aber es werden Fortschritte erzielt ). Zitat von Scott Chacons "Pro Git" , Abschnitt 6.1 :

Hier ist ein Beispiel, um Ihnen eine Vorstellung davon zu geben, was nötig wäre, um eine SHA-1-Kollision zu erhalten. Wenn alle 6,5 Milliarden Menschen auf der Erde programmieren und jede Sekunde Code produzieren würden, der der gesamten Linux-Kernel-Historie (1 Million Git-Objekte) entspricht, und ihn in ein riesiges Git-Repository verschieben würden, würde es 5 Jahre dauern, bis Dieses Repository enthielt genügend Objekte, um eine Wahrscheinlichkeit von 50% für eine einzelne SHA-1-Objektkollision zu haben. Es besteht eine höhere Wahrscheinlichkeit, dass jedes Mitglied Ihres Programmierteams in derselben Nacht in nicht zusammenhängenden Vorfällen von Wölfen angegriffen und getötet wird.

Zusammenfassung :

Der byteweise Vergleich ist gut für lokale Vergleiche. sha1sum ist gut für Fernvergleiche und bietet keine signifikante Chance auf Fehlalarme.

Hier ist eine andere Möglichkeit, darüber nachzudenken.

Wenn es keine Möglichkeit gibt, dass zwei verschiedene Dateien dieselbe CRC haben, bedeutet dies, dass jede Datei durch eine eindeutige CRC dargestellt werden kann. Wenn die CRC kleiner als die ursprüngliche Datei ist, handelt es sich um eine Form der verlustfreien Komprimierung. Wenn nicht, sollten Sie auch die Originaldateien vergleichen, da Sie die gleiche Anzahl von Bytes vergleichen würden.

Theoretisch könnten Sie die verlustfreie Komprimierung beider Seiten des Vergleichs verwenden, um die Anzahl der für den Vergleich erforderlichen Bytes zu verringern. Dies ist jedoch ein Kinderspiel, da Sie mehr Zyklen verschwenden und jedes Byte beider Dateien lesen müssten, um die Komprimierung durchzuführen . Das heißt, um jedes Byte (und seine Reihenfolge) in einem verlustfreien Komprimierungsschema zu codieren, müssten Sie es zuerst einlesen und in den Algorithmus einstecken, richtig? Spiel ist aus.

Hier ist eine Analogie:
Wenn Sie schnell feststellen möchten, ob zwei gedruckte Dokumente identisch sind, ohne Buchstaben für Buchstaben zu vergleichen, können Sie die Anzahl der Buchstaben in jeder Zeile der Dokumente vergleichen. Wenn die Zählungen alle übereinstimmen, verbessern sich die Chancen erheblich, dass die Dokumente identisch sind. Allerdings würde niemand behaupten, dass Sie mit diesem Ansatz sicher sein können, dass jeder Buchstabe der gleiche ist.

Die einzige perfekte Möglichkeit, nach identischen Dateien zu suchen, ist der Byte-für-Byte-Vergleich. Eine andere Möglichkeit, eine faire Annäherung zu treffen, besteht darin, einen Hash wie MD5 für die Dateien zu berechnen und diese zu vergleichen. Es ist möglich, dass es eine Hash-Kollision gibt, aber nicht sehr wahrscheinlich.

Ich würde mir vorstellen, dass der Byte-für-Byte-Vergleich schneller ist als die Berechnung des Hashs für beide Dateien zum Zeitpunkt des Vergleichs. Wenn Ihre Anwendung jedoch den Hash vorberechnet und Metadaten zu Ihren Dateien speichert, ist der Vergleich von Hashes erheblich schneller.

CRC ist wahrscheinlich nicht der richtige Weg, da es sich lediglich um einen Fehlererkennungsmechanismus handelt, nicht um einen Hash. (oder ein schlechter Hash mit vielen möglichen Kollisionen)

Um 100% sicher zu sein, dass zwei Dateien identisch sind, müssen Sie die Bytes wirklich überprüfen.

Warum? Hash-Kollisionen, deshalb! Abhängig von dem für das Hashing verwendeten Algorithmus ist eine Kollision zwar mehr oder weniger wahrscheinlich, aber dennoch möglich. Befolgen Sie diese Schritte:

1. Überprüfen Sie die Dateigröße
2. Überprüfen Sie die MIME-Typen
3. Überprüfen Sie den Hash
4. Überprüfen Sie einige zufällige Offsets und vergleichen Sie die Bits

Dies gibt Ihnen eine sehr hohe Gewissheit, dass die beiden Dateien identisch sind, es besteht jedoch eine sehr (äußerst) geringe Wahrscheinlichkeit, dass Sie eine Kollision in Ihren Händen haben. Die Wahl, wie weit Sie mit Ihren Vergleichen gehen möchten, wird von der Situation bestimmt.

Wie andere gesagt haben, ist es schneller, einen byteweisen Vergleich durchzuführen, wenn sich die beiden Dateien auf demselben System befinden. Wenn Sie versuchen, eine Reihe von Dateien zu vergleichen, erreichen Sie den Punkt, an dem Hashing die bessere Antwort ist, wenn sich die Dateien auf dem rotierenden Speicher befinden.

Hashing strahlt wirklich, wenn Sie nicht über alle verfügbaren Daten verfügen. Beispielsweise befinden sich die Dateien auf verschiedenen Computern. Außerdem können Sie die Ergebnisse von Berechnungen speichern und später darauf verweisen. (Ist dieser Bericht derselbe wie der alte? Wenn Sie den Bericht erstellen, speichern Sie einen Hash. Wenn Sie den nächsten erstellen, können Sie einfach die Hashes vergleichen. Sie müssen nicht einmal eine Kopie davon zur Verfügung haben.)

Ich denke, Sie sollten das mitgelieferte Dienstprogramm zum Vergleichen von Dateien mit Ihrem Betriebssystem verwenden oder ein Dateivergleichstool (siehe: Wiki-Dateivergleichstools ) zum Vergleichen von Inhalten verwenden, nachdem Sie die von @Glenn Nelson beschriebenen Dateieigenschaften überprüft haben.

Ich denke nicht, dass CRC 100% genau ist und ich denke, dass seine Genauigkeit mit der Dateilänge abnimmt. Ich schlage auch nicht vor, dass Sie es von Grund auf neu schreiben, da es möglicherweise viele Tests erfordert.

Muss jedes einzelne Byte gelesen werden, um zu überprüfen, ob eine kopierte Datei mit dem Original identisch ist? JA, um 100% sicher zu sein

Muss jedes einzelne Byte gelesen werden, um zu überprüfen, ob eine kopierte Datei NICHT mit dem Original identisch ist? NEIN

Um die Nichtidentität schnell zu ermitteln, überprüfen Sie zunächst Metadaten wie die Dateigröße und alle Prüfsummen / CRC- oder MIME-Typen, die das Betriebssystem / Dateisystem / Store möglicherweise bereits verwaltet . Da sie von diesem System vorberechnet werden, zahlen Sie diese Kosten zum Zeitpunkt des Vergleichs nicht.

Wenn dieser Test bestanden wird, müssen Sie jedes Byte einzeln vergleichen, wenn Sie 100% sicher sein müssen. Beachten Sie jedoch, dass in modernen Pipeline-CPUs und bei Verwendung mehrerer Threads und möglicherweise mehrerer Prozessoren / CPUs das Durchführen von Blockvergleichen großer Dateien WIRKLICH schnell ist und effizient, weil der Prozess in hohem Maße parallelisierbar ist. Weit schneller als jede Art von mathematischer Berechnung, die jedes Byte umfasst (obwohl einige Algorithmen möglicherweise auch parallelisierbar sind, aber möglicherweise nicht so einfach oder so gut). Das liegt daran, dass CPUs, die über Pipelines verbunden sind, Blockvergleichsoperationen des Speichers in Mikrocode oder sogar Hardware (sehr schnell) durchführen können und Disk-to-Memory-Subsysteme in hohem Maße optimiert sind, um große Blöcke von Dateien in den / aus dem Speicher zu bringen, und das alles parallel und mit Hardware. Wenn Ihre Anwendung dies regelmäßig durchführt und dies ein bekannter Leistungsengpass ist, sollten Sie dies in gut geschriebenem Multithread-Code implementieren, der die Parallelisierungsfunktionen Ihres Betriebssystems und Ihrer Hardware nutzt (verwenden Sie möglicherweise eine Sprache, für die dies entwickelt wurde) Dies).

Nur wenn Sie jede Datei einmal verarbeiten und später mehrere Vergleiche durchführen möchten (wobei Sie sich an das zusammengefasste oder komprimierte Analyseergebnis (wie JohnFX es ausdrückt) erinnern), hat dies einen erheblichen Vorteil. und selbst dann, nur um den Unterschied zu beweisen (wahrscheinlich); Um die Identität zu beweisen, müssten Sie immer noch den byteweisen Vergleich durchführen.