NAND 纠错码¶

简介¶

在研究了 linux mtd/nand Hamming 软件 ECC 引擎驱动程序之后，我觉得有优化的空间。我花了几个小时修改代码，进行诸如查表之类的技巧，删除多余的代码等等。之后，速度提高了 35-40%。但我仍然不太满意，因为我觉得还有进一步改进的空间。

糟糕！我被迷住了。我决定在这个文件中注释我的步骤。也许这对某人有用，或者某人可以从中学习到一些东西。

问题¶

NAND 闪存（至少 SLC）通常具有 256 字节的扇区。然而，NAND 闪存并非极其可靠，因此需要一些错误检测（有时是纠正）。

这是通过 Hamming 码完成的。我将尝试用通俗易懂的术语来解释它（如果我没有使用正确的术语，请向该领域的所有专业人士道歉，我的编码理论课几乎是 30 年前的事情了，而且我必须承认它不是我最喜欢的课）。

正如我之前所说，ecc 计算是在 256 字节的扇区上执行的。这是通过计算行和列上的几个奇偶校验位来完成的。使用的奇偶校验是偶校验，这意味着如果计算奇偶校验的数据为 1，则奇偶校验位 = 1，如果计算奇偶校验的数据为 0，则奇偶校验位 = 0。因此，计算奇偶校验的数据上的总位数 + 奇偶校验位是偶数。（如果您无法理解，请参阅维基百科）。奇偶校验通常通过异或运算来计算，有时也称为 xor。在 C 语言中，xor 的运算符是 ^

回到 ecc。让我们给出一个小图

字节 0

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp0

rp2

rp4

...

rp14

字节 1

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp1

rp2

rp4

...

rp14

字节 2

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp0

rp3

rp4

...

rp14

字节 3

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp1

rp3

rp4

...

rp14

字节 4

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp0

rp2

rp5

...

rp14

...

字节 254

位 7

位 6

位 5

位 4

位 3

位 2

位 1

位 0

rp0

rp3

rp5

...

rp15

字节 255

位 7 cp1 cp3 cp5

位 6 cp0 cp3 cp5

位 5 cp1 cp2 cp5

位 4 cp0 cp2 cp5

位 3 cp1 cp3 cp4

位 2 cp0 cp3 cp4

位 1 cp1 cp2 cp4

位 0 cp0 cp2 cp4

rp1

rp3

rp5

...

rp15

该图表示 256 字节的扇区。 cp 是列奇偶校验的缩写，rp 是行奇偶校验的缩写。

让我们开始解释列奇偶校验。

cp0 是属于所有位 0、位 2、位 4、位 6 的奇偶校验。

因此，所有位 0、位 2、位 4 和位 6 值的总和 + cp0 本身是偶数。

类似地，cp1 是所有位 1、位 3、位 5 和位 7 的总和。

cp2 是位 0、位 1、位 4 和位 5 上的奇偶校验
cp3 是位 2、位 3、位 6 和位 7 上的奇偶校验。
cp4 是位 0、位 1、位 2 和位 3 上的奇偶校验。
cp5 是位 4、位 5、位 6 和位 7 上的奇偶校验。

请注意，cp0 .. cp5 中的每一个都恰好是一位。

行奇偶校验实际上工作方式几乎相同。

rp0 是所有偶数字节（0、2、4、6、... 252、254）的奇偶校验
rp1 是所有奇数字节（1、3、5、7、...、253、255）的奇偶校验
rp2 是所有字节 0、1、4、5、8、9、... 的奇偶校验（因此处理两个字节，然后跳过 2 个字节）。
rp3 覆盖 rp2 未覆盖的一半（字节 2、3、6、7、10、11、...）
对于 rp4，规则是覆盖 4 个字节，跳过 4 个字节，覆盖 4 个字节，跳过 4 个字节等等。

因此 rp4 计算字节 0、1、2、3、8、9、10、11、16、... 上的奇偶校验）
rp5 覆盖另一半，因此字节 4、5、6、7、12、13、14、15、20、..

