Lines Matching +full:0 +full:deg
79 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
99 #define dbg(_fmt, args...) do {} while (0)
106 unsigned int deg; /* polynomial degree */ member
107 unsigned int c[0]; /* polynomial terms */
126 return 0; in fls()
127 if (!(x & 0xffff0000u)) { in fls()
131 if (!(x & 0xff000000u)) { in fls()
135 if (!(x & 0xf0000000u)) { in fls()
139 if (!(x & 0xc0000000u)) { in fls()
143 if (!(x & 0x80000000u)) { in fls()
164 p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); in encode_bch_unaligned()
166 for (i = 0; i < l; i++) in encode_bch_unaligned()
179 uint8_t pad[4] = {0, 0, 0, 0}; in load_ecc8()
182 for (i = 0; i < nwords; i++, src += 4) in load_ecc8()
183 dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; in load_ecc8()
186 dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; in load_ecc8()
198 for (i = 0; i < nwords; i++) { in store_ecc8()
200 *dst++ = (src[i] >> 16) & 0xff; in store_ecc8()
201 *dst++ = (src[i] >> 8) & 0xff; in store_ecc8()
202 *dst++ = (src[i] >> 0) & 0xff; in store_ecc8()
204 pad[0] = (src[nwords] >> 24); in store_ecc8()
205 pad[1] = (src[nwords] >> 16) & 0xff; in store_ecc8()
206 pad[2] = (src[nwords] >> 8) & 0xff; in store_ecc8()
207 pad[3] = (src[nwords] >> 0) & 0xff; in store_ecc8()
220 * @ecc_bytes of @bch, and should be initialized to 0 before the first call.
242 memset(bch->ecc_buf, 0, sizeof(r)); in encode_bch()
264 * 31 ...24 23 ...16 15 ... 8 7 ... 0 in encode_bch()
274 w = r[0]^cpu_to_be32(*pdata++); in encode_bch()
275 p0 = tab0 + (l+1)*((w >> 0) & 0xff); in encode_bch()
276 p1 = tab1 + (l+1)*((w >> 8) & 0xff); in encode_bch()
277 p2 = tab2 + (l+1)*((w >> 16) & 0xff); in encode_bch()
278 p3 = tab3 + (l+1)*((w >> 24) & 0xff); in encode_bch()
280 for (i = 0; i < l; i++) in encode_bch()
315 static inline int deg(unsigned int poly) in deg() function
329 x = (x & 0x11111111U) * 0x11111111U; in parity()
339 bch->a_log_tab[b])] : 0; in gf_mul()
344 return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; in gf_sqr()
351 GF_N(bch)-bch->a_log_tab[b])] : 0; in gf_div()
391 memset(syn, 0, 2*t*sizeof(*syn)); in compute_syndromes()
398 i = deg(poly); in compute_syndromes()
399 for (j = 0; j < 2*t; j += 2) in compute_syndromes()
404 } while (s > 0); in compute_syndromes()
407 for (j = 0; j < t; j++) in compute_syndromes()
413 memcpy(dst, src, GF_POLY_SZ(src->deg)); in gf_poly_copy()
421 unsigned int i, j, tmp, l, pd = 1, d = syn[0]; in compute_error_locator_polynomial()
423 struct gf_poly *pelp = bch->poly_2t[0]; in compute_error_locator_polynomial()
427 memset(pelp, 0, GF_POLY_SZ(2*t)); in compute_error_locator_polynomial()
428 memset(elp, 0, GF_POLY_SZ(2*t)); in compute_error_locator_polynomial()
430 pelp->deg = 0; in compute_error_locator_polynomial()
431 pelp->c[0] = 1; in compute_error_locator_polynomial()
432 elp->deg = 0; in compute_error_locator_polynomial()
433 elp->c[0] = 1; in compute_error_locator_polynomial()
436 for (i = 0; (i < t) && (elp->deg <= t); i++) { in compute_error_locator_polynomial()
442 for (j = 0; j <= pelp->deg; j++) { in compute_error_locator_polynomial()
449 tmp = pelp->deg+k; in compute_error_locator_polynomial()
450 if (tmp > elp->deg) { in compute_error_locator_polynomial()
451 elp->deg = tmp; in compute_error_locator_polynomial()
460 for (j = 1; j <= elp->deg; j++) in compute_error_locator_polynomial()
465 return (elp->deg > t) ? -1 : (int)elp->deg; in compute_error_locator_polynomial()
479 k = 0; in solve_linear_system()
483 for (c = 0; c < m; c++) { in solve_linear_system()
484 rem = 0; in solve_linear_system()
512 if (k > 0) { in solve_linear_system()
514 for (r = m-1; r >= 0; r--) { in solve_linear_system()
517 return 0; in solve_linear_system()
526 return 0; in solve_linear_system()
528 for (p = 0; p < nsol; p++) { in solve_linear_system()
530 for (c = 0; c < k; c++) in solve_linear_system()
534 tmp = 0; in solve_linear_system()
535 for (r = m-1; r >= 0; r--) { in solve_linear_system()
554 unsigned int mask = 0xff, t, rows[16] = {0,}; in find_affine4_roots()
558 rows[0] = c; in find_affine4_roots()
560 /* buid linear system to solve X^4+aX^2+bX+c = 0 */ in find_affine4_roots()
561 for (i = 0; i < m; i++) { in find_affine4_roots()
563 (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ in find_affine4_roots()
564 (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); in find_affine4_roots()
572 for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { in find_affine4_roots()
573 for (k = 0; k < 16; k = (k+j+1) & ~j) { in find_affine4_roots()
588 int n = 0; in find_poly_deg1_roots()
590 if (poly->c[0]) in find_poly_deg1_roots()
591 /* poly[X] = bX+c with c!=0, root=c/b */ in find_poly_deg1_roots()
592 roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ in find_poly_deg1_roots()
603 int n = 0, i, l0, l1, l2; in find_poly_deg2_roots()
606 if (poly->c[0] && poly->c[1]) { in find_poly_deg2_roots()
608 l0 = bch->a_log_tab[poly->c[0]]; in find_poly_deg2_roots()
615 * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): in find_poly_deg2_roots()
618 * i.e. r and r+1 are roots iff Tr(u)=0 in find_poly_deg2_roots()
620 r = 0; in find_poly_deg2_roots()
623 i = deg(v); in find_poly_deg2_roots()
645 int i, n = 0; in find_poly_deg3_roots()
648 if (poly->c[0]) { in find_poly_deg3_roots()
651 c2 = gf_div(bch, poly->c[0], e3); in find_poly_deg3_roots()
663 for (i = 0; i < 4; i++) { in find_poly_deg3_roots()
678 int i, l, n = 0; in find_poly_deg4_roots()
679 unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; in find_poly_deg4_roots()
681 if (poly->c[0] == 0) in find_poly_deg4_roots()
682 return 0; in find_poly_deg4_roots()
686 d = gf_div(bch, poly->c[0], e4); in find_poly_deg4_roots()
693 /* first, eliminate cX by using z=X+e with ae^2+c=0 */ in find_poly_deg4_roots()
698 l += (l & 1) ? GF_N(bch) : 0; in find_poly_deg4_roots()
711 if (d == 0) in find_poly_deg4_roots()
713 return 0; in find_poly_deg4_roots()
726 for (i = 0; i < 4; i++) { in find_poly_deg4_roots()
742 int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); in gf_poly_logrep()
744 /* represent 0 values with -1; warning, rep[d] is not set to 1 */ in gf_poly_logrep()
745 for (i = 0; i < d; i++) in gf_poly_logrep()
757 const unsigned int d = b->deg; in gf_poly_mod()
759 if (a->deg < d) in gf_poly_mod()
768 for (j = a->deg; j >= d; j--) { in gf_poly_mod()
772 for (i = 0; i < d; i++, p++) { in gf_poly_mod()
774 if (m >= 0) in gf_poly_mod()
780 a->deg = d-1; in gf_poly_mod()
781 while (!c[a->deg] && a->deg) in gf_poly_mod()
782 a->deg--; in gf_poly_mod()
791 if (a->deg >= b->deg) { in gf_poly_div()
792 q->deg = a->deg-b->deg; in gf_poly_div()
796 memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); in gf_poly_div()
798 q->deg = 0; in gf_poly_div()
799 q->c[0] = 0; in gf_poly_div()
813 if (a->deg < b->deg) { in gf_poly_gcd()
819 while (b->deg > 0) { in gf_poly_gcd()
843 z->deg = 1; in compute_trace_bk_mod()
844 z->c[0] = 0; in compute_trace_bk_mod()
847 out->deg = 0; in compute_trace_bk_mod()
848 memset(out, 0, GF_POLY_SZ(f->deg)); in compute_trace_bk_mod()
853 for (i = 0; i < m; i++) { in compute_trace_bk_mod()
855 for (j = z->deg; j >= 0; j--) { in compute_trace_bk_mod()
858 z->c[2*j+1] = 0; in compute_trace_bk_mod()
860 if (z->deg > out->deg) in compute_trace_bk_mod()
861 out->deg = z->deg; in compute_trace_bk_mod()
864 z->deg *= 2; in compute_trace_bk_mod()
869 while (!out->c[out->deg] && out->deg) in compute_trace_bk_mod()
870 out->deg--; in compute_trace_bk_mod()
881 struct gf_poly *f2 = bch->poly_2t[0]; in factor_polynomial()
895 if (tk->deg > 0) { in factor_polynomial()
899 if (gcd->deg < f->deg) { in factor_polynomial()
903 *h = &((struct gf_poly_deg1 *)f)[gcd->deg].poly; in factor_polynomial()
920 switch (poly->deg) { in find_poly_roots()
936 cnt = 0; in find_poly_roots()
937 if (poly->deg && (k <= GF_M(bch))) { in find_poly_roots()
958 unsigned int i, j, syn, syn0, count = 0; in chien_search()
963 bch->cache[p->deg] = 0; in chien_search()
964 syn0 = gf_div(bch, p->c[0], p->c[p->deg]); in chien_search()
968 for (j = 1, syn = syn0; j <= p->deg; j++) { in chien_search()
970 if (m >= 0) in chien_search()
973 if (syn == 0) { in chien_search()
975 if (count == p->deg) in chien_search()
979 return (count == p->deg) ? count : 0; in chien_search()
1054 for (i = 0, sum = 0; i < (int)ecc_words; i++) { in decode_bch()
1060 return 0; in decode_bch()
1067 if (err > 0) { in decode_bch()
1072 if (err > 0) { in decode_bch()
1075 for (i = 0; i < err; i++) { in decode_bch()
1084 return (err >= 0) ? err : -EBADMSG; in decode_bch()
1093 const unsigned int k = 1 << deg(poly); in build_gf_tables()
1099 for (i = 0; i < GF_N(bch); i++) { in build_gf_tables()
1103 /* polynomial is not primitive (a^i=1 with 0<i<2^m-1) */ in build_gf_tables()
1110 bch->a_log_tab[0] = 0; in build_gf_tables()
1112 return 0; in build_gf_tables()
1126 memset(bch->mod8_tab, 0, 4*256*l*sizeof(*bch->mod8_tab)); in build_mod8_tables()
1128 for (i = 0; i < 256; i++) { in build_mod8_tables()
1130 for (b = 0; b < 4; b++) { in build_mod8_tables()
1131 /* we want to compute (p(X).X^(8*b+deg(g))) mod g(X) */ in build_mod8_tables()
1135 d = deg(data); in build_mod8_tables()
1136 /* subtract X^d.g(X) from p(X).X^(8*b+deg(g)) */ in build_mod8_tables()
1137 data ^= g[0] >> (31-d); in build_mod8_tables()
1138 for (j = 0; j < ecclen; j++) { in build_mod8_tables()
1139 hi = (d < 31) ? g[j] << (d+1) : 0; in build_mod8_tables()
1141 g[j+1] >> (31-d) : 0; in build_mod8_tables()
1156 unsigned int sum, x, y, remaining, ak = 0, xi[m]; in build_deg2_base()
1158 /* find k s.t. Tr(a^k) = 1 and 0 <= k < m */ in build_deg2_base()
1159 for (i = 0; i < m; i++) { in build_deg2_base()
1160 for (j = 0, sum = 0; j < m; j++) in build_deg2_base()
1168 /* find xi, i=0..m-1 such that xi^2+xi = a^i+Tr(a^i).a^k */ in build_deg2_base()
1170 memset(xi, 0, sizeof(xi)); in build_deg2_base()
1172 for (x = 0; (x <= GF_N(bch)) && remaining; x++) { in build_deg2_base()
1174 for (i = 0; i < 2; i++) { in build_deg2_base()
1187 return remaining ? -1 : 0; in build_deg2_base()
1207 int n, err = 0; in compute_generator_polynomial()
1223 memset(roots , 0, (bch->n+1)*sizeof(*roots)); in compute_generator_polynomial()
1224 for (i = 0; i < t; i++) { in compute_generator_polynomial()
1225 for (j = 0, r = 2*i+1; j < m; j++) { in compute_generator_polynomial()
1231 g->deg = 0; in compute_generator_polynomial()
1232 g->c[0] = 1; in compute_generator_polynomial()
1233 for (i = 0; i < GF_N(bch); i++) { in compute_generator_polynomial()
1237 g->c[g->deg+1] = 1; in compute_generator_polynomial()
1238 for (j = g->deg; j > 0; j--) in compute_generator_polynomial()
1241 g->c[0] = gf_mul(bch, g->c[0], r); in compute_generator_polynomial()
1242 g->deg++; in compute_generator_polynomial()
1246 n = g->deg+1; in compute_generator_polynomial()
1247 i = 0; in compute_generator_polynomial()
1249 while (n > 0) { in compute_generator_polynomial()
1251 for (j = 0, word = 0; j < nbits; j++) { in compute_generator_polynomial()
1258 bch->ecc_bits = g->deg; in compute_generator_polynomial()
1271 * @prim_poly: user-provided primitive polynomial (or 0 to use default)
1290 int err = 0; in init_bch()
1300 0x25, 0x43, 0x83, 0x11d, 0x211, 0x409, 0x805, 0x1053, 0x201b, in init_bch()
1301 0x402b, 0x8003, in init_bch()
1326 if (prim_poly == 0) in init_bch()
1348 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) in init_bch()
1396 for (i = 0; i < ARRAY_SIZE(bch->poly_2t); i++) in free_bch()