🚀 go-pugleaf

rbach@bnr.ca (Richard Bach) writes:

>I'm looking for a standard asychronous RS-232 data link protocol 
>for use in a transaction processing application on a point
>to point dedicated link.  Error detection and auto-recovery
>mechanisms are important.

>I have heard that there is an asynchronous HDLC protocol as
>defined in ISO 3309-1984/PDAD1 - "Addemdum 1: Start/Stop 
>Transmission".  I have thus far been unable to obtain
>a copy of the ISO document but an still trying.  

You might also be interessted in ISO 7776 which defines LAPB, a HDLC
subset with error detection and auto-recovery. CCITT X.25 contains
also an LAPB description, but I feel that the ISO doc is much easier
to understand.

ISO 3309 only defines the framing. The following text contains some
information about it (the 7-bit transparency option is still
Draft Amendment 3, they simply make 8 septets out of 7 octets :-):

----------------------------------------------------------------------

Guidelines for adding HDLC Framing to Serial Port Drivers
---------------------------------------------------------

Markus Kuhn, 1992-06-21             [DRAFT VERSION!]


Summary
-------

This  text  is intended to encourage developers  of  serial  line 
drivers to include support for the asynchronous HDLC framing mode 
in  their software. Distribution of [the final version!] of  this 
text is unlimited.


Introduction
------------

Most  of today's asynchronous port drivers are  character  orien-
tated. They provide the application programmer an interface  that 
allows to send and receive single bytes or sequences of bytes and 
to  modify port parameters like transmission speed,  parity  bits 
and flow control.

Many application programs (e.g. file transfer tools, packet  net-
work access daemons) need an error corrected link over which data 
packets  can  be sent. Today, every  application  protocol  (e.g. 
Kermit, Zmodem, SLIP, PPP) defines it's own packet error  correc-
tion method.

Last  year,  the International Organization  for  Standardization 
(ISO)  published a new version of the International Standard  ISO 
3309.  This  document defines a well designed  frame  format  for 
serial  lines. The old version of ISO 3309 only defined a  synch-
ronous  frame format which is today used in nearly every  profes-
sional  data communication product, especially  those  supporting 
the  protocols  V.42, X.25/LAPB, ISDN/LAPD, Ethernet  LLC,  SDLC, 
synchronous PPP and many others. Now ISO extended the standard by 
an asynchronous mode (they call it start/stop transmission) which 
is  likely to become as popular in the world of cheap RS-232C  PC
interfaces  as the synchronous version has already been the  last 
decade in the professional world.

ISO  3309  is one part of a series of standards that  define  the 
HDLC  (High-level data link control procedures) family of  proto-
cols.  We will only discuss the framing level of HDLC here,  i.e. 
the  checksum  algorithm and the method used to  mark  the  frame 
boundaries.  In  addition the asynchronous  HDLC  framing  method 
allows to avoid some characters on the line, if they are used for 
other purposes (e.g. XON/XOFF) or not transmitted (e.g. on not 8-
bit  transparent connections), where this is necessary and  still
provides  a completely 8-bit transparent link. It seems to  be  a 
good  idea to perform these tasks within the serial  line  driver 
that  controls  the interface chip, because framing may  be  time 
consuming  and  should  be implemented  efficiently  with  direct 
access  to  the input/output FIFOs. We will not  deal  here  with 
higher layer functions like packet sequence control, error  reco-
very  and  timeout  handling,  but if you  want  to  implement  a 
complete  error correction protocol, you might be  interested  in 
ISO 7776 which defines the LAPB protocol, a HDLC subset that uses 
ISO 3309 framing.


Frame structure
---------------

In  the HDLC asynchronous framing mode, all transmissions are  in 
the  form of frames. Each frame is a sequence of bytes with  each
byte  consisting of 1 start bit (logical 0), 8 data  bits  trans-
mitted with low order bit first (the usual order), no  additional 
parity  bit  and  one stop bit (logical 1). Each  frame  has  the 
following structure:

              +------+--------------+-----+------+
              | Flag |     Data     | FCS | Flag |
              +------+--------------+-----+------+

The  flag is the byte 01111110 = 7Eh = '~'. All frames start  and 
end with this flag byte. A single flag byte may at the same  time 
be used as the closing flag of a frame and as the opening flag of 
the  next frame. The data field may be any sequence of  at  least 
two bytes followed by a 2- or 4-byte CRC frame checking  sequence 
(FCS).


Transparency
------------

