/* * 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 <[email protected]> * * Description: * * This library provides runtime configurable encoding/decoding of binary * Bose-Chaudhuri-Hocquenghem (BCH) codes. * * Call bch_init 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 bch_encode to compute and store ecc parity bytes to a given buffer. * Call bch_decode to detect and locate errors in received data. * * On systems supporting hw BCH features, intermediate results may be provided * to bch_decode in order to skip certain steps. See bch_decode() 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 <linux/bitrev.h> #include <asm/byteorder.h> #include <linux/bch.h> #if defined(CONFIG_BCH_CONST_PARAMS) #define GF_M … #define GF_T … #define GF_N … #define BCH_MAX_M … #define BCH_MAX_T … #else #define GF_M(_p) … #define GF_T(_p) … #define GF_N(_p) … #define BCH_MAX_M … #define BCH_MAX_T … #endif #define BCH_ECC_WORDS(_p) … #define BCH_ECC_BYTES(_p) … #define BCH_ECC_MAX_WORDS … #ifndef dbg #define dbg(_fmt, args...) … #endif /* * represent a polynomial over GF(2^m) */ struct gf_poly { … }; /* given its degree, compute a polynomial size in bytes */ #define GF_POLY_SZ(_d) … /* polynomial of degree 1 */ struct gf_poly_deg1 { … }; static u8 swap_bits(struct bch_control *bch, u8 in) { … } /* * same as bch_encode(), but process input data one byte at a time */ static void bch_encode_unaligned(struct bch_control *bch, const unsigned char *data, unsigned int len, uint32_t *ecc) { … } /* * convert ecc bytes to aligned, zero-padded 32-bit ecc words */ static void load_ecc8(struct bch_control *bch, uint32_t *dst, const uint8_t *src) { … } /* * convert 32-bit ecc words to ecc bytes */ static void store_ecc8(struct bch_control *bch, uint8_t *dst, const uint32_t *src) { … } /** * bch_encode - calculate BCH ecc parity of data * @bch: BCH control structure * @data: data to encode * @len: data length in bytes * @ecc: ecc parity data, must be initialized by caller * * The @ecc parity array is used both as input and output parameter, in order to * allow incremental computations. It should be of the size indicated by member * @ecc_bytes of @bch, and should be initialized to 0 before the first call. * * The exact number of computed ecc parity bits is given by member @ecc_bits of * @bch; it may be less than m*t for large values of t. */ void bch_encode(struct bch_control *bch, const uint8_t *data, unsigned int len, uint8_t *ecc) { … } EXPORT_SYMBOL_GPL(…); static inline int modulo(struct bch_control *bch, unsigned int v) { … } /* * shorter and faster modulo function, only works when v < 2N. */ static inline int mod_s(struct bch_control *bch, unsigned int v) { … } static inline int deg(unsigned int poly) { … } static inline int parity(unsigned int x) { … } /* Galois field basic operations: multiply, divide, inverse, etc. */ static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, unsigned int b) { … } static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) { … } static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, unsigned int b) { … } static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) { … } static inline unsigned int a_pow(struct bch_control *bch, int i) { … } static inline int a_log(struct bch_control *bch, unsigned int x) { … } static inline int a_ilog(struct bch_control *bch, unsigned int x) { … } /* * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t */ static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, unsigned int *syn) { … } static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) { … } static int compute_error_locator_polynomial(struct bch_control *bch, const unsigned int *syn) { … } /* * solve a m x m linear system in GF(2) with an expected number of solutions, * and return the number of found solutions */ static int solve_linear_system(struct bch_control *bch, unsigned int *rows, unsigned int *sol, int nsol) { … } /* * this function builds and solves a linear system for finding roots of a degree * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). */ static int find_affine4_roots(struct bch_control *bch, unsigned int a, unsigned int b, unsigned int c, unsigned int *roots) { … } /* * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) */ static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { … } /* * compute roots of a degree 2 polynomial over GF(2^m) */ static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { … } /* * compute roots of a degree 3 polynomial over GF(2^m) */ static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { … } /* * compute roots of a degree 4 polynomial over GF(2^m) */ static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { … } /* * build monic, log-based representation of a polynomial */ static void gf_poly_logrep(struct bch_control *bch, const struct gf_poly *a, int *rep) { … } /* * compute polynomial Euclidean division remainder in GF(2^m)[X] */ static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, const struct gf_poly *b, int *rep) { … } /* * compute polynomial Euclidean division quotient in GF(2^m)[X] */ static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, const struct gf_poly *b, struct gf_poly *q) { … } /* * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] */ static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, struct gf_poly *b) { … } /* * Given a polynomial f and an integer k, compute Tr(a^kX) mod f * This is used in Berlekamp Trace algorithm for splitting polynomials */ static void compute_trace_bk_mod(struct bch_control *bch, int k, const struct gf_poly *f, struct gf_poly *z, struct gf_poly *out) { … } /* * factor a polynomial using Berlekamp Trace algorithm (BTA) */ static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, struct gf_poly **g, struct gf_poly **h) { … } /* * find roots of a polynomial, using BTZ algorithm; see the beginning of this * file for details */ static int find_poly_roots(struct bch_control *bch, unsigned int k, struct gf_poly *poly, unsigned int *roots) { … } #if defined(USE_CHIEN_SEARCH) /* * exhaustive root search (Chien) implementation - not used, included only for * reference/comparison tests */ static int chien_search(struct bch_control *bch, unsigned int len, struct gf_poly *p, unsigned int *roots) { int m; unsigned int i, j, syn, syn0, count = 0; const unsigned int k = 8*len+bch->ecc_bits; /* use a log-based representation of polynomial */ gf_poly_logrep(bch, p, bch->cache); bch->cache[p->deg] = 0; syn0 = gf_div(bch, p->c[0], p->c[p->deg]); for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { /* compute elp(a^i) */ for (j = 1, syn = syn0; j <= p->deg; j++) { m = bch->cache[j]; if (m >= 0) syn ^= a_pow(bch, m+j*i); } if (syn == 0) { roots[count++] = GF_N(bch)-i; if (count == p->deg) break; } } return (count == p->deg) ? count : 0; } #define find_poly_roots … #endif /* USE_CHIEN_SEARCH */ /** * bch_decode - decode received codeword and find bit error locations * @bch: BCH control structure * @data: received data, ignored if @calc_ecc is provided * @len: data length in bytes, must always be provided * @recv_ecc: received ecc, if NULL then assume it was XORed in @calc_ecc * @calc_ecc: calculated ecc, if NULL then calc_ecc is computed from @data * @syn: hw computed syndrome data (if NULL, syndrome is calculated) * @errloc: output array of error locations * * Returns: * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if * invalid parameters were provided * * Depending on the available hw BCH support and the need to compute @calc_ecc * separately (using bch_encode()), this function should be called with one of * the following parameter configurations - * * by providing @data and @recv_ecc only: * bch_decode(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc) * * by providing @recv_ecc and @calc_ecc: * bch_decode(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc) * * by providing ecc = recv_ecc XOR calc_ecc: * bch_decode(@bch, NULL, @len, NULL, ecc, NULL, @errloc) * * by providing syndrome results @syn: * bch_decode(@bch, NULL, @len, NULL, NULL, @syn, @errloc) * * Once bch_decode() has successfully returned with a positive value, error * locations returned in array @errloc should be interpreted as follows - * * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for * data correction) * * if (errloc[n] < 8*len), then n-th error is located in data and can be * corrected with statement data[errloc[n]/8] ^= 1 << (errloc[n] % 8); * * Note that this function does not perform any data correction by itself, it * merely indicates error locations. */ int bch_decode(struct bch_control *bch, const uint8_t *data, unsigned int len, const uint8_t *recv_ecc, const uint8_t *calc_ecc, const unsigned int *syn, unsigned int *errloc) { … } EXPORT_SYMBOL_GPL(…); /* * generate Galois field lookup tables */ static int build_gf_tables(struct bch_control *bch, unsigned int poly) { … } /* * compute generator polynomial remainder tables for fast encoding */ static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) { … } /* * build a base for factoring degree 2 polynomials */ static int build_deg2_base(struct bch_control *bch) { … } static void *bch_alloc(size_t size, int *err) { … } /* * compute generator polynomial for given (m,t) parameters. */ static uint32_t *compute_generator_polynomial(struct bch_control *bch) { … } /** * bch_init - initialize a BCH encoder/decoder * @m: Galois field order, should be in the range 5-15 * @t: maximum error correction capability, in bits * @prim_poly: user-provided primitive polynomial (or 0 to use default) * @swap_bits: swap bits within data and syndrome bytes * * Returns: * a newly allocated BCH control structure if successful, NULL otherwise * * This initialization can take some time, as lookup tables are built for fast * encoding/decoding; make sure not to call this function from a time critical * path. Usually, bch_init() should be called on module/driver init and * bch_free() should be called to release memory on exit. * * You may provide your own primitive polynomial of degree @m in argument * @prim_poly, or let bch_init() use its default polynomial. * * Once bch_init() has successfully returned a pointer to a newly allocated * BCH control structure, ecc length in bytes is given by member @ecc_bytes of * the structure. */ struct bch_control *bch_init(int m, int t, unsigned int prim_poly, bool swap_bits) { … } EXPORT_SYMBOL_GPL(…); /** * bch_free - free the BCH control structure * @bch: BCH control structure to release */ void bch_free(struct bch_control *bch) { … } EXPORT_SYMBOL_GPL(…); MODULE_LICENSE(…) …; MODULE_AUTHOR(…) …; MODULE_DESCRIPTION(…) …;
Codebase Browser
linux