bugs in CRC32 (copy)

[Chad Yates]

I just started recieving list messages again today.  It appears that my
previous messages were lost, so I'm forwarding them again...

I did a little research -- I'm not an expert on CRC algorithms, allthough I
might be after all this ;)

I did a myriad of searches on google to see if I could find out how many
different versions of crc32 there are.  I had hoped to find a definite
answer, however, that doesn't seem to be the case.  I found a document that
discusses this problem
(http://ce.sharif.edu/~cheraghchi/science/cs/crc_algorithm.htm if
interestd).

it appears that the most common CRC32 version is the one for ethernet, and
according to the above, is also "reportedly used in PKZip, AUTODIN II,
Ethernet, and FDDI."  I'm not familiar with ATM, so don't know if it uses a
different version.

anyway, according to the docs above this version has these distinguishing
attributes. (The Check: value is the result of running it against
'123456789').

   Name   : "CRC-32"
   Width  : 32
   Poly   : 04C11DB7
   Init   : FFFFFFFF
   RefIn  : True
   RefOut : True
   XorOut : FFFFFFFF
   Check  : CBF43926

The fsum program I've been using to validate some of my tests also generates
that number:

  ; SlavaSoft Optimizing Checksum Utility fsum 2.0 <www.slavasoft.com>
  ; Generated on 01/06/03 at 14:19:17
  cbf43926 ?CRC32*check.txt

So, it should be pretty safe to assume that it is implementing the same
version of the algorithm.  the changes I made bring it into check with that
version.  It's really a shame that there is the possiblilyt of multiple
versions masquerading as "CRC32"  we may need to create 2 or more versions
if we want to cover both the old and new versions.  perhaps the code could
be templatized (using template values) and be instantiated into digest.cpp
for CRC, CRC16, CRC32_Ethernet, CRC32_ATM, etc... or , if those weren't
enough they could just use the template directly like so:

  CRC<32, 0x04C11DB7, 0xFFFFFFFF, true, true, 0xFFFFFFFF>

Its an idea anyway :)  I might even be willing to pursue it if it sounds
useful (for educational reasons)

another idea may be to copy the code from the above doc (it says the code is
public domain) and then have the commoncpp2 classes call it with the right
parms.  I don't know if it's fast or not.  the current CRC32 creates tables
everytime it's called, so I'd say it's not exactly efficient either (maybe
the initialization should be moved to a class initializer?)

thoughts?

,Chad


>       As for the algorithm results, either the cc++ implementation
> or the two programs appear to be wrong. However, the three tests of
> the crc32 demo are the official examples of the ATM standard. Do those
> two programs you mention provide the result expected in the demo for
> the three tests?  They may be using a different generator polynomial.
>
> On Thu, Jan 02, 2003 at 05:59:38PM -0800, Chad Yates wrote:
> > I have discovered and fixed some bugs in the CRC32Digest class while
> > developing test cases for the digest classes.
> >
> > 1) the virtual function overflow was not being called (at least
> on win32) so
> > I changed the argument and return type to int (as in the other digest
> > classes)...
> >
> > 2) the lookup table was not using "reflection" during its initialization
> > (apparently this is a part of the CRC32 standard
> implementation) so I added
> > a reflect function and changed (replaced) the lookup code to use it. I
> > commented out the old code so you can see it in the diff.
> >
> > 3) I moved the crc32 = 0 from the constructor to the initDigest
> method so it
> > is reset both during construction and reseting.
> >
> > 4) I removed the crc32 = ~crc_reg in the overload method and moved it to
> > both the getDigest and strDigest methods as a minor performance
> improvement
> > (won't be re-computed for every octet in the stream)
> >
> > finally, I checked the output agains two programs available on
> the net, and
> > it matches both, however the existing CRC32 demo program now reports all
> > failures.  I suspect that the tests were not valid to begin with, but if
> > anyone would like to verify this (or comment) please do so.
> >
> > ,chad
> >
> > Index: digest.h
> > ===================================================================
> > RCS file: /cvsroot/commoncpp/commoncpp2/include/cc++/digest.h,v
> > retrieving revision 1.10
> > diff -r1.10 digest.h
> > 204c204
> > <    unsigned char overflow(unsigned char octet);
> > ---
> > >    int overflow(int octet);
> > 207c207,209
> > <
> > ---
> > >
> > >    unsigned long reflect(unsigned long ref, unsigned char ch);
> > >
> >
> > Index: digest.cpp
> > ===================================================================
> > RCS file: /cvsroot/commoncpp/commoncpp2/src/digest.cpp,v
> > retrieving revision 1.4
> > diff -r1.4 digest.cpp
> > 145d144
> > <    crc32 = 0;
> > 161,172c160,182
> > <    for (i = 0; i < 256; i++)
> > <    {
> > <       crc = ( (unsigned long) i << 24 );
> > <       for (j = 0; j < 8; j++)
> > <       {
> > <          if (crc & 0x80000000)
> > <             crc = (crc << 1) ^ POLYNOMIAL;
> > <          else
> > <             crc <<= 1;
> > <       }
> > <       crc_table[i] = crc;
> > <    }
> > ---
> > >   for(i = 0; i <= 0xFF; i++)
> > >   {
> > >     crc=reflect(i, 8) << 24;
> > >     for (j = 0; j < 8; j++)
> > >       crc = (crc << 1) ^ (crc & (1 << 31) ? POLYNOMIAL : 0);
> > >     crc_table[i] = reflect(crc, 32);
> > >   }
> > >   /* old loop without reflection
> > >   for (i = 0; i < 256; i++)
> > >   {
> > >     crc = ( (unsigned long) i << 24 );
> > >     for (j = 0; j < 8; j++)
> > >     {
> > >       if (crc & 0x80000000)
> > >         crc = (crc << 1) ^ POLYNOMIAL;
> > >       else
> > >         crc <<= 1;
> > >     }
> > >     crc_table[i] = crc;
> > >   }
> > >   */
> > >
> > >    crc32 = 0;
> > 175c185,201
> > < unsigned char CRC32Digest::overflow(unsigned char octet)
> > ---
> > > unsigned long CRC32Digest::reflect(unsigned long ref,
> unsigned char ch)
> > > {
> > >   unsigned long value = 0;
> > >
> > >   // Swap bit 0 for bit 7
> > >   // bit 1 for bit 6, etc.
> > >   for(int i = 1; i < (ch + 1); i++)
> > >   {
> > >     if(ref & 1)
> > >       value |= 1 << (ch - i);
> > >     ref >>= 1;
> > >   }
> > >
> > >   return value;
> > > }
> > >
> > > int CRC32Digest::overflow(int octet)
> > 177,179c203,206
> > <    crc_reg = crc_table[((crc_reg >> 24) ^ octet) & 0xFF] ^
> (crc_reg << 8);
> > <    crc32 = ~crc_reg;
> > <
> > ---
> > >    //crc_reg = crc_table[((crc_reg >> 24) ^ octet) & 0xFF] ^
> (crc_reg <<
> > 8);
> > >        crc_reg = (crc_reg >> 8) ^ crc_table[(crc_reg & 0xFF) ^ octet];
> > >    //crc32 = ~crc_reg; deferred calculation until later
> rather than for
> > every
> > byte
> > >
> > 184a212
> > >    crc32 = ~crc_reg; // finalize crc32 before exporting
> > 198a227
> > >    crc32 = ~crc_reg;  // finalize crc32 before exporting
> >
> >
> >
> > _______________________________________________
> > Bug-commoncpp mailing list
> > address@hidden
> > http://mail.gnu.org/mailman/listinfo/bug-commoncpp