Software ECC embedded with a parallel NAND Flash interface

Question

I'm developing an embedded solution (STM32L4R5 MCU - Cortex-M4F: 120 Mhz / 640 kb of ram) featuring a parallel NAND Flash (MICRON) interface and my platform lacks hardware ECC computation powerful enough to handle page sizes of 8KB so I elected to use software ECC. This one, to be precise. I refactored it as much as I could, unrolling some loops and replacing the count_bits_in_byte with a lookup table. The result is 5-10 2 times faster code (depending on the input). Measured with an oscilloscope.

This piece of code takes a 256 byte input and outputs 3 bytes of error correction code.

static void compute256(const uint8_t *data, uint8_t *code)
{
    uint32_t i;
    uint8_t column_sum = 0;
    uint8_t even_line_code = 0;
    uint8_t odd_line_code = 0;
    uint8_t even_column_code = 0;
    uint8_t odd_column_code = 0;

    for (i = 0; i < 256; ++i)
    {
        column_sum ^= data[i];

        // lookup table containing number of set bits in any given byte
        if ((setBitsInByteLookupTable[data[i]] & 1) != 0)
        {
            even_line_code ^= (255 - i);
            odd_line_code ^= i;
        }
    }
    // unrolled this loop
    if (column_sum & 1) {  even_column_code ^= 7;  odd_column_code ^= 0;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 6;  odd_column_code ^= 1;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 5;  odd_column_code ^= 2;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 4;  odd_column_code ^= 3;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 3;  odd_column_code ^= 4;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 2;  odd_column_code ^= 5;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 1;  odd_column_code ^= 6;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 0;  odd_column_code ^= 7;} column_sum >>= 1;
    // unrolled this loop
    code[0] = 0;
    code[1] = 0;
    code[2] = 0;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }
}

Probably using assembly would be a solution, sadly I'm a little less proficient with assembly than a lobotomized duck.

Any pointer would be greatly appreciated. How can I further optimize an ECC code computation?

Answer 1

Shift the constants not the variable

    if (column_sum & 1) {  even_column_code ^= 7;  odd_column_code ^= 0;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 6;  odd_column_code ^= 1;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 5;  odd_column_code ^= 2;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 4;  odd_column_code ^= 3;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 3;  odd_column_code ^= 4;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 2;  odd_column_code ^= 5;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 1;  odd_column_code ^= 6;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 0;  odd_column_code ^= 7;} column_sum >>= 1;

As I hinted in a comment, I'm not sure how much unrolling this loop gained you. When doing this kind of optimization, you need to measure each step separately (at least, independently is even better). But starting from this code, you could simplify it with

    if (column_sum &   1) { even_column_code ^= 7;  odd_column_code ^= 0;} 
    if (column_sum &   2) { even_column_code ^= 6;  odd_column_code ^= 1;} 
    if (column_sum &   4) { even_column_code ^= 5;  odd_column_code ^= 2;} 
    if (column_sum &   8) { even_column_code ^= 4;  odd_column_code ^= 3;} 
    if (column_sum &  16) { even_column_code ^= 3;  odd_column_code ^= 4;} 
    if (column_sum &  32) { even_column_code ^= 2;  odd_column_code ^= 5;} 
    if (column_sum &  64) { even_column_code ^= 1;  odd_column_code ^= 6;} 
    if (column_sum & 128) { even_column_code ^= 0;  odd_column_code ^= 7;} 

You already know what your shift is supposed to achieve. So if unrolled, you don't need to do it as a shift. You can shift the 1 manually instead.

Skip no-ops

    code[0] = 0;
    code[1] = 0;
    code[2] = 0;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

I believe that you could simply leave off the last three lines. Because left shifting 0 will end up with 0. This was required in the loop for consistency. It's effectively a no-op. But unrolled you can skip this. That might pick up three instructions (if the compiler didn't already optimize it out).

More constant shifting

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

This is the second "iteration" of your unrolled loop. It could be

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x40) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x40) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x04) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x04) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x02) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x02) != 0)
    {
        code[2] |= 1;
    }

For the third iteration, the constants to & would be 0x20, 0x02, and 0x01.

More advanced

The next step would be

    /* Line 1 */
    if ((odd_line_code & 0x40) != 0)
    {
        code[0] |= 8;
    }

    if ((even_line_code & 0x40) != 0)
    {
        code[0] |= 4;
    }
    /* Line 2 */
    if ((odd_line_code & 0x04) != 0)
    {
        code[1] |= 8;
    }

    if ((even_line_code & 0x04) != 0)
    {
        code[1] |= 4;
    }
    /* Column */
    if ((odd_column_code & 0x02) != 0)
    {
        code[2] |= 8;
    }
    if ((even_column_code & 0x02) != 0)
    {
        code[2] |= 4;
    }

