[comp.lang.pascal] WANTED: checksum algrithms references

thurn@cis.ohio-state.edu (Martin Thurn) (03/18/89)

Hello Netland,
  I am currently designing and implementing (in TurboPascal 5.0) a simple
ASCII file transfer program (part of a larger application).  I would like
to incorporate a checksum into each data packet (i.e. string of characters)
as an error-detection help.  Can anyone recommend some good reference on
checksum algorithms?  Thanks in advance,

---Martin Thurn     thurn@cis.ohio-state.edu

englandr@phoenix.Princeton.EDU (Scott Englander) (03/20/89)

In article <39784@tut.cis.ohio-state.edu> thurn@cis.ohio-state.edu (Martin Thurn) writes:
>  I am currently designing and implementing (in TurboPascal 5.0) a simple
>ASCII file transfer program (part of a larger application).  I would like
>to incorporate a checksum into each data packet (i.e. string of characters)
>as an error-detection help.  Can anyone recommend some good reference on
>checksum algorithms?  Thanks in advance,


   A good reference on checksums is _Computer Networks_ by Andrew S. Tanenbaum,
Prentice-Hall, (year?), section 3.5.  This reference talks about several
methods and outlines the CRC scheme, one of the most widespread.  If you 
translate the method outlined there into an algorithm, though, you get some codethat is unnecessarily long and inefficient.  Here is a better way.  I've tested 
it somewhat under Turbo 5.0, but you should verify that it works in your 
situation.

Usage:

To prepare a message for transmission:
  add_crc(msg);  {msg is type packet}

To check received message, test the value of CRCgood(msg).
---------------------------------------------------------------------------

{Cylic Redundancy Code (CRC) functions}

type
  packet = array[0..40] of byte;
  { element 0 must be set to the length of the message }

function crc_update(crc : longint; crc_char : byte) : longint;
{
     By Environmental Technologies, Inc.  Converted from C to Pascal by
  Scott Englander.

     This function must be called once for each character which is to be
  included in the CRC for messages to be transmitted.  This function is
  called once for each character which is included in the CRC of a received
  message, AND once for each of the two CRC characters at the end of the
  received message.  If the resulting CRC is zero, then the message has been
  correctly received.

     x will contain the character to be processed in bits 0-7 and the CRC
  in bits 8-23.  Bit 24 will be used to test for overflow, and then cleared
  to prevent the sign bit of x from being set to 1.  Bits 25-31 are not used
  (x is treated as though it is a 32 bit register.)

     The loop is repeated once for each bit of the character.  The high-order
  bit of the character is shifted into the low-order bit of the CRC, and the
  high order bit of the CRC is shifted into bit 24.  The high order bit of
  the CRC is tested to see if it is a 1; if so, it is exclusive or'd with a 1
  to set it to 0, and the CRC is also xor'd with hex 1021 to produce the
  CCITT-recommended generator of X**16 + X**12 + X**5 + 1.  (To produce the
  CRC generator of X**16 + X**15 + X**2 + 1, change the constant from
  $01102100 to $01800500.  This will xor the CRC with hex 8005 and produce
  the same CRC that IBM uses for their synchronous transmission protocols.)
  Finally, the unneeded bits are anded off and the result is shifted 8 bits
  to the right.

  calling sequence:
    crc := crc_update(crc,next_char);

}
  const
    generator = $01102100;   { CRC-CCITT standard, used by ETI }
    { generator = $01800500  { CRC-16 standard, used by IBM }
  var
    x : longint;
    i : integer;
    temp : real;
  begin
    temp := crc;             {trunc expects a real argument}
    x := (trunc(temp) shl 8) + crc_char;
    for i := 0 to 7 do
      begin
        x := x shl 1;
        if (x and $01000000) > 0 then
          x := x xor generator
      end;
    crc_update :=(x and $00ffff00) shr 8
  end;

function crc_finish(crc : longint) : longint;
{ by ETI, translated to Pascal by Scott Englander }
{    This function must be called once after all the characters in a block
  have been processed for a message which is to be TRANSMITTED.  It returns
  the calculated CRC bytes, which should be transmitted as the two characters
  following the block.  The first of these 2 bytes must be taken from the
  high-order byte of the CRC, and the second must be taken from the low-order
  byte of the CRC.  This routine is NOT called for a message which has been
  RECEIVED.

  calling sequence:
    crc := crc_finish(crc);

        crc_update is called twice, passed a character of hex 00 each time,
     to flush out the last 16 bits from the CRC calculation, and return the
     result as the value of this function.
  }

  begin
    crc_finish := crc_update(crc_update(crc,0),0)
  end;


procedure add_crc(var msg : packet);
var crc : longint;
    i, msglen : integer;
begin
  crc := 0;
  msglen := msg[0];
  for i := 1 to msglen do
    crc := crc_update(crc,msg[i]);
  crc := crc_finish(crc);
  msg[msglen + 1] := crc shr 8;
  msg[msglen + 2] := crc and $FF;
  msg[0] := msglen + 2;  {adjust length of msg for crc bytes}
end;

function CRCgood(msg : packet;
                 var bad_data : boolean) : boolean;
var crc : longint;
    i : integer;
begin
  crc := 0;
  for i := 1 to msg[0] do
    crc := crc_update(crc,msg[i]);
  bad_data := (crc <> 0);
  CRCgood := (crc = 0);
end;
-- 

                                               - Scott