故事现在变得很无聊。我猜你明白了。

rp6 覆盖 8 个字节，然后跳过 8 个字节，等等
rp7 跳过 8 个字节，然后覆盖 8 个字节，等等
rp8 覆盖 16 个字节，然后跳过 16 个字节，等等
rp9 跳过 16 个字节，然后覆盖 16 个字节，等等
rp10 覆盖 32 个字节，然后跳过 32 个字节，等等
rp11 跳过 32 个字节，然后覆盖 32 个字节，等等
rp12 覆盖 64 个字节，然后跳过 64 个字节，等等
rp13 跳过 64 个字节，然后覆盖 64 个字节，等等
rp14 覆盖 128 个字节，然后跳过 128 个字节
rp15 跳过 128 个字节，然后覆盖 128 个字节

最后，奇偶校验位按以下方式分组到三个字节中

ECC	位 7	位 6	位 5	位 4	位 3	位 2	位 1	位 0
ECC 0	rp07	rp06	rp05	rp04	rp03	rp02	rp01	rp00
ECC 1	rp15	rp14	rp13	rp12	rp11	rp10	rp09	rp08
ECC 2	cp5	cp4	cp3	cp2	cp1	cp0	1	1

在写完这个之后，我发现 ST 应用笔记 AN1823 (http://www.st.com/stonline/) 给出了一个更好的图片。（但是他们使用线路奇偶校验作为术语，而我使用行奇偶校验）嗯，我在图形方面有困难，所以请暂时忍受我 :-)

无论如何，由于版权原因，我无法重复使用 ST 图片。

尝试 0¶

实现奇偶校验计算非常简单。在 C 伪代码中

for (i = 0; i < 256; i++)
{
  if (i & 0x01)
     rp1 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp1;
  else
     rp0 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp0;
  if (i & 0x02)
     rp3 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp3;
  else
     rp2 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp2;
  if (i & 0x04)
    rp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp5;
  else
    rp4 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp4;
  if (i & 0x08)
    rp7 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp7;
  else
    rp6 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp6;
  if (i & 0x10)
    rp9 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp9;
  else
    rp8 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp8;
  if (i & 0x20)
    rp11 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp11;
  else
    rp10 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp10;
  if (i & 0x40)
    rp13 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp13;
  else
    rp12 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp12;
  if (i & 0x80)
    rp15 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp15;
  else
    rp14 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp14;
  cp0 = bit6 ^ bit4 ^ bit2 ^ bit0 ^ cp0;
  cp1 = bit7 ^ bit5 ^ bit3 ^ bit1 ^ cp1;
  cp2 = bit5 ^ bit4 ^ bit1 ^ bit0 ^ cp2;
  cp3 = bit7 ^ bit6 ^ bit3 ^ bit2 ^ cp3
  cp4 = bit3 ^ bit2 ^ bit1 ^ bit0 ^ cp4
  cp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ cp5
}

分析 0¶

C 确实有按位运算符，但没有真正能有效执行上述操作的运算符（而且大多数硬件也没有这样的指令）。因此，在没有实现它的情况下，很明显上面的代码不会给我带来诺贝尔奖 :-)

幸运的是，异或运算是可交换的，因此我们可以按任何顺序组合这些值。因此，与其单独计算所有位，不如尝试重新排列事物。对于列奇偶校验，这很容易。我们可以只异或字节，最后过滤掉相关的位。这非常好，因为它会将所有 cp 计算从 for 循环中移出。

类似地，我们可以首先异或各个行的字节。这导致

尝试 1¶

const char parity[256] = {
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1,
    0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0
};

