Commit | Line | Data |
---|---|---|
dc8f923e | 1 | // SPDX-License-Identifier: GPL-2.0 |
03ead842 | 2 | /* |
3413e189 | 3 | * Generic Reed Solomon encoder / decoder library |
03ead842 | 4 | * |
1da177e4 LT |
5 | * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de) |
6 | * | |
7 | * Reed Solomon code lifted from reed solomon library written by Phil Karn | |
8 | * Copyright 2002 Phil Karn, KA9Q | |
9 | * | |
1da177e4 | 10 | * Description: |
03ead842 | 11 | * |
1da177e4 LT |
12 | * The generic Reed Solomon library provides runtime configurable |
13 | * encoding / decoding of RS codes. | |
14 | * Each user must call init_rs to get a pointer to a rs_control | |
15 | * structure for the given rs parameters. This structure is either | |
16 | * generated or a already available matching control structure is used. | |
17 | * If a structure is generated then the polynomial arrays for | |
18 | * fast encoding / decoding are built. This can take some time so | |
19 | * make sure not to call this function from a time critical path. | |
03ead842 | 20 | * Usually a module / driver should initialize the necessary |
1da177e4 LT |
21 | * rs_control structure on module / driver init and release it |
22 | * on exit. | |
03ead842 TG |
23 | * The encoding puts the calculated syndrome into a given syndrome |
24 | * buffer. | |
1da177e4 LT |
25 | * The decoding is a two step process. The first step calculates |
26 | * the syndrome over the received (data + syndrome) and calls the | |
27 | * second stage, which does the decoding / error correction itself. | |
28 | * Many hw encoders provide a syndrome calculation over the received | |
29 | * data + syndrome and can call the second stage directly. | |
1da177e4 | 30 | */ |
1da177e4 LT |
31 | #include <linux/errno.h> |
32 | #include <linux/kernel.h> | |
33 | #include <linux/init.h> | |
34 | #include <linux/module.h> | |
35 | #include <linux/rslib.h> | |
36 | #include <linux/slab.h> | |
97d1f15b | 37 | #include <linux/mutex.h> |
1da177e4 LT |
38 | |
39 | /* This list holds all currently allocated rs control structures */ | |
40 | static LIST_HEAD (rslist); | |
41 | /* Protection for the list */ | |
97d1f15b | 42 | static DEFINE_MUTEX(rslistlock); |
1da177e4 | 43 | |
03ead842 | 44 | /** |
1da177e4 | 45 | * rs_init - Initialize a Reed-Solomon codec |
1da177e4 LT |
46 | * @symsize: symbol size, bits (1-8) |
47 | * @gfpoly: Field generator polynomial coefficients | |
d7e5a546 | 48 | * @gffunc: Field generator function |
1da177e4 LT |
49 | * @fcr: first root of RS code generator polynomial, index form |
50 | * @prim: primitive element to generate polynomial roots | |
51 | * @nroots: RS code generator polynomial degree (number of roots) | |
83a530e1 | 52 | * @gfp: GFP_ flags for allocations |
1da177e4 LT |
53 | * |
54 | * Allocate a control structure and the polynom arrays for faster | |
9dc65576 | 55 | * en/decoding. Fill the arrays according to the given parameters. |
1da177e4 | 56 | */ |
d7e5a546 | 57 | static struct rs_control *rs_init(int symsize, int gfpoly, int (*gffunc)(int), |
83a530e1 | 58 | int fcr, int prim, int nroots, gfp_t gfp) |
1da177e4 LT |
59 | { |
60 | struct rs_control *rs; | |
61 | int i, j, sr, root, iprim; | |
62 | ||
a85e126a | 63 | rs = kzalloc(sizeof(*rs), gfp); |
83a530e1 | 64 | if (!rs) |
1da177e4 LT |
65 | return NULL; |
66 | ||
67 | INIT_LIST_HEAD(&rs->list); | |
68 | ||
69 | rs->mm = symsize; | |
70 | rs->nn = (1 << symsize) - 1; | |
71 | rs->fcr = fcr; | |
72 | rs->prim = prim; | |
73 | rs->nroots = nroots; | |
74 | rs->gfpoly = gfpoly; | |
d7e5a546 | 75 | rs->gffunc = gffunc; |
1da177e4 LT |
76 | |
77 | /* Allocate the arrays */ | |
83a530e1 | 78 | rs->alpha_to = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp); |
1da177e4 | 79 | if (rs->alpha_to == NULL) |
a85e126a | 80 | goto err; |
1da177e4 | 81 | |
83a530e1 | 82 | rs->index_of = kmalloc(sizeof(uint16_t) * (rs->nn + 1), gfp); |
1da177e4 | 83 | if (rs->index_of == NULL) |
a85e126a | 84 | goto err; |
1da177e4 | 85 | |
83a530e1 | 86 | rs->genpoly = kmalloc(sizeof(uint16_t) * (rs->nroots + 1), gfp); |
1da177e4 | 87 | if(rs->genpoly == NULL) |
a85e126a | 88 | goto err; |
1da177e4 LT |
89 | |
90 | /* Generate Galois field lookup tables */ | |
91 | rs->index_of[0] = rs->nn; /* log(zero) = -inf */ | |
92 | rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ | |
d7e5a546 SB |
93 | if (gfpoly) { |
94 | sr = 1; | |
95 | for (i = 0; i < rs->nn; i++) { | |
96 | rs->index_of[sr] = i; | |
97 | rs->alpha_to[i] = sr; | |
98 | sr <<= 1; | |
99 | if (sr & (1 << symsize)) | |
100 | sr ^= gfpoly; | |
101 | sr &= rs->nn; | |
102 | } | |
103 | } else { | |
104 | sr = gffunc(0); | |
105 | for (i = 0; i < rs->nn; i++) { | |
106 | rs->index_of[sr] = i; | |
107 | rs->alpha_to[i] = sr; | |
108 | sr = gffunc(sr); | |
109 | } | |
1da177e4 LT |
110 | } |
111 | /* If it's not primitive, exit */ | |
d7e5a546 | 112 | if(sr != rs->alpha_to[0]) |
a85e126a | 113 | goto err; |
1da177e4 LT |
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) { | |
03ead842 TG |
127 | rs->genpoly[j] = rs->genpoly[j -1] ^ |
128 | rs->alpha_to[rs_modnn(rs, | |
1da177e4 LT |
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 */ | |
03ead842 TG |
134 | rs->genpoly[0] = |
135 | rs->alpha_to[rs_modnn(rs, | |
1da177e4 LT |
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 | ||
a85e126a | 143 | err: |
1da177e4 | 144 | kfree(rs->genpoly); |
1da177e4 | 145 | kfree(rs->index_of); |
1da177e4 | 146 | kfree(rs->alpha_to); |
1da177e4 LT |
147 | kfree(rs); |
148 | return NULL; | |
149 | } | |
150 | ||
151 | ||
03ead842 | 152 | /** |
9dc65576 | 153 | * free_rs - Free the rs control structure, if it is no longer used |
1da177e4 LT |
154 | * @rs: the control structure which is not longer used by the |
155 | * caller | |
156 | */ | |
157 | void free_rs(struct rs_control *rs) | |
158 | { | |
97d1f15b | 159 | mutex_lock(&rslistlock); |
1da177e4 LT |
160 | rs->users--; |
161 | if(!rs->users) { | |
162 | list_del(&rs->list); | |
163 | kfree(rs->alpha_to); | |
164 | kfree(rs->index_of); | |
165 | kfree(rs->genpoly); | |
166 | kfree(rs); | |
167 | } | |
97d1f15b | 168 | mutex_unlock(&rslistlock); |
1da177e4 | 169 | } |
83a530e1 | 170 | EXPORT_SYMBOL_GPL(free_rs); |
1da177e4 | 171 | |
03ead842 | 172 | /** |
d7e5a546 | 173 | * init_rs_internal - Find a matching or allocate a new rs control structure |
1da177e4 LT |
174 | * @symsize: the symbol size (number of bits) |
175 | * @gfpoly: the extended Galois field generator polynomial coefficients, | |
176 | * with the 0th coefficient in the low order bit. The polynomial | |
177 | * must be primitive; | |
d7e5a546 SB |
178 | * @gffunc: pointer to function to generate the next field element, |
179 | * or the multiplicative identity element if given 0. Used | |
180 | * instead of gfpoly if gfpoly is 0 | |
cc4b86e4 | 181 | * @fcr: the first consecutive root of the rs code generator polynomial |
1da177e4 LT |
182 | * in index form |
183 | * @prim: primitive element to generate polynomial roots | |
184 | * @nroots: RS code generator polynomial degree (number of roots) | |
83a530e1 | 185 | * @gfp: GFP_ flags for allocations |
1da177e4 | 186 | */ |
d7e5a546 | 187 | static struct rs_control *init_rs_internal(int symsize, int gfpoly, |
83a530e1 TG |
188 | int (*gffunc)(int), int fcr, |
189 | int prim, int nroots, gfp_t gfp) | |
1da177e4 | 190 | { |
83a530e1 TG |
191 | struct list_head *tmp; |
192 | struct rs_control *rs; | |
1da177e4 LT |
193 | |
194 | /* Sanity checks */ | |
195 | if (symsize < 1) | |
196 | return NULL; | |
197 | if (fcr < 0 || fcr >= (1<<symsize)) | |
cc4b86e4 | 198 | return NULL; |
1da177e4 | 199 | if (prim <= 0 || prim >= (1<<symsize)) |
cc4b86e4 | 200 | return NULL; |
03ead842 | 201 | if (nroots < 0 || nroots >= (1<<symsize)) |
1da177e4 | 202 | return NULL; |
03ead842 | 203 | |
97d1f15b | 204 | mutex_lock(&rslistlock); |
1da177e4 LT |
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; | |
d7e5a546 SB |
213 | if (gffunc != rs->gffunc) |
214 | continue; | |
1da177e4 | 215 | if (fcr != rs->fcr) |
03ead842 | 216 | continue; |
1da177e4 | 217 | if (prim != rs->prim) |
03ead842 | 218 | continue; |
1da177e4 LT |
219 | if (nroots != rs->nroots) |
220 | continue; | |
221 | /* We have a matching one already */ | |
222 | rs->users++; | |
223 | goto out; | |
224 | } | |
225 | ||
226 | /* Create a new one */ | |
83a530e1 | 227 | rs = rs_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp); |
1da177e4 LT |
228 | if (rs) { |
229 | rs->users = 1; | |
230 | list_add(&rs->list, &rslist); | |
231 | } | |
03ead842 | 232 | out: |
97d1f15b | 233 | mutex_unlock(&rslistlock); |
1da177e4 LT |
234 | return rs; |
235 | } | |
236 | ||
d7e5a546 | 237 | /** |
83a530e1 | 238 | * init_rs_gfp - Find a matching or allocate a new rs control structure |
d7e5a546 SB |
239 | * @symsize: the symbol size (number of bits) |
240 | * @gfpoly: the extended Galois field generator polynomial coefficients, | |
241 | * with the 0th coefficient in the low order bit. The polynomial | |
242 | * must be primitive; | |
cc4b86e4 | 243 | * @fcr: the first consecutive root of the rs code generator polynomial |
d7e5a546 SB |
244 | * in index form |
245 | * @prim: primitive element to generate polynomial roots | |
246 | * @nroots: RS code generator polynomial degree (number of roots) | |
83a530e1 | 247 | * @gfp: GFP_ flags for allocations |
d7e5a546 | 248 | */ |
83a530e1 TG |
249 | struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim, |
250 | int nroots, gfp_t gfp) | |
d7e5a546 | 251 | { |
83a530e1 | 252 | return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp); |
d7e5a546 | 253 | } |
83a530e1 | 254 | EXPORT_SYMBOL_GPL(init_rs_gfp); |
d7e5a546 SB |
255 | |
256 | /** | |
257 | * init_rs_non_canonical - Find a matching or allocate a new rs control | |
258 | * structure, for fields with non-canonical | |
259 | * representation | |
260 | * @symsize: the symbol size (number of bits) | |
261 | * @gffunc: pointer to function to generate the next field element, | |
262 | * or the multiplicative identity element if given 0. Used | |
263 | * instead of gfpoly if gfpoly is 0 | |
cc4b86e4 | 264 | * @fcr: the first consecutive root of the rs code generator polynomial |
d7e5a546 SB |
265 | * in index form |
266 | * @prim: primitive element to generate polynomial roots | |
267 | * @nroots: RS code generator polynomial degree (number of roots) | |
268 | */ | |
269 | struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), | |
cc4b86e4 | 270 | int fcr, int prim, int nroots) |
d7e5a546 | 271 | { |
83a530e1 TG |
272 | return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots, |
273 | GFP_KERNEL); | |
d7e5a546 | 274 | } |
83a530e1 | 275 | EXPORT_SYMBOL_GPL(init_rs_non_canonical); |
d7e5a546 | 276 | |
1da177e4 | 277 | #ifdef CONFIG_REED_SOLOMON_ENC8 |
03ead842 | 278 | /** |
1da177e4 | 279 | * encode_rs8 - Calculate the parity for data values (8bit data width) |
1da177e4 LT |
280 | * @rs: the rs control structure |
281 | * @data: data field of a given type | |
03ead842 | 282 | * @len: data length |
1da177e4 LT |
283 | * @par: parity data, must be initialized by caller (usually all 0) |
284 | * @invmsk: invert data mask (will be xored on data) | |
285 | * | |
286 | * The parity uses a uint16_t data type to enable | |
287 | * symbol size > 8. The calling code must take care of encoding of the | |
288 | * syndrome result for storage itself. | |
289 | */ | |
03ead842 | 290 | int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par, |
1da177e4 LT |
291 | uint16_t invmsk) |
292 | { | |
293 | #include "encode_rs.c" | |
294 | } | |
295 | EXPORT_SYMBOL_GPL(encode_rs8); | |
296 | #endif | |
297 | ||
298 | #ifdef CONFIG_REED_SOLOMON_DEC8 | |
03ead842 | 299 | /** |
1da177e4 | 300 | * decode_rs8 - Decode codeword (8bit data width) |
1da177e4 LT |
301 | * @rs: the rs control structure |
302 | * @data: data field of a given type | |
303 | * @par: received parity data field | |
304 | * @len: data length | |
305 | * @s: syndrome data field (if NULL, syndrome is calculated) | |
306 | * @no_eras: number of erasures | |
307 | * @eras_pos: position of erasures, can be NULL | |
308 | * @invmsk: invert data mask (will be xored on data, not on parity!) | |
309 | * @corr: buffer to store correction bitmask on eras_pos | |
310 | * | |
311 | * The syndrome and parity uses a uint16_t data type to enable | |
312 | * symbol size > 8. The calling code must take care of decoding of the | |
313 | * syndrome result and the received parity before calling this code. | |
eb684507 | 314 | * Returns the number of corrected bits or -EBADMSG for uncorrectable errors. |
1da177e4 LT |
315 | */ |
316 | int decode_rs8(struct rs_control *rs, uint8_t *data, uint16_t *par, int len, | |
03ead842 | 317 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
1da177e4 LT |
318 | uint16_t *corr) |
319 | { | |
320 | #include "decode_rs.c" | |
321 | } | |
322 | EXPORT_SYMBOL_GPL(decode_rs8); | |
323 | #endif | |
324 | ||
325 | #ifdef CONFIG_REED_SOLOMON_ENC16 | |
326 | /** | |
327 | * encode_rs16 - Calculate the parity for data values (16bit data width) | |
1da177e4 LT |
328 | * @rs: the rs control structure |
329 | * @data: data field of a given type | |
03ead842 | 330 | * @len: data length |
1da177e4 LT |
331 | * @par: parity data, must be initialized by caller (usually all 0) |
332 | * @invmsk: invert data mask (will be xored on data, not on parity!) | |
333 | * | |
334 | * Each field in the data array contains up to symbol size bits of valid data. | |
335 | */ | |
03ead842 | 336 | int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par, |
1da177e4 LT |
337 | uint16_t invmsk) |
338 | { | |
339 | #include "encode_rs.c" | |
340 | } | |
341 | EXPORT_SYMBOL_GPL(encode_rs16); | |
342 | #endif | |
343 | ||
344 | #ifdef CONFIG_REED_SOLOMON_DEC16 | |
03ead842 | 345 | /** |
1da177e4 | 346 | * decode_rs16 - Decode codeword (16bit data width) |
1da177e4 LT |
347 | * @rs: the rs control structure |
348 | * @data: data field of a given type | |
349 | * @par: received parity data field | |
350 | * @len: data length | |
351 | * @s: syndrome data field (if NULL, syndrome is calculated) | |
352 | * @no_eras: number of erasures | |
353 | * @eras_pos: position of erasures, can be NULL | |
03ead842 | 354 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
1da177e4 LT |
355 | * @corr: buffer to store correction bitmask on eras_pos |
356 | * | |
357 | * Each field in the data array contains up to symbol size bits of valid data. | |
eb684507 | 358 | * Returns the number of corrected bits or -EBADMSG for uncorrectable errors. |
1da177e4 LT |
359 | */ |
360 | int decode_rs16(struct rs_control *rs, uint16_t *data, uint16_t *par, int len, | |
03ead842 | 361 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
1da177e4 LT |
362 | uint16_t *corr) |
363 | { | |
364 | #include "decode_rs.c" | |
365 | } | |
366 | EXPORT_SYMBOL_GPL(decode_rs16); | |
367 | #endif | |
368 | ||
1da177e4 LT |
369 | MODULE_LICENSE("GPL"); |
370 | MODULE_DESCRIPTION("Reed Solomon encoder/decoder"); | |
371 | MODULE_AUTHOR("Phil Karn, Thomas Gleixner"); | |
372 |