Program CRC;

{ CRC generation program, version 7b (optimized + timing + documentation)


   This set of implementations was written by David Dantowitz, and
   has been placed in the public domain, to be used at the user's
   discretion.

   This program demonstrates various ways by which Cyclic
   Redundancy Checks (CRC) may be computed and their relative speeds.

   Please note the cautionary notice involving the routine SET_TIMER.  
   This routine should be used only by users who understand its 
   consequences and who wish to experiment with interrupt and timer 
   routines.  The routine has been written for use on an IBM PC or 
   compatible.   

   The variable TIME is the location of the low 16 bits of the TIMER
   location incremented by DOS 2.0 with each clock tick.  It is defined 
   in the source code for the IBM PC ROM BIOS.  This should work with 
   most compatibles as well as later versions of the operating system.


   Here are some sample results.  These were obtained using TURBO 3.0
   under DOS 2.0 on a SEEQUA Chameleon.   (Your mileage may vary.)
   (Note that the CRC is printed to assure that all implementations
   are working properly.)


                      D a t a   S t r e a m   L e n g t h

                    512      1024      2048      4096     32767

No table           0.33      0.65      1.31      2.62     20.93     CRC = -31717
Nybble table       0.10      0.18      0.38      0.76      6.03     CRC = -31717
Two Nybble tables  0.10      0.18      0.36      0.74      5.88     CRC = -31717
Byte table         0.08      0.16      0.32      0.64      5.12     CRC = -31717
Nybble string      0.03      0.05      0.09      0.18      1.50     CRC = -31717
Byte string        0.01      0.03      0.05      0.09      0.73     CRC = -31717

}

Const
      max = 32767;

Type
      Bytes = Array [1..max] of Byte;

Var
      time : Integer Absolute $0040:$006c;  { TIMER_LOW
                                              IBM PC ROM BIOS location }

      initial_clock, stop, j, i : Integer;

      length : Array [1..5] of Integer;

      table_16 : Array [0..15] of Integer;
      table_32a : Array [0..16] of Integer;
      table_32b : Array [0..16] of Integer;
      table_256 : Array [0 .. 255] of Integer;

      CRC_value : Integer;

      byte_string : Bytes;

      POLY : Integer;

{
   CRC polynomials in this program are represented by replacing
   each term that is non-zero with a 1 and each zero term with a 0.
   Note that the highest order bits represent the low order terms 
   of the polynomial.

   Thus X^3+X^1+1 becomes 1101 and X^4+X^1+1 becomes 11001.

   Since all polynomials have a highest term (X^a) we drop the
   highest term during computation (shift right one bit).


   Here are some examples :


           Polynomial                Representation     Hex

          X^5 + X^2 + 1                  10100          $14

            X^7 + 1                     1000000         $40

          X^3+X^2+X^1+1                   111           $7

          X^6+X^5+X^3+1                 100101          $25


   For a good discussion of polynomial selection see "Cyclic
   Codes for Error Detection", by W. W. Peterson and
   D. T. Brown, Proceedings of the IEEE, volume 49, pp 228-235,
   January 1961.

   A reference on table driven CRC computation is "A Cyclic
   Redundancy Checking (CRC) Algorithm" by A. B. Marton and
   T. K. Frambs, The Honeywell Computer Journal, volume 5,
   number 3, 1971.

   Also used to prepare these examples was "Computer Networks",
   by Andrew S. Tanenbaum, Prentice Hall, Inc.  Englewood Cliffs,
   New Jersey, 1981.

   The following three polynomials are international standards:


        CRC-12 = X^12 + X^11 + X^3 + X^2 + X^1 + 1
        CRC-16 = X^16 + X^15 + X^2 + 1
        CRC-CCITT = X^16 + X^12 + X^5 + 1

   In Binary and hexadecimal :

                   Binary                     Hex

        CRC-12    = 1111 0000 0001           $0F01
        CRC-16    = 1010 0000 0000 0001      $A001
        CRC-CCITT = 1000 0100 0000 1000      $8404    (Used below)

   The first is used with 6-bit characters and the second two
   with 8-bit characters.  All of the above will detect any
   odd number of errors.  The second two will catch all 16-bit
   bursts, a high percentage of 17-bit bursts (~99.997%) and
   also a large percentage of 18-bit or larger bursts (~99.998%).
   The paper mentioned above (Peterson and Brown) discusses how 
   to compute the statistics presented which have been quoted 
   from Tanenbaum.

   (A burst of length N is defined a sequence of N bits, where
   the first and last bits are incorrect and the bits in the
   middle are any possible combination of correct and incorrect.
   See the paper by Peterson and Brown for more information)


   Note that when using a polynomial of degree N, the CRC is the
   first N bits of the value returned by the routines below.
   (e.g. with CRC-12, the CRC is bits 0 to 11 of the CRC value,
   with the other two mentioned above, the CRC is all 16 bits.)


   Here is a quick idea of what is being calculated ...

   The CRC is the residual from division of the data stream by
   the CRC polynomial.  The data stream is also thought of as a
   polynomial, with the highest order term being the lowest bit
   of the first byte of the data stream and the lowest order term
   of the polynomial being the high bit of the last byte of data.
   The actual division is performed on the data stream polynomial
   multiplied by X^y where y is the degree of the CRC polynomial.


   CRC use ...

   The CRC is then appended to the end of the data stream.  When
   the receiver gets the data stream, the CRC is again computed
   and matched against the received CRC, if the two do not match
   then an error has most likely occurred.





}


{

   This work was prompted by a submission by David Kirschbaum,
   who unknowingly submitted a program that contained an error.
   I have not determined if what it computed has any reliable
   error-detecting capabilities, only that it was an attempt to
   compute a CRC, that really did not work.  The original code
   is correctly used in the program KERMIT (Columbia University)
   to compute the CRC-CCITT polynomial CRC.


   My address is

   David Dantowitz
   Digital Equipment Corporation
   Dantowitz%eagle1.dec@decwrl


   The views and ideas expressed here are my own and do not necessarily
   reflect those of the Digital Equipment Corporation.


   David Kirschbaum
   Toad Hall
   ABN.ISCAMS@USC-ISID.ARPA
}

Procedure set_timer(count : Integer);

{
    This routine sets the clock (timer) count-down value to
    count.  The DOS value is 0 (this is the maximum value ...
    it really means 65536).  This routine is used to obtain 
    better resolution in timing.

    WARNING : The setting of count to too small a value will
              HANG your system.  Please study interrupts in
              real time systems before using this routine.

    WARNING : This routine was written to run on an IBM PC or
              compatible.  Disable this routine when this 
              program is run on other machines.
}

Begin

inline($b0/$36/        { mov al,36        }
       $e6/$43/        { out 43,al        }
       $8b/$86/count/  { mov ax,bp[count] }
       $e6/$40/        { out 40,al        }
       $88/$e0/        { mov al,ah        }
       $e6/$40);       { out 40,al        }

End;

Procedure simple_crc(b:byte);

{
    This routine computes the CRC value bit by bit.  The initial value
 is assumed to be in a global variable CRC_value and the global variable
 POLY contains the representation of the polynomial be used.  The routine
 is called for each byte.  The result is placed in the global CRC_value.
}

Var
    i : Integer;

Begin
CRC_value := b xor CRC_value;

For i := 1 to 8 Do
   Begin
      If (CRC_value and 1) = 1
         then CRC_value := (CRC_value shr 1) xor POLY
         else CRC_value :=  CRC_value shr 1;
   End;

End;

Procedure generate_table_16(POLY : Integer);

{
    This routine computes the remainder values of 0 through 15 divided
  by the polynomial represented by POLY.  These values are placed in a
  table and used to compute the CRC of a block of data efficiently.


    This implementation only permits polynomials up to degree 16.
}


Var
   val, i, result : Integer;

Begin
For val := 0 to 15 Do
  Begin
     result := val;
     For i := 1 to 4 Do
        Begin
           If (result and 1) = 1
              then result := (result shr 1) xor POLY
              else result :=  result shr 1;
        End;

     table_16[val] := result;
  End
End;


Procedure generate_table_32(POLY : Integer);

