Re: Review: CRC Library

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-03-12 16:25:11

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 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.

> - 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.

> - 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.

> - 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.

> * 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 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.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com