Generation of CCITT 16 bit CRC checksums
----------------------------------------

The BASIC code below implements a 16 bit CRC generator in R83 style BASIC.
It is assumed that the platform has no 'bitwise' functions/operators. This
means that the bit manipulations will be rather cumbersome and VERY slow.

The Basic code:

SUBROUTINE CHECKSUM(STRING, CRC)
* ***************************************************** *
* ***************************************************** *
* Function to generate a CCITT 16 bit CRC for a string. *
* This checksum is compatible with the intrinsic        *
* CHECKSUM() function supplied with uniVerse.           *
* Note: This function is VERY slow!        (dmm 1/96)   *
*                                                       *
* Parameters:  STRING - String to derive checksum for   *
*              CRC    - Returned checksum for 'STRING'  *
* ***************************************************** *
* ***************************************************** *
*
DIM TBL(8)  ;* Use a 'table' to avoid use of 'PWR()' function!  
*
TBL(1) = 256  ; TBL(2) = 512  ; TBL(3) = 1024  ; TBL(4) = 2048
TBL(5) = 4096 ; TBL(6) = 8192 ; TBL(7) = 16384 ; TBL(8) = 32768
*
CRC  = 0
LGTH = LEN(STRING)
FOR I = 1 TO LGTH
   CVAL = SEQ(STRING[I, 1]) * 256      ;* Char value shifted left 8 bits!
   TEMP = MOD(CRC, 256)                ;* isolate lower 8 bits of accum.
   FOR J = 1 TO 8                      ;* Now XOR 'Z' and 'CRC' into 'TEMP'
      P = TBL(J)                       ;* Derive 'PWR(2, J+7)' from table
      IF MOD(INT(CRC / P), 2) # MOD(INT(CVAL / P), 2) THEN TEMP = TEMP + P
   NEXT J
   CRC = TEMP                          ;* Replace accum. with XOR'd result!
   FOR J = 1 TO 8
      IF MOD(INT(CRC / 32768), 2) THEN ;* MSB bit set?
         CRC = CRC - 32768             ;* Remove the MSB from accumulator
         CRC = CRC + CRC               ;* then Shift left 1 bit
         * XOR our crc accumulator with the CCITT poly 0x01021
         IF MOD(CRC, 2) THEN
            CRC = CRC - 1
         END ELSE CRC = CRC + 1
         IF MOD(INT(CRC / 32), 2)   THEN
            CRC = CRC - 32
         END ELSE CRC = CRC + 32
         IF MOD(INT(CRC / 4096), 2) THEN
            CRC = CRC - 4096
         END ELSE CRC = CRC + 4096
      END ELSE CRC = CRC + CRC         ;* Shift left 1 bit
   NEXT J
NEXT I
RETURN
*
END

The above code demonstrates that CRC values may be generated using a
BASIC program. However, it takes only a minute or two of testing to see
that this method is far too slow for practical use. Two Assembler versions
of this function are presented below. The first is small, but of rather
naive implementation. The second is much faster, but longer.

*WARNING* *WARNING* *WARNING* *WARNING* *WARNING* *WARNING* *WARNING*

Use of user written Assembler modes on your system may invalidate any
support from Pick Systems. I supply this code 'as is', but make no
warranty as to it being correct. Use at your own risk.

The following code is intended to generate a 16 bit checksum value for
a passed string. It was written on a R83 3.1 system.

The Assembler code:

          FRAME 511
*CHECKSUM
*15 JAN 1996
*DMM
*
* 0 = CHKSUM - Generate uniVerse compatible 'CRC-16' Value for passed
*              string. Syntax:  CRC = OCONV(string, 'Uxxxx')
*              Element usage:  R14, R15, TS, TSEND, D0
************************************************************************
*
          EP !CHKSUM              * generate CCITT 16 bit checksum
*
!CHKSUM   EQU *
          MOV TSBEG,TS            * use 'TS' to traverse passed string
          SRA R15,H0              * point 'R15' to low byte of 'T0'
          SRA R14,H1              * point 'R14' to high byte of 'T0'
          ZERO T0                 * clear our CRC Accumulator
!LOOP1    INC TS                  * point 'TS' to next character
          BCE TS,SM,!ENDSTR       * exit if past end of string!
          XOR R14,TS              * XOR char into high byte of 'T0'
          MOV 8,H2                * number of times to do inner loop!
!LOOP2    BDLZ H2,!LOOP1          * dec counter, exit loop if < 0
          BBS B15,!DOXOR          * jump if high bit set in accumulator
          INC T0,T0               * else shift accumulator left 1 bit!
          B !LOOP2                * and then repeat inner loop
!DOXOR    INC T0,T0               * shift accumulator left 1 bit!
          XOR R15,X'21'           * XOR accumulator with CCITT poly
          XOR R14,X'10'           * value 0x1021
          B !LOOP2                * and then repeat inner loop
!ENDSTR   MOV TSBEG,TS            * reset 'TS' to start of buffer
          ZERO T1                 * clear high tally of 'D0' so we
          MBD D0,TS               * return +ve 16 bit CRC value!
          MCI SM,TS               * terminate CRC value with 'SM'
          DEC TS                  * back up 'TS' from terminator
          MOV TS,TSEND            * and set 'TSEND = TS' (do we need this?)
          ENT CONVEXIT            * all done!
