problem w/ setting polynomial for CRC

[BradWalker]

I'm trying to set the polynomial for the CRC block and having some difficulty. I want to set the CRC block to compute a CRC-32K (Reversed Koopman) over my data.

Here are the details

CRC-32K (reversed Koopman polynomial) - 0xEB31D82E

Input data - 0x31, 0x32, . . ., 0x39

I expect the resulting CRC to be 0x2D3DD0AE

How I setup my STMh755 CRC block

#define CRC_POLYNOMIAL_32B 0xeb31d82e
static const uint8_t aDataBuffer[] = {
0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39
};

/*##-1- Configure the CRC peripheral #######################################*/
CrcHandle.Instance = CRC;

/* The default polynomial is not used. It is required to defined it in CrcHandle.Init.GeneratingPolynomial*/
CrcHandle.Init.DefaultPolynomialUse = DEFAULT_POLYNOMIAL_DISABLE;

/* Set the value of the polynomial */
CrcHandle.Init.GeneratingPolynomial = CRC_POLYNOMIAL_32B;

/* The user-defined generating polynomial generates a
8-bit long CRC */
CrcHandle.Init.CRCLength = CRC_POLYLENGTH_32B;

/* The default init value is used */
CrcHandle.Init.DefaultInitValueUse = DEFAULT_INIT_VALUE_ENABLE;

/* The input data are not inverted */
CrcHandle.Init.InputDataInversionMode = CRC_INPUTDATA_INVERSION_NONE;

/* The output data are not inverted */
CrcHandle.Init.OutputDataInversionMode = CRC_OUTPUTDATA_INVERSION_DISABLE;

/* The input data are 32-bit long */
CrcHandle.InputDataFormat = CRC_INPUTDATA_FORMAT_BYTES;

if (HAL_CRC_Init(&CrcHandle) != HAL_OK)
{
/* Initialization Error */
Error_Handler();
}

/*##-2- Compute the CRC of "aDataBuffer" ###################################*/

uwCRCValue = HAL_CRC_Calculate(&CrcHandle, (uint32_t *)&aDataBuffer, BUFFER_SIZE);

A couple of issues:

1 - I get a return error from HAL_CRC_Init(). Why does HAL layer only allow ODD parity polynomials?

  /* Ensure that the generating polynomial is odd */
  if ((Pol & (uint32_t)(0x1U)) ==  0U)
  {
    status =  HAL_ERROR;
  }

2 - Am I missing something in setting up the CRC block?

Thanks.

[Tesla DeLorean]

Mechanically I'm not sure the hardware has this limitation, it shouldn't need too.

Did some hackery that suggests it's not, where I did a 15-bit CRC/Polynomial

https://github.com/cturvey/RandomNinjaChef/blob/main/STM32_CRC15_CRC_CAN.c

The hardware is LEFT shifting

The initial value would be 0xFFFFFFFF and the result inverted to get the solution, right shifting.

// Related to musings here
// https://community.st.com/t5/stm32-mcus-products/problem-w-setting-polynomial-for-crc/td-p/730403

// CRC-32K (reversed Koopman polynomial) - 0xEB31D82E
// Input data - 0x31, 0x32, . . ., 0x39
// I expect the resulting CRC to be 0x2D3DD0AE

// Copyright (C) 2024 Clive Turvey (aka Tesla DeLorean, sourcer32@gmail.com)
//  All Rights Reserved

//******************************************************************************

#include <windows.h>
#include <stdio.h>

typedef unsigned char uint8_t;
typedef unsigned int uint32_t;

//******************************************************************************

uint8_t data[] = {
  0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39 };

//******************************************************************************

uint32_t crc32k(uint32_t crc, size_t size, uint8_t *buffer)
{
  int i;
  while(size--)
  {
    crc ^= (uint32_t)*buffer++;
    for(i=0; i<8; i++)
      if (crc & 0x00000001)
        crc = (crc >> 1) ^ 0xEB31D82E;
      else
        crc >>= 1;
  }

  return(crc);
}

//******************************************************************************

int main(int argc, char **argv)
{
  uint32_t crc;

  crc = crc32k(0xFFFFFFFF, sizeof(data), data);
  printf("%08X %08X\n", crc, ~crc);

  return(1);
}

//******************************************************************************

Is suspect I can make the hardware work, but will take the polynomial being reversed, byte input reversed, answer reversed and inverted.

[Tesla DeLorean]

