CRC: dělení, které se dělá posunem a XORem
CRC vypadá jako magie a je to zbytek po dělení. Zpráva se vezme jako jedno obrovské číslo, vydělí se dohodnutým číslem a co zbyde, to se pošle s ní. Příjemce udělá totéž a porovná.
Jediná zvláštnost je, že se dělí v aritmetice bez přenosů — odčítání je XOR. Díky tomu je celý výpočet posuvný registr a pár hradel, což v roce 1961, kdy to Peterson popsal, rozhodovalo.
- 1101 0011
Bajty za sebou, bez ohledu na to, co znamenají. CRC nezajímá obsah.
- 1101 0011 0000 0000
Tím se udělá místo, kam zbytek nakonec padne.
- 1 0000 0111 ← x⁸ + x² + x + 1
Odčítání je XOR. Žádné výpůjčky, žádné přenosy. Proto je to v křemíku jen posuvný registr a pár hradel.
- 1101 0011 1111 0100
Připojí se na konec zprávy. Nic víc se s ním nedělá.
- (zpráva · x8 + zbytek) mod P = 0
Příjemce projede celou zprávu i s kontrolou. Když vyjde nula, je zpráva dělitelná polynomem — a to je přesně to, co se odesláním zařídilo.
Polynom je jen jiný zápis téhož čísla
Když se řekne „polynom x⁸ + x² + x + 1“, myslí se tím číslo 1 0000 0111: jednička
tam, kde je mocnina přítomná. Nic víc v tom není. Zvyk psát to jako polynom pochází z teorie, která
tomu dala vlastnosti — ale počítá se s tím jako s bitovým vzorkem.
Šest parametrů, které musí obě strany znát
„CRC-16“ není zadání. Existuje jich několik a liší se parametry, které vypadají jako implementační detail a nejsou:
| parametr | co znamená |
|---|---|
width | kolik bitů má výsledek |
poly | ten dělitel |
init | čím je registr naplněný na začátku — nenulová hodnota chytí i vedoucí nuly |
refin, refout | jestli se bity zrcadlí; viz kapitola 2, LSB napřed |
xorout | čím se výsledek nakonec proXORuje |
Proč init není nula: s nulovým počátečním
registrem má zpráva 00 00 12 34 stejné CRC jako 12 34. Vedoucí nuly nic
nezmění, protože nula dělená čímkoli je nula. Naplnit registr jedničkami to spraví, a je to jediný
důvod, proč to tam je.
Že to není teorie: kontrolní hodnota
Ke každé sadě parametrů se publikuje, co má vyjít pro řetězec "123456789". Je to
tabulková hodnota v pravém slova smyslu — a testy v repu jí kontrolují všech devět sad, které tahle
labka zná. CRC-32 se navíc porovnává se zlib, tedy s implementací, kterou psal někdo
jiný.
| název | polynom | kontrola „123456789“ |
|---|---|---|
| CRC-8 (SMBus) | 0x07 | 0xF4 |
| CRC-16/CCITT-FALSE | 0x1021 | 0x29B1 |
| CRC-16/MODBUS | 0x8005 | 0x4B37 |
| CRC-15/CAN | 0x4599 | 0x059E |
| CRC-32 (Ethernet, ZIP) | 0x04C11DB7 | 0xCBF43926 |