3. [Gelöst] Mehrfach-Dateien erkennen C++ und std::filesystem

[Gelöst] Mehrfach-Dateien erkennen C++ und std::filesystem


  • @Schlangenmensch sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Kryptografische Hashfunktionen: Es ist hinreichend schwer eine Kollision zu finden (Pre-image resistance, Second pre-image resistance und collsion resistance)

    Ich verstehe schon was SeppJ meint.

    So einfach darf man nicht Hash Funktion und kryptografische Hashfunktionen in einen Topf werfen. Folgende zusätzliche Eigenschaften von kryptografischen Hashfunktionen kenne ich noch:

    0
    S
     1 Antwort

  • Also ich würde es vermutlich so machen:

    1. Pfade und Grössen sammeln
    2. Eindeutig einzigartige Files anhand der Grösse ermitteln und rauswerfen
    3. Von allem was übrig geblieben ist einen Hash über die ersten paar kB erstellen
    4. Eindeutig einzigartige Files anhand der Grösse + partiellem Hash ermitteln und rauswerfen

    Danach könnte man dann entweder einen Hash über den gesamten Inhalt machen.

    Oder man könnte einen weiteren partiellen Hash über einen grösseren Bereich machen und schauen was danach noch übrig geblieben ist. Dann einen nochmal grösseren Bereich usw. bis man alle verbliebenen Files vollständig gehasht hat.

    Evtl. könnte es auch Sinn machen zusätzlich zu den ersten paar kB auch die letzten paar kB zu hashen. Gibt ja ein paar File-Formate die sich in bestimmten Fällen erst sehr weit hinten unterscheiden. Z.B. ZIP Archive die sich erst in Files unterscheiden die zuletzt hinzugefügt wurden. Die könnte man dann schneller rauswerfen.

    Weiters würde es vermutlich auch Sinn machen die Inodes der Files zu ermitteln. Denn zwei Files die die selbe Inode haben (und auf dem selben Volume liegen) sind ja notwendigerweise identisch. Die sollte das Programm dann nicht vergleichen. Und ggf. auch gesondert ausweisen. Denn wenn es z.B. darum geht dass man Speicherplatz sparen will indem man Duplikate löscht, dann könnte es interessant sein dass diese "Duplikate" gar keinen Speicherplatz verschwenden. Also abgesehen von dem bisschen Platz den der Verzeichniseintrag braucht.

    0
  • S

    @Quiche-Lorraine @SeppJ Wahrscheinlich habe ich mich ungünstig ausgedrückt. Mir ging es darum, dass Kollisionsresitenz ein Merkmal von krypotografischen Hashfunktionen sind, aber nicht von Hashfunktionen im Allgemeinen.
    zB. die einstellige Quersumme, ist eine Hashfunktion, aber natürlich weit weg von einer kryptorafischen Hashfunktion. U.a. ist es hier sehr einfach eine Kollision zu erzeugen.

    0 1 Antwort

  • @Schlangenmensch sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    @Quiche-Lorraine @SeppJ Wahrscheinlich habe ich mich ungünstig ausgedrückt. Mir ging es darum, dass Kollisionsresitenz ein Merkmal von krypotografischen Hashfunktionen sind, aber nicht von Hashfunktionen im Allgemeinen.

    Resistenz gegen zufällige Kollisionen ist eine Eigenschaft jeder (guten) Hashfunktion. Natürlich nur soweit die Länge/der Wertebereich es zulässt. Was dagegen nicht für jede Hashfunktion erforderlich ist, ist Resistenz gegen Angriffe, wo man absichtlich versucht Kollisionen herbeizuführen.

    zB. die einstellige Quersumme, ist eine Hashfunktion, aber natürlich weit weg von einer kryptorafischen Hashfunktion. U.a. ist es hier sehr einfach eine Kollision zu erzeugen.

    Das ist ein unsinniges Beispiel. Das Problem ist hier nicht nur der Algorithmus, sondern bereits der Wertebereich. Den Wertebereich gross genug zu machen ist aber nicht genug. Es muss auch der Algorithmus derart sein, dass es trotz voller Kontrolle über die Inputs praktisch unmöglich ist zwei Inputs zu erzeugen die auf den selben Wert hashen.

    0
    S
     1 Antwort
  • S

    @hustbaer Aber all das sind nicht zwangsläufig Eigenschaften von Hashfunktionen, sondern Eigenschaften die von speziellen Hashfunktionen für bestimmte Anwendungen gefordert werden.

    Nehmen wir die Prüfsumme für eine IBAN (Module 97-10). Die ist 2 Stellig. Da wird ein 20 stelliger Wertebereich auf 2 Stellen reduziert. Das reicht um typische Vertipper zu erkennen, ist aber weit weg von dem, was ich unter Kollisionsresitenz verstehe.

    0

  • @Schlangenmensch
    Ich würde die IBAN Prüfsumme nicht als Hashfunktion bezeichnen.

    0
  • W

    Warum nicht?

    Ich habe mal geschaut, was Wikipedia schreibt. Dort findet sich u.a. der Satz "Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen". (Hervorhebung von mir)

    Der Definition dort scheint das auch nicht zu widersprechen.

    Dann kommt auf allerdings der Absatz "Kriterien" mit "Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte." Das klingt nach Wischi-Waschi und ich kann es aus der Definition dort nicht ableiten. Finde auch spannend, dass dort "Die Funktion muss schnell berechenbar sein" als Kriterium angegeben ist. Für Krypto kann man ja auch das Gegenteil wollen.

    (nun ist Wikipedia aber sicher nicht der einzige Ort, wo es Definitionen von Hash-Funktionen gibt).

    0 1 Antwort

  • @wob sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Warum nicht?

    Der Zweck einer Prüfsumme ist es Fehler zu erkennen.
    Der Zweck eines Hashcodes ist es Inputs gleichmässig auf Buckets zu verteilen.

    Es gibt natürlich viele Algorithmen die sich für beides gut eignen.

    Und der Zweck der IBAN Prüfsumme ist halt Fehler zu erkennen. Weiters ist sie als Hashcode nur sehr begrenzt geeignet - eigentlich nur wenn man zufällig genau 97 Buckets verwenden will. Mehr Buckets geht sowieso nicht, und bei weniger Buckets muss man eine beträchtliche Ungleichverteilung in Kauf nehmen. Von daher macht die Bezeichnung als Hashcode mMn. keinen Sinn.

    0

  • @SeppJ sagte in Mehrfach-Dateien erkennen C++ und std::filesystem:

    Aber hoffentlich nicht alles auf einmal?

    Upps... daran muss man arbeiten, hatte ich schon vermutet, das ist ja katastrophal langsam (und außerdem müsste man wohl Spezialfälle für große Dateien ebenfalls betrachten).

    Das ist jetzt das Beste, was ich ohne Hashing und sonstigen Schnick-Schnack erzielen konnte, für den ad-hoc Dateivergleich:

    template<std::streamsize BufSize>
