rfc1549.txt

RFC 的详细文档！


RFC 1549                      HDLC Framing                Decvember 1993


A.  Fast Frame Check Sequence (FCS) Implementation

   The FCS was originally designed with hardware implementations in
   mind.  A serial bit stream is transmitted on the wire, the FCS is
   calculated over the serial data as it goes out, and the complement of
   the resulting FCS is appended to the serial stream, followed by the
   Flag Sequence.

   The receiver has no way of determining that it has finished
   calculating the received FCS until it detects the Flag Sequence.
   Therefore, the FCS was designed so that a particular pattern results
   when the FCS operation passes over the complemented FCS.  A good
   frame is indicated by this "good FCS" value.

A.1 FCS Computation Method

   The following code provides a table lookup computation for
   calculating the Frame Check Sequence as data arrives at the
   interface.  This implementation is based on [9], [10], and [11].  The
   table is created by the code in section B.2.































Simpson                                                        [Page 13]

RFC 1549                      HDLC Framing                Decvember 1993


/*
 * 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.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 PPPINITFCS16    0xffff  /* Initial FCS value */
#define PPPGOODFCS16    0xf0b8  /* Good final FCS value */

/*



Simpson                                                        [Page 14]

RFC 1549                      HDLC Framing                Decvember 1993


 * Calculate a new fcs given the current fcs and the new data.
 */
u16 pppfcs16(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);
}

/*
 * How to use the fcs
 */
tryfcs16(cp, len)
    register unsigned char *cp;
    register int len;
{
    u16 trialfcs;

    /* add on output */
    trialfcs = pppfcs16( PPPINITFCS16, cp, len );
    trialfcs ^= 0xffff;             /* complement */
    cp[len] = (trialfcs & 0x00ff);  /* least significant byte first */
    cp[len+1] = ((trialfcs >> 8) & 0x00ff);

    /* check on input */
    trialfcs = pppfcs16( PPPINITFCS16, cp, len + 2 );
    if ( trialfcs == PPPGOODFCS16 )
        printf("Good FCS0);
}

A.2.  Fast FCS table generator

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












Simpson                                                        [Page 15]

RFC 1549                      HDLC Framing                Decvember 1993


/*
 * 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;0);
    printf("static u16 fcstab[256] = {");
    for (b = 0; ; ) {
        if (b % 8 == 0)
            printf("0);

        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("0;0);
}

Security Considerations

   As noted in the Physical Layer Requirements section, the link layer
   might not be informed when the connected state of physical layer is
   changed.  This results in possible security lapses due to over-
   reliance on the integrity and security of switching systems and
   administrations.  An insertion attack might be undetected.  An
   attacker which is able to spoof the same calling identity might be
   able to avoid link authentication.





Simpson                                                        [Page 16]

RFC 1549                      HDLC Framing                Decvember 1993


References

   [1]  Simpson, W., Editor, "The Point-to-Point Protocol (PPP)",
        RFC 1548, December 1993

   [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, Proposed Draft
        International Standard ISO 3309-1991/PDAD1, "Information
        processing systems - Data communication - High-level data link
        control procedures - Frame structure - Addendum 1: Start/stop
        transmission", 1991.

   [4]  International Organization For Standardization, ISO Standard
        4335-1979, "Data communication - High-level data link control
        procedures - Elements of procedures", 1979.

   [5]  International Organization For Standardization, ISO Standard
        4335-1979/Addendum 1, "Data communication - High-level data
        link control procedures - Elements of procedures - Addendum 1",
        1979.

   [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]  International Telegraph and Telephone Consultative Committee,
        CCITT Recommendation Q.922, "ISDN Data Link Layer Specification
        for Frame Mode Bearer Services", April 1991.

   [8]  American National Standards Institute, ANSI X3.4-1977,
        "American National Standard Code for Information Interchange",
        1977.

   [9]  Perez, "Byte-wise CRC Calculations", IEEE Micro, June, 1983.

   [10] Morse, G., "Calculating CRC's by Bits and Bytes", Byte,
        September 1986.

   [11] LeVan, J., "A Fast CRC", Byte, November 1987.

Acknowledgments

   This specification is based on previous RFCs, where many



Simpson                                                        [Page 17]

RFC 1549                      HDLC Framing                Decvember 1993


   contributions have been acknowleged.

   Additional implementation detail for this version was provided by
   Fred Baker (ACC), Craig Fox (NSC), and Phil Karn (Qualcomm).

   Special thanks to Morning Star Technologies for providing computing
   resources and network access support for writing this specification.

Chair's Address

   The working group can be contacted via the current chair:

      Fred Baker
      Advanced Computer Communications
      315 Bollay Drive
      Santa Barbara, California, 93111

      EMail: [e-mail]

Editor's Address

   Questions about this memo can also be directed to:

      William Allen Simpson
      Daydreamer
      Computer Systems Consulting Services
      1384 Fontaine
      Madison Heights, Michigan  48071

      EMail: [e-mail]





















Simpson                                                        [Page 18]