Consolidate with Android fixes
[yaffs2.git] / yaffs_ecc.c
1 /*
2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3  *
4  * Copyright (C) 2002-2007 Aleph One Ltd.
5  *   for Toby Churchill Ltd and Brightstar Engineering
6  *
7  * Created by Charles Manning <charles@aleph1.co.uk>
8  *
9  * This program is free software; you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License version 2 as
11  * published by the Free Software Foundation.
12  */
13
14 /*
15  * This code implements the ECC algorithm used in SmartMedia.
16  *
17  * The ECC comprises 22 bits of parity information and is stuffed into 3 bytes.
18  * The two unused bit are set to 1.
19  * The ECC can correct single bit errors in a 256-byte page of data. Thus, two such ECC
20  * blocks are used on a 512-byte NAND page.
21  *
22  */
23
24 /* Table generated by gen-ecc.c
25  * Using a table means we do not have to calculate p1..p4 and p1'..p4'
26  * for each byte of data. These are instead provided in a table in bits7..2.
27  * Bit 0 of each entry indicates whether the entry has an odd or even parity, and therefore
28  * this bytes influence on the line parity.
29  */
30
31 const char *yaffs_ecc_c_version =
32     "$Id: yaffs_ecc.c,v 1.10 2007-12-13 15:35:17 wookey Exp $";
33
34 #include "yportenv.h"
35
36 #include "yaffs_ecc.h"
37
38 static const unsigned char column_parity_table[] = {
39         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
40         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
41         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
42         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
43         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
44         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
45         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
46         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
47         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
48         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
49         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
50         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
51         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
52         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
53         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
54         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
55         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
56         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
57         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
58         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
59         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
60         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
61         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
62         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
63         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
64         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
65         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
66         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
67         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
68         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
69         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
70         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
71 };
72
73 /* Count the bits in an unsigned char or a U32 */
74
75 static int yaffs_CountBits(unsigned char x)
76 {
77         int r = 0;
78         while (x) {
79                 if (x & 1)
80                         r++;
81                 x >>= 1;
82         }
83         return r;
84 }
85
86 static int yaffs_CountBits32(unsigned x)
87 {
88         int r = 0;
89         while (x) {
90                 if (x & 1)
91                         r++;
92                 x >>= 1;
93         }
94         return r;
95 }
96
97 /* Calculate the ECC for a 256-byte block of data */
98 void yaffs_ECCCalculate(const unsigned char *data, unsigned char *ecc)
99 {
100         unsigned int i;
101
102         unsigned char col_parity = 0;
103         unsigned char line_parity = 0;
104         unsigned char line_parity_prime = 0;
105         unsigned char t;
106         unsigned char b;
107
108         for (i = 0; i < 256; i++) {
109                 b = column_parity_table[*data++];
110                 col_parity ^= b;
111
112                 if (b & 0x01)   // odd number of bits in the byte
113                 {
114                         line_parity ^= i;
115                         line_parity_prime ^= ~i;
116                 }
117
118         }
119
120         ecc[2] = (~col_parity) | 0x03;
121
122         t = 0;
123         if (line_parity & 0x80)
124                 t |= 0x80;
125         if (line_parity_prime & 0x80)
126                 t |= 0x40;
127         if (line_parity & 0x40)
128                 t |= 0x20;
129         if (line_parity_prime & 0x40)
130                 t |= 0x10;
131         if (line_parity & 0x20)
132                 t |= 0x08;
133         if (line_parity_prime & 0x20)
134                 t |= 0x04;
135         if (line_parity & 0x10)
136                 t |= 0x02;
137         if (line_parity_prime & 0x10)
138                 t |= 0x01;
139         ecc[1] = ~t;
140
141         t = 0;
142         if (line_parity & 0x08)
143                 t |= 0x80;
144         if (line_parity_prime & 0x08)
145                 t |= 0x40;
146         if (line_parity & 0x04)
147                 t |= 0x20;
148         if (line_parity_prime & 0x04)
149                 t |= 0x10;
150         if (line_parity & 0x02)
151                 t |= 0x08;
152         if (line_parity_prime & 0x02)
153                 t |= 0x04;
154         if (line_parity & 0x01)
155                 t |= 0x02;
156         if (line_parity_prime & 0x01)
157                 t |= 0x01;
158         ecc[0] = ~t;
159
160 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
161         // Swap the bytes into the wrong order
162         t = ecc[0];
163         ecc[0] = ecc[1];
164         ecc[1] = t;
165 #endif
166 }
167
168
169 /* Correct the ECC on a 256 byte block of data */
170
171 int yaffs_ECCCorrect(unsigned char *data, unsigned char *read_ecc,
172                      const unsigned char *test_ecc)
173 {
174         unsigned char d0, d1, d2;       /* deltas */
175
176         d0 = read_ecc[0] ^ test_ecc[0];
177         d1 = read_ecc[1] ^ test_ecc[1];
178         d2 = read_ecc[2] ^ test_ecc[2];
179
180         if ((d0 | d1 | d2) == 0)
181                 return 0; /* no error */
182
183         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
184             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
185             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
186                 /* Single bit (recoverable) error in data */
187
188                 unsigned byte;
189                 unsigned bit;
190
191 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
192                 // swap the bytes to correct for the wrong order
193                 unsigned char t;
194
195                 t = d0;
196                 d0 = d1;
197                 d1 = t;
198 #endif
199
200                 bit = byte = 0;
201
202                 if (d1 & 0x80)
203                         byte |= 0x80;
204                 if (d1 & 0x20)
205                         byte |= 0x40;
206                 if (d1 & 0x08)
207                         byte |= 0x20;
208                 if (d1 & 0x02)
209                         byte |= 0x10;
210                 if (d0 & 0x80)
211                         byte |= 0x08;
212                 if (d0 & 0x20)
213                         byte |= 0x04;
214                 if (d0 & 0x08)
215                         byte |= 0x02;
216                 if (d0 & 0x02)
217                         byte |= 0x01;
218
219                 if (d2 & 0x80)
220                         bit |= 0x04;
221                 if (d2 & 0x20)
222                         bit |= 0x02;
223                 if (d2 & 0x08)
224                         bit |= 0x01;
225
226                 data[byte] ^= (1 << bit);
227
228                 return 1; /* Corrected the error */
229         }
230
231         if ((yaffs_CountBits(d0) +
232              yaffs_CountBits(d1) +
233              yaffs_CountBits(d2)) ==  1) {
234                 /* Reccoverable error in ecc */
235
236                 read_ecc[0] = test_ecc[0];
237                 read_ecc[1] = test_ecc[1];
238                 read_ecc[2] = test_ecc[2];
239
240                 return 1; /* Corrected the error */
241         }
242
243         /* Unrecoverable error */
244
245         return -1;
246
247 }
248
249
250 /*
251  * ECCxxxOther does ECC calcs on arbitrary n bytes of data
252  */
253 void yaffs_ECCCalculateOther(const unsigned char *data, unsigned nBytes,
254                              yaffs_ECCOther * eccOther)
255 {
256         unsigned int i;
257
258         unsigned char col_parity = 0;
259         unsigned line_parity = 0;
260         unsigned line_parity_prime = 0;
261         unsigned char b;
262
263         for (i = 0; i < nBytes; i++) {
264                 b = column_parity_table[*data++];
265                 col_parity ^= b;
266
267                 if (b & 0x01)    {
268                         /* odd number of bits in the byte */
269                         line_parity ^= i;
270                         line_parity_prime ^= ~i;
271                 }
272
273         }
274
275         eccOther->colParity = (col_parity >> 2) & 0x3f;
276         eccOther->lineParity = line_parity;
277         eccOther->lineParityPrime = line_parity_prime;
278 }
279
280 int yaffs_ECCCorrectOther(unsigned char *data, unsigned nBytes,
281                           yaffs_ECCOther * read_ecc,
282                           const yaffs_ECCOther * test_ecc)
283 {
284         unsigned char cDelta;   /* column parity delta */
285         unsigned lDelta;        /* line parity delta */
286         unsigned lDeltaPrime;   /* line parity delta */
287         unsigned bit;
288
289         cDelta = read_ecc->colParity ^ test_ecc->colParity;
290         lDelta = read_ecc->lineParity ^ test_ecc->lineParity;
291         lDeltaPrime = read_ecc->lineParityPrime ^ test_ecc->lineParityPrime;
292
293         if ((cDelta | lDelta | lDeltaPrime) == 0)
294                 return 0; /* no error */
295
296         if (lDelta == ~lDeltaPrime &&
297             (((cDelta ^ (cDelta >> 1)) & 0x15) == 0x15))
298         {
299                 /* Single bit (recoverable) error in data */
300
301                 bit = 0;
302
303                 if (cDelta & 0x20)
304                         bit |= 0x04;
305                 if (cDelta & 0x08)
306                         bit |= 0x02;
307                 if (cDelta & 0x02)
308                         bit |= 0x01;
309
310                 if(lDelta >= nBytes)
311                         return -1;
312
313                 data[lDelta] ^= (1 << bit);
314
315                 return 1; /* corrected */
316         }
317
318         if ((yaffs_CountBits32(lDelta) + yaffs_CountBits32(lDeltaPrime) +
319              yaffs_CountBits(cDelta)) == 1) {
320                 /* Reccoverable error in ecc */
321
322                 *read_ecc = *test_ecc;
323                 return 1; /* corrected */
324         }
325
326         /* Unrecoverable error */
327
328         return -1;
329
330 }
331