crc32
Для себя, одна мелкая ссылка.
Про crc написано много разных вещей.
Прежде всего отличный документ, где объясняется сама математика процесса.
Потом 'Алгоритмические трюки для программистов (2ed)'. Очень кратко упомянуто, как эту вещи ускорить, когда шагаешь словами по 4 байта. Ещё помниться видел эту штуку в ядре у Linux, там где встроен генератор энтропии. Там был какой-то замечательный механизм который оценивал энтропию данных, в нём была таблица, которая была точной копий таблицы от crc32, но в разреженном виде. Как это работает, я так и не понял, но на данный момент догадываюсь.
В копилку ссылка, как сделать crc32 ещё и ещё быстрее. А так же как сделать таблицу компактнее. Всё на свой вкус:
http://create.stephan-brumme.com/crc32/
Ещё я как-то задался вопросом, а есть ли в crc32 колизии. В md5 например точно есть. В crc оказалось что нету. Если подавать на вход 32 бита, и брать 32 бита на выходе, колизий нету. Каждому числу на входе соотв. своё уникальное число на выходе. Т.е. функция как-бы обратима. Единственная тонкость, в crc16, crc32 это не всегда так, очень многие предлагаемые там полиномы, которые подаются как качественные и исползуются во всяких программах/алгоритмах, всё таки дают колизии, притом иногда до 50%. Может быть многочлен в них попросту не примитивен, вот это я как-то поглядеть не успел.
Итак для crc32 полиномы edb88320, db710641, 82f63b78, eb31d82e - не имеют колизии, 32 битное число в можго прогнать них по кругу, не будет не одного повтора. Хотя этого тоже не достаточно для работы, надо ещё изучать разброс значений.
Полиномы 4c11db7 (pkzip), 5ec76f1, 741b8cd7 (koopman), 1edc6f41 - дают невероятное число колизий и для нормальной работы, для той же конторльной суммы, просто неприменимы.
Проверить на самом деле надо все изветные на практике полиномы или вообще все числа, но это, когда будет время.
p.s. вычислил замечательные полиномчики: ccccccd4,e666666b,999999aa - они подходят для любой работы. Казалось такая простая вещь - контрольная сумма. А уже хочется целую книгу написать.
Про crc написано много разных вещей.
Прежде всего отличный документ, где объясняется сама математика процесса.
Потом 'Алгоритмические трюки для программистов (2ed)'. Очень кратко упомянуто, как эту вещи ускорить, когда шагаешь словами по 4 байта. Ещё помниться видел эту штуку в ядре у Linux, там где встроен генератор энтропии. Там был какой-то замечательный механизм который оценивал энтропию данных, в нём была таблица, которая была точной копий таблицы от crc32, но в разреженном виде. Как это работает, я так и не понял, но на данный момент догадываюсь.
В копилку ссылка, как сделать crc32 ещё и ещё быстрее. А так же как сделать таблицу компактнее. Всё на свой вкус:
http://create.stephan-brumme.com/crc32/
Ещё я как-то задался вопросом, а есть ли в crc32 колизии. В md5 например точно есть. В crc оказалось что нету. Если подавать на вход 32 бита, и брать 32 бита на выходе, колизий нету. Каждому числу на входе соотв. своё уникальное число на выходе. Т.е. функция как-бы обратима. Единственная тонкость, в crc16, crc32 это не всегда так, очень многие предлагаемые там полиномы, которые подаются как качественные и исползуются во всяких программах/алгоритмах, всё таки дают колизии, притом иногда до 50%. Может быть многочлен в них попросту не примитивен, вот это я как-то поглядеть не успел.
Итак для crc32 полиномы edb88320, db710641, 82f63b78, eb31d82e - не имеют колизии, 32 битное число в можго прогнать них по кругу, не будет не одного повтора. Хотя этого тоже не достаточно для работы, надо ещё изучать разброс значений.
Полиномы 4c11db7 (pkzip), 5ec76f1, 741b8cd7 (koopman), 1edc6f41 - дают невероятное число колизий и для нормальной работы, для той же конторльной суммы, просто неприменимы.
Проверить на самом деле надо все изветные на практике полиномы или вообще все числа, но это, когда будет время.
p.s. вычислил замечательные полиномчики: ccccccd4,e666666b,999999aa - они подходят для любой работы. Казалось такая простая вещь - контрольная сумма. А уже хочется целую книгу написать.