From d7e5a5462f68270ed66efff22b1981be57a28c19 Mon Sep 17 00:00:00 2001 From: Segher Boessenkool Date: Wed, 2 May 2007 12:18:41 +0200 Subject: [RSLIB] Support non-canonical GF representations MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit For the CAFÉ NAND controller, we need to support non-canonical representations of the Galois field. Allow the caller to provide its own function for generating the field, and CAFÉ can use rslib instead of its own implementation. Signed-off-by: Segher Boessenkool Signed-off-by: David Woodhouse --- lib/reed_solomon/reed_solomon.c | 84 +++++++++++++++++++++++++++++++++-------- 1 file changed, 69 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c index a4b730a2180c..5b0d8522b7ca 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -56,6 +56,7 @@ static DEFINE_MUTEX(rslistlock); * rs_init - Initialize a Reed-Solomon codec * @symsize: symbol size, bits (1-8) * @gfpoly: Field generator polynomial coefficients + * @gffunc: Field generator function * @fcr: first root of RS code generator polynomial, index form * @prim: primitive element to generate polynomial roots * @nroots: RS code generator polynomial degree (number of roots) @@ -63,8 +64,8 @@ static DEFINE_MUTEX(rslistlock); * Allocate a control structure and the polynom arrays for faster * en/decoding. Fill the arrays according to the given parameters. */ -static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, - int prim, int nroots) +static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int), + int fcr, int prim, int nroots) { struct rs_control *rs; int i, j, sr, root, iprim; @@ -82,6 +83,7 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, rs->prim = prim; rs->nroots = nroots; rs->gfpoly = gfpoly; + rs->gffunc = gffunc; /* Allocate the arrays */ rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); @@ -99,17 +101,26 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, /* Generate Galois field lookup tables */ rs->index_of[0] = rs->nn; /* log(zero) = -inf */ rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ - sr = 1; - for (i = 0; i < rs->nn; i++) { - rs->index_of[sr] = i; - rs->alpha_to[i] = sr; - sr <<= 1; - if (sr & (1 << symsize)) - sr ^= gfpoly; - sr &= rs->nn; + if (gfpoly) { + sr = 1; + for (i = 0; i < rs->nn; i++) { + rs->index_of[sr] = i; + rs->alpha_to[i] = sr; + sr <<= 1; + if (sr & (1 << symsize)) + sr ^= gfpoly; + sr &= rs->nn; + } + } else { + sr = gffunc(0); + for (i = 0; i < rs->nn; i++) { + rs->index_of[sr] = i; + rs->alpha_to[i] = sr; + sr = gffunc(sr); + } } /* If it's not primitive, exit */ - if(sr != 1) + if(sr != rs->alpha_to[0]) goto errpol; /* Find prim-th root of 1, used in decoding */ @@ -173,18 +184,22 @@ void free_rs(struct rs_control *rs) } /** - * init_rs - Find a matching or allocate a new rs control structure + * init_rs_internal - Find a matching or allocate a new rs control structure * @symsize: the symbol size (number of bits) * @gfpoly: the extended Galois field generator polynomial coefficients, * with the 0th coefficient in the low order bit. The polynomial * must be primitive; + * @gffunc: pointer to function to generate the next field element, + * or the multiplicative identity element if given 0. Used + * instead of gfpoly if gfpoly is 0 * @fcr: the first consecutive root of the rs code generator polynomial * in index form * @prim: primitive element to generate polynomial roots * @nroots: RS code generator polynomial degree (number of roots) */ -struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, - int nroots) +static struct rs_control *init_rs_internal(int symsize, int gfpoly, + int (*gffunc)(int), int fcr, + int prim, int nroots) { struct list_head *tmp; struct rs_control *rs; @@ -208,6 +223,8 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, continue; if (gfpoly != rs->gfpoly) continue; + if (gffunc != rs->gffunc) + continue; if (fcr != rs->fcr) continue; if (prim != rs->prim) @@ -220,7 +237,7 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, } /* Create a new one */ - rs = rs_init(symsize, gfpoly, fcr, prim, nroots); + rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots); if (rs) { rs->users = 1; list_add(&rs->list, &rslist); @@ -230,6 +247,42 @@ out: return rs; } +/** + * init_rs - Find a matching or allocate a new rs control structure + * @symsize: the symbol size (number of bits) + * @gfpoly: the extended Galois field generator polynomial coefficients, + * with the 0th coefficient in the low order bit. The polynomial + * must be primitive; + * @fcr: the first consecutive root of the rs code generator polynomial + * in index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + */ +struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, + int nroots) +{ + return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots); +} + +/** + * init_rs_non_canonical - Find a matching or allocate a new rs control + * structure, for fields with non-canonical + * representation + * @symsize: the symbol size (number of bits) + * @gffunc: pointer to function to generate the next field element, + * or the multiplicative identity element if given 0. Used + * instead of gfpoly if gfpoly is 0 + * @fcr: the first consecutive root of the rs code generator polynomial + * in index form + * @prim: primitive element to generate polynomial roots + * @nroots: RS code generator polynomial degree (number of roots) + */ +struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), + int fcr, int prim, int nroots) +{ + return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots); +} + #ifdef CONFIG_REED_SOLOMON_ENC8 /** * encode_rs8 - Calculate the parity for data values (8bit data width) @@ -321,6 +374,7 @@ EXPORT_SYMBOL_GPL(decode_rs16); #endif EXPORT_SYMBOL_GPL(init_rs); +EXPORT_SYMBOL_GPL(init_rs_non_canonical); EXPORT_SYMBOL_GPL(free_rs); MODULE_LICENSE("GPL"); -- cgit v1.2.1