CRC generation

[sueppchen]

In the meantime, I've updated my crc.ino file with folowing changes :

• zero-based values for all of the 7 bytes (as you did)
• as bytes may have different meaning according to the mode value, I moved to a 7*64 table, with no reference anymore to the role of each of the bytes
• CRC table updated with valid values for all values of byte 5 (formerly called Attack/Random) and for all values of byte 7 (formerly called GROUP) crc2.ino.txt

_Originally posted by @Serge-45 in https://github.com/sueppchen/PixMob_waveband/issues/1#issuecomment-2053998108_

[sueppchen]

I moved this question to another topic --> CRC generation. and yes - I did nearly the same with mode==4 I filled up the byte7 and byte5 and switched to a byte-depended matrix (list of lists) like you can see in /investigation/advanced.ino

ok you where a little faster, so I'll copy your values

what does mode = xx x1xx do when > 4 ?

... I'll do the tests on mode = xx xx1x to proof my idea with end3:2

[sueppchen]

have you tried to xor the values in each table with its direct neighbor? I can see a scheme...

[Serge-45]

Good catch ! Yes, definitely there is something which is absolutely not random !

[Serge-45]

According to the kind of logic I can see, I think that the CRC calculation is done on 16-bit words, and then the lower 12 bits are taken and split as 6 + 6 bits values to give the 2 CRC bytes. CRC1 (first byte of the message) is the lower 6 bits, CRC2 (last byte) is the MSB.

[sueppchen]

most MCU have an internal CRC16 generator to check firmware upload. it is fed with 0x1d0f as start value.

would it be possible that an crc16 is calculated over each byte? (maybe possition+value )

the XOR with the neighbor generates a list with repeating values for each sublist (byte1, byte 2) but there are no values in the new byte2-list found in byte1-list...

same XOR in every list: 14^15 = 16^17 = 20^21 = 24^25 = 34^35 = 46^47 00^01 = 17^18 = 29^30 08^09 = 10^11 = 22^23 = 30^31 = 48^49 = 50^51 = 52^53 28^29 = 32^33 33^34 = 35^36 = 45^46 = 61^62 31^32 = 51^52 = 54^55 09^10 = 21^22 18^19 = 62^63 04^05 = 26^27 = 58^59

others share some bits...always

[Serge-45]

Some new values of CRC available for byte 1 (MOD) : crc2.ino.txt

    {   /* Byte 1 (MOD) */                                  
        __REF_, _NONE_, 0x3D30, _NONE_, 0x1E2D, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 00-07 */
        _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 08-0F */
        0x0C3B, 0x1D1D, 0x1130, _NONE_, 0x222D, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 10-17 */
        _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 18-1F */
        0x3B30, _NONE_, 0x171D, _NONE_, 0x2000, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 20-27 */
        _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 28-2F */
        0x2200, _NONE_, 0x2D1D, 0x162D, 0x3A16, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 30-37 */
        _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_, _NONE_,     /* Byte 1 (MOD), 38-3F */
    },                                      

[sueppchen]

mode = 0x13: 0x262d mode = 0x31: 0x1930

the other values do not create valid CRC

funfact: most of the valid crcB values end with b or 6

[Serge-45]

Updated with new values for byte 1 : crc2.ino.txt

[sueppchen]

ok... news: mode[0x30] ^ mode[0x31] = mode[0x20] there are more of that.

[sueppchen]

it is a bit like solving a sudoku: with the steps 1..62 0x38=0x22 ^ 0x24 ... have a look @ investigation/listRules.py

[sueppchen]

list for MODE = { 0x0000, 0x0c2d, 0x3d30, 0x283b, 0x1e2d, 0x1b26, 0x3726, 0x130b, 0x0f0b, 0x343b, 0x0726, 0x3c16, 0x1600, 0x1c2d, 0x291d, 0x383b,
0x0c3b, 0x1d1d, 0x1130, 0x262d, 0x222d, 0x330b, 0x0016, 0x3b26, 0x3816, 0x2930, 0x0200, 0x070b, 0x2a00, 0x2016, 0x2c3b, 0x170b,
0x3b30, 0x3126, 0x171d, 0x063b, 0x2000, 0x0e3b, 0x2c2d, 0x350b, 0x3d0b, 0x191d, 0x2600, 0x083b, 0x0a16, 0x242d, 0x0216, 0x1330,
0x2200, 0x1930, 0x2d1d, 0x162d, 0x3a16, 0x0126, 0x0326, 0x2f1d, 0x371d, 0x1926, 0x2b30, 0x2e3b, 0x0d0b, 0x2330, 0x050b, 0x3216},

