Reused parameters and algorithms

vovagorodok commented 1 year ago

What was changed:

Moved source code to src folder
Created CrcParameters.h where all CRC parameters will be stored instead only polynomes. Reused this param constants everywhere.
CRC32 class and crc32 func now use default CRC32 params
Created specific yieldAdd() methods and yieldCrc..() functions instead yeald by default
crc..() functions now use the same codebase as classes
Created FastCRC32 based on lookup table for default CRC32

Proposed to change:

Rename getCRC() methods to calc() or calculate()
Rename crc..() functions to calcCRC..()

RobTillaart commented 1 year ago

Thanks for these explanations, I'll try to review this week.

RobTillaart commented 1 year ago

Changing default behavior is probably the cause of the fail of the unit test Please be aware that existing projects depend on earlier defaults.

vovagorodok commented 1 year ago

Fixed CRC64 crc(); was interpreted as function

Changing default behavior is probably the cause of the fail of the unit test Please be aware that existing projects depend on earlier defaults.

Defaults are not the same only for CRC32, for other CRC types defaults were correct

vovagorodok commented 1 year ago

Ahh CRC64_test.ino was not compiled by me because printHelpers.h. Fixed

vovagorodok commented 1 year ago

How you run all CI jobs locally?

RobTillaart commented 1 year ago

I don't => on the github of Arduino-CI there is an installation guide, so it is very well possible you need to install ruby and more (and keep that in sync)

RobTillaart commented 1 year ago

I don't => on the github of Arduino-CI there is an installation guide, so it is very well possible you need to install ruby and more (and keep that in sync)

RobTillaart commented 1 year ago

I don't => on the github of Arduino-CI there is an installation guide, so it is very well possible you need to install ruby and more (and keep that in sync)

RobTillaart commented 1 year ago

I don't => on the github of Arduino-CI there is an installation guide, so it is very well possible you need to install ruby and more (and keep that in sync)

vovagorodok commented 1 year ago

GitHub is a bit laggy today. Works locally. Forgot about mask 0x0FFF in CRC12::getCRC(). Tests passed. Commit is pushed but not processed it github yet

vovagorodok commented 1 year ago

Opened questions:

Rename getCRC() methods to calc() or calculate()
Rename crc..() functions to calcCRC..()
Rename reverse8 to reverse8bits. Or move names back? Or other names?
This topic: https://github.com/RobTillaart/CRC/pull/32#discussion_r1188670099
Separate yield.. functionality. Or maybe rename yieldAdd(array, length, yieldPeriod) to add(array, length, yieldPeriod) and remove add(array, length)?

RobTillaart commented 1 year ago

Opened questions:

Rename getCRC() methods to calc() or calculate()

I prefer calc() over calculate()

Rename crc..() functions to calcCRC..()

I like the short CRC..() function name but you want it to be more distinct from the class name? am I correct? No real problem with it.

Rename reverse8 to reverse8bits. Or move names back? Or other names?

OK, reverseXXbits is more descriptive The link to the bitHelper library gets lost a bit.

Note: in my libraries thus far I introduced new function names side by side to the old as depreciated interface. So people get time to get used to the new ones. Too much work here.

(other answers wil come asap)

RobTillaart commented 1 year ago

Opened questions

Separate yield.. functionality. Or maybe rename yieldAdd(array, length, yieldPeriod) to add(array, length, yieldPeriod) and remove add(array, length)?

Can you explain why you want the yield() function configurable per loop iteration ? The name yieldPeriod sounds like a duration of time, while one configures # loops. This is only to be understood by expert users.

Code wise:

void CRC12::yieldAdd(const uint8_t *array, size_t length, size_t yieldPeriod)
{
  while (length--)
  {
    add(*array++);
    if ((_count % yieldPeriod) == 0) yield();
  }
}

The modulo is expensive and executed for every byte. I would propose a simple (countdown) counter.

void CRC12::yieldAdd(const uint8_t *array, size_t length, size_t yieldPeriod)
{
  size_t _period = yieldPeriod;
  while (length--)
  {
    add(*array++);
    if (--period == 0)  //  subtraction to remove expensive modulo
    {
      yield();
      period = yieldPeriod
    }
  }
}

Another thought:

Breaking the add() function in two (one with one without yield) makes code more confusing imho. Could be solved by making yieldPeriod default zero if one does not need yield()?

