aboutsummaryrefslogtreecommitdiff
path: root/lib/reed_solomon/reed_solomon.c
blob: bbc01bad3053e7ef247d383234f6ade9fb1f717b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
// SPDX-License-Identifier: GPL-2.0
/*
 * Generic Reed Solomon encoder / decoder library
 *
 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
 *
 * Reed Solomon code lifted from reed solomon library written by Phil Karn
 * Copyright 2002 Phil Karn, KA9Q
 *
 * Description:
 *
 * The generic Reed Solomon library provides runtime configurable
 * encoding / decoding of RS codes.
 *
 * Each user must call init_rs to get a pointer to a rs_control structure
 * for the given rs parameters. The control struct is unique per instance.
 * It points to a codec which can be shared by multiple control structures.
 * If a codec is newly allocated then the polynomial arrays for fast
 * encoding / decoding are built. This can take some time so make sure not
 * to call this function from a time critical path.  Usually a module /
 * driver should initialize the necessary rs_control structure on module /
 * driver init and release it on exit.
 *
 * The encoding puts the calculated syndrome into a given syndrome buffer.
 *
 * The decoding is a two step process. The first step calculates the
 * syndrome over the received (data + syndrome) and calls the second stage,
 * which does the decoding / error correction itself.  Many hw encoders
 * provide a syndrome calculation over the received data + syndrome and can
 * call the second stage directly.
 */
#include <linux/errno.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/rslib.h>
#include <linux/slab.h>
#include <linux/mutex.h>

enum {
	RS_DECODE_LAMBDA,
	RS_DECODE_SYN,
	RS_DECODE_B,
	RS_DECODE_T,
	RS_DECODE_OMEGA,
	RS_DECODE_ROOT,
	RS_DECODE_REG,
	RS_DECODE_LOC,
	RS_DECODE_NUM_BUFFERS
};

/* This list holds all currently allocated rs codec structures */
static LIST_HEAD(codec_list);
/* Protection for the list */
static DEFINE_MUTEX(rslistlock);

/**
 * codec_init - Initialize a Reed-Solomon codec
 * @symsize:	symbol size, bits (1-8)
 * @gfpoly:	Field generator polynomial coefficients
 * @gffunc:	Field generator function
 * @fcr:	first root of RS code generator polynomial, index form
 * @prim:	primitive element to generate polynomial roots
 * @nroots:	RS code generator polynomial degree (number of roots)
 * @gfp:	GFP_ flags for allocations
 *
 * Allocate a codec structure and the polynom arrays for faster
 * en/decoding. Fill the arrays according to the given parameters.
 */
static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
				   int fcr, int prim, int nroots, gfp_t gfp)
{
	int i, j, sr, root, iprim;
	struct rs_codec *rs;

	rs = kzalloc(sizeof(*rs), gfp);
	if (!rs)
		return NULL;

	INIT_LIST_HEAD(&rs->list);

	rs->mm = symsize;
	rs->nn = (1 << symsize) - 1;
	rs->fcr = fcr;
	rs->prim = prim;
	rs->nroots = nroots;
	rs->gfpoly = gfpoly;
	rs->gffunc = gffunc;

	/* Allocate the arrays */
	rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
	if (rs->alpha_to == NULL)
		goto err;

	rs->index_of = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
	if (rs->index_of == NULL)
		goto err;

	rs->genpoly = kmalloc_array(rs->nroots + 1, sizeof(uint16_t), gfp);
	if(rs->genpoly == NULL)
		goto err;

	/* Generate Galois field lookup tables */
	rs->index_of[0] = rs->nn;	/* log(zero) = -inf */
	rs->alpha_to[rs->nn] = 0;	/* alpha**-inf = 0 */
	if (gfpoly) {
		sr = 1;
		for (i = 0; i < rs->nn; i++) {
			rs->index_of[sr] = i;
			rs->alpha_to[i] = sr;
			sr <<= 1;
			if (sr & (1 << symsize))
				sr ^= gfpoly;
			sr &= rs->nn;
		}
	} else {
		sr = gffunc(0);
		for (i = 0; i < rs->nn; i++) {
			rs->index_of[sr] = i;
			rs->alpha_to[i] = sr;
			sr = gffunc(sr);
		}
	}
	/* If it's not primitive, exit */
	if(sr != rs->alpha_to[0])
		goto err;

	/* Find prim-th root of 1, used in decoding */
	for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
	/* prim-th root of 1, index form */
	rs->iprim = iprim / prim;

	/* Form RS code generator polynomial from its roots */
	rs->genpoly[0] = 1;
	for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
		rs->genpoly[i + 1] = 1;
		/* Multiply rs->genpoly[] by  @**(root + x) */
		for (j = i; j > 0; j--) {
			if (rs->genpoly[j] != 0) {
				rs->genpoly[j] = rs->genpoly[j -1] ^
					rs->alpha_to[rs_modnn(rs,
					rs->index_of[rs->genpoly[j]] + root)];
			} else
				rs->genpoly[j] = rs->genpoly[j - 1];
		}
		/* rs->genpoly[0] can never be zero */
		rs->genpoly[0] =
			rs->alpha_to[rs_modnn(rs,
				rs->index_of[rs->genpoly[0]] + root)];
	}
	/* convert rs->genpoly[] to index form for quicker encoding */
	for (i = 0; i <= nroots; i++)
		rs->genpoly[i] = rs->index_of[rs->genpoly[i]];

	rs->users = 1;
	list_add(&rs->list, &codec_list);
	return rs;

