Реализации алгоритмов/Циклический избыточный код
Примеры программ для вычисления CRC. Некоторые из этих алгоритмов заимствованы у Ross Williams[1].
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 (результат работы вышеприведенного кода)
const int CRC4_Table[256] = {
0x00, 0x30, 0x60, 0x50, 0xC0, 0xF0, 0xA0, 0x90, 0xB0, 0x80, 0xD0, 0xE0, 0x70, 0x40, 0x10, 0x20,
0x50, 0x60, 0x30, 0x00, 0x90, 0xA0, 0xF0, 0xC0, 0xE0, 0xD0, 0x80, 0xB0, 0x20, 0x10, 0x40, 0x70,
0xA0, 0x90, 0xC0, 0xF0, 0x60, 0x50, 0x00, 0x30, 0x10, 0x20, 0x70, 0x40, 0xD0, 0xE0, 0xB0, 0x80,
0xF0, 0xC0, 0x90, 0xA0, 0x30, 0x00, 0x50, 0x60, 0x40, 0x70, 0x20, 0x10, 0x80, 0xB0, 0xE0, 0xD0,
0x70, 0x40, 0x10, 0x20, 0xB0, 0x80, 0xD0, 0xE0, 0xC0, 0xF0, 0xA0, 0x90, 0x00, 0x30, 0x60, 0x50,
0x20, 0x10, 0x40, 0x70, 0xE0, 0xD0, 0x80, 0xB0, 0x90, 0xA0, 0xF0, 0xC0, 0x50, 0x60, 0x30, 0x00,
0xD0, 0xE0, 0xB0, 0x80, 0x10, 0x20, 0x70, 0x40, 0x60, 0x50, 0x00, 0x30, 0xA0, 0x90, 0xC0, 0xF0,
0x80, 0xB0, 0xE0, 0xD0, 0x40, 0x70, 0x20, 0x10, 0x30, 0x00, 0x50, 0x60, 0xF0, 0xC0, 0x90, 0xA0,
0xE0, 0xD0, 0x80, 0xB0, 0x20, 0x10, 0x40, 0x70, 0x50, 0x60, 0x30, 0x00, 0x90, 0xA0, 0xF0, 0xC0,
0xB0, 0x80, 0xD0, 0xE0, 0x70, 0x40, 0x10, 0x20, 0x00, 0x30, 0x60, 0x50, 0xC0, 0xF0, 0xA0, 0x90,
0x40, 0x70, 0x20, 0x10, 0x80, 0xB0, 0xE0, 0xD0, 0xF0, 0xC0, 0x90, 0xA0, 0x30, 0x00, 0x50, 0x60,
0x10, 0x20, 0x70, 0x40, 0xD0, 0xE0, 0xB0, 0x80, 0xA0, 0x90, 0xC0, 0xF0, 0x60, 0x50, 0x00, 0x30,
0x90, 0xA0, 0xF0, 0xC0, 0x50, 0x60, 0x30, 0x00, 0x20, 0x10, 0x40, 0x70, 0xE0, 0xD0, 0x80, 0xB0,
0xC0, 0xF0, 0xA0, 0x90, 0x00, 0x30, 0x60, 0x50, 0x70, 0x40, 0x10, 0x20, 0xB0, 0x80, 0xD0, 0xE0,
0x30, 0x00, 0x50, 0x60, 0xF0, 0xC0, 0x90, 0xA0, 0x80, 0xB0, 0xE0, 0xD0, 0x40, 0x70, 0x20, 0x10,
0x60, 0x50, 0x00, 0x30, 0xA0, 0x90, 0xC0, 0xF0, 0xD0, 0xE0, 0xB0, 0x80, 0x10, 0x20, 0x70, 0x40
};
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 бит) - обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/
const unsigned char Crc8Table[256] = {
0x00, 0x31, 0x62, 0x53, 0xC4, 0xF5, 0xA6, 0x97,
0xB9, 0x88, 0xDB, 0xEA, 0x7D, 0x4C, 0x1F, 0x2E,
0x43, 0x72, 0x21, 0x10, 0x87, 0xB6, 0xE5, 0xD4,
0xFA, 0xCB, 0x98, 0xA9, 0x3E, 0x0F, 0x5C, 0x6D,
0x86, 0xB7, 0xE4, 0xD5, 0x42, 0x73, 0x20, 0x11,
0x3F, 0x0E, 0x5D, 0x6C, 0xFB, 0xCA, 0x99, 0xA8,
0xC5, 0xF4, 0xA7, 0x96, 0x01, 0x30, 0x63, 0x52,
0x7C, 0x4D, 0x1E, 0x2F, 0xB8, 0x89, 0xDA, 0xEB,
0x3D, 0x0C, 0x5F, 0x6E, 0xF9, 0xC8, 0x9B, 0xAA,
0x84, 0xB5, 0xE6, 0xD7, 0x40, 0x71, 0x22, 0x13,
0x7E, 0x4F, 0x1C, 0x2D, 0xBA, 0x8B, 0xD8, 0xE9,
0xC7, 0xF6, 0xA5, 0x94, 0x03, 0x32, 0x61, 0x50,
0xBB, 0x8A, 0xD9, 0xE8, 0x7F, 0x4E, 0x1D, 0x2C,
0x02, 0x33, 0x60, 0x51, 0xC6, 0xF7, 0xA4, 0x95,
0xF8, 0xC9, 0x9A, 0xAB, 0x3C, 0x0D, 0x5E, 0x6F,
0x41, 0x70, 0x23, 0x12, 0x85, 0xB4, 0xE7, 0xD6,
0x7A, 0x4B, 0x18, 0x29, 0xBE, 0x8F, 0xDC, 0xED,
0xC3, 0xF2, 0xA1, 0x90, 0x07, 0x36, 0x65, 0x54,
0x39, 0x08, 0x5B, 0x6A, 0xFD, 0xCC, 0x9F, 0xAE,
0x80, 0xB1, 0xE2, 0xD3, 0x44, 0x75, 0x26, 0x17,
0xFC, 0xCD, 0x9E, 0xAF, 0x38, 0x09, 0x5A, 0x6B,
0x45, 0x74, 0x27, 0x16, 0x81, 0xB0, 0xE3, 0xD2,
0xBF, 0x8E, 0xDD, 0xEC, 0x7B, 0x4A, 0x19, 0x28,
0x06, 0x37, 0x64, 0x55, 0xC2, 0xF3, 0xA0, 0x91,
0x47, 0x76, 0x25, 0x14, 0x83, 0xB2, 0xE1, 0xD0,
0xFE, 0xCF, 0x9C, 0xAD, 0x3A, 0x0B, 0x58, 0x69,
0x04, 0x35, 0x66, 0x57, 0xC0, 0xF1, 0xA2, 0x93,
0xBD, 0x8C, 0xDF, 0xEE, 0x79, 0x48, 0x1B, 0x2A,
0xC1, 0xF0, 0xA3, 0x92, 0x05, 0x34, 0x67, 0x56,
0x78, 0x49, 0x1A, 0x2B, 0xBC, 0x8D, 0xDE, 0xEF,
0x82, 0xB3, 0xE0, 0xD1, 0x46, 0x77, 0x24, 0x15,
0x3B, 0x0A, 0x59, 0x68, 0xFF, 0xCE, 0x9D, 0xAC
};
unsigned char Crc8(unsigned char *pcBlock, unsigned char len)
{
unsigned char crc = 0xFF;
while (len--)
crc = Crc8Table[crc ^ *pcBlock++];
return crc;
}
Пример проверки CRC-8 для BBHeader стандарта ETSI EN 302 307 V1.2.1
unsigned char Crc8_ETSIEN302307(unsigned char *pcBlock, unsigned int len)
{
unsigned char crc = 0x00;
unsigned int i;
while (len--)
{
crc ^= *pcBlock++;
for (i = 0; i < 8; i++)
crc = crc & 0x80 ? (crc << 1) ^ 0xD5 : crc << 1;
}
return crc;
}
Пример программы табличного расчёта CRC-8 на языке C#
public static class CRC
{
// CRC-8 for Dallas iButton products from Maxim/Dallas AP Note 27
static readonly byte[] crc8Table = new byte[]
{
0x00, 0x5E, 0xBC, 0xE2, 0x61, 0x3F, 0xDD, 0x83,
0xC2, 0x9C, 0x7E, 0x20, 0xA3, 0xFD, 0x1F, 0x41,
0x9D, 0xC3, 0x21, 0x7F, 0xFC, 0xA2, 0x40, 0x1E,
0x5F, 0x01, 0xE3, 0xBD, 0x3E, 0x60, 0x82, 0xDC,
0x23, 0x7D, 0x9F, 0xC1, 0x42, 0x1C, 0xFE, 0xA0,
0xE1, 0xBF, 0x5D, 0x03, 0x80, 0xDE, 0x3C, 0x62,
0xBE, 0xE0, 0x02, 0x5C, 0xDF, 0x81, 0x63, 0x3D,
0x7C, 0x22, 0xC0, 0x9E, 0x1D, 0x43, 0xA1, 0xFF,
0x46, 0x18, 0xFA, 0xA4, 0x27, 0x79, 0x9B, 0xC5,
0x84, 0xDA, 0x38, 0x66, 0xE5, 0xBB, 0x59, 0x07,
0xDB, 0x85, 0x67, 0x39, 0xBA, 0xE4, 0x06, 0x58,
0x19, 0x47, 0xA5, 0xFB, 0x78, 0x26, 0xC4, 0x9A,
0x65, 0x3B, 0xD9, 0x87, 0x04, 0x5A, 0xB8, 0xE6,
0xA7, 0xF9, 0x1B, 0x45, 0xC6, 0x98, 0x7A, 0x24,
0xF8, 0xA6, 0x44, 0x1A, 0x99, 0xC7, 0x25, 0x7B,
0x3A, 0x64, 0x86, 0xD8, 0x5B, 0x05, 0xE7, 0xB9,
0x8C, 0xD2, 0x30, 0x6E, 0xED, 0xB3, 0x51, 0x0F,
0x4E, 0x10, 0xF2, 0xAC, 0x2F, 0x71, 0x93, 0xCD,
0x11, 0x4F, 0xAD, 0xF3, 0x70, 0x2E, 0xCC, 0x92,
0xD3, 0x8D, 0x6F, 0x31, 0xB2, 0xEC, 0x0E, 0x50,
0xAF, 0xF1, 0x13, 0x4D, 0xCE, 0x90, 0x72, 0x2C,
0x6D, 0x33, 0xD1, 0x8F, 0x0C, 0x52, 0xB0, 0xEE,
0x32, 0x6C, 0x8E, 0xD0, 0x53, 0x0D, 0xEF, 0xB1,
0xF0, 0xAE, 0x4C, 0x12, 0x91, 0xCF, 0x2D, 0x73,
0xCA, 0x94, 0x76, 0x28, 0xAB, 0xF5, 0x17, 0x49,
0x08, 0x56, 0xB4, 0xEA, 0x69, 0x37, 0xD5, 0x8B,
0x57, 0x09, 0xEB, 0xB5, 0x36, 0x68, 0x8A, 0xD4,
0x95, 0xCB, 0x29, 0x77, 0xF4, 0xAA, 0x48, 0x16,
0xE9, 0xB7, 0x55, 0x0B, 0x88, 0xD6, 0x34, 0x6A,
0x2B, 0x75, 0x97, 0xC9, 0x4A, 0x14, 0xF6, 0xA8,
0x74, 0x2A, 0xC8, 0x96, 0x15, 0x4B, 0xA9, 0xF7,
0xB6, 0xE8, 0x0A, 0x54, 0xD7, 0x89, 0x6B, 0x35
};
public static byte CRC8(byte[] bytes, int len)
{
byte crc = 0;
for (var i = 0; i < len; i++)
crc = crc8Table[crc ^ bytes[i]];
return crc;
}
}
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 бит) - обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/
const unsigned short Crc16Table[256] = {
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};
unsigned short Crc16(unsigned char * pcBlock, unsigned short len)
{
unsigned short crc = 0xFFFF;
while (len--)
crc = (crc << 8) ^ Crc16Table[(crc >> 8) ^ *pcBlock++];
return crc;
}
Пример программы табличного (быстрого) расчёта стандартного (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 бит) - обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/
const unsigned short Crc16Table[256] = {
0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};
unsigned short Crc16(unsigned char * pcBlock, unsigned short len)
{
unsigned short crc = 0xFFFF;
while (len--)
crc = (crc >> 8) ^ Crc16Table[(crc & 0xFF) ^ *pcBlock++];
return crc;
}
Пример программы расчёта 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")
; MaxLen: 4095 байт (32767 бит) - обнаружение
; одинарных, двойных, тройных и всех нечетных ошибок
; IN
; YL:YH - Указатель на исходный буфер в памяти
; R24:R25 - Длина буфера в байтах
; R16:R17 - Начальное значение
; OUT
; R16:R17 - CRC16
crc16:
ld R22, Y++
mov R21, R16
eor R21, R22
add R21, R21 ; маштабирование индекса таблицы
clr R22
adc R22, R22
ldi ZL, low(crc16table*2)
ldi ZH, high(crc16table*2)
add ZL, R21 ; R21:R22=crc16table[R21:R22];
adc ZH, R22
lpm R22, Z++
lpm R23, Z++
mov R16, R17 ; (R16:R17>>8) ^ R21:R22
eor R16, R22
mov R17, R23
sbiw R24:R25, 1
brne crc16
ret
crc16table:
.dw 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241
.dw 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440
.dw 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40
.dw 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841
.dw 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40
.dw 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41
.dw 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641
.dw 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040
.dw 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240
.dw 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441
.dw 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41
.dw 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840
.dw 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41
.dw 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40
.dw 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640
.dw 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041
.dw 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240
.dw 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441
.dw 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41
.dw 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840
.dw 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41
.dw 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40
.dw 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640
.dw 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041
.dw 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241
.dw 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440
.dw 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40
.dw 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841
.dw 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40
.dw 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41
.dw 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641
.dw 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
Пример программы табличного (быстрого) расчёта Modbus CRC-16 на языке C#
public static class CRC
{
// Расчет CRC16 для проверки пакетов ModBusRTU
// для добавления в пакет старший и младший байты должны быть поменяны местами
static readonly ushort[] crc16Table = new ushort[]
{
0x0000, 0xC1C0, 0x81C1, 0x4001, 0x01C3, 0xC003, 0x8002, 0x41C2,
0x01C6, 0xC006, 0x8007, 0x41C7, 0x0005, 0xC1C5, 0x81C4, 0x4004,
0x01CC, 0xC00C, 0x800D, 0x41CD, 0x000F, 0xC1CF, 0x81CE, 0x400E,
0x000A, 0xC1CA, 0x81CB, 0x400B, 0x01C9, 0xC009, 0x8008, 0x41C8,
0x01D8, 0xC018, 0x8019, 0x41D9, 0x001B, 0xC1DB, 0x81DA, 0x401A,
0x001E, 0xC1DE, 0x81DF, 0x401F, 0x01DD, 0xC01D, 0x801C, 0x41DC,
0x0014, 0xC1D4, 0x81D5, 0x4015, 0x01D7, 0xC017, 0x8016, 0x41D6,
0x01D2, 0xC012, 0x8013, 0x41D3, 0x0011, 0xC1D1, 0x81D0, 0x4010,
0x01F0, 0xC030, 0x8031, 0x41F1, 0x0033, 0xC1F3, 0x81F2, 0x4032,
0x0036, 0xC1F6, 0x81F7, 0x4037, 0x01F5, 0xC035, 0x8034, 0x41F4,
0x003C, 0xC1FC, 0x81FD, 0x403D, 0x01FF, 0xC03F, 0x803E, 0x41FE,
0x01FA, 0xC03A, 0x803B, 0x41FB, 0x0039, 0xC1F9, 0x81F8, 0x4038,
0x0028, 0xC1E8, 0x81E9, 0x4029, 0x01EB, 0xC02B, 0x802A, 0x41EA,
0x01EE, 0xC02E, 0x802F, 0x41EF, 0x002D, 0xC1ED, 0x81EC, 0x402C,
0x01E4, 0xC024, 0x8025, 0x41E5, 0x0027, 0xC1E7, 0x81E6, 0x4026,
0x0022, 0xC1E2, 0x81E3, 0x4023, 0x01E1, 0xC021, 0x8020, 0x41E0,
0x01A0, 0xC060, 0x8061, 0x41A1, 0x0063, 0xC1A3, 0x81A2, 0x4062,
0x0066, 0xC1A6, 0x81A7, 0x4067, 0x01A5, 0xC065, 0x8064, 0x41A4,
0x006C, 0xC1AC, 0x81AD, 0x406D, 0x01AF, 0xC06F, 0x806E, 0x41AE,
0x01AA, 0xC06A, 0x806B, 0x41AB, 0x0069, 0xC1A9, 0x81A8, 0x4068,
0x0078, 0xC1B8, 0x81B9, 0x4079, 0x01BB, 0xC07B, 0x807A, 0x41BA,
0x01BE, 0xC07E, 0x807F, 0x41BF, 0x007D, 0xC1BD, 0x81BC, 0x407C,
0x01B4, 0xC074, 0x8075, 0x41B5, 0x0077, 0xC1B7, 0x81B6, 0x4076,
0x0072, 0xC1B2, 0x81B3, 0x4073, 0x01B1, 0xC071, 0x8070, 0x41B0,
0x0050, 0xC190, 0x8191, 0x4051, 0x0193, 0xC053, 0x8052, 0x4192,
0x0196, 0xC056, 0x8057, 0x4197, 0x0055, 0xC195, 0x8194, 0x4054,
0x019C, 0xC05C, 0x805D, 0x419D, 0x005F, 0xC19F, 0x819E, 0x405E,
0x005A, 0xC19A, 0x819B, 0x405B, 0x0199, 0xC059, 0x8058, 0x4198,
0x0188, 0xC048, 0x8049, 0x4189, 0x004B, 0xC18B, 0x818A, 0x404A,
0x004E, 0xC18E, 0x818F, 0x404F, 0x018D, 0xC04D, 0x804C, 0x418C,
0x0044, 0xC184, 0x8185, 0x4045, 0x0187, 0xC047, 0x8046, 0x4186,
0x0182, 0xC042, 0x8043, 0x4183, 0x0041, 0xC181, 0x8180, 0x4040
};
public static ushort CRC16(byte[] bytes, int len)
{
ushort crc = 0xFFFF;
for (var i = 0; i < len; i++)
crc = (ushort)((crc << 8) ^ crc16Table[(crc >> 8) ^ bytes[i]]);
return crc;
}
}
Пример программы расчёта Modbus CRC-16 на языке C#
//http://www.ccontrolsys.com/w/How_to_Compute_the_Modbus_RTU_Message_CRC
UInt16 ModRTU_CRC(byte[] buf, int len)
{
UInt16 crc = 0xFFFF;
for (int pos = 0; pos < len; pos++) {
crc ^= (UInt16)buf[pos];
for (int i = 8; i != 0; i--) {
if ((crc & 0x0001) != 0) {
crc >>= 1;
crc ^= 0xA001;
}
else
crc >>= 1;
}
}
// Помните, что младший и старший байты поменяны местами, используйте соответственно (или переворачивайте)
return crc;
}
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 бит) - обнаружение
одинарных, двойных, пакетных и всех нечетных ошибок
*/
const uint_least32_t Crc32Table[256] = {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE,
0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC,
0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5,
0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B,
0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116,
0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F,
0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A,
0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818,
0x7F6A0DBB, 0x086D3D2D, 0x91646C97, 0xE6635C01,
0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457,
0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, 0xFCB9887C,
0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2,
0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9,
0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086,
0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD,
0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683,
0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8,
0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE,
0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7,
0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5,
0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60,
0xDF60EFC3, 0xA867DF55, 0x316E8EEF, 0x4669BE79,
0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04,
0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A,
0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713,
0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21,
0x86D3D2D4, 0xF1D4E242, 0x68DDB3F8, 0x1FDA836E,
0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C,
0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB,
0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0,
0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF,
0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
};
uint_least32_t Crc32(const unsigned char * buf, size_t len)
{
uint_least32_t crc = 0xFFFFFFFF;
while (len--)
crc = (crc >> 8) ^ Crc32Table[(crc ^ *buf++) & 0xFF];
return crc ^ 0xFFFFFFFF;
}
Хороший пример для расчёта CRC-32 файла на языке С++
#include <fstream>
#include <iostream>
using namespace std;
unsigned int CRC32_function(unsigned char *buf, unsigned long len)
{
unsigned long crc_table[256];
unsigned long crc;
for (int i = 0; i < 256; i++)
{
crc = i;
for (int 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;
}
//возвращание конечного CRC32. Достаточно вызвать эту функцию и указать имя файла, для которого будет произведён расчёт
unsigned int CRC32_count(char* filename)
{
char buf[4096*64]; //сколько символов в файле, на самом деле, это должно быть больше, 2^31-1 будет для файла размером 2ГБ
ifstream f (filename,std::ios::binary);
f.read(buf,4096*64);
return CRC32_function((unsigned char*)buf, f.gcount());
}
Программная реализация на C
[править]Получили распространение несколько методов программного расчета CRC:
- оригинальный алгоритм с побитовым вводом данных:
Расчет одного бита CRC8 по оригинальному алгоритму
// _D - входной бит
// _crc - сдвиговый регистр CRC
// CRC_Polynom - значение полинома CRC
if (_crc & (1<<7)) {
if (_D) {
_crc = _crc << 1;
} else {
_crc = (_crc << 1) ^ CRC_Polynom;
}
} else {
if (_D) {
_crc = (_crc << 1) ^ CRC_Polynom;
} else {
_crc = _crc << 1;
}
}
- Конечно, этот алгоритм может быть записан короче:
Расчет одного бита CRC8 по оригинальному алгоритму
if (_crc & (1<<7)) {
_crc = _crc << 1;
if (0 == _D) _crc ^= CRC_Polynom;
} else {
_crc = _crc << 1;
if (_D) _crc ^= CRC_Polynom;
}
- Псевдотабличный с побайтовым вводом данных и генерацией требуемого элемента таблицы непосредственно в цикле расчета:
Расчет одного байта CRC8 по псевдотабличному алгоритму
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CRC_Polynom - значение полинома CRC
_crc ^= _D;
for (i = 0; i < 8; i++) {
_crc = (_crc & (1<<7)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
- По объему кода псевдотабличный метод почти не отличается от прямого расчета, но может быть чуть быстрее, поэтому практически вытеснил оригинальный метод.
- Табличный с побайтовым вводом данных и заранее созданной таблицей:
Расчет одного байта CRC8 по табличному алгоритму
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CrcTable - таблица, здесь не показана ввиду значительного объема
_crc = CrcTable[_crc ^ _D];
Расчет одного байта CRC32 по табличному алгоритму
// _D - входной байт
// _crc - сдвиговый регистр CRC
// CrcTable - таблица, здесь не показана ввиду значительного объема
_crc = CrcTable[(_crc ^ _D) & 0xFF] ^ (_crc << 8);
- Таблица может быть задана константой (создаваться до компиляции) или генерироваться непосредственно перед выполнением расчета. Табличный метод основан на том что одинаковые последовательности входных данных дают одинаковые изменения регистра сдвига, поэтому за один цикл можно рассчитать больше чем один бит входных данных. Табличный метод требует значительных затрат памяти под таблицы. Размер элемента таблицы равен размеру выбранного полинома. Длина таблицы равна , где D - выбранная длина входных данных в битах для одного цикла расчета (например, для однобайтового варианта это 8 бит). Например, для 32-битной CRC с побайтовым расчетом длина таблицы будет 256 слов по 32 бита, т.е. 1024 байта. Алгоритм генерации таблицы:
Генерация таблицы CRC8
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x;
for (y = 0; y < 8; y++) {
_crc = (_crc & (1<<7)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
CRCTable[x] = _crc;
}
Генерация таблицы CRC32
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x; //ошибка! так полином не используется; ?: _crc = x<<(32-8);
for (y = 0; y < 8; y++) {
_crc = (_crc & (1<<31)) ? ((_crc << 1) ^ CRC_Polynom) : (_crc << 1);
}
CRCTable[x] = _crc;
}