Česky:
|
Kontrolní součty
a jejich výpočty v C
Kontrolní součty jsou nevyhnutelnou součástí přenosu dat a kontroly zařízení. Slouží k detekci chyb. Důležitou vlastností kontrolního součtu je odolnost vůči vícenásobným chybám. Vliv jedné chyby na výsledný kontrolní součet by neměl vykompenzovat vliv jiné chyby. Zde si ukážeme několik nejpoužívanějších kontrolních součtů a jejich výpočty, včetně statistického porovnání úspěšnosti. Většinu funkcí zde naleznete v rychlé i pomalé variantě - s tabulkou nebo bez tabulky. Obzvláštní pozornost pro použití v MCU si zaslouží CCITT XModem, který je k dispozici v rychlé verzi i bez tabulky.
CRC-32 se používá jako jeden z nejsilnějších typů kontrolních součtů, s velkou citlivostí na chyby. Výsledkem je 32-bitové číslo. K výpočtu používá polynom 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 + x^0. Výchozí hodnotou je číslo 0xFFFFFFFF. Používá se např. v grafickém souboru PNG. V tabulkové rychlé verzi vyžaduje předgenerovanou tabulku o velikosti 1 KB. Ve zdrojovém kódu knihovny naleznete i variantu pro hardwarový CRC32 procesoru STM32. Kontrolní vzorek: "123456789" -> 0xCBF43926, 0xFC 0x05 0x4A -> 0xA8E10F6D. Výpočet 1 bajtu v pomalé verzi:
, 
#define CRC32_POLY 0xEDB88320 // reversed 0x04C11DB7
u32 crc32_slow_1(u32 crc, u8 data)
{
int i;
crc ^= data;
for (i = 8; i > 0; i--)
{
if ((crc & 1) == 0)
crc >>= 1;
else
crc = (crc >> 1) ^ CRC32_POLY;
}
return crc;
}
Jako zvláštní varinta je v knihovně uveden i výpočet CRC32 pro Raspberry Pico. Možná jsem kód jen špatně pochopil, ale domnívám se, že v závěru jejich funkce je chyba a proto výpočet dává jiné výsledky než obdobné výpočty (je to varianta s obráceným pořadím bitů a inverzí, ale i tak...). Proto jsem funkci pro výpočet nasimuloval napodobením operací s registry ARMu. Kontrolní vzorek: "123456789" -> 0x0376E6E7, 0xFC 0x05 0x4A -> 0x8E10D720.
CRC-16 je druhým nejsilnějším typem kontrolního součtu. Přestože jeho výsledek je jen 16-bitový, stále ještě má výbornou citlivost na chyby. Výpočet probíhá podle polynomu x^16 + x^15 + x^2 + x^0. Používá se např. v diskových řadičích ke kontrole sektorů, na sběrnici Modbus nebo na sběrnici Dallas Maxim 1-wire. V tabulkové verzi vyžaduje tabulku o velikosti 512 bajtů. Podle výchozí hodnoty se rozlišuje několik verzí. Diskové řadiče a Dallas Maxim používají výchozí hodnotu 0. Kontrolní vzorek: "123456789" -> 0xBB3D, 0xFC 0x05 0x4A -> 0x9742. Sběrnice Modbus používá výchozí hodnotu 0xFFFF. Kontrolní vzorek: "123456789" -> 0x4B37, 0xFC 0x05 0x4A -> 0x5733. Výpočet 1 bajtu v pomalé verzi:
#define CRC16_POLY 0xA001 // reversed 0x8005
u16 crc16_slow_1(u16 crc, u8 data)
{
int i;
crc ^= data;
for (i = 8; i > 0; i--)
{
if ((crc & 1) == 0)
crc >>= 1;
else
crc = (crc >> 1) ^ CRC16_POLY;
}
return crc;
}
Přenosový protokol Kermit používá také 16-bitový kontrolní součet, ale výpočet probíhá podle polynomu x^16 + x^12 + x^5 + x^0. Někdy se tento kontrolní součet označuje jako originální CRC-CCITT. V tabulkové verzi vyžaduje tabulku o velikosti 512 bajtů. Kontrolní vzorek: "123456789" -> 0x8921, 0xFC 0x05 0x4A -> 0x71BA. Výpočet 1 bajtu v pomalé verzi:
#define CRCKERMIT_POLY 0x8408 // reversed 0x1021
u16 crc_kermit_slow_1(u16 crc, u8 data)
{
int i;
crc ^= data;
for (i = 8; i > 0; i--)
{
if ((crc & 1) == 0)
crc >>= 1;
else
crc = (crc >> 1) ^ CRCKERMIT_POLY;
}
return crc; // swap bytes of result
}
DNP je komunikační protokol pro komunikaci mezi počítači v síti. Výpočet probíhá podle polynomu x^16 + x^13 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^2 + x^0. V tabulkové verzi vyžaduje tabulku o velikosti 512 bajtů. Kontrolní vzorek: "123456789" -> 0x82EA, 0xFC 0x05 0x4A -> 0x8AE7. Výpočet 1 bajtu v pomalé verzi:
#define CRCDNP_POLY 0xA6BC // reversed 0x3D65
u16 crc_dnp_slow_1(u16 crc, u8 data)
{
int i;
crc ^= data;
for (i = 8; i > 0; i--)
{
if ((crc & 1) == 0)
crc >>= 1;
else
crc = (crc >> 1) ^ CRCDNP_POLY;
}
return crc; // invert and swap bytes of result
}
16-bitový kontrolní součet CCITT XModem je používaný v přenosovém protokolu XModem. Výpočet probíhá podle polynomu x^16 + x^12 + x^5 + x^0, podobně jako u crc Kermit, ale pořadí bitů je opačné. V tabulkové verzi vyžaduje tabulku o velikosti 512 bajtů. Výchozí hodnotou crc XModem je číslo 0. Kontrolní vzorek: "123456789" -> 0x31C3, 0xFC 0x05 0x4A -> 0x8048. V knihovně je uvedena ještě varianta CRC-CCITT s výchozí hodnotou 0xFFFF. Kontrolní vzorek: "123456789" -> 0x29B1, 0xFC 0x05 0x4A -> 0x4CD4. A dále varianta označená jako CRC-CCITTB, s výchozí hodnotou 0x1D0F. Kontrolní vzorek: "123456789" -> 0xE5CC, 0xFC 0x05 0x4A -> 0x9144. Výpočet 1 bajtu v pomalé verzi:
#define CRCCCITT_POLY 0x1021
u16 crc_ccitt_slow_1(u16 crc, u8 data)
{
int i;
crc ^= ((u16)data << 8);
for (i = 8; i > 0; i--)
{
if ((crc & 0x8000) == 0)
crc <<= 1;
else
crc = (u16)((crc << 1) ^ CRCCCITT_POLY);
}
return crc;
}
Kontrolní součet XModem mám obzvláště rád a to z toho důvodu, že pro něj existuje kód pro snadný a rychlý výpočet, který je srovnatelný s tabulkovou verzí a přitom nevyžaduje tabulku. Proto je vhodný pro použití v malých procesorech s málo pamětí a malým výkonem (pracuje dobře i v Z80). V knihovně uvádím i kód v assembleru pro procesor ATmega, kde ho používám např. ke kontrole programové Flash paměti v kalkulátorech. Výpočet 1 bajtu:
u16 crc_ccitt_fast_1(u16 crc, u8 data) // without table
{
crc = (crc >> 8) | (crc << 8);
crc ^= data;
crc ^= (crc & 0xff) >> 4;
crc ^= crc << 12;
crc ^= (crc & 0xff) << 5;
return crc;
}
Na netu lze najít i další implementace rychlého algoritmu, např.: https://www.ccsinfo.com/forum/viewtopic.php?t=24977, https://www.oldcomp.cz/viewtopic.php?p=109443#p109443 .
Kontrolní součet Sick se používá v zařízeních Sick pro průmyslové měření a detekci. Tento kontrolní součet zde uvádím spíš jako zajímavost, ne k reálnému použití. V knihovně libcrc je uveden následující výpočet, což se podobá výpočtu 1 bitu v kódu CRC-16, ne výpočtu celého bajtu. Zřejmě se jedná o starou verzi výpočtu CRC v zařízeních Sick, protože v současnosti u zařízení Sick uvádějí použití kontrolního součtu CRC-CCITT. Autor knihovny uvádí, že následující výpočet se má aplikovat pro každý bajt 2x. Výpočet 1 bajtu:
#define CRCSICKPOLY 0x8005
u16 crc_sick_1(u16 crc, u8 data, u8 prev)
{
if (crc & 0x8000)
crc = (crc << 1) ^ CRCSICKPOLY;
else
crc <<= 1;
crc ^= (data | (prev << 8));
return crc;
}
Kontrolní součet CRC-8 Dallas je 8-bitový. Používá se na sběrnici Dallas Maxim 1-Wire. Výpočet probíhá podle polynomu x^8 + x^5 + x^4 + x^0. Jeho výstup je 8-bitový a tudíž už má horší odolnost vůči vícenásobným chybám (je zvýšená šance kompenzace chyb). Pro nižší nároky na přenos se používá k zabezpečení krátkých dat s malou chybovostí. V tabulkové verzi vyžaduje tabulku o velikosti 256 bajtů. Kontrolní vzorek: "123456789" -> 0xA1, 0xFC 0x05 0x4A -> 0xF1. Výpočet 1 bajtu v pomalé verzi:
u8 crc8_dallas_slow_1(u8 crc, u8 data)
{
int i;
crc ^= data;
for (i = 8; i > 0; i--)
{
if ((crc & 1) != 0)
crc = (crc >> 1) ^ CRC8DALLAS_POLY;
else
crc >>= 1;
}
return crc;
}
CRC-8 RDallas je inverzní verze kontrolního součtu Dallas, používaná v některých zařízeních se sériovou linkou. Kontrolní vzorek: "123456789" -> 0x7C, 0xFC 0x05 0x4A -> 0x85. Výpočet 1 bajtu v pomalé verzi:
u8 crc8_rdallas_slow_1(u8 crc, u8 data)
{
int i;
u8 carry;
for (i = 8; i > 0; i--)
{
carry = (crc & 0x80);
crc <<= 1;
if ((data & 1) != 0) crc |= 1;
data >>= 1;
if (carry != 0) crc ^= CRC8RDALLAS_POLY;
}
return crc;
}
CRC-8 Sum je první z řady jednoduchých a rychlých kontrolních součtů. Jedná se o pouhý součet bajtů dat. Oproti výpočtům s polynomy má nižší odolnost proti vícenásobným chybám, ale přesto je odolnost vyšší než prostý XOR dat (kde se chyby na stejné bitový pozici navzájem kompenzují). Kontrolní vzorek: "123456789" -> 0xDD, 0xFC 0x05 0x4A -> 0x4B. Výpočet 1 bajtu:
u8 crc8_sum_1(u8 crc, u8 data)
{
return (u8)(crc + data);
}
CRC-16 Sum je součet podobně jako v předešlém případě, jen je výsledkem 16-bitové číslo. Kontrolní vzorek: "123456789" -> 0x01DD, 0xFC 0x05 0x4A -> 0x014B. Výpočet 1 bajtu:
u16 crc16_sum_1(u16 crc, u8 data)
{
return (u16)(crc + data);
}
CRC-32 Sum je opět součet dat jako předešlé 2 případy, jen s 32-bitovým výsledkem. Kontrolní vzorek: "123456789" -> 0x000001DD, 0xFC 0x05 0x4A -> 0x0000014B. Výpočet 1 bajtu:
u32 crc32_sum_1(u32 crc, u8 data)
{
return (u32)(crc + data);
}
CRC-SHT je 8-bitový kontrolní součet používaný u tepelných a vlhkostních senzorů série SHT1x a SHT7x. K dispozici je pouze tabulková verze. Výpočet je údajně podle polynomu x^8 + x^5 + x^4 + x^0, což by měl být stejný polynom jako u Dallas, ale liší se to, takže nevím. Kontrolní vzorek: "123456789" -> 0xA2, 0xFC 0x05 0x4A -> 0x10. Výpočet 1 bajtu:
u8 crc_sht_1(u8 crc, u8 data)
{
return crc_sht_tab[data ^ crc];
}
S kontrolním součtem CRC-16 XOR jsem se poprvé setkal v zařízeních Robotron, kde se používal ke kontrole obsahu pamětí EEPROM. Nepamatuji si už pořadí operací a zda rotace byla vlevo nebo vpravo, ale to by na odolnost kódu nemělo mít vliv. Domnívám se, že odolnost proti chybám bude o kousek vyšší než u prostého součtu. Výpočet je prostý a rychlý - provede se XOR s datovým bajtem a výsledek se rotuje o 1 bit. Kontrolní vzorek: "123456789" -> 0x406A, 0xFC 0x05 0x4A -> 0x0760. Výpočet 1 bajtu:
u16 crc_xor_1(u16 crc, u8 data)
{
crc ^= data;
return rol16(crc, 1);
}
Nevím jestli jsem špatně hledal, ale na netu jsem se nesetkal se statistickým vyhodnocením úspěšnosti kontrolních součtů. Do knihovny jsem doplnil i statistický test kontrolních součtů - předkládal jsem jim vzorek obsahující chybu a sledoval, zda kontrolní součet vyhodnotí vzorek jako správný. Zde jsem sestavil žebříček úspěšnosti kontrolních součtů, po provedení 1000 milionů testů:
CRC check: OK
Checked samples: 1000000K
CRC32 err=0 (0.00000%)
Pico err=0 (0.00000%)
IBM err=16353 (0.00164%)
Modbus err=16353 (0.00164%)
Kermit err=14846 (0.00148%)
DNP err=48016 (0.00480%)
XModem err=13216 (0.00132%)
CCITT err=13216 (0.00132%)
CCITTB err=13216 (0.00132%)
Sick err=325582 (0.03256%)
Dallas err=3883375 (0.38834%)
RDallas err=3883375 (0.38834%)
Sum8 err=4790763 (0.47908%)
Sum16 err=2208416 (0.22084%)
Sum32 err=2208416 (0.22084%)
SHT err=3876875 (0.38769%)
XOR err=752766 (0.07528%)
XOR8 err=5694701 (0.56947%)
XOR0 err=5661974 (0.56620%)
CCITT0 err=13216 (0.00132%)
1) CRC-32 (počet chyb=0, tj. 0.00000%)
Jak se dalo předpokládat, CRC-32 v úspěšnosti jednoznačně vede. Dokonce za celou dobu testů neudělal ani jedinou chybu. A to včetně varianty pro Raspberry Pico, zřejmě tedy mé podezření na chybu v kódu bylo nesprávné a Pico pouze generuje CRC-32 v inverzním tvaru.
2) XModem, CCITT, CCITTB (počet chyb=13216, tj. 0.00132%)
Na druhém místě je kontrolní součet CCITT a to ve všech svých 3 variantách (XModem, CCITT, CCITTB). Díky rychlé variantě výpočtu tak máme k dispozici velmi kvalitní a rychlý kontrolní součet, nenáročný na paměť (nevyžadující tabulky). Na netu jsem se setkal s názorem, že pro správnost kontrolního součtu je důležitá výchozí hodnota. Proto jsem doplnil variantu CCITT0, kde jsem jako výchozí hodnotu použil náhodně zvolené číslo 12345. Jak je vidět ze statistických výsledků, úspěšnost je stejná jako u ostatních variant CCITT, výchozí hodnota úspěšnost neovlivní.
3) Kermit (počet chyb=14846, tj. 0.00148%)
Kontrolní součet Kermit je v těsném závěsu za CCITT. Jeho úspěšnost je jen o málo horší.
4) IBM, Modbus (počet chyb=16353, tj. 0.00164%)
Na 4. místě těsně následuje CRC-16 ve variantách IBM a Modbus. Všechny tyto 3 kontrolní součty jsou 16-bitové polynomy (se 4 členy polynomu) a mají poměrně dobrou úspěšnost.
5) DNP (počet chyb=48016, tj. 0.00480%)
Na 5. místě je kontrolní součet DNP. Přestože je to 16-bitový kontrolní součet, jeho úspěšnost je značně horší než u předešlých 3 kontrolních součtů. Zřejmě proto, protože jeho polynom má 10 členů a jak se zdá, vyšší složitost polynomu je spíše na škodu a nelze ho tedy doporučit. Zřejmě si autoři neověřili úspěšnost v praxi.
6) Sick (počet chyb=325582, tj. 0.03256%)
Kontrolní součet Sick je na 6. místě. Oproti předešlým crc jeho úspěšnost již značně poklesla, ale ještě se nedostala na úroveň následujících crc. Úspěšnost odpovídá tomu, že se jedná o jakýsi hybrid mezi bitovým a bajtovým kontrolním součtem. Kompromis co do úspěšnosti a co do rychlosti, spíše s nevalným výsledkem v obou. Proto zřejmě od něj bylo později upuštěno a byl nahrazen plným CCITT.
7) XOR (počet chyb=752766, tj. 0.07528%)
Kontrolní součet XOR příjemně překvapil. Výstup je sice 16-bitový a kvalitou nemůže konkurovat 16-bitovým součtům s polynomem, ale jeho velkou předností je rychlost a jednoduchost. Je téměř stejně složitý jako prostý součet a přitom úspěšnost má mnohem vyšší. Budete-li tedy chtít snadný a rychlý kontrolní součet, nevyžadující složité výpočty s polynomy, jednoduše data XORujte a rotujte o 1 bit a získáte snadno a rychle poměrně kvalitní metodu.
8) Sum16, Sum32 (počet chyb=2208416, tj. 0.22084%)
Jednoduché součty 16 a 32 bitů vyšly lépe, než následující 8-bitové součty. To je tím, že výsledkem je 16 a 32-bitové číslo, zatímco u 8-bitových jen 8 bitů. Sum32 a Sum16 vycházejí stejně proto, protože vzorek je příliš krátký (32 bajtů) a tak součet nepřeteče 16 bitů. Kvalitou je součet 3x horší než XORování dat s rotací.
9) SHT (počet chyb=3876875, tj. 0.38769%)
8-bitový kontrolní součet SHT je na 9. místě. Přestože výpočet by měl údajně probíhat stejným polynomem jako u Dallas, chybovost je o trochu lepší.
10) Dallas, RDallas (počet chyb=3883375, tj. 0.38834%)
Kontrolní součty Dallas a RDallas jsou jen nepatrně horší než SHT. RDallas je stejně úspěšný jako Dallas, přestože pořadí bitů je opačné - zjevně tedy pořadí bitů není důležité (pořadí bitů kontrolních součtů se jinak běžně rozlišuje podle toho, zda se jedná o počítač s Big endian nebo Little endian).
11) Sum8 (počet chyb=4790763, tj. 0.47908%)
Jednoduchý bajtový součet 8 bitů je téměř na konci žebříčku. Přesto ale se dá říct, že jeho úspěšnost není o moc horší než 8-bitové výpočty s polynomem. Výhodou je jednoduchost a rychlost a proto může být vážným konkurentem 8-bitových kontrolních součtů s polynomem.
12) XOR0 (počet chyb=5661974, tj. 0.56620%)
Jak se dalo předpokládat, prostý XOR dat (bez rotace) vyšel hůře než jednoduchý bajtový součet. Tento výpočet jsem doplnil jen na zkoušku a porovnání úspěšnosti. Výstupem je 8-bitový CRC. Chyby na stejných bitových pozicích se kompenzují a proto je výsledek horší než u prostého součtu.
13) XOR8 (počet chyb=5694701, tj. 0.56947%)
XOR8 je opět doplněk na zkoušku "mimo pořadí". Opět se s daty dělá XOR a bitová rotace, ale pouze v rámci 8 bitů. Výsledek je horší než u prostého 8-bitového součtu, což je překvapivé. Vzhledem k úspěšnosti 16-bitové XOR verze bych čekal lepší výsledek než prostý součet.
Z uvedených výsledků lze učinit následující závěr:
Výpočty kontrolních součtů si můžete zkontrolovat v online kalkulátoru https://www.lammertbies.nl/comm/info/crc-calculation .
Zde v knihovně je k dispozici překlad jednak pro MS Visual Studio 2005 a jednak pro Raspberry Pico - a to ve variantě pro UART port a pro USB virtuální COM port (včetně plného překladového prostředí, stačí přidat GCC ARM). V knihovně se provádí jednak ověření správnosti výpočtu kontrolních součtů a jednak statistické vyhodnocení jejich úspěšnosti. Samotná CRC knihovna se nachází v souborech cpp.*.
Odkaz ke stažení knihovny: CheckSum_src.zip
Byl jsem upozorněn na možnost používat zkrácenou tabulku jen pro 4 bity (Small Table CRC). Výpočet je jen o málo pomalejší než s plnou tabulkou, ale tabulka zabírá jen 1/16 původní velikosti. Lze takto počítat rychle CRC i v procesorech s malou pamětí. https://wiki.wxwidgets.org/Development:_Small_Table_CRC
Miroslav Němeček