Lines Matching +full:codeword +full:- +full:by +full:- +full:codeword
5 * under the terms of the GNU General Public License version 2 as published by
15 * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
24 * Bose-Chaudhuri-Hocquenghem (BCH) codes.
45 * Encoding is performed by processing 32 input bits in parallel, using 4
50 * b. Error locator polynomial computation using Berlekamp-Massey algorithm
51 * c. Error locator root finding (by far the most expensive step)
56 * (BTA) down to a certain degree (4), after which ad hoc low-degree polynomial
63 * - WEWoRC 2009, Graz, Austria, LNCS, Springer, July 2009, to appear.
81 #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
85 #define GF_M(_p) ((_p)->m)
86 #define GF_T(_p) ((_p)->t)
87 #define GF_N(_p) ((_p)->n)
120 if (!bch->swap_bits) in swap_bits()
135 const int l = BCH_ECC_WORDS(bch)-1; in bch_encode_unaligned()
137 while (len--) { in bch_encode_unaligned()
140 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff); in bch_encode_unaligned()
150 * convert ecc bytes to aligned, zero-padded 32-bit ecc words
156 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; in load_ecc8()
164 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); in load_ecc8()
172 * convert 32-bit ecc words to ecc bytes
178 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; in store_ecc8()
190 memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); in store_ecc8()
194 * bch_encode - calculate BCH ecc parity of data
198 * @ecc: ecc parity data, must be initialized by caller
201 * allow incremental computations. It should be of the size indicated by member
204 * The exact number of computed ecc parity bits is given by member @ecc_bits of
210 const unsigned int l = BCH_ECC_WORDS(bch)-1; in bch_encode()
215 const uint32_t * const tab0 = bch->mod8_tab; in bch_encode()
225 /* load ecc parity bytes into internal 32-bit buffer */ in bch_encode()
226 load_ecc8(bch, bch->ecc_buf, ecc); in bch_encode()
228 memset(bch->ecc_buf, 0, r_bytes); in bch_encode()
234 mlen = (len < (4-m)) ? len : 4-m; in bch_encode()
235 bch_encode_unaligned(bch, data, mlen, bch->ecc_buf); in bch_encode()
237 len -= mlen; in bch_encode()
240 /* process 32-bit aligned data words */ in bch_encode()
244 len -= 4*mlen; in bch_encode()
245 memcpy(r, bch->ecc_buf, r_bytes); in bch_encode()
248 * split each 32-bit word into 4 polynomials of weight 8 as follows: in bch_encode()
258 while (mlen--) { in bch_encode()
259 /* input data is read in big-endian format */ in bch_encode()
261 if (bch->swap_bits) in bch_encode()
277 memcpy(bch->ecc_buf, r, r_bytes); in bch_encode()
281 bch_encode_unaligned(bch, data, len, bch->ecc_buf); in bch_encode()
285 store_ecc8(bch, ecc, bch->ecc_buf); in bch_encode()
293 v -= n; in modulo()
305 return (v < n) ? v : v-n; in mod_s()
310 /* polynomial degree is the most-significant bit index */ in deg()
311 return fls(poly)-1; in deg()
318 * http://www-graphics.stanford.edu/~seander/bithacks.html in parity()
331 return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ in gf_mul()
332 bch->a_log_tab[b])] : 0; in gf_mul()
337 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; in gf_sqr()
343 return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ in gf_div()
344 GF_N(bch)-bch->a_log_tab[b])] : 0; in gf_div()
349 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; in gf_inv()
354 return bch->a_pow_tab[modulo(bch, i)]; in a_pow()
359 return bch->a_log_tab[x]; in a_log()
364 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); in a_ilog()
378 s = bch->ecc_bits; in compute_syndromes()
383 ecc[s/32] &= ~((1u << (32-m))-1); in compute_syndromes()
386 /* compute v(a^j) for j=1 .. 2t-1 */ in compute_syndromes()
389 s -= 32; in compute_syndromes()
406 memcpy(dst, src, GF_POLY_SZ(src->deg)); in gf_poly_copy()
415 struct gf_poly *elp = bch->elp; in compute_error_locator_polynomial()
416 struct gf_poly *pelp = bch->poly_2t[0]; in compute_error_locator_polynomial()
417 struct gf_poly *elp_copy = bch->poly_2t[1]; in compute_error_locator_polynomial()
418 int k, pp = -1; in compute_error_locator_polynomial()
423 pelp->deg = 0; in compute_error_locator_polynomial()
424 pelp->c[0] = 1; in compute_error_locator_polynomial()
425 elp->deg = 0; in compute_error_locator_polynomial()
426 elp->c[0] = 1; in compute_error_locator_polynomial()
428 /* use simplified binary Berlekamp-Massey algorithm */ in compute_error_locator_polynomial()
429 for (i = 0; (i < t) && (elp->deg <= t); i++) { in compute_error_locator_polynomial()
431 k = 2*i-pp; in compute_error_locator_polynomial()
433 /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ in compute_error_locator_polynomial()
434 tmp = a_log(bch, d)+n-a_log(bch, pd); in compute_error_locator_polynomial()
435 for (j = 0; j <= pelp->deg; j++) { in compute_error_locator_polynomial()
436 if (pelp->c[j]) { in compute_error_locator_polynomial()
437 l = a_log(bch, pelp->c[j]); in compute_error_locator_polynomial()
438 elp->c[j+k] ^= a_pow(bch, tmp+l); in compute_error_locator_polynomial()
441 /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ in compute_error_locator_polynomial()
442 tmp = pelp->deg+k; in compute_error_locator_polynomial()
443 if (tmp > elp->deg) { in compute_error_locator_polynomial()
444 elp->deg = tmp; in compute_error_locator_polynomial()
450 /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ in compute_error_locator_polynomial()
451 if (i < t-1) { in compute_error_locator_polynomial()
453 for (j = 1; j <= elp->deg; j++) in compute_error_locator_polynomial()
454 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); in compute_error_locator_polynomial()
458 return (elp->deg > t) ? -1 : (int)elp->deg; in compute_error_locator_polynomial()
478 p = c-k; in solve_linear_system()
504 for (r = m-1; r >= 0; r--) { in solve_linear_system()
505 if ((r > m-1-k) && rows[r]) in solve_linear_system()
509 rows[r] = (p && (r == param[p-1])) ? in solve_linear_system()
510 p--, 1u << (m-r) : rows[r-p]; in solve_linear_system()
519 /* set parameters for p-th solution */ in solve_linear_system()
525 for (r = m-1; r >= 0; r--) { in solve_linear_system()
527 tmp |= parity(mask) << (m-r); in solve_linear_system()
552 rows[i+1] = bch->a_pow_tab[4*i]^ in find_affine4_roots()
553 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ in find_affine4_roots()
554 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); in find_affine4_roots()
580 if (poly->c[0]) in find_poly_deg1_roots()
582 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ in find_poly_deg1_roots()
583 bch->a_log_tab[poly->c[1]]); in find_poly_deg1_roots()
596 if (poly->c[0] && poly->c[1]) { in find_poly_deg2_roots()
598 l0 = bch->a_log_tab[poly->c[0]]; in find_poly_deg2_roots()
599 l1 = bch->a_log_tab[poly->c[1]]; in find_poly_deg2_roots()
600 l2 = bch->a_log_tab[poly->c[2]]; in find_poly_deg2_roots()
603 u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); in find_poly_deg2_roots()
605 * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): in find_poly_deg2_roots()
614 r ^= bch->xi_tab[i]; in find_poly_deg2_roots()
620 roots[n++] = modulo(bch, 2*GF_N(bch)-l1- in find_poly_deg2_roots()
621 bch->a_log_tab[r]+l2); in find_poly_deg2_roots()
622 roots[n++] = modulo(bch, 2*GF_N(bch)-l1- in find_poly_deg2_roots()
623 bch->a_log_tab[r^1]+l2); in find_poly_deg2_roots()
638 if (poly->c[0]) { in find_poly_deg3_roots()
640 e3 = poly->c[3]; in find_poly_deg3_roots()
641 c2 = gf_div(bch, poly->c[0], e3); in find_poly_deg3_roots()
642 b2 = gf_div(bch, poly->c[1], e3); in find_poly_deg3_roots()
643 a2 = gf_div(bch, poly->c[2], e3); in find_poly_deg3_roots()
671 if (poly->c[0] == 0) in find_poly_deg4_roots()
675 e4 = poly->c[4]; in find_poly_deg4_roots()
676 d = gf_div(bch, poly->c[0], e4); in find_poly_deg4_roots()
677 c = gf_div(bch, poly->c[1], e4); in find_poly_deg4_roots()
678 b = gf_div(bch, poly->c[2], e4); in find_poly_deg4_roots()
679 a = gf_div(bch, poly->c[3], e4); in find_poly_deg4_roots()
683 /* first, eliminate cX by using z=X+e with ae^2+c=0 */ in find_poly_deg4_roots()
717 /* post-process roots (reverse transformations) */ in find_poly_deg4_roots()
727 * build monic, log-based representation of a polynomial
732 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); in gf_poly_logrep()
734 /* represent 0 values with -1; warning, rep[d] is not set to 1 */ in gf_poly_logrep()
736 rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; in gf_poly_logrep()
746 unsigned int i, j, *c = a->c; in gf_poly_mod()
747 const unsigned int d = b->deg; in gf_poly_mod()
749 if (a->deg < d) in gf_poly_mod()
754 rep = bch->cache; in gf_poly_mod()
758 for (j = a->deg; j >= d; j--) { in gf_poly_mod()
761 p = j-d; in gf_poly_mod()
765 c[p] ^= bch->a_pow_tab[mod_s(bch, in gf_poly_mod()
770 a->deg = d-1; in gf_poly_mod()
771 while (!c[a->deg] && a->deg) in gf_poly_mod()
772 a->deg--; in gf_poly_mod()
781 if (a->deg >= b->deg) { in gf_poly_div()
782 q->deg = a->deg-b->deg; in gf_poly_div()
786 memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); in gf_poly_div()
788 q->deg = 0; in gf_poly_div()
789 q->c[0] = 0; in gf_poly_div()
801 if (a->deg < b->deg) in gf_poly_gcd()
804 while (b->deg > 0) { in gf_poly_gcd()
826 z->deg = 1; in compute_trace_bk_mod()
827 z->c[0] = 0; in compute_trace_bk_mod()
828 z->c[1] = bch->a_pow_tab[k]; in compute_trace_bk_mod()
830 out->deg = 0; in compute_trace_bk_mod()
831 memset(out, 0, GF_POLY_SZ(f->deg)); in compute_trace_bk_mod()
834 gf_poly_logrep(bch, f, bch->cache); in compute_trace_bk_mod()
838 for (j = z->deg; j >= 0; j--) { in compute_trace_bk_mod()
839 out->c[j] ^= z->c[j]; in compute_trace_bk_mod()
840 z->c[2*j] = gf_sqr(bch, z->c[j]); in compute_trace_bk_mod()
841 z->c[2*j+1] = 0; in compute_trace_bk_mod()
843 if (z->deg > out->deg) in compute_trace_bk_mod()
844 out->deg = z->deg; in compute_trace_bk_mod()
846 if (i < m-1) { in compute_trace_bk_mod()
847 z->deg *= 2; in compute_trace_bk_mod()
849 gf_poly_mod(bch, z, f, bch->cache); in compute_trace_bk_mod()
852 while (!out->c[out->deg] && out->deg) in compute_trace_bk_mod()
853 out->deg--; in compute_trace_bk_mod()
864 struct gf_poly *f2 = bch->poly_2t[0]; in factor_polynomial()
865 struct gf_poly *q = bch->poly_2t[1]; in factor_polynomial()
866 struct gf_poly *tk = bch->poly_2t[2]; in factor_polynomial()
867 struct gf_poly *z = bch->poly_2t[3]; in factor_polynomial()
878 if (tk->deg > 0) { in factor_polynomial()
882 if (gcd->deg < f->deg) { in factor_polynomial()
885 /* store g and h in-place (clobbering f) */ in factor_polynomial()
886 *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; in factor_polynomial()
903 switch (poly->deg) { in find_poly_roots()
920 if (poly->deg && (k <= GF_M(bch))) { in find_poly_roots()
934 * exhaustive root search (Chien) implementation - not used, included only for
942 const unsigned int k = 8*len+bch->ecc_bits; in chien_search()
944 /* use a log-based representation of polynomial */ in chien_search()
945 gf_poly_logrep(bch, p, bch->cache); in chien_search()
946 bch->cache[p->deg] = 0; in chien_search()
947 syn0 = gf_div(bch, p->c[0], p->c[p->deg]); in chien_search()
949 for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) { in chien_search()
951 for (j = 1, syn = syn0; j <= p->deg; j++) { in chien_search()
952 m = bch->cache[j]; in chien_search()
957 roots[count++] = GF_N(bch)-i; in chien_search()
958 if (count == p->deg) in chien_search()
962 return (count == p->deg) ? count : 0; in chien_search()
968 * bch_decode - decode received codeword and find bit error locations
978 * The number of errors found, or -EBADMSG if decoding failed, or -EINVAL if
983 * the following parameter configurations -
985 * by providing @data and @recv_ecc only:
988 * by providing @recv_ecc and @calc_ecc:
991 * by providing ecc = recv_ecc XOR calc_ecc:
994 * by providing syndrome results @syn:
998 * locations returned in array @errloc should be interpreted as follows -
1000 * if (errloc[n] >= 8*len), then n-th error is located in ecc (no need for
1003 * if (errloc[n] < 8*len), then n-th error is located in data and can be
1006 * Note that this function does not perform any data correction by itself, it
1019 if (8*len > (bch->n-bch->ecc_bits)) in bch_decode()
1020 return -EINVAL; in bch_decode()
1027 return -EINVAL; in bch_decode()
1031 load_ecc8(bch, bch->ecc_buf, calc_ecc); in bch_decode()
1035 load_ecc8(bch, bch->ecc_buf2, recv_ecc); in bch_decode()
1038 bch->ecc_buf[i] ^= bch->ecc_buf2[i]; in bch_decode()
1039 sum |= bch->ecc_buf[i]; in bch_decode()
1045 compute_syndromes(bch, bch->ecc_buf, bch->syn); in bch_decode()
1046 syn = bch->syn; in bch_decode()
1051 nroots = find_poly_roots(bch, 1, bch->elp, errloc); in bch_decode()
1053 err = -1; in bch_decode()
1056 /* post-process raw error locations for easier correction */ in bch_decode()
1057 nbits = (len*8)+bch->ecc_bits; in bch_decode()
1060 err = -1; in bch_decode()
1063 errloc[i] = nbits-1-errloc[i]; in bch_decode()
1064 if (!bch->swap_bits) in bch_decode()
1066 (7-(errloc[i] & 7)); in bch_decode()
1069 return (err >= 0) ? err : -EBADMSG; in bch_decode()
1083 return -1; in build_gf_tables()
1086 bch->a_pow_tab[i] = x; in build_gf_tables()
1087 bch->a_log_tab[x] = i; in build_gf_tables()
1089 /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */ in build_gf_tables()
1090 return -1; in build_gf_tables()
1095 bch->a_pow_tab[GF_N(bch)] = 1; in build_gf_tables()
1096 bch->a_log_tab[0] = 0; in build_gf_tables()
1109 const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32); in build_mod8_tables()
1110 const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32); in build_mod8_tables()
1112 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); in build_mod8_tables()
1118 tab = bch->mod8_tab + (b*256+i)*l; in build_mod8_tables()
1123 data ^= g[0] >> (31-d); in build_mod8_tables()
1127 g[j+1] >> (31-d) : 0; in build_mod8_tables()
1150 ak = bch->a_pow_tab[i]; in build_deg2_base()
1154 /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ in build_deg2_base()
1163 bch->xi_tab[r] = x; in build_deg2_base()
1165 remaining--; in build_deg2_base()
1173 return remaining ? -1 : 0; in build_deg2_base()
1199 roots = bch_alloc((bch->n+1)*sizeof(*roots), &err); in compute_generator_polynomial()
1209 memset(roots , 0, (bch->n+1)*sizeof(*roots)); in compute_generator_polynomial()
1217 g->deg = 0; in compute_generator_polynomial()
1218 g->c[0] = 1; in compute_generator_polynomial()
1221 /* multiply g(X) by (X+root) */ in compute_generator_polynomial()
1222 r = bch->a_pow_tab[i]; in compute_generator_polynomial()
1223 g->c[g->deg+1] = 1; in compute_generator_polynomial()
1224 for (j = g->deg; j > 0; j--) in compute_generator_polynomial()
1225 g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1]; in compute_generator_polynomial()
1227 g->c[0] = gf_mul(bch, g->c[0], r); in compute_generator_polynomial()
1228 g->deg++; in compute_generator_polynomial()
1231 /* store left-justified binary representation of g(X) */ in compute_generator_polynomial()
1232 n = g->deg+1; in compute_generator_polynomial()
1238 if (g->c[n-1-j]) in compute_generator_polynomial()
1239 word |= 1u << (31-j); in compute_generator_polynomial()
1242 n -= nbits; in compute_generator_polynomial()
1244 bch->ecc_bits = g->deg; in compute_generator_polynomial()
1254 * bch_init - initialize a BCH encoder/decoder
1255 * @m: Galois field order, should be in the range 5-15
1257 * @prim_poly: user-provided primitive polynomial (or 0 to use default)
1272 * BCH control structure, ecc length in bytes is given by member @ecc_bytes of
1315 if ((t < 1) || (m*t >= ((1 << m)-1))) in bch_init()
1321 prim_poly = prim_poly_tab[m-min_m]; in bch_init()
1327 bch->m = m; in bch_init()
1328 bch->t = t; in bch_init()
1329 bch->n = (1 << m)-1; in bch_init()
1331 bch->ecc_bytes = DIV_ROUND_UP(m*t, 8); in bch_init()
1332 bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err); in bch_init()
1333 bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err); in bch_init()
1334 bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err); in bch_init()
1335 bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err); in bch_init()
1336 bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err); in bch_init()
1337 bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err); in bch_init()
1338 bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err); in bch_init()
1339 bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err); in bch_init()
1340 bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err); in bch_init()
1341 bch->swap_bits = swap_bits; in bch_init()
1343 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) in bch_init()
1344 bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err); in bch_init()
1374 * bch_free - free the BCH control structure
1382 kfree(bch->a_pow_tab); in bch_free()
1383 kfree(bch->a_log_tab); in bch_free()
1384 kfree(bch->mod8_tab); in bch_free()
1385 kfree(bch->ecc_buf); in bch_free()
1386 kfree(bch->ecc_buf2); in bch_free()
1387 kfree(bch->xi_tab); in bch_free()
1388 kfree(bch->syn); in bch_free()
1389 kfree(bch->cache); in bch_free()
1390 kfree(bch->elp); in bch_free()
1392 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) in bch_free()
1393 kfree(bch->poly_2t[i]); in bch_free()