[Tinyos-devel] Default CRC implementation in tinyos-2

[David Gay]

On 4/26/07, Andreas Koepke <koepke at tkn.tu-berlin.de> wrote:
>
>
> David Gay wrote:
> > On 4/25/07, Andreas Koepke <koepke at tkn.tu-berlin.de> wrote:
> >
> >> The current default CRC implementation is based on a loop and single bit
> >> shifts. CRCs are usually taught that way, but faster implementations are
> >> available. I propose to change the default crc implementation to:
> >>
> >> uint16_t crcByte(uint16_t crc, uint8_t b) {
> >>   crc = (uint8_t)(crc >> 8) | (crc << 8);
> >>   crc ^= b;
> >>   crc ^= (uint8_t)(crc & 0xff) >> 4;
> >>   crc ^= crc << 12;
> >>   crc ^= (crc & 0xff) << 5;
> >>   return crc;
> >> }
> >>
> >> This implementation was pointed out by Paul Curtis on the MSP430 mailing
> >> list. (Does anyone know the first author of this code?)
> >>
> >> Advantages:
> >>  - same poly
> >>  - fast (about 10 times on an MSP430)
> >>  - compact (in contrast to the table
> >>    based implementation by Ross Williams used in tinyos-1.x)
> >>
> >> Disadvantage:
> >>  - you can't use it to teach CRCs ;-)
> >>  - takes two times longer than the table based implementation
> >
> >
> > Good points. The intent of the system code is that is supposed to be
> > the reference implementation, with each platform and/or
> > microcontroller providing a more optimised version. This didn't happen
> > for the msp430 though...
> >
> > David Gay
>
> The proposed implementation should be a fast and compact default on any
> platform, so it may become the reference. I can not imagine a processor
> where it is slower than the for-loop.

Yes, I realise that. I was thinking more about the clarity issue
(better to be clear in the ref implementation). But that could be
addressed by leaving the original code as a comment.

David Gay