I made the magic happen on a STM32G031 to hand..

In ST-Speak inversion means bit-reversal

CRC-32-K 2D3DD0AE TEST 2D3DD0AE ?

//****************************************************************************

void TestCRC(void) // sourcer32@gmail.com PayPal accepted.. gauge by man-hours saved
{
  uint8_t test[] = { 0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39 }; // 0x2D3DD0AE

  /* CRC handler declaration */
  CRC_HandleTypeDef CrcHandle = {0};

  /* CRC Peripheral clock enable */
  __HAL_RCC_CRC_CLK_ENABLE();

  /*##-1- Configure the CRC peripheral #######################################*/
  CrcHandle.Instance = CRC;

  /* The default polynomial is not used. It is required to defined it in CrcHandle.Init.GeneratingPolynomial*/
  CrcHandle.Init.DefaultPolynomialUse    = DEFAULT_POLYNOMIAL_DISABLE; // ST double-negative, use user supplied

  /* Set the value of the polynomial */
  CrcHandle.Init.GeneratingPolynomial    = 0x741B8CD7; // 32-bit CRC-32-K, bit reversed 0xEB31D82E, hw left shifts, always

  /* The user-defined generating polynomial generates a 32-bit long CRC */
  CrcHandle.Init.CRCLength               = CRC_POLYLENGTH_32B;
	
  /* The default init value is not used */
  CrcHandle.Init.DefaultInitValueUse     = DEFAULT_INIT_VALUE_DISABLE; // ST double-negative

  /* The used-defined initialization value */
  CrcHandle.Init.InitValue               = 0xFFFFFFFF; // 32-bit all set

  /* The input data is inverted (bit-reversed) */
  CrcHandle.Init.InputDataInversionMode  = CRC_INPUTDATA_INVERSION_BYTE; // Bit swap byte end-to-end

  /* The output data is inverted (bit-reversed)*/
  CrcHandle.Init.OutputDataInversionMode = CRC_OUTPUTDATA_INVERSION_ENABLE;// Bit swap word end-to-end

  /* The input data are 8-bit long */
  CrcHandle.InputDataFormat              = CRC_INPUTDATA_FORMAT_BYTES;

  if (HAL_CRC_Init(&CrcHandle) != HAL_OK)
  {
    /* Initialization Error */
    Error_Handler(__FILE__, __LINE__);
  }

  /* Note that I negate the response the hardware spins end-to-end */
  printf("CRC-32-K %08X TEST 2D3DD0AE ?\n", ~HAL_CRC_Calculate(&CrcHandle, (uint32_t *)test, sizeof(test)));
}

//****************************************************************************

[Tesla DeLorean]

@STOne-32 @STTwo-32 "Why does HAL layer only allow ODD parity polynomials?"

https://community.st.com/t5/stm32-mcus-security/can-the-stm32-crc-peripheral-be-abused-into-doing-crc-24q-or/m-p/65228

Case in point I can also do 24-bit and 15-bit CRC's where I do ALL the work in the high-order bits

[STOne-32]

Dear @Tesla DeLorean  @BradWalker ,

Thank you for the interesting exchanges, the main is reason is simply because our specification / manual say it.

here an example of our reference manual for STM32G4 series : STM32G4 series advanced Arm<Sup>®</Sup>-based 32-bit MCUs - Reference manual  ,

Go to Page 456/2138 from Manual revision 8.

I fully understand it might work perfectly at your end , but from our side, we do not support the behavior or results as it could be never tested/verified as at industry level  Odd Polynomials are the mostly used.

Hope it helps to clarify the topic. 

STOne-32.

[Tesla DeLorean]

Software table methods, 4-bit (64-byte table) and 8-bit (1KB table)

//******************************************************************************

uint32_t crc32k_quick(uint32_t crc, size_t size, uint8_t *buffer)
{
  static const uint32_t crctable[] = { // CRC-32-K nibble table
    0x00000000,0x83CF0F3C,0xD1FDAE25,0x5232A119,
    0x7598EC17,0xF657E32B,0xA4654232,0x27AA4D0E,
    0xEB31D82E,0x68FED712,0x3ACC760B,0xB9037937,
    0x9EA93439,0x1D663B05,0x4F549A1C,0xCC9B9520 }; // sourcer32@gmail.com

  while(size--)
  {
    crc ^= (uint32_t)*buffer++;

    crc = (crc >> 4) ^ crctable[crc & 0xF]; // Process byte, 4-bits at a time
    crc = (crc >> 4) ^ crctable[crc & 0xF];
  }

  return(crc);
}

