1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
39#undef B0
40
41#define MM 10
42#define KK (1023-4)
43#define B0 510
44#define PRIM 1
45#define NN ((1 << MM) - 1)
46
47typedef unsigned short dtype;
48
49
50static const int Pp[MM+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
51
52
53
54
55
56
57
58
59typedef int gf;
60
61
62
63
64#define A0 (NN)
65
66
67
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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
141 if (Pp[i] != 0)
142 Alpha_to[MM] ^= mask;
143 mask <<= 1;
144 }
145 Index_of[Alpha_to[MM]] = MM;
146
147
148
149
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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
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];
193
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
204
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
223
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
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
248
249
250
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
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
286
287
288 r = no_eras;
289 el = no_eras;
290 while (++r <= NN-KK) {
291
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];
299 if (discr_r == A0) {
300
301 COPYDOWN(&b[1],b,NN-KK);
302 b[0] = A0;
303 } else {
304
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
316
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
322 COPYDOWN(&b[1],b,NN-KK);
323 b[0] = A0;
324 }
325 COPY(lambda,t,NN-KK+1);
326 }
327 }
328
329
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
338
339
340 COPY(®[1],&lambda[1],NN-KK);
341 count = 0;
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
353 root[count] = i;
354 loc[count] = k;
355
356
357
358 if(++count == deg_lambda)
359 break;
360 }
361 if (deg_lambda != count) {
362
363
364
365
366 count = -1;
367 goto finish;
368 }
369
370
371
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
389
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
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
410 count = -1;
411 goto finish;
412 }
413
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
428
429#define SECTOR_SIZE 512
430
431#define NB_DATA (((SECTOR_SIZE + 1) * 8 + 6) / MM)
432
433
434
435
436
437
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
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
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
481 pos = 10 * (NB_DATA - 1 - pos) - 6;
482
483
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
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