§ Описание

Существуют различные варианты реализации CRC (Циклического Избыточного Кода), их просто огромное множество. Самым, пожалуй, популярным из них является CRC32 - и это число 32-х битное. С помощью него можно хешировать данные, и количество различных вариантов этих данных будет равно 2³², почти 4 миллиарда различных хешей.
Алгоритм расчета CRC состоит из 2 частей:

• Создается таблица размером 256, состоящая из 32 битных значений для каждого символа
• На основе входящего потока символов вычисляется конечное значение CRC

§ Инициализация таблицы символов

Для каждого символа создается собственный уникальный код в таблице. Сначала входящему значению присваивается код символа от 0 до 255 (байт).

• Если в младшем байте значения кода 1 (единица), то тогда сдвинуть код вправо и применить XOR 0xEDB88320
• Если же там 0, то просто сдвинуть вправо
• Повторить процедуру 8 раз (по количеству входящих битов в исходный байт)
• Присвоить в таблице полученное значение

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

§ Расчет CRC

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

• 1. Сначала инициализируется переменная CRC всеми единицами (битами)
• 2. Для каждого нового символа делается XOR с предыдущим значением переменной CRC, и берется только нижние 8 бит, из ранее сгенерированной таблицы выбирается необходимое значение
• 3. Делается XOR над полученным значением и сдвинутым на 8 бит вправо предыдущим значением CRC
• 4. Повторяется 2 и 3 до тех пор, пока все символы не будут обработаны
• 5. После обработки все биты в результате должны быть инвертированы

Все, получается итоговое значение CRC32. Все очень просто. Главное запомнить, как это работает.

§ Код на С++

Ниже приведен код из Википедии для расчета CRC32

unsigned 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;
}