CRC

In computer networking, errors are a common issue. Think about everything that’s going on during data transmission, from serialization, to packaging, filtering, ordering, buffering and, among many other things, transmission. Each step adds a layer of complexity (and a potential error source), but the lower level layer is the most prone to errors. Finding errors and fixing them is one of the fundamental functionalities of this layer. In this post, I will try to explain CRC, the algorithm used to detects errors and (try to) fix them.

Everything that could go wrong

Let’s begin this post with a simple, yet unlikely, assumption: Networks work perfectly, thus rendering error detection useless.

Yes, you heard me right, everything works flawlessly, from applications not messing up with their data, to routing being performed optimally without packet duplication and, finally, the gods of physics grant us with their almighty knowledge so our wires are not affected by noise or other unimportant little stuff and information is delivered as it was intended from the upper layers. In short, everything works perfectly but, as the Morphy’s law describes:

Whatever can go wrong, will go wrong.

So be it

Wait, what? Applications are retransmitting data to synchronize operations instead of implementing lower level synchronization functionalities?

Whoa, whoa! Our co-working assholes connected 3 routers to a switch forcing a battle between DHCP servers? –¡En garde! Fuck your IP ranges, they suck!–

The cabling company installed our UTP Cat. 3 uplink next to the entire electrical installation of the building so our noise-signal ratio is f****d up?

As veterans on Tinder often say: some mistakes are inevitable. The chances of getting everything working perfectly are closer to 0 than you may assume and, in fact, errors happen all the freaking time.

There you are!

Networks are, conceptually, operating on many different layers of abstraction which allows each layer to take care of a specific task. Every layer should perform one specific task and nothing more. The lower we dive, the closer to bits and physical infrastructure we get and, as a consequence, the more susceptible to errors we become. Designing ways for us to detect those errors, allow us to take actions to keep an open communication and being able to fix some of them, will prevent further retransmissions lowering the amount of packages flooding our networks with unnecessary traffic.

Hello CRC

When the Ethernet protocol was firstly accepted and standarized by the IEEE 802.3 back in 1983, the top speed was about of 10Mbps. Still, engineers had to find a way to prevent errors even when they couldn’t predict the exact speed evolution in the comming years, the solution you ask? The Cyclick Redundancy Check.

What does it is?

From Wikipedia:

A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. Blocks of data entering these systems get a short check value attached, based on the remainder of a polynomial division of their contents. On retrieval, the calculation is repeated and, in the event the check values do not match, corrective action can be taken against data corruption.

Basically, it is an algorithm in which some control bits, known as parity bits, are added to data and then compared against a polynomial division in order to generate a hash-like code that can be used to calculate if the data is corrupted and, most importantly, where is located the error.

This algorithm was invented back in 1961 by W. Wesley Peterson. It was perfected and optimized in order to be added to the Ethernet standard in 1975. It is one of the most important algorithms, so multiple implementations exist with lower-level ones standing out as the most efficient and fast among other higher-level implementations used mostly for educational purposes, during this article I will present later ones. However, if you, dear reader, search google, you may find almost unreadable yet efficient code which may be more suitable for production environments.

How does it work?

CRC is based upon division, which will need the selection of a generator polynomial, which will serve as the divisor, the message as the dividend, the quotient is discarded and the remainder will be our resulting hash or CRC code. The important caveat is that the polynomial coefficients are calculated according to the arithmetic of a finite field, so the addition operation can always be performed bitwise-parallel (there is no carry between digits). For each data to be sent, a short-length CRC value is calculated based on the polynomial generator and is appended to the end, when the receiver reads the data, whenever it detects the appended word it can compare the resulting value of it’s own CRC calculation or a backwards algorithm execution, and it will be able to detect if there was an error and in which word does the error exists.

Select a polynomial

Selecting a generator polynomial is, if not the most, one of the most important tasks to performing a CRC calculation. Both the sender and the receiver should use the same polynomial in order to correctly interpret the CRC field. There are multiple pre-defined polynomials implemented in multiple standards, one of the mostly used are:

