1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Generic Reed Solomon encoder / decoder library |
4 | * |
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 | * |
10 | * Description: |
11 | * |
12 | * The generic Reed Solomon library provides runtime configurable |
13 | * encoding / decoding of RS codes. |
14 | * |
15 | * Each user must call init_rs to get a pointer to a rs_control structure |
16 | * for the given rs parameters. The control struct is unique per instance. |
17 | * It points to a codec which can be shared by multiple control structures. |
18 | * If a codec is newly allocated then the polynomial arrays for fast |
19 | * encoding / decoding are built. This can take some time so make sure not |
20 | * to call this function from a time critical path. Usually a module / |
21 | * driver should initialize the necessary rs_control structure on module / |
22 | * driver init and release it on exit. |
23 | * |
24 | * The encoding puts the calculated syndrome into a given syndrome buffer. |
25 | * |
26 | * The decoding is a two step process. The first step calculates the |
27 | * syndrome over the received (data + syndrome) and calls the second stage, |
28 | * which does the decoding / error correction itself. Many hw encoders |
29 | * provide a syndrome calculation over the received data + syndrome and can |
30 | * call the second stage directly. |
31 | */ |
32 | #include <linux/errno.h> |
33 | #include <linux/kernel.h> |
34 | #include <linux/init.h> |
35 | #include <linux/module.h> |
36 | #include <linux/rslib.h> |
37 | #include <linux/slab.h> |
38 | #include <linux/mutex.h> |
39 | |
40 | enum { |
41 | RS_DECODE_LAMBDA, |
42 | RS_DECODE_SYN, |
43 | RS_DECODE_B, |
44 | RS_DECODE_T, |
45 | RS_DECODE_OMEGA, |
46 | RS_DECODE_ROOT, |
47 | RS_DECODE_REG, |
48 | RS_DECODE_LOC, |
49 | RS_DECODE_NUM_BUFFERS |
50 | }; |
51 | |
52 | /* This list holds all currently allocated rs codec structures */ |
53 | static LIST_HEAD(codec_list); |
54 | /* Protection for the list */ |
55 | static DEFINE_MUTEX(rslistlock); |
56 | |
57 | /** |
58 | * codec_init - Initialize a Reed-Solomon codec |
59 | * @symsize: symbol size, bits (1-8) |
60 | * @gfpoly: Field generator polynomial coefficients |
61 | * @gffunc: Field generator function |
62 | * @fcr: first root of RS code generator polynomial, index form |
63 | * @prim: primitive element to generate polynomial roots |
64 | * @nroots: RS code generator polynomial degree (number of roots) |
65 | * @gfp: GFP_ flags for allocations |
66 | * |
67 | * Allocate a codec structure and the polynom arrays for faster |
68 | * en/decoding. Fill the arrays according to the given parameters. |
69 | */ |
70 | static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int), |
71 | int fcr, int prim, int nroots, gfp_t gfp) |
72 | { |
73 | int i, j, sr, root, iprim; |
74 | struct rs_codec *rs; |
75 | |
76 | rs = kzalloc(size: sizeof(*rs), flags: gfp); |
77 | if (!rs) |
78 | return NULL; |
79 | |
80 | INIT_LIST_HEAD(list: &rs->list); |
81 | |
82 | rs->mm = symsize; |
83 | rs->nn = (1 << symsize) - 1; |
84 | rs->fcr = fcr; |
85 | rs->prim = prim; |
86 | rs->nroots = nroots; |
87 | rs->gfpoly = gfpoly; |
88 | rs->gffunc = gffunc; |
89 | |
90 | /* Allocate the arrays */ |
91 | rs->alpha_to = kmalloc_array(n: rs->nn + 1, size: sizeof(uint16_t), flags: gfp); |
92 | if (rs->alpha_to == NULL) |
93 | goto err; |
94 | |
95 | rs->index_of = kmalloc_array(n: rs->nn + 1, size: sizeof(uint16_t), flags: gfp); |
96 | if (rs->index_of == NULL) |
97 | goto err; |
98 | |
99 | rs->genpoly = kmalloc_array(n: rs->nroots + 1, size: sizeof(uint16_t), flags: gfp); |
100 | if(rs->genpoly == NULL) |
101 | goto err; |
102 | |
103 | /* Generate Galois field lookup tables */ |
104 | rs->index_of[0] = rs->nn; /* log(zero) = -inf */ |
105 | rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */ |
106 | if (gfpoly) { |
107 | sr = 1; |
108 | for (i = 0; i < rs->nn; i++) { |
109 | rs->index_of[sr] = i; |
110 | rs->alpha_to[i] = sr; |
111 | sr <<= 1; |
112 | if (sr & (1 << symsize)) |
113 | sr ^= gfpoly; |
114 | sr &= rs->nn; |
115 | } |
116 | } else { |
117 | sr = gffunc(0); |
118 | for (i = 0; i < rs->nn; i++) { |
119 | rs->index_of[sr] = i; |
120 | rs->alpha_to[i] = sr; |
121 | sr = gffunc(sr); |
122 | } |
123 | } |
124 | /* If it's not primitive, exit */ |
125 | if(sr != rs->alpha_to[0]) |
126 | goto err; |
127 | |
128 | /* Find prim-th root of 1, used in decoding */ |
129 | for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn); |
130 | /* prim-th root of 1, index form */ |
131 | rs->iprim = iprim / prim; |
132 | |
133 | /* Form RS code generator polynomial from its roots */ |
134 | rs->genpoly[0] = 1; |
135 | for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) { |
136 | rs->genpoly[i + 1] = 1; |
137 | /* Multiply rs->genpoly[] by @**(root + x) */ |
138 | for (j = i; j > 0; j--) { |
139 | if (rs->genpoly[j] != 0) { |
140 | rs->genpoly[j] = rs->genpoly[j -1] ^ |
141 | rs->alpha_to[rs_modnn(rs, |
142 | x: rs->index_of[rs->genpoly[j]] + root)]; |
143 | } else |
144 | rs->genpoly[j] = rs->genpoly[j - 1]; |
145 | } |
146 | /* rs->genpoly[0] can never be zero */ |
147 | rs->genpoly[0] = |
148 | rs->alpha_to[rs_modnn(rs, |
149 | x: rs->index_of[rs->genpoly[0]] + root)]; |
150 | } |
151 | /* convert rs->genpoly[] to index form for quicker encoding */ |
152 | for (i = 0; i <= nroots; i++) |
153 | rs->genpoly[i] = rs->index_of[rs->genpoly[i]]; |
154 | |
155 | rs->users = 1; |
156 | list_add(new: &rs->list, head: &codec_list); |
157 | return rs; |
158 | |
159 | err: |
160 | kfree(objp: rs->genpoly); |
161 | kfree(objp: rs->index_of); |
162 | kfree(objp: rs->alpha_to); |
163 | kfree(objp: rs); |
164 | return NULL; |
165 | } |
166 | |
167 | |
168 | /** |
169 | * free_rs - Free the rs control structure |
170 | * @rs: The control structure which is not longer used by the |
171 | * caller |
172 | * |
173 | * Free the control structure. If @rs is the last user of the associated |
174 | * codec, free the codec as well. |
175 | */ |
176 | void free_rs(struct rs_control *rs) |
177 | { |
178 | struct rs_codec *cd; |
179 | |
180 | if (!rs) |
181 | return; |
182 | |
183 | cd = rs->codec; |
184 | mutex_lock(&rslistlock); |
185 | cd->users--; |
186 | if(!cd->users) { |
187 | list_del(entry: &cd->list); |
188 | kfree(objp: cd->alpha_to); |
189 | kfree(objp: cd->index_of); |
190 | kfree(objp: cd->genpoly); |
191 | kfree(objp: cd); |
192 | } |
193 | mutex_unlock(lock: &rslistlock); |
194 | kfree(objp: rs); |
195 | } |
196 | EXPORT_SYMBOL_GPL(free_rs); |
197 | |
198 | /** |
199 | * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one |
200 | * @symsize: the symbol size (number of bits) |
201 | * @gfpoly: the extended Galois field generator polynomial coefficients, |
202 | * with the 0th coefficient in the low order bit. The polynomial |
203 | * must be primitive; |
204 | * @gffunc: pointer to function to generate the next field element, |
205 | * or the multiplicative identity element if given 0. Used |
206 | * instead of gfpoly if gfpoly is 0 |
207 | * @fcr: the first consecutive root of the rs code generator polynomial |
208 | * in index form |
209 | * @prim: primitive element to generate polynomial roots |
210 | * @nroots: RS code generator polynomial degree (number of roots) |
211 | * @gfp: GFP_ flags for allocations |
212 | */ |
213 | static struct rs_control *init_rs_internal(int symsize, int gfpoly, |
214 | int (*gffunc)(int), int fcr, |
215 | int prim, int nroots, gfp_t gfp) |
216 | { |
217 | struct list_head *tmp; |
218 | struct rs_control *rs; |
219 | unsigned int bsize; |
220 | |
221 | /* Sanity checks */ |
222 | if (symsize < 1) |
223 | return NULL; |
224 | if (fcr < 0 || fcr >= (1<<symsize)) |
225 | return NULL; |
226 | if (prim <= 0 || prim >= (1<<symsize)) |
227 | return NULL; |
228 | if (nroots < 0 || nroots >= (1<<symsize)) |
229 | return NULL; |
230 | |
231 | /* |
232 | * The decoder needs buffers in each control struct instance to |
233 | * avoid variable size or large fixed size allocations on |
234 | * stack. Size the buffers to arrays of [nroots + 1]. |
235 | */ |
236 | bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1); |
237 | rs = kzalloc(size: sizeof(*rs) + bsize, flags: gfp); |
238 | if (!rs) |
239 | return NULL; |
240 | |
241 | mutex_lock(&rslistlock); |
242 | |
243 | /* Walk through the list and look for a matching entry */ |
244 | list_for_each(tmp, &codec_list) { |
245 | struct rs_codec *cd = list_entry(tmp, struct rs_codec, list); |
246 | |
247 | if (symsize != cd->mm) |
248 | continue; |
249 | if (gfpoly != cd->gfpoly) |
250 | continue; |
251 | if (gffunc != cd->gffunc) |
252 | continue; |
253 | if (fcr != cd->fcr) |
254 | continue; |
255 | if (prim != cd->prim) |
256 | continue; |
257 | if (nroots != cd->nroots) |
258 | continue; |
259 | /* We have a matching one already */ |
260 | cd->users++; |
261 | rs->codec = cd; |
262 | goto out; |
263 | } |
264 | |
265 | /* Create a new one */ |
266 | rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp); |
267 | if (!rs->codec) { |
268 | kfree(objp: rs); |
269 | rs = NULL; |
270 | } |
271 | out: |
272 | mutex_unlock(lock: &rslistlock); |
273 | return rs; |
274 | } |
275 | |
276 | /** |
277 | * init_rs_gfp - Create a RS control struct and initialize it |
278 | * @symsize: the symbol size (number of bits) |
279 | * @gfpoly: the extended Galois field generator polynomial coefficients, |
280 | * with the 0th coefficient in the low order bit. The polynomial |
281 | * must be primitive; |
282 | * @fcr: the first consecutive root of the rs code generator polynomial |
283 | * in index form |
284 | * @prim: primitive element to generate polynomial roots |
285 | * @nroots: RS code generator polynomial degree (number of roots) |
286 | * @gfp: Memory allocation flags. |
287 | */ |
288 | struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim, |
289 | int nroots, gfp_t gfp) |
290 | { |
291 | return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp); |
292 | } |
293 | EXPORT_SYMBOL_GPL(init_rs_gfp); |
294 | |
295 | /** |
296 | * init_rs_non_canonical - Allocate rs control struct for fields with |
297 | * non-canonical representation |
298 | * @symsize: the symbol size (number of bits) |
299 | * @gffunc: pointer to function to generate the next field element, |
300 | * or the multiplicative identity element if given 0. Used |
301 | * instead of gfpoly if gfpoly is 0 |
302 | * @fcr: the first consecutive root of the rs code generator polynomial |
303 | * in index form |
304 | * @prim: primitive element to generate polynomial roots |
305 | * @nroots: RS code generator polynomial degree (number of roots) |
306 | */ |
307 | struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int), |
308 | int fcr, int prim, int nroots) |
309 | { |
310 | return init_rs_internal(symsize, gfpoly: 0, gffunc, fcr, prim, nroots, |
311 | GFP_KERNEL); |
312 | } |
313 | EXPORT_SYMBOL_GPL(init_rs_non_canonical); |
314 | |
315 | #ifdef CONFIG_REED_SOLOMON_ENC8 |
316 | /** |
317 | * encode_rs8 - Calculate the parity for data values (8bit data width) |
318 | * @rsc: the rs control structure |
319 | * @data: data field of a given type |
320 | * @len: data length |
321 | * @par: parity data, must be initialized by caller (usually all 0) |
322 | * @invmsk: invert data mask (will be xored on data) |
323 | * |
324 | * The parity uses a uint16_t data type to enable |
325 | * symbol size > 8. The calling code must take care of encoding of the |
326 | * syndrome result for storage itself. |
327 | */ |
328 | int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par, |
329 | uint16_t invmsk) |
330 | { |
331 | #include "encode_rs.c" |
332 | } |
333 | EXPORT_SYMBOL_GPL(encode_rs8); |
334 | #endif |
335 | |
336 | #ifdef CONFIG_REED_SOLOMON_DEC8 |
337 | /** |
338 | * decode_rs8 - Decode codeword (8bit data width) |
339 | * @rsc: the rs control structure |
340 | * @data: data field of a given type |
341 | * @par: received parity data field |
342 | * @len: data length |
343 | * @s: syndrome data field, must be in index form |
344 | * (if NULL, syndrome is calculated) |
345 | * @no_eras: number of erasures |
346 | * @eras_pos: position of erasures, can be NULL |
347 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
348 | * @corr: buffer to store correction bitmask on eras_pos |
349 | * |
350 | * The syndrome and parity uses a uint16_t data type to enable |
351 | * symbol size > 8. The calling code must take care of decoding of the |
352 | * syndrome result and the received parity before calling this code. |
353 | * |
354 | * Note: The rs_control struct @rsc contains buffers which are used for |
355 | * decoding, so the caller has to ensure that decoder invocations are |
356 | * serialized. |
357 | * |
358 | * Returns the number of corrected symbols or -EBADMSG for uncorrectable |
359 | * errors. The count includes errors in the parity. |
360 | */ |
361 | int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len, |
362 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
363 | uint16_t *corr) |
364 | { |
365 | #include "decode_rs.c" |
366 | } |
367 | EXPORT_SYMBOL_GPL(decode_rs8); |
368 | #endif |
369 | |
370 | #ifdef CONFIG_REED_SOLOMON_ENC16 |
371 | /** |
372 | * encode_rs16 - Calculate the parity for data values (16bit data width) |
373 | * @rsc: the rs control structure |
374 | * @data: data field of a given type |
375 | * @len: data length |
376 | * @par: parity data, must be initialized by caller (usually all 0) |
377 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
378 | * |
379 | * Each field in the data array contains up to symbol size bits of valid data. |
380 | */ |
381 | int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par, |
382 | uint16_t invmsk) |
383 | { |
384 | #include "encode_rs.c" |
385 | } |
386 | EXPORT_SYMBOL_GPL(encode_rs16); |
387 | #endif |
388 | |
389 | #ifdef CONFIG_REED_SOLOMON_DEC16 |
390 | /** |
391 | * decode_rs16 - Decode codeword (16bit data width) |
392 | * @rsc: the rs control structure |
393 | * @data: data field of a given type |
394 | * @par: received parity data field |
395 | * @len: data length |
396 | * @s: syndrome data field, must be in index form |
397 | * (if NULL, syndrome is calculated) |
398 | * @no_eras: number of erasures |
399 | * @eras_pos: position of erasures, can be NULL |
400 | * @invmsk: invert data mask (will be xored on data, not on parity!) |
401 | * @corr: buffer to store correction bitmask on eras_pos |
402 | * |
403 | * Each field in the data array contains up to symbol size bits of valid data. |
404 | * |
405 | * Note: The rc_control struct @rsc contains buffers which are used for |
406 | * decoding, so the caller has to ensure that decoder invocations are |
407 | * serialized. |
408 | * |
409 | * Returns the number of corrected symbols or -EBADMSG for uncorrectable |
410 | * errors. The count includes errors in the parity. |
411 | */ |
412 | int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len, |
413 | uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk, |
414 | uint16_t *corr) |
415 | { |
416 | #include "decode_rs.c" |
417 | } |
418 | EXPORT_SYMBOL_GPL(decode_rs16); |
419 | #endif |
420 | |
421 | MODULE_LICENSE("GPL" ); |
422 | MODULE_DESCRIPTION("Reed Solomon encoder/decoder" ); |
423 | MODULE_AUTHOR("Phil Karn, Thomas Gleixner" ); |
424 | |
425 | |