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 const char *yaffs_ecc_c_version =
  33     "$Id: yaffs_ecc.c,v 1.5 2005-08-11 00:34:14 charles 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 static int yaffs_CountBits(unsigned char x)
  75 {
  76         int r = 0;
  77         while (x) {
  78                 if (x & 1)
  79                         r++;
  80                 x >>= 1;
  81         }
  82         return r;
  83 }
  84
  85 static int yaffs_CountBits32(unsigned x)
  86 {
  87         int r = 0;
  88         while (x) {
  89                 if (x & 1)
  90                         r++;
  91                 x >>= 1;
  92         }
  93         return r;
  94 }
  95
  96 void yaffs_ECCCalculate(const unsigned char *data, unsigned char *ecc)
  97 {
  98         unsigned int i;
  99
 100         unsigned char col_parity = 0;
 101         unsigned char line_parity = 0;
 102         unsigned char line_parity_prime = 0;
 103         unsigned char t;
 104         unsigned char b;
 105
 106         for (i = 0; i < 256; i++) {
 107                 b = column_parity_table[*data++];
 108                 col_parity ^= b;
 109
 110                 if (b & 0x01)   // odd number of bits in the byte
 111                 {
 112                         line_parity ^= i;
 113                         line_parity_prime ^= ~i;
 114                 }
 115
 116         }
 117
 118         ecc[2] = (~col_parity) | 0x03;
 119
 120         t = 0;
 121         if (line_parity & 0x80)
 122                 t |= 0x80;
 123         if (line_parity_prime & 0x80)
 124                 t |= 0x40;
 125         if (line_parity & 0x40)
 126                 t |= 0x20;
 127         if (line_parity_prime & 0x40)
 128                 t |= 0x10;
 129         if (line_parity & 0x20)
 130                 t |= 0x08;
 131         if (line_parity_prime & 0x20)
 132                 t |= 0x04;
 133         if (line_parity & 0x10)
 134                 t |= 0x02;
 135         if (line_parity_prime & 0x10)
 136                 t |= 0x01;
 137         ecc[1] = ~t;
 138
 139         t = 0;
 140         if (line_parity & 0x08)
 141                 t |= 0x80;
 142         if (line_parity_prime & 0x08)
 143                 t |= 0x40;
 144         if (line_parity & 0x04)
 145                 t |= 0x20;
 146         if (line_parity_prime & 0x04)
 147                 t |= 0x10;
 148         if (line_parity & 0x02)
 149                 t |= 0x08;
 150         if (line_parity_prime & 0x02)
 151                 t |= 0x04;
 152         if (line_parity & 0x01)
 153                 t |= 0x02;
 154         if (line_parity_prime & 0x01)
 155                 t |= 0x01;
 156         ecc[0] = ~t;
 157
 158 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
 159         // Swap the bytes into the wrong order
 160         t = ecc[0];
 161         ecc[0] = ecc[1];
 162         ecc[1] = t;
 163 #endif
 164 }
 165
 166 int yaffs_ECCCorrect(unsigned char *data, unsigned char *read_ecc,
 167                      const unsigned char *test_ecc)
 168 {
 169         unsigned char d0, d1, d2;       // deltas
 170
 171         d0 = read_ecc[0] ^ test_ecc[0];
 172         d1 = read_ecc[1] ^ test_ecc[1];
 173         d2 = read_ecc[2] ^ test_ecc[2];
 174
 175         if ((d0 | d1 | d2) == 0) {
 176                 // no error
 177                 return 0;
 178         }
 179
 180         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
 181             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
 182             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
 183                 // Single bit (recoverable) error in data
 184
 185                 unsigned byte;
 186                 unsigned bit;
 187
 188 #ifdef CONFIG_YAFFS_ECC_WRONG_ORDER
 189                 // swap the bytes to correct for the wrong order
 190                 unsigned char t;
 191
 192                 t = d0;
 193                 d0 = d1;
 194                 d1 = t;
 195 #endif
 196
 197                 bit = byte = 0;
 198
 199                 if (d1 & 0x80)
 200                         byte |= 0x80;
 201                 if (d1 & 0x20)
 202                         byte |= 0x40;
 203                 if (d1 & 0x08)
 204                         byte |= 0x20;
 205                 if (d1 & 0x02)
 206                         byte |= 0x10;
 207                 if (d0 & 0x80)
 208                         byte |= 0x08;
 209                 if (d0 & 0x20)
 210                         byte |= 0x04;
 211                 if (d0 & 0x08)
 212                         byte |= 0x02;
 213                 if (d0 & 0x02)
 214                         byte |= 0x01;
 215
 216                 if (d2 & 0x80)
 217                         bit |= 0x04;
 218                 if (d2 & 0x20)
 219                         bit |= 0x02;
 220                 if (d2 & 0x08)
 221                         bit |= 0x01;
 222
 223                 data[byte] ^= (1 << bit);
 224
 225                 return 1;
 226         }
 227
 228         if ((yaffs_CountBits(d0) + yaffs_CountBits(d1) + yaffs_CountBits(d2)) ==
 229             1) {
 230                 // Reccoverable error in ecc
 231
 232                 read_ecc[0] = test_ecc[0];
 233                 read_ecc[1] = test_ecc[1];
 234                 read_ecc[2] = test_ecc[2];
 235
 236                 return 1;
 237         }
 238         // Unrecoverable error
 239
 240         return -1;
 241
 242 }
 243
 244 void yaffs_ECCCalculateOther(const unsigned char *data, unsigned nBytes,
 245                              yaffs_ECCOther * eccOther)
 246 {
 247         unsigned int i;
 248
 249         unsigned char col_parity = 0;
 250         unsigned line_parity = 0;
 251         unsigned line_parity_prime = 0;
 252         unsigned char b;
 253
 254         for (i = 0; i < nBytes; i++) {
 255                 b = column_parity_table[*data++];
 256                 col_parity ^= b;
 257
 258                 if (b & 0x01)   // odd number of bits in the byte
 259                 {
 260                         line_parity ^= i;
 261                         line_parity_prime ^= ~i;
 262                 }
 263
 264         }
 265
 266         eccOther->colParity = (col_parity >> 2) & 0x3f;
 267         eccOther->lineParity = line_parity;
 268         eccOther->lineParityPrime = line_parity_prime;
 269 }
 270
 271 int yaffs_ECCCorrectOther(unsigned char *data, unsigned nBytes,
 272                           yaffs_ECCOther * read_ecc,
 273                           const yaffs_ECCOther * test_ecc)
 274 {
 275         unsigned char cDelta;   // column parity delta
 276         unsigned lDelta;        // line parity delta
 277         unsigned lDeltaPrime;   // line parity delta
 278         unsigned bit;
 279
 280         cDelta = read_ecc->colParity ^ test_ecc->colParity;
 281         lDelta = read_ecc->lineParity ^ test_ecc->lineParity;
 282         lDeltaPrime = read_ecc->lineParityPrime ^ test_ecc->lineParityPrime;
 283
 284         if ((cDelta | lDelta | lDeltaPrime) == 0) {
 285                 // no error
 286                 return 0;
 287         }
 288
 289         if (lDelta == ~lDeltaPrime && (((cDelta ^ (cDelta >> 1)) & 0x15) == 0x15))      // Not correct
 290         {
 291                 // Single bit (recoverable) error in data
 292
 293                 bit = 0;
 294
 295                 if (cDelta & 0x20)
 296                         bit |= 0x04;
 297                 if (cDelta & 0x08)
 298                         bit |= 0x02;
 299                 if (cDelta & 0x02)
 300                         bit |= 0x01;
 301
 302                 data[lDelta] ^= (1 << bit);
 303
 304                 return 1;
 305         }
 306
 307         if ((yaffs_CountBits32(lDelta) + yaffs_CountBits32(lDeltaPrime) +
 308              yaffs_CountBits(cDelta)) == 1) {
 309                 // Reccoverable error in ecc
 310
 311                 *read_ecc = *test_ecc;
 312                 return 1;
 313         }
 314         // Unrecoverable error
 315
 316         return -1;
 317
 318 }