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