Циклический избыточный код

Эта статья — о коде. О методе мозгового штурма см. CRC-карта.

Циклический избыточный код (англ. Cyclic redundancy check, CRC^[1]) — алгоритм вычисления контрольной суммы, предназначенный для проверки целостности данных^[2]. CRC является практическим приложением помехоустойчивого кодирования, основанном на определенных математических свойствах циклического кода.

Введение

Основная статья: Циклические коды

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Понятие циклические коды достаточно широкое^[3]. В англоязычной литературе CRC расшифровывается двояко в зависимости от контекста: Cyclic Redundancy Code или Cyclic Redundancy Check^[4]. Под первой расшифровкой понимают математический феномен циклических кодов, под второй — конкретное применение этого феномена как хэш-функции.

Помехоустойчивое кодирование

Основная статья: Обнаружение и исправление ошибок

Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

Но далеко не везде от кода требуется коррекция ошибок. Многие современные каналы связи обладают приемлемыми характеристиками, и зачастую достаточно лишь проверить, успешно ли прошла передача или возникли какие-нибудь сложности; структура же ошибок и конкретные позиции неверных символов совершенно не интересуют принимающую сторону. И в этих условиях очень удачным решением оказались алгоритмы, использующие контрольные суммы. CRC как нельзя лучше подходит для подобных задач: невысокие затраты ресурсов, простота реализации и уже сформированный математический аппарат из теории линейных циклических кодов обеспечили ей огромную популярность.

Контрольная сумма

Основная статья: Контрольная сумма

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

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

Математическое описание

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем $GF(2^N)$. Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Каждой конечной последовательности битов $a_0, a_1, \dots, a_{N-1}$ взаимно однозначно сопоставляется двоичный полином $\textstyle\sum_{n=0}^{N-1} a_n x^n$, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

$P(x) = 1\cdot x^6 + 0\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x^1 + 0\cdot x^0 = x^6 + x^4 + x^3 + x^1$

Количество различных многочленов степени меньшей $N$ равно $2^N$, что совпадает с числом всех двоичных последовательностей длины $N$ .

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

$R(x) = P(x)\cdot x^N\, \bmod\, G(x)$

где

$R(x)$ — многочлен, представляющий значение CRC.

$P(x)$ — многочлен, коэффициенты которого представляют входные данные.

$G(x)$ — порождающий многочлен.

$N$ — степень порождающего многочлена.

Умножение $x^N$ осуществляется приписыванием $N$ нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2^N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.

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

Вычисление CRC

Параметры алгоритма

Схема формирования контрольной суммы CRC-8. Порождающий многочлен g(x) = x8+x5+x4+1

Говоря о формировании контрольной суммы CRC, в первую очередь нужно упомянуть о полиноме-генераторе. Существует огромное множество многочленов, участвующих в формировании cyclic reduntancy code; многие из них указаны в конце статьи.

Другим параметром конкретного алгоритма вычисления контрольной суммы является размер слова, или суммарное количество регистров — информационных ячеек, используемых для вычисления численного значения хэша. При этом обязательно учитывается то, что размер слова и степень образующего контрольную сумму полинома совпадают. На практике более всего распространены 8, 16 и 32 — битовые слова, что является следствием особенностей архитектуры современной вычислительной техники.

И последний параметр, важный при описании определенной методики — начальные состояния регистров (стартовое слово). Это последняя из трех значимых характеристик; зная их в совокупности, мы можем восстановить алгоритм вычисления CRC, если данная модификация методики не имеет специфических особенностей, таких, как обратный порядок обработки битов.

Описание процедуры

Реализация CRC на логических элементах

Из файла берется первое слово — это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно, если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается — его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

Наиболее используемые и стандартизованные полиномы

В то время, как циклические избыточные коды являются частью стандартов, у этого термина не существует общепринятого определения — трактовки различных авторов нередко противоречат друг другу.^[1][5]

Этот парадокс касается и выбора многочлена-генератора: зачастую стандартизованные полиномы не являются самыми эффективными в плане статистических свойств соответствующего им check reduntancy code .

