Lines Matching refs:bch
75 #include <linux/bch.h>
152 static u8 swap_bits(struct bch_control *bch, u8 in)
154 if (!bch->swap_bits)
163 static void bch_encode_unaligned(struct bch_control *bch,
169 const int l = BCH_ECC_WORDS(bch)-1;
172 u8 tmp = swap_bits(bch, *data++);
174 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff);
186 static void load_ecc8(struct bch_control *bch, uint32_t *dst,
190 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
193 dst[i] = ((u32)swap_bits(bch, src[0]) << 24) |
194 ((u32)swap_bits(bch, src[1]) << 16) |
195 ((u32)swap_bits(bch, src[2]) << 8) |
196 swap_bits(bch, src[3]);
198 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords);
199 dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) |
200 ((u32)swap_bits(bch, pad[1]) << 16) |
201 ((u32)swap_bits(bch, pad[2]) << 8) |
202 swap_bits(bch, pad[3]);
208 static void store_ecc8(struct bch_control *bch, uint8_t *dst,
212 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
215 *dst++ = swap_bits(bch, src[i] >> 24);
216 *dst++ = swap_bits(bch, src[i] >> 16);
217 *dst++ = swap_bits(bch, src[i] >> 8);
218 *dst++ = swap_bits(bch, src[i]);
220 pad[0] = swap_bits(bch, src[nwords] >> 24);
221 pad[1] = swap_bits(bch, src[nwords] >> 16);
222 pad[2] = swap_bits(bch, src[nwords] >> 8);
223 pad[3] = swap_bits(bch, src[nwords]);
224 memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);
229 * @bch: BCH control structure
236 * @ecc_bytes of @bch, and should be initialized to 0 before the first call.
239 * @bch; it may be less than m*t for large values of t.
241 void bch_encode(struct bch_control *bch, const uint8_t *data,
244 const unsigned int l = BCH_ECC_WORDS(bch)-1;
248 const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r);
249 const uint32_t * const tab0 = bch->mod8_tab;
260 load_ecc8(bch, bch->ecc_buf, ecc);
262 memset(bch->ecc_buf, 0, r_bytes);
269 bch_encode_unaligned(bch, data, mlen, bch->ecc_buf);
279 memcpy(r, bch->ecc_buf, r_bytes);
295 if (bch->swap_bits)
296 w = (u32)swap_bits(bch, w) |
297 ((u32)swap_bits(bch, w >> 8) << 8) |
298 ((u32)swap_bits(bch, w >> 16) << 16) |
299 ((u32)swap_bits(bch, w >> 24) << 24);
311 memcpy(bch->ecc_buf, r, r_bytes);
315 bch_encode_unaligned(bch, data, len, bch->ecc_buf);
319 store_ecc8(bch, ecc, bch->ecc_buf);
323 static inline int modulo(struct bch_control *bch, unsigned int v)
325 const unsigned int n = GF_N(bch);
328 v = (v & n) + (v >> GF_M(bch));
336 static inline int mod_s(struct bch_control *bch, unsigned int v)
338 const unsigned int n = GF_N(bch);
362 static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a,
365 return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
366 bch->a_log_tab[b])] : 0;
369 static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a)
371 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;
374 static inline unsigned int gf_div(struct bch_control *bch, unsigned int a,
377 return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
378 GF_N(bch)-bch->a_log_tab[b])] : 0;
381 static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a)
383 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];
386 static inline unsigned int a_pow(struct bch_control *bch, int i)
388 return bch->a_pow_tab[modulo(bch, i)];
391 static inline int a_log(struct bch_control *bch, unsigned int x)
393 return bch->a_log_tab[x];
396 static inline int a_ilog(struct bch_control *bch, unsigned int x)
398 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]);
404 static void compute_syndromes(struct bch_control *bch, uint32_t *ecc,
410 const int t = GF_T(bch);
412 s = bch->ecc_bits;
427 syn[j] ^= a_pow(bch, (j+1)*(i+s));
435 syn[2*j+1] = gf_sqr(bch, syn[j]);
443 static int compute_error_locator_polynomial(struct bch_control *bch,
446 const unsigned int t = GF_T(bch);
447 const unsigned int n = GF_N(bch);
449 struct gf_poly *elp = bch->elp;
450 struct gf_poly *pelp = bch->poly_2t[0];
451 struct gf_poly *elp_copy = bch->poly_2t[1];
468 tmp = a_log(bch, d)+n-a_log(bch, pd);
471 l = a_log(bch, pelp->c[j]);
472 elp->c[j+k] ^= a_pow(bch, tmp+l);
488 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);
499 static int solve_linear_system(struct bch_control *bch, unsigned int *rows,
502 const int m = GF_M(bch);
575 static int find_affine4_roots(struct bch_control *bch, unsigned int a,
580 const int m = GF_M(bch);
583 j = a_log(bch, b);
584 k = a_log(bch, a);
589 rows[i+1] = bch->a_pow_tab[4*i]^
590 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^
591 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0);
606 return solve_linear_system(bch, rows, roots, 4);
612 static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly,
619 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+
620 bch->a_log_tab[poly->c[1]]);
627 static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly,
635 l0 = bch->a_log_tab[poly->c[0]];
636 l1 = bch->a_log_tab[poly->c[1]];
637 l2 = bch->a_log_tab[poly->c[2]];
640 u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));
651 r ^= bch->xi_tab[i];
655 if ((gf_sqr(bch, r)^r) == u) {
657 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
658 bch->a_log_tab[r]+l2);
659 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
660 bch->a_log_tab[r^1]+l2);
669 static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly,
678 c2 = gf_div(bch, poly->c[0], e3);
679 b2 = gf_div(bch, poly->c[1], e3);
680 a2 = gf_div(bch, poly->c[2], e3);
683 c = gf_mul(bch, a2, c2); /* c = a2c2 */
684 b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */
685 a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */
688 if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
692 roots[n++] = a_ilog(bch, tmp[i]);
702 static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly,
713 d = gf_div(bch, poly->c[0], e4);
714 c = gf_div(bch, poly->c[1], e4);
715 b = gf_div(bch, poly->c[2], e4);
716 a = gf_div(bch, poly->c[3], e4);
723 f = gf_div(bch, c, a);
724 l = a_log(bch, f);
725 l += (l & 1) ? GF_N(bch) : 0;
726 e = a_pow(bch, l/2);
734 d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;
735 b = gf_mul(bch, a, e)^b;
742 c2 = gf_inv(bch, d);
743 b2 = gf_div(bch, a, d);
744 a2 = gf_div(bch, b, d);
752 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
755 f = a ? gf_inv(bch, roots[i]) : roots[i];
756 roots[i] = a_ilog(bch, f^e);
766 static void gf_poly_logrep(struct bch_control *bch,
769 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]);
773 rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1;
779 static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a,
791 rep = bch->cache;
792 gf_poly_logrep(bch, b, rep);
797 la = a_log(bch, c[j]);
802 c[p] ^= bch->a_pow_tab[mod_s(bch,
815 static void gf_poly_div(struct bch_control *bch, struct gf_poly *a,
821 gf_poly_mod(bch, a, b, NULL);
833 static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a,
847 gf_poly_mod(bch, a, b, NULL);
862 static void compute_trace_bk_mod(struct bch_control *bch, int k,
866 const int m = GF_M(bch);
872 z->c[1] = bch->a_pow_tab[k];
878 gf_poly_logrep(bch, f, bch->cache);
884 z->c[2*j] = gf_sqr(bch, z->c[j]);
893 gf_poly_mod(bch, z, f, bch->cache);
905 static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f,
908 struct gf_poly *f2 = bch->poly_2t[0];
909 struct gf_poly *q = bch->poly_2t[1];
910 struct gf_poly *tk = bch->poly_2t[2];
911 struct gf_poly *z = bch->poly_2t[3];
920 compute_trace_bk_mod(bch, k, f, z, tk);
925 gcd = gf_poly_gcd(bch, f2, tk);
928 gf_poly_div(bch, f, gcd, q);
941 static int find_poly_roots(struct bch_control *bch, unsigned int k,
950 cnt = find_poly_deg1_roots(bch, poly, roots);
953 cnt = find_poly_deg2_roots(bch, poly, roots);
956 cnt = find_poly_deg3_roots(bch, poly, roots);
959 cnt = find_poly_deg4_roots(bch, poly, roots);
964 if (poly->deg && (k <= GF_M(bch))) {
965 factor_polynomial(bch, k, poly, &f1, &f2);
967 cnt += find_poly_roots(bch, k+1, f1, roots);
969 cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
981 static int chien_search(struct bch_control *bch, unsigned int len,
986 const unsigned int k = 8*len+bch->ecc_bits;
989 gf_poly_logrep(bch, p, bch->cache);
990 bch->cache[p->deg] = 0;
991 syn0 = gf_div(bch, p->c[0], p->c[p->deg]);
993 for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) {
996 m = bch->cache[j];
998 syn ^= a_pow(bch, m+j*i);
1001 roots[count++] = GF_N(bch)-i;
1013 * @bch: BCH control structure
1030 * bch_decode(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc)
1033 * bch_decode(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc)
1036 * bch_decode(@bch, NULL, @len, NULL, ecc, NULL, @errloc)
1039 * bch_decode(@bch, NULL, @len, NULL, NULL, @syn, @errloc)
1053 int bch_decode(struct bch_control *bch, const uint8_t *data, unsigned int len,
1057 const unsigned int ecc_words = BCH_ECC_WORDS(bch);
1063 if (8*len > (bch->n-bch->ecc_bits))
1072 bch_encode(bch, data, len, NULL);
1075 load_ecc8(bch, bch->ecc_buf, calc_ecc);
1079 load_ecc8(bch, bch->ecc_buf2, recv_ecc);
1082 bch->ecc_buf[i] ^= bch->ecc_buf2[i];
1083 sum |= bch->ecc_buf[i];
1089 compute_syndromes(bch, bch->ecc_buf, bch->syn);
1090 syn = bch->syn;
1093 err = compute_error_locator_polynomial(bch, syn);
1095 nroots = find_poly_roots(bch, 1, bch->elp, errloc);
1101 nbits = (len*8)+bch->ecc_bits;
1108 if (!bch->swap_bits)
1120 static int build_gf_tables(struct bch_control *bch, unsigned int poly)
1126 if (k != (1u << GF_M(bch)))
1129 for (i = 0; i < GF_N(bch); i++) {
1130 bch->a_pow_tab[i] = x;
1131 bch->a_log_tab[x] = i;
1139 bch->a_pow_tab[GF_N(bch)] = 1;
1140 bch->a_log_tab[0] = 0;
1148 static void build_mod8_tables(struct bch_control *bch, const uint32_t *g)
1152 const int l = BCH_ECC_WORDS(bch);
1153 const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32);
1154 const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32);
1156 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab));
1162 tab = bch->mod8_tab + (b*256+i)*l;
1182 static int build_deg2_base(struct bch_control *bch)
1184 const int m = GF_M(bch);
1191 sum ^= a_pow(bch, i*(1 << j));
1194 ak = bch->a_pow_tab[i];
1202 for (x = 0; (x <= GF_N(bch)) && remaining; x++) {
1203 y = gf_sqr(bch, x)^x;
1205 r = a_log(bch, y);
1207 bch->xi_tab[r] = x;
1233 static uint32_t *compute_generator_polynomial(struct bch_control *bch)
1235 const unsigned int m = GF_M(bch);
1236 const unsigned int t = GF_T(bch);
1243 roots = bch_alloc((bch->n+1)*sizeof(*roots), &err);
1253 memset(roots , 0, (bch->n+1)*sizeof(*roots));
1257 r = mod_s(bch, 2*r);
1263 for (i = 0; i < GF_N(bch); i++) {
1266 r = bch->a_pow_tab[i];
1269 g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1];
1271 g->c[0] = gf_mul(bch, g->c[0], r);
1288 bch->ecc_bits = g->deg;
1325 struct bch_control *bch = NULL;
1337 printk(KERN_ERR "bch encoder/decoder was configured to support "
1367 bch = kzalloc(sizeof(*bch), GFP_KERNEL);
1368 if (bch == NULL)
1371 bch->m = m;
1372 bch->t = t;
1373 bch->n = (1 << m)-1;
1375 bch->ecc_bytes = DIV_ROUND_UP(m*t, 8);
1376 bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err);
1377 bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err);
1378 bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err);
1379 bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err);
1380 bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err);
1381 bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err);
1382 bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err);
1383 bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err);
1384 bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err);
1385 bch->swap_bits = swap_bits;
1387 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1388 bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);
1393 err = build_gf_tables(bch, prim_poly);
1398 genpoly = compute_generator_polynomial(bch);
1402 build_mod8_tables(bch, genpoly);
1405 err = build_deg2_base(bch);
1409 return bch;
1412 bch_free(bch);
1419 * @bch: BCH control structure to release
1421 void bch_free(struct bch_control *bch)
1425 if (bch) {
1426 kfree(bch->a_pow_tab);
1427 kfree(bch->a_log_tab);
1428 kfree(bch->mod8_tab);
1429 kfree(bch->ecc_buf);
1430 kfree(bch->ecc_buf2);
1431 kfree(bch->xi_tab);
1432 kfree(bch->syn);
1433 kfree(bch->cache);
1434 kfree(bch->elp);
1436 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1437 kfree(bch->poly_2t[i]);
1439 kfree(bch);