NAND 纠错码¶

简介¶

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

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

问题¶

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

这是通过汉明码实现的。我将尝试用通俗易懂的语言来解释它（如果我没有使用正确的术语，请向该领域的所有专业人士道歉，我的编码理论课几乎是 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 中，我们也可以使用无符号 long 数据类型，而且几乎每个现代微处理器都支持 32 位操作，所以为什么不尝试以这种方式编写我们的代码，以便我们以 32 位块处理数据。

当然，这意味着需要进行一些修改，因为行奇偶校验是逐字节进行的。快速分析：对于列奇偶校验，我们使用 par 变量。当扩展到 32 位时，我们可以很容易地从中计算出 rp0 和 rp1。（因为 par 现在由 4 个字节组成，分别从 MSB 到 LSB 贡献给 rp1、rp0、rp1、rp0）此外，rp2 和 rp3 也可以很容易地从 par 中检索，因为 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%（根据时间）。

嗯，预计这不容易，所以也许可以转移到不同的轨道：让我们回到 attempt2 中的代码并进行一些循环展开。这将消除一些 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 秒，而我的代码现在需要大约 0.73 秒进行这 1000 万次迭代。因此，基本上，我在我的系统上的性能提高了 18 倍。还不错。当然，在不同的硬件上，您会得到不同的结果。不作任何保证！

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

纠正错误¶

为了纠正错误，我再次使用了 ST 应用说明作为入门，但也查看了现有代码。

该算法本身非常简单。只需异或给定的 ecc 和计算出的 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 hw）。

作者：Frans Meulenbroeks

Linux 内核

目录

本页

NAND 纠错码¶

简介¶

问题¶

尝试 0¶

分析 0¶

尝试 1¶

分析 1¶

尝试 2¶

分析 2¶

尝试 3¶

分析 3¶

尝试 4¶

分析 4¶

尝试 5¶

分析 5¶

尝试 6¶

分析 6¶

尝试 7¶

分析 7¶

尝试 8¶

分析 8¶

尝试 9¶

纠正错误¶

结论¶