[Serge-45]

Great !!! Deduced from the XOR you have detected ? Here is the updated crc2.ino file with now ALL values for CRC calculation : crc2.ino.txt

[sueppchen]

yes deduced with the rules found in the valid lists (see investigation/listRules.py) wich shows the rules. I automated the process to take the few input-bytes to generate the complete List.

I uploaded play.ino with all values and basic CLI to be controlled by host program or user.

there are some rules which make me suspect that the table are based on the 0x3f'th element and not on the 0x00'th

[0x38] ^ [0x39] = [0x3b] [0x39] ^ [0x3a] = [0x3f] [0x3a] ^ [0x3b] = [0x3e] [0x3b] ^ [0x3c] = [0x3d] [0x3c] ^ [0x3d] = [0x3b] [0x3e] ^ [0x3f] = [0x38]

stay tuned

[sueppchen]

it is possible to offset every list by any value IN the list without breaking the rules (the rules change, but they are consistent) but if a list is offset (XORed) with another value (even from another List) the rules disappear.

I tried to rotate the values in the table by 0-11 bit but there is no rule which is true for all 7 tables

[sueppchen]

the mode table can be checked for beeing valid by shortening the time until the batch goes to sleep, try to wake it with test-message - if it falls asleep again: invalid ...if not: valid. this is because mode does not output always something...

[sueppchen]

all values seem to be valid. now lets ge rid of the tables: internal everything is processed as 8bit value, also the incoming color-information is shifted left by 2

the checksum for stored colors is simple an addition of all values cut to 8 bit.

[sueppchen]

updated readme and wiki

[Serge-45]

Great news, I've progressed on the CRC calculation! Here are the outcomes.

Overall process:

• the 7 bytes of the messages are first converted to 8-bit using the custom 6b8b table
• the 7 converted bytes are most probably input into a kind of CRC algorithm (not able to identify it yet) giving a 16-bit word (or 12-bit word ?)
• two 6-bit values are extracted from this CRC word, it could be the last 2x6 bits, or the last 6 bits of each byte, or whatever other way to extract 2x6 bits. In this process, 4 bits from the CRC word are lost if the CRC is a 16-bit algorithm!
• the two 6-bit values are insterted, one as the first byte of the message, the other as the last byte
• before sending, the 1+7+1 bytes are converted to 8-bit using the custom 6b8b table

Starting from the initial CRC value of 0x1b05, each bit of each of the 7 bytes has its own effect on the resulting CRC word, it applies a XOR to the CRC according to the following table (XOR value to apply to update CRC1/CRC2, assuming that CRC1 is the MSB and CRC2 the LSB) :

byte#	bit 0 (lsb)	bit 1	bit 2	bit 3	bit 4	bit 5	bit 6	bit 7 (msb)
1	2416	082D	371D	2E3B	3B30	1126	050B	0A16
2	142C	0F1F	1E3E	1B3B	1131	0525	2D0D	1A1B
3	3436	0F2A	3913	3227	0308	0610	0C20	3F07
4	3E0F	3C1F	383F	1738	0937	3529	0D14	1A28
5	1317	262E	2B1A	1635	0B2D	311D	223B	2330
6	2126	250A	0A15	142A	0F13	1E26	1B0B	3616
7	2C2D	3F1C	3E39	1B34	112F	0519	0A32	3323

These values are most probably coming from a CRC calculation based on a given polynomial, not identified yet.

Application example:

