Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 2 | * This file contains an ECC algorithm from Toshiba that detects and |
| 3 | * corrects 1 bit errors in a 256 byte block of data. |
| 4 | * |
| 5 | * drivers/mtd/nand/nand_ecc.c |
| 6 | * |
| 7 | * Copyright (C) 2000-2004 Steven J. Hill (sjhill@realitydiluted.com) |
| 8 | * Toshiba America Electronics Components, Inc. |
| 9 | * |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 10 | * Copyright (C) 2006 Thomas Gleixner <tglx@linutronix.de> |
| 11 | * |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 12 | * $Id: nand_ecc.c,v 1.15 2005/11/07 11:14:30 gleixner Exp $ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 13 | * |
| 14 | * This file is free software; you can redistribute it and/or modify it |
| 15 | * under the terms of the GNU General Public License as published by the |
| 16 | * Free Software Foundation; either version 2 or (at your option) any |
| 17 | * later version. |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 18 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 19 | * This file is distributed in the hope that it will be useful, but WITHOUT |
| 20 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 21 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
| 22 | * for more details. |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 23 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 24 | * You should have received a copy of the GNU General Public License along |
| 25 | * with this file; if not, write to the Free Software Foundation, Inc., |
| 26 | * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 27 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 28 | * As a special exception, if other files instantiate templates or use |
| 29 | * macros or inline functions from these files, or you compile these |
| 30 | * files and link them with other works to produce a work based on these |
| 31 | * files, these files do not by themselves cause the resulting work to be |
| 32 | * covered by the GNU General Public License. However the source code for |
| 33 | * these files must still be made available in accordance with section (3) |
| 34 | * of the GNU General Public License. |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 35 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 36 | * This exception does not invalidate any other reasons why a work based on |
| 37 | * this file might be covered by the GNU General Public License. |
| 38 | */ |
| 39 | |
| 40 | #include <linux/types.h> |
| 41 | #include <linux/kernel.h> |
| 42 | #include <linux/module.h> |
| 43 | #include <linux/mtd/nand_ecc.h> |
| 44 | |
| 45 | /* |
| 46 | * Pre-calculated 256-way 1 byte column parity |
| 47 | */ |
| 48 | static const u_char nand_ecc_precalc_table[] = { |
| 49 | 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00, |
| 50 | 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, |
| 51 | 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, |
| 52 | 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, |
| 53 | 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, |
| 54 | 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, |
| 55 | 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, |
| 56 | 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, |
| 57 | 0x6a, 0x3f, 0x3c, 0x69, 0x33, 0x66, 0x65, 0x30, 0x30, 0x65, 0x66, 0x33, 0x69, 0x3c, 0x3f, 0x6a, |
| 58 | 0x0f, 0x5a, 0x59, 0x0c, 0x56, 0x03, 0x00, 0x55, 0x55, 0x00, 0x03, 0x56, 0x0c, 0x59, 0x5a, 0x0f, |
| 59 | 0x0c, 0x59, 0x5a, 0x0f, 0x55, 0x00, 0x03, 0x56, 0x56, 0x03, 0x00, 0x55, 0x0f, 0x5a, 0x59, 0x0c, |
| 60 | 0x69, 0x3c, 0x3f, 0x6a, 0x30, 0x65, 0x66, 0x33, 0x33, 0x66, 0x65, 0x30, 0x6a, 0x3f, 0x3c, 0x69, |
| 61 | 0x03, 0x56, 0x55, 0x00, 0x5a, 0x0f, 0x0c, 0x59, 0x59, 0x0c, 0x0f, 0x5a, 0x00, 0x55, 0x56, 0x03, |
| 62 | 0x66, 0x33, 0x30, 0x65, 0x3f, 0x6a, 0x69, 0x3c, 0x3c, 0x69, 0x6a, 0x3f, 0x65, 0x30, 0x33, 0x66, |
| 63 | 0x65, 0x30, 0x33, 0x66, 0x3c, 0x69, 0x6a, 0x3f, 0x3f, 0x6a, 0x69, 0x3c, 0x66, 0x33, 0x30, 0x65, |
| 64 | 0x00, 0x55, 0x56, 0x03, 0x59, 0x0c, 0x0f, 0x5a, 0x5a, 0x0f, 0x0c, 0x59, 0x03, 0x56, 0x55, 0x00 |
| 65 | }; |
| 66 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 67 | /** |
Randy Dunlap | 844d3b4 | 2006-06-28 21:48:27 -0700 | [diff] [blame] | 68 | * nand_calculate_ecc - [NAND Interface] Calculate 3-byte ECC for 256-byte block |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 69 | * @mtd: MTD block structure |
| 70 | * @dat: raw data |
| 71 | * @ecc_code: buffer for ECC |
| 72 | */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 73 | int nand_calculate_ecc(struct mtd_info *mtd, const u_char *dat, |
| 74 | u_char *ecc_code) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 75 | { |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 76 | uint8_t idx, reg1, reg2, reg3, tmp1, tmp2; |
| 77 | int i; |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 78 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 79 | /* Initialize variables */ |
| 80 | reg1 = reg2 = reg3 = 0; |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 81 | |
| 82 | /* Build up column parity */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 83 | for(i = 0; i < 256; i++) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 84 | /* Get CP0 - CP5 from table */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 85 | idx = nand_ecc_precalc_table[*dat++]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 86 | reg1 ^= (idx & 0x3f); |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 87 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 88 | /* All bit XOR = 1 ? */ |
| 89 | if (idx & 0x40) { |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 90 | reg3 ^= (uint8_t) i; |
| 91 | reg2 ^= ~((uint8_t) i); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 92 | } |
| 93 | } |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 94 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 95 | /* Create non-inverted ECC code from line parity */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 96 | tmp1 = (reg3 & 0x80) >> 0; /* B7 -> B7 */ |
| 97 | tmp1 |= (reg2 & 0x80) >> 1; /* B7 -> B6 */ |
| 98 | tmp1 |= (reg3 & 0x40) >> 1; /* B6 -> B5 */ |
| 99 | tmp1 |= (reg2 & 0x40) >> 2; /* B6 -> B4 */ |
| 100 | tmp1 |= (reg3 & 0x20) >> 2; /* B5 -> B3 */ |
| 101 | tmp1 |= (reg2 & 0x20) >> 3; /* B5 -> B2 */ |
| 102 | tmp1 |= (reg3 & 0x10) >> 3; /* B4 -> B1 */ |
| 103 | tmp1 |= (reg2 & 0x10) >> 4; /* B4 -> B0 */ |
| 104 | |
| 105 | tmp2 = (reg3 & 0x08) << 4; /* B3 -> B7 */ |
| 106 | tmp2 |= (reg2 & 0x08) << 3; /* B3 -> B6 */ |
| 107 | tmp2 |= (reg3 & 0x04) << 3; /* B2 -> B5 */ |
| 108 | tmp2 |= (reg2 & 0x04) << 2; /* B2 -> B4 */ |
| 109 | tmp2 |= (reg3 & 0x02) << 2; /* B1 -> B3 */ |
| 110 | tmp2 |= (reg2 & 0x02) << 1; /* B1 -> B2 */ |
| 111 | tmp2 |= (reg3 & 0x01) << 1; /* B0 -> B1 */ |
| 112 | tmp2 |= (reg2 & 0x01) << 0; /* B7 -> B0 */ |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 113 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 114 | /* Calculate final ECC code */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 115 | #ifdef CONFIG_NAND_ECC_SMC |
| 116 | ecc_code[0] = ~tmp2; |
| 117 | ecc_code[1] = ~tmp1; |
| 118 | #else |
| 119 | ecc_code[0] = ~tmp1; |
| 120 | ecc_code[1] = ~tmp2; |
| 121 | #endif |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 122 | ecc_code[2] = ((~reg1) << 2) | 0x03; |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 123 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 124 | return 0; |
| 125 | } |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 126 | EXPORT_SYMBOL(nand_calculate_ecc); |
| 127 | |
| 128 | static inline int countbits(uint32_t byte) |
| 129 | { |
| 130 | int res = 0; |
| 131 | |
| 132 | for (;byte; byte >>= 1) |
| 133 | res += byte & 0x01; |
| 134 | return res; |
| 135 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 136 | |
| 137 | /** |
| 138 | * nand_correct_data - [NAND Interface] Detect and correct bit error(s) |
| 139 | * @mtd: MTD block structure |
| 140 | * @dat: raw data read from the chip |
| 141 | * @read_ecc: ECC from the chip |
| 142 | * @calc_ecc: the ECC calculated from raw data |
| 143 | * |
| 144 | * Detect and correct a 1 bit error for 256 byte block |
| 145 | */ |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 146 | int nand_correct_data(struct mtd_info *mtd, u_char *dat, |
| 147 | u_char *read_ecc, u_char *calc_ecc) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 148 | { |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 149 | uint8_t s0, s1, s2; |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 150 | |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 151 | #ifdef CONFIG_NAND_ECC_SMC |
| 152 | s0 = calc_ecc[0] ^ read_ecc[0]; |
| 153 | s1 = calc_ecc[1] ^ read_ecc[1]; |
| 154 | s2 = calc_ecc[2] ^ read_ecc[2]; |
| 155 | #else |
| 156 | s1 = calc_ecc[0] ^ read_ecc[0]; |
| 157 | s0 = calc_ecc[1] ^ read_ecc[1]; |
| 158 | s2 = calc_ecc[2] ^ read_ecc[2]; |
| 159 | #endif |
| 160 | if ((s0 | s1 | s2) == 0) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 161 | return 0; |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 162 | |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 163 | /* Check for a single bit error */ |
| 164 | if( ((s0 ^ (s0 >> 1)) & 0x55) == 0x55 && |
| 165 | ((s1 ^ (s1 >> 1)) & 0x55) == 0x55 && |
| 166 | ((s2 ^ (s2 >> 1)) & 0x54) == 0x54) { |
| 167 | |
| 168 | uint32_t byteoffs, bitnum; |
| 169 | |
| 170 | byteoffs = (s1 << 0) & 0x80; |
| 171 | byteoffs |= (s1 << 1) & 0x40; |
| 172 | byteoffs |= (s1 << 2) & 0x20; |
| 173 | byteoffs |= (s1 << 3) & 0x10; |
| 174 | |
| 175 | byteoffs |= (s0 >> 4) & 0x08; |
| 176 | byteoffs |= (s0 >> 3) & 0x04; |
| 177 | byteoffs |= (s0 >> 2) & 0x02; |
| 178 | byteoffs |= (s0 >> 1) & 0x01; |
| 179 | |
| 180 | bitnum = (s2 >> 5) & 0x04; |
| 181 | bitnum |= (s2 >> 4) & 0x02; |
| 182 | bitnum |= (s2 >> 3) & 0x01; |
| 183 | |
| 184 | dat[byteoffs] ^= (1 << bitnum); |
| 185 | |
| 186 | return 1; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 187 | } |
Thomas Gleixner | 61b03bd | 2005-11-07 11:15:49 +0000 | [diff] [blame] | 188 | |
Thomas Gleixner | 819d6a3 | 2006-05-23 11:32:45 +0200 | [diff] [blame] | 189 | if(countbits(s0 | ((uint32_t)s1 << 8) | ((uint32_t)s2 <<16)) == 1) |
| 190 | return 1; |
| 191 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 192 | return -1; |
| 193 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 194 | EXPORT_SYMBOL(nand_correct_data); |
| 195 | |
| 196 | MODULE_LICENSE("GPL"); |
| 197 | MODULE_AUTHOR("Steven J. Hill <sjhill@realitydiluted.com>"); |
| 198 | MODULE_DESCRIPTION("Generic NAND ECC support"); |