cfriedt/crcx

LibCRCx

crcx's Issues

testcase for rfc1662

It would be good to demonstrate support for the CRC-16 and CRC-32 algorithms in rfc1662.

Add support for CRC's that are not a multiple of 8 in length

Ideally, this would be done after most / all optimizations are already complete so that it can take advantage of fast paths and so that the amount of code that needs to be refactored is minimized.

Therefore, I suggest that this be done after #10

Create a nice github site

Add performance-based tests

It would be absolutely necessary to ensure that these performance-based tests were testing the CPU rather than memory. However, being cache-oblivious is also... well.. oblivious.
CRC is an interesting computation, for one because the entire table can be kept in L1 cache, so large blocks of input can be preloaded.

Preloading will likely come into play in #40.

Add SIMD

A couple of architectures (at least) have cpu instructions that are targeted at crc computation.

It would be interesting to take advantage of them.

A common approach is to do crc calculations in groups of 4. Some compilers have auto-vectorization optimizations that take care of that.

Another possible approach is to do create hand-optimized inline assembly routines that are capable of computing the crc using N, N/2, N/4, ... 1 very quickly, where N is the number of SIMD registers.

I'm familiar with 32-bit NEON SIMD, and (to some extent) MMX SIMD, but I haven't looked at any of the SSE family of instructions on x86_64.

The other main concern is that I would likely only be initially comfortable doing this in GCC style assembly language (and, even then, mainly 32-bit ARM).

It will likely be an iterative improvement over time.

Conditional compilation targets for different compilers ISAs (e.g. clang & gcc would build .S files, and msvc or something else would build .asm files).

For that reason, it would be do this this well after #36.

Additionally, perf testing will be incredibly important at that point.

This will likely also pave the way for #10.

Add doxygen to crc3x.h

Also, take this time to rename the Cxx lib to libcrc3x instead of libcrcxxx

Look into C11 generics

Currently using uintmax_t for all tables / variables.
It's a huge space suck and waste of ram, probably also lowers cache efficiency / hit rate too.

It would be cool if there was a way to do this generically with C11.

Could require different structs as well as different function implementations. Function implementations may be doable in one go with yet another abuse of macros.

Add linter option to configure.ac

Previously Makefile.old used to run the clang-tidy linter. We should check if its available in configure.ac and then add targets in enable that stage in test/Makefile.am .

Refactor Polynomial parameter placement in crcx_init()

The Crc3x C++ class orders template parameters as <type, N, poly>. However, the crcx_init() API call orders parameters as crcx_init (struct crcx_ctx *ctx, uint8_t n, uintmax_t init, uintmax_t fini, uintmax_t poly, bool reflect_input, bool reflect_output).

It would probably be more intuitive to modify the C api to be crcx_init (struct crcx_ctx *ctx, uint8_t n, uintmax_t poly, uintmax_t init, uintmax_t fini, bool reflect_input, bool reflect_output) and would be a bit more consistent with the C++ API

Fix CRC16

[ RUN      ] CRCx.Sunshine_CRC16_CCIT_ZERO
crcx-test.cpp:227: Failure
Expected equality of these values:
  actual_uintmax
    Which is: 11890
  expected_uintmax
    Which is: 12739
The calculated CRC is incorrect
[  FAILED  ] CRCx.Sunshine_CRC16_CCIT_ZERO (1 ms)

Install headers under crcx/

Installing headers directly to e.g. /usr/include/ is not very friendly.

Use a static analyzer

clang's scan-build would be a good choice

https://clang-analyzer.llvm.org/

https://android.googlesource.com/toolchain/llvm/+/release_34/autoconf/configure.ac

https://clang-analyzer.llvm.org/scan-build.html

Figure out how allow_failures works with travis

Ideally it would be possible to have some included builds and then have some with allow_failures to be set, but that does not seem to work.

Ideally we would never allow a single commit to break any of the builds, but there may be cases where a particular changeset is split up over several commits, and it can be anticipated.

In that case, it would be ideal to display which builds are broken and which are successful.

Maybe it's best to allow failures for any of the items in the build matrix except for tagged releases.

There should be some info on the travis site about how to achieve that.

This is related to #37

Fix s390x / Big-Endian Issues

The LibCRCx (C API) tests that were failing. The Sanity and LibCRC3x (C++ API) tests are all fine.

Since the build works from for 3 little-endian architectures, I assume that this is due to the big-endian s390x architecture.

