]>
git.proxmox.com Git - mirror_ubuntu-artful-kernel.git/blob - lib/reed_solomon/reed_solomon.c
2 * lib/reed_solomon/rslib.c
5 * Generic Reed Solomon encoder / decoder library
7 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
9 * Reed Solomon code lifted from reed solomon library written by Phil Karn
10 * Copyright 2002 Phil Karn, KA9Q
12 * $Id: rslib.c,v 1.7 2005/11/07 11:14:59 gleixner Exp $
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.
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
31 * The encoding puts the calculated syndrome into a given syndrome
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.
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 #include <asm/semaphore.h>
50 /* This list holds all currently allocated rs control structures */
51 static LIST_HEAD (rslist
);
52 /* Protection for the list */
53 static DEFINE_MUTEX(rslistlock
);
56 * rs_init - Initialize a Reed-Solomon codec
58 * @symsize: symbol size, bits (1-8)
59 * @gfpoly: Field generator polynomial coefficients
60 * @fcr: first root of RS code generator polynomial, index form
61 * @prim: primitive element to generate polynomial roots
62 * @nroots: RS code generator polynomial degree (number of roots)
64 * Allocate a control structure and the polynom arrays for faster
65 * en/decoding. Fill the arrays according to the given parameters
67 static struct rs_control
*rs_init(int symsize
, int gfpoly
, int fcr
,
70 struct rs_control
*rs
;
71 int i
, j
, sr
, root
, iprim
;
73 /* Allocate the control structure */
74 rs
= kmalloc(sizeof (struct rs_control
), GFP_KERNEL
);
78 INIT_LIST_HEAD(&rs
->list
);
81 rs
->nn
= (1 << symsize
) - 1;
87 /* Allocate the arrays */
88 rs
->alpha_to
= kmalloc(sizeof(uint16_t) * (rs
->nn
+ 1), GFP_KERNEL
);
89 if (rs
->alpha_to
== NULL
)
92 rs
->index_of
= kmalloc(sizeof(uint16_t) * (rs
->nn
+ 1), GFP_KERNEL
);
93 if (rs
->index_of
== NULL
)
96 rs
->genpoly
= kmalloc(sizeof(uint16_t) * (rs
->nroots
+ 1), GFP_KERNEL
);
97 if(rs
->genpoly
== NULL
)
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 */
104 for (i
= 0; i
< rs
->nn
; i
++) {
105 rs
->index_of
[sr
] = i
;
106 rs
->alpha_to
[i
] = sr
;
108 if (sr
& (1 << symsize
))
112 /* If it's not primitive, exit */
116 /* Find prim-th root of 1, used in decoding */
117 for(iprim
= 1; (iprim
% prim
) != 0; iprim
+= rs
->nn
);
118 /* prim-th root of 1, index form */
119 rs
->iprim
= iprim
/ prim
;
121 /* Form RS code generator polynomial from its roots */
123 for (i
= 0, root
= fcr
* prim
; i
< nroots
; i
++, root
+= prim
) {
124 rs
->genpoly
[i
+ 1] = 1;
125 /* Multiply rs->genpoly[] by @**(root + x) */
126 for (j
= i
; j
> 0; j
--) {
127 if (rs
->genpoly
[j
] != 0) {
128 rs
->genpoly
[j
] = rs
->genpoly
[j
-1] ^
129 rs
->alpha_to
[rs_modnn(rs
,
130 rs
->index_of
[rs
->genpoly
[j
]] + root
)];
132 rs
->genpoly
[j
] = rs
->genpoly
[j
- 1];
134 /* rs->genpoly[0] can never be zero */
136 rs
->alpha_to
[rs_modnn(rs
,
137 rs
->index_of
[rs
->genpoly
[0]] + root
)];
139 /* convert rs->genpoly[] to index form for quicker encoding */
140 for (i
= 0; i
<= nroots
; i
++)
141 rs
->genpoly
[i
] = rs
->index_of
[rs
->genpoly
[i
]];
158 * free_rs - Free the rs control structure, if its not longer used
160 * @rs: the control structure which is not longer used by the
163 void free_rs(struct rs_control
*rs
)
165 mutex_lock(&rslistlock
);
174 mutex_unlock(&rslistlock
);
178 * init_rs - Find a matching or allocate a new rs control structure
180 * @symsize: the symbol size (number of bits)
181 * @gfpoly: the extended Galois field generator polynomial coefficients,
182 * with the 0th coefficient in the low order bit. The polynomial
184 * @fcr: the first consecutive root of the rs code generator polynomial
186 * @prim: primitive element to generate polynomial roots
187 * @nroots: RS code generator polynomial degree (number of roots)
189 struct rs_control
*init_rs(int symsize
, int gfpoly
, int fcr
, int prim
,
192 struct list_head
*tmp
;
193 struct rs_control
*rs
;
198 if (fcr
< 0 || fcr
>= (1<<symsize
))
200 if (prim
<= 0 || prim
>= (1<<symsize
))
202 if (nroots
< 0 || nroots
>= (1<<symsize
))
205 mutex_lock(&rslistlock
);
207 /* Walk through the list and look for a matching entry */
208 list_for_each(tmp
, &rslist
) {
209 rs
= list_entry(tmp
, struct rs_control
, list
);
210 if (symsize
!= rs
->mm
)
212 if (gfpoly
!= rs
->gfpoly
)
216 if (prim
!= rs
->prim
)
218 if (nroots
!= rs
->nroots
)
220 /* We have a matching one already */
225 /* Create a new one */
226 rs
= rs_init(symsize
, gfpoly
, fcr
, prim
, nroots
);
229 list_add(&rs
->list
, &rslist
);
232 mutex_unlock(&rslistlock
);
236 #ifdef CONFIG_REED_SOLOMON_ENC8
238 * encode_rs8 - Calculate the parity for data values (8bit data width)
240 * @rs: the rs control structure
241 * @data: data field of a given type
243 * @par: parity data, must be initialized by caller (usually all 0)
244 * @invmsk: invert data mask (will be xored on data)
246 * The parity uses a uint16_t data type to enable
247 * symbol size > 8. The calling code must take care of encoding of the
248 * syndrome result for storage itself.
250 int encode_rs8(struct rs_control
*rs
, uint8_t *data
, int len
, uint16_t *par
,
253 #include "encode_rs.c"
255 EXPORT_SYMBOL_GPL(encode_rs8
);
258 #ifdef CONFIG_REED_SOLOMON_DEC8
260 * decode_rs8 - Decode codeword (8bit data width)
262 * @rs: the rs control structure
263 * @data: data field of a given type
264 * @par: received parity data field
266 * @s: syndrome data field (if NULL, syndrome is calculated)
267 * @no_eras: number of erasures
268 * @eras_pos: position of erasures, can be NULL
269 * @invmsk: invert data mask (will be xored on data, not on parity!)
270 * @corr: buffer to store correction bitmask on eras_pos
272 * The syndrome and parity uses a uint16_t data type to enable
273 * symbol size > 8. The calling code must take care of decoding of the
274 * syndrome result and the received parity before calling this code.
276 int decode_rs8(struct rs_control
*rs
, uint8_t *data
, uint16_t *par
, int len
,
277 uint16_t *s
, int no_eras
, int *eras_pos
, uint16_t invmsk
,
280 #include "decode_rs.c"
282 EXPORT_SYMBOL_GPL(decode_rs8
);
285 #ifdef CONFIG_REED_SOLOMON_ENC16
287 * encode_rs16 - Calculate the parity for data values (16bit data width)
289 * @rs: the rs control structure
290 * @data: data field of a given type
292 * @par: parity data, must be initialized by caller (usually all 0)
293 * @invmsk: invert data mask (will be xored on data, not on parity!)
295 * Each field in the data array contains up to symbol size bits of valid data.
297 int encode_rs16(struct rs_control
*rs
, uint16_t *data
, int len
, uint16_t *par
,
300 #include "encode_rs.c"
302 EXPORT_SYMBOL_GPL(encode_rs16
);
305 #ifdef CONFIG_REED_SOLOMON_DEC16
307 * decode_rs16 - Decode codeword (16bit data width)
309 * @rs: the rs control structure
310 * @data: data field of a given type
311 * @par: received parity data field
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
319 * Each field in the data array contains up to symbol size bits of valid data.
321 int decode_rs16(struct rs_control
*rs
, uint16_t *data
, uint16_t *par
, int len
,
322 uint16_t *s
, int no_eras
, int *eras_pos
, uint16_t invmsk
,
325 #include "decode_rs.c"
327 EXPORT_SYMBOL_GPL(decode_rs16
);
330 EXPORT_SYMBOL_GPL(init_rs
);
331 EXPORT_SYMBOL_GPL(free_rs
);
333 MODULE_LICENSE("GPL");
334 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
335 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");