yaffs_ecc.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2011 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
  20  * such ECC blocks are used on a 512-byte NAND page.
  21  *
  22  */
  23
  24 #include "yportenv.h"
  25
  26 #include "yaffs_ecc.h"
  27
  28 /* Table generated by gen-ecc.c
  29  * Using a table means we do not have to calculate p1..p4 and p1'..p4'
  30  * for each byte of data. These are instead provided in a table in bits7..2.
  31  * Bit 0 of each entry indicates whether the entry has an odd or even parity,
  32  * and therefore this bytes influence on the line parity.
  33  */
  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
  71 /* Calculate the ECC for a 256-byte block of data */
  72 void yaffs_ecc_calc(const unsigned char *data, unsigned char *ecc)
  73 {
  74         unsigned int i;
  75         unsigned char col_parity = 0;
  76         unsigned char line_parity = 0;
  77         unsigned char line_parity_prime = 0;
  78         unsigned char t;
  79         unsigned char b;
  80
  81         for (i = 0; i < 256; i++) {
  82                 b = column_parity_table[*data++];
  83                 col_parity ^= b;
  84
  85                 if (b & 0x01) { /* odd number of bits in the byte */
  86                         line_parity ^= i;
  87                         line_parity_prime ^= ~i;
  88                 }
  89         }
  90
  91         ecc[2] = (~col_parity) | 0x03;
  92
  93         t = 0;
  94         if (line_parity & 0x80)
  95                 t |= 0x80;
  96         if (line_parity_prime & 0x80)
  97                 t |= 0x40;
  98         if (line_parity & 0x40)
  99                 t |= 0x20;
 100         if (line_parity_prime & 0x40)
 101                 t |= 0x10;
 102         if (line_parity & 0x20)
 103                 t |= 0x08;
 104         if (line_parity_prime & 0x20)
 105                 t |= 0x04;
 106         if (line_parity & 0x10)
 107                 t |= 0x02;
 108         if (line_parity_prime & 0x10)
 109                 t |= 0x01;
 110         ecc[1] = ~t;
 111
 112         t = 0;
 113         if (line_parity & 0x08)
 114                 t |= 0x80;
 115         if (line_parity_prime & 0x08)
 116                 t |= 0x40;
 117         if (line_parity & 0x04)
 118                 t |= 0x20;
 119         if (line_parity_prime & 0x04)
 120                 t |= 0x10;
 121         if (line_parity & 0x02)
 122                 t |= 0x08;
 123         if (line_parity_prime & 0x02)
 124                 t |= 0x04;
 125         if (line_parity & 0x01)
 126                 t |= 0x02;
 127         if (line_parity_prime & 0x01)
 128                 t |= 0x01;
 129         ecc[0] = ~t;
 130
 131 }
 132
 133 /* Correct the ECC on a 256 byte block of data */
 134
 135 int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc,
 136                       const unsigned char *test_ecc)
 137 {
 138         unsigned char d0, d1, d2;       /* deltas */
 139
 140         d0 = read_ecc[0] ^ test_ecc[0];
 141         d1 = read_ecc[1] ^ test_ecc[1];
 142         d2 = read_ecc[2] ^ test_ecc[2];
 143
 144         if ((d0 | d1 | d2) == 0)
 145                 return 0;       /* no error */
 146
 147         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
 148             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
 149             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
 150                 /* Single bit (recoverable) error in data */
 151
 152                 unsigned byte;
 153                 unsigned bit;
 154
 155                 bit = byte = 0;
 156
 157                 if (d1 & 0x80)
 158                         byte |= 0x80;
 159                 if (d1 & 0x20)
 160                         byte |= 0x40;
 161                 if (d1 & 0x08)
 162                         byte |= 0x20;
 163                 if (d1 & 0x02)
 164                         byte |= 0x10;
 165                 if (d0 & 0x80)
 166                         byte |= 0x08;
 167                 if (d0 & 0x20)
 168                         byte |= 0x04;
 169                 if (d0 & 0x08)
 170                         byte |= 0x02;
 171                 if (d0 & 0x02)
 172                         byte |= 0x01;
 173
 174                 if (d2 & 0x80)
 175                         bit |= 0x04;
 176                 if (d2 & 0x20)
 177                         bit |= 0x02;
 178                 if (d2 & 0x08)
 179                         bit |= 0x01;
 180
 181                 data[byte] ^= (1 << bit);
 182
 183                 return 1;       /* Corrected the error */
 184         }
 185
 186         if ((hweight8(d0) + hweight8(d1) + hweight8(d2)) == 1) {
 187                 /* Reccoverable error in ecc */
 188
 189                 read_ecc[0] = test_ecc[0];
 190                 read_ecc[1] = test_ecc[1];
 191                 read_ecc[2] = test_ecc[2];
 192
 193                 return 1;       /* Corrected the error */
 194         }
 195
 196         /* Unrecoverable error */
 197
 198         return -1;
 199
 200 }
 201
 202 /*
 203  * ECCxxxOther does ECC calcs on arbitrary n bytes of data
 204  */
 205 void yaffs_ecc_calc_other(const unsigned char *data, unsigned n_bytes,
 206                           struct yaffs_ecc_other *ecc_other)
 207 {
 208         unsigned int i;
 209         unsigned char col_parity = 0;
 210         unsigned line_parity = 0;
 211         unsigned line_parity_prime = 0;
 212         unsigned char b;
 213
 214         for (i = 0; i < n_bytes; i++) {
 215                 b = column_parity_table[*data++];
 216                 col_parity ^= b;
 217
 218                 if (b & 0x01) {
 219                         /* odd number of bits in the byte */
 220                         line_parity ^= i;
 221                         line_parity_prime ^= ~i;
 222                 }
 223
 224         }
 225
 226         ecc_other->col_parity = (col_parity >> 2) & 0x3f;
 227         ecc_other->line_parity = line_parity;
 228         ecc_other->line_parity_prime = line_parity_prime;
 229 }
 230
 231 int yaffs_ecc_correct_other(unsigned char *data, unsigned n_bytes,
 232                             struct yaffs_ecc_other *read_ecc,
 233                             const struct yaffs_ecc_other *test_ecc)
 234 {
 235         unsigned char delta_col;        /* column parity delta */
 236         unsigned delta_line;    /* line parity delta */
 237         unsigned delta_line_prime;      /* line parity delta */
 238         unsigned bit;
 239
 240         delta_col = read_ecc->col_parity ^ test_ecc->col_parity;
 241         delta_line = read_ecc->line_parity ^ test_ecc->line_parity;
 242         delta_line_prime =
 243             read_ecc->line_parity_prime ^ test_ecc->line_parity_prime;
 244
 245         if ((delta_col | delta_line | delta_line_prime) == 0)
 246                 return 0;       /* no error */
 247
 248         if (delta_line == ~delta_line_prime &&
 249             (((delta_col ^ (delta_col >> 1)) & 0x15) == 0x15)) {
 250                 /* Single bit (recoverable) error in data */
 251
 252                 bit = 0;
 253
 254                 if (delta_col & 0x20)
 255                         bit |= 0x04;
 256                 if (delta_col & 0x08)
 257                         bit |= 0x02;
 258                 if (delta_col & 0x02)
 259                         bit |= 0x01;
 260
 261                 if (delta_line >= n_bytes)
 262                         return -1;
 263
 264                 data[delta_line] ^= (1 << bit);
 265
 266                 return 1;       /* corrected */
 267         }
 268
 269         if ((hweight32(delta_line) +
 270              hweight32(delta_line_prime) +
 271              hweight8(delta_col)) == 1) {
 272                 /* Reccoverable error in ecc */
 273
 274                 *read_ecc = *test_ecc;
 275                 return 1;       /* corrected */
 276         }
 277
 278         /* Unrecoverable error */
 279
 280         return -1;
 281 }