425 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Generic Reed Solomon encoder / decoder library4 *5 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)6 *7 * Reed Solomon code lifted from reed solomon library written by Phil Karn8 * Copyright 2002 Phil Karn, KA9Q9 *10 * Description:11 *12 * The generic Reed Solomon library provides runtime configurable13 * encoding / decoding of RS codes.14 *15 * Each user must call init_rs to get a pointer to a rs_control structure16 * for the given rs parameters. The control struct is unique per instance.17 * It points to a codec which can be shared by multiple control structures.18 * If a codec is newly allocated then the polynomial arrays for fast19 * encoding / decoding are built. This can take some time so make sure not20 * to call this function from a time critical path. Usually a module /21 * driver should initialize the necessary rs_control structure on module /22 * driver init and release it on exit.23 *24 * The encoding puts the calculated syndrome into a given syndrome buffer.25 *26 * The decoding is a two step process. The first step calculates the27 * syndrome over the received (data + syndrome) and calls the second stage,28 * which does the decoding / error correction itself. Many hw encoders29 * provide a syndrome calculation over the received data + syndrome and can30 * call the second stage directly.31 */32#include <linux/errno.h>33#include <linux/kernel.h>34#include <linux/init.h>35#include <linux/module.h>36#include <linux/rslib.h>37#include <linux/slab.h>38#include <linux/mutex.h>39 40enum {41 RS_DECODE_LAMBDA,42 RS_DECODE_SYN,43 RS_DECODE_B,44 RS_DECODE_T,45 RS_DECODE_OMEGA,46 RS_DECODE_ROOT,47 RS_DECODE_REG,48 RS_DECODE_LOC,49 RS_DECODE_NUM_BUFFERS50};51 52/* This list holds all currently allocated rs codec structures */53static LIST_HEAD(codec_list);54/* Protection for the list */55static DEFINE_MUTEX(rslistlock);56 57/**58 * codec_init - Initialize a Reed-Solomon codec59 * @symsize: symbol size, bits (1-8)60 * @gfpoly: Field generator polynomial coefficients61 * @gffunc: Field generator function62 * @fcr: first root of RS code generator polynomial, index form63 * @prim: primitive element to generate polynomial roots64 * @nroots: RS code generator polynomial degree (number of roots)65 * @gfp: GFP_ flags for allocations66 *67 * Allocate a codec structure and the polynom arrays for faster68 * en/decoding. Fill the arrays according to the given parameters.69 */70static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),71 int fcr, int prim, int nroots, gfp_t gfp)72{73 int i, j, sr, root, iprim;74 struct rs_codec *rs;75 76 rs = kzalloc(sizeof(*rs), gfp);77 if (!rs)78 return NULL;79 80 INIT_LIST_HEAD(&rs->list);81 82 rs->mm = symsize;83 rs->nn = (1 << symsize) - 1;84 rs->fcr = fcr;85 rs->prim = prim;86 rs->nroots = nroots;87 rs->gfpoly = gfpoly;88 rs->gffunc = gffunc;89 90 /* Allocate the arrays */91 rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);92 if (rs->alpha_to == NULL)93 goto err;94 95 rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);96 if (rs->index_of == NULL)97 goto err;98 99 rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp);100 if(rs->genpoly == NULL)101 goto err;102 103 /* Generate Galois field lookup tables */104 rs->index_of[0] = rs->nn; /* log(zero) = -inf */105 rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */106 if (gfpoly) {107 sr = 1;108 for (i = 0; i < rs->nn; i++) {109 rs->index_of[sr] = i;110 rs->alpha_to[i] = sr;111 sr <<= 1;112 if (sr & (1 << symsize))113 sr ^= gfpoly;114 sr &= rs->nn;115 }116 } else {117 sr = gffunc(0);118 for (i = 0; i < rs->nn; i++) {119 rs->index_of[sr] = i;120 rs->alpha_to[i] = sr;121 sr = gffunc(sr);122 }123 }124 /* If it's not primitive, exit */125 if(sr != rs->alpha_to[0])126 goto err;127 128 /* Find prim-th root of 1, used in decoding */129 for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);130 /* prim-th root of 1, index form */131 rs->iprim = iprim / prim;132 133 /* Form RS code generator polynomial from its roots */134 rs->genpoly[0] = 1;135 for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {136 rs->genpoly[i + 1] = 1;137 /* Multiply rs->genpoly[] by @**(root + x) */138 for (j = i; j > 0; j--) {139 if (rs->genpoly[j] != 0) {140 rs->genpoly[j] = rs->genpoly[j -1] ^141 rs->alpha_to[rs_modnn(rs,142 rs->index_of[rs->genpoly[j]] + root)];143 } else144 rs->genpoly[j] = rs->genpoly[j - 1];145 }146 /* rs->genpoly[0] can never be zero */147 rs->genpoly[0] =148 rs->alpha_to[rs_modnn(rs,149 rs->index_of[rs->genpoly[0]] + root)];150 }151 /* convert rs->genpoly[] to index form for quicker encoding */152 for (i = 0; i <= nroots; i++)153 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];154 155 rs->users = 1;156 list_add(&rs->list, &codec_list);157 return rs;158 159err:160 kfree(rs->genpoly);161 kfree(rs->index_of);162 kfree(rs->alpha_to);163 kfree(rs);164 return NULL;165}166 167 168/**169 * free_rs - Free the rs control structure170 * @rs: The control structure which is not longer used by the171 * caller172 *173 * Free the control structure. If @rs is the last user of the associated174 * codec, free the codec as well.175 */176void free_rs(struct rs_control *rs)177{178 struct rs_codec *cd;179 180 if (!rs)181 return;182 183 cd = rs->codec;184 mutex_lock(&rslistlock);185 cd->users--;186 if(!cd->users) {187 list_del(&cd->list);188 kfree(cd->alpha_to);189 kfree(cd->index_of);190 kfree(cd->genpoly);191 kfree(cd);192 }193 mutex_unlock(&rslistlock);194 kfree(rs);195}196EXPORT_SYMBOL_GPL(free_rs);197 198/**199 * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one200 * @symsize: the symbol size (number of bits)201 * @gfpoly: the extended Galois field generator polynomial coefficients,202 * with the 0th coefficient in the low order bit. The polynomial203 * must be primitive;204 * @gffunc: pointer to function to generate the next field element,205 * or the multiplicative identity element if given 0. Used206 * instead of gfpoly if gfpoly is 0207 * @fcr: the first consecutive root of the rs code generator polynomial208 * in index form209 * @prim: primitive element to generate polynomial roots210 * @nroots: RS code generator polynomial degree (number of roots)211 * @gfp: GFP_ flags for allocations212 */213static struct rs_control *init_rs_internal(int symsize, int gfpoly,214 int (*gffunc)(int), int fcr,215 int prim, int nroots, gfp_t gfp)216{217 struct list_head *tmp;218 struct rs_control *rs;219 unsigned int bsize;220 221 /* Sanity checks */222 if (symsize < 1)223 return NULL;224 if (fcr < 0 || fcr >= (1<<symsize))225 return NULL;226 if (prim <= 0 || prim >= (1<<symsize))227 return NULL;228 if (nroots < 0 || nroots >= (1<<symsize))229 return NULL;230 231 /*232 * The decoder needs buffers in each control struct instance to233 * avoid variable size or large fixed size allocations on234 * stack. Size the buffers to arrays of [nroots + 1].235 */236 bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);237 rs = kzalloc(sizeof(*rs) + bsize, gfp);238 if (!rs)239 return NULL;240 241 mutex_lock(&rslistlock);242 243 /* Walk through the list and look for a matching entry */244 list_for_each(tmp, &codec_list) {245 struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);246 247 if (symsize != cd->mm)248 continue;249 if (gfpoly != cd->gfpoly)250 continue;251 if (gffunc != cd->gffunc)252 continue;253 if (fcr != cd->fcr)254 continue;255 if (prim != cd->prim)256 continue;257 if (nroots != cd->nroots)258 continue;259 /* We have a matching one already */260 cd->users++;261 rs->codec = cd;262 goto out;263 }264 265 /* Create a new one */266 rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);267 if (!rs->codec) {268 kfree(rs);269 rs = NULL;270 }271out:272 mutex_unlock(&rslistlock);273 return rs;274}275 276/**277 * init_rs_gfp - Create a RS control struct and initialize it278 * @symsize: the symbol size (number of bits)279 * @gfpoly: the extended Galois field generator polynomial coefficients,280 * with the 0th coefficient in the low order bit. The polynomial281 * must be primitive;282 * @fcr: the first consecutive root of the rs code generator polynomial283 * in index form284 * @prim: primitive element to generate polynomial roots285 * @nroots: RS code generator polynomial degree (number of roots)286 * @gfp: Memory allocation flags.287 */288struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,289 int nroots, gfp_t gfp)290{291 return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);292}293EXPORT_SYMBOL_GPL(init_rs_gfp);294 295/**296 * init_rs_non_canonical - Allocate rs control struct for fields with297 * non-canonical representation298 * @symsize: the symbol size (number of bits)299 * @gffunc: pointer to function to generate the next field element,300 * or the multiplicative identity element if given 0. Used301 * instead of gfpoly if gfpoly is 0302 * @fcr: the first consecutive root of the rs code generator polynomial303 * in index form304 * @prim: primitive element to generate polynomial roots305 * @nroots: RS code generator polynomial degree (number of roots)306 */307struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),308 int fcr, int prim, int nroots)309{310 return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,311 GFP_KERNEL);312}313EXPORT_SYMBOL_GPL(init_rs_non_canonical);314 315#ifdef CONFIG_REED_SOLOMON_ENC8316/**317 * encode_rs8 - Calculate the parity for data values (8bit data width)318 * @rsc: the rs control structure319 * @data: data field of a given type320 * @len: data length321 * @par: parity data, must be initialized by caller (usually all 0)322 * @invmsk: invert data mask (will be xored on data)323 *324 * The parity uses a uint16_t data type to enable325 * symbol size > 8. The calling code must take care of encoding of the326 * syndrome result for storage itself.327 */328int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par,329 uint16_t invmsk)330{331#include "encode_rs.c"332}333EXPORT_SYMBOL_GPL(encode_rs8);334#endif335 336#ifdef CONFIG_REED_SOLOMON_DEC8337/**338 * decode_rs8 - Decode codeword (8bit data width)339 * @rsc: the rs control structure340 * @data: data field of a given type341 * @par: received parity data field342 * @len: data length343 * @s: syndrome data field, must be in index form344 * (if NULL, syndrome is calculated)345 * @no_eras: number of erasures346 * @eras_pos: position of erasures, can be NULL347 * @invmsk: invert data mask (will be xored on data, not on parity!)348 * @corr: buffer to store correction bitmask on eras_pos349 *350 * The syndrome and parity uses a uint16_t data type to enable351 * symbol size > 8. The calling code must take care of decoding of the352 * syndrome result and the received parity before calling this code.353 *354 * Note: The rs_control struct @rsc contains buffers which are used for355 * decoding, so the caller has to ensure that decoder invocations are356 * serialized.357 *358 * Returns the number of corrected symbols or -EBADMSG for uncorrectable359 * errors. The count includes errors in the parity.360 */361int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,362 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,363 uint16_t *corr)364{365#include "decode_rs.c"366}367EXPORT_SYMBOL_GPL(decode_rs8);368#endif369 370#ifdef CONFIG_REED_SOLOMON_ENC16371/**372 * encode_rs16 - Calculate the parity for data values (16bit data width)373 * @rsc: the rs control structure374 * @data: data field of a given type375 * @len: data length376 * @par: parity data, must be initialized by caller (usually all 0)377 * @invmsk: invert data mask (will be xored on data, not on parity!)378 *379 * Each field in the data array contains up to symbol size bits of valid data.380 */381int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,382 uint16_t invmsk)383{384#include "encode_rs.c"385}386EXPORT_SYMBOL_GPL(encode_rs16);387#endif388 389#ifdef CONFIG_REED_SOLOMON_DEC16390/**391 * decode_rs16 - Decode codeword (16bit data width)392 * @rsc: the rs control structure393 * @data: data field of a given type394 * @par: received parity data field395 * @len: data length396 * @s: syndrome data field, must be in index form397 * (if NULL, syndrome is calculated)398 * @no_eras: number of erasures399 * @eras_pos: position of erasures, can be NULL400 * @invmsk: invert data mask (will be xored on data, not on parity!)401 * @corr: buffer to store correction bitmask on eras_pos402 *403 * Each field in the data array contains up to symbol size bits of valid data.404 *405 * Note: The rc_control struct @rsc contains buffers which are used for406 * decoding, so the caller has to ensure that decoder invocations are407 * serialized.408 *409 * Returns the number of corrected symbols or -EBADMSG for uncorrectable410 * errors. The count includes errors in the parity.411 */412int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,413 uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,414 uint16_t *corr)415{416#include "decode_rs.c"417}418EXPORT_SYMBOL_GPL(decode_rs16);419#endif420 421MODULE_LICENSE("GPL");422MODULE_DESCRIPTION("Reed Solomon encoder/decoder");423MODULE_AUTHOR("Phil Karn, Thomas Gleixner");424 425