Code generation use different algorithm for reflected

[cmcqueen]

When generating code for a "reflected" CRC, a function is used to reflect each input byte. This is inefficient—it would be preferable to use an alternative core CRC algorithm that is a "reflected" algorithm. See Chapter 11 "Reflected" Table-Driven Implementations of A Painless Guide to CRC Error Detection Algorithms by Ross Williams. That describes a reflected table-driven algorithm; there would similarly be a reflected bit-by-bit algorithm.

[tpircher-zz]

Hi Craig,

thanks for the feed-back! The bit-by-bit implementation is certainly not optimal and should be improved in future. But I'm not sure the table-driven algorithm ever reflects the input bytes. (The finalize function does, but that happens once). Can you give me an example set of parameters where the implementation can be improved?

[cmcqueen]

Sorry, I think my comments about the table-driven algorithm are wrong. I was getting a few things confused:

• I didn't see there's a different bit-by-bit-fast algorithm that generates different code.
• I saw that the table-driven algorithm generates a crc_reflect() function, but it doesn't use it or need it.

Now I see the table-driven algorithm is already using a "reflected" version of the algorithm as needed. So that's fine.

Still, a few observations...

I'm testing generation of the CRC-8/ROHC algorithm, with parameters as follows:

./pycrc.py --width 8 --poly 0x107 --xor-in 0xFF --reflect-in=true --reflect-out=true --xor-out 0 -o test.c --generate=c --algorithm=bbb

I now realised I should also be looking at the generated header file:

./pycrc.py --width 8 --poly 0x107 --xor-in 0xFF --reflect-in=true --reflect-out=true --xor-out 0 -o test.h --generate=h --algorithm=bbb

• The bit-by-bit algorithm generated code does reflect each input byte, and the final output byte, using a crc_reflect() function.
• The bit-by-bit-fast algorithm generated code doesn't need to reflect each input byte, however it does need to call crc_reflect() function from the crc_finalize() function.
• The table-driven algorithm generated code also doesn't need to reflect each input byte, however it also still generates a crc_reflect() function even though it doesn't use it.

There is a "reflected" version of the bit-by-bit algorithm that reflects the algorithm itself, and therefore doesn't need any final output byte reflection. Here is code for CRC-8/ROHC that I wrote by hand (just for a single data byte):

#define CRC8_107_POLY           0x07u
#define CRC8_107_POLY_REV       0xE0u   /* reverse (bit-swap) of CRC8_107_POLY */

uint8_t crc8_rohc_core(uint8_t data, uint8_t crc)
{
    uint_fast8_t    i;
    bool            overflow;

    crc ^= data;
    for (i = 0; i < 8u; i++) {
        overflow = ((crc & 1u) != 0);
        crc = (crc >> 1u);
        if (overflow)
            crc ^= CRC8_107_POLY_REV;
    }
    return crc;
}

This algorithm pattern could also be extended to 16 or 32 bits with some tweaking.

[tpircher-zz]

Craig, this is really useful, thanks! Most of your suggestions will make it into the next release 0.9. I might defer the change to the reflected bit-by-bit algorithm to v0.9.1, as I'd like to release v0.9 with the slice-by variant of the table-driven algorithm as soon as it is working reliably for some corner cases.