2 * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
4 * Copyright (C) 2002-2007 Aleph One Ltd.
5 * for Toby Churchill Ltd and Brightstar Engineering
7 * Created by Charles Manning <charles@aleph1.co.uk>
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.
15 * This code implements the ECC algorithm used in SmartMedia.
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.
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.
31 const char *yaffs_ecc_c_version
=
32 "$Id: yaffs_ecc.c,v 1.9 2007-02-14 01:09:06 wookey Exp $";
36 #include "yaffs_ecc.h"
38 static const unsigned char column_parity_table
[] = {
39 0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
40 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
41 0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
42 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
43 0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
44 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
45 0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
46 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
47 0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
48 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
49 0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
50 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
51 0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
52 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
53 0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
54 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
55 0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
56 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
57 0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
58 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
59 0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
60 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
61 0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
62 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
63 0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
64 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
65 0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
66 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
67 0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
68 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
69 0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
70 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
73 /* Count the bits in an unsigned char or a U32 */
75 static int yaffs_CountBits(unsigned char x
)
86 static int yaffs_CountBits32(unsigned x
)
97 /* Calculate the ECC for a 256-byte block of data */
98 void yaffs_ECCCalculate(const unsigned char *data
, unsigned char *ecc
)
102 unsigned char col_parity
= 0;
103 unsigned char line_parity
= 0;
104 unsigned char line_parity_prime
= 0;
108 for (i
= 0; i
< 256; i
++) {
109 b
= column_parity_table
[*data
++];
112 if (b
& 0x01) // odd number of bits in the byte
115 line_parity_prime
^= ~i
;
120 ecc
[2] = (~col_parity
) | 0x03;
123 if (line_parity
& 0x80)
125 if (line_parity_prime
& 0x80)
127 if (line_parity
& 0x40)
129 if (line_parity_prime
& 0x40)
131 if (line_parity
& 0x20)
133 if (line_parity_prime
& 0x20)
135 if (line_parity
& 0x10)
137 if (line_parity_prime
& 0x10)
142 if (line_parity
& 0x08)
144 if (line_parity_prime
& 0x08)
146 if (line_parity
& 0x04)
148 if (line_parity_prime
& 0x04)
150 if (line_parity
& 0x02)
152 if (line_parity_prime
& 0x02)
154 if (line_parity
& 0x01)
156 if (line_parity_prime
& 0x01)
160 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
161 // Swap the bytes into the wrong order
169 /* Correct the ECC on a 256 byte block of data */
171 int yaffs_ECCCorrect(unsigned char *data
, unsigned char *read_ecc
,
172 const unsigned char *test_ecc
)
174 unsigned char d0
, d1
, d2
; /* deltas */
176 d0
= read_ecc
[0] ^ test_ecc
[0];
177 d1
= read_ecc
[1] ^ test_ecc
[1];
178 d2
= read_ecc
[2] ^ test_ecc
[2];
180 if ((d0
| d1
| d2
) == 0)
181 return 0; /* no error */
183 if (((d0
^ (d0
>> 1)) & 0x55) == 0x55 &&
184 ((d1
^ (d1
>> 1)) & 0x55) == 0x55 &&
185 ((d2
^ (d2
>> 1)) & 0x54) == 0x54) {
186 /* Single bit (recoverable) error in data */
191 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
192 // swap the bytes to correct for the wrong order
226 data
[byte
] ^= (1 << bit
);
228 return 1; /* Corrected the error */
231 if ((yaffs_CountBits(d0
) +
232 yaffs_CountBits(d1
) +
233 yaffs_CountBits(d2
)) == 1) {
234 /* Reccoverable error in ecc */
236 read_ecc
[0] = test_ecc
[0];
237 read_ecc
[1] = test_ecc
[1];
238 read_ecc
[2] = test_ecc
[2];
240 return 1; /* Corrected the error */
243 /* Unrecoverable error */
251 * ECCxxxOther does ECC calcs on arbitrary n bytes of data
253 void yaffs_ECCCalculateOther(const unsigned char *data
, unsigned nBytes
,
254 yaffs_ECCOther
* eccOther
)
258 unsigned char col_parity
= 0;
259 unsigned line_parity
= 0;
260 unsigned line_parity_prime
= 0;
263 for (i
= 0; i
< nBytes
; i
++) {
264 b
= column_parity_table
[*data
++];
268 /* odd number of bits in the byte */
270 line_parity_prime
^= ~i
;
275 eccOther
->colParity
= (col_parity
>> 2) & 0x3f;
276 eccOther
->lineParity
= line_parity
;
277 eccOther
->lineParityPrime
= line_parity_prime
;
280 int yaffs_ECCCorrectOther(unsigned char *data
, unsigned nBytes
,
281 yaffs_ECCOther
* read_ecc
,
282 const yaffs_ECCOther
* test_ecc
)
284 unsigned char cDelta
; /* column parity delta */
285 unsigned lDelta
; /* line parity delta */
286 unsigned lDeltaPrime
; /* line parity delta */
289 cDelta
= read_ecc
->colParity
^ test_ecc
->colParity
;
290 lDelta
= read_ecc
->lineParity
^ test_ecc
->lineParity
;
291 lDeltaPrime
= read_ecc
->lineParityPrime
^ test_ecc
->lineParityPrime
;
293 if ((cDelta
| lDelta
| lDeltaPrime
) == 0)
294 return 0; /* no error */
296 if (lDelta
== ~lDeltaPrime
&&
297 (((cDelta
^ (cDelta
>> 1)) & 0x15) == 0x15))
299 /* Single bit (recoverable) error in data */
313 data
[lDelta
] ^= (1 << bit
);
315 return 1; /* corrected */
318 if ((yaffs_CountBits32(lDelta
) + yaffs_CountBits32(lDeltaPrime
) +
319 yaffs_CountBits(cDelta
)) == 1) {
320 /* Reccoverable error in ecc */
322 *read_ecc
= *test_ecc
;
323 return 1; /* corrected */
326 /* Unrecoverable error */
This page took 0.055626 seconds and 5 git commands to generate.