68 #include <linux/kernel.h>
69 #include <linux/errno.h>
71 #include <linux/module.h>
72 #include <linux/slab.h>
73 #include <linux/bitops.h>
74 #include <asm/byteorder.h>
77 #if defined(CONFIG_BCH_CONST_PARAMS)
78 #define GF_M(_p) (CONFIG_BCH_CONST_M)
79 #define GF_T(_p) (CONFIG_BCH_CONST_T)
80 #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
82 #define GF_M(_p) ((_p)->m)
83 #define GF_T(_p) ((_p)->t)
84 #define GF_N(_p) ((_p)->n)
87 #define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32)
88 #define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8)
91 #define dbg(_fmt, args...) do {} while (0)
103 #define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int))
114 static void encode_bch_unaligned(
struct bch_control *bch,
115 const unsigned char *
data,
unsigned int len,
123 p = bch->
mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff);
125 for (i = 0; i <
l; i++)
126 ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++);
128 ecc[
l] = (ecc[
l] << 8)^(*p);
141 for (i = 0; i < nwords; i++, src += 4)
142 dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3];
145 dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3];
157 for (i = 0; i < nwords; i++) {
158 *dst++ = (src[
i] >> 24);
159 *dst++ = (src[
i] >> 16) & 0xff;
160 *dst++ = (src[
i] >> 8) & 0xff;
161 *dst++ = (src[
i] >> 0) & 0xff;
163 pad[0] = (src[nwords] >> 24);
164 pad[1] = (src[nwords] >> 16) & 0xff;
165 pad[2] = (src[nwords] >> 8) & 0xff;
166 pad[3] = (src[nwords] >> 0) & 0xff;
188 unsigned int i, mlen;
192 const uint32_t *
const tab1 = tab0 + 256*(l+1);
193 const uint32_t *
const tab2 = tab1 + 256*(l+1);
194 const uint32_t *
const tab3 = tab2 + 256*(l+1);
199 load_ecc8(bch, bch->
ecc_buf, ecc);
205 m = ((
unsigned long)data) & 3;
207 mlen = (len < (4-
m)) ? len : 4-
m;
208 encode_bch_unaligned(bch, data, mlen, bch->
ecc_buf);
234 p0 = tab0 + (l+1)*((w >> 0) & 0xff);
235 p1 = tab1 + (l+1)*((w >> 8) & 0xff);
236 p2 = tab2 + (l+1)*((w >> 16) & 0xff);
237 p3 = tab3 + (l+1)*((w >> 24) & 0xff);
239 for (i = 0; i <
l; i++)
240 r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i];
242 r[
l] = p0[
l]^p1[
l]^p2[
l]^p3[
l];
248 encode_bch_unaligned(bch, data, len, bch->
ecc_buf);
252 store_ecc8(bch, ecc, bch->
ecc_buf);
258 const unsigned int n =
GF_N(bch);
261 v = (v &
n) + (v >>
GF_M(bch));
269 static inline int mod_s(
struct bch_control *bch,
unsigned int v)
271 const unsigned int n =
GF_N(bch);
272 return (v < n) ? v : v-
n;
275 static inline int deg(
unsigned int poly)
281 static inline int parity(
unsigned int x)
289 x = (x & 0x11111111
U) * 0x11111111U;
290 return (x >> 28) & 1;
295 static inline unsigned int gf_mul(
struct bch_control *bch,
unsigned int a,
302 static inline unsigned int gf_sqr(
struct bch_control *bch,
unsigned int a)
307 static inline unsigned int gf_div(
struct bch_control *bch,
unsigned int a,
314 static inline unsigned int gf_inv(
struct bch_control *bch,
unsigned int a)
319 static inline unsigned int a_pow(
struct bch_control *bch,
int i)
324 static inline int a_log(
struct bch_control *bch,
unsigned int x)
329 static inline int a_ilog(
struct bch_control *bch,
unsigned int x)
343 const int t =
GF_T(bch);
348 m = ((
unsigned int)s) & 31;
350 ecc[s/32] &= ~((1
u << (32-
m))-1);
351 memset(syn, 0, 2*t*
sizeof(*syn));
359 for (j = 0; j < 2*
t; j += 2)
360 syn[j] ^= a_pow(bch, (j+1)*(i+s));
367 for (j = 0; j <
t; j++)
368 syn[2*j+1] = gf_sqr(bch, syn[j]);
371 static void gf_poly_copy(
struct gf_poly *dst,
struct gf_poly *src)
376 static int compute_error_locator_polynomial(
struct bch_control *bch,
377 const unsigned int *syn)
379 const unsigned int t =
GF_T(bch);
380 const unsigned int n =
GF_N(bch);
381 unsigned int i,
j,
tmp,
l,
pd = 1,
d = syn[0];
396 for (i = 0; (i <
t) && (elp->
deg <= t); i++) {
399 gf_poly_copy(elp_copy, elp);
401 tmp = a_log(bch,
d)+n-a_log(bch, pd);
402 for (j = 0; j <= pelp->
deg; j++) {
404 l = a_log(bch, pelp->
c[j]);
405 elp->
c[j+
k] ^= a_pow(bch, tmp+l);
410 if (tmp > elp->
deg) {
412 gf_poly_copy(pelp, elp_copy);
420 for (j = 1; j <= elp->
deg; j++)
421 d ^= gf_mul(bch, elp->
c[j], syn[2*i+2-j]);
424 dbg(
"elp=%s\n", gf_poly_str(elp));
425 return (elp->
deg > t) ? -1 : (
int)elp->
deg;
432 static int solve_linear_system(
struct bch_control *bch,
unsigned int *
rows,
433 unsigned int *sol,
int nsol)
435 const int m =
GF_M(bch);
443 for (c = 0; c <
m; c++) {
447 for (r = p; r <
m; r++) {
448 if (rows[r] & mask) {
461 for (r = rem; r <
m; r++) {
474 for (r = m-1; r >= 0; r--) {
475 if ((r > m-1-k) && rows[r])
479 rows[
r] = (p && (r == param[p-1])) ?
480 p--, 1
u << (m-
r) : rows[r-p];
484 if (nsol != (1 << k))
488 for (p = 0; p < nsol; p++) {
490 for (c = 0; c <
k; c++)
491 rows[param[c]] = (rows[param[c]] & ~1)|((p >>
c) & 1);
495 for (r = m-1; r >= 0; r--) {
496 mask = rows[
r] & (tmp|1);
508 static int find_affine4_roots(
struct bch_control *bch,
unsigned int a,
509 unsigned int b,
unsigned int c,
513 const int m =
GF_M(bch);
514 unsigned int mask = 0xff,
t, rows[16] = {0,};
521 for (i = 0; i <
m; i++) {
532 for (j = 8; j != 0; j >>= 1, mask ^= (mask <<
j)) {
533 for (k = 0; k < 16; k = (k+j+1) & ~j) {
534 t = ((rows[
k] >>
j)^rows[k+j]) &
mask;
539 return solve_linear_system(bch, rows, roots, 4);
563 int n = 0,
i, l0,
l1,
l2;
564 unsigned int u,
v,
r;
566 if (poly->
c[0] && poly->
c[1]) {
573 u = a_pow(bch, l0+l2+2*(
GF_N(bch)-l1));
588 if ((gf_sqr(bch, r)^r) ==
u) {
606 unsigned int a,
b,
c,
a2, b2, c2,
e3, tmp[4];
611 c2 = gf_div(bch, poly->
c[0], e3);
612 b2 = gf_div(bch, poly->
c[1], e3);
613 a2 = gf_div(bch, poly->
c[2], e3);
616 c = gf_mul(bch, a2, c2);
617 b = gf_mul(bch, a2, b2)^c2;
618 a = gf_sqr(bch, a2)^b2;
621 if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
623 for (i = 0; i < 4; i++) {
625 roots[n++] = a_ilog(bch, tmp[i]);
639 unsigned int a,
b,
c,
d,
e = 0,
f,
a2, b2, c2, e4;
646 d = gf_div(bch, poly->
c[0], e4);
647 c = gf_div(bch, poly->
c[1], e4);
648 b = gf_div(bch, poly->
c[2], e4);
649 a = gf_div(bch, poly->
c[3], e4);
656 f = gf_div(bch, c, a);
658 l += (l & 1) ?
GF_N(bch) : 0;
667 d = a_pow(bch, 2*l)^gf_mul(bch, b,
f)^
d;
668 b = gf_mul(bch, a, e)^
b;
676 b2 = gf_div(bch, a, d);
677 a2 = gf_div(bch, b, d);
685 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
686 for (i = 0; i < 4; i++) {
688 f = a ? gf_inv(bch, roots[i]) : roots[i];
689 roots[
i] = a_ilog(bch,
f^e);
699 static void gf_poly_logrep(
struct bch_control *bch,
702 int i, d = a->
deg, l =
GF_N(bch)-a_log(bch, a->
c[a->
deg]);
705 for (i = 0; i <
d; i++)
706 rep[i] = a->
c[i] ? mod_s(bch, a_log(bch, a->
c[i])+l) : -1;
713 const struct gf_poly *b,
int *rep)
716 unsigned int i,
j, *c = a->
c;
717 const unsigned int d = b->
deg;
725 gf_poly_logrep(bch, b, rep);
728 for (j = a->
deg; j >= d; j--) {
730 la = a_log(bch, c[j]);
732 for (i = 0; i <
d; i++, p++) {
741 while (!c[a->
deg] && a->
deg)
754 gf_poly_mod(bch, a, b,
NULL);
771 dbg(
"gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b));
780 gf_poly_mod(bch, a, b,
NULL);
786 dbg(
"%s\n", gf_poly_str(a));
795 static void compute_trace_bk_mod(
struct bch_control *bch,
int k,
799 const int m =
GF_M(bch);
811 gf_poly_logrep(bch, f, bch->
cache);
813 for (i = 0; i <
m; i++) {
815 for (j = z->
deg; j >= 0; j--) {
816 out->
c[
j] ^= z->
c[
j];
817 z->
c[2*
j] = gf_sqr(bch, z->
c[j]);
826 gf_poly_mod(bch, z, f, bch->
cache);
829 while (!out->
c[out->
deg] && out->
deg)
832 dbg(
"Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out));
847 dbg(
"factoring %s...\n", gf_poly_str(f));
853 compute_trace_bk_mod(bch, k, f, z, tk);
858 gcd = gf_poly_gcd(bch, f2, tk);
861 gf_poly_div(bch, f, gcd, q);
864 gf_poly_copy(*g, gcd);
874 static int find_poly_roots(
struct bch_control *bch,
unsigned int k,
875 struct gf_poly *poly,
unsigned int *roots)
883 cnt = find_poly_deg1_roots(bch, poly, roots);
886 cnt = find_poly_deg2_roots(bch, poly, roots);
889 cnt = find_poly_deg3_roots(bch, poly, roots);
892 cnt = find_poly_deg4_roots(bch, poly, roots);
897 if (poly->
deg && (k <=
GF_M(bch))) {
898 factor_polynomial(bch, k, poly, &f1, &f2);
900 cnt += find_poly_roots(bch, k+1, f1, roots);
902 cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
909 #if defined(USE_CHIEN_SEARCH)
914 static int chien_search(
struct bch_control *bch,
unsigned int len,
915 struct gf_poly *p,
unsigned int *roots)
919 const unsigned int k = 8*len+bch->
ecc_bits;
922 gf_poly_logrep(bch, p, bch->
cache);
924 syn0 = gf_div(bch, p->
c[0], p->
c[p->
deg]);
926 for (i =
GF_N(bch)-k+1; i <=
GF_N(bch); i++) {
928 for (j = 1, syn = syn0; j <= p->
deg; j++) {
931 syn ^= a_pow(bch, m+j*i);
934 roots[count++] =
GF_N(bch)-
i;
939 return (count == p->
deg) ? count : 0;
941 #define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc)
988 const unsigned int *syn,
unsigned int *errloc)
1003 if (!data || !recv_ecc)
1008 load_ecc8(bch, bch->
ecc_buf, calc_ecc);
1012 load_ecc8(bch, bch->
ecc_buf2, recv_ecc);
1014 for (i = 0, sum = 0; i < (
int)ecc_words; i++) {
1022 compute_syndromes(bch, bch->
ecc_buf, bch->
syn);
1026 err = compute_error_locator_polynomial(bch, syn);
1028 nroots = find_poly_roots(bch, 1, bch->
elp, errloc);
1035 for (i = 0; i <
err; i++) {
1036 if (errloc[i] >= nbits) {
1040 errloc[
i] = nbits-1-errloc[
i];
1041 errloc[
i] = (errloc[
i] & ~7)|(7-(errloc[i] & 7));
1044 return (err >= 0) ? err : -
EBADMSG;
1051 static int build_gf_tables(
struct bch_control *bch,
unsigned int poly)
1053 unsigned int i, x = 1;
1054 const unsigned int k = 1 <<
deg(poly);
1057 if (k != (1u <<
GF_M(bch)))
1060 for (i = 0; i <
GF_N(bch); i++) {
1089 for (i = 0; i < 256; i++) {
1091 for (b = 0; b < 4; b++) {
1098 data ^= g[0] >> (31-
d);
1099 for (j = 0; j < ecclen; j++) {
1100 hi = (d < 31) ? g[j] << (d+1) : 0;
1102 g[j+1] >> (31-d) : 0;
1113 static int build_deg2_base(
struct bch_control *bch)
1115 const int m =
GF_M(bch);
1117 unsigned int sum,
x,
y, remaining, ak = 0,
xi[
m];
1120 for (i = 0; i <
m; i++) {
1121 for (j = 0, sum = 0; j <
m; j++)
1122 sum ^= a_pow(bch, i*(1 << j));
1131 memset(xi, 0,
sizeof(xi));
1133 for (x = 0; (x <=
GF_N(bch)) && remaining; x++) {
1134 y = gf_sqr(bch, x)^
x;
1135 for (i = 0; i < 2; i++) {
1137 if (y && (r < m) && !xi[r]) {
1141 dbg(
"x%d = %x\n", r, x);
1148 return remaining ? -1 : 0;
1151 static void *bch_alloc(
size_t size,
int *
err)
1166 const unsigned int m =
GF_M(bch);
1167 const unsigned int t =
GF_T(bch);
1169 unsigned int i,
j, nbits,
r,
word, *roots;
1174 roots = bch_alloc((bch->
n+1)*
sizeof(*roots), &err);
1175 genpoly = bch_alloc(
DIV_ROUND_UP(m*t+1, 32)*
sizeof(*genpoly), &err);
1184 memset(roots , 0, (bch->
n+1)*
sizeof(*roots));
1185 for (i = 0; i <
t; i++) {
1186 for (j = 0, r = 2*i+1; j <
m; j++) {
1188 r = mod_s(bch, 2*r);
1194 for (i = 0; i <
GF_N(bch); i++) {
1199 for (j = g->
deg; j > 0; j--)
1200 g->
c[
j] = gf_mul(bch, g->
c[j], r)^g->
c[j-1];
1202 g->
c[0] = gf_mul(bch, g->
c[0], r);
1211 nbits = (n > 32) ? 32 : n;
1212 for (j = 0, word = 0; j < nbits; j++) {
1214 word |= 1u << (31-
j);
1216 genpoly[i++] =
word;
1252 unsigned int i, words;
1256 const int min_m = 5;
1257 const int max_m = 15;
1260 static const unsigned int prim_poly_tab[] = {
1261 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b,
1265 #if defined(CONFIG_BCH_CONST_PARAMS)
1266 if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) {
1268 "parameters m=%d, t=%d only!\n",
1269 CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T);
1273 if ((m < min_m) || (m > max_m))
1282 if ((t < 1) || (m*t >= ((1 << m)-1)))
1288 prim_poly = prim_poly_tab[m-min_m];
1296 bch->
n = (1 <<
m)-1;
1305 bch->
syn = bch_alloc(2*t*
sizeof(*bch->
syn), &err);
1306 bch->
cache = bch_alloc(2*t*
sizeof(*bch->
cache), &err);
1315 err = build_gf_tables(bch, prim_poly);
1320 genpoly = compute_generator_polynomial(bch);
1321 if (genpoly ==
NULL)
1324 build_mod8_tables(bch, genpoly);
1327 err = build_deg2_base(bch);