diff options
Diffstat (limited to 'lib/reed_solomon')
| -rw-r--r-- | lib/reed_solomon/decode_rs.c | 34 | ||||
| -rw-r--r-- | lib/reed_solomon/encode_rs.c | 15 | ||||
| -rw-r--r-- | lib/reed_solomon/reed_solomon.c | 240 |
3 files changed, 159 insertions, 130 deletions
diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c index 0ec3f257ffdf..1db74eb098d0 100644 --- a/lib/reed_solomon/decode_rs.c +++ b/lib/reed_solomon/decode_rs.c @@ -1,22 +1,16 @@ +// SPDX-License-Identifier: GPL-2.0 /* - * lib/reed_solomon/decode_rs.c - * - * Overview: - * Generic Reed Solomon encoder / decoder library + * Generic Reed Solomon encoder / decoder library * * Copyright 2002, Phil Karn, KA9Q * May be used under the terms of the GNU General Public License (GPL) * * Adaption to the kernel by Thomas Gleixner (tglx@linutronix.de) * - * $Id: decode_rs.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $ - * - */ - -/* Generic data width independent code which is included by the - * wrappers. + * Generic data width independent code which is included by the wrappers. */ { + struct rs_codec *rs = rsc->codec; int deg_lambda, el, deg_omega; int i, j, r, k, pad; int nn = rs->nn; @@ -27,16 +21,22 @@ uint16_t *alpha_to = rs->alpha_to; uint16_t *index_of = rs->index_of; uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error; - /* Err+Eras Locator poly and syndrome poly The maximum value - * of nroots is 8. So the necessary stack size will be about - * 220 bytes max. - */ - uint16_t lambda[nroots + 1], syn[nroots]; - uint16_t b[nroots + 1], t[nroots + 1], omega[nroots + 1]; - uint16_t root[nroots], reg[nroots + 1], loc[nroots]; int count = 0; uint16_t msk = (uint16_t) rs->nn; + /* + * The decoder buffers are in the rs control struct. They are + * arrays sized [nroots + 1] + */ + uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1); + uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1); + uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1); + uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1); + uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1); + uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1); + uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1); + uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1); + /* Check length parameter for validity */ pad = nn - nroots - len; BUG_ON(pad < 0 || pad >= nn); diff --git a/lib/reed_solomon/encode_rs.c b/lib/reed_solomon/encode_rs.c index 0b5b1a6728ec..9112d46e869e 100644 --- a/lib/reed_solomon/encode_rs.c +++ b/lib/reed_solomon/encode_rs.c @@ -1,23 +1,16 @@ +// SPDX-License-Identifier: GPL-2.0 /* - * lib/reed_solomon/encode_rs.c - * - * Overview: - * Generic Reed Solomon encoder / decoder library + * Generic Reed Solomon encoder / decoder library * * Copyright 2002, Phil Karn, KA9Q * May be used under the terms of the GNU General Public License (GPL) * * Adaption to the kernel by Thomas Gleixner (tglx@linutronix.de) * - * $Id: encode_rs.c,v 1.5 2005/11/07 11:14:59 gleixner Exp $ - * - */ - -/* Generic data width independent code which is included by the - * wrappers. - * int encode_rsX (struct rs_control *rs, uintX_t *data, int len, uintY_t *par) + * Generic data width independent code which is included by the wrappers. */ { + struct rs_codec *rs = rsc->codec; int i, j, pad; int nn = rs->nn; int nroots = rs->nroots; diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c index 06d04cfa9339..dfcf54242fb9 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -1,43 +1,34 @@ +// SPDX-License-Identifier: GPL-2.0 /* - * lib/reed_solomon/reed_solomon.c - * - * Overview: - * Generic Reed Solomon encoder / decoder library + * Generic Reed Solomon encoder / decoder library * * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de) * * Reed Solomon code lifted from reed solomon library written by Phil Karn * Copyright 2002 Phil Karn, KA9Q * - * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $ - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. - * * Description: * * The generic Reed Solomon library provides runtime configurable * encoding / decoding of RS codes. - * Each user must call init_rs to get a pointer to a rs_control - * structure for the given rs parameters. This structure is either - * generated or a already available matching control structure is used. - * If a structure is generated then the polynomial arrays for - * fast encoding / decoding are built. This can take some time so - * make sure not to call this function from a time critical path. - * Usually a module / driver should initialize the necessary - * rs_control structure on module / driver init and release it - * on exit. - * The encoding puts the calculated syndrome into a given syndrome - * buffer. - * The decoding is a two step process. The first step calculates - * the syndrome over the received (data + syndrome) and calls the - * second stage, which does the decoding / error correction itself. - * Many hw encoders provide a syndrome calculation over the received - * data + syndrome and can call the second stage directly. * + * Each user must call init_rs to get a pointer to a rs_control structure + * for the given rs parameters. The control struct is unique per instance. + * It points to a codec which can be shared by multiple control structures. + * If a codec is newly allocated then the polynomial arrays for fast + * encoding / decoding are built. This can take some time so make sure not + * to call this function from a time critical path. Usually a module / + * driver should initialize the necessary rs_control structure on module / + * driver init and release it on exit. + * + * The encoding puts the calculated syndrome into a given syndrome buffer. + * + * The decoding is a two step process. The first step calculates the + * syndrome over the received (data + syndrome) and calls the second stage, + * which does the decoding / error correction itself. Many hw encoders + * provide a syndrome calculation over the received data + syndrome and can + * call the second stage directly. */ - #include <linux/errno.h> #include <linux/kernel.h> #include <linux/init.h> @@ -46,32 +37,44 @@ #include <linux/slab.h> #include <linux/mutex.h> -/* This list holds all currently allocated rs control structures */ -static LIST_HEAD (rslist); +enum { + RS_DECODE_LAMBDA, + RS_DECODE_SYN, + RS_DECODE_B, + RS_DECODE_T, + RS_DECODE_OMEGA, + RS_DECODE_ROOT, + RS_DECODE_REG, + RS_DECODE_LOC, + RS_DECODE_NUM_BUFFERS +}; + +/* This list holds all currently allocated rs codec structures */ +static LIST_HEAD(codec_list); /* Protection for the list */ static DEFINE_MUTEX(rslistlock); /** - * rs_init - Initialize a Reed-Solomon codec + * codec_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) + * @gfp: GFP_ flags for allocations * - * Allocate a control structure and the polynom arrays for faster + * Allocate a codec 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 (*gffunc)(int), - int fcr, int prim, int nroots) +static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int), + int fcr, int prim, int nroots, gfp_t gfp) { - struct rs_control *rs; int i, j, sr, root, iprim; + struct rs_codec *rs; - /* Allocate the control structure */ - rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL); - if (rs == NULL) + rs = kzalloc(sizeof(*rs), gfp); + if (!rs) return NULL; INIT_LIST_HEAD(&rs->list); @@ -85,17 +88,17 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int), rs->gffunc = gffunc; /* Allocate the arrays */ - rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); + rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp); if (rs->alpha_to == NULL) - goto errrs; + goto err; - rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL); + rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp); if (rs->index_of == NULL) - goto erralp; + goto err; - rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL); + rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), gfp); if(rs->genpoly == NULL) - goto erridx; + goto err; /* Generate Galois field lookup tables */ rs->index_of[0] = rs->nn; /* log(zero) = -inf */ @@ -120,7 +123,7 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int), } /* If it's not primitive, exit */ if(sr != rs->alpha_to[0]) - goto errpol; + goto err; /* Find prim-th root of 1, used in decoding */ for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn); @@ -148,42 +151,52 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int), /* convert rs->genpoly[] to index form for quicker encoding */ for (i = 0; i <= nroots; i++) rs->genpoly[i] = rs->index_of[rs->genpoly[i]]; + + rs->users = 1; + list_add(&rs->list, &codec_list); return rs; - /* Error exit */ -errpol: +err: kfree(rs->genpoly); -erridx: kfree(rs->index_of); -erralp: kfree(rs->alpha_to); -errrs: kfree(rs); return NULL; } /** - * free_rs - Free the rs control structure, if it is no longer used - * @rs: the control structure which is not longer used by the + * free_rs - Free the rs control structure + * @rs: The control structure which is not longer used by the * caller + * + * Free the control structure. If @rs is the last user of the associated + * codec, free the codec as well. */ void free_rs(struct rs_control *rs) { + struct rs_codec *cd; + + if (!rs) + return; + + cd = rs->codec; mutex_lock(&rslistlock); - rs->users--; - if(!rs->users) { - list_del(&rs->list); - kfree(rs->alpha_to); - kfree(rs->index_of); - kfree(rs->genpoly); - kfree(rs); + cd->users--; + if(!cd->users) { + list_del(&cd->list); + kfree(cd->alpha_to); + kfree(cd->index_of); + kfree(cd->genpoly); + kfree(cd); } mutex_unlock(&rslistlock); + kfree(rs); } +EXPORT_SYMBOL_GPL(free_rs); /** - * init_rs_internal - Find a matching or allocate a new rs control structure + * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one * @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 @@ -191,55 +204,69 @@ void free_rs(struct rs_control *rs) * @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 + * @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) + * @gfp: GFP_ flags for allocations */ static struct rs_control *init_rs_internal(int symsize, int gfpoly, - int (*gffunc)(int), int fcr, - int prim, int nroots) + int (*gffunc)(int), int fcr, + int prim, int nroots, gfp_t gfp) { - struct list_head *tmp; - struct rs_control *rs; + struct list_head *tmp; + struct rs_control *rs; + unsigned int bsize; /* Sanity checks */ if (symsize < 1) return NULL; if (fcr < 0 || fcr >= (1<<symsize)) - return NULL; + return NULL; if (prim <= 0 || prim >= (1<<symsize)) - return NULL; + return NULL; if (nroots < 0 || nroots >= (1<<symsize)) return NULL; + /* + * The decoder needs buffers in each control struct instance to + * avoid variable size or large fixed size allocations on + * stack. Size the buffers to arrays of [nroots + 1]. + */ + bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1); + rs = kzalloc(sizeof(*rs) + bsize, gfp); + if (!rs) + return NULL; + mutex_lock(&rslistlock); /* Walk through the list and look for a matching entry */ - list_for_each(tmp, &rslist) { - rs = list_entry(tmp, struct rs_control, list); - if (symsize != rs->mm) + list_for_each(tmp, &codec_list) { + struct rs_codec *cd = list_entry(tmp, struct rs_codec, list); + + if (symsize != cd->mm) continue; - if (gfpoly != rs->gfpoly) + if (gfpoly != cd->gfpoly) continue; - if (gffunc != rs->gffunc) + if (gffunc != cd->gffunc) continue; - if (fcr != rs->fcr) + if (fcr != cd->fcr) continue; - if (prim != rs->prim) + if (prim != cd->prim) continue; - if (nroots != rs->nroots) + if (nroots != cd->nroots) continue; /* We have a matching one already */ - rs->users++; + cd->users++; + rs->codec = cd; goto out; } /* Create a new one */ - rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots); - if (rs) { - rs->users = 1; - list_add(&rs->list, &rslist); + rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp); + if (!rs->codec) { + kfree(rs); + rs = NULL; } out: mutex_unlock(&rslistlock); @@ -247,45 +274,48 @@ out: } /** - * init_rs - Find a matching or allocate a new rs control structure + * init_rs_gfp - Create a RS control struct and initialize it * @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 + * @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) + * @gfp: GFP_ flags for allocations */ -struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, - int nroots) +struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim, + int nroots, gfp_t gfp) { - return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots); + return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp); } +EXPORT_SYMBOL_GPL(init_rs_gfp); /** - * init_rs_non_canonical - Find a matching or allocate a new rs control - * structure, for fields with non-canonical - * representation + * init_rs_non_canonical - Allocate rs control struct 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 + * @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) + int fcr, int prim, int nroots) { - return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots); + return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots, + GFP_KERNEL); } +EXPORT_SYMBOL_GPL(init_rs_non_canonical); #ifdef CONFIG_REED_SOLOMON_ENC8 /** * encode_rs8 - Calculate the parity for data values (8bit data width) - * @rs: the rs control structure + * @rsc: the rs control structure * @data: data field of a given type * @len: data length * @par: parity data, must be initialized by caller (usually all 0) @@ -295,7 +325,7 @@ struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), * symbol size > 8. The calling code must take care of encoding of the * syndrome result for storage itself. */ -int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par, +int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par, uint16_t invmsk) { #include "encode_rs.c" @@ -306,7 +336,7 @@ EXPORT_SYMBOL_GPL(encode_rs8); #ifdef CONFIG_REED_SOLOMON_DEC8 /** * decode_rs8 - Decode codeword (8bit data width) - * @rs: the rs control structure + * @rsc: the rs control structure * @data: data field of a given type * @par: received parity data field * @len: data length @@ -319,9 +349,14 @@ EXPORT_SYMBOL_GPL(encode_rs8); * The syndrome and parity uses a uint16_t data type to enable * symbol size > 8. The calling code must take care of decoding of the * syndrome result and the received parity before calling this code. + * + * Note: The rs_control struct @rsc contains buffers which are used for + * decoding, so the caller has to ensure that decoder invocations are + * serialized. + * * Returns the number of corrected bits or -EBADMSG for uncorrectable errors. */ -int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len, +int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, uint16_t *corr) { @@ -333,7 +368,7 @@ EXPORT_SYMBOL_GPL(decode_rs8); #ifdef CONFIG_REED_SOLOMON_ENC16 /** * encode_rs16 - Calculate the parity for data values (16bit data width) - * @rs: the rs control structure + * @rsc: the rs control structure * @data: data field of a given type * @len: data length * @par: parity data, must be initialized by caller (usually all 0) @@ -341,7 +376,7 @@ EXPORT_SYMBOL_GPL(decode_rs8); * * Each field in the data array contains up to symbol size bits of valid data. */ -int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par, +int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par, uint16_t invmsk) { #include "encode_rs.c" @@ -352,7 +387,7 @@ EXPORT_SYMBOL_GPL(encode_rs16); #ifdef CONFIG_REED_SOLOMON_DEC16 /** * decode_rs16 - Decode codeword (16bit data width) - * @rs: the rs control structure + * @rsc: the rs control structure * @data: data field of a given type * @par: received parity data field * @len: data length @@ -363,9 +398,14 @@ EXPORT_SYMBOL_GPL(encode_rs16); * @corr: buffer to store correction bitmask on eras_pos * * Each field in the data array contains up to symbol size bits of valid data. + * + * Note: The rc_control struct @rsc contains buffers which are used for + * decoding, so the caller has to ensure that decoder invocations are + * serialized. + * * Returns the number of corrected bits or -EBADMSG for uncorrectable errors. */ -int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, +int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, uint16_t *corr) { @@ -374,10 +414,6 @@ int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, 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"); MODULE_DESCRIPTION("Reed Solomon encoder/decoder"); MODULE_AUTHOR("Phil Karn, Thomas Gleixner"); |