void ecc1(const unsigned char *buf, unsigned char *code)
{
    int i;
    const unsigned char *bp = buf;
    unsigned char cur;
    unsigned char rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7;
    unsigned char rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15;
    unsigned char par;

    par = 0;
    rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0;
    rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0;
    rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0;
    rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0;

    for (i = 0; i < 256; i++)
    {
        cur = *bp++;
        par ^= cur;
        if (i & 0x01) rp1 ^= cur; else rp0 ^= cur;
        if (i & 0x02) rp3 ^= cur; else rp2 ^= cur;
        if (i & 0x04) rp5 ^= cur; else rp4 ^= cur;
        if (i & 0x08) rp7 ^= cur; else rp6 ^= cur;
        if (i & 0x10) rp9 ^= cur; else rp8 ^= cur;
        if (i & 0x20) rp11 ^= cur; else rp10 ^= cur;
        if (i & 0x40) rp13 ^= cur; else rp12 ^= cur;
        if (i & 0x80) rp15 ^= cur; else rp14 ^= cur;
    }
    code[0] =
        (parity[rp7] << 7) |
        (parity[rp6] << 6) |
        (parity[rp5] << 5) |
        (parity[rp4] << 4) |
        (parity[rp3] << 3) |
        (parity[rp2] << 2) |
        (parity[rp1] << 1) |
        (parity[rp0]);
    code[1] =
        (parity[rp15] << 7) |
        (parity[rp14] << 6) |
        (parity[rp13] << 5) |
        (parity[rp12] << 4) |
        (parity[rp11] << 3) |
        (parity[rp10] << 2) |
        (parity[rp9]  << 1) |
        (parity[rp8]);
    code[2] =
        (parity[par & 0xf0] << 7) |
        (parity[par & 0x0f] << 6) |
        (parity[par & 0xcc] << 5) |
        (parity[par & 0x33] << 4) |
        (parity[par & 0xaa] << 3) |
        (parity[par & 0x55] << 2);
    code[0] = ~code[0];
    code[1] = ~code[1];
    code[2] = ~code[2];
}

仍然很简单。最后三个反转语句用于为空闪存提供 0xff 0xff 0xff 的校验和。在空闪存中，所有数据都是 0xff，因此校验和匹配。

我还介绍了奇偶校验查找。我希望这是计算奇偶校验的最快方法，但我稍后将调查替代方法。

分析 1¶

代码有效，但效率不高。在我的系统上，它花费的时间几乎是 linux 驱动程序代码的 4 倍。但是，嘿，如果 *那么* 容易，早就完成了。没有付出，就没有收获。

幸运的是，还有很大的改进空间。

在步骤 1 中，我们从按位计算转移到按字节计算。然而，在 C 语言中，我们也可以使用 unsigned long 数据类型，并且几乎每个现代微处理器都支持 32 位操作，因此为什么不尝试以处理 32 位块的方式编写我们的代码呢？

当然，这意味着一些修改，因为行奇偶校验是逐字节进行的。快速分析：对于列奇偶校验，我们使用 par 变量。当扩展到 32 位时，我们最终可以很容易地从中计算出 rp0 和 rp1。（因为 par 现在由 4 个字节组成，分别从 MSB 到 LSB 贡献给 rp1、rp0、rp1、rp0）也可以很容易地从 par 中检索到 rp2 和 rp3，因为 rp3 覆盖前两个 MSB，而 rp2 覆盖最后两个 LSB。

请注意，当然现在循环只执行 64 次 (256/4)。还要注意，必须注意字节顺序。字节在 long 中排序的方式与机器相关，并且可能会影响我们。无论如何，如果存在问题：此代码是在 x86 上开发的（准确地说是：具有 D920 Intel CPU 的 DELL PC）

当然，性能可能取决于对齐方式，但我希望 nand 驱动程序中的 I/O 缓冲区已正确对齐（否则应该修复它以获得最大性能）。

让我们试一试...

尝试 2¶

extern const char parity[256];

