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