{
    This routine computes the remainder values of 0 through 15 divided
  by the polynomial represented by POLY.  These values are placed in two
  tables and used to compute the CRC of a block of data efficiently.


    This implementation only permits polynomials up to degree 16.
}


Var
   val, i, result, divide : Integer;

Begin
{
   Table_32a divides the number for eight bits (not four).
   Note that Table_32b is identical to Table_16.
}

For val := 0 to 15 Do
  Begin
     result := val;
     For i := 1 to 4 Do
        Begin
           If (result and 1) = 1
              then result := (result shr 1) xor POLY
              else result :=  result shr 1;
        End;

     table_32b[val] := result;
  End;

For val := 0 to 15 Do
  Begin
     result := table_32b[val];
     For i := 1 to 4 Do
        Begin
           If (result and 1) = 1
              then result := (result shr 1) xor POLY
              else result :=  result shr 1;
        End;

     table_32a[val] := result;
  End;

End;

Procedure generate_table_256(POLY : Integer);

{
    This routine computes the remainder values of 0 through 255 divided
  by the polynomial represented by POLY.  These values are placed in a
  table and used to compute the CRC of a block of data efficiently.
  More space is used, but the CRC computation will be faster.



    This implementation only permits polynomials up to degree 16.
}


Var
   val, i, result, divide : Integer;

Begin
For val := 0 to 255 Do
  Begin
     result := val;
     For i := 1 to 8 Do
        Begin
           If (result and 1) = 1
              then result := (result shr 1) xor POLY
              else result :=  result shr 1;
        End;

     table_256[val] := result;
  End
End;


Procedure Compute_crc_16(next_byte : byte);

{
   This routine calculates the CRC and stores the result in a global
 variable CRC_value.  You must first initialize CRC_value to 0 or the
 proper initial value for the CRC and then call this routine with
 each byte.

    This routine uses table_16.

}

Begin

inline(
$8b/$16/CRC_value/         {mov dx,CRC_value      }
$32/$56/<next_byte/        {xor dl,next_byte[bp]    CRC = CRC XOR Next_byte  }
$be/table_16/              {mov si,offset table_16  (table address)          }
$30/$ff/                   {xor bh,bh               (bh <- 0)                }

$88/$d3/                   {mov bl,dl             }
$80/$e3/$0f/               {and bl,0f             }
$d0/$e3/                   {shl bl,1              }
$b1/$04/                   {mov cl,4              }
$d3/$ea/                   {shr dx,cl             }
$33/$10/                   {xor dx,[bx+si]          CRC = (CRC shr 4) XOR
                                                           table[CRC and 0F] }

$88/$d3/                   {mov bl,dl             }
$80/$e3/$0f/               {and bl,0f             }
$d0/$e3/                   {shl bl,1              }
$b1/$04/                   {mov cl,4              }
$d3/$ea/                   {shr dx,cl             }
$33/$10/                   {xor dx,[bx+si]          CRC = (CRC shr 4) XOR
                                                           table[CRC and 0F] }


$89/$16/CRC_value);        {mov CRC_value,dx        Update CRC in memory     }

{  basic algorithm expressed above

temp := crc XOR next_byte;

For i := 1 to 2 Do
   temp := (temp shr 4) XOR table [temp and $0F];

CRC_value := temp;
}
End;

Procedure Compute_crc_32(next_byte : byte);
{
   This is the algorithm used in KERMIT and attempted by the routine
   DoCRC from Toad Hall.

   The code here completely new.  This routine uses table_32a and
   table_32b.
}

Begin