bool is_duplicate_file(const fs::path& a_path, const fs::path& b_path)
{
	if (!fs::is_regular_file(a_path) || !fs::is_regular_file(b_path)) return false;
        if (fs::equivalent(a_path, b_path)) return true;
	if (fs::file_size(a_path) != fs::file_size(b_path)) return false;
	
	std::ifstream a_in{ a_path, std::ios::binary };
	std::ifstream b_in{ b_path, std::ios::binary };
	if (!a_in || !b_in) {
		// Exceptional case because files cannot be compared. Therefore, can neither return true nor false.
		throw std::runtime_error("is_duplicate_file: Unable to open file(s) for reading");
	}
	if (a_in.peek() != b_in.peek()) return false;
	
	std::array<char, BufSize> a_buf{};
	std::array<char, BufSize> b_buf{};
	while (a_in.read(a_buf.data(), BufSize) && b_in.read(b_buf.data(), BufSize)) {
		if (a_buf != b_buf) return false;
	}
	
	if (!a_in.eof() || !b_in.eof()) {
		// Exceptional case because if this point is reached, given file sizes are equal, eventually while-loop would exit due to eof().
		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
	}
	
	return true;
}
    0
  • Mod

    Schaut mir fein aus 👍

    0 1 Antwort

  • @SeppJ Ein Bug ist mir noch reingerutscht, ich weiß auch gar nicht, ob man so einen Mist verhindern kann (o.k., mit Tests halt, oder wahrscheinlich bessere Namensgebung, z. B. sollten a und b eher bennant sein, um auf einen Pfad/Datei/... hinzudeuten, wie a_path und b_path):

    if (a != b) return false;
