yaffs_ecc.c

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