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?