NAND Error-correction Code

최적화 기록의 배경

작성자는 Linux MTD/NAND Hamming software ECC engine driver를 살펴보고 최적화 여지가 있다고 판단했습니다.

Table lookup과 불필요한 코드 제거를 몇 시간 적용해 속도를 35~40% 높였지만, 추가 개선 가능성을 느껴 이후 단계를 이 문서에 기록했습니다.

이 기록은 다른 개발자가 최적화 과정을 활용하거나 그 과정에서 무언가를 배울 수 있도록 작성됐습니다.

==========================
NAND Error-correction Code
==========================

Introduction
============

Having looked at the linux mtd/nand Hamming software ECC engine driver
I felt there was room for optimisation. I bashed the code for a few hours
performing tricks like table lookup removing superfluous code etc.
After that the speed was increased by 35-40%.
Still I was not too happy as I felt there was additional room for improvement.

Bad! I was hooked.
I decided to annotate my steps in this file. Perhaps it is useful to someone
or someone learns something from it.

256-byte sector의 Hamming parity

SLC NAND flash는 일반적으로 256-byte sector를 사용하지만 완전히 신뢰할 수 없으므로 error detection과 때로는 correction이 필요합니다. 이 문서는 이를 Hamming code로 수행하는 원리를 설명합니다.

ECC는 256 byte에 대해 row와 column parity를 계산합니다. Even parity에서는 대상 data bit와 parity bit를 합친 1의 개수가 짝수가 되도록 parity bit를 정합니다. Parity는 보통 XOR, C에서는 `^` 연산으로 계산합니다.

Column parity `cp0..cp5`는 한 byte 안의 bit 위치를 서로 보완하는 절반 집합으로 나눕니다. `cp0`은 bit0·2·4·6, `cp1`은 bit1·3·5·7, `cp2`는 bit0·1·4·5, `cp3`은 bit2·3·6·7, `cp4`는 bit0~3, `cp5`는 bit4~7의 parity입니다. 각 값은 1 bit입니다.

Row parity `rp0..rp15`는 byte index를 1, 2, 4, 8, 16, 32, 64, 128 byte 단위의 보완 집합으로 나눕니다. 예를 들어 `rp0`은 짝수 byte, `rp1`은 홀수 byte, `rp2`는 두 byte를 포함하고 두 byte를 건너뛰며 `rp3`은 그 반대 절반입니다. 이후 pair도 같은 방식으로 group size를 두 배씩 늘립니다.

최종 parity는 3 byte에 배치합니다. ECC 0에는 `rp07..rp00`, ECC 1에는 `rp15..rp08`, ECC 2에는 `cp5..cp0`과 고정 bit `1,1`을 둡니다. ST AN1823에서는 row parity를 line parity라고 부릅니다.

The problem
===========

NAND flash (at least SLC one) typically has sectors of 256 bytes.
However NAND flash is not extremely reliable so some error detection
(and sometimes correction) is needed.

This is done by means of a Hamming code. I'll try to explain it in
laymans terms (and apologies to all the pro's in the field in case I do
not use the right terminology, my coding theory class was almost 30
years ago, and I must admit it was not one of my favourites).