При этом многие широко используемые полиномы не являются наиболее эффективными из всех возможных. В 1993—2004 годах группа ученых занималась исследованием порождающих многочленов разрядности до 16,^[1] 24 и 32 бит,^[6][7] и нашла полиномы, дающие лучшую, нежели стандартизированные многочлены, производительность в смысле кодового расстояния.^[7] Один из результатов этого исследования уже нашёл своё применение в протоколе iSCSI.

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI; также этот многочлен является генератором кода Хемминга^[8]. Использование другого полинома — CRC-32C — позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью.^[7] К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке.

Ниже в таблице перечислены наиболее распространенные многочлены — генераторы CRC.На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В проприетарных реализациях CRC для усложнения анализа кода применяют ненулевые начальные значения регистров.

Название	Полином	Представления:[9] нормальное / реверсированное / реверсированное от обратного
CRC-1	$x + 1$ (используется в аппаратном контроле ошибок; также известен как бит чётности)	0x1 / 0x1 / 0x1
CRC-4-ITU	$x^4 + x + 1$ (ITU G.704[10])	0x3 / 0xC / 0x9
CRC-5-EPC	$x^5 + x^3 + 1$ (Gen 2 RFID[11])	0x09 / 0x12 / 0x14
CRC-5-ITU	$x^5 + x^4 + x^2 + 1$ (ITU G.704[12])	0x15 / 0x15 / 0x1A
CRC-5-USB	$x^5 + x^2 + 1$ (USB token packets)	0x05 / 0x14 / 0x12
CRC-6-ITU	$x^6 + x + 1$ (ITU G.704[13])	0x03 / 0x30 / 0x21
CRC-7	$x^7 + x^3 + 1$ (системы телекоммуникации, ITU-T G.707[14], ITU-T G.832[15], MMC, SD)	0x09 / 0x48 / 0x44
CRC-8-CCITT	$x^8 + x^2 + x + 1$ (ATM HEC), ISDN Header Error Control and Cell Delineation ITU-T I.432.1 (02/99)	0x07 / 0xE0 / 0x83
CRC-8-Dallas/Maxim	$x^8 + x^5 + x^4 + 1$ (1-Wire bus)	0x31 / 0x8C / 0x98
CRC-8	$x^8 + x^7 + x^6 + x^4 + x^2 + 1$ (ETSI EN 302 307[16], 5.1.4)	0xD5 / 0xAB / 0xEA[1]
CRC-8-SAE J1850	$x^8 + x^4 + x^3 + x^2 + 1$	0x1D / 0xB8 / 0x8E
CRC-10	$x^{10} + x^9 + x^5 + x^4 + x + 1$	0x233 / 0x331 / 0x319
CRC-11	$x^{11} + x^9 + x^8 + x^7 + x^2 + 1$ (FlexRay[17])	0x385 / 0x50E / 0x5C2
CRC-12	$x^{12} + x^{11} + x^3 + x^2 + x + 1$ (системы телекоммуникации[18][19])	0x80F / 0xF01 / 0xC07
CRC-15-CAN	$x^{15} + x^{14} + x^{10} + x^8 + x^7 + x^4 + x^3 + 1$	0x4599 / 0x4CD1 / 0x62CC
CRC-16-IBM	$x^{16} + x^{15} + x^2 + 1$ (Bisync, Modbus, USB, ANSI X3.28[20], многие другие; также известен как CRC-16 и CRC-16-ANSI)	0x8005 / 0xA001 / 0xC002
CRC-16-CCITT	$x^{16} + x^{12} + x^5 + 1$ (X.25, HDLC, XMODEM, Bluetooth, SD и др.)	0x1021 / 0x8408 / 0x8810[1]
CRC-16-T10-DIF	$x^{16} + x^{15} + x^{11} + x^{9} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ (SCSI DIF)	0x8BB7[21] / 0xEDD1 / 0xC5DB
CRC-16-DNP	$x^{16} + x^{13} + x^{12} + x^{11} + x^{10} + x^8 + x^6 + x^5 + x^2 + 1$ (DNP, IEC 870, M-Bus)	0x3D65 / 0xA6BC / 0x9EB2
CRC-16-Fletcher	Not a CRC; see Fletcher's checksum	Used in Adler-32 A & B CRCs
CRC-24	$x^{24} + x^{22} + x^{20} + x^{19} + x^{18} + x^{16} + x^{14} + x^{13} + x^{11} + x^{10} + x^8 + x^7 + x^6 + x^3 + x + 1$ (FlexRay[17])	0x5D6DCB / 0xD3B6BA / 0xAEB6E5
CRC-24-Radix-64	$x^{24} + x^{23} + x^{18} + x^{17} + x^{14} + x^{11} + x^{10} + x^7 + x^6 + x^5 + x^4 + x^3 + x + 1$ (OpenPGP)	0x864CFB / 0xDF3261 / 0xC3267D
CRC-30	$x^{30} + x^{29} + x^{21} + x^{20} + x^{15} + x^{13} + x^{12} + x^{11} + x^{8} + x^{7} + x^{6} + x^{2} + x + 1$ (CDMA)	0x2030B9C7 / 0x38E74301 / 0x30185CE3
CRC-32-Adler	Not a CRC; see Adler-32	See Adler-32
CRC-32-IEEE 802.3	$x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ (V.42, MPEG-2, PNG[22], POSIX cksum)	0x04C11DB7 / 0xEDB88320 / 0x82608EDB[7]
CRC-32C (Castagnoli)	$x^{32} + x^{28} + x^{27} + x^{26} + x^{25} + x^{23} + x^{22} + x^{20} + x^{19} + x^{18} + x^{14} + x^{13} + x^{11} + x^{10} + x^9 + x^8 + x^6 + 1$ (iSCSI, G.hn payload)	0x1EDC6F41 / 0x82F63B78 / 0x8F6E37A0[7]
CRC-32K (Koopman)	$x^{32} + x^{30} + x^{29} + x^{28} + x^{26} + x^{20} + x^{19} + x^{17} + x^{16} + x^{15} + x^{11} + x^{10} + x^{7} + x^{6} + x^{4} + x^{2} + x + 1$	0x741B8CD7 / 0xEB31D82E / 0xBA0DC66B[7]
CRC-32Q	$x^{32} + x^{31} + x^{24} + x^{22} + x^{16} + x^{14} + x^{8} + x^{7} + x^{5} + x^{3} + x + 1$ (aviation; AIXM[23])	0x814141AB / 0xD5828281 / 0xC0A0A0D5
CRC-64-ISO	$x^{64} + x^4 + x^3 + x + 1$ (HDLC — ISO 3309)	0x000000000000001B / 0xD800000000000000 / 0x800000000000000D
CRC-64-ECMA-182	$x^{64} + x^{62} + x^{57} + x^{55} + x^{54} + x^{53} + x^{52} + x^{47} + x^{46} + x^{45} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + x^{33} +$ $x^{32} + x^{31} + x^{29} + x^{27} + x^{24} + x^{23} + x^{22} + x^{21} + x^{19} + x^{17} + x^{13} + x^{12} + x^{10} + x^9 + x^7 + x^4 + x + 1$[24]	0x42F0E1EBA9EA3693 / 0xC96C5795D7870F42 / 0xA17870F5D4F51B49