For  proper operation, the flag byte must not appear between  the 
frame boundaries. Otherwise it would not be possible to determine 
the  end of the frame correctly and thus the location of the  FCS
and the length of the data sequence would be unclear. The  trans-
mitter  shall  examine the frame content consisting of  the  data 
byte sequence and the FCS and shall replace every appearance of a 
byte that is not allowed between the flags with the byte 01111101 
=  7Dh = '}' followed by the replaced byte with bit 6 (which  has 
the value 32 = 20h) being complemented.

The receiver discards each occurence of 7Dh and complements bit 6 
in  the following byte. If the byte following 7Dh is the  closing 
flag  7Eh, the complete frame is considered invalid and shall  be 
discarded.

ISO 3309 defines three alternative levels of transparency:

  - Basic  transparency: Only the bytes 7Dh and 7Eh are  replaced 
    by  7Dh 5Dh and 7Dh 5Eh. This is the minimal required  trans-
    parency.  Represented  as ASCII characters,  the  replacement
    rules are:
                            }    ->    }]
                            ~    ->    }^

  - Flow-control transparency: In some environments, the  control 
    characters DC1/XON and DC3/XOFF with and without bit 8 set to 
    1  must not be used in a frame as they may confuse  the  flow 
    control between the modem and the serial line driver. In  the 
    flow-control transparency mode, the characters 11h, 13h,  91h 
    and 93h or in binary format the bytes x00100x1 (where each  x 
    may  be  either  0 or 1) are replaced in  addition  to  those
    replaced in basic transparency mode.

  - Control-character  octet transparency: This mode  avoids  all 
    non-printable  characters  that might cause problems  on  the 
    line. The replaced characters are 00h to 1Fh, 7Fh to 9Fh  and 
    FFh  or  in  binary format the bytes  x00xxxxx  and  x1111111
    (where  each  x may be either 0 or 1) in  addition  to  those 
    replaced in basic transparency mode.

[do to: 7-bit transparency mode, PDAM not available for me, yet]


Frame Check Sequence
--------------------

A 16-bit or a 32-bit FCS are available as options. With a  16-bit 
FCS, at least 4 bytes (without transparency replacements) between
the  flags  are necessary to form a valid frame, with  32-bit  at 
least  6  bytes are required. Shorter frames and  frames  without 
correct  FCS  are considered to be transmission  errors  and  are 
discarded.  The  16-bit  FCS shall be  implemented  in  all  HDLC 
drivers, the 32-bit FCS is a possible extension.

The  mathematical  details of the FCS are defined  in  ISO  3309. 
Appendix A describes an efficient way to implement the FCS.


Example Frames
--------------

[...]


Implementation
--------------

The  following chapter gives only some hints which  functionality 
should be supported by the serial line driver and how it might be 
provided to an application programmer.

A  serial  line driver can be operated in two  modes.  In  normal 
mode,  single  bytes  and/or sequences of bytes can  be  sent  or 
received to and from a FIFO. The only thing the driver is looking 
for  in the byte stream are perhaps XON/XOFF characters  if  this 
has  been selected. The normal mode may also be necessary  before  
HDLC operation for modem control or perhaps a login procedure.

In HDLC framing mode, the application program uses two functions. 
One  is used to get the data byte sequence and it's length  of  a 
completely  received  frame  with correct  checksum.  The  second 
function  will send a frame with a given data byte  sequence.  If
sending a complete frame is not possible at the moment because of 
lack  of FIFO space, an appropriate error value will be  returned 
and no single byte will be sent.

Normaly,  an  opening flag is only needed for  the  first  frame. 
After  this,  the closing flag of the last frame is  already  the
opening flag of the next frame. The risk that comes with  leaving 
away the opening flag is that if the time between the two  frames 
is  bigger than a few seconds, the chances get higher that  noise 
bytes  are  received  that will make the next  frame  longer  and 
invalid.  The solution is to send a single frame flag  each  time 
after a few seconds silence on the line. This silence time  could 
be made configurable by the application program. One second might 
be a good default value. An alternative solution would be to send 
a new opening flag with the next frame if the last flag has  been 
transmitted more than a few seconds ago.

The  application  program might want to set the  following  para-
meters  (apart from standard things like baud rate  and  XON/XOFF 
usage):

    send FCS:              16 or 32 bit
    receive FCS:           same as send direction or both
    send transparency:     basic, flow-control or control
    receive transparency:  basic, flow-control or control
    send 7-bit transp.:    yes or no
    receive 7-bit transp.: same as send direction or both

There  are  2*3*2=12 different frame formats  available.  One  of 
these  has  to be selected for outgoing frames.  The  application 
program has to negotiate with the remote station which format  is 
used (depending on line characteristics). In order to allow nego-
tiation, it should be possible to set the driver in a mode  where 
all alternatives are accepted. If the CRC for received frames  is
not  fixed to the same used for outgoing frames, the driver  will 
first  check  whether the frame has a correct 16-bit FCS  and  if 
this fails (and there are more than 6 bytes between the flags) if 
it  is a correct 32-bit FCS. The same principle might be  applied 
with  the 7-bit transparency: try 8-bit mode at first and if  the 
FCS is (or both are) incorrect, try the 7-bit mode and check  the
FCS again.

