CRC32 Koopman? 256 length tables?

[JPHutchins]

I was listening to this great discussion with Philip Koopman that gave me a few ideas: https://embedded.fm/episodes/473

1. Should we add an option to use 1024B of lookup instead of 64B? Room for SIMD or other optimizations?

   zephyr/lib/crc/crc32c_sw.c

   Line 4 in 5049ac4

   * SPDX-License-Identifier: Apache-2.0

2. Should we add the Koopman polynomial in addition to IEEE and Castagnoli?

[jukkar]

I am not a crc code maintainer nor I have answer to your question. You could propose a PR for this if you think it could be useful, at least at that point the answer is given. The 1kb lookup table sounds a bit large compared with just 64 bytes, but it is just a tradeoff with speed vs space.

[JPHutchins]

Looking fairly reasonable

uint32_t crc_k_4_2(uint32_t crc, uint8_t const * data, size_t len) {
#if IS_ENABLED(CONFIG_CRC32K_4_2_TABLE_256)

    /**
     * CRC table generated from polynomial 0xc9d204f5 CRC-32_K/4.2 (*op) (Koopman)
     *
     * pycrc --width 32 --poly 0xc9d204f5 --reflect-in False --xor-in 0 --reflect-out False --xor-out 0 --generate table --table-idx-width 8
     */
    static uint32_t const table[256] = {
        0x00000000, 0xc9d204f5, 0x5a760d1f, 0x93a409ea, 0xb4ec1a3e, 0x7d3e1ecb, 0xee9a1721, 0x274813d4,
        0xa00a3089, 0x69d8347c, 0xfa7c3d96, 0x33ae3963, 0x14e62ab7, 0xdd342e42, 0x4e9027a8, 0x8742235d,
        0x89c665e7, 0x40146112, 0xd3b068f8, 0x1a626c0d, 0x3d2a7fd9, 0xf4f87b2c, 0x675c72c6, 0xae8e7633,
        0x29cc556e, 0xe01e519b, 0x73ba5871, 0xba685c84, 0x9d204f50, 0x54f24ba5, 0xc756424f, 0x0e8446ba,
        0xda5ecf3b, 0x138ccbce, 0x8028c224, 0x49fac6d1, 0x6eb2d505, 0xa760d1f0, 0x34c4d81a, 0xfd16dcef,
        0x7a54ffb2, 0xb386fb47, 0x2022f2ad, 0xe9f0f658, 0xceb8e58c, 0x076ae179, 0x94cee893, 0x5d1cec66,
        0x5398aadc, 0x9a4aae29, 0x09eea7c3, 0xc03ca336, 0xe774b0e2, 0x2ea6b417, 0xbd02bdfd, 0x74d0b908,
        0xf3929a55, 0x3a409ea0, 0xa9e4974a, 0x603693bf, 0x477e806b, 0x8eac849e, 0x1d088d74, 0xd4da8981,
        0x7d6f9a83, 0xb4bd9e76, 0x2719979c, 0xeecb9369, 0xc98380bd, 0x00518448, 0x93f58da2, 0x5a278957,
        0xdd65aa0a, 0x14b7aeff, 0x8713a715, 0x4ec1a3e0, 0x6989b034, 0xa05bb4c1, 0x33ffbd2b, 0xfa2db9de,
        0xf4a9ff64, 0x3d7bfb91, 0xaedff27b, 0x670df68e, 0x4045e55a, 0x8997e1af, 0x1a33e845, 0xd3e1ecb0,
        0x54a3cfed, 0x9d71cb18, 0x0ed5c2f2, 0xc707c607, 0xe04fd5d3, 0x299dd126, 0xba39d8cc, 0x73ebdc39,
        0xa73155b8, 0x6ee3514d, 0xfd4758a7, 0x34955c52, 0x13dd4f86, 0xda0f4b73, 0x49ab4299, 0x8079466c,
        0x073b6531, 0xcee961c4, 0x5d4d682e, 0x949f6cdb, 0xb3d77f0f, 0x7a057bfa, 0xe9a17210, 0x207376e5,
        0x2ef7305f, 0xe72534aa, 0x74813d40, 0xbd5339b5, 0x9a1b2a61, 0x53c92e94, 0xc06d277e, 0x09bf238b,
        0x8efd00d6, 0x472f0423, 0xd48b0dc9, 0x1d59093c, 0x3a111ae8, 0xf3c31e1d, 0x606717f7, 0xa9b51302,
        0xfadf3506, 0x330d31f3, 0xa0a93819, 0x697b3cec, 0x4e332f38, 0x87e12bcd, 0x14452227, 0xdd9726d2,
        0x5ad5058f, 0x9307017a, 0x00a30890, 0xc9710c65, 0xee391fb1, 0x27eb1b44, 0xb44f12ae, 0x7d9d165b,
        0x731950e1, 0xbacb5414, 0x296f5dfe, 0xe0bd590b, 0xc7f54adf, 0x0e274e2a, 0x9d8347c0, 0x54514335,
        0xd3136068, 0x1ac1649d, 0x89656d77, 0x40b76982, 0x67ff7a56, 0xae2d7ea3, 0x3d897749, 0xf45b73bc,
        0x2081fa3d, 0xe953fec8, 0x7af7f722, 0xb325f3d7, 0x946de003, 0x5dbfe4f6, 0xce1bed1c, 0x07c9e9e9,
        0x808bcab4, 0x4959ce41, 0xdafdc7ab, 0x132fc35e, 0x3467d08a, 0xfdb5d47f, 0x6e11dd95, 0xa7c3d960,
        0xa9479fda, 0x60959b2f, 0xf33192c5, 0x3ae39630, 0x1dab85e4, 0xd4798111, 0x47dd88fb, 0x8e0f8c0e,
        0x094daf53, 0xc09faba6, 0x533ba24c, 0x9ae9a6b9, 0xbda1b56d, 0x7473b198, 0xe7d7b872, 0x2e05bc87,
        0x87b0af85, 0x4e62ab70, 0xddc6a29a, 0x1414a66f, 0x335cb5bb, 0xfa8eb14e, 0x692ab8a4, 0xa0f8bc51,
        0x27ba9f0c, 0xee689bf9, 0x7dcc9213, 0xb41e96e6, 0x93568532, 0x5a8481c7, 0xc920882d, 0x00f28cd8,
        0x0e76ca62, 0xc7a4ce97, 0x5400c77d, 0x9dd2c388, 0xba9ad05c, 0x7348d4a9, 0xe0ecdd43, 0x293ed9b6,
        0xae7cfaeb, 0x67aefe1e, 0xf40af7f4, 0x3dd8f301, 0x1a90e0d5, 0xd342e420, 0x40e6edca, 0x8934e93f,
        0x5dee60be, 0x943c644b, 0x07986da1, 0xce4a6954, 0xe9027a80, 0x20d07e75, 0xb374779f, 0x7aa6736a,
        0xfde45037, 0x343654c2, 0xa7925d28, 0x6e4059dd, 0x49084a09, 0x80da4efc, 0x137e4716, 0xdaac43e3,
        0xd4280559, 0x1dfa01ac, 0x8e5e0846, 0x478c0cb3, 0x60c41f67, 0xa9161b92, 0x3ab21278, 0xf360168d,
        0x742235d0, 0xbdf03125, 0x2e5438cf, 0xe7863c3a, 0xc0ce2fee, 0x091c2b1b, 0x9ab822f1, 0x536a2604
    };

    for (size_t i = 0; i < len; i++) {
        crc = table[(crc ^ data[i]) & 0xFF] ^ (crc >> 8);
    }

#else

    /**
     * CRC table generated from polynomial 0xc9d204f5 CRC-32_K/4.2 (*op) (Koopman)
     *
     * pycrc --width 32 --poly 0xc9d204f5 --reflect-in False --xor-in 0 --reflect-out False --xor-out 0 --generate table --table-idx-width 4
     */
    static uint32_t const table[16] = {
        0x00000000, 0xc9d204f5, 0x5a760d1f, 0x93a409ea, 0xb4ec1a3e, 0x7d3e1ecb, 0xee9a1721, 0x274813d4,
        0xa00a3089, 0x69d8347c, 0xfa7c3d96, 0x33ae3963, 0x14e62ab7, 0xdd342e42, 0x4e9027a8, 0x8742235d
    };

    for (size_t i = 0; i < len; i++) {
        crc = table[(crc ^ data[i]) & 0x0F] ^ (crc >> 4);
        crc = table[(crc ^ (data[i] >> 4)) & 0x0F] ^ (crc >> 4);
    }

#endif /* CONFIG_CRC32K_4_2_TABLE_256 */
    
    return crc;
}

[jukkar]

Looks pretty reasonable to me, I would suggest that you send a PR for it.

[JPHutchins]

I decided to start by adding the best HD=4 CRC32: #81558

Plan on adding 6 next - I think it covers 5.