Subject: Re: iSCSI: 12-97 Bit Rule

From: "Julian Satran" <[email-masked]>
Date: Thu, 13 Jun 2002 17:20:28 +0300

I took out completely the bit rule.
I reformulated the CRC text as:

The CRC MUST be calculated by a method that produces the same results as 
the following process:

 - The PDU bits are considered as the coefficients of a polyno-mial M(x) of 
degree n-1; bit 7 of the lowest numbered byte is considered the most 
significant bit (x^n-1), followed by bit 6 of the lowest numbered byte and 
through bit 0 of the high-est numbered byte (x^0).

- The most significant 32 bits are complemented.

- The polynomial is multiplied by x^32 then divided by G(x). The generator 
polynomial produces a remainder R(x) of degree <= 31.

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

- The bit sequence is complemented and the result is the CRC.

- the CRC bits are mapped into the digest word - the x^31 coef-ficient in 
bit 7 of the lowest numbered byte of the digest continuing to through the 
byte up to the x^24 coefficient in bit 0 of the lowest numbered byte, 
continuing with the x^23 coefficient in bit 7 of next byte through x^0 in 
bit 0 of the highest numbered byte.

- Computing the CRC over any segment (data or header) extended to include 
the CRC built using the generator 0x11edc6f41 will get always the value 
0x1c2d19ed as its final CRC. This value is given here in its polynomial 
form - i.e. not mapped as the digest word 

I hope you will find it less confusing 

Julo

[email-masked]
06/12/2002 08:41 PM
Please respond to pat_thaler

        To:     Julian Satran/Haifa/IBM@IBMIL
        cc:     [email-masked], [email-masked]
        Subject:        iSCSI: 12-97 Bit Rule

Julian,
 
The bit rule added to 12-97 (1.3.4 page 31) is inconsistant with the 
clauses above it: Word Rule,  Half-Word Rule and Byte Rule. 
 
It says "when the sequence of bits has a positional significance (e.g., a 
modulo 2 polynomial) then bit 7 of the lowest numbered byte is considered 
the most significant bit (2**n), followed by ...."
 
When bits represent a number, they have positional significance so that 
sentence applies. However, the other rules apply the opposite significance 
to the bits within each byte.
 
Also, note that bits represent polynomials at other times than the CRC 
such as for the purpose of authentication or encryption algorithms and 
those algorithms do not necessarily use the bit significance of the Bit 
Rule. The bit rule only applies to bit significance for CRC calculation. 
 
Bit Rule should be CRC Bit Rule and the associated text should make it 
clear that it only applies to the CRC calculation. Since it only applies 
there, it would be kinder to the reader to put the text in 11.1 rather 
than making the reader of 11.1 look nearly 200 pages back in the spec.
 
Regards,
Pat

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 14:14:50 -0400

Julian Satran wrote:
> The CRC MUST be calculated by a method that produces the same results as the following process:
> 
>  - The PDU bits are considered as the coefficients of a polyno-mial M(x) of degree n-1; bit 7 of
> the lowest numbered byte is considered the most significant bit (x^n-1), followed by bit 6 of the
> lowest numbered byte and through bit 0 of the high-est numbered byte (x^0).

This description, taken by itself, as you quote it here,
mentions bit 7 of a byte. Normally, bit 7 of a byte is
the Most Significant bit (MSb).

But somewhere you MUST mention that bit 7 is, contrary to all
intuition, the LSb, NOT, as many of us would assume, the MSb.
(I.e. the _bit_ ordering as per the PDU template doesn't
imply bit significance, or does it?)

I.e. you need to mention that the bytes are mirrored.

Here it is, again:

1) The bytes of the message form a bit stream, ordered
   Most Significant Byte (MSB), Most Significant bit (MSb)
   in memory, i.e. Big endian on bytes, Big endian on bits.
   Call this bit stream P.

2) The bytes of P are mirrored, thus forming byte 0, LSb
   first to MSb, then byte 1, LSb first to MSb, etc,
   (Big endian on Bytes, Little endian on bits), this forms the
   bit sequence A = {a_0, a_1, ..., a_(n-1)}.

