Line data Source code
1 : /*
2 : * libpoporon - decode.c
3 : *
4 : * This file is part of libpoporon.
5 : *
6 : * Author: Brian Armstrong (original, libcorrect)
7 : * SPDX-License-Identifier: BSD-3-Clause
8 : */
9 :
10 : #include "internal/common.h"
11 : #include "internal/ldpc.h"
12 : #include "internal/polynomial.h"
13 : #include "internal/rs.h"
14 :
15 : #if POPORON_USE_SIMD
16 : #include "internal/simd.h"
17 : #endif
18 :
19 6 : static inline void rs_decoder_init(poporon_rs_t *rs)
20 : {
21 : uint32_t i;
22 :
23 6 : rs->has_init_decode = true;
24 6 : rs->syndromes = (uint16_t *)pcalloc(rs->num_roots, sizeof(uint16_t));
25 6 : rs->modified_syndromes = (uint16_t *)pcalloc(2 * (size_t)rs->num_roots, sizeof(uint16_t));
26 6 : rs->received_polynomial = polynomial_create(rs->block_length - 1);
27 6 : rs->error_locator = polynomial_create(rs->num_roots);
28 6 : rs->error_locator_log = polynomial_create(rs->num_roots);
29 6 : rs->erasure_locator = polynomial_create(rs->num_roots);
30 6 : rs->last_error_locator = polynomial_create(rs->num_roots);
31 6 : rs->error_evaluator = polynomial_create(rs->num_roots - 1);
32 6 : rs->error_locator_derivative = polynomial_create(rs->num_roots - 1);
33 6 : rs->error_roots = (uint16_t *)pcalloc(2 * (size_t)rs->num_roots, sizeof(uint16_t));
34 6 : rs->error_vals = (uint16_t *)pcalloc(rs->num_roots, sizeof(uint16_t));
35 6 : rs->error_locations = (uint16_t *)pcalloc(rs->num_roots, sizeof(uint16_t));
36 :
37 6 : rs->generator_root_exp = (uint16_t **)pmalloc(rs->num_roots * sizeof(uint16_t *));
38 198 : for (i = 0; i < rs->num_roots; i++) {
39 192 : rs->generator_root_exp[i] = (uint16_t *)pmalloc(rs->block_length * sizeof(uint16_t));
40 192 : polynomial_build_exp_lut(rs->gf, rs->generator_roots[i], rs->block_length - 1, rs->generator_root_exp[i]);
41 : }
42 :
43 6 : rs->element_exp = (uint16_t **)pmalloc(((size_t)rs->gf->field_size + 1) * sizeof(uint16_t *));
44 1542 : for (i = 0; i <= rs->gf->field_size; i++) {
45 1536 : rs->element_exp[i] = (uint16_t *)pmalloc(rs->num_roots * sizeof(uint16_t));
46 1536 : polynomial_build_exp_lut(rs->gf, (uint16_t)i, rs->num_roots - 1, rs->element_exp[i]);
47 : }
48 :
49 6 : rs->init_from_roots_scratch[0] = polynomial_create(rs->num_roots);
50 6 : rs->init_from_roots_scratch[1] = polynomial_create(rs->num_roots);
51 6 : }
52 :
53 25 : static inline bool rs_find_syndromes(poporon_rs_t *rs, uint16_t *syndromes)
54 : {
55 25 : bool all_zero = true;
56 : uint32_t i;
57 :
58 825 : for (i = 0; i < rs->num_roots; i++) {
59 800 : syndromes[i] = polynomial_eval_lut(rs->gf, rs->received_polynomial, rs->generator_root_exp[i]);
60 800 : if (syndromes[i]) {
61 702 : all_zero = false;
62 : }
63 : }
64 :
65 25 : return all_zero;
66 : }
67 :
68 22 : static inline uint32_t rs_find_error_locator(poporon_rs_t *rs, uint32_t num_erasures)
69 : {
70 22 : uint16_t discrepancy, last_discrepancy = 1;
71 : uint32_t temp_order;
72 : uint16_t temp;
73 22 : uint32_t i, j, numerrors = 0, delay_length = 1;
74 :
75 22 : pmemset(rs->error_locator.coeff, 0, (rs->num_roots + 1) * sizeof(uint16_t));
76 22 : rs->error_locator.coeff[0] = 1;
77 22 : rs->error_locator.order = 0;
78 :
79 22 : pmemcpy(rs->last_error_locator.coeff, rs->error_locator.coeff, (rs->num_roots + 1) * sizeof(uint16_t));
80 22 : rs->last_error_locator.order = rs->error_locator.order;
81 :
82 690 : for (i = rs->error_locator.order; i < rs->num_roots - num_erasures; i++) {
83 668 : discrepancy = rs->syndromes[i];
84 4062 : for (j = 1; j <= numerrors; j++) {
85 3394 : discrepancy = field_add(discrepancy, field_mul(rs->gf, rs->error_locator.coeff[j], rs->syndromes[i - j]));
86 : }
87 :
88 668 : if (!discrepancy) {
89 485 : delay_length++;
90 485 : continue;
91 : }
92 :
93 183 : if (2 * numerrors <= i) {
94 1012 : for (j = rs->last_error_locator.order; (int)j >= 0; j--) {
95 850 : rs->last_error_locator.coeff[j + delay_length] = field_div(
96 850 : rs->gf, field_mul(rs->gf, rs->last_error_locator.coeff[j], discrepancy), last_discrepancy);
97 : }
98 470 : for (j = 0; j < delay_length; j++) {
99 308 : rs->last_error_locator.coeff[j] = 0;
100 : }
101 :
102 1320 : for (j = 0; j <= rs->last_error_locator.order + delay_length; j++) {
103 1158 : temp = rs->error_locator.coeff[j];
104 1158 : rs->error_locator.coeff[j] = field_add(rs->error_locator.coeff[j], rs->last_error_locator.coeff[j]);
105 1158 : rs->last_error_locator.coeff[j] = temp;
106 : }
107 :
108 162 : temp_order = rs->error_locator.order;
109 162 : rs->error_locator.order = rs->last_error_locator.order + delay_length;
110 162 : rs->last_error_locator.order = temp_order;
111 :
112 162 : numerrors = i + 1 - numerrors;
113 162 : last_discrepancy = discrepancy;
114 162 : delay_length = 1;
115 :
116 162 : continue;
117 : }
118 :
119 47 : for (j = rs->last_error_locator.order; (int)j >= 0; j--) {
120 26 : rs->error_locator.coeff[j + delay_length] = field_add(
121 26 : rs->error_locator.coeff[j + delay_length],
122 26 : field_div(rs->gf, field_mul(rs->gf, rs->last_error_locator.coeff[j], discrepancy), last_discrepancy));
123 : }
124 :
125 21 : if (rs->last_error_locator.order + delay_length > rs->error_locator.order) {
126 0 : rs->error_locator.order = rs->last_error_locator.order + delay_length;
127 : }
128 :
129 21 : delay_length++;
130 : }
131 :
132 22 : return rs->error_locator.order;
133 : }
134 :
135 22 : static inline bool rs_factorize_error_locator(poporon_rs_t *rs, uint32_t num_skip)
136 : {
137 22 : uint32_t root = num_skip;
138 : uint16_t i;
139 :
140 22 : pmemset(rs->error_roots + num_skip, 0, rs->error_locator_log.order * sizeof(uint16_t));
141 :
142 5654 : for (i = 0; i <= rs->gf->field_size; i++) {
143 5632 : if (!polynomial_eval_log_lut(rs->gf, rs->error_locator_log, rs->element_exp[i])) {
144 149 : rs->error_roots[root] = i;
145 149 : root++;
146 : }
147 : }
148 :
149 22 : return root == rs->error_locator_log.order + num_skip;
150 : }
151 :
152 19 : static inline void rs_find_error_evaluator(poporon_rs_t *rs)
153 : {
154 : polynomial_t syndrome_poly;
155 :
156 19 : syndrome_poly.order = rs->num_roots - 1;
157 19 : syndrome_poly.coeff = rs->syndromes;
158 :
159 19 : pmemset(rs->error_evaluator.coeff, 0, (rs->error_evaluator.order + 1) * sizeof(uint16_t));
160 :
161 19 : polynomial_mul(rs->gf, rs->error_locator, syndrome_poly, rs->error_evaluator);
162 19 : }
163 :
164 21 : static inline void rs_find_error_values(poporon_rs_t *rs, uint32_t num_skip)
165 : {
166 : uint32_t i;
167 : polynomial_t omega;
168 :
169 21 : if (num_skip > 0) {
170 2 : omega.order = rs->num_roots - 1;
171 2 : omega.coeff = rs->modified_syndromes;
172 :
173 2 : if (rs->erasure_locator.order > 0) {
174 2 : rs->error_locator_derivative.order = rs->erasure_locator.order - 1;
175 2 : polynomial_formal_derivative(rs->gf, rs->erasure_locator, rs->error_locator_derivative);
176 : } else {
177 0 : rs->error_locator_derivative.order = 0;
178 0 : rs->error_locator_derivative.coeff[0] = 0;
179 : }
180 :
181 38 : for (i = 0; i < num_skip; i++) {
182 36 : if (rs->error_roots[i] == 0) {
183 0 : continue;
184 : }
185 36 : rs->error_vals[i] =
186 36 : field_mul(rs->gf, field_pow(rs->gf, rs->error_roots[i], (int)rs->first_consecutive_root - 1),
187 36 : field_div(rs->gf, polynomial_eval_lut(rs->gf, omega, rs->element_exp[rs->error_roots[i]]),
188 36 : polynomial_eval_lut(rs->gf, rs->error_locator_derivative,
189 36 : rs->element_exp[rs->error_roots[i]])));
190 : }
191 : }
192 :
193 21 : if (rs->error_locator.order == 0) {
194 2 : return;
195 : }
196 :
197 19 : rs_find_error_evaluator(rs);
198 :
199 19 : rs->error_locator_derivative.order = rs->error_locator.order - 1;
200 19 : polynomial_formal_derivative(rs->gf, rs->error_locator, rs->error_locator_derivative);
201 :
202 167 : for (i = 0; i < rs->error_locator.order; i++) {
203 148 : if (rs->error_roots[i + num_skip] == 0) {
204 0 : continue;
205 : }
206 148 : rs->error_vals[i + num_skip] = field_mul(
207 148 : rs->gf, field_pow(rs->gf, rs->error_roots[i + num_skip], (int)rs->first_consecutive_root - 1),
208 148 : field_div(rs->gf,
209 148 : polynomial_eval_lut(rs->gf, rs->error_evaluator, rs->element_exp[rs->error_roots[i + num_skip]]),
210 148 : polynomial_eval_lut(rs->gf, rs->error_locator_derivative,
211 148 : rs->element_exp[rs->error_roots[i + num_skip]])));
212 : }
213 : }
214 :
215 21 : static inline void rs_find_error_locations(poporon_rs_t *rs, uint32_t num_errors, uint32_t num_skip)
216 : {
217 : uint32_t i;
218 : uint16_t loc, j;
219 :
220 169 : for (i = num_skip; i < num_errors; i++) {
221 148 : if (rs->error_roots[i] == 0) {
222 0 : continue;
223 : }
224 :
225 148 : loc = field_div(rs->gf, 1, rs->error_roots[i]);
226 :
227 21234 : for (j = 0; j <= rs->gf->field_size; j++) {
228 21234 : if (field_pow(rs->gf, j, rs->generator_root_gap) == loc) {
229 148 : rs->error_locations[i] = rs->gf->log[j];
230 148 : break;
231 : }
232 : }
233 : }
234 21 : }
235 :
236 2 : static inline void rs_find_error_roots_from_locations(poporon_rs_t *rs, uint32_t num_errors)
237 : {
238 : uint32_t i;
239 : uint16_t loc;
240 :
241 38 : for (i = 0; i < num_errors; i++) {
242 36 : loc = field_pow(rs->gf, rs->gf->exp[rs->error_locations[i]], rs->generator_root_gap);
243 36 : rs->error_roots[i] = field_div(rs->gf, 1, loc);
244 : }
245 2 : }
246 :
247 2 : static inline void rs_find_modified_syndromes(poporon_rs_t *rs, uint16_t *syndromes, polynomial_t erasure_locator)
248 : {
249 : polynomial_t syndrome_poly, modified_poly;
250 :
251 2 : syndrome_poly.order = rs->num_roots - 1;
252 2 : syndrome_poly.coeff = syndromes;
253 :
254 2 : modified_poly.order = rs->num_roots - 1;
255 2 : modified_poly.coeff = rs->modified_syndromes;
256 :
257 2 : polynomial_mul(rs->gf, erasure_locator, syndrome_poly, modified_poly);
258 2 : }
259 :
260 25 : static inline int16_t calculate_padding_length(poporon_rs_t *rs, size_t size)
261 : {
262 25 : if (size > (size_t)rs->message_length || size == 0) {
263 0 : return -1;
264 : }
265 25 : return (int16_t)(rs->message_length - size);
266 : }
267 :
268 25 : static inline bool rs_decode(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, size_t *corrected_num)
269 : {
270 25 : poporon_rs_t *rs = pprn->ctx.rs.rs;
271 : poporon_erasure_t *eras;
272 : int16_t padding_length;
273 : uint32_t i, order, num_skip;
274 25 : bool success = false;
275 25 : size_t errors_corrected = 0;
276 :
277 25 : padding_length = calculate_padding_length(rs, size);
278 25 : if (padding_length < 0) {
279 0 : goto finish;
280 : }
281 :
282 25 : if (!rs->has_init_decode) {
283 6 : rs_decoder_init(rs);
284 : }
285 :
286 25 : pmemset(rs->received_polynomial.coeff, 0, (rs->received_polynomial.order + 1) * sizeof(uint16_t));
287 :
288 1625 : for (i = 0; i < size; i++) {
289 1600 : rs->received_polynomial.coeff[rs->received_polynomial.order - (i + (size_t)padding_length)] =
290 1600 : data[i] & rs->gf->field_size;
291 : }
292 :
293 825 : for (i = 0; i < rs->num_roots; i++) {
294 800 : rs->received_polynomial.coeff[rs->num_roots - 1 - i] = parity[i] & rs->gf->field_size;
295 : }
296 :
297 25 : if (rs_find_syndromes(rs, rs->syndromes)) {
298 3 : success = true;
299 3 : if (pprn->ctx.rs.ext_syndrome) {
300 1 : pmemcpy(pprn->ctx.rs.ext_syndrome, rs->syndromes, rs->num_roots * sizeof(uint16_t));
301 : }
302 :
303 3 : goto finish;
304 : }
305 :
306 22 : if (pprn->ctx.rs.ext_syndrome) {
307 0 : pmemcpy(pprn->ctx.rs.ext_syndrome, rs->syndromes, rs->num_roots * sizeof(uint16_t));
308 : }
309 :
310 22 : num_skip = 0;
311 :
312 22 : if (pprn->ctx.rs.erasure) {
313 2 : eras = pprn->ctx.rs.erasure;
314 2 : if (eras->erasure_count > rs->num_roots) {
315 0 : goto finish;
316 : }
317 :
318 38 : for (i = 0; i < eras->erasure_count; i++) {
319 36 : rs->error_locations[i] = rs->block_length - (eras->erasure_positions[i] + (size_t)padding_length + 1);
320 : }
321 2 : num_skip = eras->erasure_count;
322 :
323 2 : rs_find_error_roots_from_locations(rs, eras->erasure_count);
324 :
325 2 : rs->erasure_locator = polynomial_init_from_roots(rs->gf, eras->erasure_count, rs->error_roots,
326 2 : rs->erasure_locator, rs->init_from_roots_scratch);
327 :
328 2 : rs_find_modified_syndromes(rs, rs->syndromes, rs->erasure_locator);
329 :
330 30 : for (i = eras->erasure_count; i < rs->num_roots; i++) {
331 28 : rs->syndromes[i - eras->erasure_count] = rs->modified_syndromes[i];
332 : }
333 : }
334 :
335 22 : order = rs_find_error_locator(rs, num_skip);
336 22 : rs->error_locator.order = order;
337 :
338 208 : for (i = 0; i <= rs->error_locator.order; i++) {
339 186 : rs->error_locator_log.coeff[i] = rs->gf->log[rs->error_locator.coeff[i]];
340 : }
341 :
342 22 : rs->error_locator_log.order = rs->error_locator.order;
343 :
344 22 : if (!rs_factorize_error_locator(rs, num_skip)) {
345 1 : goto finish;
346 : }
347 :
348 21 : rs_find_error_locations(rs, rs->error_locator.order + num_skip, num_skip);
349 21 : rs_find_error_values(rs, num_skip);
350 :
351 205 : for (i = 0; i < rs->error_locator.order + num_skip; i++) {
352 184 : rs->received_polynomial.coeff[rs->error_locations[i]] =
353 184 : field_sub(rs->received_polynomial.coeff[rs->error_locations[i]], rs->error_vals[i]);
354 : }
355 :
356 1365 : for (i = 0; i < size; i++) {
357 1344 : data[i] = (uint8_t)rs->received_polynomial.coeff[rs->received_polynomial.order - (i + (size_t)padding_length)];
358 : }
359 :
360 693 : for (i = 0; i < rs->num_roots; i++) {
361 672 : parity[i] = (uint8_t)rs->received_polynomial.coeff[rs->num_roots - 1 - i];
362 : }
363 :
364 21 : errors_corrected = rs->error_locator.order + num_skip;
365 21 : success = true;
366 :
367 25 : finish:
368 25 : pprn->ctx.rs.last_corrected = errors_corrected;
369 :
370 25 : if (corrected_num) {
371 24 : *corrected_num = errors_corrected;
372 : }
373 :
374 25 : return success;
375 : }
376 :
377 11 : static inline bool ldpc_decode(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, size_t *corrected_num)
378 : {
379 11 : poporon_ldpc_t *ldpc = pprn->ctx.ldpc.ldpc;
380 11 : uint32_t iterations_used = 0;
381 : uint8_t *codeword, *temp;
382 : size_t i;
383 : bool ok;
384 :
385 11 : if (size != ldpc->info_bytes) {
386 0 : return false;
387 : }
388 :
389 11 : if (ldpc->config.use_inner_interleave && ldpc->temp_interleaved) {
390 7 : codeword = ldpc->temp_interleaved;
391 : } else {
392 4 : codeword = ldpc->temp_codeword;
393 : }
394 :
395 11 : pmemcpy(codeword, data, ldpc->info_bytes);
396 11 : pmemcpy(codeword + ldpc->info_bytes, parity, ldpc->parity_bytes);
397 :
398 11 : if (pprn->ctx.ldpc.use_soft_decode && pprn->ctx.ldpc.soft_llr) {
399 0 : ok = poporon_ldpc_decode_soft(ldpc, pprn->ctx.ldpc.soft_llr, codeword, pprn->ctx.ldpc.max_iterations,
400 : &iterations_used);
401 : } else {
402 11 : ok = poporon_ldpc_decode_hard(ldpc, codeword, pprn->ctx.ldpc.max_iterations, &iterations_used);
403 : }
404 :
405 11 : pprn->ctx.ldpc.last_iterations = iterations_used;
406 :
407 11 : if (!ok) {
408 0 : return false;
409 : }
410 :
411 11 : if (ldpc->config.use_outer_interleave && ldpc->outer_interleaver.inverse) {
412 7 : temp = ldpc->temp_outer;
413 7 : if (!temp) {
414 0 : return false;
415 : }
416 :
417 775 : for (i = 0; i < ldpc->info_bytes; i++) {
418 768 : temp[ldpc->outer_interleaver.inverse[i]] = codeword[i];
419 : }
420 :
421 7 : pmemcpy(data, temp, ldpc->info_bytes);
422 : } else {
423 4 : pmemcpy(data, codeword, ldpc->info_bytes);
424 : }
425 :
426 11 : if (corrected_num) {
427 11 : *corrected_num = iterations_used;
428 : }
429 :
430 11 : return true;
431 : }
432 :
433 1 : static inline bool bch_decode(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, size_t *corrected_num)
434 : {
435 1 : poporon_bch_t *bch = pprn->ctx.bch.bch;
436 1 : uint32_t data_val = 0, parity_val = 0, received = 0, corrected = 0, corrected_data;
437 : uint16_t i, data_len, codeword_len, parity_bits, data_bytes, parity_bytes_len;
438 1 : int32_t num_errors = 0;
439 :
440 1 : data_len = poporon_bch_get_data_length(bch);
441 1 : codeword_len = poporon_bch_get_codeword_length(bch);
442 1 : parity_bits = codeword_len - data_len;
443 1 : data_bytes = (data_len + 7) / 8;
444 1 : parity_bytes_len = (parity_bits + 7) / 8;
445 :
446 1 : if (size < data_bytes) {
447 0 : return false;
448 : }
449 :
450 2 : for (i = 0; i < data_bytes && i < 4; i++) {
451 1 : data_val |= ((uint32_t)data[i]) << (8 * (data_bytes - 1 - i));
452 : }
453 :
454 1 : if (data_len < 32) {
455 1 : data_val &= ((uint32_t)1 << data_len) - 1;
456 : }
457 :
458 3 : for (i = 0; i < parity_bytes_len && i < 4; i++) {
459 2 : parity_val |= ((uint32_t)parity[i]) << (8 * (parity_bytes_len - 1 - i));
460 : }
461 :
462 1 : if (parity_bits < 32) {
463 1 : parity_val &= ((uint32_t)1 << parity_bits) - 1;
464 : }
465 :
466 1 : received = (data_val << parity_bits) | parity_val;
467 :
468 1 : if (!poporon_bch_decode(bch, received, &corrected, &num_errors)) {
469 0 : pprn->ctx.bch.last_num_errors = -1;
470 0 : return false;
471 : }
472 :
473 1 : pprn->ctx.bch.last_num_errors = num_errors;
474 :
475 1 : corrected_data = poporon_bch_extract_data(bch, corrected);
476 2 : for (i = 0; i < data_bytes && i < 4; i++) {
477 1 : data[data_bytes - 1 - i] = (uint8_t)(corrected_data >> (8 * i));
478 : }
479 :
480 1 : if (corrected_num) {
481 1 : *corrected_num = (num_errors > 0) ? (size_t)num_errors : 0;
482 : }
483 :
484 1 : return true;
485 : }
486 :
487 43 : extern bool poporon_decode(poporon_t *pprn, uint8_t *data, size_t size, uint8_t *parity, size_t *corrected_num)
488 : {
489 43 : if (!pprn || !data || !parity || !size) {
490 6 : return false;
491 : }
492 :
493 37 : switch (pprn->fec_type) {
494 25 : case PPLN_FEC_RS:
495 25 : return rs_decode(pprn, data, size, parity, corrected_num);
496 11 : case PPLN_FEC_LDPC:
497 11 : return ldpc_decode(pprn, data, size, parity, corrected_num);
498 1 : case PPLN_FEC_BCH:
499 1 : return bch_decode(pprn, data, size, parity, corrected_num);
500 0 : default:
501 0 : return false;
502 : }
503 : }
|
