linux/lib/reed_solomon/reed_solomon.c
<<
>>
Prefs
   1/*
   2 * lib/reed_solomon/reed_solomon.c
   3 *
   4 * Overview:
   5 *   Generic Reed Solomon encoder / decoder library
   6 *
   7 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
   8 *
   9 * Reed Solomon code lifted from reed solomon library written by Phil Karn
  10 * Copyright 2002 Phil Karn, KA9Q
  11 *
  12 * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
  13 *
  14 * This program is free software; you can redistribute it and/or modify
  15 * it under the terms of the GNU General Public License version 2 as
  16 * published by the Free Software Foundation.
  17 *
  18 * Description:
  19 *
  20 * The generic Reed Solomon library provides runtime configurable
  21 * encoding / decoding of RS codes.
  22 * Each user must call init_rs to get a pointer to a rs_control
  23 * structure for the given rs parameters. This structure is either
  24 * generated or a already available matching control structure is used.
  25 * If a structure is generated then the polynomial arrays for
  26 * fast encoding / decoding are built. This can take some time so
  27 * make sure not to call this function from a time critical path.
  28 * Usually a module / driver should initialize the necessary
  29 * rs_control structure on module / driver init and release it
  30 * on exit.
  31 * The encoding puts the calculated syndrome into a given syndrome
  32 * buffer.
  33 * The decoding is a two step process. The first step calculates
  34 * the syndrome over the received (data + syndrome) and calls the
  35 * second stage, which does the decoding / error correction itself.
  36 * Many hw encoders provide a syndrome calculation over the received
  37 * data + syndrome and can call the second stage directly.
  38 *
  39 */
  40
  41#include <linux/errno.h>
  42#include <linux/kernel.h>
  43#include <linux/init.h>
  44#include <linux/module.h>
  45#include <linux/rslib.h>
  46#include <linux/slab.h>
  47#include <linux/mutex.h>
  48
  49/* This list holds all currently allocated rs control structures */
  50static LIST_HEAD (rslist);
  51/* Protection for the list */
  52static DEFINE_MUTEX(rslistlock);
  53
  54/**
  55 * rs_init - Initialize a Reed-Solomon codec
  56 * @symsize:    symbol size, bits (1-8)
  57 * @gfpoly:     Field generator polynomial coefficients
  58 * @gffunc:     Field generator function
  59 * @fcr:        first root of RS code generator polynomial, index form
  60 * @prim:       primitive element to generate polynomial roots
  61 * @nroots:     RS code generator polynomial degree (number of roots)
  62 *
  63 * Allocate a control structure and the polynom arrays for faster
  64 * en/decoding. Fill the arrays according to the given parameters.
  65 */
  66static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int),
  67                                  int fcr, int prim, int nroots)
  68{
  69        struct rs_control *rs;
  70        int i, j, sr, root, iprim;
  71
  72        /* Allocate the control structure */
  73        rs = kmalloc(sizeof (struct rs_control), GFP_KERNEL);
  74        if (rs == NULL)
  75                return NULL;
  76
  77        INIT_LIST_HEAD(&rs->list);
  78
  79        rs->mm = symsize;
  80        rs->nn = (1 << symsize) - 1;
  81        rs->fcr = fcr;
  82        rs->prim = prim;
  83        rs->nroots = nroots;
  84        rs->gfpoly = gfpoly;
  85        rs->gffunc = gffunc;
  86
  87        /* Allocate the arrays */
  88        rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
  89        if (rs->alpha_to == NULL)
  90                goto errrs;
  91
  92        rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
  93        if (rs->index_of == NULL)
  94                goto erralp;
  95
  96        rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL);
  97        if(rs->genpoly == NULL)
  98                goto erridx;
  99
 100        /* Generate Galois field lookup tables */
 101        rs->index_of[0] = rs->nn;       /* log(zero) = -inf */
 102        rs->alpha_to[rs->nn] = 0;       /* alpha**-inf = 0 */
 103        if (gfpoly) {
 104                sr = 1;
 105                for (i = 0; i < rs->nn; i++) {
 106                        rs->index_of[sr] = i;
 107                        rs->alpha_to[i] = sr;
 108                        sr <<= 1;
 109                        if (sr & (1 << symsize))
 110                                sr ^= gfpoly;
 111                        sr &= rs->nn;
 112                }
 113        } else {
 114                sr = gffunc(0);
 115                for (i = 0; i < rs->nn; i++) {
 116                        rs->index_of[sr] = i;
 117                        rs->alpha_to[i] = sr;
 118                        sr = gffunc(sr);
 119                }
 120        }
 121        /* If it's not primitive, exit */
 122        if(sr != rs->alpha_to[0])
 123                goto errpol;
 124
 125        /* Find prim-th root of 1, used in decoding */
 126        for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
 127        /* prim-th root of 1, index form */
 128        rs->iprim = iprim / prim;
 129
 130        /* Form RS code generator polynomial from its roots */
 131        rs->genpoly[0] = 1;
 132        for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
 133                rs->genpoly[i + 1] = 1;
 134                /* Multiply rs->genpoly[] by  @**(root + x) */
 135                for (j = i; j > 0; j--) {
 136                        if (rs->genpoly[j] != 0) {
 137                                rs->genpoly[j] = rs->genpoly[j -1] ^
 138                                        rs->alpha_to[rs_modnn(rs,
 139                                        rs->index_of[rs->genpoly[j]] + root)];
 140                        } else
 141                                rs->genpoly[j] = rs->genpoly[j - 1];
 142                }
 143                /* rs->genpoly[0] can never be zero */
 144                rs->genpoly[0] =
 145                        rs->alpha_to[rs_modnn(rs,
 146                                rs->index_of[rs->genpoly[0]] + root)];
 147        }
 148        /* convert rs->genpoly[] to index form for quicker encoding */
 149        for (i = 0; i <= nroots; i++)
 150                rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
 151        return rs;
 152
 153        /* Error exit */
 154errpol:
 155        kfree(rs->genpoly);
 156erridx:
 157        kfree(rs->index_of);
 158erralp:
 159        kfree(rs->alpha_to);
 160errrs:
 161        kfree(rs);
 162        return NULL;
 163}
 164
 165
 166/**
 167 *  free_rs - Free the rs control structure, if it is no longer used
 168 *  @rs:        the control structure which is not longer used by the
 169 *              caller
 170 */
 171void free_rs(struct rs_control *rs)
 172{
 173        mutex_lock(&rslistlock);
 174        rs->users--;
 175        if(!rs->users) {
 176                list_del(&rs->list);
 177                kfree(rs->alpha_to);
 178                kfree(rs->index_of);
 179                kfree(rs->genpoly);
 180                kfree(rs);
 181        }
 182        mutex_unlock(&rslistlock);
 183}
 184
 185/**
 186 * init_rs_internal - Find a matching or allocate a new rs control structure
 187 *  @symsize:   the symbol size (number of bits)
 188 *  @gfpoly:    the extended Galois field generator polynomial coefficients,
 189 *              with the 0th coefficient in the low order bit. The polynomial
 190 *              must be primitive;
 191 *  @gffunc:    pointer to function to generate the next field element,
 192 *              or the multiplicative identity element if given 0.  Used
 193 *              instead of gfpoly if gfpoly is 0
 194 *  @fcr:       the first consecutive root of the rs code generator polynomial
 195 *              in index form
 196 *  @prim:      primitive element to generate polynomial roots
 197 *  @nroots:    RS code generator polynomial degree (number of roots)
 198 */
 199static struct rs_control *init_rs_internal(int symsize, int gfpoly,
 200                                           int (*gffunc)(int), int fcr,
 201                                           int prim, int nroots)
 202{
 203        struct list_head        *tmp;
 204        struct rs_control       *rs;
 205
 206        /* Sanity checks */
 207        if (symsize < 1)
 208                return NULL;
 209        if (fcr < 0 || fcr >= (1<<symsize))
 210                return NULL;
 211        if (prim <= 0 || prim >= (1<<symsize))
 212                return NULL;
 213        if (nroots < 0 || nroots >= (1<<symsize))
 214                return NULL;
 215
 216        mutex_lock(&rslistlock);
 217
 218        /* Walk through the list and look for a matching entry */
 219        list_for_each(tmp, &rslist) {
 220                rs = list_entry(tmp, struct rs_control, list);
 221                if (symsize != rs->mm)
 222                        continue;
 223                if (gfpoly != rs->gfpoly)
 224                        continue;
 225                if (gffunc != rs->gffunc)
 226                        continue;
 227                if (fcr != rs->fcr)
 228                        continue;
 229                if (prim != rs->prim)
 230                        continue;
 231                if (nroots != rs->nroots)
 232                        continue;
 233                /* We have a matching one already */
 234                rs->users++;
 235                goto out;
 236        }
 237
 238        /* Create a new one */
 239        rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots);
 240        if (rs) {
 241                rs->users = 1;
 242                list_add(&rs->list, &rslist);
 243        }
 244out:
 245        mutex_unlock(&rslistlock);
 246        return rs;
 247}
 248
 249/**
 250 * init_rs - Find a matching or allocate a new rs control structure
 251 *  @symsize:   the symbol size (number of bits)
 252 *  @gfpoly:    the extended Galois field generator polynomial coefficients,
 253 *              with the 0th coefficient in the low order bit. The polynomial
 254 *              must be primitive;
 255 *  @fcr:       the first consecutive root of the rs code generator polynomial
 256 *              in index form
 257 *  @prim:      primitive element to generate polynomial roots
 258 *  @nroots:    RS code generator polynomial degree (number of roots)
 259 */
 260struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
 261                           int nroots)
 262{
 263        return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots);
 264}
 265
 266/**
 267 * init_rs_non_canonical - Find a matching or allocate a new rs control
 268 *                         structure, for fields with non-canonical
 269 *                         representation
 270 *  @symsize:   the symbol size (number of bits)
 271 *  @gffunc:    pointer to function to generate the next field element,
 272 *              or the multiplicative identity element if given 0.  Used
 273 *              instead of gfpoly if gfpoly is 0
 274 *  @fcr:       the first consecutive root of the rs code generator polynomial
 275 *              in index form
 276 *  @prim:      primitive element to generate polynomial roots
 277 *  @nroots:    RS code generator polynomial degree (number of roots)
 278 */
 279struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
 280                                         int fcr, int prim, int nroots)
 281{
 282        return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots);
 283}
 284
 285#ifdef CONFIG_REED_SOLOMON_ENC8
 286/**
 287 *  encode_rs8 - Calculate the parity for data values (8bit data width)
 288 *  @rs:        the rs control structure
 289 *  @data:      data field of a given type
 290 *  @len:       data length
 291 *  @par:       parity data, must be initialized by caller (usually all 0)
 292 *  @invmsk:    invert data mask (will be xored on data)
 293 *
 294 *  The parity uses a uint16_t data type to enable
 295 *  symbol size > 8. The calling code must take care of encoding of the
 296 *  syndrome result for storage itself.
 297 */
 298int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,
 299               uint16_t invmsk)
 300{
 301#include "encode_rs.c"
 302}
 303EXPORT_SYMBOL_GPL(encode_rs8);
 304#endif
 305
 306#ifdef CONFIG_REED_SOLOMON_DEC8
 307/**
 308 *  decode_rs8 - Decode codeword (8bit data width)
 309 *  @rs:        the rs control structure
 310 *  @data:      data field of a given type
 311 *  @par:       received parity data field
 312 *  @len:       data length
 313 *  @s:         syndrome data field (if NULL, syndrome is calculated)
 314 *  @no_eras:   number of erasures
 315 *  @eras_pos:  position of erasures, can be NULL
 316 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 317 *  @corr:      buffer to store correction bitmask on eras_pos
 318 *
 319 *  The syndrome and parity uses a uint16_t data type to enable
 320 *  symbol size > 8. The calling code must take care of decoding of the
 321 *  syndrome result and the received parity before calling this code.
 322 *  Returns the number of corrected bits or -EBADMSG for uncorrectable errors.
 323 */
 324int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len,
 325               uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
 326               uint16_t *corr)
 327{
 328#include "decode_rs.c"
 329}
 330EXPORT_SYMBOL_GPL(decode_rs8);
 331#endif
 332
 333#ifdef CONFIG_REED_SOLOMON_ENC16
 334/**
 335 *  encode_rs16 - Calculate the parity for data values (16bit data width)
 336 *  @rs:        the rs control structure
 337 *  @data:      data field of a given type
 338 *  @len:       data length
 339 *  @par:       parity data, must be initialized by caller (usually all 0)
 340 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 341 *
 342 *  Each field in the data array contains up to symbol size bits of valid data.
 343 */
 344int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,
 345        uint16_t invmsk)
 346{
 347#include "encode_rs.c"
 348}
 349EXPORT_SYMBOL_GPL(encode_rs16);
 350#endif
 351
 352#ifdef CONFIG_REED_SOLOMON_DEC16
 353/**
 354 *  decode_rs16 - Decode codeword (16bit data width)
 355 *  @rs:        the rs control structure
 356 *  @data:      data field of a given type
 357 *  @par:       received parity data field
 358 *  @len:       data length
 359 *  @s:         syndrome data field (if NULL, syndrome is calculated)
 360 *  @no_eras:   number of erasures
 361 *  @eras_pos:  position of erasures, can be NULL
 362 *  @invmsk:    invert data mask (will be xored on data, not on parity!)
 363 *  @corr:      buffer to store correction bitmask on eras_pos
 364 *
 365 *  Each field in the data array contains up to symbol size bits of valid data.
 366 *  Returns the number of corrected bits or -EBADMSG for uncorrectable errors.
 367 */
 368int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len,
 369                uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
 370                uint16_t *corr)
 371{
 372#include "decode_rs.c"
 373}
 374EXPORT_SYMBOL_GPL(decode_rs16);
 375#endif
 376
 377EXPORT_SYMBOL_GPL(init_rs);
 378EXPORT_SYMBOL_GPL(init_rs_non_canonical);
 379EXPORT_SYMBOL_GPL(free_rs);
 380
 381MODULE_LICENSE("GPL");
 382MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
 383MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
 384
 385
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.