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