The Great CRC Mystery: LISTING TWO

Various CRC-CCITT Implementations

(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 crctime.pas, 85/9/15/tfr (from 7/13, 6/27-26,
                    showtime.pas 3/23, 1/4, 84/12/25
                    and showkeys 12/12-11, 11/17
                    and strnkey.pas, 11/17 }
{ compute crc execution times }

{ Copyright (c) 1984, 1985, T.F. Ritter; All Rights Reserved }


{ display a number of different CRC-CCITT implementations }
{ verify identical operation }
{ collect and display time statistics }

(* under 7.0 on a P90 results should be displayed in usec! *)


PROGRAM showtime;


{$R-}  { Range Checks OFF }
{$C-}  { Ctrl-C Checking OFF }

USES
   Dos;  { defines Registers type and MsDos routine in 7.0 }


PROCEDURE ownership;
   BEGIN
   WRITE(
^M^J, 'CRCTIME, 85/9/15',
^M^J, 'Execution times for various CRC implementations.',
^M^J, 'Copyright (c) 1985, T.F. Ritter;  All Rights Reserved.',
^M^J     );
   END;


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


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


{ start of time operations }

TYPE
   timearty = ARRAY[0..3] of INTEGER; {originally had yr, dy}


PROCEDURE readhms( VAR dt: timearty );
   { Hi(dt[2]) = hrs (0 - 23), Lo(dt[2]) = mins (0 - 59) }
   { Hi(dt[3]) = secs (0 - 59), Lo(dt[3] = msecs (0 - 99) }
   VAR
      r: Registers;
   BEGIN
   r.ax := $2c00;
   MsDos( r );
   dt[2] := r.cx;
   dt[3] := r.dx;
   END; {rddtti}


FUNCTION timetorealsecs( x: timearty ): REAL;
   BEGIN
   timetorealsecs := (Hi(x[2]) * 3600.0) + (Lo(x[2])* 60.0) +
                      Hi(x[3]) + (Lo(x[3]) / 100.0);
   END;



FUNCTION timedif( a, b: timearty ): REAL;
   BEGIN
   timedif := timetorealsecs( b ) - timetorealsecs( a );
   END;



{ start of CRC stuff }
{ byte crc in Turbo Pascal }
{ for MSDOS }



{ METHOD 1: Pascal Bit-By-Bit }
{ bit manipulation in a high-level-language }
{ simulation of "longhand" division " }
{ mostly for verification of other methods }


PROCEDURE crcittb( VAR a: INTEGER; bit: BOOLEAN );
   { single bit computation; simulate polydiv hardware }
   { other Pascals can replace "a Shl 1" with "a + a" }
   BEGIN
   IF bit = (a < 0 ) THEN
      a := a Shl 1
   ELSE
      a := (a Shl 1) XOR $1021;  { CRC-CCITT }
   END; {crcittb }


PROCEDURE crcittby( VAR aa: INTEGER; d: INTEGER );
   { whole byte computation }
   VAR
      i: INTEGER;
   BEGIN
   d := d Shl 7;
   FOR i := 7 DOWNTO 0 DO
      BEGIN
      d := d Shl 1;
      crcittb( aa, (d < 0) );
      END;
   END; { crcittby }




{ METHOD 2: Pascal Fast Bit-By-Bit }
{ eliminates procedure overhead in the loop }
{ similar to most XMODEM crc implementations }


PROCEDURE crcfbbb( VAR aa: INTEGER; d: INTEGER );
   { fast bit-by-bit whole byte computation }
   VAR
      i: INTEGER;
   BEGIN
   d := d Shl 7;
   FOR i := 7 DOWNTO 0 DO
      BEGIN
      d := d Shl 1;
      IF ((d XOR aa) < 0) THEN
         aa := (aa Shl 1) XOR $1021
      ELSE
         aa := aa Shl 1;
      END;
   END; { crcfbbb }




{ METHOD 3: Pascal Byte }
{ process the data byte without loops }
{ transportable within Turbo Pascal, and fairly fast }
{ may be slower in Pascals without bit-shifting opns }


PROCEDURE crcitta( var dx: INTEGER; data: INTEGER );
   { dx := crcTransform( dx; data ) }
   { polynomial = $11021 }

   { for other Pascals, generate a Swap function }
   { probably x := (x * 256) + (x DIV 256) would work }
   { Lo(x) = x AND $00ff = x AND 255 }
   { x Shr 4 = x DIV 16 }
   { x Shl 4 = x * 16;  x Shl 5 = x * 32 }

   BEGIN { crcitta }

   dx := Swap( dx ) XOR data;

   dx := dx XOR ( Lo(dx) Shr 4 );

   dx := dx XOR (Swap(Lo(dx)) Shl 4) XOR (Lo(dx) Shl 5);

   END; { crcitta }




{ METHOD 4: Pascal Table }
{ pull changes from table, indexed by composite value }
{ still faster, but requires the table, and filling the table }
{ may be easier to port into a quick routine in another Pascal }
{ a slower routine is fine to fill the table }


VAR
   crctab: ARRAY[0..255] of INTEGER;


PROCEDURE crctablu( VAR crcreg: INTEGER; data: INTEGER );
   BEGIN
   crcreg := Swap(crcreg) XOR data;
   crcreg := (crcreg AND $ff00) XOR crctab[ Lo(crcreg) ];
   END;


PROCEDURE initctab;
   { use method 3 to init the table }
   VAR
      i: INTEGER;
   BEGIN
   FOR i := 0 TO 255 DO
      BEGIN
      crctab[i] := 0;
      crcitta( crctab[i], i );
      END;
   END; {initctab}




{ METHOD 5: Machine Code Byte }
{ method 3 ini "Inline" machine code (MSDOS) }
{ typically hidden away in an "Include" file }
{ other Pascals may need to modify the stack interface }


PROCEDURE mcrcitt1( VAR dx: INTEGER; data: INTEGER );
   { a := crcTransform( ds; data ) }
   { for MSDOS }
   { polynomial = $11021 }

   BEGIN { mcrcitt1 }
   INLINE (
             $c4/$7e/<dx/   {  es:di := [bp+ "dx"]   }
             $26/$8b/$05/   {  ax := [es:di]         }

   { dx := SWAP(dx) XOR data; }
             $86/$e0/       {  ah <=> al             }
             $33/$46/<data/ {  ax := ax XOR [bp + "data"] }
             $89/$c2/       {  dx := ax              }

   { dx := dx XOR ( LO(dx) SHR 4 ); }
             $d0/$e8/       {  al := al SHR 1        }
             $d0/$e8/       {  al := al SHR 1        }
             $d0/$e8/       {  al := al SHR 1        }
             $d0/$e8/       {  al := al SHR 1        }
             $32/$d0/       {  dl := dl XOR al       }

   { dx := dx XOR ( (SWAP( LO(dx) ) SHL 4 ); }
             $88/$d4/       {  ah := dl              }
             $d0/$e4/       {  ah := ah SHL 1        }
             $d0/$e4/       {  ah := ah SHL 1        }
             $d0/$e4/       {  ah := ah SHL 1        }
             $d0/$e4/       {  ah := ah SHL 1        }
             $32/$f4/       {  dh := dh XOR ah       }

   { dx := dx XOR ( ( LO(dx) ) SHL 5); }
             $88/$d0/       {  al := dl              }
             $b4/$00/       {  ah := 0               }
             $d1/$e0/       {  ax := ax SHL 1        }
             $d1/$e0/       {  ax := ax SHL 1        }
             $d1/$e0/       {  ax := ax SHL 1        }
             $d1/$e0/       {  ax := ax SHL 1        }
             $d1/$e0/       {  ax := ax SHL 1        }
             $33/$d0/       {  dx := dx XOR ax       }

             $26/$89/$15    {  es:[di] := dx         } );

   END; { mcrcitt1 }




   { METHOD 6: Machine Code Table }
   { here the stack parameter interface becomes significant }
   { note the exchange notation "x :=: y" in the comments }


   PROCEDURE mcrcitt3( VAR dx: INTEGER; data: INTEGER );
      { a := crcTransform( dx; data ) }
      { for MSDOS }
      { polynomial = $11021 }

      BEGIN { mcrcitt3 }
      INLINE (
                $c4/$7e/<dx/   {  es:di := [bp + "dx"]  }
                $26/$8b/$15/   {  dx := [es:di]         }

      { dx := Swap(dx) XOR data; }
                $86/$d6/       {  dh :=: dl             }
                $33/$56/<data/ {  dx := dx XOR [bp + "data"] }

      { bx := Lo(dx) SHL 1;  dl := 0; }
                $31/$db/       { bx := bx XOR bx        }
                $86/$d3/       { bl :=: dl              }
                $d1/$e3/       { bx := bx SHL 1         }

      { dx := dx XOR crctab[ bx ]; }
                $33/$97/>crctab/  {  dx := dx XOR [bx + "crctab"] }

                $26/$89/$15    {  [es:di] := dx         } );

      END; { mcrcitt3 }



{ start of validation testing }


PROCEDURE fultest( beg, en: INTEGER );
   TYPE
      st40 = STRING[40];
   VAR
      adi, adr, adt: INTEGER;


   PROCEDURE overall( VAR a: INTEGER; t: INTEGER );
      VAR
         loc: INTEGER;
         data: BYTE;
      BEGIN
      a := adi;
      FOR loc := beg TO en DO
         BEGIN
         data := MEM[ Cseg: loc ];
            CASE t OF
            1: crcittby( a, data );
            2: crcfbbb( a, data );
            3: crcitta( a, data );
            4: crctablu( a, data );
            5: mcrcitt1( a, data );
            6: mcrcitt3( a, data );
            END; {case}
         END;
      END; {overall}


   PROCEDURE pbin( value: INTEGER );
      VAR
         i: INTEGER;
      BEGIN
      FOR i := 15 DOWNTO 0 DO
         BEGIN
         IF value < 0 THEN
            WRITE( '1' )
         ELSE
            WRITE( '0' );
         value := value SHL 1;
         END;
      END; {pbin}


   PROCEDURE showres( s: st40 );
      BEGIN
      WRITE( ^M^J'   ', s );
      IF (adt <> adr) THEN
         BEGIN
         WRITE(': CRC error. ' );
         WRITE( ^M^J, 'Reference:  '); pbin( adr );
         WRITE( ^M^J, 'Under Test: '); pbin( adt );
         END
      ELSE
         WRITE( ': No error.' );
      END; {showres}


   BEGIN {fultest}
   WRITE( ^M^J^J'BEGIN Validation Testing.' );
   adi := -1;

   initctab;

   overall( adr, 1 );
   WRITE( ^M^J'   Reference = crcittby (Pascal Bit-By-Bit).' );

   overall( adt, 2 );
   showres( 'crcfbbb (Pascal Fast Bit-By-Bit)' );

   overall( adt, 3 );
   showres( 'crcitta (Pascal Byte)' );

   overall( adt, 4 );
   showres( 'crctablu (Pascal Table)' );

   overall( adt, 5 );
   showres( 'mcrcitt1 (Machine Code Byte)' );

   overall( adt, 6 );
   showres( 'mcrcitt3 (Machine Code Table)' );

   WRITELN( ^M^J'END Validation Testing.' );
   END; { fultest}



{ start of timing }


PROCEDURE timetest( loops: INTEGER );
   { organize the time ttesting of various routines }
   VAR
      a, b: timearty;
      i, x: INTEGER;
      by: BYTE;
      empty: REAL;  { time for empty loops }
      calltime: REAL;  { time for loops and empty procedure }

   PROCEDURE crcmt( VAR dx: INTEGER; data: INTEGER );
      BEGIN
      END;


   PROCEDURE showtimedif( a, b: timearty; c: INTEGER );
      { display a line of time results }
      VAR
         dif, Noloop, NoloopNocall: REAL;
      BEGIN
      dif := timedif( a, b );
      Noloop := dif - empty;
      NoloopNocall := dif - calltime;
      WRITE(
   Noloop:7:3, '  ', NoloopNocall:7:3, '        ',
   Noloop* (1000.0 / c):7:3, '  ', NoloopNocall * (1000.0 / c):7:3 );
      END; {showtimedif}


   BEGIN {timetest}
   calltime := 0.0;  {the global}
   by := $a5;  {your typical data byte}

   WRITELN(
^M^J^J'Turbo Pascal runs CRC-CCITT on 8088 under Bare MSDOS',
  ^M^J'   FOR ', loops, ' OPERATIONS; 7.16 MHz CLOCK  (multiply by 1.5 for 4.77 MHz) ' );

   WRITE( ^M^J'Empty loop:  ' );
   readhms( a );
   FOR i := 1 TO loops DO
       ;
   readhms( b );
   empty := timedif( a, b );  {the global}
   WRITE( empty:5:3, ' secs' );

   WRITE( ^M^J'Empty procedure in loop:  ' );
   readhms( a );
   FOR i := 1 TO loops DO
      crcmt( x, by );
   readhms( b );
   calltime := timedif( a, b ); {another global}
   WRITE( calltime:5:3, ' secs' );

   WRITE( ^M^J'   (procedure overhead alone = ',
           (calltime - empty) * (1000.0 / loops):6:3,
           ' msec each)' );

   WRITELN(
^M^J^J'                 ', loops:5, ' Uses (secs)        1 Use (msec)',
  ^M^J'                Procedure   In Line    Procedure   In Line' );

   WRITE(
^M^J'Pascal Bit-by-Bit:    ' );
   readhms( a );
   FOR i := 1 TO loops DO
      crcittby( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITE(
^M^J'Pascal Fast B-B-B:    ' );
   readhms( a );
   FOR i := 1 TO loops DO
      crcfbbb( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITE(
^M^J'Pascal Byte:          ' );
   readhms( a );
   FOR i := 1 TO loops DO
      crcitta( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITE(
^M^J'Pascal Table:         ' );
   readhms( a );
   FOR i := 1 TO loops DO
      crctablu( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITE(
^M^J'Machine Code Byte:    ' );
   readhms( a );
   FOR i := 1 TO loops DO
      mcrcitt1( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITE(
^M^J'Machine Code Table:   ' );
   readhms( a );
   FOR i := 1 TO loops DO
      mcrcitt3( x, by );
   readhms( b );
   showtimedif( a, b, loops );

   WRITELN;
   END; {timetest}



PROCEDURE datatimes;
   { data character times, for comparison }
   CONST
      rates: ARRAY[1..7] of INTEGER =
             ( 12, 24, 48, 96, 192, 384, 576 );
   VAR i: INTEGER;
   BEGIN
   WRITELN( ^M^J^J'Character Times for Various Bit Rates: ' );
   WRITE( ^M^J'   bits/sec     char/sec    msec/char' );
   FOR i := 1 TO 7 DO
      WRITE( ^M^J, '':4, (100.0 * rates[i]):5:0, '':8,
                         (10.0 * rates[i]):5:0, '':8,
                         (100.0 / rates[i]):5:3 );
   WRITELN;
   END; {datatimes}


BEGIN { main: crctime }
WRITELN;

(* not useful in 7.0
ConOutPtr := OFS( bdosch );  {output through MSDOS}
*)

ownership;

fultest( 100, 1000 );

timetest( 10000 );

datatimes;

END.

{ end file crctime.pas }


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

Last updated: 1996-04-30