Я ищу алгоритм контрольной суммы, где для большого блока данных контрольная сумма равна сумме контрольных сумм из всех меньших блоков компонентов. Большинство из того, что я нашел, это RFCs 1624/1141, которые предоставляют эту функциональность. Есть ли у кого-нибудь опыт работы с этими методами контрольной суммы или аналогичный?Дополнительные контрольные суммы
Я использовал только контрольные суммы Adler/Fletcher, которые работают, как вы описываете.
Существует хорошее сравнение реализаций хеша/контрольной суммы crypto ++ here.
Я пытался играть с Адлером, и я не могу получить ожидаемый результат, вы имеете в виду: 'adler ('wiki') + adler ('pedia')' должен давать тот же дайджест, что и 'adler ('wikipedia')', или я что-то упускаю? –
Чтобы ответить на вопрос о щедрое задание Кларк Кент, для целей идентификации файлов вы, вероятно, хотите использовать криптографическую хеш-функцию, которая пытается гарантировать, что любые два заданных файла имеют чрезвычайно низкую вероятность создания одного и того же значения, в отличие от контрольной суммы, которая обычно используется только для обнаружения ошибок и может обеспечивать одинаковое значение для двух очень разных файлов.
Многие криптографические хэш-функции, такие, как MD5 и SHA-1, используют Merkle–Damgård construction, в котором есть вычисление для сжатия блока данных в фиксированный размер, а затем совмещают, что со значением фиксированного размера от предыдущего блока (или вектором инициализации для первого блока). Таким образом, они могут работать в потоковом режиме, постепенно вычисляя по мере их продвижения.
Если это просто вопрос быстрого объединения контрольных сумм меньших блоков, чтобы добраться до контрольных сумм большего сообщения (не обязательно путем простого суммирования), вы можете сделать это с помощью CRC-типа (или аналогичного) алгоритма.
КПР-32 алгоритм так же просто, как это:
uint32_t update(uint32_t state, unsigned bit)
{
if (((state >> 31)^bit) & 1) state = (state << 1)^0x04C11DB7;
else state = (state << 1);
return state;
}
Математически, состояние представляет собой многочлен над полем GF2, что всегда сводится по модулю полинома генератора. Учитывая новое битое b старого государство превращается в новое состояние, как этот
state --> (state * x^1 + b * x^32) mod G
где G является порождающим полиномом и добавление делается в GF2 (XOR). Эта контрольная сумма в смысле линейный, что вы можете написать сообщение M в виде суммы (XOR) сообщений A, B, C, ... как этот
10110010 00000000 00000000 = A = a 00000000 00000000
00000000 10010001 00000000 = B = 00000000 b 00000000
00000000 00000000 11000101 = C = 00000000 00000000 c
-------------------------------------------------------------
= 10110010 10010001 11000101 = M = a b c
со следующими свойствами
M = A + B + C
checksum(M) = checksum(A) + checksum(B) + checksum(C)
Опять же, я имею в виду + в GF2, который вы можете реализовать с помощью двоичного XOR.
Наконец, можно вычислить checksum(B) на основе checksum(b) и позиции субблока b относительно B. Простая часть - это ведущие нули. Ведущие нули вообще не влияют на контрольную сумму. Таким образом, checksum(0000xxxx) - это то же самое, что и у checksum(xxxx). Если вы хотите вычислить контрольную сумму нулевого запаса (вправо -> завершающие нули) с учетом контрольной суммы непроложенного сообщения, это немного сложнее.Но не так уж сложно:
zero_pad(old_check_sum, number_of_zeros)
:= (old_check_sum * x^{number_of_zeros} ) mod G
= (old_check_sum * (x^{number_of_zeros} mod G)) mod G
Таким образом, получение контрольной суммы нулей сообщения является лишь вопросом умножения «контрольной суммой Полинома» из НЕДОПОЛНЯЮЩИХ сообщений с каким-либо другими полиномиальными (x^{number_of_zeros} mod G), что зависит только от на количество нулей, которые вы хотите добавить. Вы можете прекомпотировать это в таблице или использовать алгоритм с квадратным и размножающимся, чтобы быстро вычислить эту мощность.
Предложенное чтение: Painless Guide to CRC Error Detection Algorithms
Должен ли он конкретно будет равна арифметической сумме контрольных сумм меньших блоков, или вы просто больше вообще хотят быть в состоянии вычислить контрольную сумму большого блока из контрольные суммы меньших блоков? –
Мне кажется, проблема контрольных сумм сегодня считается «в основном решена» и часто отклоняется как «привязана к IO» и, следовательно, не интересна с точки зрения алгоритмической производительности. Но ОК, «IO bound» это, что мы можем сделать с IO? Ну, если бы мы могли вычислять хэши, а IO все еще горячо в кэшах, это было бы хорошо. –
@Amigable Clark Kent Возможно, было бы лучше открыть новый вопрос, с вашими точными требованиями, вместо того, чтобы откидываться от существующего ответа. Вы просто ищете контрольную сумму для обнаружения ошибок? Вы ищете криптографическую хэш-функцию? Требуется ли, чтобы контрольная сумма состояла из некоторой комбинации контрольных сумм каждого блока, как задает первоначальный вопрос, или требуется только, чтобы вы могли инкрементно вычислить контрольную сумму в потоке данных и дать контрольную сумму для всего потока один раз все готово? –