Subject: RE: clarification please

From: "CAVANNA,VICENTE V (A-Roseville,ex1)" <[email-masked]>
Date: Wed, 12 Dec 2001 15:55:37 -0700

Hi Paul,
I used to agree with you on this, and that is what I had also communicated
to Luben ( it was I who originally asked Julian to put in the iSCSI spec the
same initial conditions for the CRC register as in ethernet), but ...
based on your description, the circuit you appear to have in mind is the
circuit that performs simultaneous multiplication by x^32 and division by
G(x). When you go through the same reasoning for the circuit that performs
only division (and thus requires you to perform the pre-multiplication by
x^32 externally) your two descriptions appear not to be equivalent; and that
surprised me! Please refer to my recent memo to the reflector "effect of
initializing ..." for details.
Vince

|-----Original Message-----
|From: Paul Koning [mailto:[email-masked]]
|Sent: Monday, December 10, 2001 9:23 AM
|To: [email-masked]
|Cc: [email-masked]
|Subject: Re: clarification please
|
|
|>>>>> "Luben" == Luben Tuikov <[email-masked]> writes:
|
| Luben> Hello, I have a question.  The draft says: - the CRC register
| Luben> is initialized with all 1s (equivalent to complementing the
| Luben> first 32 bits of the message)
|
| Luben> Those two are NOT equivalent, e.g. if the message started with
| Luben> 32 1's then complementing will yield 32 0's, and this is not
| Luben> like ``initializing'' the CRC with 32 1's?
|
| Luben> Does this mean that the first 32 most significant bits of the
| Luben> message are complemented, or does it mean that the message is
| Luben> _prefixed_ with 32 1's and then the division starts?
|
| Luben> If it means prefixing, could you please use that word, as is
| Luben> customary in computer science literature... and to diminish
| Luben> ambiguities...
|
|It does NOT mean prefixing.  The wording about "complementing" comes
|directly from the Ethernet spec, and is common to all recent CRC
|algorithms. 
|
|The wording in the spec implies that the following two descriptions
|are equivalent:
|
|1. Initialize the CRC register to all 1s, then process the data
|2. Initialize the CRC to all 0s, complement the first 32 bits of the
|   data, then process it
|
|Consider a packet that begins with 32 bits of 1.  It's obvious that
|the second description will result in an all-zero CRC register after
|those 32 bits have been processed.
|
|The first description has the same effect.  For each bit, you shift
|out a 1 from one end; that is XORed with the data bit, resulting in a
|zero shifting into the other end, and the other bits remaining the
|same.  Do that 32 times and you end up with an all-zero CRC register,
|just as for description 2.
|
|Incidentally, this implies that this CRC will not detect the insertion
|of any number of 0 bits immediately after a packet beginning of 32
|bits of 1.  That's a fine tradeoff, since that error pattern is a lot
|less likely than simply having extraneous 0 bits at packet start --
|which is why the complement was introduced into datacomm CRC
|algorithms. 
|
|     paul
|

---

From: Paul Koning <[email-masked]>
Date: Wed, 12 Dec 2001 18:02:05 -0500 (EST)

>>>>> "Vince" == A-Roseville,ex1  <CAVANNA> writes:

 Vince> Hi Paul, I used to agree with you on this, and that is what I
 Vince> had also communicated to Luben ( it was I who originally asked
 Vince> Julian to put in the iSCSI spec the same initial conditions
 Vince> for the CRC register as in ethernet), but ...  based on your
 Vince> description, the circuit you appear to have in mind is the
 Vince> circuit that performs simultaneous multiplication by x^32 and
 Vince> division by G(x). When you go through the same reasoning for
 Vince> the circuit that performs only division (and thus requires you
 Vince> to perform the pre-multiplication by x^32 externally) your two
 Vince> descriptions appear not to be equivalent; and that surprised
 Vince> me!

I suspect that you're right.

The circuit I'm referring to is the classic LFSR based CRC
implementation, described in Appendix C of the Ethernet spec (and seen
in software implementations in many places; I think I quoted
linux/drivers/net/ewrk3.c in the past).  That one indeed does the
multiplication along with the division.

I haven't seen circuits that do the division only, and I'm not sure I
could generate an example of what one might look like.

      paul

---

From: Luben Tuikov <[email-masked]>
Date: Wed, 12 Dec 2001 21:17:55 -0800 (PST)

I've been sticking closely to the iSCSI draft,
some papers I found on CRC and CRC32/4, some
lecture notes, my abstract algebra lecure notes and
approached the CRC computation from a purely
mathematical model showing the exact origin of the
``magic'' value of 0x1c2d19ed, using pure algebra.

The two methods which I refer to are not equivalent,
since they do not produce the same remainder, R(x),
when it is computed at the sender.

Please see the 1 page worksheet attached for the math.

In a software implementation:
1. I assume straightforward poly division (table lookup,
shifting, whatever).

2. Premultiplication by x^32 (deg of generator poly).
E.g. appending 32 0s. This is so that when ~R(x) is added,
the message bits are unchanged!

3. Prefixing by 32 1s. E.g. CRC = 31 1's and then
the message bits are fed in from the right, popping out
the left. Logically this is s.t. a sequence of 1 or more
0s at the start of a message are detected.

The aforementioned steps, get the right CRC for the
all 0s example in the iSCSI draft but the rest three
examples are not correct.

Now if I stipulate step 3:

3. Complement the first 32 bits of the message and let
the CRC be 0 and then do the division.

Then I do not get even close to the samples in the draft.

If I stipulate step 3 as:

3. Complement the first 32 bits of the message and let this
be the initial value of the CRC and then do the division.

Then I do not get even close to the samples in the
draft.

Clearly the last 2 are equivalent.

In all 3 cases I _do_get_ the magic value at the end, 
and this is mathematically sound, since playing
with the CRC is like adding a certain polynomial,
C(x), and C(x)+C(x)=0, since the CRC is done the same
at the receiver, and the coefficients are in Z_2.

For any CRC, we have to have a solid mathematical model,
in order to avoid confision, etc.

We CAN provide a solid mathematical model for CRC32/4,
as is specified in the iSCSI draft, but the sample
CRC's will have to be changed.

My interpretation (word for word from the draft) is:
specifies CRC32/4, straightforward
premult. by x^32 and prefixing by 32 1s, and
straightforward division.

NO! Prefixing and adding ARE NOT equivalent in any sense!

I say prefixing, since it makes more sense to catch 0's
rather than not to. As well as it makes less sense to
mess with the message bits (as it would be for adding).

But the examples seem to be taken from a different
(Ethernet algo with CRC32/4 poly?) algorithm, or the
examples were mistyped.

If something else was intended, then so mentioned it
should've been.

-l

=====
--

__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com