5  * under the terms of the GNU General Public License version 2 as published by
39  * better (up to 2x) encoding performance. Using this option makes sense when
51  * c. Error locator root finding (by far the most expensive step)
53  * In this implementation, step c is not performed using the usual Chien search.
57  * solving techniques [2] are used. The resulting algorithm, called BTZ, yields
62  * of characteristic 2, in: Western European Workshop on Research in Cryptology
64  * [2] [Zin96] V.A. Zinoviev. On the solution of equations of degree 10 over
65  * finite fields GF(2^q). In Rapport de recherche INRIA no 2829, 1996.
88 #define BCH_MAX_M              15 /* 2KB */
102  * represent a polynomial over GF(2^m)
106 	unsigned int c[];   /* polynomial terms */  member
115 	unsigned int   c[2];  member
161 			((u32)swap_bits(bch, src[2]) << 8) |  in load_ecc8()
167 		((u32)swap_bits(bch, pad[2]) << 8) |  in load_ecc8()
188 	pad[2] = swap_bits(bch, src[nwords] >> 8);  in store_ecc8()
300  * shorter and faster modulo function, only works when v < 2N.
321 	x ^= x >> 2;  in parity()
337 	return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0;  in gf_sqr()
368  * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t
384 	memset(syn, 0, 2*t*sizeof(*syn));  in compute_syndromes()
386 	/* compute v(a^j) for j=1 .. 2t-1 */  in compute_syndromes()
392 			for (j = 0; j < 2*t; j += 2)  in compute_syndromes()
399 	/* v(a^(2j)) = v(a^j)^2 */  in compute_syndromes()
401 		syn[2*j+1] = gf_sqr(bch, syn[j]);  in compute_syndromes()
420 	memset(pelp, 0, GF_POLY_SZ(2*t));  in compute_error_locator_polynomial()
421 	memset(elp, 0, GF_POLY_SZ(2*t));  in compute_error_locator_polynomial()
424 	pelp->c[0] = 1;  in compute_error_locator_polynomial()
426 	elp->c[0] = 1;  in compute_error_locator_polynomial()
431 			k = 2*i-pp;  in compute_error_locator_polynomial()
433 			/* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */  in compute_error_locator_polynomial()
436 				if (pelp->c[j]) {  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()
441 			/* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */  in compute_error_locator_polynomial()
447 				pp = 2*i;  in compute_error_locator_polynomial()
450 		/* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */  in compute_error_locator_polynomial()
452 			d = syn[2*i+2];  in compute_error_locator_polynomial()
454 				d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]);  in compute_error_locator_polynomial()
462  * solve a m x m linear system in GF(2) with an expected number of solutions,
470 	int rem, c, r, p, k, param[BCH_MAX_M];  in solve_linear_system()  local
476 	for (c = 0; c < m; c++) {  in solve_linear_system()
478 		p = c-k;  in solve_linear_system()
497 			param[k++] = c;  in solve_linear_system()
520 		for (c = 0; c < k; c++)  in solve_linear_system()
521 			rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1);  in solve_linear_system()
536  * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m).
539 			      unsigned int b, unsigned int c,  in find_affine4_roots()  argument
548 	rows[0] = c;  in find_affine4_roots()
550 	/* build linear system to solve X^4+aX^2+bX+c = 0 */  in find_affine4_roots()
556 		k += 2;  in find_affine4_roots()
573  * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r))
580 	if (poly->c[0])  in find_poly_deg1_roots()
581 		/* poly[X] = bX+c with c!=0, root=c/b */  in find_poly_deg1_roots()
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()
588  * compute roots of a degree 2 polynomial over GF(2^m)
596 	if (poly->c[0] && poly->c[1]) {  in find_poly_deg2_roots()
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()
602 		/* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */  in find_poly_deg2_roots()
603 		u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1));  in find_poly_deg2_roots()
606 		 * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) =  in find_poly_deg2_roots()
620 			roots[n++] = modulo(bch, 2*GF_N(bch)-l1-  in find_poly_deg2_roots()
622 			roots[n++] = modulo(bch, 2*GF_N(bch)-l1-  in find_poly_deg2_roots()
630  * compute roots of a degree 3 polynomial over GF(2^m)
636 	unsigned int a, b, c, a2, b2, c2, e3, tmp[4];  in find_poly_deg3_roots()  local
638 	if (poly->c[0]) {  in find_poly_deg3_roots()
639 		/* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */  in find_poly_deg3_roots()
640 		e3 = poly->c[3];  in find_poly_deg3_roots()
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()
645 		/* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */  in find_poly_deg3_roots()
646 		c = gf_mul(bch, a2, c2);           /* c = a2c2      */  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()
663  * compute roots of a degree 4 polynomial over GF(2^m)
669 	unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4;  in find_poly_deg4_roots()  local
671 	if (poly->c[0] == 0)  in find_poly_deg4_roots()
674 	/* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */  in find_poly_deg4_roots()
675 	e4 = poly->c[4];  in find_poly_deg4_roots()
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()
683 		/* first, eliminate cX by using z=X+e with ae^2+c=0 */  in find_poly_deg4_roots()
684 		if (c) {  in find_poly_deg4_roots()
685 			/* compute e such that e^2 = c/a */  in find_poly_deg4_roots()
686 			f = gf_div(bch, c, a);  in find_poly_deg4_roots()
689 			e = a_pow(bch, l/2);  in find_poly_deg4_roots()
692 			 * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d  in find_poly_deg4_roots()
693 			 * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d  in find_poly_deg4_roots()
694 			 * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d  in find_poly_deg4_roots()
695 			 * z^4 + az^3 +     b'z^2 + d'  in find_poly_deg4_roots()
697 			d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d;  in find_poly_deg4_roots()
700 		/* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */  in find_poly_deg4_roots()
711 		b2 = c;  in find_poly_deg4_roots()
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()
740  * compute polynomial Euclidean division remainder in GF(2^m)[X]
746 	unsigned int i, j, *c = a->c;  in gf_poly_mod()  local
759 		if (c[j]) {  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()
771 	while (!c[a->deg] && a->deg)  in gf_poly_mod()
776  * compute polynomial Euclidean division quotient in GF(2^m)[X]
786 		memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int));  in gf_poly_div()
789 		q->c[0] = 0;  in gf_poly_div()
794  * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X]
825 	/* z contains z^2j mod f */  in compute_trace_bk_mod()
827 	z->c[0] = 0;  in compute_trace_bk_mod()
828 	z->c[1] = bch->a_pow_tab[k];  in compute_trace_bk_mod()
837 		/* add a^(k*2^i)(z^(2^i) mod f) and compute (z^(2^i) mod f)^2 */  in compute_trace_bk_mod()
839 			out->c[j] ^= z->c[j];  in compute_trace_bk_mod()
840 			z->c[2*j] = gf_sqr(bch, z->c[j]);  in compute_trace_bk_mod()
841 			z->c[2*j+1] = 0;  in compute_trace_bk_mod()
847 			z->deg *= 2;  in compute_trace_bk_mod()
848 			/* z^(2(i+1)) mod f = (z^(2^i) mod f)^2 mod f */  in compute_trace_bk_mod()
852 	while (!out->c[out->deg] && out->deg)  in compute_trace_bk_mod()
866 	struct gf_poly *tk = bch->poly_2t[2];  in factor_polynomial()
908 	case 2:  in find_poly_roots()
947 	syn0 = gf_div(bch, p->c[0], p->c[p->deg]);  in chien_search()
1089 			/* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */  in build_gf_tables()
1136  * build a base for factoring degree 2 polynomials
1154 	/* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */  in build_deg2_base()
1160 		for (i = 0; i < 2; i++) {  in build_deg2_base()
1211 		for (j = 0, r = 2*i+1; j < m; j++) {  in compute_generator_polynomial()
1213 			r = mod_s(bch, 2*r);  in compute_generator_polynomial()
1218 	g->c[0] = 1;  in compute_generator_polynomial()
1223 			g->c[g->deg+1] = 1;  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()
1238 			if (g->c[n-1-j])  in compute_generator_polynomial()
1319 	/* select a primitive polynomial for generating GF(2^m) */  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()
1344 		bch->poly_2t[i] = bch_alloc(GF_POLY_SZ(2*t), &err);  in bch_init()