bb@lanl-a.UUCP (11/18/83)
==============================================================================
The following are translations of byte-wise CRC-16 calculation
algorithms given the the June 83 issue of IEEE Micro. Included
are an on-the-fly 8086 assembler version, a C table driven version
and a C program to produce the table as well as the table itself.
I have tested these against each other and am fairly certain they
work. If they don't, I apologize now -- please send me your fixes.
;===================================================================
;
; CRC -- calculates CRC checksum on string of bytes
; on the stack -- length of string, string offset
; returns -- 16 bit CRC-16 value in AX, BX.
; other data regs. garbled NOTE IF CI CHANGES C COMPILER
;
; Programmer: Bryan Bingham 8 Nov 1983
; System: CompuPro 8086/8085
;
; This code is intended to be called by a C program compiled with the CI-86
; compiler, the format of the directives is suggested by CI cvtobj document.
; It has no seperate data segment, it uses just registers. The algorithm
; comes from "Byte-wise CRC Calculations" by Aram Perez, IEEE Micro June
; 1983 pp.40-50 and uses several tricks based on the 8080/8086 design.
; I suggest getting that paper if you want to understand what is happening
; because I did not try to fully document the thing here, and the comments
; here only make sense after you read the paper.
;
; Called from C as crc(buf, strlen(buf));
;===================================================================
;
;
cseg
crc: ; global entry point
;
; 1st get params, initialize regs
;
push bp ; save frame pointer
mov bp,sp ; get ready to read args
mov cx,6[bp] ; char count
mov si,4[bp] ; pointer to string of bytes
xor ax,ax ; 0 out accumulator, crc
xor bx,bx ;
xor dx,dx ; used for inter. processing
;
; Main loop, get char from string, do crc calculation
;
cycle equ $
lods al
xor al,bl ; xor low order byte of current crc
mov dl,al ; save for later
add al,al ; set cf, pf for later
pushf ; save x8 and xx7 (cf and pf)
xor al,dl ; a = x.xor.(x.shl.1) r14 thru r7
mov dl,al ; save again
popf ; restore flags
mov al,0 ; xx7 <- 0 xx8 <- xx7
jp f1 ;
mov al, 011b ; if xx7 then make xx8 = 1 too
;
f1: jnb f2
xor al, 010b ; if x8 then complement xx8
f2: mov dh,al
shr al,1 ; shift al right 1 bit
push cx ; save char count
mov cx,6 ; shift count
shl dx,cl
pop cx ; restore cx
or al,dl ; get last bits into proper place
xor al,bh ; xor with high order CRC bits
mov bl,al ; save new CRC
mov bh,dh
loop cycle ; end of loop jmp back if cx <> 0
;
mov ax,bx ; put answer in ax
pop bp ; restore frame pointer
ret
;
;
eseg
; This is for relocation -- can be left out if not using CI-86 C compiler
dw crc
db 0c1h,'crc',0
dw 0,0
end
;=========================================================================
/*
CRCC -- C subroutine to calcute CRC-16 of string of byte using
byte-wise method described in June 1983 IEEE Micro. Uses crctab
created by program CRCT.C I suggest reading the article if you
really want to know how it works.
Programmer: Bryan Bingham 9 Nov 1983
Input: a null terminated string
Output: The unsigned CRC value
*/
#include "crctab.h" /* created by CRCT, a table of 256 ints */
unsigned int crcc(line)
char *line ;
{
unsigned int
crc , /* result stored here */
x ; /* index to table crctab */
char
*p ; /* into line */
crc = 0 ;
while (*p = *line++) {
x = *p ^ (crc & 0xff) ; /* make x from byte and low 8 crc */
crc >>= 8 ; /* shift crc 8 to right */
crc ^= crctab[x] ; /* x guaranteed 0 <= x <= 255 */
}
return (crc) ;
}
/*
CRCT -- program to tabulate values necessary for CRC-16 byte-wise
calculations.
Programmer: Bryan Bingham 9 Nov 1983
Will output a table, suitable for editing, of 256 hex values to
use with table driven CRC algorithm -- see crc.c and Jun 1983
IEEE Micro magazine for how table is used.
Editing required includes filling in the spaces between the 0x
and the hex numbers generated. Also make the whole thing a
declaration for an integer array crctab[256].
*/
#include <stdio.h>
main()
{
int
x, x1, x2, x3, x4, x5, x6, x7, x8, v, i
;
v = i = 0 ;
printf("\n\t") ;
for (x8 = 0 ; x8 < 2 ; x8++)
for (x7 = 0 ; x7 < 2 ; x7++)
for(x6 = 0 ; x6 < 2 ; x6++)
for (x5 = 0 ; x5 < 2 ; x5++)
for (x4 = 0 ; x4 < 2 ; x4++)
for (x3 = 0 ; x3 < 2 ; x3++)
for(x2 = 0 ; x2 < 2 ; x2++)
for (x1 = 0 ; x1 < 2 ; x1++) {
x = x8^x7^x6^x5^x4^x3^x2^x1 ;
v = x << 15 ;
/* vertical bar not : */ v |= (x7^x6^x5^x4^x3^x2^x1) << 14 ;
v |= (x8^x7) << 13 ;
v |= (x7^x6) << 12 ;
v |= (x6^x5) << 11 ;
v |= (x5^x4) << 10 ;
v |= (x4^x3) << 09 ;
v |= (x3^x2) << 08 ;
v |= (x2^x1) << 07 ;
v |= x1 << 6 ;
v |= x ;
if ( !(i++%8) ) {
printf("\n\t") ;
i = 1 ;
}
printf("0x%4x, ", v) ;
v = 0 ;
}
} /* end of program! */
/* CRC-16 values for CRC-16 table driven byte-wise algorithm. See CRCC.C */
/* Created with crct.c and then hand edited to make legal C code. */
/* Programmer: Bryan Bingham 8 Nov 1983 LANL */
unsigned int crctab[256] = {
0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040
} ;
Bryan Bingham {ucbvax!lbl-csam,purdue,cmcl2}!lanl-a!bb @ LANL