Aerospace Software Ltd.

Objective Real-Time Software on the ADSP21XX

HDLC Protocol Framing

General

HDLC framing is used in many applications, PPP links, Ethernet, X25, modems etc. In short, HDLC is used wherever a bit stream is used to transmit packetized data.

In this chapter, we present an HDLC frame receiver. Creating a frame transmitter is always easier than the receiver, since the transmitter is in control of the situation, so I'm not going to bother with that one, maybe I'll add it later. The difficult part is the receiver, since it has to synchronize with the received data bit stream and extract 8 bit bytes from it.

The complete HDLC protocol is a complicated beast, allowing for multiple messages to be outstanding, with a multiple message ack/nak system. It is consequently a quite efficient protocol, but many applications do not use the complete protocol, only the framing and once you have the framing right and can extract HDLC encapsulated messages, the rest is a lot easier.

This example was extracted from a real application and cleaned up to make it presentable. It is a multi channel beast, which in this case handles 4 channels of HDLC data. You can change it to handle any number of channels, by changing a single literal HD_CHAN_MAX. Effectively, this chapter provides all you need to create a multi channel HDLC protocol analyzer.

The HDLC Frame

The HDLC Frame consists of a data packet, surrounded by flag sequences. The flag sequence is unique and is binary 01111110 or hexadecimal 7EH. This is a pattern consisting of a leading 0, followed by 6 1s and then another 0. Hey! That can occur in a real life data pattern, so it's not unique! Hmm, well, yes and no. In practice, the data is twiddled just a wee bit, to prevent the data from ever resembling a flag sequence, so don't worry about it now.

To receive a packet of data, one has to scan for a start flag, then capture the message until one detects an end flag. The framer then sends the message up in the protocol stack and go look for the next message.

In practice, there are a few problems to bear in mind here. Firstly, there are no start/end flags, a flag, is a flag, is a flag. Furthermore, there may be only one or more flags between packets, and there may be abort sequences when the system is idle and doesn't have anything useful to transmit. (Some systems transmit 7EH flags when idle, others send FFH). Also, since the data is a bit stream, you can be sure that the data will never start/stop on byte boundaries, so complex bit shifting is required in the receiver to extract a byte stream from the raw data.

Abort Sequence

An abort sequence is any sequence with more than 6 consecutive 1s. Hey! Surely that can happen with real data? Yes it can, but the data is twiddled just a wee bit, to prevent the data from ever resembling an abort sequence, so don't worry about it now either. An abort should cause whatever the receiver is doing to terminate and go back to looking for a start flag. I have seen several HDLC systems where the designers did not allow for the abort sequence, causing weird results once in a while.

Cyclic Redundancy Check

HDLC encapsulated messages are usually also protected with a cyclic redundancy check. This is usually either the ITU-T CRC16 or CRC32. For messages with lengths up to 1 kilobyte, CRC16 is usually employed. There is a chapter on CRCs elsewhere in this book, so I'm not going to elaborate here, but I did add look-up table driven assembler routines for the CRC16 to it, so do go have a look.

Bit Stuffing

So, how do we handle those Flag and Abort turkeys? Easy, we stuff the turkey so it won't have any data resembling either a flag or an abort sequence.

Whenever the packet has 5 consecutive 1s, we stuff in a 0.

This stuffing has to be done in the transmitter after the message was protected with a CRC. Therefore, we have to remove the stuffing before we can recalculate the CRC.

Framer Code

The full source of the framer is on the CD-ROM in directory work\hdlc.

Initialization

Initialization of the framer is performed by procedure hd_init(), which will initialize the whole machine for all channels and should be called at startup. During operation, procedure hd_init_chan() is used to initialize a specific channel when an abort sequence is received. Procedure hd_reset_msg_ptr() is used to clear a channel message buffer.

HDLC Receiver

The HDLC framer in procedure hd_frame() has to keep track of a lot of detail. It grabs one byte of data at a time from the bit stream and saves it in a variable called hd_data_byte. It then runs in a loop over all 8 bits of this byte and keeps track of the number of consecutive 1s in the variable hd_one_count. If the current bit is a zero, it resets the 1 counter.