3) The first 32 bits of A are complemented (a_0 to a_31).

4) The bits of A are considered coefficients of M(x),
   where M(x) = a_0 x^(n-1) + ... + a_(n-1) x^0.

5) The polynomial M(x) is multiplied by x^32, then divided by G(x),
   where G(x) is the polynomial representation of 0x11edc6f41.
   This produces a remainder R(x) of degree <= 31.

6) The coefficients of R(x) are considered a 32 bit sequence,
   R(x) = r_31 x^31 + ... + r_0 x^0.

7) R(x) is complemented and mirrored, the result is CRC(x).

8) The message sent is P and appended at the end are the
   bit coefficients of CRC(x), with x^31 bit coefficient
   first, then x^30, etc.

9) A receiver of a "good" message sent as per step (8),
   will get the value 0x1c2d19ed as R(x) (steps (1) to (6)).

Note that CRC(x) is a polynomial and independent of
the machine's representation.

For clarity, I've omitted the fact that x^0 = 1.

So, steps 1 to 6 form ``R(x) = compute_crc(P)'',
and steps 7 to 8 form ``Send_This = inject_crc(P, R(x))''.

I.e. ``Magic_Value = compute_crc(inject_crc(P, compute_crc(P)))''

Thus, one sends ``inject_crc(P, compute_crc(P))'',
and the receiver does ``Magic_Value =?= compute_crc(message_received)'',
which is step 9.

-- 
Luben

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 16:00:54 -0400

> 7) R(x) is complemented and mirrored, the result is CRC(x).
                             ^
Missed here ``byte'', i.e. ``complemented and byte mirrored''.

-- 
Luben

---

From: Bill Studenmund <[email-masked]>
Date: Thu, 13 Jun 2002 14:27:14 -0700 (PDT)

> imply bit significance, or does it?)

Uhm, that's standard practice for an IETF draft. While it may be
counter-intuitive (I'd agree it is), it's standard practice with the ietf,
and is used that way through the draft.

Take care,

Bill

---

From: Bill Studenmund <[email-masked]>
Date: Thu, 13 Jun 2002 14:35:58 -0700 (PDT)

On Thu, 13 Jun 2002, Julian Satran wrote:

One minor question.

> - The bit sequence is complemented and the result is the CRC.

Call the above step 5.

> form - i.e. not mapped as the digest word

About the use of "final CRC" with respect to 0x1c2d19ed. Step 5 says the
"CRC" is after the complementation, but my experiments indicate that
0x1c2d19ed is the uncomplimented result, and that the complimented result
would be 0xe3d2e612. Thus 0xe3d2e612 would be the "CRC."

> I hope you will find it less confusing

I'm not sure what to do. The thoughts which come to my mind take up space.
The simplest would be to mention what coefficents one uses in well-known
crc packages. A more complex one would be to include source code, as the
sctp crc draft did.

Take care,

Bill

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 17:40:48 -0400

> and is used that way through the draft.

Other than _repeating_ what Julian has said, do you have a point?

Anyway, if you had paid attention you'd have noticed
that the algorithm I sent DOESN'T DEPEND on the
bit numbering (7:0 or 0:7) of the draft. _This_
was the more important subject (and my point)...

-- 
Luben

---

From: Bill Studenmund <[email-masked]>
Date: Thu, 13 Jun 2002 14:46:32 -0700 (PDT)

> Other than _repeating_ what Julian has said, do you have a point?

Yes, actually, I do. 1) An independent reader of the document agreed with
the author as to the meaning of the bit ordering. This fact is important
as authors (as I have found with most of the technical documents I have
written) have an intimate association with the document, and as such may
not see things as an independent reader would. 2) I wasn't repeating
Julian, I was expressing my opinion. The fact we agree indicates that
we agree. :-)

> was the more important subject (and my point)...

Then why distract everyone by talking about bit sequence?

Take care,

Bill

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 18:30:39 -0400

> Julian, I was expressing my opinion. The fact we agree indicates that

So, this is all contrary to the fact that you mentioned
that it is indeed confusing in a previous letter on this thread.