inline(
$8b/$16/CRC_value/         {mov dx,CRC_value      }

$32/$56/<next_byte/        {xor dl,next_byte[bp]    CRC = CRC XOR Next_byte  }

{ intermediate steps, see comments for overall effect }

$31/$db/                   {xor bx,bx               (bx <- 0)                }
$86/$d3/                   {xchg bl,dl              (bx <- dx and 0FF)       }
$86/$f2/                   {xchg dl,dh              (dx <- dx shr 8)         }

$88/$d8/                   {mov al,bl             }
$80/$e3/$0f/               {and bl,0fh            }
$d0/$e3/                   {shl bl,1                (bx <- bx+bx)            }
$be/table_32a/             {mov si,offset table_32a (table address)          }
$33/$10/                   {xor dx,[bx+si]        }

$88/$c3/                   {mov bl,al             }
$80/$e3/$f0/               {and bl,0f0h           }
$b1/$03/                   {mov cl,3              }
$d2/$eb/                   {shr bl,cl             }
$be/table_32b/             {mov si,offset table_32b (table address)          }
$33/$10/                   {xor dx,[bx+si]        }

$89/$16/CRC_value);        {mov CRC_value,dx        Update CRC in memory     }
End;



Procedure Compute_crc_256(next_byte : byte);

{
   This routine calculates the CRC and stores the result in a global
 variable CRC_value.  You must first initialize CRC_value to 0 or the
 proper initial value for the CRC and then call this routine with
 each byte.

   This routine uses table_256.
}

Begin

inline(
$8b/$16/CRC_value/         {mov dx,CRC_value      }
$be/table_256/             {mov si,offset table_256 (table address)          }


$32/$56/<next_byte/        {xor dl,next_byte[bp]    CRC = CRC XOR Next_byte  }

{ intermediate steps, see comments for overall effect }

$31/$db/                   {xor bx,bx               (bx <- 0)                }
$86/$d3/                   {xchg bl,dl              (bx <- dx and 0FF)       }
$86/$f2/                   {xchg dl,dh              (dx <- dx shr 8)         }
$d1/$e3/                   {shl bx,1                (bx <- bx+bx)            }
$33/$10/                   {xor dx,[bx+si]          CRC = (CRC shr 8) XOR
                                                           table[CRC and 0FF] }

$89/$16/CRC_value);        {mov CRC_value,dx        Update CRC in memory     }

{  basic algorithm expressed above

temp := crc XOR next_byte;

temp := (temp shr 8) XOR table_256 [temp and $FF];

CRC_value := temp;
}
End;

Function crc_string_16(Var s : Bytes; length, initial_crc : Integer) : Integer;

{
     This routine computes the CRC value and returns it as the function
  value.  The routine takes an array of Bytes, a length and an initial
  value for the CRC.  The routine requires that a table of 16 values
  be set up by a previous call to Generate_table_16.

     This routine uses table_16.
}

Begin

inline(

$c4/$7e/<s/                {les di,s[bp]            (es:di points to array)  }
$8b/$46/<initial_crc/      {mov ax,initial_crc[bp]  (initial CRC value)      }
$8b/$56/<length/           {mov dx,length[bp]       (count)                  }
$be/table_16/              {mov si,offset table_16  (table address)          }
$30/$ff/                   {xor bh,bh               (bh <- 0)                }


{ next:  }

$26/$32/$05/               {xor al,es:[di]          CRC = CRC XOR next byte  }
$47/                       {inc di                  (point to next byte)     }


$88/$c3/                   {mov bl,al             }
$80/$e3/$0f/               {and bl,0f             }
$d0/$e3/                   {shl bl,1              }
$b1/$04/                   {mov cl,4              }
$d3/$e8/                   {shr ax,cl             }
$33/$00/                   {xor ax,[bx+si]          CRC = (CRC shr 4) XOR
                                                           table[CRC and 0F] }


$88/$c3/                   {mov bl,al             }
$80/$e3/$0f/               {and bl,0f             }
$d0/$e3/                   {shl bl,1              }
$b1/$04/                   {mov cl,4              }
$d3/$e8/                   {shr ax,cl             }
$33/$00/                   {xor ax,[bx+si]          CRC = (CRC shr 4) XOR
                                                           table[CRC and 0F] }

$4a/                       {dec dx                  (count <- count -1)      }
$75/$df/                   {jnz next               }

$89/$46/<s+4);             {mov s+4[bp],ax          (crc_string_16 := CRC)   }

{  basic algorithm expressed above


temp := initial_crc;

For each byte Do

Begin
temp := temp XOR next_byte;

For i := 1 to 2 Do
   temp := (temp shr 4) XOR table [temp and $0F];
End;

Crc_string_16 := temp;
}