The framer assumes that the data is already in the variable hd_rx_data when this procedure is called. You have to supply the I/O handler which will probably be some interrupt driven thing and which may use a SPORT, PLD or USART, then call hd_frame for every byte of data received.

The data bits are packed into an output variable hd_rx_byte and it keeps track of the number of bits in this byte using variable hd_bit_count. As soon as 8 bits are reached, the rx byte is full, is appended to the receive message and the receive message length in hd_byte_count is incremented.

If the current bit is 0, it starts a sequence of tests:

If hd_one_count is 5, then this zero is stuffing and is discarded
If hd_one_count is 6, then this is a flag sequence and if hd_byte_count is zero, then this is a start flag, else it is an end flag and we have to test the crc
If hd_one_count is > 6, then this is an abort sequence and we have to reset all variables and start looking for a flag again.

Finally, if the CRC test passes with a result equal to F0B8H, then we have a message that can be sent up into the protocol stack. Obviously, if we haven't received a full set of bytes, then the CRC test is not going to pass and the message will be discarded.

Message Handler

The message handler procedure hd_analyze_msg() performs a rudimentary check on the message length before bothering to calculate the checksum. This can save a lot of processing time when things are going wrong. You have to insert your message handling code at the marker "YOUR CODE GOES HERE" in this procedure.

Hardware Solutions

One also get complete hardware solutions for HDLC framing. The framer chips will handle HDLC transmit/receive and CRC-16 generation/test and can be handy in some applications, but a software solution is always more fun.

Code Listing

Table 1 contains the HDLC Framer code listing.

Table 1. HDLC Framer Code Listing

/*********************************************************************
*
* Name:        HDLC.dsp
*
* Description: HDLC Framing Handler
*
* Copyright (c) 1996 Aerospace Software Ltd
*
* Revisions:
* -------------------------------------------------------------------
* 1.0       May 96      Herman Oosthuysen    
*
*
*********************************************************************/

#define HD
#include "macros.h"
#include "crc16.h"
#include "hdlc.h"
#undef HD

/********************************************************************
* Name:        hd_init
* Description: initialize the complete HDLC protocol machine
* Constraints: none
* Tested in simulator
********************************************************************/
hd_init: 
   MAC_ENTER
   
   /*
    * Zap all protocol machine variables
    */
   ay1 = ^hd_msg_buf; 
   l3 = 0; 
   m3 = HD_MSG_SIZE; 
   ax0 = 0; 
   ar = 0; 
   
   cntr = HD_CHAN_MAX; 
   do hd_init_loop until ce; 
   MAC_WR_DM ( ax0, ^hd_rx_byte, ar )
   MAC_WR_DM ( ax0, ^hd_rx_data, ar )
   MAC_WR_DM ( ax0, ^hd_bit_count, ar )
   MAC_WR_DM ( ax0, ^hd_byte_count, ar )
   MAC_WR_DM ( ax0, ^hd_one_count, ar )
   
   MAC_WR_DM ( ay1, ^hd_msg_ptr, ar )
   i3 = ay1; 
   modify ( i3, m3 ); 
   ay1 = i3; 
   ar = ar + 1; 
hd_init_loop: nop; 

   /* ----INITIALIZE YOUR VARIABLES HERE---- */

   MAC_EXIT
   rts; 
   
/********************************************************************
* Name:        hd_reset_msg_ptr
* Description: initialize msg pointer to start of msg buffer
* Constraints: ar = channel
* Tested in simulator and on ICE
********************************************************************/
hd_reset_msg_ptr: 
   MAC_ENTER
   
   ay0 = ar; 
   mr0 = ^hd_msg_buf; 
   mr1 = 0; 
   my0 = ay0; 
   mx0 = HD_MSG_SIZE; 
   mr = mr + mx0 * my0 ( UU ); 
   MAC_WR_DM ( mr0, ^hd_msg_ptr, ay0 )
   
   MAC_EXIT
   rts; 
   
