Czy trzeba czytać każdy bajt, aby sprawdzić, czy skopiowany plik jest identyczny z oryginałem?

16

Niedawno dowiedziałem się o programie o nazwie Total Commander. Jest to zamiennik Eksploratora Windows i ma własne rzeczy do kopiowania plików. Aby sprawdzić, czy pliki są identyczne, zamiast obliczać CRC, dosłownie sprawdza każdy bajt, jeden po drugim, zarówno na oryginale, jak i na kopii.

Moje pytanie brzmi: czy to konieczne? Czy CRC lub jakakolwiek inna technika może się nie udać? Czy jako programista powinieneś wdrożyć ten doskonały, ale powolny system, czy może jest on zbyt ekstremalny?

difference file-handling

— Koen027
źródło

3

Zobacz, jak radzi sobie z tym „rsync”.

21

Obliczanie CRC (lub, lepiej, sum sha1) w obu plikach i tak wymaga odczytu każdego bajtu. Jeśli porównasz bajt po bajcie, możesz wyjść, gdy tylko zobaczysz niedopasowanie - i nie musisz się martwić o dwa różne pliki, które mają taką samą sumę kontrolną (choć jest to mało prawdopodobne w przypadku sha1sum) . Z drugiej strony porównania sum kontrolnych są przydatne, gdy porównujesz pliki, które nie są na tym samym komputerze; sumy kontrolne można obliczać lokalnie i nie trzeba przesyłać całej zawartości przez sieć.

— Keith Thompson,

3

Jeśli chodzi o prawdopodobieństwo kolizji, jeśli używasz porządnego skrótu, takiego jak sha1sumty, nie musisz się o to martwić, chyba że ktoś celowo i kosztownie konstruuje pliki, których sumy zderzają się. Nie mam na to źródła, ale słyszałem (w kontekście git), że prawdopodobieństwo, że dwa różne pliki mają tę samą sumę sumaryczną, jest mniej więcej takie samo, jak prawdopodobieństwo, że każdy członek zespołu programistów zostanie zjedzony przez wilki Tego samego dnia. W całkowicie niepowiązanych zdarzeniach.

— Keith Thompson,

5

@KeithThompson: Myślę, że twój pierwszy komentarz powinien być odpowiedzią :-)

— Dean Harding

6

Krótka odpowiedź - nie, najlepiej, aby komputer zrobił to za ciebie.

— psr

40

Obliczanie CRC (lub, lepiej, sum sha1) w obu plikach i tak wymaga odczytu każdego bajtu. Jeśli porównasz bajt po bajcie, możesz wyjść, gdy tylko zobaczysz niedopasowanie - i nie musisz się martwić o dwa różne pliki, które mają taką samą sumę kontrolną (choć jest to mało prawdopodobne w przypadku sha1sum) . Jeśli więc przeprowadzasz porównanie lokalnie, porównanie bajt po bajcie będzie co najmniej tak szybkie jak porównanie sumy kontrolnej (chyba że i tak już obliczyłeś sumy kontrolne).

Z drugiej strony porównania sum kontrolnych są przydatne podczas porównywania plików, które nie znajdują się na tym samym komputerze; sumy kontrolne można obliczać lokalnie i nie trzeba przesyłać całej zawartości przez sieć.

Możliwe są również podejścia hybrydowe. Na przykład możesz obliczyć i porównać sumy kontrolne dla dwóch plików po jednym kawałku, co pozwoli uniknąć odczytu całych plików ( jeśli się różnią), a jednocześnie pozwoli uniknąć przesyłania całego pliku przez sieć. Protokołem rsync robi coś takiego.

Zauważ, że użycie prostego CRC daje uczciwą szansę na kolizję, jak wspomniał Dave Rager w swojej odpowiedzi. Użyj przynajmniej sha1sum lub nawet czegoś nowszego. (Nie próbuj wynaleźć własnego algorytmu haszującego; ludzie, którzy opracowali sha1sum, wiedzą o tym dużo więcej niż każdy z nas.)

Jeśli chodzi o prawdopodobieństwo kolizji, jeśli używasz porządnego skrótu, takiego jak sha1sum, prawie nie musisz się tym martwić, chyba że ktoś celowo i kosztownie konstruuje pliki, których zderzają się sha1sum (generowanie takich kolizji nie było wykonalne, kiedy pierwszy raz to napisałem , ale poczyniono postępy ). Cytując „Pro Git” Scotta Chakona , sekcja 6.1 :

Oto przykład, który daje wyobrażenie o tym, czego potrzeba, aby uzyskać kolizję SHA-1. Gdyby wszystkie 6,5 miliarda ludzi na Ziemi programowało i co sekundę, każdy produkowałby kod, który byłby ekwiwalentem całej historii jądra Linuksa (1 milion obiektów Git) i umieszczał go w jednym ogromnym repozytorium Git, zajęłoby to 5 lat repozytorium zawierało wystarczającą liczbę obiektów, aby prawdopodobieństwo 50% zderzenia pojedynczego obiektu SHA-1 było 50%. Istnieje większe prawdopodobieństwo, że każdy członek zespołu programistycznego zostanie zaatakowany i zabity przez wilki w niepowiązanych zdarzeniach tej samej nocy.

