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