/********************************************************************
* Name:        hd_init_chan
* Description: initialize the HDLC protocol machine for one channel
* Constraints: ar = channel
* Tested in simulator and on ICE
********************************************************************/
hd_init_chan: 
   MAC_QUICK_ENTER

   /*
    * reset all bit counters
    */ 
   ay0 = ar; 
   ar = 0; 
   MAC_WR_DM ( ar, ^hd_rx_byte, ay0 )
   MAC_WR_DM ( ar, ^hd_rx_data, ay0 )
   MAC_WR_DM ( ar, ^hd_bit_count, ay0 )
   MAC_WR_DM ( ar, ^hd_byte_count, ay0 )
   MAC_WR_DM ( ar, ^hd_one_count, ay0 )

   /*
    * reset the msg pointer to the start of the msg buffer
    */
   ar = ay0; 
   call hd_reset_msg_ptr; 

   /*
    * zap the msg buffer
    * (easier debugging if one can see the new msg uniquely)
    */
   ax1 = 0; 
   MAC_RD_DM ( ax0, ^hd_msg_ptr, ay0 )
   cntr = HD_MSG_SIZE; 
   do hd_init_chan_loop until ce; 
   MAC_WR_DM ( ax1, ax0, ay0 )
   ar = ax0 + 1; 
   ax0 = ar; 
hd_init_chan_loop: nop; 

   MAC_QUICK_EXIT
   rts; 
   
/********************************************************************
* Name:        hd_frame
* Description: Look for a HDLC flag sequence, collect data bits etc
* Constraints: ar = data, ay0 = channel
* Tested in simulator and on ICE
********************************************************************/
hd_frame: 
   MAC_QUICK_ENTER
   
   /*
    * Get the data and HDLC state
    * Assumes raw data is already in variable hd_rx_data
    */
   ax0 = ar; 
#if HD_DEBUG_RX
   call ut_hex_out2; 
   ar = ASC_COLON; 
   call ut_char_out; 
#endif 

   MAC_WR_DM ( ax0, ^hd_rx_data, ay0 )      /* ax0 = rx data */

   MAC_RD_DM ( ax1, ^hd_rx_byte, ay0 )      /* ax1 = rx byte */
   MAC_RD_DM ( mr0, ^hd_bit_count, ay0 )    /* mr0 = bit counter */
   MAC_RD_DM ( mr1, ^hd_one_count, ay0 )    /* mr1 = one_counter */
   
   /*
    * Process an 8 bit data byte
    * of PPP compatible HDLC data
    */
   cntr = HD_BYTE_SIZE; 
   do hd_frame_loop until ce; 
   ar = tstbit 0 of ax0;                    /* test LSB of received data */
   sr0 = ax0; 
   sr = LSHIFT sr0 by - 1 ( lo );           /* shift data and save it in ax0 */
   ax0 = sr0; 
   
   if eq jump hd_frame_flag0;               /* bit test - one or zero? */

   /*
    * received a 1 bit 
    */
hd_frame1: 
   sr0 = 0x0080;                            /* shift a 1 into the rx byte */
   sr1 = 0; 
   si = ax1; 
   sr = sr or LSHIFT si by - 1 ( lo ); 
   ax1 = sr0; 
   
   ar = mr0 + 1;                            /* increment bit counter */
   mr0 = ar; 

   ar = mr1 + 1;                            /* increment one counter */
   mr1 = ar; 

   ay1 = 7;                                 /* reset test (7 1s) */
   ar = ar - ay1; 
   if lt jump hd_frame_test_byte1; 
   ar = ay0; 
   call hd_init_chan;                       /* reset the channel */
   ax0 = 0; 
   ax1 = 0; 
   mr0 = 0; 
   mr1 = 0; 
   jump hd_frame_loop; 
   
   /* 
    * received a 0 bit 
    */
hd_frame0: 
   ay1 = 5;                                 /* 0 stuffing test (5 1s) */
   ar = mr1 - ay1; 
   if eq jump hd_wait_frame_test_byte0;     /* discard stuffing bit */
   
