LINUX.ORG.RU
ФорумTalks

посоветуйте быстрый хэш

 


1

2

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

★★★★★

ты только учти что если инфа посыпется то из хеша ты ее не восстановишь

Deleted ()
Ответ на: комментарий от Deleted

да ему походу очередной сервер картинок надо написать, вот он так и вуалирует вопросы

Karapuz ★★★★★ ()

также реквестируется консольная утилита, которая наиболее быстро с этим справляется. raid не предлагать.

man cksum

ну или сам пиши для CRC16 или вообще простой суммы по модулю скажем 2^32. Хотя CRC32 работает обычно быстрее чтения файлов, потому что cat >/dev/null, что cksum - без разницы по скорости.

drBatty ★★ ()
Ответ на: комментарий от Karapuz

Решил запилить имэджборду и воскресить двач? Не одобряю.

По теме: MD5 на openCL.

kranky ★★★★★ ()
Ответ на: комментарий от Deleted

ты только учти что если инфа посыпется то из хеша ты ее не восстановишь

а это надо «хеши» Рида-Соломона тогда считать. man par2

drBatty ★★ ()

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

Legioner ★★★★★ ()

Поддерживаю предыдущего оратора, в диск упрёшься.

melkor217 ★★★★★ ()

Хэш и контрольная сумма не одно и то же.

Tark ★★ ()
Ответ на: комментарий от Deleted

ты только учти что если инфа посыпется то из хеша ты ее не восстановишь

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

http://www.strchr.com/hash_functions

кажется то что надо, спасибо

jcd ★★★★★ ()
Ответ на: комментарий от Karapuz

да ему походу очередной сервер картинок надо написать, вот он так и вуалирует вопросы

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

jcd ★★★★★ ()
Ответ на: комментарий от Legioner

скорость будет ограничена скоростью чтения с диска

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

jcd ★★★★★ ()
Ответ на: комментарий от jcd

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

void ()
Ответ на: комментарий от void

попробуй прочитать сообщение вдумчиво?

jcd ★★★★★ ()

man hashdeep
...
-c <alg1>[,<alg2>...]
Computation mode. Compute hashes of FILES using the algorithms specified. Legal values are md5, sha1, sha256, tiger, and whirlpool.
...
-jnn Controls multi-threading
...
-r Enables recursive mode. All subdirectories are traversed
...

zolden ★★★★★ ()
Ответ на: комментарий от jcd

прочитал вдумчиво - на ум пришло только то, что повелительное наклонение и вопросительный знак как-то не очень сочетаются.

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

Excellent performance - measured on an Intel Core 2 Duo @ 2.4 ghz

    OneAtATime - 354.163715 mb/sec
    FNV - 443.668038 mb/sec
    SuperFastHash - 985.335173 mb/sec
    lookup3 - 988.080652 mb/sec
    MurmurHash 1.0 - 1363.293480 mb/sec
    MurmurHash 2.0 - 2056.885653 mb/sec

https://sites.google.com/site/murmurhash/

void ()
Ответ на: комментарий от void

неплохо... попробую, спасибо

я имел ввиду ситуацию, когда алгоритм хэширования все еще работает работает со старыми данными из кэша файловой системы, в то время как уже загружены новые

jcd ★★★★★ ()
Ответ на: комментарий от zolden

man hashdeep

мне нужно не только считать, но и записывать и проверять

jcd ★★★★★ ()

Тебе не хэширование нужно, а система контроля версия для бинарных данных — http://code.google.com/p/boar/

Она держит контрольные суммы на все хранимые данные и все собственные метаданные. Так что любое нарушение целостности будет сразу обнаружено.

geekless ★★ ()
Ответ на: комментарий от jcd

Это ты мне так тонко намекаешь что готовые решения тебе неинтересны, раз в голове почти созрел свой велосипед?

-a Audit mode. Each input file is compared against the set of knowns

-k Load a file of known hashes

% hashdeep *.bin > test.hash
% hashdeep -av -k test.hash *.bin
hashdeep: Audit passed
          Files matched: 2
Files partially matched: 0
            Files moved: 0
        New files found: 0
  Known files not found: 0
zolden ★★★★★ ()

Есть ещё программа cfv, sfv-суммы считаются очень быстро, надёжность приемлемая. А тип данных как бы не имеет значения.

Homura_Akemi ()
Ответ на: комментарий от zolden

