Re: Review: CRC Library

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-03-13 13:23:36

on 3/12/01 11:44 PM, Doug Gregor at gregod_at_[hidden] wrote:

> On Monday 12 March 2001 04:25, you wrote:
>> on 3/12/01 12:37 AM, Doug Gregor at gregod_at_[hidden] wrote:
[SNIP]
>>> * 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'm agreeing with you.

>> 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)?

Yes.  I'll find a way to make the masking constants work reliably.

[SNIP]
>>> - 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?

Maybe.  I would have to make sure that the two classes keep a compatible
interface.

[SNIP]
>>> * 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".

OK.

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

I'm on one of the major platforms without GCC.  ;_;

[SNIP]
>>> * 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)?
[TRUNCATE]

No, it hasn't.  I've only used the tests that had results in the Internet
papers I read.  I did the one-bit example by hand as a check.

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