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

Содержимое удалено Содержимое добавлено
Использован {{BookCat}}; пробелы; →‎К переименованию: снят шаблон после переименования.
Строка 1:
{{КПримеры переименованиюпрограмм |2014-11-21|Реализациидля алгоритмов/вычисления [[w:Циклический избыточный код}}|CRC]]. Некоторые из этих алгоритмов заимствованы у Ross Williams<ref>
 
Примеры программ для вычисления [[w:Циклический избыточный код|CRC]]. Некоторые из этих алгоритмов заимствованы у Ross Williams<ref>
{{cite web
| author = Ross N.Williams.
Строка 56 ⟶ 54 :
 
local++;
local &= 0xf;
}
 
Строка 73 ⟶ 71 :
{
if ((r & (1 << 15)) == 0x8000)
{
r ^= shifted_Polinom;
r = (r << 1);
Строка 94 ⟶ 92 :
<source lang="csharp">
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
};
</source>
Строка 242 ⟶ 240 :
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
};
Строка 455 ⟶ 453 :
0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
};
 
Строка 546 ⟶ 544 :
mov R21, R16
eor R21, R22
 
add R21, R21 ; маштабирование индекса таблицы
clr R22
Строка 556 ⟶ 554 :
adc ZH, R22
lpm R22, Z++
lpm R23, Z++
 
mov R16, R17 ; (R16:R17>>8) ^ R21:R22
Строка 643 ⟶ 641 :
0x004E, 0xC18E, 0x818F, 0x404F, 0x018D, 0xC04D, 0x804C, 0x418C,
0x0044, 0xC184, 0x8185, 0x4045, 0x0187, 0xC047, 0x8046, 0x4186,
0x0182, 0xC042, 0x8043, 0x4183, 0x0041, 0xC181, 0x8180, 0x4040
};
 
Строка 665 ⟶ 663 :
{
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) {
Строка 679 ⟶ 677 :
}
// Помните, что младший и старший байты поменяны местами, используйте соответственно (или переворачивайте)
return crc;
}
</source>
Строка 695 ⟶ 693 :
/*
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
Строка 720 ⟶ 718 :
crc = 0xFFFFFFFFUL;
 
while (len--)
crc = crc_table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
 
Строка 737 ⟶ 735 :
/*
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
Строка 869 ⟶ 867 :
 
== Программная реализация на C ==
Получили распространение несколько методов программного расчета CRC:
* оригинальный алгоритм с побитовым вводом данных:
{{Hider hiding|title=Расчет одного бита CRC8 по оригинальному алгоритму|content= <source lang="c">
// _D - входной бит
Строка 926 ⟶ 924 :
{{Hider hiding|title=Генерация таблицы CRC8|content= <source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x;
Строка 937 ⟶ 935 :
{{Hider hiding|title=Генерация таблицы CRC32|content= <source lang="c">
// CRC_Polynom - значение полинома CRC
// CRCTable[0x100] - таблица
for (x = 0; x < 0x100; x++) {
_crc = x;
Строка 951 ⟶ 949 :
{{примечания}}
 
{{BookCat}}
[[Категория:Программирование]]