[LIB] reed_solomon: Clean up trailing white spaces
[linux-2.6.git] / lib / reed_solomon / reed_solomon.c
1 /*
2  * lib/reed_solomon/rslib.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 <asm/semaphore.h>
48
49 /* This list holds all currently allocated rs control structures */
50 static LIST_HEAD (rslist);
51 /* Protection for the list */
52 static DECLARE_MUTEX(rslistlock);
53
54 /**
55  * rs_init - Initialize a Reed-Solomon codec
56  *
57  * @symsize:    symbol size, bits (1-8)
58  * @gfpoly:     Field generator polynomial coefficients
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  */
66 static struct rs_control *rs_init(int symsize, int gfpoly, int fcr,
67                                    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
86         /* Allocate the arrays */
87         rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
88         if (rs->alpha_to == NULL)
89                 goto errrs;
90
91         rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), GFP_KERNEL);
92         if (rs->index_of == NULL)
93                 goto erralp;
94
95         rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), GFP_KERNEL);
96         if(rs->genpoly == NULL)
97                 goto erridx;
98
99         /* Generate Galois field lookup tables */
100         rs->index_of[0] = rs->nn;       /* log(zero) = -inf */
101         rs->alpha_to[rs->nn] = 0;       /* alpha**-inf = 0 */
102         sr = 1;
103         for (i = 0; i < rs->nn; i++) {
104                 rs->index_of[sr] = i;
105                 rs->alpha_to[i] = sr;
106                 sr <<= 1;
107                 if (sr & (1 << symsize))
108                         sr ^= gfpoly;
109                 sr &= rs->nn;
110         }
111         /* If it's not primitive, exit */
112         if(sr != 1)
113                 goto errpol;
114
115         /* Find prim-th root of 1, used in decoding */
116         for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
117         /* prim-th root of 1, index form */
118         rs->iprim = iprim / prim;
119
120         /* Form RS code generator polynomial from its roots */
121         rs->genpoly[0] = 1;
122         for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
123                 rs->genpoly[i + 1] = 1;
124                 /* Multiply rs->genpoly[] by  @**(root + x) */
125                 for (j = i; j > 0; j--) {
126                         if (rs->genpoly[j] != 0) {
127                                 rs->genpoly[j] = rs->genpoly[j -1] ^
128                                         rs->alpha_to[rs_modnn(rs,
129                                         rs->index_of[rs->genpoly[j]] + root)];
130                         } else
131                                 rs->genpoly[j] = rs->genpoly[j - 1];
132                 }
133                 /* rs->genpoly[0] can never be zero */
134                 rs->genpoly[0] =
135                         rs->alpha_to[rs_modnn(rs,
136                                 rs->index_of[rs->genpoly[0]] + root)];
137         }
138         /* convert rs->genpoly[] to index form for quicker encoding */
139         for (i = 0; i <= nroots; i++)
140                 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
141         return rs;
142
143         /* Error exit */
144 errpol:
145         kfree(rs->genpoly);
146 erridx:
147         kfree(rs->index_of);
148 erralp:
149         kfree(rs->alpha_to);
150 errrs:
151         kfree(rs);
152         return NULL;
153 }
154
155
156 /**
157  *  free_rs - Free the rs control structure, if its not longer used
158  *
159  *  @rs:        the control structure which is not longer used by the
160  *              caller
161  */
162 void free_rs(struct rs_control *rs)
163 {
164         down(&rslistlock);
165         rs->users--;
166         if(!rs->users) {
167                 list_del(&rs->list);
168                 kfree(rs->alpha_to);
169                 kfree(rs->index_of);
170                 kfree(rs->genpoly);
171                 kfree(rs);
172         }
173         up(&rslistlock);
174 }
175
176 /**
177  * init_rs - Find a matching or allocate a new rs control structure
178  *
179  *  @symsize:   the symbol size (number of bits)
180  *  @gfpoly:    the extended Galois field generator polynomial coefficients,
181  *              with the 0th coefficient in the low order bit. The polynomial
182  *              must be primitive;
183  *  @fcr:       the first consecutive root of the rs code generator polynomial
184  *              in index form
185  *  @prim:      primitive element to generate polynomial roots
186  *  @nroots:    RS code generator polynomial degree (number of roots)
187  */
188 struct rs_control *init_rs(int symsize, int gfpoly, int fcr, int prim,
189                            int nroots)
190 {
191         struct list_head        *tmp;
192         struct rs_control       *rs;
193
194         /* Sanity checks */
195         if (symsize < 1)
196                 return NULL;
197         if (fcr < 0 || fcr >= (1<<symsize))
198                 return NULL;
199         if (prim <= 0 || prim >= (1<<symsize))
200                 return NULL;
201         if (nroots < 0 || nroots >= (1<<symsize))
202                 return NULL;
203
204         down(&rslistlock);
205
206         /* Walk through the list and look for a matching entry */
207         list_for_each(tmp, &rslist) {
208                 rs = list_entry(tmp, struct rs_control, list);
209                 if (symsize != rs->mm)
210                         continue;
211                 if (gfpoly != rs->gfpoly)
212                         continue;
213                 if (fcr != rs->fcr)
214                         continue;
215                 if (prim != rs->prim)
216                         continue;
217                 if (nroots != rs->nroots)
218                         continue;
219                 /* We have a matching one already */
220                 rs->users++;
221                 goto out;
222         }
223
224         /* Create a new one */
225         rs = rs_init(symsize, gfpoly, fcr, prim, nroots);
226         if (rs) {
227                 rs->users = 1;
228                 list_add(&rs->list, &rslist);
229         }
230 out:
231         up(&rslistlock);
232         return rs;
233 }
234
235 #ifdef CONFIG_REED_SOLOMON_ENC8
236 /**
237  *  encode_rs8 - Calculate the parity for data values (8bit data width)
238  *
239  *  @rs:        the rs control structure
240  *  @data:      data field of a given type
241  *  @len:       data length
242  *  @par:       parity data, must be initialized by caller (usually all 0)
243  *  @invmsk:    invert data mask (will be xored on data)
244  *
245  *  The parity uses a uint16_t data type to enable
246  *  symbol size > 8. The calling code must take care of encoding of the
247  *  syndrome result for storage itself.
248  */
249 int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,
250                uint16_t invmsk)
251 {
252 #include "encode_rs.c"
253 }
254 EXPORT_SYMBOL_GPL(encode_rs8);
255 #endif
256
257 #ifdef CONFIG_REED_SOLOMON_DEC8
258 /**
259  *  decode_rs8 - Decode codeword (8bit data width)
260  *
261  *  @rs:        the rs control structure
262  *  @data:      data field of a given type
263  *  @par:       received parity data field
264  *  @len:       data length
265  *  @s:         syndrome data field (if NULL, syndrome is calculated)
266  *  @no_eras:   number of erasures
267  *  @eras_pos:  position of erasures, can be NULL
268  *  @invmsk:    invert data mask (will be xored on data, not on parity!)
269  *  @corr:      buffer to store correction bitmask on eras_pos
270  *
271  *  The syndrome and parity uses a uint16_t data type to enable
272  *  symbol size > 8. The calling code must take care of decoding of the
273  *  syndrome result and the received parity before calling this code.
274  */
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,
277                uint16_t *corr)
278 {
279 #include "decode_rs.c"
280 }
281 EXPORT_SYMBOL_GPL(decode_rs8);
282 #endif
283
284 #ifdef CONFIG_REED_SOLOMON_ENC16
285 /**
286  *  encode_rs16 - Calculate the parity for data values (16bit data width)
287  *
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, not on parity!)
293  *
294  *  Each field in the data array contains up to symbol size bits of valid data.
295  */
296 int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,
297         uint16_t invmsk)
298 {
299 #include "encode_rs.c"
300 }
301 EXPORT_SYMBOL_GPL(encode_rs16);
302 #endif
303
304 #ifdef CONFIG_REED_SOLOMON_DEC16
305 /**
306  *  decode_rs16 - Decode codeword (16bit data width)
307  *
308  *  @rs:        the rs control structure
309  *  @data:      data field of a given type
310  *  @par:       received parity data field
311  *  @len:       data length
312  *  @s:         syndrome data field (if NULL, syndrome is calculated)
313  *  @no_eras:   number of erasures
314  *  @eras_pos:  position of erasures, can be NULL
315  *  @invmsk:    invert data mask (will be xored on data, not on parity!)
316  *  @corr:      buffer to store correction bitmask on eras_pos
317  *
318  *  Each field in the data array contains up to symbol size bits of valid data.
319  */
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,
322                 uint16_t *corr)
323 {
324 #include "decode_rs.c"
325 }
326 EXPORT_SYMBOL_GPL(decode_rs16);
327 #endif
328
329 EXPORT_SYMBOL_GPL(init_rs);
330 EXPORT_SYMBOL_GPL(free_rs);
331
332 MODULE_LICENSE("GPL");
333 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
334 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
335