// muss sein:
if (a_buf != b_buf) return false;

    Edit 1: Weiterer potenzieller Bug, durch die Konstruktion der while-Schleife wird beim letzten gültigen read bereits a_in.eof() und somit wird das letzte b.read() nicht mehr erreicht, ist mir dadurch erst aufgefallen, dass die if (!a_in.eof() || !b_in.eof()) Ausnahme ausgelöst wurde.

    while (a_in.read(a_buf.data(), BufSize) && b_in.read(b_buf.data(), BufSize))

// müsste evtl. sein: -- NEIN, das ist Quatsch, das ist wie while(true)
while ((a_in.read(buf_a.data(), BufSize) || a_in.eof()) && 
       (b_in.read(buf_b.data(), BufSize) || b_in.eof()))
{
}

// müsste evtl. sein (das ist auch nicht optimal, wenn a::fail und b nicht, aber die Dateien in Wirklichkeit gleich wären, passt es nicht):
do {
	a_in.read(buf_a.data(), BufSize);
	b_in.read(buf_b.data(), BufSize);
	if (buf_a != buf_b) return false;
} while (a_in && b_in);

// Oder so, und dann den äußeren if (!a_in.eof() || !b_in.eof()) weglassen (hässlich, aber gut?):
do {
	a_in.read(buf_a.data(), BufSize);
	if (a_in.fail() || a_in.bad())
		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
		
	b_in.read(buf_b.data(), BufSize);
	if (b_in.fail() || b_in.bad())
		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
		
	if (buf_a != buf_b) return false;
} while (a_in && b_in);
    0
  • Mod

    Argh, das hätte mir auffallen müssen. Zumal ich speziell auf das Verhalten in Fehlerfällen geachtet habe, das aber solide aussieht. Habe da wohl beim Lesen den Normalfall vernachlässigt 🙂

    PS: Was hältst du von a_in.read(…).rd-state() == b_in.read(…).rd_state() && a_in?
    PPS: Schaut so aus als hätte ein iostate keinen Vergleichsoperator 😞 . Cast zu bool dann? Deine Vorschläge finde ich jedenfalls ein bisschen schwer verständlich, bin mir gar nicht sicher, ob sie stimmen.

    0 1 Antwort

  • @SeppJ Meine Überlegung ist, dass das mit der while-Bedingung (und Prüfen des Rückgabewerts von read()) nicht funktioneren kann, weil eof() immer abbrechen würde. Also ich könnte damit leben:

    while (a_in && b_in) {
	a_in.read(buf_a.data(), BufSize);
	b_in.read(buf_b.data(), BufSize);
	if (a_in.fail() || a_in.bad() || b_in.fail() || b_in.bad()) {
		throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
	}
	if (buf_a != buf_b) return false;
}

    Edit2: Ach manno: https://devdocs.io/cpp/io/ios_base/iostate

    [...]
    Note that in nearly all situations, if eofbit is set, the failbit is set as well.
    [...]
    The failbit is set by the following standard library functions:

    • basic_istream::read, if the end-of-file condition occurs on the input stream before all requested characters could be extracted.

    Es scheint eigentlich so, dass realistisch bei read() nichts schiefgehen kann, sobald die Datei erfolgreich geöffnet wurde (was nicht auch das Programm abschießen würde, z. B. Stromausfall), außer dass die Dateien EOF sind. Vielleicht ist also dieser zweite Check mit throw overkill.

    Edit3: Noch ein allgemeiner Hinweis (oder Vermutung): Die filesystem Funktionen wie file_size oder is_regular_file führen zu "syscalls" o. Ä. und unnötige Aufrufe sind unbedingt zu vermeiden / minimieren, sofern möglich. Ich hatte einen zusätzlichen file_size sowie is_regular_file aufruf und dadurch gleich mal die Performance halbiert im Vergleich zur Funktion ohne die zusätzlichen Aufrufe. Wohingegen fs::equivalent vernachlässigbar zu sein scheint. Die Verwendung von peek() bringt nicht zuverlässig etwas, sodass sich die Zeile wohl nicht lohnt.
    Wie man sieht, habe ich einiges ausprobiert:

    $ ./dupf.exe --benchmark 'D:/Pictures'
Running [FileCompare_baseline]
  Total bytes compared   : 0
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 2481.48ms

Running [FileCompare_baseline_file_size]
  Total bytes compared   : 0
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3515.58ms

Running [FileCompare_baseline_is_regular_file]
  Total bytes compared   : 0
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3534.22ms

Running [FileCompare_bytewise_ignoreSize]
  Total bytes compared   : 48502896
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 7210.14ms

Running [FileCompare_bytewise_peek_ignoreSize]
  Total bytes compared   : 48472646
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 30264
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 7464.32ms

Running [FileCompare_noHash<128ll>]
  Total bytes compared   : 48453120
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3639.78ms

Running [FileCompare_noHash_2<128ll>]
  Total bytes compared   : 44416768
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 12
  Time                   : 3642.16ms

Running [FileCompare_noHash_2_ignoreSize<128ll>]
  Total bytes compared   : 44759040
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 30264
  Total seekg exits      : 0
  Total duplicates found : 12
  Time                   : 10373.1ms

Running [FileCompare_bytewise_size]
  Total bytes compared   : 48454500
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 4923.53ms

Running [FileCompare_stdequal_ignoreSize<128ull>]
  Total bytes compared   : 52627840
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 5880.31ms

Running [FileCompare_memcmp_ignoreSize<128ull>]
  Total bytes compared   : 52627840
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 5890.91ms

Running [FileCompare_stdequal<128ull>]
  Total bytes compared   : 48453120
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3618.82ms

Running [FileCompare_memcmp<128ull>]
  Total bytes compared   : 48453120
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3671.38ms

Running [FileCompare_stdequal<2048ull>]
  Total bytes compared   : 48439296
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3623.17ms

Running [FileCompare_memcmp<2048ull>]
  Total bytes compared   : 48439296
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3608.61ms

Running [FileCompare_memcmp<16384ull>]
  Total bytes compared   : 48365568
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3548.36ms

Running [FileCompare_memcmp<65536ull>]
  Total bytes compared   : 47972352
  Total files compared   : 12
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 3545.12ms

Running [FileCompare_mmap]
  Total bytes compared   : 48454488
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 12
  Time                   : 7584.03ms

Running [FileCompare_peek_end]
  Total bytes compared   : 48454500
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 8355.01ms

Running [FileCompare_xxHash]
  Total bytes compared   : 48454488
  Total files compared   : 32950
  Total size exits       : 32938
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 12
  Time                   : 3564.38ms

Running [FileCompare_readall]
  Total bytes compared   : 7533884225
  Total files compared   : 32950
  Total size exits       : 0
  Total peek exits       : 0
  Total seekg exits      : 0
  Total duplicates found : 0
  Time                   : 13140.2ms

    Man sieht auch wie viele dieser "Benchmarks" hier tatsächlich fehlerbehaftet waren (weil "Total duplicates found : 0", obwohl es 12 sein müssen), wegen ähnlicher Probleme wie oben beschrieben, weil der eof() Fall beispielsweise nicht korrekt gehandhabt wird. Die Zahlen sind trotzdem einigermaßen nützlich für mich gewesen. Die oben beschriebene Funktion wird durch FileCompare_noHash_2 verwendet.

    0

  • Ich würde hier explizit memcmp verwenden für den Vergleich. Klar, man kann hoffen dass std::array::operator == ne passende Spezialisierung hat oder der Compiler schlau genug ist die char-Vergleichs-Schleife zu nem memcmp zu optimieren. Aber man kann es auch direkt selbst hinschreiben und sich sicher sein 😉

    Weitere Optimierung wird dann ... schwierig. Weil man dann unterscheiden müsste ob die Files vom selben Datenträger kommen oder nicht. Auf dem selben Datenträger wären sehr grosse Puffer von Vorteil und abwechselnd Lesen -- speziell wenn es HDDs sind. Bei unterschiedlichen Datenträgern ist meist ne kleinere Puffergrösse besser und gleichzeitig lesen (mit async IO oder zwei Threads).

    Und dann kann man natürlich noch den Vergleich in einen eigenen Thread auslagern. Also zwei Sets an Puffern verwenden und dann gleichzeitig Lesen und Vergleichen.

    Wobei es gut sein kann dass man mit passender Puffergrösse selbst mit der einfachen Variante (single threaded, synchron) in den meisten Fällen close-to-optimal Performance schaffen wird. Jedes vernünftige OS macht ja read-ahead. Man muss nur schauen dass man den read-ahead Mechanismus nicht ohne es zu wollen deaktiviert -- was AFAIK passiert wenn man zu grosse Puffer verwendet. 64 oder 128 kB sollte "safe" sein.

    0 1 Antwort

  • @hustbaer Danke für die zusätzlichen Hinweise.
    Um das Thema im Rahmen zu halten war mein Ziel, ein einfach gestricktes "standard C++", single-threaded Programm ohne (explizit) OS-spezifische Funktionen zu verwenden, auch um einfach std::filesystem mal auszuloten aber auch überhaupt kennenzulernen. Das wird nicht "perfekt" sein bei weitem. Allein dieses "inode"-Thema habe ich bei anderer SW auch schon gesehen, und darauf hat man mit std::filesystem gar keinen Zugriff. D. h. ich habe eine einfache is_duplicate Funktion, das werde ich demnächst noch mit dem Rest verknüpfen und dann lass ich's erstmal gut sein.

    Ich hab ja von dem Ganzen nicht so viel Ahnung, aber ich interpretiere das so, dass GCC die schlaue memcmp Optimierung durchführt, man kann also eigentlich immer getrost std::equal verwenden (und std::array::operator== verwendet (hier) auch std::equal):

    // [gcc/libstdc++-v3/include/std/array]
