Subject: RE: effect of initializing CRC reg to 1's depends on implementati on?

From: "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
Date: Fri, 14 Dec 2001 10:32:26 -0700

Paul,

I agree that we should use the mathematical description of the CRC as the
spec. Equivalent ways of obtaining the effect of inverting the first bits or
checking the result (magic number) are implementation details. I'm not
convinced that we need to show an implementation example in the annex. Given
the misleading information that Vince has found in some of the literature if
we show an implementation example, we need to point out that the technique
of initializing the register to 1's applies specifically to that
implementation and may not work for other implementations.

Regards,
Pat

-----Original Message-----
From: Paul Koning [mailto:[email-masked]]
Sent: Thursday, December 13, 2001 8:40 AM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: effect of initializing CRC reg to 1's depends on
implementation?

>>>>> "vince" == vince cavanna <[email-masked]> writes:

 vince> In working with Luben Tuikov to document the math behind the
 vince> CRC I discovered something that surprised me. I intend to
 vince> study this further but hope someone can save me work by
 vince> pointing out that I am wrong (or right) and offering some
 vince> proof.

 vince> Consider two ways to implement the iSCSI CRC with a serial
 vince> divider (see PDF file):

 vince> 1. divide the message directly using a serial circuit that,
 vince> when its stages are initialized to zeroes, simultaneously
 vince> multiplies by x^32 and divides by G(x).

 vince> 2. pre-multiply message by x^32 and then divide the results by
 vince> G(x) using a serial circuit that, when its stages are
 vince> initialized to zeroes performs a division by G(x).

 vince> The two circuits, of course, produce the same results when
 vince> they are initialized to 0's.

 vince> In the approach in (1) initializing the register to 1's
 vince> appears equivalent (produces the same quotient; same
 vince> remainder) to initializing the register to 0's and
 vince> complementing the most significant 32 bits of the message
 vince> prior to processing.

 vince> In the approach of (2) such an equivalence does not appear
 vince> true!

 vince> This means to me that it is meaningless to specify that the
 vince> CRC must be initialized to 1's unless we refer to a specific
 vince> implementation which we did not do in the iSCSI spec! What is
 vince> troublesome is that I have seen claims in the literature (and
 vince> in one textbook on data communications) that initializing the
 vince> CRc to 1's is equivalent to complementing the most significant
 vince> n bits of the dividend for both implementations. I have also
 vince> seen the same claim with no reference to an implementation
 vince> (e.g. iSCSI) which would imply that the implementation does
 vince> not matter.

I must be sounding like a broken record at this point, but I believe
the answer is to use the Ethernet spec as an example.

The Ethernet spec has the mathematical definition of the CRC in the
body of the spec.  In other words, it talks about complementing the
message, multiplying by x^32. dividing by G(x), and so forth.  That
definition is unambiguous.

In addition, the Ethernet spec gives an EXAMPLE implementation in
appendix C.  That is not normative; it merely shows one way to
translate the math into gates.  In that example implementation -- and
NOT in the mathematical definition in the normative part -- it is
meaningful to talk about initializing the shift register to all 1's.

I would recommend using the same descriptive approach in the iSCSI
spec.  It may be possible simply to copy the description as it appears
there (with suitable alteration to the placement of the LFSR taps, of
course, for the sample implementation); I see no copyright claims on
the document that prevent doing so.

    paul

---

From: Luben Tuikov <[email-masked]>
Date: Fri, 14 Dec 2001 11:26:36 -0800 (PST)

--- "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
wrote:
> spec.

I've been trying to convince ppl this since I started
to work on iSCSI.

Pure math is much clearer, and simple than an
implementation. And it woudn't be more than a few
lines to describe the algorithm. (A treatment
of why it works, would of course be longer than that.)

Please note that the draft makes no mention of
the Ethernet CRC algo, and I assume there is a reason for
it. Else why not say: ``Ethernet CRC algo, with the
generator poly be ...''.

> Equivalent ways of obtaining the effect of
> inverting the first bits or
> checking the result (magic number) are implementation
> details.

