Computer Interfacing
Discussions about interfacing and electronics
 

Inquiry About HDLC CRC

Discerning HDLC CRC format for 2-way communication with existing devices


 

       Computer Interfacing Forum Index -> Error detection and correction
Author Message
shadowyfigure8
New User



Joined: 25 Jun 2008
Posts: 1
Location: Bannockburn IL, USA

Jun 25, 2008 7:25 pm

I am new to CRC, and would greatly appreciate some good advice on how to proceed with a basic problem. We have an immediate practical need to communicate with some existing devices using HDLC message frames, both inbound and outbound. According to documentation for this class of devices, the HDLC frames are supposed to use "CRC16". In the HDLC ISO standards document itself, its CRC format is not identified by name, but is said to use generator polynomial 0x1021 and remainder initialization 0xFFFF, like "CRC-CCITT", but then the one's complement of the resulting CRC value is appended to the data; at the message destination, the CRC calculation is done on BOTH the data AND the complemented number TOGETHER, and the result is supposed to match a special remainder constant 0x1D0F. I have other pieces of HDLC documentation variously identifying the format as either "CRC-16" or "CRC-CCITT" as well. The CRC numbers I'm getting however, out of an actual sample device, and their complements, seem to have no relation to the CRC-16 and CRC-CCITT values generated by Lammert Bies' calculator and other calculators, or their complements. In the document "Catalogue of Parameterized CRC Algorithms", the 19th example is called "CRC-16/ISO-HDLC", or "X-25". (My understanding is that "X.25" is not synonymous with "HDLC", and that it actually USES "LAPB", a specialized subset of HDLC.) This 19th example almost seems to fit what the standard says, but the final "magic remainder" to compare is given as 0xF0B8 rather than 0x1D0F. ???

Here are two sample HDLC messages, in hex, sent out of the actual device:

7E 08 91 87 44 7E
7E 08 B1 85 65 7E

The 0x7E bytes are HDLC frame delimiters, and I'm leaving them out of all calculations. In the first message, 0x0891 is the pair of bytes constituting the entire data payload, and 0x8744 is supposed to be the CRC number as a little-endian unsigned short. 0x8744 is what seems to have no relation to the various calculator results generated using 0x0891, or their complements. The 19th example in "Catalogue of Parameterized CRC Algorithms" (HDLC), with its Appendix A, also seems to say that the bits of the generated CRC value are "reflected" or reversed, but the numbers I get from "hand-un-reflecting" the bits myself don't seem to match anything either.

Some of the information I've seen on-line seems to imply that there are ways to discern the CRC format in use, and various constants and seed values, from observed results. Could anyone here point me in the right direction, or let me know if I've missed any important points? I've just done my very first perusal of the forum topics, and a number of them seem to be related. Could the device manufacturer be bypassing the HDLC standard and using a renegade format?
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Jun 30, 2008 6:24 pm

Hello shadowyfigure8, welcome to the forum and thank you very much for your post.

As you have seen, the HDLC algorithm is not yet included in the online calculator. The examples given however have valid HDLC CRC codes according to the entry in the catalogue.

The document "A Painless Guide to CRC Error Detection Algorithms", by Ross N. Williams, contains sample C code that will compile a compliant HDLC CRC generator based on the entry in the CRC Catalogue. There is also Lammert's library linked from the online calculator page.

Bear in mind that in a reflected algorithm the data bytes as well as the result are reflected. Compare with the "I-CODE" algorithm which differs only in the reflect option. When given a message of 10 89, I-CODE returns a CRC of E122 (=reflected 4487.) Likewise it gives the message 10 8D a CRC of A1A6 (=reflected 6585.) CRC-CCITT, which has no final inversion either, gives results of 1EDD (=complemented E122) and 5E59 (=complemented A1A6) respectively. In this way the HDLC CRC of a message can be derived from the CCITT CRC of the reflected message.

The magic remainder of F0B8 is quoted from the book "Numerical Recipes in C" by William H. Press, full reference in the catalogue. If each message+CRC pair is run through a compliant HDLC algorithm, the CRC is given as 0F47, which is the complement of F0B8.

HTH

Greg.
Guest








Jul 10, 2008 11:16 pm