//******************************************************************************

uint32_t crc32k_fast(uint32_t crc, size_t size, uint8_t *buffer)
{
  static const uint32_t crctable[] = { // CRC-32-K byte table
    0x00000000,0x9695C4CA,0xFB4839C9,0x6DDDFD03,0x20F3C3CF,0xB6660705,0xDBBBFA06,0x4D2E3ECC,
    0x41E7879E,0xD7724354,0xBAAFBE57,0x2C3A7A9D,0x61144451,0xF781809B,0x9A5C7D98,0x0CC9B952,
    0x83CF0F3C,0x155ACBF6,0x788736F5,0xEE12F23F,0xA33CCCF3,0x35A90839,0x5874F53A,0xCEE131F0,
    0xC22888A2,0x54BD4C68,0x3960B16B,0xAFF575A1,0xE2DB4B6D,0x744E8FA7,0x199372A4,0x8F06B66E,
    0xD1FDAE25,0x47686AEF,0x2AB597EC,0xBC205326,0xF10E6DEA,0x679BA920,0x0A465423,0x9CD390E9,
    0x901A29BB,0x068FED71,0x6B521072,0xFDC7D4B8,0xB0E9EA74,0x267C2EBE,0x4BA1D3BD,0xDD341777,
    0x5232A119,0xC4A765D3,0xA97A98D0,0x3FEF5C1A,0x72C162D6,0xE454A61C,0x89895B1F,0x1F1C9FD5,
    0x13D52687,0x8540E24D,0xE89D1F4E,0x7E08DB84,0x3326E548,0xA5B32182,0xC86EDC81,0x5EFB184B,
    0x7598EC17,0xE30D28DD,0x8ED0D5DE,0x18451114,0x556B2FD8,0xC3FEEB12,0xAE231611,0x38B6D2DB,
    0x347F6B89,0xA2EAAF43,0xCF375240,0x59A2968A,0x148CA846,0x82196C8C,0xEFC4918F,0x79515545,
    0xF657E32B,0x60C227E1,0x0D1FDAE2,0x9B8A1E28,0xD6A420E4,0x4031E42E,0x2DEC192D,0xBB79DDE7,
    0xB7B064B5,0x2125A07F,0x4CF85D7C,0xDA6D99B6,0x9743A77A,0x01D663B0,0x6C0B9EB3,0xFA9E5A79,
    0xA4654232,0x32F086F8,0x5F2D7BFB,0xC9B8BF31,0x849681FD,0x12034537,0x7FDEB834,0xE94B7CFE,
    0xE582C5AC,0x73170166,0x1ECAFC65,0x885F38AF,0xC5710663,0x53E4C2A9,0x3E393FAA,0xA8ACFB60,
    0x27AA4D0E,0xB13F89C4,0xDCE274C7,0x4A77B00D,0x07598EC1,0x91CC4A0B,0xFC11B708,0x6A8473C2,
    0x664DCA90,0xF0D80E5A,0x9D05F359,0x0B903793,0x46BE095F,0xD02BCD95,0xBDF63096,0x2B63F45C,
    0xEB31D82E,0x7DA41CE4,0x1079E1E7,0x86EC252D,0xCBC21BE1,0x5D57DF2B,0x308A2228,0xA61FE6E2,
    0xAAD65FB0,0x3C439B7A,0x519E6679,0xC70BA2B3,0x8A259C7F,0x1CB058B5,0x716DA5B6,0xE7F8617C,
    0x68FED712,0xFE6B13D8,0x93B6EEDB,0x05232A11,0x480D14DD,0xDE98D017,0xB3452D14,0x25D0E9DE,
    0x2919508C,0xBF8C9446,0xD2516945,0x44C4AD8F,0x09EA9343,0x9F7F5789,0xF2A2AA8A,0x64376E40,
    0x3ACC760B,0xAC59B2C1,0xC1844FC2,0x57118B08,0x1A3FB5C4,0x8CAA710E,0xE1778C0D,0x77E248C7,
    0x7B2BF195,0xEDBE355F,0x8063C85C,0x16F60C96,0x5BD8325A,0xCD4DF690,0xA0900B93,0x3605CF59,
    0xB9037937,0x2F96BDFD,0x424B40FE,0xD4DE8434,0x99F0BAF8,0x0F657E32,0x62B88331,0xF42D47FB,
    0xF8E4FEA9,0x6E713A63,0x03ACC760,0x953903AA,0xD8173D66,0x4E82F9AC,0x235F04AF,0xB5CAC065,
    0x9EA93439,0x083CF0F3,0x65E10DF0,0xF374C93A,0xBE5AF7F6,0x28CF333C,0x4512CE3F,0xD3870AF5,
    0xDF4EB3A7,0x49DB776D,0x24068A6E,0xB2934EA4,0xFFBD7068,0x6928B4A2,0x04F549A1,0x92608D6B,
    0x1D663B05,0x8BF3FFCF,0xE62E02CC,0x70BBC606,0x3D95F8CA,0xAB003C00,0xC6DDC103,0x504805C9,
    0x5C81BC9B,0xCA147851,0xA7C98552,0x315C4198,0x7C727F54,0xEAE7BB9E,0x873A469D,0x11AF8257,
    0x4F549A1C,0xD9C15ED6,0xB41CA3D5,0x2289671F,0x6FA759D3,0xF9329D19,0x94EF601A,0x027AA4D0,
    0x0EB31D82,0x9826D948,0xF5FB244B,0x636EE081,0x2E40DE4D,0xB8D51A87,0xD508E784,0x439D234E,
    0xCC9B9520,0x5A0E51EA,0x37D3ACE9,0xA1466823,0xEC6856EF,0x7AFD9225,0x17206F26,0x81B5ABEC,
    0x8D7C12BE,0x1BE9D674,0x76342B77,0xE0A1EFBD,0xAD8FD171,0x3B1A15BB,0x56C7E8B8,0xC0522C72 }; // sourcer32@gmail.com

  while(size--)
  {
    crc ^= (uint32_t)*buffer++;

    crc = (crc >> (8)) ^ crctable[crc & 0xFF]; // Process byte, 8-bits at a time
  }

  return(crc);
}