err:
	kfree(rs->genpoly);
	kfree(rs->index_of);
	kfree(rs->alpha_to);
	kfree(rs);
	return NULL;
}


/**
 *  free_rs - Free the rs control structure
 *  @rs:	The control structure which is not longer used by the
 *		caller
 *
 * Free the control structure. If @rs is the last user of the associated
 * codec, free the codec as well.
 */
void free_rs(struct rs_control *rs)
{
	struct rs_codec *cd;

	if (!rs)
		return;

	cd = rs->codec;
	mutex_lock(&rslistlock);
	cd->users--;
	if(!cd->users) {
		list_del(&cd->list);
		kfree(cd->alpha_to);
		kfree(cd->index_of);
		kfree(cd->genpoly);
		kfree(cd);
	}
	mutex_unlock(&rslistlock);
	kfree(rs);
}
EXPORT_SYMBOL_GPL(free_rs);

/**
 * init_rs_internal - Allocate rs control, find a matching codec or allocate a new one
 *  @symsize:	the symbol size (number of bits)
 *  @gfpoly:	the extended Galois field generator polynomial coefficients,
 *		with the 0th coefficient in the low order bit. The polynomial
 *		must be primitive;
 *  @gffunc:	pointer to function to generate the next field element,
 *		or the multiplicative identity element if given 0.  Used
 *		instead of gfpoly if gfpoly is 0
 *  @fcr:	the first consecutive root of the rs code generator polynomial
 *		in index form
 *  @prim:	primitive element to generate polynomial roots
 *  @nroots:	RS code generator polynomial degree (number of roots)
 *  @gfp:	GFP_ flags for allocations
 */
static struct rs_control *init_rs_internal(int symsize, int gfpoly,
					   int (*gffunc)(int), int fcr,
					   int prim, int nroots, gfp_t gfp)
{
	struct list_head *tmp;
	struct rs_control *rs;
	unsigned int bsize;

	/* Sanity checks */
	if (symsize < 1)
		return NULL;
	if (fcr < 0 || fcr >= (1<<symsize))
		return NULL;
	if (prim <= 0 || prim >= (1<<symsize))
		return NULL;
	if (nroots < 0 || nroots >= (1<<symsize))
		return NULL;

	/*
	 * The decoder needs buffers in each control struct instance to
	 * avoid variable size or large fixed size allocations on
	 * stack. Size the buffers to arrays of [nroots + 1].
	 */
	bsize = sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS * (nroots + 1);
	rs = kzalloc(sizeof(*rs) + bsize, gfp);
	if (!rs)
		return NULL;

	mutex_lock(&rslistlock);

	/* Walk through the list and look for a matching entry */
	list_for_each(tmp, &codec_list) {
		struct rs_codec *cd = list_entry(tmp, struct rs_codec, list);

		if (symsize != cd->mm)
			continue;
		if (gfpoly != cd->gfpoly)
			continue;
		if (gffunc != cd->gffunc)
			continue;
		if (fcr != cd->fcr)
			continue;
		if (prim != cd->prim)
			continue;
		if (nroots != cd->nroots)
			continue;
		/* We have a matching one already */
		cd->users++;
		rs->codec = cd;
		goto out;
	}

	/* Create a new one */
	rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
	if (!rs->codec) {
		kfree(rs);
		rs = NULL;
	}
out:
	mutex_unlock(&rslistlock);
	return rs;
}

/**
 * init_rs_gfp - Create a RS control struct and initialize it
 *  @symsize:	the symbol size (number of bits)
 *  @gfpoly:	the extended Galois field generator polynomial coefficients,
 *		with the 0th coefficient in the low order bit. The polynomial
 *		must be primitive;
 *  @fcr:	the first consecutive root of the rs code generator polynomial
 *		in index form
 *  @prim:	primitive element to generate polynomial roots
 *  @nroots:	RS code generator polynomial degree (number of roots)
 *  @gfp:	Memory allocation flags.
 */
struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
			       int nroots, gfp_t gfp)
{
	return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
}
EXPORT_SYMBOL_GPL(init_rs_gfp);

/**
 * init_rs_non_canonical - Allocate rs control struct for fields with
 *                         non-canonical representation
 *  @symsize:	the symbol size (number of bits)
 *  @gffunc:	pointer to function to generate the next field element,
 *		or the multiplicative identity element if given 0.  Used
 *		instead of gfpoly if gfpoly is 0
 *  @fcr:	the first consecutive root of the rs code generator polynomial
 *		in index form
 *  @prim:	primitive element to generate polynomial roots
 *  @nroots:	RS code generator polynomial degree (number of roots)
 */
struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
					 int fcr, int prim, int nroots)
{
	return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
				GFP_KERNEL);
}
EXPORT_SYMBOL_GPL(init_rs_non_canonical);

#ifdef CONFIG_REED_SOLOMON_ENC8
/**
 *  encode_rs8 - Calculate the parity for data values (8bit data width)
 *  @rsc:	the rs control structure
 *  @data:	data field of a given type
 *  @len:	data length
 *  @par:	parity data, must be initialized by caller (usually all 0)
 *  @invmsk:	invert data mask (will be xored on data)
 *
 *  The parity uses a uint16_t data type to enable
 *  symbol size > 8. The calling code must take care of encoding of the
 *  syndrome result for storage itself.
 */
int encode_rs8(struct rs_control *rsc, uint8_t *data, int len, uint16_t *par,
	       uint16_t invmsk)
{
#include "encode_rs.c"
}
EXPORT_SYMBOL_GPL(encode_rs8);
#endif

#ifdef CONFIG_REED_SOLOMON_DEC8
/**
 *  decode_rs8 - Decode codeword (8bit data width)
 *  @rsc:	the rs control structure
 *  @data:	data field of a given type
 *  @par:	received parity data field
 *  @len:	data length
 *  @s: 	syndrome data field, must be in index form
 *		(if NULL, syndrome is calculated)
 *  @no_eras:	number of erasures
 *  @eras_pos:	position of erasures, can be NULL
 *  @invmsk:	invert data mask (will be xored on data, not on parity!)
 *  @corr:	buffer to store correction bitmask on eras_pos
 *
 *  The syndrome and parity uses a uint16_t data type to enable
 *  symbol size > 8. The calling code must take care of decoding of the
 *  syndrome result and the received parity before calling this code.
 *
 *  Note: The rs_control struct @rsc contains buffers which are used for
 *  decoding, so the caller has to ensure that decoder invocations are
 *  serialized.
 *
 *  Returns the number of corrected symbols or -EBADMSG for uncorrectable
 *  errors. The count includes errors in the parity.
 */
int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len,
	       uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
	       uint16_t *corr)
{
#include "decode_rs.c"
}
EXPORT_SYMBOL_GPL(decode_rs8);
#endif

#ifdef CONFIG_REED_SOLOMON_ENC16
/**
 *  encode_rs16 - Calculate the parity for data values (16bit data width)
 *  @rsc:	the rs control structure
 *  @data:	data field of a given type
 *  @len:	data length
 *  @par:	parity data, must be initialized by caller (usually all 0)
 *  @invmsk:	invert data mask (will be xored on data, not on parity!)
 *
 *  Each field in the data array contains up to symbol size bits of valid data.
 */
int encode_rs16(struct rs_control *rsc, uint16_t *data, int len, uint16_t *par,
	uint16_t invmsk)
{
#include "encode_rs.c"
}
EXPORT_SYMBOL_GPL(encode_rs16);
#endif

#ifdef CONFIG_REED_SOLOMON_DEC16
/**
 *  decode_rs16 - Decode codeword (16bit data width)
 *  @rsc:	the rs control structure
 *  @data:	data field of a given type
 *  @par:	received parity data field
 *  @len:	data length
 *  @s: 	syndrome data field, must be in index form
 *		(if NULL, syndrome is calculated)
 *  @no_eras:	number of erasures
 *  @eras_pos:	position of erasures, can be NULL
 *  @invmsk:	invert data mask (will be xored on data, not on parity!)
 *  @corr:	buffer to store correction bitmask on eras_pos
 *
 *  Each field in the data array contains up to symbol size bits of valid data.
 *
 *  Note: The rc_control struct @rsc contains buffers which are used for
 *  decoding, so the caller has to ensure that decoder invocations are
 *  serialized.
 *
 *  Returns the number of corrected symbols or -EBADMSG for uncorrectable
 *  errors. The count includes errors in the parity.
 */
int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len,
		uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
		uint16_t *corr)
{
#include "decode_rs.c"
}
EXPORT_SYMBOL_GPL(decode_rs16);
#endif

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
MODULE_AUTHOR("Phil Karn, Thomas Gleixner");