Существующие стандарты CRC-128 (IEEE) и CRC-256 (IEEE) в настоящее время вытеснены криптографическими хеш-функциями.

Попытки описания алгоритмов CRC

Одной из самых известных является методика Ross N. Williams^[25]. В ней используются следующие параметры:

• Название алгоритма (name);

• Степень порождающего контрольную сумму многочлена(width);

• Сам производящий полином (poly). Для того, чтобы записать его в виде значения, его сначала записывают как битовую последовательность, при этом старший бит опускается — он всегда равен 1. К примеру, многочлен $x^8+x^4+1$ в данной нотации будет записан числом $00010001_2$. Для удобства полученное двоичное представление записывают в шестнадцатеричной форме. Для нашего случая оно будет равно $11_h$ или 0x11;

• Стартовые данные (init), то есть значения регистров на момент начала вычислений;

• Флаг (RefIn), указывающий на начало и направление вычислений. Существует два варианта: начиная со старшего значащего бита (MSB-first), или с младшего (LSB-first);

• Флаг (RefOut), определяющий, инвертируется ли данные регистра при входе на элемент XOR;

• Число (XorOut), с которым складывается по модулю 2 полученный результат;

• Значение CRC (check) для строки «123456789» .

Примеры спецификаций некоторых алгоритмов CRC

Name : CRC 16 Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : BB3D