Thank you Greg/regregex for your very helpful response. I think that the key piece for me was your remark:

"Bear in mind that in a reflected algorithm the data bytes as well as the result are reflected."

I've created C++ code for myself, using Lammert Bies' table-based CRC update routines and Sven Reifegerste's bit-reversal routine. I find it hard to believe that HDLC message handling hasn't been spelled out before in step-by-step detail already, in a form that is easier to digest than a formal specification. It seems that most people on the forum are approaching CRC handling all from a software perspective, and not assuming any hardware or firmware assistance. At this point, I'm aiming at handling HDLC messages just as Serial communications data, doing the encoding and decoding overhead myself explicitly. I'm working on a regular Windows PC, where integers are normally handled as little-endian. Also, I'm using more programmer-like terminology, such as "byte" rather than "octet".

I've just finished recreating my sample HDLC frames from data in its presumably original form, with the two data bytes bit-reversed from what was shown in the packets, and also decoding them as they were, including checking the CRC in "magic number" form. I was having fits, doing quadruple-head fakes, to keep all the steps of reflection, setting the number of bits being reflected, CRC-CCITT calculation, value complementing, and storage-order byte reversal in proper form and order, but it all seems to be happening OK.

My original two sample HDLC frames:

7E 08 91 87 44 7E
7E 08 B1 85 65 7E

With everyone's help, I'd like to compose something to "leave for posterity", so that implementing all of this might be a bit easier for folks in the future. Of course there could be any number of variations to the actual implemented procedures. For my own code, I've started with the approach that "outbound" HDLC messages are being transformed into a second "transmissible" message area before being sent, and that "inbound" ones are being transformed in place. I might make a judgment call and change this pattern.



Questions for the community:

* Is the "reflection" that we are implementing here with software functions typically an operation of an IC in communications hardware? If so, does it happen AS the message is being sent onto the communications line in that case, rather than BEFORE?

* Am I correct in my assumption that HDLC escape bytes of value 0x7D are reflected to 0xBE in a transmission-ready message, or is a 0x7D byte "already reflected" as-is? I haven't experimented with any HDLC message values that need to be escaped yet, even though I've coded for them.

* Have I gotten any other points wrong or out of sequence in my summary below? It all seems to work this way, but I want to be sure.



Important Points about HDLC message frame data and CRC calculation:

1. HDLC CRC calculation follows exactly the same algorithm and initialization pattern as does the 16-bit CRC-CCITT standard, EXCEPT for a complementing / bit inversion done to the finished CRC value after its last "remainder" calculation, and a subsequent "reflection" bit reversal operation done to it before it is sent or compared.

2. CRC calculation is done on the "original" byte values of the data, PRIOR to their conversion to "reflected" form in the payload of an HDLC message frame, NOT on the reflected values.

3. ALL DATA byte "reflection" bit reversal is done "byte-wise", i.e., one byte at a time. The values of HDLC frame delimiters (0x7E) and "idle flags" (0xFF) would be unchanged after reflection, WHETHER OR NOT they WERE reflected. HOWEVER, the CRC value is reflected "word-wise", i.e. according to its full 16-bit integer length (in the 16-bit case), NOT byte-by-byte, then THEREAFTER, being "little-endian", it appears in storage with its bytes swapped.

4. Different sources may refer to the operations of bit-inverting the CRC value, setting it to its own ones-complement, NOT-ing it, and exclusive-ORing it with 0xFFFF . These operations all amount to the same thing.


Encoding an HDLC message frame:

1. Begin with a data structure that matches the particular data payload format of HDLC that you need, such as 8-bit Address, 8-bit Control, n-bit Info., and 16-bit little-endian FCS. Set the address, control and information areas according to the needs of your application.

2. Allocate another data structure for a full HDLC message frame, with a similar data payload format, for creating the message frame in its "transmissible" form, and set its beginning and ending message delimiter bytes to 0x7E. Make the size of its data payload area twice the size of all the data items within it, to accommodate the remote possibility that EVERY data byte will need to be "escaped" by an extra preceding byte.

3. Initialize the "transmissible" frame's FCS CRC "remainder" value to all one-bits, e.g. 0xFFFF for a 16-bit FCS.