void ecc2(const unsigned char *buf, unsigned char *code)
{
    int i;
    const unsigned long *bp = (unsigned long *)buf;
    unsigned long cur;
    unsigned long rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7;
    unsigned long rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15;
    unsigned long par;

    par = 0;
    rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0;
    rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0;
    rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0;
    rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0;

    for (i = 0; i < 64; i++)
    {
        cur = *bp++;
        par ^= cur;
        if (i & 0x01) rp5 ^= cur; else rp4 ^= cur;
        if (i & 0x02) rp7 ^= cur; else rp6 ^= cur;
        if (i & 0x04) rp9 ^= cur; else rp8 ^= cur;
        if (i & 0x08) rp11 ^= cur; else rp10 ^= cur;
        if (i & 0x10) rp13 ^= cur; else rp12 ^= cur;
        if (i & 0x20) rp15 ^= cur; else rp14 ^= cur;
    }
    /*
       we need to adapt the code generation for the fact that rp vars are now
       long; also the column parity calculation needs to be changed.
       we'll bring rp4 to 15 back to single byte entities by shifting and
       xoring
    */
    rp4 ^= (rp4 >> 16); rp4 ^= (rp4 >> 8); rp4 &= 0xff;
    rp5 ^= (rp5 >> 16); rp5 ^= (rp5 >> 8); rp5 &= 0xff;
    rp6 ^= (rp6 >> 16); rp6 ^= (rp6 >> 8); rp6 &= 0xff;
    rp7 ^= (rp7 >> 16); rp7 ^= (rp7 >> 8); rp7 &= 0xff;
    rp8 ^= (rp8 >> 16); rp8 ^= (rp8 >> 8); rp8 &= 0xff;
    rp9 ^= (rp9 >> 16); rp9 ^= (rp9 >> 8); rp9 &= 0xff;
    rp10 ^= (rp10 >> 16); rp10 ^= (rp10 >> 8); rp10 &= 0xff;
    rp11 ^= (rp11 >> 16); rp11 ^= (rp11 >> 8); rp11 &= 0xff;
    rp12 ^= (rp12 >> 16); rp12 ^= (rp12 >> 8); rp12 &= 0xff;
    rp13 ^= (rp13 >> 16); rp13 ^= (rp13 >> 8); rp13 &= 0xff;
    rp14 ^= (rp14 >> 16); rp14 ^= (rp14 >> 8); rp14 &= 0xff;
    rp15 ^= (rp15 >> 16); rp15 ^= (rp15 >> 8); rp15 &= 0xff;
    rp3 = (par >> 16); rp3 ^= (rp3 >> 8); rp3 &= 0xff;
    rp2 = par & 0xffff; rp2 ^= (rp2 >> 8); rp2 &= 0xff;
    par ^= (par >> 16);
    rp1 = (par >> 8); rp1 &= 0xff;
    rp0 = (par & 0xff);
    par ^= (par >> 8); par &= 0xff;

    code[0] =
        (parity[rp7] << 7) |
        (parity[rp6] << 6) |
        (parity[rp5] << 5) |
        (parity[rp4] << 4) |
        (parity[rp3] << 3) |
        (parity[rp2] << 2) |
        (parity[rp1] << 1) |
        (parity[rp0]);
    code[1] =
        (parity[rp15] << 7) |
        (parity[rp14] << 6) |
        (parity[rp13] << 5) |
        (parity[rp12] << 4) |
        (parity[rp11] << 3) |
        (parity[rp10] << 2) |
        (parity[rp9]  << 1) |
        (parity[rp8]);
    code[2] =
        (parity[par & 0xf0] << 7) |
        (parity[par & 0x0f] << 6) |
        (parity[par & 0xcc] << 5) |
        (parity[par & 0x33] << 4) |
        (parity[par & 0xaa] << 3) |
        (parity[par & 0x55] << 2);
    code[0] = ~code[0];
    code[1] = ~code[1];
    code[2] = ~code[2];
}

不再显示奇偶校验数组。另请注意，对于这些示例，我通过允许一行上有多个语句、在只有单个语句的 then 和 else 块中不使用 { } 以及使用诸如 ^= 之类的运算符，在某种程度上偏离了我的常规编程风格。

