diff options
author | Jeff Garzik <jgarzik@pobox.com> | 2005-11-07 22:51:47 -0500 |
---|---|---|
committer | Jeff Garzik <jgarzik@pobox.com> | 2005-11-07 22:51:47 -0500 |
commit | 6b995751c2e851d2bc9c277b5884d0adb519e31d (patch) | |
tree | 7a15b41b5d8ce612915584a0773c670d5c0ab5b8 /lib/reed_solomon/reed_solomon.c | |
parent | 6c2f4267833f453156f8f439cc32eb4c92f357b4 (diff) | |
parent | d27ba47e7e8c466c18983a1779d611f82d6a354f (diff) |
Merge branch 'master'
Diffstat (limited to 'lib/reed_solomon/reed_solomon.c')
-rw-r--r-- | lib/reed_solomon/reed_solomon.c | 64 |
1 files changed, 32 insertions, 32 deletions
diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c index 6604e3b1940c..f5fef948a415 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c | |||
@@ -1,22 +1,22 @@ | |||
1 | /* | 1 | /* |
2 | * lib/reed_solomon/rslib.c | 2 | * lib/reed_solomon/rslib.c |
3 | * | 3 | * |
4 | * Overview: | 4 | * Overview: |
5 | * Generic Reed Solomon encoder / decoder library | 5 | * Generic Reed Solomon encoder / decoder library |
6 | * | 6 | * |
7 | * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de) | 7 | * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de) |
8 | * | 8 | * |
9 | * Reed Solomon code lifted from reed solomon library written by Phil Karn | 9 | * Reed Solomon code lifted from reed solomon library written by Phil Karn |
10 | * Copyright 2002 Phil Karn, KA9Q | 10 | * Copyright 2002 Phil Karn, KA9Q |
11 | * | 11 | * |
12 | * $Id: rslib.c,v 1.5 2004/10/22 15:41:47 gleixner Exp $ | 12 | * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $ |
13 | * | 13 | * |
14 | * This program is free software; you can redistribute it and/or modify | 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 | 15 | * it under the terms of the GNU General Public License version 2 as |
16 | * published by the Free Software Foundation. | 16 | * published by the Free Software Foundation. |
17 | * | 17 | * |
18 | * Description: | 18 | * Description: |
19 | * | 19 | * |
20 | * The generic Reed Solomon library provides runtime configurable | 20 | * The generic Reed Solomon library provides runtime configurable |
21 | * encoding / decoding of RS codes. | 21 | * encoding / decoding of RS codes. |
22 | * Each user must call init_rs to get a pointer to a rs_control | 22 | * Each user must call init_rs to get a pointer to a rs_control |
@@ -25,11 +25,11 @@ | |||
25 | * If a structure is generated then the polynomial arrays for | 25 | * If a structure is generated then the polynomial arrays for |
26 | * fast encoding / decoding are built. This can take some time so | 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. | 27 | * make sure not to call this function from a time critical path. |
28 | * Usually a module / driver should initialize the necessary | 28 | * Usually a module / driver should initialize the necessary |
29 | * rs_control structure on module / driver init and release it | 29 | * rs_control structure on module / driver init and release it |
30 | * on exit. | 30 | * on exit. |
31 | * The encoding puts the calculated syndrome into a given syndrome | 31 | * The encoding puts the calculated syndrome into a given syndrome |
32 | * buffer. | 32 | * buffer. |
33 | * The decoding is a two step process. The first step calculates | 33 | * The decoding is a two step process. The first step calculates |
34 | * the syndrome over the received (data + syndrome) and calls the | 34 | * the syndrome over the received (data + syndrome) and calls the |
35 | * second stage, which does the decoding / error correction itself. | 35 | * second stage, which does the decoding / error correction itself. |
@@ -51,7 +51,7 @@ static LIST_HEAD (rslist); | |||
51 | /* Protection for the list */ | 51 | /* Protection for the list */ |
52 | static DECLARE_MUTEX(rslistlock); | 52 | static DECLARE_MUTEX(rslistlock); |
53 | 53 | ||
54 | /** | 54 | /** |
55 | * rs_init - Initialize a Reed-Solomon codec | 55 | * rs_init - Initialize a Reed-Solomon codec |
56 | * | 56 | * |
57 | * @symsize: symbol size, bits (1-8) | 57 | * @symsize: symbol size, bits (1-8) |
@@ -63,7 +63,7 @@ static DECLARE_MUTEX(rslistlock); | |||
63 | * Allocate a control structure and the polynom arrays for faster | 63 | * Allocate a control structure and the polynom arrays for faster |
64 | * en/decoding. Fill the arrays according to the given parameters | 64 | * en/decoding. Fill the arrays according to the given parameters |
65 | */ | 65 | */ |
66 | static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, | 66 | static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, |
67 | int prim, int nroots) | 67 | int prim, int nroots) |
68 | { | 68 | { |
69 | struct rs_control *rs; | 69 | struct rs_control *rs; |
@@ -124,15 +124,15 @@ static struct rs_control *rs_init(int symsize, int gfpoly, int fcr, | |||
124 | /* Multiply rs->genpoly[] by @**(root + x) */ | 124 | /* Multiply rs->genpoly[] by @**(root + x) */ |
125 | for (j = i; j > 0; j--) { | 125 | for (j = i; j > 0; j--) { |
126 | if (rs->genpoly[j] != 0) { | 126 | if (rs->genpoly[j] != 0) { |
127 | rs->genpoly[j] = rs->genpoly[j -1] ^ | 127 | rs->genpoly[j] = rs->genpoly[j -1] ^ |
128 | rs->alpha_to[rs_modnn(rs, | 128 | rs->alpha_to[rs_modnn(rs, |
129 | rs->index_of[rs->genpoly[j]] + root)]; | 129 | rs->index_of[rs->genpoly[j]] + root)]; |
130 | } else | 130 | } else |
131 | rs->genpoly[j] = rs->genpoly[j - 1]; | 131 | rs->genpoly[j] = rs->genpoly[j - 1]; |
132 | } | 132 | } |
133 | /* rs->genpoly[0] can never be zero */ | 133 | /* rs->genpoly[0] can never be zero */ |
134 | rs->genpoly[0] = | 134 | rs->genpoly[0] = |
135 | rs->alpha_to[rs_modnn(rs, | 135 | rs->alpha_to[rs_modnn(rs, |
136 | rs->index_of[rs->genpoly[0]] + root)]; | 136 | rs->index_of[rs->genpoly[0]] + root)]; |
137 | } | 137 | } |
138 | /* convert rs->genpoly[] to index form for quicker encoding */ | 138 | /* convert rs->genpoly[] to index form for quicker encoding */ |
@@ -153,7 +153,7 @@ errrs: | |||
153 | } | 153 | } |
154 | 154 | ||
155 | 155 | ||
156 | /** | 156 | /** |
157 | * free_rs - Free the rs control structure, if its not longer used | 157 | * free_rs - Free the rs control structure, if its not longer used |
158 | * | 158 | * |
159 | * @rs: the control structure which is not longer used by the | 159 | * @rs: the control structure which is not longer used by the |
@@ -173,19 +173,19 @@ void free_rs(struct rs_control *rs) | |||
173 | up(&rslistlock); | 173 | up(&rslistlock); |
174 | } | 174 | } |
175 | 175 | ||
176 | /** | 176 | /** |
177 | * init_rs - Find a matching or allocate a new rs control structure | 177 | * init_rs - Find a matching or allocate a new rs control structure |
178 | * | 178 | * |
179 | * @symsize: the symbol size (number of bits) | 179 | * @symsize: the symbol size (number of bits) |
180 | * @gfpoly: the extended Galois field generator polynomial coefficients, | 180 | * @gfpoly: the extended Galois field generator polynomial coefficients, |
181 | * with the 0th coefficient in the low order bit. The polynomial | 181 | * with the 0th coefficient in the low order bit. The polynomial |
182 | * must be primitive; | 182 | * must be primitive; |
183 | * @fcr: the first consecutive root of the rs code generator polynomial | 183 | * @fcr: the first consecutive root of the rs code generator polynomial |
184 | * in index form | 184 | * in index form |
185 | * @prim: primitive element to generate polynomial roots | 185 | * @prim: primitive element to generate polynomial roots |
186 | * @nroots: RS code generator polynomial degree (number of roots) | 186 | * @nroots: RS code generator polynomial degree (number of roots) |
187 | */ | 187 | */ |
188 | struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, | 188 | struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, |
189 | int nroots) | 189 | int nroots) |
190 | { | 190 | { |
191 | struct list_head *tmp; | 191 | struct list_head *tmp; |
@@ -198,9 +198,9 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, | |||
198 | return NULL; | 198 | return NULL; |
199 | if (prim <= 0 || prim >= (1<<symsize)) | 199 | if (prim <= 0 || prim >= (1<<symsize)) |
200 | return NULL; | 200 | return NULL; |
201 | if (nroots < 0 || nroots >= (1<<symsize) || nroots > 8) | 201 | if (nroots < 0 || nroots >= (1<<symsize)) |
202 | return NULL; | 202 | return NULL; |
203 | 203 | ||
204 | down(&rslistlock); | 204 | down(&rslistlock); |
205 | 205 | ||
206 | /* Walk through the list and look for a matching entry */ | 206 | /* Walk through the list and look for a matching entry */ |
@@ -211,9 +211,9 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, | |||
211 | if (gfpoly != rs->gfpoly) | 211 | if (gfpoly != rs->gfpoly) |
212 | continue; | 212 | continue; |
213 | if (fcr != rs->fcr) | 213 | if (fcr != rs->fcr) |
214 | continue; | 214 | continue; |
215 | if (prim != rs->prim) | 215 | if (prim != rs->prim) |
216 | continue; | 216 | continue; |
217 | if (nroots != rs->nroots) | 217 | if (nroots != rs->nroots) |
218 | continue; | 218 | continue; |
219 | /* We have a matching one already */ | 219 | /* We have a matching one already */ |
@@ -227,18 +227,18 @@ struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim, | |||
227 | rs->users = 1; | 227 | rs->users = 1; |
228 | list_add(&rs->list, &rslist); | 228 | list_add(&rs->list, &rslist); |
229 | } | 229 | } |
230 | out: | 230 | out: |
231 | up(&rslistlock); | 231 | up(&rslistlock); |
232 | return rs; | 232 | return rs; |
233 | } | 233 | } |
234 | 234 | ||
235 | #ifdef CONFIG_REED_SOLOMON_ENC8 | 235 | #ifdef CONFIG_REED_SOLOMON_ENC8 |
236 | /** | 236 | /** |
237 | * encode_rs8 - Calculate the parity for data values (8bit data width) | 237 | * encode_rs8 - Calculate the parity for data values (8bit data width) |
238 | * | 238 | * |
239 | * @rs: the rs control structure | 239 | * @rs: the rs control structure |
240 | * @data: data field of a given type | 240 | * @data: data field of a given type |
241 | * @len: data length | 241 | * @len: data length |
242 | * @par: parity data, must be initialized by caller (usually all 0) | 242 | * @par: parity data, must be initialized by caller (usually all 0) |
243 | * @invmsk: invert data mask (will be xored on data) | 243 | * @invmsk: invert data mask (will be xored on data) |
244 | * | 244 | * |
@@ -246,7 +246,7 @@ out: | |||
246 | * symbol size > 8. The calling code must take care of encoding of the | 246 | * symbol size > 8. The calling code must take care of encoding of the |
247 | * syndrome result for storage itself. | 247 | * syndrome result for storage itself. |
248 | */ | 248 | */ |
249 | int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par, | 249 | int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par, |
250 | uint16_t invmsk) | 250 | uint16_t invmsk) |
251 | { | 251 | { |
252 | #include "encode_rs.c" | 252 | #include "encode_rs.c" |
@@ -255,7 +255,7 @@ EXPORT_SYMBOL_GPL(encode_rs8); | |||
255 | #endif | 255 | #endif |
256 | 256 | ||
257 | #ifdef CONFIG_REED_SOLOMON_DEC8 | 257 | #ifdef CONFIG_REED_SOLOMON_DEC8 |
258 | /** | 258 | /** |
259 | * decode_rs8 - Decode codeword (8bit data width) | 259 | * decode_rs8 - Decode codeword (8bit data width) |
260 | * | 260 | * |
261 | * @rs: the rs control structure | 261 | * @rs: the rs control structure |
@@ -273,7 +273,7 @@ EXPORT_SYMBOL_GPL(encode_rs8); | |||
273 | * syndrome result and the received parity before calling this code. | 273 | * syndrome result and the received parity before calling this code. |
274 | */ | 274 | */ |
275 | int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len, | 275 | int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len, |
276 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, | 276 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
277 | uint16_t *corr) | 277 | uint16_t *corr) |
278 | { | 278 | { |
279 | #include "decode_rs.c" | 279 | #include "decode_rs.c" |
@@ -287,13 +287,13 @@ EXPORT_SYMBOL_GPL(decode_rs8); | |||
287 | * | 287 | * |
288 | * @rs: the rs control structure | 288 | * @rs: the rs control structure |
289 | * @data: data field of a given type | 289 | * @data: data field of a given type |
290 | * @len: data length | 290 | * @len: data length |
291 | * @par: parity data, must be initialized by caller (usually all 0) | 291 | * @par: parity data, must be initialized by caller (usually all 0) |
292 | * @invmsk: invert data mask (will be xored on data, not on parity!) | 292 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
293 | * | 293 | * |
294 | * Each field in the data array contains up to symbol size bits of valid data. | 294 | * Each field in the data array contains up to symbol size bits of valid data. |
295 | */ | 295 | */ |
296 | int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par, | 296 | int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par, |
297 | uint16_t invmsk) | 297 | uint16_t invmsk) |
298 | { | 298 | { |
299 | #include "encode_rs.c" | 299 | #include "encode_rs.c" |
@@ -302,7 +302,7 @@ EXPORT_SYMBOL_GPL(encode_rs16); | |||
302 | #endif | 302 | #endif |
303 | 303 | ||
304 | #ifdef CONFIG_REED_SOLOMON_DEC16 | 304 | #ifdef CONFIG_REED_SOLOMON_DEC16 |
305 | /** | 305 | /** |
306 | * decode_rs16 - Decode codeword (16bit data width) | 306 | * decode_rs16 - Decode codeword (16bit data width) |
307 | * | 307 | * |
308 | * @rs: the rs control structure | 308 | * @rs: the rs control structure |
@@ -312,13 +312,13 @@ EXPORT_SYMBOL_GPL(encode_rs16); | |||
312 | * @s: syndrome data field (if NULL, syndrome is calculated) | 312 | * @s: syndrome data field (if NULL, syndrome is calculated) |
313 | * @no_eras: number of erasures | 313 | * @no_eras: number of erasures |
314 | * @eras_pos: position of erasures, can be NULL | 314 | * @eras_pos: position of erasures, can be NULL |
315 | * @invmsk: invert data mask (will be xored on data, not on parity!) | 315 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
316 | * @corr: buffer to store correction bitmask on eras_pos | 316 | * @corr: buffer to store correction bitmask on eras_pos |
317 | * | 317 | * |
318 | * Each field in the data array contains up to symbol size bits of valid data. | 318 | * Each field in the data array contains up to symbol size bits of valid data. |
319 | */ | 319 | */ |
320 | int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, | 320 | int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, |
321 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, | 321 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
322 | uint16_t *corr) | 322 | uint16_t *corr) |
323 | { | 323 | { |
324 | #include "decode_rs.c" | 324 | #include "decode_rs.c" |