Teensy CRC Generator/Checker

Status
Not open for further replies.

TelephoneBill

Well-known member
Looking in the Freescale reference manuals, I spotted that the various chips have hardware CRC generation/checking capability.

I'm looking to test 14 bit CRCs from a radio experiment. I notice that in the manual, the hardware refers to CRC-16 and CRC-32.

Does anyone know if this hardware can be used for CRCs other than 16 bit or 32 bit? I suspect not...
 
Hmmmm. I wonder what you're up to :)

I vaguely remember looking at the hardware to see if it could do CRC14 and concluding that it couldn't so I wrote a routine to do the CRC14 used by the FT8 and FT4 protocols.
Code:
// Modify crc_gen to try for a routine which can be told to do
// a CRC over a specified number of bits, rather than bytes
// The polynomial crc_p must be specified in explicit+1 format
// Note that Koopman uses implicit +1 format
uint32_t crc_gen_bits(uint16_t crc_size, uint32_t crc_p, uint8_t *data, uint32_t data_bit_size)
{
  uint32_t crc_acc = 0;
  uint32_t crc_poly = crc_p;
  int i;
  uint32_t byte_count;
  if (!(crc_poly & 1)) {
//      printf("ERROR: an explicit+1 poly MUST be odd (low order bit set) 0x%X\n", crc_poly);
      // as good an error return value as any other
    return 0xDEADBEEF;
  }

  if (data_bit_size == 0) {
//    printf("ERROR: data_bit_size is zero\n");
    return 0xBEEFDEAD;
  }

  if ((crc_size == 0) || (crc_size > 24)) {
//    printf("ERROR: invalid crc_size is zero or >24\n");
    return 0xBEADDEAF;
  }
  // shift the polynomial up to the 24 bit mark
  crc_poly <<= 24 - crc_size;

  // Load the first 3 bytes into the crc accumulator
  for (i = 0; i < 3 && i < ((int)data_bit_size + 7) / 8; i++) {
    crc_acc <<= 8;
    crc_acc |= *data++;
  }
  // If there's less than 3 bytes of data, shift zeroes in
  // for the remaining bytes
  for (; i < 3; i++)crc_acc <<= 8;

  byte_count = 3;

  // For each bit in the message.
  for (i = 0; i < (int)data_bit_size /*- crc_size*/; i++) {
    crc_acc <<= 1;
    if (crc_acc & 0x1000000) {
      crc_acc ^= crc_poly;
    }
    // If we have just processed the 7th bit then we
    // need to load another byte
    if ((i & 7) == 7) {
      if (byte_count < (data_bit_size + 7) / 8) {
        crc_acc |= *data++;
      }
      byte_count++;
    }
  }
  crc_acc &= 0xffffff;
  crc_acc >>= 24 - crc_size;
  return (crc_acc);
}

// This will return the 14-bit CRC result
unsigned short crc14(unsigned char *data, int length)
{
	return(crc_gen_bits(14, 0x2757, data, 82));
}

Pete
 
Great stuff Pete. Will give it a try asap. Thanks too Frank - I will look at your work on FastCRC to see if I can mod for CRC14.

I'm back working on LORAN C (eLORAN) to decode the Loran Data Channel. Its encoded with Eurofix protocol and has data, reed solomon FEC, and CRC14 messages. Messages are only 210 bits long and can give differential GPS and GLONASS data - plus UTC. There is also an SMS type message (several consecutive 210 bits), so I'm curious to see what this contains.

Using the Teensy Comparator (CMP1 which I only discovered recently), I can take the output directly from a ferrite loop, through an FET and two stage op-amp. The analogue out is a healthy 2 volts pk-pk and gives a very nice burst from the comparator of two groups of pulses, simulating Master and Slave transmissions (both from Anthorn in Cumbria). The data is within slave pulses P3 to P8 and uses 3 state symbols of phase modulation (-1 uS, o, +1uS), which Eurofix translates into 7 bit characters.

I've got the data working as 7 bits stored as 8 bits, but I cannot tell where one message ends and the next one starts. So my plan is to test each data character as a CRC of the previous 29, and this should reveal a general start/stop pattern - which then allows me to parse correctly into messages.