I guess that would be true, but one thing needs mentioning:

======================================================
The start point of all those algoritms and circuits is a
message premultiplied by x^n (n=degG(x)), e.g. AUGMENTED,
and PREFIXED. And then division is done on that, I.e.
x^nM(x) + Prefix.
======================================================

Setting an initial value of the CRC register will result in
a constant apperaing here and there.

Now you want to object to this, and rightly so.
Why? Well after analysis, the above said can be so much
transformed that it doesn't look like that statement
anymore. E.g. Prefixing can be done away with, by adding a
constant value to the n MSb of the message; as well as
augmentation, by changing the div algo to include mult on
the fly.

As an exampe of this ``compilation'' is the circuits that
Vince has provided.

But we need a mathematical description, and by analogy,
reading source code makes understanding a lot easier than
reading compiled binary code.

> I'm not
> convinced that we need to show an implementation example
> in the annex.

Yes we should stick with the way it currently is in the
draft: mathematical steps, but make them clearer.

> Given

It was I who first brought this up using pure analysis.
Maybe you should take a look at the iSCSI archives.

When I started work on iSCSI -- the CRC thead was quiet and
by word of mouth ppl were implementing Ethernet using the
CRC32/4 generator poly. But the description of the draft
had some inconsistencies and here we are.
 
> Pat

Regards,
Luben

=====
--

__________________________________________________
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

---

From: Paul Koning <[email-masked]>
Date: Fri, 14 Dec 2001 15:18:11 -0500 (EST)

I guess the problem with the spec is that it is a confusing mix of
pieces of the mathematical definition and pieces of description from a
specific (and unstated) implementation.

Ok, so let me propose specific replacement text.

This is for Appendix D, starting at the top of page 193 in the -09 rev
of the spec.

----------------
The generator polynomial for the CRC is x^32 + x^28 + x^27 + x^26 +
x^25 + x^23 + x^22 + x^20 + x^19 + x^18 +x^14 + x+13 + x+11 + x^10 +
x^9 + x^8 +x^6 + 1.

The CRC value for a PDU is defined mathematically as follows:

1. The first 32 bits of the PDU are complemented.

2. The N bits of the PDU are then considered to be coefficients of a
polynomial M(x) of degree N-1.  Bit 0 of byte 0, i.e., the low order
bit of the high order byte of the first word of the PDU, corresponds
to the X^(N-1) term of this polynomial, and the high order bit of the
last byte of the PDU corresponds to the x^0 term.  Note that any pad
bytes for the PDU are included.

3. M(x) is multiplied by x^32, and divided by G(x), producing a
remainder R(x) of degree < 32.

4. The coefficients of R(x) are considered to be a 32-bit sequence.

5. This bit sequence is complemented and the result is the CRC.

The CRC is trannsmitted with the high order bit (corresponding to the
x^31 term of R(x)) in the low order bit of the first byte transmitted,
and the low order bit (corresponding to the x^0 term of R(x)) in the
high order bit of the fourth byte transmitted.
----------------

This text is inspired by the text in the Ethernet spec, with some
wording changes needed for the iSCSI context.  I believe this is a
precise definition of what is needed.

For additional information, more text could be included.  For example:

----------------
The above algorithm is exactly that used in the Ethernet/802.3 LAN,
with the exception of the choice of generator polynomial.
----------------

And perhaps a note on implementation:

----------------
The above algorithm may be efficiently implemented in a variety of
ways, such as linear feedback shift registers, table lookup, etc.
----------------

Finally, we could capture the "magic constant" receive algorithm as
follows:

----------------
Implementation of the CRC32C checking for PDU reception can be done in
several ways.  

One approach is to calculate the CRC over the PDU not including the
CRC field, and compare that with the received CRC.  If the two values
are equal, the digest is considered valid.