As I said before the ecc calculation is performed on sectors of 256
bytes. This is done by calculating several parity bits over the rows and
columns. The parity used is even parity which means that the parity bit = 1
if the data over which the parity is calculated is 1 and the parity bit = 0
if the data over which the parity is calculated is 0. So the total
number of bits over the data over which the parity is calculated + the
parity bit is even. (see wikipedia if you can't follow this).
Parity is often calculated by means of an exclusive or operation,
sometimes also referred to as xor. In C the operator for xor is ^

Back to ecc.
Let's give a small figure:

=========  ==== ==== ==== ==== ==== ==== ==== ====   === === === === ====
byte   0:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp0 rp2 rp4 ... rp14
byte   1:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp1 rp2 rp4 ... rp14
byte   2:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp0 rp3 rp4 ... rp14
byte   3:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp1 rp3 rp4 ... rp14
byte   4:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp0 rp2 rp5 ... rp14
...
byte 254:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp0 rp3 rp5 ... rp15
byte 255:  bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0   rp1 rp3 rp5 ... rp15
           cp1  cp0  cp1  cp0  cp1  cp0  cp1  cp0
           cp3  cp3  cp2  cp2  cp3  cp3  cp2  cp2
           cp5  cp5  cp5  cp5  cp4  cp4  cp4  cp4
=========  ==== ==== ==== ==== ==== ==== ==== ====   === === === === ====

This figure represents a sector of 256 bytes.
cp is my abbreviation for column parity, rp for row parity.

Let's start to explain column parity.

- cp0 is the parity that belongs to all bit0, bit2, bit4, bit6.

  so the sum of all bit0, bit2, bit4 and bit6 values + cp0 itself is even.

Similarly cp1 is the sum of all bit1, bit3, bit5 and bit7.

- cp2 is the parity over bit0, bit1, bit4 and bit5
- cp3 is the parity over bit2, bit3, bit6 and bit7.
- cp4 is the parity over bit0, bit1, bit2 and bit3.
- cp5 is the parity over bit4, bit5, bit6 and bit7.

Note that each of cp0 .. cp5 is exactly one bit.

Row parity actually works almost the same.

- rp0 is the parity of all even bytes (0, 2, 4, 6, ... 252, 254)
- rp1 is the parity of all odd bytes (1, 3, 5, 7, ..., 253, 255)
- rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ...
  (so handle two bytes, then skip 2 bytes).
- rp3 is covers the half rp2 does not cover (bytes 2, 3, 6, 7, 10, 11, ...)
- for rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc.

  so rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...)
- and rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, ..

The story now becomes quite boring. I guess you get the idea.

- rp6 covers 8 bytes then skips 8 etc
- rp7 skips 8 bytes then covers 8 etc
- rp8 covers 16 bytes then skips 16 etc
- rp9 skips 16 bytes then covers 16 etc
- rp10 covers 32 bytes then skips 32 etc
- rp11 skips 32 bytes then covers 32 etc
- rp12 covers 64 bytes then skips 64 etc
- rp13 skips 64 bytes then covers 64 etc
- rp14 covers 128 bytes then skips 128
- rp15 skips 128 bytes then covers 128

In the end the parity bits are grouped together in three bytes as
follows:

=====  ===== ===== ===== ===== ===== ===== ===== =====
ECC    Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 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
=====  ===== ===== ===== ===== ===== ===== ===== =====

I detected after writing this that ST application note AN1823
(http://www.st.com/stonline/) gives a much
nicer picture.(but they use line parity as term where I use row parity)
Oh well, I'm graphically challenged, so suffer with me for a moment :-)

And I could not reuse the ST picture anyway for copyright reasons.

Attempt 0: bit 단위 직접 계산

첫 pseudocode는 256개 byte를 순회하며 index bit에 따라 각 byte의 8개 bit를 XOR해 `rp0..rp15` 중 하나에 누적합니다.

동시에 byte 안의 선택된 bit를 직접 XOR해 `cp0..cp5`를 갱신합니다. 원리를 그대로 옮긴 단순한 구현이지만 한 byte마다 매우 많은 bit 연산을 수행합니다.

Attempt 0
=========

Implementing the parity calculation is pretty simple.
In C pseudocode::

  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
  }

Analysis 0: XOR 결합 순서 변경

C와 대부분의 hardware에는 앞선 bit별 계산을 효율적으로 수행할 전용 연산이 없어 Attempt 0은 실용적인 고속 구현이 되기 어렵습니다.

XOR은 commutative이므로 값을 어떤 순서로 결합해도 됩니다. Column parity는 모든 byte를 먼저 XOR한 뒤 필요한 bit만 걸러내면 loop 밖에서 계산할 수 있습니다.

Row parity도 각 row 집합에 속한 byte를 먼저 XOR하는 방식으로 바꿀 수 있습니다.

Analysis 0
==========

C does have bitwise operators but not really operators to do the above
efficiently (and most hardware has no such instructions either).
Therefore without implementing this it was clear that the code above was
not going to bring me a Nobel prize :-)

