]>
Commit | Line | Data |
---|---|---|
0e8cc8bd WJ |
1 | /* |
2 | * YAFFS: Yet Another Flash File System. A NAND-flash specific file system. | |
3 | * | |
753ac610 | 4 | * Copyright (C) 2002-2011 Aleph One Ltd. |
0e8cc8bd WJ |
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 | * | |
4b070809 | 17 | * The ECC comprises 22 bits of parity information and is stuffed into 3 bytes. |
0e8cc8bd | 18 | * The two unused bit are set to 1. |
753ac610 CM |
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. | |
0e8cc8bd WJ |
21 | * |
22 | */ | |
23 | ||
753ac610 CM |
24 | #include "yportenv.h" |
25 | ||
26 | #include "yaffs_ecc.h" | |
27 | ||
0e8cc8bd WJ |
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. | |
753ac610 CM |
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. | |
0e8cc8bd WJ |
33 | */ |
34 | ||
0e8cc8bd WJ |
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 | ||
0e8cc8bd WJ |
70 | |
71 | /* Calculate the ECC for a 256-byte block of data */ | |
753ac610 | 72 | void yaffs_ecc_calc(const unsigned char *data, unsigned char *ecc) |
0e8cc8bd WJ |
73 | { |
74 | unsigned int i; | |
0e8cc8bd WJ |
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 | ||
753ac610 | 85 | if (b & 0x01) { /* odd number of bits in the byte */ |
0e8cc8bd WJ |
86 | line_parity ^= i; |
87 | line_parity_prime ^= ~i; | |
88 | } | |
0e8cc8bd WJ |
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 | ||
0e8cc8bd WJ |
131 | } |
132 | ||
0e8cc8bd WJ |
133 | /* Correct the ECC on a 256 byte block of data */ |
134 | ||
753ac610 CM |
135 | int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc, |
136 | const unsigned char *test_ecc) | |
0e8cc8bd WJ |
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) | |
753ac610 | 145 | return 0; /* no error */ |
0e8cc8bd WJ |
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 | ||
0e8cc8bd WJ |
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 | ||
753ac610 | 183 | return 1; /* Corrected the error */ |
0e8cc8bd WJ |
184 | } |
185 | ||
753ac610 | 186 | if ((hweight8(d0) + hweight8(d1) + hweight8(d2)) == 1) { |
0e8cc8bd WJ |
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 | ||
753ac610 | 193 | return 1; /* Corrected the error */ |
0e8cc8bd | 194 | } |
4b070809 | 195 | |
0e8cc8bd WJ |
196 | /* Unrecoverable error */ |
197 | ||
198 | return -1; | |
199 | ||
200 | } | |
201 | ||
0e8cc8bd WJ |
202 | /* |
203 | * ECCxxxOther does ECC calcs on arbitrary n bytes of data | |
204 | */ | |
753ac610 CM |
205 | void yaffs_ecc_calc_other(const unsigned char *data, unsigned n_bytes, |
206 | struct yaffs_ecc_other *ecc_other) | |
0e8cc8bd WJ |
207 | { |
208 | unsigned int i; | |
0e8cc8bd WJ |
209 | unsigned char col_parity = 0; |
210 | unsigned line_parity = 0; | |
211 | unsigned line_parity_prime = 0; | |
212 | unsigned char b; | |
213 | ||
753ac610 | 214 | for (i = 0; i < n_bytes; i++) { |
0e8cc8bd WJ |
215 | b = column_parity_table[*data++]; |
216 | col_parity ^= b; | |
217 | ||
753ac610 | 218 | if (b & 0x01) { |
0e8cc8bd WJ |
219 | /* odd number of bits in the byte */ |
220 | line_parity ^= i; | |
221 | line_parity_prime ^= ~i; | |
222 | } | |
223 | ||
224 | } | |
225 | ||
753ac610 CM |
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; | |
0e8cc8bd WJ |
229 | } |
230 | ||
753ac610 CM |
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) | |
0e8cc8bd | 234 | { |
753ac610 CM |
235 | unsigned char delta_col; /* column parity delta */ |
236 | unsigned delta_line; /* line parity delta */ | |
237 | unsigned delta_line_prime; /* line parity delta */ | |
0e8cc8bd WJ |
238 | unsigned bit; |
239 | ||
753ac610 CM |
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; | |
0e8cc8bd | 244 | |
753ac610 CM |
245 | if ((delta_col | delta_line | delta_line_prime) == 0) |
246 | return 0; /* no error */ | |
0e8cc8bd | 247 | |
753ac610 CM |
248 | if (delta_line == ~delta_line_prime && |
249 | (((delta_col ^ (delta_col >> 1)) & 0x15) == 0x15)) { | |
0e8cc8bd WJ |
250 | /* Single bit (recoverable) error in data */ |
251 | ||
252 | bit = 0; | |
253 | ||
753ac610 | 254 | if (delta_col & 0x20) |
0e8cc8bd | 255 | bit |= 0x04; |
753ac610 | 256 | if (delta_col & 0x08) |
0e8cc8bd | 257 | bit |= 0x02; |
753ac610 | 258 | if (delta_col & 0x02) |
0e8cc8bd WJ |
259 | bit |= 0x01; |
260 | ||
753ac610 | 261 | if (delta_line >= n_bytes) |
0e8cc8bd | 262 | return -1; |
4b070809 | 263 | |
753ac610 | 264 | data[delta_line] ^= (1 << bit); |
0e8cc8bd | 265 | |
753ac610 | 266 | return 1; /* corrected */ |
0e8cc8bd WJ |
267 | } |
268 | ||
753ac610 CM |
269 | if ((hweight32(delta_line) + |
270 | hweight32(delta_line_prime) + | |
271 | hweight8(delta_col)) == 1) { | |
0e8cc8bd WJ |
272 | /* Reccoverable error in ecc */ |
273 | ||
274 | *read_ecc = *test_ecc; | |
753ac610 | 275 | return 1; /* corrected */ |
0e8cc8bd WJ |
276 | } |
277 | ||
278 | /* Unrecoverable error */ | |
279 | ||
280 | return -1; | |
0e8cc8bd | 281 | } |