2 * drivers/mtd/nand_ecc.c
4 * Copyright (C) 2000 Steven J. Hill (sjhill@cotw.com)
5 * Toshiba America Electronics Components, Inc.
7 * $Id: nand_ecc.c,v 1.2 2002-09-17 04:45:48 charles Exp $
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU Lesser General Public License
11 * version 2.1 as published by the Free Software Foundation.
13 * This file contains an ECC algorithm from Toshiba that detects and
14 * corrects 1 bit errors in a 256 byte block of data.
16 // Minor tweak by Charles Manning to prevent exporting symbols
17 // when compiled in with yaffs.
20 #include <linux/types.h>
21 #include <linux/kernel.h>
22 #include <linux/module.h>
28 * Pre-calculated 256-way 1 byte column parity
30 static const u_char nand_ecc_precalc_table[] = {
31 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00,
32 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
33 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
34 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
35 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
36 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
37 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
38 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
39 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a,
40 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f,
41 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c,
42 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69,
43 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03,
44 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66,
45 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65,
46 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00
51 * Creates non-inverted ECC code from line parity
53 static void nand_trans_result(u_char reg2, u_char reg3,
56 u_char a, b, i, tmp1, tmp2;
58 /* Initialize variables */
62 /* Calculate first ECC byte */
63 for (i = 0; i < 4; i++) {
64 if (reg3 & a) /* LP15,13,11,9 --> ecc_code[0] */
67 if (reg2 & a) /* LP14,12,10,8 --> ecc_code[0] */
73 /* Calculate second ECC byte */
75 for (i = 0; i < 4; i++) {
76 if (reg3 & a) /* LP7,5,3,1 --> ecc_code[1] */
79 if (reg2 & a) /* LP6,4,2,0 --> ecc_code[1] */
85 /* Store two of the ECC bytes */
91 * Calculate 3 byte ECC code for 256 byte block
93 void nand_calculate_ecc (const u_char *dat, u_char *ecc_code)
95 u_char idx, reg1, reg2, reg3;
98 /* Initialize variables */
99 reg1 = reg2 = reg3 = 0;
100 ecc_code[0] = ecc_code[1] = ecc_code[2] = 0;
102 /* Build up column parity */
103 for(j = 0; j < 256; j++) {
105 /* Get CP0 - CP5 from table */
106 idx = nand_ecc_precalc_table[dat[j]];
107 reg1 ^= (idx & 0x3f);
109 /* All bit XOR = 1 ? */
112 reg2 ^= ~((u_char) j);
116 /* Create non-inverted ECC code from line parity */
117 nand_trans_result(reg2, reg3, ecc_code);
119 /* Calculate final ECC code */
120 ecc_code[0] = ~ecc_code[0];
121 ecc_code[1] = ~ecc_code[1];
122 ecc_code[2] = ((~reg1) << 2) | 0x03;
126 * Detect and correct a 1 bit error for 256 byte block
128 int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc)
130 u_char a, b, c, d1, d2, d3, add, bit, i;
132 /* Do error detection */
133 d1 = calc_ecc[0] ^ read_ecc[0];
134 d2 = calc_ecc[1] ^ read_ecc[1];
135 d3 = calc_ecc[2] ^ read_ecc[2];
137 if ((d1 | d2 | d3) == 0) {
142 a = (d1 ^ (d1 >> 1)) & 0x55;
143 b = (d2 ^ (d2 >> 1)) & 0x55;
144 c = (d3 ^ (d3 >> 1)) & 0x54;
146 /* Found and will correct single bit error in the data */
147 if ((a == 0x55) && (b == 0x55) && (c == 0x54)) {
151 for (i=0; i<4; i++) {
158 for (i=0; i<4; i++) {
167 for (i=0; i<3; i++) {
197 /* ECC Code Error Correction */
198 read_ecc[0] = calc_ecc[0];
199 read_ecc[1] = calc_ecc[1];
200 read_ecc[2] = calc_ecc[2];
204 /* Uncorrectable Error */
210 /* Should never happen */
215 EXPORT_SYMBOL(nand_calculate_ecc);
216 EXPORT_SYMBOL(nand_correct_data);
218 MODULE_LICENSE("GPL");
219 MODULE_AUTHOR("Steven J. Hill <sjhill@cotw.com>");
220 MODULE_DESCRIPTION("Generic NAND ECC support");