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