4. Encode: Working from the beginning of the data payload area of the original structure to the end, byte by byte, if any byte with a data value 0x7E is encountered, concatenate a byte with the value 0xBE (the bit-reversal of a 0x7D data transparency escape byte) to the data payload area of the new "transmissible" message frame, then concatenate a byte with the value 0x7A (0x5E bit-reversed) immediately after it. Similarly, for any data value 0x7D found, concatenate a 0xBE byte then a 0xBA byte (the bit-reversal of a 0x5D data byte) in the new frame. For all other data byte values, concatenate just one byte containing the bits of the original byte reversed. Update the CRC value with the original value of EACH data byte encountered, BEFORE its bits have been reversed, but NOT any escape bytes and following escaped values that may have replaced it.

5. Set the fully calculated FCS CRC value of the "transmissible" frame to its own one's-complement, then bit-reverse all the bits of the result (word-wise, all 16 bits), also in place.

6. "Shrink to fit": If the transformed and adjusted data payload does not fill the entire data area of the "transmissible" message structure, copy its finished FCS CRC value (in the 16-bit case) within it, then the message frame end-flag, back into the 3 bytes immediately following its last transformed data byte, and take note of the reduced message frame length.

7. Send the new "transmissible" HDLC message frame packet to its destination.


Decoding an HDLC message frame:

1. Begin with a data structure that matches the particular data payload format of HDLC that you need, such as 8-bit Address, 8-bit Control, n-bit Info., and 16-bit little-endian FCS. Bring an inbound HDLC message packet into the structure.

2. Determine the message area and length according to the positions of the 0x7E message delimiter bytes, but ignore them for decoding purposes.

3. Initialize a CRC variable, to check against the received frame's FCS CRC value, to all one-bits, e.g. 0xFFFF for a 16-bit FCS.

4. Decode: Working from the beginning of the entire data payload area of the frame to the end, byte by byte, INCLUDING the received FCS CRC value, if any 0xBE byte (the bit-reversal of a 0x7D data transparency escape byte) is encountered among the bytes found between the 0x7E delimiters, shift any remaining data payload bytes beyond it down one byte address, overwriting the 0xBE byte; if the first byte shifted has the value 0x7A, replace it with 0x7E as data, or if its value is 0xBA, replace it with 0xBE as data; reverse the bits of the replacement data value of the first byte shifted, in place, then update the CRC variable with the result; repeat as necessary during examination of the entire data sequence. Handle the CRC value just as if it were ANOTHER 2 DATA BYTES (in the 16-bit CRC case), IGNORING the fact that it was originally encoded by reversing all 16 bits at once. For each byte examined that is not involved in a two-byte escape sequence, just reverse its bits in place, then update the CRC variable with it. Updates to the CRC variable with each frame payload byte as it is encountered, excluding any 0xBE escape bytes, all should happen AFTER its byte's bits have been transformed to the original form they had before being transmitted from their source, with the exception regarding exactly how the FCS bytes are handled.

5. Set the fully calculated FCS CRC variable's value to its own one's-complement, then word-wise (all 16 bits) bit-reverse it in place.

6. Compare the finished CRC variable (in the 16-bit case), calculated INCLUDING the received FCS CRC value itself, and AFTER its bits have already been inverted and reversed, to the "magic remainder" value 0x0F47 (C/C++ literal value for the ones-complement of 0xF0B8, which is in turn the byte-wise bit-reversal of the literal value 0x1021 given in binary form by the HDLC specification). Accept the HDLC message frame as valid if the comparison is equal.

7. Make whatever use of the decoded payload data is appropriate to your application.
HDLC_CRC
Guest







Oct 29, 2009 11:53 am

Hi,

