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
|
/*
* Reed-Solomon encoder, based on libfec
*
* Copyright (C) 2002, Phil Karn, KA9Q
* libcryptsetup modifications
* Copyright (C) 2017-2021 Red Hat, Inc. All rights reserved.
*
* This file is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This file is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this file; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
#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;
}
}
|