//  give yieldPeriod a default value of  0  for no yield
//  should be done in the CRC12.h file of course but to get the idea
void CRC12::add(const uint8_t *array, size_t length, size_t yieldPeriod = 0)    
{
  size_t period = yieldPeriod;
  while (length--)
  {
    add(*array++);
    if (yieldPeriod == 0) continue;  //  skip yield code if period = 0;, compare to zero is fast.
    if (--period == 0)
    {
      yield();
      period = yieldPeriod
    }
  }
}

Recall in my original code I have the variable _canYield and when this is never set to true, the compiler optimizes the yield block away.

RobTillaart commented 1 year ago

Openend questions

This topic: https://github.com/RobTillaart/CRC/pull/32#discussion_r1188670099

CRC16-CCITT 0xFFFF or 0x0000 ?

http://zorc.breitbandkatze.de/crc.html (uses 0xFFFF as default for CRC-CCITT)
https://srecord.sourceforge.net/crc16-ccitt.html#:~:text=According%20to%20the%20document%20by,%E2%80%9D%20CRC16%2DCCITT%20is%200xFFFF.
https://www.lddgo.net/en/encrypt/crc (let select both

To support both create a CRC16 _CCITT and CRC16_CCITT_FALSE in the CRCparameters Think that is the best solution.

And yes there is discussion about it on the net, users are free to choose their parameters in the end,

RobTillaart commented 1 year ago

you could change the authors part in library.json as you are spending serious time on this lib.

  "authors":
  [
    {
      "name": "Rob Tillaart",
      "email": "Rob.Tillaart@gmail.com",
      "maintainer": true
    }
  ]

==>

  "authors":
  [
    {
      "name": "Rob Tillaart",
      "email": "Rob.Tillaart@gmail.com",
      "maintainer": true
    },
    {
      "name": "vovagorodok",
    }
  ]

(working on some other projects this week, so time is limited)

vovagorodok commented 1 year ago

Note: in my libraries thus far I introduced new function names side by side to the old as depreciated interface. So people get time to get used to the new ones. Too much work here.

Added deprecated functions/mathods

Can you explain why you want the yield() function configurable per loop iteration ? The name yieldPeriod sounds like a duration of time, while one configures # loops. This is only to be understood by expert users.

No need to add yield logic for void add(uint8_t value); because it can be easly solved externally when needed. Period doesn't sounds for me like a duration of time. Can rename to something else if you prefer.

The modulo is expensive and executed for every byte. I would propose a simple (countdown) counter.

Good point. Done.

Breaking the add() function in two (one with one without yield) makes code more confusing imho. Could be solved by making yieldPeriod default zero if one does not need yield()?

Decided to just rename yieldAdd to add instead default yieldPeriod in order to avoid additional logic in add method Looks more clear now. Please take a look.

Recall in my original code I have the variable _canYield and when this is never set to true, the compiler optimizes the yield block away.

Not sure. enable/disableYield() are public methods and can be changed from another TU (Translation Unit). That why compliler does not optimize it. Dont know if such optimizations can be done by linker with LTO (Link time optimization).

To support both create a CRC16 _CCITT and CRC16_CCITT_FALSE in the CRCparameters Think that is the best solution.

Done

vovagorodok commented 1 year ago

you could change the authors part in library.json as you are spending serious time on this lib.

Done. Thanks!

vovagorodok commented 1 year ago

What about version? 0.4.0?

RobTillaart commented 1 year ago

What about version? 0.4.0?

0.4.0 is OK, Given the amount of changes 1.0.0 could be better.

vovagorodok commented 1 year ago

ok, I'll change it

RobTillaart commented 1 year ago

Version number should also be updated in

library.json
library.properties

vovagorodok commented 1 year ago

Done. I have a question. Why we need both library. files? Think about this in my libraries, should I have only .json or both there

RobTillaart commented 1 year ago

library.properties is used by the Arduino library manager (and some derived sites)
library.json is used by platform.io and maybe more

I intend to add CMakeLists.txt files too in the future (low prio)

vovagorodok commented 1 year ago

@RobTillaart any updates?

RobTillaart commented 1 year ago

Sorry too busy with other tasks that have priority.

RobTillaart commented 1 year ago

Found a few hours to do a comparison test with ESP32 and UNO using the CRC_performance.ino example. (IDE 1.8.19)

