yaffs_ecc.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2007 Aleph One Ltd.
   5  *   for Toby Churchill Ltd and Brightstar Engineering
   6  *
   7  * Created by Charles Manning <charles@aleph1.co.uk>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License version 2 as
  11  * published by the Free Software Foundation.
  12  */
  13
  14 /*
  15  * This code implements the ECC algorithm used in SmartMedia.
  16  *
  17  * The ECC comprises 22 bits of parity information and is stuffed into 3 bytes.
  18  * The two unused bit are set to 1.
  19  * The ECC can correct single bit errors in a 256-byte page of data. Thus, two such ECC
  20  * blocks are used on a 512-byte NAND page.
  21  *
  22  */
  23
  24 /* Table generated by gen-ecc.c
  25  * Using a table means we do not have to calculate p1..p4 and p1'..p4'
  26  * for each byte of data. These are instead provided in a table in bits7..2.
  27  * Bit 0 of each entry indicates whether the entry has an odd or even parity, and therefore
  28  * this bytes influence on the line parity.
  29  */
  30
  31 const char *yaffs_ecc_c_version =
  32     "$Id: yaffs_ecc.c,v 1.10 2007-12-13 15:35:17 wookey Exp $";
  33
  34 #include "yportenv.h"
  35
  36 #include "yaffs_ecc.h"
  37
  38 static const unsigned char column_parity_table[] = {
  39         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
  40         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  41         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
  42         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  43         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
  44         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  45         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
  46         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  47         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
  48         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  49         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
  50         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  51         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
  52         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  53         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
  54         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  55         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
  56         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  57         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
  58         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  59         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
  60         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  61         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
  62         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  63         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
  64         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  65         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
  66         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  67         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
  68         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  69         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
  70         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  71 };
  72
  73 /* Count the bits in an unsigned char or a U32 */
  74
  75 static int yaffs_CountBits(unsigned char x)
  76 {
  77         int r = 0;
  78         while (x) {
  79                 if (x & 1)
  80                         r++;
  81                 x >>= 1;
  82         }
  83         return r;
  84 }
  85
  86 static int yaffs_CountBits32(unsigned x)
  87 {
  88         int r = 0;
  89         while (x) {
  90                 if (x & 1)
  91                         r++;
  92                 x >>= 1;
  93         }
  94         return r;
  95 }
  96
  97 /* Calculate the ECC for a 256-byte block of data */
  98 void yaffs_ECCCalculate(const unsigned char *data, unsigned char *ecc)
  99 {
 100         unsigned int i;
 101
 102         unsigned char col_parity = 0;
 103         unsigned char line_parity = 0;
 104         unsigned char line_parity_prime = 0;
 105         unsigned char t;
 106         unsigned char b;
 107
 108         for (i = 0; i < 256; i++) {
 109                 b = column_parity_table[*data++];
 110                 col_parity ^= b;
 111
 112                 if (b & 0x01)   // odd number of bits in the byte
 113                 {
 114                         line_parity ^= i;
 115                         line_parity_prime ^= ~i;
 116                 }
 117
 118         }
 119
 120         ecc[2] = (~col_parity) | 0x03;
 121
 122         t = 0;
 123         if (line_parity & 0x80)
 124                 t |= 0x80;
 125         if (line_parity_prime & 0x80)
 126                 t |= 0x40;
 127         if (line_parity & 0x40)
 128                 t |= 0x20;
 129         if (line_parity_prime & 0x40)
 130                 t |= 0x10;
 131         if (line_parity & 0x20)
 132                 t |= 0x08;
 133         if (line_parity_prime & 0x20)
 134                 t |= 0x04;
 135         if (line_parity & 0x10)
 136                 t |= 0x02;
 137         if (line_parity_prime & 0x10)
 138                 t |= 0x01;
 139         ecc[1] = ~t;
 140
 141         t = 0;
 142         if (line_parity & 0x08)
 143                 t |= 0x80;
 144         if (line_parity_prime & 0x08)
 145                 t |= 0x40;
 146         if (line_parity & 0x04)
 147                 t |= 0x20;
 148         if (line_parity_prime & 0x04)
 149                 t |= 0x10;
 150         if (line_parity & 0x02)
 151                 t |= 0x08;
 152         if (line_parity_prime & 0x02)
 153                 t |= 0x04;
 154         if (line_parity & 0x01)
 155                 t |= 0x02;
 156         if (line_parity_prime & 0x01)
 157                 t |= 0x01;
 158         ecc[0] = ~t;
 159
 160 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
 161         // Swap the bytes into the wrong order
 162         t = ecc[0];
 163         ecc[0] = ecc[1];
 164         ecc[1] = t;
 165 #endif
 166 }
 167
 168
 169 /* Correct the ECC on a 256 byte block of data */
 170
 171 int yaffs_ECCCorrect(unsigned char *data, unsigned char *read_ecc,
 172                      const unsigned char *test_ecc)
 173 {
 174         unsigned char d0, d1, d2;       /* deltas */
 175
 176         d0 = read_ecc[0] ^ test_ecc[0];
 177         d1 = read_ecc[1] ^ test_ecc[1];
 178         d2 = read_ecc[2] ^ test_ecc[2];
 179
 180         if ((d0 | d1 | d2) == 0)
 181                 return 0; /* no error */
 182
 183         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
 184             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
 185             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
 186                 /* Single bit (recoverable) error in data */
 187
 188                 unsigned byte;
 189                 unsigned bit;
 190
 191 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
 192                 // swap the bytes to correct for the wrong order
 193                 unsigned char t;
 194
 195                 t = d0;
 196                 d0 = d1;
 197                 d1 = t;
 198 #endif
 199
 200                 bit = byte = 0;
 201
 202                 if (d1 & 0x80)
 203                         byte |= 0x80;
 204                 if (d1 & 0x20)
 205                         byte |= 0x40;
 206                 if (d1 & 0x08)
 207                         byte |= 0x20;
 208                 if (d1 & 0x02)
 209                         byte |= 0x10;
 210                 if (d0 & 0x80)
 211                         byte |= 0x08;
 212                 if (d0 & 0x20)
 213                         byte |= 0x04;
 214                 if (d0 & 0x08)
 215                         byte |= 0x02;
 216                 if (d0 & 0x02)
 217                         byte |= 0x01;
 218
 219                 if (d2 & 0x80)
 220                         bit |= 0x04;
 221                 if (d2 & 0x20)
 222                         bit |= 0x02;
 223                 if (d2 & 0x08)
 224                         bit |= 0x01;
 225
 226                 data[byte] ^= (1 << bit);
 227
 228                 return 1; /* Corrected the error */
 229         }
 230
 231         if ((yaffs_CountBits(d0) +
 232              yaffs_CountBits(d1) +
 233              yaffs_CountBits(d2)) ==  1) {
 234                 /* Reccoverable error in ecc */
 235
 236                 read_ecc[0] = test_ecc[0];
 237                 read_ecc[1] = test_ecc[1];
 238                 read_ecc[2] = test_ecc[2];
 239
 240                 return 1; /* Corrected the error */
 241         }
 242
 243         /* Unrecoverable error */
 244
 245         return -1;
 246
 247 }
 248
 249
 250 /*
 251  * ECCxxxOther does ECC calcs on arbitrary n bytes of data
 252  */
 253 void yaffs_ECCCalculateOther(const unsigned char *data, unsigned nBytes,
 254                              yaffs_ECCOther * eccOther)
 255 {
 256         unsigned int i;
 257
 258         unsigned char col_parity = 0;
 259         unsigned line_parity = 0;
 260         unsigned line_parity_prime = 0;
 261         unsigned char b;
 262
 263         for (i = 0; i < nBytes; i++) {
 264                 b = column_parity_table[*data++];
 265                 col_parity ^= b;
 266
 267                 if (b & 0x01)    {
 268                         /* odd number of bits in the byte */
 269                         line_parity ^= i;
 270                         line_parity_prime ^= ~i;
 271                 }
 272
 273         }
 274
 275         eccOther->colParity = (col_parity >> 2) & 0x3f;
 276         eccOther->lineParity = line_parity;
 277         eccOther->lineParityPrime = line_parity_prime;
 278 }
 279
 280 int yaffs_ECCCorrectOther(unsigned char *data, unsigned nBytes,
 281                           yaffs_ECCOther * read_ecc,
 282                           const yaffs_ECCOther * test_ecc)
 283 {
 284         unsigned char cDelta;   /* column parity delta */
 285         unsigned lDelta;        /* line parity delta */
 286         unsigned lDeltaPrime;   /* line parity delta */
 287         unsigned bit;
 288
 289         cDelta = read_ecc->colParity ^ test_ecc->colParity;
 290         lDelta = read_ecc->lineParity ^ test_ecc->lineParity;
 291         lDeltaPrime = read_ecc->lineParityPrime ^ test_ecc->lineParityPrime;
 292
 293         if ((cDelta | lDelta | lDeltaPrime) == 0)
 294                 return 0; /* no error */
 295
 296         if (lDelta == ~lDeltaPrime &&
 297             (((cDelta ^ (cDelta >> 1)) & 0x15) == 0x15))
 298         {
 299                 /* Single bit (recoverable) error in data */
 300
 301                 bit = 0;
 302
 303                 if (cDelta & 0x20)
 304                         bit |= 0x04;
 305                 if (cDelta & 0x08)
 306                         bit |= 0x02;
 307                 if (cDelta & 0x02)
 308                         bit |= 0x01;
 309
 310                 if(lDelta >= nBytes)
 311                         return -1;
 312
 313                 data[lDelta] ^= (1 << bit);
 314
 315                 return 1; /* corrected */
 316         }
 317
 318         if ((yaffs_CountBits32(lDelta) + yaffs_CountBits32(lDeltaPrime) +
 319              yaffs_CountBits(cDelta)) == 1) {
 320                 /* Reccoverable error in ecc */
 321
 322                 *read_ecc = *test_ecc;
 323                 return 1; /* corrected */
 324         }
 325
 326         /* Unrecoverable error */
 327
 328         return -1;
 329
 330 }
 331