CRC for Program Validation
Leonard Morgenstern
Forth Day, 1998

During program development it is usual to check each new Forth word by means of a test suite, that is, a set of words designed for the purpose. The word is rejected if its output is not equal to the expected value. Formerly, it was not usual to check all words everytime they are used in a program, but today, this is no longer adequate. One cannot assure the reliablilty of a program segment when it is compiled in a different environment.

In most cases the output of a test suite is a single quantity, or only a few, which can be checked by simple matching. However, some tests output a whole array, for example a sorting algorithm. CRC provides an efficient method for checking these.

Cyclic Redundancy Code (CRC)

CRC is a well-known method for error detection in data communications. Both sender and recipient use the CRC algorithm on each byte sent or received to update a quantity called the checksum.. When a block of data is complete, the sender transmits the sum, and the recipient compares it with his own sum. If the two don't match, the block is re-transmitted. The CRC checksum is not actually a sum, but is far more sensitive to errors than a simple bInary sum. In particular, the transposition of two bytes can be detected.

The value to which the CRC is initialized varies with the protocol. Here it is reset to zero. Sixteen-bit or 32-bit CRC methods exist, but using the latter for checking would limit one to 32-bit operations.

In the method presented here, it is required that the output of the test suite be a stream of bytes which can either be pushed onto the stack or stored in an array of characters (i. e. a string). Then the word >XMODEMS will compute CRC for elements on the stack, and >XMODEM$ for elements in the array. The programmer includes the correct value in the source code. Then, each time the segment is assembled, the CRC is re-computed and the result compared with the expected value.

The word MATCH-CRC illustrates one way to handle failure to check: abort & stop compilation.

Analysis of program

The XMODEM CRC protocol, is copied from the Forth Scientific Library Algorithm #44, by Gordon Charlton, omitting steps needed for communications only.

1. Define REV8 ( ch1 -- ch2)
Perform bit reversal on a CHAR. Uses lookup table for speed.
2. Define >< ( ch1 -- ch2)
Swap the 8 least significant bits with the 8 next significant bits. Set other bits to zero.
3. Define REV16 ( n -- n')
Reverse the order of the 16 least significant bits of the word n and set other bits to zero.
4. Define CRC ( crc ch -- crc')
Update a crc using the character ch. This is a slow method.
5. Redefine CRC ( crc ch -- crc') to use a lookup table for speed.
The table contains values that are retrieved and XOR'd into the crc.
6. >XMODEM$ ( addr n -- crc) Redefined from Charlton's similar >XMODEM
Compute the crc of a string of chars in RAM.
7. >XMODEMS ( n -- crc)
Compute the crc of the top n stack items. Only the 8 low-order bits are used.

The CRC algorithm

.( 16 Bit Cyclic Redundancy Checksums. Version FSL1.0  29th October 1994) CR 
.(             Gordon Charlton - CR
\ Portions of Forth Scientific Library Algorithm #44 used
\ (c) Copyright 1994 Gordon R Charlton.  Permission is
\ granted by the author to use this software for any 
\ application provided this copyright notice is preserved.
\ ANS Forth Program.
\ Requiring ?DO \ from the Core Extensions word set.
CREATE revtable  100 CHARS ALLOT
\ A lookup table for bit-reversed bytes.
MARKER dispose
: rev8 ( ch--ch)  0 SWAP
                  8 0 DO  DUP 1 AND 
                          ROT 2* OR 
                          SWAP 2/ 
                  DROP ;\
\ Brute force bit reversal of a byte.
: filltable (  )  100 0 DO  I rev8  
                            I CHARS revtable + C!
                        LOOP ; 
filltable  dispose
\ Initialise the look-up table and clear out the code required 
\ to do so.

: rev8 ( ch--ch)  CHARS revtable + C@ ;
\ Reverse the order bits in a byte by table-lookup for speed.
\ : >< ( n--n)  DUP   FF AND  8 LSHIFT
\             SWAP FF00 AND  8 RSHIFT  OR ;
\ For F-PC
' flip alias ><
\ Swap the least significant 8 bits of a stack element with 
\ the next leas significant 8 bits. More significant bits are 
\ set to zero.
\ >< is a traditional name for this function, which is present
\ as a primitive on many 16 bit systems.

 : rev16 ( n--n)  DUP   FF AND  rev8  8 LSHIFT
                 SWAP FF00 AND  8 RSHIFT  rev8  OR ;
\ Reverse the order of bits of the 16 least significant bits of
\ a stack elemen More significant bits are set to zero.
CREATE crctable  100 CELLS ALLOT
\ A lookup table for crc values for various byte length bit
\ patterns.
MARKER dispose
1021 CONSTANT crc-polynomial ( CCITT or: 8005 for CRC-16)
\ The CCITT standard crc-polynomial is presumed. Others,
\ such as CRC-16, whic is used in IBMs BISYNCH, may be
\ editted in here)
: crc ( n ch--n)  >< XOR 
                  8 0 DO  DUP 8000 AND  
                          IF  2* FFFF AND  crc-polynomial XOR
                        ELSE  2* 
                    LOOP ; 
\ n is a CRC. Executing crc computes a new value, to
\ include the byte ch one bit at  time. This is a slow method,
\ used only to initialise the lookup table.

\ FFFF AND is, of course, redundant on a 16 bit system, but
\ as this word is only used during compilation there is no
\ benefit to be gained from removin it from the source.

: filltable  ( ) 100 0 DO  0 I crc  I XOR  
                           I CELLS crctable + ! 
                     LOOP ;
filltable  dispose
\ Initialise the look-up table and clear out the code required
\ to do so.

: crc ( n ch--n)  >< XOR >< 
                  DUP FF AND CELLS  crctable + @ 
                  XOR ;
\ n is a CRC. crc computes a new value, to include the byte 
\ ch.

\ Charlton's algorithm for CRC, abridged ends here

Using CRC to check compilation

\ Adapting Charlton's algorithm for CRC to program
\ checking
\ The XMODEM convention is selected. It uses a starting 
\ value of zero
\    (all bits low).

\ >xmodem$ analyzes a counted string in RAM
\ >xmodemS analyzes the low order bytes of items on the 
\ stack.

: >xmodem$ ( addr n--n)  0 ROT ROT
                        OVER + 1-
                        ?DO  I C@ crc  1 CHARS NEGATE +LOOP ;
: >xmodemS ( n1 -- n2 )
    0 SWAP 0 ?DO
        SWAP 0FF AND    \ Low order byte only!
        CRC LOOP ;BASE !

\ A brute force way to handle failure to check: abort & stop
\ compilation
: match-crc ( n1 n2 -- )
    <> abort" Does not compile correctly" ;

\ A small test suite
.( CRC on string )

$1 >XMODEM$         \ perform CRC test on string & 
                    \ leave result on stack
-12344              \ expected value
match-crc           \ act on mismatch
.( compiles correctly) CR

.( CRC on stack )
    11 0 DO [CHAR] A I + LOOP ;

-12344              \ expected value
\ 1+                \ force it to be wrong
.( compiles correctly)