// ...
  // Array comparisons.
  template<typename _Tp, std::size_t _Nm>
  [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
  inline bool operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
    { return std::equal(__one.begin(), __one.end(), __two.begin()); }
// ..

// [gcc/libstdc++-v3/include/bits/stl_algobase.h]
  template<bool _BoolType>
    struct __equal
    {
      template<typename _II1, typename _II2>
	_GLIBCXX20_CONSTEXPR
	static bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
	{
	  for (; __first1 != __last1; ++__first1, (void) ++__first2)
	    if (!(*__first1 == *__first2))
	      return false;
	  return true;
	}
    };

  template<>
    struct __equal<true>
    {
      template<typename _Tp>
	_GLIBCXX20_CONSTEXPR
	static bool equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
	{
	  if (const size_t __len = (__last1 - __first1))
	    return !std::__memcmp(__first1, __first2, __len);
	  return true;
	}
    };
// ...
  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      typedef typename iterator_traits<_II1>::value_type _ValueType1;
      const bool __simple = ((__is_integer<_ValueType1>::__value
			      || __is_pointer<_ValueType1>::__value)
			     && __memcmpable<_II1, _II2>::__value);
      return std::__equal<__simple>::equal(__first1, __last1, __first2);
    }

  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      return std::__equal_aux1(std::__niter_base(__first1), std::__niter_base(__last1), std::__niter_base(__first2));
    }
// ...
  template<typename _II1, typename _II2>
    _GLIBCXX20_CONSTEXPR
    inline bool equal(_II1 __first1, _II1 __last1, _II2 __first2)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_II1>)
      __glibcxx_function_requires(_InputIteratorConcept<_II2>)
      __glibcxx_function_requires(_EqualOpConcept<
	    typename iterator_traits<_II1>::value_type,
	    typename iterator_traits<_II2>::value_type>)
      __glibcxx_requires_can_increment_range(__first1, __last1, __first2);

      return std::__equal_aux(__first1, __last1, __first2);
    }

    Aber ich sehe den Punkt, man kann ja auch einfach <cstring> und std::memcmp verwenden, warum nicht, ja.

    0

  • Hier jetzt ein aktualisiertes Beispielprogramm:

    #include <array>
#include <cstring>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>

namespace fs = std::filesystem;
static constexpr std::streamsize BufSize{ 4096 };

template<std::streamsize BufSize>
bool is_duplicate_file(const fs::directory_entry& file_a, const fs::directory_entry& file_b) {
    if (!file_a.is_regular_file() || !file_b.is_regular_file()) {
        return false;
    }
    if (fs::equivalent(file_a, file_b)) {
        return true;
    }
    if (file_a.file_size() != file_b.file_size()) {
        return false;
    }

    std::ifstream a_in{ file_a.path(), std::ios::binary };
    std::ifstream b_in{ file_b.path(), std::ios::binary };
    if (!a_in || !b_in) {
        throw std::runtime_error("is_duplicate_file: Unable to open file(s) for reading");
    }
    
    if (a_in.peek() != b_in.peek()) {
        return false;
    }
    std::array<char, BufSize> buf_a{};
    std::array<char, BufSize> buf_b{};
    while (a_in && b_in) {
        a_in.read(buf_a.data(), BufSize);
        b_in.read(buf_b.data(), BufSize);
        /* Seems superfluous since what can fail besides hitting EOF on ifstream::read().
        if (a_in.fail() && !a_in.eof() || a_in.bad() || b_in.fail() && !b_in.eof() || b_in.bad()) {
            throw std::runtime_error("is_duplicate_file: Unexpected file read error while comparing");
        }
        */
        if (std::memcmp(buf_a.data(), buf_b.data(), BufSize))
            return false;
    }
    return true;    
}

