1/* 2 * ECC algorithm for M-systems disk on chip. We use the excellent Reed 3 * Solmon code of Phil Karn (karn@ka9q.ampr.org) available under the 4 * GNU GPL License. The rest is simply to convert the disk on chip 5 * syndrom into a standard syndom. 6 * 7 * Author: Fabrice Bellard (fabrice.bellard@netgem.com) 8 * Copyright (C) 2000 Netgem S.A. 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 as published by 12 * the Free Software Foundation; either version 2 of the License, or 13 * (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 23 */ 24#include <linux/kernel.h> 25#include <linux/module.h> 26#include <asm/errno.h> 27#include <asm/io.h> 28#include <asm/uaccess.h> 29#include <linux/delay.h> 30#include <linux/slab.h> 31#include <linux/init.h> 32#include <linux/types.h> 33 34#include <linux/mtd/mtd.h> 35#include <linux/mtd/doc2000.h> 36 37#define DEBUG_ECC 0 38/* need to undef it (from asm/termbits.h) */ 39#undef B0 40 41#define MM 10 /* Symbol size in bits */ 42#define KK (1023-4) /* Number of data symbols per block */ 43#define B0 510 /* First root of generator polynomial, alpha form */ 44#define PRIM 1 /* power of alpha used to generate roots of generator poly */ 45#define NN ((1 << MM) - 1) 46 47typedef unsigned short dtype; 48 49/* 1+x^3+x^10 */ 50static const int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 }; 51 52/* This defines the type used to store an element of the Galois Field 53 * used by the code. Make sure this is something larger than a char if 54 * if anything larger than GF(256) is used. 55 * 56 * Note: unsigned char will work up to GF(256) but int seems to run 57 * faster on the Pentium. 58 */ 59typedef int gf; 60 61/* No legal value in index form represents zero, so 62 * we need a special value for this purpose 63 */ 64#define A0 (NN) 65 66/* Compute x % NN, where NN is 2**MM - 1, 67 * without a slow divide 68 */ 69static inline gf 70modnn(int x) 71{ 72 while (x >= NN) { 73 x -= NN; 74 x = (x >> MM) + (x & NN); 75 } 76 return x; 77} 78 79#define CLEAR(a,n) {\ 80int ci;\ 81for(ci=(n)-1;ci >=0;ci--)\ 82(a)[ci] = 0;\ 83} 84 85#define COPY(a,b,n) {\ 86int ci;\ 87for(ci=(n)-1;ci >=0;ci--)\ 88(a)[ci] = (b)[ci];\ 89} 90 91#define COPYDOWN(a,b,n) {\ 92int ci;\ 93for(ci=(n)-1;ci >=0;ci--)\ 94(a)[ci] = (b)[ci];\ 95} 96 97#define Ldec 1 98 99/* generate GF(2**m) from the irreducible polynomial p(X) in Pp[0]..Pp[m] 100 lookup tables: index->polynomial form alpha_to[] contains j=alpha**i; 101 polynomial form -> index form index_of[j=alpha**i] = i 102 alpha=2 is the primitive element of GF(2**m) 103 HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows: 104 Let @ represent the primitive element commonly called "alpha" that 105 is the root of the primitive polynomial p(x). Then in GF(2^m), for any 106 0 <= i <= 2^m-2, 107 @^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1) 108 where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation 109 of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for 110 example the polynomial representation of @^5 would be given by the binary 111 representation of the integer "alpha_to[5]". 112 Similarily, index_of[] can be used as follows: 113 As above, let @ represent the primitive element of GF(2^m) that is 114 the root of the primitive polynomial p(x). In order to find the power 115 of @ (alpha) that has the polynomial representation 116 a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1) 117 we consider the integer "i" whose binary representation with a(0) being LSB 118 and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry 119 "index_of[i]". Now, @^index_of[i] is that element whose polynomial 120 representation is (a(0),a(1),a(2),...,a(m-1)). 121 NOTE: 122 The element alpha_to[2^m-1] = 0 always signifying that the 123 representation of "@^infinity" = 0 is (0,0,0,...,0). 124 Similarily, the element index_of[0] = A0 always signifying 125 that the power of alpha which has the polynomial representation 126 (0,0,...,0) is "infinity". 127 128*/ 129 130static void 131generate_gf(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1]) 132{ 133 register int i, mask; 134 135 mask = 1; 136 Alpha_to[MM] = 0; 137 for (i = 0; i < MM; i++) { 138 Alpha_to[i] = mask; 139 Index_of[Alpha_to[i]] = i; 140 /* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */ 141 if (Pp[i] != 0) 142 Alpha_to[MM] ^= mask; /* Bit-wise EXOR operation */ 143 mask <<= 1; /* single left-shift */ 144 } 145 Index_of[Alpha_to[MM]] = MM; 146 /* 147 * Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by 148 * poly-repr of @^i shifted left one-bit and accounting for any @^MM 149 * term that may occur when poly-repr of @^i is shifted. 150 */ 151 mask >>= 1; 152 for (i = MM + 1; i < NN; i++) { 153 if (Alpha_to[i - 1] >= mask) 154 Alpha_to[i] = Alpha_to[MM] ^ ((Alpha_to[i - 1] ^ mask) << 1); 155 else 156 Alpha_to[i] = Alpha_to[i - 1] << 1; 157 Index_of[Alpha_to[i]] = i; 158 } 159 Index_of[0] = A0; 160 Alpha_to[NN] = 0; 161} 162 163/* 164 * Performs ERRORS+ERASURES decoding of RS codes. bb[] is the content 165 * of the feedback shift register after having processed the data and 166 * the ECC. 167 * 168 * Return number of symbols corrected, or -1 if codeword is illegal 169 * or uncorrectable. If eras_pos is non-null, the detected error locations 170 * are written back. NOTE! This array must be at least NN-KK elements long. 171 * The corrected data are written in eras_val[]. They must be xor with the data 172 * to retrieve the correct data : data[erase_pos[i]] ^= erase_val[i] . 173 * 174 * First "no_eras" erasures are declared by the calling program. Then, the 175 * maximum # of errors correctable is t_after_eras = floor((NN-KK-no_eras)/2). 176 * If the number of channel errors is not greater than "t_after_eras" the 177 * transmitted codeword will be recovered. Details of algorithm can be found 178 * in R. Blahut's "Theory ... of Error-Correcting Codes". 179 180 * Warning: the eras_pos[] array must not contain duplicate entries; decoder failure 181 * will result. The decoder *could* check for this condition, but it would involve 182 * extra time on every decoding operation. 183 * */ 184static int 185eras_dec_rs(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1], 186 gf bb[NN - KK + 1], gf eras_val[NN-KK], int eras_pos[NN-KK], 187 int no_eras) 188{ 189 int deg_lambda, el, deg_omega; 190 int i, j, r,k; 191 gf u,q,tmp,num1,num2,den,discr_r; 192 gf lambda[NN-KK + 1], s[NN-KK + 1]; /* Err+Eras Locator poly 193 * and syndrome poly */ 194 gf b[NN-KK + 1], t[NN-KK + 1], omega[NN-KK + 1]; 195 gf root[NN-KK], reg[NN-KK + 1], loc[NN-KK]; 196 int syn_error, count; 197 198 syn_error = 0; 199 for(i=0;i<NN-KK;i++) 200 syn_error |= bb[i]; 201 202 if (!syn_error) { 203 /* if remainder is zero, data[] is a codeword and there are no 204 * errors to correct. So return data[] unmodified 205 */ 206 count = 0; 207 goto finish; 208 } 209 210 for(i=1;i<=NN-KK;i++){ 211 s[i] = bb[0]; 212 } 213 for(j=1;j<NN-KK;j++){ 214 if(bb[j] == 0) 215 continue; 216 tmp = Index_of[bb[j]]; 217 218 for(i=1;i<=NN-KK;i++) 219 s[i] ^= Alpha_to[modnn(tmp + (B0+i-1)*PRIM*j)]; 220 } 221 222 /* undo the feedback register implicit multiplication and convert 223 syndromes to index form */ 224 225 for(i=1;i<=NN-KK;i++) { 226 tmp = Index_of[s[i]]; 227 if (tmp != A0) 228 tmp = modnn(tmp + 2 * KK * (B0+i-1)*PRIM); 229 s[i] = tmp; 230 } 231 232 CLEAR(&lambda[1],NN-KK); 233 lambda[0] = 1; 234 235 if (no_eras > 0) { 236 /* Init lambda to be the erasure locator polynomial */ 237 lambda[1] = Alpha_to[modnn(PRIM * eras_pos[0])]; 238 for (i = 1; i < no_eras; i++) { 239 u = modnn(PRIM*eras_pos[i]); 240 for (j = i+1; j > 0; j--) { 241 tmp = Index_of[lambda[j - 1]]; 242 if(tmp != A0) 243 lambda[j] ^= Alpha_to[modnn(u + tmp)]; 244 } 245 } 246#if DEBUG_ECC >= 1 247 /* Test code that verifies the erasure locator polynomial just constructed 248 Needed only for decoder debugging. */ 249 250 /* find roots of the erasure location polynomial */ 251 for(i=1;i<=no_eras;i++) 252 reg[i] = Index_of[lambda[i]]; 253 count = 0; 254 for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) { 255 q = 1; 256 for (j = 1; j <= no_eras; j++) 257 if (reg[j] != A0) { 258 reg[j] = modnn(reg[j] + j); 259 q ^= Alpha_to[reg[j]]; 260 } 261 if (q != 0) 262 continue; 263 /* store root and error location number indices */ 264 root[count] = i; 265 loc[count] = k; 266 count++; 267 } 268 if (count != no_eras) { 269 printf("\n lambda(x) is WRONG\n"); 270 count = -1; 271 goto finish; 272 } 273#if DEBUG_ECC >= 2 274 printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n"); 275 for (i = 0; i < count; i++) 276 printf("%d ", loc[i]); 277 printf("\n"); 278#endif 279#endif 280 } 281 for(i=0;i<NN-KK+1;i++) 282 b[i] = Index_of[lambda[i]]; 283 284 /* 285 * Begin Berlekamp-Massey algorithm to determine error+erasure 286 * locator polynomial 287 */ 288 r = no_eras; 289 el = no_eras; 290 while (++r <= NN-KK) { /* r is the step number */ 291 /* Compute discrepancy at the r-th step in poly-form */ 292 discr_r = 0; 293 for (i = 0; i < r; i++){ 294 if ((lambda[i] != 0) && (s[r - i] != A0)) { 295 discr_r ^= Alpha_to[modnn(Index_of[lambda[i]] + s[r - i])]; 296 } 297 } 298 discr_r = Index_of[discr_r]; /* Index form */ 299 if (discr_r == A0) { 300 /* 2 lines below: B(x) <-- x*B(x) */ 301 COPYDOWN(&b[1],b,NN-KK); 302 b[0] = A0; 303 } else { 304 /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */ 305 t[0] = lambda[0]; 306 for (i = 0 ; i < NN-KK; i++) { 307 if(b[i] != A0) 308 t[i+1] = lambda[i+1] ^ Alpha_to[modnn(discr_r + b[i])]; 309 else 310 t[i+1] = lambda[i+1]; 311 } 312 if (2 * el <= r + no_eras - 1) { 313 el = r + no_eras - el; 314 /* 315 * 2 lines below: B(x) <-- inv(discr_r) * 316 * lambda(x) 317 */ 318 for (i = 0; i <= NN-KK; i++) 319 b[i] = (lambda[i] == 0) ? A0 : modnn(Index_of[lambda[i]] - discr_r + NN); 320 } else { 321 /* 2 lines below: B(x) <-- x*B(x) */ 322 COPYDOWN(&b[1],b,NN-KK); 323 b[0] = A0; 324 } 325 COPY(lambda,t,NN-KK+1); 326 } 327 } 328 329 /* Convert lambda to index form and compute deg(lambda(x)) */ 330 deg_lambda = 0; 331 for(i=0;i<NN-KK+1;i++){ 332 lambda[i] = Index_of[lambda[i]]; 333 if(lambda[i] != A0) 334 deg_lambda = i; 335 } 336 /* 337 * Find roots of the error+erasure locator polynomial by Chien 338 * Search 339 */ 340 COPY(®[1],&lambda[1],NN-KK); 341 count = 0; /* Number of roots of lambda(x) */ 342 for (i = 1,k=NN-Ldec; i <= NN; i++,k = modnn(NN+k-Ldec)) { 343 q = 1; 344 for (j = deg_lambda; j > 0; j--){ 345 if (reg[j] != A0) { 346 reg[j] = modnn(reg[j] + j); 347 q ^= Alpha_to[reg[j]]; 348 } 349 } 350 if (q != 0) 351 continue; 352 /* store root (index-form) and error location number */ 353 root[count] = i; 354 loc[count] = k; 355 /* If we've already found max possible roots, 356 * abort the search to save time 357 */ 358 if(++count == deg_lambda) 359 break; 360 } 361 if (deg_lambda != count) { 362 /* 363 * deg(lambda) unequal to number of roots => uncorrectable 364 * error detected 365 */ 366 count = -1; 367 goto finish; 368 } 369 /* 370 * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 371 * x**(NN-KK)). in index form. Also find deg(omega). 372 */ 373 deg_omega = 0; 374 for (i = 0; i < NN-KK;i++){ 375 tmp = 0; 376 j = (deg_lambda < i) ? deg_lambda : i; 377 for(;j >= 0; j--){ 378 if ((s[i + 1 - j] != A0) && (lambda[j] != A0)) 379 tmp ^= Alpha_to[modnn(s[i + 1 - j] + lambda[j])]; 380 } 381 if(tmp != 0) 382 deg_omega = i; 383 omega[i] = Index_of[tmp]; 384 } 385 omega[NN-KK] = A0; 386 387 /* 388 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 389 * inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form 390 */ 391 for (j = count-1; j >=0; j--) { 392 num1 = 0; 393 for (i = deg_omega; i >= 0; i--) { 394 if (omega[i] != A0) 395 num1 ^= Alpha_to[modnn(omega[i] + i * root[j])]; 396 } 397 num2 = Alpha_to[modnn(root[j] * (B0 - 1) + NN)]; 398 den = 0; 399 400 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */ 401 for (i = min(deg_lambda,NN-KK-1) & ~1; i >= 0; i -=2) { 402 if(lambda[i+1] != A0) 403 den ^= Alpha_to[modnn(lambda[i+1] + i * root[j])]; 404 } 405 if (den == 0) { 406#if DEBUG_ECC >= 1 407 printf("\n ERROR: denominator = 0\n"); 408#endif 409 /* Convert to dual- basis */ 410 count = -1; 411 goto finish; 412 } 413 /* Apply error to data */ 414 if (num1 != 0) { 415 eras_val[j] = Alpha_to[modnn(Index_of[num1] + Index_of[num2] + NN - Index_of[den])]; 416 } else { 417 eras_val[j] = 0; 418 } 419 } 420 finish: 421 for(i=0;i<count;i++) 422 eras_pos[i] = loc[i]; 423 return count; 424} 425 426/***************************************************************************/ 427/* The DOC specific code begins here */ 428 429#define SECTOR_SIZE 512 430/* The sector bytes are packed into NB_DATA MM bits words */ 431#define NB_DATA (((SECTOR_SIZE + 1) * 8 + 6) / MM) 432 433/* 434 * Correct the errors in 'sector[]' by using 'ecc1[]' which is the 435 * content of the feedback shift register applyied to the sector and 436 * the ECC. Return the number of errors corrected (and correct them in 437 * sector), or -1 if error 438 */ 439int doc_decode_ecc(unsigned char sector[SECTOR_SIZE], unsigned char ecc1[6]) 440{ 441 int parity, i, nb_errors; 442 gf bb[NN - KK + 1]; 443 gf error_val[NN-KK]; 444 int error_pos[NN-KK], pos, bitpos, index, val; 445 dtype *Alpha_to, *Index_of; 446 447 /* init log and exp tables here to save memory. However, it is slower */ 448 Alpha_to = kmalloc((NN + 1) * sizeof(dtype), GFP_KERNEL); 449 if (!Alpha_to) 450 return -1; 451 452 Index_of = kmalloc((NN + 1) * sizeof(dtype), GFP_KERNEL); 453 if (!Index_of) { 454 kfree(Alpha_to); 455 return -1; 456 } 457 458 generate_gf(Alpha_to, Index_of); 459 460 parity = ecc1[1]; 461 462 bb[0] = (ecc1[4] & 0xff) | ((ecc1[5] & 0x03) << 8); 463 bb[1] = ((ecc1[5] & 0xfc) >> 2) | ((ecc1[2] & 0x0f) << 6); 464 bb[2] = ((ecc1[2] & 0xf0) >> 4) | ((ecc1[3] & 0x3f) << 4); 465 bb[3] = ((ecc1[3] & 0xc0) >> 6) | ((ecc1[0] & 0xff) << 2); 466 467 nb_errors = eras_dec_rs(Alpha_to, Index_of, bb, 468 error_val, error_pos, 0); 469 if (nb_errors <= 0) 470 goto the_end; 471 472 /* correct the errors */ 473 for(i=0;i<nb_errors;i++) { 474 pos = error_pos[i]; 475 if (pos >= NB_DATA && pos < KK) { 476 nb_errors = -1; 477 goto the_end; 478 } 479 if (pos < NB_DATA) { 480 /* extract bit position (MSB first) */ 481 pos = 10 * (NB_DATA - 1 - pos) - 6; 482 /* now correct the following 10 bits. At most two bytes 483 can be modified since pos is even */ 484 index = (pos >> 3) ^ 1; 485 bitpos = pos & 7; 486 if ((index >= 0 && index < SECTOR_SIZE) || 487 index == (SECTOR_SIZE + 1)) { 488 val = error_val[i] >> (2 + bitpos); 489 parity ^= val; 490 if (index < SECTOR_SIZE) 491 sector[index] ^= val; 492 } 493 index = ((pos >> 3) + 1) ^ 1; 494 bitpos = (bitpos + 10) & 7; 495 if (bitpos == 0) 496 bitpos = 8; 497 if ((index >= 0 && index < SECTOR_SIZE) || 498 index == (SECTOR_SIZE + 1)) { 499 val = error_val[i] << (8 - bitpos); 500 parity ^= val; 501 if (index < SECTOR_SIZE) 502 sector[index] ^= val; 503 } 504 } 505 } 506 507 /* use parity to test extra errors */ 508 if ((parity & 0xff) != 0) 509 nb_errors = -1; 510 511 the_end: 512 kfree(Alpha_to); 513 kfree(Index_of); 514 return nb_errors; 515} 516 517EXPORT_SYMBOL_GPL(doc_decode_ecc); 518 519MODULE_LICENSE("GPL"); 520MODULE_AUTHOR("Fabrice Bellard <fabrice.bellard@netgem.com>"); 521MODULE_DESCRIPTION("ECC code for correcting errors detected by DiskOnChip 2000 and Millennium ECC hardware"); 522