But that would require changes to the first and third iterations to match. Get rid of all the <<= in that section of code and change the |= constants in the first iteration with 32 and 16 (for 2 and 1 respectively).

Timing

When testing these, you really should be testing each change separately and if possible, independently. Separately means that you should change one thing and then time that one thing. So each of

1. Convert function call to lookup table.
2. Unroll loop.
3. Unroll the other loop.

should be timed separately.

What you may find is that unrolling the loops doesn't help you, or even makes it worse (unrolling loops can bypass optimizations that the compiler would otherwise make).

Independently means that you should try testing them with and without the others. So compile with the function call converted. Time. Then undo that and try with an unrolled loop. Then undo that and try with the other loop unrolled.

Once you've tested them independently of each other, then you can time with them in various combinations. Sometimes you'll find that two optimizations that work separately don't work well together. Timing this way will allow you to pick the better one.

Note that I have suggested additional optimizations in this post. They only make sense with the unrolled loops. So that increases the number of possibilities.

1. With loop.
2. Unrolled.
3. With the constants shifted.
4. With the no-op instructions removed.
5. With the no-op instructions removed and the constants shifted.
6. With the other constants shifted (implicitly removes the no-op instructions).
7. With the both sets of constants shifted.

Only the second unrolled loop has no-op instructions and two sets of constants to shift. The first unrolled loop only has three possibilities. That's forty-two combinations to check (perhaps we've stumbled onto the Ultimate Question). Note that if something doesn't work independently, you might drop it from potential combination checking. While not impossible, it is less likely that an optimization that didn't work independently would start working in combination.

Caveat

I'm not an embedded guy. To me, an oscilloscope is something that makes pretty but abstract art, like a screen saver, not something that I would use to test how fast code is. I have tried to express general principles. These may or may not be practical in your situation.

Answer 2

mdfst13 already gave a great review of the code itself. I'll just add this:

Consider changing the ECC algorithm

Since you are implementing ECC in software, you are free to choose whatever algorithm you want. You could change it to something more friendly for the Cortex-M4 CPU to calculate. In particular, if you don't use the ECC code to correct for single-bit errors, but only to detect errors, then you can choose an arbitrary checksum or hash function.

Answer 3

From what I remember ST Cortex M4 has some "wannabe cache"-like feature, "ART accelerator", something like that. This is supposedly mainly there to reduce wait states. But if it works like normal data/instruction cache (I don't know any details here, I'd have to check the friendly manual), then regular for loops is probably as good as it gets when accessing adjacent flash memory. That could mean that manual loop unrolling is actually harmful for optimization.

At any rate, it's fairly safe to assume that flash wait states is a bottleneck. So you should focus on minimizing branches.

For example, something like column_sum & 1 is 0 or 1, so there shouldn't need to be a branch there. You have to disassemble to tell if it makes any difference, but maybe code like this will eliminate the branch:

uint32_t bit = column_sum & 1;
even_column_code ^= mask*bit;
odd_column_code ^= (7-mask)*bit;

Come up with similar tricks to get rid of as many of those slow if statements as possible!

---

In general, you should never do bitwise arithmetic on small integer types or signed integer types - the former get implicitly promoted to the latter. See Implicit type promotion rules. What you are risking is that upon setting MSB at any point, you could end up with shifting a negative number, which is poorly-defined behavior and almost always a bug.

This means that all your uint8_t should be swapped for uint32_t - which is unlikely to affect performance on a Cortex M.

---

The usual mini-optimization of no pointer aliasing between parameters is possible:

static void compute256 (const uint8_t* restrict data, uint8_t* restrict code)

It may or may not have an effect. Seems more likely to get optimized on gcc than other compilers.

---

However, I can't really use optimizations, as it tends to break some of STM's HAL

Well, you are done for then. When something like that happens, everyone needs to raise a support ticket with ST asking why their code sucks. If enough people do it, they will eventually have to hire professional programmers to fix the so-called "HAL".

Now if you are already stuck with their bloatware, what you can perhaps do is to play around with local optimization per translation unit: #pragma GCC optimize ("O3") and #pragma GCC optimize ("O0"). Brittle bloatware code gets the -O0, properly written C code gets optimized.

For what it's worth, one of the most likely reasons for hardware drivers breaking upon optimization is missing volatile qualifiers for register access or variables shared with ISRs or DMA etc. So if you are lucky, the problem is just something trivial like that, not the hardest bugs to track down.