Мне лень читать ман, hashdeep умеет обновлять существующий список хэшей, добавляя только те файлы, которых там нет?

Homura_Akemi ()
Ответ на: комментарий от Homura_Akemi

такой опции в явном виде нет, но так как можно строить хэши на основе списков файлов, то можно предварительно сам список подготовить

zolden ★★★★★ ()
Ответ на: комментарий от zolden

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

Homura_Akemi ()
Ответ на: комментарий от drakmail

Не, вроде разные алгоритмы.

CityHash нацелен на скорость работы с короткими строками и в этом, похоже, даже быстрее MurmurHash:

CityHash64 v1.0.3 7ns for 1 byte, or 6ns for 8 bytes, or 9ns for 64 bytes
Murmur2 (64-bit)  6ns for 1 byte, or 6ns for 8 bytes, or 15ns for 64 bytes
Murmur3F          14ns for 1 byte, or 15ns for 8 bytes, or 23ns for 64 bytes

Бенчмарк взят из readme

http://code.google.com/p/cityhash/

void ()
Ответ на: комментарий от vasily_pupkin

crc32

теряет эффективность при 12к+ данных и вообще не для этого, нужно использовать md5/sha1/sha256

frame ★★★ ()
Ответ на: комментарий от frame

теряет эффективность при 12к+ данных

В каком смысле «эффективность»? Реквестирую линк с подробностями.

Manhunt ★★★★★ ()
Ответ на: комментарий от Manhunt

В каком смысле «эффективность»? Реквестирую линк с подробностями.

http://en.wikipedia.org/wiki/Jumbo_frame
http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/ecc.html
http://stackoverflow.com/questions/3800788/what-is-the-hamming-distance-and-h...

frame ★★★ ()
Последнее исправление: frame (всего исправлений: 1)
Ответ на: комментарий от frame

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

Manhunt ★★★★★ ()
Ответ на: комментарий от Manhunt

Очень расплывчато

Это фундамент

А другие хэш-функции

Ещё раз: crc32 это не хеш, а контроль чётности, т.е. эффективность его ниже любой более-менее приличной хеш-функции by design - с тем же успехом можно просто все байты просуммировать и назвать это «супер-быстро и достоверно» (уже молчу про размер подписи)

frame ★★★ ()
Ответ на: комментарий от frame

Ещё раз: crc32 это не хеш, а контроль чётности

Формально, crc является хэш-функцией.

эффективность его ниже любой более-менее приличной хеш-функции by design

Ещё раз: что ты называешь эффективностью хэш-функции? Я так и не понял этого из твоих ссылок.

Manhunt ★★★★★ ()
Ответ на: комментарий от Manhunt

эффективностью хэш-функции?

Соотношение скорости к количеству коллизий.

devl547 ★★★★★ ()
Ответ на: комментарий от devl547

Соотношение скорости к количеству коллизий.

Хотелось бы узнать мнение frame

Manhunt ★★★★★ ()
Ответ на: комментарий от Kindly_Cat

А можно просто не использовать и оставить извращения Изе.

devl547 ★★★★★ ()
Ответ на: комментарий от Manhunt

Формально, crc является хэш-функцией.

Да, но фактически это лишь контроль чётности

Ещё раз: что ты называешь эффективностью хэш-функции? Я так и не понял этого из твоих ссылок.

Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Что происходит при росте (значения) многочлена предлагаю подумать самостоятельно

frame ★★★ ()
Ответ на: комментарий от jcd

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

Chaser_Andrey ★★★★★ ()
Ответ на: комментарий от frame

Что происходит при росте (значения) многочлена предлагаю подумать самостоятельно

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

То есть значение многочлена ни на каком этапе не вычисляется и никакой роли не играет.

Пожалуйста, перестань говорить загадками и намеками, и дай явное определение: что ты называешь «эффективностью хэш-функции»? Почему у этой эффективности в случае crc наступает переломный момент при 12к входных данных (а не 1к и не 1200к)?

Manhunt ★★★★★ ()
Ответ на: комментарий от Manhunt

То есть значение многочлена ни на каком этапе не вычисляется и никакой роли не играет.

Играет значение модель (т.е. характер) преобразования, а не конкретные сложения-умножения

Почему у этой эффективности в случае crc наступает переломный момент при 12к входных данных (а не 1к и не 1200к)?

см. Hamming Distance

frame ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.