Friday, May 25, 2012

A smattering of MyForth: CRC16 checksums

I talk a lot of about using MyForth in this blog.  MyForth was written by Charlie Shattuck as a minimalist 8-bit Forth for the 8051.  As an 8-bit Forth it doesn't have a lot of math capabilities (how much math can you really do in just 8 bits?).  However, I've added a few primitives to help manipulate 16 bits (which represents as two 8 bit numbers on the stack, with the MSB topmost).

So, I needed to compute a 16 bit checksum.  The Silab C8051F930 has a built in CRC engine, but I wasn't using that particular MCU.  However, I wanted to maintain some compatibility across Silab chips, so I looked at the C8051F930 datasheet and found a C implementation of the built in CRC checksum.

Here is the basic C function (abridged):
#define POLY 0x1021
unsigned short crc (unsigned short CRC_acc, unsigned char CRC_input)
{
  unsigned char i;
  CRC_acc = CRC_acc ^ (CRC_input << 8);
  for (i = 0; i < 8; i++) {
    if ((CRC_acc & 0x8000) == 0x8000) {
      CRC_acc = (CRC_acc << 1) ^ POLY;
    } else {
      // if not, just shift the CRC value
      CRC_acc = CRC_acc << 1;
    }
  }
  return CRC_acc;
}
And here is my MyForth translation:
$1021 constant POLY 
: crc-xor-poly ( accum16 -- accum16 )
    -if d2* POLY ## dxor ; then d2* ;

: >crc ( accum16 c -- accum16 )
    0 # swap dxor
    8 # 2 #for crc-xor-poly 2 #next ;
I added a couple of helper functions to MyForth to deal with the 16 bit numbers:
: dxor rot xor push xor pop ;
: d2* swap 2* push 2*' pop swap ;
I don't expect you to understand the code (and I will not attempt a detailed explanation here), but I thought it would be interesting to show what minimalist Forth code can look like.  


It may be worth pointing out a few things:


That the stack is 8 bit wide and 16 bit numbers are pushed as two 8 bit values (MSB topmost).  


The "-if" is a quick way to check if the 7th bit is set on the MSB (hence negative). 
"If" condition values are not consumed off of the stack, so that allows me to test and use the top value without a "dup".


The weird looking "for" loop (" 2 #for") indicates that I am using Register 2 to hold the loop value. Yes, I have to do book keeping on registers (remember the days of old?), but it isn't bad as it seems.  Deeply nested loops are frowned upon in Forth.

There is certainly a brevity and density to the MyForth source. ;-)

No comments: