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