message to send     | 01 00 00 00 00 00 00
converted to 8b     | 35 21 21 21 21 21 21
initial CRC value   | 1b05 
xor for byte 1 = 35 | 2416 ^ 0000 ^ 371D ^ 0000 ^ 3B30 ^ 1126 ^ 0000 ^ 0000
xor for byte 2 = 21 | 142c ^ 0000 ^ 0000 ^ 0000 ^ 0000 ^ 0525 ^ 0000 ^ 0000
xor for byte 3 = 21 | 3436 ^ 0000 ^ 0000 ^ 0000 ^ 0000 ^ 0610 ^ 0000 ^ 0000
and so on for bytes 4 to 7...
Final result of all | 3e2f ==> CRC1=3e, CRC2=2f
message with CRC    | 3e 01 00 00 00 00 00 00 2f
Convert to 8b       | 61 35 21 21 21 21 21 21 ad

[sueppchen]

uuuh, nice. we are getting closer. I've tried the polynominals from 0x0000 to 0xffff... no match.

I updated the play.ino with the new calculation routine

have you seen, that the values are repeating (nearly , not exactly) see: byte 1 bit 1 and compare with byte 5 bit 4 and following... if it is an endless list there is something until byte 6.6 ...

take a look at /investigation/rules01.py --> it is a rotation. when I XOR it with it's neighbor the result rotates left.

[Serge-45]

Hi! I currently suspect a CRC-16 with 0x8005 as polynomial, no clue about the initial value. Bit order may also be reversed. The CRC1 and CRC2 bytes could also be swapped as MSB/LSB. As we loose 2x2 bits of the calculated CRC, it makes the checking more difficult. Check message <00,00,00,01,00,02,00> which gets xx000000-xx000000 as the two CRC bytes.

[sueppchen]

0x8005 does not produce a valid output: I checkes 0x0 - 0xffff as initial value and also all kinds of reflection, shifting or swaping...

[Serge-45]

Got it !!!

It's a CRC-12, polynom=CF1, init=963, data bytes are considered Little-Endian. First CRC byte in message is the MSB, second is LSB. We can reproduce this calculation using "reveng" utility which gives the two 6-bit bytes:

> reveng -w 12 -p CF1 -i 963 -l -A 6 -S -c 12345678abcdef
14 00

The 7 bytes to use as input are the conversion via 6b8b of the 7 6-bit bytes of the message. The two 6-bit CRC bytes have to be converted via 6b8b to 8-bit bytes before sending.

[Serge-45]

Process followed to discover the CRC parameters:

• first assumption is a CRC-16 algorithm starting at the first byte of the message, bit ordering 7..0
• try all possible values on the first 2 bytes (message <xx,yy,00,00,00,00,00>) and identify the values giving a CRC=0x0000 => several values found as 03E7, 125A,...
• having CRC=0 may mean that the 2 bytes at start of the message are zeroed by the initial value of the CRC algorithm. Then, all next intermediate values are 0 until the end.
• due to the fact that the CRC algorithm computes the remainder of polynom quotient, on such a message with CRC=0, setting to 1 the very last bit processed by the algorithm force the CRC resulting value to be the CRC polynom itself => two candidates (if the last bit is bit 0 or bit 7 of the last byte):
  • <xx,yy,00,00,00,00,01> => CRC = 2C2D = [00][101100] [00][101101]
  • <xx,yy,00,00,00,00,80> => CRC = 3323 = [00][110011] [00][100011]
• Now, let's use 3 different test messages and their respective CRC bytes (2x6 bits given by the CRC tables):
  • <00,00,00,00,00,00,00> => CRC = 1B05 = [00][011011] [00][000101]
  • <66,66,66,66,66,66,66> => CRC = 332B = [00][110011] [00][101011]
  • <99,99,99,99,99,99,99> => CRC = 1026 = [00][010000] [00][100110] Benefit of using these messages : they are no dependent on bit order or byte order
• with a real CRC algorithm (Python code), scan all results:
  • with polynom = any kind of combination of the two 6-bit sequences extracted from 2C2D or 3323, and 4 additional bits, including reversing bit order
  • with initial value = all 2^16 numbers
  • using the combination used to get the polynom, apply it to the calculated CRC, and check if the result matches the expected CRC bytes for all three test messages
  • if yes => we have a highly probable candidate for polynom and initial value of the CRC algorithm

Several good matches for all three messages found with combinations based on 3323, taking as polynom: [reverse bin of MSB][reverse bin of LSB][0000] = [110011][110001][0000] = 0xCF10

As a polynom must end with a binary '1', guessing that the effective polynom is 12-bit long and is 0xCF1, used with the combination [reverse bin of MSB][reverse bin of LSB] and no need to add more bits:

