Lines Matching full:bch
2 * Generic binary BCH encoding/decoding library
24 * Bose-Chaudhuri-Hocquenghem (BCH) codes.
33 * On systems supporting hw BCH features, intermediate results may be provided
40 * (m,t) are fixed and known in advance, e.g. when using BCH error correction
76 #include <linux/bch.h>
118 static u8 swap_bits(struct bch_control *bch, u8 in) in swap_bits() argument
120 if (!bch->swap_bits) in swap_bits()
129 static void bch_encode_unaligned(struct bch_control *bch, in bch_encode_unaligned() argument
135 const int l = BCH_ECC_WORDS(bch)-1; in bch_encode_unaligned()
138 u8 tmp = swap_bits(bch, *data++); in bch_encode_unaligned()
140 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(tmp)) & 0xff); in bch_encode_unaligned()
152 static void load_ecc8(struct bch_control *bch, uint32_t *dst, in load_ecc8() argument
156 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; in load_ecc8()
159 dst[i] = ((u32)swap_bits(bch, src[0]) << 24) | in load_ecc8()
160 ((u32)swap_bits(bch, src[1]) << 16) | in load_ecc8()
161 ((u32)swap_bits(bch, src[2]) << 8) | in load_ecc8()
162 swap_bits(bch, src[3]); in load_ecc8()
164 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); in load_ecc8()
165 dst[nwords] = ((u32)swap_bits(bch, pad[0]) << 24) | in load_ecc8()
166 ((u32)swap_bits(bch, pad[1]) << 16) | in load_ecc8()
167 ((u32)swap_bits(bch, pad[2]) << 8) | in load_ecc8()
168 swap_bits(bch, pad[3]); in load_ecc8()
174 static void store_ecc8(struct bch_control *bch, uint8_t *dst, in store_ecc8() argument
178 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; in store_ecc8()
181 *dst++ = swap_bits(bch, src[i] >> 24); in store_ecc8()
182 *dst++ = swap_bits(bch, src[i] >> 16); in store_ecc8()
183 *dst++ = swap_bits(bch, src[i] >> 8); in store_ecc8()
184 *dst++ = swap_bits(bch, src[i]); in store_ecc8()
186 pad[0] = swap_bits(bch, src[nwords] >> 24); in store_ecc8()
187 pad[1] = swap_bits(bch, src[nwords] >> 16); in store_ecc8()
188 pad[2] = swap_bits(bch, src[nwords] >> 8); in store_ecc8()
189 pad[3] = swap_bits(bch, src[nwords]); 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
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, in bch_encode() argument
210 const unsigned int l = BCH_ECC_WORDS(bch)-1; in bch_encode()
214 const size_t r_bytes = BCH_ECC_WORDS(bch) * sizeof(*r); in bch_encode()
215 const uint32_t * const tab0 = bch->mod8_tab; 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()
235 bch_encode_unaligned(bch, data, mlen, bch->ecc_buf); in bch_encode()
245 memcpy(r, bch->ecc_buf, r_bytes); in bch_encode()
261 if (bch->swap_bits) in bch_encode()
262 w = (u32)swap_bits(bch, w) | in bch_encode()
263 ((u32)swap_bits(bch, w >> 8) << 8) | in bch_encode()
264 ((u32)swap_bits(bch, w >> 16) << 16) | in bch_encode()
265 ((u32)swap_bits(bch, w >> 24) << 24); 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()
289 static inline int modulo(struct bch_control *bch, unsigned int v) in modulo() argument
291 const unsigned int n = GF_N(bch); in modulo()
294 v = (v & n) + (v >> GF_M(bch)); in modulo()
302 static inline int mod_s(struct bch_control *bch, unsigned int v) in mod_s() argument
304 const unsigned int n = GF_N(bch); in mod_s()
328 static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, in gf_mul() argument
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()
335 static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) in gf_sqr() argument
337 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; in gf_sqr()
340 static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, in gf_div() argument
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()
347 static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) in gf_inv() argument
349 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; in gf_inv()
352 static inline unsigned int a_pow(struct bch_control *bch, int i) in a_pow() argument
354 return bch->a_pow_tab[modulo(bch, i)]; in a_pow()
357 static inline int a_log(struct bch_control *bch, unsigned int x) in a_log() argument
359 return bch->a_log_tab[x]; in a_log()
362 static inline int a_ilog(struct bch_control *bch, unsigned int x) in a_ilog() argument
364 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); in a_ilog()
370 static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, in compute_syndromes() argument
376 const int t = GF_T(bch); in compute_syndromes()
378 s = bch->ecc_bits; in compute_syndromes()
393 syn[j] ^= a_pow(bch, (j+1)*(i+s)); in compute_syndromes()
401 syn[2*j+1] = gf_sqr(bch, syn[j]); in compute_syndromes()
409 static int compute_error_locator_polynomial(struct bch_control *bch, in compute_error_locator_polynomial() argument
412 const unsigned int t = GF_T(bch); in compute_error_locator_polynomial()
413 const unsigned int n = GF_N(bch); in compute_error_locator_polynomial()
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()
434 tmp = a_log(bch, d)+n-a_log(bch, pd); 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()
454 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); in compute_error_locator_polynomial()
465 static int solve_linear_system(struct bch_control *bch, unsigned int *rows, in solve_linear_system() argument
468 const int m = GF_M(bch); in solve_linear_system()
538 static int find_affine4_roots(struct bch_control *bch, unsigned int a, in find_affine4_roots() argument
543 const int m = GF_M(bch); in find_affine4_roots()
546 j = a_log(bch, b); in find_affine4_roots()
547 k = a_log(bch, a); in find_affine4_roots()
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()
569 return solve_linear_system(bch, rows, roots, 4); in find_affine4_roots()
575 static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, in find_poly_deg1_roots() argument
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()
590 static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, in find_poly_deg2_roots() argument
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()
614 r ^= bch->xi_tab[i]; in find_poly_deg2_roots()
618 if ((gf_sqr(bch, r)^r) == u) { 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()
632 static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, in find_poly_deg3_roots() argument
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()
646 c = gf_mul(bch, a2, c2); /* c = a2c2 */ in find_poly_deg3_roots()
647 b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ in find_poly_deg3_roots()
648 a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ in find_poly_deg3_roots()
651 if (find_affine4_roots(bch, a, b, c, tmp) == 4) { in find_poly_deg3_roots()
655 roots[n++] = a_ilog(bch, tmp[i]); in find_poly_deg3_roots()
665 static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, in find_poly_deg4_roots() argument
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()
686 f = gf_div(bch, c, a); in find_poly_deg4_roots()
687 l = a_log(bch, f); in find_poly_deg4_roots()
688 l += (l & 1) ? GF_N(bch) : 0; in find_poly_deg4_roots()
689 e = a_pow(bch, l/2); in find_poly_deg4_roots()
697 d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; in find_poly_deg4_roots()
698 b = gf_mul(bch, a, e)^b; in find_poly_deg4_roots()
705 c2 = gf_inv(bch, d); in find_poly_deg4_roots()
706 b2 = gf_div(bch, a, d); in find_poly_deg4_roots()
707 a2 = gf_div(bch, b, d); in find_poly_deg4_roots()
715 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { in find_poly_deg4_roots()
718 f = a ? gf_inv(bch, roots[i]) : roots[i]; in find_poly_deg4_roots()
719 roots[i] = a_ilog(bch, f^e); in find_poly_deg4_roots()
729 static void gf_poly_logrep(struct bch_control *bch, in gf_poly_logrep() argument
732 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); 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()
742 static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, in gf_poly_mod() argument
754 rep = bch->cache; in gf_poly_mod()
755 gf_poly_logrep(bch, b, rep); in gf_poly_mod()
760 la = a_log(bch, c[j]); in gf_poly_mod()
765 c[p] ^= bch->a_pow_tab[mod_s(bch, in gf_poly_mod()
778 static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, in gf_poly_div() argument
784 gf_poly_mod(bch, a, b, NULL); in gf_poly_div()
796 static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, in gf_poly_gcd() argument
805 gf_poly_mod(bch, a, b, NULL); in gf_poly_gcd()
818 static void compute_trace_bk_mod(struct bch_control *bch, int k, in compute_trace_bk_mod() argument
822 const int m = GF_M(bch); in compute_trace_bk_mod()
828 z->c[1] = bch->a_pow_tab[k]; in compute_trace_bk_mod()
834 gf_poly_logrep(bch, f, bch->cache); in compute_trace_bk_mod()
840 z->c[2*j] = gf_sqr(bch, z->c[j]); in compute_trace_bk_mod()
849 gf_poly_mod(bch, z, f, bch->cache); in compute_trace_bk_mod()
861 static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f, in factor_polynomial() argument
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()
876 compute_trace_bk_mod(bch, k, f, z, tk); in factor_polynomial()
881 gcd = gf_poly_gcd(bch, f2, tk); in factor_polynomial()
884 gf_poly_div(bch, f, gcd, q); in factor_polynomial()
897 static int find_poly_roots(struct bch_control *bch, unsigned int k, in find_poly_roots() argument
906 cnt = find_poly_deg1_roots(bch, poly, roots); in find_poly_roots()
909 cnt = find_poly_deg2_roots(bch, poly, roots); in find_poly_roots()
912 cnt = find_poly_deg3_roots(bch, poly, roots); in find_poly_roots()
915 cnt = find_poly_deg4_roots(bch, poly, roots); in find_poly_roots()
920 if (poly->deg && (k <= GF_M(bch))) { in find_poly_roots()
921 factor_polynomial(bch, k, poly, &f1, &f2); in find_poly_roots()
923 cnt += find_poly_roots(bch, k+1, f1, roots); in find_poly_roots()
925 cnt += find_poly_roots(bch, k+1, f2, roots+cnt); in find_poly_roots()
937 static int chien_search(struct bch_control *bch, unsigned int len, in chien_search() argument
942 const unsigned int k = 8*len+bch->ecc_bits; 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()
952 m = bch->cache[j]; in chien_search()
954 syn ^= a_pow(bch, m+j*i); in chien_search()
957 roots[count++] = GF_N(bch)-i; in chien_search()
969 * @bch: BCH control structure
981 * Depending on the available hw BCH support and the need to compute @calc_ecc
986 * bch_decode(@bch, @data, @len, @recv_ecc, NULL, NULL, @errloc)
989 * bch_decode(@bch, NULL, @len, @recv_ecc, @calc_ecc, NULL, @errloc)
992 * bch_decode(@bch, NULL, @len, NULL, ecc, NULL, @errloc)
995 * bch_decode(@bch, NULL, @len, NULL, NULL, @syn, @errloc)
1009 int bch_decode(struct bch_control *bch, const uint8_t *data, unsigned int len, in bch_decode() argument
1013 const unsigned int ecc_words = BCH_ECC_WORDS(bch); in bch_decode()
1019 if (8*len > (bch->n-bch->ecc_bits)) in bch_decode()
1028 bch_encode(bch, data, len, NULL); 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()
1049 err = compute_error_locator_polynomial(bch, syn); in bch_decode()
1051 nroots = find_poly_roots(bch, 1, bch->elp, errloc); in bch_decode()
1057 nbits = (len*8)+bch->ecc_bits; in bch_decode()
1064 if (!bch->swap_bits) in bch_decode()
1076 static int build_gf_tables(struct bch_control *bch, unsigned int poly) in build_gf_tables() argument
1082 if (k != (1u << GF_M(bch))) in build_gf_tables()
1085 for (i = 0; i < GF_N(bch); i++) { 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()
1095 bch->a_pow_tab[GF_N(bch)] = 1; in build_gf_tables()
1096 bch->a_log_tab[0] = 0; in build_gf_tables()
1104 static void build_mod8_tables(struct bch_control *bch, const uint32_t *g) in build_mod8_tables() argument
1108 const int l = BCH_ECC_WORDS(bch); in build_mod8_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()
1138 static int build_deg2_base(struct bch_control *bch) in build_deg2_base() argument
1140 const int m = GF_M(bch); in build_deg2_base()
1147 sum ^= a_pow(bch, i*(1 << j)); in build_deg2_base()
1150 ak = bch->a_pow_tab[i]; in build_deg2_base()
1158 for (x = 0; (x <= GF_N(bch)) && remaining; x++) { in build_deg2_base()
1159 y = gf_sqr(bch, x)^x; in build_deg2_base()
1161 r = a_log(bch, y); in build_deg2_base()
1163 bch->xi_tab[r] = x; in build_deg2_base()
1189 static uint32_t *compute_generator_polynomial(struct bch_control *bch) in compute_generator_polynomial() argument
1191 const unsigned int m = GF_M(bch); in compute_generator_polynomial()
1192 const unsigned int t = GF_T(bch); in compute_generator_polynomial()
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()
1213 r = mod_s(bch, 2*r); in compute_generator_polynomial()
1219 for (i = 0; i < GF_N(bch); i++) { in compute_generator_polynomial()
1222 r = bch->a_pow_tab[i]; 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()
1244 bch->ecc_bits = g->deg; in compute_generator_polynomial()
1254 * bch_init - initialize a BCH encoder/decoder
1261 * a newly allocated BCH control structure if successful, NULL otherwise
1272 * BCH control structure, ecc length in bytes is given by member @ecc_bytes of
1281 struct bch_control *bch = NULL; in bch_init() local
1293 printk(KERN_ERR "bch encoder/decoder was configured to support " in bch_init()
1323 bch = kzalloc(sizeof(*bch), GFP_KERNEL); in bch_init()
1324 if (bch == NULL) 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()
1349 err = build_gf_tables(bch, prim_poly); in bch_init()
1354 genpoly = compute_generator_polynomial(bch); in bch_init()
1358 build_mod8_tables(bch, genpoly); in bch_init()
1361 err = build_deg2_base(bch); in bch_init()
1365 return bch; in bch_init()
1368 bch_free(bch); in bch_init()
1374 * bch_free - free the BCH control structure
1375 * @bch: BCH control structure to release
1377 void bch_free(struct bch_control *bch) in bch_free() argument
1381 if (bch) { in bch_free()
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()
1395 kfree(bch); in bch_free()
1402 MODULE_DESCRIPTION("Binary BCH encoder/decoder");