Embedded C programming Tutorial , Keil C ide , microsoftware.gr
Keil CRC and CAN BUS codes.
1. Shift led left
2.It's time for DAVE! <7/6/13>
3.Capture/Compare unit 6
6.Analog converter
7.Memory manipulation routines
8. Recursion
9.Understanding interrupt priorities using CAPCOM2 module
10. POINTERS TO FUNCTION <4/7/13>,<4/28/13>
11.Memory models, memory types
12. The heap , part 1
13. The heap , part 2
14. The heap , part 3
15. Structure example
16. Nested structures, Array of structures.
17. Passing array of structures to function using pointers.<1/5/13>
18. Self Referential Structures
20. Linked list example
21. Circular linked list
22. Union example
23. Enumeration example
24. Watchdog timer example
25. Void pointer example <7/4/13>
26. The sieve of Eratosthenes
27. The stack
28. Union and bitfields as flags example. <6/23/13>
29. Look up table example. <8/11/13>
30. Seven segment display multiplexing -four digits with dot- example
31. LCD character display example - JHD162A
32. Hash table introduction example <8/27/14>
33. Array of Linked Lists example
34. Array of Linked lists-more functions included.
35. Hash table construction,searching and printing.
36. Fininte state machines- a first approach.
37. Finite state machines- two events example.
38. SPI port and an AT25128 serial eeprom hardware.
40. Definite Integral Calculator for Scientists, Engineers...
41 .Hamming distance of a CRC polynomial
42. Linux play starting.
43. Galois GF(2^4) Finite Field
44. Construct your own time triggered real time operating system.


The problem : how to check that a received message is correct and it is not disturbed? (due to electronic noise.)

For example having the message  04 29 06 a first idea is to calculate the sum of all of the bytes of the message that is sum S=39 and adding the sum at the end of the message.
Message with checksum: 04 29 06 39
Reciever has to add the bytes of the message and to compare the sum with the last byte of the message simply.

But if the message was disturbed like 03 29 07 then S=39, correct!

A much more sensitive and safe methode, as mathematics proove, is to see the message as a polynomial of x modulo 2, the coeficients of the polynomial will be 0 or 1 only.


Our message is 0000 0011 0010 1001 0000 0111 so we can see it as the polynomial :

Now having a fix polynomial, say D= x^6+x^3+x^2+x+1 or the 0100 1111 that is known by the transmiter and reciever
and dividing M by D we find the remainder: R=x^2 or  0100.
1001111 ) 110010100100000111

Modulo2 addition, subtraction ,multiplication and division calculator:
If our message was the 0000 0011 0010 1001 0000 0110 or the polynomial M=x^17+x^16+x^13+x^11+x^8+x^2+x then dividing
it by D= x^6+x^3+x^2+x+1 gives R=x^2+1 or  0101
For M=x^17+x^16+x^13+x^11+x^8+x^2+1  or
0000 0011 0010 1001 0000 0100 we have R=x^2+x+1 or  0111
for 0000 0011 0010 1001 0100 0000 we have   R=1100
sensitive process !
1001111 ) 110010100101000000

Now subtracting the Remainder (The CRC checksum) from the original message (subtraction and addition are the same at modulo2 arithmetic ,Modulo2 addition is a simple XORing) we have:
0000 0011 0010 1001 0100 0000 XOR 00001100 =110010100101001100
and dividing this new polynomial    110010100101001100   by
D= x^6+x^3+x^2+x+1 or the 0100 1111 we have:
R=0   Bingo!!!

It is important to know that the Arithmetic of CRC checksum is the Arithmetic of the Field of Polynomials Modulo2 and that this Arithmetic is different than the Arithmetic of the Set of Binary Numbers !

Next, watch an interesting property of CRC  with an example:

Our message is  the:
1100100000101101 or the x15+x14+x11+x5+x3+x2+1 =(x15+x14+x11)+ (x5+x3+x2+1)

and our divisor is   01001111 or the x6+x3+x2+x+1

THE REMAINDER OF THE DIVISION  :  1100100000101101/01001111 is  x^2+x  or R=110 ,

x15+x14+x11   is the  1100100000000000
THE REMAINDER 1100100000000000/01001111   is  R1=101011

x5+x3+x2+1    is the      00101101
THE REMAINDER  00101101/01001111   is  R2=101101

and  R1 XOR R2 = R   nice !!!

(the largest power of x  at the remainders R1 and R2 is less than the power of the divisor--in our case 6-- so  the power of the polynomial R1 XOR  R2 is less than 6)

We can proove the above result easily writting some Algebra:
Say M= x15+x14+x11+x5+x3+x2+1 and D= x6+x3+x2+x+1

M1= x15+x14+x11  and  M2= x5+x3+x2+1 so,

M1= D*Q1+R1  and  M2= D*Q2+R2  Q1 and Q2 are the unknown quotients (nobody gives care to them) .

M=Μ1+Μ2=D*(Q1+Q2)+(R1+R2), since GF(2) field is commutative.

Also we have:

M1+R2= D*Q1+(R2+R1)= D*Q1+R 
beautyfull !!!

in words: the CRC of M= the CRC of (M1 XOR (CRC of M2) )

M=1100100000101101 , M1= 1100100000000000 , M2=00101101 , D=01001111

CRC OF M2=101101
M1 XOR  (CRC of M2)= 1100100000000000 XOR 101101 =1100100000101101 
CRC of (M1 XOR (CRC of M2) ) =110

