yaffs_ecc.c

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