Developing.ru

Document: FSC-0060
Version: 001
Date: 08-Mar-1992




Calculation and Usage of CRC's
Frank van der Loos
2:285/305.4




Status of this document:

This FSC contains information of value to the general FidoNet(r)
community. Distribution of this document is unlimited.

Fido and FidoNet are registered marks of Tom Jennings and Fido
Software.




This document is written by :

Frank van der Loos
Torenstraat 123
3311 TR Dordrecht
The Netherlands (Europe)
FIDO mail : 2:285/305.4

Thanx to :
Willem van Pelt
FIDO mail : 2:285/305
- for giving me a mail-box :-))
- for telling me some theoretical stuff about CRC's

Richard Faasen (Yeaahh "Pfjew" he says)
FIDO mail : 2:285/311
- for giving me some CRC programs

Arie Ballegooyen
FIDO mail : 2:283/300
- for giving me all the original FTS & FSC doc's



This doument is a DOC in which the CRC encoding and some usages of this
encoding are explained. Also some routines are included. In some of the
FTS & FTC doc's the encoding is very badly and sometimes wrong explained
this will take a lot of time when you are planning to program a CRC encoding
routine instead of using a routine which is made by someone. I will also
include some routines and also the scheme to make a CRC routine so you
can easily make a CRC check routine yourself in your program.

What is a CRC :

Simply explained a CRC is a division and the remainder is the CRC value.
I think this example will help you to understand it :

1011 / 10011101 \
1011
----
1011
1011
----
001 (This is the CRC value)

Look familiar to division as you are used to learn at school. But there
are some differences.

When substracting a bit the following table is used :
0 - 0 = 0
0 - 1 = 1
1 - 0 = 1
1 - 1 = 0

There is a function called XOR which will use this table. When you are
substracting 0-1 = 1 then there is a shortage and normally you will take
a higher bit to complete to substraction.

234
91 -
-----
143

You cutted 200 to 100 because 3-9 = negative. But with the CRC you
DO NOT use this !!!

The divisor used with CRC encoding is a divisor with 1 bit more then
de actual CRC. This is explained by the remainder which is always 1 bit
less then the divisor. If not then you can divide it a time again, not ?

Now you have to perform dividing on a row of char's and you can't do that
without a special trick. What you do is shifting all the bits one by one
into the CRCvalue and then checking if you can perform a division. Lets
have a look at this example :

1011 / 10011101 \

We are gonna use a CRC of 3 bits (the highest bit is always cutted).
The first bit is the checkbit. We can divide if this bit is 1. In that
case the value is big enough to divide.


x 100 no we can not divide
perform a shift to left and shift in the next bit.
1 001 yes we can divide
divide it by 1011
0 010 the divided value (XOR'ed)
we can not divide so shift to left and shift in the next bit.
0 101 the shifted value + shifted bit.
we can not divide so shift to left and shift in the next bit.
1 011 the shifted value + shifted bit.
divide it by 1011
0 000 the divied value (XOR'ed)
we can not divide it so shift to left and shift in the next bit.
0 000 the shifted value + shifted bit.
we can not divide it so shift to left and shift in the next bit.
0 001 the shifted value + shifted bit.
we can not divide it so shift to left and shift in the next bit.
OOOppps sorry the bits are gone so this is the remainder
001 The 3 bit remainder (is 1 less then the divisor)


0 101 no we can not divide so
no we can not divide
shift to left and take the next bit.
1 011 yes we can divide
0 000 the divided value (XOR'ed)
0 001 oke we have shifted again to left and took again the next
bit.
0 010 again
0 101 again

Compare it to the division performed at page 1 and you will see the result
is the same. But this method is more comfortable for computers. In fact
it is the same way to divide but we as humans can take more bits and we
can see direct if it is possible to divide and the computer can not. But if
we have to check every bit it will take a lot of time to put in every time
1 bit by bit. Now luckily for you that is not neccesairy. The computer and
also your program can shift in byte per byte. But then you have to try the
division 8 times every time you have putted in a byte. And the byte you have
put in has to fit in your CRC. So when you have a CRC which is 2 bits in
length than it won't fit of course. Bu generally a 16 bit CRC is used and
even CRC32 are now in use. When in the near future CRC64 are used I'm not
surprised. Oke now to the computuer programming stuff. Here is a table with
a good method to implement a CRC16 in any language. After this a program
is stated with all the documentation in it. Remember a CRC16 has a 17bit
divisor. Bit 16 (As you know we start at bit 0) is 1. When not we have again
a smaller divisor.

CRC : wordvalue

{ This routine has to be executed 8 times }
IF CRC bit 15 = 1
then
shift left 1, divide by divisor (16 bits)
else
shift left 1, {do not divide cause we can't}

{After this put in the next byte}
CRC = CRC + inputbyte

{end of this routine}

Simple isn't it. Now for the more experienced programmers a sample in
pascal at the next page.


inpbyte = input byte for CRC
oldCRC = old crc value
divisor = the least 16 bits of the divisor string

Function CRC16 ( inpbyte : byte, oldCRC : word, divisor : word ) : word ;

var
tel : word;
temp : word; {A simple variable to use to store the CRC)

begin
temp := oldCRC;
for tel := 1 to 8 do
begin

If (temp and $8000)= $8000
then
begin
temp := temp shl 1;
temp := temp xor divisor;
end
else
begin
temp := temp shl 1;
end;

{ Now we have to put in the next byte }

temp := temp xor inpbyte;

CRC16 := temp;

end;

{End of routine}

This routine is easily to expand to CRC32. In that case you have to expand
your divisor and temp and CRC function to LONG value's.

Some additional information about CRC's :

CRC16 divisor = $1021 ( + bit 16 = $3021 )
The CRC16 feed value (when you first call the CRC routine) is $0000
CRC32 divisor = $77073096 ( + bit 32 = $17707306 )
The CRC32 feed value (when you first call the CRC routine) is $FFFFFFFF