This was discovered in #36.

https://travis-ci.com/github/cfriedt/crcx/jobs/318598400

Running main() from /tmp/googletest/googletest/src/gtest_main.cc
[==========] Running 26 tests from 2 test suites.
[----------] Global test environment set-up.
[----------] 13 tests from Sanity
[ RUN      ] Sanity.ctx_null
[       OK ] Sanity.ctx_null (1 ms)
[ RUN      ] Sanity.poly_zero
[       OK ] Sanity.poly_zero (0 ms)
[ RUN      ] Sanity.poly_highest_bit_greater_than_n
[       OK ] Sanity.poly_highest_bit_greater_than_n (0 ms)
[ RUN      ] Sanity.n_zero
[       OK ] Sanity.n_zero (0 ms)
[ RUN      ] Sanity.n_not_a_multiple_of_8
[       OK ] Sanity.n_not_a_multiple_of_8 (0 ms)
[ RUN      ] Sanity.n_greater_than_sizeof_uintmax
[       OK ] Sanity.n_greater_than_sizeof_uintmax (0 ms)
[ RUN      ] Sanity.msb_invalid
[       OK ] Sanity.msb_invalid (0 ms)
[ RUN      ] Sanity.mask_invalid
[       OK ] Sanity.mask_invalid (1 ms)
[ RUN      ] Sanity.mask_invalid64
[       OK ] Sanity.mask_invalid64 (0 ms)
[ RUN      ] Sanity.invalid_ctx_tries_to_generate_table
[       OK ] Sanity.invalid_ctx_tries_to_generate_table (0 ms)
[ RUN      ] Sanity.invalid_param_to_crcx_init
[       OK ] Sanity.invalid_param_to_crcx_init (0 ms)
[ RUN      ] Sanity.invalid_ctx_to_crcx_fini
[       OK ] Sanity.invalid_ctx_to_crcx_fini (1 ms)
[ RUN      ] Sanity.invalid_ctx_to_crcx
[       OK ] Sanity.invalid_ctx_to_crcx (0 ms)
[----------] 13 tests from Sanity (6 ms total)
[----------] 13 tests from LibCRCx
[ RUN      ] LibCRCx.Wikipedia_example1
crcx-test.cpp:235: Failure
Value of: ::crcx_init(&ctx, 8, 0, 0, 0b100000111, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Wikipedia_example1 (6 ms)
[ RUN      ] LibCRCx.Sunshine_CRC8
crcx-test.cpp:295: Failure
Value of: ::crcx_init(&ctx, 8, 0, 0, 0x07, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC8 (1 ms)
[ RUN      ] LibCRCx.Sunshine_CRC8_ITU
crcx-test.cpp:321: Failure
Value of: ::crcx_init(&ctx, 8, 0, 0x55, 0x07, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC8_ITU (1 ms)
[ RUN      ] LibCRCx.Sunshine_CRC8_DARC
crcx-test.cpp:347: Failure
Value of: ::crcx_init(&ctx, 8, 0, 0, 0x39, true, true)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC8_DARC (0 ms)
[ RUN      ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_one_byte
crcx-test.cpp:372: Failure
Value of: ::crcx_init(&ctx, 16, 0, 0, 0x1021, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_one_byte (1 ms)
[ RUN      ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_incremental
crcx-test.cpp:441: Failure
Value of: ::crcx_init(&ctx, 16, 0, 0, 0x1021, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_incremental (1 ms)
[ RUN      ] LibCRCx.Sunshine_CRC16_CCIT_ZERO
crcx-test.cpp:471: Failure
Value of: ::crcx_init(&ctx, 16, 0, 0, 0x1021, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO (1 ms)
[ RUN      ] LibCRCx.Sunshine_CRC32_POSIX
crcx-test.cpp:521: Failure
Value of: ::crcx_init(&ctx, 32, 0, -1, 0x4c11db7, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC32_POSIX (0 ms)
[ RUN      ] LibCRCx.Sunshine_CRC64_ECMA_182
crcx-test.cpp:587: Failure
Value of: ::crcx_init(&ctx, 64, 0, 0, 0x42F0E1EBA9EA3693, false, false)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.Sunshine_CRC64_ECMA_182 (1 ms)
[ RUN      ] LibCRCx.reflect24
[       OK ] LibCRCx.reflect24 (1 ms)
[ RUN      ] LibCRCx.board_example1
crcx-test.cpp:728: Failure
Value of: ::crcx_init(&ctx, ble_crc_n, ble_init, ble_fini, ble_poly, ble_reflect_input, ble_reflect_output)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.board_example1 (0 ms)
[ RUN      ] LibCRCx.nrf_support1
crcx-test.cpp:763: Failure
Value of: ::crcx_init(&ctx, ble_crc_n, ble_init, ble_fini, ble_poly, ble_reflect_input, ble_reflect_output)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.nrf_support1 (1 ms)
[ RUN      ] LibCRCx.ble_core_52_4_2_1_Legacy_Advertising_PDUs
crcx-test.cpp:799: Failure
Value of: ::crcx_init(&ctx, ble_crc_n, ble_init, ble_fini, ble_poly, ble_reflect_input, ble_reflect_output)
  Actual: false
Expected: true
[  FAILED  ] LibCRCx.ble_core_52_4_2_1_Legacy_Advertising_PDUs (1 ms)
[----------] 13 tests from LibCRCx (15 ms total)

[----------] Global test environment tear-down
[==========] 26 tests from 2 test suites ran. (28 ms total)
[  PASSED  ] 14 tests.
[  FAILED  ] 12 tests, listed below:
[  FAILED  ] LibCRCx.Wikipedia_example1
[  FAILED  ] LibCRCx.Sunshine_CRC8
[  FAILED  ] LibCRCx.Sunshine_CRC8_ITU
[  FAILED  ] LibCRCx.Sunshine_CRC8_DARC
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_one_byte
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO_incremental
[  FAILED  ] LibCRCx.Sunshine_CRC16_CCIT_ZERO
[  FAILED  ] LibCRCx.Sunshine_CRC32_POSIX
[  FAILED  ] LibCRCx.Sunshine_CRC64_ECMA_182
[  FAILED  ] LibCRCx.board_example1
[  FAILED  ] LibCRCx.nrf_support1
[  FAILED  ] LibCRCx.ble_core_52_4_2_1_Legacy_Advertising_PDUs

12 FAILED TESTS
Running main() from /tmp/googletest/googletest/src/gtest_main.cc
[==========] Running 12 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 12 tests from LibCRC3x
[ RUN      ] LibCRC3x.Wikipedia_example1
[       OK ] LibCRC3x.Wikipedia_example1 (3 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC8
[       OK ] LibCRC3x.Sunshine_CRC8 (1 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC8_ITU
[       OK ] LibCRC3x.Sunshine_CRC8_ITU (0 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC8_DARC
[       OK ] LibCRC3x.Sunshine_CRC8_DARC (0 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC16_CCIT_ZERO_one_byte
[       OK ] LibCRC3x.Sunshine_CRC16_CCIT_ZERO_one_byte (0 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC16_CCIT_ZERO
[       OK ] LibCRC3x.Sunshine_CRC16_CCIT_ZERO (1 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC32_POSIX
[       OK ] LibCRC3x.Sunshine_CRC32_POSIX (0 ms)
[ RUN      ] LibCRC3x.Sunshine_CRC64_ECMA_182
[       OK ] LibCRC3x.Sunshine_CRC64_ECMA_182 (0 ms)
[ RUN      ] LibCRC3x.reflect24
[       OK ] LibCRC3x.reflect24 (0 ms)
[ RUN      ] LibCRC3x.board_example1
[       OK ] LibCRC3x.board_example1 (1 ms)
[ RUN      ] LibCRC3x.nrf_support1
[       OK ] LibCRC3x.nrf_support1 (0 ms)
[ RUN      ] LibCRC3x.ble_core_52_4_2_1_Legacy_Advertising_PDUs
[       OK ] LibCRC3x.ble_core_52_4_2_1_Legacy_Advertising_PDUs (0 ms)
[----------] 12 tests from LibCRC3x (7 ms total)

[----------] Global test environment tear-down
[==========] 12 tests from 1 test suite ran. (13 ms total)
[  PASSED  ] 12 tests.

Add pkg-config files

Should add a template under src/crcx.pc.in that gets preprocessed by configure.

A good automated test would also be to ensure that a user application can be compiled and linked. This would need to be done after installing, so in .travis.yml

Add some buttons to the README

Deploy Doxygen to GH-Pages

Might also be useful to make a landing page - libcrcx.github.io?

Display Badges For Each Job In' the Build Matrix

Related to #36

Although it seems pretty darn intuitive to display the individual build statuses of a build matrix using different badges displayed as a matrix, travis-ci is not directly supporting it, because it seems to be a niche uses case.

Doing so would not require any additional changes to the .travis.yml spec (at most, users may want to name their jobs, which is already supported).

Anyway, travis-ci is not directly supporting it.

travis-ci/travis-ci#5035 (comment)

They suggest using a 3rd party API to query the build status.

Fix CRC32

[ RUN      ] CRCx.Sunshine_CRC32_POSIX
crcx-test.cpp:282: Failure
Expected equality of these values:
  actual_v
    Which is: { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... }
  expected_v
    Which is: { 0, 79764919, 159529838, 222504665, 319059676, 398814059, 445009330, 507990021, 638119352, 583659535, 797628118, 726387553, 890018660, 835552979, 1015980042, 944750013, 1276238704, 1221641927, 1167319070, 1095957929, 1595256236, 1540665371, 1452775106, 1381403509, 1780037320, 1859660671, 1671105958, 1733955601, 2031960084, 2111593891, 1889500026, 1952343757, ... }
The generated table is incorrect
[  FAILED  ] CRCx.Sunshine_CRC32_POSIX (1 ms)

Get windows build working

Found some extra information here:
https://travis-ci.community/t/autoconf-automake/964/4

I honestly think it would be a heck of a lot easier to just use cmake here (issue #16), so I might just end up doing that first.

Fix macOS Build

The osx build is failing because tests cannot be linked with "-lgcov".

It's worth noting that gcc is an alias for clang and g++ is an alias for clang++ on osx.

If gcov integration is not possible, it's probably fair to just disable test coverage for anything other than linux / amd64.

https://travis-ci.com/github/cfriedt/crcx/jobs/318598402

Add multi-word algorithm

Use the algorithm developed at Google available in libcrcutil

There is a paper outlining the algorithm here.

Remove Makefile.old

Build Doxygen

Add clang to the build matrix

It's already there for macOS.. although it would be nice to I have it there for Linux as well.

Upload Builds of Tagged Releases to GitHub

Automatically upload builds of tagged releases to GH.

Related to #36

Fix CRC64

[ RUN      ] CRCx.Sunshine_CRC64_ECMA_182
crcx-test.cpp:342: Failure
Expected equality of these values:
  actual_v
    Which is: { 0, 13623140471917917843, 4102460140072885173, 9647207202101161254, 3687703099949351417, 10241823797472442218, 847670330492770892, 13172072025944157407, 2642017826432824673, 11071337875796460530, 2036903521235332820, 11622549157563291719, 1695340660985541784, 12288090609561600523, 3416493358543007533, 10549344092192889278, 838878467555875921, 13162708417809115842, 3695931677883369444, 10251750020595331447, 4073807042470665640, 9621395243829619515, 29216399801746973, 13648389832364699790, 3390681321971083568, 10520690918406315939, 1720589945147306629, 12317306930895193110, 2027539972205439177, 11613757355914681946, 2651944110676226940, 11079566512734963183, ... }
  expected_v
    Which is: { 0, 4823603603198064275, 9647207206396128550, 14344283933443513269, 5274672035359026399, 847670339082705484, 14759040976900489721, 10241823793177474922, 10549344070718052798, 15030250704074698541, 1695340678165410968, 6158653484774949387, 15804726273676621153, 11071337880091427826, 6824194888265062471, 2036903512645398228, 7367177604490692079, 2651944067726553980, 16419204125234161865, 11613757334439845466, 3390681356330821936, 7926053118503640995, 12317306969549898774, 16726154088988619397, 17607865585094646865, 13162708473643690690, 8194994013375312247, 3695931686473304036, 13648389776530124942, 18417527692557321757, 4073807025290796456, 8825348881154370363, ... }
The generated table is incorrect
[  FAILED  ] CRCx.Sunshine_CRC64_ECMA_182 (14 ms)

fini methods should reset the lfsr

The LFSR (Linear Feedback Shift Register) holds all of the state necessary for the CRC to be either updated with a new value or finalized.

When the CRC is finalized, the LFSR should be reset to the initialization value so that the same CRC object or context can be reused for repeated, successive CRC computation.

Add debug option to configure.ac

Create a Build Matrix

Travis supports a number of different architectures and operating systems. It would be nice to build for each of those architectures and operating systems automatically (e.g. to discover portability bugs, word-size bugs, or endianness bugs). This looks like it would be a good starting point.

jobs:
  include:
   - os: linux
     arch: amd64
   - os: linux
     arch: arm64

It would probably be smart to turn the configure flags and environment variables into yaml variables to be passed to each of the jobs in the build matrix.

Ideally we would be able to to perform coverage on each platform and display badges. That could be a separate ticket.

If we're building them anyway, for tagged releasees, we may as well also create build artifacts that get uploaded to the release page. That could be a separate ticket.

Additionally, it would be nice to use multiple compilers (gcc, clang, msvc, an obscure embedded one, and allow for a build mode (debug, release), thus making our build matrix 4-dimensional.

(arch, os, compiler, mode)

BLE v5.2 CRC-24 tests

Optimize reflect

There is a pretty simple way to optimize reflect() in the case where N (the number of bits) is a multiple of 4 (or 8). We can use a LUT of length 16 (or 256) where each entry in the LUT is simply the bit-reversed entry of its index. This would mean that all reflect() calls would be O( log( N ) ) operations rather than O( N ). Possibly for embedded systems we may want to use a LUT of length 16, but on most systems 256 bytes is nothing significant.

At runtime, reflect could be optimized by using machine-specific instructions. E.g. on ARM this would correspond to RBIT and on x86_64 this would correspond to ??. There is a longstanding bug in GCC to provide a compiler builtin specifically for this purpose.

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50481

It would be nice to quantize the speedup as well. That will likely involve pre-generating a significant amount of random data of varying word-lengths and then calling the function repeatedly, then dividing the total execution time by the number of calls made to reflect().

Doing this with C++ templates is pretty straight forward. I would like to look into C11 generics (issue #13) before this is done though, since that could simplify the C API.

Make compiler warnings more strict

Noticed that the c / c++ compilers were not being called with -Wall -Wextra -Werror, which I though I specified in src/Makefile.am.

Fixed that.

Bumped C++ standard to C++17 so that the CRC table can use the inline keyword. I'm not really sure how static members of templates are specified otherwise.

support cmake

Add a proper C++ API

This will probably just be templated so that there is a constexpr LUT for any templated type T (e.g. uint8_t, uint16_t, uint32_t, uint64_t. The tricky part will be things like 24-bit CRC's - is it possible to round up to a multiple of 8 in templates?

Add coverage option to configure.ac

Previously with Makefile.old, we used to run code coverage as part of the regular build.

It should definitely be run as part of CI with make check still, and Codecov should be updated still.

Switch to GitHub Actions for Ci

Travis seems to be losing steam. Builds take a very long time. GitHub Actions should support macOS and Windows environments shortly, if not already, so that would likely be the best solution.

Look into Coveralls.io Instead of Codecov

https://coveralls.io/

Improve README.md

Make it look pretty
https://gist.github.com/fvcproductions/1bfc2d4aecb01a834b46

Fix Windows Build

The windows build fails due to the lack of a number of autotools programs.

Need to find out how to install those via chocolatey.

https://travis-ci.com/github/cfriedt/crcx/jobs/318598404

Possible lead:

choco install -r --no-progress -y zip xz iwget autoconf libtool automake make autoconf-archive pkg-config

https://travis-ci.community/t/autoconf-automake/964

Use Precompiled GoogleTest

To reduce build times, it would be helpful to not build gtest / gmock from source every single time the build runs.

There are a couple of Ubuntu packages

• libgtest-dev
• googletest

The former contains a slightly older version of gtest (1.8.0 whereas current is 1.10.0) but it does include precompiled static libraries (libgtest.a and libgtest_main.a). However, the former does not include any pkg-config files.
The latter contains the source files for gtest and gmock but not a precompiled binary it is also stuck at version 1.8.0. It does not contain any precompiled libraries.

Since we're using pkg-config in configure.ac, we can override the following variables.

  GTEST_CFLAGS
              C compiler flags for GTEST, overriding pkg-config
  GTEST_LIBS  linker flags for GTEST, overriding pkg-config

That should allow us to support both the former option (libgtest-dev) as well as the built-from-source googletest (i.e. the "proper" way which installs pkg-config files) as well.

These packages do not have regular installations (with C++ libraries) likely because they are written in C++ and contain vtable information that will change from build to build. Therefore the ABI is unstable (even though the API is certainly stable).

For this ticket, I'll see if I can adjust the .travis-ci.yml file to use Ubuntu's pre-packaged libgtest-dev

Convert to an Autotools project