aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig39
-rw-r--r--lib/Makefile1
-rw-r--r--lib/bch.c1368
3 files changed, 1408 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 23fa7a359db..9c10e38fc60 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -158,6 +158,45 @@ config REED_SOLOMON_DEC16
158 boolean 158 boolean
159 159
160# 160#
161# BCH support is selected if needed
162#
163config BCH
164 tristate
165
166config BCH_CONST_PARAMS
167 boolean
168 help
169 Drivers may select this option to force specific constant
170 values for parameters 'm' (Galois field order) and 't'
171 (error correction capability). Those specific values must
172 be set by declaring default values for symbols BCH_CONST_M
173 and BCH_CONST_T.
174 Doing so will enable extra compiler optimizations,
175 improving encoding and decoding performance up to 2x for
176 usual (m,t) values (typically such that m*t < 200).
177 When this option is selected, the BCH library supports
178 only a single (m,t) configuration. This is mainly useful
179 for NAND flash board drivers requiring known, fixed BCH
180 parameters.
181
182config BCH_CONST_M
183 int
184 range 5 15
185 help
186 Constant value for Galois field order 'm'. If 'k' is the
187 number of data bits to protect, 'm' should be chosen such
188 that (k + m*t) <= 2**m - 1.
189 Drivers should declare a default value for this symbol if
190 they select option BCH_CONST_PARAMS.
191
192config BCH_CONST_T
193 int
194 help
195 Constant value for error correction capability in bits 't'.
196 Drivers should declare a default value for this symbol if
197 they select option BCH_CONST_PARAMS.
198
199#
161# Textsearch support is select'ed if needed 200# Textsearch support is select'ed if needed
162# 201#
163config TEXTSEARCH 202config TEXTSEARCH
diff --git a/lib/Makefile b/lib/Makefile
index d7872b5c4c1..ef0f2857115 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -69,6 +69,7 @@ obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
69obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ 69obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
70obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ 70obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/
71obj-$(CONFIG_REED_SOLOMON) += reed_solomon/ 71obj-$(CONFIG_REED_SOLOMON) += reed_solomon/
72obj-$(CONFIG_BCH) += bch.o
72obj-$(CONFIG_LZO_COMPRESS) += lzo/ 73obj-$(CONFIG_LZO_COMPRESS) += lzo/
73obj-$(CONFIG_LZO_DECOMPRESS) += lzo/ 74obj-$(CONFIG_LZO_DECOMPRESS) += lzo/
74obj-$(CONFIG_XZ_DEC) += xz/ 75obj-$(CONFIG_XZ_DEC) += xz/
diff --git a/lib/bch.c b/lib/bch.c
new file mode 100644
index 00000000000..bc89dfe4d1b
--- /dev/null
+++ b/lib/bch.c
@@ -0,0 +1,1368 @@
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 */
97struct 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 */
106struct 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 */
114static 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 */
135static 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 */
151static 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 */
184void 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}
254EXPORT_SYMBOL_GPL(encode_bch);
255
256static 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 */
269static 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
275static inline int deg(unsigned int poly)
276{
277 /* polynomial degree is the most-significant bit index */
278 return fls(poly)-1;
279}
280
281static 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
295static 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
302static 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
307static 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
314static 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
319static inline unsigned int a_pow(struct bch_control *bch, int i)
320{
321 return bch->a_pow_tab[modulo(bch, i)];
322}
323
324static inline int a_log(struct bch_control *bch, unsigned int x)
325{
326 return bch->a_log_tab[x];
327}
328
329static 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 */
337static 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
371static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src)
372{
373 memcpy(dst, src, GF_POLY_SZ(src->deg));
374}
375
376static 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 */
432static 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 */
508static 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 */
545static 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 */
560static 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 */
602static 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 */
635static 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 */
699static 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 */
712static 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 */
748static 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 */
766static 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 */
795static 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 */
838static 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 */
874static 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 */
914static 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 */
986int 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}
1046EXPORT_SYMBOL_GPL(decode_bch);
1047
1048/*
1049 * generate Galois field lookup tables
1050 */
1051static 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 */
1079static 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 */
1113static 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
1151static 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 */
1164static 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
1221finish:
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 */
1249struct 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
1333fail:
1334 free_bch(bch);
1335 return NULL;
1336}
1337EXPORT_SYMBOL_GPL(init_bch);
1338
1339/**
1340 * free_bch - free the BCH control structure
1341 * @bch: BCH control structure to release
1342 */
1343void 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}
1364EXPORT_SYMBOL_GPL(free_bch);
1365
1366MODULE_LICENSE("GPL");
1367MODULE_AUTHOR("Ivan Djelic <ivan.djelic@parrot.com>");
1368MODULE_DESCRIPTION("Binary BCH encoder/decoder");
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-27 21:27:38 -0500