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 } 282