xref: /openbmc/u-boot/fs/yaffs2/yaffs_ecc.c (revision 753ac610)
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 */
yaffs_ecc_calc(const unsigned char * data,unsigned char * ecc)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 
yaffs_ecc_correct(unsigned char * data,unsigned char * read_ecc,const unsigned char * test_ecc)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  */
yaffs_ecc_calc_other(const unsigned char * data,unsigned n_bytes,struct yaffs_ecc_other * ecc_other)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 
yaffs_ecc_correct_other(unsigned char * data,unsigned n_bytes,struct yaffs_ecc_other * read_ecc,const struct yaffs_ecc_other * test_ecc)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 }
282