/*
* Generic binary BCH encoding/decoding library
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 as published by
* the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program; if not, write to the Free Software Foundation, Inc., 51
* Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Copyright © 2011 Parrot S.A.
*
* Author: Ivan Djelic <ivan.djelic@parrot.com>
*
* Description:
*
* This library provides runtime configurable encoding/decoding of binary
* Bose-Chaudhuri-Hocquenghem (BCH) codes.
*
* Call init_bch to get a pointer to a newly allocated bch_control structure for
* the given m (Galois field order), t (error correction capability) and
* (optional) primitive polynomial parameters.
*
* Call encode_bch to compute and store ecc parity bytes to a given buffer.
* Call decode_bch to detect and locate errors in received data.
*
* On systems supporting hw BCH features, intermediate results may be provided
* to decode_bch in order to skip certain steps. See decode_bch() documentation
* for details.
*
* Option CONFIG_BCH_CONST_PARAMS can be used to force fixed values of
* parameters m and t; thus allowing extra compiler optimizations and providing
* better (up to 2x) encoding performance. Using this option makes sense when
* (m,t) are fixed and known in advance, e.g. when using BCH error correction
* on a particular NAND flash device.
*
* Algorithmic details:
*
* Encoding is performed by processing 32 input bits in parallel, using 4
* remainder lookup tables.
*
* The final stage of decoding involves the following internal steps:
* a. Syndrome computation
* b. Error locator polynomial computation using Berlekamp-Massey algorithm
* c. Error locator root finding (by far the most expensive step)
*
* In this implementation, step c is not performed using the usual Chien search.
* Instead, an alternative approach described in [1] is used. It consists in
* factoring the error locator polynomial using the Berlekamp Trace algorithm
* (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial
* solving techniques [2] are used. The resulting algorithm, called BTZ, yields
* much better performance than Chien search for usual (m,t) values (typically
* m >= 13, t < 32, see [1]).
*
* [1] B. Biswas, V. Herbert. Efficient root finding of polynomials over fields
* of characteristic 2, in: Western European Workshop on Research in Cryptology
* - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear.
* [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over
* finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996.
*/
#include <linux/kernel.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/bitops.h>
#include <asm/byteorder.h>
#include <linux/bch.h>
#if defined(CONFIG_BCH_CONST_PARAMS)
#define GF_M(_p) (CONFIG_BCH_CONST_M)
#define GF_T(_p) (CONFIG_BCH_CONST_T)
#define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
#define BCH_MAX_M (CONFIG_BCH_CONST_M)
#define BCH_MAX_T (CONFIG_BCH_CONST_T)
#else
#define GF_M(_p) ((_p)->m)
#define GF_T(_p) ((_p)->t)
#define GF_N(_p) ((_p)->n)
#define BCH_MAX_M 15 /* 2KB */
#define BCH_MAX_T 64 /* 64 bit correction */
#endif
#define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32)
#define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8)
#define BCH_ECC_MAX_WORDS DIV_ROUND_UP(BCH_MAX_M * BCH_MAX_T, 32)
#ifndef dbg
#define dbg(_fmt, args...) do {} while (0)
#endif
/*
* represent a polynomial over GF(2^m)
*/
struct gf_poly {
unsigned int deg; /* polynomial degree */
unsigned int c[0]; /* polynomial terms */
};
/* given its degree, compute a polynomial size in bytes */
#define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int))
/* polynomial of degree 1 */
struct gf_poly_deg1 {
struct gf_poly poly;
unsigned int c[2];
};
/*
* same as encode_bch(), but process input data one byte at a time
*/
static void encode_bch_unaligned(struct bch_control *bch,
const unsigned char *data, unsigned int len,