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.1.1.1 2005/04/11 02:50:26 jack 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.
17 #include <linux/types.h>
18 #include <linux/kernel.h>
19 #include <linux/module.h>
22 * Pre-calculated 256-way 1 byte column parity
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
45 * Creates non-inverted ECC code from line parity
47 static void nand_trans_result(u_char reg2, u_char reg3,
50 u_char a, b, i, tmp1, tmp2;
52 /* Initialize variables */
56 /* Calculate first ECC byte */
57 for (i = 0; i < 4; i++) {
58 if (reg3 & a) /* LP15,13,11,9 --> ecc_code[0] */
61 if (reg2 & a) /* LP14,12,10,8 --> ecc_code[0] */
67 /* Calculate second ECC byte */
69 for (i = 0; i < 4; i++) {
70 if (reg3 & a) /* LP7,5,3,1 --> ecc_code[1] */
73 if (reg2 & a) /* LP6,4,2,0 --> ecc_code[1] */
79 /* Store two of the ECC bytes */
85 * Calculate 3 byte ECC code for 256 byte block
87 void nand_calculate_ecc (const u_char *dat, u_char *ecc_code)
89 u_char idx, reg1, reg2, reg3;
92 /* Initialize variables */
93 reg1 = reg2 = reg3 = 0;
94 ecc_code[0] = ecc_code[1] = ecc_code[2] = 0;
96 /* Build up column parity */
97 for(j = 0; j < 256; j++) {
99 /* Get CP0 - CP5 from table */
100 idx = nand_ecc_precalc_table[dat[j]];
101 reg1 ^= (idx & 0x3f);
103 /* All bit XOR = 1 ? */
106 reg2 ^= ~((u_char) j);
110 /* Create non-inverted ECC code from line parity */
111 nand_trans_result(reg2, reg3, ecc_code);
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;
120 * Detect and correct a 1 bit error for 256 byte block
122 int nand_correct_data (u_char *dat, u_char *read_ecc, u_char *calc_ecc)
124 u_char a, b, c, d1, d2, d3, add, bit, i;
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];
131 if ((d1 | d2 | d3) == 0) {
136 a = (d1 ^ (d1 >> 1)) & 0x55;
137 b = (d2 ^ (d2 >> 1)) & 0x55;
138 c = (d3 ^ (d3 >> 1)) & 0x54;
140 /* Found and will correct single bit error in the data */
141 if ((a == 0x55) && (b == 0x55) && (c == 0x54)) {
145 for (i=0; i<4; i++) {
152 for (i=0; i<4; i++) {
161 for (i=0; i<3; i++) {
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];
198 /* Uncorrectable Error */
204 /* Should never happen */
208 EXPORT_SYMBOL(nand_calculate_ecc);
209 EXPORT_SYMBOL(nand_correct_data);
211 MODULE_LICENSE("GPL");
212 MODULE_AUTHOR("Steven J. Hill <sjhill@cotw.com>");
213 MODULE_DESCRIPTION("Generic NAND ECC support");