1/*
2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
3 *
4 * Copyright (C) 2002-2010 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#include "yportenv.h"
32
33#include "yaffs_ecc.h"
34
35static 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/* Count the bits in an unsigned char or a U32 */
71
72static int yaffs_count_bits(unsigned char x)
73{
74	int r = 0;
75	while (x) {
76		if (x & 1)
77			r++;
78		x >>= 1;
79	}
80	return r;
81}
82
83static int yaffs_count_bits32(unsigned x)
84{
85	int r = 0;
86	while (x) {
87		if (x & 1)
88			r++;
89		x >>= 1;
90	}
91	return r;
92}
93
94/* Calculate the ECC for a 256-byte block of data */
95void yaffs_ecc_cacl(const unsigned char *data, unsigned char *ecc)
96{
97	unsigned int i;
98
99	unsigned char col_parity = 0;
100	unsigned char line_parity = 0;
101	unsigned char line_parity_prime = 0;
102	unsigned char t;
103	unsigned char b;
104
105	for (i = 0; i < 256; i++) {
106		b = column_parity_table[*data++];
107		col_parity ^= b;
108
109		if (b & 0x01) {		/* odd number of bits in the byte */
110			line_parity ^= i;
111			line_parity_prime ^= ~i;
112		}
113	}
114
115	ecc[2] = (~col_parity) | 0x03;
116
117	t = 0;
118	if (line_parity & 0x80)
119		t |= 0x80;
120	if (line_parity_prime & 0x80)
121		t |= 0x40;
122	if (line_parity & 0x40)
123		t |= 0x20;
124	if (line_parity_prime & 0x40)
125		t |= 0x10;
126	if (line_parity & 0x20)
127		t |= 0x08;
128	if (line_parity_prime & 0x20)
129		t |= 0x04;
130	if (line_parity & 0x10)
131		t |= 0x02;
132	if (line_parity_prime & 0x10)
133		t |= 0x01;
134	ecc[1] = ~t;
135
136	t = 0;
137	if (line_parity & 0x08)
138		t |= 0x80;
139	if (line_parity_prime & 0x08)
140		t |= 0x40;
141	if (line_parity & 0x04)
142		t |= 0x20;
143	if (line_parity_prime & 0x04)
144		t |= 0x10;
145	if (line_parity & 0x02)
146		t |= 0x08;
147	if (line_parity_prime & 0x02)
148		t |= 0x04;
149	if (line_parity & 0x01)
150		t |= 0x02;
151	if (line_parity_prime & 0x01)
152		t |= 0x01;
153	ecc[0] = ~t;
154
155#ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
156	/* Swap the bytes into the wrong order */
157	t = ecc[0];
158	ecc[0] = ecc[1];
159	ecc[1] = t;
160#endif
161}
162
163
164/* Correct the ECC on a 256 byte block of data */
165
166int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc,
167		     const unsigned char *test_ecc)
168{
169	unsigned char d0, d1, d2;	/* deltas */
170
171	d0 = read_ecc[0] ^ test_ecc[0];
172	d1 = read_ecc[1] ^ test_ecc[1];
173	d2 = read_ecc[2] ^ test_ecc[2];
174
175	if ((d0 | d1 | d2) == 0)
176		return 0; /* no error */
177
178	if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
179	    ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
180	    ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
181		/* Single bit (recoverable) error in data */
182
183		unsigned byte;
184		unsigned bit;
185
186#ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
187		/* swap the bytes to correct for the wrong order */
188		unsigned char t;
189
190		t = d0;
191		d0 = d1;
192		d1 = t;
193#endif
194
195		bit = byte = 0;
196
197		if (d1 & 0x80)
198			byte |= 0x80;
199		if (d1 & 0x20)
200			byte |= 0x40;
201		if (d1 & 0x08)
202			byte |= 0x20;
203		if (d1 & 0x02)
204			byte |= 0x10;
205		if (d0 & 0x80)
206			byte |= 0x08;
207		if (d0 & 0x20)
208			byte |= 0x04;
209		if (d0 & 0x08)
210			byte |= 0x02;
211		if (d0 & 0x02)
212			byte |= 0x01;
213
214		if (d2 & 0x80)
215			bit |= 0x04;
216		if (d2 & 0x20)
217			bit |= 0x02;
218		if (d2 & 0x08)
219			bit |= 0x01;
220
221		data[byte] ^= (1 << bit);
222
223		return 1; /* Corrected the error */
224	}
225
226	if ((yaffs_count_bits(d0) +
227	     yaffs_count_bits(d1) +
228	     yaffs_count_bits(d2)) ==  1) {
229		/* Reccoverable error in ecc */
230
231		read_ecc[0] = test_ecc[0];
232		read_ecc[1] = test_ecc[1];
233		read_ecc[2] = test_ecc[2];
234
235		return 1; /* Corrected the error */
236	}
237
238	/* Unrecoverable error */
239
240	return -1;
241
242}
243
244
245/*
246 * ECCxxxOther does ECC calcs on arbitrary n bytes of data
247 */
248void yaffs_ecc_calc_other(const unsigned char *data, unsigned n_bytes,
249				yaffs_ECCOther *eccOther)
250{
251	unsigned int i;
252
253	unsigned char col_parity = 0;
254	unsigned line_parity = 0;
255	unsigned line_parity_prime = 0;
256	unsigned char b;
257
258	for (i = 0; i < n_bytes; i++) {
259		b = column_parity_table[*data++];
260		col_parity ^= b;
261
262		if (b & 0x01)	 {
263			/* odd number of bits in the byte */
264			line_parity ^= i;
265			line_parity_prime ^= ~i;
266		}
267
268	}
269
270	eccOther->colParity = (col_parity >> 2) & 0x3f;
271	eccOther->lineParity = line_parity;
272	eccOther->lineParityPrime = line_parity_prime;
273}
274
275int yaffs_ecc_correct_other(unsigned char *data, unsigned n_bytes,
276			yaffs_ECCOther *read_ecc,
277			const yaffs_ECCOther *test_ecc)
278{
279	unsigned char cDelta;	/* column parity delta */
280	unsigned lDelta;	/* line parity delta */
281	unsigned lDeltaPrime;	/* line parity delta */
282	unsigned bit;
283
284	cDelta = read_ecc->colParity ^ test_ecc->colParity;
285	lDelta = read_ecc->lineParity ^ test_ecc->lineParity;
286	lDeltaPrime = read_ecc->lineParityPrime ^ test_ecc->lineParityPrime;
287
288	if ((cDelta | lDelta | lDeltaPrime) == 0)
289		return 0; /* no error */
290
291	if (lDelta == ~lDeltaPrime &&
292	    (((cDelta ^ (cDelta >> 1)) & 0x15) == 0x15)) {
293		/* Single bit (recoverable) error in data */
294
295		bit = 0;
296
297		if (cDelta & 0x20)
298			bit |= 0x04;
299		if (cDelta & 0x08)
300			bit |= 0x02;
301		if (cDelta & 0x02)
302			bit |= 0x01;
303
304		if (lDelta >= n_bytes)
305			return -1;
306
307		data[lDelta] ^= (1 << bit);
308
309		return 1; /* corrected */
310	}
311
312	if ((yaffs_count_bits32(lDelta) + yaffs_count_bits32(lDeltaPrime) +
313			yaffs_count_bits(cDelta)) == 1) {
314		/* Reccoverable error in ecc */
315
316		*read_ecc = *test_ecc;
317		return 1; /* corrected */
318	}
319
320	/* Unrecoverable error */
321
322	return -1;
323}
324