Fortunately the exclusive or operation is commutative, so we can combine
the values in any order. So instead of calculating all the bits
individually, let us try to rearrange things.
For the column parity this is easy. We can just xor the bytes and in the
end filter out the relevant bits. This is pretty nice as it will bring
all cp calculation out of the for loop.

Similarly we can first xor the bytes for the various rows.
This leads to:

Attempt 1: byte XOR와 parity table

Attempt 1은 256-entry `parity` lookup table과 `ecc1()`을 사용합니다. 각 byte를 전체 parity `par`에 XOR하고 index bit에 따라 `rp0..rp15`의 보완 pair 중 하나에 byte 전체를 XOR합니다.

Loop가 끝나면 lookup table로 각 row accumulator의 1-bit parity를 구해 ECC 0과 ECC 1에 배치합니다. `par`에 mask `0xf0`, `0x0f`, `0xcc`, `0x33`, `0xaa`, `0x55`를 적용해 column parity를 ECC 2에 배치합니다.

마지막 세 invert는 erased flash의 모든 data가 `0xff`일 때 checksum도 `0xff 0xff 0xff`가 되도록 합니다. 작성자는 parity lookup이 가장 빠를 것으로 예상했지만 이후 다른 방법도 조사합니다.

Attempt 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];
  }

Still pretty straightforward. The last three invert statements are there to
give a checksum of 0xff 0xff 0xff for an empty flash. In an empty flash
all data is 0xff, so the checksum then matches.

I also introduced the parity lookup. I expected this to be the fastest
way to calculate the parity, but I will investigate alternatives later
on.

Analysis 1: 32-bit chunk 처리

코드는 동작하지만 작성자의 system에서는 Linux driver보다 거의 4배 오래 걸렸습니다. 개선 방향은 byte-wise에서 32-bit `unsigned long` chunk로 이동하는 것입니다.

32-bit `par`는 4개 byte의 XOR을 담으므로 byte 위치를 이용해 `rp0/rp1`과 `rp2/rp3`를 나중에 추출할 수 있습니다. Loop 횟수는 256회에서 64회로 줄어듭니다.

Long 안의 byte order는 machine-dependent이므로 endian에 주의해야 하며, 성능은 alignment에도 영향을 받습니다. 이 실험은 x86 DELL PC의 Intel D920에서 개발됐고 NAND I/O buffer가 적절히 align됐다고 가정합니다.

Analysis 1
==========

The code works, but is not terribly efficient. On my system it took
almost 4 times as much time as the linux driver code. But hey, if it was
*that* easy this would have been done long before.
No pain. no gain.

Fortunately there is plenty of room for improvement.

In step 1 we moved from bit-wise calculation to byte-wise calculation.
However in C we can also use the unsigned long data type and virtually
every modern microprocessor supports 32 bit operations, so why not try
to write our code in such a way that we process data in 32 bit chunks.

Of course this means some modification as the row parity is byte by
byte. A quick analysis:
for the column parity we use the par variable. When extending to 32 bits
we can in the end easily calculate rp0 and rp1 from it.
(because par now consists of 4 bytes, contributing to rp1, rp0, rp1, rp0
respectively, from MSB to LSB)
also rp2 and rp3 can be easily retrieved from par as rp3 covers the
first two MSBs and rp2 covers the last two LSBs.

Note that of course now the loop is executed only 64 times (256/4).
And note that care must taken wrt byte ordering. The way bytes are
ordered in a long is machine dependent, and might affect us.
Anyway, if there is an issue: this code is developed on x86 (to be
precise: a DELL PC with a D920 Intel CPU)

And of course the performance might depend on alignment, but I expect
that the I/O buffers in the nand driver are aligned properly (and
otherwise that should be fixed to get maximum performance).

Let's give it a try...

Attempt 2: `unsigned long` 누적

`ecc2()`는 input을 `unsigned long *`로 보고 64회 순회합니다. `par`에는 모든 32-bit word를 XOR하고, index mask에 따라 `rp4..rp15` pair 중 하나에 word를 누적합니다.

