aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Rientjes <rientjes@google.com>2007-05-11 01:51:05 -0400
committerRalf Baechle <ralf@linux-mips.org>2007-05-11 09:28:33 -0400
commite8b6d40a007774bde5110c110290f8090c7e48ad (patch)
tree633130b62ce77771d91368dd0022c71186de6806
parentf6d376aac33ccdce95b42fdcc916d4ee98c05623 (diff)
[MIPS] tlbex: use __maybe_unused
Replace function instances of __attribute__((unused)) with __maybe_unused. Acked-by: Ralf Baechle <ralf@linux-mips.org> Signed-off-by: David Rientjes <rientjes@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Ralf Baechle <ralf@linux-mips.org>
Diffstat
-rw-r--r--arch/mips/mm/tlbex.c36
1 files changed, 18 insertions, 18 deletions
diff --git a/arch/mips/mm/tlbex.c b/arch/mips/mm/tlbex.c
index 492c518e7ba5..e7149290d1cb 100644
--- a/arch/mips/mm/tlbex.c
+++ b/arch/mips/mm/tlbex.c
@@ -35,24 +35,24 @@
35#include <asm/smp.h> 35#include <asm/smp.h>
36#include <asm/war.h> 36#include <asm/war.h>
37 37
38static __init int __attribute__((unused)) r45k_bvahwbug(void) 38static __init int __maybe_unused r45k_bvahwbug(void)
39{ 39{
40 /* XXX: We should probe for the presence of this bug, but we don't. */ 40 /* XXX: We should probe for the presence of this bug, but we don't. */
41 return 0; 41 return 0;
42} 42}
43 43
44static __init int __attribute__((unused)) r4k_250MHZhwbug(void) 44static __init int __maybe_unused r4k_250MHZhwbug(void)
45{ 45{
46 /* XXX: We should probe for the presence of this bug, but we don't. */ 46 /* XXX: We should probe for the presence of this bug, but we don't. */
47 return 0; 47 return 0;
48} 48}
49 49
50static __init int __attribute__((unused)) bcm1250_m3_war(void) 50static __init int __maybe_unused bcm1250_m3_war(void)
51{ 51{
52 return BCM1250_M3_WAR; 52 return BCM1250_M3_WAR;
53} 53}
54 54
55static __init int __attribute__((unused)) r10000_llsc_war(void) 55static __init int __maybe_unused r10000_llsc_war(void)
56{ 56{
57 return R10000_LLSC_WAR; 57 return R10000_LLSC_WAR;
58} 58}
@@ -511,18 +511,18 @@ L_LA(_r3000_write_probe_fail)
511#define i_ehb(buf) i_sll(buf, 0, 0, 3) 511#define i_ehb(buf) i_sll(buf, 0, 0, 3)
512 512
513#ifdef CONFIG_64BIT 513#ifdef CONFIG_64BIT
514static __init int __attribute__((unused)) in_compat_space_p(long addr) 514static __init int __maybe_unused in_compat_space_p(long addr)
515{ 515{
516 /* Is this address in 32bit compat space? */ 516 /* Is this address in 32bit compat space? */
517 return (((addr) & 0xffffffff00000000L) == 0xffffffff00000000L); 517 return (((addr) & 0xffffffff00000000L) == 0xffffffff00000000L);
518} 518}
519 519
520static __init int __attribute__((unused)) rel_highest(long val) 520static __init int __maybe_unused rel_highest(long val)
521{ 521{
522 return ((((val + 0x800080008000L) >> 48) & 0xffff) ^ 0x8000) - 0x8000; 522 return ((((val + 0x800080008000L) >> 48) & 0xffff) ^ 0x8000) - 0x8000;
523} 523}
524 524
525static __init int __attribute__((unused)) rel_higher(long val) 525static __init int __maybe_unused rel_higher(long val)
526{ 526{
527 return ((((val + 0x80008000L) >> 32) & 0xffff) ^ 0x8000) - 0x8000; 527 return ((((val + 0x80008000L) >> 32) & 0xffff) ^ 0x8000) - 0x8000;
528} 528}
@@ -556,8 +556,8 @@ static __init void i_LA_mostly(u32 **buf, unsigned int rs, long addr)
556 i_lui(buf, rs, rel_hi(addr)); 556 i_lui(buf, rs, rel_hi(addr));
557} 557}
558 558
559static __init void __attribute__((unused)) i_LA(u32 **buf, unsigned int rs, 559static __init void __maybe_unused i_LA(u32 **buf, unsigned int rs,
560 long addr) 560 long addr)
561{ 561{
562 i_LA_mostly(buf, rs, addr); 562 i_LA_mostly(buf, rs, addr);
563 if (rel_lo(addr)) 563 if (rel_lo(addr))
@@ -636,8 +636,8 @@ static __init void copy_handler(struct reloc *rel, struct label *lab,
636 move_labels(lab, first, end, off); 636 move_labels(lab, first, end, off);
637} 637}
638 638
639static __init int __attribute__((unused)) insn_has_bdelay(struct reloc *rel, 639static __init int __maybe_unused insn_has_bdelay(struct reloc *rel,
640 u32 *addr) 640 u32 *addr)
641{ 641{
642 for (; rel->lab != label_invalid; rel++) { 642 for (; rel->lab != label_invalid; rel++) {
643 if (rel->addr == addr 643 if (rel->addr == addr
@@ -650,15 +650,15 @@ static __init int __attribute__((unused)) insn_has_bdelay(struct reloc *rel,
650} 650}
651 651
652/* convenience functions for labeled branches */ 652/* convenience functions for labeled branches */
653static void __init __attribute__((unused)) 653static void __init __maybe_unused
654 il_bltz(u32 **p, struct reloc **r, unsigned int reg, enum label_id l) 654 il_bltz(u32 **p, struct reloc **r, unsigned int reg, enum label_id l)
655{ 655{
656 r_mips_pc16(r, *p, l); 656 r_mips_pc16(r, *p, l);
657 i_bltz(p, reg, 0); 657 i_bltz(p, reg, 0);
658} 658}
659 659
660static void __init __attribute__((unused)) il_b(u32 **p, struct reloc **r, 660static void __init __maybe_unused il_b(u32 **p, struct reloc **r,
661 enum label_id l) 661 enum label_id l)
662{ 662{
663 r_mips_pc16(r, *p, l); 663 r_mips_pc16(r, *p, l);
664 i_b(p, 0); 664 i_b(p, 0);
@@ -671,7 +671,7 @@ static void __init il_beqz(u32 **p, struct reloc **r, unsigned int reg,
671 i_beqz(p, reg, 0); 671 i_beqz(p, reg, 0);
672} 672}
673 673
674static void __init __attribute__((unused)) 674static void __init __maybe_unused
675il_beqzl(u32 **p, struct reloc **r, unsigned int reg, enum label_id l) 675il_beqzl(u32 **p, struct reloc **r, unsigned int reg, enum label_id l)
676{ 676{
677 r_mips_pc16(r, *p, l); 677 r_mips_pc16(r, *p, l);
@@ -692,7 +692,7 @@ static void __init il_bgezl(u32 **p, struct reloc **r, unsigned int reg,
692 i_bgezl(p, reg, 0); 692 i_bgezl(p, reg, 0);
693} 693}
694 694
695static void __init __attribute__((unused)) 695static void __init __maybe_unused
696il_bgez(u32 **p, struct reloc **r, unsigned int reg, enum label_id l) 696il_bgez(u32 **p, struct reloc **r, unsigned int reg, enum label_id l)
697{ 697{
698 r_mips_pc16(r, *p, l); 698 r_mips_pc16(r, *p, l);
@@ -810,7 +810,7 @@ static __initdata u32 final_handler[64];
810 * 810 *
811 * As if we MIPS hackers wouldn't know how to nop pipelines happy ... 811 * As if we MIPS hackers wouldn't know how to nop pipelines happy ...
812 */ 812 */
813static __init void __attribute__((unused)) build_tlb_probe_entry(u32 **p) 813static __init void __maybe_unused build_tlb_probe_entry(u32 **p)
814{ 814{
815 switch (current_cpu_data.cputype) { 815 switch (current_cpu_data.cputype) {
816 /* Found by experiment: R4600 v2.0 needs this, too. */ 816 /* Found by experiment: R4600 v2.0 needs this, too. */
@@ -1098,7 +1098,7 @@ build_get_pgd_vmalloc64(u32 **p, struct label **l, struct reloc **r,
1098 * TMP and PTR are scratch. 1098 * TMP and PTR are scratch.
1099 * TMP will be clobbered, PTR will hold the pgd entry. 1099 * TMP will be clobbered, PTR will hold the pgd entry.
1100 */ 1100 */
1101static __init void __attribute__((unused)) 1101static __init void __maybe_unused
1102build_get_pgde32(u32 **p, unsigned int tmp, unsigned int ptr) 1102build_get_pgde32(u32 **p, unsigned int tmp, unsigned int ptr)
1103{ 1103{
1104 long pgdc = (long)pgd_current; 1104 long pgdc = (long)pgd_current;
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-09 16:31:00 -0400
(CONFIG_BCH_CONST_M) #define GF_T(_p) (CONFIG_BCH_CONST_T) #define GF_N(_p) ((1 << (CONFIG_BCH_CONST_M))-1) #else #define GF_M(_p) ((_p)->m) #define GF_T(_p) ((_p)->t) #define GF_N(_p) ((_p)->n) #endif #define BCH_ECC_WORDS(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 32) #define BCH_ECC_BYTES(_p) DIV_ROUND_UP(GF_M(_p)*GF_T(_p), 8) #ifndef dbg #define dbg(_fmt, args...) do {} while (0) #endif /* * represent a polynomial over GF(2^m) */ struct gf_poly { unsigned int deg; /* polynomial degree */ unsigned int c[0]; /* polynomial terms */ }; /* given its degree, compute a polynomial size in bytes */ #define GF_POLY_SZ(_d) (sizeof(struct gf_poly)+((_d)+1)*sizeof(unsigned int)) /* polynomial of degree 1 */ struct gf_poly_deg1 { struct gf_poly poly; unsigned int c[2]; }; /* * same as encode_bch(), but process input data one byte at a time */ static void encode_bch_unaligned(struct bch_control *bch, const unsigned char *data, unsigned int len, uint32_t *ecc) { int i; const uint32_t *p; const int l = BCH_ECC_WORDS(bch)-1; while (len--) { p = bch->mod8_tab + (l+1)*(((ecc[0] >> 24)^(*data++)) & 0xff); for (i = 0; i < l; i++) ecc[i] = ((ecc[i] << 8)|(ecc[i+1] >> 24))^(*p++); ecc[l] = (ecc[l] << 8)^(*p); } } /* * convert ecc bytes to aligned, zero-padded 32-bit ecc words */ static void load_ecc8(struct bch_control *bch, uint32_t *dst, const uint8_t *src) { uint8_t pad[4] = {0, 0, 0, 0}; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++, src += 4) dst[i] = (src[0] << 24)|(src[1] << 16)|(src[2] << 8)|src[3]; memcpy(pad, src, BCH_ECC_BYTES(bch)-4*nwords); dst[nwords] = (pad[0] << 24)|(pad[1] << 16)|(pad[2] << 8)|pad[3]; } /* * convert 32-bit ecc words to ecc bytes */ static void store_ecc8(struct bch_control *bch, uint8_t *dst, const uint32_t *src) { uint8_t pad[4]; unsigned int i, nwords = BCH_ECC_WORDS(bch)-1; for (i = 0; i < nwords; i++) { *dst++ = (src[i] >> 24); *dst++ = (src[i] >> 16) & 0xff; *dst++ = (src[i] >> 8) & 0xff; *dst++ = (src[i] >> 0) & 0xff; } pad[0] = (src[nwords] >> 24); pad[1] = (src[nwords] >> 16) & 0xff; pad[2] = (src[nwords] >> 8) & 0xff; pad[3] = (src[nwords] >> 0) & 0xff; memcpy(dst, pad, BCH_ECC_BYTES(bch)-4*nwords); } /** * encode_bch - calculate BCH ecc parity of data * @bch: BCH control structure * @data: data to encode * @len: data length in bytes * @ecc: ecc parity data, must be initialized by caller * * The @ecc parity array is used both as input and output parameter, in order to * allow incremental computations. It should be of the size indicated by member * @ecc_bytes of @bch, and should be initialized to 0 before the first call. * * The exact number of computed ecc parity bits is given by member @ecc_bits of * @bch; it may be less than m*t for large values of t. */ void encode_bch(struct bch_control *bch, const uint8_t *data, unsigned int len, uint8_t *ecc) { const unsigned int l = BCH_ECC_WORDS(bch)-1; unsigned int i, mlen; unsigned long m; uint32_t w, r[l+1]; const uint32_t * const tab0 = bch->mod8_tab; const uint32_t * const tab1 = tab0 + 256*(l+1); const uint32_t * const tab2 = tab1 + 256*(l+1); const uint32_t * const tab3 = tab2 + 256*(l+1); const uint32_t *pdata, *p0, *p1, *p2, *p3; if (ecc) { /* load ecc parity bytes into internal 32-bit buffer */ load_ecc8(bch, bch->ecc_buf, ecc); } else { memset(bch->ecc_buf, 0, sizeof(r)); } /* process first unaligned data bytes */ m = ((unsigned long)data) & 3; if (m) { mlen = (len < (4-m)) ? len : 4-m; encode_bch_unaligned(bch, data, mlen, bch->ecc_buf); data += mlen; len -= mlen; } /* process 32-bit aligned data words */ pdata = (uint32_t *)data; mlen = len/4; data += 4*mlen; len -= 4*mlen; memcpy(r, bch->ecc_buf, sizeof(r)); /* * split each 32-bit word into 4 polynomials of weight 8 as follows: * * 31 ...24 23 ...16 15 ... 8 7 ... 0 * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt * tttttttt mod g = r0 (precomputed) * zzzzzzzz 00000000 mod g = r1 (precomputed) * yyyyyyyy 00000000 00000000 mod g = r2 (precomputed) * xxxxxxxx 00000000 00000000 00000000 mod g = r3 (precomputed) * xxxxxxxx yyyyyyyy zzzzzzzz tttttttt mod g = r0^r1^r2^r3 */ while (mlen--) { /* input data is read in big-endian format */ w = r[0]^cpu_to_be32(*pdata++); p0 = tab0 + (l+1)*((w >> 0) & 0xff); p1 = tab1 + (l+1)*((w >> 8) & 0xff); p2 = tab2 + (l+1)*((w >> 16) & 0xff); p3 = tab3 + (l+1)*((w >> 24) & 0xff); for (i = 0; i < l; i++) r[i] = r[i+1]^p0[i]^p1[i]^p2[i]^p3[i]; r[l] = p0[l]^p1[l]^p2[l]^p3[l]; } memcpy(bch->ecc_buf, r, sizeof(r)); /* process last unaligned bytes */ if (len) encode_bch_unaligned(bch, data, len, bch->ecc_buf); /* store ecc parity bytes into original parity buffer */ if (ecc) store_ecc8(bch, ecc, bch->ecc_buf); } EXPORT_SYMBOL_GPL(encode_bch); static inline int modulo(struct bch_control *bch, unsigned int v) { const unsigned int n = GF_N(bch); while (v >= n) { v -= n; v = (v & n) + (v >> GF_M(bch)); } return v; } /* * shorter and faster modulo function, only works when v < 2N. */ static inline int mod_s(struct bch_control *bch, unsigned int v) { const unsigned int n = GF_N(bch); return (v < n) ? v : v-n; } static inline int deg(unsigned int poly) { /* polynomial degree is the most-significant bit index */ return fls(poly)-1; } static inline int parity(unsigned int x) { /* * public domain code snippet, lifted from * http://www-graphics.stanford.edu/~seander/bithacks.html */ x ^= x >> 1; x ^= x >> 2; x = (x & 0x11111111U) * 0x11111111U; return (x >> 28) & 1; } /* Galois field basic operations: multiply, divide, inverse, etc. */ static inline unsigned int gf_mul(struct bch_control *bch, unsigned int a, unsigned int b) { return (a && b) ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ bch->a_log_tab[b])] : 0; } static inline unsigned int gf_sqr(struct bch_control *bch, unsigned int a) { return a ? bch->a_pow_tab[mod_s(bch, 2*bch->a_log_tab[a])] : 0; } static inline unsigned int gf_div(struct bch_control *bch, unsigned int a, unsigned int b) { return a ? bch->a_pow_tab[mod_s(bch, bch->a_log_tab[a]+ GF_N(bch)-bch->a_log_tab[b])] : 0; } static inline unsigned int gf_inv(struct bch_control *bch, unsigned int a) { return bch->a_pow_tab[GF_N(bch)-bch->a_log_tab[a]]; } static inline unsigned int a_pow(struct bch_control *bch, int i) { return bch->a_pow_tab[modulo(bch, i)]; } static inline int a_log(struct bch_control *bch, unsigned int x) { return bch->a_log_tab[x]; } static inline int a_ilog(struct bch_control *bch, unsigned int x) { return mod_s(bch, GF_N(bch)-bch->a_log_tab[x]); } /* * compute 2t syndromes of ecc polynomial, i.e. ecc(a^j) for j=1..2t */ static void compute_syndromes(struct bch_control *bch, uint32_t *ecc, unsigned int *syn) { int i, j, s; unsigned int m; uint32_t poly; const int t = GF_T(bch); s = bch->ecc_bits; /* make sure extra bits in last ecc word are cleared */ m = ((unsigned int)s) & 31; if (m) ecc[s/32] &= ~((1u << (32-m))-1); memset(syn, 0, 2*t*sizeof(*syn)); /* compute v(a^j) for j=1 .. 2t-1 */ do { poly = *ecc++; s -= 32; while (poly) { i = deg(poly); for (j = 0; j < 2*t; j += 2) syn[j] ^= a_pow(bch, (j+1)*(i+s)); poly ^= (1 << i); } } while (s > 0); /* v(a^(2j)) = v(a^j)^2 */ for (j = 0; j < t; j++) syn[2*j+1] = gf_sqr(bch, syn[j]); } static void gf_poly_copy(struct gf_poly *dst, struct gf_poly *src) { memcpy(dst, src, GF_POLY_SZ(src->deg)); } static int compute_error_locator_polynomial(struct bch_control *bch, const unsigned int *syn) { const unsigned int t = GF_T(bch); const unsigned int n = GF_N(bch); unsigned int i, j, tmp, l, pd = 1, d = syn[0]; struct gf_poly *elp = bch->elp; struct gf_poly *pelp = bch->poly_2t[0]; struct gf_poly *elp_copy = bch->poly_2t[1]; int k, pp = -1; memset(pelp, 0, GF_POLY_SZ(2*t)); memset(elp, 0, GF_POLY_SZ(2*t)); pelp->deg = 0; pelp->c[0] = 1; elp->deg = 0; elp->c[0] = 1; /* use simplified binary Berlekamp-Massey algorithm */ for (i = 0; (i < t) && (elp->deg <= t); i++) { if (d) { k = 2*i-pp; gf_poly_copy(elp_copy, elp); /* e[i+1](X) = e[i](X)+di*dp^-1*X^2(i-p)*e[p](X) */ tmp = a_log(bch, d)+n-a_log(bch, pd); for (j = 0; j <= pelp->deg; j++) { if (pelp->c[j]) { l = a_log(bch, pelp->c[j]); elp->c[j+k] ^= a_pow(bch, tmp+l); } } /* compute l[i+1] = max(l[i]->c[l[p]+2*(i-p]) */ tmp = pelp->deg+k; if (tmp > elp->deg) { elp->deg = tmp; gf_poly_copy(pelp, elp_copy); pd = d; pp = 2*i; } } /* di+1 = S(2i+3)+elp[i+1].1*S(2i+2)+...+elp[i+1].lS(2i+3-l) */ if (i < t-1) { d = syn[2*i+2]; for (j = 1; j <= elp->deg; j++) d ^= gf_mul(bch, elp->c[j], syn[2*i+2-j]); } } dbg("elp=%s\n", gf_poly_str(elp)); return (elp->deg > t) ? -1 : (int)elp->deg; } /* * solve a m x m linear system in GF(2) with an expected number of solutions, * and return the number of found solutions */ static int solve_linear_system(struct bch_control *bch, unsigned int *rows, unsigned int *sol, int nsol) { const int m = GF_M(bch); unsigned int tmp, mask; int rem, c, r, p, k, param[m]; k = 0; mask = 1 << m; /* Gaussian elimination */ for (c = 0; c < m; c++) { rem = 0; p = c-k; /* find suitable row for elimination */ for (r = p; r < m; r++) { if (rows[r] & mask) { if (r != p) { tmp = rows[r]; rows[r] = rows[p]; rows[p] = tmp; } rem = r+1; break; } } if (rem) { /* perform elimination on remaining rows */ tmp = rows[p]; for (r = rem; r < m; r++) { if (rows[r] & mask) rows[r] ^= tmp; } } else { /* elimination not needed, store defective row index */ param[k++] = c; } mask >>= 1; } /* rewrite system, inserting fake parameter rows */ if (k > 0) { p = k; for (r = m-1; r >= 0; r--) { if ((r > m-1-k) && rows[r]) /* system has no solution */ return 0; rows[r] = (p && (r == param[p-1])) ? p--, 1u << (m-r) : rows[r-p]; } } if (nsol != (1 << k)) /* unexpected number of solutions */ return 0; for (p = 0; p < nsol; p++) { /* set parameters for p-th solution */ for (c = 0; c < k; c++) rows[param[c]] = (rows[param[c]] & ~1)|((p >> c) & 1); /* compute unique solution */ tmp = 0; for (r = m-1; r >= 0; r--) { mask = rows[r] & (tmp|1); tmp |= parity(mask) << (m-r); } sol[p] = tmp >> 1; } return nsol; } /* * this function builds and solves a linear system for finding roots of a degree * 4 affine monic polynomial X^4+aX^2+bX+c over GF(2^m). */ static int find_affine4_roots(struct bch_control *bch, unsigned int a, unsigned int b, unsigned int c, unsigned int *roots) { int i, j, k; const int m = GF_M(bch); unsigned int mask = 0xff, t, rows[16] = {0,}; j = a_log(bch, b); k = a_log(bch, a); rows[0] = c; /* buid linear system to solve X^4+aX^2+bX+c = 0 */ for (i = 0; i < m; i++) { rows[i+1] = bch->a_pow_tab[4*i]^ (a ? bch->a_pow_tab[mod_s(bch, k)] : 0)^ (b ? bch->a_pow_tab[mod_s(bch, j)] : 0); j++; k += 2; } /* * transpose 16x16 matrix before passing it to linear solver * warning: this code assumes m < 16 */ for (j = 8; j != 0; j >>= 1, mask ^= (mask << j)) { for (k = 0; k < 16; k = (k+j+1) & ~j) { t = ((rows[k] >> j)^rows[k+j]) & mask; rows[k] ^= (t << j); rows[k+j] ^= t; } } return solve_linear_system(bch, rows, roots, 4); } /* * compute root r of a degree 1 polynomial over GF(2^m) (returned as log(1/r)) */ static int find_poly_deg1_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { int n = 0; if (poly->c[0]) /* poly[X] = bX+c with c!=0, root=c/b */ roots[n++] = mod_s(bch, GF_N(bch)-bch->a_log_tab[poly->c[0]]+ bch->a_log_tab[poly->c[1]]); return n; } /* * compute roots of a degree 2 polynomial over GF(2^m) */ static int find_poly_deg2_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { int n = 0, i, l0, l1, l2; unsigned int u, v, r; if (poly->c[0] && poly->c[1]) { l0 = bch->a_log_tab[poly->c[0]]; l1 = bch->a_log_tab[poly->c[1]]; l2 = bch->a_log_tab[poly->c[2]]; /* using z=a/bX, transform aX^2+bX+c into z^2+z+u (u=ac/b^2) */ u = a_pow(bch, l0+l2+2*(GF_N(bch)-l1)); /* * let u = sum(li.a^i) i=0..m-1; then compute r = sum(li.xi): * r^2+r = sum(li.(xi^2+xi)) = sum(li.(a^i+Tr(a^i).a^k)) = * u + sum(li.Tr(a^i).a^k) = u+a^k.Tr(sum(li.a^i)) = u+a^k.Tr(u) * i.e. r and r+1 are roots iff Tr(u)=0 */ r = 0; v = u; while (v) { i = deg(v); r ^= bch->xi_tab[i]; v ^= (1 << i); } /* verify root */ if ((gf_sqr(bch, r)^r) == u) { /* reverse z=a/bX transformation and compute log(1/r) */ roots[n++] = modulo(bch, 2*GF_N(bch)-l1- bch->a_log_tab[r]+l2); roots[n++] = modulo(bch, 2*GF_N(bch)-l1- bch->a_log_tab[r^1]+l2); } } return n; } /* * compute roots of a degree 3 polynomial over GF(2^m) */ static int find_poly_deg3_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { int i, n = 0; unsigned int a, b, c, a2, b2, c2, e3, tmp[4]; if (poly->c[0]) { /* transform polynomial into monic X^3 + a2X^2 + b2X + c2 */ e3 = poly->c[3]; c2 = gf_div(bch, poly->c[0], e3); b2 = gf_div(bch, poly->c[1], e3); a2 = gf_div(bch, poly->c[2], e3); /* (X+a2)(X^3+a2X^2+b2X+c2) = X^4+aX^2+bX+c (affine) */ c = gf_mul(bch, a2, c2); /* c = a2c2 */ b = gf_mul(bch, a2, b2)^c2; /* b = a2b2 + c2 */ a = gf_sqr(bch, a2)^b2; /* a = a2^2 + b2 */ /* find the 4 roots of this affine polynomial */ if (find_affine4_roots(bch, a, b, c, tmp) == 4) { /* remove a2 from final list of roots */ for (i = 0; i < 4; i++) { if (tmp[i] != a2) roots[n++] = a_ilog(bch, tmp[i]); } } } return n; } /* * compute roots of a degree 4 polynomial over GF(2^m) */ static int find_poly_deg4_roots(struct bch_control *bch, struct gf_poly *poly, unsigned int *roots) { int i, l, n = 0; unsigned int a, b, c, d, e = 0, f, a2, b2, c2, e4; if (poly->c[0] == 0) return 0; /* transform polynomial into monic X^4 + aX^3 + bX^2 + cX + d */ e4 = poly->c[4]; d = gf_div(bch, poly->c[0], e4); c = gf_div(bch, poly->c[1], e4); b = gf_div(bch, poly->c[2], e4); a = gf_div(bch, poly->c[3], e4); /* use Y=1/X transformation to get an affine polynomial */ if (a) { /* first, eliminate cX by using z=X+e with ae^2+c=0 */ if (c) { /* compute e such that e^2 = c/a */ f = gf_div(bch, c, a); l = a_log(bch, f); l += (l & 1) ? GF_N(bch) : 0; e = a_pow(bch, l/2); /* * use transformation z=X+e: * z^4+e^4 + a(z^3+ez^2+e^2z+e^3) + b(z^2+e^2) +cz+ce+d * z^4 + az^3 + (ae+b)z^2 + (ae^2+c)z+e^4+be^2+ae^3+ce+d * z^4 + az^3 + (ae+b)z^2 + e^4+be^2+d * z^4 + az^3 + b'z^2 + d' */ d = a_pow(bch, 2*l)^gf_mul(bch, b, f)^d; b = gf_mul(bch, a, e)^b; } /* now, use Y=1/X to get Y^4 + b/dY^2 + a/dY + 1/d */ if (d == 0) /* assume all roots have multiplicity 1 */ return 0; c2 = gf_inv(bch, d); b2 = gf_div(bch, a, d); a2 = gf_div(bch, b, d); } else { /* polynomial is already affine */ c2 = d; b2 = c; a2 = b; } /* find the 4 roots of this affine polynomial */ if (find_affine4_roots(bch, a2, b2, c2, roots) == 4) { for (i = 0; i < 4; i++) { /* post-process roots (reverse transformations) */ f = a ? gf_inv(bch, roots[i]) : roots[i]; roots[i] = a_ilog(bch, f^e); } n = 4; } return n; } /* * build monic, log-based representation of a polynomial */ static void gf_poly_logrep(struct bch_control *bch, const struct gf_poly *a, int *rep) { int i, d = a->deg, l = GF_N(bch)-a_log(bch, a->c[a->deg]); /* represent 0 values with -1; warning, rep[d] is not set to 1 */ for (i = 0; i < d; i++) rep[i] = a->c[i] ? mod_s(bch, a_log(bch, a->c[i])+l) : -1; } /* * compute polynomial Euclidean division remainder in GF(2^m)[X] */ static void gf_poly_mod(struct bch_control *bch, struct gf_poly *a, const struct gf_poly *b, int *rep) { int la, p, m; unsigned int i, j, *c = a->c; const unsigned int d = b->deg; if (a->deg < d) return; /* reuse or compute log representation of denominator */ if (!rep) { rep = bch->cache; gf_poly_logrep(bch, b, rep); } for (j = a->deg; j >= d; j--) { if (c[j]) { la = a_log(bch, c[j]); p = j-d; for (i = 0; i < d; i++, p++) { m = rep[i]; if (m >= 0) c[p] ^= bch->a_pow_tab[mod_s(bch, m+la)]; } } } a->deg = d-1; while (!c[a->deg] && a->deg) a->deg--; } /* * compute polynomial Euclidean division quotient in GF(2^m)[X] */ static void gf_poly_div(struct bch_control *bch, struct gf_poly *a, const struct gf_poly *b, struct gf_poly *q) { if (a->deg >= b->deg) { q->deg = a->deg-b->deg; /* compute a mod b (modifies a) */ gf_poly_mod(bch, a, b, NULL); /* quotient is stored in upper part of polynomial a */ memcpy(q->c, &a->c[b->deg], (1+q->deg)*sizeof(unsigned int)); } else { q->deg = 0; q->c[0] = 0; } } /* * compute polynomial GCD (Greatest Common Divisor) in GF(2^m)[X] */ static struct gf_poly *gf_poly_gcd(struct bch_control *bch, struct gf_poly *a, struct gf_poly *b) { struct gf_poly *tmp; dbg("gcd(%s,%s)=", gf_poly_str(a), gf_poly_str(b)); if (a->deg < b->deg) { tmp = b; b = a; a = tmp; }