DOWNLOADED FROM WARD CHRISTENSEN'S BOARD AT (312) 849-1132
ON 2/13/85 23:30 PST


Msg 00006 is 99 line(s) on 01/16/85 from JOHN BYRNS
to ALL re: MODEM PROTOCOL (CONT):CRC

(really, 221 lines - but 99 is max in hdr)
MODEM PROTOCOL OVERVIEW, CRC OPTION ADDENDUM

1/13/85 by John Byrns.
Please pass on any reports of errors in this document or suggestions
for improvement to me via Ward's/CBBS at (312) 849-1132, or by voice
at (312) 885-1105.

Last Rev: (preliminary 1/13/85)

This document describes the changes to the Christensen Modem Protocol
that implement the CRC option. This document is an addendum to
Ward Christensen's "Modem Protocol Overview". This document and
Ward's document are both required for a complete description of the
Modem Protocol.

Table of Contents

1. DEFINITIONS
7. OVERVIEW OF CRC OPTION
8. MESSAGE BLOCK LEVEL PROTOCOL, CRC MODE
9. CRC CALCULATION
10. FILE LEVEL PROTOCOL, CHANGES FOR COMPATIBILITY
11. DATA FLOW EXAMPLES WITH CRC OPTION


---- 1B. ADDITIONAL DEFINITIONS

<C> 43H

-------- 7. OVERVIEW OF CRC OPTION

The CRC used in the Modem Protocol is an alternate form of block check
which provides more robust error detection than the original checksum.
Andrew S. Tanenbaum says in his book, Computer Networks, that the
CRC-CCITT used by the Modem Protocol will detect all single and double
bit errors, all errors with an odd number of bits, all burst errors of
length 16 or less, 99.997% of 17-bit error bursts, and 99.998% of
18-bit and longer bursts.

The changes to the Modem Protocol to replace the checksum with the CRC
are straight forward. If that were all that we did we would not be
able to communicate between a program using the old checksum protocol
and one using the new CRC protocol. An initial handshake was added to
solve this problem. The handshake allows a receiving program with CRC
capability to determine whether the sending program supports the CRC
option, and to switch it to CRC mode if it does. This handshake is
designed so that it will work properly with programs which implement
only the original protocol. A description of this handshake is
presented in section 10.

-------- 8. MESSAGE BLOCK LEVEL PROTOCOL, CRC MODE

Each block of the transfer in CRC mode looks like:
<SOH><blk #><255-blk #><--128 data bytes--><CRC hi><CRC lo>
in which:
<SOH> = 01 hex
<blk #> = binary number, starts at 01 increments by 1, and
wraps 0FFH to 00H (not to 01)
<255-blk #> = ones complement of blk #.
<CRC hi> = byte containing the 8 hi order coefficients of the CRC.
<CRC lo> = byte containing the 8 lo order coefficients of the CRC.
See the next section for CRC calculation.

-------- 9. CRC CALCULATION

---- 9A. FORMAL DEFINITION OF THE CRC CALCULATION

To calculate the 16 bit CRC the message bits are considered to be the
coefficients of a polynomial. This message polynomial is first
multiplied by X^16 and then divided by the generator polynomial
(X^16 + X^12 + X^5 + 1) using modulo two arithemetic. The remainder
left after the division is the desired CRC. Since a message block in
the Modem Protocol is 128 bytes or 1024 bits, the message polynomial
will be of order X^1023. The hi order bit of the first byte of the
message block is the coefficient of X^1023 in the message polynomial.
The lo order bit of the last byte of the message block is the
coefficient of X^0 in the message polynomial.

---- 9B. EXAMPLE OF CRC CALCULATION WRITTEN IN C

/*
This function calculates the CRC used by the "Modem Protocol"
The first argument is a pointer to the message block. The second
argument is the number of bytes in the message block. The message
block used by the Modem Protocol contains 128 bytes.
The function return value is an integer which contains the CRC. The
lo order 16 bits of this integer are the coefficients of the CRC. The
The lo order bit is the lo order coefficient of the CRC.
*/

int calcrc(ptr, count) char *ptr; int count; {

int crc, i;

crc = 0;
while(--count >= 0) {
crc = crc ^ (int)*ptr++ << 8;
for(i = 0; i < 8; ++i)
if(crc & 0x8000)
crc = crc << 1 ^ 0x1021;
else
crc = crc << 1;
}
return (crc & 0xFFFF);
}

-------- 10. FILE LEVEL PROTOCOL, CHANGES FOR COMPATIBILITY

