| 1 |
========================== |
| 2 |
NAND Error-correction Code |
| 3 |
========================== |
| 4 |
|
| 5 |
Introduction |
| 6 |
============ |
| 7 |
|
| 8 |
Having looked at the linux mtd/nand Hamming software ECC engine driver |
| 9 |
I felt there was room for optimisation. I bashed the code for a few hours |
| 10 |
performing tricks like table lookup removing superfluous code etc. |
| 11 |
After that the speed was increased by 35-40%. |
| 12 |
Still I was not too happy as I felt there was additional room for improvement. |
| 13 |
|
| 14 |
Bad! I was hooked. |
| 15 |
I decided to annotate my steps in this file. Perhaps it is useful to someone |
| 16 |
or someone learns something from it. |
| 17 |
|
| 18 |
|
| 19 |
The problem |
| 20 |
=========== |
| 21 |
|
| 22 |
NAND flash (at least SLC one) typically has sectors of 256 bytes. |
| 23 |
However NAND flash is not extremely reliable so some error detection |
| 24 |
(and sometimes correction) is needed. |
| 25 |
|
| 26 |
This is done by means of a Hamming code. I'll try to explain it in |
| 27 |
laymans terms (and apologies to all the pro's in the field in case I do |
| 28 |
not use the right terminology, my coding theory class was almost 30 |
| 29 |
years ago, and I must admit it was not one of my favourites). |
| 30 |
|
| 31 |
As I said before the ecc calculation is performed on sectors of 256 |
| 32 |
bytes. This is done by calculating several parity bits over the rows and |
| 33 |
columns. The parity used is even parity which means that the parity bit = 1 |
| 34 |
if the data over which the parity is calculated is 1 and the parity bit = 0 |
| 35 |
if the data over which the parity is calculated is 0. So the total |
| 36 |
number of bits over the data over which the parity is calculated + the |
| 37 |
parity bit is even. (see wikipedia if you can't follow this). |
| 38 |
Parity is often calculated by means of an exclusive or operation, |
| 39 |
sometimes also referred to as xor. In C the operator for xor is ^ |
| 40 |
|
| 41 |
Back to ecc. |
| 42 |
Let's give a small figure: |
| 43 |
|
| 44 |
========= ==== ==== ==== ==== ==== ==== ==== ==== === === === === ==== |
| 45 |
byte 0: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp0 rp2 rp4 ... rp14 |
| 46 |
byte 1: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp1 rp2 rp4 ... rp14 |
| 47 |
byte 2: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp0 rp3 rp4 ... rp14 |
| 48 |
byte 3: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp1 rp3 rp4 ... rp14 |
| 49 |
byte 4: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp0 rp2 rp5 ... rp14 |
| 50 |
... |
| 51 |
byte 254: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp0 rp3 rp5 ... rp15 |
| 52 |
byte 255: bit7 bit6 bit5 bit4 bit3 bit2 bit1 bit0 rp1 rp3 rp5 ... rp15 |
| 53 |
cp1 cp0 cp1 cp0 cp1 cp0 cp1 cp0 |
| 54 |
cp3 cp3 cp2 cp2 cp3 cp3 cp2 cp2 |
| 55 |
cp5 cp5 cp5 cp5 cp4 cp4 cp4 cp4 |
| 56 |
========= ==== ==== ==== ==== ==== ==== ==== ==== === === === === ==== |
| 57 |
|
| 58 |
This figure represents a sector of 256 bytes. |
| 59 |
cp is my abbreviation for column parity, rp for row parity. |
| 60 |
|
| 61 |
Let's start to explain column parity. |
| 62 |
|
| 63 |
- cp0 is the parity that belongs to all bit0, bit2, bit4, bit6. |
| 64 |
|
| 65 |
so the sum of all bit0, bit2, bit4 and bit6 values + cp0 itself is even. |
| 66 |
|
| 67 |
Similarly cp1 is the sum of all bit1, bit3, bit5 and bit7. |
| 68 |
|
| 69 |
- cp2 is the parity over bit0, bit1, bit4 and bit5 |
| 70 |
- cp3 is the parity over bit2, bit3, bit6 and bit7. |
| 71 |
- cp4 is the parity over bit0, bit1, bit2 and bit3. |
| 72 |
- cp5 is the parity over bit4, bit5, bit6 and bit7. |
| 73 |
|
| 74 |
Note that each of cp0 .. cp5 is exactly one bit. |
| 75 |
|
| 76 |
Row parity actually works almost the same. |
| 77 |
|
| 78 |
- rp0 is the parity of all even bytes (0, 2, 4, 6, ... 252, 254) |
| 79 |
- rp1 is the parity of all odd bytes (1, 3, 5, 7, ..., 253, 255) |
| 80 |
- rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ... |
| 81 |
(so handle two bytes, then skip 2 bytes). |
| 82 |
- rp3 is covers the half rp2 does not cover (bytes 2, 3, 6, 7, 10, 11, ...) |
| 83 |
- for rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc. |
| 84 |
|
| 85 |
so rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...) |
| 86 |
- and rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, .. |
| 87 |
|
| 88 |
The story now becomes quite boring. I guess you get the idea. |
| 89 |
|
| 90 |
- rp6 covers 8 bytes then skips 8 etc |
| 91 |
- rp7 skips 8 bytes then covers 8 etc |
| 92 |
- rp8 covers 16 bytes then skips 16 etc |
| 93 |
- rp9 skips 16 bytes then covers 16 etc |
| 94 |
- rp10 covers 32 bytes then skips 32 etc |
| 95 |
- rp11 skips 32 bytes then covers 32 etc |
| 96 |
- rp12 covers 64 bytes then skips 64 etc |
| 97 |
- rp13 skips 64 bytes then covers 64 etc |
| 98 |
- rp14 covers 128 bytes then skips 128 |
| 99 |
- rp15 skips 128 bytes then covers 128 |
| 100 |
|
| 101 |
In the end the parity bits are grouped together in three bytes as |
| 102 |
follows: |
| 103 |
|
| 104 |
===== ===== ===== ===== ===== ===== ===== ===== ===== |
| 105 |
ECC Bit 7 Bit 6 Bit 5 Bit 4 Bit 3 Bit 2 Bit 1 Bit 0 |
| 106 |
===== ===== ===== ===== ===== ===== ===== ===== ===== |
| 107 |
ECC 0 rp07 rp06 rp05 rp04 rp03 rp02 rp01 rp00 |
| 108 |
ECC 1 rp15 rp14 rp13 rp12 rp11 rp10 rp09 rp08 |
| 109 |
ECC 2 cp5 cp4 cp3 cp2 cp1 cp0 1 1 |
| 110 |
===== ===== ===== ===== ===== ===== ===== ===== ===== |
| 111 |
|
| 112 |
I detected after writing this that ST application note AN1823 |
| 113 |
(http://www.st.com/stonline/) gives a much |
| 114 |
nicer picture.(but they use line parity as term where I use row parity) |
| 115 |
Oh well, I'm graphically challenged, so suffer with me for a moment :-) |
| 116 |
|
| 117 |
And I could not reuse the ST picture anyway for copyright reasons. |
| 118 |
|
| 119 |
|
| 120 |
Attempt 0 |
| 121 |
========= |
| 122 |
|
| 123 |
Implementing the parity calculation is pretty simple. |
| 124 |
In C pseudocode:: |
| 125 |
|
| 126 |
for (i = 0; i < 256; i++) |
| 127 |
{ |
| 128 |
if (i & 0x01) |
| 129 |
rp1 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp1; |
| 130 |
else |
| 131 |
rp0 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp0; |
| 132 |
if (i & 0x02) |
| 133 |
rp3 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp3; |
| 134 |
else |
| 135 |
rp2 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp2; |
| 136 |
if (i & 0x04) |
| 137 |
rp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp5; |
| 138 |
else |
| 139 |
rp4 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp4; |
| 140 |
if (i & 0x08) |
| 141 |
rp7 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp7; |
| 142 |
else |
| 143 |
rp6 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp6; |
| 144 |
if (i & 0x10) |
| 145 |
rp9 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp9; |
| 146 |
else |
| 147 |
rp8 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp8; |
| 148 |
if (i & 0x20) |
| 149 |
rp11 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp11; |
| 150 |
else |
| 151 |
rp10 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp10; |
| 152 |
if (i & 0x40) |
| 153 |
rp13 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp13; |
| 154 |
else |
| 155 |
rp12 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp12; |
| 156 |
if (i & 0x80) |
| 157 |
rp15 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp15; |
| 158 |
else |
| 159 |
rp14 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp14; |
| 160 |
cp0 = bit6 ^ bit4 ^ bit2 ^ bit0 ^ cp0; |
| 161 |
cp1 = bit7 ^ bit5 ^ bit3 ^ bit1 ^ cp1; |
| 162 |
cp2 = bit5 ^ bit4 ^ bit1 ^ bit0 ^ cp2; |
| 163 |
cp3 = bit7 ^ bit6 ^ bit3 ^ bit2 ^ cp3 |
| 164 |
cp4 = bit3 ^ bit2 ^ bit1 ^ bit0 ^ cp4 |
| 165 |
cp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ cp5 |
| 166 |
} |
| 167 |
|
| 168 |
|
| 169 |
Analysis 0 |
| 170 |
========== |
| 171 |
|
| 172 |
C does have bitwise operators but not really operators to do the above |
| 173 |
efficiently (and most hardware has no such instructions either). |
| 174 |
Therefore without implementing this it was clear that the code above was |
| 175 |
not going to bring me a Nobel prize :-) |
| 176 |
|
| 177 |
Fortunately the exclusive or operation is commutative, so we can combine |
| 178 |
the values in any order. So instead of calculating all the bits |
| 179 |
individually, let us try to rearrange things. |
| 180 |
For the column parity this is easy. We can just xor the bytes and in the |
| 181 |
end filter out the relevant bits. This is pretty nice as it will bring |
| 182 |
all cp calculation out of the for loop. |
| 183 |
|
| 184 |
Similarly we can first xor the bytes for the various rows. |
| 185 |
This leads to: |
| 186 |
|
| 187 |
|
| 188 |
Attempt 1 |
| 189 |
========= |
| 190 |
|
| 191 |
:: |
| 192 |
|
| 193 |
const char parity[256] = { |
| 194 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 195 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 196 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 197 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 198 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 199 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 200 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 201 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 202 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 203 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 204 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 205 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 206 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, |
| 207 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 208 |
1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, |
| 209 |
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 |
| 210 |
}; |
| 211 |
|
| 212 |
void ecc1(const unsigned char *buf, unsigned char *code) |
| 213 |
{ |
| 214 |
int i; |
| 215 |
const unsigned char *bp = buf; |
| 216 |
unsigned char cur; |
| 217 |
unsigned char rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; |
| 218 |
unsigned char rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; |
| 219 |
unsigned char par; |
| 220 |
|
| 221 |
par = 0; |
| 222 |
rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; |
| 223 |
rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; |
| 224 |
rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; |
| 225 |
rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; |
| 226 |
|
| 227 |
for (i = 0; i < 256; i++) |
| 228 |
{ |
| 229 |
cur = *bp++; |
| 230 |
par ^= cur; |
| 231 |
if (i & 0x01) rp1 ^= cur; else rp0 ^= cur; |
| 232 |
if (i & 0x02) rp3 ^= cur; else rp2 ^= cur; |
| 233 |
if (i & 0x04) rp5 ^= cur; else rp4 ^= cur; |
| 234 |
if (i & 0x08) rp7 ^= cur; else rp6 ^= cur; |
| 235 |
if (i & 0x10) rp9 ^= cur; else rp8 ^= cur; |
| 236 |
if (i & 0x20) rp11 ^= cur; else rp10 ^= cur; |
| 237 |
if (i & 0x40) rp13 ^= cur; else rp12 ^= cur; |
| 238 |
if (i & 0x80) rp15 ^= cur; else rp14 ^= cur; |
| 239 |
} |
| 240 |
code[0] = |
| 241 |
(parity[rp7] << 7) | |
| 242 |
(parity[rp6] << 6) | |
| 243 |
(parity[rp5] << 5) | |
| 244 |
(parity[rp4] << 4) | |
| 245 |
(parity[rp3] << 3) | |
| 246 |
(parity[rp2] << 2) | |
| 247 |
(parity[rp1] << 1) | |
| 248 |
(parity[rp0]); |
| 249 |
code[1] = |
| 250 |
(parity[rp15] << 7) | |
| 251 |
(parity[rp14] << 6) | |
| 252 |
(parity[rp13] << 5) | |
| 253 |
(parity[rp12] << 4) | |
| 254 |
(parity[rp11] << 3) | |
| 255 |
(parity[rp10] << 2) | |
| 256 |
(parity[rp9] << 1) | |
| 257 |
(parity[rp8]); |
| 258 |
code[2] = |
| 259 |
(parity[par & 0xf0] << 7) | |
| 260 |
(parity[par & 0x0f] << 6) | |
| 261 |
(parity[par & 0xcc] << 5) | |
| 262 |
(parity[par & 0x33] << 4) | |
| 263 |
(parity[par & 0xaa] << 3) | |
| 264 |
(parity[par & 0x55] << 2); |
| 265 |
code[0] = ~code[0]; |
| 266 |
code[1] = ~code[1]; |
| 267 |
code[2] = ~code[2]; |
| 268 |
} |
| 269 |
|
| 270 |
Still pretty straightforward. The last three invert statements are there to |
| 271 |
give a checksum of 0xff 0xff 0xff for an empty flash. In an empty flash |
| 272 |
all data is 0xff, so the checksum then matches. |
| 273 |
|
| 274 |
I also introduced the parity lookup. I expected this to be the fastest |
| 275 |
way to calculate the parity, but I will investigate alternatives later |
| 276 |
on. |
| 277 |
|
| 278 |
|
| 279 |
Analysis 1 |
| 280 |
========== |
| 281 |
|
| 282 |
The code works, but is not terribly efficient. On my system it took |
| 283 |
almost 4 times as much time as the linux driver code. But hey, if it was |
| 284 |
*that* easy this would have been done long before. |
| 285 |
No pain. no gain. |
| 286 |
|
| 287 |
Fortunately there is plenty of room for improvement. |
| 288 |
|
| 289 |
In step 1 we moved from bit-wise calculation to byte-wise calculation. |
| 290 |
However in C we can also use the unsigned long data type and virtually |
| 291 |
every modern microprocessor supports 32 bit operations, so why not try |
| 292 |
to write our code in such a way that we process data in 32 bit chunks. |
| 293 |
|
| 294 |
Of course this means some modification as the row parity is byte by |
| 295 |
byte. A quick analysis: |
| 296 |
for the column parity we use the par variable. When extending to 32 bits |
| 297 |
we can in the end easily calculate rp0 and rp1 from it. |
| 298 |
(because par now consists of 4 bytes, contributing to rp1, rp0, rp1, rp0 |
| 299 |
respectively, from MSB to LSB) |
| 300 |
also rp2 and rp3 can be easily retrieved from par as rp3 covers the |
| 301 |
first two MSBs and rp2 covers the last two LSBs. |
| 302 |
|
| 303 |
Note that of course now the loop is executed only 64 times (256/4). |
| 304 |
And note that care must taken wrt byte ordering. The way bytes are |
| 305 |
ordered in a long is machine dependent, and might affect us. |
| 306 |
Anyway, if there is an issue: this code is developed on x86 (to be |
| 307 |
precise: a DELL PC with a D920 Intel CPU) |
| 308 |
|
| 309 |
And of course the performance might depend on alignment, but I expect |
| 310 |
that the I/O buffers in the nand driver are aligned properly (and |
| 311 |
otherwise that should be fixed to get maximum performance). |
| 312 |
|
| 313 |
Let's give it a try... |
| 314 |
|
| 315 |
|
| 316 |
Attempt 2 |
| 317 |
========= |
| 318 |
|
| 319 |
:: |
| 320 |
|
| 321 |
extern const char parity[256]; |
| 322 |
|
| 323 |
void ecc2(const unsigned char *buf, unsigned char *code) |
| 324 |
{ |
| 325 |
int i; |
| 326 |
const unsigned long *bp = (unsigned long *)buf; |
| 327 |
unsigned long cur; |
| 328 |
unsigned long rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; |
| 329 |
unsigned long rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; |
| 330 |
unsigned long par; |
| 331 |
|
| 332 |
par = 0; |
| 333 |
rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; |
| 334 |
rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; |
| 335 |
rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; |
| 336 |
rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; |
| 337 |
|
| 338 |
for (i = 0; i < 64; i++) |
| 339 |
{ |
| 340 |
cur = *bp++; |
| 341 |
par ^= cur; |
| 342 |
if (i & 0x01) rp5 ^= cur; else rp4 ^= cur; |
| 343 |
if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; |
| 344 |
if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; |
| 345 |
if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; |
| 346 |
if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; |
| 347 |
if (i & 0x20) rp15 ^= cur; else rp14 ^= cur; |
| 348 |
} |
| 349 |
/* |
| 350 |
we need to adapt the code generation for the fact that rp vars are now |
| 351 |
long; also the column parity calculation needs to be changed. |
| 352 |
we'll bring rp4 to 15 back to single byte entities by shifting and |
| 353 |
xoring |
| 354 |
*/ |
| 355 |
rp4 ^= (rp4 >> 16); rp4 ^= (rp4 >> 8); rp4 &= 0xff; |
| 356 |
rp5 ^= (rp5 >> 16); rp5 ^= (rp5 >> 8); rp5 &= 0xff; |
| 357 |
rp6 ^= (rp6 >> 16); rp6 ^= (rp6 >> 8); rp6 &= 0xff; |
| 358 |
rp7 ^= (rp7 >> 16); rp7 ^= (rp7 >> 8); rp7 &= 0xff; |
| 359 |
rp8 ^= (rp8 >> 16); rp8 ^= (rp8 >> 8); rp8 &= 0xff; |
| 360 |
rp9 ^= (rp9 >> 16); rp9 ^= (rp9 >> 8); rp9 &= 0xff; |
| 361 |
rp10 ^= (rp10 >> 16); rp10 ^= (rp10 >> 8); rp10 &= 0xff; |
| 362 |
rp11 ^= (rp11 >> 16); rp11 ^= (rp11 >> 8); rp11 &= 0xff; |
| 363 |
rp12 ^= (rp12 >> 16); rp12 ^= (rp12 >> 8); rp12 &= 0xff; |
| 364 |
rp13 ^= (rp13 >> 16); rp13 ^= (rp13 >> 8); rp13 &= 0xff; |
| 365 |
rp14 ^= (rp14 >> 16); rp14 ^= (rp14 >> 8); rp14 &= 0xff; |
| 366 |
rp15 ^= (rp15 >> 16); rp15 ^= (rp15 >> 8); rp15 &= 0xff; |
| 367 |
rp3 = (par >> 16); rp3 ^= (rp3 >> 8); rp3 &= 0xff; |
| 368 |
rp2 = par & 0xffff; rp2 ^= (rp2 >> 8); rp2 &= 0xff; |
| 369 |
par ^= (par >> 16); |
| 370 |
rp1 = (par >> 8); rp1 &= 0xff; |
| 371 |
rp0 = (par & 0xff); |
| 372 |
par ^= (par >> 8); par &= 0xff; |
| 373 |
|
| 374 |
code[0] = |
| 375 |
(parity[rp7] << 7) | |
| 376 |
(parity[rp6] << 6) | |
| 377 |
(parity[rp5] << 5) | |
| 378 |
(parity[rp4] << 4) | |
| 379 |
(parity[rp3] << 3) | |
| 380 |
(parity[rp2] << 2) | |
| 381 |
(parity[rp1] << 1) | |
| 382 |
(parity[rp0]); |
| 383 |
code[1] = |
| 384 |
(parity[rp15] << 7) | |
| 385 |
(parity[rp14] << 6) | |
| 386 |
(parity[rp13] << 5) | |
| 387 |
(parity[rp12] << 4) | |
| 388 |
(parity[rp11] << 3) | |
| 389 |
(parity[rp10] << 2) | |
| 390 |
(parity[rp9] << 1) | |
| 391 |
(parity[rp8]); |
| 392 |
code[2] = |
| 393 |
(parity[par & 0xf0] << 7) | |
| 394 |
(parity[par & 0x0f] << 6) | |
| 395 |
(parity[par & 0xcc] << 5) | |
| 396 |
(parity[par & 0x33] << 4) | |
| 397 |
(parity[par & 0xaa] << 3) | |
| 398 |
(parity[par & 0x55] << 2); |
| 399 |
code[0] = ~code[0]; |
| 400 |
code[1] = ~code[1]; |
| 401 |
code[2] = ~code[2]; |
| 402 |
} |
| 403 |
|
| 404 |
The parity array is not shown any more. Note also that for these |
| 405 |
examples I kinda deviated from my regular programming style by allowing |
| 406 |
multiple statements on a line, not using { } in then and else blocks |
| 407 |
with only a single statement and by using operators like ^= |
| 408 |
|
| 409 |
|
| 410 |
Analysis 2 |
| 411 |
========== |
| 412 |
|
| 413 |
The code (of course) works, and hurray: we are a little bit faster than |
| 414 |
the linux driver code (about 15%). But wait, don't cheer too quickly. |
| 415 |
There is more to be gained. |
| 416 |
If we look at e.g. rp14 and rp15 we see that we either xor our data with |
| 417 |
rp14 or with rp15. However we also have par which goes over all data. |
| 418 |
This means there is no need to calculate rp14 as it can be calculated from |
| 419 |
rp15 through rp14 = par ^ rp15, because par = rp14 ^ rp15; |
| 420 |
(or if desired we can avoid calculating rp15 and calculate it from |
| 421 |
rp14). That is why some places refer to inverse parity. |
| 422 |
Of course the same thing holds for rp4/5, rp6/7, rp8/9, rp10/11 and rp12/13. |
| 423 |
Effectively this means we can eliminate the else clause from the if |
| 424 |
statements. Also we can optimise the calculation in the end a little bit |
| 425 |
by going from long to byte first. Actually we can even avoid the table |
| 426 |
lookups |
| 427 |
|
| 428 |
Attempt 3 |
| 429 |
========= |
| 430 |
|
| 431 |
Odd replaced:: |
| 432 |
|
| 433 |
if (i & 0x01) rp5 ^= cur; else rp4 ^= cur; |
| 434 |
if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; |
| 435 |
if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; |
| 436 |
if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; |
| 437 |
if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; |
| 438 |
if (i & 0x20) rp15 ^= cur; else rp14 ^= cur; |
| 439 |
|
| 440 |
with:: |
| 441 |
|
| 442 |
if (i & 0x01) rp5 ^= cur; |
| 443 |
if (i & 0x02) rp7 ^= cur; |
| 444 |
if (i & 0x04) rp9 ^= cur; |
| 445 |
if (i & 0x08) rp11 ^= cur; |
| 446 |
if (i & 0x10) rp13 ^= cur; |
| 447 |
if (i & 0x20) rp15 ^= cur; |
| 448 |
|
| 449 |
and outside the loop added:: |
| 450 |
|
| 451 |
rp4 = par ^ rp5; |
| 452 |
rp6 = par ^ rp7; |
| 453 |
rp8 = par ^ rp9; |
| 454 |
rp10 = par ^ rp11; |
| 455 |
rp12 = par ^ rp13; |
| 456 |
rp14 = par ^ rp15; |
| 457 |
|
| 458 |
And after that the code takes about 30% more time, although the number of |
| 459 |
statements is reduced. This is also reflected in the assembly code. |
| 460 |
|
| 461 |
|
| 462 |
Analysis 3 |
| 463 |
========== |
| 464 |
|
| 465 |
Very weird. Guess it has to do with caching or instruction parallelism |
| 466 |
or so. I also tried on an eeePC (Celeron, clocked at 900 Mhz). Interesting |
| 467 |
observation was that this one is only 30% slower (according to time) |
| 468 |
executing the code as my 3Ghz D920 processor. |
| 469 |
|
| 470 |
Well, it was expected not to be easy so maybe instead move to a |
| 471 |
different track: let's move back to the code from attempt2 and do some |
| 472 |
loop unrolling. This will eliminate a few if statements. I'll try |
| 473 |
different amounts of unrolling to see what works best. |
| 474 |
|
| 475 |
|
| 476 |
Attempt 4 |
| 477 |
========= |
| 478 |
|
| 479 |
Unrolled the loop 1, 2, 3 and 4 times. |
| 480 |
For 4 the code starts with:: |
| 481 |
|
| 482 |
for (i = 0; i < 4; i++) |
| 483 |
{ |
| 484 |
cur = *bp++; |
| 485 |
par ^= cur; |
| 486 |
rp4 ^= cur; |
| 487 |
rp6 ^= cur; |
| 488 |
rp8 ^= cur; |
| 489 |
rp10 ^= cur; |
| 490 |
if (i & 0x1) rp13 ^= cur; else rp12 ^= cur; |
| 491 |
if (i & 0x2) rp15 ^= cur; else rp14 ^= cur; |
| 492 |
cur = *bp++; |
| 493 |
par ^= cur; |
| 494 |
rp5 ^= cur; |
| 495 |
rp6 ^= cur; |
| 496 |
... |
| 497 |
|
| 498 |
|
| 499 |
Analysis 4 |
| 500 |
========== |
| 501 |
|
| 502 |
Unrolling once gains about 15% |
| 503 |
|
| 504 |
Unrolling twice keeps the gain at about 15% |
| 505 |
|
| 506 |
Unrolling three times gives a gain of 30% compared to attempt 2. |
| 507 |
|
| 508 |
Unrolling four times gives a marginal improvement compared to unrolling |
| 509 |
three times. |
| 510 |
|
| 511 |
I decided to proceed with a four time unrolled loop anyway. It was my gut |
| 512 |
feeling that in the next steps I would obtain additional gain from it. |
| 513 |
|
| 514 |
The next step was triggered by the fact that par contains the xor of all |
| 515 |
bytes and rp4 and rp5 each contain the xor of half of the bytes. |
| 516 |
So in effect par = rp4 ^ rp5. But as xor is commutative we can also say |
| 517 |
that rp5 = par ^ rp4. So no need to keep both rp4 and rp5 around. We can |
| 518 |
eliminate rp5 (or rp4, but I already foresaw another optimisation). |
| 519 |
The same holds for rp6/7, rp8/9, rp10/11 rp12/13 and rp14/15. |
| 520 |
|
| 521 |
|
| 522 |
Attempt 5 |
| 523 |
========= |
| 524 |
|
| 525 |
Effectively so all odd digit rp assignments in the loop were removed. |
| 526 |
This included the else clause of the if statements. |
| 527 |
Of course after the loop we need to correct things by adding code like:: |
| 528 |
|
| 529 |
rp5 = par ^ rp4; |
| 530 |
|
| 531 |
Also the initial assignments (rp5 = 0; etc) could be removed. |
| 532 |
Along the line I also removed the initialisation of rp0/1/2/3. |
| 533 |
|
| 534 |
|
| 535 |
Analysis 5 |
| 536 |
========== |
| 537 |
|
| 538 |
Measurements showed this was a good move. The run-time roughly halved |
| 539 |
compared with attempt 4 with 4 times unrolled, and we only require 1/3rd |
| 540 |
of the processor time compared to the current code in the linux kernel. |
| 541 |
|
| 542 |
However, still I thought there was more. I didn't like all the if |
| 543 |
statements. Why not keep a running parity and only keep the last if |
| 544 |
statement. Time for yet another version! |
| 545 |
|
| 546 |
|
| 547 |
Attempt 6 |
| 548 |
========= |
| 549 |
|
| 550 |
THe code within the for loop was changed to:: |
| 551 |
|
| 552 |
for (i = 0; i < 4; i++) |
| 553 |
{ |
| 554 |
cur = *bp++; tmppar = cur; rp4 ^= cur; |
| 555 |
cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; |
| 556 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 557 |
cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; |
| 558 |
|
| 559 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; |
| 560 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; |
| 561 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 562 |
cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; |
| 563 |
|
| 564 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur; |
| 565 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; rp8 ^= cur; |
| 566 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp8 ^= cur; |
| 567 |
cur = *bp++; tmppar ^= cur; rp8 ^= cur; |
| 568 |
|
| 569 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; |
| 570 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; |
| 571 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 572 |
cur = *bp++; tmppar ^= cur; |
| 573 |
|
| 574 |
par ^= tmppar; |
| 575 |
if ((i & 0x1) == 0) rp12 ^= tmppar; |
| 576 |
if ((i & 0x2) == 0) rp14 ^= tmppar; |
| 577 |
} |
| 578 |
|
| 579 |
As you can see tmppar is used to accumulate the parity within a for |
| 580 |
iteration. In the last 3 statements is added to par and, if needed, |
| 581 |
to rp12 and rp14. |
| 582 |
|
| 583 |
While making the changes I also found that I could exploit that tmppar |
| 584 |
contains the running parity for this iteration. So instead of having: |
| 585 |
rp4 ^= cur; rp6 ^= cur; |
| 586 |
I removed the rp6 ^= cur; statement and did rp6 ^= tmppar; on next |
| 587 |
statement. A similar change was done for rp8 and rp10 |
| 588 |
|
| 589 |
|
| 590 |
Analysis 6 |
| 591 |
========== |
| 592 |
|
| 593 |
Measuring this code again showed big gain. When executing the original |
| 594 |
linux code 1 million times, this took about 1 second on my system. |
| 595 |
(using time to measure the performance). After this iteration I was back |
| 596 |
to 0.075 sec. Actually I had to decide to start measuring over 10 |
| 597 |
million iterations in order not to lose too much accuracy. This one |
| 598 |
definitely seemed to be the jackpot! |
| 599 |
|
| 600 |
There is a little bit more room for improvement though. There are three |
| 601 |
places with statements:: |
| 602 |
|
| 603 |
rp4 ^= cur; rp6 ^= cur; |
| 604 |
|
| 605 |
It seems more efficient to also maintain a variable rp4_6 in the while |
| 606 |
loop; This eliminates 3 statements per loop. Of course after the loop we |
| 607 |
need to correct by adding:: |
| 608 |
|
| 609 |
rp4 ^= rp4_6; |
| 610 |
rp6 ^= rp4_6 |
| 611 |
|
| 612 |
Furthermore there are 4 sequential assignments to rp8. This can be |
| 613 |
encoded slightly more efficiently by saving tmppar before those 4 lines |
| 614 |
and later do rp8 = rp8 ^ tmppar ^ notrp8; |
| 615 |
(where notrp8 is the value of rp8 before those 4 lines). |
| 616 |
Again a use of the commutative property of xor. |
| 617 |
Time for a new test! |
| 618 |
|
| 619 |
|
| 620 |
Attempt 7 |
| 621 |
========= |
| 622 |
|
| 623 |
The new code now looks like:: |
| 624 |
|
| 625 |
for (i = 0; i < 4; i++) |
| 626 |
{ |
| 627 |
cur = *bp++; tmppar = cur; rp4 ^= cur; |
| 628 |
cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; |
| 629 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 630 |
cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; |
| 631 |
|
| 632 |
cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; |
| 633 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; |
| 634 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 635 |
cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; |
| 636 |
|
| 637 |
notrp8 = tmppar; |
| 638 |
cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; |
| 639 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; |
| 640 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 641 |
cur = *bp++; tmppar ^= cur; |
| 642 |
rp8 = rp8 ^ tmppar ^ notrp8; |
| 643 |
|
| 644 |
cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; |
| 645 |
cur = *bp++; tmppar ^= cur; rp6 ^= cur; |
| 646 |
cur = *bp++; tmppar ^= cur; rp4 ^= cur; |
| 647 |
cur = *bp++; tmppar ^= cur; |
| 648 |
|
| 649 |
par ^= tmppar; |
| 650 |
if ((i & 0x1) == 0) rp12 ^= tmppar; |
| 651 |
if ((i & 0x2) == 0) rp14 ^= tmppar; |
| 652 |
} |
| 653 |
rp4 ^= rp4_6; |
| 654 |
rp6 ^= rp4_6; |
| 655 |
|
| 656 |
|
| 657 |
Not a big change, but every penny counts :-) |
| 658 |
|
| 659 |
|
| 660 |
Analysis 7 |
| 661 |
========== |
| 662 |
|
| 663 |
Actually this made things worse. Not very much, but I don't want to move |
| 664 |
into the wrong direction. Maybe something to investigate later. Could |
| 665 |
have to do with caching again. |
| 666 |
|
| 667 |
Guess that is what there is to win within the loop. Maybe unrolling one |
| 668 |
more time will help. I'll keep the optimisations from 7 for now. |
| 669 |
|
| 670 |
|
| 671 |
Attempt 8 |
| 672 |
========= |
| 673 |
|
| 674 |
Unrolled the loop one more time. |
| 675 |
|
| 676 |
|
| 677 |
Analysis 8 |
| 678 |
========== |
| 679 |
|
| 680 |
This makes things worse. Let's stick with attempt 6 and continue from there. |
| 681 |
Although it seems that the code within the loop cannot be optimised |
| 682 |
further there is still room to optimize the generation of the ecc codes. |
| 683 |
We can simply calculate the total parity. If this is 0 then rp4 = rp5 |
| 684 |
etc. If the parity is 1, then rp4 = !rp5; |
| 685 |
|
| 686 |
But if rp4 = rp5 we do not need rp5 etc. We can just write the even bits |
| 687 |
in the result byte and then do something like:: |
| 688 |
|
| 689 |
code[0] |= (code[0] << 1); |
| 690 |
|
| 691 |
Lets test this. |
| 692 |
|
| 693 |
|
| 694 |
Attempt 9 |
| 695 |
========= |
| 696 |
|
| 697 |
Changed the code but again this slightly degrades performance. Tried all |
| 698 |
kind of other things, like having dedicated parity arrays to avoid the |
| 699 |
shift after parity[rp7] << 7; No gain. |
| 700 |
Change the lookup using the parity array by using shift operators (e.g. |
| 701 |
replace parity[rp7] << 7 with:: |
| 702 |
|
| 703 |
rp7 ^= (rp7 << 4); |
| 704 |
rp7 ^= (rp7 << 2); |
| 705 |
rp7 ^= (rp7 << 1); |
| 706 |
rp7 &= 0x80; |
| 707 |
|
| 708 |
No gain. |
| 709 |
|
| 710 |
The only marginal change was inverting the parity bits, so we can remove |
| 711 |
the last three invert statements. |
| 712 |
|
| 713 |
Ah well, pity this does not deliver more. Then again 10 million |
| 714 |
iterations using the linux driver code takes between 13 and 13.5 |
| 715 |
seconds, whereas my code now takes about 0.73 seconds for those 10 |
| 716 |
million iterations. So basically I've improved the performance by a |
| 717 |
factor 18 on my system. Not that bad. Of course on different hardware |
| 718 |
you will get different results. No warranties! |
| 719 |
|
| 720 |
But of course there is no such thing as a free lunch. The codesize almost |
| 721 |
tripled (from 562 bytes to 1434 bytes). Then again, it is not that much. |
| 722 |
|
| 723 |
|
| 724 |
Correcting errors |
| 725 |
================= |
| 726 |
|
| 727 |
For correcting errors I again used the ST application note as a starter, |
| 728 |
but I also peeked at the existing code. |
| 729 |
|
| 730 |
The algorithm itself is pretty straightforward. Just xor the given and |
| 731 |
the calculated ecc. If all bytes are 0 there is no problem. If 11 bits |
| 732 |
are 1 we have one correctable bit error. If there is 1 bit 1, we have an |
| 733 |
error in the given ecc code. |
| 734 |
|
| 735 |
It proved to be fastest to do some table lookups. Performance gain |
| 736 |
introduced by this is about a factor 2 on my system when a repair had to |
| 737 |
be done, and 1% or so if no repair had to be done. |
| 738 |
|
| 739 |
Code size increased from 330 bytes to 686 bytes for this function. |
| 740 |
(gcc 4.2, -O3) |
| 741 |
|
| 742 |
|
| 743 |
Conclusion |
| 744 |
========== |
| 745 |
|
| 746 |
The gain when calculating the ecc is tremendous. Om my development hardware |
| 747 |
a speedup of a factor of 18 for ecc calculation was achieved. On a test on an |
| 748 |
embedded system with a MIPS core a factor 7 was obtained. |
| 749 |
|
| 750 |
On a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor |
| 751 |
5 (big endian mode, gcc 4.1.2, -O3) |
| 752 |
|
| 753 |
For correction not much gain could be obtained (as bitflips are rare). Then |
| 754 |
again there are also much less cycles spent there. |
| 755 |
|
| 756 |
It seems there is not much more gain possible in this, at least when |
| 757 |
programmed in C. Of course it might be possible to squeeze something more |
| 758 |
out of it with an assembler program, but due to pipeline behaviour etc |
| 759 |
this is very tricky (at least for intel hw). |
| 760 |
|
| 761 |
Author: Frans Meulenbroeks |
| 762 |
|
| 763 |
Copyright (C) 2008 Koninklijke Philips Electronics NV. |