Another approach is to perform the above algorithm over the entire
received PDU, including the CRC field.  With that approach, a valid
digest results in R(x) having the value x^28 + x^27 + x^26 + x^21 +
x^19 + x^18 +x^16 + x^12 + x^11 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + 1,
i.e., the value of the 32-bit sequence obtained in step 4 is
0x1c2d19ed. 
----------------

Following Pat Thaler's comments, I am not proposing any more text on
implementation approaches.  Both the table based approaches and the
LFSR approach can be covered by references to literature, though
admittedly some of the references may not be all that easy to
acquire. 

So my proposal is to replace the text on page 193 up to the
"Proprietary algorithms MAY also..." with the four pieces given
above.  If people don't like the later pieces, then I'll fall back to
proposing just the first chunk of text (the formal definition of the
CRC) as replacement for the current text.

	 paul

---

From: Luben Tuikov <[email-masked]>
Date: Fri, 14 Dec 2001 16:45:34 -0800 (PST)

Hello Paul,

I like the current description of CRC32C of iSCSI, except
for one small little thing: page 194 of v9, dash 2:

  - the CRC register is initialized with all 1s (equivalent
     to complementing the first 32 bits of the message)

This is actually equivalent to XORing the first
32 bits of the message with the magic constant as Vince
and I have shown.

If this is changed, then the message in its form:
  M'(x) = x^32 M(x) + x^(32+n) I(x)

yields to better optimizations as Vince and I have shown.
(see his circuits and worksheet4.pdf, which I posted
yesterday)

I.e. the message is augmented (mult by x^32, aka postfixed)
and prefixed by 32 1's (aka CRC=32 1's).

From this M'(x) one can derive the Simultaneous Multiply
and Divide alogirthm (SMD), get the constants to which the
CRC has to be set or the first 32 MSb of the PDU, etc.

In an SMD, one would have to set the CRC to the magic
constant and then proceed as the algorithm indicates,
(this is identical to what you'd find in Ethernet,
and is derived from M'(x), as Williams [1] shows)

In a simple divide, one would have to Magic XOR 32 MSb of
PDU, CRC = 0 and then proceed.

Williams [1], shows how this is possible, in his paper, but
he doesn't use math to show how/why as the title of the
paper indicates (``Painless guide...''), and most
derivations are omitted.

Regarding examples: I like examples, we should have the
examples as they are in the draft, but fix the CRCs for
ones, decs and incs.

``A picture's worth a thousand words.''

-l

P.S. I've just got the math on the SMD, and will be
communicating it with Vince. A worksheet5.pdf will follow
with the math.

[1] Williams, Ross, Painless guide to CRC error detection
algorithms. Rocksoft.

=====
--

---

From: Paul Koning <[email-masked]>
Date: Sat, 15 Dec 2001 15:48:35 -0500

> 32 bits of the message with the magic constant as Vince

Are you saying that you believe the intent of the current spec is NOT
the same as the Ethernet CRC, i.e., complement the first 32 bits,
multiply by x^32, then divide by G(x)?

If that is your interpretation, then we absolutely MUST fix the spec,
I'm quite sure that the intent of the spec is as I wrote it, i.e.,
Ethernet except for the generator.  

> and prefixed by 32 1's (aka CRC=32 1's).

But that is NOT what the spec currently says.  What you describe may
be a fine CRC but it is not the one that's in the spec.  Initializing
the CRC register to all 1 is not the same as prefixing 32 1 bits onto
the message.

What does "better optimizations" mean?