An other way to proove it is this:
We have CRC (MI+CRC M2)= CRC(M1+R2)= CRC M1+CRC R2 = CRC(M-M2)+CRC R2=
CRC (M+M2)+ R2= CRC M+ CRC M2 +R2= CRC M + R2+ R2= CRC M.

Since in GF(2) addition and subtraction of polynomials are idendical and F(X)+F(X)=0 polynomial.

Remember that our arithmetic is the arithmetic of the field of polynomials modulo 2, called Galois field of polynomials modulo 2 , GF(2),  and XORing is the addition.

The equation R1 XOR R2 =R above gives to us the permition to calculate tje CRC checksum of our message byte to byte.

so our message  1100100000101101 separated to two bytes :
11001000   00101101

11001000 XOR 1111111111111111 = 1111111100110111  (1111111111111111 Is 16 bits long).

1111111100110111 XOR 1111111111111111 =0000000011001000

SIFTING LEFT 8 PLACES THE 0000000011001000 WE HAVE :  1100100000000000     that is the polynomial  x15+x14+x11 .

A shift left and shift right calculator is at:

A "trick" that you
,may be, have seen at various pages is the following:
Our message is the:

1100100000101101 or the x15+x14+x11+x5+x3+x2+1
and our CRC generator is the   01001111 or the x6+x3+x2+x+1 ( its degree is 6 ).

Adding 6 zeros at the original message we have a new polynomial:


dividing it by  01001111  we find the remainder R=100010  (it is not the CRC of
1100100000101101 ).

Subtracting this remainder from the 1100100000101101000000 we have:

1100100000101101000000 XOR  100010 =1100100000101101100010   (1)

The polynomial 1100100000101101100010 is our original message  1100100000101101
"appended" at its end the CRC of the  different polynomial 
1100100000101101000000  , and the remainder of the division  

1100100000101101100010 /01001111 is ofcourse zero due to (1).

The maximun degree of x at the remainder of a division by x6+x3+x2+x+1 is 5,  it will be a polynomial 6 bits long, so the minimun number of zeros that you have to append at the original message in order to save space to "append" the remainder of the new polynomial that you produced ,in our case the  100010 , is 6, but as you understand you can append more than 6 zeros making your own design. Appending n-zeros at the end of a message it is equivalent with the multiplication of the polynomial of the original message by x^n.

Danger !
Do not mixing the Arithmetic of Galois field  GF(2)  with the arithmetic of the set of binary numbers. If you are mixing your results will be ...so nice !

Exercise:Proove that you can calculate the CRC of the above message ...bit by bit.

It is time to exam in detail the procedure of the division modulo2, but we have to proove the following simple theorem firstly:

given: a polynomial p of degree k, a divisor d of degree l  ,we are looking for two polynomials q and r such that:

p=d*q+r , where the maximun possible degree of q will be k-l and the degree of r will be less than l.

Adding the polynomial (x^(k-l)*d we have:

p+(x^(k-l))*d=d*(x^(k-l)+q)+r   since GF(2) is distributive.

in words: the polynomial p+(x^(k-l))*d  diveded by d gives as a remainder the same r for that we are searching for. The degree of the  new polynomial p+(x^(k-l))*d will be less than k and continue the process  till to find a polynomial r having degree less than of d. This r will be the final remainder. Multiplication of d by x^(k-l) it is equivalent to append k-l zeros at the end of d.
Applying the above to our example message we have:

Our message is M=1100100000101101 or the x15+x14+x11+x5+x3+x2+1
and our CRC generator is the D=01001111 or the x6+x3+x2+x+1 ( its degree is 6 ).
Using polynomial calculator and writing down the division process step by step and in detail ,using the above proven theorem , we have:

                                          1100100000101101   Message
                                    1001111000000000    it is D* x^(15-6)
                      100111100000000   it is D*x^8 ....
                              1001111000000     it is the D*X^6 .

100111100000       D*X^5 ...
                                1001111000        D*X^3...
                                   100111100        D*X^2....





Observe , using the calculator,  that all the red polynomials divided by D all give remainder 110.

The above procedure of the calculation of CRC of a message or file by sequential XORings with polynomials of degree smaller and smaller than k includes a great advantage.There is no need to have all the message or the big file in a register of the microcontroller. We have to use the l  bits only (l is the degree of the generator polynomial) of a register at each one of the sequential steps. The size in bits of the registers of a microcontroller is limited.
Manufactures of microcontroller boards prefer to enclose big files inside of memory chips like an AT29C020 flash memory or an AT28HC256 EEPROM memory chip and outside of the microcontroller integrated circuit. Manunacturers are able to modify these files throught internet  with the help of a bootloader included inside of the software of the board, re-calculating and a new CRC.

As you see the procedure of the calculation of a CRC is  sequential  XORings
  starting from the most significant bit (MSB) of a byte and going to the least significant bit (LSB), the MSB of the next byte is coming... (fetching next bits  are simple sifts of the byte  that is fetched at r1).

Using an 8 bit register r1 of a microcontoller  fetching here  byte by byte  our file and a register r2 to save our generator polynomial to do XORings we have:

                                                           r1----->right shift
... byte of file ----------------------->   bit7.....................bit0

generator poly----------------------->  bit7......................bit0


Observe that bytes are inserted to the registers r1 and r2 from the left side and the content of r1 has to be sifted right to continue the procedure of calculation.
Observe also that the MSB bit will occupy the place of bit0.
How to do it? Using a ...mirror? No, but reversing the order of bits of the byte, at both of r1 and r2.

A simple way to reverse a byte is to use a table look up like:

static const unsigned char reflect [] =
  0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
  0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
  0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
  0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
  0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
  0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
  0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
  0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
  0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
  0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
  0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
  0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
  0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
  0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
  0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
  0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF

At the followings change the word "reverse" with the word "reflect" !

For example the reverse of  0000 0001  (0x01)  is the 1000 0000 (0x80)  .
The final calculated CRC has to be reversed.

                           byte 1              byte 2
Our message is M=11001000   00101101

and our CRC generator is the D=  1001111

We will calculate the checksum byte by byte in steps , using reversed bytes in r1 and r2 registers undrer the law :
' when bit0 of r1 is 0 then shift 1 bit right, if bit0 is 1 then shift 1 bit right and after it XOR ,result in r1'

we have: byte 1 reversed  00010011 ,  byte 2 reversed  10110100
             D reversed  111100)1 in r2 we have to put only the part 111100

