# The Great CRC Mystery: LISTING ONE

## Polynomial Division Binary Trace

(Reconstructed by hand from 10-year-old listings. This is Turbo Pascal 3.01A or older, circa 1985, modified slightly to work under Borland Pascal 7.0, 1996-04-30/tfr. Note that the "less than" character is modified to &lt; for HTML. )

```
{ file polydiv.pas, 85/9/15/tfr (from 9/13)}
{ simulation of CRC-type operations }

{ generates a binary trace through the polynmial division
{ and crc algorithms to illustrate equivalent results
{ (this assumes we init the remainder reg. to 0) }

{\$R+}  { Range Checks ON }

PROGRAM polydiv;

{ first, output through MSDOS, and define binary display }

(* unnecessary in 7.0
TYPE
registers = RECORD
ax,bx,cx,dx,bp,si,di,ds,es,flags: INTEGER;
END;

PROCEDURE bdosch( ch: CHAR );
{ output through MSDOS; allow Ctrl-P toggle }
VAR r: registers;
BEGIN
r.ax := \$0200;
r.dx := ORD(ch);
MsDos(r);
END;
*)

TYPE
small = 0..15;

PROCEDURE showbin( x: INTEGER; from, too: small );
{ display subset of integer as binary bits }
{ from and too are place values (15 - 0) left to right }
VAR i: small;
BEGIN
WRITE( ' ' );
FOR i := 15 DOWNTO 0 DO
BEGIN
IF i IN [too..from] THEN
IF (x < 0) THEN
WRITE( ' 1')
ELSE
WRITE( ' 0');
x := x Shl 1;
END;
WRITE( ' ' );
END; {showbin}

VAR  { globals }
a: INTEGER;  { the remainder value register; right-aligned }
p: INTEGER;  { the polynomial; right-aligned }
d: INTEGER;  { the data; left-aligned }
deg: small;  { the degree of the polynomial }
dbits: BYTE; { the number of data bits to process }

{ show current remainder and next data bit (only) }
{ the data bit on the last step is meaningless }
BEGIN
WRITELN;
showbin( a, (pb - 1), 0 );
showbin( d, 15, 15 );
END;

{ start bit-level utilities for crc-type algorithms }

TYPE
abit = 0..1;

FUNCTION dn: abit;
{ value of next data bit }
{ since d is an INTEGER, "d Shl 1" = "d + d" }
{ use "d := d + d" in other Pascals }
BEGIN
IF (d < 0) THEN
dn := 1
ELSE
dn := 0;
d := d Shl 1;
END;

FUNCTION an( n: small ): BOOLEAN;
{ value of particular remainder bit }
{ for other Pascals, use a loop and do "x Shl 1" n times }
{ "x Shl 1" must itself be "x + x"; init x to 1 first }
BEGIN
an := ((a AND (1 Shl n)) <> 0);
END;

{ start crc-type algorithms }

PROCEDURE pdiv;
{ mod-2 polynomial division (for remainder only) }
BEGIN
IF an(deg - 1) THEN
a := (a Shl 1) XOR p XOR dn
ELSE
a := (a Shl 1) XOR dn;
END; {pdiv}

PROCEDURE crc;
{ mod-2 remainder without extra zeros }
BEGIN
IF (an(deg - 1) XOR (dn <> 0)) THEN
a := (a Shl 1) XOR p
ELSE
a := (a Shl 1);
END; {crc}

{ start trace displays; show one or the other }

PROCEDURE showpdiv( dbits: BYTE );
VAR i: BYTE;
BEGIN
WRITE( ^M^J'POLYNOMIAL DIVIDE;  Polynomial = ' );
showbin( p, deg, 0 );
WRITE( ^M^J'Remainder   Data' );
FOR i := 1 TO dbits DO
BEGIN
pdiv;
END;
WRITELN;
END;

PROCEDURE showcrc( dbits: BYTE );
VAR i: BYTE;
BEGIN
WRITE( ^M^J'CRC OPERATION;  Polynomial = ' );
showbin( p, deg, 0 );
WRITE( ^M^J'Remainder   Data' );
FOR i := 1 TO dbits DO
BEGIN
crc;
END;
WRITELN;
END;

PROCEDURE init( i: BYTE );
{ select one of the initializations }

PROCEDURE init1;
{ simulating long division example }
{ from Peterson & Brown, Proc. of the IRE, Jan. 1961, p. 232 }
BEGIN
p := \$0005;
deg := 2;
WORD(d) := \$e800;  (* WORD needed for 7.0 *)
dbits := 6;
END; {init1}

PROCEDURE init2;
{ simulating generation of check code }
{ Peterson & Brown, 1961, p. 229 }
{ data are shifted left, so are in reversed order from article }
BEGIN
p := \$0035;  { the classical example polynomial }
deg := 5;
WORD(d) := \$8940;  (* WORD needed for 7.0 *)
dbits := 10;
END; {init2}

PROCEDURE init3;
{ simulating published tables }
{ K. Rallapalli, EDN, Sept. 5 1978, pp. 119 - 123 }
BEGIN
p := \$0035;  { here it is again }
deg := 5;
WORD(d) := \$d1b0;  (* WORD needed for 7.0 *)
dbits := 12;
END; {init3}

BEGIN {init}
CASE i OF
1: init1;
2: init2;
3: init3;
END; {case}
a := 0;
END; {init}

{ start of the ultimate command code }

VAR
i: BYTE;

BEGIN {main}

(* not available in 7.0
ConOutPtr := Ofs( bdosch );  {allow Ctrl-P printer toggle}
*)

{ for three different initializations . . . }
FOR i := 1 TO 3 DO
{ show binary trace of pdiv and crc algorithms }
BEGIN
init( i );
showpdiv( dbits + deg );
init( i );
showcrc( dbits );
END;

END. {main}

{ end file polydiv }

```

Terry Ritter, his current address, and his top page.

Last updated: 1996-04-30