Root/
1 | /* |
2 | * Generic binary BCH encoding/decoding library |
3 | * |
4 | * This program is free software; you can redistribute it and/or modify it |
5 | * under the terms of the GNU General Public License version 2 as published by |
6 | * the Free Software Foundation. |
7 | * |
8 | * This program is distributed in the hope that it will be useful, but WITHOUT |
9 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
10 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for |
11 | * more details. |
12 | * |
13 | * You should have received a copy of the GNU General Public License along with |
14 | * this program; if not, write to the Free Software Foundation, Inc., 51 |
15 | * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
16 | * |
17 | * Copyright © 2011 Parrot S.A. |
18 | * |
19 | * Author: Ivan Djelic <ivan.djelic@parrot.com> |
20 | * |
21 | * Description: |
22 | * |
23 | * This library provides runtime configurable encoding/decoding of binary |
24 | * Bose-Chaudhuri-Hocquenghem (BCH) codes. |
25 | * |
26 | * Call init_bch to get a pointer to a newly allocated bch_control structure for |
27 | * the given m (Galois field order), t (error correction capability) and |
28 | * (optional) primitive polynomial parameters. |
29 | * |
30 | * Call encode_bch to compute and store ecc parity bytes to a given buffer. |
31 | * Call decode_bch to detect and locate errors in received data. |
32 | * |
33 | * On systems supporting hw BCH features, intermediate results may be provided |
34 | * to decode_bch in order to skip certain steps. See decode_bch() documentation |
35 | * for details. |
36 | * |
37 | * Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of |
38 | * parameters m and t; thus allowing extra compiler optimizations and providing |
39 | * better (up to 2x) encoding performance. Using this option makes sense when |
40 | * (m,t) are fixed and known in advance, e.g. when using BCH error correction |
41 | * on a particular NAND flash device. |
42 | * |
43 | * Algorithmic details: |
44 | * |
45 | * Encoding is performed by processing 32 input bits in parallel, using 4 |
46 | * remainder lookup tables. |
47 | * |
48 | * The final stage of decoding involves the following internal steps: |
49 | * a. Syndrome computation |
50 | * b. Error locator polynomial computation using Berlekamp-Massey algorithm |
51 | * c. Error locator root finding (by far the most expensive step) |
52 | * |
53 | * In this implementation, step c is not performed using the usual Chien search. |
54 | * Instead, an alternative approach described in [1] is used. It consists in |
55 | * factoring the error locator polynomial using the Berlekamp Trace algorithm |
56 | * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial |
57 | * solving techniques [2] are used. The resulting algorithm, called BTZ, yields |
58 | * much better performance than Chien search for usual (m,t) values (typically |
59 | * m >= 13, t < 32, see [1]). |
60 | * |
61 | * [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields |
62 | * of characteristic 2, in: Western European Workshop on Research in Cryptology |
63 | * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear. |
64 | * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over |
65 | * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996. |
66 | */ |
67 | |
68 | #include <linux/kernel.h> |
69 | #include <linux/errno.h> |
70 | #include <linux/init.h> |
71 | #include <linux/module.h> |
72 | #include <linux/slab.h> |
73 | #include <linux/bitops.h> |
74 | #include <asm/byteorder.h> |
75 | #include <linux/bch.h> |
76 | |
77 | #if defined(CONFIG_BCH_CONST_PARAMS) |
78 | #define GF_M(_p) (CONFIG_BCH_CONST_M) |
79 | #define GF_T(_p) (CONFIG_BCH_CONST_T) |
80 | #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1) |
81 | #else |
82 | #define GF_M(_p) ((_p)->m) |
83 | #define GF_T(_p) ((_p)->t) |
84 | #define GF_N(_p) ((_p)->n) |
85 | #endif |
86 | |
87 | #define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32) |
88 | #define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8) |
89 | |
90 | #ifndef dbg |
91 | #define dbg(_fmt, args...) do {} while (0) |
92 | #endif |
93 | |
94 | /* |
95 | * represent a polynomial over GF(2^m) |
96 | */ |
97 | struct gf_poly { |
98 | unsigned int deg; /* polynomial degree */ |
99 | unsigned int c[0]; /* polynomial terms */ |
100 | }; |
101 | |
102 | /* given its degree, compute a polynomial size in bytes */ |
103 | #define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int)) |
104 | |
105 | /* polynomial of degree 1 */ |
106 | struct gf_poly_deg1 { |
107 | struct gf_poly poly; |
108 | unsigned int c[2]; |
109 | }; |
110 | |
111 | /* |
112 | * same as encode_bch(), but process input data one byte at a time |
113 | */ |
114 | static void encode_bch_unaligned(struct bch_control *bch, |
115 | const unsigned char *data, unsigned int len, |
116 | uint32_t *ecc) |
117 | { |
118 | int i; |
119 | const uint32_t *p; |
120 | const int l = BCH_ECC_WORDS(bch)-1; |
121 | |
122 | while (len--) { |
123 | p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); |
124 | |
125 | for (i = 0; i < l; i++) |
126 | ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); |
127 | |
128 | ecc[l] = (ecc[l] << 8)^(*p); |
129 | } |
130 | } |
131 | |
132 | /* |
133 | * convert ecc bytes to aligned, zero-padded 32-bit ecc words |
134 | */ |
135 | static void load_ecc8(struct bch_control *bch, uint32_t *dst, |
136 | const uint8_t *src) |
137 | { |
138 | uint8_t pad[4] = {0, 0, 0, 0}; |
139 | unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; |
140 | |
141 | for (i = 0; i < nwords; i++, src += 4) |
142 | dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; |
143 | |
144 | memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); |
145 | dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; |
146 | } |
147 | |
148 | /* |
149 | * convert 32-bit ecc words to ecc bytes |
150 | */ |
151 | static void store_ecc8(struct bch_control *bch, uint8_t *dst, |
152 | const uint32_t *src) |
153 | { |
154 | uint8_t pad[4]; |
155 | unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; |
156 | |
157 | for (i = 0; i < nwords; i++) { |
158 | *dst++ = (src[i] >> 24); |
159 | *dst++ = (src[i] >> 16) & 0xff; |
160 | *dst++ = (src[i] >> 8) & 0xff; |
161 | *dst++ = (src[i] >> 0) & 0xff; |
162 | } |
163 | pad[0] = (src[nwords] >> 24); |
164 | pad[1] = (src[nwords] >> 16) & 0xff; |
165 | pad[2] = (src[nwords] >> 8) & 0xff; |
166 | pad[3] = (src[nwords] >> 0) & 0xff; |
167 | memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); |
168 | } |
169 | |
170 | /** |
171 | * encode_bch - calculate BCH ecc parity of data |
172 | * @bch: BCH control structure |
173 | * @data: data to encode |
174 | * @len: data length in bytes |
175 | * @ecc: ecc parity data, must be initialized by caller |
176 | * |
177 | * The @ecc parity array is used both as input and output parameter, in order to |
178 | * allow incremental computations. It should be of the size indicated by member |
179 | * @ecc_bytes of @bch, and should be initialized to 0 before the first call. |
180 | * |
181 | * The exact number of computed ecc parity bits is given by member @ecc_bits of |
182 | * @bch; it may be less than m*t for large values of t. |
183 | */ |
184 | void encode_bch(struct bch_control *bch, const uint8_t *data, |
185 | unsigned int len, uint8_t *ecc) |
186 | { |
187 | const unsigned int l = BCH_ECC_WORDS(bch)-1; |
188 | unsigned int i, mlen; |
189 | unsigned long m; |
190 | uint32_t w, r[l+1]; |
191 | const uint32_t * const tab0 = bch->mod8_tab; |
192 | const uint32_t * const tab1 = tab0 + 256*(l+1); |
193 | const uint32_t * const tab2 = tab1 + 256*(l+1); |
194 | const uint32_t * const tab3 = tab2 + 256*(l+1); |
195 | const uint32_t *pdata, *p0, *p1, *p2, *p3; |
196 | |
197 | if (ecc) { |
198 | /* load ecc parity bytes into internal 32-bit buffer */ |
199 | load_ecc8(bch, bch->ecc_buf, ecc); |
200 | } else { |
201 | memset(bch->ecc_buf, 0, sizeof(r)); |
202 | } |
203 | |
204 | /* process first unaligned data bytes */ |
205 | m = ((unsigned long)data) & 3; |
206 | if (m) { |
207 | mlen = (len < (4-m)) ? len : 4-m; |
208 | encode_bch_unaligned(bch, data, mlen, bch->ecc_buf); |
209 | data += mlen; |
210 | len -= mlen; |
211 | } |
212 | |
213 | /* process 32-bit aligned data words */ |
214 | pdata = (uint32_t *)data; |
215 | mlen = len/4; |
216 | data += 4*mlen; |
217 | len -= 4*mlen; |
218 | memcpy(r, bch->ecc_buf, sizeof(r)); |
219 | |
220 | /* |
221 | * split each 32-bit word into 4 polynomials of weight 8 as follows: |
222 | * |
223 | * 31 ...24 23 ...16 15 ... 8 7 ... 0 |
224 | * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt |
225 | * tttttttt mod g = r0 (precomputed) |
226 | * zzzzzzzz 00000000 mod g = r1 (precomputed) |
227 | * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) |
228 | * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) |
229 | * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 |
230 | */ |
231 | while (mlen--) { |
232 | /* input data is read in big-endian format */ |
233 | w = r[0]^cpu_to_be32(*pdata++); |
234 | p0 = tab0 + (l+1)*((w >> 0) & 0xff); |
235 | p1 = tab1 + (l+1)*((w >> 8) & 0xff); |
236 | p2 = tab2 + (l+1)*((w >> 16) & 0xff); |
237 | p3 = tab3 + (l+1)*((w >> 24) & 0xff); |
238 | |
239 | for (i = 0; i < l; i++) |
240 | r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; |
241 | |
242 | r[l] = p0[l]^p1[l]^p2[l]^p3[l]; |
243 | } |
244 | memcpy(bch->ecc_buf, r, sizeof(r)); |
245 | |
246 | /* process last unaligned bytes */ |
247 | if (len) |
248 | encode_bch_unaligned(bch, data, len, bch->ecc_buf); |
249 | |
250 | /* store ecc parity bytes into original parity buffer */ |
251 | if (ecc) |
252 | store_ecc8(bch, ecc, bch->ecc_buf); |
253 | } |
254 | EXPORT_SYMBOL_GPL(encode_bch); |
255 | |
256 | static inline int modulo(struct bch_control *bch, unsigned int v) |
257 | { |
258 | const unsigned int n = GF_N(bch); |
259 | while (v >= n) { |
260 | v -= n; |
261 | v = (v & n) + (v >> GF_M(bch)); |
262 | } |
263 | return v; |
264 | } |
265 | |
266 | /* |
267 | * shorter and faster modulo function, only works when v < 2N. |
268 | */ |
269 | static inline int mod_s(struct bch_control *bch, unsigned int v) |
270 | { |
271 | const unsigned int n = GF_N(bch); |
272 | return (v < n) ? v : v-n; |
273 | } |
274 | |
275 | static inline int deg(unsigned int poly) |
276 | { |
277 | /* polynomial degree is the most-significant bit index */ |
278 | return fls(poly)-1; |
279 | } |
280 | |
281 | static inline int parity(unsigned int x) |
282 | { |
283 | /* |
284 | * public domain code snippet, lifted from |
285 | * http://www-graphics.stanford.edu/~seander/bithacks.html |
286 | */ |
287 | x ^= x >> 1; |
288 | x ^= x >> 2; |
289 | x = (x & 0x11111111U) * 0x11111111U; |
290 | return (x >> 28) & 1; |
291 | } |
292 | |
293 | /* Galois field basic operations: multiply, divide, inverse, etc. */ |
294 | |
295 | static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, |
296 | unsigned int b) |
297 | { |
298 | return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ |
299 | bch->a_log_tab[b])] : 0; |
300 | } |
301 | |
302 | static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) |
303 | { |
304 | return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; |
305 | } |
306 | |
307 | static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, |
308 | unsigned int b) |
309 | { |
310 | return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ |
311 | GF_N(bch)-bch->a_log_tab[b])] : 0; |
312 | } |
313 | |
314 | static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) |
315 | { |
316 | return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; |
317 | } |
318 | |
319 | static inline unsigned int a_pow(struct bch_control *bch, int i) |
320 | { |
321 | return bch->a_pow_tab[modulo(bch, i)]; |
322 | } |
323 | |
324 | static inline int a_log(struct bch_control *bch, unsigned int x) |
325 | { |
326 | return bch->a_log_tab[x]; |
327 | } |
328 | |
329 | static inline int a_ilog(struct bch_control *bch, unsigned int x) |
330 | { |
331 | return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); |
332 | } |
333 | |
334 | /* |
335 | * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t |
336 | */ |
337 | static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, |
338 | unsigned int *syn) |
339 | { |
340 | int i, j, s; |
341 | unsigned int m; |
342 | uint32_t poly; |
343 | const int t = GF_T(bch); |
344 | |
345 | s = bch->ecc_bits; |
346 | |
347 | /* make sure extra bits in last ecc word are cleared */ |
348 | m = ((unsigned int)s) & 31; |
349 | if (m) |
350 | ecc[s/32] &= ~((1u << (32-m))-1); |
351 | memset(syn, 0, 2*t*sizeof(*syn)); |
352 | |
353 | /* compute v(a^j) for j=1 .. 2t-1 */ |
354 | do { |
355 | poly = *ecc++; |
356 | s -= 32; |
357 | while (poly) { |
358 | i = deg(poly); |
359 | for (j = 0; j < 2*t; j += 2) |
360 | syn[j] ^= a_pow(bch, (j+1)*(i+s)); |
361 | |
362 | poly ^= (1 << i); |
363 | } |
364 | } while (s > 0); |
365 | |
366 | /* v(a^(2j)) = v(a^j)^2 */ |
367 | for (j = 0; j < t; j++) |
368 | syn[2*j+1] = gf_sqr(bch, syn[j]); |
369 | } |
370 | |
371 | static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) |
372 | { |
373 | memcpy(dst, src, GF_POLY_SZ(src->deg)); |
374 | } |
375 | |
376 | static int compute_error_locator_polynomial(struct bch_control *bch, |
377 | const unsigned int *syn) |
378 | { |
379 | const unsigned int t = GF_T(bch); |
380 | const unsigned int n = GF_N(bch); |
381 | unsigned int i, j, tmp, l, pd = 1, d = syn[0]; |
382 | struct gf_poly *elp = bch->elp; |
383 | struct gf_poly *pelp = bch->poly_2t[0]; |
384 | struct gf_poly *elp_copy = bch->poly_2t[1]; |
385 | int k, pp = -1; |
386 | |
387 | memset(pelp, 0, GF_POLY_SZ(2*t)); |
388 | memset(elp, 0, GF_POLY_SZ(2*t)); |
389 | |
390 | pelp->deg = 0; |
391 | pelp->c[0] = 1; |
392 | elp->deg = 0; |
393 | elp->c[0] = 1; |
394 | |
395 | /* use simplified binary Berlekamp-Massey algorithm */ |
396 | for (i = 0; (i < t) && (elp->deg <= t); i++) { |
397 | if (d) { |
398 | k = 2*i-pp; |
399 | gf_poly_copy(elp_copy, elp); |
400 | /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ |
401 | tmp = a_log(bch, d)+n-a_log(bch, pd); |
402 | for (j = 0; j <= pelp->deg; j++) { |
403 | if (pelp->c[j]) { |
404 | l = a_log(bch, pelp->c[j]); |
405 | elp->c[j+k] ^= a_pow(bch, tmp+l); |
406 | } |
407 | } |
408 | /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ |
409 | tmp = pelp->deg+k; |
410 | if (tmp > elp->deg) { |
411 | elp->deg = tmp; |
412 | gf_poly_copy(pelp, elp_copy); |
413 | pd = d; |
414 | pp = 2*i; |
415 | } |
416 | } |
417 | /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ |
418 | if (i < t-1) { |
419 | d = syn[2*i+2]; |
420 | for (j = 1; j <= elp->deg; j++) |
421 | d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); |
422 | } |
423 | } |
424 | dbg("elp=%s\n", gf_poly_str(elp)); |
425 | return (elp->deg > t) ? -1 : (int)elp->deg; |
426 | } |
427 | |
428 | /* |
429 | * solve a m x m linear system in GF(2) with an expected number of solutions, |
430 | * and return the number of found solutions |
431 | */ |
432 | static int solve_linear_system(struct bch_control *bch, unsigned int *rows, |
433 | unsigned int *sol, int nsol) |
434 | { |
435 | const int m = GF_M(bch); |
436 | unsigned int tmp, mask; |
437 | int rem, c, r, p, k, param[m]; |
438 | |
439 | k = 0; |
440 | mask = 1 << m; |
441 | |
442 | /* Gaussian elimination */ |
443 | for (c = 0; c < m; c++) { |
444 | rem = 0; |
445 | p = c-k; |
446 | /* find suitable row for elimination */ |
447 | for (r = p; r < m; r++) { |
448 | if (rows[r] & mask) { |
449 | if (r != p) { |
450 | tmp = rows[r]; |
451 | rows[r] = rows[p]; |
452 | rows[p] = tmp; |
453 | } |
454 | rem = r+1; |
455 | break; |
456 | } |
457 | } |
458 | if (rem) { |
459 | /* perform elimination on remaining rows */ |
460 | tmp = rows[p]; |
461 | for (r = rem; r < m; r++) { |
462 | if (rows[r] & mask) |
463 | rows[r] ^= tmp; |
464 | } |
465 | } else { |
466 | /* elimination not needed, store defective row index */ |
467 | param[k++] = c; |
468 | } |
469 | mask >>= 1; |
470 | } |
471 | /* rewrite system, inserting fake parameter rows */ |
472 | if (k > 0) { |
473 | p = k; |
474 | for (r = m-1; r >= 0; r--) { |
475 | if ((r > m-1-k) && rows[r]) |
476 | /* system has no solution */ |
477 | return 0; |
478 | |
479 | rows[r] = (p && (r == param[p-1])) ? |
480 | p--, 1u << (m-r) : rows[r-p]; |
481 | } |
482 | } |
483 | |
484 | if (nsol != (1 << k)) |
485 | /* unexpected number of solutions */ |
486 | return 0; |
487 | |
488 | for (p = 0; p < nsol; p++) { |
489 | /* set parameters for p-th solution */ |
490 | for (c = 0; c < k; c++) |
491 | rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1); |
492 | |
493 | /* compute unique solution */ |
494 | tmp = 0; |
495 | for (r = m-1; r >= 0; r--) { |
496 | mask = rows[r] & (tmp|1); |
497 | tmp |= parity(mask) << (m-r); |
498 | } |
499 | sol[p] = tmp >> 1; |
500 | } |
501 | return nsol; |
502 | } |
503 | |
504 | /* |
505 | * this function builds and solves a linear system for finding roots of a degree |
506 | * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). |
507 | */ |
508 | static int find_affine4_roots(struct bch_control *bch, unsigned int a, |
509 | unsigned int b, unsigned int c, |
510 | unsigned int *roots) |
511 | { |
512 | int i, j, k; |
513 | const int m = GF_M(bch); |
514 | unsigned int mask = 0xff, t, rows[16] = {0,}; |
515 | |
516 | j = a_log(bch, b); |
517 | k = a_log(bch, a); |
518 | rows[0] = c; |
519 | |
520 | /* buid linear system to solve X^4+aX^2+bX+c = 0 */ |
521 | for (i = 0; i < m; i++) { |
522 | rows[i+1] = bch->a_pow_tab[4*i]^ |
523 | (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ |
524 | (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); |
525 | j++; |
526 | k += 2; |
527 | } |
528 | /* |
529 | * transpose 16x16 matrix before passing it to linear solver |
530 | * warning: this code assumes m < 16 |
531 | */ |
532 | for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { |
533 | for (k = 0; k < 16; k = (k+j+1) & ~j) { |
534 | t = ((rows[k] >> j)^rows[k+j]) & mask; |
535 | rows[k] ^= (t << j); |
536 | rows[k+j] ^= t; |
537 | } |
538 | } |
539 | return solve_linear_system(bch, rows, roots, 4); |
540 | } |
541 | |
542 | /* |
543 | * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) |
544 | */ |
545 | static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, |
546 | unsigned int *roots) |
547 | { |
548 | int n = 0; |
549 | |
550 | if (poly->c[0]) |
551 | /* poly[X] = bX+c with c!=0, root=c/b */ |
552 | roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ |
553 | bch->a_log_tab[poly->c[1]]); |
554 | return n; |
555 | } |
556 | |
557 | /* |
558 | * compute roots of a degree 2 polynomial over GF(2^m) |
559 | */ |
560 | static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, |
561 | unsigned int *roots) |
562 | { |
563 | int n = 0, i, l0, l1, l2; |
564 | unsigned int u, v, r; |
565 | |
566 | if (poly->c[0] && poly->c[1]) { |
567 | |
568 | l0 = bch->a_log_tab[poly->c[0]]; |
569 | l1 = bch->a_log_tab[poly->c[1]]; |
570 | l2 = bch->a_log_tab[poly->c[2]]; |
571 | |
572 | /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */ |
573 | u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); |
574 | /* |
575 | * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): |
576 | * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) = |
577 | * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u) |
578 | * i.e. r and r+1 are roots iff Tr(u)=0 |
579 | */ |
580 | r = 0; |
581 | v = u; |
582 | while (v) { |
583 | i = deg(v); |
584 | r ^= bch->xi_tab[i]; |
585 | v ^= (1 << i); |
586 | } |
587 | /* verify root */ |
588 | if ((gf_sqr(bch, r)^r) == u) { |
589 | /* reverse z=a/bX transformation and compute log(1/r) */ |
590 | roots[n++] = modulo(bch, 2*GF_N(bch)-l1- |
591 | bch->a_log_tab[r]+l2); |
592 | roots[n++] = modulo(bch, 2*GF_N(bch)-l1- |
593 | bch->a_log_tab[r^1]+l2); |
594 | } |
595 | } |
596 | return n; |
597 | } |
598 | |
599 | /* |
600 | * compute roots of a degree 3 polynomial over GF(2^m) |
601 | */ |
602 | static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, |
603 | unsigned int *roots) |
604 | { |
605 | int i, n = 0; |
606 | unsigned int a, b, c, a2, b2, c2, e3, tmp[4]; |
607 | |
608 | if (poly->c[0]) { |
609 | /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */ |
610 | e3 = poly->c[3]; |
611 | c2 = gf_div(bch, poly->c[0], e3); |
612 | b2 = gf_div(bch, poly->c[1], e3); |
613 | a2 = gf_div(bch, poly->c[2], e3); |
614 | |
615 | /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */ |
616 | c = gf_mul(bch, a2, c2); /* c = a2c2 */ |
617 | b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ |
618 | a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ |
619 | |
620 | /* find the 4 roots of this affine polynomial */ |
621 | if (find_affine4_roots(bch, a, b, c, tmp) == 4) { |
622 | /* remove a2 from final list of roots */ |
623 | for (i = 0; i < 4; i++) { |
624 | if (tmp[i] != a2) |
625 | roots[n++] = a_ilog(bch, tmp[i]); |
626 | } |
627 | } |
628 | } |
629 | return n; |
630 | } |
631 | |
632 | /* |
633 | * compute roots of a degree 4 polynomial over GF(2^m) |
634 | */ |
635 | static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, |
636 | unsigned int *roots) |
637 | { |
638 | int i, l, n = 0; |
639 | unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; |
640 | |
641 | if (poly->c[0] == 0) |
642 | return 0; |
643 | |
644 | /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */ |
645 | e4 = poly->c[4]; |
646 | d = gf_div(bch, poly->c[0], e4); |
647 | c = gf_div(bch, poly->c[1], e4); |
648 | b = gf_div(bch, poly->c[2], e4); |
649 | a = gf_div(bch, poly->c[3], e4); |
650 | |
651 | /* use Y=1/X transformation to get an affine polynomial */ |
652 | if (a) { |
653 | /* first, eliminate cX by using z=X+e with ae^2+c=0 */ |
654 | if (c) { |
655 | /* compute e such that e^2 = c/a */ |
656 | f = gf_div(bch, c, a); |
657 | l = a_log(bch, f); |
658 | l += (l & 1) ? GF_N(bch) : 0; |
659 | e = a_pow(bch, l/2); |
660 | /* |
661 | * use transformation z=X+e: |
662 | * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d |
663 | * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d |
664 | * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d |
665 | * z^4 + az^3 + b'z^2 + d' |
666 | */ |
667 | d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; |
668 | b = gf_mul(bch, a, e)^b; |
669 | } |
670 | /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */ |
671 | if (d == 0) |
672 | /* assume all roots have multiplicity 1 */ |
673 | return 0; |
674 | |
675 | c2 = gf_inv(bch, d); |
676 | b2 = gf_div(bch, a, d); |
677 | a2 = gf_div(bch, b, d); |
678 | } else { |
679 | /* polynomial is already affine */ |
680 | c2 = d; |
681 | b2 = c; |
682 | a2 = b; |
683 | } |
684 | /* find the 4 roots of this affine polynomial */ |
685 | if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { |
686 | for (i = 0; i < 4; i++) { |
687 | /* post-process roots (reverse transformations) */ |
688 | f = a ? gf_inv(bch, roots[i]) : roots[i]; |
689 | roots[i] = a_ilog(bch, f^e); |
690 | } |
691 | n = 4; |
692 | } |
693 | return n; |
694 | } |
695 | |
696 | /* |
697 | * build monic, log-based representation of a polynomial |
698 | */ |
699 | static void gf_poly_logrep(struct bch_control *bch, |
700 | const struct gf_poly *a, int *rep) |
701 | { |
702 | int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); |
703 | |
704 | /* represent 0 values with -1; warning, rep[d] is not set to 1 */ |
705 | for (i = 0; i < d; i++) |
706 | rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; |
707 | } |
708 | |
709 | /* |
710 | * compute polynomial Euclidean division remainder in GF(2^m)[X] |
711 | */ |
712 | static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, |
713 | const struct gf_poly *b, int *rep) |
714 | { |
715 | int la, p, m; |
716 | unsigned int i, j, *c = a->c; |
717 | const unsigned int d = b->deg; |
718 | |
719 | if (a->deg < d) |
720 | return; |
721 | |
722 | /* reuse or compute log representation of denominator */ |
723 | if (!rep) { |
724 | rep = bch->cache; |
725 | gf_poly_logrep(bch, b, rep); |
726 | } |
727 | |
728 | for (j = a->deg; j >= d; j--) { |
729 | if (c[j]) { |
730 | la = a_log(bch, c[j]); |
731 | p = j-d; |
732 | for (i = 0; i < d; i++, p++) { |
733 | m = rep[i]; |
734 | if (m >= 0) |
735 | c[p] ^= bch->a_pow_tab[mod_s(bch, |
736 | m+la)]; |
737 | } |
738 | } |
739 | } |
740 | a->deg = d-1; |
741 | while (!c[a->deg] && a->deg) |
742 | a->deg--; |
743 | } |
744 | |
745 | /* |
746 | * compute polynomial Euclidean division quotient in GF(2^m)[X] |
747 | */ |
748 | static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, |
749 | const struct gf_poly *b, struct gf_poly *q) |
750 | { |
751 | if (a->deg >= b->deg) { |
752 | q->deg = a->deg-b->deg; |
753 | /* compute a mod b (modifies a) */ |
754 | gf_poly_mod(bch, a, b, NULL); |
755 | /* quotient is stored in upper part of polynomial a */ |
756 | memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); |
757 | } else { |
758 | q->deg = 0; |
759 | q->c[0] = 0; |
760 | } |
761 | } |
762 | |
763 | /* |
764 | * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] |
765 | */ |
766 | static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, |
767 | struct gf_poly *b) |
768 | { |
769 | struct gf_poly *tmp; |
770 | |
771 | dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b)); |
772 | |
773 | if (a->deg < b->deg) { |
774 | tmp = b; |
775 | b = a; |
776 | a = tmp; |
777 | } |
778 | |
779 | while (b->deg > 0) { |
780 | gf_poly_mod(bch, a, b, NULL); |
781 | tmp = b; |
782 | b = a; |
783 | a = tmp; |
784 | } |
785 | |
786 | dbg("%s\n", gf_poly_str(a)); |
787 | |
788 | return a; |
789 | } |
790 | |
791 | /* |
792 | * Given a polynomial f and an integer k, compute Tr(a^kX) mod f |
793 | * This is used in Berlekamp Trace algorithm for splitting polynomials |
794 | */ |
795 | static void compute_trace_bk_mod(struct bch_control *bch, int k, |
796 | const struct gf_poly *f, struct gf_poly *z, |
797 | struct gf_poly *out) |
798 | { |
799 | const int m = GF_M(bch); |
800 | int i, j; |
801 | |
802 | /* z contains z^2j mod f */ |
803 | z->deg = 1; |
804 | z->c[0] = 0; |
805 | z->c[1] = bch->a_pow_tab[k]; |
806 | |
807 | out->deg = 0; |
808 | memset(out, 0, GF_POLY_SZ(f->deg)); |
809 | |
810 | /* compute f log representation only once */ |
811 | gf_poly_logrep(bch, f, bch->cache); |
812 | |
813 | for (i = 0; i < m; i++) { |
814 | /* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */ |
815 | for (j = z->deg; j >= 0; j--) { |
816 | out->c[j] ^= z->c[j]; |
817 | z->c[2*j] = gf_sqr(bch, z->c[j]); |
818 | z->c[2*j+1] = 0; |
819 | } |
820 | if (z->deg > out->deg) |
821 | out->deg = z->deg; |
822 | |
823 | if (i < m-1) { |
824 | z->deg *= 2; |
825 | /* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */ |
826 | gf_poly_mod(bch, z, f, bch->cache); |
827 | } |
828 | } |
829 | while (!out->c[out->deg] && out->deg) |
830 | out->deg--; |
831 | |
832 | dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out)); |
833 | } |
834 | |
835 | /* |
836 | * factor a polynomial using Berlekamp Trace algorithm (BTA) |
837 | */ |
838 | static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, |
839 | struct gf_poly **g, struct gf_poly **h) |
840 | { |
841 | struct gf_poly *f2 = bch->poly_2t[0]; |
842 | struct gf_poly *q = bch->poly_2t[1]; |
843 | struct gf_poly *tk = bch->poly_2t[2]; |
844 | struct gf_poly *z = bch->poly_2t[3]; |
845 | struct gf_poly *gcd; |
846 | |
847 | dbg("factoring %s...\n", gf_poly_str(f)); |
848 | |
849 | *g = f; |
850 | *h = NULL; |
851 | |
852 | /* tk = Tr(a^k.X) mod f */ |
853 | compute_trace_bk_mod(bch, k, f, z, tk); |
854 | |
855 | if (tk->deg > 0) { |
856 | /* compute g = gcd(f, tk) (destructive operation) */ |
857 | gf_poly_copy(f2, f); |
858 | gcd = gf_poly_gcd(bch, f2, tk); |
859 | if (gcd->deg < f->deg) { |
860 | /* compute h=f/gcd(f,tk); this will modify f and q */ |
861 | gf_poly_div(bch, f, gcd, q); |
862 | /* store g and h in-place (clobbering f) */ |
863 | *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; |
864 | gf_poly_copy(*g, gcd); |
865 | gf_poly_copy(*h, q); |
866 | } |
867 | } |
868 | } |
869 | |
870 | /* |
871 | * find roots of a polynomial, using BTZ algorithm; see the beginning of this |
872 | * file for details |
873 | */ |
874 | static int find_poly_roots(struct bch_control *bch, unsigned int k, |
875 | struct gf_poly *poly, unsigned int *roots) |
876 | { |
877 | int cnt; |
878 | struct gf_poly *f1, *f2; |
879 | |
880 | switch (poly->deg) { |
881 | /* handle low degree polynomials with ad hoc techniques */ |
882 | case 1: |
883 | cnt = find_poly_deg1_roots(bch, poly, roots); |
884 | break; |
885 | case 2: |
886 | cnt = find_poly_deg2_roots(bch, poly, roots); |
887 | break; |
888 | case 3: |
889 | cnt = find_poly_deg3_roots(bch, poly, roots); |
890 | break; |
891 | case 4: |
892 | cnt = find_poly_deg4_roots(bch, poly, roots); |
893 | break; |
894 | default: |
895 | /* factor polynomial using Berlekamp Trace Algorithm (BTA) */ |
896 | cnt = 0; |
897 | if (poly->deg && (k <= GF_M(bch))) { |
898 | factor_polynomial(bch, k, poly, &f1, &f2); |
899 | if (f1) |
900 | cnt += find_poly_roots(bch, k+1, f1, roots); |
901 | if (f2) |
902 | cnt += find_poly_roots(bch, k+1, f2, roots+cnt); |
903 | } |
904 | break; |
905 | } |
906 | return cnt; |
907 | } |
908 | |
909 | #if defined(USE_CHIEN_SEARCH) |
910 | /* |
911 | * exhaustive root search (Chien) implementation - not used, included only for |
912 | * reference/comparison tests |
913 | */ |
914 | static int chien_search(struct bch_control *bch, unsigned int len, |
915 | struct gf_poly *p, unsigned int *roots) |
916 | { |
917 | int m; |
918 | unsigned int i, j, syn, syn0, count = 0; |
919 | const unsigned int k = 8*len+bch->ecc_bits; |
920 | |
921 | /* use a log-based representation of polynomial */ |
922 | gf_poly_logrep(bch, p, bch->cache); |
923 | bch->cache[p->deg] = 0; |
924 | syn0 = gf_div(bch, p->c[0], p->c[p->deg]); |
925 | |
926 | for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { |
927 | /* compute elp(a^i) */ |
928 | for (j = 1, syn = syn0; j <= p->deg; j++) { |
929 | m = bch->cache[j]; |
930 | if (m >= 0) |
931 | syn ^= a_pow(bch, m+j*i); |
932 | } |
933 | if (syn == 0) { |
934 | roots[count++] = GF_N(bch)-i; |
935 | if (count == p->deg) |
936 | break; |
937 | } |
938 | } |
939 | return (count == p->deg) ? count : 0; |
940 | } |
941 | #define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc) |
942 | #endif /* USE_CHIEN_SEARCH */ |
943 | |
944 | /** |
945 | * decode_bch - decode received codeword and find bit error locations |
946 | * @bch: BCH control structure |
947 | * @data: received data, ignored if @calc_ecc is provided |
948 | * @len: data length in bytes, must always be provided |
949 | * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc |
950 | * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data |
951 | * @syn: hw computed syndrome data (if NULL, syndrome is calculated) |
952 | * @errloc: output array of error locations |
953 | * |
954 | * Returns: |
955 | * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if |
956 | * invalid parameters were provided |
957 | * |
958 | * Depending on the available hw BCH support and the need to compute @calc_ecc |
959 | * separately (using encode_bch()), this function should be called with one of |
960 | * the following parameter configurations - |
961 | * |
962 | * by providing @data and @recv_ecc only: |
963 | * decode_bch(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc) |
964 | * |
965 | * by providing @recv_ecc and @calc_ecc: |
966 | * decode_bch(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc) |
967 | * |
968 | * by providing ecc = recv_ecc XOR calc_ecc: |
969 | * decode_bch(@bch, NULL, @len, NULL, ecc, NULL, @errloc) |
970 | * |
971 | * by providing syndrome results @syn: |
972 | * decode_bch(@bch, NULL, @len, NULL, NULL, @syn, @errloc) |
973 | * |
974 | * Once decode_bch() has successfully returned with a positive value, error |
975 | * locations returned in array @errloc should be interpreted as follows - |
976 | * |
977 | * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for |
978 | * data correction) |
979 | * |
980 | * if (errloc[n] < 8*len), then n-th error is located in data and can be |
981 | * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8); |
982 | * |
983 | * Note that this function does not perform any data correction by itself, it |
984 | * merely indicates error locations. |
985 | */ |
986 | int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, |
987 | const uint8_t *recv_ecc, const uint8_t *calc_ecc, |
988 | const unsigned int *syn, unsigned int *errloc) |
989 | { |
990 | const unsigned int ecc_words = BCH_ECC_WORDS(bch); |
991 | unsigned int nbits; |
992 | int i, err, nroots; |
993 | uint32_t sum; |
994 | |
995 | /* sanity check: make sure data length can be handled */ |
996 | if (8*len > (bch->n-bch->ecc_bits)) |
997 | return -EINVAL; |
998 | |
999 | /* if caller does not provide syndromes, compute them */ |
1000 | if (!syn) { |
1001 | if (!calc_ecc) { |
1002 | /* compute received data ecc into an internal buffer */ |
1003 | if (!data || !recv_ecc) |
1004 | return -EINVAL; |
1005 | encode_bch(bch, data, len, NULL); |
1006 | } else { |
1007 | /* load provided calculated ecc */ |
1008 | load_ecc8(bch, bch->ecc_buf, calc_ecc); |
1009 | } |
1010 | /* load received ecc or assume it was XORed in calc_ecc */ |
1011 | if (recv_ecc) { |
1012 | load_ecc8(bch, bch->ecc_buf2, recv_ecc); |
1013 | /* XOR received and calculated ecc */ |
1014 | for (i = 0, sum = 0; i < (int)ecc_words; i++) { |
1015 | bch->ecc_buf[i] ^= bch->ecc_buf2[i]; |
1016 | sum |= bch->ecc_buf[i]; |
1017 | } |
1018 | if (!sum) |
1019 | /* no error found */ |
1020 | return 0; |
1021 | } |
1022 | compute_syndromes(bch, bch->ecc_buf, bch->syn); |
1023 | syn = bch->syn; |
1024 | } |
1025 | |
1026 | err = compute_error_locator_polynomial(bch, syn); |
1027 | if (err > 0) { |
1028 | nroots = find_poly_roots(bch, 1, bch->elp, errloc); |
1029 | if (err != nroots) |
1030 | err = -1; |
1031 | } |
1032 | if (err > 0) { |
1033 | /* post-process raw error locations for easier correction */ |
1034 | nbits = (len*8)+bch->ecc_bits; |
1035 | for (i = 0; i < err; i++) { |
1036 | if (errloc[i] >= nbits) { |
1037 | err = -1; |
1038 | break; |
1039 | } |
1040 | errloc[i] = nbits-1-errloc[i]; |
1041 | errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7)); |
1042 | } |
1043 | } |
1044 | return (err >= 0) ? err : -EBADMSG; |
1045 | } |
1046 | EXPORT_SYMBOL_GPL(decode_bch); |
1047 | |
1048 | /* |
1049 | * generate Galois field lookup tables |
1050 | */ |
1051 | static int build_gf_tables(struct bch_control *bch, unsigned int poly) |
1052 | { |
1053 | unsigned int i, x = 1; |
1054 | const unsigned int k = 1 << deg(poly); |
1055 | |
1056 | /* primitive polynomial must be of degree m */ |
1057 | if (k != (1u << GF_M(bch))) |
1058 | return -1; |
1059 | |
1060 | for (i = 0; i < GF_N(bch); i++) { |
1061 | bch->a_pow_tab[i] = x; |
1062 | bch->a_log_tab[x] = i; |
1063 | if (i && (x == 1)) |
1064 | /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */ |
1065 | return -1; |
1066 | x <<= 1; |
1067 | if (x & k) |
1068 | x ^= poly; |
1069 | } |
1070 | bch->a_pow_tab[GF_N(bch)] = 1; |
1071 | bch->a_log_tab[0] = 0; |
1072 | |
1073 | return 0; |
1074 | } |
1075 | |
1076 | /* |
1077 | * compute generator polynomial remainder tables for fast encoding |
1078 | */ |
1079 | static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) |
1080 | { |
1081 | int i, j, b, d; |
1082 | uint32_t data, hi, lo, *tab; |
1083 | const int l = BCH_ECC_WORDS(bch); |
1084 | const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32); |
1085 | const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32); |
1086 | |
1087 | memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); |
1088 | |
1089 | for (i = 0; i < 256; i++) { |
1090 | /* p(X)=i is a small polynomial of weight <= 8 */ |
1091 | for (b = 0; b < 4; b++) { |
1092 | /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */ |
1093 | tab = bch->mod8_tab + (b*256+i)*l; |
1094 | data = i << (8*b); |
1095 | while (data) { |
1096 | d = deg(data); |
1097 | /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */ |
1098 | data ^= g[0] >> (31-d); |
1099 | for (j = 0; j < ecclen; j++) { |
1100 | hi = (d < 31) ? g[j] << (d+1) : 0; |
1101 | lo = (j+1 < plen) ? |
1102 | g[j+1] >> (31-d) : 0; |
1103 | tab[j] ^= hi|lo; |
1104 | } |
1105 | } |
1106 | } |
1107 | } |
1108 | } |
1109 | |
1110 | /* |
1111 | * build a base for factoring degree 2 polynomials |
1112 | */ |
1113 | static int build_deg2_base(struct bch_control *bch) |
1114 | { |
1115 | const int m = GF_M(bch); |
1116 | int i, j, r; |
1117 | unsigned int sum, x, y, remaining, ak = 0, xi[m]; |
1118 | |
1119 | /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */ |
1120 | for (i = 0; i < m; i++) { |
1121 | for (j = 0, sum = 0; j < m; j++) |
1122 | sum ^= a_pow(bch, i*(1 << j)); |
1123 | |
1124 | if (sum) { |
1125 | ak = bch->a_pow_tab[i]; |
1126 | break; |
1127 | } |
1128 | } |
1129 | /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ |
1130 | remaining = m; |
1131 | memset(xi, 0, sizeof(xi)); |
1132 | |
1133 | for (x = 0; (x <= GF_N(bch)) && remaining; x++) { |
1134 | y = gf_sqr(bch, x)^x; |
1135 | for (i = 0; i < 2; i++) { |
1136 | r = a_log(bch, y); |
1137 | if (y && (r < m) && !xi[r]) { |
1138 | bch->xi_tab[r] = x; |
1139 | xi[r] = 1; |
1140 | remaining--; |
1141 | dbg("x%d = %x\n", r, x); |
1142 | break; |
1143 | } |
1144 | y ^= ak; |
1145 | } |
1146 | } |
1147 | /* should not happen but check anyway */ |
1148 | return remaining ? -1 : 0; |
1149 | } |
1150 | |
1151 | static void *bch_alloc(size_t size, int *err) |
1152 | { |
1153 | void *ptr; |
1154 | |
1155 | ptr = kmalloc(size, GFP_KERNEL); |
1156 | if (ptr == NULL) |
1157 | *err = 1; |
1158 | return ptr; |
1159 | } |
1160 | |
1161 | /* |
1162 | * compute generator polynomial for given (m,t) parameters. |
1163 | */ |
1164 | static uint32_t *compute_generator_polynomial(struct bch_control *bch) |
1165 | { |
1166 | const unsigned int m = GF_M(bch); |
1167 | const unsigned int t = GF_T(bch); |
1168 | int n, err = 0; |
1169 | unsigned int i, j, nbits, r, word, *roots; |
1170 | struct gf_poly *g; |
1171 | uint32_t *genpoly; |
1172 | |
1173 | g = bch_alloc(GF_POLY_SZ(m*t), &err); |
1174 | roots = bch_alloc((bch->n+1)*sizeof(*roots), &err); |
1175 | genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err); |
1176 | |
1177 | if (err) { |
1178 | kfree(genpoly); |
1179 | genpoly = NULL; |
1180 | goto finish; |
1181 | } |
1182 | |
1183 | /* enumerate all roots of g(X) */ |
1184 | memset(roots , 0, (bch->n+1)*sizeof(*roots)); |
1185 | for (i = 0; i < t; i++) { |
1186 | for (j = 0, r = 2*i+1; j < m; j++) { |
1187 | roots[r] = 1; |
1188 | r = mod_s(bch, 2*r); |
1189 | } |
1190 | } |
1191 | /* build generator polynomial g(X) */ |
1192 | g->deg = 0; |
1193 | g->c[0] = 1; |
1194 | for (i = 0; i < GF_N(bch); i++) { |
1195 | if (roots[i]) { |
1196 | /* multiply g(X) by (X+root) */ |
1197 | r = bch->a_pow_tab[i]; |
1198 | g->c[g->deg+1] = 1; |
1199 | for (j = g->deg; j > 0; j--) |
1200 | g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1]; |
1201 | |
1202 | g->c[0] = gf_mul(bch, g->c[0], r); |
1203 | g->deg++; |
1204 | } |
1205 | } |
1206 | /* store left-justified binary representation of g(X) */ |
1207 | n = g->deg+1; |
1208 | i = 0; |
1209 | |
1210 | while (n > 0) { |
1211 | nbits = (n > 32) ? 32 : n; |
1212 | for (j = 0, word = 0; j < nbits; j++) { |
1213 | if (g->c[n-1-j]) |
1214 | word |= 1u << (31-j); |
1215 | } |
1216 | genpoly[i++] = word; |
1217 | n -= nbits; |
1218 | } |
1219 | bch->ecc_bits = g->deg; |
1220 | |
1221 | finish: |
1222 | kfree(g); |
1223 | kfree(roots); |
1224 | |
1225 | return genpoly; |
1226 | } |
1227 | |
1228 | /** |
1229 | * init_bch - initialize a BCH encoder/decoder |
1230 | * @m: Galois field order, should be in the range 5-15 |
1231 | * @t: maximum error correction capability, in bits |
1232 | * @prim_poly: user-provided primitive polynomial (or 0 to use default) |
1233 | * |
1234 | * Returns: |
1235 | * a newly allocated BCH control structure if successful, NULL otherwise |
1236 | * |
1237 | * This initialization can take some time, as lookup tables are built for fast |
1238 | * encoding/decoding; make sure not to call this function from a time critical |
1239 | * path. Usually, init_bch() should be called on module/driver init and |
1240 | * free_bch() should be called to release memory on exit. |
1241 | * |
1242 | * You may provide your own primitive polynomial of degree @m in argument |
1243 | * @prim_poly, or let init_bch() use its default polynomial. |
1244 | * |
1245 | * Once init_bch() has successfully returned a pointer to a newly allocated |
1246 | * BCH control structure, ecc length in bytes is given by member @ecc_bytes of |
1247 | * the structure. |
1248 | */ |
1249 | struct bch_control *init_bch(int m, int t, unsigned int prim_poly) |
1250 | { |
1251 | int err = 0; |
1252 | unsigned int i, words; |
1253 | uint32_t *genpoly; |
1254 | struct bch_control *bch = NULL; |
1255 | |
1256 | const int min_m = 5; |
1257 | const int max_m = 15; |
1258 | |
1259 | /* default primitive polynomials */ |
1260 | static const unsigned int prim_poly_tab[] = { |
1261 | 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b, |
1262 | 0x402b, 0x8003, |
1263 | }; |
1264 | |
1265 | #if defined(CONFIG_BCH_CONST_PARAMS) |
1266 | if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) { |
1267 | printk(KERN_ERR "bch encoder/decoder was configured to support " |
1268 | "parameters m=%d, t=%d only!\n", |
1269 | CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T); |
1270 | goto fail; |
1271 | } |
1272 | #endif |
1273 | if ((m < min_m) || (m > max_m)) |
1274 | /* |
1275 | * values of m greater than 15 are not currently supported; |
1276 | * supporting m > 15 would require changing table base type |
1277 | * (uint16_t) and a small patch in matrix transposition |
1278 | */ |
1279 | goto fail; |
1280 | |
1281 | /* sanity checks */ |
1282 | if ((t < 1) || (m*t >= ((1 << m)-1))) |
1283 | /* invalid t value */ |
1284 | goto fail; |
1285 | |
1286 | /* select a primitive polynomial for generating GF(2^m) */ |
1287 | if (prim_poly == 0) |
1288 | prim_poly = prim_poly_tab[m-min_m]; |
1289 | |
1290 | bch = kzalloc(sizeof(*bch), GFP_KERNEL); |
1291 | if (bch == NULL) |
1292 | goto fail; |
1293 | |
1294 | bch->m = m; |
1295 | bch->t = t; |
1296 | bch->n = (1 << m)-1; |
1297 | words = DIV_ROUND_UP(m*t, 32); |
1298 | bch->ecc_bytes = DIV_ROUND_UP(m*t, 8); |
1299 | bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err); |
1300 | bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err); |
1301 | bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err); |
1302 | bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err); |
1303 | bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err); |
1304 | bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err); |
1305 | bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err); |
1306 | bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err); |
1307 | bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err); |
1308 | |
1309 | for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) |
1310 | bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err); |
1311 | |
1312 | if (err) |
1313 | goto fail; |
1314 | |
1315 | err = build_gf_tables(bch, prim_poly); |
1316 | if (err) |
1317 | goto fail; |
1318 | |
1319 | /* use generator polynomial for computing encoding tables */ |
1320 | genpoly = compute_generator_polynomial(bch); |
1321 | if (genpoly == NULL) |
1322 | goto fail; |
1323 | |
1324 | build_mod8_tables(bch, genpoly); |
1325 | kfree(genpoly); |
1326 | |
1327 | err = build_deg2_base(bch); |
1328 | if (err) |
1329 | goto fail; |
1330 | |
1331 | return bch; |
1332 | |
1333 | fail: |
1334 | free_bch(bch); |
1335 | return NULL; |
1336 | } |
1337 | EXPORT_SYMBOL_GPL(init_bch); |
1338 | |
1339 | /** |
1340 | * free_bch - free the BCH control structure |
1341 | * @bch: BCH control structure to release |
1342 | */ |
1343 | void free_bch(struct bch_control *bch) |
1344 | { |
1345 | unsigned int i; |
1346 | |
1347 | if (bch) { |
1348 | kfree(bch->a_pow_tab); |
1349 | kfree(bch->a_log_tab); |
1350 | kfree(bch->mod8_tab); |
1351 | kfree(bch->ecc_buf); |
1352 | kfree(bch->ecc_buf2); |
1353 | kfree(bch->xi_tab); |
1354 | kfree(bch->syn); |
1355 | kfree(bch->cache); |
1356 | kfree(bch->elp); |
1357 | |
1358 | for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) |
1359 | kfree(bch->poly_2t[i]); |
1360 | |
1361 | kfree(bch); |
1362 | } |
1363 | } |
1364 | EXPORT_SYMBOL_GPL(free_bch); |
1365 | |
1366 | MODULE_LICENSE("GPL"); |
1367 | MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>"); |
1368 | MODULE_DESCRIPTION("Binary BCH encoder/decoder"); |
1369 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9