mskuhn@faui09.informatik.uni-erlangen.de (Markus Kuhn) (03/11/91)
Here is a short description for everybody interested
in using OSI protocols on asynchronous connections
(RS-232-C etc.). This might be useful for connecting a PC with
a host or a BBS.
The HDLC standard (normally used only on synchronous lines)
has been modified by an ISO addendum for asynch transmission.
The following text has been copied from the appendix of RFC1171.
Please check the ISO document if you plan to implement anything.
---------------------------------------------------------------------
A. Asynchronous HDLC
This appendix summarizes the modifications to ISO 3309-1979 proposed
in ISO 3309:1984/PDAD1. These modifications allow HDLC to be used
with 8-bit asynchronous links.
Transmission Considerations
Each octet is delimited by a start and a stop element.
Flag Sequence
The Flag Sequence is a single octet and indicates the beginning or
end of a frame. The Flag Sequence consists of the binary sequence
01111110 (hexadecimal 0x7e).
Transparency
On asynchronous links, a character stuffing procedure is used.
The Control Escape octet is defined as binary 01111101
(hexadecimal 0x7d) where the bit positions are numbered 87654321
(not 76543210, BEWARE).
After FCS computation, the transmitter examines the entire frame
between the two Flag Sequences. Each Flag Sequence, Control
Escape octet and octet with value less than hexadecimal 0x20 is
replaced by a two octet sequence consisting of the Control Escape
octet and the original octet with bit 6 complemented (i.e.,
exclusive-or'd with hexadecimal 0x20).
Prior to FCS computation, the receiver examines the entire frame
between the two Flag Sequences. Each octet with value less than
hexadecimal 0x20 is simply removed (it may have been inserted by
intervening data communications equipment). For each Control
Escape octet, that octet is also removed, but bit 6 of the
following octet is complemented. A Control Escape octet
immediately preceding the closing Flag Sequence indicates an
invalid frame.
Note: The inclusion of all octets less than hexadecimal 0x20
allows all ASCII control characters [10] excluding DEL (Delete)
to be transparently communicated through almost all known data
communications equipment.
A few examples may make this more clear. Packet data is
transmitted on the link as follows:
0x7e is encoded as 0x7d, 0x5e.
0x7d is encoded as 0x7d, 0x5d.
0x01 is encoded as 0x7d, 0x21.
Aborting a Transmission
On asynchronous links, frames may be aborted by transmitting a "0"
stop bit where a "1" bit is expected (framing error) or by
transmitting a Control Escape octet followed immediately by a
closing Flag Sequence.
Inter-frame Time Fill
On asynchronous links, inter-octet and inter-frame time fill
should be accomplished by transmitting continuous "1" bits (mark-
hold state).
Note: On asynchronous links, inter-frame time fill can be
viewed as extended inter-octet time fill. Doing so can save
one octet for every frame, decreasing delay and increasing
bandwidth. This is possible since a Flag Sequence may serve as
both a frame close and a frame begin. After having received
any frame, an idle receiver will always be in a frame begin
state.
Robust transmitters should avoid using this trick over-
zealously since the price for decreased delay is decreased
reliability. Noisy links may cause the receiver to receive
garbage characters and interpret them as part of an incoming
frame. If the transmitter does not transmit a new opening Flag
Sequence before sending the next frame, then that frame will be
appended to the noise characters causing an invalid frame (with
high reliability). Transmitters should avoid this by
transmitting an open Flag Sequence whenever "appreciable time"
has elapsed since the prior closing Flag Sequence. It is
suggested that implementations will achieve the best results by
always sending an opening Flag Sequence if the new frame is not
back-to-back with the last. The maximum value for "appreciable
time" is likely to be no greater than the typing rate of a slow
to average typist, say 1 second.
B. Fast Frame Check Sequence (FCS) Implementation
B.1. FCS Computation Method
The following code provides a table lookup computation for
calculating the Frame Check Sequence as data arrives at the
interface. The table is created by the code in section 2.
/*
* u16 represents an unsigned 16-bit number. Adjust the typedef for
* your hardware.
*/
typedef unsigned short u16;
/*
* FCS lookup table as calculated by the table generator in section 2.
*/
static u16 fcstab[256] = {
0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
};
#define PPPINITFCS 0xffff /* Initial FCS value */
#define PPPGOODFCS 0xf0b8 /* Good final FCS value */
/*
* Calculate a new fcs given the current fcs and the new data.
*/
u16 pppfcs(fcs, cp, len)
register u16 fcs;
register unsigned char *cp;
register int len;
{
ASSERT(sizeof (u16) == 2);
ASSERT(((u16) -1) > 0);
while (len--)
fcs = (fcs >> 8) ^ fcstab[(fcs ^ *cp++) & 0xff];
return (fcs);
}
B.2. Fast FCS table generator
The following code creates the lookup table used to calculate the
FCS.
/*
* Generate a FCS table for the HDLC FCS.
*
* Drew D. Perkins at Carnegie Mellon University.
*
* Code liberally borrowed from Mohsen Banan and D. Hugh Redelmeier.
*/
/*
* The HDLC polynomial: x**0 + x**5 + x**12 + x**16 (0x8408).
*/
#define P 0x8408
main()
{
register unsigned int b, v;
register int i;
printf("typedef unsigned short u16;\n");
printf("static u16 fcstab[256] = {");
for (b = 0; ; ) {
if (b % 8 == 0)
printf("\n");
v = b;
for (i = 8; i--; )
v = v & 1 ? (v >> 1) ^ P : v >> 1;
printf("0x%04x", v & 0xFFFF);
if (++b == 256)
break;
printf(",");
}
printf("\n};\n");
}
References
[1] Electronic Industries Association, EIA Standard RS-232-C,
"Interface Between Data Terminal Equipment and Data
Communications Equipment Employing Serial Binary Data
Interchange", August 1969.
[2] International Organization For Standardization, ISO Standard
3309-1979, "Data communication - High-level data link control
procedures - Frame structure", 1979.
[3] International Organization For Standardization, ISO Standard
4335-1979, "Data communication - High-level data link control
procedures - Elements of procedures", 1979.
[4] International Organization For Standardization, ISO Standard
4335-1979/Addendum 1, "Data communication - High-level data
link control procedures - Elements of procedures - Addendum 1",
1979.
[5] International Organization For Standardization, Proposed Draft
International Standard ISO 3309:1983/PDAD1, "Information
processing systems - Data communication - High-level data link
control procedures - Frame structure - Addendum 1: Start/stop
transmission", 1984.
[6] International Telecommunication Union, CCITT Recommendation
X.25, "Interface Between Data Terminal Equipment (DTE) and Data
Circuit Terminating Equipment (DCE) for Terminals Operating in
the Packet Mode on Public Data Networks", CCITT Red Book,
Volume VIII, Fascicle VIII.3, Rec. X.25., October 1984.
[7] Perez, "Byte-wise CRC Calculations", IEEE Micro, June, 1983.
[8] Morse, G., "Calculating CRC's by Bits and Bytes", Byte,
September 1986.
[9] LeVan, J., "A Fast CRC", Byte, November 1987.
[10] American National Standards Institute, ANSI X3.4-1977,
"American National Standard Code for Information Interchange",
1977.
--
Markus Kuhn, Computer Science student
University of Erlangen, Germany