Dateien miteinander vergleichen

NES-Spieler

Ich möchte gerne zwei (binäre) Dateien miteinander vergleichen, wobei der genaue Inhalt unwichtig ist. Es geht nur darum, herauszufinden, ob die Dateien gleich oder ungleich sind. Nun benutze ich bisher die ifstream-Klasse, lese zeichenweise aus und vergleiche die beiden Zeichen. Das dauert aber ziemlich lange. Gibt es da eine schnellere Möglichkeit?

ich würde es mit MD5 Prüfsummen probieren. Weiß ich leider aber nicht, ob es dafür fertige Funktionen gibt...

CStoll

Ich glaube nicht, daß so eine Prüfsumme viel schneller ist - schließlich muß sie auch die gesamte Datei durchscannen. Und außerdem ist es durchaus möglich, daß unterschiedliche Dateien die selbe Prüfsumme ergeben.

@NES: Du könntest ja einen Vortest machen, ob die Dateien die selbe Größe haben (wenn nicht, sind sie garantiert verschieden). Außerdem könnte es evt schneller sein, die Dateien blockweise einzulesen und zu vergleichen (memcmp()).

Jordy

Ich frage mich: Haben die Binären Dateien bekannte Eigenschaften? Vielleicht muss man nicht von Vorne nach Hinten vergleichen? Vielleicht reicht in 90% der Fälle ein Vergleich von ein paar wenigen Bytes, um Ungleichheit festzustellen? Dann wäre nur noch in 10% der Fälle ein Vergleich der gesammten Dateien notwendig. Dürfen die Datein unterschiedlich groß sein?

thordk

CStoll schrieb:

Außerdem könnte es evt schneller sein, die Dateien blockweise einzulesen und zu vergleichen (memcmp()).

das ist mit sicherheit schneller, spart nämlich ne menge zugriffe auf den massenspeicher.

Ich würde das auch mit MD5 machen. Diese Routine ist relativ schnell und sicher und das 2 Dateien die gleiche Prüfsumme haben, halte ich für relativ unwahrscheinlich.

Thomas ** 0

MD5 schrieb:

Ich würde das auch mit MD5 machen. Diese Routine ist relativ schnell und sicher und das 2 Dateien die gleiche Prüfsumme haben, halte ich für relativ unwahrscheinlich.

Das ist mit Sicherheit langsamer, denn dazu musst du beide Dateien ganz auslesen um die MD5 Pruefsummen zu bilden. Bei einem einfachen Vergleich kannst du schon abbrechen wenn ein Byte nicht gleich ist.

@Topic: Ich wueder als aller erster die Groesse vergleichen. Ist die nicht gleich hats sich eh schon erledigt.

RHBaum

Das ist mit Sicherheit langsamer, denn dazu musst du beide Dateien ganz auslesen um die MD5 Pruefsummen zu bilden.

Richtig, aber wenn er sagt das ihm nen kompletter scan eh zu langsam ist :

kann er optimieren klar, die frage ist ob das damit fuer seine anwendung schnell genug ist (inklusive aller varianten die z.b. Jordy vorschlaegt). DIe wahrscheinlichkeit ist relativ hoch !

@NES-Spieler
wie gross sind denn deine "daten" im schnitt ?

Wenn es wie gesagt ned schnellgenug ist, kommt als naechster schritt "caching" ins spiel ... einmal die datei scannen "nen eindeutigen Schluessel" hinterlegen, das er es nicht jedesmal tun muss. Dann kommen die pruefsummen doch wieder ins spiel.
Gibts da keine BS funktion fuer checksummen, die vielleicht im kernelspace laufen ?

@NES-Spieler
die daten die Du vergleichst, kommen die jedesmal neu von irgend ner externen quelle, oder vergleichst du mal die und mal die datei auf der pladde miteinander, die relativ "lang" schon da drauf laufen ...

Wenn die dateien von ner externen quelle kommen, kann man vielleicht deren "Lieferant" (dem Modul aufn eigenen PC mein ich ) aufbohren das er quasi die checksum gleich mit leifert, zum 0 tarif quasi, wenn das zeug als stream eintrudelt ...

Ciao ...

probier mal folgenden, noch nicht ausprobierten code, aus:

