efg's Computer Lab   Mathematics

Crc.gif (968 bytes)   Cyclic Redundancy Code Calculator   Lab Report

Calculate CRCs of Character Strings using a CRC Calculator
(Also see the FileCheck Lab Report for CRCs of Files, Directories, Volumes)

 

ScreenCRCCalc.jpg (17211 bytes)

 

Purpose
The purpose of the CRCCalculator is to display interactively the CRC-16 and CRC-32 values for a specified string.  (The CRC-32 values will match those computed by PKZIP.)

Additional files, CRC16Dem and CRC32Dem, show how to create a command-line program to calculate CRC values.   A "C" command-line program is also available.

Materials and Equipment

Software Requirements
Windows 95/98
Delphi 3/4/5 (to recompile)

Hardware Requirements
VGA display

Procedure

  1. Double click on the CRCCalculator.EXE icon to start the program.
  2. Enter any text in the edit box.
  3. Observe the CRC-16 and CRC-32 values in decimal or hexadecimal.

Expected Values
Hex values do not change by version of Delphi, but the decimal values are intended to be unsigned.  CRC-16 values have always been unsigned, but since there was no 4-byte unsigned integer in D1-D3, the decimal values are signed for the CRC-32 until the Delphi 4 version.

 

Test String

CRC-16

CRC-32

 

Comments

Decimal

Hex

Decimal

Hex

<null string>

0

0000

0

00000000

Delphi 2/3/4/5

abc

38712

9738

891568578

352441C2

Delphi 2/3/4/5

ABC

17697

4521

-1551695032

A3830348

Delphi 2/3

2743272264

Delphi 4/5

This is a string

19524

4C44

141976383

0876633F

Delphi 2/3/4/5

The CRC-32s of the files abcLower.TXT, ABCupper.TXT, and ThisIsAString.TXT in the CRCDelphi.ZIP file match the values above, which are also verified in the CRC32Dem.PAS command line program:

CRC-32    Bytes         F i l e n a m e
-------- -------- ------------------------
352441C2        3 abcLower.TXT
A3830348        3 ABCUpper.TXT
0876633F       16 ThisIsAString.TXT

Discussion
CRC values, especially the CRC-32, are an extremely good way to verify the integrity of a file.  If the CRC-32 for a file stays the same, there is only an extremely small probability that the file has been changed -- about 1 in 4 billion.   CRCs could be used as a preliminary verification tool to find identical files.   If the CRCs of two files do not match, the file are not the same.  This could even be used to compare image files.

The "hardware" method of computing CRCs involves bit manipulations, which is very inefficient for a software computation.  Instead of computing the CRC bit-by-bit, a 256-element lookup table can be used to perform the equivalent of 8 bit operations at a time.  (This is described in "Byte-wise CRC Calculations" in IEEE Micro, June 1983, pp. 40-50.) 

For a CRC-16, the lookup table consists of 256 2-byte WORDs (see the CRC16.PAS unit for the actual table).  For a CRC-32, the lookup table consists of 256 4-byte DWORDs (see the CRC32.PAS unit for the actual table).  Given the lookup Table, the code for computing a CRC-32 is as follows:

// Use CalcCRC32 as a procedure so CRCValue can be passed in but
// also returned. This allows multiple calls to CalcCRC32 for
// the "same" CRC-32 calculation.
PROCEDURE CalcCRC32 (p: pointer; ByteCount: DWORD; VAR CRCValue: DWORD);
  // The following is a little cryptic (but executes very quickly).
  // The algorithm is as follows:
  // 1. exclusive-or the input byte with the low-order byte of
  // the CRC register to get an INDEX
  // 2. shift the CRC register eight bits to the right
  // 3. exclusive-or the CRC register with the contents of Table[INDEX]
  // 4. repeat steps 1 through 3 for all bytes

  VAR
    i:  DWORD;
    q: ^BYTE;
BEGIN
  q := p;
  FOR i := 0 TO ByteCount-1 DO
  BEGIN
    CRCvalue := (CRCvalue SHR 8) XOR
    Table[ q^ XOR (CRCvalue AND $000000FF) ];
    INC(q)
  END
END {CalcCRC32};

You can pass nearly any argument to this routine since the first parameter is a pointer.  For a string, pass the address of the first character, for example:

     CalcCRC32 (Addr(s[1]), LENGTH(s), CRC32);

