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