231 lines
8.9 KiB
Prolog
231 lines
8.9 KiB
Prolog
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)?
|
||
|