CRC32

[Don]

Hi NG.

Does anyone know of a place where I could download/get a C implementation of
a CRC32 check.
I would like a simple function that, for example, had a pointer to where the
data to be CRC32 calculated reside, an indication of the length of the data
and perhaps the polynomium as input arguments and then would return the
calculated crc32 value like e.g. an unsigned long.

Don

[Dan Pop]

In <Xn************ *************** *******@130.133 .1.4> "Mark A. Odell" <no****@embedde dfw.com> writes:

"Don" <no**@spam.dk > wrote in news:bg******** **@news.net.uni-c.dk:

Ok. Thank you all for your help. I need to implement this crc32 check in
a microcontroller and I have a program now that states:

#define POLYNOMIAL (unsigned long)0x04c11db7
What possible (practical) benefit is there to making this a #define
instead of a const var (e.g. const unsigned long polynomial = 0x04c11db7)?

You have forgotten static. And it's still better to spell it in upper
case, to point out that it isn't an ordinary variable.
Try finding the #define in your debugger by name.

Why would one want to do such a thing? You have the source code in
front of your eyes while using the debugger, don't you?

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Randy Howard]

In article <bg**********@n ews.net.uni-c.dk>, no**@spam.dk says...

I would like to cross-check this with some program or similar. Does anyone
know of a program similar to:
http://www.smbus.org/faq/crc8Applet.htm
Making me capable of calculating the crc32 (instead of only crc8) of a
hexadecimal string?

Don

Btw, if you want a very efficient implementation, do a google search for
"Hacker's Delight". The website for this (very interesting) book has an
implementation of crc32 that is very well explained and along with that
is half a dozen or more implementations of it, each analyzed for
performance.

[Carsten Hansen]

"Don" <no**@spam.dk > wrote in message news:bg******** **@news.net.uni-c.dk...

"Carsten Hansen" <ha******@world net.att.net> wrote in message
news:eA******** *************@b gtnsc04-news.ops.worldn et.att.net...

"Glenn C. Rhoads" <gc******@yahoo .com> wrote in message
news:33******** *************** ***@posting.goo gle.com...

"Arthur J. O'Dwyer" <aj*@andrew.cmu .edu> wrote in message news:<Pi******* *************** *************@u nix44.andrew.cm u.edu>...

> On Wed, 30 Jul 2003, Mark A. Odell wrote:
>>
>> Pieter Droogendijk <gi*@binky.home unix.org> wrote...
>>>
>>> http://remus.rutgers.edu/~rhoads/Code/crc-32b.c
>>
>> I grabbed this and was confused by this function's use of 'int char'. >>
>> unsigned long get_crc( FILE *fp) /* calculate the crc value */
>> {
>> register unsigned long crc;
>> int char; <------------------ NOTE
>>
>> crc = 0xFFFFFFFF;
>> while ((char = getc(fp)) != EOF)
>> crc = ((crc>>8) & 0x00FFFFFF) ^ crc_table[ (crc^char) & 0xFF ]; >>
>> return( crc^0xFFFFFFFF );
>> }
>>
>> What's with the NOTE'd line. Could someone really have published a
>> function with this sort of error?
>
> Yes. :) That is absolutely ridiculous. Maybe the OP should look
> somewhere else for more reliable code, since this was obviously
> never tested in a real program.
>
> The lines
>
> #ifndef FILE /* if FILE type not defined */
> #include <stdio.h> /* then bring it in */
> #endif
>
> should also have raised several red flags. I'm going to mail
> the guy right away and point it out.
>
> http://www.google.com/search?q=crc32+ c+source&btnI=I 'mFeelingLucky
>
> -Arthur

From my email response:
The line "int char" is *not* a syntax error! In fact there is a very
good reason for using a variable of type "int" instead of "char." The
function "getc" can return any value from the character set *plus*
the special non-character value EOF. According to the C standard, the
type "char" is guaranteed to contain enough bits to hold all of the
values corresponding to the machine's character set; it is *not*
guaranteed to be able to hold the additional EOF value (without
possibly mixing up EOF with some actual character value). Thus, to
ensure that the code works across all implementations , you need to
declare the variable as an "int" instead of a "char." For
portability reasons, it is good practice to always declare character
data as type "int" except when you are declaring an array of
characters.
> (Also, the lines
>
> #ifndef FILE
> #include <stdio.h>
> #endif
>
> are suspicious; the #ifndef and #endif directives
> are completely useless and irrelevant there.)

I disagree with this claim too. There are two distinct methods of
making use of this crc code as part of a system library. First, you
may want to compile the crc code separately to generate an object
file only and then make the object file available as part of your
library while hiding the actual source code. Alternatively, you may
want to make the actual source code available and have the user
compile their source code and the crc source code together at once.
To use the first method, you need to include "stdio.h" so the
compiler will not complain about the type "FILE." But if include
"stdio.h" without the preprocessor directives #ifndef and #endif,
then you will run into a problem using the second method if your own
source code file also includes "stdio.h." Since I cannot know in
advance which method someone might use, I used the above method
to let you to use either method without running into a problem.
Having the #ifndef and #endif directives will not hurt you if your
preferred method does not need them.