> (this is identical to what you'd find in Ethernet, ...

No it isn't.  The Ethernet spec appendix C, and, more importantly, the
formal definition of the CRC in the body of the spec, makes it quite
clear that it isn't.  I don't understand how you arrive at any other
conclusion.

     paul

---

From: Luben Tuikov <[email-masked]>
Date: Sun, 16 Dec 2001 02:43:43 -0800 (PST)

--- Paul Koning <[email-masked]> wrote:
> Excerpt of message (sent 14 December 2001) by Luben

In our profession we cannot talk about beliefs and
intentions, more so for documents, rfc, etc.

If you show the current description of the CRC of the draft
to a mathematician, they will object to the same thing I've
objected.

The reason is that they don't have the preconception about
what circuit is being used, and any such higher level
notions.

All they would have and all I had was long division in Z_2.
(Actually Z_2[x] since we deal with polynomials.) 

Then I started from first principles of CRC, polydivision,
etc, etc. -- similarly to how Williams proceeds in his
paper, but my treatment was purely algebraic.

The same applies to anyone looking at a description of an
algorithm. (An ``algorithm'' has a precise definition in
Computer Science.)

In its current form the description of the algorithm to
compute the CRC in the iSCSI draft is not consistent, just
because there is an unspoken assumption that a SMD circuit
will be used. We cannot afford to do this in a definition
document, unless we refer explicitly to it. We cannot even
assume that a circuit will be used...

Please also note that the Ethernet spec CRC algorithm, is
an optimized version of a basic
prefix-postfix-initialize-the-
CRC-register-to-some-constant algoritm. BUT as SMD it
operates on NON-AUGMENTED messages. FOR THAT REASON you
cannot say that we have to multiply M(x) by x^32!!!

I.e. SMD algoritms like the one in the Ethernet spec,
operate on non-augmented messages, while simple Division
(D) algorithms operate on augmented messages.

Any D can be optimized to SMD, but the constant has to be
changed. Also, prefixing a message is equivalent to loading
the CRC register with that prefix (WLG), but this is not so
for SMD. (elaborated below)

Further more for any SMD there is an equivalent D,
including for the Ethernet spec SMD; and for any D there is
an equivalent SMD.

> Ethernet except for the generator.  

Probably it is. But lets not hasten here.
We can further generalize the explanation of the algorithm.
 
> the CRC register to all 1 is not the same as prefixing 32

It is, in a simple division, e.g. in D. This is clearly and
simply explained in the Williams paper. It is an equivalent
to a long division.

Now, in D, if I initialize the CRC to all 1's and then do
division of M(x) by G(x), so that I catch 0's at the
beginning of the message,

(which is equivalent to prefixing the message by 1's of the
number of the width of the CRC, and then do just simple
division,(CRC=0), since after so many clicks the CRC will
be loaded with the prefixing bits, and also 0/G(x) = 0)

then I can find a constant which I can XOR to the first 32
bits of the message and then perform the division, still in
D, with the same effect. In this particular case that
constant is the magic constant. (We are one step closer to
SMD...)

(Now we jump to SMD, by means of worksheet4.pdf, Prefixing
part.)

Now, in the Ethernet CRC spec, that constant is 32 1's, and
XORing 32 1's with the 32 MSb of the message is equivalent
to complementing them.

BUT the Ethernet spec uses SMD, not D, so I claim that
there is an equivalent D, which for a suitable initial CRC
(also equivalent to prefixing the message with it) value
will yield IDENTICAL results as Ethernet SMD.

Now using a bit of algebra similar to worksheet4.pdf which
I posted a couple of days ago and numerical methods
(solving a linear system of 33 unknowns) I have found such
a constant:
0x2a26f826 which in simple division, D, will yield results
identical to SMD of Ethernet.

So, here is an abstractization of the Ethernet CRC SMD,
explained in a simple, simple, simple division only way:

TX:
1. Mutliply the message, M(x), by x^32.
2. Prefix the result of 1. with 0x2a26f826.
3. Find the remainder of the result of 2.
4. Complement that remainder and add it to the 
   result of 1.
5. Send the result of 4. to the recipient.

RX: (same as steps 1-3 in TX)
1. Mutliply the message by x^32.
2. Prefix the result of 1. with 0x2a26f826.
3. Find the remainder of the result of 2.

The result of 3 should be 0x1c2d19ed (the magic constant).

Of course I've ommitted the mirroring of bytes for clarity
and brevity. It can be mentioned on the side, e.g. How to
build the message: mirror the bytes == to swapping the bits
inside the bytes, ....

Also note that step 4 in TX, adding means exactly that,
since we already mult. by x^32, so the remainder will
nicely fit in the last 32 0 bits.

Also note that step 2, can be made clearer:
let C(x), be the polynomial representation of 0x2a26f826.
Let n = deg G(x), k-1 = deg M(x) (there are k bits), then
step 2 is:

2. Add x^n x^k C(x) to the message M(x).

Or we can swap step 1 and 2:

1. Add x^k C(x) to M(x).
2. Multiply the result of 1. by x^n.

I hope this makes things a bit clearer.

So from this D specification above, I can derive SMD
exaclty as it is in the Ethernet spec. I'll include this
derivation in the paper -- it will be pure math, but in
english it goes like this: First we notice that after 32
clicks the CRC register will contain only 32 1's XOR-ed
with the message, then we see that we can just load the crc
with ones and then kick one byte off the left xor it with
the next message bit...

The above equivalence I've tested empirically.

> What does "better optimizations" mean?

See above.
 
> clear that it isn't.  I don't understand how you arrive

I didn't mean identical as in the constant. I meant
identical in a way of equivalence of algorithms, that one
can be derived from the other, etc. See above. Or simpler
answer: Math.

-l

=====
--

---

From: Mark Bakke <[email-masked]>
Date: Mon, 17 Dec 2001 08:55:19 -0600

This is becoming somewhat disturbing, given the comment about
the Ethernet CRC.  The intent of the document is absolutely,
positively to keep the CRC identical to Ethernet, with the
exception of the generator, just as Paul had said.  I'm not
enough of a mathematician to complain about the definition; if
there's a good way to fix it so it says what we intend, we
should do so.  We got around this problem somewhat by simply
providing a set of examples.  If someone has an implementation
that does not match the examples, they simply try a few
variations until they get it right.  This has worked very well
for everyone I have talked to who is implementing the CRC.

Here is some text that I had suggested adding instead of (or 
in addition to) the mathematical description a while ago:

The generator polynomial selected is evaluated in [Castagnioli93].
When using the CRC the CRC register must be initialized to all 1s
(0xFFFFFFFF).  Input bytes are processed with bit 7 being the most
significant bit.  Before transmission, the CRC bits must be
reflected (bit 31 swapped with bit 0, bit 30 swapped with bit 1,
etc.), and complemented.  The CRC bytes must be transmitted in
network order.  Padding bytes, when present, in a segment covered
by a CRC, should be set to 0 and are included in the CRC.

Running the CRC-32C generator on an input stream that includes a
valid CRC-32C will result in the constant remainder 0x1c2d19ed,
(without being reversed and complemented).

The above, plus the examples, have seem to work out just fine
for the implementors.  Getting the math right would be nice, but
most of us implementors don't look at it anyway, and prefer the
more practical description.  If we are going to include the math,
it has to match the examples.

Anyway, my guess is that is what you are discussing; it was just
disturbing to think that anything but the Ethernet + new poly
was being considered, since that has been agreed on for a long
time, and is being widely implemented.

--
Mark

-- 
Mark A. Bakke
Cisco Systems
[email-masked]
763.398.1054

---

From: Paul Koning <[email-masked]>
Date: Mon, 17 Dec 2001 10:36:35 -0500 (EST)

>>>>> "Luben" == Luben Tuikov <[email-masked]> writes:

 Luben> --- Paul Koning <[email-masked]> wrote:
 >> Excerpt of message (sent 14 December 2001) by Luben > This is
 >> actually equivalent to XORing the first > 32 bits of the message
 >> with the magic constant as Vince > and I have shown.
 >> 
 >> Are you saying that you believe the intent of the current spec is
 >> NOT the same as the Ethernet CRC, i.e., complement the first 32
 >> bits, multiply by x^32, then divide by G(x)?

 Luben> In our profession we cannot talk about beliefs and intentions,
 Luben> more so for documents, rfc, etc.

 Luben> If you show the current description of the CRC of the draft to
 Luben> a mathematician, they will object to the same thing I've
 Luben> objected.

 Luben> ...
 Luben> In its current form the description of the algorithm to
 Luben> compute the CRC in the iSCSI draft is not consistent, just
 Luben> because there is an unspoken assumption that a SMD circuit
 Luben> will be used. We cannot afford to do this in a definition
 Luben> document, unless we refer explicitly to it. We cannot even
 Luben> assume that a circuit will be used...

I agree that the current description is not consistent and is
confusing.  That's why I proposed replacement text.  I'd be interested
in comments on that text.

 Luben> Please also note that the Ethernet spec CRC algorithm, is an
 Luben> optimized version of a basic prefix-postfix-initialize-the-
 Luben> CRC-register-to-some-constant algoritm.

I'm not sure what spec you're talking about.

The algorithm in the Ethernet spec (section 6.2.4) which was copied
into the 802.3 spec (section 3.2.8) pretty much verbatim except for a
typo, is not a prefix-postfix-whatever algorithm at all.  Instead, it
is a mathematical definition of the CRC value.  The phrase "initialize
the CRC register" does not occur at all in any form.

 Luben> ...
 Luben> TX: 1. Mutliply the message, M(x), by x^32.  2. Prefix the
 Luben> result of 1. with 0x2a26f826.  3. Find the remainder of the
 Luben> result of 2.  4. Complement that remainder and add it to the
 Luben> result of 1.  5. Send the result of 4. to the recipient.

 Luben> RX: (same as steps 1-3 in TX) 1. Mutliply the message by x^32.
 Luben> 2. Prefix the result of 1. with 0x2a26f826.  3. Find the
 Luben> remainder of the result of 2.

If I understand right, this is a mathematically equivalent way of
describing an Ethernet-style CRC.

Fine, no problem.  But what's the point?  All we need is a single
formal definition.  And it would make the most sense for that
definition to look like the ones found in other standards, so it will
be clear to the reader that the CRC in iSCSI is the same as the one
used in many other places except for the G(x).  The text I proposed
does that, since it uses the classic text except for G(x).  The
description you gave may be mathematically equivalent, but that is not
at all obvious unless you're fluent in abstract math.

In any case, no mathematical description by itself translates easily
to an implementation (again, unless you're fluent in abstract math).
Most specs disregard that concern and leave it up to the implementer
to search the literature.  My current proposal is to do likewise for
iSCSI.  The only exception I've seen is the Ethernet spec, which gives
a single example implementation in its appendix.  

     paul

---

From: Luben Tuikov <[email-masked]>
Date: Mon, 17 Dec 2001 11:14:15 -0800 (PST)

--- Mark Bakke <[email-masked]> wrote:
> the Ethernet CRC.

Which comment did you have in mind?

>  The intent of the document is
> absolutely,
> exception of the generator, just as Paul had said.

Then we should JUST say THAT in the iSCSI spec.
I think that it is enough.

> If someone has an
> implementation
> variations until they get it right.

Mark, iSCSI draft/rfc is supposed to be THE AUTHORITY
reference for iSCSI implementation.

You cannot say ``just try a few variations until you get it
right''!

>  This has worked very
> well

The reason is that they know and/or have a preconception
about what is being talked about. I.e. the current
description is very IMPLICIT. As part of a definition
document it has to be EXPLICIT.

You need an outsider, an impartial party to scrutinize the
draft. All parts of it.
 
> in addition to) the mathematical description a while ago:

I liked the one you had above better.
 
> it has to match the examples.

Most certainly agree! Including math is not necessary. We
can prepare a document (what I and Vince are doing) and
make a reference to it in the draft for all the math,
optimization, derivation, equivalence and implementaion
details.
 
> time, and is being widely implemented.

... and not being mentioned anywhere in the draft!

-l

=====
--

---

From: Luben Tuikov <[email-masked]>
Date: Mon, 17 Dec 2001 11:44:29 -0800 (PST)

> in comments on that text.

I gave you a comment in my last letter:

  Please also note that the Ethernet spec CRC algorithm,
  is an optimized version of a basic
  prefix-postfix-initialize-the-
  CRC-register-to-some-constant algoritm. BUT as SMD it
  operates on NON-AUGMENTED messages. FOR THAT REASON
  you cannot say that we have to multiply M(x) by x^32!!!

You see, you cannot say that the message has to be
multiplied by x^32, if you are describing the Ethernet
CRC algo.

> I'm not sure what spec you're talking about.

The one you always mention, the one you quote in you
messages. The one iSCSI is trying to present.

> typo, is not a prefix-postfix-whatever algorithm at all. 

Yes, it is. I'll send you the math when I finish it (later
this week).

