![]() |
![]() |
![]() |
![]() |
![]() |
Here is an example, written in Free Pascal, that explains the CRC algorithm . The program shows the partial results of each polynomial division. Here is also the Pascal source code of a function that calculate CRC-16 over a byte.
File: crc_calculator.pas
//CRC generator/verifier algorithm demostration: //it explains the partial results of each division //Copyleft Fabio Zorba var cmd, message, polynomial, result, log : string; i, pos : integer; function xor_string (str1, str2 : string) : string; var tmp : string; i : integer; begin tmp := ''; for i := 1 to length (str1) do begin if str1 [i] = str2 [i] then tmp := tmp + '0' else tmp := tmp + '1'; end; xor_string := tmp; end; procedure get_only_01 (var str : string); var result : string; i : integer; begin result := ''; for i := 1 to length (str) do if (str [i] = '0') or (str [i] = '1') then result := result + str [i]; str := result; end; procedure shift_left_string (var str : string); var i : integer; begin for i := 1 to length (str)-1 do str [i] := str [i+1]; str [length (str)] := '0'; end; begin if paramcount < 3 then begin writeln ('Usage:'); writeln ('crc_calculator G|V message polynomial'); writeln ('example:'); writeln ('generate crc --> crc_calculator G 110101 101'); writeln ('check message --> crc_calculator V 11010111 101'); exit; end; cmd := upcase (paramstr (1)); message := paramstr (2); polynomial := paramstr (3); if (cmd <> 'G') and (cmd <> 'V') then begin writeln ('Please choose:'); writeln ('G --> generate crc'); writeln ('V --> verify message'); exit; end; //remove characters that not are '0' or '1' get_only_01 (message); get_only_01 (polynomial); if cmd = 'G' then //append zeroes to binary message for i := 1 to length (polynomial)-1 do message := message + '0'; result := ''; for i := 1 to length (polynomial) do result := result + message [i]; pos := length (polynomial); writeln (message); while pos <= length (message) do begin log := '<-- shift only '; if result [1] = '1' then log := '<-- (' + result + ' xor ' + polynomial + ') <-- shift '; if result [1] = '1' then result := xor_string (result, polynomial); pos := pos + 1; shift_left_string (result); if pos <= length (message) then result [length(result)] := message [pos] //remove last bit if end of division else result [0] := char (ord (result [0])-1); for i := pos downto length (polynomial)+1 do write ('_'); writeln (result,' ',log,'+ ',message [pos]); end; writeln ('crc: ',result); end.
Output example:
$ ./crc_calculator G 1000_1111 1_1000_0000_0000_0101 100011110000000000000000 _10011110000001010 <-- (10001111000000000 xor 11000000000000101) <-- shift + 0 __10111100000011110 <-- (10011110000001010 xor 11000000000000101) <-- shift + 0 ___11111000000110110 <-- (10111100000011110 xor 11000000000000101) <-- shift + 0 ____01110000001100110 <-- (11111000000110110 xor 11000000000000101) <-- shift + 0 _____11100000011001100 <-- shift only + 0 ______01000000110010010 <-- (11100000011001100 xor 11000000000000101) <-- shift + 0 _______10000001100100100 <-- shift only + 0 ________1000001100100001 <-- (10000001100100100 xor 11000000000000101) <-- shift + crc: 1000001100100001 bash-4.1$ bash-4.1$ bash-4.1$ ./crc_calculator V 1000_1111_1000001100100001 1_1000_0000_0000_0101 100011111000001100100001 _10011111000000110 <-- (10001111100000110 xor 11000000000000101) <-- shift + 0 __10111110000000111 <-- (10011111000000110 xor 11000000000000101) <-- shift + 1 ___11111100000000100 <-- (10111110000000111 xor 11000000000000101) <-- shift + 0 ____01111000000000010 <-- (11111100000000100 xor 11000000000000101) <-- shift + 0 _____11110000000000100 <-- shift only + 0 ______01100000000000010 <-- (11110000000000100 xor 11000000000000101) <-- shift + 0 _______11000000000000101 <-- shift only + 1 ________0000000000000000 <-- (11000000000000101 xor 11000000000000101) <-- shift + 0 crc: 0000000000000000
Write a code that perform the algorithm don't seems so simple, there are some "tricks", in particular the "trick" that shifts the CRC word before perform a XOR with the polynomial divisor (to drop the MSB of divisor, that will drop anyhow due the left shift). Here the code:
File: crc16.pas
//CRC-16 over 1 byte function //Copyleft Fabio Zorba 2013 const crc16_polynom = $8005; var data : byte; function ByteCrc16(data : byte) : word; var crc : word; i : integer; begin crc := data; crc := crc shl 8; //crc = data + 0000_0000 //8 bit in a byte for i := 1 to 8 do begin if crc and $8000 <> 0 then begin crc := crc shl 1; //drop MSB bit, so drop the MSB polynom 0x1_8005 crc := crc xor crc16_polynom; end else crc := crc shl 1; end; ByteCrc16 := crc; end; begin val (paramstr(1), data); //input 8 bit data write (ByteCrc16(data)); //output 16 bit CRC end.
To test:
bash-4.1$ echo "obase=16; `./crc16 127`" | bc 8101 bash-4.1$