Does anyone know if the US are still experimenting with eLORAN? If so on which coast?
 
if you tell me the name and the parameters (like "width=14 poly=0x0805 init=0x0000 refin=true refout=true xorout=0x0000 check=0x082d residue=0x0000 name="CRC-14/DARC") I can try it - ( not sure if 14BIT are possible in Hardware, but I want to give it a try )

The "check"-value is the CRC of the ascii-string "123456789" (without ' " ')

Edit: Would be good if you could give me some more teststrings and their CRCs.

http://reveng.sourceforge.net/crc-catalogue/
 
Last edited:
I'll try to dig up some more but here's one test string:
Code:
#include "my_crc14.h"
uint8_t test[] = {0x29,0x66,0x1A,0xBE,0x74,0x6D,0x2A,0x31,0x48,0x28,0x00,0x00};

void setup(void)
{
  Serial.begin(9600);
  while(!Serial);

// Prints 0x28DC (correct)
  Serial.printf("crc14 = 0x%02X\n",crc14(test,sizeof(test)));
}

void loop(void)
{
}

Pete
 
Frank, Pete - thanks very much for your interest and help. I'll tell you what I know so far. I'm on a steep learning curve...

Each Eurofix "Message" format is 210 bits long - that's 30 times 7 bit characters. Its structure is 70 bits of Application Data, followed by 140 bits of Reed-Solomon FEC. The Application Data is composed of MESSAGE_TYPE (4 bits), MESSAGE_CONTENT (52 bits), CRC (14 bits). Total MESSAGE Application Data equals 70 bits, and the CRC is protecting just the 56 bits previous.

The 7 bit characters are elements of a Galois Field GF(128) - that's how a purist mathematician would describe them. I would simply refer to these as the hexadecimal set from 0 to 7F. There is a table mapping from "6 symbols" of modulation to hex (e.g. "0 0 + - - +" equals 0x2D) but I already perform this translation inside Teensy on the fly, so I hold the 7 bit data as a hex number in a byte array. I simply drop the hex into an 8 bit byte, which is then part of a larger "data array" of type byte. In real time, its easier to do it this way now rather than to try concatenate a long bit string adding 7 bits each time. There is a lot happening in real time inside an ISR (not least of which is a precision phase locked 100 KHz sq wave), but that may change in the future. The spec says that the least significant symbol is transmitted first - so I'm hoping that I have performed the translation correctly (but it could be the other way around). You would expect "little endian" for serial data.

So the test data I can give you is a list of bytes, where the m.s. bit is never set. This list is in time order of arrival. But I cannot yet say where in this list sits the CRC - reason: I don't have any "start" or "stop" information of where a MESSAGE begins and ends. Its a 14 bit CRC, so there will be two of my bytes that make it up. It is possible that the "Message" sits within a DATA LINK layer (as Ethernet stuff does with the "01111110" flags) and there may be 7 bit characters wrapped around the "Message", but I don't have that spec, and its not obvious from inspecting the data that this is so. I cannot see an obvious pattern.

My strategy therefore is to trawl through the data testing pairs of 7 bits as a possible CRC for the 56 bits which precede them (56 bits followed by CRC of 14 bits). There should be a pattern emerge if I can find it, but its a little like looking for "needles in a haystack".

The CRC14 uses this polynomial... x^14 + X^13 + x^7 + x^5 + x^4 + 1. I calculate this to be "0x60B1" or "110000010110001".

Here is some data in time order and lines of 30 Bytes... (I was hoping to see a pattern but I can't. There should be at least six messages in here.)... There may be some errors too (its a very noise channel), but I'm using averaging of 20 cycles of pulse per 6 symbols in making phase decisions, so I don't expect many...

0x18,0x18,0x07,0x50,0x5D,0x5D,0x61,0x4D,0x63,0x64,0x7C,0x15,0x42,0x01,0x1D,0x6C,0x59,0x2A,0x60,0x59,0x35,0x35,0x59,0x68,0x70,0x58,0x32,0x66,0x49,0x2B,
0x15,0x0A,0x41,0x27,0x70,0x55,0x47,0x37,0x4A,0x5D,0x0F,0x45,0x4F,0x2B,0x59,0x16,0x35,0x7B,0x36,0x3F,0x47,0x75,0x4D,0x51,0x67,0x21,0x6D,0x4D,0x1D,0x4D,
0x4F,0x14,0x77,0x7F,0x2E,0x5A,0x3A,0x11,0x11,0x35,0x1A,0x6A,0x2C,0x6A,0x52,0x41,0x3A,0x31,0x34,0x3F,0x52,0x40,0x1E,0x22,0x20,0x41,0x6E,0x14,0x15,0x22,
0x27,0x0D,0x73,0x59,0x5D,0x2B,0x67,0x1A,0x39,0x1D,0x45,0x7C,0x5B,0x1B,0x76,0x29,0x3E,0x65,0x25,0x56,0x03,0x72,0x60,0x1C,0x53,0x64,0x09,0x4E,0x53,0x2E,
0x4D,0x4E,0x75,0x52,0x31,0x32,0x0B,0x2A,0x3F,0x18,0x5B,0x57,0x59,0x34,0x76,0x1A,0x0A,0x5E,0x5F,0x3B,0x56,0x59,0x4C,0x6B,0x5B,0x59,0x79,0x77,0x3A,0x71,
0x7A,0x48,0x41,0x4D,0x1F,0x2E,0x7D,0x42,0x2B,0x5A,0x58,0x2C,0x16,0x25,0x59,0x35,0x3F,0x2C,0x3F,0x52,0x24,0x7B,0x58,0x62,0x11,0x34,0x62,0x2A,0x31,0x7D,
0x7B,0x32,0x7D,0x35,0x14,0x28,0x57,0x47,0x33,0x59,0x1F,0x11,0x18,0x39,0x1B,0x31,0x56,0x4F,0x38,0x6B,0x60,0x43,0x2B,0x6A,0x16,0x27,0x2F,0x7E,0x1A,0x7E

It would pay me to have some simple test data first for the CRC14, and that's what I'm looking at currently using Pete's software algorithm.

regards, Bill
 
@Frank B: Here's 6 more test strings and their CRC

Code:
0x4F, 0x76, 0x4C, 0xA4, 0xE2, 0x61, 0x2F, 0xF2, 0x65, 0xB0, 0x00, 0x00, 
crc14 = 0x2F7A

0x4A, 0x5E, 0xD7, 0xD4, 0xE3, 0x33, 0x6E, 0xDD, 0xE9, 0xE0, 0x00, 0x00, 
crc14 = 0x01D9

0x4E, 0x81, 0x44, 0x7B, 0x88, 0x66, 0xBC, 0xCA, 0x6C, 0xB0, 0x00, 0x00, 
crc14 = 0x16EA

0x4A, 0x5E, 0xD7, 0xD3, 0xE2, 0x03, 0x09, 0x5C, 0x44, 0x60, 0x00, 0x00, 
crc14 = 0x1FCF

0x4C, 0x4A, 0xB0, 0xD0, 0x72, 0x9B, 0x74, 0x52, 0x67, 0xB0, 0x00, 0x00, 
crc14 = 0x22EE

0x3A, 0x2D, 0x5D, 0x94, 0xFE, 0x64, 0x04, 0x82, 0x65, 0xF0, 0x00, 0x00, 
crc14 = 0x132D

Pete
 
@ TelephoneBill: I haven't tested that crc code with anything other than the 77 bit messages in the FT4 protocol. I'll try to verify that it works for 56 bit messages in the next day or so.

Pete
 
I noticed a tiny glitch in your wrapper function in post #2, in case anyone copies it verbatim.

You have left a fixed integer of '82' in your call to crc_gen_bits, instead of using the "length" parameter passed in the crc14 call. Also, is "length" a reserved word in Teensyduino ? - it gets coloured orange in my Arduino IDE.

Appreciate your time/effort - I have learnt a lot from just looking at your code (don't claim any great expertise with 'c' - pascal was my apprenticeship).
 
I have CRC-14/DARC working - turned out to be easy, only the bitshifts for polynom and seed need to be adjusted for CRC-14:

(in fastCRC, it will look like this - other code similar to crc-16)
Code:
/** CRC-14/DARC
 * @param data Pointer to Data
 * @param datalen Length of Data
 * @return CRC value
 */
uint16_t FastCRC14::darc(const uint8_t *data,const uint16_t datalen)
{
 // poly=0x0805 init=0x0000 refin=true refout=true xorout=0x0000 check=0x082d residue=0x0000
  return generic(0x0805, 0x0000, CRC_FLAG_REFLECT, data, datalen);
}

[...]

uint16_t FastCRC14::generic(const uint16_t polynom, const uint16_t seed, const uint32_t flags, const uint8_t *data, const uint16_t datalen)
{

  rCRC->CTRL  = flags | (1<<CRC_CTRL_TCRC) | (1<<CRC_CTRL_WAS);// 32-Bit Mode, prepare to write seed(25)
  rCRC->GPOLY = ((uint32_t)polynom) << [B][COLOR=#ff0000](32 - 14)[/COLOR][/B];                       // set polynom
  rCRC->CRC   = ((uint32_t)seed <<[COLOR=#ff0000][B] (32 - 14)[/B][/COLOR] );                          // this is the seed
  rCRC->CTRL  = flags | (1<<CRC_CTRL_TCRC);                         // Clear WAS Bit - prepare to write data

  return update(data, datalen);
}

However, the data need to be right-adjusted, with the upper bits (bit 14 and bit 15) = 0
Usually, this has to be done somewhere in the user-code anyway, so I hope it's not a problem.

If I have some time today, i'll try it for your CRCs.
 
Last edited:
@ TelephoneBill: I had forgotten that I made that CRC routine very specific to the CRC used in the FT4 protocol. I did a quick test last night and it doesn't handle messages of any length other than 77 bits (the 82 makes the code cycle an extra 5 bits to get the CRC in the right position). I'll have a look at Frank's FastCRC update today.

Pete
 
@el_supremo: I edited your code to remove the '82' and substituted 'data_length' instead, with 'int data_length' as the second parameter in the crc14 wrapper function. That meant I could then pass my own specified length to the wrapper in my own code. It appears to work fine certainly for 3 bytes of data (24 bits). To test it, I did a worked calculation in longhand on paper for the 3 bytes of 0x18,0x18,0x18 just to see what result it gave for the poly of 0x60B1. The paper remainder was 0x1d56 and I am sure that that is correct having rechecked it several times. Your code gave me the same answer of 0x1d56, so agrees with my longhand. I think it should then work for 56 bits being a multiple of 8 (7 bytes). If we get Frank's hardware operational then that should confirm things.

@Frank B: I'm now ready to try out your FastCRC.h. I'm not very familiar with c++ coding, so could you please give me a worked example of how I would use it practically. I did try to call FastCRC14::darc(Data1, sizeof(Data1)*8) when FastCRC.h was "included" (as a separate file) but the compile error told me FastCRC14 was not defined. A simple example will put me straight.
 
Code:
#include <FastCRC.h>

FastCRC14 CRC14;

//Teststring - result for CRC DARC is 0x082d
uint8_t buf[9] = {'1','2','3','4','5','6','7','8','9'};

void setup() {
 uint32_t crc;
  delay(1500);
  crc = CRC14.darc(buf, sizeof(buf));
  Serial.println(crc, HEX);
}

void loop() {
}
It returns the correct CRC for the given string. I should say, that I did not test with other teststrings, because I had no other testdata and their CRC. For this reason, I hav'nt added DARC to the documentation.. ;)
Of course this is only a example, and it lacks your CRCs so far..
@el supremo - your data is 14 bit format - (without two "filling" zeros), so I need to convert it, right?
 
Apologies. Can't get your example to compile. Keep getting "FastCRC14 does not name a type". Tried copying from github and putting 8 hours FastCRC.h in my program folder. Tried "Add File..." with a copy of the 8 hours FastCRC.h from program folder. Nothing seems to remove compile complaint.

Is the zip up to date? I did download and extract all into my program folder but that didn't work either. Obviously not "seeing" the latest files for some reason. Forgotten how to update the library for FastCRC (which is visible in the list)... would that work?

FrankBTest01.jpg
 
Maybe it is still using the old version which comes with Teensyduino.
- So, its best to delete the default version - it is in Arduino\hardware\teensy\avr\libraries

- If it does not exist, Create a subfolder "libraries" in documents\arduino: ...\documents\arduino\libraries\
- create a subfolder "FastCRC" : ...\documents\arduino\libraries\FastCRC\
- extract the zipfile to the new folder
contents should look like this:
fastCRC.png

You can check if it up to date if there is a line "class FastCRC14" in the file FastCRC.h

Edit: there is a line "uint16_t ft4(const uint8_t *data, const uint16_t datalen);" - but ft4 is not implemented, yet ;) - so no need to try it ;)
 
Last edited:
Yes, that solved the issue. Thanks for your patience.

I note that you have a different polynomial to 0x60B1, so I will alter that when I do some tests. Going to try the same one as in #15 with just three bytes to get 0x1D56 and that will give me confidence that the new poly works with the hardware CRC.

Getting close now to doing the real job of parsing.
 
The data does not require adjustment.

I added code to FastCRC to do the FT4 CRC. In FastCRChw.cpp:
Code:
uint16_t FastCRC14::ft4(const uint8_t *data,const uint16_t datalen)
{
  return generic(0x2757, 0x0000, CRC_FLAG_REFLECT, data, datalen);
}


I've been using the BOOST package on the PC to test CRCs (WSJTX uses BOOST).
FastCRC does not agree with BOOST when doing a CRC14.ft4
From FastCRC:
Code:
crc14 of crc14_tests[0] = 0x0C0A (strlen = 12)
crc14 of crc14_tests[1] = 0x0CEB (strlen = 12)
crc14 of crc14_tests[2] = 0x2296 (strlen = 12)
crc14 of crc14_tests[3] = 0x03FD (strlen = 12)
crc14 of crc14_tests[4] = 0x3678 (strlen = 12)
crc14 of crc14_tests[5] = 0x1066 (strlen = 12)

Same data using Boost:
Code:
crc14 of crc14_tests[0] = 0x2F7A (strlen = 12)
crc14 of crc14_tests[1] = 0x01D9 (strlen = 12)
crc14 of crc14_tests[2] = 0x16EA (strlen = 12)
crc14 of crc14_tests[3] = 0x1FCF (strlen = 12)
crc14 of crc14_tests[4] = 0x22EE (strlen = 12)
crc14 of crc14_tests[5] = 0x132D (strlen = 12)

This is the code I used on the T3.6:
Code:
#include <FastCRC.h>

FastCRC14 CRC14;

void setup()
{
  uint32_t crc;
  Serial.begin(9600);
  while(!Serial);
  delay(1000);
  
  uint8_t crc14_tests[][12] = {
    {0x4F, 0x76, 0x4C, 0xA4, 0xE2, 0x61, 0x2F, 0xF2, 0x65, 0xB0, 0x00, 0x00},
//crc14 = 0x2F7A

    {0x4A, 0x5E, 0xD7, 0xD4, 0xE3, 0x33, 0x6E, 0xDD, 0xE9, 0xE0, 0x00, 0x00},
//crc14 = 0x01D9

    {0x4E, 0x81, 0x44, 0x7B, 0x88, 0x66, 0xBC, 0xCA, 0x6C, 0xB0, 0x00, 0x00},
//crc14 = 0x16EA

    {0x4A, 0x5E, 0xD7, 0xD3, 0xE2, 0x03, 0x09, 0x5C, 0x44, 0x60, 0x00, 0x00},
//crc14 = 0x1FCF

    {0x4C, 0x4A, 0xB0, 0xD0, 0x72, 0x9B, 0x74, 0x52, 0x67, 0xB0, 0x00, 0x00},
//crc14 = 0x22EE

    {0x3A, 0x2D, 0x5D, 0x94, 0xFE, 0x64, 0x04, 0x82, 0x65, 0xF0, 0x00, 0x00},
//crc14 = 0x132D
  };

  for(int i = 0; i < sizeof(crc14_tests)/sizeof(crc14_tests[0]); i++) {
    crc = CRC14.ft4(crc14_tests[i],sizeof(crc14_tests[i]));
    Serial.printf("crc14 of crc14_tests[%d] = 0x%04X (strlen = %d)\n",i,crc,sizeof(crc14_tests[i]));
  }
}

void loop()
{
}


BOOST also disagrees with the darc CRC result using your test string. FastCRC on T3.6 gets CRC.darc=0x082d but BOOST gets 0x247A

The K66 reference manual says that the hardware can only do 16 and 32 bit CRC. How do you get it to do 8 or 14 bits?

Pete
 
Like all other CRC, it just uses the Hardware - CRC in the 32Bit mode and just shifts the polynom accordingly. This works for all other methods, too, even 7 Bits.
But, ok, there may be some details that are not 100% correct (reflecting or xor) - and I had only 1 set of testdata.

Sadly, boost seems to be wrong in this case ;) - maybe it does not use 16bit calculation (upper two bits zero, mentioned above - EDIT: i see you did not convert the data?) or has an other problem.
The 0x82d is the "official" result from the "official" teststring:

http://reveng.sourceforge.net/crc-catalogue/1-15.htm#crc.cat-bits.14
 
Last edited:
TelephoneBill
: I have it working - i Think - it is return generic(0x60b1, 0x0, CRC_FLAG_NOREFLECT , data, datalen); and shifting the result >>2
Do you have a second teststring? I used (0x18,0x18,0x18) - Result: 0x1d56
 
Ok, it's too late here.
The code is:
Code:
[COLOR=#ff0000]uint16_t FastCRC14::bill(const uint8_t *data,const uint16_t datalen)
{
 // poly=0x60b1 init=0x0000 refin=false refout=false xorout=0x0000 check=0x38d1
  return generic(0x60b1, 0x0, CRC_FLAG_NOREFLECT , data, datalen);
}[/COLOR]

/** Update
 * Call for subsequent calculations with previous seed
 * @param data Pointer to Data
 * @param datalen Length of Data
 * @return CRC value
 */
uint16_t FastCRC14::update(const uint8_t *data, const uint16_t datalen)
{
  const uint8_t *src = data;
  const uint8_t *target = src + datalen;

  while (((uintptr_t)src & 0x03) !=0 && (src < target))  {
    rCRC->CRC8_3 = *src++; //Write 8 BIT
  }

  while (src <= target-4) {
    rCRC->CRC = *( uint32_t  *)src; //Write 32 BIT
    src += 4;
  }

  while (src < target) {
    rCRC->CRC8_3 = *src++; //Write 8 Bit
  }

[COLOR=#ff0000]  if (rCRC->CTRL & (1<<CRC_CTRL_TOTR1))
    return rCRC->CRC16;
  else
    return rCRC->CRC>>18;  [/COLOR] 
}

if you want to try it.

If you can give a second teststring, to verfiy it, and a name (or is "bill" OK :D) i'll update the lib tomorrow. (It's 00:30 here)


Edit: The problem was the "CRC_FLAG_NOREFLECT" - case. I added CRC-14/GSM now which uses CRC_FLAG_NOREFLECT | CRC_FLAG_XOR - this gives the correct result, too. So I think, it's good. Bill?
 
Last edited:
@FrankB: Excellent news with 0x18,0x18,0x18 and the result 0x01D5. I don't have another verified (longhand) test string yet, but will make one later (busy all day today).

The naming should reflect the ITU document ITU-R M589 Part 3, which mentions Loran/Chayka (where the poly is defined). Perhaps FastCRC::eLOR ? It is eLoran that has the radio data channel and differs it from standard Loran.

If you update the zip today, I will download tonight and give it a test. I have lots of other data from the radio experiment in my "needles in haystack" search, so it should find something very quickly.
 
Status
Not open for further replies.
Back
Top