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