Контрольная сумма файла

Ну, эм, crc32?

можно другой вопрос?

на какой хрен тебе хеши? нельзя получать ивенты от ведра/фс?

А хэши можно по AES вычислять?

http://ru.wikipedia.org/wiki/Кольцевой_хэш

Применяется в алгоритме поиска подстроки Рабина — Карпа, а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).

Пользуюсь md5 в таких случаях.

MD5 и SHA256 уже очень сильно нагружают машину, для утилиты бекапа слишком, её в идеале должно быть незаметно...

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

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

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

«Хорошая» хеш-функция отличается более-менее равномерным распределением вычисленных значений. Очевидно, что Adler-32 не удоволетворяет этому требованию для коротких данных (максимальное значение A для 128-байтного сообщения равняется 32640, которое ниже чем 65521 — число по которому берется операция модуля). Из-за этого недостатка разработчики протокола SCTP предпочли этому алгоритму CRC32, так как в сетевом протоколе необходимо хеширование коротких последовательностей байт. Точно как и для CRC32, для Adler-32 можно легко сконструировать коллизию, то есть для данного хеша найти другие исходные данные, имеющие то же значение функции.

Как-то уж слишком печально, хотя ТСа, вероятно, устроит.

http://www.openbsd.ru/docs/rsync.html

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

В большинстве редакторов кнопка «Сохранить» неактивна же, пока изменения не будут внесены. Хотя можно добавить пробел, стереть его и сохранить.

З.Ы. Если большинство файлов текстовые, может стоит приспособить для этого дела какой-нибудь Mercurial, например?

З.Ы. Если большинство файлов текстовые, может стоит приспособить для этого дела какой-нибудь Mercurial, например?

Нет, большинство файлов будут бинарные и всяких форматов, неэффективно обрабатываемых всякими гитами и меркуриалами.

Пишу небольшую утилитку для бекапов файлов.

Для начала: почему не использовать готовый rsync, tar -u или даже cp -u?

В общем, определять, что файл изменился, нужно по контрольной сумме.

Зачем по контрольной сумме? Можно же тупо сравнить файлы. И, кстати, быстрее, если только они не на одном физическом диске. Но если они на одном диске, то «бакап» будет уже не бакапом, т.к. если диск накроется, то накроется и сам файл и его бакап.

Вопрос: какой алгоритм использовать? MD5, SHA256?

Формально надёжнее тот, что длиннее. Т.е. из стандатных это sha512. Затем sha386, sha256, sha224, sha1 и md5.

большинство файлов будут бинарные и всяких форматов, неэффективно обрабатываемых всякими гитами и меркуриалами.

Вообще-то всякие гиты и меркуриалы вполне себе работают с бинарными файлами.

Итого: не морочь себе голову, используй то, что проще. Если так хочется именно контрольную сумму — бери её. Если под рукой есть готовая либа с sha512 — бери её. Если под рукой нет sha512, но есть md5 — бери её. Если можно ничего не писать, а просто заюзать готовый rsync/tar/cp — юзай их. :)

Я советую по времени изменения

Например, 10 серий «Звездных врат» по 900 метров каждая. Будем хеш считать?

man rsync

Можно исхитриться, ввести стратегии сравнения для типов файлов.
Например всё кино/музыку сравнивать по размеру, дате, имени и содержащейся внутри информации, такой как название, битрейт, кодек, разрешение и т.п. (уж явно быстрее чем считывать кучу серий по 900 метров, или кучу кино по много гиг). Ну и для контроля можно читать в нескольких разных местах небольшими блоками (а то можно нарваться на недокачанный файл допустим).

SHA1 и взять реализацию Торвальдса )

еще можно использовать Git )))

определять, что файл изменился, нужно по контрольной сумме

А по mtime не вариант, что ли? И make для резервирования использовать.

открыл посмотрел и нажал сохранить

И какой ненормальный редактор переписывает неизмененный файл?

Ты уверен, что машину грузит вычисление хеша а не считывание файла?

Ну это я для примера, я точно не уверен, как себя ведут редакторы.

И какой ненормальный редактор переписывает неизмененный файл?

Очень многие, если не все. Для компиляции порой нужно просто обновить дату изменения файла.

а можно вопрос? чем rdiff-backup не устроил?

Потому что нужен свой алгоритм. Ну или скажем так, я хочу свой алгоритм бекапа :)

Для компиляции порой нужно просто обновить дату изменения файла.

А не быстрей ли будет набрать touch file?

1. Сравниваем даты
2. Если находим файл с обновленной датой, сравниваем размеры
3. Если размер не изменился, считаем контрольную сумму
4. Если суммы/размеры отличаются →

ну, если только NIH или лабораторная. ☺

а так, если хочешь что бы было быстро, то

сверяешь ctime и размер, если сходится — то файл не менялся, идёш дальше; иначе если md5 разный, то бэкап, если одинатовый, то побайтовое сравнение, если сходится — то файл не менялся, идёш дальше; иначе бэкап.

как-то так, быстро и сердито. md5 забэкапеных файлов лучше хранить предрасчинанными.

PS: при таком подходе может уже и CRC32 хватить.

5. побайтовое сравнение, что бы исключить коллизии

Если файл здоровый, это будет долго.

… но железно ☺

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

или k.o. критерий — побайтовое сравнение только если файл меньше, скажим, килобайта, если больше, то доверяем md5.

А не быстрей ли будет набрать touch file?

А подумать? Нет, я подскажу: для сохранения файла нужно нажать Ctrl+S. Для «touch file» нужно открыть консоль или переключиться на нее, зайти в нужный каталог и там набрать touch <file>. И что быстрее?

Это если файл уже открыт. Кроме того, make-то все равно в консоли набираешь…

Кроме того, make-то все равно в консоли набираешь…

Я что, дурак? Я F7 в IDE нажимаю.

Я что, дурак?

Это риторический вопрос.

CRC32. Надежность 1 - 2^-32, считается быстро.