Re: CRC review

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

on 3/11/01 7:31 AM, John Maddock at John_Maddock_at_[hidden] wrote:

> Following on from yesterday, I've been investigating the CRC problems some
> more:
> 
> I had to modify the code (again) to get it to build with gcc, the good news
> is that it runs successfully under gcc (updated code attached -
> fast_crc::operator* contained some borderline illegal code).

I've looked at it.  What's wrong with it?  I'm calling a "const" member
function of a temporary object; isn't that OK?  I've seen it in some C++
books, and I use it in crc_fast's constructor.  (I have no choice there
unless I stop using an initializer list.)

> With VC6 I've tracked the problem down to the reflect code - for some
> reason reflect is getting called not as reflect<8>, but as reflect<1>, this
> is the cause of the problem here, and I've added some debugging assertion
> code to help track this down (see attached header). However what I don't
> have is any kind of solution.

I'll probably turn that to a test in "crc_test.cpp".

> I still don't know what the problem is with the Borland compiler - except
> that it's nothing to do with reflect which is working fine here.
> 
> At this point some more general comments are probably in order:
> 
> Implementation:
> ~~~~~~~~~~
> What on earth is:
> ~( ~(value_type( 0u )) << Bits
> supposed to mean, isn't ~(~0u) alway zero or am I missing something?  If so
> some kind of explanatory comment would be nice :-)

You're missing a parenthesis here; there's supposed to be one after "Bits."
What the code does is:

1.  value_type(0u) returns the all-zeros bit pattern
2.  ~(answer[1]) returns the all-ones bit pattern
3.  answer[2] << Bits returns a number with the lower "Bits" bits zero and
the higher bits as ones
4.  ~(answer[3]) returns a mask for the lowest "Bits" bits

> Names:
> ~~~~~
> 
> Don't care what you call crc_slow - it's probably only of academic interest
> anyway?  But crc_fast may as well just be called "crc" IMO.
> 
> Also most people will never use the crc template directly, instead I would
> like to see a set of typedefs for the "standard" crc parameters.  Most
> people (like me!) will have no idea which parameters they should be using
> in any case and will just want a particular crc implementation:
> 
> typedef crc_fast<2, 0x1021, 0xFFFF, 0, false, false>  crc_ccitt;
> typedef crc_fast<2, 0x8005, 0, 0, true, true>  crc16;
> typedef crc_fast<4, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>  crc32;

I don't think there are "standard" CRC parameters.  I picked the ones above
as examples because those were the examples used in the Internet papers I
read.  If I use other types, I would have to compute the "123456789"
reference CRC result by hand as a check; which isn't easy.  (I took about a
half-hour doing the 1-bit example that is in the test.)

Another problem is that an application might say that it uses a CRC, stating
it like there was only one.  If the application's documentation doesn't give
a complete description of the CRC type, then we would have to dig through
the source code.  If the source uses a CRC table, but has no hints on how it
was generated, then we're stuck short of doing an exhaustive reverse
engineering effort.

The "crc32" type given is sort-of common since it is used in Ethernet, ZIP
files, and some other computer applications.

> The docs should then reflect the fact that most people will be using these
> rather than the templates directly - indeed it should be emphasised that
> they should not use the templates directly unless they really *really* know
> what they're doing!
> 
> Interface:
> ~~~~~~
> 
> I don't like the use of operators in the crc_fast interface - with the
> possible exception of operator()(unsigned char) I don't see what these gain
> you: crc's are not iterators, smart pointers, or even function objects
> (strictly speaking function objects aren't supposed to have state - but
> this is an open issue - hence the exception for operator()(unsigned char)
> for use with std::for_each).
> 
> I would change operator* to:
> 
> value_type  value() const;
> 
> and operator() to :
> 
> void  add( unsigned char byte );
> template <class InputIterator>
> void  add( InputIterator bytes_begin, InputIterator bytes_end );
> void  add( void const *buffer, ::std::size_t length );

I still need the version that takes two void-pointers, since that's the main
version that the other ones call.  If I keep an operator() that takes a
single unsigned-char, then you can run iterators through with std::for_each.
I think I would need an iterator processor for crc_slow, since that class
isn't suitable as a function object.

> I would also add overloads for char and signed char for completeness, the
> choice of the name "add" is moot here, maybe someone can come up with
> something better?

The unsigned-char version should cover the others by implicit conversion.
For a name, maybe "process"?

> Again that's all for now...

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