Lines Matching refs:bch
76 #include <linux/bch.h>
118 static u8 swap_bits(struct bch_control *bch, u8 in)
120 if (!bch->swap_bits)
129 static void bch_encode_unaligned(struct bch_control *bch,
135 const int l = BCH_ECC_WORDS(bch)-1;
138 u8 tmp = swap_bits(bch, *data++);
140 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff);
152 static void load_ecc8(struct bch_control *bch, uint32_t *dst,
156 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
159 dst[i] = ((u32)swap_bits(bch, src[0]) << 24) |
160 ((u32)swap_bits(bch, src[1]) << 16) |
161 ((u32)swap_bits(bch, src[2]) << 8) |
162 swap_bits(bch, src[3]);
164 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords);
165 dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) |
166 ((u32)swap_bits(bch, pad[1]) << 16) |
167 ((u32)swap_bits(bch, pad[2]) << 8) |
168 swap_bits(bch, pad[3]);
174 static void store_ecc8(struct bch_control *bch, uint8_t *dst,
178 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
181 *dst++ = swap_bits(bch, src[i] >> 24);
182 *dst++ = swap_bits(bch, src[i] >> 16);
183 *dst++ = swap_bits(bch, src[i] >> 8);
184 *dst++ = swap_bits(bch, src[i]);
186 pad[0] = swap_bits(bch, src[nwords] >> 24);
187 pad[1] = swap_bits(bch, src[nwords] >> 16);
188 pad[2] = swap_bits(bch, src[nwords] >> 8);
189 pad[3] = swap_bits(bch, src[nwords]);
190 memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);
195 * @bch: BCH control structure
202 * @ecc_bytes of @bch, and should be initialized to 0 before the first call.
205 * @bch; it may be less than m*t for large values of t.
207 void bch_encode(struct bch_control *bch, const uint8_t *data,
210 const unsigned int l = BCH_ECC_WORDS(bch)-1;
214 const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r);
215 const uint32_t * const tab0 = bch->mod8_tab;
226 load_ecc8(bch, bch->ecc_buf, ecc);
228 memset(bch->ecc_buf, 0, r_bytes);
235 bch_encode_unaligned(bch, data, mlen, bch->ecc_buf);
245 memcpy(r, bch->ecc_buf, r_bytes);
261 if (bch->swap_bits)
262 w = (u32)swap_bits(bch, w) |
263 ((u32)swap_bits(bch, w >> 8) << 8) |
264 ((u32)swap_bits(bch, w >> 16) << 16) |
265 ((u32)swap_bits(bch, w >> 24) << 24);
277 memcpy(bch->ecc_buf, r, r_bytes);
281 bch_encode_unaligned(bch, data, len, bch->ecc_buf);
285 store_ecc8(bch, ecc, bch->ecc_buf);
289 static inline int modulo(struct bch_control *bch, unsigned int v)
291 const unsigned int n = GF_N(bch);
294 v = (v & n) + (v >> GF_M(bch));
302 static inline int mod_s(struct bch_control *bch, unsigned int v)
304 const unsigned int n = GF_N(bch);
328 static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a,
331 return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
332 bch->a_log_tab[b])] : 0;
335 static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a)
337 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;
340 static inline unsigned int gf_div(struct bch_control *bch, unsigned int a,
343 return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
344 GF_N(bch)-bch->a_log_tab[b])] : 0;
347 static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a)
349 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];
352 static inline unsigned int a_pow(struct bch_control *bch, int i)
354 return bch->a_pow_tab[modulo(bch, i)];
357 static inline int a_log(struct bch_control *bch, unsigned int x)
359 return bch->a_log_tab[x];
362 static inline int a_ilog(struct bch_control *bch, unsigned int x)
364 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]);
370 static void compute_syndromes(struct bch_control *bch, uint32_t *ecc,
376 const int t = GF_T(bch);
378 s = bch->ecc_bits;
393 syn[j] ^= a_pow(bch, (j+1)*(i+s));
401 syn[2*j+1] = gf_sqr(bch, syn[j]);
409 static int compute_error_locator_polynomial(struct bch_control *bch,
412 const unsigned int t = GF_T(bch);
413 const unsigned int n = GF_N(bch);
415 struct gf_poly *elp = bch->elp;
416 struct gf_poly *pelp = bch->poly_2t[0];
417 struct gf_poly *elp_copy = bch->poly_2t[1];
434 tmp = a_log(bch, d)+n-a_log(bch, pd);
437 l = a_log(bch, pelp->c[j]);
438 elp->c[j+k] ^= a_pow(bch, tmp+l);
454 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);
465 static int solve_linear_system(struct bch_control *bch, unsigned int *rows,
468 const int m = GF_M(bch);
541 static int find_affine4_roots(struct bch_control *bch, unsigned int a,
546 const int m = GF_M(bch);
549 j = a_log(bch, b);
550 k = a_log(bch, a);
555 rows[i+1] = bch->a_pow_tab[4*i]^
556 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^
557 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0);
572 return solve_linear_system(bch, rows, roots, 4);
578 static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly,
585 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+
586 bch->a_log_tab[poly->c[1]]);
593 static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly,
601 l0 = bch->a_log_tab[poly->c[0]];
602 l1 = bch->a_log_tab[poly->c[1]];
603 l2 = bch->a_log_tab[poly->c[2]];
606 u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));
617 r ^= bch->xi_tab[i];
621 if ((gf_sqr(bch, r)^r) == u) {
623 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
624 bch->a_log_tab[r]+l2);
625 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
626 bch->a_log_tab[r^1]+l2);
635 static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly,
644 c2 = gf_div(bch, poly->c[0], e3);
645 b2 = gf_div(bch, poly->c[1], e3);
646 a2 = gf_div(bch, poly->c[2], e3);
649 c = gf_mul(bch, a2, c2); /* c = a2c2 */
650 b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */
651 a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */
654 if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
658 roots[n++] = a_ilog(bch, tmp[i]);
668 static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly,
679 d = gf_div(bch, poly->c[0], e4);
680 c = gf_div(bch, poly->c[1], e4);
681 b = gf_div(bch, poly->c[2], e4);
682 a = gf_div(bch, poly->c[3], e4);
689 f = gf_div(bch, c, a);
690 l = a_log(bch, f);
691 l += (l & 1) ? GF_N(bch) : 0;
692 e = a_pow(bch, l/2);
700 d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;
701 b = gf_mul(bch, a, e)^b;
708 c2 = gf_inv(bch, d);
709 b2 = gf_div(bch, a, d);
710 a2 = gf_div(bch, b, d);
718 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
721 f = a ? gf_inv(bch, roots[i]) : roots[i];
722 roots[i] = a_ilog(bch, f^e);
732 static void gf_poly_logrep(struct bch_control *bch,
735 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]);
739 rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1;
745 static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a,
757 rep = bch->cache;
758 gf_poly_logrep(bch, b, rep);
763 la = a_log(bch, c[j]);
768 c[p] ^= bch->a_pow_tab[mod_s(bch,
781 static void gf_poly_div(struct bch_control *bch, struct gf_poly *a,
787 gf_poly_mod(bch, a, b, NULL);
799 static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a,
813 gf_poly_mod(bch, a, b, NULL);
828 static void compute_trace_bk_mod(struct bch_control *bch, int k,
832 const int m = GF_M(bch);
838 z->c[1] = bch->a_pow_tab[k];
844 gf_poly_logrep(bch, f, bch->cache);
850 z->c[2*j] = gf_sqr(bch, z->c[j]);
859 gf_poly_mod(bch, z, f, bch->cache);
871 static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f,
874 struct gf_poly *f2 = bch->poly_2t[0];
875 struct gf_poly *q = bch->poly_2t[1];
876 struct gf_poly *tk = bch->poly_2t[2];
877 struct gf_poly *z = bch->poly_2t[3];
886 compute_trace_bk_mod(bch, k, f, z, tk);
891 gcd = gf_poly_gcd(bch, f2, tk);
894 gf_poly_div(bch, f, gcd, q);
907 static int find_poly_roots(struct bch_control *bch, unsigned int k,
916 cnt = find_poly_deg1_roots(bch, poly, roots);
919 cnt = find_poly_deg2_roots(bch, poly, roots);
922 cnt = find_poly_deg3_roots(bch, poly, roots);
925 cnt = find_poly_deg4_roots(bch, poly, roots);
930 if (poly->deg && (k <= GF_M(bch))) {
931 factor_polynomial(bch, k, poly, &f1, &f2);
933 cnt += find_poly_roots(bch, k+1, f1, roots);
935 cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
947 static int chien_search(struct bch_control *bch, unsigned int len,
952 const unsigned int k = 8*len+bch->ecc_bits;
955 gf_poly_logrep(bch, p, bch->cache);
956 bch->cache[p->deg] = 0;
957 syn0 = gf_div(bch, p->c[0], p->c[p->deg]);
959 for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) {
962 m = bch->cache[j];
964 syn ^= a_pow(bch, m+j*i);
967 roots[count++] = GF_N(bch)-i;
979 * @bch: BCH control structure
996 * bch_decode(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc)
999 * bch_decode(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc)
1002 * bch_decode(@bch, NULL, @len, NULL, ecc, NULL, @errloc)
1005 * bch_decode(@bch, NULL, @len, NULL, NULL, @syn, @errloc)
1019 int bch_decode(struct bch_control *bch, const uint8_t *data, unsigned int len,
1023 const unsigned int ecc_words = BCH_ECC_WORDS(bch);
1029 if (8*len > (bch->n-bch->ecc_bits))
1038 bch_encode(bch, data, len, NULL);
1041 load_ecc8(bch, bch->ecc_buf, calc_ecc);
1045 load_ecc8(bch, bch->ecc_buf2, recv_ecc);
1048 bch->ecc_buf[i] ^= bch->ecc_buf2[i];
1049 sum |= bch->ecc_buf[i];
1055 compute_syndromes(bch, bch->ecc_buf, bch->syn);
1056 syn = bch->syn;
1059 err = compute_error_locator_polynomial(bch, syn);
1061 nroots = find_poly_roots(bch, 1, bch->elp, errloc);
1067 nbits = (len*8)+bch->ecc_bits;
1074 if (!bch->swap_bits)
1086 static int build_gf_tables(struct bch_control *bch, unsigned int poly)
1092 if (k != (1u << GF_M(bch)))
1095 for (i = 0; i < GF_N(bch); i++) {
1096 bch->a_pow_tab[i] = x;
1097 bch->a_log_tab[x] = i;
1105 bch->a_pow_tab[GF_N(bch)] = 1;
1106 bch->a_log_tab[0] = 0;
1114 static void build_mod8_tables(struct bch_control *bch, const uint32_t *g)
1118 const int l = BCH_ECC_WORDS(bch);
1119 const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32);
1120 const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32);
1122 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab));
1128 tab = bch->mod8_tab + (b*256+i)*l;
1148 static int build_deg2_base(struct bch_control *bch)
1150 const int m = GF_M(bch);
1157 sum ^= a_pow(bch, i*(1 << j));
1160 ak = bch->a_pow_tab[i];
1168 for (x = 0; (x <= GF_N(bch)) && remaining; x++) {
1169 y = gf_sqr(bch, x)^x;
1171 r = a_log(bch, y);
1173 bch->xi_tab[r] = x;
1199 static uint32_t *compute_generator_polynomial(struct bch_control *bch)
1201 const unsigned int m = GF_M(bch);
1202 const unsigned int t = GF_T(bch);
1209 roots = bch_alloc((bch->n+1)*sizeof(*roots), &err);
1219 memset(roots , 0, (bch->n+1)*sizeof(*roots));
1223 r = mod_s(bch, 2*r);
1229 for (i = 0; i < GF_N(bch); i++) {
1232 r = bch->a_pow_tab[i];
1235 g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1];
1237 g->c[0] = gf_mul(bch, g->c[0], r);
1254 bch->ecc_bits = g->deg;
1291 struct bch_control *bch = NULL;
1303 printk(KERN_ERR "bch encoder/decoder was configured to support "
1333 bch = kzalloc(sizeof(*bch), GFP_KERNEL);
1334 if (bch == NULL)
1337 bch->m = m;
1338 bch->t = t;
1339 bch->n = (1 << m)-1;
1341 bch->ecc_bytes = DIV_ROUND_UP(m*t, 8);
1342 bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err);
1343 bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err);
1344 bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err);
1345 bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err);
1346 bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err);
1347 bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err);
1348 bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err);
1349 bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err);
1350 bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err);
1351 bch->swap_bits = swap_bits;
1353 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1354 bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);
1359 err = build_gf_tables(bch, prim_poly);
1364 genpoly = compute_generator_polynomial(bch);
1368 build_mod8_tables(bch, genpoly);
1371 err = build_deg2_base(bch);
1375 return bch;
1378 bch_free(bch);
1385 * @bch: BCH control structure to release
1387 void bch_free(struct bch_control *bch)
1391 if (bch) {
1392 kfree(bch->a_pow_tab);
1393 kfree(bch->a_log_tab);
1394 kfree(bch->mod8_tab);
1395 kfree(bch->ecc_buf);
1396 kfree(bch->ecc_buf2);
1397 kfree(bch->xi_tab);
1398 kfree(bch->syn);
1399 kfree(bch->cache);
1400 kfree(bch->elp);
1402 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1403 kfree(bch->poly_2t[i]);
1405 kfree(bch);