lkml.org 
[lkml]   [2005]   [Aug]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: CCITT-CRC16 in kernel
    > The "Bible" has been:
    > http://www.joegeluso.com/software/articles/ccitt.htm

    This fellow is just plain Confused.

    First of all, The Standard Way to do it is to preset to -1 *and* to
    invert the result. Any combination is certainly valid, but if you don't
    invert the CRC before appending it, you fail to detect added or deleted
    trailing zero bits, which can be A Bad Thing in some applications.

    Secondly, I see what he's on about "trailing zero bits", but he isn't
    aware that *everyone* uses the "implicit" algorithm, so the reason that
    the specs don't explain that very well is that the spec writers forgot
    there was any other way to do it.

    So his long-hand calculations are just plain WRONG. Presetting the CRC
    accumulator to -1 is equivalent to *inverting the first 16 bits of the
    message*, and NOT to prepending 16 1 bits.

    Also, he's got his bit ordering wrong.

    The correct way to do it, long-hand, is this:

    Polynomial: x^16 + x^12 + x^5 + 1. In bits, that's 10001000000100001
    Message: ascii "A", 0x41.
    Convert to bits, lsbit first: 10000010
    Append trailing padding to hold CRC: 100000100000000000000000
    Invert first 16 bits: 011111011111111100000000

    Now let's do the long division. You can compute the quotient, but it's
    not needed for anything, so I'm not bothering to write it down:

    011111011111111100000000
    10001000000100001
    -----------------
    11100111110111010
    10001000000100001
    -----------------
    11011111100110110
    10001000000100001
    -----------------
    10101111000101110
    10001000000100001
    -----------------
    10011100000111100
    10001000000100001
    -----------------
    0101000000111010 - Final remainder

    XOR trailing padding with computed CRC (since we used padding of zero,
    that's equivalent to overwriting it): 100000100101000000111010
    Or, if the CRC is inverted: 100000101101011111000101

    To double-check, let's verify that CRC. I'm verifying the
    non-inverted CRC, so I expect a remainder of zero:

    Received message: 100000100101000000111010
    Invert first 16 bits: 011111011010111100111010

    011111011010111100111010
    10001000000100001
    -----------------
    11100110100111011
    10001000000100001
    -----------------
    11011101000110101
    10001000000100001
    -----------------
    10101010000101001
    10001000000100001
    -----------------
    10001000000100001
    10001000000100001
    -----------------
    000000000000000 - Final remainder

    Now, note how in each step, the decision whether to XOR with the 17-bit
    polynomial is made based soley on the leading bit of the remainder.
    The trailing 16 bits are modified (by XOR with the polynomial), but
    not examined.

    This leads to a standard optimization, where the bits from the dividend
    are not merged into the working remainder until the moment they are
    needed. Each step, the leading bit of the 17-bit remainder is XORed
    with the next dividend bit, and the polynomial is XORed in as required
    to force the leading bit to 0. Then the remainder is shifted, discarding
    the leading 0 bit and shifting in a trailing 0 bit.

    This technique avoids the need for explicit padding, and is the way
    that the computation is invariably performed in all but pedagogical
    implementations.

    Also, the awkward 17-bit size of the remainder register can be reduced
    to 16 bits with care, as at any given moment, one of the bits is known
    to be zero. It is usually the trailing bit, but between the XOR and
    the shift, it is the leading bit.

    (Again, recall that in a typical software implementation, the "leading
    bit" is the lsbit and the "trailing bit" is the msbit. Because the
    CRC algorithm does not use addition or carries or anything of the sort,
    it does not care which convention software uses.)

    > I have spent over a week grabbing everything on the Web that
    > could help decipher the CCITT CRC and they all show this
    > same kind of code and same kind of organization. Nothing
    > I could find on the Web is like the linux kernel ccitt_crc.
    > Go figure.

    Funny, I can find it all over the place:
    http://www.nongnu.org/avr-libc/user-manual/group__avr__crc.html
    http://www.aerospacesoftware.com/checks.htm
    http://www.bsdg.org/SWAG/CRC/0011.PAS.html
    http://www.ethereal.com/lists/ethereal-dev/200406/msg00414.html
    http://pajhome.org.uk/progs/crcsrcc.html
    http://koders.com/c/fidE2A434B346BFDCD29DA556A54E37C99E403ED26B.aspx

    > Do you suppose it was bit-swapped to bypass a patent?

    There's no patent. That's just the way that the entire SDLC family of
    protocols (HDLC, LAPB, LAPD, SS#7, X.25, AX.25, PPP, IRDA, etc.) do it.
    They transmit lsbit-first, so they compute lsbit-first.
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-08-12 12:50    [W:0.025 / U:0.720 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site