Slick CRC7 code

Go To Last Post
12 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Does anyone have a slick CRC7 routine that is small, quick, and doesnt use a lookup table. Something along the lines of this CRC16 routine:

unsigned int
CRC16(unsigned char *data, unsigned int length)
{
	unsigned int crc = 0;

	while(length--)
	{
		crc  = (unsigned char)(crc >> 8) | (crc << 8);
		crc ^= *data++;
		crc ^= (unsigned char)(crc & 0xff) >> 4;
		crc ^= (crc << 8) << 4;
		crc ^= ((crc & 0xff) << 4) << 1;
	}
	
	return(crc);
}

I started to dig into the workings so I could use the same theory for CRC7, but thought it best not to reinvent the wheel if its out there already (the real reaon: I feel like I am in number theory again and my brain is melting). Maybe someone would share if they had it? I have 2 version that work but, one is a solution that has a lot of branching and one is a lookup. Simple, elegant, clean, you have to respect that (even if you dont understand it).

Thanks,

Vern

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is a crc implementation for an SAE datastream:

unsigned char gen_crc(unsigned char *ptr, unsigned char count)
{
  unsigned char i, crc = 0xff;

  for (i = 0; i < count; i++)
  {
    unsigned char mask, data = *ptr++;

    for (mask = 0x80; mask != 0; mask >>= 1)
    {
      unsigned char poly = 0, adder = 0;

      if (data & mask)        /* case for new bit = 1 */
      {
        poly = 0x1c;          /* define the polynomial */
        adder++;
      }
      if (crc & 0x80)
        poly ^= 0x1d;
      crc <<= 1;
      crc += adder;
      crc ^= poly;
    }
  }
  return ~crc;
}

Dave Raymond

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

snafles wrote:
Does anyone have a slick CRC7 routine

Terminology clarification: The 16 in "CRC16" means 16 bits. Are you looking for a 7 bit CRC algorithm? Or are you really trying to find a CRC8 algorithm?

snafles wrote:
that is small, quick, and doesnt use a lookup table.

This is usually a tradeoff. If you want quick, go with a lookup table at the cost of some size. If you want small go with a loop style algorithm at the cost of speed. Pick your priority.

Have you tried searching Google? These are pretty common routines.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

EW wrote:
Terminology clarification: The 16 in "CRC16" means 16 bits. Are you looking for a 7 bit CRC algorithm? Or are you really trying to find a CRC8 algorithm?

Nope, I was talking about CRC7. They have been around a while now.

EW wrote:
This is usually a tradeoff. If you want quick, go with a lookup table at the cost of some size. If you want small go with a loop style algorithm at the cost of speed. Pick your priority.

They are all loops no matter which way you go. That CRC16 routine is pretty fast. Faster than a couple lookup routines I have seen. But still about twice as many instructions per loop as a good lookup. I really meant quick as in easy and simple, for example the CRC16 code I provided.

Quote:
Have you tried searching Google? These are pretty common routines.

snafles wrote:
I have 2 versions that work but, one is a solution that has a lot of branching and one is a lookup.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

what is the polynomial associated with the crc you're trying to compute? x^7+x^3+1?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

gizmo wrote:
what is the polynomial associated with the crc you're trying to compute? x^7+x^3+1?

x^7+x^3+1

I guess that would be very important information, huh? Sorry about that.

Vern

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

well, assuming 7 bit characters this might work:

unsigned char crc, data;

crc ^= data;
crc = (crc & 0x78) ^ (crc << 4) ^ (crc >> 3);
crc = (crc & 0x70>>1) ^ (crc << 3) ^ (crc >> 4);

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

or, even this

crc ^= data;
crc = (crc>>3) ^ (crc<<4);
crc ^= (crc & 0xf ) <<3;
crc = (crc>>4) ^ (crc<<3);
crc ^= (crc & 0x7) <<3;
crc &=0x7f;

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for the info gizmo, I will try them out after the holiday (4th of July in US).

Vern

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is the C code that I use (or was going to use) for calculating the CRC7 byte for a MMC command message. The CRC7 Poly is 0x89. The unsigned short value (treg) contains the working CRC value (upper byte) and the working data byte (lower byte). After every 8 shifts, a new data byte is loaded into the lower byte of the 16 bit register. This was a little easier than having to deal with rotating the carry from the data byte into the CRC.

The function inputs are the address of the first data byte and the number of bytes in the buffer. The function returns the CRC7 value with the MMC stop bit appended.

It's a little hard to read because of the True Type fonts.

unsigned char MMC_CalcCRC7(unsigned char *address, unsigned char ByteCount)
{
unsigned short treg;
unsigned char BitCount;

/****************************************************
* treg structure

* + + + + + + + + + + + + + + + + +
* |15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00|
* + + + + + + + + + + + + + + + + +
* | C| CRC | DATA |
* + + + + + + + + + + + + + + + + +
*
****************************************************/

treg = *address++ << 8;

for (; ByteCount != 0; ByteCount--)
{
treg |= *address++; // Merge data byte into lower byte of CRC-Data register

for (BitCount = 8; BitCount != 0; BitCount--)
{
if (treg & 0x8000)
treg ^= CRC7_Poly << 8; // if carry out of CRC, then EOR with Poly (0x89)

treg <<= 1; // Shift CRC-Data register left 1 bit
}
}

return (treg >> 8) | 0x01; // Add stop bit to CRC for MMC
}

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Gahelton!

Quote:
It's a little hard to read because of the True Type fonts.

This can be avoided by using the Code tag when posting.

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is the C code that I use (or was going to use) for calculating the CRC7 byte for a MMC command message. The CRC7 Poly is 0x89. The unsigned short value (treg) contains the working CRC value (upper byte) and the working data byte (lower byte). After every 8 shifts, a new data byte is loaded into the lower byte of the 16 bit register. This was a little easier than having to deal with rotating the carry from the data byte into the CRC.

The function inputs are the address of the first data byte and the number of bytes in the buffer. The function returns the CRC7 value with the MMC stop bit appended.

Lets see if this is easier to read than my previous post (using the code tag this time).

unsigned char MMC_CalcCRC7(unsigned char *address, unsigned char ByteCount) 
{ 
unsigned short treg; 
unsigned char BitCount; 

/**************************************************** 
* treg structure 

* + + + + + + + + + + + + + + + + + 
* |15|14|13|12|11|10|09|08|07|06|05|04|03|02|01|00| 
* + + + + + + + + + + + + + + + + + 
* | C| CRC | DATA | 
* + + + + + + + + + + + + + + + + + 
* 
****************************************************/ 

treg = *address++ << 8; 

for (; ByteCount != 0; ByteCount--) 
{ 
treg |= *address++; // Merge data byte into lower byte of CRC-Data register 

for (BitCount = 8; BitCount != 0; BitCount--) 
{ 
if (treg & 0x8000) 
treg ^= CRC7_Poly << 8; // if carry out of CRC, then EOR with Poly (0x89) 

treg <<= 1; // Shift CRC-Data register left 1 bit 
} 
} 

return (treg >>  | 0x01; // Add stop bit to CRC for MMC 
}