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