For ESP32 things look just fine, UNO (AVR) pays a serious penalty. Opinion?

Arduino UNO (16 MHz)

Compile size

Version	Size / vars
0.3.3	5184 / 512
1.0.0	6018 / 512
Diff	830 / 0

The 1.0.0 version has a larger footprint (for UNO this is substantial). As the sketch uses 4 CRC's it is not representative, but even 1/4 == 200+ bytes is quite a lot for an UNO.

Runtimes

algo	output 0.3.3	output 1.0.0	time 0.3.3	time 1.0.0	delta %
CRC8	2	2	412	800	+94%
CRC8	3E	3E	580	964	+66%
CRC16	6E99	6E99	1016	1120	+10%
CRC16	7480	7480	1208	1288	+07%
CRC32	50FD78E4	50FD78E4	760	1824	+140%
CRC32	1D73421	1D73421	992	2004	+102%
CRC64	BFF3AA1C182ABDB1	BFF3AA1C182ABDB1	5084	7380	+45%
CRC64	451DF73FA9BFFA5A	451DF73FA9BFFA5A	5176	7608	+47%

Output is identical (as should be).
Timing is worse than expected. (CRC64 is imho less important, but CRC8 and CRC32 are)

ESP32 (240 MHz)

Compile size

less interesting as sufficient RAM.

Runtimes

algo	output 0.3.3	output 1.0.0	time 0.3.3	time 1.0.0	delta %
CRC8	2	2	66	65	-01%
CRC8	3E	3E	61	61	+00%
CRC16	6E99	6E99	61	61	+00%
CRC16	7480	7480	66	66	+00%
CRC32	50FD78E4	50FD78E4	63	63	+00%
CRC32	1D73421	1D73421	67	66	-01%
CRC64	BFF3AA1C182ABDB1	BFF3AA1C182ABDB1	81	80	-01%
CRC64	451DF73FA9BFFA5A	451DF73FA9BFFA5A	91	91	+00%

Output is identical (as should be).
Timing is identical or a minor gain.

vovagorodok commented 1 year ago

Hmm, only one serious difference I see. Perhaps it's an issue. In 1.0.0 we use common type for length/size size_t (perhaps uint32_t everywhere). Before was uint16_t. Perhaps for UNO (8bit architecture) is hard to calculate 32bit values.

What if use custom type for size:

#if defined(CRC_CUSTOM_SIZE)
using crc_size_t = CRC_CUSTOM_SIZE;
#elif defined(__AVR__)
using crc_size_t = uint16_t;
#else
using crc_size_t = size_t;
#endif

?

vovagorodok commented 1 year ago

For binary size of UNO perhaps compiler/linker for avr doesn't optimize code as gcc for esp32. We can remove FastCRC32 and check if binary size become less

RobTillaart commented 1 year ago

For binary size of UNO perhaps compiler/linker for avr doesn't optimize code as gcc for esp32. We can remove FastCRC32 and check if binary size become less

Manually removed the FastCRC32 gave the same binary size. So that works well.

No time today to do the size_t test, maybe later this week. Yes AVR is 16 bit intern, so yes it can be the cause.

vovagorodok commented 1 year ago

Let's check it. I'll prepare commit with crc_size_t today

vovagorodok commented 1 year ago

Manually removed the FastCRC32 gave the same binary size. So that works well.

I see. We left a lot of deprecated functions and methods:

[[deprecated("Use reverse8bits() instead")]] uint8_t reverse8(uint8_t in);
[[deprecated("Use reverse12bits() instead")]] uint16_t reverse16(uint16_t in);
[[deprecated("Use reverse16bits() instead")]] uint16_t reverse12(uint16_t in);
[[deprecated("Use reverse32bits() instead")]] uint32_t reverse32(uint32_t in);
[[deprecated("Use reverse64bits() instead")]] uint64_t reverse64(uint64_t in);

[[deprecated("Use calcCRC8() instead")]]
uint8_t crc8(...)