Streszczenie :

Porównanie bajtów po bajcie jest dobre dla porównań lokalnych. sha1sum jest dobry do zdalnego porównywania i nie ma znaczącej szansy na fałszywe alarmy.

— Keith Thompson
źródło

Należy zauważyć, że wspólna definicja „dobrej” funkcji skrótu obejmuje właściwość polegającą na tym, że bardzo trudno jest tworzyć różne dane wejściowe za pomocą tego samego skrótu („odporność na kolizje”). SHA-1 ma pewne (jak dotąd teoretyczne) słabości w tym zakresie, ale nie można po prostu „zbudować dwóch plików, które kolidują”, nawet jeśli bardzo się starasz.

— śleske,

@sleske: Zaktualizowano

— Keith Thompson

1

@KeithThompson Poprawiam odpowiedź, ale myślę, że nadszedł czas na aktualizację SHA1 - SHAppening

— K.Steff,

Podejrzewam, że zepsują się, jeśli spróbujesz zorganizować te teoretyczne repozytorium na GitHub.

— hBy2Py 18.10.16

1

Miałem na myśli to, że byliby niezadowoleni z powodu posiadania tak wielu eksabajtów na sekundę danych. :-)

— hBy2Py 18.10.16

10

Oto inny sposób, aby o tym pomyśleć.

Jeśli nie ma możliwości, że dwa różne pliki mają ten sam CRC, to przez rozszerzenie oznacza, że każdy plik może być reprezentowany przez unikalny CRC. Jeśli CRC byłby mniejszy niż oryginalny plik, reprezentowałby on formę bezstratnej kompresji. Jeśli nie, równie dobrze byłoby porównać oryginalne pliki, ponieważ porównywałbyś tę samą liczbę bajtów.

Teoretycznie możesz użyć bezstratnej kompresji obu stron porównania, aby zmniejszyć liczbę bajtów potrzebnych w porównaniu, ale jest to głupota, ponieważ marnowałbyś więcej cykli i musiałeś czytać każdy bajt obu plików, aby wykonać kompresję . Oznacza to, że aby zakodować każdy bajt (i jego kolejność) w bezstratnym schemacie kompresji, musisz najpierw go odczytać i podłączyć do algorytmu, prawda? Koniec gry.

Oto analogia:
jeśli chciałbyś szybko ustalić, czy dwa drukowane dokumenty były identyczne bez porównywania liter po literze, możesz porównać liczbę liter w każdym wierszu dokumentów. Jeśli liczone są wszystkie pasujące, szanse znacznie się poprawiają, że dokumenty są identyczne, jednak nikt nie argumentowałby, że można być pewnym, że każda litera była taka sama, stosując takie podejście.

— JohnFx
źródło

3

Jedynym doskonałym sposobem sprawdzenia identycznych plików jest bajt do porównania bajtów. Innym sposobem na uczciwe zbliżenie jest obliczenie skrótu, takiego jak MD5, dla plików i ich porównanie. Możliwe, że doszło do kolizji skrótu, ale mało prawdopodobne.

Wyobrażam sobie, że bajt dla porównania bajtów byłby szybszy niż obliczanie skrótu dla obu plików w czasie, gdy robisz porównanie. Jeśli jednak aplikacja wstępnie obliczy skrót i zapisze metadane dotyczące plików, porównanie skrótów będzie znacznie szybsze.

CRC prawdopodobnie nie jest właściwą drogą, ponieważ jest to po prostu mechanizm wykrywania błędów, a nie skrót. (lub słaby skrót z dużą ilością możliwych kolizji)

— Dave Rager
źródło

+1 Zgadzam się. O wiele bardziej prawdopodobne jest uszkodzenie dysku twardego w porównaniu z przypadkowym kolizją dobrej funkcji haszującej (CRC32 jest słaby - zgadzam się).

— Michał Šrajer

2

Aby być w 100% pewnym, że dwa pliki są identyczne, naprawdę trzeba sprawdzić bajty.

Dlaczego? Hash kolizje, dlatego! W zależności od algorytmu używanego do mieszania, kolizja może być mniej lub bardziej prawdopodobna, ale jest jednak możliwa. Wykonując następujące kroki:

Sprawdź rozmiary plików
Sprawdź typy MIME
Sprawdź skrót
Sprawdź kilka losowych przesunięć i porównaj bity

Daje ci bardzo wysoką gwarancję pewności, że oba pliki są takie same, jednak istnieje bardzo (bardzo) niewielka szansa, że masz kolizję. Wybór tego, jak daleko chcesz posunąć się w porównaniu, będzie podyktowany sytuacją.

