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

From: "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
Date: Mon, 17 Dec 2001 18:42:58 -0700

Luben,

The Ethernet spec does not use SMD, D or any other implementation. Here is
the text from IEEE 802.3 on CRC computation:

"A cyclic redundancy check (CRC)is used by the transmit and receive
algorithms to generate a CRC value for the FCS field. The frame check
sequence (FCS)field contains a 4-octet (32-bit)cyclic redundancy check
(CRC)value. This value is computed as a function of the contents of the
source address, destination address, length, LLC data and pad (that is, all
fields except the preamble, SFD, FCS, and extension). The encoding is de?ned
by the following generating polynomial.

G(x)=x^32 +x^26 +x^23 +x^22 +x^16 +x^12 +x^11 +x^10 +x^8 +x^7 +x^5 +x^4 +x^2
+x +1

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

a)The first 32 bits of the frame are complemented.

b)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.)

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

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

e)The bit sequence is complemented and the result is the CRC.

The 32 bits of the CRC value are placed in the frame check sequence field so
that the x 31 term is the left-most bit of the first octet,and the x^0 term
is the right most bit of the last octet. (The bits of the CRC are thus
transmitted in the order x^31 ,x^30 ,...,x^1 ,x^0 .) See reference [B37 ]."

Note that Ethernet MAC describes bit serial transmission of the packet so
the final paragraph is a sensible way for Ethernet to describe the bit
ordering of the CRC result in the transmitted packet. For iSCSI, one would
describe the placement of the bits into the message format instead of
transmission order.

Pat

-----Original Message-----
From: Luben Tuikov [mailto:[email-masked]]
Sent: Sunday, December 16, 2001 2:44 AM
To: Paul Koning; VICENTE V CAVANNA
Cc: [email-masked]
Subject: RE: effect of initializing CRC reg to 1's depends on
implementati on? iSCSI

--- 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)?

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.

> 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.  

Probably it is. But lets not hasten here.
We can further generalize the explanation of the algorithm.
 
> > 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).
> 
> 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.

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.
 
> > 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, ...
> 
> 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.

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

=====
--

__________________________________________________
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: Luben Tuikov <[email-masked]>
Date: Mon, 17 Dec 2001 20:03:58 -0800 (PST)

Pat,

First I refer you to this message by Vince.
http://www.pdl.cmu.edu/mailinglists/ips/mail/msg08109.html
Read it again, please.

Then, let us think a bit.

In Ethernet realm, we get bits off the wire, one at a time.

A good CRC algorithm will have to be as strong as being
able to produce the CRC at any time. That is, it has to
have the correct CRC _after_ _each_ _bit_ has arrived.

I.e. in any moment in time, if I were to say STOP, I would
have to be able to ``produce'' the right CRC.

In other words, the algorithm needs NOT know in advance
how many bits there are of the message.

This eliminates the need to store the whole message and
then ``multiply it by x^32''.

I.e. I need only 32 + 1 bits of storage to compute the CRC
of any length message, and I can do so as the bits are
coming in from/to the wire, no need to store any bits. 32
for the CRC and 1 for the newly arrived bit. I don't need
to know the previous or next bits.

AND I will give you a CRC which is the same as if you HAD
multiplied the message by x^32, and done division of
the message, putting a suitable constant in the CRC
register (equivalent to prepending the message by it and
CRC=0) in D.

You see, this is the whole point of SMD (Simultaneous
Multiply and Divide) algorithm. It needs not multiply by
x^32, or prepend the message.

This multiplication of x^32 is needed only when we are in D
(simple Division) algorithm. And this is where it is coming
from.

Lets see a simple example in the decimal system:
let G(x) = 4 and M(x) = 7 (WLG).

then R(x) = 7 modulo 4 = 3

But this is wrong, we should have computed the remainder
of 70 modulo 4 which is 2.

and then we'd send 72, which has remainder 0 modulo 4.

And this is the SMD in Ethernet (WLG), if you feed it 7 it
will tell you 2 (not 3), so that you can append 2 at the
end to get 72 which has 0 remainder, etc.

Once we have a 0 remainder I can add any value from 1 to
3 to get that value back when the thing is received and
the remainder is computed e.g. 7 append (2+1) = 73.
73 modulo 4 = 1, etc. as per the spec. and this is where
the magical constant comes from...

And then the next digit comes along, say 5, now we have 75,
but the algorithm gives 2 (rather than 75 modulo 4 = 3).
And 2 is correct since 752 modulo 4 = 0...

So you see, before quoting the document, please
try to actually implement it, at least. And then
see how that would fit into Ethernet.

You can even implement it by hand, as arithmetic
in Z_2 is quite easy (XOR). And the make things
interesting make the message be one bit longer than
G(x), i.e. 34 bits.

Then you'll see how cumbersome is the multiplication
by x^32. And that a better way has to exist.

In fact SMD is what is actually implemented in Ethernet,
and in a real circuit I bet you'd never see actual
multiplication by x^32.

-l

=====
--