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
|
// SPDX-License-Identifier: LGPL-2.1-or-later
/*
* Reed-Solomon encoder, based on libfec
*
* Copyright (C) 2002, Phil Karn, KA9Q
* libcryptsetup modifications
* Copyright (C) 2017-2025 Red Hat, Inc. All rights reserved.
*/
#include <string.h>
#include <stdlib.h>
#include "rs.h"
/* Initialize a Reed-Solomon codec
* symsize = symbol size, bits
* gfpoly = Field generator polynomial coefficients
* 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)
* pad = padding bytes at front of shortened block
*/
struct rs *init_rs_char(int symsize, int gfpoly, int fcr, int prim, int nroots, int pad)
{
struct rs *rs;
int i, j, sr, root, iprim;
/* Check parameter ranges */
if (symsize < 0 || symsize > 8 * (int)sizeof(data_t))
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; /* Can't have more roots than symbol values! */
if (pad < 0 || pad >= ((1<<symsize) - 1 - nroots))
return NULL; /* Too much padding */
rs = calloc(1, sizeof(struct rs));
if (rs == NULL)
return NULL;
rs->mm = symsize;
rs->nn = (1<<symsize) - 1;
rs->pad = pad;
rs->alpha_to = malloc(sizeof(data_t) * (rs->nn + 1));
if (rs->alpha_to == NULL) {
free(rs);
return NULL;
}
rs->index_of = malloc(sizeof(data_t) * (rs->nn + 1));
if (rs->index_of == NULL) {
free(rs->alpha_to);
free(rs);
return NULL;
}
memset(rs->index_of, 0, sizeof(data_t) * (rs->nn + 1));
/* Generate Galois field lookup tables */
rs->index_of[0] = A0; /* log(zero) = -inf */
rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
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;
}
if (sr != 1) {
/* field generator polynomial is not primitive! */
free(rs->alpha_to);
free(rs->index_of);
free(rs);
return NULL;
}
/* Form RS code generator polynomial from its roots */
rs->genpoly = malloc(sizeof(data_t) * (nroots + 1));
if (rs->genpoly == NULL) {
free(rs->alpha_to);
free(rs->index_of);
free(rs);
return NULL;
}
rs->fcr = fcr;
rs->prim = prim;
rs->nroots = nroots;
/* Find prim-th root of 1, used in decoding */
for (iprim = 1; (iprim % prim) != 0; iprim += rs->nn)
;
rs->iprim = iprim / prim;
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[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[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]];
return rs;
}
void free_rs_char(struct rs *rs)
{
if (!rs)
return;
free(rs->alpha_to);
free(rs->index_of);
free(rs->genpoly);
free(rs);
}
void encode_rs_char(struct rs *rs, data_t *data, data_t *parity)
{
int i, j;
data_t feedback;
memset(parity, 0, rs->nroots * sizeof(data_t));
for (i = 0; i < rs->nn - rs->nroots - rs->pad; i++) {
feedback = rs->index_of[data[i] ^ parity[0]];
if (feedback != A0) {
/* feedback term is non-zero */
#ifdef UNNORMALIZED
/* This line is unnecessary when GENPOLY[NROOTS] is unity, as it must
* always be for the polynomials constructed by init_rs() */
feedback = modnn(rs, rs->nn - rs->genpoly[rs->nroots] + feedback);
#endif
for (j = 1; j < rs->nroots; j++)
parity[j] ^= rs->alpha_to[modnn(rs, feedback + rs->genpoly[rs->nroots - j])];
}
/* Shift */
memmove(&parity[0], &parity[1], sizeof(data_t) * (rs->nroots - 1));
if (feedback != A0)
parity[rs->nroots - 1] = rs->alpha_to[modnn(rs, feedback + rs->genpoly[0])];
else
parity[rs->nroots - 1] = 0;
}
}
|