As I said: we'll just wait to see for the comments
from the industruy and the implementers. Especially
the Linux community, which has defied all
``consensus'', ``ideology'', and what-not,
and has chosen for the ``makes sense'' attitude.
(Badly quoted from Linus.)
 
> Then why distract everyone by talking about bit sequence?

So that it doesn't matter if YOU count bits 0 to 7 or 7 to 0
in a byte. So that anyone can implement it anyway.

-- 
Luben

---

From: Bill Studenmund <[email-masked]>
Date: Thu, 13 Jun 2002 16:04:06 -0700 (PDT)

> that it is indeed confusing in a previous letter on this thread.

No, it's not contrary to that statement.

The IETF does something, as part of its standards, that I find counter-
intuitive, and at first glance is confusing. It numbers bits in bytes in a
manner I would not choose.

However, the IETF uses this bit numbering scheme in ALL of its documents.
It is consistent in its bit numbering. Thus if I read an IETF document, I
prepare my mind for IETF bit numbering.

Note that the IETF is not the only group to use this bit numbering. As I
understand it the Mainframe folks use this bit numbering. Also, the
documentation I have on PowerPC chips all uses this bit numbering, so it's
not something the IETF made up.

> (Badly quoted from Linus.)

Well, two thoughts come to mind:

1) For me, no explanation of how to perform this CRC calculation will make
sense if it dives into the space of abstract bit streams and such. My mind
works much better with code snippets.

2) I expect the Linux community will start by looking at the
implementations out there. The UNH implementation has CRC32C code in it.
That code, AFAICT, is correct.

> in a byte. So that anyone can implement it anyway.

I'm sorry, that came out wrong. If your main point was that your proposed
text is independent of bit numbering, then the way you were discussing
Julian's use of the bit numbering which is consistent with the rest of the
document didn't help. At least not for me.

Take care,

Bill

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 19:23:35 -0400

> prepare my mind for IETF bit numbering.

Wow!
 
> not something the IETF made up.

Wow -- so you've just discovered that it is just a convention --
good for you.
 
> works much better with code snippets.

Aaaah, here is the key!

And my mind works better when I see more abstract ideas,
just because the implementation/bit order/byte order doesn't matter.

> That code, AFAICT, is correct.

You forget that there are incrediby smart ppl there, that will
most likely NOT look, since they've done it before, long ago,
in a galaxy far, far away... but I digress.
 
> document didn't help. At least not for me.

Well, what can I say? (red star for Bill, black dot for Luben)

-- 
Luben

---

From: Bill Studenmund <[email-masked]>
Date: Thu, 13 Jun 2002 16:34:26 -0700 (PDT)

Luben, what in the world are you hoping to achieve by this dialog? I fail
to see how the note you just sent (partially quoted below), complete with
hostile sarcasm, will achieve any changing to the CRC text.

Are you wanting to change the spec, or are you wanting to be sarcastic?

Take care,

Bill

> Wow -- so you've just discovered that it is just a convention --

[snip]

---

From: Luben Tuikov <[email-masked]>
Date: Thu, 13 Jun 2002 19:52:58 -0400

> hostile sarcasm, will achieve any changing to the CRC text.

1. Trying to extract more constructive emails from ppl,
   especially when they refer to emails sent by me.

There is no point in you sending your praise of organization X
and person Y to me.

Just send me something of the sort: ``Luben, a+b = c+1, contrary
to what you claim.'' and I'll be so happy.

2. I'm not trying to change the CRC text. Just trying to make
   it clearer.

If you have a problem with abstract ideas, just say so,
and that will be the end of it, rather than going around
for a few emails.

As I mentioned, I'm reading other mailing lists and ppl
the DO NOT use ``I agree with X'' so as to preserve
their own identity! They agree with rule, idea, notion, equation,
postulate, etc. Preserve your identity!

I've never seen ``I agree with X'' used so much (at all) elsewhere
(Mailing lists).

Let me hear YOUR opinion and YOUR ideas, but posting just
to say that you praise organization X and person Y,
is hardly of any help and is not constructive.

-- 
Luben