Алгоритм CRC

Я бы хотел расскажать об интересном алгоритме CRC ( сyclic redundancy check ). С помощью этого алгоритма можно не только использовать для проверки целострости данных, но и для других полезных целей. Приведу простой вариант алгорима:

uint64_t crc_calc_slow( uint64_t poly, uint64_t crc, const void * buffer, size_t size )
{
    while( size-- ) {
        crc ^= * ( uint8_t * ) buffer++;
        int bit = 8;
        while( bit-- ) crc = crc & 1 ? ( crc >> 1 ) ^ poly : crc >> 1;
    }
    return crc;
}

где:
    poly - полином
    crc - начальное либо предыдущее состояние crc
    buffer - указатель на блок в памяти
    size - размер блока

это простой и медленно работающий вариант алгоритма т.к. для каждого байта ему нужно сделать 8 итераций, потому его на практике используют табличный вариант который обрабатывает 1 байт за итерацию, по моим тестам работаетающий где то в 10 раз быстрее. Табличный вариант можете найти в интернете или в моем пакете http://sourceforge.net/projects/csnippets

CRC файла можно вычислить сразу для всего файла или последовательно порциями указав для функции предыдыщий вычисленный CRC;

вот пример:

вычислим CRC для всего сообщения:
crc_calc_slow( POLY, 0, "MESSAGE", strlen( "MESSAGE" ) ) ==
0x1494111b;

а вот для двух частей "МЕSS" и "AGE"
crc_calc_slow( POLY, 0, "MESS", strlen( "MESS" ) ) == 0x7cdbc112
crc_calc_slow( POLY, 0x7cdbc112, "AGE", strlen( "AGE" ) ) ==
0x1494111b

т.е. сначала мы вычиляем CRC части сообщения "MESS" с начальным значением 0 и получим 0x7cdbc112, а затем вычислим CRC для другой части сообщения "AGE" с начальным значение 0x7cdbc112 и получим значение 0x1494111b.