分析 2¶

代码（当然）有效，并且万岁：我们比 linux 驱动程序代码快一点（大约 15%）。但是等等，不要太快欢呼。还有更多的收获。如果我们看例如 rp14 和 rp15，我们会看到我们要么用 rp14 异或我们的数据，要么用 rp15 异或我们的数据。然而，我们也有遍历所有数据的 par。这意味着不需要计算 rp14，因为它可以从 rp15 通过 rp14 = par ^ rp15 计算，因为 par = rp14 ^ rp15; （或者如果需要，我们可以避免计算 rp15 并从 rp14 计算它）。这就是为什么有些地方提到反向奇偶校验。当然，对于 rp4/5、rp6/7、rp8/9、rp10/11 和 rp12/13 也是如此。实际上，这意味着我们可以从 if 语句中消除 else 子句。此外，我们可以通过首先从 long 变为 byte 来稍微优化最终的计算。实际上，我们甚至可以避免查表

尝试 3¶

奇数已替换

if (i & 0x01) rp5 ^= cur; else rp4 ^= cur;
if (i & 0x02) rp7 ^= cur; else rp6 ^= cur;
if (i & 0x04) rp9 ^= cur; else rp8 ^= cur;
if (i & 0x08) rp11 ^= cur; else rp10 ^= cur;
if (i & 0x10) rp13 ^= cur; else rp12 ^= cur;
if (i & 0x20) rp15 ^= cur; else rp14 ^= cur;

为

if (i & 0x01) rp5 ^= cur;
if (i & 0x02) rp7 ^= cur;
if (i & 0x04) rp9 ^= cur;
if (i & 0x08) rp11 ^= cur;
if (i & 0x10) rp13 ^= cur;
if (i & 0x20) rp15 ^= cur;

并在循环外添加了

rp4  = par ^ rp5;
rp6  = par ^ rp7;
rp8  = par ^ rp9;
rp10  = par ^ rp11;
rp12  = par ^ rp13;
rp14  = par ^ rp15;

之后，代码花费的时间增加了大约 30%，尽管语句的数量减少了。这也反映在汇编代码中。

分析 3¶

非常奇怪。猜测这与缓存或指令并行性有关。我还在 eeePC（赛扬，主频为 900 Mhz）上进行了尝试。一个有趣的观察结果是，这段代码的执行速度（根据时间）仅比我的 3Ghz D920 处理器慢 30%。

嗯，预计这不会容易，所以也许转向不同的方向：让我们回到尝试 2 中的代码并进行一些循环展开。这将消除一些 if 语句。我将尝试不同数量的展开，看看哪个效果最好。

尝试 4¶

将循环展开了 1、2、3 和 4 次。对于 4，代码以