Name : CRC 16/IBM Width : 16 Poly : 8005 Init : FFFF RefIn : True RefOut : True XorOut : 0000 Check : 4B37

Name : CRC 32 Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : CBF43926

Name : CRC 16/CITT Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : 0000

Name : XMODEM Width : 16 Poly : 8408 Init : 0000 RefIn : True RefOut : True XorOut : 0000

Name : ARC Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000

Примеры программ для вычисления CRC на языке C

Некоторые из этих алгоритмов заимствованы у Ross Williams^[26].

CRC-4

Пример программы, генерирующей массив, предназначенный для табличного способа вычисления CRC4 на языке C#

/*
  Name  : CRC-4
  Poly  : 0x13    x4 + x + 1
  rtbOutput : объект класса RichTextBox
*/
 
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
 
namespace CRC_Table
{
    public partial class Form1 : Form
    {
 
        const int Polinom = 0x13;
 
        public Form1()
        {
            InitializeComponent();
        }
 
        private void btnGenerate_Click(object sender, EventArgs e)
        {
            rtbOutput.Text = "const int CRC4_Table[256] = {\n";
 
            int local = 0;
            for (int i = 0; i < 256; i++)
            {
                rtbOutput.Text += (local == 0) ? "\t\t" : "";
                rtbOutput.Text += CRCTableCell(i) + ", ";
                rtbOutput.Text += (local == 0xf) ? "\n" : "";
 
                local++;
                local &= 0xf;                               
            }
 
            rtbOutput.Text += "};";
        }
 
        string CRCTableCell(int value)
        {
          int r;
 
          r = (value << 8) & 0xFF00;
          int shifted_Polinom = Polinom << (3+8); // 3 сдвига для дополнения полинома до размера 1 байта, 8 сдв. для заполнения нулями
 
 
          for(byte j=0; j<8; j++)
          {
              if ((r & (1 << 15)) == 0x8000)
              {                  
                  r ^= shifted_Polinom;
                  r = (r << 1);
              }
              else r = r << 1;
          }
 
          r = r >> 8;
          return String.Format("0x{0:X2}", r);
        }
 
    }
}

Итоговый массив для табличного (быстрого) расчёта CRC4 (результат работы вышеприведенного кода)

CRC-8

Пример программы расчёта CRC8 на языке Си

