> On Wed, 15 Jan 2003, Scott Dattalo wrote:
>
> <snip>
>
> Not wanting to leave good enough alone, I dove into the CRC16
> calculation again. I found another implementation that also takes
> only 17-cycles. Oh well. But what's interesting, is I found a way to
> express the CRC16 algorithm in a very simple way that's useful for
> high level languages:
>
>
> int crc_1021(int data)
> {
>
>   int x;
>
>   x = ((crc>>8) ^ data) & 0xff;
>   x ^= x>>4;
>
>   crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;
>
>   crc &= 0xffff;
>
>   return crc;
>
> }
>
>
> Any barrel-shifter equipped processor ought to rip through this in
> just a few cycles! I arrived at this by taking the PIC code and
> writing it algebraically and then simplifying it. I was surprised to
> see what popped out. Here's another PIC routine that uses this C
> implementation as a guide.
>
>
> CRC16_1021_version2:
>
>         xorwf   CRC16_High,w
>         movwf   Index
>         andlw   0xf0
>         swapf   Index,f
>         xorwf   Index,f         ;'x' with high and low nibbles swapped
>
>
>         movf    Index,W
>         andlw   0xf0            ; x<<12
>         xorwf   CRC16_Low,W
>         movwf   CRC16_High
>
>         rlf     Index,W         ; x<<5
>         rlf     Index,W         ;
>         xorwf   CRC16_High,f
>         andlw   0xe0
>         xorwf   CRC16_High,f
>
>         swapf   Index,F         ; x
>         xorwf   Index,W
>         movwf   CRC16_Low
>
> Scott

>
> Scott, other than just clarifying that the poly you are using above
> (16-12-5-0) are CRC16-CCITT or in short form X.25, or even, FCS for IBM
> protocols, the CRC routines can be done in several ways, from look-ahead
> tables to strange routines.
>
> The logic I am being using for many years, for pure (16-15-2-0) CRC16 (not
> CCITT/X.25/FCS), using any programming platform is this:
>
> --------------------------------------------------
> Variables:
>
>    CRC16VAR (16 bits composed by CRC16H + CRC16L)
>    DATABYTE
>    8BITSCOUNTER
>
> 1) At start CRC16VAR = 0
> 2) 8BITSCOUNTER = 8
> 3) Logic Shift Right CRC16VAR, save carryBit
> 4) Logic Shift Right DATABYTE, XOR carrybit with carryBit from [2]
> 5) If the above XOR = 1 then XOR hex "A001" over the CRC16VAR
> 6) Decrement 8BITSCOUNTER, if not zero, goto 3.
> 7) If more data, load into DATABYTE and goto 2.

> Hi,
>
>
> Scott Dattalo wrote:
> <snip>
> >Not wanting to leave good enough alone, I dove into the CRC16
> calculation
> >again. I found another implementation that also takes only 17-cycles.
> Oh
> >well. But what's interesting, is I found a way to express the CRC16
> >algorithm in a very simple way that's useful for high level languages:
> <snip>
>
> For some reason I missed this thread ( and Scotts original post ) but
> it's never to
> late for catching up :). Anyway, interesting expression. I left the crc
> stuff
> on the backburner for a while but crc-32 is luring me to take another
> stab, not
> that I'll ever have the insightfullness that Scott has but I might
> provide some
> neat ideas :).

> On Tue, 21 Jan 2003, Tony K|bek wrote:
>
> > Hi,
> >
> >
> > Scott Dattalo wrote:
> > <snip>
> > >Not wanting to leave good enough alone, I dove into the CRC16
> > calculation
> > >again. I found another implementation that also takes only 17-cycles.
> > Oh
> > >well. But what's interesting, is I found a way to express the CRC16
> > >algorithm in a very simple way that's useful for high level languages:
> > <snip>
> >
> > For some reason I missed this thread ( and Scotts original post ) but
> > it's never to
> > late for catching up :). Anyway, interesting expression. I left the crc
> > stuff
> > on the backburner for a while but crc-32 is luring me to take another
> > stab, not
> > that I'll ever have the insightfullness that Scott has but I might
> > provide some
> > neat ideas :).
>
> I was wondering why you hadn't responded yet!
>
> >
> > So if time permits an crc-32 should be added to this list sometimes in
> > the future.
> > This could be useful for tcp/ip implementations, as far as I know
> > current implemenations
> > does not compute the full crc32 for the outgoing message.
>
> I don't know why, but I've been thinking about the CRC-32 too :). I was
> surprised to discover that the 8-bit CRC in Dallas' 1-wire products is
> more difficult to implement than the 16-bit CRCs. It lacks the symmetry of
> say a CRC-16 computation.  This made me curious about the 32-bit CRC's. Do
> they have the simple symmetry that allows them to be efficiently computed?
> Incidently, the technique used to implement the 8-bit CRC (see
> http://www.dattalo.com/technical/software/pic/crc_8.asm for an
> implementation, but no description) is completely generic. It takes 19
> cycles. In general, for an N-byte crc, this technique will take about 9*N
> cycles to implement. I'd expect 36 to 40 cycles for a 32-bit CRC. I'd
> expect less if symmetry can be exploited.
>
> Scott
>
> --
> http://www.piclist.com hint: To leave the PICList
> RemoveMEpiclist-unsubscribe-requestTakeThisOuTmitvma.mit.edu
>

> Hi,
>
> Scott Dattalo wrote:
> <snip>
> > I don't know why, but I've been thinking about the CRC-32 too :). I
> was
> > surprised to discover that the 8-bit CRC in Dallas' 1-wire products is
> > more difficult to implement than the 16-bit CRCs. It lacks the
> symmetry of
> > say a CRC-16 computation.  This made me curious about the 32-bit
> CRC's. Do
> > they have the simple symmetry that allows them to be efficiently
> computed?
> > Incidently, the technique used to implement the 8-bit CRC (see
> > http://www.dattalo.com/technical/software/pic/crc_8.asm for an
> > implementation, but no description) is completely generic. It takes 19
> > cycles. In general, for an N-byte crc, this technique will take about
> 9*N
> > cycles to implement. I'd expect 36 to 40 cycles for a 32-bit CRC. I'd
> > expect less if symmetry can be exploited.
> <snip>
>
> :) my initial estimates were a few cycles over that, something around
> 50 cycles, an initial glance the crc32 leans towards more brute force
> than
> elegant symetry, however there are a few 'shortcuts' that can be made
> but if these will
> save cycles in the end I'm still not sure.

> The polynom for crc32 affect many more bits than the crc16, that is in
> relative
> number of bits affected, crc16 affects 3 bits/16 bits ~19%, crc32
> affects 14/32 ~45%.
> I belive that the low percentage of affected bits in the crc16 polynom
> 'helped' finding
> the symetry. Affecting more number of bits will make symetry harder (and
> more inefficent) to
> calculate.