The three levels of receive character transparency define,  which 
received  characters  are completely ignored. In basic  mode,  no 
byte is ignored, and in the other modes those bytes that have  to 
be  replaced in outgoing frames are discarded. If  XON/XOFF  flow 
control is selected between the modem and the computer, at  least 
the  flow-control transparency should be selected in both  direc-
tions.  In this way, no flow control characters will be sent  and 
the received ones are only used for flow control and not as  part 
of a frame.

The  most flexible mode for initial handshaking between  applica-
tion protocols might be:

    send FCS:              16 bit
    receive FCS:           both
    send transparency:     control
    receive transparency:  basic
    send 7-bit transp.:    yes
    receive 7-bit transp.: both

This mode is very unefficient and the FCS and 7-bit  transparency 
for received frames should be defined as soon as possible by  the 
application  program.  It  might be useful,  if  the  application 
program could determine the frame format (FCS and 7-bit  transpa-
rency) of the last received frame.

All  this  provides  a very powerful  and  flexible  transparency 
mechanism that will be succesful on nearly every possible connec-
tion. Under special circumstances, it might even be useful if the 
application  program could define with an array which bytes  have 
to be replaced in addition to the three defined sets, but this is 
not required by ISO 3309. Protocols like PPP support this option.

Some application programs might want to send their frame as  late 
as possible, because they want to include the latest packet  ack-
nowledge information for received frames or recent keystrokes  in 
the  next frame. The frame should not be sent too  late,  because 
otherwise not every millisecond of the connection would be  used. 
So  the  application needs a way to estimate the  time  that  the 
transmission FIFO will need to get empty or the actual FIFO size. 
It  seems  to be a good compromise, if  the  application  program 
sends the packet if the actual FIFO size is less than the  length 
of the next packet or a fixed limit.

It  might also be useful for the application program to  get  the 
time that has elapsed since the last flag byte has been received. 
In this way, it might detect a broken connection by timeout.

It is suggested, that drivers support frames containing data byte
sequences of at least 1040 Bytes. This will allow 1024 byte  user 
protocol  data units plus a reasonable amount of header  informa-
tion from higher layer protocols.


Appendix A: Fast Frame Check Sequence (FCS) Implementation
----------------------------------------------------------

The  following algorithm for the 16 bit FCS has been  copied  and 
slightly  modified  from RFC 1171. The author also  adapted  this 
code  to  get the 32 bit routines in section c) and d).  The  FCS
bytes  that have to be appended at the end of the frame  are  the 
complement of the return value beginning with the low order byte. 
[The 32 bit version has not been tested for compatibility yet!]

a) 16 bit FCS Computation Method

The following code provides a table lookup computation for calcu-
lating the Frame Check Sequence as data arrives at the interface.  
The table is created by the code in section b).

/*
 * 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 b).
 */
static u16 fcstab16[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 INITFCS16      0xffff  /* Initial FCS value */
#define GOODFCS16      0xf0b8  /* Good final FCS value */

/*
 * Calculate a new fcs given the current fcs and the new data.
 */
u16 crc16(fcs16, cp, len)
    register u16 fcs16;
    register unsigned char *cp;
    register int len;
{
    assert(sizeof (u16) == 2);
    assert(((u16) -1) > ((u16) 0));
    while (len--)
        fcs16 = (fcs16 >> 8) ^ fcstab16[(fcs16 ^ *cp++) & 0xff];

    return (fcs16);
}


b) Fast 16 bit 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 fcstab16[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");
}


c) 32 bit FCS Computation Method

/*
 * u32 represents an unsigned 32-bit number.  Adjust the
 * typedef for your hardware.
 */
typedef unsigned long u32;


/*
 * FCS lookup table as calculated by the table generator in section d).
 */
static u32 fcstab32[256] = {
   0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
   0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
   0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
   0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
   0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
   0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
   0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
   0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
   0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
   0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
   0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
   0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
   0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
   0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
   0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
   0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
   0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
   0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
   0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
   0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
   0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
   0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
   0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
   0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
   0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
   0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
   0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
   0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
   0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
   0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
   0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
   0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
   0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
   0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
   0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
   0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
   0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
   0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
   0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
   0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
   0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
   0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
   0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

#define INITFCS32      0xffffffff  /* Initial FCS value */
#define GOODFCS32      0xdebb20e3  /* Good final FCS value */

/*
 * Calculate a new fcs given the current fcs and the new data.
 */
u32 crc32(fcs32, cp, len)
    register u32 fcs32;
    register unsigned char *cp;
    register int len;
{
    assert(sizeof (u32) == 4);
    assert(((u32) -1) > ((u32) 0));
    while (len--)
        fcs32 = (fcs32 >> 8) ^ fcstab32[(fcs32 ^ *cp++) & 0xff];

    return (fcs32);
}


d) Fast 32 bit FCS table generator