and for 12, 16..

  [[deprecated("Use calc() instead")]]
  uint64_t getCRC() const;
  [[deprecated("Use setInitial() instead")]]
  void setStartXOR(uint64_t initial) { _initial = initial; }
  [[deprecated("Use setXorOut() instead")]]
  void setEndXOR(uint64_t xorOut) { _xorOut = xorOut; }
  [[deprecated("Use getInitial() instead")]]
  uint64_t getStartXOR() const { return _initial; }
  [[deprecated("Use getXorOut() instead")]]
  uint64_t getEndXOR() const { return _xorOut; }
  [[deprecated("Use add() with yieldPeriod instead")]]
  void enableYield() const {}
  [[deprecated("Use add() without yieldPeriod instead")]]
  void disableYield() const {}

and for 12, 16..

That why binary size is higher. After removing them I think binary size should be less even than 0.3.3, because we reuse a lot of code in 1.0.0

vovagorodok commented 1 year ago

In stddef.h of UNO:

#ifndef __SIZE_TYPE__
#define __SIZE_TYPE__ long unsigned int
#endif
#if !(defined (__GNUG__) && defined (size_t))
typedef __SIZE_TYPE__ size_t;

RobTillaart commented 1 year ago

Quick test in my coffee break, disabled the deprecated functions and patched the test

6018 ==> 5894 versus 5184 (0.3.3)

vovagorodok commented 1 year ago

I think that for CRC.h will be a bit higher because we use algorithms from classes inside functions and class is linked when we use a function.

Binary size will be lower than 0.3.3 when we use functions and classes.

For this moment cant find solution to not duplicate code and not reuse classes. Have an idea?

vovagorodok commented 1 year ago

Not sure if we should consider CRC_reference_test result for that, because it uses all possible CRC functions in one test (binary). For CRC32_test binary size is 2450 (library overhaed ~2000 bytes) for ver 1.0.0. CRC32_test for ver 0.3.3 has binary size 2708

RobTillaart commented 1 year ago

Quick check latest version => CRC16 has improved a lot, others are (nearly)identical to previous 1.0.0

Good step forward

CRC_performance.ino
Calculating CRC of 100 bytes message

CRC8:   2
TIME:   800
CRC8:   3E
TIME:   964
=============================
CRC16:  6E99
TIME:   552     (was 1120)
CRC16:  7480
TIME:   724    (was 1288)
=============================
CRC32:  50FD78E4
TIME:   1820
CRC32:  1D73421
TIME:   2004
=============================
CRC64:  BFF3AA1C182ABDB1
TIME:   7384
CRC64:  451DF73FA9BFFA5A
TIME:   7616
=============================

vovagorodok commented 1 year ago

Next possible issue that I see:

void CRC32::add(const uint8_t *array, crc_size_t length)
{
  while (length--)
  {
    add(*array++);
  }
}

We call add() each time instead of direct calculations in 0.3.3. Method calling can cost

Maybe change:

void CRC32::add(uint8_t value)
{
  _count++;

  if (_reverseIn) value = reverse8bits(value);
  _crc ^= ((uint32_t)value) << 24;
  for (uint8_t i = 8; i; i--) 
  {
    if (_crc & (1UL << 31))
    {
      _crc <<= 1;
      _crc ^= _polynome;
    }
    else
    {
      _crc <<= 1;
    }
  }
}

as inline function?

vovagorodok commented 1 year ago

Lets prepare small check before. Changed reverse8bits as inline

vovagorodok commented 1 year ago

I bought a board in order to check. Changing functions to inline doesn't help. But in function uint32_t calcCRC32(...) when was changed from:

CRC32 crc(polynome, initial, xorOut, reverseIn, reverseOut);
crc.add(array, length);
return crc.calc();

to:

CRC32 crc(polynome, initial, xorOut, reverseIn, reverseOut);
while (length--)
{
  crc.add(*array++);
}
return crc.calc();

calculation time was decreased from:

=============================
CRC32:  50FD78E4
TIME:   1820
CRC32:  1D73421
TIME:   2004

to:

=============================
CRC32:  50FD78E4
TIME:   776
CRC32:  1D73421
TIME:   948

Hmm, crc.add(array, length); does the same job (only while with length decrementation). Don't know what happens for this moment. AVR compiler issue?

RobTillaart commented 1 year ago

Could be an AVR issue, I expect to (squash and) merge your work coming weeks, there might be some loose ends but those can be handled separately. Merging will get more feedback from other users, which is important.

RobTillaart commented 1 year ago

Lots of work piles up, so sorry this one does not get attention. I might do an update to move the sources to a src folder. That allows an easier compare of the sum of all your commits against the last version.

RobTillaart / CRC