Change the kernel config for scenario test
[kvmfornfv.git] / kernel / lib / reed_solomon / reed_solomon.c
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 */
50 static LIST_HEAD (rslist);
51 /* Protection for the list */
52 static 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  */
66 static 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 */
154 errpol:
155         kfree(rs->genpoly);
156 erridx:
157         kfree(rs->index_of);
158 erralp:
159         kfree(rs->alpha_to);
160 errrs:
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  */
171 void 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  */
199 static 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         }
244 out:
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  */
260 struct 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  */
279 struct 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  */
298 int 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 }
303 EXPORT_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  */
324 int 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 }
330 EXPORT_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  */
344 int 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 }
349 EXPORT_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  */
368 int 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 }
374 EXPORT_SYMBOL_GPL(decode_rs16);
375 #endif
376
377 EXPORT_SYMBOL_GPL(init_rs);
378 EXPORT_SYMBOL_GPL(init_rs_non_canonical);
379 EXPORT_SYMBOL_GPL(free_rs);
380
381 MODULE_LICENSE("GPL");
382 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
383 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");
384