RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

["Douglas Otis" <dotis@sanlight.net>]

Julian,

The memory referencing technique used to compute CRC without processing each
bit separately requires two accesses to memory, one for the data being
processed and once again for a translation against this data, an index into
a table as you have described.  In the C code it looks as if there is a
single memory reference and perhaps this is your confusion.  As memory runs
at a slower rate than instructions for any looping algorithm, such access
was my concern regarding your statement about Alder-32 and CRC-32 having
equivalent overhead.  For any confusion that I have caused in expressing
this opinion, I am sorry.

Here is an example using a 256 byte table but should provide an
understanding why 64k tables are desired as you indicated:

  unsigned char* dat_buf;
  unsigned long crc_syn = 0xffffffff;

  while(length--)
    crc_syn = (crc_syn >> 8) ^ crc32_table[(crc_syn & 0xff) ^ *dat_buf++];

  return (crc_syn ^ 0xffffffff);

Doug

> Doug,
>
>
> There is no lookup in CRC computation.
>
> A table entry (indexed by the code) is used in computation.
>
> I would appreciate if you would not spread confusion.
>
> Julo
>
>
>
> "Douglas Otis" <dotis@sanlight.net> on 04/03/2001 18:58:27
>
> Please respond to "Douglas Otis" <dotis@sanlight.net>
>
> To:   ips@ece.cmu.edu
> cc:
> Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt
>
>
>
>
> Julian,
>
> Errors being detected are not created by a media defect or an impulse on a
> serial line.  CRC serial burst error detection will be in place on the
> serial medium so focus on burst errors seems misplaced.  Also,
> CRC requires
> a relatively expensive lookup compared to an algorithm that only accesses
> data being checked.  I would not be surprised the difference running 2:1
> for
> most architectures.  The suggestion by John Howard sounds interesting for
> small regions of less than 512 bytes.
>
> Doug
>
> > John,
> >
> > We all due respect I disagree with both your statements:
> >
> > - CRC is not expensive in software if you are willing to spend some
> memory
> > for tables
> >    and literature about how to do it is abundant.
> >
> > - Adler and Fletcher are weak and there is no theory behind your
> > distribution statements, nor any simulation results as far as I
> know.  We
> > found that on very simple sequences the Hamming distance gets
> > down to 2 (or
> > lower) and the burst protection is probably not better than 16 bit.
> There
> > is even a simple formula for what sequences will get you false
> codes (see
> > bellow for a reference)
> >
> > - CRC gets you alway a 32 bit burst protection and that makes for a very
> > low probability for undetected burst and a guaranteed Hamming
> > distance of 3
> > (or higher blocks up to 2k). There seems to exist also a class of
> > CRCs that
> > are excellent for very long blocks with distances higher than 4.
> >
> > Computing the undetected error probability was never published
> > for Adler or
> > Flletcher and adding thhis to the lack of theoretical background make it
> a
> > very poor choice for a data storage platform.
> >
> >
> > If you want some theory background please read:
> >
> > http://www.haifa.il.ibm.com/satran/ips/draft-sheinwald-iSCSI-CRC-00.txt
> >
> >
> > You will find there both theoretical references and CRC implementation
> > references that include even code.
> > We are planing to update it with some newer CRCs.
> >
> > Regards,
> > Julo
> >
> >
> > John H Howard <jhh@sun.com> on 02/03/2001 15:42:25
> >
> > Please respond to John H Howard <jhh@sun.com>
> >
> > To:   Douglas Otis <dotis@sanlight.net>
> > cc:   IPS Reflector <ips@ece.cmu.edu>
> > Subject:  Re: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt
> >
> >
> >
> >
> >
> > CRC-32 is very expensive in software; it may require hardware assist in
> > fast networks.  Is iSCSI really intended to be a hardware only protocol?
> >
> > Fletcher-32 has a serious flaw:  it does not distinguish between an
> > input halfword of all ones (FFFFx) and an input halfword of all zeros
> > (0000x).  Both are equal to zero under ones' complement addition.
> > [Stone, J., Greenwald, M., Partridge, C., & Hughes, J., "Performance of
> > Checksums and CRC's over Real Data", IEEE/ACM Trans. on Networking,
> > Vol., 6, No. 5, October 1988] gives several examples of situations in
> > which this is important.
> >
> > Adler-32 avoids this problem by adding 8-bit inputs into its 16-bit
> > sub-sums.  It also uses a prime modulus (2**16-15) rather than ones'
> > complement's 2**16-1.  Using 8 bit rather than 16 bit inputs doubles the
> > number of additions Adler-32 performs compared to Fletcher-32.  A more
> > subtle problem is that the high-order bits of the sums are not uniformly
> > distributed until the block size becomes very large.  I estimate that
> > this causes Adler-32 to lose one or two bits worth of resolving power.
> > Still, a 30 bit checksum is still quite strong.
> >
> > An alternative worth consideration is Fletcher-32 modified to use the
> > prime modulus 2**16-15.  It's fast, doesn't have the 0000=FFFF problem,
> > detects permutations, and distributes all result bits uniformly.  It
> > does confuse an input halfword of 0 with 2**16-15 (and similarly for
> > 1..14), but I think this only a minor problem because the potentially
> > confused inputs are unlikely.  By definition every checksum confuses
> > many inputs.  If you are going to argue from bad examples you really
> > should estimate how likely your bad examples are.
> >
> > John Howard
> > Sun Microsystems
> >
> >
> >
> >
>
>
>
>
>