Name Polynomial Uses
CRC-1 x+1 Hardware, also known as parity bit
CRC3-GSM x^{3}+x+1 Mobile GSM networks
CRC-5-USB x^{5}+x^{2}+1 USB token packets
CRC-32 x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^{8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1 This is the mostly used version, featured in ISO 3309 (HDLC), ANSI X3.66 (ADCCP), FIPS PUB 71, FED-STD-1003, ITU-T V.42, ISO/IEC/IEEE 802-3 (Ethernet), SATA, MPEG-2, PKZIP, Gzip, Bzip2, POSIX cksum, PNG, ZMODEM, many others.

There exist many, many, many other generator polynomials. In fact, most communication protocols are known to implement their own CRC function and, based on each one requirements, they pick a generator polynomial.

Pseudocode

The rest of the article will focus on the CRC-32 which is the implementation Ethernet uses. The pseudo-code for this algorithm is as follows:

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

The divisor works bits directly on each step, performing a bitwise XOR operation of the polynomial function above it, resulting in an execution like:

11010011101100 000 <--- input right padded by 3 bits
1011               <--- divisor
01100011101100 000 <--- result (note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged)
 1011              <--- divisor ...
00111011101100 000
  1011
00010111101100 000
   1011
00000001101100 000 <--- note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
       1011             (in other words, it doesn't necessarily move one bit per iteration)
00000000110100 000
        1011
00000000011000 000
         1011
00000000001110 000
          1011
00000000000101 000
           101 1
-----------------
00000000000000 100 <--- remainder (3 bits).  Division algorithm stops here as dividend is equal to zero.

As you can see, performing this operation does not require higher-level capabilities as it can be programmed into our hardware directly with logical gates, specifically XOR ones.

Implementation in Python

The simplest implementation would be done in Python, as follows:

def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):
    '''
    Calculates the CRC remainder of a string of bits using a chosen polynomial.
    initial_filler should be '1' or '0'.
    '''
    polynomial_bitstring = polynomial_bitstring.lstrip('0')
    len_input = len(input_bitstring)
    initial_padding = initial_filler * (len(polynomial_bitstring) - 1)
    input_padded_array = list(input_bitstring + initial_padding)
    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
    return ''.join(input_padded_array)[len_input:]

def crc_check(input_bitstring, polynomial_bitstring, check_value):
    '''
    Calculates the CRC check of a string of bits using a chosen polynomial.
    '''
    polynomial_bitstring = polynomial_bitstring.lstrip('0')
    len_input = len(input_bitstring)
    initial_padding = check_value
    input_padded_array = list(input_bitstring + initial_padding)
    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(int(polynomial_bitstring[i] != input_padded_array[cur_shift + i]))
    return ('1' not in ''.join(input_padded_array)[len_input:])

Which upon execution may throw:

>>> crc_check('11010011101100','1011','100')
True
>>> crc_remainder('11010011101100','1011','0')
'100'

Where is it implemented?

As you may know, the CRC-32 algorithm is implemented on the Ethernet standard (802.3 specifically), as follows:

Ethernet Header

Being 4 bytes, the actual length bitwise would be of 32 bits, now you see? It allows an error-detection system to be runned upon layer 2, enabling communications to fix (or discard) corrupted data faster and easier.

In the Ethernet frame, the CRC field is the resulting CRC validation of the data section, which contains the upper-level PDU. Being a lower-level-capable implementation, this calculation and verification is performed directly on your NIC, rendering virtually invisible errors to our own computers.

Fun fact: When I was first learning about error correction, my assignment was to create a program which, upon execution, was supposed to detect any CRC errors. I spent a ridiculous amount of time writing it and, after I finished it, another absurd and gross entire week figuring out why it couldn’t detect any errors. Later on, I figured out that, by performing the CRC calculation and verification directly on the hardware-level of my computer’s NIC, erroneus packets won’t even reach my computer’s interface making my program useless by cpaturing packets on the wild. TLDR: if you would like to check for errors on some Ethernet frames, get yourself some corrupted ones from the internet and read them from file, our computers outsmart our engineering asses.

A few considerations

The idea behind fixing errors is a valuable and important process, but it is mostly impossible. There’s almost zero chance of errors being present just on one bit of the transmitted information, in fact, the probablity of data being corrupted on a single bit is very low. On the other side, probablity of multiple errors is very high. Consider that, when an error occurs during data transmission, the transmission speed is so freaking high that it will affect more than one package. This risk becomes higher with wireless communications, in fact, the initial versions of the WiFi protocol (802.11) had so many errors, the transmission speeds couldn’t go higher than 5-10Mbps, even if it could physically go higher. Later on, as the technology evolved, higher speeds became available, but still 5% to 30% of packets get discarded during a normal transmission due to the abominable number of things that could (and would) go wrong.

With today’s top internet speeds being around 10Gbps with standard fiber-optic communications, error-correction is rendered inviable, and current protocols are focused mostly on error-detection and retransmission upon discarded packets.

Conclussion

The CRC algorithm is one of the most analyzed algorithms ever, it is the foundation of many communication protocols and it is widely used even for today’s communications. It is quite difficult to understand it from a simple viewpoint, but the essential elements might give the reader an idea of how much effort has been done to ensure communications are secure and, most importantly, error-free.

If you feel like something’s missing, you’d like to discuss this article or got any comments and/or feedback, you can find me on Twitter as @humbertowoody.