*
*EOI

When assembled, this code will produce the following R83 object. This
may be edited into an item for loading, if the Assembler is unavailable.

\0001 7FF001FF
\0000 CCCCE900009AD84F0000BEDC009A0C1D00008EC3BA0F00BF00019A27
\0018 00019A271B00008EC3BA0E00BF00019A161B000031C0A30E009AD84F
\0030 009AD84F00009A491E0000C43E680126803DFF746CC5367001268A05
\0048 01268A05300481CD00408EDBC6060D00089AD84F0000802E0D00017C
\0060 0D00017CCCF6060E008075148B0E0E0086E9A10E0086E001C886E0A3
\0078 C886E0A30E00EBD99AD84F00008B0E0E0086E9A10E0086E001C886E0
\0090 01C886E0A30E00C43E78012680352181CD0080C43E70012680351081
\00A8 80351081CD0040EBA89AD84F0000BEDC009A0C1D000031C0A30C00A1
\00C0 A30C00A10C00A30C00A10E00A30E00BF68019A231B0000B808009A03
\00D8 08009A03150000BF78019A011B00009A491E0000C43E680126C605FF
\00F0 26C605FF81CD00209AF91D00008B166C01A16801F6C280750383E80B
\0108 0383E80B86E0A3E2008916E400A16E01A3E600B85A10EA09150000CC
\0120 150000

Note: the '\' characters are actually sub-value marks!

load using the MLOAD verb. Assuming this object is edited into a file
called 'PATCHFILE', item 'CHECKSUM', this would look like:

>MLOAD PATCHFILE CHECKSUM

[216] 'CHECKSUM' loaded;  frame = 511  size = 122  cksum = 72F9

If any other result is shown, do NOT attempt to use this function.

Assuming all worked ok, you would use this user-exit from Basic via
the conversion interface. For example:

   CRC = OCONV(SVAL, "U01FF")  ;* Return 16 bit CRC for string in 'SVAL'

While the above code is ok, there is a faster method that involves a
table lookup of precomputed intermediate values. This code is somewhat
longer, but runs much faster. I have included this second version, but
without the object code.

The Assembler code:

          FRAME 511
*CRC16
*18 JAN 1996
*DMM
*
* 0 = CRC16 - Fast CCITT 16 bit CRC generation for passed string.
*             From: Joe Campbell, 'C Programmers Guide to Serial
*             Communications' - Chapter 19. This CRC is compatible
*             with the uniVerse 'CHECKSUM()' function.
*************************************************************************
*
          EP !CRC16               * Fast CCITT 16 bit CRC generator 
