This is absolutely brilliant. I stood by in awe watching the various flavors
flying by, each more quickly than I could come up with a comparable
imrprovement. I don't think I'll be finding the last 5 instructions, either.

Bob Ammerman
RAm Systems

----- Original Message -----
From: "Scott Dattalo" <scott@DATTALO.COM>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Tuesday, May 14, 2002 12:48 PM
Subject: Re: [PIC]: Small Table Driven CRC16 Routine


> On Tue, 14 May 2002, K|bek Tony wrote:
>
> > Hi Scott and Ashley,
> > nice initiative and somewhat challenging :) *gee* probably to much free
time
> > today. Anyway I concluded by reading the original post the same result
as
> > Scott
> > did, there were ways one could skip the table and make some parts
shorter.
> > However
> > one thing was still bugging me, the double 4 bits shifts, I felt that
these
> > should not be
> > needed. Wrapping my head around what exactely was happening ( I never
have
> > dealt with CRC
> > or feedback registers before ) made me realise something, kind of an
'aha'
> > experience,
> > so without further ramblings here goes an *really breifly* commented
version
> > ( for challenge ).
> > It works with the test vector but don't take it for granted that it's
fully
> > operational :)
> > ( although I think so ).
> >
> > It does not save much in regards to Scotts version (unrolled), but I
guess
> > it is atleast
> > a few cycles shorther.
> >
> > Ofcource I'll post an more commented version if there is anyone who
actually
> > is interested,
> >
> > The snippet is really migrane inducing :) and not for the faint hearted.
> >
> > I needed three temps, and used the 'available' in the original snippet.
> > Executes in around 36 instr./byte, no additional stack or tables are
needed
> > (including call/return).
> >
> > But it wouldn't surprise me if Scott,Nikolai or Bob presents an 10 cycle
> > version :) *hint* hint*
>
> :)
>
> Tony, this *is* a brilliant observation and am ashamed I didn't think of
> it :). But, you do realize that it can be optimized...
>
> ; W = CRC Message byte
> ; CRC16 - current 16-bit CRC check sum
> ;
> ; let CRC16 = abcd
> ;     Message Byte = xy
> ;
> ; where abcd, xy are nibble variables
> ;
> ; Upon exit,
> ;
> ;  a = c ^ (i1>>3) ^ i2
> ;  b = d ^ ((i1<<1)&0xf) ^ (i2>>3)
> ;  c = i1 ^ ((i2<<1)&0xf)
> ;  d = i2
> ;
> ; First compute the nibble array indices:
> ;  i1 = a ^ x
> ;  i2 = i1 ^ b ^ y
> ;
> ;
> ; Notation  (I) : (J)  is a byte with I= high nibble, J= low nibble
> ;
>
> CRC_Update
>         xorwf   CRC16_High,w    ; (a^x):(b^y)
>         movwf   Index           ;
>         andlw   0xf0            ; W = (x^x):0
>         swapf   Index,f         ; Index = (b^y):(a^x)
>         xorwf   Index,f         ; Index = (a^b^x^y):(a^x) = i2:i1
>
>
>   ; High byte
>         rlf     Index,W         ;
>         rlf     Index,W         ;
>         andlw   0x1f            ; W = (i1>>3) : (((i1<<1)&0xf) | (i2>>3))
>         xorwf   CRC16_Low,w     ; W = (i1>>3)^c : ((((i1<<1)&0xf) |
>                                 ;     (i2>>3)) ^ d)
>         movwf   CRC16_High      ; low nibble of high byte is done
>
>         movf    Index,w
>         andlw   0xf0            ; W = i2 : 0
>         xorwf   CRC16_High,f    ; High nibble is of high byte is done
>
>   ; now low byte
>         movwf   CRC16_Low       ; Low = i2 : 0
>         addwf   CRC16_Low,f     ; Low = (i2<<1) : 0
>         swapf   Index,W         ; W = i1 : i2
>         xorwf   CRC16_Low,f     ; Low = i1 ^ (i2<<1) : i2
>
>         retlw   0
>
> 17 Instructions, one extra working ram location. I'll let Nikolai, Bob,
> and Dmitry squeeze out the last 5.
>
> Scott
>
> --
> http://www.piclist.com hint: The PICList is archived three different
> ways.  See http://www.piclist.com/#archives for details.
>
>

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.