yaffs_ecc.c

   1 /*
   2  * YAFFS: Yet Another Flash File System. A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2018 Aleph One Ltd.
   5  *
   6  * Created by Charles Manning <charles@aleph1.co.uk>
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License version 2 as
  10  * published by the Free Software Foundation.
  11  */
  12
  13 /*
  14  * This code implements the ECC algorithm used in SmartMedia.
  15  *
  16  * The ECC comprises 22 bits of parity information and is stuffed into 3 bytes.
  17  * The two unused bit are set to 1.
  18  * The ECC can correct single bit errors in a 256-byte page of data. Thus, two
  19  * such ECC blocks are used on a 512-byte NAND page.
  20  *
  21  */
  22
  23 #include "yportenv.h"
  24
  25 #include "yaffs_ecc.h"
  26
  27 /* Table generated by gen-ecc.c
  28  * Using a table means we do not have to calculate p1..p4 and p1'..p4'
  29  * for each byte of data. These are instead provided in a table in bits7..2.
  30  * Bit 0 of each entry indicates whether the entry has an odd or even parity,
  31  * and therefore this bytes influence on the line parity.
  32  */
  33
  34 static const unsigned char column_parity_table[] = {
  35         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
  36         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  37         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
  38         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  39         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
  40         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  41         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
  42         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  43         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
  44         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  45         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
  46         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  47         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
  48         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  49         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
  50         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  51         0xa9, 0xfc, 0xf0, 0xa5, 0xcc, 0x99, 0x95, 0xc0,
  52         0xc0, 0x95, 0x99, 0xcc, 0xa5, 0xf0, 0xfc, 0xa9,
  53         0x3c, 0x69, 0x65, 0x30, 0x59, 0x0c, 0x00, 0x55,
  54         0x55, 0x00, 0x0c, 0x59, 0x30, 0x65, 0x69, 0x3c,
  55         0x30, 0x65, 0x69, 0x3c, 0x55, 0x00, 0x0c, 0x59,
  56         0x59, 0x0c, 0x00, 0x55, 0x3c, 0x69, 0x65, 0x30,
  57         0xa5, 0xf0, 0xfc, 0xa9, 0xc0, 0x95, 0x99, 0xcc,
  58         0xcc, 0x99, 0x95, 0xc0, 0xa9, 0xfc, 0xf0, 0xa5,
  59         0x0c, 0x59, 0x55, 0x00, 0x69, 0x3c, 0x30, 0x65,
  60         0x65, 0x30, 0x3c, 0x69, 0x00, 0x55, 0x59, 0x0c,
  61         0x99, 0xcc, 0xc0, 0x95, 0xfc, 0xa9, 0xa5, 0xf0,
  62         0xf0, 0xa5, 0xa9, 0xfc, 0x95, 0xc0, 0xcc, 0x99,
  63         0x95, 0xc0, 0xcc, 0x99, 0xf0, 0xa5, 0xa9, 0xfc,
  64         0xfc, 0xa9, 0xa5, 0xf0, 0x99, 0xcc, 0xc0, 0x95,
  65         0x00, 0x55, 0x59, 0x0c, 0x65, 0x30, 0x3c, 0x69,
  66         0x69, 0x3c, 0x30, 0x65, 0x0c, 0x59, 0x55, 0x00,
  67 };
  68
  69
  70 /* Calculate the ECC for a 256-byte block of data */
  71 void yaffs_ecc_calc(const unsigned char *data, unsigned char *ecc)
  72 {
  73         unsigned int i;
  74         unsigned char col_parity = 0;
  75         unsigned char line_parity = 0;
  76         unsigned char line_parity_prime = 0;
  77         unsigned char t;
  78         unsigned char b;
  79
  80         for (i = 0; i < 256; i++) {
  81                 b = column_parity_table[*data++];
  82                 col_parity ^= b;
  83
  84                 if (b & 0x01) { /* odd number of bits in the byte */
  85                         line_parity ^= i;
  86                         line_parity_prime ^= ~i;
  87                 }
  88         }
  89
  90         ecc[2] = (~col_parity) | 0x03;
  91
  92         t = 0;
  93         if (line_parity & 0x80)
  94                 t |= 0x80;
  95         if (line_parity_prime & 0x80)
  96                 t |= 0x40;
  97         if (line_parity & 0x40)
  98                 t |= 0x20;
  99         if (line_parity_prime & 0x40)
 100                 t |= 0x10;
 101         if (line_parity & 0x20)
 102                 t |= 0x08;
 103         if (line_parity_prime & 0x20)
 104                 t |= 0x04;
 105         if (line_parity & 0x10)
 106                 t |= 0x02;
 107         if (line_parity_prime & 0x10)
 108                 t |= 0x01;
 109         ecc[1] = ~t;
 110
 111         t = 0;
 112         if (line_parity & 0x08)
 113                 t |= 0x80;
 114         if (line_parity_prime & 0x08)
 115                 t |= 0x40;
 116         if (line_parity & 0x04)
 117                 t |= 0x20;
 118         if (line_parity_prime & 0x04)
 119                 t |= 0x10;
 120         if (line_parity & 0x02)
 121                 t |= 0x08;
 122         if (line_parity_prime & 0x02)
 123                 t |= 0x04;
 124         if (line_parity & 0x01)
 125                 t |= 0x02;
 126         if (line_parity_prime & 0x01)
 127                 t |= 0x01;
 128         ecc[0] = ~t;
 129
 130 }
 131
 132 /* Correct the ECC on a 256 byte block of data */
 133
 134 int yaffs_ecc_correct(unsigned char *data, unsigned char *read_ecc,
 135                       const unsigned char *test_ecc)
 136 {
 137         unsigned char d0, d1, d2;       /* deltas */
 138
 139         d0 = read_ecc[0] ^ test_ecc[0];
 140         d1 = read_ecc[1] ^ test_ecc[1];
 141         d2 = read_ecc[2] ^ test_ecc[2];
 142
 143         if ((d0 | d1 | d2) == 0)
 144                 return 0;       /* no error */
 145
 146         if (((d0 ^ (d0 >> 1)) & 0x55) == 0x55 &&
 147             ((d1 ^ (d1 >> 1)) & 0x55) == 0x55 &&
 148             ((d2 ^ (d2 >> 1)) & 0x54) == 0x54) {
 149                 /* Single bit (recoverable) error in data */
 150
 151                 unsigned byte;
 152                 unsigned bit;
 153
 154                 bit = byte = 0;
 155
 156                 if (d1 & 0x80)
 157                         byte |= 0x80;
 158                 if (d1 & 0x20)
 159                         byte |= 0x40;
 160                 if (d1 & 0x08)
 161                         byte |= 0x20;
 162                 if (d1 & 0x02)
 163                         byte |= 0x10;
 164                 if (d0 & 0x80)
 165                         byte |= 0x08;
 166                 if (d0 & 0x20)
 167                         byte |= 0x04;
 168                 if (d0 & 0x08)
 169                         byte |= 0x02;
 170                 if (d0 & 0x02)
 171                         byte |= 0x01;
 172
 173                 if (d2 & 0x80)
 174                         bit |= 0x04;
 175                 if (d2 & 0x20)
 176                         bit |= 0x02;
 177                 if (d2 & 0x08)
 178                         bit |= 0x01;
 179
 180                 data[byte] ^= (1 << bit);
 181
 182                 return 1;       /* Corrected the error */
 183         }
 184
 185         if ((hweight8(d0) + hweight8(d1) + hweight8(d2)) == 1) {
 186                 /* Reccoverable error in ecc */
 187
 188                 read_ecc[0] = test_ecc[0];
 189                 read_ecc[1] = test_ecc[1];
 190                 read_ecc[2] = test_ecc[2];
 191
 192                 return 1;       /* Corrected the error */
 193         }
 194
 195         /* Unrecoverable error */
 196
 197         return -1;
 198
 199 }
 200
 201 /*
 202  * ECCxxxOther does ECC calcs on arbitrary n bytes of data
 203  */
 204 void yaffs_ecc_calc_other(const unsigned char *data, unsigned n_bytes,
 205                           struct yaffs_ecc_other *ecc_other)
 206 {
 207         unsigned int i;
 208         unsigned char col_parity = 0;
 209         unsigned line_parity = 0;
 210         unsigned line_parity_prime = 0;
 211         unsigned char b;
 212
 213         for (i = 0; i < n_bytes; i++) {
 214                 b = column_parity_table[*data++];
 215                 col_parity ^= b;
 216
 217                 if (b & 0x01) {
 218                         /* odd number of bits in the byte */
 219                         line_parity ^= i;
 220                         line_parity_prime ^= ~i;
 221                 }
 222
 223         }
 224
 225         ecc_other->col_parity = (col_parity >> 2) & 0x3f;
 226         ecc_other->line_parity = line_parity;
 227         ecc_other->line_parity_prime = line_parity_prime;
 228 }
 229
 230 int yaffs_ecc_correct_other(unsigned char *data, unsigned n_bytes,
 231                             struct yaffs_ecc_other *read_ecc,
 232                             const struct yaffs_ecc_other *test_ecc)
 233 {
 234         unsigned char delta_col;        /* column parity delta */
 235         unsigned delta_line;    /* line parity delta */
 236         unsigned delta_line_prime;      /* line parity delta */
 237         unsigned bit;
 238
 239         delta_col = read_ecc->col_parity ^ test_ecc->col_parity;
 240         delta_line = read_ecc->line_parity ^ test_ecc->line_parity;
 241         delta_line_prime =
 242             read_ecc->line_parity_prime ^ test_ecc->line_parity_prime;
 243
 244         if ((delta_col | delta_line | delta_line_prime) == 0)
 245                 return 0;       /* no error */
 246
 247         if (delta_line == ~delta_line_prime &&
 248             (((delta_col ^ (delta_col >> 1)) & 0x15) == 0x15)) {
 249                 /* Single bit (recoverable) error in data */
 250
 251                 bit = 0;
 252
 253                 if (delta_col & 0x20)
 254                         bit |= 0x04;
 255                 if (delta_col & 0x08)
 256                         bit |= 0x02;
 257                 if (delta_col & 0x02)
 258                         bit |= 0x01;
 259
 260                 if (delta_line >= n_bytes)
 261                         return -1;
 262
 263                 data[delta_line] ^= (1 << bit);
 264
 265                 return 1;       /* corrected */
 266         }
 267
 268         if ((hweight32(delta_line) +
 269              hweight32(delta_line_prime) +
 270              hweight8(delta_col)) == 1) {
 271                 /* Reccoverable error in ecc */
 272
 273                 *read_ecc = *test_ecc;
 274                 return 1;       /* corrected */
 275         }
 276
 277         /* Unrecoverable error */
 278
 279         return -1;
 280 }