Loop 뒤 `rp4..rp15`는 shift와 XOR로 32 bit에서 한 byte로 fold합니다. `par`의 상·하위 word와 byte를 결합해 `rp0..rp3`을 만들고, 다시 한 byte의 column accumulator로 줄입니다.

최종 ECC bit 배치는 Attempt 1과 같으며 parity table lookup 후 세 byte를 invert합니다. 예제는 간결함을 위해 한 줄에 여러 statement와 단일 statement branch를 사용합니다.

Attempt 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];
  }

The parity array is not shown any more. Note also that for these
examples I kinda deviated from my regular programming style by allowing
multiple statements on a line, not using { } in then and else blocks
with only a single statement and by using operators like ^=

Analysis 2: inverse parity 관계

Attempt 2는 Linux driver보다 약 15% 빨랐습니다.

보완 row pair는 전체 parity와 XOR 관계를 가집니다. 예를 들어 `par = rp14 ^ rp15`이므로 `rp14 = par ^ rp15`이고, 같은 관계가 `rp4/5`부터 `rp12/13`까지 모두 성립합니다. 이를 inverse parity라고도 합니다.

따라서 각 `if`의 `else` 계산을 제거하고 loop 뒤에 보완 parity를 복원할 수 있습니다. Long을 먼저 byte로 줄이면 마지막 계산도 단순화하고 table lookup도 피할 가능성이 있습니다.

Analysis 2
==========

The code (of course) works, and hurray: we are a little bit faster than
the linux driver code (about 15%). But wait, don't cheer too quickly.
There is more to be gained.
If we look at e.g. rp14 and rp15 we see that we either xor our data with
rp14 or with rp15. However we also have par which goes over all data.
This means there is no need to calculate rp14 as it can be calculated from
rp15 through rp14 = par ^ rp15, because par = rp14 ^ rp15;
(or if desired we can avoid calculating rp15 and calculate it from
rp14).  That is why some places refer to inverse parity.
Of course the same thing holds for rp4/5, rp6/7, rp8/9, rp10/11 and rp12/13.
Effectively this means we can eliminate the else clause from the if
statements. Also we can optimise the calculation in the end a little bit
by going from long to byte first. Actually we can even avoid the table
lookups

Attempt 3: `else` 제거

Attempt 3은 index bit가 설정된 경우의 odd row parity만 loop에서 갱신하고 `else` branch를 제거합니다.

Loop 밖에서 `rp4 = par ^ rp5`부터 `rp14 = par ^ rp15`까지 even parity를 복원합니다.

Statement 수와 assembly instruction이 줄었음에도 실행 시간은 약 30% 늘었습니다.

Attempt 3
=========

Odd replaced::

          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;

with::

          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;

and outside the loop added::

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

And after that the code takes about 30% more time, although the number of
statements is reduced. This is also reflected in the assembly code.

Analysis 3: instruction-level 영향

예상과 반대인 결과는 cache나 instruction parallelism 영향으로 추정됐습니다. 900 MHz Celeron eeePC는 3 GHz D920보다 실행 시간이 약 30%만 느린 흥미로운 결과도 보였습니다.

작성자는 Attempt 2 코드로 돌아가 loop unrolling을 여러 정도로 적용해 `if` 수를 줄이는 방향을 시험합니다.

Analysis 3
==========

Very weird. Guess it has to do with caching or instruction parallelism
or so. I also tried on an eeePC (Celeron, clocked at 900 Mhz). Interesting
observation was that this one is only 30% slower (according to time)
executing the code as my 3Ghz D920 processor.

Well, it was expected not to be easy so maybe instead move to a
different track: let's move back to the code from attempt2 and do some
loop unrolling. This will eliminate a few if statements. I'll try
different amounts of unrolling to see what works best.

Attempt 4: loop unrolling

Loop를 1, 2, 3, 4회 unroll해 비교했습니다. 4회 unroll 예시는 각 word 위치에서 확정되는 row parity를 branch 없이 갱신하고, 상위 pair에 필요한 일부 조건만 남깁니다.

Attempt 4
=========

Unrolled the loop 1, 2, 3 and 4 times.
For 4 the code starts with::

    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;
        ...