I am new to CRC generation and want to implement CRC generator for HDLC Layer 2 that's based on CCITT/ITUT Q.921 standard. From the ITUT specification, the CRC or as they call it FCS is calculated as follows:
1. The FCS field shall be a 16-bit sequence. It shall be the ones complement of the sum (modulo 2) of:
a) the remainder of xk (x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x +
1) divided (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, where k is the number
of bits in the frame existing between, but not including, the final bit of the opening flag and
the first bit of the FCS, excluding bits inserted for transparency; and
b) the remainder of the division (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, of
the product of x16 by the content of the frame existing between, but not including, the final
bit of the opening flag and the first bit of the FCS, excluding bits inserted for transparency.

As a typical implementation at the transmitter, the initial content of the register of the device
computing the remainder of the division is preset to all 1s and is then modified by division by the
generator polynomial (as described above) on the address, control and information fields; the ones
complement of the resulting remainder is transmitted as the 16-bit FCS.

As a typical implementation at the receiver, the initial content of the register of the device computing the remainder is preset to all 1s. The final remainder, after multiplication by x16 and then division(modulo 2) by the generator polynomial x16 + x12 + x5 + 1 of the serial incoming protected bits and the FCS, will be 0001110100001111 (1D0FH) (x15 through x0, respectively) in the absence of transmission
errors.

I tried the trick mentioned in the reply on Jun 30, 2008 6:24 pm on this topic, but that also does not help me.
Some example HDLC packets from the real time lab captures are as follows:
1. 7E 00 01 01 3F AE 76 7E
2. 7E 02 01 01 01 25 97 7E
3. 7E 00 01 01 0D 3F 64 7E
In the above examples, 7E are closing and ending flags and and last two bytes before closing flag is CRC.
Can you please help in finding out the right algorithm for this scenario?
Thanks in advance.
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Oct 30, 2009 12:22 pm

Hello HDLC_CRC,

Since my earlier post I have updated the CRC Catalogue entry for X.25, and found a code example in RFC 1171 appendix B. From your quotation the Q.921 algorithm looks to be the same as X.25. If you prefer, you can insert the parameters from the Catalogue into Lammert's CRC library (near bottom of page) or the code in the Painless Guide.

To get the results using Lammert's calculator, my trick still works:
  1. 7E 00 01 01 3F AE 76 7E, bytewise reflected=00 80 80 FC, output=8A91, inverted=756E, bytewise reflected=AE 76
  2. 7E 02 01 01 01 25 97 7E, bytewise reflected=40 80 80 80, output=5B16, inverted=A4E9, bytewise reflected=25 97
  3. 7E 00 01 01 0D 3F 64 7E, bytewise reflected=00 80 80 B0, output=03D9, inverted=FC26, bytewise reflected=3F 64
HTH

Greg
HDLC_CRC
Guest







Nov 02, 2009 11:07 am

Hi Greg,

Thanks a lot for your response. It really helped me understand the algorithm. I was trying reflections and inversion one at a time and not all at once.

Thanks again.

Below I am posting the basic algorithm for CRC-CCITT(FFFF), in Verilog for everyone's reference.
-----------------------------------------------------
`timescale 1ns / 1ps
module tb_checksum_shw();

reg clk_in= 1'b 1;
wire data_i;
reg [31:0]reg1= 32'h 008080fc;
reg rst_in;
reg [15:0]crc;
wire [15:0] fb;
reg [4:0]i;

parameter clk_64M = 15.625;

always
#(clk_64M/2) clk_in = ~ clk_in;


initial
begin
rst_in <= 1'b 0;

# 500
rst_in <= 1'b1;
end

assign data_i = (rst_in==1'b1) ? reg1[i] : 1'bz;

assign fb[0] = (rst_in==1'b 1)? (data_i ^ crc[15]) : 1'b1;
assign fb[1] = (rst_in==1'b 1)? crc[0] : 1'b1;
assign fb[2] = (rst_in==1'b 1)? crc[1] : 1'b1;
assign fb[3] = (rst_in==1'b 1)? crc[2] : 1'b1;
assign fb[4] = (rst_in==1'b 1)? crc[3] : 1'b1;
assign fb[5] = (rst_in==1'b 1)? (data_i ^ crc[4] ^ crc[15]) : 1'b1;
assign fb[6] = (rst_in==1'b 1)? crc[5] : 1'b1;
assign fb[7] = (rst_in==1'b 1)? crc[6] : 1'b1;
assign fb[8] = (rst_in==1'b 1)? crc[7] : 1'b1;
assign fb[9] = (rst_in==1'b 1)? crc[8] : 1'b1;
assign fb[10] = (rst_in==1'b 1)? crc[9] : 1'b1;
assign fb[11] = (rst_in==1'b 1)? crc[10] : 1'b1;
assign fb[12] = (rst_in==1'b 1)? (data_i ^ crc[11] ^ crc[15]) : 1'b1;
assign fb[13] = (rst_in==1'b 1)? crc[12] : 1'b1;
assign fb[14] = (rst_in==1'b 1)? crc[13] : 1'b1;
assign fb[15] = (rst_in==1'b 1)? crc[14] : 1'b1;

always @(posedge clk_in or negedge rst_in)
begin
if (rst_in == 1'b 0)
begin
crc <= 16'h ffff;
i<= 5'b11111;
end
else
begin
i<= i-1;
if(i == 5'b00000)
begin
i <= 5'b11111;
end
crc <= fb;
end
end
endmodule
----------------------------------------------------
raviksharma
New User



Joined: 22 Mar 2011
Posts: 2


Mar 22, 2011 6:56 am

hey guys. i am trying to do the same thing.. implementing crc for hdlc frame. somehow i cant get my head around this thing.

below is what standard (ITU T Q.921)says...
_______________________________________________________

2.7 Frame check sequence (FCS) field
The FCS field shall be a 16-bit sequence. It shall be the ones complement of the sum (modulo 2) of:

a) the remainder of xk (x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x + 1)
divided (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, where k is the number of bits in the
frame existing between, but not including, the final bit of the opening flag and the first bit of the FCS,
excluding bits inserted for transparency, and

b) the remainder of the division (modulo 2) by the generator polynomial x16 + x12 + x5 + 1, of the product
of x16 by the content of the frame existing between, but not including, the final bit of the opening flag and
the first bit of the FCS, excluding bits inserted for transparency.

As a typical implementation at the transmitter, the initial content of the register of the device computing the remainder of
the division is preset to all 1s and is then modified by division by the generator polynomial (as described above) on the
address, control and information fields; the ones complement of the resulting remainder is transmitted as the 16-bit FCS.

As a typical implementation at the receiver, the initial content of the register of the device computing the remainder is
preset to all 1s. The final remainder, after multiplication by x16 and then division (modulo 2) by the generator
polynomial x16 + x12 + x5 + 1 of the serial incoming protected bits and the FCS, will be 0001110100001111 (x15
through x0, respectively) in the absence of transmission errors.
____________________________________________________

Code:

/**********************************************************************
 *
 * Filename:    crc.h
 *
 * Description: A header file describing the various CRC standards.
 *
 * Notes:       
 *
 *
 * Copyright (c) 2000 by Michael Barr.  This software is placed into
 * the public domain and may be used for any purpose.  However, this
 * notice must not be changed or removed and no warranty is either
 * expressed or implied by its publication or distribution.
 **********************************************************************/

#ifndef _crc_h
#define _crc_h


#define FALSE   0
#define TRUE   !FALSE

/*
 * Select the CRC standard from the list that follows.
 */
#define CRC_CCITT


#if defined(CRC_CCITT)

typedef unsigned short  crc;

#define CRC_NAME         "CRC-CCITT"
#define POLYNOMIAL         0x1021
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE      0xFFFF   //0x0000 returns 0x1D0F
#define REFLECT_DATA      TRUE   //FALSE
#define REFLECT_REMAINDER   TRUE   //FALSE
#define CHECK_VALUE         0x1D0F

#elif defined(CRC16)

typedef unsigned short  crc;

#define CRC_NAME         "CRC-16"
#define POLYNOMIAL         0x8005
#define INITIAL_REMAINDER   0x0000
#define FINAL_XOR_VALUE      0x0000
#define REFLECT_DATA      TRUE
#define REFLECT_REMAINDER   TRUE
#define CHECK_VALUE         0xBB3D

#elif defined(CRC32)

typedef unsigned long  crc;

#define CRC_NAME         "CRC-32"
#define POLYNOMIAL         0x04C11DB7
#define INITIAL_REMAINDER   0xFFFFFFFF
#define FINAL_XOR_VALUE      0xFFFFFFFF
#define REFLECT_DATA      TRUE
#define REFLECT_REMAINDER   TRUE
#define CHECK_VALUE         0xCBF43926

#else

#error "One of CRC_CCITT, CRC16, or CRC32 must be #define'd."

#endif

extern crc  crcTable[256];

void  crcInit(void);
crc   crcSlow(unsigned char const message[], int nBytes);
crc   crcFast(unsigned char const message[], int nBytes);


#endif /* _crc_h */



Code:


/**********************************************************************
 *
 * Filename:    crc.c
 *
 * Description: Slow and fast implementations of the CRC standards.
 *
 * Notes:       The parameters for each supported CRC standard are
 *            defined in the header file crc.h.  The implementations
 *            here should stand up to further additions to that list.
 *
 *
 * Copyright (c) 2000 by Michael Barr.  This software is placed into
 * the public domain and may be used for any purpose.  However, this
 * notice must not be changed or removed and no warranty is either
 * expressed or implied by its publication or distribution.
 **********************************************************************/
 
#include "crc.h"


/*
 * Derive parameters from the standard-specific parameters in crc.h.
 */
#define WIDTH    (8 * sizeof(crc))
#define TOPBIT   (1 << (WIDTH - 1))

#if (REFLECT_DATA == TRUE)
#undef  REFLECT_DATA
#define REFLECT_DATA(X)         ((unsigned char) reflect((X), 8))
#else
#undef  REFLECT_DATA
#define REFLECT_DATA(X)         (X)
#endif

#if (REFLECT_REMAINDER == TRUE)
#undef  REFLECT_REMAINDER
#define REFLECT_REMAINDER(X)   ((crc) reflect((X), WIDTH))
#else
#undef  REFLECT_REMAINDER
#define REFLECT_REMAINDER(X)   (X)
#endif


/*********************************************************************
 *
 * Function:    reflect()
 *
 * Description: Reorder the bits of a binary sequence, by reflecting
 *            them about the middle position.
 *
 * Notes:      No checking is done that nBits <= 32.
 *
 * Returns:      The reflection of the original data.
 *
 *********************************************************************/
static unsigned long
reflect(unsigned long data, unsigned char nBits)
{
   unsigned long  reflection = 0x00000000;
   unsigned char  bit;

   /*
    * Reflect the data about the center bit.
    */
   for (bit = 0; bit < nBits; ++bit)
   {
      /*
       * If the LSB bit is set, set the reflection of it.
       */
      if (data & 0x01)
      {
         reflection |= (1 << ((nBits - 1) - bit));
      }

      data = (data >> 1);
   }

   return (reflection);

}   /* reflect() */


crc  crcTable[256];


/*********************************************************************
 *
 * Function:    crcInit()
 *
 * Description: Populate the partial CRC lookup table.
 *
 * Notes:      This function must be rerun any time the CRC standard
 *            is changed.  If desired, it can be run "offline" and
 *            the table results stored in an embedded system's ROM.
 *
 * Returns:      None defined.
 *
 *********************************************************************/
void
crcInit(void)
{
    crc            remainder;
   int            dividend;
   unsigned char  bit;


    /*
     * Compute the remainder of each possible dividend.
     */
    for (dividend = 0; dividend < 256; ++dividend)
    {
        /*
         * Start with the dividend followed by zeros.
         */
        remainder = dividend << (WIDTH - 8);

        /*
         * Perform modulo-2 division, a bit at a time.
         */
        for (bit = 8; bit > 0; --bit)
        {
            /*
             * Try to divide the current data bit.
             */         
            if (remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = (remainder << 1);
            }
        }

        /*
         * Store the result into the table.
         */
        crcTable[dividend] = remainder;
    }

}   /* crcInit() */


/*********************************************************************
 *
 * Function:    crcFast()
 *
 * Description: Compute the CRC of a given message.
 *
 * Notes:      crcInit() must be called first.
 *
 * Returns:      The CRC of the message.
 *
 *********************************************************************/
crc
crcFast(unsigned char const message[], int nBytes)
{
    crc              remainder = INITIAL_REMAINDER;
    unsigned char  data;
   int            byte;


    /*
     * Divide the message by the polynomial, a byte at a time.
     */
    for (byte = 0; byte < nBytes; ++byte)
    {
        data = REFLECT_DATA(message[byte]) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }

    /*
     * The final remainder is the CRC.
     */
    return (REFLECT_REMAINDER(remainder) ^ FINAL_XOR_VALUE);

}   /* crcFast() */



Code:

/**********************************************************************
 *
 * Filename:    main.c
 *
 * Description: A simple test program for the CRC implementations.
 *
 * Notes:       To test a different CRC standard, modify crc.h.
 *
 *
 * Copyright (c) 2000 by Michael Barr.  This software is placed into
 * the public domain and may be used for any purpose.  However, this
 * notice must not be changed or removed and no warranty is either
 * expressed or implied by its publication or distribution.
 **********************************************************************/

#include <stdio.h>
#include <string.h>

#include "crc.h"


static const unsigned short crc_itu16_table[] =
{
    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
};


int crc_itu16_check(const unsigned char *buf, int len)
{
    unsigned short crc;
    int i;

    crc = 0xFFFF;
    for (i = 0;  i < len;  i++)
        crc = (crc >> 8) ^ crc_itu16_table[(crc ^ buf[i]) & 0xFF];
    return (crc & 0xFFFF) == 0xF0B8;
   //return (crc ^ 0xF0B8) == 0x0000;
}
/*- End of function --------------------------------------------------------*/


void
main(void)
{
   //unsigned char  test[] = {0x40, 0xc0, 0x80, 0x52, 0x52, 0x7b, 0x00, 0x00} ;
   //unsigned char  test[] = {0x45, 0x34, 0xf4, 0xb6, 0xa2, 0x5c, 0x7b, 0xd3, 0x00, 0x00} ;
   unsigned char  test[] = {0x11, 0x33, 0x22, 0xaa, 0x00, 0x00} ;
   unsigned char  msg[100] = {0};
   int i, len;
   unsigned short crcin, crcout;


   
   crcInit();
   crcin = crcFast(test, (sizeof(test)-2));

   test[sizeof(test)-2] = crcin&0x00FF;
   test[sizeof(test)-1] = (crcin>>8)&0x00FF;

   // send data


   //at recv side
   for(i = 0; i< sizeof(test); ++i)
      msg[i] = test[i];
   len = i;



   for (i = 0;  i < len;  i++)
        printf("%02X ", msg[i]);
    printf("\n");

   crcout = crcFast(msg, len+2);
   printf("%02X ", crcout);


   if (crc_itu16_check(msg, len))
        printf("CRC is OK\n");


}   


for all test inputs - crc_itu16_check returns OK(so i am hoping.. i am sending correct crc) and crcout is always 0xFCDE, some sort of magic number.. but i cant find it anywhere.. besides need 0x1D0F.

also.. how do you generate this "crc_itu16_table". is it a good idea to increase its size to 2^16.. i have plenty of memory.

thanks
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Mar 23, 2011 2:23 pm

Hello raviksharma, welcome to the forum!

Regarding the test result, BB 50 is the correct CRC, however the residue value in the X.25/Q.921 algorithm is 0x0F47, not 0x1D0F. (For the record, the CHECK_VALUE in crc.h:39 should be 0x906E).

The value 0xFDCE comes from the test program processing two excess bytes in the test string: notice that on the sending side, crcFast() is called with a length argument of 4, but on the receiving side the argument is 8 when it should be 6. crcFast() would return 0x0F47 for a length of 6, but after processing the extra characters (both zero) the 'magic number' is changed to 0xFDCE.

The crcInit() function contains the code to fill a CRC lookup table. The program contains two tables: crcTable[], used by crcFast(), and crc_itu16_table[], used only by crc_itu16_check(). There is no reason for this, it could be changed to use just one or the other. However their contents are different and in fact the following relation holds:
Code:
crc16_itu_table[reflect(i, 8)] == reflect(crcTable[i], 16)

All crcInit() does is calculate the CRCs of 256 single bytes (the index) by the slower, bit-by-bit algorithm. Only the polynomial division part is performed; INITIAL_REMAINDER, FINAL_XOR, REFLECT_DATA and REFLECT_REMAINDER are dealt with in crcFast().

For another C program that will generate such a table, see chapter 20 of "A Painless Guide to CRC Error Detection Algorithms" by Ross Williams.

crcFast() could certainly be adapted to use a 64K table, but I'm not sure how to do it right now.

Best of luck,

Greg
raviksharma
New User



Joined: 22 Mar 2011
Posts: 2


Mar 29, 2011 2:10 pm

Thanks regregex.
highly appreciate it. and that guide by Ross Williams is a life saver.
chicocanha2
Guest







Jun 16, 2011 6:27 pm

Hey there,

I'm capturing the following packet out of a device:

0x7e 0x55 0x33 0x55 0x33 0xD9 0xCE 0x7e (AACCAACC + CRC)

This is supposed to be a HDLC packet... nevertheless, the CRC doesn't look OK (although it is accepted as a good packet). The trick of using lammert's calculator doesn't work for it. Any ideas if this is a variation of the standard HDLC CRC algorithm?
regregex
Preferred Member



Joined: 30 Oct 2007
Posts: 184
Location: London, UK

Jun 18, 2011 8:03 pm

Hello chicocanha2,

The CRC used on that packet is indeed a variation of the HDLC algorithm, known as CRC-16/GENIBUS. The difference is that the Genibus algorithm is not reflected, i.e. the shift register shifts left.

The Genibus CRC in turn is related to the 'false CRC-CCITT' algorithm included in Lammert's calculator. If you enter 55 33 55 33 in Hex, the calculator returns "CRC-CCITT (0xFFFF) 0x2631". XORing this value with 0xffff yields 0xd9ce, the Genibus CRC for the packet.

HTH

Greg
Dennytes
Guest







Dec 15, 2012 7:28 pm

Hallo to everyone,

All these comments were helpfull to understand the calculation of many different crc solutions.

But i'm still stuck finding the right one for my modem packets.

This is te first packet received from the modem (siemens mc35) after the gprs dial command:
7e3f7d233f217d217d237d207d397d227d267d207d2a7d207d207d277d227d287d227d257d263f433f3f7d237d253f237d253f3f7e

same packet with flags removed and escaped:
3f033f21010300190206000a00000702080205063f433f3f03053f23053f3f

I can't calculate the 3f3f myself.
I also understand that the last two bytes should not be included in the calculation.

The calculated checksum i get is 7e4f it is done like the rfc describes.
Hope someone can help me out with this.

Thanks in advance!
Dennis.
Guest








Dec 18, 2012 12:09 am

Hi guys,

I found what was going wrong here.
The CRC calculation was going totally right. Only the byts from the serialport were not parsed into a string like i suspected.
The function "serialPort1.ReadExisting();" in c# is using ascii(7bit) encoding as default, so i did use the wrong data to calculate the checksum on.
I also tryed to change the encoding to utf8
with the following statement: serialPort1.Encoding = Encoding.UTF8; (before opening)
And this also did not give the result i was looking for. So i decided to use hyperterminal.

packet captured with hyperterminal and hex file viewer: (this is the right data)
7EFF7D23C0217D217D237D207D397D227D267D207D2A7D207D207D277D227D287D227D257D26BC5B9D247D237D25C2237D257D39407E

flags removed and escaped:
FF03C021010300190206000A0000070208020506BC5B9D240305C22305 1940

now i can also calculate the checksum / crc: 1940
Smile Smile Smile

maybe this will help someone...

Greetings,
Dennis.
moldrak
New User



Joined: 27 Dec 2012
Posts: 1


Dec 27, 2012 4:47 pm

Hi there,

i'm new with CRC and i've got some problem to calculate one.

Here a frame from serial port:

7E 12 5F 1B DE 09 C0 E2 48 F9 00 00 3E 00 2B 8F 7E

using this documentation: "rfc1662 from w.Simpson", i made some function for calculate crc but i can't find the good one (0x2B8F).

i try many crc generator (this one for exemple: "zorc.breitbandkatze") but i have never found the good one.

for my test i used 125F1BDE09C0E248F900003E00 with this parameter:

CRC polynom (hex) 8408
Initial value (hex) ffff
Final XOR value (hex) f0b8

I think i forgot something or i used some wrong input data.

thanks for any help !

       Computer Interfacing Forum Index -> Error detection and correction
Page 1 of 1



Running on php BB © 2001, 2009 php BB Group
   Lammert Bies     Interfacing     Sitemap     Forum