auto build_file_index(const fs::path& start_path) {
    std::unordered_multimap<std::uintmax_t, fs::directory_entry> files_by_size;
    for (const auto& entry : fs::recursive_directory_iterator{ start_path }) {
        if (entry.is_regular_file()) {
            files_by_size.emplace(entry.file_size(), entry);
        }
    }
    return files_by_size;
}

auto find_duplicate_files(const auto& files) {
    std::unordered_map<fs::path, std::vector<fs::path>> dupes;
    for (auto entry = files.begin(); entry != files.end(); ) {
        auto range{ files.equal_range(entry->first) };
        int idx_i{};
        std::vector<bool> matched(std::distance(range.first, range.second), false);  // std::unordered_map<fs::path, bool> works, too!
        for (auto i = range.first; i != range.second; ++i, ++idx_i) {
            int idx_j{ idx_i + 1 };
            for (auto j = std::next(i); j != range.second; ++j, ++idx_j) {
                if (!matched[idx_i] && !matched[idx_j] && is_duplicate_file<BufSize>(i->second, j->second)) {
                    dupes[i->second.path()].emplace_back(j->second.path());
                    matched[idx_j] = true;
                }
            }
        }
        entry = range.second;
    }
    return dupes;
}

void print_dupes(const auto& dupes) {
    for (const auto& a : dupes) {
        std::cout << "\nReference: " << a.first << '\n';
        for (const auto& b : a.second) {
            std::cout << "Duplicate: " << b << '\n';
        }
    }
    std::cout << "\nFound a total of " << dupes.size() << " duplicate groups.\n\n";
}

int main(int argc, char* argv[])
try {
    if (argc != 2) {
        std::cout << "Program expects one argument: <Starting path>\n";
        return 1;
    }
    
    fs::path start_path{ argv[1] };
    if (!fs::exists(start_path)) {
        std::cout << "Provided argument is not an existing path.\n";
        return 2;
    }
    
    print_dupes(
        find_duplicate_files(
            build_file_index(start_path)));
}
catch (const fs::filesystem_error& e) {
    std::cerr << e.what() << '\n';
    return e.code().value();
}
catch (const std::runtime_error& e) {
    std::cerr << e.what() << '\n';
    return -2;
}
catch (...) {
    std::cerr << "Unhandled exception!\n";
    return -1;
}

    Edit 1: Ich hatte beim Programmieren auch an std::unordered_map<fs::path, bool> gedacht, was sich performance-technisch nicht viel schenkt mit std::vector<bool>. Inzwischen wurde ich darauf hingewiesen, dass man auch einfach std::unordered_set<fs::path> verwenden könnte - auch von der Performance her ähnlich, aber wahrscheinlich eleganter als dieser Pfusch mit den Indizes.
    Die Idee war klar, wenn z. B. Dateien A, B, C mit Größe X geprüft werden, und ich habe bereits erkannt, dass Datei B mit A identisch sind, dann brauche ich gar nicht erst versuchen, Datei B auch noch mit C zu vergleichen (das wäre sinnlos, wenn B==C, dann wäre C bereits gegen A gefunden worden).

    Edit 2:
    Jetzt so:

    auto find_duplicate_files(const auto& files) {
    std::unordered_map<fs::path, std::vector<fs::path>> duplicates;
    std::unordered_set<fs::path> matched;
    for (auto left = files.begin(); left != files.end(); ) {
        auto range = files.equal_range(left->first);
        left = range.second;
        for (auto ref_it = range.first; ref_it != range.second; ++ref_it) {
            if (matched.contains(ref_it->second.path())) {
                continue;
            }
            for (auto file_it = std::next(ref_it); file_it != range.second; ++file_it) {
                if (!matched.contains(file_it->second.path()) && is_duplicate_file<BufSize>(ref_it->second, file_it->second)) {
                    matched.emplace(file_it->second.path());
                    duplicates[ref_it->second.path()].emplace_back(file_it->second.path());
                }
            }
        }
    }
    return duplicates;
}
    0
Anmelden zum Antworten