The problem with

>> int char; <------------------ NOTE

is that char is a keyword. You cannot use it as an identifier for a
variable.

The problem with

> #ifndef FILE
> #include <stdio.h>
> #endif

is that FILE is not a macro. Hence it is not defined during the

preprocessor

stage of compilation, no matter whether <stdio.h> has previously been
included or not.
Moreover, the C standard explicitly allows a standard header to be

included

multiple times "with no effect different from being included only once".

So,

basically you have a wrong solution to a non-existing problem.

Finally, the masking in

>> crc = ((crc>>8) & 0x00FFFFFF) ^ crc_table[ (crc^char) &

0xFF ];

is superfluous. Right shifting of an unsigned is guaranteed to fill the
vacated bits with zeros.
Carsten Hansen

Ok. Thank you all for your help. I need to implement this crc32 check in a
microcontroller and I have a program now that states:

#define POLYNOMIAL (unsigned long)0x04c11db7

static unsigned long crc_table[256];

static void make_crc_table( ) {
unsigned int i, j;
unsigned long h = 1;
crc_table[0] = 0;
for (i = 128; i; i >>= 1) {
h = (h >> 1) ^ ((h & 1) ? POLYNOMIAL : 0);
/* h is now crc_table[i] */
for (j = 0; j < 256; j += 2*i)
crc_table[i+j] = crc_table[j] ^ h;
}
}
unsigned long crc32(unsigned long crc, char const *buf, unsigned int len)

{ if (crc_table[255] == 0)
make_crc_table( );
crc ^= 0xffffffff;
while (len--)
crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
return crc ^ 0xffffffff;
}
main(){
unsigned char temp[10];
unsigned long mycrc;

temp[0] = 0x55;
temp[1] = 0x77;
temp[2] = 0x78;
temp[3] = 0x45;
temp[4] = 0x89;
temp[5] = 0x03;
temp[6] = 0x89;
temp[7] = 0x87;
temp[8] = 0x65;
temp[9] = 0x91;

mycrc = crc32(mycrc,tem p,10);

}

This gives me mycrc = 0xfe7c9148

I would like to cross-check this with some program or similar. Does anyone
know of a program similar to:
http://www.smbus.org/faq/crc8Applet.htm
Making me capable of calculating the crc32 (instead of only crc8) of a
hexadecimal string?

Don

Your program has undefined behavior. You never initialize mycrc.
There are many variations on CRC. The one you are using here is not the most
common.
Usually one uses the reflected polynomial (0xEDB88320) to the one you are
using here.
Here are some references:
Michael Barr (mb***@netrino. com)
Wrote Easier Said Than Done, a less-confusing guide to implementing CRC
algorithms. (Originally published as "Slow and Steady Never Lost the Race"
in the January 2000 issue of Embedded Systems Programming, pages 37-46.)
Ross N. Williams
Wrote A Painless Guide to CRC Error Detection Algorithms, a definitive
source of CRC information.

Carsten Hansen

[bd]

On Wed, 30 Jul 2003 17:41:47 -0700, Glenn C. Rhoads wrote:

"Arthur J. O'Dwyer" <aj*@andrew.cmu .edu> wrote in message news:<Pi******* *************** *************@u nix44.andrew.cm u.edu>...

On Wed, 30 Jul 2003, Mark A. Odell wrote:

Pieter Droogendijk <gi*@binky.home unix.org> wrote...

http://remus.rutgers.edu/~rhoads/Code/crc-32b.c

I grabbed this and was confused by this function's use of 'int char'.

unsigned long get_crc( FILE *fp) /* calculate the crc value */
{
register unsigned long crc;
int char; <------------------ NOTE

crc = 0xFFFFFFFF;
while ((char = getc(fp)) != EOF)
crc = ((crc>>8) & 0x00FFFFFF) ^ crc_table[ (crc^char) & 0xFF ];

return( crc^0xFFFFFFFF );
}

What's with the NOTE'd line. Could someone really have published a
function with this sort of error?
Yes. :) That is absolutely ridiculous. Maybe the OP should look
somewhere else for more reliable code, since this was obviously
never tested in a real program.

The lines

#ifndef FILE /* if FILE type not defined */
#include <stdio.h> /* then bring it in */
#endif

should also have raised several red flags. I'm going to mail
the guy right away and point it out.

http://www.google.com/search?q=crc32+ c+source&btnI=I 'mFeelingLucky

-Arthur

From my email response:
The line "int char" is *not* a syntax error! In fact there is a very
good reason for using a variable of type "int" instead of "char." The
function "getc" can return any value from the character set *plus*
the special non-character value EOF. According to the C standard, the
type "char" is guaranteed to contain enough bits to hold all of the
values corresponding to the machine's character set; it is *not*
guaranteed to be able to hold the additional EOF value (without
possibly mixing up EOF with some actual character value). Thus, to
ensure that the code works across all implementations , you need to
declare the variable as an "int" instead of a "char." For
portability reasons, it is good practice to always declare character
data as type "int" except when you are declaring an array of
characters.