for (i = 0; i < 4; i++)
{
    cur = *bp++;
    par ^= cur;
    rp4 ^= cur;
    rp6 ^= cur;
    rp8 ^= cur;
    rp10 ^= cur;
    if (i & 0x1) rp13 ^= cur; else rp12 ^= cur;
    if (i & 0x2) rp15 ^= cur; else rp14 ^= cur;
    cur = *bp++;
    par ^= cur;
    rp5 ^= cur;
    rp6 ^= cur;
    ...

分析 4¶

展开一次可获得大约 15% 的收益

展开两次可将收益保持在大约 15%

与尝试 2 相比，展开三次可获得 30% 的收益。

与展开三次相比，展开四次仅能获得微小的改进。

我决定无论如何都要继续使用四次展开循环。我的直觉是在接下来的步骤中，我将从中获得额外的收益。

下一步是由这样一个事实触发的：par 包含所有字节的异或，而 rp4 和 rp5 各自包含一半字节的异或。因此，实际上 par = rp4 ^ rp5。但是由于异或是可交换的，我们也可以说 rp5 = par ^ rp4。因此无需保留 rp4 和 rp5。我们可以消除 rp5（或 rp4，但我已经预见到了另一个优化）。对于 rp6/7、rp8/9、rp10/11 rp12/13 和 rp14/15 也是如此。

尝试 5¶

实际上，循环中所有奇数位 rp 的赋值都被删除了。这包括 if 语句的 else 子句。当然，在循环之后，我们需要通过添加类似的代码来纠正事情

rp5 = par ^ rp4;

还可以删除初始赋值（rp5 = 0; 等）。沿着这条线，我还删除了 rp0/1/2/3 的初始化。

分析 5¶

测量表明这是一个好举动。与 4 次展开的尝试 4 相比，运行时间大约减半，并且我们只需要 linux 内核中当前代码 1/3 的处理器时间。

但是，我仍然认为还有更多。我不喜欢所有的 if 语句。为什么不保持运行奇偶校验并只保留最后一个 if 语句。是时候推出另一个版本了！

尝试 6¶

for 循环内的代码已更改为

for (i = 0; i < 4; i++)
{
    cur = *bp++; tmppar  = cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= tmppar;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp8 ^= tmppar;

    cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp10 ^= tmppar;

    cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur; rp8 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp8 ^= cur;
    cur = *bp++; tmppar ^= cur; rp8 ^= cur;

    cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur;

    par ^= tmppar;
    if ((i & 0x1) == 0) rp12 ^= tmppar;
    if ((i & 0x2) == 0) rp14 ^= tmppar;
}

如你所见，tmppar 用于累积 for 迭代中的奇偶校验。在最后 3 个语句中，它被添加到 par，如果需要，添加到 rp12 和 rp14。

在进行更改时，我还发现我可以利用 tmppar 包含此迭代的运行奇偶校验。因此，与其有：rp4 ^= cur; rp6 ^= cur; 我删除了 rp6 ^= cur; 语句并在下一个语句上做了 rp6 ^= tmppar; 对 rp8 和 rp10 做了类似的更改

分析 6¶

再次测量这段代码显示出很大的收益。当执行原始 linux 代码 100 万次时，在我的系统上花费了大约 1 秒。（使用 time 来测量性能）。在此迭代之后，我回到了 0.075 秒。实际上，我不得不决定开始测量超过 1000 万次迭代，以免损失太多精度。这一个绝对似乎是头奖！

不过，还有一些改进的空间。有三个地方有声明

rp4 ^= cur; rp6 ^= cur;

似乎更有效的方法是在 while 循环中也维护变量 rp4_6；这消除了每个循环的 3 个语句。当然，在循环之后，我们需要通过添加以下内容来纠正

rp4 ^= rp4_6;
rp6 ^= rp4_6

此外，对 rp8 有 4 个顺序赋值。通过在 4 行之前保存 tmppar 并在之后执行 rp8 = rp8 ^ tmppar ^ notrp8;（其中 notrp8 是 4 行之前 rp8 的值）可以更有效地编码它。再次使用异或的交换律。是时候进行新的测试了！

尝试 7¶

新代码现在看起来像

for (i = 0; i < 4; i++)
{
    cur = *bp++; tmppar  = cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= tmppar;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp8 ^= tmppar;

    cur = *bp++; tmppar ^= cur; rp4_6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur; rp10 ^= tmppar;

    notrp8 = tmppar;
    cur = *bp++; tmppar ^= cur; rp4_6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur;
    rp8 = rp8 ^ tmppar ^ notrp8;

    cur = *bp++; tmppar ^= cur; rp4_6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp6 ^= cur;
    cur = *bp++; tmppar ^= cur; rp4 ^= cur;
    cur = *bp++; tmppar ^= cur;

    par ^= tmppar;
    if ((i & 0x1) == 0) rp12 ^= tmppar;
    if ((i & 0x2) == 0) rp14 ^= tmppar;
}
rp4 ^= rp4_6;
rp6 ^= rp4_6;

这不是一个很大的变化，但每一分钱都很重要 :-)