Myślę, że jeśli wybierzesz dobry algorytm mieszający, 2. i 4. nie zapewnią żadnego rzeczywistego wzrostu „równej” jakości. Prawdopodobnie 1. jest potrzebny tylko w przypadku słabego skrótu.

— Michał Šrajer

1

-1 To nie ma sensu. Jeśli wybierzesz dobry algorytm mieszania, wszystkie pozostałe kroki są zbędne. 1. i 4. są już właściwie objęte tym, co robi skrót, a 2. to nonsens (większość systemów plików nie ma nawet pojęcia „typu MIME”, a nawet jeśli tak, to dodaje bardzo mało informacji).

— sleske,

@sleske Mówię, zamiast płaskiego mieszania pliku, co jest intensywną operacją, możesz wykonać pewne wstępne operacje, które nie są tak ciężkie.

Rozumiem, że tylko 1 i 3 mają sens. (1) oznaczy większość przypadków różnych plików, oszczędzając potrzebę obliczania wartości skrótu. Konflikt skrótu na tym samym pliku długości jest tak mało prawdopodobny, że nie warto się martwić.

— Michael Shaw

1

Jak powiedzieli inni, szybsze jest porównanie bajtów po bajcie, jeśli dwa pliki są w tym samym systemie. Jeśli próbujesz porównać kilka plików, dojdziesz do punktu, w którym haszowanie jest lepszą odpowiedzią, jeśli pliki są w spinningowym magazynie.

Hashowanie naprawdę świeci, gdy nie masz wszystkich dostępnych danych. Na przykład pliki znajdują się na różnych komputerach. Pozwala także zapisać wyniki obliczeń i odwołać się do nich później. (Czy ten raport jest taki sam jak stary? Kiedy tworzysz raport, zachowujesz jego skrót. Kiedy robisz następny, możesz po prostu porównać skróty. Nie tylko nie musisz czytać starego w sobie muszę nawet mieć dostępną jego kopię.)

— Loren Pechtel
źródło

0

Myślę, że powinieneś użyć dostarczonego narzędzia porównywania plików z systemem operacyjnym lub narzędzia porównywania plików (patrz: narzędzia porównywania plików wiki ) do porównywania zawartości PO sprawdzeniu właściwości pliku opisanych przez @Glenn Nelson.

Nie sądzę, że CRC jest w 100% dokładny i myślę, że jego dokładność maleje wraz z długością pliku. Nie sugeruję też, aby pisać od zera, ponieważ może to wymagać wielu testów.

— Bez szans
źródło

0

Czy trzeba czytać każdy bajt, aby sprawdzić, czy skopiowany plik jest identyczny z oryginałem? TAK, aby być w 100% pewnym

Czy trzeba czytać każdy bajt, aby sprawdzić, czy skopiowany plik NIE jest identyczny z oryginałem? NIE

Dlatego, aby szybko ustalić brak identyczności, najpierw sprawdź metadane, takie jak rozmiar pliku i jakakolwiek suma kontrolna / CRC lub MIME, które system / system plików / sklep może już utrzymywać . Ponieważ są one wstępnie obliczane przez ten system, nie płacisz tego kosztu w momencie porównania.

Jeśli ten test się powiedzie, nadal musisz porównywać każdy bajt osobno, jeśli chcesz być w 100% pewien, ALE UWAGA, że w nowoczesnych procesorach potokowych i przy użyciu wielu wątków i być może wielu procesorów / procesorów porównywanie dużych plików jest NAPRAWDĘ szybkie i wydajny, ponieważ proces jest wysoce równoległy. O wiele szybsze niż JAKIEKOLWIEK obliczenia matematyczne obejmujące każdy bajt (chociaż niektóre algorytmy są również możliwe do zrównoleglenia, ale być może nie tak łatwo lub tak dobrze). Dzieje się tak, ponieważ procesory przetwarzane potokowo mogą wykonywać operacje porównywania bloków pamięci w mikrokodzie, a nawet sprzętowo (naprawdę szybko), a podsystemy typu „dysk do pamięci” są wysoce zoptymalizowane pod kątem dostarczania ogromnych bloków plików do / z pamięci, wszystkie wykonywane równolegle i za pomocą sprzęt komputerowy. Jeśli twoja aplikacja robi takie rzeczy regularnie i jest to znane wąskie gardło wydajności, dobrze byłoby zaimplementować to w dobrze napisanym wielowątkowym kodzie, który korzysta z możliwości paralelizacji twojego systemu operacyjnego i sprzętu (być może użyj języka, który jest zaprojektowany dla to).

Tylko wtedy, gdy chcesz przetworzyć każdy plik raz i wykonać wiele porównań później (gdy pamiętasz [„pamięć podręczną”] podsumowany lub „skompresowany” [jak to określa JohnFX] wynik analizy), będzie to miało znaczącą korzyść, i nawet wtedy, aby udowodnić różnicę (prawdopodobnie); aby udowodnić identyczność, nadal musisz wykonać porównanie bajt po bajcie.

— użytkownik14517
źródło