/* * 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 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 <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[]; /* 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];}; static u8 swap_bits_table[] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,}; static u8 swap_bits(struct bch_control *bch, u8 in){ if (!bch->swap_bits) return in; return swap_bits_table[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){ int i; const uint32_t *p; const int l = BCH_ECC_WORDS(bch)-1; while (len--) { u8 tmp = swap_bits(bch, *data++); p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff); for (i = 0; i < l; i++) ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); ecc[l] = (ecc[l] << 8)^(*p); }} /* * 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){ uint8_t pad[4] = {0, 0, 0, 0}; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++, src += 4) dst[i] = ((u32)swap_bits(bch, src[0]) << 24) | ((u32)swap_bits(bch, src[1]) << 16) | ((u32)swap_bits(bch, src[2]) << 8) | swap_bits(bch, src[3]); memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) | ((u32)swap_bits(bch, pad[1]) << 16) | ((u32)swap_bits(bch, pad[2]) << 8) | swap_bits(bch, pad[3]);} /* * convert 32-bit ecc words to ecc bytes */static void store_ecc8(struct bch_control *bch, uint8_t *dst, const uint32_t *src){ uint8_t pad[4]; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++) { *dst++ = swap_bits(bch, src[i] >> 24); *dst++ = swap_bits(bch, src[i] >> 16); *dst++ = swap_bits(bch, src[i] >> 8); *dst++ = swap_bits(bch, src[i]); } pad[0] = swap_bits(bch, src[nwords] >> 24); pad[1] = swap_bits(bch, src[nwords] >> 16); pad[2] = swap_bits(bch, src[nwords] >> 8); pad[3] = swap_bits(bch, src[nwords]); memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);} /** * 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){ const unsigned int l = BCH_ECC_WORDS(bch)-1; unsigned int i, mlen; unsigned long m; uint32_t w, r[BCH_ECC_MAX_WORDS]; const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r); const uint32_t * const tab0 = bch->mod8_tab; const uint32_t * const tab1 = tab0 + 256*(l+1); const uint32_t * const tab2 = tab1 + 256*(l+1); const uint32_t * const tab3 = tab2 + 256*(l+1); const uint32_t *pdata, *p0, *p1, *p2, *p3; if (WARN_ON(r_bytes > sizeof(r))) return; if (ecc) { /* load ecc parity bytes into internal 32-bit buffer */ load_ecc8(bch, bch->ecc_buf, ecc); } else { memset(bch->ecc_buf, 0, r_bytes); } /* process first unaligned data bytes */ m = ((unsigned long)data) & 3; if (m) { mlen = (len < (4-m)) ? len : 4-m; bch_encode_unaligned(bch, data, mlen, bch->ecc_buf); data += mlen; len -= mlen; } /* process 32-bit aligned data words */ pdata = (uint32_t *)data; mlen = len/4; data += 4*mlen; len -= 4*mlen; memcpy(r, bch->ecc_buf, r_bytes); /* * split each 32-bit word into 4 polynomials of weight 8 as follows: * * 31 ...24 23 ...16 15 ... 8 7 ... 0 * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt * tttttttt mod g = r0 (precomputed) * zzzzzzzz 00000000 mod g = r1 (precomputed) * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 */ while (mlen--) { /* input data is read in big-endian format */ w = cpu_to_be32(*pdata++); if (bch->swap_bits) w = (u32)swap_bits(bch, w) | ((u32)swap_bits(bch, w >> 8) << 8) | ((u32)swap_bits(bch, w >> 16) << 16) | ((u32)swap_bits(bch, w >> 24) << 24); w ^= r[0]; p0 = tab0 + (l+1)*((w >> 0) & 0xff); p1 = tab1 + (l+1)*((w >> 8) & 0xff); p2 = tab2 + (l+1)*((w >> 16) & 0xff); p3 = tab3 + (l+1)*((w >> 24) & 0xff); for (i = 0; i < l; i++) r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; r[l] = p0[l]^p1[l]^p2[l]^p3[l]; } memcpy(bch->ecc_buf, r, r_bytes); /* process last unaligned bytes */ if (len) bch_encode_unaligned(bch, data, len, bch->ecc_buf); /* store ecc parity bytes into original parity buffer */ if (ecc) store_ecc8(bch, ecc, bch->ecc_buf);}EXPORT_SYMBOL_GPL(bch_encode); static inline int modulo(struct bch_control *bch, unsigned int v){ const unsigned int n = GF_N(bch); while (v >= n) { v -= n; v = (v & n) + (v >> GF_M(bch)); } return v;} /* * shorter and faster modulo function, only works when v < 2N. */static inline int mod_s(struct bch_control *bch, unsigned int v){ const unsigned int n = GF_N(bch); return (v < n) ? v : v-n;} static inline int deg(unsigned int poly){ /* polynomial degree is the most-significant bit index */ return fls(poly)-1;} static inline int parity(unsigned int x){ /* * public domain code snippet, lifted from * http://www-graphics.stanford.edu/~seander/bithacks.html */ x ^= x >> 1; x ^= x >> 2; x = (x & 0x11111111U) * 0x11111111U; return (x >> 28) & 1;} /* Galois field basic operations: multiply, divide, inverse, etc. */ static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, unsigned int b){ return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ bch->a_log_tab[b])] : 0;} static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a){ return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;} static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, unsigned int b){ return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ GF_N(bch)-bch->a_log_tab[b])] : 0;} static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a){ return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];} static inline unsigned int a_pow(struct bch_control *bch, int i){ return bch->a_pow_tab[modulo(bch, i)];} static inline int a_log(struct bch_control *bch, unsigned int x){ return bch->a_log_tab[x];} static inline int a_ilog(struct bch_control *bch, unsigned int x){ return mod_s(bch, GF_N(bch)-bch->a_log_tab[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){ int i, j, s; unsigned int m; uint32_t poly; const int t = GF_T(bch); s = bch->ecc_bits; /* make sure extra bits in last ecc word are cleared */ m = ((unsigned int)s) & 31; if (m) ecc[s/32] &= ~((1u << (32-m))-1); memset(syn, 0, 2*t*sizeof(*syn)); /* compute v(a^j) for j=1 .. 2t-1 */ do { poly = *ecc++; s -= 32; while (poly) { i = deg(poly); for (j = 0; j < 2*t; j += 2) syn[j] ^= a_pow(bch, (j+1)*(i+s)); poly ^= (1 << i); } } while (s > 0); /* v(a^(2j)) = v(a^j)^2 */ for (j = 0; j < t; j++) syn[2*j+1] = gf_sqr(bch, syn[j]);} static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src){ memcpy(dst, src, GF_POLY_SZ(src->deg));} static int compute_error_locator_polynomial(struct bch_control *bch, const unsigned int *syn){ const unsigned int t = GF_T(bch); const unsigned int n = GF_N(bch); unsigned int i, j, tmp, l, pd = 1, d = syn[0]; struct gf_poly *elp = bch->elp; struct gf_poly *pelp = bch->poly_2t[0]; struct gf_poly *elp_copy = bch->poly_2t[1]; int k, pp = -1; memset(pelp, 0, GF_POLY_SZ(2*t)); memset(elp, 0, GF_POLY_SZ(2*t)); pelp->deg = 0; pelp->c[0] = 1; elp->deg = 0; elp->c[0] = 1; /* use simplified binary Berlekamp-Massey algorithm */ for (i = 0; (i < t) && (elp->deg <= t); i++) { if (d) { k = 2*i-pp; gf_poly_copy(elp_copy, elp); /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ tmp = a_log(bch, d)+n-a_log(bch, pd); for (j = 0; j <= pelp->deg; j++) { if (pelp->c[j]) { l = a_log(bch, pelp->c[j]); elp->c[j+k] ^= a_pow(bch, tmp+l); } } /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ tmp = pelp->deg+k; if (tmp > elp->deg) { elp->deg = tmp; gf_poly_copy(pelp, elp_copy); pd = d; pp = 2*i; } } /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ if (i < t-1) { d = syn[2*i+2]; for (j = 1; j <= elp->deg; j++) d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); } } dbg("elp=%s\n", gf_poly_str(elp)); return (elp->deg > t) ? -1 : (int)elp->deg;} /* * 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)Lines 1–500 of 1446. Load more
/* * 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 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 <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[]; /* 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]; }; static u8 swap_bits_table[] = { 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8, 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4, 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2, 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa, 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee, 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1, 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5, 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd, 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb, 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7, 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff, }; static u8 swap_bits(struct bch_control *bch, u8 in) { if (!bch->swap_bits) return in; return swap_bits_table[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) { int i; const uint32_t *p; const int l = BCH_ECC_WORDS(bch)-1; while (len--) { u8 tmp = swap_bits(bch, *data++); p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff); for (i = 0; i < l; i++) ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); ecc[l] = (ecc[l] << 8)^(*p); } } /* * 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) { uint8_t pad[4] = {0, 0, 0, 0}; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++, src += 4) dst[i] = ((u32)swap_bits(bch, src[0]) << 24) | ((u32)swap_bits(bch, src[1]) << 16) | ((u32)swap_bits(bch, src[2]) << 8) | swap_bits(bch, src[3]); memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) | ((u32)swap_bits(bch, pad[1]) << 16) | ((u32)swap_bits(bch, pad[2]) << 8) | swap_bits(bch, pad[3]); } /* * convert 32-bit ecc words to ecc bytes */ static void store_ecc8(struct bch_control *bch, uint8_t *dst, const uint32_t *src) { uint8_t pad[4]; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++) { *dst++ = swap_bits(bch, src[i] >> 24); *dst++ = swap_bits(bch, src[i] >> 16); *dst++ = swap_bits(bch, src[i] >> 8); *dst++ = swap_bits(bch, src[i]); } pad[0] = swap_bits(bch, src[nwords] >> 24); pad[1] = swap_bits(bch, src[nwords] >> 16); pad[2] = swap_bits(bch, src[nwords] >> 8); pad[3] = swap_bits(bch, src[nwords]); memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); } /** * 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) { const unsigned int l = BCH_ECC_WORDS(bch)-1; unsigned int i, mlen; unsigned long m; uint32_t w, r[BCH_ECC_MAX_WORDS]; const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r); const uint32_t * const tab0 = bch->mod8_tab; const uint32_t * const tab1 = tab0 + 256*(l+1); const uint32_t * const tab2 = tab1 + 256*(l+1); const uint32_t * const tab3 = tab2 + 256*(l+1); const uint32_t *pdata, *p0, *p1, *p2, *p3; if (WARN_ON(r_bytes > sizeof(r))) return; if (ecc) { /* load ecc parity bytes into internal 32-bit buffer */ load_ecc8(bch, bch->ecc_buf, ecc); } else { memset(bch->ecc_buf, 0, r_bytes); } /* process first unaligned data bytes */ m = ((unsigned long)data) & 3; if (m) { mlen = (len < (4-m)) ? len : 4-m; bch_encode_unaligned(bch, data, mlen, bch->ecc_buf); data += mlen; len -= mlen; } /* process 32-bit aligned data words */ pdata = (uint32_t *)data; mlen = len/4; data += 4*mlen; len -= 4*mlen; memcpy(r, bch->ecc_buf, r_bytes); /* * split each 32-bit word into 4 polynomials of weight 8 as follows: * * 31 ...24 23 ...16 15 ... 8 7 ... 0 * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt * tttttttt mod g = r0 (precomputed) * zzzzzzzz 00000000 mod g = r1 (precomputed) * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 */ while (mlen--) { /* input data is read in big-endian format */ w = cpu_to_be32(*pdata++); if (bch->swap_bits) w = (u32)swap_bits(bch, w) | ((u32)swap_bits(bch, w >> 8) << 8) | ((u32)swap_bits(bch, w >> 16) << 16) | ((u32)swap_bits(bch, w >> 24) << 24); w ^= r[0]; p0 = tab0 + (l+1)*((w >> 0) & 0xff); p1 = tab1 + (l+1)*((w >> 8) & 0xff); p2 = tab2 + (l+1)*((w >> 16) & 0xff); p3 = tab3 + (l+1)*((w >> 24) & 0xff); for (i = 0; i < l; i++) r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; r[l] = p0[l]^p1[l]^p2[l]^p3[l]; } memcpy(bch->ecc_buf, r, r_bytes); /* process last unaligned bytes */ if (len) bch_encode_unaligned(bch, data, len, bch->ecc_buf); /* store ecc parity bytes into original parity buffer */ if (ecc) store_ecc8(bch, ecc, bch->ecc_buf); } EXPORT_SYMBOL_GPL(bch_encode); static inline int modulo(struct bch_control *bch, unsigned int v) { const unsigned int n = GF_N(bch); while (v >= n) { v -= n; v = (v & n) + (v >> GF_M(bch)); } return v; } /* * shorter and faster modulo function, only works when v < 2N. */ static inline int mod_s(struct bch_control *bch, unsigned int v) { const unsigned int n = GF_N(bch); return (v < n) ? v : v-n; } static inline int deg(unsigned int poly) { /* polynomial degree is the most-significant bit index */ return fls(poly)-1; } static inline int parity(unsigned int x) { /* * public domain code snippet, lifted from * http://www-graphics.stanford.edu/~seander/bithacks.html */ x ^= x >> 1; x ^= x >> 2; x = (x & 0x11111111U) * 0x11111111U; return (x >> 28) & 1; } /* Galois field basic operations: multiply, divide, inverse, etc. */ static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, unsigned int b) { return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ bch->a_log_tab[b])] : 0; } static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) { return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; } static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, unsigned int b) { return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ GF_N(bch)-bch->a_log_tab[b])] : 0; } static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) { return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; } static inline unsigned int a_pow(struct bch_control *bch, int i) { return bch->a_pow_tab[modulo(bch, i)]; } static inline int a_log(struct bch_control *bch, unsigned int x) { return bch->a_log_tab[x]; } static inline int a_ilog(struct bch_control *bch, unsigned int x) { return mod_s(bch, GF_N(bch)-bch->a_log_tab[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) { int i, j, s; unsigned int m; uint32_t poly; const int t = GF_T(bch); s = bch->ecc_bits; /* make sure extra bits in last ecc word are cleared */ m = ((unsigned int)s) & 31; if (m) ecc[s/32] &= ~((1u << (32-m))-1); memset(syn, 0, 2*t*sizeof(*syn)); /* compute v(a^j) for j=1 .. 2t-1 */ do { poly = *ecc++; s -= 32; while (poly) { i = deg(poly); for (j = 0; j < 2*t; j += 2) syn[j] ^= a_pow(bch, (j+1)*(i+s)); poly ^= (1 << i); } } while (s > 0); /* v(a^(2j)) = v(a^j)^2 */ for (j = 0; j < t; j++) syn[2*j+1] = gf_sqr(bch, syn[j]); } static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) { memcpy(dst, src, GF_POLY_SZ(src->deg)); } static int compute_error_locator_polynomial(struct bch_control *bch, const unsigned int *syn) { const unsigned int t = GF_T(bch); const unsigned int n = GF_N(bch); unsigned int i, j, tmp, l, pd = 1, d = syn[0]; struct gf_poly *elp = bch->elp; struct gf_poly *pelp = bch->poly_2t[0]; struct gf_poly *elp_copy = bch->poly_2t[1]; int k, pp = -1; memset(pelp, 0, GF_POLY_SZ(2*t)); memset(elp, 0, GF_POLY_SZ(2*t)); pelp->deg = 0; pelp->c[0] = 1; elp->deg = 0; elp->c[0] = 1; /* use simplified binary Berlekamp-Massey algorithm */ for (i = 0; (i < t) && (elp->deg <= t); i++) { if (d) { k = 2*i-pp; gf_poly_copy(elp_copy, elp); /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ tmp = a_log(bch, d)+n-a_log(bch, pd); for (j = 0; j <= pelp->deg; j++) { if (pelp->c[j]) { l = a_log(bch, pelp->c[j]); elp->c[j+k] ^= a_pow(bch, tmp+l); } } /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ tmp = pelp->deg+k; if (tmp > elp->deg) { elp->deg = tmp; gf_poly_copy(pelp, elp_copy); pd = d; pp = 2*i; } } /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ if (i < t-1) { d = syn[2*i+2]; for (j = 1; j <= elp->deg; j++) d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); } } dbg("elp=%s\n", gf_poly_str(elp)); return (elp->deg > t) ? -1 : (int)elp->deg; } /* * 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)