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

From: "CAVANNA,VICENTE V (A-Roseville,ex1)" <[email-masked]>
Date: Mon, 17 Dec 2001 15:17:57 -0700

Luben is right, Paul's description is still ambiguous, although I do not
quite agree that the issue is the multiplication by x^32. I will attempt to
clarify.

When Paul, in his 12/14/01 memo "re:effect of initializing CRC reg to 1's
depends on implementation? iSCSI", says to multiply the message by x^32 he
means that is what the implied circuit does. He does not mean to multiply
the message by x^32 and _then_ to perform the CRC computation with a circuit
that multiplies by x^32 and divides by the CRC polynomial. Note also that
Paul said to complement the first 32 bits of the PDU and he did not say that
this is equivalent to initializing the CRC to ones like the iSCSI spec
currently says.

Anyone who attempts to implement Paul's process using a multiply-divide
circuit  will obtain the results in the examples in hte iSCSI spec. If that
person then, instead of complementing the first 32 bits of the PDU,
initializes the circuit to 1s, he will also obtain the results in the iSCSI
spec.

On the other hand, if that person implements paul's process using a
divide-only circuit as Luben I and others have tried to do, the circuit will
not yield the results in the examples and furthermore for that circuit
initializing the circuit to ones is not the same as complementing the first
32 bits of the PDU.

So it is important that we either specify the circuit or we specify the
process more rigorously. Again, specifying the circuit means specifying its
response to an input _and_ its response to an initial state. This can be
accomplished by specifying the serial implementation that I have posted or
by specifying the complete response that I have also posted.

I repeat below two ways to specify the implementation unambiguously:

One way to specify the circuit is to show the reference implementation (e.g.
the serial implementation of the multiply-divide circuit that I posted) and
to say that any circuit that performs the same function, ie. has the exact
same response to initial state and to the input is also acceptable.

Another way is to describe the response of the implied circuit (the
multiply-divide implementation) after the application of n input bits is:

1. when I(x) is zero, multiplies the input, M(x), by x^32 and divides by
G(x).
2. when M(x) is zero, multiplies the initial state, I(x), by x^n and divides
by G(x).

where I(x) represents the initial state of the CRC register and M(x)
represents the input.

I also claim that the description in the ethernet spec is also ambiguous but
got away with it because of the implementation that they referenced (a
multiply-divide implementation) and which removed the ambiguity - whether
folk realized it or not. The parallel implementations that were derived from
_that_ serial implementation had exactly the same response to an input and
to an initial state.

Vince

|-----Original Message-----
|From: Luben Tuikov [mailto:[email-masked]]
|Sent: Monday, December 17, 2001 12:07 PM
|To: CAVANNA,VICENTE V (A-Roseville,ex1); 'Mark Bakke'
|Cc: Paul Koning; CAVANNA,VICENTE V (A-Roseville,ex1); [email-masked];
|Luben Tuikov; THALER,PAT (A-Roseville,ex1); SHEEHY,DAVE
|(A-Americas,unix1)
|Subject: RE: effect of initializing CRC reg to 1's depends on
|implementati on? iSCSI
|
|
|--- "CAVANNA,VICENTE V (A-Roseville,ex1)"
|<[email-masked]> wrote:
|> 
|> I do not think we should rely on examples to serve as the
|> specification.
|
|Absolutely true.
|
|But lets include examples _just_ to back it up, and maybe a
|sample implementation (skeleton of), that will be good for
|both hardware and software. Of course some optimization
|will be sacrificed... (e.g. like processing more than one
|bit at a time).
|
|> For
|> this reason I recommend that we modify the spec in one of
|> 3 ways:
|> 
|> 1. explicitly show the reference implementation- what I
|> call the
|> multiply-divide implementation and which I have sent to
|> the reflector. It is
|> basically the ethernet reference implementation modified
|> for the iSCSI poly.
|
|Yep, maybe we should just mention that, plus plenty of
|references, the 4 examples with correct values, and a
|sample bit-at-a-time skeleton implementation.
|
|> 2. use Paul's description
|
|It says that the message is multiplied by x^32, which
|is not correct. See below.
|
|> 3. use Luben's formal description
|
|I wouldn't. In implementor wants to get some speedup, and
|optimization and as a formal definition it doesn't offer
|them. Maybe the implementor will notice that after 32
|clicks the CRC will be all 1's, and that they don't need to
|multiply the message by x^32 if they init the CRC register
|with all 1's and only xor the message bit and the MSb of
|CRC on each click.... but that implies that the implementor
|will have to do extra thinking work.
|
|> The point I have been trying to make is that initializing
|> the register to 1s
|> does not necessarily result in the same process as
|> described in the ethernet
|> spec. Initializing the register to 1s only results in the
|> desired results
|> (i.e. agrees with the examples in the iSCSI spec) if you
|> are using the
|> implementation that I have been calling the
|> multiply-divide implementation.
|> This is the implementation that ethernet had in mind and
|> iSCSI had in mind.
|
|Absolutely true.
|
|> The only reason that the above has worked right for
|> implementors is that
|> they all use the equivalent of a multiply-divide
|> implementation as was
|> described in the ethernet spec but that has not been
|> described in any manner
|> in iSCSI and that I have since recommended that we
|> specify.
|
|Abosultely true.
| 
|> I have to admit that by giving examples the iSCSI spec
|> has removed the
|> ambiguity since nobody will be able to get results that
|> agree with the
|> examples _unless_ they use the multiply-divide
|> implementation but why not
|> make it explicit and eliminate the need for implementors
|> to have familiarity
|> with ethernet and its implementations. Please note that
|> any parallel
|> implementations (that process 8 or 16 or 32 input bits at
|> once) for ethernet
|> are equivalent to the serial implementation that is shown
|> as reference in
|> the ethernet spec.
|
|Abosultely true.
| 
|> I can however implement the iSCSi (and ethernet) CRCs
|> using what I call a
|> divide-only circuit and, if I initialize the circuit to
|> 1's, and process the
|> examples I will not get the results in the iSCSI spec but
|> I will still get
|> the magic constant at the receiver! What I will get
|> instead are the same
|> results as if I had XORed the most significant 32 bits of
|> the messages in
|> the examples with the magic constant and then processed
|> them.
|
|Aboslutely true.
| 
|-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 15:36:35 -0800 (PST)

--- "CAVANNA,VICENTE V (A-Roseville,ex1)"
<[email-masked]> wrote:
> response to an input _and_ its response to an initial
> state. 

All true.

But let's not really aim at ``circuit''.

A simple explanation of how to compute the
CRC, bit at a time will suffice.

From it an engineer can make a circuit,
and a computer scientist can make a program.

It would also be nice to make a document
describing all the math, derivations, etc.
cleanly and clearly and make a reference
to it in the draft. So if anyone is interested
they can follow the reference, if not, an implementaion
is clearly defined.

> One way to specify the circuit is to show the reference

Circuit?

> Another way is to describe the response of the implied

Circuit again?

> folk realized it or not.

Absolutely AGREE!

-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