Вводный курс или закидываем удочку: CRC (Cyclic Redundancy Checksum) - контрольная сумма (своеобразная "цифровая подпись") какого-либо потока данных. Различные алгоритмы конрольных сумм в основном используются для проверки целостности/коректности данных. Это достигается благодаря тому, что при использовании алгоритма к одному потоку данных, как результат формируется одна и та же контрольная сумма. Но если изменяется хотя бы один бит входного потока, контрольная сумма принимает другое значение.
Adler32 - алгоритм конрольной суммы (изобретен Марком Адлером), которой часто используется как "quick and dirty" версия алгоритма CRC32. Данный алгоритм намного быстрее и почти так же надежен.
Несмотря на простоту алгоритма, его результат обладает главным свойством контрольной суммы: при отличии входного потока хотя бы одним битом, котрольная сумма меняется.
unsigned long s1 = adler32 & 0xFFFF;
unsigned long s2 = (adler32 >> 16) & 0xFFFF;
while (input_len > 0)
{
int k = input_len < NMAX ? input_len : NMAX;
input_len -= k;
while (k >= 16)
{
s1 += *input++;
s2 += s1;
}
s1 %= BASE;
s2 %= BASE;
}
adler32 = (s2 << 16) | s1;
В данном алгоритме BASE является наибольшим простым числом меньше 65535, а NMAX - наибольшее n, удовлетворяющее следующее неравенство:
255n(n + 1) / 2 + (n + 1)(BASE - 1) <= 2^32 - 1
Перед началом вычисления контрольная сумма (adler32) инициализируется в 1.
Пример: abrakadabra - 1A2A045D; abrakadabrc - 1A2C045F.
Как видно из примера, данный алгоритм не дает такого различия контрольных сумм при замене одного бита входного потока, как CRC32. Но несмотря на это, alder32 остается приемлемым для многих задач (например, ZLIB).
Приглашаются все программеры для обсуждения написания/правки распаковщика/упаковщика прошивок.
- участник сейчас на форуме