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
版權 (C) 2008 Koninklijke Philips Electronics NV.