hd_frame_frame: 
   sr0 = ax1;                               /* shift a 0 into the rx byte */
   sr1 = 0; 
   sr = LSHIFT sr0 by - 1 ( lo ); 
   ax1 = sr0; 
   
   ar = mr0 + 1;                            /* increment bit counter */
   mr0 = ar; 

   ay1 = 6;                                 /* flag = 7E test (6 1s) */
   ar = mr1 - ay1; 
   if ne jump hd_frame_test_byte0; 
   MAC_RD_DM ( ar, ^hd_byte_count, ay0 )
   ar = pass ar; 
   ar = ay0; 
   if ne call hd_analyze_msg;               /* end flag - process message */
   
   /* Byte grabber is now synchronized! */
   mr0 = 0;                                 /* zero bit counter after a flag */
   ax1 = 0;                                 /* zero the rx byte */
#if HD_DEBUG_FLAG
   ar = ASC_f; 
   call ut_char_out; 
#endif 

   /* 
    * see whether 8 bits received 
    */ 
hd_frame_test_byte0: 
   mr1 = 0;                                 /* zero 1 counter */
   
hd_frame_test_byte1: 
   ay1 = 8;                                 /* 8 bit byte test */
   ar = mr0 - ay1; 
   if ne jump hd_frame_loop; 
   MAC_RD_DM ( ar, ^hd_byte_count, ay0 )
   ay1 = HD_MSG_SIZE;                       /* stop when msg buffer is full */
   af = ar - ay1; 
   if ge jump hd_frame_test_full; 
   ar = ar + 1;                             /* increment the byte counter */
   MAC_WR_DM ( ar, ^hd_byte_count, ay0 )

   m3 = 1; 
   l3 = HD_MSG_SIZE; 
   MAC_RD_DM ( ar, ^hd_msg_ptr, ay0 )
   i3 = ar; 
   dm ( i3, m3 ) = ax1;                     /* save the received byte */
   ar = i3;                                 /* in the msg buffer */
   MAC_WR_DM ( ar, ^hd_msg_ptr, ay0 )
   
#if HD_DEBUG_DATA
   ar = ax1; 
   call ut_hex_out2; 
   ar = ASC_SP; 
   call ut_char_out; 
#endif
hd_frame_test_full: 
   ax1 = 0;                                 /* zero rx byte */
   mr0 = 0;                                 /* zero bit counter */

   /* WEND */
hd_frame_loop: nop;                         /* loop back on rx nibble */

   /*
    * Save the HDLC protocol state
    */
hd_frame_done: 
   MAC_WR_DM ( ax1, ^hd_rx_byte, ay0 )      /* ax1 = rx byte */
   MAC_WR_DM ( mr0, ^hd_bit_count, ay0 )    /* mr0 = bit counter */
   MAC_WR_DM ( mr1, ^hd_one_count, ay0 )    /* mr1 = one_counter */

hd_frame_exit: 
   MAC_QUICK_EXIT
   rts; 
   
   
/********************************************************************
* Name:        hd_analyze_msg
* Description: Analyze the received message
* Constraints: ar = channel
********************************************************************/
hd_analyze_msg: 
   MAC_QUICK_ENTER

   /* 
    * Reset the port status timer whenever a msg is received
    * See whether the message is long enough, 
    * but not too long
    */
   ay0 = ar;                                /* Save port number in ay0 */

   MAC_RD_DM ( ax0, ^hd_byte_count, ay0 )   /* message too short? */
   ay1 = HD_MSG_MIN_SIZE; 
   ar = ax0 - ay1; 
   if le jump hd_analyze_msg_done; 
   
   ay1 = HD_MSG_SIZE;                       /* message too long? */
   ar = ax0 - ay1; 
   if ge jump hd_analyze_msg_done; 

   MAC_RD_DM ( ax0, ^hd_byte_count, ay0 )   /* decr length */
   ay1 = HD_HEADER_MSG_SIZE;                /* disregard header and crc */
   ar = ax0 - ay1; 
   MAC_WR_DM ( ar, ^hd_byte_count, ay0 )
   if le jump hd_analyze_msg_done;          /* quit if empty message */
   
   /* 
    * verify the CRC-16 
    * the CRC is inverted and byte swapped
    */
hd_analyze_msg_verify: 
#if HD_DEBUG_MSG
   ar = ASC_m; 
   call ut_char_out; 
