]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - lib/reed_solomon/reed_solomon.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Generic Reed Solomon encoder / decoder library
5 * Copyright (C) 2004 Thomas Gleixner (tglx@linutronix.de)
7 * Reed Solomon code lifted from reed solomon library written by Phil Karn
8 * Copyright 2002 Phil Karn, KA9Q
12 * The generic Reed Solomon library provides runtime configurable
13 * encoding / decoding of RS codes.
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.
24 * The encoding puts the calculated syndrome into a given syndrome buffer.
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.
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>
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
);
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
67 * Allocate a codec structure and the polynom arrays for faster
68 * en/decoding. Fill the arrays according to the given parameters.
70 static struct rs_codec
*codec_init(int symsize
, int gfpoly
, int (*gffunc
)(int),
71 int fcr
, int prim
, int nroots
, gfp_t gfp
)
73 int i
, j
, sr
, root
, iprim
;
76 rs
= kzalloc(sizeof(*rs
), gfp
);
80 INIT_LIST_HEAD(&rs
->list
);
83 rs
->nn
= (1 << symsize
) - 1;
90 /* Allocate the arrays */
91 rs
->alpha_to
= kmalloc_array(rs
->nn
+ 1, sizeof(uint16_t), gfp
);
92 if (rs
->alpha_to
== NULL
)
95 rs
->index_of
= kmalloc_array(rs
->nn
+ 1, sizeof(uint16_t), gfp
);
96 if (rs
->index_of
== NULL
)
99 rs
->genpoly
= kmalloc_array(rs
->nroots
+ 1, sizeof(uint16_t), gfp
);
100 if(rs
->genpoly
== NULL
)
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 */
108 for (i
= 0; i
< rs
->nn
; i
++) {
109 rs
->index_of
[sr
] = i
;
110 rs
->alpha_to
[i
] = sr
;
112 if (sr
& (1 << symsize
))
118 for (i
= 0; i
< rs
->nn
; i
++) {
119 rs
->index_of
[sr
] = i
;
120 rs
->alpha_to
[i
] = sr
;
124 /* If it's not primitive, exit */
125 if(sr
!= rs
->alpha_to
[0])
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
;
133 /* Form RS code generator polynomial from its roots */
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
)];
144 rs
->genpoly
[j
] = rs
->genpoly
[j
- 1];
146 /* rs->genpoly[0] can never be zero */
148 rs
->alpha_to
[rs_modnn(rs
,
149 rs
->index_of
[rs
->genpoly
[0]] + root
)];
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
]];
156 list_add(&rs
->list
, &codec_list
);
169 * free_rs - Free the rs control structure
170 * @rs: The control structure which is not longer used by the
173 * Free the control structure. If @rs is the last user of the associated
174 * codec, free the codec as well.
176 void free_rs(struct rs_control
*rs
)
184 mutex_lock(&rslistlock
);
193 mutex_unlock(&rslistlock
);
196 EXPORT_SYMBOL_GPL(free_rs
);
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
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
209 * @prim: primitive element to generate polynomial roots
210 * @nroots: RS code generator polynomial degree (number of roots)
211 * @gfp: GFP_ flags for allocations
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
)
217 struct list_head
*tmp
;
218 struct rs_control
*rs
;
224 if (fcr
< 0 || fcr
>= (1<<symsize
))
226 if (prim
<= 0 || prim
>= (1<<symsize
))
228 if (nroots
< 0 || nroots
>= (1<<symsize
))
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].
236 bsize
= sizeof(uint16_t) * RS_DECODE_NUM_BUFFERS
* (nroots
+ 1);
237 rs
= kzalloc(sizeof(*rs
) + bsize
, gfp
);
241 mutex_lock(&rslistlock
);
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
);
247 if (symsize
!= cd
->mm
)
249 if (gfpoly
!= cd
->gfpoly
)
251 if (gffunc
!= cd
->gffunc
)
255 if (prim
!= cd
->prim
)
257 if (nroots
!= cd
->nroots
)
259 /* We have a matching one already */
265 /* Create a new one */
266 rs
->codec
= codec_init(symsize
, gfpoly
, gffunc
, fcr
, prim
, nroots
, gfp
);
272 mutex_unlock(&rslistlock
);
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
282 * @fcr: the first consecutive root of the rs code generator polynomial
284 * @prim: primitive element to generate polynomial roots
285 * @nroots: RS code generator polynomial degree (number of roots)
286 * @gfp: Memory allocation flags.
288 struct rs_control
*init_rs_gfp(int symsize
, int gfpoly
, int fcr
, int prim
,
289 int nroots
, gfp_t gfp
)
291 return init_rs_internal(symsize
, gfpoly
, NULL
, fcr
, prim
, nroots
, gfp
);
293 EXPORT_SYMBOL_GPL(init_rs_gfp
);
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
304 * @prim: primitive element to generate polynomial roots
305 * @nroots: RS code generator polynomial degree (number of roots)
307 struct rs_control
*init_rs_non_canonical(int symsize
, int (*gffunc
)(int),
308 int fcr
, int prim
, int nroots
)
310 return init_rs_internal(symsize
, 0, gffunc
, fcr
, prim
, nroots
,
313 EXPORT_SYMBOL_GPL(init_rs_non_canonical
);
315 #ifdef CONFIG_REED_SOLOMON_ENC8
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
321 * @par: parity data, must be initialized by caller (usually all 0)
322 * @invmsk: invert data mask (will be xored on data)
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.
328 int encode_rs8(struct rs_control
*rsc
, uint8_t *data
, int len
, uint16_t *par
,
331 #include "encode_rs.c"
333 EXPORT_SYMBOL_GPL(encode_rs8
);
336 #ifdef CONFIG_REED_SOLOMON_DEC8
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
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
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.
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
358 * Returns the number of corrected symbols or -EBADMSG for uncorrectable
359 * errors. The count includes errors in the parity.
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
,
365 #include "decode_rs.c"
367 EXPORT_SYMBOL_GPL(decode_rs8
);
370 #ifdef CONFIG_REED_SOLOMON_ENC16
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
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!)
379 * Each field in the data array contains up to symbol size bits of valid data.
381 int encode_rs16(struct rs_control
*rsc
, uint16_t *data
, int len
, uint16_t *par
,
384 #include "encode_rs.c"
386 EXPORT_SYMBOL_GPL(encode_rs16
);
389 #ifdef CONFIG_REED_SOLOMON_DEC16
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
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
403 * Each field in the data array contains up to symbol size bits of valid data.
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
409 * Returns the number of corrected symbols or -EBADMSG for uncorrectable
410 * errors. The count includes errors in the parity.
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
,
416 #include "decode_rs.c"
418 EXPORT_SYMBOL_GPL(decode_rs16
);
421 MODULE_LICENSE("GPL");
422 MODULE_DESCRIPTION("Reed Solomon encoder/decoder");
423 MODULE_AUTHOR("Phil Karn, Thomas Gleixner");