xref: /nrf52832-nimble/rt-thread/components/dfs/filesystems/uffs/src/uffs/uffs_ecc.c (revision 104654410c56c573564690304ae786df310c91fc)
1 /*
2   This file is part of UFFS, the Ultra-low-cost Flash File System.
3 
4   Copyright (C) 2005-2009 Ricky Zheng <[email protected]>
5 
6   UFFS is free software; you can redistribute it and/or modify it under
7   the GNU Library General Public License as published by the Free Software
8   Foundation; either version 2 of the License, or (at your option) any
9   later version.
10 
11   UFFS is distributed in the hope that it will be useful, but WITHOUT
12   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14   or GNU Library General Public License, as applicable, for more details.
15 
16   You should have received a copy of the GNU General Public License
17   and GNU Library General Public License along with UFFS; if not, write
18   to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19   Boston, MA  02110-1301, USA.
20 
21   As a special exception, if other files instantiate templates or use
22   macros or inline functions from this file, or you compile this file
23   and link it with other works to produce a work based on this file,
24   this file does not by itself cause the resulting work to be covered
25   by the GNU General Public License. However the source code for this
26   file must still be made available in accordance with section (3) of
27   the GNU General Public License v2.
28 
29   This exception does not invalidate any other reasons why a work based
30   on this file might be covered by the GNU General Public License.
31 */
32 
33 /**
34  * \file uffs_ecc.c
35  * \brief ecc maker and correct
36  * \author Ricky Zheng, created in 12th Jun, 2005
37  */
38 #include "uffs_config.h"
39 #include "uffs/uffs_fs.h"
40 #include <string.h>
41 
42 #define PFX "ecc : "
43 
44 static const u8 bits_tbl[256] = {
45 	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
46 	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
47 	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
48 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
49 	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
50 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
51 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
52 	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
53 	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
54 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
55 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
56 	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
57 	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
58 	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
59 	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
60 	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
61 };
62 
63 static const u8 line_parity_tbl[16] = {
64 	0x00, 0x02, 0x08, 0x0a, 0x20, 0x22, 0x28, 0x2a,
65 	0x80, 0x82, 0x88, 0x8a, 0xa0, 0xa2, 0xa8, 0xaa
66 };
67 
68 static const u8 line_parity_prime_tbl[16] = {
69 	0x00, 0x01, 0x04, 0x05, 0x10, 0x11, 0x14, 0x15,
70 	0x40, 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55
71 };
72 
73 static const u8 column_parity_tbl[256] = {
74 	0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
75 	0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
76 	0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
77 	0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
78 	0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
79 	0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
80 	0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
81 	0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
82 	0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
83 	0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
84 	0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
85 	0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
86 	0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
87 	0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
88 	0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
89 	0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
90 	0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
91 	0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
92 	0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
93 	0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
94 	0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
95 	0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
96 	0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
97 	0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
98 	0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
99 	0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
100 	0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
101 	0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
102 	0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
103 	0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
104 	0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
105 	0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
106 };
107 
108 /**
109  * calculate 3 bytes ECC for 256 bytes data.
110  *
111  * \param[in] data input data
112  * \param[out] ecc output ecc
113  * \param[in] length of data in bytes
114  */
uffs_EccMakeChunk256(const void * data,void * ecc,u16 len)115 static void uffs_EccMakeChunk256(const void *data, void *ecc, u16 len)
116 {
117 	u8 *pecc = (u8 *)ecc;
118 	const u8 *p = (const u8 *)data;
119 	u8 b, col_parity = 0, line_parity = 0, line_parity_prime = 0;
120 	u16 i;
121 
122 	for (i = 0; i < len; i++) {
123 		b = column_parity_tbl[*p++];
124 		col_parity ^= b;
125 		if (b & 0x01) { // odd number of bits in the byte
126 			line_parity ^= i;
127 			line_parity_prime ^= ~i;
128 		}
129 	}
130 
131 	// ECC layout:
132 	// Byte[0]  P64   | P64'   | P32  | P32'  | P16  | P16'  | P8   | P8'
133 	// Byte[1]  P1024 | P1024' | P512 | P512' | P256 | P256' | P128 | P128'
134 	// Byte[2]  P4    | P4'    | P2   | P2'   | P1   | P1'   | 1    | 1
135 	pecc[0] = ~(line_parity_tbl[line_parity & 0xf] |
136 				line_parity_prime_tbl[line_parity_prime & 0xf]);
137 	pecc[1] = ~(line_parity_tbl[line_parity >> 4] |
138 				line_parity_prime_tbl[line_parity_prime >> 4]);
139 	pecc[2] = (~col_parity) | 0x03;
140 
141 }
142 
143 
144 /**
145  * calculate ECC. (3 bytes ECC per 256 data)
146  *
147  * \param[in] data input data
148  * \param[in] data_len length of data in byte
149  * \param[out] ecc output ecc
150  *
151  * \return length of ECC in byte. (3 bytes ECC per 256 data)
152  */
uffs_EccMake(const void * data,int data_len,void * ecc)153 int uffs_EccMake(const void *data, int data_len, void *ecc)
154 {
155 	const u8 *p_data = (const u8 *)data;
156 	u8 *p_ecc = (u8 *)ecc;
157 	int len;
158 
159 	if (data == NULL || ecc == NULL)
160 		return 0;
161 
162 	while (data_len > 0) {
163 		len = data_len > 256 ? 256 : data_len;
164 		uffs_EccMakeChunk256(p_data, p_ecc, len);
165 		data_len -= len;
166 		p_data += len;
167 		p_ecc += 3;
168 	}
169 
170 	return p_ecc - (u8 *)ecc;
171 }
172 
173 /**
174  * perform ECC error correct for 256 bytes data chunk.
175  *
176  * \param[in|out] data input data to be corrected
177  * \param[in] read_ecc 3 bytes ECC read from storage
178  * \param[in] test_ecc 3 bytes ECC calculated from data
179  * \param[in] errtop top position of error
180  *
181  * \return:  0 -- no error
182  *			-1 -- can not be corrected
183  *			>0 -- how many bits corrected
184  */
uffs_EccCorrectChunk256(void * data,void * read_ecc,const void * test_ecc,int errtop)185 static int uffs_EccCorrectChunk256(void *data, void *read_ecc,
186 								   const void *test_ecc, int errtop)
187 {
188 	u8 d0, d1, d2;		/* deltas */
189 	u8 *p = (u8 *)data;
190 	u8 *pread_ecc = (u8 *)read_ecc, *ptest_ecc = (u8 *)test_ecc;
191 
192 	d0 = pread_ecc[0] ^ ptest_ecc[0];
193 	d1 = pread_ecc[1] ^ ptest_ecc[1];
194 	d2 = pread_ecc[2] ^ ptest_ecc[2];
195 
196 	if ((d0 | d1 | d2) == 0)
197 		return 0;
198 
199 	if( ((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
200 	    ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
201 	    ((d2 ^ (d2 >> 1)) & 0x54) == 0x54)
202 	{
203 		// Single bit (recoverable) error in data
204 
205 		u8 b;
206 		u8 bit;
207 
208 		bit = b = 0;
209 
210 		if(d1 & 0x80) b |= 0x80;
211 		if(d1 & 0x20) b |= 0x40;
212 		if(d1 & 0x08) b |= 0x20;
213 		if(d1 & 0x02) b |= 0x10;
214 		if(d0 & 0x80) b |= 0x08;
215 		if(d0 & 0x20) b |= 0x04;
216 		if(d0 & 0x08) b |= 0x02;
217 		if(d0 & 0x02) b |= 0x01;
218 
219 		if(d2 & 0x80) bit |= 0x04;
220 		if(d2 & 0x20) bit |= 0x02;
221 		if(d2 & 0x08) bit |= 0x01;
222 
223 		if (b >= errtop) return -1;
224 
225 		p[b] ^= (1 << bit);
226 
227 		return 1;
228 	}
229 
230 	if ((bits_tbl[d0] + bits_tbl[d1] + bits_tbl[d2]) == 1) {
231 		// error in ecc, no action need
232 		return 1;
233 	}
234 
235 	// Unrecoverable error
236 	return -1;
237 }
238 
239 /**
240  * perform ECC error correct
241  *
242  * \param[in|out] data input data to be corrected
243  * \param[in] data_len length of data in byte
244  * \param[in] read_ecc ECC read from storage
245  * \param[in] test_ecc ECC calculated from data
246  *
247  * \return:  0 -- no error
248  *			-1 -- can not be corrected
249  *			>0 -- how many bits corrected
250  */
251 
uffs_EccCorrect(void * data,int data_len,void * read_ecc,const void * test_ecc)252 int uffs_EccCorrect(void *data, int data_len,
253 					void *read_ecc, const void *test_ecc)
254 {
255 	u8 *p_data = (u8 *)data;
256 	u8 *p_read_ecc = (u8 *)read_ecc;
257 	u8 *p_test_ecc = (u8 *)test_ecc;
258 	int total = 0, ret, len;
259 
260 	if (data == NULL || read_ecc == NULL || test_ecc == NULL)
261 		return -1;
262 
263 	while (data_len > 0) {
264 		len = (data_len > 256 ? 256 : data_len);
265 		ret = uffs_EccCorrectChunk256(p_data, p_read_ecc, p_test_ecc, len);
266 		if (ret < 0) {
267 			total = ret;
268 			break;
269 		}
270 		else
271 			total += ret;
272 
273 		p_data += len;
274 		p_read_ecc += 3;
275 		p_test_ecc += 3;
276 		data_len -= len;
277 	}
278 
279 	return total;
280 
281 }
282 
283 /**
284  * generate 12 bit ecc for 8 bytes data.
285  *	(use 0xFF padding if the data length is less then 8 bytes)
286  *
287  * \param[in] data input data
288  * \param[in] data_len length of data in byte
289  *
290  * \return 12 bits ECC data (lower 12 bits).
291  */
uffs_EccMake8(void * data,int data_len)292 u16 uffs_EccMake8(void *data, int data_len)
293 {
294 	u8 *p = (u8 *)data;
295 	u8 b, col_parity = 0, line_parity = 0, line_parity_prime = 0;
296 	u8 i;
297 	u16 ecc = 0;
298 
299 
300 	data_len = (data_len > 8 ? 8 : data_len);
301 
302 	for (i = 0; i < data_len; i++) {
303 		b = column_parity_tbl[*p++];
304 		col_parity ^= b;
305 		if (b & 0x01) { // odd number of bits in the byte
306 			line_parity ^= i;
307 			line_parity_prime ^= ~i;
308 		}
309 	}
310 
311 	// ECC layout:
312 	// row:         (1) | (1)  | P32 | P32' | P16 | P16' | P8  | P8'
313 	// column:      P4  | P4'  | P2  | P2'  | P1  | P1'  | (1) | (1)
314 	// 12-bit ecc:  P32 | P32' | P16 | P16' | P8  | P8'  | P4  | P4' | P2 | P2' | P1 | P1' |
315 	ecc = (~(
316 			line_parity_tbl[line_parity & 0xf] |
317 			line_parity_prime_tbl[line_parity_prime & 0xf]
318 			)) << 6;
319 	ecc |= (((~col_parity) >> 2) & 0x3f);
320 
321 	return ecc & 0xfff;
322 }
323 
324 /**
325  * correct 8 bytes data from 12 bits ECC
326  *
327  * \param[in|out] data input data
328  * \param[in] read_ecc ecc read from storage
329  * \param[in] test_ecc ecc calculated from data
330  * \param[in] errtop top position of error.
331  *
332  * \return:  0 -- no error
333  *			-1 -- can not be corrected
334  *			>0 -- how many bits corrected
335  */
uffs_EccCorrect8(void * data,u16 read_ecc,u16 test_ecc,int errtop)336 int uffs_EccCorrect8(void *data, u16 read_ecc, u16 test_ecc, int errtop)
337 {
338 	u8 d0, d1;			/* deltas */
339 	u8 *p = (u8 *)data;
340 
341 	read_ecc &= 0xfff;
342 	test_ecc &= 0xfff;
343 
344 	d0 = (read_ecc >> 6) ^ (test_ecc >> 6);
345 	d1 = (read_ecc & 0x3f) ^ (test_ecc & 0x3f);
346 
347 	if ((d0 | d1) == 0)
348 		return 0;
349 
350 	if( ((d0 ^ (d0 >> 1)) & 0x15) == 0x15 &&
351 	    ((d1 ^ (d1 >> 1)) & 0x15) == 0x15)
352 	{
353 		// Single bit (recoverable) error in data
354 
355 		u8 b;
356 		u8 bit;
357 
358 		bit = b = 0;
359 
360 		if(d0 & 0x20) b |= 0x04;
361 		if(d0 & 0x08) b |= 0x02;
362 		if(d0 & 0x02) b |= 0x01;
363 
364 		if(d1 & 0x20) bit |= 0x04;
365 		if(d1 & 0x08) bit |= 0x02;
366 		if(d1 & 0x02) bit |= 0x01;
367 
368 		if (b >= (u8)errtop) return -1;
369 		if (bit >= 8) return -1;
370 
371 		p[b] ^= (1 << bit);
372 
373 		return 1;
374 	}
375 
376 	if ((bits_tbl[d0] + bits_tbl[d1]) == 1) {
377 		// error in ecc, no action need
378 		return 1;
379 	}
380 
381 	// Unrecoverable error
382 	return -1;
383 }
384 
385