#endif
   ar = ay0; 
   call hd_reset_msg_ptr; 
   
   MAC_RD_DM ( ax1, ^hd_msg_ptr, ay0 )      /* get start of msg buf */

   l3 = 0; 
   m3 = 1; 
   i3 = ax1;                                /* get start of msg buf */

   ay1 = ay0;                               /* Save port number in ay1 */
   ay0 = HD_CRC16_INIT;                     /* ay0 is the shiftreg = CRC */

hd_analyze_msg_crc: 
   cntr = ax0;                              /* length */
   do hd_analyze_msg_loop until ce;         /* calc CRC with 4808 poly */
   ar = dm ( i3, m3 ); 
   call cc_calc_crc;                        /* lookup table based CRC-16 */
   ay0 = ar; 
hd_analyze_msg_loop: nop; 
   ay0 = ay1;                               /* restore port number to ay0 */
   
   ay1 = HD_CRC16_CONST;                    /* compare with F0B8 */
   af = ar - ay1; 
   if ne jump hd_analyze_msg_crc_fail; 

   
   /*
    * CRC-16 is good:
    */
hd_analyze_msg_crc_pass: 
#if HD_DEBUG_MSG
   ar = ASC_g; 
   call ut_char_out; 
#endif
   /* 
    * switch on the msg opcode 
    * Packet Format:
    * Flag DD DD... CC Flag
    */
   MAC_RD_DM ( ar, ^hd_msg_ptr, ay0 )
   
   /* -------YOUR CODE GOES HERE-------- */




   /*
    * CRC-16 is BAD:
    */
hd_analyze_msg_crc_fail: 
#if HD_DEBUG_MSG
   ar = ASC_b; 
   call ut_char_out; 
#endif

   /* ----YOU MAY WANT TO ADD SOMETHING HERE---- */
   

   /*
    * Prepare for the next message packet
    */
hd_analyze_msg_done: 
   ar = ay0; 
   call hd_init_chan; 
   
hd_analyze_msg_exit: 
   MAC_QUICK_EXIT
   rts; 

   
   
.ENDMOD; 
/**************************** EOF - hdlc.DSP ***********************/

Header File

Table 2 contains the HDLC Framer header file.

Table 2. HDLC Framer Header File.

/*********************************************************************
*
* Name:        HDLC.h
*
* Description: HDLC Frame Handler
*
* Copyright (c) 1996 Aerospace Software Ltd.
*
* Revisions:
* -------------------------------------------------------------------
* 1.0       May 96      Herman Oosthuysen    
*
*
*********************************************************************/

/* Resolve public definitions */
#undef   PUBLIC
#undef   PROTOTYPE
#ifdef   HD
#define  PUBLIC      GLOBAL
#define  PROTOTYPE   ENTRY
#else
#define  PUBLIC      EXTERNAL
#define  PROTOTYPE   EXTERNAL
#endif

/***************************** Literals *****************************/
#define  HD_CHAN_MAX             0x0004
#define  HD_MSG_SIZE             0x0020   
#define  HD_BUF_SIZE             (HD_MSG_SIZE * HD_CHAN_MAX)

#define  HD_BYTE_SIZE            8
#define  HD_MSG_MIN_SIZE         0x0006


/***************************** Variables ****************************/
#ifdef HD
.VAR/DM/RAM/circ/SEG=INT_DM
   hd_msg_buf[HD_BUF_SIZE];
   
.VAR/DM/RAM/SEG=INT_DM
   hd_msg_ptr[HD_CHAN_MAX],
   hd_rx_byte[HD_CHAN_MAX],
   hd_rx_data[HD_CHAN_MAX],
   hd_bit_count[HD_CHAN_MAX],
   hd_byte_count[HD_CHAN_MAX],
   hd_one_count[HD_CHAN_MAX];


#endif

/****************************** Publics *****************************/
.PUBLIC
   hd_rx_byte,
   hd_rx_data,
   hd_bit_count,
   hd_byte_count,
   hd_one_count;

/***************************** Prototypes ***************************/
.PROTOTYPE
   hd_init,
   hd_init_chan,
   hd_frame,
   hd_analyze_msg,
   hd_reset_msg_ptr;
   
/**************************** EOF - HDLC.H **************************/