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(sizeof(*rs), gfp);
77 if (!rs)
78 return NULL;
79
80 INIT_LIST_HEAD(&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(rs->nn + 1, sizeof(uint16_t), gfp);
92 if (rs->alpha_to == NULL)
93 goto err;
94
95 rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
96 if (rs->index_of == NULL)
97 goto err;
98
99 rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), 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 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 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(&rs->list, &codec_list);
157 return rs;
158
159 err:
160 kfree(rs->genpoly);
161 kfree(rs->index_of);
162 kfree(rs->alpha_to);
163 kfree(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(&cd->list);
188 kfree(cd->alpha_to);
189 kfree(cd->index_of);
190 kfree(cd->genpoly);
191 kfree(cd);
192 }
193 mutex_unlock(&rslistlock);
194 kfree(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(sizeof(*rs) + bsize, 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(rs);
269 rs = NULL;
270 }
271 out:
272 mutex_unlock(&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, 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
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.