//******************************************************************************

[Tesla DeLorean]

Ok, but LFSR's and CRC methods have been a staple of DfT (Design for Test) / BiST (Built in Self Test) for over 4 decades.

I'm not sure of your CRC implementation here, but it's usually a net of feed back terms and flip-flops, gated by a latched polynomial pattern in this case, it should be able to be validated "by-design". Do you test all the other 2^(32-1) patterns for a polynomial that would be ODD? I'd wager serious money you do not, or come remotely close.

The CRC-24 implementation should be able to provide some robust test-patterns / test-vectors that could be applied at the DESIGN stages to exercise the gate level implementation. And prove robustly that the ODD rule is patently nonsense.

For the CRC-32-K I reversed the polynomial to deal with the left-shifting implementation, and that does make it ODD at the LSB.

But in the case of the 15-bit and 24-bit CRC that I've expressly demonstrated here, all the low order bits of the polynomial registers are zero, as I've left aligned them, whilst the CRC-24 itself is in the form x^24 + ... + 1

Pretty sure I can demonstrate 4 and 5-bit exploits of the hardware too.

Need to dig out an STM32G4

[Tesla DeLorean]

Here's 4-bit on a STM32G474RE.. (using 1.5.0)

//****************************************************************************

// This exploits my understanding of the STM32 CRC Hardware
//  Tested on a STM32G474RE on a NUCLEO-G474RE

// 4-bit, Right Shifting, x^4 + x^3 + 1  used in the SPARTN protocol
//  https://www.spartnformat.org/wp-content/uploads/210928_SPARTN_v2.0.1.pdf#page=34
//  Mentioned also at https://users.ece.cmu.edu/~koopman/crc/

// Copyright (C) 2024 Clive Turvey (aka Tesla DeLorean, sourcer32@gmail.com)
//  All Rights Reserved

