Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 |
Brian Norris | 7854d3f | 2011-06-23 14:12:08 -0700 | [diff] [blame] | 5 | * syndrome into a standard syndome. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 6 | * |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 7 | * Author: Fabrice Bellard (fabrice.bellard@netgem.com) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 8 | * Copyright (C) 2000 Netgem S.A. |
| 9 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 29 | #include <linux/delay.h> |
| 30 | #include <linux/slab.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 31 | #include <linux/init.h> |
| 32 | #include <linux/types.h> |
| 33 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 34 | #include <linux/mtd/mtd.h> |
| 35 | #include <linux/mtd/doc2000.h> |
| 36 | |
Grant Coady | 66c81f0 | 2005-09-22 21:43:54 -0700 | [diff] [blame] | 37 | #define DEBUG_ECC 0 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
| 47 | typedef unsigned short dtype; |
| 48 | |
| 49 | /* 1+x^3+x^10 */ |
| 50 | static 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 | */ |
| 59 | typedef 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 | */ |
| 69 | static inline gf |
| 70 | modnn(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) {\ |
| 80 | int ci;\ |
| 81 | for(ci=(n)-1;ci >=0;ci--)\ |
| 82 | (a)[ci] = 0;\ |
| 83 | } |
| 84 | |
| 85 | #define COPY(a,b,n) {\ |
| 86 | int ci;\ |
| 87 | for(ci=(n)-1;ci >=0;ci--)\ |
| 88 | (a)[ci] = (b)[ci];\ |
| 89 | } |
| 90 | |
| 91 | #define COPYDOWN(a,b,n) {\ |
| 92 | int ci;\ |
| 93 | for(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]". |
Lucas De Marchi | 25985ed | 2011-03-30 22:57:33 -0300 | [diff] [blame] | 112 | Similarly, index_of[] can be used as follows: |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 119 | "index_of[i]". Now, @^index_of[i] is that element whose polynomial |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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). |
Lucas De Marchi | 25985ed | 2011-03-30 22:57:33 -0300 | [diff] [blame] | 124 | Similarly, the element index_of[0] = A0 always signifying |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 125 | that the power of alpha which has the polynomial representation |
| 126 | (0,0,...,0) is "infinity". |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 127 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 128 | */ |
| 129 | |
| 130 | static void |
| 131 | generate_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] . |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 173 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | * */ |
| 184 | static int |
| 185 | eras_dec_rs(dtype Alpha_to[NN + 1], dtype Index_of[NN + 1], |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 186 | gf bb[NN - KK + 1], gf eras_val[NN-KK], int eras_pos[NN-KK], |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | } |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 209 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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]]; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 217 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | } |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 231 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | } |
Grant Coady | 66c81f0 | 2005-09-22 21:43:54 -0700 | [diff] [blame] | 246 | #if DEBUG_ECC >= 1 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 247 | /* Test code that verifies the erasure locator polynomial just constructed |
| 248 | Needed only for decoder debugging. */ |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 249 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | } |
Grant Coady | 66c81f0 | 2005-09-22 21:43:54 -0700 | [diff] [blame] | 273 | #if DEBUG_ECC >= 2 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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]]; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 283 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 386 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 399 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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) { |
Grant Coady | 66c81f0 | 2005-09-22 21:43:54 -0700 | [diff] [blame] | 406 | #if DEBUG_ECC >= 1 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 433 | /* |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 437 | * sector), or -1 if error |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 438 | */ |
| 439 | int 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; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 451 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 467 | nb_errors = eras_dec_rs(Alpha_to, Index_of, bb, |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 486 | if ((index >= 0 && index < SECTOR_SIZE) || |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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; |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 497 | if ((index >= 0 && index < SECTOR_SIZE) || |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | } |
Thomas Gleixner | e5580fb | 2005-11-07 11:15:40 +0000 | [diff] [blame] | 506 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | |
| 517 | EXPORT_SYMBOL_GPL(doc_decode_ecc); |
| 518 | |
| 519 | MODULE_LICENSE("GPL"); |
| 520 | MODULE_AUTHOR("Fabrice Bellard <fabrice.bellard@netgem.com>"); |
| 521 | MODULE_DESCRIPTION("ECC code for correcting errors detected by DiskOnChip 2000 and Millennium ECC hardware"); |