Line data Source code
1 : /*
2 : * libpoporon - decode.c
3 : *
4 : * Copyright (c) 2025 Go Kudo
5 : *
6 : * This library is licensed under the BSD 3-Clause License.
7 : * For license details, please refer to the LICENSE file.
8 : *
9 : * SPDX-FileCopyrightText: Go Kudo <zeriyoshi@gmail.com>
10 : * SPDX-License-Identifier: BSD-3-Clause
11 : */
12 :
13 : #include "poporon_internal.h"
14 :
15 20 : static inline bool error_correction_u8(
16 : poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, uint16_t *syndrome_ptr,
17 : uint32_t erasure_count, uint32_t *erasure_positions, uint16_t *corrections,
18 : int16_t padding_length,
19 : size_t *errors_corrected
20 : ) {
21 : uint32_t iteration_count, polynomial_degree;
22 : uint16_t error_locator_degree, error_evaluator_degree, polynomial_evaluation;
23 : uint16_t temp_value, numerator_value, second_numerator, denominator_value, discrepancy;
24 : uint16_t error_count;
25 : int16_t i, j, k;
26 : uint8_t poly_term;
27 : bool success;
28 :
29 20 : success = true;
30 :
31 20 : pmemset(&pprn->buffer->error_locator[1], 0, pprn->rs->num_roots * sizeof(pprn->buffer->error_locator[0]));
32 20 : pprn->buffer->error_locator[0] = 1;
33 :
34 20 : if (erasure_count > 0) {
35 1 : pprn->buffer->error_locator[1] = pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->primitive_element * (pprn->rs->gf->field_size - 1 - (erasure_positions[0] + padding_length)))];
36 16 : for (i = 1; i < erasure_count; i++) {
37 15 : poly_term = gf_mod(pprn->rs->gf, pprn->rs->primitive_element * (pprn->rs->gf->field_size - 1 - (erasure_positions[i] + padding_length)));
38 150 : for (j = i + 1; j > 0; j--) {
39 135 : temp_value = pprn->rs->gf->exp2log[pprn->buffer->error_locator[j - 1]];
40 135 : if (temp_value != pprn->rs->gf->field_size) {
41 135 : pprn->buffer->error_locator[j] ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, poly_term + temp_value)];
42 : }
43 : }
44 : }
45 : }
46 :
47 680 : for (i = 0; i < pprn->rs->num_roots + 1; i++) {
48 660 : pprn->buffer->coefficients[i] = pprn->rs->gf->exp2log[pprn->buffer->error_locator[i]];
49 : }
50 :
51 : /* Berlekamp-Massey */
52 20 : iteration_count = erasure_count;
53 20 : polynomial_degree = erasure_count;
54 644 : while (++iteration_count <= pprn->rs->num_roots) {
55 624 : discrepancy = 0;
56 11048 : for (i = 0; i < iteration_count; i++) {
57 10424 : if ((pprn->buffer->error_locator[i] != 0) && (syndrome_ptr[iteration_count - i - 1] != pprn->rs->gf->field_size)) {
58 4031 : discrepancy ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[pprn->buffer->error_locator[i]] + syndrome_ptr[iteration_count - i - 1])];
59 : }
60 : }
61 624 : discrepancy = pprn->rs->gf->exp2log[discrepancy];
62 :
63 624 : if (discrepancy == pprn->rs->gf->field_size) {
64 451 : pmemmove(&pprn->buffer->coefficients[1], pprn->buffer->coefficients, pprn->rs->num_roots * sizeof(pprn->buffer->coefficients[0]));
65 451 : pprn->buffer->coefficients[0] = pprn->rs->gf->field_size;
66 : } else {
67 173 : pprn->buffer->polynomial[0] = pprn->buffer->error_locator[0];
68 :
69 5709 : for (i = 0; i < pprn->rs->num_roots; i++) {
70 5536 : if (pprn->buffer->coefficients[i] != pprn->rs->gf->field_size) {
71 1672 : pprn->buffer->polynomial[i + 1] = pprn->buffer->error_locator[i + 1] ^
72 836 : pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, discrepancy + pprn->buffer->coefficients[i])];
73 : } else {
74 4700 : pprn->buffer->polynomial[i + 1] = pprn->buffer->error_locator[i + 1];
75 : }
76 : }
77 :
78 173 : if (2 * polynomial_degree <= iteration_count + erasure_count - 1) {
79 154 : polynomial_degree = iteration_count + erasure_count - polynomial_degree;
80 5236 : for (i = 0; i <= pprn->rs->num_roots; i++) {
81 10164 : pprn->buffer->coefficients[i] = (pprn->buffer->error_locator[i] == 0) ?
82 4131 : pprn->rs->gf->field_size :
83 951 : gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[pprn->buffer->error_locator[i]] - discrepancy + pprn->rs->gf->field_size);
84 : }
85 : } else {
86 19 : pmemmove(&pprn->buffer->coefficients[1], pprn->buffer->coefficients, pprn->rs->num_roots * sizeof(pprn->buffer->coefficients[0]));
87 19 : pprn->buffer->coefficients[0] = pprn->rs->gf->field_size;
88 : }
89 :
90 173 : pmemcpy(pprn->buffer->error_locator, pprn->buffer->polynomial, (pprn->rs->num_roots + 1) * sizeof(pprn->buffer->polynomial[0]));
91 : }
92 : }
93 :
94 20 : error_locator_degree = 0;
95 680 : for (i = 0; i < pprn->rs->num_roots + 1; i++) {
96 660 : pprn->buffer->error_locator[i] = pprn->rs->gf->exp2log[pprn->buffer->error_locator[i]];
97 :
98 660 : if (pprn->buffer->error_locator[i] != pprn->rs->gf->field_size) {
99 189 : error_locator_degree = i;
100 : }
101 : }
102 :
103 20 : if (error_locator_degree == 0) {
104 0 : return false;
105 : }
106 :
107 : /* Chien search */
108 20 : pmemcpy(&pprn->buffer->register_coefficients[1], &pprn->buffer->error_locator[1], pprn->rs->num_roots * sizeof(pprn->buffer->register_coefficients[0]));
109 20 : error_count = 0;
110 4045 : for (i = 1, k = pprn->buffer->primitive_inverse - 1; i <= pprn->rs->gf->field_size; i++, k = gf_mod(pprn->rs->gf, k + pprn->buffer->primitive_inverse)) {
111 4045 : polynomial_evaluation = 1;
112 :
113 38471 : for (j = error_locator_degree; j > 0; j--) {
114 34426 : if (pprn->buffer->register_coefficients[j] != pprn->rs->gf->field_size) {
115 34364 : pprn->buffer->register_coefficients[j] = gf_mod(pprn->rs->gf, pprn->buffer->register_coefficients[j] + j);
116 34364 : polynomial_evaluation ^= pprn->rs->gf->log2exp[pprn->buffer->register_coefficients[j]];
117 : }
118 : }
119 :
120 4045 : if (polynomial_evaluation != 0)
121 3890 : continue;
122 :
123 155 : if (k < padding_length) {
124 1 : return false;
125 : }
126 :
127 154 : pprn->buffer->error_roots[error_count] = i;
128 154 : pprn->buffer->error_locations[error_count] = k;
129 154 : if (++error_count == error_locator_degree) {
130 19 : break;
131 : }
132 : }
133 :
134 19 : if (error_locator_degree != error_count) {
135 0 : return false;
136 : }
137 :
138 : /* Forney */
139 19 : error_evaluator_degree = error_locator_degree - 1;
140 173 : for (i = 0; i <= error_evaluator_degree; i++) {
141 154 : temp_value = 0;
142 :
143 1108 : for (j = i; j >= 0; j--) {
144 954 : if ((syndrome_ptr[i - j] != pprn->rs->gf->field_size) && (pprn->buffer->error_locator[j] != pprn->rs->gf->field_size)) {
145 954 : temp_value ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, syndrome_ptr[i - j] + pprn->buffer->error_locator[j])];
146 : }
147 : }
148 :
149 154 : pprn->buffer->error_evaluator[i] = pprn->rs->gf->exp2log[temp_value];
150 : }
151 19 : *errors_corrected = 0;
152 173 : for (j = error_count - 1; j >= 0; j--) {
153 154 : numerator_value = 0;
154 :
155 1908 : for (i = error_evaluator_degree; i >= 0; i--) {
156 1754 : if (pprn->buffer->error_evaluator[i] != pprn->rs->gf->field_size) {
157 910 : numerator_value ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->buffer->error_evaluator[i] + i * pprn->buffer->error_roots[j])];
158 : }
159 : }
160 :
161 154 : if (numerator_value == 0) {
162 0 : pprn->buffer->coefficients[j] = 0;
163 0 : continue;
164 : }
165 :
166 154 : second_numerator = pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->buffer->error_roots[j] * (pprn->rs->first_consective_root - 1) + pprn->rs->gf->field_size)];
167 154 : denominator_value = 0;
168 :
169 1152 : for (i = (error_locator_degree < (pprn->rs->num_roots - 1) ? error_locator_degree : (pprn->rs->num_roots - 1)) & ~1; i >= 0; i -= 2) {
170 998 : if (pprn->buffer->error_locator[i + 1] != pprn->rs->gf->field_size) {
171 910 : denominator_value ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->buffer->error_locator[i + 1] + i * pprn->buffer->error_roots[j])];
172 : }
173 : }
174 :
175 154 : pprn->buffer->coefficients[j] = pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[numerator_value] + pprn->rs->gf->exp2log[second_numerator] + pprn->rs->gf->field_size - pprn->rs->gf->exp2log[denominator_value])];
176 154 : (*errors_corrected)++;
177 : }
178 :
179 : /* Validate */
180 627 : for (i = 0; i < pprn->rs->num_roots; i++) {
181 608 : temp_value = 0;
182 :
183 5536 : for (j = 0; j < error_count; j++) {
184 4928 : if (pprn->buffer->coefficients[j] == 0) {
185 0 : continue;
186 : }
187 :
188 4928 : k = (pprn->rs->first_consective_root + i) * pprn->rs->primitive_element * (pprn->rs->gf->field_size - pprn->buffer->error_locations[j] - 1);
189 4928 : temp_value ^= pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[pprn->buffer->coefficients[j]] + k)];
190 : }
191 :
192 608 : if (temp_value != pprn->rs->gf->log2exp[syndrome_ptr[i]]) {
193 0 : return false;
194 : }
195 : }
196 :
197 : /* Correction */
198 19 : if (corrections && erasure_positions) {
199 17 : for (i = 0; i < error_count; i++) {
200 16 : data[erasure_positions[i]] ^= pprn->buffer->coefficients[i];
201 : }
202 18 : } else if (data && parity) {
203 156 : for (i = 0; i < error_count; i++) {
204 138 : if (pprn->buffer->error_locations[i] < (pprn->rs->gf->field_size - pprn->rs->num_roots)) {
205 138 : data[pprn->buffer->error_locations[i] - padding_length] ^= pprn->buffer->coefficients[i];
206 : }
207 : else {
208 0 : parity[pprn->buffer->error_locations[i] - padding_length - size] ^= pprn->buffer->coefficients[i];
209 : }
210 : }
211 : }
212 :
213 19 : return true;
214 : }
215 :
216 21 : static inline bool calculate_syndrome_u8(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, uint16_t *syndrome)
217 : {
218 : int16_t i, j;
219 : uint16_t syndrome_error_flag;
220 :
221 21 : syndrome_error_flag = 0;
222 :
223 : /* Calculate syndrome from data */
224 693 : for (i = 0; i < pprn->rs->num_roots; i++) {
225 672 : syndrome[i] = data[0] & ((uint16_t)pprn->rs->gf->field_size);
226 : }
227 :
228 1344 : for (j = 1; j < size; j++) {
229 43659 : for (i = 0; i < pprn->rs->num_roots; i++) {
230 42336 : if (syndrome[i] == 0) {
231 159 : syndrome[i] = data[j] & ((uint16_t)pprn->rs->gf->field_size);
232 : } else {
233 84354 : syndrome[i] = (data[j] & ((uint16_t)pprn->rs->gf->field_size)) ^
234 42177 : pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[syndrome[i]] + (pprn->rs->first_consective_root + i) * pprn->rs->primitive_element)];
235 : }
236 : }
237 : }
238 :
239 : /* Calculate syndrome from parity */
240 693 : for (j = 0; j < pprn->rs->num_roots; j++) {
241 22176 : for (i = 0; i < pprn->rs->num_roots; i++) {
242 21504 : if (syndrome[i] == 0) {
243 90 : syndrome[i] = parity[j] & ((uint16_t)pprn->rs->gf->field_size);
244 : } else {
245 42828 : syndrome[i] = (parity[j] & ((uint16_t)pprn->rs->gf->field_size)) ^
246 21414 : pprn->rs->gf->log2exp[gf_mod(pprn->rs->gf, pprn->rs->gf->exp2log[syndrome[i]] + (pprn->rs->first_consective_root + i) * pprn->rs->primitive_element)];
247 : }
248 : }
249 : }
250 :
251 693 : for (i = 0; i < pprn->rs->num_roots; i++) {
252 672 : syndrome_error_flag |= syndrome[i];
253 672 : syndrome[i] = pprn->rs->gf->exp2log[syndrome[i]];
254 : }
255 :
256 21 : return syndrome_error_flag != 0;
257 : }
258 :
259 22 : static inline int16_t calculate_padding_length(poporon_t *pprn, size_t size)
260 : {
261 : int16_t padding_length;
262 :
263 22 : padding_length = pprn->rs->gf->field_size - pprn->rs->num_roots - size;
264 :
265 22 : if (padding_length < 0 || padding_length >= pprn->rs->gf->field_size - pprn->rs->num_roots) {
266 0 : return -1;
267 : }
268 :
269 22 : return padding_length;
270 : }
271 :
272 6 : extern bool poporon_decode_u8_with_syndrome(poporon_t *pprn, uint8_t *data, uint8_t *parity, size_t size, uint16_t *syndrome, size_t *corrected_num)
273 : {
274 : size_t errors_corrected;
275 : int16_t padding_length;
276 : uint16_t i;
277 : bool success, has_errors;
278 :
279 6 : errors_corrected = 0;
280 6 : success = false;
281 6 : has_errors = false;
282 :
283 6 : if (!pprn || !data || !parity || !size || !syndrome) {
284 5 : goto finish;
285 : }
286 :
287 1 : padding_length = calculate_padding_length(pprn, size);
288 1 : if (padding_length < 0) {
289 0 : goto finish;
290 : }
291 :
292 33 : for (i = 0; i < pprn->rs->num_roots; i++) {
293 32 : if (syndrome[i] != pprn->rs->gf->field_size) {
294 0 : has_errors = true;
295 0 : break;
296 : }
297 : }
298 :
299 1 : if (has_errors && !error_correction_u8(pprn, data, size, parity, syndrome, 0, NULL, NULL, padding_length, &errors_corrected)) {
300 0 : goto finish;
301 : }
302 :
303 1 : success = true;
304 :
305 6 : finish:
306 6 : if (corrected_num) {
307 6 : *corrected_num = errors_corrected;
308 : }
309 :
310 6 : return success;
311 : }
312 :
313 6 : extern bool poporon_decode_u8_with_erasure(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, poporon_erasure_t *eras, size_t *corrected_num)
314 : {
315 : size_t errors_corrected;
316 : int16_t padding_length;
317 : bool success;
318 :
319 6 : errors_corrected = 0;
320 6 : success = false;
321 :
322 6 : if (!pprn || !data || !parity || !eras || !size) {
323 5 : goto finish;
324 : }
325 :
326 1 : padding_length = calculate_padding_length(pprn, size);
327 1 : if (padding_length < 0) {
328 0 : goto finish;
329 : }
330 :
331 2 : success = !calculate_syndrome_u8(pprn, data, size, parity, pprn->buffer->syndrome)
332 1 : || error_correction_u8(pprn, data, size, parity, pprn->buffer->syndrome, eras->erasure_count, eras->erasure_positions, eras->corrections, padding_length, &errors_corrected);
333 :
334 6 : finish:
335 6 : if (corrected_num) {
336 6 : *corrected_num = errors_corrected;
337 : }
338 :
339 6 : return success;
340 : }
341 :
342 24 : extern bool poporon_decode_u8(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, size_t *corrected_num)
343 : {
344 : size_t errors_corrected;
345 : int16_t padding_length;
346 : bool success;
347 :
348 24 : errors_corrected = 0;
349 24 : success = false;
350 :
351 24 : if (!pprn || !data || !parity || !size) {
352 4 : goto finish;
353 : }
354 :
355 20 : padding_length = calculate_padding_length(pprn, size);
356 20 : if (padding_length < 0) {
357 0 : goto finish;
358 : }
359 :
360 40 : success = !calculate_syndrome_u8(pprn, data, size, parity, pprn->buffer->syndrome)
361 20 : || error_correction_u8(pprn, data, size, parity, pprn->buffer->syndrome, 0, NULL, NULL, padding_length, &errors_corrected);
362 :
363 24 : finish:
364 24 : if (corrected_num) {
365 23 : *corrected_num = errors_corrected;
366 : }
367 :
368 24 : return success;
369 : }
|
