RE: found the constant for divide-only circuit!

["CAVANNA,VICENTE V (A-Roseville,ex1)" <vince_cavanna@agilent.com>]

I have modified the preferred implementation (simultaneous multiply-divide
circuit) to include the control logic as Paul suggested (similar to ethernet
spec). By showing this circuit the iSCSI spec becomes less ambiguous and,
just maybe, Luben and Paul will be happy men :-).
Vince <<SerialCRC32c.pdf>> 

>  -----Original Message-----
> From: 	CAVANNA,VICENTE V (A-Roseville,ex1)  
> Sent:	Thursday, December 13, 2001 7:46 PM
> To:	'ips@ece.cmu.edu'
> Cc:	'ltuikov@yahoo.com'; 'Paul Koning'; SHEEHY,DAVE (A-Americas,unix1);
> THALER,PAT (A-Roseville,ex1); CAVANNA,VICENTE V (A-Roseville,ex1); 'Julian
> Satran'
> Subject:	found the constant for divide-only circuit!
> 
> 
> Luben and I found the constant polynomial, C1(x), that makes the following
> two operations eqivalent for a divide-only implementation (attached) of
> CRC32c:
> 
> 1. CRC register initialized to zeroes and C1(x) added (XORed) to the most
> significant bits of the message.
> 
> 2.CRC initialized to ones and nothing added to the message.
> 
> At the end I summarize my recommendation to Julian for fixing the iSCSI
> spec.
> 
> C1(x) turned out to be the same as the magic constant specified in the
> iSCSI spec!!
> As some of us have explained before, the magic constant is equal to
> L(x)x^32 modulo G(x) with L(x) being the 32 bit all 1's poly and G(x) the
> CRc poly. For the simultaneous multiply and divide circuit we already knew
> that the constant, C2(x), is just L(x).
> 
> We now know the equivalences for both implementations:
> 
> 1. For the divide-only circuit, initializing the register to all 1s and
> applying an all zeroes message is equivalent (produces the same results)
> as initializing the register to all zeroes and applying the C1(x) input
> message above.
> 
> We can also say that C1(x) is what you would add (not append) to the most
> significant 32 bits of your message and apply to the divide-only circuit
> which has been initialized to zeroes. You would get the same results as if
> you initialized the circuit to ones and applied the raw message.
> 
> 2. For the simultaneous multiply and divide circuit we already knew that
> initializing the register to 1s and applying an all zeroes message is
> equivalent to initializing the register to zeroes and applying the C2(x)
> input message.
> 
> So C2(x) is what you would add (not append) to the most significant 32
> bits of your message and apply to the multiply-divide circuit which has
> been initialized to zeroes. You would get the same results as if you
> initialized the circuit to ones and applied the raw message.
> 
> For those interested here is one way to find the constant C1(x):
> 
> Initialize the divide-only circuit to 1's and apply an all-zeroes message.
> Look at the state after the 32nd clock and record that value, which I
> called C1(x). We now want to find what 32-bit input message would produce
> the same result when the circuit is initialized to 0's. I reasoned that,
> until the 33rd clock, the order of the input poly is less than that of the
> CRC polynomial and thus the current remainder must be equal to the input
> message itself. Thus if I let the input be C1(x), after 32 clocks I would
> end up with C1(x) in the CRC register which was indeed the case. 
> Luben had a different development (see upcoming internet draft) that is
> more rigorous and shows why C1(x) happens to be equal to the magic
> constant.
> 
> 
> 	There are several ways we can fix the iSCSi spec:
> 
> 	1. making it explicit that the assumed implementation performs
> simultaneous multiplication by x^32 and division by G(x) by showing an
> implementation such as the attached circuit OR 
> 
> 	2. saying that the CRC must be initialized to ones and not saying
> that this is equivalent to adding 1s to the most significant 32 bits of
> the message (because the statement would be only true for one
> implementation).
> 
> 	3. saying that the CRc must be initialized to ones and explaining
> that, for the multiply-divide implementation, this is equivalent to adding
> 1s to the most significant 32 bits, and, for the divide-only
> implementation, this is equivalent to adding the magic constant to the
> most significant 32 bits.
> 
> 	Option one is the simplest, and the one I recommend. In fact, for
> options 2 and 3 we may (need to think about this some more) need to fix
> the examples.
> 
> 
> Vince
>  << File: BothCircuits.pdf >> 
> 
> 
> 
> 	 -----Original Message-----
> 	From: 	CAVANNA,VICENTE V (A-Roseville,ex1)  
> 	Sent:	Wednesday, December 12, 2001 10:06 PM
> 	To:	'ips@ece.cmu.edu'
> 	Cc:	'ltuikov@yahoo.com'; 'Paul Koning'; CAVANNA,VICENTE V
> (A-Roseville,ex1); SHEEHY,DAVE (A-Americas,unix1); THALER,PAT
> (A-Roseville,ex1)
> 	Subject:	assumed CRC circuit performs simultaneous mult and
> division
> 
> 	Regarding my earlier memo "effect of initializing CRC reg to 1's
> depends on implementation?", here are more details and a proposed fix.
> This little detail has generated a _lot_ of discussion among Luben Tuikov,
> Paul Koning and myself and in fact we have not all quite agreed yet on the
> severity of hte problem and how to fix it. 
> 
> 	Where I see the iSCSI spec deficient is in not making explicit that
> the assumed circuit performs _simultaneous_ multiplication by x^32 of the
> message, M(x), and division by G(x). When the spec says that the message
> M(x) is multiplied by x^32 and divided by G(x), if the spec said that the
> division must occur simultaneously with the multiplication by x^32, as it
> does in the attached circuit, then the spec would be correct. In other
> words, with that assumption the spec is correct in saying that
> initializing the CRC register to 1's is equivalent (produces same
> remainder and quotient) to complementing the first 32 bits of the message.
> 
> 	If the assumed circuit is the divide-only circuit that I also am
> attaching, then initializing the CRC register to 1's, as the spec
> requires, will _not_ result in the correct remainder specified by iSCSI in
> its examples since initializing _that_ circuit to 1's implements a
> different division than what the iSCSI examples assume. 
> 	On the other hand the receiver will still compute the same magic
> constant that the iSCSi spec specifies since the magic constant is not
> dependent on the actual message or its remainder but rather on the fact
> that there were no errors. This is what Luben observed and what he and
> Paul and I have been discussing (and still are) for a while.
> 
> 	This is why I am claiming that the iSCSI spec should be fixed by
> either:
> 
> 	1. making it explicit that the assumed circuit performs simultaneous
> multiplication by x^32 and division by G(x) such as the attached circuit
> OR 
> 
> 	2. saying that hte most significant 32 bits of the message should be
> complemented - rather than saying that the CRC register be initialized to
> 1s, since the effect of the last statement is implementation dependent,
> whereas the effect of the first statement is independent of the
> implementation.
> 
> 	Vince
> 
> 	 << File: Scan_Fro.pdf >> 
>

SerialCRC32c.pdf