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.8 2002/09/16 09:19:53 dwmw2 Exp $
   8  *
   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.
  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
 211 MODULE_LICENSE("GPL");
 212 MODULE_AUTHOR("Steven J. Hill <sjhill@cotw.com>");
 213 MODULE_DESCRIPTION("Generic NAND ECC support");