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  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation.
  13  *
  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.1 2003-05-20 22:32:24 charles Exp $";
  33
  34
  35 #include "yaffs_ecc.h"
  36
  37 static const unsigned char column_parity_table[] = {
  38 0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69, 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  39 0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc, 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  40 0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0, 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  41 0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65, 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  42 0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc, 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  43 0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59, 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  44 0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55, 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  45 0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0, 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  46 0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0, 0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  47 0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55, 0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  48 0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59, 0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  49 0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc, 0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  50 0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65, 0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  51 0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0, 0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  52 0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc, 0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  53 0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69, 0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  54 };
  55
  56
  57 static int yaffs_CountBits(unsigned char x)
  58 {
  59         int r = 0;
  60         while(x)
  61         {
  62                 if(x & 1) r++;
  63                 x >>= 1;
  64         }
  65         return r;
  66 }
  67
  68 void yaffs_ECCCalculate(const unsigned char *data,unsigned char *ecc)
  69 {
  70         unsigned int i;
  71
  72         unsigned char col_parity = 0;
  73         unsigned char line_parity = 0;
  74         unsigned char line_parity_prime = 0;
  75         unsigned char t;
  76         unsigned char b;
  77
  78         for(i = 0; i < 256; i++)
  79         {
  80                 b = column_parity_table[*data++];
  81                 col_parity ^= b;
  82
  83                 if(b & 0x01) // odd number of bits in the byte
  84                 {
  85                         line_parity ^= i;
  86                         line_parity_prime ^= ~i;
  87                 }
  88
  89         }
  90
  91         ecc[2] = (~col_parity) | 0x03;
  92
  93         t = 0;
  94         if(line_parity       & 0x80) t |= 0x80;
  95         if(line_parity_prime & 0x80) t |= 0x40;
  96         if(line_parity       & 0x40) t |= 0x20;
  97         if(line_parity_prime & 0x40) t |= 0x10;
  98         if(line_parity       & 0x20) t |= 0x08;
  99         if(line_parity_prime & 0x20) t |= 0x04;
 100         if(line_parity       & 0x10) t |= 0x02;
 101         if(line_parity_prime & 0x10) t |= 0x01;
 102         ecc[1] = ~t;
 103
 104         t = 0;
 105         if(line_parity       & 0x08) t |= 0x80;
 106         if(line_parity_prime & 0x08) t |= 0x40;
 107         if(line_parity       & 0x04) t |= 0x20;
 108         if(line_parity_prime & 0x04) t |= 0x10;
 109         if(line_parity       & 0x02) t |= 0x08;
 110         if(line_parity_prime & 0x02) t |= 0x04;
 111         if(line_parity       & 0x01) t |= 0x02;
 112         if(line_parity_prime & 0x01) t |= 0x01;
 113         ecc[0] = ~t;
 114
 115 #if CONFIG_YAFFS_ECC_WRONG_ORDER
 116         // Swap the bytes into the wrong order
 117         t = ecc[0];
 118         ecc[0] = ecc[1];
 119         ecc[1] = t;
 120 #endif
 121 }
 122
 123 int yaffs_ECCCorrect(unsigned char *data, unsigned char *read_ecc, const unsigned char *test_ecc)
 124 {
 125         unsigned char d0, d1, d2; // deltas
 126
 127         d0 = read_ecc[0] ^ test_ecc[0];
 128         d1 = read_ecc[1] ^ test_ecc[1];
 129         d2 = read_ecc[2] ^ test_ecc[2];
 130
 131
 132
 133         if((d0 | d1 | d2) == 0)
 134         {
 135                 // no error
 136                 return 0;
 137         }
 138
 139         if( ((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
 140             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
 141             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54)
 142         {
 143                 // Single bit (recoverable) error in data
 144
 145                 unsigned byte;
 146                 unsigned bit;
 147
 148 #if CONFIG_YAFFS_ECC_WRONG_ORDER
 149                 // swap the bytes to correct for the wrong order
 150                 unsigned char t;
 151
 152                 t = d0;
 153                 d0 = d1;
 154                 d1 = t;
 155 #endif
 156
 157                 bit = byte = 0;
 158
 159
 160                 if(d1 & 0x80) byte |= 0x80;
 161                 if(d1 & 0x20) byte |= 0x40;
 162                 if(d1 & 0x08) byte |= 0x20;
 163                 if(d1 & 0x02) byte |= 0x10;
 164                 if(d0 & 0x80) byte |= 0x08;
 165                 if(d0 & 0x20) byte |= 0x04;
 166                 if(d0 & 0x08) byte |= 0x02;
 167                 if(d0 & 0x02) byte |= 0x01;
 168
 169                 if(d2 & 0x80) bit |= 0x04;
 170                 if(d2 & 0x20) bit |= 0x02;
 171                 if(d2 & 0x08) bit |= 0x01;
 172
 173                 data[byte] ^= (1 << bit);
 174
 175                 return 1;
 176         }
 177
 178         if((yaffs_CountBits(d0)+yaffs_CountBits(d1)+yaffs_CountBits(d2)) == 1)
 179         {
 180                 // Reccoverable error in ecc
 181
 182                 read_ecc[0] = test_ecc[0];
 183                 read_ecc[1] = test_ecc[1];
 184                 read_ecc[2] = test_ecc[2];
 185
 186                 return 1;
 187         }
 188
 189         // Unrecoverable error
 190
 191         return -1;
 192
 193
 194 }