Необходимо ли читать каждый байт, чтобы проверить, идентичен ли скопированный файл оригиналу?

Недавно я узнал о программе под названием Total Commander. Это замена Windows Explorer и имеет свои собственные вещи для копирования файлов. Чтобы проверить, являются ли файлы идентичными, вместо вычисления CRC, он буквально проверяет каждый байт, по одному, как на оригинале, так и на копии.

Мой вопрос: это необходимо? Может ли CRC или любой другой подобный метод пойти не так? Стоит ли вам, как программисту, попытаться реализовать эту совершенную, но медленную систему или она слишком экстремальна?

Для вычисления CRC (или, лучше, sha1sums) для обоих файлов в любом случае требуется чтение каждого байта. Если вы проводите побайтовое сравнение, вы можете выйти, как только увидите несоответствие, и вам не нужно беспокоиться о двух разных файлах, которые имеют одинаковую контрольную сумму (хотя для sha1sum это маловероятно) , Поэтому, если вы выполняете сравнение локально, побайтовое сравнение будет, по крайней мере, таким же быстрым, как сравнение контрольной суммы (если вы все равно не вычислили контрольные суммы).

С другой стороны, сравнение контрольных сумм полезно, когда вы сравниваете файлы, которые находятся не на одном компьютере; контрольные суммы могут быть вычислены локально, и вам не нужно передавать весь контент по сети.

Гибридные подходы также возможны. Например, вы можете вычислять и сравнивать контрольные суммы для двух файлов по частям за раз, что позволяет избежать чтения целых файлов ( если они различаются), а также избежать передачи всего файла по сети. Протокол rsync делает что-то вроде этого.

Обратите внимание, что использование простого CRC дает вам хороший шанс столкновения, как упоминал Дейв Рэйджер в своем ответе. Используйте хотя бы sha1sum или даже что-то более новое. (Не пытайтесь придумать свой собственный алгоритм хэширования; люди, разработавшие sha1sum, знают об этом гораздо больше, чем кто-либо из нас.)

Что касается вероятности коллизии, если вы используете приличный хеш, такой как sha1sum, вам почти не придется об этом беспокоиться, если только кто-то намеренно и дорого не создает файлы, чьи sha1sums сталкиваются (генерация таких коллизий была невозможна, когда я впервые написал это , но прогресс налицо ). Цитирую Скотта Чакона "Pro Git" , раздел 6.1 :

Вот пример, чтобы дать вам представление о том, что потребуется, чтобы получить столкновение SHA-1. Если бы все 6,5 миллиарда людей на Земле программировали, и каждую секунду каждый из них создавал код, который был эквивалентен всей истории ядра Linux (1 миллион объектов Git), и помещал его в один огромный репозиторий Git, это заняло бы 5 лет, пока этот репозиторий содержал достаточно объектов, чтобы иметь 50% вероятности столкновения одного объекта SHA-1. Существует более высокая вероятность того, что каждый член вашей команды программистов будет атакован и убит волками в несвязанных инцидентах в одну и ту же ночь.

Резюме :

Побайтовое сравнение хорошо для локальных сравнений. sha1sum хорош для удаленного сравнения и не дает значительного шанса ложных срабатываний.

Вот еще один способ думать об этом.

Если нет возможности того, что два разных файла имеют одинаковый CRC, то по расширению это означает, что каждый файл может быть представлен уникальным CRC. Если бы CRC был меньше исходного файла, то он представлял бы форму сжатия без потерь. Если нет, то вы бы с таким же успехом сравнивали исходные файлы, поскольку сравнивали бы одинаковое количество байтов.

Теоретически, вы можете использовать сжатие без потерь с обеих сторон сравнения, чтобы уменьшить количество байтов, необходимых для сравнения, но это глупая задача, потому что вы тратите больше циклов и должны читать каждый байт обоих файлов, чтобы выполнить сжатие. , То есть, чтобы закодировать каждый байт (и его порядок) в схеме сжатия без потерь, вы должны сначала прочитать его и включить в алгоритм, верно? Игра закончена.

Вот аналогия:
если вам нужен способ быстро определить, являются ли два напечатанных документа идентичными, не сравнивая букву за буквой, вы можете сравнить количество букв в каждой строке документов. Если все совпадения совпадают, шансы существенно улучшаются, что документы идентичны, однако никто не станет утверждать, что вы могли быть уверены, что каждое письмо было одинаковым при использовании этого подхода.

Единственный идеальный способ проверить наличие идентичных файлов - это сравнение байтов. Другой способ получить справедливое приближение - вычислить хеш, такой как MD5, для файлов и сравнить их. Возможно, может быть коллизия хэшей, но не очень вероятно.

