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