End;


Function crc_string_256(Var s : Bytes; length, initial_crc : Integer) : Integer;

{
     This routine computes the CRC value and returns it as the function
  value.  The routine takes an array of Bytes, a length and an initial
  value for the CRC.  The routine requires that a table of 256 values
  be set up by a previous call to Generate_table_256.

      This routine uses table_256.
}

Begin

inline(

$c4/$7e/<s/                {les di,s[bp]            (es:di points to array)  }
$8b/$46/<initial_crc/      {mov ax,initial_crc[bp]  (initial CRC value)      }
$8b/$4e/<length/           {mov cx,length[bp]       (count)                  }
$be/table_256/             {mov si,offset table_256 (table address)          }


{ next:  }

$26/$32/$05/               {xor al,es:[di]          CRC = CRC XOR next byte  }
$47/                       {inc di                  (point to next byte)     }

{ intermediate steps, see comments for overall effect }

$31/$db/                   {xor bx,bx               (bx <- 0)                }
$86/$d8/                   {xchg al,bl              (bx <- ax and 0FF)       }
$86/$e0/                   {xchg al,ah              (ax <- ax shr 8)         }
$d1/$e3/                   {shl bx,1                (bx <- bx+bx)            }

$33/$00/                   {xor ax,[bx+si]          CRC = (CRC shr 8) XOR
                                                          table[CRC and 0FF] }

$e2/$f0/                   {loop next               (count <- count -1)      }

$89/$46/<s+4);             {mov s+4[bp],ax          (crc_string_256 := CRC)  }


{  basic algorithm expressed above

crc := initial_crc

For each byte Do
Begin
crc := crc XOR next_byte;       

crc := (crc shr 8) XOR table_256 [crc and $FF];
End;

crc_string_256 := crc;
}
End;



Begin

Writeln('Generating the data string, please wait ...');
Writeln;
Writeln;

Generate_table_16($8404);
Generate_table_32($8404);
Generate_table_256($8404);

For j := 1 to max Do
   byte_string[j] := trunc(random*256);    { Create a data string }

length[1] := 512;
length[2] := 1024;
length[3] := 2048;
length[4] := 4096;
length[5] := 32767;

Writeln;
Writeln('                      D a t a   S t r e a m   L e n g t h');
Writeln;
Write('             ');

For j := 1 to 5 Do
   Write('  ', length[j]:8);

Writeln;
Writeln;

Initial_clock := time;

Set_timer(5964);    { each tick = ~0.005 seconds }

{-----------------------------------------------------------------------------}

CRC_value := 0;
POLY := $8404;

Write('No table          ');

For j := 1 to 5 Do
   Begin
   time := 0;
   For i := 1 to length[j] Do
      simple_crc(byte_string[i]);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

CRC_value := 0;

Write('Nybble table      ');

For j := 1 to 5 Do
   Begin
   time := 0;
   For i := 1 to length[j] Do
      compute_crc_16(byte_string[i]);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

CRC_value := 0;

Write('Two Nybble tables ');

For j := 1 to 5 Do
   Begin
   time := 0;
   For i := 1 to length[j] Do
      compute_crc_32(byte_string[i]);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

CRC_value := 0;

Write('Byte table        ');

For j := 1 to 5 Do
   Begin
   time := 0;
   For i := 1 to length[j] Do
      compute_crc_256(byte_string[i]);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

CRC_value := 0;

Write('Nybble string     ');

For j := 1 to 5 Do
   Begin
   time := 0;
   CRC_value := crc_string_16(byte_string, length[j], CRC_value);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

CRC_value := 0;

Write('Byte string       ');    

For j := 1 to 5 Do
   Begin
   time := 0;
   CRC_value := crc_string_256(byte_string, length[j], CRC_value);
   stop := time;
   Write(stop/200:5:2, '     ');
   End;

Writeln('CRC = ', CRC_value);

{-----------------------------------------------------------------------------}

set_timer(0);   { restore the clock to the normal DOS value }

time := initial_clock;   { we may have lost a few minutes ... }

End.