Re: bugs in CRC32

[Federico Montesino Pouzols]

        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