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

[Andreas Koepke]

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.

Best, Andreas