we will count 8-N (about N see below at C code)  right shits total and finished.

r1    00010011 --- 1-->00 001001 XOR r2= 00110101--2->00 011010
XOR r2=00 100110


C code example is coming.

Special topics about crc. <21/March/2015>
In order to exame the reliability of crc method we have to introduce the term of the "error polynomial" e. Polynomial e is a polynomial that is added to the original message m, so the corrupted message is m+e. As you see the places of 1 in e correspond to bit changes in m. We have the following cases:
Case 1, you have bad luck and crc(e)=0. So,
Denoting crc(m)=r we have crc(m+e)=r  ok!
You can find plenty of e polynomials having crc(e)=0.
Good generator poly g are selected in such a way that binomials of the form b=x^i + x^j to be not divisible by g for small i and j, b will be divisible by g for long i and j , for example for a 16 bit generator poly i and j must be greater than 2^16. Then crc(m+b) is not equal to r and the error is caught.
Case 2, you have much more bad luck,  sending to the receiver m and r at two separate steps. It , may be, was happend this:
At first step receiver receives m+e. (2)
At the next following second step receiver receives the crc remainder (r+ crc e ).  (3)
We have: crc(m+e)=crc m +crc e =r+ crc e  ok! 
As you observe it is safe to send m and crc m in only only step , sending m+r at once, in this case crc (m+r)=0 but crc (m+r+e) is not zero.
If the order of generator poly is k we can append k zeros to m , in order to bits of m and r to be not overwiten as explained.

server and my editor problems ,sorry.!!!

C code here, one byte long message.

We will calculate the checksum  in steps , using reversed bytes in r1 and r2 registers undrer the law :
' when bit0 of r1 is 0 then shift 1 bit right, if bit0 is 1 then shift 1 bit right and after it XOR  and the result stay in r1'

unsigned char byte = 0xfd;  //you can change the divitend here!!!- 
                                     //  dividend,the message,   is 0xfd


// byte       remainder  |  generator poly | used reversed generator poly| PAEAMETERS: j    N

// 0x9f     0x03           0x1d              0x0b                             3   4
// 0xaf     0x09               '                 '                                 '     '
// 0xc9     0x06              '                  '                                 '     '
// 0xc8     0x07              '                  '                                 '     '
// 0x0c     0x0c               '                  '                                 '     '
// 0x0d     0x0d              '                  '                                  '     '
// 0x1d     0x1d           0x3d               0x17                           2    5
// 0xf5      0x01             '                    '                                '      '
// 0xf4      0x00             '                    '                                '      '
// 0xfd      0x09             '                    '                                '      '
// 0xa7     0x14             '                     '                               '      ' 
// 0xa5     0x16             '                     '                               '      '
// 0xb7     0x04             '                     '                               '      '
// 0xd3     0x1a             '                     '

/* The program uses two parameters j and N depended upon the number of bits of the used generator polynomial exclusively,
at STAGE (1)  AND STAGE (2) of the crc8() function below.
The above results agree with the results of the polynomial calculator of GF(2) of this article  above*/

The C function that we will use to find the crc is the:

