"Fossies" - the Fresh Open Source Software Archive 
Member "cryptsetup-2.4.3/lib/verity/rs_encode_char.c" (13 Jan 2022, 4851 Bytes) of package /linux/misc/cryptsetup-2.4.3.tar.xz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "rs_encode_char.c" see the
Fossies "Dox" file reference documentation.
1 /*
2 * Reed-Solomon encoder, based on libfec
3 *
4 * Copyright (C) 2002, Phil Karn, KA9Q
5 * libcryptsetup modifications
6 * Copyright (C) 2017-2021 Red Hat, Inc. All rights reserved.
7 *
8 * This file is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This file is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this file; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #include <string.h>
24 #include <stdlib.h>
25
26 #include "rs.h"
27
28 /* Initialize a Reed-Solomon codec
29 * symsize = symbol size, bits
30 * gfpoly = Field generator polynomial coefficients
31 * fcr = first root of RS code generator polynomial, index form
32 * prim = primitive element to generate polynomial roots
33 * nroots = RS code generator polynomial degree (number of roots)
34 * pad = padding bytes at front of shortened block
35 */
36 struct rs *init_rs_char(int symsize, int gfpoly, int fcr, int prim, int nroots, int pad)
37 {
38 struct rs *rs;
39 int i, j, sr, root, iprim;
40
41 /* Check parameter ranges */
42 if (symsize < 0 || symsize > 8 * (int)sizeof(data_t))
43 return NULL;
44 if (fcr < 0 || fcr >= (1<<symsize))
45 return NULL;
46 if (prim <= 0 || prim >= (1<<symsize))
47 return NULL;
48 if (nroots < 0 || nroots >= (1<<symsize))
49 return NULL; /* Can't have more roots than symbol values! */
50
51 if (pad < 0 || pad >= ((1<<symsize) - 1 - nroots))
52 return NULL; /* Too much padding */
53
54 rs = calloc(1, sizeof(struct rs));
55 if (rs == NULL)
56 return NULL;
57
58 rs->mm = symsize;
59 rs->nn = (1<<symsize) - 1;
60 rs->pad = pad;
61
62 rs->alpha_to = malloc(sizeof(data_t) * (rs->nn + 1));
63 if (rs->alpha_to == NULL) {
64 free(rs);
65 return NULL;
66 }
67 rs->index_of = malloc(sizeof(data_t) * (rs->nn + 1));
68 if (rs->index_of == NULL) {
69 free(rs->alpha_to);
70 free(rs);
71 return NULL;
72 }
73 memset(rs->index_of, 0, sizeof(data_t) * (rs->nn + 1));
74
75 /* Generate Galois field lookup tables */
76 rs->index_of[0] = A0; /* log(zero) = -inf */
77 rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
78 sr = 1;
79 for (i = 0; i < rs->nn; i++) {
80 rs->index_of[sr] = i;
81 rs->alpha_to[i] = sr;
82 sr <<= 1;
83 if(sr & (1<<symsize))
84 sr ^= gfpoly;
85 sr &= rs->nn;
86 }
87 if (sr != 1) {
88 /* field generator polynomial is not primitive! */
89 free(rs->alpha_to);
90 free(rs->index_of);
91 free(rs);
92 return NULL;
93 }
94
95 /* Form RS code generator polynomial from its roots */
96 rs->genpoly = malloc(sizeof(data_t) * (nroots + 1));
97 if (rs->genpoly == NULL) {
98 free(rs->alpha_to);
99 free(rs->index_of);
100 free(rs);
101 return NULL;
102 }
103
104 rs->fcr = fcr;
105 rs->prim = prim;
106 rs->nroots = nroots;
107
108 /* Find prim-th root of 1, used in decoding */
109 for (iprim = 1; (iprim % prim) != 0; iprim += rs->nn)
110 ;
111 rs->iprim = iprim / prim;
112
113 rs->genpoly[0] = 1;
114 for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
115 rs->genpoly[i + 1] = 1;
116
117 /* Multiply rs->genpoly[] by @**(root + x) */
118 for (j = i; j > 0; j--){
119 if (rs->genpoly[j] != 0)
120 rs->genpoly[j] = rs->genpoly[j - 1] ^ rs->alpha_to[modnn(rs, rs->index_of[rs->genpoly[j]] + root)];
121 else
122 rs->genpoly[j] = rs->genpoly[j - 1];
123 }
124 /* rs->genpoly[0] can never be zero */
125 rs->genpoly[0] = rs->alpha_to[modnn(rs, rs->index_of[rs->genpoly[0]] + root)];
126 }
127 /* convert rs->genpoly[] to index form for quicker encoding */
128 for (i = 0; i <= nroots; i++)
129 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
130
131 return rs;
132 }
133
134 void free_rs_char(struct rs *rs)
135 {
136 if (!rs)
137 return;
138
139 free(rs->alpha_to);
140 free(rs->index_of);
141 free(rs->genpoly);
142 free(rs);
143 }
144
145 void encode_rs_char(struct rs *rs, data_t *data, data_t *parity)
146 {
147 int i, j;
148 data_t feedback;
149
150 memset(parity, 0, rs->nroots * sizeof(data_t));
151
152 for (i = 0; i < rs->nn - rs->nroots - rs->pad; i++) {
153 feedback = rs->index_of[data[i] ^ parity[0]];
154 if (feedback != A0) {
155 /* feedback term is non-zero */
156 #ifdef UNNORMALIZED
157 /* This line is unnecessary when GENPOLY[NROOTS] is unity, as it must
158 * always be for the polynomials constructed by init_rs() */
159 feedback = modnn(rs, rs->nn - rs->genpoly[rs->nroots] + feedback);
160 #endif
161 for (j = 1; j < rs->nroots; j++)
162 parity[j] ^= rs->alpha_to[modnn(rs, feedback + rs->genpoly[rs->nroots - j])];
163 }
164
165 /* Shift */
166 memmove(&parity[0], &parity[1], sizeof(data_t) * (rs->nroots - 1));
167
168 if (feedback != A0)
169 parity[rs->nroots - 1] = rs->alpha_to[modnn(rs, feedback + rs->genpoly[0])];
170 else
171 parity[rs->nroots - 1] = 0;
172 }
173 }