Re: [boost] Re: Review: CRC Library

From: Doug Gregor (gregod_at_[hidden])
Date: 2001-03-12 23:44:20

On Monday 12 March 2001 04:25, you wrote:
> on 3/12/01 12:37 AM, Doug Gregor at gregod_at_[hidden] wrote:
> > Disclaimer: I know very little about CRC computations, so I can make no
> > comment as to the algorithmic correctness of the CRC library.
>
> I just adapted the code I saw in some Internet papers to C++.  I made
> changes to support multiple objects.  (The original code used globals.)
>
> > Comments
> > ----------
> > * Naming:
> > - If crc_fast will be used most (all?) of the time, perhaps it should be
> > renamed just to "crc"?
>
> I named it "crc_fast" to counter the other class's name "crc_slow."  I have
> more to say at your free-function comment.
>
> > - operator* seems an awkward choice for returning the current CRC value.
> > Perhaps a member function "value" would be more readable.
>
> OK.
>
> > * Interface:
> > -crc_slow takes a the number of bits whereas crc_fast takes a number of
> > bytes, which may be confusing. Suggestion: use bits for both and add a
> > static assert ensuring that bits is a multiple of
> > std::numeric_limits<unsignedc har>::digits.
>
> I used byte counts for "crc_fast" since that is what that class template
> works in, and so the user doesn't have to remember the number of bits per
> byte.  I'm not sure the second point is valid since CRCs are bit sensitive
> anyway.

I can see three reasons for using bit counts for the crc_fast interface:
        1) crc_slow uses bit counts (and should use bit counts). Because crc_fast 
and crc_slow perform the same calculations, the interfaces should be 
consistent. Looking through the test code the first time it was very shocking 
for me to see:
        crc_slow<32>  crc_32 // ...
        followed by
        typedef crc_fast<4, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>
              crc_32_type
        
        2) A quick web search came up with many more references to N-bit CRC's than 
M-byte CRC's, so it appears that the general concensus is to use bits. 

        3) Bits are a known quantity, 0 or 1. Bytes are not. Though almost any 
system one could find will have 8-bit bytes, it isn't necessary and probably 
shouldn't be relied upon for an interface.

Perhaps someone else can chime in with a convincing argument either way.

> I may add a stricter requirement: that the bit count has to exactly match a
> built-in type.  For example, if we have an 8-bit byte, 2-byte, and 4-byte
> types; we would only allow 8, 16, and 32 as bit values.  That way I don't
> have to worry about extra bits.

It may be useful in the future to have the capability to strip off the extra 
bits (i.e., a 16-bit CRC on a 64-bit processor would likely be computed 
faster in a 32 or 64-bit register). Isn't this capability already available 
(hence the masking constants)?

> > - The ability to specify an initial remainder as part of the constructor
> > might be useful. For instance, if you wanted to pick up calculation of a
> > CRC but only have the remainder still (not the crc_fast object used).
>
> OK.
>
> > - Free functions that calculate CRCs for a block of data and return the
> > resulting CRC value would easy usage.
>
> Sounds neat.  If I do this, I think this function (template) would get the
> "crc" name.

Sounds great. Perhaps even something that would choose crc_fast if the 
specified number of bits can be computed with the faster version, but falls 
back to crc_slow otherwise?

> > - The addition of typedefs for common CRC types would greatly help.
>
> I mentioned to John Maddock that there may be no "common" CRC types, at
> least not an exhaustive list.
>
> > * Implementation:
> > - The nontype template parameters TruncPoly, InitRem, and FinalXor all
> > have type "unsigned long". The parameters' types would more accurately be
> > described by
> > "typename detail::bit_traits<(Bytes *
> > detail::bits_per_byte)>::fast_type".
>
> I originally was going to do something like that, but:
>
> 1.  The template argument would look big & ugly.
> 2.  I found out later that my compiler doesn't support this.  So I would
> have no way to test the code myself.
> 3.  I could put the code in anyway with a #define from <boost/config.hpp>
> to separate the two versions, but the code would get even bigger & uglier.

It seems that it could be done without mucking up too much code:

#ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
#  define BOOST_CRC_PARM_TYPE typename detail::bit_traits<(Bytes *\ 
detail::bits_per_byte)>::fast_type
#else
#  define BOOST_CRC_PARM_TYPE unsigned long
#endif

Then just use BOOST_CRC_PARM_TYPE instead of "unsigned long". 

GCC can handle dependent types as template parameters, and it is more than 
likely available for your platform of choice if you want to try it.

> > - The following two expressions, ~( ~(value_type( 0u )) << Bits ) and
> > ~( ~(fast_type( 0u )) << Bits ), cause errors on Comeau 4.2.44 because
> > shifting by >= the number of bits in an integral type invokes undefined
> > behavior. Suggestion:
> > template<typename Type> struct all_bits_significant {
> > BOOST_STATIC_CONSTANT(Type, value = ~((Type)0));
> > };
> >
> > template<typename Type, int Bits> struct low_bits_significant {
> > BOOST_STATIC_CONSTANT(Type, value = ~( ~(value_type( 0u )) << Bits ));
> > };
> >
> > Then use a meta-IF, i.e.,
> > IF<(Bits ==std::numeric_traits<fast_type>::digits),
> > all_bits_significant<fast_type>,
> > low_bits_significant<fast_type, Bits> >::type::value
> >
> > - The two aforementioned expressions really need a comment
>
> It seems that everyone has a different problem with this code.

I think it is the same problem all around - it invokes undefined behavior, 
and different compilers are doing things differently. 

> > * General:
> > - The test code is very short. Is a more comprehensive testsuite
> > available or are these tests sufficient?
>
> All the code does is process bytes and returns checksums.  What more is
> there to test?

I understand that it only returns checksums, but the test code tests one set 
of data (with several different CRC types). I assume that's sufficient, but 
it raises an eyebrow when there are seven hardcoded testcases for 600 lines 
of code.

Also, if the capability is kept in the library, has crc_fast been tested with 
fewer bits than exist in the fast_type (i.e., a 24-bit CRC in a 32-bit type)?

> > I think the CRC library should be accepted into Boost provided the
> > portability concerns (i.e., that John Maddock has reported) are
> > addressed.
>
> Thanks.  It seems that all the portability stuff could be a nightmare.
> Maybe I'll switch to std::bitset for the crc_slow code.

        Doug