CRC-16 Reverse Algorithm ?
![Liu, Qingzhu [CAR:CF36:EXCH]'s profile photo](https://lh3.googleusercontent.com/a/default-user=s40-c)
Liu, Qingzhu [CAR:CF36:EXCH]
I try to implement an algorithm for crc-16 reverse
(Poly: 1 + x + x^14 + x^16) in PIC17c756 assembly code.
My questions are:
1. What does the "Reverse' mean ?
2. How is the dividing circuit looking like?
3. Is there a Byte-wise CRC calculation algorithm for it?
4. What is good text book about this topic?
Thansk for helps in advance.
--
Qinghu Liu
BWA, Nortel Networks
Phone: (613)763-3705
Fax: (613)763-6681
email: ql...@nortelnetworks.com
Doug Stell
<ql...@americasm01.nt.com> wrote:
>Hello,
>
>I try to implement an algorithm for crc-16 reverse
>(Poly: 1 + x + x^14 + x^16) in PIC17c756 assembly code.
>
>My questions are:
>1. What does the "Reverse' mean ?
1. You can reverse/reflect the polynomial. The reverse of a good
polynomial is also a good polynomial.
2. You can reverse the direction of the register.
3. You can reverse the final CRC.
>2. How is the dividing circuit looking like?
A few XORs
>3. Is there a Byte-wise CRC calculation algorithm for it?
Sure. You can tradeoff memory for speed by processing n bits at a time
using a 2^n table. A byte-wide implementation is attached below, FYI
>4. What is good text book about this topic?
There really are no good texts. However, there is a great paper
available from
ftp://www.rocksoft.com/clients/rocksoft/papers/crc_v3.txt
http://ww.repairfaq.org/filipg/LINK/F_crc_v3.html
Attached is the table and code fragment for a byte-wide CRC-16. This
is working code which has been successfully used in products by
multiple companies.
/*
---------------------------------------------------------------------
The 16-bit CRC_16 is built upon the following shift-register
reference model. Polynomial: g(x) = 1 + x^2 + x^15 + x^16
-------------------------------------------------------------
|(1) |(x^2) (x^15)| |(x^16)
-->[15] [14]->X->[13] [12] [11] - - - [3] [2] [1]->X->[0]-->X
|
Input data bit 0 first -------
Leading-zero checking is NOT provided by the CRC_16 and it is used
as follows:
1. The crc register is initialized to ZERO.
2. When a crc is appended, it is not inverted.
3. When checking a good message with an appended cec, the
register will return to its initial value of ZERO.
---------------------------------------------------------------------
*/
/* polynomial for bit-wize CRC-16 calculation, using reference model
*/
/* uint16 CRC_16_POLY = 0xa001 ; */
/* table for nibble-wize CRC-16 calculation; smaller table, slower */
/* uint16 CRC_16_TABLE [16] = {
0x0000, 0xcc01, 0xd801, 0x1400, 0xf001, 0x3c00, 0x2800, 0xe401,
0xa001, 0x6c00, 0x7800, 0xb401, 0x5000, 0x9c01, 0x8801, 0x4400,
} ;
*/
/* table for byte-wize CRC-16 calculation; faster, larger table */
uint16 CRC_16_TABLE [256] = {
0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00, 0xcfc1, 0xce81, 0x0e40,
0x0a00, 0xcac1, 0xcb81, 0x0b40, 0xc901, 0x09c0, 0x0880, 0xc841,
0xd801, 0x18c0, 0x1980, 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40,
0x1e00, 0xdec1, 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41,
0x1400, 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081, 0x1040,
0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1, 0xf281, 0x3240,
0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501, 0x35c0, 0x3480, 0xf441,
0x3c00, 0xfcc1, 0xfd81, 0x3d40, 0xff01, 0x3fc0, 0x3e80, 0xfe41,
0xfa01, 0x3ac0, 0x3b80, 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840,
0x2800, 0xe8c1, 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41,
0xee01, 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681, 0x2640,
0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0, 0x2080, 0xe041,
0xa001, 0x60c0, 0x6180, 0xa141, 0x6300, 0xa3c1, 0xa281, 0x6240,
0x6600, 0xa6c1, 0xa781, 0x6740, 0xa501, 0x65c0, 0x6480, 0xa441,
0x6c00, 0xacc1, 0xad81, 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41,
0xaa01, 0x6ac0, 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840,
0x7800, 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81, 0x7c40,
0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1, 0xb681, 0x7640,
0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101, 0x71c0, 0x7080, 0xb041,
0x5000, 0x90c1, 0x9181, 0x5140, 0x9301, 0x53c0, 0x5280, 0x9241,
0x9601, 0x56c0, 0x5780, 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440,
0x9c01, 0x5cc0, 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40,
0x5a00, 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81, 0x4a40,
0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0, 0x4c80, 0x8c41,
0x4400, 0x84c1, 0x8581, 0x4540, 0x8701, 0x47c0, 0x4680, 0x8641,
0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040,
} ;
if ( CRC_16_CRC == algorithm )
{
/* do NOT invert crcReg, but initialize to ZERO */
temp = *crcReg ;
/* generate the CRC over the entire input */
i = partInLen ;
while ( i-- )
{
index = ( temp ^ (uint32)*partIn++ ) & 0xff ;
temp = ( ( temp >> 8 ) ^ CRC_16_TABLE [ index ] ) & 0xffff
;
}
/* do NOT invert output to crcReg for appending */
*crcReg = temp ;
/* check result for return code */
if ( temp )
return ( 1 ) ; /* non-ZERO residue is BAD */
return ( 0 ) ; /* ZERO residue is GOOD */
}
doug
Anne & Lynn Wheeler
one of the interesting things in CRC16 chips in the '70s where
computer boxes using it for bit error detection and RF modem boxes
using the same chip for eliminating runs of zeros. There was strange
situation in some <college campus> RF/broadband systems which were
getting undected transmission errors because of unfortunate
interaction of using the same CRC16 recursively.
--
Anne & Lynn Wheeler | ly...@adcomsys.net, ly...@garlic.com
http://www.garlic.com/~lynn/ http://www.adcomsys.net/lynn/
John Savard
part:
>I try to implement an algorithm for crc-16 reverse
>(Poly: 1 + x + x^14 + x^16) in PIC17c756 assembly code.
>My questions are:
>1. What does the "Reverse' mean ?
It isn't 1 + x^2 + x^15 + x^16, the polynomial turned around
'backwards'.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
Doug Stell
<ly...@adcomsys.net> wrote:
>
>one of the interesting things in CRC16 chips in the '70s where
>computer boxes using it for bit error detection and RF modem boxes
>using the same chip for eliminating runs of zeros. There was strange
>situation in some <college campus> RF/broadband systems which were
>getting undected transmission errors because of unfortunate
>interaction of using the same CRC16 recursively.
CRCs that are initialized to all zeros (CRC-16 is one of these) can
not detect the addition or deletion of leading zeros. Likewise, CRCs
that are initialized to all ones can not not detect the addition or
deletion of leading ones. That's why some CRCs initialize to some
known, fixed value that is neither all ones nor all zeros.
doug
Marty
Doug Stell <p27...@email.mot.com> wrote in message
news:38b710e3....@schbbs.mot.com...
Inserted and/or deleted ones at the start of a ones initialized CRC are
indeed detected.
It's also a good idea to negate the CRC at the end for detecting appended
zeros.
-Marty
David A. Wagner
> Inserted and/or deleted ones at the start of a ones initialized CRC are
> indeed detected.
Did you mean "not detected"? I thought Doug Stell got it right.
Surely I'm missing something. We know that, when the CRC uses an
primitive polynomial, the all-ones state 111..1 goes to 11..10
after clocking it once [*]. In other words, if initialize the CRC
to all-ones and feed in a zero bit, we get the new state 11..10.
But now we can imagine initializing it to the all-ones state and
feeding in a one bit; this complements the feedback tap, and so
where a zero was previously fed in, now a one will be fed in, and
thus the new state will be 11..11, always.
Consequently, if the CRC is initialized to the all-ones state, we
can insert as many one bits at the start of the message as we like,
and it won't affect the final result.
(It may be easier to see this by symmetry: a corresponding property
holds for the all-zeros state and prepending zero bits; and everything
is linear, so you can just complement everything in sight and by
symmetry the property will still hold.)
Where did I go wrong? What am I missing? I'm confused.
[*] Proof: Obvious. Treat it as a free-running LFSR. There are only
two states it can go to, i.e., 11..11 and 11..10. If it goes to
the former, then we have a cycle of length, so the LFSR isn't
full-period, and thus the polynomial can't be primitive, contradiction.
When you eliminate the impossible, whatever remains must be true,
and so surely 111..1 -> 11..10.
Marty
David A. Wagner <d...@blowfish.isaac.cs.berkeley.edu> wrote in message
news:89a959$to6$1...@blowfish.isaac.cs.berkeley.edu...
> In article <#txNt0Ng$GA.262@cpmsnbbsa03>, Marty <an...@nowhere.edu> wrote:
> > Inserted and/or deleted ones at the start of a ones initialized CRC are
> > indeed detected.
>
> Did you mean "not detected"? I thought Doug Stell got it right.
No, I believe Doug's incorrect.
>
> Surely I'm missing something. We know that, when the CRC uses an
> primitive polynomial, the all-ones state 111..1 goes to 11..10
> after clocking it once [*]. In other words, if initialize the CRC
First, CRC's do not ussually use a primitive polynomial. They serve
a somewhat different purpose, error detection rather than max
cyclical length.
Second, when the state of a CRC is all ones it transforms to a non
zero, non all ones state on the next clock. This state is independent (
except for the lsb) of the incomming data bit. The data bit
is not xored in before the decision to toggle the other crc state bits.
> to all-ones and feed in a zero bit, we get the new state 11..10.
> But now we can imagine initializing it to the all-ones state and
> feeding in a one bit; this complements the feedback tap, and so
> where a zero was previously fed in, now a one will be fed in, and
> thus the new state will be 11..11, always.
>
> Consequently, if the CRC is initialized to the all-ones state, we
> can insert as many one bits at the start of the message as we like,
> and it won't affect the final result.
>
Another way to see this is to note that the high speed lookup table
entry for 0xff is not 0xffffff.....00 which would be the case if the state
register remained all ones after recieving a 0xff byte.
> (It may be easier to see this by symmetry: a corresponding property
> holds for the all-zeros state and prepending zero bits; and everything
> is linear, so you can just complement everything in sight and by
> symmetry the property will still hold.)
>
Symmetry is not applicable here. 0's act quite differntly from 1's.
> Where did I go wrong? What am I missing? I'm confused.
>
I hope this explanation makes sense. Try out a CRC-32 which starts
with all ones. You will see it changes state when fed ones.
>
> [*] Proof: Obvious. Treat it as a free-running LFSR. There are only
> two states it can go to, i.e., 11..11 and 11..10. If it goes to
> the former, then we have a cycle of length, so the LFSR isn't
> full-period, and thus the polynomial can't be primitive,
contradiction.
> When you eliminate the impossible, whatever remains must be true,
> and so surely 111..1 -> 11..10.
-Marty
klock...@cix.compulink.co.uk
*THE* reference site for programmers looking to understand and write CRC
algorithms is:
http://www.ross.net/crc/crcpaper.html
Look for the paper "A Painless Guide to CRC Error Detection Algorithms"
by Ross Williams. It explains how they work, gives operating parameters
for several standard CRCs, and includes working portable C source for a
model CRC implementation.
The model code is slow since it's not hard-wired for a particular
endian-ness or CRC flavor and is not table-driven, but this enables it
to be used with many different CRC divisors and reflection options. VERY
handy to be able to check the results of that tight assembly code
against a known good result.
The paper does include a table generation function and guidance on how
to implement a tight, fast table-driven CRC engine.
Keith
http://www.cix.co.uk/~klockstone
------------------------
'Unwise a grave for Arthur'
-- The Black Book of Carmarthen
David A. Wagner
> Second, when the state of a CRC is all ones it transforms to a non
> zero, non all ones state on the next clock.
Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
assuming Fibonacci configuration, not Galois). Right?
> This state is independent (
> except for the lsb) of the incomming data bit.
Right. Now, if 111..11 -> 111..10 under input bit zero, then
111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
> Symmetry is not applicable here. 0's act quite differntly from 1's.
But if S is an initial state and M is a message, then
CRC(complement(S),complement(M)) = complement(CRC(S,M)),
unless you do something specifically to defeat this property
(e.g., appending/prepending fixed bits to M).
Therefore, if you have a problem with leading zeros in M when S = 000...0,
you will also have a problem with leading ones in M when S = 111...1.
Or so it would appear to me.
Where have I gone wrong? Perhaps there is some difference between
CRCs and LFSRs that I'm missing?
Terry Ritter
What a mess!
On Sat, 26 Feb 2000 22:23:34 -0800, in <eu7wttOg$GA.277@cpmsnbbsa03>,
in sci.crypt "Marty" <an...@nowhere.edu> wrote:
>David A. Wagner <d...@blowfish.isaac.cs.berkeley.edu> wrote in message
>news:89a959$to6$1...@blowfish.isaac.cs.berkeley.edu...
>> In article <#txNt0Ng$GA.262@cpmsnbbsa03>, Marty <an...@nowhere.edu> wrote:
>> > Inserted and/or deleted ones at the start of a ones initialized CRC are
>> > indeed detected.
>>
>> Did you mean "not detected"? I thought Doug Stell got it right.
>
>No, I believe Doug's incorrect.
Doug is wrong. CRC *does* indeed detect every 1-bit at the start of a
message. Missing 1's *ARE* detected. Extra 1's *ARE* detected.
Missing and extra 0's are also detected.
>> Surely I'm missing something. We know that, when the CRC uses an
>> primitive polynomial, the all-ones state 111..1 goes to 11..10
>> after clocking it once [*]. In other words, if initialize the CRC
>
>First, CRC's do not ussually use a primitive polynomial.
Generally false. Modern CRC's normally are primitive. CRC32 is
primitive. CRC-16 and CRC-CCITT are composite with a factor of 11,
which is the same as parity error detection. Systems which previously
used parity were thus in no way disadvantaged by using CRC.
>They serve
>a somewhat different purpose, error detection rather than max
>cyclical length.
>
>Second, when the state of a CRC is all ones it transforms to a non
>zero, non all ones state on the next clock. This state is independent (
>except for the lsb) of the incomming data bit. The data bit
>is not xored in before the decision to toggle the other crc state bits.
True, but confusing. Assuming a shift-left CRC, what happens is that
new zero bits are shifted in from the right, and if the data bits are
the same as the shifted out bit (they will be with all-1's CRC and
data), then the poly is not added in. So if we have all-1's, we just
accumulate 0's until the CRC becomes zero, after which data 1's imply
that the poly will be added in.
for shift left:
if (msb(crc) = databit)
crc = crc << 1;
else
crc = (crc << 1) ^ poly;
>> to all-ones and feed in a zero bit, we get the new state 11..10.
Correct, assuming a left-shift computation.
(I think this is from Doug.)
>> But now we can imagine initializing it to the all-ones state and
>> feeding in a one bit; this complements the feedback tap, and so
>> where a zero was previously fed in, now a one will be fed in, and
>> thus the new state will be 11..11, always.
False. Assuming a shift-left CRC starting at "all 1's," we get a new
zero with every shift and every data bit. Since msb(crc) = databit,
what we don't get is the poly addition, and that is the way the
rightmost bit gets set, so it stays zero.
>> Consequently, if the CRC is initialized to the all-ones state, we
>> can insert as many one bits at the start of the message as we like,
>> and it won't affect the final result.
FALSE. Try it.
>Another way to see this is to note that the high speed lookup table
>entry for 0xff is not 0xffffff.....00 which would be the case if the state
>register remained all ones after recieving a 0xff byte.
Correct. CRC32 with crc = 0xffffffff and data = 0xff produces
crc = 0xffffff00
>> (It may be easier to see this by symmetry: a corresponding property
>> holds for the all-zeros state and prepending zero bits; and everything
>> is linear, so you can just complement everything in sight and by
>> symmetry the property will still hold.)
>>
>
>Symmetry is not applicable here. 0's act quite differntly from 1's.
Well, if we have "all-0's" and data of 0's we will accumulate more
zeros, which will not detect leading zeros. The whole point of
setting the CRC register to all-1's prior to CRC operations is to
detect missing bits. I suppose the symmetry breaks because the
computation is crc = crc*2 instead of crc = crc*2 + 1.
>> Where did I go wrong? What am I missing? I'm confused.
>I hope this explanation makes sense. Try out a CRC-32 which starts
>with all ones. You will see it changes state when fed ones.
Exactly the right answer: Try it.
>> [*] Proof: Obvious. Treat it as a free-running LFSR. There are only
>> two states it can go to, i.e., 11..11 and 11..10. If it goes to
>> the former, then we have a cycle of length, so the LFSR isn't
>> full-period, and thus the polynomial can't be primitive,
>contradiction.
>> When you eliminate the impossible, whatever remains must be true,
>> and so surely 111..1 -> 11..10.
Alas, CRC32 is primitive. Now, about that proof....
---
Terry Ritter rit...@io.com http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Terry Ritter
On 27 Feb 2000 12:49:58 -0800, in
<89c2lm$un2$1...@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
>In article <eu7wttOg$GA.277@cpmsnbbsa03>, Marty <an...@nowhere.edu> wrote:
>> Second, when the state of a CRC is all ones it transforms to a non
>> zero, non all ones state on the next clock.
>
>Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
>assuming Fibonacci configuration, not Galois). Right?
Right.
>> This state is independent (
>> except for the lsb) of the incomming data bit.
>
>Right. Now, if 111..11 -> 111..10 under input bit zero, then
>111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
No.
In a shift-left CRC, 0's always shift in, and this is independent of
the data value. the only way the rightmost bit gets set to a 1 is
from the poly add.
>> Symmetry is not applicable here. 0's act quite differntly from 1's.
>
>But if S is an initial state and M is a message, then
> CRC(complement(S),complement(M)) = complement(CRC(S,M)),
>unless you do something specifically to defeat this property
>(e.g., appending/prepending fixed bits to M).
No.
>Therefore, if you have a problem with leading zeros in M when S = 000...0,
>you will also have a problem with leading ones in M when S = 111...1.
>Or so it would appear to me.
>
>Where have I gone wrong? Perhaps there is some difference between
>CRCs and LFSRs that I'm missing?
There is no real difference. Certainly a CRC has a data input that
LFSR's do not have. I suppose what you are missing is a understanding
of the CRC algorithm.
David A. Wagner
> Missing and extra 0's are also detected.
How can this be? Take a vanilla CRC initialized to the all-zeros state.
Clock in a single zero bit. The result will still be the all-zeros
state. Clock in as many zero bits as you like, the state won't change.
Consequently, the CRC can't tell the difference between the message
0^j || M (i.e., j zeros followed by M) and the message 0^k || M.
Sure, in a real implementation you should add extra precautions to eliminate
this property. For instance, simply avoid starting in the all-zeros state.
Or start in the all-zeros state but always prepend a one-bit to the message
(a roughly equivalent countermeasure). But if you do nothing, it seems you
get into trouble. And I'm talking about the vanilla "do-nothing" case.
Consider the pseudocode you suggested:
if (msb(crc) = databit)
crc = crc << 1;
else
crc = (crc << 1) ^ poly;
If you run this code fragment with crc=0 and databit=0, you will execute the
statement `crc = crc << 1;', and since 0 << 1 = 0, we will still have crc=0
after the code fragment. This supports what I said above.
There, I tried it. Now, where did I go wrong?
Ignore the all-ones stuff for the moment;
Are you *sure* I'm wrong about this all-zeros property?
David A. Wagner
> d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
> >Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
> >assuming Fibonacci configuration, not Galois). Right?
>
> Right.
>
> >111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
>
> No.
>
> In a shift-left CRC, 0's always shift in, and this is independent of
> the data value. the only way the rightmost bit gets set to a 1 is
> from the poly add.
Ok. That looks like the source of the confusion, then. Thanks.
See my earlier quoted comments -- I was assuming we were talking
about a Fibonacci configuration (what CRC folks seem to call "forward"
CRC), rather than a Galois configuration (what CRC folks seem to be
calling a "reverse" CRC, if I understand correctly). This seems to
be where we diverged.
As far as I can see, it remains true that the all-ones state is bad
for Fibonacci ("forward"?) if you xor the incoming data bit along with
the feedback taps to get your new state-bit. But the poster was
apparently talking about Galois / "reverse" configuration.
I think.
Right?
lordcow77
>Are you *sure* I'm wrong about this all-zeros property?
>
>
You're right if the CRC register starts with all zeroes, but IF
the register is initially initialized with all ones, the CRC
algorithm will detect a prepended string ones OR zeroes. Just
run the algorithm through a couple of times (I find the byte-
wise table method more clear for intiutive expression of these
concepts).
REG=0xffffffff
After we push a 0x00 byte into the register, we get
REG=0xffffff00 and so on until REG=0x00000000.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
David A. Wagner
> if (msb(crc) = databit)
> crc = crc << 1;
> else
> crc = (crc << 1) ^ poly;
Ok, let's try this.
I will show a initial state which allows you to prepend as many
one bits as you like without changing the final CRC hash.
(But I could well have made mistakes in my calculations, so
check my work... Does it look right to you?)
Suppose, before we execute this code fragment, we have
crc == poly ^ (poly<<1) ^ (poly<<2) ^ (poly<<3) ^ ...
and msb(crc) != databit. The 'else' branch will be executed,
and we will compute
crc' := ((crc )<<1) ^ poly
= ((poly ^ (poly<<1) ^ (poly<<2) ^ ...)<<1) ^ poly
= (((poly<<1) ^ (poly<<2) ^ (poly<<3) ^ ...) ^ poly
= poly ^ (poly<<1) ^ (poly<<2) ^ (poly<<3)^ ...
so the state of the CRC before and after the code fragment will
remain unchanged.
The only thing to check now is that the requirement
msb(crc) != databit can be satisfied when databit == 1.
The result: It can.
Why? It's not too hard to see that msb(crc) == parity(poly).
Furthermore, whenever the CRC uses an primitive polynomial (or
even just an irreducible one), we have parity(poly) == 0.
(Why? If parity(poly) == 1, then x+1 divides the polynomial,
and hence the polynomial can't be irreducible or, for that matter,
primitive.) Hence msb(crc) == 0 always, and so if databit == 1,
we will automatically have msb(crc) != databit.
Marty
at the
end of it all he will be more enlightened.
-Marty
Terry Ritter <rit...@io.com> wrote in message
news:38b9fa75...@news.io.com...
>
> On 27 Feb 2000 15:25:11 -0800, in
> <89cbon$v9s$1...@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
> d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
>
> >In article <38b9ad89...@news.io.com>, Terry Ritter <rit...@io.com>
wrote:
> >> d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
> >> >Yes, 111..11 -> 111..10 (if the incoming data bit is zero;
> >> >assuming Fibonacci configuration, not Galois). Right?
> >>
> >> Right.
> >>
> >> >Right. Now, if 111..11 -> 111..10 under input bit zero, then
> >> >111..11 -> 111..10 xor 1 = 111..11 under input bit one. No?
> >>
> >> No.
> >>
> >> In a shift-left CRC, 0's always shift in, and this is independent of
> >> the data value. the only way the rightmost bit gets set to a 1 is
> >> from the poly add.
> >
> >Ok. That looks like the source of the confusion, then. Thanks.
> >
> >See my earlier quoted comments -- I was assuming we were talking
> >about a Fibonacci configuration (what CRC folks seem to call "forward"
> >CRC), rather than a Galois configuration (what CRC folks seem to be
> >calling a "reverse" CRC, if I understand correctly). This seems to
> >be where we diverged.
>
> Yeah. We "diverged" when some of us were talking about CRC, and
> others of us were not.
>
>
> >As far as I can see, it remains true that the all-ones state is bad
> >for Fibonacci ("forward"?) if you xor the incoming data bit along with
> >the feedback taps to get your new state-bit.
>
> Obviously, that is not CRC.
>
>
> >But the poster was
> >apparently talking about Galois / "reverse" configuration.
>
> I know quite a few different various configurations for CRC. But the
> CRC result is unambiguous.
>
> CRC does use LFSR operations. But not all forms of LFSR are CRC. I
> don't know whether we can do a CRC in the other LFSR form. Maybe we
> can, but we had better get the same result from it. Which means that
> it had better detect both leading 1's and 0's.
>
>
> >I think.
> >
> >Right?
>
> No.
Terry Ritter
Terry Ritter
On 27 Feb 2000 15:08:08 -0800, in
<89caoo$v8j$1...@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
>In article <38b9ab7e...@news.io.com>, Terry Ritter <rit...@io.com> wrote:
>> Missing and extra 0's are also detected.
>
>How can this be? Take a vanilla CRC initialized to the all-zeros state.
>Clock in a single zero bit. The result will still be the all-zeros
>state. Clock in as many zero bits as you like, the state won't change.
If the CRC register is initialized with zeros, it cannot detect
leading zeros in the data. That problem was detected early in CRC
use, and from that time it became common to init the CRC register as
ones. When this is done, CRC can detect both leading zeros and
leading ones.
Here is what you said, which defines the current issue:
>David A. Wagner <d...@blowfish.isaac.cs.berkeley.edu> wrote in message
>news:89a959$to6$1...@blowfish.isaac.cs.berkeley.edu...
>> In article <#txNt0Ng$GA.262@cpmsnbbsa03>, Marty <an...@nowhere.edu> wrote:
>> > Inserted and/or deleted ones at the start of a ones initialized CRC are
>> > indeed detected.
>>
>> Did you mean "not detected"? I thought Doug Stell got it right.
And here is the statement which you thought was right:
On Fri, 25 Feb 2000 23:34:15 GMT, in
<38b710e3....@schbbs.mot.com>, in sci.crypt p27...@email.mot.com
(Doug Stell) wrote:
>[...]
>CRCs that are initialized to all zeros (CRC-16 is one of these) can
>not detect the addition or deletion of leading zeros. Likewise, CRCs
>that are initialized to all ones can not not detect the addition or
>deletion of leading ones.
The last statement was false.
>Consequently, the CRC can't tell the difference between the message
>0^j || M (i.e., j zeros followed by M) and the message 0^k || M.
>
>Sure, in a real implementation you should add extra precautions to eliminate
>this property. For instance, simply avoid starting in the all-zeros state.
>Or start in the all-zeros state but always prepend a one-bit to the message
>(a roughly equivalent countermeasure). But if you do nothing, it seems you
>get into trouble. And I'm talking about the vanilla "do-nothing" case.
The CRC register has to be initialized to *some* known value. The
vanilla case is to initialize the CRC to all-1's.
>Consider the pseudocode you suggested:
> if (msb(crc) = databit)
> crc = crc << 1;
> else
> crc = (crc << 1) ^ poly;
>If you run this code fragment with crc=0 and databit=0, you will execute the
>statement `crc = crc << 1;', and since 0 << 1 = 0, we will still have crc=0
>after the code fragment. This supports what I said above.
>
>There, I tried it. Now, where did I go wrong?
By not actually trying some working CRC code after thinking about it.
>Ignore the all-ones stuff for the moment;
>Are you *sure* I'm wrong about this all-zeros property?
What you said originally was wrong. I'm not sure what you have
changed to now.
Terry Ritter
On 27 Feb 2000 15:20:51 -0800, in
<89cbgj$v98$1...@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
>In article <38b9ab7e...@news.io.com>, Terry Ritter <rit...@io.com> wrote:
>> if (msb(crc) = databit)
>> crc = crc << 1;
>> else
>> crc = (crc << 1) ^ poly;
>
>Ok, let's try this.
>I will show a initial state which allows you to prepend as many
>one bits as you like without changing the final CRC hash.
But that is not the issue.
You have agreed with the statement that CRC could not detect faults in
*leading* 1's.
Here is the original statement:
On Fri, 25 Feb 2000 23:34:15 GMT, in
<38b710e3....@schbbs.mot.com>, in sci.crypt p27...@email.mot.com
(Doug Stell) wrote:
>[...]
>CRCs that are initialized to all zeros (CRC-16 is one of these) can
>not detect the addition or deletion of leading zeros. Likewise, CRCs
>that are initialized to all ones can not not detect the addition or
>deletion of leading ones.
The last statement is false. And since modern CRC's do set the CRC
register to 1's they do indeed detect both leading 0's and 1's. End
of story.
Are you now saying that if, mid operations, the CRC register has some
particular state, it will not detect extra 1's? While that may be an
interesting idea, it is a completely different issue.
Terry Ritter
On Sun, 27 Feb 2000 20:57:23 -0800, in <#IF5Piag$GA.57@cpmsnbbsa04>,
in sci.crypt "Marty" <an...@nowhere.edu> wrote:
>Terry, You gave a better explanation than I had. David is persistent, maybe
>at the
>end of it all he will be more enlightened.
I am not overly hopeful.
Doug Stell
>
>Doug Stell <p27...@email.mot.com> wrote in message
>>
>> CRCs that are initialized to all zeros (CRC-16 is one of these) can
>> not detect the addition or deletion of leading zeros. Likewise, CRCs
>> that are initialized to all ones can not not detect the addition or
>> deletion of leading ones. That's why some CRCs initialize to some
>> known, fixed value that is neither all ones nor all zeros.
>
>Inserted and/or deleted ones at the start of a ones initialized CRC are
>indeed detected.
I am indeed wrong. A CRC initialized to all ones can detect inserted
and/or deleted leading ones.
doug
David A. Wagner
> Are you now saying that if, mid operations, the CRC register has some
> particular state, it will not detect extra 1's? While that may be an
> interesting idea, it is a completely different issue.
Yup.
But this state I'm describing, in some vague sense that I don't know how
to put my finger on, feels like "just" a renaming of the all-ones state.
In other words, I *suspect* that, no matter which configuration of CRC you
use, there will usually be some initial state which doesn't detect leading
ones. The exact value of that initial state depends on the configuration.
If you pick one particular configuration, that bad initial state is all-ones;
if you pick another one, that bad initial state is something else.
But I don't have any evidence for this. These are just squishy, unscientific,
unproven, groundless guesses.
Terry Ritter
On 29 Feb 2000 12:50:00 -0800, in
<89hbdo$8d9$1...@blowfish.isaac.cs.berkeley.edu>, in sci.crypt
d...@blowfish.isaac.cs.berkeley.edu (David A. Wagner) wrote:
This just doesn't make any sense to me. We don't pick just any random
initial state for CRC's. In data communications at least, both ends
have to pick the same starting state. In general, that starting state
is all-ones, which does detect both leading zeros and ones.
The first uses of the first-generation 16-bit CRC's were initialized
to all-zeros, so a zeros init might have some support. But I am aware
of no support for a random initialization value.
So even if the guess is true, it simply has nothing to do with real
CRC initialization. It is a theoretical problem which never arises
because we have a standard init value which does not do that.
David A. Wagner
configurations that could have a problem with the all-ones initialization
state. Good.
Sorry for the confusion. It was my fault. Thanks for explaining.
Douglas A. Gwyn
will fail to detect. One wants to design the scheme so that they
are not among the *probable* modes of garbling.
D. J. Bernstein
> The simple fact is, there are some garbles that *any* CRC scheme
> will fail to detect.
False. If you have two different messages up to a billion bits long, for
example, then that difference will be detected by more than 99.99999% of
the possible CRC-64 polynomials.
---Dan
Douglas A. Gwyn
I'm sorry; you didn't parse it the way I meant it:
For *any* CRC scheme, there are some garbles that it will fail to
detect.
Which is meant to be an almost-trivial observation,
but nevertheless one that was relevant to the discussion.
It is the *probability* of garbles like a run of 0s or 1s
that made it especially important to guard against those.
(Answering the unasked question, "Why are we so concerned
about those garbles when there are so many other garbles?".)
Paul Koning
>
> Douglas A. Gwyn <DAG...@null.net> wrote:
> > The simple fact is, there are some garbles that *any* CRC scheme
> > will fail to detect.
>
> False. If you have two different messages up to a billion bits long, for
> example, then that difference will be detected by more than 99.99999% of
> the possible CRC-64 polynomials.
Perhaps you're talking about different subjects.
As far as I know Doug is right if he meant "for any given CRC
polynomial, there are error patterns it will fail to detect".
That's obvious (it has to be true for any finite length error
detecting code, CRC or not).
More specifically, there's the "Hamming distance" of a CRC, which
is a function of the message length, and which says what the minimum
number of bits is that you can change and have it not be detected.
For example, for CRC-32 and Ethernet sized messages, that value is 4.
(For long messages, over 11k bytes or so if I remember right, it drops
to 3, which is why it is unwise to use CRC-32 with MTUs that large.)
Those minimal undetected errors have weird patterns, though -- a few
bits scattered in very precisely picked places far from each other.
In addition, there's a burst length such that not all burst errors of
that length are detected. For CRC-32 (again working from possibly
faulty memory) I believe that length is 33 bits. Is it N+1 bits for
any CRC-N?
I'm interpreting Dan's comment as "for any message even a very long
one, any of the appropriate polynomials for CRC-64 will detect nearly
all possible errors". That too fits; the rule of thumb is that long
random errors (longer than the burst length I mentioned above) are
detected in all but 2^-N cases, for CRC-N.
One interesting point is that deleted or added bits or bytes count
as an error burst from then to end of message, which is why CRC
alone is not a good mechanism if your datalink framing is capable of
truncating or concatenating messages, or adding or deleting bits or
bytes. HDLC has this property (due to bit stuffing) as do Bisync and
Packet over Sonet (due to character escaping). FDDI has it because
the frame terminator is fairly vulnerable, and ATM AAL-5 has it because
the end of packet indicator is just one bit and cells can easily be
lost.
In many of these, the solution used is to do a length check as well;
ATM AAL-5 indeed requires this.
paul
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: pko...@lucent.com
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
Scott Nelson
[snip]
>In addition, there's a burst length such that not all burst errors of
>that length are detected. For CRC-32 (again working from possibly
>faulty memory) I believe that length is 33 bits. Is it N+1 bits for
>any CRC-N?
>
If you feed all possible N bit values into an N bit crc,
(regardless of how it is initialized) you will get all possible
N bit values. It only takes a 32 bit error burst, not 33.
Also, any crc has a pattern which will not change
when fed a 1 bit. Therefore it is always possible
to construct a message 2N bits long which can be
extended indefinitely by inserting 1's after N bits,
without changing the CRC.
Scott Nelson <sc...@helsbreth.org>
Terry Ritter
On Fri, 25 Feb 2000 14:18:56 -0500, in
<38B6D5A0...@americasm01.nt.com>, in sci.crypt "Liu, Qingzhu
[CAR:CF36:EXCH]" <ql...@americasm01.nt.com> wrote:
>Hello,
>
>I try to implement an algorithm for crc-16 reverse
>(Poly: 1 + x + x^14 + x^16) in PIC17c756 assembly code.
>
>My questions are:
>1. What does the "Reverse' mean ?
"Reverse" means that the poly is intended to operate on bit-reversed
data. This was needed for large 60's-style computer reel-to-reel
tapes where the data could be read from either direction.
"Reverse" also means that the CRC poly is reversed from the original:
If we write CRC-16 as 0x18005, CRC-16 reverse will be 0x14003, which
is the same bit pattern read from opposite directions.
The way the reverse operation works depends upon the way CRC is
developed and deposited; this is the forward direction. The most
trivial way is to init the CRC register as zeros, CRC the data, then
deposit the CRC result, MS byte first. Then, when we traverse the
data plus the stored CRC result, the CRC result will be zeros.
To traverse the data in reverse direction, we again init the CRC
register as zeros, use the inverse CRC polynomial, and process the
data bits in reverse (starting with the lsb of the saved CRC value).
Again, the CRC result will be zeros.
It is also possible to init as ones, and to save the complement of the
CRC value (so the result will be non-zero), and check in reverse, but
doing that is more complicated.