I'll also send you 2 algorithms, one simplest division, and
another as per Ethernet, which produce identical results.
(I can send it now, but no time.)

> Instead, it

So it doesn't in the definition I gave you.
If it is a formal, mathematical definition, then you should
see the same initial constant as I found: 0x2a26f826.

If it mentiones 0xFFFFFFFF, then it means that SMD
(Simultaneous Divide and Multiply) algo is described, which
is hardly a formal mathematical definition.
 
> describing an Ethernet-style CRC.

Yep. Mathematically, and when implemented, by hand, by a
program, by a handheld calculator, by a mathematics
analysis program, it will yield identical results as in
``Ethernet-style CRC''.
 
> formal definition.

The point? You and Pat wanted a mathematical definition, so
here it is!

This is a ``single formal definition''.

>  And it would make the most sense for
> that
> used in many other places except for the G(x).

Then lets forget about trying to REPHRASE Ethernet and just
mention that: that it is equivalent to Ethernet, but just
that it uses a different polynomial.

> The

True.
 
> to an implementation (again, unless you're fluent in

True.

> a single example implementation in its appendix.  

Example implementation is good, as are examples.
I'd vote for both to be included in iSCSI.

-l

=====
--

---

From: Paul Koning <[email-masked]>
Date: Mon, 17 Dec 2001 15:08:14 -0500 (EST)

Luben> --- Paul Koning <[email-masked]> wrote:
 >> confusing.  That's why I proposed replacement text.  I'd be
 >> interested in comments on that text.

 Luben> I gave you a comment in my last letter:

 Luben> Please also note that the Ethernet spec CRC algorithm, is an
 Luben> optimized version of a basic prefix-postfix-initialize-the-
 Luben> CRC-register-to-some-constant algoritm. BUT as SMD it operates
 Luben> on NON-AUGMENTED messages. FOR THAT REASON you cannot say that
 Luben> we have to multiply M(x) by x^32!!!

 Luben> You see, you cannot say that the message has to be multiplied
 Luben> by x^32, if you are describing the Ethernet CRC algo.

 >> Please also note that the Ethernet spec CRC
 >> algorithm, is an
 >> optimized version of a basic
 >> CRC-register-to-some-constant algoritm.
 
 >  I'm not sure what spec you're talking about.

 Luben> The one you always mention, the one you quote in you
 Luben> messages. The one iSCSI is trying to present.

I don't think so.

The one I'm always quoting from says the following (section 6.2.4,
page 30):

  Mathematically, the CRC value corresponding to a given frame is
  defined by the following procedure:

  1. The first 32 bits of the frame are complemented.

  2. The n bits of the frame are then considered to be the
  coefficients of a polynomial M(x) of degree n-1.  (The first bit of
  the destination address field corresponds to the x^(n-1) term and
  the last bit of the data field corresponds to the x^0 term.)

  3. M(x) is multiplied by x^32 and divided by G(x), producing a
  remainder R(x) of degree <= 31.

  (rest omitted)

So as you can see, the statement about multiplying the message by x^32
is taken directly from the Ethernet spec.  That is why I put it into
my proposed text.

Your statement that "you cannot say that the message has to be
multiplied by x^32, if you are describing the Ethernet CRC algo" is
clearly not correct.

The text in my proposed replacement text is the Ethernet text, except
for some terminology and context changes (like "PDU" instead of
"frame") and a slightly different but equivalent way of stating bit
order).

	paul