Linux Audio

Check our new training course

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