Solved

# CRC Polynomials

Posted on 2003-02-27
Medium Priority
932 Views
Hello

I am trying to figure out how CRC poly's work.

I know that in the 16 Bit CRC we are using at the moment, the poly is x^16 + X^12 + X^5 + X^0 = 0x1021

But what I don't know is how to actually use this poly to calculate the CRC on a number, eg 0x11

I have seen that alot of people do this with a table lookup. Is that really necesarry if you have the poly. Why can't you just calculate without a table?

Thanks, John
0
Question by:JSMCM

LVL 1

Accepted Solution

larryco earned 300 total points
ID: 8034344
You can calculate without a table, but using tables is much faster.  The calculations are integer and must be exact in the lower digits.  This means a lot of costly multiplication.  Here's a sample table implementation.
/*++

Module Name:

crc.c

Abstract:

CRC32 functions

Revision History

--*/

#include "lib.h"

UINT32 CRCTable[256] = {
0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
};

VOID
SetCrc (
)
/*++

Routine Description:

Arguments:

Hdr     - The table to update

Returns:

None

--*/
{
}

VOID
SetCrcAltSize (
IN UINTN                 Size,
)
/*++

Routine Description:

Arguments:

Hdr     - The table to update

Returns:

None

--*/
{
Hdr->CRC32 = 0;
Hdr->CRC32 = CalculateCrc((UINT8 *)Hdr, Size);
}

BOOLEAN
CheckCrc (
IN UINTN                 MaxSize,
)
/*++

Routine Description:

Checks the CRC32 value in the table header

Arguments:

Hdr     - The table to check

Returns:

TRUE if the CRC is OK in the table

--*/
{
}

BOOLEAN
CheckCrcAltSize (
IN UINTN                 MaxSize,
IN UINTN                 Size,
)
/*++

Routine Description:

Checks the CRC32 value in the table header

Arguments:

Hdr     - The table to check

Returns:

TRUE if the CRC is OK in the table

--*/
{
UINT32      Crc;
UINT32      OrgCrc;
BOOLEAN     f;

if (Size == 0) {
//
// If header size is 0 CRC will pass so return FALSE here
//
return FALSE;
}
if (MaxSize && Size > MaxSize) {
DEBUG((D_ERROR, "CheckCrc32: Size > MaxSize\n"));
return FALSE;
}

// clear old crc from header
OrgCrc = Hdr->CRC32;
Hdr->CRC32 = 0;
Crc = CalculateCrc((UINT8 *)Hdr, Size);

// set restults
Hdr->CRC32 = OrgCrc;

// return status
f = OrgCrc == (UINT32) Crc;
if (!f) {
DEBUG((D_ERROR, "CheckCrc32: Crc check failed\n"));
}

return f;
}

UINT32
CalculateCrc (
UINT8 *pt,
UINTN Size
)
{
UINTN Crc;

// compute crc
Crc = 0xffffffff;
while (Size) {
Crc = (Crc >> 8) ^ CRCTable[(UINT8) Crc ^ *pt];
pt += 1;
Size -= 1;
}
Crc = Crc ^ 0xffffffff;
return (UINT32)Crc;
}

0

LVL 5

Expert Comment

ID: 8036232
I have a sample Delphi program which codes and decodes data with CRC using polynomials. It has user-friendly interface and was originally developed to show in details the encoding end decoding algorithms and code error-correction and error-identification opportunities. You may use this program with pre-defined set of polynomials, or enter costom values.

Now I didn't placed a link to this program because it has only Russian language interface. If you need this program I'll translate it to English.

It doesn't use tables.
0

LVL 3

Expert Comment

ID: 8036445
If you are looking for info on CRCs and how to implement them and how the poly is used to calculate a CRC then go to:  http://www.cs.waikato.ac.nz/~312/crc.txt

It is the "Painless Guide TO CRC ERROR DETECTION ALGORITHMS," and it has a good bit of info about how the poly is used.
0

LVL 6

Expert Comment

ID: 8036507
I asked a similar question a while back here:
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20146760.html
It may help explain some stuff.
Paul
0

LVL 2

Author Comment

ID: 8056165
Thanks, I'll have a look at these suggestions, but it may take a while to get back to you guys.

John
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

There is an easy way, in .NET, to centralize the treatment of all unexpected errors. First of all, instead of launching the application directly in a Form, you need first to write a Sub called Main, in a module. Then, set the Startup Object to th…
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month7 days, 23 hours left to enroll