]> git.sur5r.net Git - u-boot/blob - fs/yaffs2/yaffs_ecc.c
cmd_bootm.c: Correct BOOTM_ERR_OVERLAP handling
[u-boot] / fs / yaffs2 / yaffs_ecc.c
1 /*
2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3  *
4  * Copyright (C) 2002-2011 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
20  * such ECC blocks are used on a 512-byte NAND page.
21  *
22  */
23
24 #include "yportenv.h"
25
26 #include "yaffs_ecc.h"
27
28 /* Table generated by gen-ecc.c
29  * Using a table means we do not have to calculate p1..p4 and p1'..p4'
30  * for each byte of data. These are instead provided in a table in bits7..2.
31  * Bit 0 of each entry indicates whether the entry has an odd or even parity,
32  * and therefore this bytes influence on the line parity.
33  */
34
35 static const unsigned char column_parity_table[] = {
36         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
37         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
38         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
39         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
40         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
41         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
42         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
43         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
44         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
45         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
46         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
47         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
48         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
49         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
50         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
51         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
52         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
53         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
54         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
55         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
56         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
57         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
58         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
59         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
60         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
61         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
62         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
63         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
64         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
65         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
66         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
67         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
68 };
69
70
71 /* Calculate the ECC for a 256-byte block of data */
72 void yaffs_ecc_calc(const unsigned char *data, unsigned char *ecc)
73 {
74         unsigned int i;
75         unsigned char col_parity = 0;
76         unsigned char line_parity = 0;
77         unsigned char line_parity_prime = 0;
78         unsigned char t;
79         unsigned char b;
80
81         for (i = 0; i < 256; i++) {
82                 b = column_parity_table[*data++];
83                 col_parity ^= b;
84
85                 if (b & 0x01) { /* odd number of bits in the byte */
86                         line_parity ^= i;
87                         line_parity_prime ^= ~i;
88                 }
89         }
90
91         ecc[2] = (~col_parity) | 0x03;
92
93         t = 0;
94         if (line_parity & 0x80)
95                 t |= 0x80;
96         if (line_parity_prime & 0x80)
97                 t |= 0x40;
98         if (line_parity & 0x40)
99                 t |= 0x20;
100         if (line_parity_prime & 0x40)
101                 t |= 0x10;
102         if (line_parity & 0x20)
103                 t |= 0x08;
104         if (line_parity_prime & 0x20)
105                 t |= 0x04;
106         if (line_parity & 0x10)
107                 t |= 0x02;
108         if (line_parity_prime & 0x10)
109                 t |= 0x01;
110         ecc[1] = ~t;
111
112         t = 0;
113         if (line_parity & 0x08)
114                 t |= 0x80;
115         if (line_parity_prime & 0x08)
116                 t |= 0x40;
117         if (line_parity & 0x04)
118                 t |= 0x20;
119         if (line_parity_prime & 0x04)
120                 t |= 0x10;
121         if (line_parity & 0x02)
122                 t |= 0x08;
123         if (line_parity_prime & 0x02)
124                 t |= 0x04;
125         if (line_parity & 0x01)
126                 t |= 0x02;
127         if (line_parity_prime & 0x01)
128                 t |= 0x01;
129         ecc[0] = ~t;
130
131 }
132
133 /* Correct the ECC on a 256 byte block of data */
134
135 int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc,
136                       const unsigned char *test_ecc)
137 {
138         unsigned char d0, d1, d2;       /* deltas */
139
140         d0 = read_ecc[0] ^ test_ecc[0];
141         d1 = read_ecc[1] ^ test_ecc[1];
142         d2 = read_ecc[2] ^ test_ecc[2];
143
144         if ((d0 | d1 | d2) == 0)
145                 return 0;       /* no error */
146
147         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
148             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
149             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
150                 /* Single bit (recoverable) error in data */
151
152                 unsigned byte;
153                 unsigned bit;
154
155                 bit = byte = 0;
156
157                 if (d1 & 0x80)
158                         byte |= 0x80;
159                 if (d1 & 0x20)
160                         byte |= 0x40;
161                 if (d1 & 0x08)
162                         byte |= 0x20;
163                 if (d1 & 0x02)
164                         byte |= 0x10;
165                 if (d0 & 0x80)
166                         byte |= 0x08;
167                 if (d0 & 0x20)
168                         byte |= 0x04;
169                 if (d0 & 0x08)
170                         byte |= 0x02;
171                 if (d0 & 0x02)
172                         byte |= 0x01;
173
174                 if (d2 & 0x80)
175                         bit |= 0x04;
176                 if (d2 & 0x20)
177                         bit |= 0x02;
178                 if (d2 & 0x08)
179                         bit |= 0x01;
180
181                 data[byte] ^= (1 << bit);
182
183                 return 1;       /* Corrected the error */
184         }
185
186         if ((hweight8(d0) + hweight8(d1) + hweight8(d2)) == 1) {
187                 /* Reccoverable error in ecc */
188
189                 read_ecc[0] = test_ecc[0];
190                 read_ecc[1] = test_ecc[1];
191                 read_ecc[2] = test_ecc[2];
192
193                 return 1;       /* Corrected the error */
194         }
195
196         /* Unrecoverable error */
197
198         return -1;
199
200 }
201
202 /*
203  * ECCxxxOther does ECC calcs on arbitrary n bytes of data
204  */
205 void yaffs_ecc_calc_other(const unsigned char *data, unsigned n_bytes,
206                           struct yaffs_ecc_other *ecc_other)
207 {
208         unsigned int i;
209         unsigned char col_parity = 0;
210         unsigned line_parity = 0;
211         unsigned line_parity_prime = 0;
212         unsigned char b;
213
214         for (i = 0; i < n_bytes; i++) {
215                 b = column_parity_table[*data++];
216                 col_parity ^= b;
217
218                 if (b & 0x01) {
219                         /* odd number of bits in the byte */
220                         line_parity ^= i;
221                         line_parity_prime ^= ~i;
222                 }
223
224         }
225
226         ecc_other->col_parity = (col_parity >> 2) & 0x3f;
227         ecc_other->line_parity = line_parity;
228         ecc_other->line_parity_prime = line_parity_prime;
229 }
230
231 int yaffs_ecc_correct_other(unsigned char *data, unsigned n_bytes,
232                             struct yaffs_ecc_other *read_ecc,
233                             const struct yaffs_ecc_other *test_ecc)
234 {
235         unsigned char delta_col;        /* column parity delta */
236         unsigned delta_line;    /* line parity delta */
237         unsigned delta_line_prime;      /* line parity delta */
238         unsigned bit;
239
240         delta_col = read_ecc->col_parity ^ test_ecc->col_parity;
241         delta_line = read_ecc->line_parity ^ test_ecc->line_parity;
242         delta_line_prime =
243             read_ecc->line_parity_prime ^ test_ecc->line_parity_prime;
244
245         if ((delta_col | delta_line | delta_line_prime) == 0)
246                 return 0;       /* no error */
247
248         if (delta_line == ~delta_line_prime &&
249             (((delta_col ^ (delta_col >> 1)) & 0x15) == 0x15)) {
250                 /* Single bit (recoverable) error in data */
251
252                 bit = 0;
253
254                 if (delta_col & 0x20)
255                         bit |= 0x04;
256                 if (delta_col & 0x08)
257                         bit |= 0x02;
258                 if (delta_col & 0x02)
259                         bit |= 0x01;
260
261                 if (delta_line >= n_bytes)
262                         return -1;
263
264                 data[delta_line] ^= (1 << bit);
265
266                 return 1;       /* corrected */
267         }
268
269         if ((hweight32(delta_line) +
270              hweight32(delta_line_prime) +
271              hweight8(delta_col)) == 1) {
272                 /* Reccoverable error in ecc */
273
274                 *read_ecc = *test_ecc;
275                 return 1;       /* corrected */
276         }
277
278         /* Unrecoverable error */
279
280         return -1;
281 }