• 3323 = [00][MSB][00][LSB] ==> [reverse bin of MSB][reverse bin of LSB] = [110011][110001] = 0xCF1

Testing all 2^12 initial values, only 0x963 gives a match for all messages. Example:

• <00,00,00,00,00,00,00> => 0xDA8 with the CRC-12 algorithm (0xCF1,0x963), 0xDA8 = [110110][101000]
• [reverse MSB] = [011011] = 1B, [reverse LSB] = [000101] = 05
• this matches the value 1B05 given by the CRC tables

[Serge-45]

Proposed code for CRC calculation:

#define POLY  0xCF1     // polynom
#define POLYR 0x8f3     // reversed polynom (on 12 bits)
#define INIT  0x963     // init value
#define INITR 0xc69     // reversed init value (on 12 bits)

uint16_t crc12(uint8_t *message) {
  // message = buffer of 7 bytes which have already been converted from 6b to 8b
  // read data from first byte to last byte
  // read data bytes starting from lsb bit (bit 0)
  // register and POLY are reversed, bit 0 is the most significant
  uint8_t *ptr = message;   // pointer to the 1st message byte
  uint16_t reg = INITR;     // 12 bits of the INIT (reversed) value

  // 7*8 bits to process
  for (uint8_t count_bytes = 7; count_bytes != 0; count_bytes--) {
    printf("DATA=%02x\n", *ptr);
    reg ^= (*ptr++);          // get next byte of data
    for (uint8_t count_bits = 8; count_bits != 0; count_bits--) {
      if (reg & 0x0001) {     // if most significant bit is 1
        reg >>= 1;            // shift the register
        reg ^= POLYR;         // and xor with polynom
      } else {                // if most significant bit is 0
        reg >>= 1;            // just shift the register
      }
    }
  }

  printf("CRC1=%02x, CRC2=%02x\n", reg & 0x003f, reg >> 6); // split as 2x6 bits
  return ((reg & 0x003f) << 8) | ((reg & 0x0FC0) >> 6); // return the 2 CRC bytes as a double byte
}

**EDIT: code simplified

[Serge-45]

Option: pre-calculate a CRC table in order to speed up

#define POLY  0xCF1     // polynom
#define POLYR 0x8f3     // reversed polynom (on 12 bits)
#define INIT  0x963     // init value
#define INITR 0xc69     // reversed init value (on 12 bits)

uint16_t crctable[256]; // CRC values for each of the 256 possible bytes

void crc12table() { // to be called once at startup
                    // preload the CRC values for each of the 256 possible bytes
  uint16_t reg;     // 12 bits of the INIT (reversed) value
  uint8_t b = 0;    // compte CRC value for all 256 values
  do {
    reg = b;                  // next byte of data
    for (uint8_t count_bits = 8; count_bits != 0; count_bits--) {
      if (reg & 0x0001) {     // if most significant bit is 1
        reg >>= 1;            // shift the register
        reg ^= POLYR;         // and xor with polynom
      } else {                // if most significant bit is 0
        reg >>= 1;            // just shift the register
      }
    }
    crctable[b] = reg;        // store result
  } while (++b != 0);         // stop after value 255
}

uint16_t crc12t(uint8_t *message) {
                            // use pre-loaded table of 256 CRC values
  uint8_t *ptr = message;   // pointer to the 1st message byte
  uint16_t reg = INITR;     // 12 bits of the INIT (reversed) value

  // 7 bytes to process
  for (uint8_t count_bytes = 7; count_bytes != 0; count_bytes--) {
    reg = crctable[(*ptr++) ^ (reg & 0x00ff)] ^ (reg >> 8);
  }

  printf("CRC1=%02x, CRC2=%02x\n", reg & 0x003f, (reg & 0x0FC0) >> 6); // split as 2x6 bits
  return ((reg & 0x003f) << 8) | ((reg & 0x0FC0) >> 6); // return the 2 CRC bytes as a double byte
}

[sueppchen]

congratulations!

I tried reveng, but it didn't work for me - so I wrote my own python stuff. but I never combined CRC12 and 8 bit input values ...

so... I converted all TX-stuff to a arduino library and would like to work on the library to include all functions.