void TestCRC4_9R(void) // sourcer32@gmail.com PayPal accepted.. gauge by man-hours saved
{
  uint8_t test1[] = { 0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39 }; // 0x02
  uint8_t test2[] = { 0x12,0x34,0x56 };  // 0x9
	
  /* CRC handler declaration */
  CRC_HandleTypeDef CrcHandle = {0};

  /* CRC Peripheral clock enable */
  __HAL_RCC_CRC_CLK_ENABLE();

  /*##-1- Configure the CRC peripheral #######################################*/
  CrcHandle.Instance = CRC;

  /* The default polynomial is not used. It is required to defined it in CrcHandle.Init.GeneratingPolynomial*/
  CrcHandle.Init.DefaultPolynomialUse    = DEFAULT_POLYNOMIAL_DISABLE; // ST double-negative, use user supplied

  /* Set the value of the polynomial */
  CrcHandle.Init.GeneratingPolynomial    = 0x9 << (32 - 4); // 4-bit CRC-4-9R, bit reversed 0x00000009, hw left shifts, always

  /* The user-defined generating polynomial generates a 32-bit long CRC */
  CrcHandle.Init.CRCLength               = CRC_POLYLENGTH_32B;
	
  /* The default init value is not used */
  CrcHandle.Init.DefaultInitValueUse     = DEFAULT_INIT_VALUE_DISABLE; // ST double-negative

  /* The used-defined initialization value */
  CrcHandle.Init.InitValue               = 0; // 32-bit all clear

  /* The input data is inverted (bit-reversed) */
  CrcHandle.Init.InputDataInversionMode  = CRC_INPUTDATA_INVERSION_BYTE; // Bit swap byte end-to-end

  /* The output data is inverted (bit-reversed)*/
  CrcHandle.Init.OutputDataInversionMode = CRC_OUTPUTDATA_INVERSION_ENABLE;// Bit swap word end-to-end

  /* The input data are 8-bit long */
  CrcHandle.InputDataFormat              = CRC_INPUTDATA_FORMAT_BYTES;

  if (HAL_CRC_Init(&CrcHandle) != HAL_OK)
  {
    /* Initialization Error */
    Error_Handler(__FILE__, __LINE__);
  }

  /* The hardware spins end-to-end, 4-bits will be in least significant bits, shouldn't need to mask
	   as the polynomial adds no bits down there as it consumes the bytes */
  printf("CRC-4-9R %1X TEST1 2 ?\n", HAL_CRC_Calculate(&CrcHandle, (uint32_t *)test1, sizeof(test1)) & 0xF);
  printf("CRC-4-9R %1X TEST2 9 ?\n", HAL_CRC_Calculate(&CrcHandle, (uint32_t *)test2, sizeof(test2)) & 0xF);
}

//****************************************************************************

[Tesla DeLorean]

https://github.com/STMicroelectronics/stm32g4xx-hal-driver/blob/3d08880e8d7f96454675d48888a3a207388268b0/Src/stm32g4xx_hal_crc_ex.c#L97

This code shows a surprisingly poor understanding of how the hardware works.

It will break my 4, 15, 17 and 24-bit CRC methods. Which work on the G4 with the V1.5.0 release

Given the fixed, left-shifting implementation of the hardware, the non-standard word lengths need to left align the polynomial, which by it's nature will make bit zero clear.

I'm not arguing that the polynomials don't take the form x^n + ... + 1, but rather that bit 0 in the POL register doesn't need to 1 when n != 7,8,16,32, and that I can do 4-bit CRC's with a 32-bit accumulator

See

4-bit, right shifting, x^4 + x^3 + 1

https://github.com/cturvey/RandomNinjaChef/blob/main/STM32_CRC4_9R.c

32-bit, right shifting, x^32 + x^30 + x^29 + x^28 + x^26 + x^20 + x^19 + x^17 + x^16 + x^15 + x^11 + x^10 + x^7 + x^6 + x^4 + x^2 + x^1 + 1

https://github.com/cturvey/RandomNinjaChef/blob/main/STM32_CRC32K.c

24-bit, left shifting, x^24+ x^23+ x^18+ x^17+ x^14+ x^11+ x^10+ x^7+ x^6+ x^5+ x^4+ x^3+ x+1

https://github.com/cturvey/RandomNinjaChef/blob/main/STM32_CRC24Q.c

17-bit, left-shifting, x^17 + x^16 + x^14 + x^13 + x^11 + x^6 + x^4 + x^3 + x^1 + 1

https://github.com/cturvey/RandomNinjaChef/blob/main/STM32_CRC17CAN.c

The odds of these working by happenstance is incredibly low..

[Tesla DeLorean]

The feed-back path is 32-bit, the data always shifts left, the mixers optionally reverse / "invert" their data paths, allowing to simulate left/right shifting and msb/lsb insertion of the byte (as configured)

Now with non-normal sizes we can only inject bytes, you can't process 5 or 13 bits, for example, but you can have 3 or 13-bit CRC's. Configuration would allow for word insertion, but I think endian issues will still be frustrating.