/*
  Name  : CRC-8
  Poly  : 0x31    x^8 + x^5 + x^4 + 1
  Init  : 0xFF
  Revert: false
  XorOut: 0x00
  Check : 0xF7 ("123456789")
  MaxLen: 15 байт(127 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/
unsigned char Crc8(unsigned char *pcBlock, unsigned int len)
{
    unsigned char crc = 0xFF;
    unsigned int i;
 
    while (len--)
    {
        crc ^= *pcBlock++;
 
        for (i = 0; i < 8; i++)
            crc = crc & 0x80 ? (crc << 1) ^ 0x31 : crc << 1;
    }
 
    return crc;
}

Пример программы табличного (быстрого) расчёта CRC8 на языке Си

/*
  Name  : CRC-8
  Poly  : 0x31    x^8 + x^5 + x^4 + 1
  Init  : 0xFF
  Revert: false
  XorOut: 0x00
  Check : 0xF7 ("123456789")
  MaxLen: 15 байт (127 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/

CRC-16

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

Оптимизированный расчёт CRC-16 CCITT на языке Си, полином 0x8408

/*
  Name  : CRC-16 CCITT
  Poly  : 0x8408
  Init  : 0xFFFF
  Revert: false
  XorOut: 0x0000
  Check : 0x6F91 ("123456789")
  MaxLen: 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/
unsigned short crc_ccitt_update (unsigned short crc, unsigned char data){
unsigned short t;
        data ^= crc&255;
        data ^= data << 4;
        t = (((unsigned short)data << 8) | ((crc>>8)&255));
        t^=(unsigned char)(data >> 4);
        t^= ((unsigned short)data << 3);
        return t;
}

Пример программы расчёта CRC-16 CCITT на языке Си

/*
  Name  : CRC-16 CCITT
  Poly  : 0x1021    x^16 + x^12 + x^5 + 1
  Init  : 0xFFFF
  Revert: false
  XorOut: 0x0000
  Check : 0x29B1 ("123456789")
  MaxLen: 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/
unsigned short Crc16(unsigned char *pcBlock, unsigned short len)
{
    unsigned short crc = 0xFFFF;
    unsigned char i;
 
    while (len--)
    {
        crc ^= *pcBlock++ << 8;
 
        for (i = 0; i < 8; i++)
            crc = crc & 0x8000 ? (crc << 1) ^ 0x1021 : crc << 1;
    }
 
    return crc;
}

Пример программы табличного (быстрого) расчёта CRC-16 CCITT на языке Си

/*
  Name  : CRC-16 CCITT
  Poly  : 0x1021    x^16 + x^12 + x^5 + 1
  Init  : 0xFFFF
  Revert: false
  XorOut: 0x0000
  Check : 0x29B1 ("123456789")
  MaxLen: 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/

Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си

/*
  Name  : CRC-16
  Poly  : 0x8005    x^16 + x^15 + x^2 + 1
  Init  : 0xFFFF
  Revert: true
  XorOut: 0x0000
  Check : 0x4B37 ("123456789")
  MaxLen: 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/

Пример программы расчёта CRC-16 CCITT на языке PHP

/*
  Name            : CRC-16 CCITT
  Poly (default)  : 0x1021    x^16 + x^12 + x^5 + 1
  Init (default)  : 0xFFFF
  XorOut (default): 0x0000
  Revert          : false
  Check           : 0x29B1 ("123456789")
  MaxLen          : 4095 байт (32767 бит) - обнаружение
    одинарных, двойных, тройных и всех нечетных ошибок
*/
function crc16($sStr, $aParams = array()){
 
   //-- устанавливаем значения по умолчанию у незаданных параметров
   $aDefaults = array(
      "polynome" => 0x1021,
      "init" => 0xFFFF,
      "xor_out" => 0,
   );
 
   foreach ($aDefaults as $key => $val){
      if (!isset($aParams[$key])){
         $aParams[$key] = $val;
      }
   }
 
   //-- инициализируем переменные
   $sStr .= "";
   $crc = $aParams['init'];
   $len = strlen($sStr);
   $i = 0;
 
   //-- считаем
   while ($len--){
      $crc ^= ord($sStr[$i++]) << 8;
      $crc &= 0xffff;
 
      for ($j = 0; $j < 8; $j++){
         $crc = ($crc & 0x8000) ? ($crc << 1) ^ $aParams['polynome'] : $crc << 1;
         $crc &= 0xffff;
      }
   }
 
   $crc ^= $aParams['xor_out'];
 
   return $crc;
}

Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке AVR assembler

