linux/lib/reed_solomon/reed_solomon.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Generic Reed Solomon encoder / decoder library
   4 *
   5 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
   6 *
   7 * Reed Solomon code lifted from reed solomon library written by Phil Karn
   8 * Copyright 2002 Phil Karn, KA9Q
   9 *
  10 * Description:
  11 *
  12 * The generic Reed Solomon library provides runtime configurable
  13 * encoding / decoding of RS codes.
  14 *
  15 * Each user must call init_rs to get a pointer to a rs_control structure
  16 * 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 fast
  19 * encoding / decoding are built. This can take some time so make sure not
  20 * 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 the
  27 * syndrome over the received (data + syndrome) and calls the second stage,
  28 * which does the decoding / error correction itself.  Many hw encoders
  29 * provide a syndrome calculation over the received data + syndrome and can
  30 * 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_BUFFERS
  50};
  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 codec
  59 * @symsize:    symbol size, bits (1-8)
  60 * @gfpoly:     Field generator polynomial coefficients
  61 * @gffunc:     Field generator function
  62 * @fcr:        first root of RS code generator polynomial, index form
  63 * @prim:       primitive element to generate polynomial roots
  64 * @nroots:     RS code generator polynomial degree (number of roots)
  65 * @gfp:        GFP_ flags for allocations
  66 *
  67 * Allocate a codec structure and the polynom arrays for faster
  68 * 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                        } else
 144                                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 structure
 170 *  @rs:        The control structure which is not longer used by the
 171 *              caller
 172 *
 173 * Free the control structure. If @rs is the last user of the associated
 174 * 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 one
 200 *  @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 polynomial
 203 *              must be primitive;
 204 *  @gffunc:    pointer to function to generate the next field element,
 205 *              or the multiplicative identity element if given 0.  Used
 206 *              instead of gfpoly if gfpoly is 0
 207 *  @fcr:       the first consecutive root of the rs code generator polynomial
 208 *              in index form
 209 *  @prim:      primitive element to generate polynomial roots
 210 *  @nroots:    RS code generator polynomial degree (number of roots)
 211 *  @gfp:       GFP_ flags for allocations
 212 */
 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 to
 233         * avoid variable size or large fixed size allocations on
 234         * 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 it
 278 *  @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 polynomial
 281 *              must be primitive;
 282 *  @fcr:       the first consecutive root of the rs code generator polynomial
 283 *              in index form
 284 *  @prim:      primitive element to generate polynomial roots
 285 *  @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 with
 297 *                         non-canonical representation
 298 *  @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.  Used
 301 *              instead of gfpoly if gfpoly is 0
 302 *  @fcr:       the first consecutive root of the rs code generator polynomial
 303 *              in index form
 304 *  @prim:      primitive element to generate polynomial roots
 305 *  @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_ENC8
 316/**
 317 *  encode_rs8 - Calculate the parity for data values (8bit data width)
 318 *  @rsc:       the rs control structure
 319 *  @data:      data field of a given type
 320 *  @len:       data length
 321 *  @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 enable
 325 *  symbol size > 8. The calling code must take care of encoding of the
 326 *  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#endif
 335
 336#ifdef CONFIG_REED_SOLOMON_DEC8
 337/**
 338 *  decode_rs8 - Decode codeword (8bit data width)
 339 *  @rsc:       the rs control structure
 340 *  @data:      data field of a given type
 341 *  @par:       received parity data field
 342 *  @len:       data length
 343 *  @s:         syndrome data field (if NULL, syndrome is calculated)
 344 *  @no_eras:   number of erasures
 345 *  @eras_pos:  position of erasures, can be NULL
 346 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 347 *  @corr:      buffer to store correction bitmask on eras_pos
 348 *
 349 *  The syndrome and parity uses a uint16_t data type to enable
 350 *  symbol size > 8. The calling code must take care of decoding of the
 351 *  syndrome result and the received parity before calling this code.
 352 *
 353 *  Note: The rs_control struct @rsc contains buffers which are used for
 354 *  decoding, so the caller has to ensure that decoder invocations are
 355 *  serialized.
 356 *
 357 *  Returns the number of corrected bits or -EBADMSG for uncorrectable errors.
 358 */
 359int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
 360               uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
 361               uint16_t *corr)
 362{
 363#include "decode_rs.c"
 364}
 365EXPORT_SYMBOL_GPL(decode_rs8);
 366#endif
 367
 368#ifdef CONFIG_REED_SOLOMON_ENC16
 369/**
 370 *  encode_rs16 - Calculate the parity for data values (16bit data width)
 371 *  @rsc:       the rs control structure
 372 *  @data:      data field of a given type
 373 *  @len:       data length
 374 *  @par:       parity data, must be initialized by caller (usually all 0)
 375 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 376 *
 377 *  Each field in the data array contains up to symbol size bits of valid data.
 378 */
 379int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,
 380        uint16_t invmsk)
 381{
 382#include "encode_rs.c"
 383}
 384EXPORT_SYMBOL_GPL(encode_rs16);
 385#endif
 386
 387#ifdef CONFIG_REED_SOLOMON_DEC16
 388/**
 389 *  decode_rs16 - Decode codeword (16bit data width)
 390 *  @rsc:       the rs control structure
 391 *  @data:      data field of a given type
 392 *  @par:       received parity data field
 393 *  @len:       data length
 394 *  @s:         syndrome data field (if NULL, syndrome is calculated)
 395 *  @no_eras:   number of erasures
 396 *  @eras_pos:  position of erasures, can be NULL
 397 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 398 *  @corr:      buffer to store correction bitmask on eras_pos
 399 *
 400 *  Each field in the data array contains up to symbol size bits of valid data.
 401 *
 402 *  Note: The rc_control struct @rsc contains buffers which are used for
 403 *  decoding, so the caller has to ensure that decoder invocations are
 404 *  serialized.
 405 *
 406 *  Returns the number of corrected bits or -EBADMSG for uncorrectable errors.
 407 */
 408int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
 409                uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
 410                uint16_t *corr)
 411{
 412#include "decode_rs.c"
 413}
 414EXPORT_SYMBOL_GPL(decode_rs16);
 415#endif
 416
 417MODULE_LICENSE("GPL");
 418MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
 419MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
 420
 421