unsigned char crc8(unsigned char byte) {
int j=0;

unsigned char crc;

unsigned char d=0x17; // d the rversed generator poly, the reversed divisor.

/* you can change the divisor here!!!- your crc generator polynomial.
for example if the generator poly is 0x3d, we don't need the MSB that is always 1 because this  '1'  is always XORed with the 'first 1' of an intermediate polynomial of the procedure giving zero - 001(1 1101- so reversing it ,in the register of the generator poly we will have the 000 1011 1 = 0x17 -so we will use in the divisor's register the 0x17 . (PARAMETER N= 5 , the number of USED bits of the divisor).
generator poly 0x1d , in register of divisor use 0x0b ,N=4
generator poly 0x3d , in register of divisor use 0x17 , N=5 */



// STAGE (1)

for (j = 0;j <=2;j++ )

/* Attention here if you will change the divisor!!!
PARAMETER j controls the total number of right sfifts to find a polynomial having degree less than the degree of the devisor, total number of right shifts = 8- N ( N=number of USED bits of the divisor).we need 3 right shifts total, so j=2 .

if (CRC0) {

else crc=crc>>1;


} ;


// STAGE (2)
// removing unwanted appended zeros after reversing crc

// Attention here if you will change the divisor!!!
// to present the reversed remainder in a right way removing
// the unwanted zeros appented to it after reversing it,
// we have to right shift it , controlling the number of right shifts (RS),
//that is RS = 8- (number of N USED bits of the divisor),
// for example if N=5 then RS=3

printf ("%c ", crc); // you can watch the final crc at the watch window of your compiler.

return crc;

// end of function.

where CRC0 is:

#define CRC0 ((T*)(&(crc)))->bit0


typedef  struct
unsigned int bit0 : 1;
unsigned int bit1 : 1;
unsigned int bit2 : 1;
unsigned int bit3 : 1;
unsigned int bit4 : 1;
unsigned int bit5 : 1;
unsigned int bit6 : 1;
unsigned int bit7 : 1;
unsigned int bit8 : 1;
unsigned int bit9 : 1;
unsigned int bit10 : 1;
unsigned int bit11 : 1;

unsigned in bit15 :1;
} T;

You can watch the result at the watch window of your compiler.

At the above C code The degree of the polynomial that represent our message is seven -it is an
8-bit long polynomial -and the maximum degree of our generator poly is seven (8 bit long polynomial). If you have longer messages and longer generator polynomials (for example an eight degree generator poly-9 bits long poly), then you need...more space.
You can use unsigned integers instead of unsigned characters but the philosophy of calculation remains the ...same.

For more than one byte long message we have to append next coming bits of the next reversed byte at the end of the crc previously calculated, continueing the procedure, and reversing the final crc at the end.

Exercise: Rewrite the above program without reversing the contents of r1 and r2 registers. Message and generator poly will be inserted at r1 and r2 from the right. You have to do left shifts of r1 now. Your generator poly will be the 0x3d but you have to calculate the right value that you will put in r2 (it is not 0x3d, it is 0xe8). No need to reverse the final CRC  but ...
#define CRC7 ((T*)(&(crc)))->bit7

and the function is:

unsigned char crc8(unsigned char byte) {
int j=0;
unsigned char crc;

unsigned char d=0xe8; // d the  poly, the  divisor.
for (j = 0;j <=2;j++ )
if (CRC7) {
else crc=crc<<1;


} ;

return crc;


Example using 16 bit long registers. We will use the stantard crc8 generator x8+x7+x6+x4+x2+1 or 0x1d5 . In C code the   1) 1101 0101 0000  0000   or 0xd500 (used number of bits N=8, so j=16-8-1, 8 left shits total)  and try to find the CRC of 0xca07 message.

#define CRC15  ((T*)(&(crc)))->bit15

unsigned int message = 0xca07;
unsigned int crc;


unsigned int crc8(unsigned int byte) {
int j=0;

unsigned int d=0xd500; // d the poly, the divisor.
for (j = 0;j <=7;j++ )

if (CRC15) {
else crc=crc<<1;

return crc;


The remainder is 0x0023 in agreement to polynomial calculator.

Next, we will try a 3 byte long message, giving the triger for a look up table driven
CRC implementation.

*Professor of Informatic at the University of Athens told me on the  far past to follow university career about Informatic, but I choose  career about Physics!


CRC look up table driven impementation.

The speed of crc calculation is very important at critical application, for example at the microcontroller board that controls the engine or the ABS module of  your car.
Microcontroller has to check many times per second the content of an eeprom , checking for corrupted data.
A fast algorithm is the crc look up table driven algorithm.
When you try to calculate the crc of 0xca07 with generator poly the 0x1d5 observe that:

0xca07=0xca00 xor 0x0007

we have crc (0xca00)=0x0024

and crc(0xca07)= 0x0024 xor 0x0007=0x0023

CRC of Quantities of the form XX00 can be precalculated and saved in a look up table and using the quantity XX as an offset at the look up table.

An algo that makes this 256 long table is:

static unsigned char table [256];
unsigned int i ,j t;

for (i=0;i<256;i++)

Try now to calculate the crc8 of the message  0xca  0x07  0x3a

we have  table[0xca]=0x24 , 0x24 xor 0x07=0x23 , table[0x23]=0x0e,  0x0e xor  0x3a= 0x34

the final crc8, it is correct in agreement to polynomial calculator.

why this?

continued with the explanation...
Prove that given two polynomials A and B ,order of B is k and crc(A)=R THEN:

Observe that polynomial AB=A*(X^(k+1))+B  and polynomial RB=R*(X^(k+1))+B,     +=xor,

                                                      <---- z- zeros---->
A  bit of exactness:
Consider the polynomial P=A0...       ...0...          ...0C , where A and C are polynamials, the order of C  is k, C is k+1 bits long, and  crc(A)=R. A polynomial begins always with a 1.
Denoting B=0...    ...0...     ...0C  we have:
A=d*q+R---->A*x^(z+k+1)+C=d*q*x^(z+k+1)+ R*x^(z+k+1)+C=d*q*x^(z+k+1) +RB .

----> P= d*q*x^(z+k+1) +RB

So, crc(P)=crc(RB) again.

Generally speaking the quantity B is  not always a polynomial but it is a quantity constructed from 0 and 1.

This is the secret encrypted under the remainders of polynomials modoulo2: connect!

We are able now to write the equation: crc(0xca073a)= table[table[0xca]xor0x07] xor 0x3a.
A function that can calculate the crc of our message m  unsigned char m[3]={0xca,0x07,0x3a};
is the:


unsigned char v; // v is the crc

unsigned char crc_calculation (void) {
for (i=1;i<=2;i++){
return v;

result is v=0x34 in agreement to polynomial calculator.

So, what we have in our hand for the moment is:

1. A function that calculates the crc using modoulo2 division--generator poly is d=0x1d5--,as in paragraph 1 above.
2. A function that makes a crc look up table , as in paragraph 2 above.
3. A function that calculates the crc using a look up table as in paragraph 3 above , but lets go to give a general form to it in order to be able to accept strings. The general form is:

unsigned char v; // v is the crc 

unsigned char crc_calculation (unsigned char* x)  {

v= *x;
for (i=1; i<= strlen(x)-1 ; i++) {
v=table[v] ^ *(x+i);
return v;


calling this function for the string unsigned char *st ="12345";
we have:  crc_calculation(st)=0xbf in agreement to polynomial calculator.

Remember that the end of a string is denoted by the NULL character \0, hexadecimal 0x00,
so if you write : for (i=1; i<=strlen(x) ; i++)  then the crc= 0x64, again in agreement to polynomial calculator.

...And take out your fear about CRC checksum, it is much more easier than the 

 Monte Carlo Statistics
   of Nuclear Physics ...

Searching various pages in web about crc I remembered a mistake that I had done driving my car:
Following the wrong way, a way that after some hundred of meters was ended. Astonished, I observed many cars that followed me !

Initial value in crc register. <21/March/2015>

Given the message unsigned char a[6]={0x00,0x31,0x32,0x33,0x34,0x35} it is in the form of an array. Writing a function to calculate the crc we will have:

unsigned char crc_calculation (unsigned char* m, unsigned int k) {
unsigned int i;
unsigned char v=0x00 ; // v is the crc  register;

for (i=0; i<k; i++)
v=table[v] ^ *(m+i);

return v;


and calling this function crc_calculation (a,6);

we find crc(a)= 0xbf as above. As you see the initial value in crc register is 0x00  and the first term 0x00 of the message a does not contribute  to the calculation of crc.
To overcome it, sender and receiver agree for an initial value in crc register different than 0x00, for example unsigned char v=0xff;
Doing it we have crc(a)=0x08 .

So, crc is encrypted under Mathematics. "People that don't understand how simple are Mathematics , they can't understand how complicated is the life."  Von Neumann.
Books that I love,    
N. Piscunov   ,  L. Elsgolts .

To admire the glory of the human thought have a look in    Quantum Mechanics

A property of crc : Given a polynomial  having crc(A)=r , with a generator poly d of degree eight and R is the complement of r then: crc (A+R)= crc (0xff). r and R  are 8 bits long.


A= d*q+r ---> A+R=d*q+r+R ----->  crc (A+R)= crc (0xff) =0xff .

Also crc ((A+R)*x^8)=crc(0xff00) .  Magic, may be,...

Have in your mind that the polynomial A+R is different than the polynomial AR.

conttinued ...

Controlling the value of the crc <12/April/2015>

Given the message unsigned char a[5]={0x31,0x32,0x33,0x34,0x35} as you saw (generator poly 0x1d5) we have:

crc (a)= table[table[table[table[0x31] xor 0x32] xor 0x33] xor 0x34]xor 0x35 =0xbf

We want to calculate  a new byte 0xYY  such that the crc of the new message

crc b[6]={0x31,0x32,0x33,0x34,0x35, 0xYY} to be a new known value, say 0xff,

crc b[6]={0x31,0x32,0x33,0x34,0x35, 0xYY}= 0xff

we have crc b[6]= table[ crc a[5] ] xor 0xYY , so we can calculate 0xYY...

0xYY=table [0xbf] xor 0xff

Exercise : Given the message unsigned char a[5]={0x31,0x32,0x33,0x34,0x35}  calculate the byte
0xYY such that the new message b[6]=]={0x31,0x32,0xYY,0x33,0x34,0x35} has a new known crc, say 0xff

crc b= 0xff , so 0xYY ?

The solution is so simple and it will be
published on the next...

If you will give the Good at the End then the End will be Good...


As you observe having a look at the elrments of the array unsigned char table[256] the function that calculates the remainders of the polynomials of the form 0xYY00 is a one to one correspondence function and therefor there is and the reverse function. We can constuct the reverse look up table unsigned char rt [256].

For example table[0x18]=0x7b,  0x18=24 decimal
rt[0x7b]=0x18  , 0x7b=123 decimal.

A function that can built the rt[256] look up table is the:

void reverse_table (void) {
unsigned int i,j;
unsigned char r;
r=(unsigned char) crc8(j);
rt [r] =(unsigned char)i;


And 0xff=table[table[table[table[table[0x31]^0x32] ^0xYY]^0x33]^0x34]^0x35

Observing this equation from left to right and from right to left we can see easily that:

0xYY= (rt [rt [rt[0xff^0x35]^0x34]^0x33]) ^(table[table[0x31]^0x32])

and the end: 0xYY=0xfb

The fact that the only polynomial of the form 0xYY00  that divided by the generator poly 0x1d5 gives as remainder the zero polynomial is the 0x0000 polynomial ,it is a pointer to the quality of 0x1d5. Using this fact you can prove easily that there are not two different polynomials of the form 0xYY00 having the same crc.

It is continued...

CRC16-CCITT   CRC  <13/April/2015>

Today I present a function that calculates a CRC16-CCITT crc. We will use unsigned long integers (32 bit long objects). Our generator polynomial is the 0x1021 , in C code we need only the 0x021 as explained above for crc8.
Since our message is 32 bit long and our divisor d=0x021 uses 12 bits the total number of left shifts is 32-12=20.

#define CRC31   ((T*)(&(test)))-->bit15    //T the stucture as above

unsigned long int crc;
unsigned int test; // test is used for testing for 0 or 1 the #31 bit of the crc, it is exlpained later.
                       //you can use bitwise operator instead.

unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x021

d=d<<20; // we don't want the 20 zeros in front
for (j=0;j<=19;j++)
   test=crc>>16;  // to test the  #31 bit of crc. see the #define above. 
                         //A warning about value truncated here but  ignore  it

if (CRC31)
   crc=crc^d ;

else crc= crc<<1;



return crc;


We used the test variable because the T structure above accepts unsigned characters or unsigned integers only. It does not accepts unsigned long integers. So I used the "trick" of test.

Calling this function for the message 0x31323334 we have:

crc16(0x31323334)= 0x010c

This result is in agreement to polynomial calculator above.

It needs a bit of modification!
CRC16-CCITT generator poly is 0x11021 so in C code use 0x1021, left shifts are 32-16=16 and

and crc16(0x31323334)=0x1381 in agreement to calculator.



CRC16-CCITT table driven implementation <19/April/2015>

So,our crc16 function is the:

unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x1021

d=d<<16; // we don't want the 16 zeros in front
for (j=0;j<=15;j++)
test=crc>>16; // to test the #31 bit of crc. see the #define above. 
                     //A warning about value truncated here but ignore it

if (CRC31)
crc=crc^d ;

else crc= crc<<1;



return crc;


Coming back to our message    unsigned char message [4]={0x31,0x32,0x33,0x34} we can see it as a composition of two polynomial 0x(313233)0x(34) .
Remember: crc(AB)=crc(RB), where crc(A)=R.

Denoting crc (0x313233)=R we  have crc (0x31323334)= crc (R 0x34)

R is a 16 bit long  polynomial  and (R 0x34) is a 24 bit long polynomial. 

crc of quantities of the form   0xYY0000  can be precalculated and saved in a look up table.

For exampe crc (0x310000)=0x2672  and R=crc(0x313233)=crc(0x310000)+crc (0x3200)+crc(0x33)=( 0x2600+0x3200) + (0x72+ 0x33)=0x1441

Repeating the procedure for the polynomial 0x 144134 we find that the crc16 is 0x1381.

As you observe the quantity 0x26 (MSB of crc 0x310000) does an action on the 0x32 and the 0x72( LSB of crc 0x310000) on 0x33.
We can constuct one look up table t1 for the MSB  and one look up tabe t2 for the LSB.

static unsigned char t1[256]  and static unsigned char t2[256]

A fuction that is doing it is the:

void crc16_table (void){
unsigned int t ;
unsigned int long i;
for (i=0;i<256;i++)


t1[(unsigned char)i]=(unsigned char)(t>>8);

t2[(unsigned char)i]=(unsigned char) t;



A function  that can calculate the crc16 using  the tables t1 and t2 is the:

unsigned int crc16_table_calculator (unsigned char *m,  unsigned int k)  {
unsigned char a=0;
unsigned int v=0;  // v the crc
unsigned int j;

for(j=0; j<=k;j++) {
v=(  (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(m+j) );
a= (unsigned char) (v>>8) ;
return v;

Calling it we have :  crc16_table_calculator (message, 3)= 0x1381 as above.

for the  message   unsigned char message [9]={ 0x31, 0x32,0x33,0x34, 0x35,0x36,0x37,0x38,0x39}
we have :  crc16_table_calculator (message ,8)= 0xbeef  in agreement to calculator.

 for the message unsigned char message [11]={ 0x31, 0x32,0x33,0x34, 0x35,0x36,0x37,0x38,0x39,0x00, 0x00}
we have : crc16_table_calculator (message ,10)= 0x31c3 in agreement to calculator.

A crc16 function that accepts strings is the :

unsigned int crc16_table_calculator_string  (unsigned char *s) {
unsigned char a=0;
unsigned int v=0; // v the crc
unsigned int j;

for(j=0; j<=strlen(s) -1 ;j++) {
v=( (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(s+j) );
a= (unsigned char) (v>>8) ;

return v;

Given the string unsigned char *st="1234";

we have:      crc16_table_calculator_string (st)=0x1381

You can observe the performance of crc16 table driven implementation using the performance analyzer of your compiler.

Controlling the value of  CRC16-CCITT  <25/April/2015>

Exercise  1 : Given the message  unsigned char message [4]={0x31,0x32,0x33,0x34} find the bytes  0xYY and 0xZZ  such that  the new message  unsigned char b [6]= {0x31,0x32,0x33,0x34,0xYY,0xZZ} has a given crc16, say 0xffff.

crc16(b)= 0xffff,   so 0xYY and 0xZZ   ?

crcb= crc(crc(message)0xYYZZ)=crc ((0x1381YY)(0xZZ))

denoting   p=   (t1[0x13]^0x81)<<8^(t2[0x13]^0xYY) =0xa300^(0x52^0xYY)=
=0x a3(0x52^0xYY)

we have:  crc (b)= (t1[0xa3]^0x52^0xYY)<<8 ^  (t2[0xa3]^0xZZ)=(0xd7^0xYY)<<8 ^ (0x89^0xZZ)

so 0xff=0xd7^0xYY   and   0xff =0x89^0xZZ   These are because in Galois field XOR's are permited  only, addition with carry is forbiten and it is meaningless.

and the end  : 0xYY= 0x28    and 0xZZ=0x76

unsigned char b [6]= {0x31,0x32,0x33,0x34,0x28,0x76}

verification :  crc16_table_calculator (b, 5)= 0xffff

Exercise  2 : Modify the function crc16_table_calculator in such a way that it shall calculate the crc of a piece of the unsigned char message[9].

My experience! Studying various files that are included in memory integrated circuits mounted on microcontroller boards I found that there is no need to know the generator polynomial in order to recalculate a new crc afrer the modifications that you have done in the file. You can recalculate the new crc using SHIFT's and XOR's  only. 

Initial value in CRC16-CCITT  register. <28/April/2015> 

A bit of modification :

A function that can calculate the crc16 using the tables t1 and t2 is the:

unsigned int v;

unsigned int crc16_table_calculator (unsigned char *m, unsigned int k) {
unsigned char a=0x00;
unsigned int v=0xffff  ; // v the crc
unsigned int j;

for(j=0; j<=k;j++) {

a= (unsigned char) (v>>8) ;
v=( (unsigned int ) (t1[a]^(unsigned char) v ) ) <<8 ^( t2[a] ^ *(m+j) );

return v;

The initial value in crc16 register is 0xffff  .

For the message : unsigned char message [6]={0x00,0x00, 0x31,0x32,0x33,0x34}

We have :
unsigned int crc16_table_calculator (message,5)=0x1d91

For initial value in crc16 register the 0x0000 we have :
unsigned int crc16_table_calculator (message,5)=0x1381 as previous.

Performance Analyzer crc16 example <3/May/2015>

Example : Constucting a message  unsigned char message [100] ;  like

message [j]=(char)j;
}while (j<100);

we have :
unsigned int crc16_table_calculator (message,99)=0xc5d2   ,  initial value 0x0000.
The passed time t of calculation is about  63 μsec  with a clock running at  40MHZ.

For the message:

message [j]=(unsigned char)j;
}while (j<200);

and initial crc16 value the 0xffff

we have: unsigned int crc16_table_calculator (message,199)=0xc440  and t=125 μsec . 

A faster CRC16-CCITT look up table driven implementetion <29/May/2015>

Avoiding intermediate SHIFT's we can use the following faster function:

unsigned char v1, v2;

unsigned int crc16_table_calculator_faster (unsigned char *m , unsigned int k) {
unsigned int v; // v the crc
unsigned int j;
unsigned char z=0x00;

v1=0xff;  //initial value in crc register
v2=0xff;  // initial value in crc register




return v=v1<<8^v2;


As you saw using your performance analyzer for the message:

message [j]=(unsigned char)j;
}while (j<200);

and initial crc16 value the 0xffff

we have:  crc16_table_calculator (message,199)=0xc440 and t=125 μsec .

for the same message we have now:

crc16_table_calculator_faster (message,199)= 0xc440  and t= 90 μsec.


About reflection <16/May/2015>

It is possible an UART (ASC0 for xc164cm )
 to transmit a message starting from bit 0 and finishing at bit 7 for each one of the bytes of the message. We say that the transmitted message has been reflected.  For example the reflect of 0x01 is 0x80, for the 0x02 is 0x40 and so on.   You can find above  an array with the reflected bytes from 0x00 to 0xff.   
An example of a reflected message is the:   

r_message [j]= reflect [(unsigned char)j];
}while (j<200);

The procedure of the calculation of the crc of this message is exactly the same as the one described already. Simply, close your eyes and imagine that you are living in a reflected world.
So, our two look up tables rt1 and rt2 will be:

unsigned int t;

void crc16_reflect_table (void) {
unsigned int long i;

for (i=0;i<256;i++){

rt1[ reflect[(unsigned char)i]  ] =reflect [(unsigned char)(t>>8)];
rt2[ reflect[(unsigned char)i] ] =reflect [(unsigned char)(t)];



Where the crc16 function is ,as previus, the:

unsigned int crc16(unsigned long int message ) {
unsigned int j=0;
unsigned long int d=0x1021
d=d<<16; // we don't want the 16 zeros in front
for (j=0;j<=15;j++)
test=crc>>16; // to test the #31 bit of crc. see the #define above.
//A warning about value truncated here but ignore it

if (CRC31)
crc=crc^d ;

else crc= crc<<1;



return crc;


The function that calculates the crc of the r_message using the tables rt1 and rt2  is the :

unsigned int v;

unsigned int crc16_r_table_calculator (unsigned char *m, unsigned int k) {
unsigned char a=0x00;
unsigned int v=0xffff ; // v the crc, initial value 0xffff
unsigned int j;

for(j=0; j<=k;j++) {

a= (unsigned char) (v>>8) ;
v=( (unsigned int ) (rt1[a]^(unsigned char) v ) ) <<8 ^( rt2[a] ^ *(m+j) );

return v;

Calling it we  have:
crc16_r_table_calculator (r_message,199)=0x2302

Coming back to the real world reflecting each one of the two bytes by hand we have:
The crc of the original message (with no reflection ) is 0xc440  .

crc32  ...
Now I am sure that you already know that you need four look up tables for a crc32 look up table driven implementation ...

A nice place for Summer holidays, the Greek historical  island Samos, the island that born Mathematics 2.500 years ago , the place of my birth,

Pythagoreon of Samos

CRC32 <10/AUGUST/2015>

Today I am presenting a crc32 modulo2 division algorithm, selecting as divisor the polynomial
In C code we need the  0x

I start with a five bytes long message and using one r1 register- unsigned long int r1- to save the first four bytes of the message and an r2 register -unsigned char r2-to save the LSB of the message.

The laws of computation of crc32 are:

"when the bit31 of r1 is 1 shift r1 one place left, after it equate bit0 of r1 to bit7 of r2,after it XOR r1 with d and the crc32 is  the content of r1"

"when the bit31 of r1 is 0 shift r1 one place left, after it equate bit0 of r1 to bit7 of r2, and the crc32 is the content of r1"

We use a 40 bits long place (r1 and r2 together) to save the message and 32 bits used by the divisor so the total number of left shifts is 40-32=8.

To equate  bit0 of r1 to bit7 of r2 we need the help of an unsigned int transfer, ORing transfer with crc32.
To test bit31 of r1 we need the help of an unsigned int test as for crc16 above.

The  C code is :

#define crc32_bit31 ((T*)(&(test)))->bit15
 #define transfer_bit0 ((T*)(&(transfer)))->bit0
 #define r2_bit7 ((T*)(&(r2)))->bit7

              unsigned long int r1;
            unsigned char r2;
            unsigned long int d=0x04c11db7;            //the crc32 divisor
            unsigned long int crc32;
            unsigned int test;
            unsigned int transfer;
            unsigned long int crc_32 (unsigned long int r1, unsigned char r2);

unsigned long int crc_32 (unsigned long int r1 , unsigned char r2 ) {
   for (j=0;j<=7;j++)
   if (crc32_bit31)

else {
   return crc32;

Example: For the message 0x3132333435  we have r1=0x31323334 and r2=0x35 .

crc32 (0x3132333435)=crc_32 (unsigned long int r1 , unsigned char r2 ).

The result is :  crc32=0xE2C04412  in agreement to polynamial calculator above.

continued...at nice Greek sea..swimming...


Following the philosophy of table driven implementation about crc16 above we have to construct four look up tables calculating the crc of polynomials of the form 0xYY00000000 .

A function that is doing it is the:

           void table_crc32 (void);

           unsigned char t1[256]

            unsigned char t2[256]

            unsigned char t3[256]

            unsigned char t4[256];

void table_crc32 (void){

 unsigned long int j;

 unsigned long int tt;


 for (j=0;j<256;j++){


 t1[ (unsigned char) j]=(unsigned char)(tt>>24);

 t2[ (unsigned char) j]=(unsigned char)(tt>>16);

 t3[ (unsigned char) j]=(unsigned char)(tt>>8);

 t4[ (unsigned char) j]=(unsigned char)(tt);



Example: We will use tables t1,t2,t3 and t4 to calculate the crc32 of the message  0x3132333435 .

A funtion that is doing it is the:

 void   __crc32(void);

unsigned long int   _crc32;

void   __crc32(void) {

    unsigned char a ;


   _crc32= (((unsigned long int)(t1[a]^0x32))<<24) ^ (((unsigned long int)(t2[a]^0x33))<<16)\ 

   ^(((unsigned long int)(t3[a]^0x34))<<8)^ (t4[a]^0x35);                           


Calling it as   __crc32();  we have:

crc32(0x3132333435)=0xE2C04412 as previus.

Continued at the beach under the sun with juice... 
more CRC32 functions comming soon...


Today  I start
to show you the power of crc check in the field of the error correction. For simplicity we begin with a crc8  and an error that occured at one bit only.
So , suppose that the sender sent a message a and crc8(a)=v1.
The receiver receives an error message e, the error is at one bit only.

What the reciever received are: the e and v1.

Now the receiver calculates the crc8 and finds crc8(e)=v2, v2 is different than v1.

Writing down some simple mathematics we have:
a=d*q1+v1  ,    e=d*q2+v2 .
Adding these equations by parts we have:
a+e=d*(q1+q2)+ (v1+v2), order of the polynomial v1+v2 is lower than the order of d.
so, crc8(a+e)=v1+v2, v1+v2 is known.

Since the error occured at one bit only The polynomial a+e is a polynomial of the form : or  10...  with unknown number of zeros, the  number of bytes of the message a+e will be equal to the number of bytes of message e .

But knowing that  crc8(a+e)=v1+v2 and knowing and the form of the polynomial a+e  it is easy to write C code to construct the polynomial a+e. Knowing a+e and e we can calculate the a.

An example is ready...

The sender sent the message
unsigned char a [5]={ 0x31,0x32,0x33,0x34,0x35}  having v1=0xbf  and the receiver receives the message
 unsigned char e [5]={ 0x31,0x12,0x33,0x34,0x35}  having crc8(e)=v2.
The program calculates the polynomial a+e denoting it by x and having crc8(x)=v1+v2 and after it calculates the original message.

the program is:

 unsigned char v1, v2, er;
 unsigned char e [5]={ 0x31,0x12,0x33,0x34,0x35} ;
 unsigned char x [5]={ 0x00,0x00,0x00,0x00,0x00} ;
 unsigned char original [5];
  void correct (void);

void main(void)
 // USER CODE BEGIN (Main,2)
//make the crc8 table
for (i=0;i<256;i++)
   j=((unsigned int)i)<<8;

correct (); // find the difference
 //calculate the original message
 for (i=0;i<5;i++) {

The used functions are the:

Make crc8 modoulo2 division

unsigned int crc8(unsigned int byte) {
int j=0;
unsigned int d=0xd500; // you can change the divisor here!!!- your crc generator polynomial.
 for (j = 0;j <=7;j++ )
if (CRC15)
else crc=crc<<1;
return crc;

Calculate crc8 using table
            unsigned char crc_calculation (unsigned char * m, unsigned int k)
 unsigned char v ;
 for (i=0; i< k ;i++)    
 return v;

Calculate the difference
void correct (void){
unsigned char i ,j, v3;
 v1= 0xbf ;            // v1 the crc8 of the right message
 // v1= crc_calculation (a,5);
v2= crc_calculation (e,5) ;   //v2 the crc8 of the wrong message
er=v1^v2; // er is the difference of crc8
for (i=0;i<5;i++) {
*(x+i)= (*(x+i)) +1;
for (j=0;j<8;j++){
v3=crc_calculation (x,5); // v3 the crc8 of an intermediate polynomial
                                     // for comparison to er
if ( !(v3^er)) {

 *(x+i)= (*(x+i)) <<1;
if ( !(v3^er))
 break;        // finished