Explain how this algorithm works because I did not find any good, understandable information on this algorithm. Everything is described in mathematical formulas, but I want to understand the very essence of the algorithm. How he works, and in particular, what he does with the incoming data.

  • CRC is the generic name for a family of algorithms. And what exactly are you asking? - Mikhail Vaysman
  • It is based on division by polynom. There can not be math. - etki
  • CRC is not a hash, as far as I know ... - Vladimir Martyanov

1 answer 1

The crc task is very simple - in accordance with the received bytes, put them in correspondence with 4 bytes (or 2, crc are different). The following conditions are met:

  • identical inputs will have the same crc.
  • different inputs will have different crc, but may be the same.
  • input data that differs quite a bit (a few bits) is likely to have different crc.

The calculation itself is described in Wikipedia and ultimately reduced to mathematical formulas. But if we discard all this, then the bottom line is basically xor and shift. That is, we read data from the input stream, shift / xorim.

Take on wikipedia a very simple crc8 and analyze

/* Name : CRC-8 Poly : 0x31 x^8 + x^5 + x^4 + 1 - Π½Π°Π΄ Π΅Π³ΠΎ Π²Ρ‹Π±ΠΎΡ€ΠΎΠΌ сидят ΠΌΠ°Ρ‚Π΅ΠΌΠ°Ρ‚ΠΈΠΊΠΈ ΠΈ ΠΊΡ€ΠΈΠΏΡ‚ΠΎΠ°Π½Π°Π»ΠΈΡ‚ΠΈΠΊΠΈ Init : 0xFF Π½Π°Π΄ этим Ρ‚Π°ΠΊΠΆΠ΅ Revert: false XorOut: 0x00 Check : 0xF7 ("123456789") ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Ρ‡Ρ‚ΠΎ Π±Ρ‹ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΠΈΡ‚ΡŒ Ρ€Π΅Π°Π»ΠΈΠ·Π°Ρ†ΠΈΡŽ MaxLen: 15 Π±Π°ΠΉΡ‚(127 Π±ΠΈΡ‚) - ΠΎΠ±Π½Π°Ρ€ΡƒΠΆΠ΅Π½ΠΈΠ΅ ΠΎΠ΄ΠΈΠ½Π°Ρ€Π½Ρ‹Ρ…, Π΄Π²ΠΎΠΉΠ½Ρ‹Ρ…, Ρ‚Ρ€ΠΎΠΉΠ½Ρ‹Ρ… ΠΈ всСх Π½Π΅Ρ‡Π΅Ρ‚Π½Ρ‹Ρ… ошибок */ unsigned char Crc8(unsigned char *pcBlock, unsigned int len) { // Π½Π°Ρ‡Π°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅. ВыбираСтся с ΠΏΠΎΡ‚ΠΎΠ»ΠΊΠ° ΠΈΠ»ΠΈ ΡΠΊΡΠΏΠ΅Ρ€ΠΈΠΌΠ΅Π½Ρ‚Π°Π»ΡŒΠ½ΠΎ unsigned char crc = 0xFF; unsigned int i; while (len--) // ΠΏΠΎΠΊΠ° Ρƒ нас Π΅ΡΡ‚ΡŒ Π΄Π°Π½Π½Ρ‹Π΅ { crc ^= *pcBlock++; // ксорим ΠΎΡ‡Π΅Ρ€Π΅Π΄Π½ΠΎΠΉ Π±Π°ΠΉΡ‚ for (i = 0; i < 8; i++) // примСняСм ΠΏΠΎΠ»ΠΈΠ½ΠΎΠΌ. Ρ‚ΡƒΡ‚ просто ксорим ΠΈ/ΠΈΠ»ΠΈ сдвигаСм. crc = crc & 0x80 ? (crc << 1) ^ 0x31 : crc << 1; } return crc; }

In principle, if the polynom is empty, the result is simply sequentially proxied bytes (for crc8) or ints (for crc32).

Wikipedia describes the different values ​​of polynomials and initial values ​​(all those magic constants) for various modifications of the algorithm. Which one to choose is a difficult task; here mathematicians let them sit and think. For their applications, the main thing is that the two algorithms have the same algorithm.