Analysis 4: unroll 측정과 pair 제거

1회와 2회 unroll은 Attempt 2보다 약 15%, 3회는 약 30% 향상됐고 4회는 3회보다 소폭만 더 빨랐습니다. 이후 최적화를 기대해 4회 unroll을 선택했습니다.

전체 parity와 pair 관계를 다시 이용하면 `par = rp4 ^ rp5`이므로 `rp5 = par ^ rp4`입니다. 같은 방식으로 모든 row pair에서 한 accumulator를 제거할 수 있습니다.

Analysis 4
==========

Unrolling once gains about 15%

Unrolling twice keeps the gain at about 15%

Unrolling three times gives a gain of 30% compared to attempt 2.

Unrolling four times gives a marginal improvement compared to unrolling
three times.

I decided to proceed with a four time unrolled loop anyway. It was my gut
feeling that in the next steps I would obtain additional gain from it.

The next step was triggered by the fact that par contains the xor of all
bytes and rp4 and rp5 each contain the xor of half of the bytes.
So in effect par = rp4 ^ rp5. But as xor is commutative we can also say
that rp5 = par ^ rp4. So no need to keep both rp4 and rp5 around. We can
eliminate rp5 (or rp4, but I already foresaw another optimisation).
The same holds for rp6/7, rp8/9, rp10/11 rp12/13 and rp14/15.

Attempt 5: odd row accumulator 제거

Loop 안의 odd-numbered row parity assignment와 해당 `else` clause를 모두 제거합니다.

Loop가 끝난 뒤 `rp5 = par ^ rp4` 같은 식으로 odd parity를 복원합니다. 제거된 accumulator의 초기화와 `rp0..rp3` 초기화도 없앴습니다.

Attempt 5
=========

Effectively so all odd digit rp assignments in the loop were removed.
This included the else clause of the if statements.
Of course after the loop we need to correct things by adding code like::

    rp5 = par ^ rp4;

Also the initial assignments (rp5 = 0; etc) could be removed.
Along the line I also removed the initialisation of rp0/1/2/3.

Analysis 5: runtime 절반

Attempt 5는 4회 unroll한 Attempt 4보다 runtime이 대략 절반이 됐고, 당시 Linux kernel 코드의 processor time 중 약 1/3만 사용했습니다.

작성자는 남은 `if`를 줄이기 위해 running parity를 유지하고 마지막 조건만 남기는 새 버전을 시도합니다.

Analysis 5
==========

Measurements showed this was a good move. The run-time roughly halved
compared with attempt 4 with 4 times unrolled, and we only require 1/3rd
of the processor time compared to the current code in the linux kernel.

However, still I thought there was more. I didn't like all the if
statements. Why not keep a running parity and only keep the last if
statement. Time for yet another version!

Attempt 6: running `tmppar`

각 outer iteration에서 `tmppar`가 16개 word의 running parity를 누적합니다. 고정 위치마다 `rp4`, `rp6`, `rp8`, `rp10`에 현재 word 또는 누적 parity를 반영합니다.

마지막에는 `tmppar`를 전체 `par`에 더하고 outer index 조건에 따라 `rp12`와 `rp14`에 반영합니다.

예를 들어 연속된 `rp4 ^= cur; rp6 ^= cur;` 대신 다음 statement에서 `rp6 ^= tmppar`를 사용해 같은 XOR을 적은 statement로 계산합니다. `rp8`과 `rp10`에도 같은 변환을 적용합니다.

Attempt 6
=========

THe code within the for loop was changed to::

    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;
    }

As you can see tmppar is used to accumulate the parity within a for
iteration. In the last 3 statements is added to par and, if needed,
to rp12 and rp14.

While making the changes I also found that I could exploit that tmppar
contains the running parity for this iteration. So instead of having:
rp4 ^= cur; rp6 ^= cur;
I removed the rp6 ^= cur; statement and did rp6 ^= tmppar; on next
statement. A similar change was done for rp8 and rp10

Analysis 6: 큰 성능 향상

