Dispersion Design

< Back

CRC-32 Calculations for the PNG Format

Written: 2012-04-21

Introduction

A cyclic redundancy check (CRC) algorithm is a method of calculating a number, or check ‘value’, that can be used to determine the integrity of a set of data. Prior to saving or transmitting data, a known CRC calculation can be performed on the data to determine it’s check value. The check value is then transmitted along with the data. When the data is received, the CRC calculation is repeated on the same data and the calculated check value is compared to the original check value. If the two check values do not match, then the data has been corrupted in some way between the times that the two values were calculated.

There are many CRC algorithms and the PNG (Portable Network Graphics) image file format uses the ‘CRC-32’ algorithm. 32-bit (4-byte) check values are calculated for each ‘chunk’ within a PNG file and these check values are stored at the end of each chunk. This article will demonstrate the code required for calculating the CRC-32 values used in the PNG format.

The example code will be written using the Perl programming language.

Initialization

First, we need a persistant variable that keeps track of the running CRC-32 value and a method to reset that variable back to it’s initial state:

package CRC32;

our $crc = 0xFFFFFFFF;

sub clear
{
	$crc = 0xFFFFFFFF;
}

This code only keeps track of a single CRC-32 calculation at a time. If multiple calculations need to be performed simultaneously, you would want to encapsulate these functions in a class, where each instance of the class maintains it’s own CRC variable ($crc).

Lookup Table

CRC calculations are typically performed one bit at a time, however we can pre-calculate an 8-bit table (256 values) that allows us to perform the CRC-32 calculation 8-bits (one byte) at a time instead. This gives us a big speed improvement:

sub build_table
{
	my $table = [];
	for(my $n = 0; $n < 256; $n++)
	{
		my $c = $n;
		for( my $k = 0; $k < 8; $k++ )
		{
			$c = ($c >> 1 ) ^ (($c & 1) ? 0xEDB88320 : 0);
		}
		$table->[$n] = $c;
	}
	return $table;
}

Process the Data

Now we need a function that takes a string of bytes and steps through it one byte at a time. The CRC-32 calculation is performed repeatedly for each byte of data:

our $crc_table;

sub add
{
	my($data_ptr) = @_;

	if(!defined $crc_table)
	{
		$crc_table = build_table();  
	}

	my @bytes = unpack("C*", $$data_ptr);
	foreach my $byte (@bytes)
	{
		$crc = $crc_table->[($crc ^ $byte) & 0xFF] ^ ($crc >> 8);
	}
}

The data is passed into this function as a scalar reference ($data_ptr), often called a pointer in other programming languages. It then has to be de-referenced ($$) when passed to the unpack() function.

We check to see if the CRC lookup table ($crc_table) already exists and only create the table the first time the add() function is called.

Getting the Check Value

Finally, we need a function to return the final CRC-32 check value:

sub result
{
	return ($crc ^ 0xFFFFFFFF);
}

Putting it All Together

The complete Perl module for performing CRC-32 calculations is now:

package CRC32;

our $crc = 0xFFFFFFFF;
our $crc_table;

sub clear
{
	$crc = 0xFFFFFFFF;
}


sub build_table
{
	my $table = [];
	for(my $n = 0; $n < 256; $n++)
	{
		my $c = $n;
		for( my $k = 0; $k < 8; $k++ )
		{
			$c = ($c >> 1 ) ^ (($c & 1) ? 0xEDB88320 : 0);
		}
		$table->[$n] = $c;
	}
	return $table;
}


sub add
{
	my($data_ptr) = @_;

	if(!defined $crc_table)
	{
		$crc_table = build_table();  
	}

	my @bytes = unpack("C*", $$data_ptr);
	foreach my $byte (@bytes)
	{
		$crc = $crc_table->[($crc ^ $byte) & 0xFF] ^ ($crc >> 8);
	}
}


sub result
{
	return ($crc ^ 0xFFFFFFFF);
}

1;

This code can be used in the following way:


#!/usr/bin/perl
use CRC32;

my $data = 'Hello World';

CRC32::clear();
CRC32::add(\$data);

my $check_value = CRC32::result();

printf("Check value (in hex): %x\n", $check_value);

Remember, the data must be passed to the add() function as a scalar reference (a pointer).