§ Описание
Существуют различные варианты реализации CRC (Циклического Избыточного Кода), их просто огромное множество. Самым, пожалуй, популярным из них является CRC32 - и это число 32-х битное. С помощью него можно хешировать данные, и количество различных вариантов этих данных будет равно 232, почти 4 миллиарда различных хешей.Алгоритм расчета CRC состоит из 2 частей:
- Создается таблица размером 256, состоящая из 32 битных значений для каждого символа
- На основе входящего потока символов вычисляется конечное значение CRC
§ Инициализация таблицы символов
Для каждого символа создается собственный уникальный код в таблице. Сначала входящему значению присваивается код символа от 0 до 255 (байт).- Если в младшем байте значения кода 1 (единица), то тогда сдвинуть код вправо и применить XOR 0xEDB88320
- Если же там 0, то просто сдвинуть вправо
- Повторить процедуру 8 раз (по количеству входящих битов в исходный байт)
- Присвоить в таблице полученное значение

§ Расчет CRC
После успешного получения таблицы, теперь можно легко произвести расчет CRC32 для любой входящей строки. Это делается крайне элементарно:- 1. Сначала инициализируется переменная CRC всеми единицами (битами)
- 2. Для каждого нового символа делается XOR с предыдущим значением переменной CRC, и берется только нижние 8 бит, из ранее сгенерированной таблицы выбирается необходимое значение
- 3. Делается XOR над полученным значением и сдвинутым на 8 бит вправо предыдущим значением CRC
- 4. Повторяется 2 и 3 до тех пор, пока все символы не будут обработаны
- 5. После обработки все биты в результате должны быть инвертированы
§ Код на С++
Ниже приведен код из Википедии для расчета CRC32unsigned int CRC32(unsigned char *buf, unsigned long len) { unsigned long crc_table[256], crc; for (int i = 0; i < 256; i++) { crc = i; for (int j = 0; j < 8; j++) crc = (crc >> 1) ^ (crc & 1 ? 0xEDB88320UL : 0); crc_table[i] = crc; }; crc = 0xFFFFFFFFUL; while (len--) crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xFF]; return crc ^ 0xFFFFFFFFUL; }
9 мар, 2021
© 2007-2023 Все кони классно отмочены