Реализации алгоритмов/Циклический избыточный код

Шаблон:Wikipedia Примеры программ для вычисления CRC. Некоторые из этих алгоритмов заимствованы у Ross Williams.

CRC-16

CRC-CCITT отличается от классического CRC-16, так как использует другой полином и порядок данных. Шаблон:Hider hiding

CRC-32

Алгоритм CRC32 основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7).

Программная реализация на C

Получили распространение несколько методов программного расчета CRC:

• оригинальный алгоритм с побитовым вводом данных:

• Конечно, этот алгоритм может быть записан короче:

• Псевдотабличный с побайтовым вводом данных и генерацией требуемого элемента таблицы непосредственно в цикле расчета:

По объему кода псевдотабличный метод почти не отличается от прямого расчета, но может быть чуть быстрее, поэтому практически вытеснил оригинальный метод.

• Табличный с побайтовым вводом данных и заранее созданной таблицей:

Таблица может быть задана константой (создаваться до компиляции) или генерироваться непосредственно перед выполнением расчета. Табличный метод основан на том что одинаковые последовательности входных данных дают одинаковые изменения регистра сдвига, поэтому за один цикл можно рассчитать больше чем один бит входных данных. Табличный метод требует значительных затрат памяти под таблицы. Размер элемента таблицы равен размеру выбранного полинома. Длина таблицы равна $2^D$, где D - выбранная длина входных данных в битах для одного цикла расчета (например, для однобайтового варианта это 8 бит). Например, для 32-битной CRC с побайтовым расчетом длина таблицы будет 256 слов по 32 бита, т.е. 1024 байта. Алгоритм генерации таблицы: