Why CRC ?

CRC stands for Cyclic Redundancy Check. When sending a sequence of bits from point A -> point B. We use CRC to check weather it arrived with or without error in any possible case. CRC check is used to detect errors in a message. It’s one of the most powerful and straight forward procedure to use data check. Typical application of CRC is 16bits long ; so that the choice of random error going undetected is 1 in 2^16 = 65536. The mathematics underlying CRCs is “Polynomial over the integers modula 2”. We will see what that means. Implementation of CRC such as CRC-CCITT, CRC-32 or other polynomials. CRC is a common method for detecting errors in transmitted messages or stored data. The CRC is a very powerful, but easily implemented technique to obtain data reliability

CRC Basics :

The data is treated by the CRC algorithm as a binary number. This number is divided by another binary number called the polynomial. If the result of this division is zero, then the transmission was successful. However, if the result is not equal to zero, an error occurred during the transmission. The CRC-16 polynomial :

$x^{16}+x^{15}+x^2+1$

Any binary message can be thought of as a polynomial with coefficients 0 and 1. For example, the message “1100001101” is the polynomial :

$x^9+x^8+x^3+x^2+1$

The division uses the Modulo-2 arithmetic. Modulo-2 calculation is simply realized by XOR’ing two numbers.

The CRC-16 polynomial has a length of 16-bits, therefore, 16-bits have to be augmented to the original message.

Into the dirt now! ~

Now below example if you see, we do like normal division as known. In this example calculation, the polynomial has a length of 2-bits, therefore, the message has to be extended by two zeros at the end. Our message was 110101 . So it has to be appended with two zeros!

At the end we get the checksum we asked for. But, if we want to check that if data for crc error. We append three one’s to the message it we have 3 bit CRC to evaluate through. Like :

Our Own Implementation :

Basically there are two ways by which CRC implemented in software system is that :

Loop Driven
Table Driven

We will be going toward Table Driven approach as it is much faster but comes at the cost of more memory consumption.

The idea behind a table driven CRC implementation is that instead of calculating the CRC bit by bit, precomputed bytes are XORed to the data. The CRC at the table driven implementation is generated by reading a precomputed value out of a table and XOR, the result with the low and high byte of the CRC shift registers.

This Answer on stackoverflow Explains:

For IEEE802.3, CRC-32. Think of the entire message as a serial bit  stream, append 32 zeros to the end of the message. Next, you MUST  reverse the bits of EVERY byte of the message and do a 1's complement  the first 32 bits. Now divide by the CRC-32 polynomial, 0x104C11DB7.  Finally, you must 1's complement the 32-bit remainder of this division  bit-reverse each of the 4 bytes of the remainder. This becomes the  32-bit CRC that is appended to the end of the message.

The reason for this strange procedure is that the first Ethernet  implementations would serialize the message one byte at a time and  transmit the least significant bit of every byte first. The serial bit  stream then went through a serial CRC-32 shift register computation,  which was simply complemented and sent out on the wire after the message was completed. The reason for complementing the first 32 bits of the  message is so that you don't get an all zero CRC even if the message was all zeros.

Infact, CRC is also calculated in hardware terms which is bits by bits and efficient for that aspect but for software case lookup tables are highly used!

Algo as on wiki :

Function CRC32
   Input:
      data:  Bytes     // Array of bytes
   Output:
      crc32: UInt32    // 32-bit unsigned CRC-32 value

// Initialize CRC-32 to starting value
crc32 ← 0xFFFFFFFF

for each byte in data do
   nLookupIndex ← (crc32 xor byte) and 0xFF;
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex]  // CRCTable is an array of 256 32-bit constants

// Finalize the CRC-32 value by inverting all the bits
crc32 ← crc32 xor 0xFFFFFFFF
return crc32

Go implementation -:

package main

import (
	"fmt"
)

var table [256]uint32

//creating lookup table
func init() {
	for i := range table {
		word := uint32(i)
		for j := 0; j < 8; j++ {
			if word&1 == 1 {
				word = (word >> 1) ^ 0xedb88320
			} else {
				word >>= 1
			}
		}
		table[i] = word
	}
}

func crc32(s string) uint32 {
	crc := ^uint32(0)
	for i := 0; i < len(s); i++ {
		/* XOR-in next input byte*/
		pos := byte(crc) ^ s[i]
		/* Shift out the MSB used for division per lookuptable and XOR with the remainder */
		crc = table[pos] ^ (crc >> 8) //right shift by 8 bit
	}
	//XOR final returned value
	return ^crc
}

func main() {

	fmt.Println(crc32("Isit"))
    //Output: 1924692841

}

A Concept and Code Beginner's Guide to CRC

Why CRC ?

CRC Basics :

Into the dirt now! ~

Our Own Implementation :

References :