The question is of whether 'char' is a legal variable name, I think.

(Also, the lines

#ifndef FILE
#include <stdio.h>
#endif

are suspicious; the #ifndef and #endif directives
are completely useless and irrelevant there.)
I disagree with this claim too. There are two distinct methods of
making use of this crc code as part of a system library. First, you
may want to compile the crc code separately to generate an object
file only and then make the object file available as part of your
library while hiding the actual source code. Alternatively, you may
want to make the actual source code available and have the user
compile their source code and the crc source code together at once.
To use the first method, you need to include "stdio.h" so the
compiler will not complain about the type "FILE." But if include
"stdio.h" without the preprocessor directives #ifndef and #endif,
then you will run into a problem using the second method if your own
source code file also includes "stdio.h."

No. Including stdio.h twice is harmless, and FILE may be a typedef, or
some sort of internal compiler magic, not a #define. As such, the #ifndef
is useless.
Since I cannot know in
advance which method someone might use, I used the above method
to let you to use either method without running into a problem.
Having the #ifndef and #endif directives will not hurt you if your
preferred method does not need them.

--
Freenet distribution not available
We were so poor we couldn't afford a watchdog. If we heard a noise at night,
we'd bark ourselves.
-- Crazy Jimmy

[bd]

On Fri, 01 Aug 2003 06:35:59 -0700, Glenn C. Rhoads wrote:

"Arthur J. O'Dwyer" <aj*@andrew.cmu .edu> wrote in message news:<Pi******* *************** **************@ unix46.andrew.c mu.edu>...

On Thu, 31 Jul 2003, Glenn C. Rhoads wrote:

"Carsten Hansen" <ha******@world net.att.net> wrote...
> "Glenn C. Rhoads" <gc******@yahoo .com> wrote in message [I wrote:]

>> (Also, the lines
>>
>> #ifndef FILE
>> #include <stdio.h>
>> #endif
>>
>> are suspicious; the #ifndef and #endif directives
>> are completely useless and irrelevant there.)
>
> I disagree with this claim too.

The problem with
>> #ifndef FILE
>> #include <stdio.h>
>> #endif
is that FILE is not a macro. Hence it is not defined during the
preprocessor stage of compilation, no matter whether <stdio.h> has
previously been included or not.

Yes.

Moreover, the C standard explicitly allows a standard header to be
included multiple times "with no effect different from being included
only once". So, basically you have a wrong solution to a non-existing
problem.

I guess you've never run into a traditional K&R compiler. With such
a compiler, you cannot bring in header files more than once.

As a matter of fact, since K&R C didn't use the standard headers, the
line #include <stdio.h> would probably cause a significant percentage
of pre-ANSI compiler to barf entirely. And, of course, no K&R C compiler
would get beyond

void gen_table(void)

without producing some *very* interesting error messages.

Mine worked fine without a single error message.

Then you're not using a K&R C compiler, are you?

This
code was written several years ago when the above was standard usage
because back then, you could reasonably run into a K&R compiler and
there is no other good way to do it on such a compiler. And it still
works on a modern ansi-C compiler.

Unfortunately, the "fix" now posted at
http://remus.rutgers.edu/~rhoads/Code/crc-32b.c
is even worse than the original.

While the original #ifndef was valid, if silly and useless,
the new version reads

#ifndef _PRINTF_H /* defined in stdio.h */
#include <stdio.h>
#endif

which is absolutely ridiculous! No compiler will #define _PRINTF_H
for you,

This is defined at the top of "stdio.h"

Maybe on your system. I just compiled:

#include <stdio.h>
#ifdef _PRINTF_H
#error _PRINTF_H defined
#else
#error _PRINTF_H not defined
#endif

And got:
foo.c:5:2: #error _PRINTF_H not defined
There are two c compilers available on the system I most commonly use,
Sun's cc compiler and the Gnu-c compile (gcc). To double check, I just
tested the above on both of them and it worked correctly. So much for
the claim that no compiler will do this.

They don't. However, stdio.h may be #included more then once.

and no user can safely #define _PRINTF_H for you, either,
because that identifier is "reserved for any use" by the Standard.

I repeat, the correct C89 (ANSI C) solution is

#include <stdio.h>

And that doesn't work on every compiler I have access to
(it does on Sun's cc compiler and the gnu-c compiler).

Which don't they work on?

and the correct K&R solution is (a) to get rid of all those 'void'
keywords (and maybe that 'register unsigned long', although in the
absence of my K&R1 I'll let Dan or somebody handle that), and
(b) to let the client worry about it.

-Arthur

You are free to get rid of the #defines if you wish but I refuse
to change what works on every compiler I have access to, to something
that works on most but all of them.

--
Freenet distribution not available
BOFH Excuse #72:

Satan did it