?
Solved

CRC Polynomials

Posted on 2003-02-27
5
Medium Priority
?
905 Views
Last Modified: 2008-02-01
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
Comment
Question by:JSMCM
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 1

Accepted Solution

by:
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.
/*++

Copyright (c) 1998  Intel Corporation
   
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,
    0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
    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 (
    IN OUT EFI_TABLE_HEADER *Hdr
    )
/*++

Routine Description:

    Updates the CRC32 value in the table header

Arguments:

    Hdr     - The table to update

Returns:

    None

--*/
{
    SetCrcAltSize (Hdr->HeaderSize, Hdr);
}

VOID
SetCrcAltSize (
    IN UINTN                 Size,
    IN OUT EFI_TABLE_HEADER *Hdr
    )
/*++

Routine Description:

    Updates the CRC32 value in the table header

Arguments:

    Hdr     - The table to update

Returns:

    None

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


BOOLEAN
CheckCrc (
    IN UINTN                 MaxSize,
    IN OUT EFI_TABLE_HEADER *Hdr
    )
/*++

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

--*/
{
    return CheckCrcAltSize (MaxSize, Hdr->HeaderSize, Hdr);
}




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

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

by:msa2003
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

by:LordThlan
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

by:zebada
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

by:JSMCM
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

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

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

How to remove superseded packages in windows w60 or w61 installation media (.wim) or online system to prevent unnecessary space. w60 means Windows Vista or Windows Server 2008. w61 means Windows 7 or Windows Server 2008 R2. There are various …
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
The viewer will learn how to implement Singleton Design Pattern in Java.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question