;  Name  : CRC-16
;  Poly  : 0x8005    x^16 + x^15 + x^2 + 1
;  Init  : 0xFFFF
;  Revert: true
;  XorOut: 0x0000
;  Check : 0x4B37 ("123456789"

CRC-32

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

Пример программы расчёта CRC-32 на языке Си

#include <stddef.h>
#include <stdint.h>
/*
  Name  : CRC-32
  Poly  : 0x04C11DB7    x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 
                       + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
  Init  : 0xFFFFFFFF
  Revert: true
  XorOut: 0xFFFFFFFF
  Check : 0xCBF43926 ("123456789")
  MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение
   одинарных, двойных, пакетных и всех нечетных ошибок
*/
uint_least32_t Crc32(unsigned char *buf, size_t len)
{
    uint_least32_t crc_table[256];
    uint_least32_t crc; int i, j;
 
    for (i = 0; i < 256; i++)
    {
        crc = i;
        for (j = 0; j < 8; j++)
            crc = crc & 1 ? (crc >> 1) ^ 0xEDB88320UL : crc >> 1;
 
        crc_table[i] = crc;
    };
 
    crc = 0xFFFFFFFFUL;
 
    while (len--) 
        crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
 
    return crc ^ 0xFFFFFFFFUL;
}

Пример программы табличного (быстрого) расчёта CRC-32 на языке Си

#include <stddef.h>
#include <stdint.h>
/*
  Name  : CRC-32
  Poly  : 0x04C11DB7    x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 
                       + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
  Init  : 0xFFFFFFFF
  Revert: true
  XorOut: 0xFFFFFFFF
  Check : 0xCBF43926 ("123456789")
  MaxLen: 268 435 455 байт (2 147 483 647 бит) - обнаружение
   одинарных, двойных, пакетных и всех нечетных ошибок
*/

Примечания

1. ↑ ^{1 2 3 4 5} Philip Koopman, Tridib Chakravarty. Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks (2004). Архивировано из первоисточника 23 августа 2011. Проверено ???.
2. ↑ Интернет-Университет Информационных Технологий. Лекция: Организация беспроводных сетей
3. ↑ Интернет-Университет Информационных Технологий. Лекция: Алгоритмы сети Ethernet/Fast Ethernet
4. ↑ Walma, M.; Pipelined Cyclic Redundancy Check (CRC) Calculation
5. ↑ Greg Cook. Catalogue of parameterised CRC algorithms (29 апреля 2009). Архивировано из первоисточника 23 августа 2011. Проверено ???.
6. ↑ G. Castagnoli, S. Braeuer, M. Herrman. Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits // IEEE Transactions on Communications. — июнь 1993. — Т. 41. — № 6. — С. 883. — DOI:10.1109/26.231911
7. ↑ ^{1 2 3 4 5 6} P. Koopman. 32-Bit Cyclic Redundancy Codes for Internet Applications // The International Conference on Dependable Systems and Networks. — июнь 2002. — С. 459. — DOI:10.1109/DSN.2002.1028931
8. ↑ Brayer, K; Hammond, J L Jr. (December 1975). "Evaluation of error detection polynomial performance on the AUTOVON channel" in National Telecommunications Conference, New Orleans, La. Conference Record 1: 8-21 to 8-25, New York: Institute of Electrical and Electronics Engineers. 
9. ↑ В представлениях опущен старший бит.
10. ↑ G.704, p. 12
11. ↑ Class-1 Generation-2 UHF RFID Protocol version 1.2.0. — 23 октября 2008. — С. 35.
12. ↑ G.704, p. 9
13. ↑ G.704, p. 3
14. ↑ G.707 : Network node interface for the synchronous digital hierarchy (SDH)
15. ↑ G.832 : Transport of SDH elements on PDH networks — Frame and multiplexing structures
16. ↑ EN 302 307. Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)
17. ↑ ^{1 2} FlexRay Protocol Specification version 2.1 Revision A. — 22 декабря 2005. — С. 93.
18. ↑ A. Perez, Wismer, Becker. Byte-Wise CRC Calculations // IEEE Micro. — 1983. — Т. 3. — № 3. — С. 40—50. — DOI:10.1109/MM.1983.291120
19. ↑ T. V. Ramabadran, S. S. Gaitonde. A tutorial on CRC computations // IEEE Micro. — 1988. — Т. 8. — № 4. — С. 62—75. — DOI:10.1109/40.7773
20. ↑ http://www.incits.org/press/1997/pr97020.htm
21. ↑ Pat Thaler. 16-bit CRC polynomial selection. INCITS T10 (28 августа 2003). Архивировано из первоисточника 23 августа 2011. Проверено ???.
22. ↑ Thomas Boutell, Glenn Randers-Pehrson и др. PNG (Portable Network Graphics) Specification, Version 1.2 (14 июля 1998). Архивировано из первоисточника 23 августа 2011. Проверено ???.
23. ↑ AIXM Primer version 4.5. European Organisation for the Safety of Air Navigation (20 марта 2006). Архивировано из первоисточника 23 августа 2011. Проверено ???.
24. ↑ ECMA-182 p. 51
25. ↑ Ross N. Williams. CRC Rocksoft (1993). Архивировано из первоисточника 15 мая 2012.
26. ↑ Ross N.Williams. Элементарное руководство по CRC-алгоритмам обнаружения ошибок. (1993). Архивировано из первоисточника 16 декабря 2012.

Литература

• Генри С. Уоррен, мл. Глава 5. Подсчет битов // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4

Ссылки

• Элементарное руководство по CRC алгоритмам обнаружения ошибок
• CRC, и как его восстановить
• Восстановление CRC
• CRC-калькулятор
• Генератор CRC-функций на языках VHDL и Verilog
• Ross N. Williams/Anarchriz. Всё о CRC32 // Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок
• Ross N. Williams. A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS (англ.)

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.