]>
git.ipfire.org Git - people/ms/u-boot.git/blob - common/docecc.c
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.
7 * Author: Fabrice Bellard (fabrice.bellard@netgem.com)
8 * Copyright (C) 2000 Netgem S.A.
10 * $Id: docecc.c,v 1.4 2001/10/02 15:05:13 dwmw2 Exp $
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License as published by
14 * the Free Software Foundation; either version 2 of the License, or
15 * (at your option) any later version.
17 * This program is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU General Public License for more details.
22 * You should have received a copy of the GNU General Public License
23 * along with this program; if not, write to the Free Software
24 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
34 #include <linux/mtd/doc2000.h>
36 /* need to undef it (from asm/termbits.h) */
39 #define MM 10 /* Symbol size in bits */
40 #define KK (1023-4) /* Number of data symbols per block */
41 #define B0 510 /* First root of generator polynomial, alpha form */
42 #define PRIM 1 /* power of alpha used to generate roots of generator poly */
43 #define NN ((1 << MM) - 1)
45 typedef unsigned short dtype
;
48 static const int Pp
[MM
+1] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
50 /* This defines the type used to store an element of the Galois Field
51 * used by the code. Make sure this is something larger than a char if
52 * if anything larger than GF(256) is used.
54 * Note: unsigned char will work up to GF(256) but int seems to run
55 * faster on the Pentium.
59 /* No legal value in index form represents zero, so
60 * we need a special value for this purpose
64 /* Compute x % NN, where NN is 2**MM - 1,
65 * without a slow divide
72 x
= (x
>> MM
) + (x
& NN
);
79 for(ci=(n)-1;ci >=0;ci--)\
83 #define COPY(a,b,n) {\
85 for(ci=(n)-1;ci >=0;ci--)\
89 #define COPYDOWN(a,b,n) {\
91 for(ci=(n)-1;ci >=0;ci--)\
97 /* generate GF(2**m) from the irreducible polynomial p(X) in Pp[0]..Pp[m]
98 lookup tables: index->polynomial form alpha_to[] contains j=alpha**i;
99 polynomial form -> index form index_of[j=alpha**i] = i
100 alpha=2 is the primitive element of GF(2**m)
101 HARI's COMMENT: (4/13/94) alpha_to[] can be used as follows:
102 Let @ represent the primitive element commonly called "alpha" that
103 is the root of the primitive polynomial p(x). Then in GF(2^m), for any
105 @^i = a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
106 where the binary vector (a(0),a(1),a(2),...,a(m-1)) is the representation
107 of the integer "alpha_to[i]" with a(0) being the LSB and a(m-1) the MSB. Thus for
108 example the polynomial representation of @^5 would be given by the binary
109 representation of the integer "alpha_to[5]".
110 Similarily, index_of[] can be used as follows:
111 As above, let @ represent the primitive element of GF(2^m) that is
112 the root of the primitive polynomial p(x). In order to find the power
113 of @ (alpha) that has the polynomial representation
114 a(0) + a(1) @ + a(2) @^2 + ... + a(m-1) @^(m-1)
115 we consider the integer "i" whose binary representation with a(0) being LSB
116 and a(m-1) MSB is (a(0),a(1),...,a(m-1)) and locate the entry
117 "index_of[i]". Now, @^index_of[i] is that element whose polynomial
118 representation is (a(0),a(1),a(2),...,a(m-1)).
120 The element alpha_to[2^m-1] = 0 always signifying that the
121 representation of "@^infinity" = 0 is (0,0,0,...,0).
122 Similarily, the element index_of[0] = A0 always signifying
123 that the power of alpha which has the polynomial representation
124 (0,0,...,0) is "infinity".
129 generate_gf(dtype Alpha_to
[NN
+ 1], dtype Index_of
[NN
+ 1])
131 register int i
, mask
;
135 for (i
= 0; i
< MM
; i
++) {
137 Index_of
[Alpha_to
[i
]] = i
;
138 /* If Pp[i] == 1 then, term @^i occurs in poly-repr of @^MM */
140 Alpha_to
[MM
] ^= mask
; /* Bit-wise EXOR operation */
141 mask
<<= 1; /* single left-shift */
143 Index_of
[Alpha_to
[MM
]] = MM
;
145 * Have obtained poly-repr of @^MM. Poly-repr of @^(i+1) is given by
146 * poly-repr of @^i shifted left one-bit and accounting for any @^MM
147 * term that may occur when poly-repr of @^i is shifted.
150 for (i
= MM
+ 1; i
< NN
; i
++) {
151 if (Alpha_to
[i
- 1] >= mask
)
152 Alpha_to
[i
] = Alpha_to
[MM
] ^ ((Alpha_to
[i
- 1] ^ mask
) << 1);
154 Alpha_to
[i
] = Alpha_to
[i
- 1] << 1;
155 Index_of
[Alpha_to
[i
]] = i
;
162 * Performs ERRORS+ERASURES decoding of RS codes. bb[] is the content
163 * of the feedback shift register after having processed the data and
166 * Return number of symbols corrected, or -1 if codeword is illegal
167 * or uncorrectable. If eras_pos is non-null, the detected error locations
168 * are written back. NOTE! This array must be at least NN-KK elements long.
169 * The corrected data are written in eras_val[]. They must be xor with the data
170 * to retrieve the correct data : data[erase_pos[i]] ^= erase_val[i] .
172 * First "no_eras" erasures are declared by the calling program. Then, the
173 * maximum # of errors correctable is t_after_eras = floor((NN-KK-no_eras)/2).
174 * If the number of channel errors is not greater than "t_after_eras" the
175 * transmitted codeword will be recovered. Details of algorithm can be found
176 * in R. Blahut's "Theory ... of Error-Correcting Codes".
178 * Warning: the eras_pos[] array must not contain duplicate entries; decoder failure
179 * will result. The decoder *could* check for this condition, but it would involve
180 * extra time on every decoding operation.
183 eras_dec_rs(dtype Alpha_to
[NN
+ 1], dtype Index_of
[NN
+ 1],
184 gf bb
[NN
- KK
+ 1], gf eras_val
[NN
-KK
], int eras_pos
[NN
-KK
],
187 int deg_lambda
, el
, deg_omega
;
189 gf u
,q
,tmp
,num1
,num2
,den
,discr_r
;
190 gf lambda
[NN
-KK
+ 1], s
[NN
-KK
+ 1]; /* Err+Eras Locator poly
191 * and syndrome poly */
192 gf b
[NN
-KK
+ 1], t
[NN
-KK
+ 1], omega
[NN
-KK
+ 1];
193 gf root
[NN
-KK
], reg
[NN
-KK
+ 1], loc
[NN
-KK
];
194 int syn_error
, count
;
201 /* if remainder is zero, data[] is a codeword and there are no
202 * errors to correct. So return data[] unmodified
208 for(i
=1;i
<=NN
-KK
;i
++){
211 for(j
=1;j
<NN
-KK
;j
++){
214 tmp
= Index_of
[bb
[j
]];
216 for(i
=1;i
<=NN
-KK
;i
++)
217 s
[i
] ^= Alpha_to
[modnn(tmp
+ (B0
+i
-1)*PRIM
*j
)];
220 /* undo the feedback register implicit multiplication and convert
221 syndromes to index form */
223 for(i
=1;i
<=NN
-KK
;i
++) {
224 tmp
= Index_of
[s
[i
]];
226 tmp
= modnn(tmp
+ 2 * KK
* (B0
+i
-1)*PRIM
);
230 CLEAR(&lambda
[1],NN
-KK
);
234 /* Init lambda to be the erasure locator polynomial */
235 lambda
[1] = Alpha_to
[modnn(PRIM
* eras_pos
[0])];
236 for (i
= 1; i
< no_eras
; i
++) {
237 u
= modnn(PRIM
*eras_pos
[i
]);
238 for (j
= i
+1; j
> 0; j
--) {
239 tmp
= Index_of
[lambda
[j
- 1]];
241 lambda
[j
] ^= Alpha_to
[modnn(u
+ tmp
)];
245 /* Test code that verifies the erasure locator polynomial just constructed
246 Needed only for decoder debugging. */
248 /* find roots of the erasure location polynomial */
249 for(i
=1;i
<=no_eras
;i
++)
250 reg
[i
] = Index_of
[lambda
[i
]];
252 for (i
= 1,k
=NN
-Ldec
; i
<= NN
; i
++,k
= modnn(NN
+k
-Ldec
)) {
254 for (j
= 1; j
<= no_eras
; j
++)
256 reg
[j
] = modnn(reg
[j
] + j
);
257 q
^= Alpha_to
[reg
[j
]];
261 /* store root and error location number indices */
266 if (count
!= no_eras
) {
267 printf("\n lambda(x) is WRONG\n");
272 printf("\n Erasure positions as determined by roots of Eras Loc Poly:\n");
273 for (i
= 0; i
< count
; i
++)
274 printf("%d ", loc
[i
]);
279 for(i
=0;i
<NN
-KK
+1;i
++)
280 b
[i
] = Index_of
[lambda
[i
]];
283 * Begin Berlekamp-Massey algorithm to determine error+erasure
288 while (++r
<= NN
-KK
) { /* r is the step number */
289 /* Compute discrepancy at the r-th step in poly-form */
291 for (i
= 0; i
< r
; i
++){
292 if ((lambda
[i
] != 0) && (s
[r
- i
] != A0
)) {
293 discr_r
^= Alpha_to
[modnn(Index_of
[lambda
[i
]] + s
[r
- i
])];
296 discr_r
= Index_of
[discr_r
]; /* Index form */
298 /* 2 lines below: B(x) <-- x*B(x) */
299 COPYDOWN(&b
[1],b
,NN
-KK
);
302 /* 7 lines below: T(x) <-- lambda(x) - discr_r*x*b(x) */
304 for (i
= 0 ; i
< NN
-KK
; i
++) {
306 t
[i
+1] = lambda
[i
+1] ^ Alpha_to
[modnn(discr_r
+ b
[i
])];
308 t
[i
+1] = lambda
[i
+1];
310 if (2 * el
<= r
+ no_eras
- 1) {
311 el
= r
+ no_eras
- el
;
313 * 2 lines below: B(x) <-- inv(discr_r) *
316 for (i
= 0; i
<= NN
-KK
; i
++)
317 b
[i
] = (lambda
[i
] == 0) ? A0
: modnn(Index_of
[lambda
[i
]] - discr_r
+ NN
);
319 /* 2 lines below: B(x) <-- x*B(x) */
320 COPYDOWN(&b
[1],b
,NN
-KK
);
323 COPY(lambda
,t
,NN
-KK
+1);
327 /* Convert lambda to index form and compute deg(lambda(x)) */
329 for(i
=0;i
<NN
-KK
+1;i
++){
330 lambda
[i
] = Index_of
[lambda
[i
]];
335 * Find roots of the error+erasure locator polynomial by Chien
338 COPY(®
[1],&lambda
[1],NN
-KK
);
339 count
= 0; /* Number of roots of lambda(x) */
340 for (i
= 1,k
=NN
-Ldec
; i
<= NN
; i
++,k
= modnn(NN
+k
-Ldec
)) {
342 for (j
= deg_lambda
; j
> 0; j
--){
344 reg
[j
] = modnn(reg
[j
] + j
);
345 q
^= Alpha_to
[reg
[j
]];
350 /* store root (index-form) and error location number */
353 /* If we've already found max possible roots,
354 * abort the search to save time
356 if(++count
== deg_lambda
)
359 if (deg_lambda
!= count
) {
361 * deg(lambda) unequal to number of roots => uncorrectable
368 * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
369 * x**(NN-KK)). in index form. Also find deg(omega).
372 for (i
= 0; i
< NN
-KK
;i
++){
374 j
= (deg_lambda
< i
) ? deg_lambda
: i
;
376 if ((s
[i
+ 1 - j
] != A0
) && (lambda
[j
] != A0
))
377 tmp
^= Alpha_to
[modnn(s
[i
+ 1 - j
] + lambda
[j
])];
381 omega
[i
] = Index_of
[tmp
];
386 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
387 * inv(X(l))**(B0-1) and den = lambda_pr(inv(X(l))) all in poly-form
389 for (j
= count
-1; j
>=0; j
--) {
391 for (i
= deg_omega
; i
>= 0; i
--) {
393 num1
^= Alpha_to
[modnn(omega
[i
] + i
* root
[j
])];
395 num2
= Alpha_to
[modnn(root
[j
] * (B0
- 1) + NN
)];
398 /* lambda[i+1] for i even is the formal derivative lambda_pr of lambda[i] */
399 for (i
= min(deg_lambda
,NN
-KK
-1) & ~1; i
>= 0; i
-=2) {
400 if(lambda
[i
+1] != A0
)
401 den
^= Alpha_to
[modnn(lambda
[i
+1] + i
* root
[j
])];
405 printf("\n ERROR: denominator = 0\n");
407 /* Convert to dual- basis */
411 /* Apply error to data */
413 eras_val
[j
] = Alpha_to
[modnn(Index_of
[num1
] + Index_of
[num2
] + NN
- Index_of
[den
])];
420 eras_pos
[i
] = loc
[i
];
424 /***************************************************************************/
425 /* The DOC specific code begins here */
427 #define SECTOR_SIZE 512
428 /* The sector bytes are packed into NB_DATA MM bits words */
429 #define NB_DATA (((SECTOR_SIZE + 1) * 8 + 6) / MM)
432 * Correct the errors in 'sector[]' by using 'ecc1[]' which is the
433 * content of the feedback shift register applyied to the sector and
434 * the ECC. Return the number of errors corrected (and correct them in
435 * sector), or -1 if error
437 int doc_decode_ecc(unsigned char sector
[SECTOR_SIZE
], unsigned char ecc1
[6])
439 int parity
, i
, nb_errors
;
442 int error_pos
[NN
-KK
], pos
, bitpos
, index
, val
;
443 dtype
*Alpha_to
, *Index_of
;
445 /* init log and exp tables here to save memory. However, it is slower */
446 Alpha_to
= malloc((NN
+ 1) * sizeof(dtype
));
450 Index_of
= malloc((NN
+ 1) * sizeof(dtype
));
456 generate_gf(Alpha_to
, Index_of
);
460 bb
[0] = (ecc1
[4] & 0xff) | ((ecc1
[5] & 0x03) << 8);
461 bb
[1] = ((ecc1
[5] & 0xfc) >> 2) | ((ecc1
[2] & 0x0f) << 6);
462 bb
[2] = ((ecc1
[2] & 0xf0) >> 4) | ((ecc1
[3] & 0x3f) << 4);
463 bb
[3] = ((ecc1
[3] & 0xc0) >> 6) | ((ecc1
[0] & 0xff) << 2);
465 nb_errors
= eras_dec_rs(Alpha_to
, Index_of
, bb
,
466 error_val
, error_pos
, 0);
470 /* correct the errors */
471 for(i
=0;i
<nb_errors
;i
++) {
473 if (pos
>= NB_DATA
&& pos
< KK
) {
478 /* extract bit position (MSB first) */
479 pos
= 10 * (NB_DATA
- 1 - pos
) - 6;
480 /* now correct the following 10 bits. At most two bytes
481 can be modified since pos is even */
482 index
= (pos
>> 3) ^ 1;
484 if ((index
>= 0 && index
< SECTOR_SIZE
) ||
485 index
== (SECTOR_SIZE
+ 1)) {
486 val
= error_val
[i
] >> (2 + bitpos
);
488 if (index
< SECTOR_SIZE
)
489 sector
[index
] ^= val
;
491 index
= ((pos
>> 3) + 1) ^ 1;
492 bitpos
= (bitpos
+ 10) & 7;
495 if ((index
>= 0 && index
< SECTOR_SIZE
) ||
496 index
== (SECTOR_SIZE
+ 1)) {
497 val
= error_val
[i
] << (8 - bitpos
);
499 if (index
< SECTOR_SIZE
)
500 sector
[index
] ^= val
;
505 /* use parity to test extra errors */
506 if ((parity
& 0xff) != 0)