分析 7¶

实际上，这使情况变得更糟。不是很多，但我不想朝着错误的方向前进。也许稍后需要调查一下。可能与缓存有关。

猜测这就是循环中要赢得的东西。也许再展开一次会有所帮助。我现在将保留 7 中的优化。

尝试 8¶

再次展开循环。

分析 8¶

这使情况变得更糟。让我们坚持尝试 6 并从那里继续。尽管循环内的代码似乎无法进一步优化，但仍然有优化 ecc 代码生成空间的余地。我们可以简单地计算总奇偶校验。如果这是 0，那么 rp4 = rp5 等。如果奇偶校验是 1，那么 rp4 = !rp5;

但是如果 rp4 = rp5，我们不需要 rp5 等。我们可以只将偶数位写入结果字节，然后执行类似的操作

code[0] |= (code[0] << 1);

让我们测试一下。

尝试 9¶

更改了代码，但这再次略微降低了性能。尝试了各种其他方法，例如使用专用奇偶校验数组来避免 parity[rp7] << 7 之后进行移位；没有增益。通过使用移位运算符来更改使用奇偶校验数组的查找（例如，将 parity[rp7] << 7 替换为

rp7 ^= (rp7 << 4);
rp7 ^= (rp7 << 2);
rp7 ^= (rp7 << 1);
rp7 &= 0x80;

没有增益。

唯一微小的变化是反转奇偶校验位，因此我们可以删除最后三个反转语句。

嗯，很遗憾这没有带来更多。再说一遍，使用 linux 驱动程序代码进行 1000 万次迭代需要 13 到 13.5 秒，而我的代码现在对于这 1000 万次迭代大约需要 0.73 秒。因此，基本上我将系统上的性能提高了 18 倍。还不错。当然，在不同的硬件上，您会得到不同的结果。不保证！

但是当然没有免费的午餐。代码大小几乎增加了两倍（从 562 字节到 1434 字节）。再说一遍，这并不是很多。

纠正错误¶

对于纠正错误，我再次使用 ST 应用笔记作为入门，但我也偷看了现有代码。

该算法本身非常简单。只需异或给定的和计算的 ecc。如果所有字节都是 0，则没有问题。如果 11 位是 1，那么我们有一个可纠正的位错误。如果有 1 位是 1，那么我们给定的 ecc 代码中有一个错误。

事实证明，使用查表法速度最快。在我的系统上，当需要修复时，这种方法带来的性能提升大约是 2 倍，如果不需要修复，则性能提升约为 1%。

此函数的代码大小从 330 字节增加到 686 字节。（gcc 4.2, -O3）

结论¶

计算 ECC 时的增益非常显著。在我的开发硬件上，ECC 计算的速度提高了 18 倍。在具有 MIPS 内核的嵌入式系统上进行的测试获得了 7 倍的提升。

在使用 Linksys NSLU2 (ARMv5TE 处理器) 的测试中，速度提高了 5 倍（大端模式，gcc 4.1.2, -O3）。

对于纠错，没有获得太多增益（因为位翻转很少发生）。但另一方面，花费在那里的周期也少得多。

似乎在这个方面没有太多提升的空间了，至少在使用 C 编程时是这样。当然，使用汇编程序可能会挤出更多的性能，但由于流水线行为等原因，这非常棘手（至少对于 Intel 硬件来说）。

作者: Frans Meulenbroeks

Linux 内核

目录

本页

NAND 纠错码¶

简介¶

问题¶

尝试 0¶

分析 0¶

尝试 1¶

分析 1¶

尝试 2¶

分析 2¶

尝试 3¶

分析 3¶

尝试 4¶

分析 4¶

尝试 5¶

分析 5¶

尝试 6¶

分析 6¶

尝试 7¶

分析 7¶

尝试 8¶

分析 8¶

尝试 9¶

纠正错误¶

结论¶