NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/protocol/iso/1057

Text File | 1992-08-26 | 25.7 KB | 633 lines

Newsgroups: comp.protocols.iso
Path: sparky!uunet!gatech!darwin.sura.net!Sirius.dfn.de!fauern!fauna!mskuhn
From: [e-mail] (Markus Kuhn)
Subject: Re: Info on Async HDLC wanted
References: <[e-mail]>
Message-ID: <[e-mail]>
Organization: CSD., University of Erlangen, Germany
Date: Wed, 26 Aug 1992 15:12:06 GMT
Keywords: HDLC, Async, datalink, RS-232
Lines: 621

[e-mail] (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: [phone]

FAX: [phone]

Internet: [e-mail]

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: [e-mail]  |  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)-