*
CHARH0    DEFC R0,H0              * Redefine 'H0' as character
CHARH1    DEFC R0,H1              * Redefine 'H1' as character
CHARH2    DEFC R0,H2              * Redefine 'H2' as character
*
* Define lookup table for CCITT 16 bit 'classic hardware model' CRC
*
CRCTBL    EQU *
          TEXT X'00001021'
          TEXT X'20423063'
          TEXT X'408450A5'
          TEXT X'60C670E7'
          TEXT X'81089129'
          TEXT X'A14AB16B'
          TEXT X'C18CD1AD'
          TEXT X'E1CEF1EF'
          TEXT X'12310210'
          TEXT X'32732252'
          TEXT X'52B54294'
          TEXT X'72F762D6'
          TEXT X'93398318'
          TEXT X'B37BA35A'
          TEXT X'D3BDC39C'
          TEXT X'F3FFE3DE'
          TEXT X'24623443'
          TEXT X'04201401'
          TEXT X'64E674C7'
          TEXT X'44A45485'
          TEXT X'A56AB54B'
          TEXT X'85289509'
          TEXT X'E5EEF5CF'
          TEXT X'C5ACD58D'
          TEXT X'36532672'
          TEXT X'16110630'
          TEXT X'76D766F6'
          TEXT X'569546B4'
          TEXT X'B75BA77A'
          TEXT X'97198738'
          TEXT X'F7DFE7FE'
          TEXT X'D79DC7BC'
          TEXT X'48C458E5'
          TEXT X'688678A7'
          TEXT X'08401861'
          TEXT X'28023823'
          TEXT X'C9CCD9ED'
          TEXT X'E98EF9AF'
          TEXT X'89489969'
          TEXT X'A90AB92B'
          TEXT X'5AF54AD4'
          TEXT X'7AB76A96'
          TEXT X'1A710A50'
          TEXT X'3A332A12'
          TEXT X'DBFDCBDC'
          TEXT X'FBBFEB9E'
          TEXT X'9B798B58'
          TEXT X'BB3BAB1A'
          TEXT X'6CA67C87'
          TEXT X'4CE45CC5'
          TEXT X'2C223C03'
          TEXT X'0C601C41'
          TEXT X'EDAEFD8F'
          TEXT X'CDECDDCD'
          TEXT X'AD2ABD0B'
          TEXT X'8D689D49'
          TEXT X'7E976EB6'
          TEXT X'5ED54EF4'
          TEXT X'3E132E32'
          TEXT X'1E510E70'
          TEXT X'FF9FEFBE'
          TEXT X'DFDDCFFC'
          TEXT X'BF1BAF3A'
          TEXT X'9F598F78'
          TEXT X'918881A9'
          TEXT X'B1CAA1EB'
          TEXT X'D10CC12D'
          TEXT X'F14EE16F'
          TEXT X'108000A1'
          TEXT X'30C220E3'
          TEXT X'50044025'
          TEXT X'70466067'
          TEXT X'83B99398'
          TEXT X'A3FBB3DA'
          TEXT X'C33DD31C'
          TEXT X'E37FF35E'
          TEXT X'02B11290'
          TEXT X'22F332D2'
          TEXT X'42355214'
          TEXT X'62777256'
          TEXT X'B5EAA5CB'
          TEXT X'95A88589'
          TEXT X'F56EE54F'
          TEXT X'D52CC50D'
          TEXT X'34E224C3'
          TEXT X'14A00481'
          TEXT X'74666447'
          TEXT X'54244405'
          TEXT X'A7DBB7FA'
          TEXT X'879997B8'
          TEXT X'E75FF77E'
          TEXT X'C71DD73C'
          TEXT X'26D336F2'
          TEXT X'069116B0'
          TEXT X'66577676'
          TEXT X'46155634'
          TEXT X'D94CC96D'
          TEXT X'F90EE92F'
          TEXT X'99C889E9'
          TEXT X'B98AA9AB'
          TEXT X'58444865'
          TEXT X'78066827'
          TEXT X'18C008E1'
          TEXT X'388228A3'
          TEXT X'CB7DDB5C'
          TEXT X'EB3FFB1E'
          TEXT X'8BF99BD8'
          TEXT X'ABBBBB9A'
          TEXT X'4A755A54'
          TEXT X'6A377A16'
          TEXT X'0AF11AD0'
          TEXT X'2AB33A92'
          TEXT X'FD2EED0F'
          TEXT X'DD6CCD4D'
          TEXT X'BDAAAD8B'
          TEXT X'9DE88DC9'
          TEXT X'7C266C07'
          TEXT X'5C644C45'
          TEXT X'3CA22C83'
          TEXT X'1CE00CC1'
          TEXT X'EF1FFF3E'
          TEXT X'CF5DDF7C'
          TEXT X'AF9BBFBA'
          TEXT X'8FD99FF8'
          TEXT X'6E177E36'
          TEXT X'4E555E74'
          TEXT X'2E933EB2'
          TEXT X'0ED11EF0'
*
* ************************************************************* *
* ************************************************************* *
* CCITT 16 bit CRC generation. Used as a Basic conversion code. *
* For example: CRC = OCONV(STRING, 'U01FF')                     *
*                                                               *
* Element usage: D0, TS, TSEND, R14, R15                        *
*                                                               *
* 'T0' used as the CRC accumulator, and 'T1' used as a scratch  *
* area for determining the index value into the table. 'TS' is  *
* used to traverse the passed string.                           *
* ************************************************************* *
* ************************************************************* *
*
!CRC16    EQU *
          MOV TSBEG,TS            * Use 'TS' to traverse passed str.
          SRA R15,H1              * Point 'R15' to high byte in 'T0'
          ZERO D0                 * Clear our CRC and scratch tally
!LOOP     INC TS                  * Point 'TS' to next character
          BCE TS,SM,!EXIT         * Jump if passed end-of-string
          SRA R14,CRCTBL          * Point 'R14' at lookup table!
*
* Now we want to XOR the high byte of the accumulator (in 'T0')
* with the current data byte (character pointed to by 'TS')
*
          XOR R15,TS              * XOR high byte of 'T0' with data
          MCC R15,CHARH2          * load result into low byte of 'T1'
          INC T1,T1               * Shift left to effect 'H1 * 2'
*
* The resultant value now in 'T1' is used as an index into the lookup table
*
          INC R14,T1              * Position 'R14' within the table!
*
* Now XOR the CRC value from the table with low byte of the accumulator.
* Do this by moving the low byte of 'T0' into the high byte, then XOR'ing
* this with the high byte of the CRC table value. Replace low byte of 'T0'
* with low byte of CRC table value.
*
          MCC CHARH0,CHARH1       * shift low byte to high in 'T0'
          XOR R15,R14             * XOR high byte of 'T0' and CRC
          MIC R14,CHARH0          * low byte of CRC into low 'T0'
          ZERO T1                 * Clear scratch tally 'T1'
          B !LOOP                 * and repeat loop for next char!
*
* Convert CRC value into ASCII form, and place in 'TS' buffer for return.
*
!EXIT     MOV TSBEG,TS            * Reset the 'TS' buffer pointer
          MBD D0,TS               * return a +ve 16 bit CRC value!
          MCI SM,TS               * terminate crc value with 'SM'
          DEC TS                  * back up 'TS' from terminator
          MOV TS,TSEND            * set 'TSEND = TS'
          ENT CONVEXIT            * all done!
*
*EOI