---- 10A. COMMON TO BOTH SENDER AND RECEIVER:

The only change to the File Level Protocol for the CRC option is the
initial handshake which is used to determine if both the sending and
the receiving programs support the CRC mode. All Modem Programs should
support the checksum mode for compatibility with older versions.
A receiving program that wishes to receive in CRC mode implements the
mode setting handshake by sending a <C> in place of the initial <nak>.
If the sending program supports CRC mode it will recognize the <C> and
will set itself into CRC mode, and respond by sending the first block
as if a <nak> had been received. If the sending program does not
support CRC mode it will not respond to the <C> at all. After the
receiver has sent the <C> it will wait up to 3 seconds for the <soh>
that starts the first block. If it receives a <soh> within 3 seconds
it will assume the sender supports CRC mode and will proceed with the
file exchange in CRC mode. If no <soh> is received within 3 seconds
the receiver will switch to checksum mode, send a <nak>, and proceed
in checksum mode. If the receiver wishes to use checksum mode it
should send an initial <nak> and the sending program should respond to
the <nak> as defined in the original Modem Protocol. After the mode
has been set by the initial <C> or <nak> the protocol follows the
original Modem Protocol and is identical whether the checksum or CRC
is being used.

---- 10B. RECEIVE PROGRAM CONSIDERATIONS:

There are at least 4 things that can go wrong with the mode setting
handshake.
1. the initial <C> can be garbled or lost.
2. the initial <soh> can be garbled.
3. the initial <C> can be changed to a <nak>.
4. the initial <nak> from a receiver which wants to receive in
checksum can be changed to a <C>.

The first problem can be solved if the receiver sends a second <C>
after it times out the first time. This process can be repeated
several times. It must not be repeated a too many times before sending
a <nak> and switching to checksum mode or a sending program without
CRC support may time out and abort. Repeating the <C> will also fix
the second problem if the sending program cooperates by responding as
if a <nak> were received instead of ignoring the extra <C>.

It is possible to fix problems 3 and 4 but probably not worth the
trouble since they will occur very infrequently. They could be fixed
by switching modes in either the sending or the receiving program
after a large number of successive <nak>s. This solution would risk
other problems however.

---- 10C. SENDING PROGRAM CONSIDERATIONS.

The sending program should start in the checksum mode. This will
insure compatibility with checksum only receiving programs. Anytime a
<C> is received before the first <nak> or <ack> the sending program
should set itself into CRC mode and respond as if a <nak> were
received. The sender should respond to additional <C>s as if they were
<nak>s until the first <ack> is received. This will assist the
receiving program in determining the correct mode when the <soh> is
lost or garbled. After the first <ack> is received the sending program
should ignore <C>s.

-------- 11. DATA FLOW EXAMPLES WITH CRC OPTION

---- 11A. RECEIVER HAS CRC OPTION, SENDER DOESN'T

Here is a data flow example for the case where the receiver requests
transmission in the CRC mode but the sender does not support the CRC
option. This example also includes various transmission errors.
<xx> represents the checksum byte.

SENDER RECEIVER
<--- <C>
times out after 3 seconds,
<--- <nak>
<soh> 01 FE -data- <xx> --->
<--- <ack>
<soh> 02 FD -data- <xx> ---> (data gets line hit)
<--- <nak>
<soh> 02 FD -data- <xx> --->
<--- <ack>
<soh> 03 FC -data- <xx> --->
(ack gets garbaged) <--- <ack>
times out after 10 seconds,
<--- <nak>
<soh> 03 FC -data- <xx> --->
<--- <ack>
<eot> --->
<--- <ack>

---- 11B. RECEIVER AND SENDER BOTH HAVE CRC OPTION

Here is a data flow example for the case where the receiver requests
transmission in the CRC mode and the sender supports the CRC option.
This example also includes various transmission errors.
<xxxx> represents the 2 CRC bytes.

SENDER RECEIVER
<--- <C>
<soh> 01 FE -data- <xxxx> --->
<--- <ack>
<soh> 02 FD -data- <xxxx> ---> (data gets line hit)
<--- <nak>
<soh> 02 FD -data- <xxxx> --->
<--- <ack>
<soh> 03 FC -data- <xxxx> --->
(ack gets garbaged) <--- <ack>
times out after 10 seconds,
<--- <nak>
<soh> 03 FC -data- <xxxx> --->
<--- <ack>
<eot> --->
<--- <ack>
--End of 00006

Msg #: to retrieve (C/R when done)?