Я полагаю, что сравнение байтов для байтов будет быстрее, чем вычисление хэша для обоих файлов во время сравнения. Однако, если ваше приложение предварительно вычисляет хеш и сохраняет метаданные о ваших файлах, сравнение хешей будет значительно быстрее.

CRC - это, вероятно, не тот путь, поскольку это просто механизм обнаружения ошибок, а не хеш. (или плохой хэш с множеством возможных коллизий)

Чтобы быть на 100% уверенными, два файла идентичны, вам действительно нужно проверить байты.

Почему? Хэш столкновения, вот почему! В зависимости от алгоритма, используемого для хеширования, коллизия может быть более или менее вероятной, но, тем не менее, возможна. Следуя этим шагам:

1. Проверьте размеры файлов
2. Проверьте типы пантомимы
3. Проверьте хеш
4. Проверьте несколько случайных смещений и сравните биты

Это даст вам очень высокую уверенность в том, что два файла одинаковы, однако есть очень (очень) небольшой шанс, что у вас на руках столкновение. Выбор того, как далеко вы хотите пойти со своими сравнениями, будет продиктован ситуацией.

Как уже говорили другие, побайтное сравнение выполняется быстрее, если два файла находятся в одной системе. Если вы попытаетесь сравнить кучу файлов, вы достигнете точки, в которой хеширование является лучшим ответом, если файлы находятся на вращающейся памяти.

Хеширование действительно светит, когда у вас нет всех доступных данных. Например, файлы находятся на разных машинах. Также позволяет сохранить результаты расчетов и обратиться к ним позже. (Является ли этот отчет тем же самым, что и старый? Когда вы создаете отчет, сохраняете его хэш. Когда вы создаете следующий, вы можете просто сравнить хэши. Мало того, что вам не нужно читать старый у вас, даже не нужно иметь его копию.)

Я думаю, что вы должны использовать прилагаемую утилиту сравнения файлов с вашей операционной системой или использовать инструмент сравнения файлов (см. Wiki-инструменты сравнения файлов ) для сравнения содержимого ПОСЛЕ того, как вы проверили свойства файла, описанные @Glenn Nelson.

Я не думаю, что CRC является точным на 100%, и я думаю, что его точность уменьшается с длиной файла. Кроме того, я не предлагаю вам писать с нуля, так как это может потребовать много испытаний.

Необходимо ли читать каждый байт, чтобы проверить, идентичен ли скопированный файл оригиналу? ДА, чтобы быть уверенным на 100%

Необходимо ли читать каждый байт, чтобы убедиться, что скопированный файл НЕ идентичен оригиналу? НЕТ

Таким образом, чтобы быстро определить неидентичность, сначала проверьте метаданные, такие как размер файла и любую контрольную сумму / CRC или MIME-тип, который OS / file-system / store может уже поддерживать . Поскольку они предварительно рассчитываются этой системой, вы не оплачиваете эту стоимость во время сравнения.

Если этот тест пройден, вам все равно нужно сравнивать каждый байт отдельно, если вам нужно быть на 100% уверенным, НО ЗАМЕТЬ, что в современных конвейерных ЦП и с использованием нескольких потоков и, возможно, нескольких процессоров / ЦП, сравнение блоков больших файлов ДЕЙСТВИТЕЛЬНО быстро и эффективный, потому что процесс очень распараллелен, Намного быстрее, чем ЛЮБОЙ вид математических вычислений, включающий каждый байт (хотя некоторые алгоритмы, возможно, также распараллеливаются, но, возможно, не так легко или так хорошо). Это связано с тем, что конвейерные процессоры могут выполнять операции сравнения блоков памяти в микрокоде или даже в аппаратном (очень быстром) и подсистеме «диск-в-память» высоко оптимизированы для доставки огромных блоков файлов в / из памяти, причем все это выполняется параллельно и с аппаратное обеспечение. Если ваше приложение делает подобные вещи регулярно, и это является известным узким местом в производительности, было бы разумно реализовать это в хорошо написанном многопоточном коде, использующем преимущества средств параллелизации вашей ОС и оборудования (возможно, используйте язык, предназначенный для это).

Только если вы захотите обработать каждый файл один раз, а потом проведете несколько сравнений (где вы помните [«кешировать») обобщенный или «сжатый» [как выразился JohnFX] результат), будет существенное преимущество для этого, и даже тогда, только чтобы доказать разницу (вероятно); чтобы доказать идентичность, вам все равно нужно сделать побайтовое сравнение.