To avoid an access violation in Delphi 4 (or later) make sure Length(s) > 0.  (I'm not sure why Delphi 3 didn't complain.)

To compute the same CRC-32 as used in the PKZIP utility, start with a CRCvalue of $FFFFFFFF.  After calling CalcCRC32 above (any number of times), the finalization consists of a 1's complement of the CRCvalue.  This can be computed with the expression NOT CRCvalue in Delphi.

The initialization and finalization of the CRC computation are arbitrary.   As mentioned above, the "standard" CRC-32 (the one used by PKZIP) starts with $FFFFFFFF as the initial value and then performs a 1's complement to yield the final value.  Here's what is done in the CRC Calculator for CRC-32s:

CRC32 := $FFFFFFFF; // To match PKZIP
IF       LENGTH(s) > 0 // Avoid access violation in D4
THEN CalcCRC32 (Addr(s[1]), LENGTH(s), CRC32);
CRC32 := NOT CRC32; // TO match PKZIP

CRC32Decimal.Caption := IntToStr(CRC32);
CRC32Hex.Caption := IntToHex(CRC32,8)

[Thanks to Rolf Gebhardt and Glen Harman for pointing out an inconsistency about how finalization was handled in an earlier version of this article.]

The CRC-16 computation starts with an initial value of 0 and performs no finalization.  Here's what is done in in the CRC Calculator for CRC-16s:

CRC16 := 0;               // Could use $FFFF or other initial value
IF       LENGTH(s) > 0 // Avoid access violation in D4
THEN CalcCRC16 (Addr(s[1]), LENGTH(s), CRC16);

CRC16Decimal.Caption := IntToStr(CRC16);
CRC16Hex.Caption := IntToHex(CRC16,4);

See the FileCheck Lab Report for information about creating CRCs of files.

The command line examples, CRC16Dem and CRC32Dem can be compiled from a DOS Window (assuming your path contains the Delphi bin directory) by entering:

     DCC32 CRC16Dem.PAS    or
     DCC32 CRC32Dem.PAS

Study the CRC16Dem and CRC32Dem command line programs for a way to calculate CRCs without a Windows interface.

Useful literature:
"Procedure for Computing CRC-32 Values," Microsoft Systems Journal, March 1995, pp. 107-108.

"Byte-wise CRC Calculations" by Aram Perez in IEEE Micro, June 1983, pp. 40-50. Shows how to create a lookup table which is the best way to implement in software (versus the shifts that are done when implemented in hardware). 

"A Tutorial on CRC Computations" by Tenkasi V. Ramabadran and Sunil S. Gaitonde in IEEE Micro, August 1988, pp. 62-75.

"Cyclic Redundancy Checks for Data Integrity or Identity" by William H. Press and Saul A. Teukolsky, Computers in Physics, Jul/Aug 1989, pp. 88-91.

"For the Love of the Gam" by Michael Barr, Embedded Systems Programming, Dec. 1999, pp. 47-54.

"Slow and Steady Never Lost the Race" by Michael Barr, Embedded Systems Programming, Jan. 2000, pp. 37-46.  Shows how to compute CRC lookup table.  The two Table 1s from these Embedded Systems Programming articles provided this information:

Standard Name CRC-CCITT CRC-16 CRC-32
Width 16 bits 16 bits 32 bits
Generator Polynomial 10001000000100001 11000000000000101 100000100110000010001110110110111
Initial remainder 0xFFFF 0x0000 0xFFFFFFFF
Final XOR value 0x0000 0x0000 0xFFFFFFFF

Conclusions
CRC values, especially the CRC-32, are an extremely good way to verify the integrity of a string or even a  file.

Keywords
cyclic redundancy check, CRC-16, CRC-32, APPTYPE CONSOLE, lookup table, XOR, Comp, Int64, IntToHex, Addr

Files
Delphi 2/3/4/5 Source and EXE (234 KB):   CRCDelphi.ZIP

Borland C++ 5.02 "C" CRC-32 Source and EXE (45 KB):  CRCC.ZIP
Use the "make file" to compile:  make -f crc32.mak
(Modify .mak file to point to correct location of wildargs.obj.  The .mak file automatically performs a test that the results will match those of PKZIP.)  This command-line utility can be used with wildcards to find the CRC-32 of files in a directory, for example:  crc32 *.*