1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <common.h>
58#include <ubi_uboot.h>
59
60#include <linux/bitops.h>
61#include <asm/byteorder.h>
62#include <linux/bch.h>
63
64#if defined(CONFIG_BCH_CONST_PARAMS)
65#define GF_M(_p) (CONFIG_BCH_CONST_M)
66#define GF_T(_p) (CONFIG_BCH_CONST_T)
67#define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1)
68#else
69#define GF_M(_p) ((_p)->m)
70#define GF_T(_p) ((_p)->t)
71#define GF_N(_p) ((_p)->n)
72#endif
73
74#define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32)
75#define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8)
76
77#ifndef dbg
78#define dbg(_fmt, args...) do {} while (0)
79#endif
80
81
82
83
84struct gf_poly {
85 unsigned int deg;
86 unsigned int c[0];
87};
88
89
90#define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int))
91
92
93struct gf_poly_deg1 {
94 struct gf_poly poly;
95 unsigned int c[2];
96};
97
98
99
100
101static void encode_bch_unaligned(struct bch_control *bch,
102 const unsigned char *data, unsigned int len,
103 uint32_t *ecc)
104{
105 int i;
106 const uint32_t *p;
107 const int l = BCH_ECC_WORDS(bch)-1;
108
109 while (len--) {
110 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff);
111
112 for (i = 0; i < l; i++)
113 ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++);
114
115 ecc[l] = (ecc[l] << 8)^(*p);
116 }
117}
118
119
120
121
122static void load_ecc8(struct bch_control *bch, uint32_t *dst,
123 const uint8_t *src)
124{
125 uint8_t pad[4] = {0, 0, 0, 0};
126 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
127
128 for (i = 0; i < nwords; i++, src += 4)
129 dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3];
130
131 memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords);
132 dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3];
133}
134
135
136
137
138static void store_ecc8(struct bch_control *bch, uint8_t *dst,
139 const uint32_t *src)
140{
141 uint8_t pad[4];
142 unsigned int i, nwords = BCH_ECC_WORDS(bch)-1;
143
144 for (i = 0; i < nwords; i++) {
145 *dst++ = (src[i] >> 24);
146 *dst++ = (src[i] >> 16) & 0xff;
147 *dst++ = (src[i] >> 8) & 0xff;
148 *dst++ = (src[i] >> 0) & 0xff;
149 }
150 pad[0] = (src[nwords] >> 24);
151 pad[1] = (src[nwords] >> 16) & 0xff;
152 pad[2] = (src[nwords] >> 8) & 0xff;
153 pad[3] = (src[nwords] >> 0) & 0xff;
154 memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords);
155}
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171void encode_bch(struct bch_control *bch, const uint8_t *data,
172 unsigned int len, uint8_t *ecc)
173{
174 const unsigned int l = BCH_ECC_WORDS(bch)-1;
175 unsigned int i, mlen;
176 unsigned long m;
177 uint32_t w, r[l+1];
178 const uint32_t * const tab0 = bch->mod8_tab;
179 const uint32_t * const tab1 = tab0 + 256*(l+1);
180 const uint32_t * const tab2 = tab1 + 256*(l+1);
181 const uint32_t * const tab3 = tab2 + 256*(l+1);
182 const uint32_t *pdata, *p0, *p1, *p2, *p3;
183
184 if (ecc) {
185
186 load_ecc8(bch, bch->ecc_buf, ecc);
187 } else {
188 memset(bch->ecc_buf, 0, sizeof(r));
189 }
190
191
192 m = ((unsigned long)data) & 3;
193 if (m) {
194 mlen = (len < (4-m)) ? len : 4-m;
195 encode_bch_unaligned(bch, data, mlen, bch->ecc_buf);
196 data += mlen;
197 len -= mlen;
198 }
199
200
201 pdata = (uint32_t *)data;
202 mlen = len/4;
203 data += 4*mlen;
204 len -= 4*mlen;
205 memcpy(r, bch->ecc_buf, sizeof(r));
206
207
208
209
210
211
212
213
214
215
216
217
218 while (mlen--) {
219
220 w = r[0]^cpu_to_be32(*pdata++);
221 p0 = tab0 + (l+1)*((w >> 0) & 0xff);
222 p1 = tab1 + (l+1)*((w >> 8) & 0xff);
223 p2 = tab2 + (l+1)*((w >> 16) & 0xff);
224 p3 = tab3 + (l+1)*((w >> 24) & 0xff);
225
226 for (i = 0; i < l; i++)
227 r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i];
228
229 r[l] = p0[l]^p1[l]^p2[l]^p3[l];
230 }
231 memcpy(bch->ecc_buf, r, sizeof(r));
232
233
234 if (len)
235 encode_bch_unaligned(bch, data, len, bch->ecc_buf);
236
237
238 if (ecc)
239 store_ecc8(bch, ecc, bch->ecc_buf);
240}
241
242static inline int modulo(struct bch_control *bch, unsigned int v)
243{
244 const unsigned int n = GF_N(bch);
245 while (v >= n) {
246 v -= n;
247 v = (v & n) + (v >> GF_M(bch));
248 }
249 return v;
250}
251
252
253
254
255static inline int mod_s(struct bch_control *bch, unsigned int v)
256{
257 const unsigned int n = GF_N(bch);
258 return (v < n) ? v : v-n;
259}
260
261static inline int deg(unsigned int poly)
262{
263
264 return fls(poly)-1;
265}
266
267static inline int parity(unsigned int x)
268{
269
270
271
272
273 x ^= x >> 1;
274 x ^= x >> 2;
275 x = (x & 0x11111111U) * 0x11111111U;
276 return (x >> 28) & 1;
277}
278
279
280
281static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a,
282 unsigned int b)
283{
284 return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
285 bch->a_log_tab[b])] : 0;
286}
287
288static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a)
289{
290 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;
291}
292
293static inline unsigned int gf_div(struct bch_control *bch, unsigned int a,
294 unsigned int b)
295{
296 return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+
297 GF_N(bch)-bch->a_log_tab[b])] : 0;
298}
299
300static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a)
301{
302 return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]];
303}
304
305static inline unsigned int a_pow(struct bch_control *bch, int i)
306{
307 return bch->a_pow_tab[modulo(bch, i)];
308}
309
310static inline int a_log(struct bch_control *bch, unsigned int x)
311{
312 return bch->a_log_tab[x];
313}
314
315static inline int a_ilog(struct bch_control *bch, unsigned int x)
316{
317 return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]);
318}
319
320
321
322
323static void compute_syndromes(struct bch_control *bch, uint32_t *ecc,
324 unsigned int *syn)
325{
326 int i, j, s;
327 unsigned int m;
328 uint32_t poly;
329 const int t = GF_T(bch);
330
331 s = bch->ecc_bits;
332
333
334 m = ((unsigned int)s) & 31;
335 if (m)
336 ecc[s/32] &= ~((1u << (32-m))-1);
337 memset(syn, 0, 2*t*sizeof(*syn));
338
339
340 do {
341 poly = *ecc++;
342 s -= 32;
343 while (poly) {
344 i = deg(poly);
345 for (j = 0; j < 2*t; j += 2)
346 syn[j] ^= a_pow(bch, (j+1)*(i+s));
347
348 poly ^= (1 << i);
349 }
350 } while (s > 0);
351
352
353 for (j = 0; j < t; j++)
354 syn[2*j+1] = gf_sqr(bch, syn[j]);
355}
356
357static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src)
358{
359 memcpy(dst, src, GF_POLY_SZ(src->deg));
360}
361
362static int compute_error_locator_polynomial(struct bch_control *bch,
363 const unsigned int *syn)
364{
365 const unsigned int t = GF_T(bch);
366 const unsigned int n = GF_N(bch);
367 unsigned int i, j, tmp, l, pd = 1, d = syn[0];
368 struct gf_poly *elp = bch->elp;
369 struct gf_poly *pelp = bch->poly_2t[0];
370 struct gf_poly *elp_copy = bch->poly_2t[1];
371 int k, pp = -1;
372
373 memset(pelp, 0, GF_POLY_SZ(2*t));
374 memset(elp, 0, GF_POLY_SZ(2*t));
375
376 pelp->deg = 0;
377 pelp->c[0] = 1;
378 elp->deg = 0;
379 elp->c[0] = 1;
380
381
382 for (i = 0; (i < t) && (elp->deg <= t); i++) {
383 if (d) {
384 k = 2*i-pp;
385 gf_poly_copy(elp_copy, elp);
386
387 tmp = a_log(bch, d)+n-a_log(bch, pd);
388 for (j = 0; j <= pelp->deg; j++) {
389 if (pelp->c[j]) {
390 l = a_log(bch, pelp->c[j]);
391 elp->c[j+k] ^= a_pow(bch, tmp+l);
392 }
393 }
394
395 tmp = pelp->deg+k;
396 if (tmp > elp->deg) {
397 elp->deg = tmp;
398 gf_poly_copy(pelp, elp_copy);
399 pd = d;
400 pp = 2*i;
401 }
402 }
403
404 if (i < t-1) {
405 d = syn[2*i+2];
406 for (j = 1; j <= elp->deg; j++)
407 d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);
408 }
409 }
410 dbg("elp=%s\n", gf_poly_str(elp));
411 return (elp->deg > t) ? -1 : (int)elp->deg;
412}
413
414
415
416
417
418static int solve_linear_system(struct bch_control *bch, unsigned int *rows,
419 unsigned int *sol, int nsol)
420{
421 const int m = GF_M(bch);
422 unsigned int tmp, mask;
423 int rem, c, r, p, k, param[m];
424
425 k = 0;
426 mask = 1 << m;
427
428
429 for (c = 0; c < m; c++) {
430 rem = 0;
431 p = c-k;
432
433 for (r = p; r < m; r++) {
434 if (rows[r] & mask) {
435 if (r != p) {
436 tmp = rows[r];
437 rows[r] = rows[p];
438 rows[p] = tmp;
439 }
440 rem = r+1;
441 break;
442 }
443 }
444 if (rem) {
445
446 tmp = rows[p];
447 for (r = rem; r < m; r++) {
448 if (rows[r] & mask)
449 rows[r] ^= tmp;
450 }
451 } else {
452
453 param[k++] = c;
454 }
455 mask >>= 1;
456 }
457
458 if (k > 0) {
459 p = k;
460 for (r = m-1; r >= 0; r--) {
461 if ((r > m-1-k) && rows[r])
462
463 return 0;
464
465 rows[r] = (p && (r == param[p-1])) ?
466 p--, 1u << (m-r) : rows[r-p];
467 }
468 }
469
470 if (nsol != (1 << k))
471
472 return 0;
473
474 for (p = 0; p < nsol; p++) {
475
476 for (c = 0; c < k; c++)
477 rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1);
478
479
480 tmp = 0;
481 for (r = m-1; r >= 0; r--) {
482 mask = rows[r] & (tmp|1);
483 tmp |= parity(mask) << (m-r);
484 }
485 sol[p] = tmp >> 1;
486 }
487 return nsol;
488}
489
490
491
492
493
494static int find_affine4_roots(struct bch_control *bch, unsigned int a,
495 unsigned int b, unsigned int c,
496 unsigned int *roots)
497{
498 int i, j, k;
499 const int m = GF_M(bch);
500 unsigned int mask = 0xff, t, rows[16] = {0,};
501
502 j = a_log(bch, b);
503 k = a_log(bch, a);
504 rows[0] = c;
505
506
507 for (i = 0; i < m; i++) {
508 rows[i+1] = bch->a_pow_tab[4*i]^
509 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^
510 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0);
511 j++;
512 k += 2;
513 }
514
515
516
517
518 for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) {
519 for (k = 0; k < 16; k = (k+j+1) & ~j) {
520 t = ((rows[k] >> j)^rows[k+j]) & mask;
521 rows[k] ^= (t << j);
522 rows[k+j] ^= t;
523 }
524 }
525 return solve_linear_system(bch, rows, roots, 4);
526}
527
528
529
530
531static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly,
532 unsigned int *roots)
533{
534 int n = 0;
535
536 if (poly->c[0])
537
538 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+
539 bch->a_log_tab[poly->c[1]]);
540 return n;
541}
542
543
544
545
546static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly,
547 unsigned int *roots)
548{
549 int n = 0, i, l0, l1, l2;
550 unsigned int u, v, r;
551
552 if (poly->c[0] && poly->c[1]) {
553
554 l0 = bch->a_log_tab[poly->c[0]];
555 l1 = bch->a_log_tab[poly->c[1]];
556 l2 = bch->a_log_tab[poly->c[2]];
557
558
559 u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));
560
561
562
563
564
565
566 r = 0;
567 v = u;
568 while (v) {
569 i = deg(v);
570 r ^= bch->xi_tab[i];
571 v ^= (1 << i);
572 }
573
574 if ((gf_sqr(bch, r)^r) == u) {
575
576 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
577 bch->a_log_tab[r]+l2);
578 roots[n++] = modulo(bch, 2*GF_N(bch)-l1-
579 bch->a_log_tab[r^1]+l2);
580 }
581 }
582 return n;
583}
584
585
586
587
588static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly,
589 unsigned int *roots)
590{
591 int i, n = 0;
592 unsigned int a, b, c, a2, b2, c2, e3, tmp[4];
593
594 if (poly->c[0]) {
595
596 e3 = poly->c[3];
597 c2 = gf_div(bch, poly->c[0], e3);
598 b2 = gf_div(bch, poly->c[1], e3);
599 a2 = gf_div(bch, poly->c[2], e3);
600
601
602 c = gf_mul(bch, a2, c2);
603 b = gf_mul(bch, a2, b2)^c2;
604 a = gf_sqr(bch, a2)^b2;
605
606
607 if (find_affine4_roots(bch, a, b, c, tmp) == 4) {
608
609 for (i = 0; i < 4; i++) {
610 if (tmp[i] != a2)
611 roots[n++] = a_ilog(bch, tmp[i]);
612 }
613 }
614 }
615 return n;
616}
617
618
619
620
621static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly,
622 unsigned int *roots)
623{
624 int i, l, n = 0;
625 unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4;
626
627 if (poly->c[0] == 0)
628 return 0;
629
630
631 e4 = poly->c[4];
632 d = gf_div(bch, poly->c[0], e4);
633 c = gf_div(bch, poly->c[1], e4);
634 b = gf_div(bch, poly->c[2], e4);
635 a = gf_div(bch, poly->c[3], e4);
636
637
638 if (a) {
639
640 if (c) {
641
642 f = gf_div(bch, c, a);
643 l = a_log(bch, f);
644 l += (l & 1) ? GF_N(bch) : 0;
645 e = a_pow(bch, l/2);
646
647
648
649
650
651
652
653 d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;
654 b = gf_mul(bch, a, e)^b;
655 }
656
657 if (d == 0)
658
659 return 0;
660
661 c2 = gf_inv(bch, d);
662 b2 = gf_div(bch, a, d);
663 a2 = gf_div(bch, b, d);
664 } else {
665
666 c2 = d;
667 b2 = c;
668 a2 = b;
669 }
670
671 if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) {
672 for (i = 0; i < 4; i++) {
673
674 f = a ? gf_inv(bch, roots[i]) : roots[i];
675 roots[i] = a_ilog(bch, f^e);
676 }
677 n = 4;
678 }
679 return n;
680}
681
682
683
684
685static void gf_poly_logrep(struct bch_control *bch,
686 const struct gf_poly *a, int *rep)
687{
688 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]);
689
690
691 for (i = 0; i < d; i++)
692 rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1;
693}
694
695
696
697
698static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a,
699 const struct gf_poly *b, int *rep)
700{
701 int la, p, m;
702 unsigned int i, j, *c = a->c;
703 const unsigned int d = b->deg;
704
705 if (a->deg < d)
706 return;
707
708
709 if (!rep) {
710 rep = bch->cache;
711 gf_poly_logrep(bch, b, rep);
712 }
713
714 for (j = a->deg; j >= d; j--) {
715 if (c[j]) {
716 la = a_log(bch, c[j]);
717 p = j-d;
718 for (i = 0; i < d; i++, p++) {
719 m = rep[i];
720 if (m >= 0)
721 c[p] ^= bch->a_pow_tab[mod_s(bch,
722 m+la)];
723 }
724 }
725 }
726 a->deg = d-1;
727 while (!c[a->deg] && a->deg)
728 a->deg--;
729}
730
731
732
733
734static void gf_poly_div(struct bch_control *bch, struct gf_poly *a,
735 const struct gf_poly *b, struct gf_poly *q)
736{
737 if (a->deg >= b->deg) {
738 q->deg = a->deg-b->deg;
739
740 gf_poly_mod(bch, a, b, NULL);
741
742 memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int));
743 } else {
744 q->deg = 0;
745 q->c[0] = 0;
746 }
747}
748
749
750
751
752static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a,
753 struct gf_poly *b)
754{
755 struct gf_poly *tmp;
756
757 dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b));
758
759 if (a->deg < b->deg) {
760 tmp = b;
761 b = a;
762 a = tmp;
763 }
764
765 while (b->deg > 0) {
766 gf_poly_mod(bch, a, b, NULL);
767 tmp = b;
768 b = a;
769 a = tmp;
770 }
771
772 dbg("%s\n", gf_poly_str(a));
773
774 return a;
775}
776
777
778
779
780
781static void compute_trace_bk_mod(struct bch_control *bch, int k,
782 const struct gf_poly *f, struct gf_poly *z,
783 struct gf_poly *out)
784{
785 const int m = GF_M(bch);
786 int i, j;
787
788
789 z->deg = 1;
790 z->c[0] = 0;
791 z->c[1] = bch->a_pow_tab[k];
792
793 out->deg = 0;
794 memset(out, 0, GF_POLY_SZ(f->deg));
795
796
797 gf_poly_logrep(bch, f, bch->cache);
798
799 for (i = 0; i < m; i++) {
800
801 for (j = z->deg; j >= 0; j--) {
802 out->c[j] ^= z->c[j];
803 z->c[2*j] = gf_sqr(bch, z->c[j]);
804 z->c[2*j+1] = 0;
805 }
806 if (z->deg > out->deg)
807 out->deg = z->deg;
808
809 if (i < m-1) {
810 z->deg *= 2;
811
812 gf_poly_mod(bch, z, f, bch->cache);
813 }
814 }
815 while (!out->c[out->deg] && out->deg)
816 out->deg--;
817
818 dbg("Tr(a^%d.X) mod f = %s\n", k, gf_poly_str(out));
819}
820
821
822
823
824static void factor_polynomial(struct bch_control *bch, int k, struct gf_poly *f,
825 struct gf_poly **g, struct gf_poly **h)
826{
827 struct gf_poly *f2 = bch->poly_2t[0];
828 struct gf_poly *q = bch->poly_2t[1];
829 struct gf_poly *tk = bch->poly_2t[2];
830 struct gf_poly *z = bch->poly_2t[3];
831 struct gf_poly *gcd;
832
833 dbg("factoring %s...\n", gf_poly_str(f));
834
835 *g = f;
836 *h = NULL;
837
838
839 compute_trace_bk_mod(bch, k, f, z, tk);
840
841 if (tk->deg > 0) {
842
843 gf_poly_copy(f2, f);
844 gcd = gf_poly_gcd(bch, f2, tk);
845 if (gcd->deg < f->deg) {
846
847 gf_poly_div(bch, f, gcd, q);
848
849 *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly;
850 gf_poly_copy(*g, gcd);
851 gf_poly_copy(*h, q);
852 }
853 }
854}
855
856
857
858
859
860static int find_poly_roots(struct bch_control *bch, unsigned int k,
861 struct gf_poly *poly, unsigned int *roots)
862{
863 int cnt;
864 struct gf_poly *f1, *f2;
865
866 switch (poly->deg) {
867
868 case 1:
869 cnt = find_poly_deg1_roots(bch, poly, roots);
870 break;
871 case 2:
872 cnt = find_poly_deg2_roots(bch, poly, roots);
873 break;
874 case 3:
875 cnt = find_poly_deg3_roots(bch, poly, roots);
876 break;
877 case 4:
878 cnt = find_poly_deg4_roots(bch, poly, roots);
879 break;
880 default:
881
882 cnt = 0;
883 if (poly->deg && (k <= GF_M(bch))) {
884 factor_polynomial(bch, k, poly, &f1, &f2);
885 if (f1)
886 cnt += find_poly_roots(bch, k+1, f1, roots);
887 if (f2)
888 cnt += find_poly_roots(bch, k+1, f2, roots+cnt);
889 }
890 break;
891 }
892 return cnt;
893}
894
895#if defined(USE_CHIEN_SEARCH)
896
897
898
899
900static int chien_search(struct bch_control *bch, unsigned int len,
901 struct gf_poly *p, unsigned int *roots)
902{
903 int m;
904 unsigned int i, j, syn, syn0, count = 0;
905 const unsigned int k = 8*len+bch->ecc_bits;
906
907
908 gf_poly_logrep(bch, p, bch->cache);
909 bch->cache[p->deg] = 0;
910 syn0 = gf_div(bch, p->c[0], p->c[p->deg]);
911
912 for (i = GF_N(bch)-k+1; i <= GF_N(bch); i++) {
913
914 for (j = 1, syn = syn0; j <= p->deg; j++) {
915 m = bch->cache[j];
916 if (m >= 0)
917 syn ^= a_pow(bch, m+j*i);
918 }
919 if (syn == 0) {
920 roots[count++] = GF_N(bch)-i;
921 if (count == p->deg)
922 break;
923 }
924 }
925 return (count == p->deg) ? count : 0;
926}
927#define find_poly_roots(_p, _k, _elp, _loc) chien_search(_p, len, _elp, _loc)
928#endif
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972int decode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len,
973 const uint8_t *recv_ecc, const uint8_t *calc_ecc,
974 const unsigned int *syn, unsigned int *errloc)
975{
976 const unsigned int ecc_words = BCH_ECC_WORDS(bch);
977 unsigned int nbits;
978 int i, err, nroots;
979 uint32_t sum;
980
981
982 if (8*len > (bch->n-bch->ecc_bits))
983 return -EINVAL;
984
985
986 if (!syn) {
987 if (!calc_ecc) {
988
989 if (!data || !recv_ecc)
990 return -EINVAL;
991 encode_bch(bch, data, len, NULL);
992 } else {
993
994 load_ecc8(bch, bch->ecc_buf, calc_ecc);
995 }
996
997 if (recv_ecc) {
998 load_ecc8(bch, bch->ecc_buf2, recv_ecc);
999
1000 for (i = 0, sum = 0; i < (int)ecc_words; i++) {
1001 bch->ecc_buf[i] ^= bch->ecc_buf2[i];
1002 sum |= bch->ecc_buf[i];
1003 }
1004 if (!sum)
1005
1006 return 0;
1007 }
1008 compute_syndromes(bch, bch->ecc_buf, bch->syn);
1009 syn = bch->syn;
1010 }
1011
1012 err = compute_error_locator_polynomial(bch, syn);
1013 if (err > 0) {
1014 nroots = find_poly_roots(bch, 1, bch->elp, errloc);
1015 if (err != nroots)
1016 err = -1;
1017 }
1018 if (err > 0) {
1019
1020 nbits = (len*8)+bch->ecc_bits;
1021 for (i = 0; i < err; i++) {
1022 if (errloc[i] >= nbits) {
1023 err = -1;
1024 break;
1025 }
1026 errloc[i] = nbits-1-errloc[i];
1027 errloc[i] = (errloc[i] & ~7)|(7-(errloc[i] & 7));
1028 }
1029 }
1030 return (err >= 0) ? err : -EBADMSG;
1031}
1032
1033
1034
1035
1036static int build_gf_tables(struct bch_control *bch, unsigned int poly)
1037{
1038 unsigned int i, x = 1;
1039 const unsigned int k = 1 << deg(poly);
1040
1041
1042 if (k != (1u << GF_M(bch)))
1043 return -1;
1044
1045 for (i = 0; i < GF_N(bch); i++) {
1046 bch->a_pow_tab[i] = x;
1047 bch->a_log_tab[x] = i;
1048 if (i && (x == 1))
1049
1050 return -1;
1051 x <<= 1;
1052 if (x & k)
1053 x ^= poly;
1054 }
1055 bch->a_pow_tab[GF_N(bch)] = 1;
1056 bch->a_log_tab[0] = 0;
1057
1058 return 0;
1059}
1060
1061
1062
1063
1064static void build_mod8_tables(struct bch_control *bch, const uint32_t *g)
1065{
1066 int i, j, b, d;
1067 uint32_t data, hi, lo, *tab;
1068 const int l = BCH_ECC_WORDS(bch);
1069 const int plen = DIV_ROUND_UP(bch->ecc_bits+1, 32);
1070 const int ecclen = DIV_ROUND_UP(bch->ecc_bits, 32);
1071
1072 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab));
1073
1074 for (i = 0; i < 256; i++) {
1075
1076 for (b = 0; b < 4; b++) {
1077
1078 tab = bch->mod8_tab + (b*256+i)*l;
1079 data = i << (8*b);
1080 while (data) {
1081 d = deg(data);
1082
1083 data ^= g[0] >> (31-d);
1084 for (j = 0; j < ecclen; j++) {
1085 hi = (d < 31) ? g[j] << (d+1) : 0;
1086 lo = (j+1 < plen) ?
1087 g[j+1] >> (31-d) : 0;
1088 tab[j] ^= hi|lo;
1089 }
1090 }
1091 }
1092 }
1093}
1094
1095
1096
1097
1098static int build_deg2_base(struct bch_control *bch)
1099{
1100 const int m = GF_M(bch);
1101 int i, j, r;
1102 unsigned int sum, x, y, remaining, ak = 0, xi[m];
1103
1104
1105 for (i = 0; i < m; i++) {
1106 for (j = 0, sum = 0; j < m; j++)
1107 sum ^= a_pow(bch, i*(1 << j));
1108
1109 if (sum) {
1110 ak = bch->a_pow_tab[i];
1111 break;
1112 }
1113 }
1114
1115 remaining = m;
1116 memset(xi, 0, sizeof(xi));
1117
1118 for (x = 0; (x <= GF_N(bch)) && remaining; x++) {
1119 y = gf_sqr(bch, x)^x;
1120 for (i = 0; i < 2; i++) {
1121 r = a_log(bch, y);
1122 if (y && (r < m) && !xi[r]) {
1123 bch->xi_tab[r] = x;
1124 xi[r] = 1;
1125 remaining--;
1126 dbg("x%d = %x\n", r, x);
1127 break;
1128 }
1129 y ^= ak;
1130 }
1131 }
1132
1133 return remaining ? -1 : 0;
1134}
1135
1136static void *bch_alloc(size_t size, int *err)
1137{
1138 void *ptr;
1139
1140 ptr = kmalloc(size, GFP_KERNEL);
1141 if (ptr == NULL)
1142 *err = 1;
1143 return ptr;
1144}
1145
1146
1147
1148
1149static uint32_t *compute_generator_polynomial(struct bch_control *bch)
1150{
1151 const unsigned int m = GF_M(bch);
1152 const unsigned int t = GF_T(bch);
1153 int n, err = 0;
1154 unsigned int i, j, nbits, r, word, *roots;
1155 struct gf_poly *g;
1156 uint32_t *genpoly;
1157
1158 g = bch_alloc(GF_POLY_SZ(m*t), &err);
1159 roots = bch_alloc((bch->n+1)*sizeof(*roots), &err);
1160 genpoly = bch_alloc(DIV_ROUND_UP(m*t+1, 32)*sizeof(*genpoly), &err);
1161
1162 if (err) {
1163 kfree(genpoly);
1164 genpoly = NULL;
1165 goto finish;
1166 }
1167
1168
1169 memset(roots , 0, (bch->n+1)*sizeof(*roots));
1170 for (i = 0; i < t; i++) {
1171 for (j = 0, r = 2*i+1; j < m; j++) {
1172 roots[r] = 1;
1173 r = mod_s(bch, 2*r);
1174 }
1175 }
1176
1177 g->deg = 0;
1178 g->c[0] = 1;
1179 for (i = 0; i < GF_N(bch); i++) {
1180 if (roots[i]) {
1181
1182 r = bch->a_pow_tab[i];
1183 g->c[g->deg+1] = 1;
1184 for (j = g->deg; j > 0; j--)
1185 g->c[j] = gf_mul(bch, g->c[j], r)^g->c[j-1];
1186
1187 g->c[0] = gf_mul(bch, g->c[0], r);
1188 g->deg++;
1189 }
1190 }
1191
1192 n = g->deg+1;
1193 i = 0;
1194
1195 while (n > 0) {
1196 nbits = (n > 32) ? 32 : n;
1197 for (j = 0, word = 0; j < nbits; j++) {
1198 if (g->c[n-1-j])
1199 word |= 1u << (31-j);
1200 }
1201 genpoly[i++] = word;
1202 n -= nbits;
1203 }
1204 bch->ecc_bits = g->deg;
1205
1206finish:
1207 kfree(g);
1208 kfree(roots);
1209
1210 return genpoly;
1211}
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234struct bch_control *init_bch(int m, int t, unsigned int prim_poly)
1235{
1236 int err = 0;
1237 unsigned int i, words;
1238 uint32_t *genpoly;
1239 struct bch_control *bch = NULL;
1240
1241 const int min_m = 5;
1242 const int max_m = 15;
1243
1244
1245 static const unsigned int prim_poly_tab[] = {
1246 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b,
1247 0x402b, 0x8003,
1248 };
1249
1250#if defined(CONFIG_BCH_CONST_PARAMS)
1251 if ((m != (CONFIG_BCH_CONST_M)) || (t != (CONFIG_BCH_CONST_T))) {
1252 printk(KERN_ERR "bch encoder/decoder was configured to support "
1253 "parameters m=%d, t=%d only!\n",
1254 CONFIG_BCH_CONST_M, CONFIG_BCH_CONST_T);
1255 goto fail;
1256 }
1257#endif
1258 if ((m < min_m) || (m > max_m))
1259
1260
1261
1262
1263
1264 goto fail;
1265
1266
1267 if ((t < 1) || (m*t >= ((1 << m)-1)))
1268
1269 goto fail;
1270
1271
1272 if (prim_poly == 0)
1273 prim_poly = prim_poly_tab[m-min_m];
1274
1275 bch = kzalloc(sizeof(*bch), GFP_KERNEL);
1276 if (bch == NULL)
1277 goto fail;
1278
1279 bch->m = m;
1280 bch->t = t;
1281 bch->n = (1 << m)-1;
1282 words = DIV_ROUND_UP(m*t, 32);
1283 bch->ecc_bytes = DIV_ROUND_UP(m*t, 8);
1284 bch->a_pow_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_pow_tab), &err);
1285 bch->a_log_tab = bch_alloc((1+bch->n)*sizeof(*bch->a_log_tab), &err);
1286 bch->mod8_tab = bch_alloc(words*1024*sizeof(*bch->mod8_tab), &err);
1287 bch->ecc_buf = bch_alloc(words*sizeof(*bch->ecc_buf), &err);
1288 bch->ecc_buf2 = bch_alloc(words*sizeof(*bch->ecc_buf2), &err);
1289 bch->xi_tab = bch_alloc(m*sizeof(*bch->xi_tab), &err);
1290 bch->syn = bch_alloc(2*t*sizeof(*bch->syn), &err);
1291 bch->cache = bch_alloc(2*t*sizeof(*bch->cache), &err);
1292 bch->elp = bch_alloc((t+1)*sizeof(struct gf_poly_deg1), &err);
1293
1294 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1295 bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);
1296
1297 if (err)
1298 goto fail;
1299
1300 err = build_gf_tables(bch, prim_poly);
1301 if (err)
1302 goto fail;
1303
1304
1305 genpoly = compute_generator_polynomial(bch);
1306 if (genpoly == NULL)
1307 goto fail;
1308
1309 build_mod8_tables(bch, genpoly);
1310 kfree(genpoly);
1311
1312 err = build_deg2_base(bch);
1313 if (err)
1314 goto fail;
1315
1316 return bch;
1317
1318fail:
1319 free_bch(bch);
1320 return NULL;
1321}
1322
1323
1324
1325
1326
1327void free_bch(struct bch_control *bch)
1328{
1329 unsigned int i;
1330
1331 if (bch) {
1332 kfree(bch->a_pow_tab);
1333 kfree(bch->a_log_tab);
1334 kfree(bch->mod8_tab);
1335 kfree(bch->ecc_buf);
1336 kfree(bch->ecc_buf2);
1337 kfree(bch->xi_tab);
1338 kfree(bch->syn);
1339 kfree(bch->cache);
1340 kfree(bch->elp);
1341
1342 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++)
1343 kfree(bch->poly_2t[i]);
1344
1345 kfree(bch);
1346 }
1347}
1348