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.
The CRC algorithm
CR
.( 16 Bit Cyclic Redundancy Checksums. Version FSL1.0 29th October 1994) CR
.( Gordon Charlton - gordon@charlton.demon.co.uk) CR
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.
BASE @ HEX
\
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/
LOOP
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*
THEN
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
CR .( TESTING COMPILATION OF CRC ) CR
.( CRC on string )
: $1 S" ABCDEFGHIJK" ;
$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 )
: SET-STACK
11 0 DO [CHAR] A I + LOOP ;
SET-STACK
11 >XMODEMS
-12344 \ expected value
\ 1+ \ force it to be wrong
match-crc
.( compiles correctly)