The following code creates the lookup table used to calculate the 
FCS.

/*
 * Generate a FCS table for the HDLC 32 bit FCS.
 *
 * Markus Kuhn, University of Erlangen
 *
 * Code liberally borrowed from Mohsen Banan, D. Hugh Redelmeier
 * and Drew D. Perkins
 *
 */

/*
 * The HDLC polynomial: x**0 + x**1 + x**2 + x**4 + x**5 + x**7 + x**8 +
 *                      x**10 + x**11 + x**12 + x**16 + x**22 + x**23 +
 *                      x**26 + x**32 (0xedb88320).
 */
#define P       0xedb88320


main()
{
    register unsigned int b;
    register unsigned long v;
    register int i;

    printf("typedef unsigned long u32;\n");
    printf("static u32 fcstab32[256] = {");
    for (b = 0; ; ) {
        if (b % 6 == 0)
        printf("\n");

        v = b;
        for (i = 8; i--; )
            v = v & 1 ? (v >> 1) ^ P : v >> 1;

        printf("0x%08lx", v & 0xFFFFFFFF);
        if (++b == 256)
            break;
        printf(",");
    }
    printf("\n};\n");
}


Appendix B: More details about HDLC
-----------------------------------

This  appendix gives you some additional information that is  not 
required  to  implement  the HDLC framing mode but  might  be  of 
interest for you.

Many protocols separate the data byte sequence between the  open-
ing flag and the FCS in an address field, a control field and  an 
information field. Some control frames don't have an  information 
field. Normaly each of the address and control fields consists of
one  byte. The address field is intended to define for  which  of 
several stations connected to a line the frame has been sent.  On 
simple  point-to-point  connections, the address field  is  often 
used  to distinguish between several protocols or  carries  other 
information. E.g. the LAPB protocol uses the addresses 01h,  03h, 
07h and 0Fh and the Internet PPP uses only FFh. The control  byte
is used by the error correction protocols in order to distinguish 
the  different command and responses defined by the protocol  and 
the  information field carries the data transfered by  the  error 
correction protocol for higher layers.

HDLC  framing  is also defined for synchronous  lines.  The  only 
difference  to the asynchronous mode is that the start  and  stop 
bits  are left away and that the transparency algorithm is  simp-
ler. The sender will insert a 0 bit after five contiguous 1 bits. 
In  this  way, the flag 01111110 will never appear  in  the  data 
stream. The receiver examines the incoming bits for 5  contiguous
1 bits. If the next bit is a 0, then it will be discarded. If the 
next bits are 1 and 0 then a frame flag has been detected and  if 
the  next  bits are 1 and 1, then the whole frame  is  considered 
invalid and discarded.

All HDLC procedures are defined in the standards ISO 3309,  4335,
7478, 7776, 7809, 8471 and 8885.

References
----------

- Information  processing systems -- Data communication --  High-
  level  data link control procedures -- Frame structure,  Inter-
  national Organization for Standardization, ISO 3309-1984(E).

- Information  processing systems -- Data communication --  High-
  level data link control procedures -- Frame structure, Addendum
  1:  Start/stop  transmission,  International  Organization  for 
  Standardization, ISO 3309-1984/AD1(E).

- Information  processing systems -- Data communication --  High-
  level  data link control procedures -- Frame structure,  Amend-
  ment 2: Extended transparency options for start/stop  transmis-
  sion, International Organization for Standardization, ISO 3309-
  1991/Am2(E).


Author
------

Markus Kuhn
Schlehenweg 9
W-8525 Uttenreuth
Germany

Phone: +49 9131 52226

FAX: +49 9131 85-8503

Internet: mskuhn@immd4.informatik.uni-erlangen.de

Don't hesitate to contact me if you want to include HDLC  framing
in  a free serial line driver and have any questions or  suggest-
ions.

----------------------------------------------------------------------

Markus

-- 
Markus Kuhn, Computer Science student -=-=- University of Erlangen, Germany
Internet: mskuhn@immd4.informatik.uni-erlangen.de  |  X.500 entry available
-A distributed system is one in which the failure of a computer you didn't-
-even know existed can render your own computer unusable. (Leslie Lamport)-