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