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

From: [email-masked]
Date: Sun, 4 Mar 2001 21:33:05 +0200

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" <[email-masked]> on 04/03/2001 18:58:27

Please respond to "Douglas Otis" <[email-masked]>

To:   [email-masked]
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 <[email-masked]> on 02/03/2001 15:42:25
>
> Please respond to John H Howard <[email-masked]>
>
> To:   Douglas Otis <[email-masked]>
> cc:   IPS Reflector <[email-masked]>
> 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
>
>
>
>

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 5 Mar 2001 14:34:54 -0800

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

---

From: "Douglas Otis" <[email-masked]>
Date: Mon, 5 Mar 2001 15:57:38 -0800

Sorry again, the example should have said 256 entry table as this will
comprise 1024 bytes.

Doug