int main()
{
	const int size = 1024;
	std::ifstream in1("input1", ios::binary);
	std::ifstream in2("input2", ios::binary);
	std::vector<char> buf1(size);
	std::vector<char> buf2(size);
	while(in1) {
		in1.read(&buf1[0], size);
		in2.read(&buf2[0], size);
		if(in1.gcount() != in2.gcount()) {
			return 1;
		}
		if(memcmp(&buf1[0], &buf2[0], in1.gcount() != 0) {
			return 1;
		}
	}
	if(in2) { // in1 schon zuende aber in2 noch nicht???
		return 1;
	}
}

Die main funktion gibt 1 zurück wenn die dateien nicht gleich sind. Hab's noch nicht ausprobiert.
Einfach mal mit der Buffer größe rumspielen und gucken wie es sich auswirkt.

Am schnellsten gehts indem du die Dateien als memory-mapped files lädst und dann einfach nen memcmp drüberlaufen lässt. Ist dann allerdings nicht mehr mit std-c++ zu lösen. Dafür ist das ganze aber deutlich schneller, da die streams nicht gerade die schnellsten sind, wenn es um zugriff(e) geht.

hustbaer

Mach nen ~1MB grossen Puffer, und vergleich Stückweise. Das ist halbwegs schnell und einfach. Wenn du optimale Performance willst dann musst du asynchrone IOs verwenden. Glaube nicht dass memory mapped da noch mitkann. Plus es ist mindestens gleich kompliziert wie wenn du asynchrone IOs verwendest.

Für beides brauchst du allerdings die API von deinem OS weils in std. C++ dafür nix gibt.

Bei memory-mapped wird im Allgemeinen der gleiche Prozess verwendet wie beim paging, ich glaub kaum, dass das einblenden von daten in den speicher schneller gehen kann, sonst würd man es wohl beim paging auch anwenden.

hustbaer

Paging erkennt erst dass was andefordert wird wenn "der page-miss auftritt" - und dann is bloss bekannt dass diese eine page gebraucht wird, nicht aber wieviele noch. D.h. die Funktion die dann die Daten ausm File lädt muss schon sehr schlau raten wenn die grosse Blöcke auf einmal von der Platte lesen will -- weil das will sie natürlich bloss wenn die chance gross ist dass die pages nachher auch wirklich gebraucht werden. Und mit kleinen Blöcken lesen is eben merklich langsamer. Die page size von 4K ist lange noch nicht genug um das optimum aus einer Platte rauszuholen. Von daher schätze ich dass asio mit nem riesen Buffer (eben so ~1MB oder sogar mehr) schneller sein wird.

Du siehst also es gibt einen grund warum memory mapped langsamer sein kann ohne dass wer gepennt hat oder mist gebaut.

p.S.: gerade bei 2 Files auf der gleichen Platte wird memory mapped wahrscheinlich garnicht ideal sein.

NES-Spieler

Entschuldigt bitte, daß ich erst jetzt antworte.

Also, hier ein paar Kommentare zu einigen Eurer Aussagen:

Du könntest ja einen Vortest machen, ob die Dateien die selbe Größe haben (wenn nicht, sind sie garantiert verschieden).

Das mache ich natürlich sowieso. Also, diese ganzen Vortests sind quasi erledigt. Ich weiß, daß die Ordnerstruktur an beiden Stellen die gleiche ist und daß die Dateien jeweils die gleiche Größe haben. Jetzt geht es wirklich rein um den Inhalt.

Ich frage mich: Haben die Binären Dateien bekannte Eigenschaften?

Nein, es handelt sich lediglich um die Gesamtheit meiner gespeicherten Dateien. Das mit dem binär hab ich nur gesagt, um herauszustellen, daß es nicht nur Textdateien sind. Aber insgesamt ist eigentlich alles dabei: DOC, TXT, EXE, PDF, BMP, CFG etc.

wie gross sind denn deine "daten" im schnitt ?

Das kann ganz unterschiedlich sein. Von wenigen Byte bis zu mehreren Megabyte.

Vielleicht reicht in 90% der Fälle ein Vergleich von ein paar wenigen Bytes, um Ungleichheit festzustellen? Dann wäre nur noch in 10% der Fälle ein Vergleich der gesammten Dateien notwendig.

Ja, doch diese 10%, wo ein kompletter Vergleich notwendig ist, weil sich am Ende herausstellt, daß beide Ordnerinhalte gleich sind, dürften eigentlich bei 99% der Überprüfungen auftreten.

Der Sinn der Sache ist folgender: Sollte ein Virus auf meine Festplatte kommen, dann lösche ich vorsichtshalber die gesamte primäre Partition und spiele das Betriebssystem mit einer Backup-CD (die ein komplettes Image der gesamten Installation mit allen möglichen Programmen enthält) wieder rauf.
Ich habe eigene Dateien, die sowohl auf der Festplatte, als auch auf einer Daten-DVD gespeichert sind. Und nun will ich, bevor ich die primäre Partition lösche, gucken, ob sich die Dateien auf der Festplatte von denen auf der DVD unterscheiden. Wenn nicht, laß ich die Dateien einfach auf und muß sie nach der Neuinstallation nicht extra wieder von der DVD auf die Festplatte kopieren. Das heißt: Ich brauche ein Verfahren, das wirklich super schnell ist, das 700 MB in vielleicht drei Minuten oder so vergleichen kann. Wenn das gesamte Verfahren selbst schon 15 Minuten braucht, kann ich es ja gleich sein lassen und meine eigenen Dateien vor so einer Neuinstallation immer löschen. Denn ob ich im Vorfeld 15 Minuten für den Vergleich brauche oder ob ich im Nachhinein 15 Minuten aufwende, um die Dateien wieder von der DVD auf die Festplatte zu kopieren, ist ja unerheblich.

Mit welchem Algorithmus läuft eigentlich dieses Windows-eigene Programm "fc.exe"? Das wirkt auf mich immer recht flott. Im Notfall könnte ich ja in C++ auch das mit der system-Funktion aufrufen, statt selbst eine Vergleichsfunktion zu schreiben. Nur weiß ich nicht, wie ich den Rückgabewert rausfinde. Wenn ich

system ("fc /b MeineDatei1.bin MeineDatei2.bin");

schreibe, liefert system immer 0 zurück, egal, ob die Dateien gleich oder unterschiedlich sind.

CStoll

NES-Spieler schrieb:

Mit welchem Algorithmus läuft eigentlich dieses Windows-eigene Programm "fc.exe"? Das wirkt auf mich immer recht flott.

Keine Ahnung. Aber vermutlich liest es auch nur blockweise die Daten ein und vergleicht.

Im Notfall könnte ich ja in C++ auch das mit der system-Funktion aufrufen, statt selbst eine Vergleichsfunktion zu schreiben. Nur weiß ich nicht, wie ich den Rückgabewert rausfinde. Wenn ich
system ("fc /b MeineDatei1.bin MeineDatei2.bin");
schreibe, liefert system immer 0 zurück, egal, ob die Dateien gleich oder unterschiedlich sind.

system() liefert ja auch nur den Exitcode des aufgerufenen Programms zurück und nicht sein Monitor-Ausgabe. Du benötigst so etwas wie man: popen (weiß nicht, ob's das auch unter Windows gibt.

PS: Schonmal etwas von "Virenscanner" gehört?

NES-Spieler

system() liefert ja auch nur den Exitcode des aufgerufenen Programms zurück

Genau den brauch ich ja, um in meinem Programm zu überprüfen, ob meine Dateien gleich oder unterschiedlich sind. Aber hier liefert system eben immer nur 0.

und nicht sein Monitor-Ausgabe.

Doch, die wird, wenn ich system in einer Konsolenanwendung aufrufe, durchaus angezeigt. Das wäre dann auch das nächste Problem: Wie unterdrücke ich die Ausgabe von "fc.exe"? Immerhin soll mein Programm nur intern die Dateien vergleichen und am Ende eine eigene Nachricht ausgeben und nicht den Ausgabetext von "fc.exe" für jede der über 1000 Einzeldateien da hinklatschen.

Du benötigst so etwas wie popen

Wie gesagt, die Ausgabe von "fc.exe" will ich ja gar nicht haben, nur seinen Return-Code.

PS: Schonmal etwas von "Virenscanner" gehört?

Klar. Der spürt im ersten Schritt auf, daß ein Virus auf meiner Festplatte liegt. Mein Programm soll dann überprüfen, ob der Virus meine Dateien in irgendeiner Weise beschädigt hat. (Das muß ja nicht bedeuten, daß sich der Virus in meine Dateien spielt. Wenn er einige meiner Dateien mit Müll vollschreibt, hat er sie auch schon verändert/beschädigt, was der Virenscanner dann natürlich nicht rausfindet, weil der Müll in der Datei nicht selbst ein Virus ist.)

CStoll

NES-Spieler schrieb:

system() liefert ja auch nur den Exitcode des aufgerufenen Programms zurück
Genau den brauch ich ja, um in meinem Programm zu überprüfen, ob meine Dateien gleich oder unterschiedlich sind. Aber hier liefert system eben immer nur 0.

und nicht sein Monitor-Ausgabe.

Doch, die wird, wenn ich system in einer Konsolenanwendung aufrufe, durchaus angezeigt.

Ja, angezeigt wird sie - aber wenn ich dich richtig verstanden habe, willst du diese Ausgaben in deinem Programm auswerten.

Das wäre dann auch das nächste Problem: Wie unterdrücke ich die Ausgabe von "fc.exe"? Immerhin soll mein Programm nur intern die Dateien vergleichen und am Ende eine eigene Nachricht ausgeben und nicht den Ausgabetext von "fc.exe" für jede der über 1000 Einzeldateien da hinklatschen.

Mit popen() kannst du sie an dein Programm zurückleiten, über pipes (> oder |) an andere Ausgabequellen weiterleiten.

Du benötigst so etwas wie popen

Wie gesagt, die Ausgabe von "fc.exe" will ich ja gar nicht haben, nur seinen Return-Code.

Bist du sicher? Afaik gibt fc nur die Unterschiede der Dateien auf dem Bildschirm aus:

help fc schrieb:

Vergleicht zwei Dateien oder zwei Sätze von Dateien und zeigt die Unterschiede zwischen ihnen an.

NES-Spieler

Ja, angezeigt wird sie - aber wenn ich dich richtig verstanden habe, willst du diese Ausgaben in deinem Programm auswerten.

Naja, ich will das Ergebnis auswerten, nicht unbedingt den Ausgabestring. Der lautet ja ungefähr so:

Verglichen werden
C:\Eigene~1\Bild.bmp
E:\Bild.bmp

Keine Unterschiede gefunden.

Wenn ich das auswerten wollte, müßte ich es ja erst in einen String speichern und in dem dann nach "Keine Unterschiede gefunden." suchen.

Bist du sicher? Afaik gibt fc nur die Unterschiede der Dateien auf dem Bildschirm aus

Naja, aber sollte so ein Programm nicht trotzdem auch einen Fehlercode zurückgeben (0 bei Gleichheit, 1 bei Ungleichheit)? Ich kann es im Moment leider ncht ausprobieren, aber wenn es tatsächlich nur 0 zurückliefert, ist das natürlich nicht so günstig. (Da das ein Konsolenprogramm ist, das nur über seine Parameter gesteuert wird, hätten die doch zumindest auf die Idee kommen müssen, das sowas vielleicht mal in Batch-Dateien oder so zur Analyse genutzt wird.)

CStoll

NES-Spieler schrieb:

Ja, angezeigt wird sie - aber wenn ich dich richtig verstanden habe, willst du diese Ausgaben in deinem Programm auswerten.

Naja, ich will das Ergebnis auswerten, nicht unbedingt den Ausgabestring. Der lautet ja ungefähr so:

Verglichen werden
C:\Eigene~1\Bild.bmp
E:\Bild.bmp

Keine Unterschiede gefunden.

Wenn ich das auswerten wollte, müßte ich es ja erst in einen String speichern und in dem dann nach "Keine Unterschiede gefunden." suchen.

Ja, da wird dir womöglich nichts anderes übrig bleiben.

Bist du sicher? Afaik gibt fc nur die Unterschiede der Dateien auf dem Bildschirm aus

Naja, aber sollte so ein Programm nicht trotzdem auch einen Fehlercode zurückgeben (0 bei Gleichheit, 1 bei Ungleichheit)? Ich kann es im Moment leider ncht ausprobieren, aber wenn es tatsächlich nur 0 zurückliefert, ist das natürlich nicht so günstig. (Da das ein Konsolenprogramm ist, das nur über seine Parameter gesteuert wird, hätten die doch zumindest auf die Idee kommen müssen, das sowas vielleicht mal in Batch-Dateien oder so zur Analyse genutzt wird.)

Ja, sollte - aber ob es das macht, ist die andere Frage. Kannst ja mal auf Batch-Ebene die exitcodes auswerten.