lib/reed_solomon/reed_solomon.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Generic Reed Solomon encoder / decoder library
0004  *
0005  * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
0006  *
0007  * Reed Solomon code lifted from reed solomon library written by Phil Karn
0008  * Copyright 2002 Phil Karn, KA9Q
0009  *
0010  * Description:
0011  *
0012  * The generic Reed Solomon library provides runtime configurable
0013  * encoding / decoding of RS codes.
0014  *
0015  * Each user must call init_rs to get a pointer to a rs_control structure
0016  * for the given rs parameters. The control struct is unique per instance.
0017  * It points to a codec which can be shared by multiple control structures.
0018  * If a codec is newly allocated then the polynomial arrays for fast
0019  * encoding / decoding are built. This can take some time so make sure not
0020  * to call this function from a time critical path.  Usually a module /
0021  * driver should initialize the necessary rs_control structure on module /
0022  * driver init and release it on exit.
0023  *
0024  * The encoding puts the calculated syndrome into a given syndrome buffer.
0025  *
0026  * The decoding is a two step process. The first step calculates the
0027  * syndrome over the received (data + syndrome) and calls the second stage,
0028  * which does the decoding / error correction itself.  Many hw encoders
0029  * provide a syndrome calculation over the received data + syndrome and can
0030  * call the second stage directly.
0031  */
0032 #include <linux/errno.h>
0033 #include <linux/kernel.h>
0034 #include <linux/init.h>
0035 #include <linux/module.h>
0036 #include <linux/rslib.h>
0037 #include <linux/slab.h>
0038 #include <linux/mutex.h>
0039
0040 enum {
0041     RS_DECODE_LAMBDA,
0042     RS_DECODE_SYN,
0043     RS_DECODE_B,
0044     RS_DECODE_T,
0045     RS_DECODE_OMEGA,
0046     RS_DECODE_ROOT,
0047     RS_DECODE_REG,
0048     RS_DECODE_LOC,
0049     RS_DECODE_NUM_BUFFERS
0050 };
0051
0052 /* This list holds all currently allocated rs codec structures */
0053 static LIST_HEAD(codec_list);
0054 /* Protection for the list */
0055 static DEFINE_MUTEX(rslistlock);
0056
0057 /**
0058  * codec_init - Initialize a Reed-Solomon codec
0059  * @symsize:    symbol size, bits (1-8)
0060  * @gfpoly: Field generator polynomial coefficients
0061  * @gffunc: Field generator function
0062  * @fcr:    first root of RS code generator polynomial, index form
0063  * @prim:   primitive element to generate polynomial roots
0064  * @nroots: RS code generator polynomial degree (number of roots)
0065  * @gfp:    GFP_ flags for allocations
0066  *
0067  * Allocate a codec structure and the polynom arrays for faster
0068  * en/decoding. Fill the arrays according to the given parameters.
0069  */
0070 static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
0071                    int fcr, int prim, int nroots, gfp_t gfp)
0072 {
0073     int i, j, sr, root, iprim;
0074     struct rs_codec *rs;
0075
0076     rs = kzalloc(sizeof(*rs), gfp);
0077     if (!rs)
0078         return NULL;
0079
0080     INIT_LIST_HEAD(&rs->list);
0081
0082     rs->mm = symsize;
0083     rs->nn = (1 << symsize) - 1;
0084     rs->fcr = fcr;
0085     rs->prim = prim;
0086     rs->nroots = nroots;
0087     rs->gfpoly = gfpoly;
0088     rs->gffunc = gffunc;
0089
0090     /* Allocate the arrays */
0091     rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
0092     if (rs->alpha_to == NULL)
0093         goto err;
0094
0095     rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
0096     if (rs->index_of == NULL)
0097         goto err;
0098
0099     rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp);
0100     if(rs->genpoly == NULL)
0101         goto err;
0102
0103     /* Generate Galois field lookup tables */
0104     rs->index_of[0] = rs->nn;   /* log(zero) = -inf */
0105     rs->alpha_to[rs->nn] = 0;   /* alpha**-inf = 0 */
0106     if (gfpoly) {
0107         sr = 1;
0108         for (i = 0; i < rs->nn; i++) {
0109             rs->index_of[sr] = i;
0110             rs->alpha_to[i] = sr;
0111             sr <<= 1;
0112             if (sr & (1 << symsize))
0113                 sr ^= gfpoly;
0114             sr &= rs->nn;
0115         }
0116     } else {
0117         sr = gffunc(0);
0118         for (i = 0; i < rs->nn; i++) {
0119             rs->index_of[sr] = i;
0120             rs->alpha_to[i] = sr;
0121             sr = gffunc(sr);
0122         }
0123     }
0124     /* If it's not primitive, exit */
0125     if(sr != rs->alpha_to[0])
0126         goto err;
0127
0128     /* Find prim-th root of 1, used in decoding */
0129     for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
0130     /* prim-th root of 1, index form */
0131     rs->iprim = iprim / prim;
0132
0133     /* Form RS code generator polynomial from its roots */
0134     rs->genpoly[0] = 1;
0135     for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
0136         rs->genpoly[i + 1] = 1;
0137         /* Multiply rs->genpoly[] by  @**(root + x) */
0138         for (j = i; j > 0; j--) {
0139             if (rs->genpoly[j] != 0) {
0140                 rs->genpoly[j] = rs->genpoly[j -1] ^
0141                     rs->alpha_to[rs_modnn(rs,
0142                     rs->index_of[rs->genpoly[j]] + root)];
0143             } else
0144                 rs->genpoly[j] = rs->genpoly[j - 1];
0145         }
0146         /* rs->genpoly[0] can never be zero */
0147         rs->genpoly[0] =
0148             rs->alpha_to[rs_modnn(rs,
0149                 rs->index_of[rs->genpoly[0]] + root)];
0150     }
0151     /* convert rs->genpoly[] to index form for quicker encoding */
0152     for (i = 0; i <= nroots; i++)
0153         rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
0154
0155     rs->users = 1;
0156     list_add(&rs->list, &codec_list);
0157     return rs;
0158
0159 err:
0160     kfree(rs->genpoly);
0161     kfree(rs->index_of);
0162     kfree(rs->alpha_to);
0163     kfree(rs);
0164     return NULL;
0165 }
0166
0167
0168 /**
0169  *  free_rs - Free the rs control structure
0170  *  @rs:    The control structure which is not longer used by the
0171  *      caller
0172  *
0173  * Free the control structure. If @rs is the last user of the associated
0174  * codec, free the codec as well.
0175  */
0176 void free_rs(struct rs_control *rs)
0177 {
0178     struct rs_codec *cd;
0179
0180     if (!rs)
0181         return;
0182
0183     cd = rs->codec;
0184     mutex_lock(&rslistlock);
0185     cd->users--;
0186     if(!cd->users) {
0187         list_del(&cd->list);
0188         kfree(cd->alpha_to);
0189         kfree(cd->index_of);
0190         kfree(cd->genpoly);
0191         kfree(cd);
0192     }
0193     mutex_unlock(&rslistlock);
0194     kfree(rs);
0195 }
0196 EXPORT_SYMBOL_GPL(free_rs);
0197
0198 /**
0199  * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one
0200  *  @symsize:   the symbol size (number of bits)
0201  *  @gfpoly:    the extended Galois field generator polynomial coefficients,
0202  *      with the 0th coefficient in the low order bit. The polynomial
0203  *      must be primitive;
0204  *  @gffunc:    pointer to function to generate the next field element,
0205  *      or the multiplicative identity element if given 0.  Used
0206  *      instead of gfpoly if gfpoly is 0
0207  *  @fcr:   the first consecutive root of the rs code generator polynomial
0208  *      in index form
0209  *  @prim:  primitive element to generate polynomial roots
0210  *  @nroots:    RS code generator polynomial degree (number of roots)
0211  *  @gfp:   GFP_ flags for allocations
0212  */
0213 static struct rs_control *init_rs_internal(int symsize, int gfpoly,
0214                        int (*gffunc)(int), int fcr,
0215                        int prim, int nroots, gfp_t gfp)
0216 {
0217     struct list_head *tmp;
0218     struct rs_control *rs;
0219     unsigned int bsize;
0220
0221     /* Sanity checks */
0222     if (symsize < 1)
0223         return NULL;
0224     if (fcr < 0 || fcr >= (1<<symsize))
0225         return NULL;
0226     if (prim <= 0 || prim >= (1<<symsize))
0227         return NULL;
0228     if (nroots < 0 || nroots >= (1<<symsize))
0229         return NULL;
0230
0231     /*
0232      * The decoder needs buffers in each control struct instance to
0233      * avoid variable size or large fixed size allocations on
0234      * stack. Size the buffers to arrays of [nroots + 1].
0235      */
0236     bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
0237     rs = kzalloc(sizeof(*rs) + bsize, gfp);
0238     if (!rs)
0239         return NULL;
0240
0241     mutex_lock(&rslistlock);
0242
0243     /* Walk through the list and look for a matching entry */
0244     list_for_each(tmp, &codec_list) {
0245         struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);
0246
0247         if (symsize != cd->mm)
0248             continue;
0249         if (gfpoly != cd->gfpoly)
0250             continue;
0251         if (gffunc != cd->gffunc)
0252             continue;
0253         if (fcr != cd->fcr)
0254             continue;
0255         if (prim != cd->prim)
0256             continue;
0257         if (nroots != cd->nroots)
0258             continue;
0259         /* We have a matching one already */
0260         cd->users++;
0261         rs->codec = cd;
0262         goto out;
0263     }
0264
0265     /* Create a new one */
0266     rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
0267     if (!rs->codec) {
0268         kfree(rs);
0269         rs = NULL;
0270     }
0271 out:
0272     mutex_unlock(&rslistlock);
0273     return rs;
0274 }
0275
0276 /**
0277  * init_rs_gfp - Create a RS control struct and initialize it
0278  *  @symsize:   the symbol size (number of bits)
0279  *  @gfpoly:    the extended Galois field generator polynomial coefficients,
0280  *      with the 0th coefficient in the low order bit. The polynomial
0281  *      must be primitive;
0282  *  @fcr:   the first consecutive root of the rs code generator polynomial
0283  *      in index form
0284  *  @prim:  primitive element to generate polynomial roots
0285  *  @nroots:    RS code generator polynomial degree (number of roots)
0286  *  @gfp:   Memory allocation flags.
0287  */
0288 struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
0289                    int nroots, gfp_t gfp)
0290 {
0291     return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
0292 }
0293 EXPORT_SYMBOL_GPL(init_rs_gfp);
0294
0295 /**
0296  * init_rs_non_canonical - Allocate rs control struct for fields with
0297  *                         non-canonical representation
0298  *  @symsize:   the symbol size (number of bits)
0299  *  @gffunc:    pointer to function to generate the next field element,
0300  *      or the multiplicative identity element if given 0.  Used
0301  *      instead of gfpoly if gfpoly is 0
0302  *  @fcr:   the first consecutive root of the rs code generator polynomial
0303  *      in index form
0304  *  @prim:  primitive element to generate polynomial roots
0305  *  @nroots:    RS code generator polynomial degree (number of roots)
0306  */
0307 struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
0308                      int fcr, int prim, int nroots)
0309 {
0310     return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
0311                 GFP_KERNEL);
0312 }
0313 EXPORT_SYMBOL_GPL(init_rs_non_canonical);
0314
0315 #ifdef CONFIG_REED_SOLOMON_ENC8
0316 /**
0317  *  encode_rs8 - Calculate the parity for data values (8bit data width)
0318  *  @rsc:   the rs control structure
0319  *  @data:  data field of a given type
0320  *  @len:   data length
0321  *  @par:   parity data, must be initialized by caller (usually all 0)
0322  *  @invmsk:    invert data mask (will be xored on data)
0323  *
0324  *  The parity uses a uint16_t data type to enable
0325  *  symbol size > 8. The calling code must take care of encoding of the
0326  *  syndrome result for storage itself.
0327  */
0328 int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par,
0329            uint16_t invmsk)
0330 {
0331 #include "encode_rs.c"
0332 }
0333 EXPORT_SYMBOL_GPL(encode_rs8);
0334 #endif
0335
0336 #ifdef CONFIG_REED_SOLOMON_DEC8
0337 /**
0338  *  decode_rs8 - Decode codeword (8bit data width)
0339  *  @rsc:   the rs control structure
0340  *  @data:  data field of a given type
0341  *  @par:   received parity data field
0342  *  @len:   data length
0343  *  @s:     syndrome data field, must be in index form
0344  *      (if NULL, syndrome is calculated)
0345  *  @no_eras:   number of erasures
0346  *  @eras_pos:  position of erasures, can be NULL
0347  *  @invmsk:    invert data mask (will be xored on data, not on parity!)
0348  *  @corr:  buffer to store correction bitmask on eras_pos
0349  *
0350  *  The syndrome and parity uses a uint16_t data type to enable
0351  *  symbol size > 8. The calling code must take care of decoding of the
0352  *  syndrome result and the received parity before calling this code.
0353  *
0354  *  Note: The rs_control struct @rsc contains buffers which are used for
0355  *  decoding, so the caller has to ensure that decoder invocations are
0356  *  serialized.
0357  *
0358  *  Returns the number of corrected symbols or -EBADMSG for uncorrectable
0359  *  errors. The count includes errors in the parity.
0360  */
0361 int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
0362            uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
0363            uint16_t *corr)
0364 {
0365 #include "decode_rs.c"
0366 }
0367 EXPORT_SYMBOL_GPL(decode_rs8);
0368 #endif
0369
0370 #ifdef CONFIG_REED_SOLOMON_ENC16
0371 /**
0372  *  encode_rs16 - Calculate the parity for data values (16bit data width)
0373  *  @rsc:   the rs control structure
0374  *  @data:  data field of a given type
0375  *  @len:   data length
0376  *  @par:   parity data, must be initialized by caller (usually all 0)
0377  *  @invmsk:    invert data mask (will be xored on data, not on parity!)
0378  *
0379  *  Each field in the data array contains up to symbol size bits of valid data.
0380  */
0381 int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,
0382     uint16_t invmsk)
0383 {
0384 #include "encode_rs.c"
0385 }
0386 EXPORT_SYMBOL_GPL(encode_rs16);
0387 #endif
0388
0389 #ifdef CONFIG_REED_SOLOMON_DEC16
0390 /**
0391  *  decode_rs16 - Decode codeword (16bit data width)
0392  *  @rsc:   the rs control structure
0393  *  @data:  data field of a given type
0394  *  @par:   received parity data field
0395  *  @len:   data length
0396  *  @s:     syndrome data field, must be in index form
0397  *      (if NULL, syndrome is calculated)
0398  *  @no_eras:   number of erasures
0399  *  @eras_pos:  position of erasures, can be NULL
0400  *  @invmsk:    invert data mask (will be xored on data, not on parity!)
0401  *  @corr:  buffer to store correction bitmask on eras_pos
0402  *
0403  *  Each field in the data array contains up to symbol size bits of valid data.
0404  *
0405  *  Note: The rc_control struct @rsc contains buffers which are used for
0406  *  decoding, so the caller has to ensure that decoder invocations are
0407  *  serialized.
0408  *
0409  *  Returns the number of corrected symbols or -EBADMSG for uncorrectable
0410  *  errors. The count includes errors in the parity.
0411  */
0412 int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
0413         uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
0414         uint16_t *corr)
0415 {
0416 #include "decode_rs.c"
0417 }
0418 EXPORT_SYMBOL_GPL(decode_rs16);
0419 #endif
0420
0421 MODULE_LICENSE("GPL");
0422 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
0423 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
0424