File: /usr/src/linux/drivers/mtd/nand/nand_ecc.c
1 /*
2 * drivers/mtd/nand_ecc.c
3 *
4 * Copyright (C) 2000 Steven J. Hill (sjhill@cotw.com)
5 * Toshiba America Electronics Components, Inc.
6 *
7 * $Id: nand_ecc.c,v 1.6 2001/06/28 10:52:26 dwmw2 Exp $
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 * This file contains an ECC algorithm from Toshiba that detects and
14 * corrects 1 bit errors in a 256 byte block of data.
15 */
16
17 #include <linux/types.h>
18 #include <linux/kernel.h>
19 #include <linux/module.h>
20
21 /*
22 * Pre-calculated 256-way 1 byte column parity
23 */
24 static const u_char nand_ecc_precalc_table[] = {
25 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00,
26 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
27 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
28 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
29 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
30 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
31 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
32 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
33 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
34 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
35 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
36 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
37 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
38 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
39 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
40 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00
41 };
42
43
44 /*
45 * Creates non-inverted ECC code from line parity
46 */
47 static void nand_trans_result(u_char reg2, u_char reg3,
48 u_char *ecc_code)
49 {
50 u_char a, b, i, tmp1, tmp2;
51
52 /* Initialize variables */
53 a = b = 0x80;
54 tmp1 = tmp2 = 0;
55
56 /* Calculate first ECC byte */
57 for (i = 0; i < 4; i++) {
58 if (reg3 & a) /* LP15,13,11,9 --> ecc_code[0] */
59 tmp1 |= b;
60 b >>= 1;
61 if (reg2 & a) /* LP14,12,10,8 --> ecc_code[0] */
62 tmp1 |= b;
63 b >>= 1;
64 a >>= 1;
65 }
66
67 /* Calculate second ECC byte */
68 b = 0x80;
69 for (i = 0; i < 4; i++) {
70 if (reg3 & a) /* LP7,5,3,1 --> ecc_code[1] */
71 tmp2 |= b;
72 b >>= 1;
73 if (reg2 & a) /* LP6,4,2,0 --> ecc_code[1] */
74 tmp2 |= b;
75 b >>= 1;
76 a >>= 1;
77 }
78
79 /* Store two of the ECC bytes */
80 ecc_code[0] = tmp1;
81 ecc_code[1] = tmp2;
82 }
83
84 /*
85 * Calculate 3 byte ECC code for 256 byte block
86 */
87 void nand_calculate_ecc (const u_char *dat, u_char *ecc_code)
88 {
89 u_char idx, reg1, reg2, reg3;
90 int j;
91
92 /* Initialize variables */
93 reg1 = reg2 = reg3 = 0;
94 ecc_code[0] = ecc_code[1] = ecc_code[2] = 0;
95
96 /* Build up column parity */
97 for(j = 0; j < 256; j++) {
98
99 /* Get CP0 - CP5 from table */
100 idx = nand_ecc_precalc_table[dat[j]];
101 reg1 ^= (idx & 0x3f);
102
103 /* All bit XOR = 1 ? */
104 if (idx & 0x40) {
105 reg3 ^= (u_char) j;
106 reg2 ^= ~((u_char) j);
107 }
108 }
109
110 /* Create non-inverted ECC code from line parity */
111 nand_trans_result(reg2, reg3, ecc_code);
112
113 /* Calculate final ECC code */
114 ecc_code[0] = ~ecc_code[0];
115 ecc_code[1] = ~ecc_code[1];
116 ecc_code[2] = ((~reg1) << 2) | 0x03;
117 }
118
119 /*
120 * Detect and correct a 1 bit error for 256 byte block
121 */
122 int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc)
123 {
124 u_char a, b, c, d1, d2, d3, add, bit, i;
125
126 /* Do error detection */
127 d1 = calc_ecc[0] ^ read_ecc[0];
128 d2 = calc_ecc[1] ^ read_ecc[1];
129 d3 = calc_ecc[2] ^ read_ecc[2];
130
131 if ((d1 | d2 | d3) == 0) {
132 /* No errors */
133 return 0;
134 }
135 else {
136 a = (d1 ^ (d1 >> 1)) & 0x55;
137 b = (d2 ^ (d2 >> 1)) & 0x55;
138 c = (d3 ^ (d3 >> 1)) & 0x54;
139
140 /* Found and will correct single bit error in the data */
141 if ((a == 0x55) && (b == 0x55) && (c == 0x54)) {
142 c = 0x80;
143 add = 0;
144 a = 0x80;
145 for (i=0; i<4; i++) {
146 if (d1 & c)
147 add |= a;
148 c >>= 2;
149 a >>= 1;
150 }
151 c = 0x80;
152 for (i=0; i<4; i++) {
153 if (d2 & c)
154 add |= a;
155 c >>= 2;
156 a >>= 1;
157 }
158 bit = 0;
159 b = 0x04;
160 c = 0x80;
161 for (i=0; i<3; i++) {
162 if (d3 & c)
163 bit |= b;
164 c >>= 2;
165 b >>= 1;
166 }
167 b = 0x01;
168 a = dat[add];
169 a ^= (b << bit);
170 dat[add] = a;
171 return 1;
172 }
173 else {
174 i = 0;
175 while (d1) {
176 if (d1 & 0x01)
177 ++i;
178 d1 >>= 1;
179 }
180 while (d2) {
181 if (d2 & 0x01)
182 ++i;
183 d2 >>= 1;
184 }
185 while (d3) {
186 if (d3 & 0x01)
187 ++i;
188 d3 >>= 1;
189 }
190 if (i == 1) {
191 /* ECC Code Error Correction */
192 read_ecc[0] = calc_ecc[0];
193 read_ecc[1] = calc_ecc[1];
194 read_ecc[2] = calc_ecc[2];
195 return 2;
196 }
197 else {
198 /* Uncorrectable Error */
199 return -1;
200 }
201 }
202 }
203
204 /* Should never happen */
205 return -1;
206 }
207
208 EXPORT_SYMBOL(nand_calculate_ecc);
209 EXPORT_SYMBOL(nand_correct_data);
210