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 < for HTML. )

{ file polydiv.pas, 85/9/15/tfr (from 9/13)}
{ simulation of CRC-type operations }
{ Copyright (c) 1985, T.F. Ritter; All Rights Reserved }

{ 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 }


PROCEDURE showad( pb: small );
   { 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' );
   showad( deg );
   FOR i := 1 TO dbits DO
      BEGIN
      pdiv;
      showad( deg );
      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' );
   showad( deg );
   FOR i := 1 TO dbits DO
      BEGIN
      crc;
      showad( deg );
      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 }

Last updated: 1996-04-30