기존 Linux 코드를 100만 회 실행하면 약 1초였지만 Attempt 6은 약 0.075초였습니다. 측정 정확도를 위해 이후에는 1,000만 회 단위로 측정할 정도로 큰 향상이었습니다.

추가 아이디어는 세 곳의 `rp4 ^= cur; rp6 ^= cur;`를 `rp4_6` accumulator 하나로 합쳐 loop당 세 statement를 줄이고, loop 뒤 두 parity에 반영하는 것입니다.

또한 `rp8`의 연속 네 assignment 전 값을 `notrp8`에 저장하고 XOR의 교환 법칙으로 한 번에 결합할 수 있습니다.

Analysis 6
==========

Measuring this code again showed big gain. When executing the original
linux code 1 million times, this took about 1 second on my system.
(using time to measure the performance). After this iteration I was back
to 0.075 sec. Actually I had to decide to start measuring over 10
million iterations in order not to lose too much accuracy. This one
definitely seemed to be the jackpot!

There is a little bit more room for improvement though. There are three
places with statements::

        rp4 ^= cur; rp6 ^= cur;

It seems more efficient to also maintain a variable rp4_6 in the while
loop; This eliminates 3 statements per loop. Of course after the loop we
need to correct by adding::

        rp4 ^= rp4_6;
        rp6 ^= rp4_6

Furthermore there are 4 sequential assignments to rp8. This can be
encoded slightly more efficiently by saving tmppar before those 4 lines
and later do rp8 = rp8 ^ tmppar ^ notrp8;
(where notrp8 is the value of rp8 before those 4 lines).
Again a use of the commutative property of xor.
Time for a new test!

Attempt 7: 공통 accumulator

Attempt 7은 `rp4_6`에 `rp4`와 `rp6`의 공통 word를 모으고 loop 뒤 두 accumulator에 XOR합니다.

`notrp8`에는 네 word 처리 전의 `tmppar`를 저장한 뒤 `rp8 = rp8 ^ tmppar ^ notrp8`로 구간 parity를 한 번에 반영합니다.

변화는 크지 않지만 loop 안 statement를 더 줄이려는 시도입니다.

Attempt 7
=========

The new code now looks like::

    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;


Not a big change, but every penny counts :-)

Analysis 7: 작은 퇴보

Attempt 7은 큰 차이는 아니지만 오히려 느려졌습니다. 원인은 다시 cache일 가능성이 있으며 나중에 조사할 수 있습니다.

Loop 내부에서 얻을 수 있는 개선이 거의 끝났다고 보고 한 단계 더 unroll을 시험하되, 일단 Attempt 7 변경을 유지합니다.

Analysis 7
==========

Actually this made things worse. Not very much, but I don't want to move
into the wrong direction. Maybe something to investigate later. Could
have to do with caching again.

Guess that is what there is to win within the loop. Maybe unrolling one
more time will help. I'll keep the optimisations from 7 for now.

Attempt 8: 한 번 더 unroll

Loop를 한 단계 더 unroll했습니다.

Attempt 8
=========

Unrolled the loop one more time.

Analysis 8: ECC byte 생성 최적화

추가 unroll은 성능을 더 나쁘게 했으므로 Attempt 6으로 돌아갑니다.

Loop 내부 최적화 대신 전체 parity가 0이면 각 row pair가 같고, 1이면 서로 반대라는 관계를 ECC byte 생성에 이용합니다.

Pair가 같으면 even bit만 result byte에 기록한 뒤 `code[0] |= code[0] << 1` 같은 연산으로 odd 위치를 채울 수 있습니다.

Analysis 8
==========

This makes things worse. Let's stick with attempt 6 and continue from there.
Although it seems that the code within the loop cannot be optimised
further there is still room to optimize the generation of the ecc codes.
We can simply calculate the total parity. If this is 0 then rp4 = rp5
etc. If the parity is 1, then rp4 = !rp5;

But if rp4 = rp5 we do not need rp5 etc. We can just write the even bits
in the result byte and then do something like::

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

Lets test this.

Attempt 9: 최종 계산과 trade-off

