Cell Relay Archive[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index][Thread Index][Author Index][Subject Index] Re: CRC-7 computation
--0-405580676-888105683=:9356
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Transfer-Encoding: 7Bit
In article <199711280713.XAA10531@jericho.one-o.com> C. M. Heard/VVNET, Inc.
<heard@vvnet.com> wrote, in response to a request for a CRC-7 program:
> I presume that you are looking for the CRC-7 used to compute the
> checksum for the 16-octet SDH path trace message, which has for
> its first octet 0x80 XOR'd with the path trace CRC-7 remainder for
> the previous frame's path trace message. In practice (because the
> path trace message is constant) this remainder is the same as the
> path trace CRC-7 remainder for the current frame; and according to
> G.709-1993, the latter is calculated by (a) clearing the CRC-7
> positions (7 LSBs) of the first octet and representing what remains
> as a polynomial m(x) over GF(2) with the most significant bit of the
> first octet being the highest order coeffiecient; and the (b) finding
> the remainder upon dividing (x^7 * m(x)) by the generator polynomial
> x^7 + x^3 + 1.
>
> Here is a program which I think does this. If any friendly listener
> could check this and send me some feedback, I'd be delighed.
Recently Kevin Wong <kwong@xylan.com> did this, and pointed out
that the program I originally posted produced results which did
not agree with the HP75000:
> Thank you very much for providing the code for computing the crc-7.
> I need to use it to calculate the checksum for the 15 byte trail trace
> ID for the E3 G.832 line type. [...] I've verified that the polynomial
> used by the E3 (G.832) is the same as the SDH, i.e. X^7 + X^3 + 1,
> [and that the] alogorithms specified in their respective spec.
> (ITU-T G.832 and G.707) are also identical.
[ ... ]
> For [the trail trace message whose last 15 characters are] "123456789ABCDEF"
> (your data), [the program you posted produces a first octet equal to 0x84.
> By contrast,] the HP-75000 will produce 0xE2 for the capture of which is
>
> E2 31 32 33 34 35 36 37 38 39 41 42 43 44 45 46
The program that I posted did indeed have a bug in the look-up table
algorithm used to generate and check the CRC-7 remainder. That bug
has been fixed, and a corrected program (followed by a set of context
diffs) has been attached to this article. Thanks to Kevin for spotting
the problem and for verifying that the corrected program agrees with
the HP7500 for a spectrum of test cases.
Mike
--
C. M. Heard/VVNET, Inc.
heard@vvnet.com
--0-405580676-888105683=:9356
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="crc7.c"
Content-Transfer-Encoding: 7Bit
Content-Description: Program to correctly generate & check E3/SDH path trace CRC
#define CRC7_POLYNOMIAL 0x89 /* x^7 + x^3 + 1 */
static unsigned char crc7_syndrome_table[256];
/*
* Generate a table of CRC-7 syndromes for x^7 * each possible input byte
*/
void
gen_crc7_syndrome_table (void)
{
int i, j, syndrome;
for (i = 0; i < 256; ++i)
{
syndrome = ((i & 0x80) != 0)? i ^ CRC7_POLYNOMIAL : i;
for (j = 0; j < 7; ++j)
{
if (((syndrome <<= 1) & 0x80) != 0)
{
syndrome ^= CRC7_POLYNOMIAL;
}
}
crc7_syndrome_table[i] = (unsigned char) syndrome;
}
}
/*
* Insert the CRC-7 into a 16-byte E.164 path trace message
*/
void
insert_crc7 (unsigned char *path_trace_message)
{
unsigned char crc7_accum = 0;
int i;
path_trace_message[0] &= ~0x7f;
for (i = 0; i < 16; ++i)
{
crc7_accum =
crc7_syndrome_table[(crc7_accum << 1) ^ path_trace_message[i]];
}
path_trace_message[0] ^= crc7_accum;
}
/*
* Check whether a 16-byte E.164 path trace message has a valid CRC-7 field
*/
int
crc7_OK (const unsigned char *path_trace_message)
{
unsigned char crc7_accum = crc7_syndrome_table[path_trace_message[0] & ~0x7f];
int i;
for (i = 1; i < 16; ++i)
{
crc7_accum =
crc7_syndrome_table[(crc7_accum << 1) ^ path_trace_message[i]];
}
return (crc7_accum == (path_trace_message[0] & 0x7f));
}
#include <stdio.h>
static unsigned char path_trace_message[] = "\200123456789ABCDEF";
int
main (void)
{
gen_crc7_syndrome_table();
insert_crc7(path_trace_message);
if (crc7_OK(path_trace_message))
{
printf("Valid CRC Byte = 0x%02X, Data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 0;
}
else
{
printf("Invalid CRC Byte = 0x%02X, Data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 1;
}
}
--0-405580676-888105683=:9356
Content-Type: TEXT/PLAIN; charset=US-ASCII; name="crc7.diff"
Content-Transfer-Encoding: 7Bit
Content-Description: Changes relative to original CRC-7 program
*** crc7.c Fri Nov 28 07:13:06 1997
--- crc7.c Wed Feb 18 16:24:23 1998
***************
*** 34,40 ****
path_trace_message[0] &= ~0x7f;
for (i = 0; i < 16; ++i)
{
! crc7_accum = crc7_syndrome_table[crc7_accum ^ path_trace_message[i]];
}
path_trace_message[0] ^= crc7_accum;
}
--- 34,41 ----
path_trace_message[0] &= ~0x7f;
for (i = 0; i < 16; ++i)
{
! crc7_accum =
! crc7_syndrome_table[(crc7_accum << 1) ^ path_trace_message[i]];
}
path_trace_message[0] ^= crc7_accum;
}
***************
*** 45,58 ****
int
crc7_OK (const unsigned char *path_trace_message)
{
! unsigned char crc7_accum = crc7_syndrome_table[path_trace_message[0] & ~0x7f]; int i;
for (i = 1; i < 16; ++i)
{
! crc7_accum = crc7_syndrome_table[crc7_accum ^ path_trace_message[i]];
}
return (crc7_accum == (path_trace_message[0] & 0x7f));
}
static unsigned char path_trace_message[] = "\200123456789ABCDEF";
int
--- 46,63 ----
int
crc7_OK (const unsigned char *path_trace_message)
{
! unsigned char crc7_accum = crc7_syndrome_table[path_trace_message[0] & ~0x7f];
! int i;
for (i = 1; i < 16; ++i)
{
! crc7_accum =
! crc7_syndrome_table[(crc7_accum << 1) ^ path_trace_message[i]];
}
return (crc7_accum == (path_trace_message[0] & 0x7f));
}
+ #include <stdio.h>
+
static unsigned char path_trace_message[] = "\200123456789ABCDEF";
int
***************
*** 64,76 ****
if (crc7_OK(path_trace_message))
{
! printf("Valid CRC Byte = %02x, data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 0;
}
else
{
! printf("Invalid CRC Byte = %02x, data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 1;
}
--- 69,81 ----
if (crc7_OK(path_trace_message))
{
! printf("Valid CRC Byte = 0x%02X, Data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 0;
}
else
{
! printf("Invalid CRC Byte = 0x%02X, Data = %s\n",
path_trace_message[0], &path_trace_message[1]);
return 1;
}
--0-405580676-888105683=:9356--
|
|