ECC byte 생성 변경은 성능을 약간 떨어뜨렸습니다. Shift를 피하려 dedicated parity array를 사용하거나 table lookup을 shift/XOR sequence로 바꾸는 시도도 이득이 없었습니다.

유일한 소폭 개선은 parity bit를 미리 invert해 마지막 세 invert statement를 제거한 것입니다.

1,000만 회 기준 Linux driver는 13~13.5초, 최적화 코드는 약 0.73초로 작성자의 system에서 약 18배 빨랐습니다. Hardware가 다르면 결과도 달라집니다.

대가로 code size는 562 byte에서 1,434 byte로 거의 세 배가 됐습니다.

Attempt 9
=========

Changed the code but again this slightly degrades performance. Tried all
kind of other things, like having dedicated parity arrays to avoid the
shift after parity[rp7] << 7; No gain.
Change the lookup using the parity array by using shift operators (e.g.
replace parity[rp7] << 7 with::

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

No gain.

The only marginal change was inverting the parity bits, so we can remove
the last three invert statements.

Ah well, pity this does not deliver more. Then again 10 million
iterations using the linux driver code takes between 13 and 13.5
seconds, whereas my code now takes about 0.73 seconds for those 10
million iterations. So basically I've improved the performance by a
factor 18 on my system. Not that bad. Of course on different hardware
you will get different results. No warranties!

But of course there is no such thing as a free lunch. The codesize almost
tripled (from 562 bytes to 1434 bytes). Then again, it is not that much.

ECC syndrome으로 오류 정정

오류 정정은 ST application note와 기존 코드를 바탕으로 합니다. 저장된 ECC와 새로 계산한 ECC를 XOR해 syndrome을 만듭니다.

세 byte가 모두 0이면 오류가 없습니다. 1인 bit가 11개면 정정 가능한 single-bit data error이고, 1인 bit가 하나면 저장된 ECC code 자체의 오류입니다.

Table lookup을 사용하면 repair가 필요할 때 작성자의 system에서 약 2배, repair가 없을 때 약 1% 향상됐습니다. Function code size는 GCC 4.2 `-O3` 기준 330 byte에서 686 byte로 늘었습니다.

Correcting errors
=================

For correcting errors I again used the ST application note as a starter,
but I also peeked at the existing code.

The algorithm itself is pretty straightforward. Just xor the given and
the calculated ecc. If all bytes are 0 there is no problem. If 11 bits
are 1 we have one correctable bit error. If there is 1 bit 1, we have an
error in the given ecc code.

It proved to be fastest to do some table lookups. Performance gain
introduced by this is about a factor 2 on my system when a repair had to
be done, and 1% or so if no repair had to be done.

Code size increased from 330 bytes to 686 bytes for this function.
(gcc 4.2, -O3)

결론과 platform별 결과

ECC 계산은 개발 hardware에서 18배, embedded MIPS system에서 7배, big-endian ARMv5TE Linksys NSLU2에서 GCC 4.1.2 `-O3` 기준 5배 빨라졌습니다.

Bitflip은 드물기 때문에 correction path에서는 큰 이득이 없었지만 원래 소비 cycle도 훨씬 적습니다.

C 구현에서 추가 개선 여지는 크지 않아 보입니다. Assembly는 더 빠를 수 있지만 pipeline behavior 때문에, 특히 Intel hardware에서는 매우 까다롭습니다.

저자는 Frans Meulenbroeks이며 저작권은 2008 Koninklijke Philips Electronics NV에 있습니다.

Conclusion
==========

The gain when calculating the ecc is tremendous. Om my development hardware
a speedup of a factor of 18 for ecc calculation was achieved. On a test on an
embedded system with a MIPS core a factor 7 was obtained.

On a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor
5 (big endian mode, gcc 4.1.2, -O3)

For correction not much gain could be obtained (as bitflips are rare). Then
again there are also much less cycles spent there.

It seems there is not much more gain possible in this, at least when
programmed in C. Of course it might be possible to squeeze something more
out of it with an assembler program, but due to pipeline behaviour etc
this is very tricky (at least for intel hw).

Author: Frans Meulenbroeks

Copyright (C) 2008 Koninklijke Philips Electronics NV.