dc8f923eaee24 (Thomas Gleixner 2018-04-22 18:23:50 +0200 1) // SPDX-License-Identifier: GPL-2.0
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 2) /*
3413e1891d443 (Thomas Gleixner 2018-04-22 18:23:49 +0200 3) * Generic Reed Solomon encoder / decoder library
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 4) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 5) * Copyright 2002, Phil Karn, KA9Q
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 6) * May be used under the terms of the GNU General Public License (GPL)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 8) * Adaption to the kernel by Thomas Gleixner (tglx@linutronix.de)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 9) *
3413e1891d443 (Thomas Gleixner 2018-04-22 18:23:49 +0200 10) * Generic data width independent code which is included by the wrappers.
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 11) */
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 12) {
2163398192f6a (Thomas Gleixner 2018-04-22 18:23:53 +0200 13) struct rs_codec *rs = rsc->codec;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 14) int deg_lambda, el, deg_omega;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 15) int i, j, r, k, pad;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 16) int nn = rs->nn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 17) int nroots = rs->nroots;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 18) int fcr = rs->fcr;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 19) int prim = rs->prim;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 20) int iprim = rs->iprim;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 21) uint16_t *alpha_to = rs->alpha_to;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 22) uint16_t *index_of = rs->index_of;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 23) uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 24) int count = 0;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 25) int num_corrected;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 26) uint16_t msk = (uint16_t) rs->nn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 27)
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 28) /*
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 29) * The decoder buffers are in the rs control struct. They are
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 30) * arrays sized [nroots + 1]
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 31) */
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 32) uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 33) uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 34) uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 35) uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 36) uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 37) uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 38) uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 39) uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1);
45888b40d2a62 (Thomas Gleixner 2018-04-22 18:23:55 +0200 40)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 41) /* Check length parameter for validity */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 42) pad = nn - nroots - len;
a343536f8f482 (Ferdinand Blomqvist 2019-06-20 17:10:35 +0300 43) BUG_ON(pad < 0 || pad >= nn - nroots);
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 44)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 45) /* Does the caller provide the syndrome ? */
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 46) if (s != NULL) {
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 47) for (i = 0; i < nroots; i++) {
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 48) /* The syndrome is in index form,
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 49) * so nn represents zero
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 50) */
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 51) if (s[i] != nn)
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 52) goto decode;
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 53) }
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 54)
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 55) /* syndrome is zero, no errors to correct */
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 56) return 0;
ef4d6a8556b63 (Ferdinand Blomqvist 2019-06-20 17:10:37 +0300 57) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 58)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 59) /* form the syndromes; i.e., evaluate data(x) at roots of
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 60) * g(x) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 61) for (i = 0; i < nroots; i++)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 62) syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 63)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 64) for (j = 1; j < len; j++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 65) for (i = 0; i < nroots; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 66) if (syn[i] == 0) {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 67) syn[i] = (((uint16_t) data[j]) ^
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 68) invmsk) & msk;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 69) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 70) syn[i] = ((((uint16_t) data[j]) ^
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 71) invmsk) & msk) ^
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 72) alpha_to[rs_modnn(rs, index_of[syn[i]] +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 73) (fcr + i) * prim)];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 74) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 75) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 76) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 77)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 78) for (j = 0; j < nroots; j++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 79) for (i = 0; i < nroots; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 80) if (syn[i] == 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 81) syn[i] = ((uint16_t) par[j]) & msk;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 82) } else {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 83) syn[i] = (((uint16_t) par[j]) & msk) ^
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 84) alpha_to[rs_modnn(rs, index_of[syn[i]] +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 85) (fcr+i)*prim)];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 86) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 87) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 88) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 89) s = syn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 90)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 91) /* Convert syndromes to index form, checking for nonzero condition */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 92) syn_error = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 93) for (i = 0; i < nroots; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 94) syn_error |= s[i];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 95) s[i] = index_of[s[i]];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 96) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 97)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 98) if (!syn_error) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 99) /* if syndrome is zero, data[] is a codeword and there are no
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 100) * errors to correct. So return data[] unmodified
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 101) */
647cc9ece63fd (Ferdinand Blomqvist 2019-06-20 17:10:36 +0300 102) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 103) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 104)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 105) decode:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 106) memset(&lambda[1], 0, nroots * sizeof(lambda[0]));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 107) lambda[0] = 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 108)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 109) if (no_eras > 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 110) /* Init lambda to be the erasure locator polynomial */
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 111) lambda[1] = alpha_to[rs_modnn(rs,
2034a42d1747f (Ferdinand Blomqvist 2019-06-20 17:10:34 +0300 112) prim * (nn - 1 - (eras_pos[0] + pad)))];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 113) for (i = 1; i < no_eras; i++) {
2034a42d1747f (Ferdinand Blomqvist 2019-06-20 17:10:34 +0300 114) u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 115) for (j = i + 1; j > 0; j--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 116) tmp = index_of[lambda[j - 1]];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 117) if (tmp != nn) {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 118) lambda[j] ^=
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 119) alpha_to[rs_modnn(rs, u + tmp)];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 120) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 121) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 122) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 123) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 124)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 125) for (i = 0; i < nroots + 1; i++)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 126) b[i] = index_of[lambda[i]];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 127)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 128) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 129) * Begin Berlekamp-Massey algorithm to determine error+erasure
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 130) * locator polynomial
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 131) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 132) r = no_eras;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 133) el = no_eras;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134) while (++r <= nroots) { /* r is the step number */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 135) /* Compute discrepancy at the r-th step in poly-form */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 136) discr_r = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137) for (i = 0; i < r; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 138) if ((lambda[i] != 0) && (s[r - i - 1] != nn)) {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 139) discr_r ^=
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 140) alpha_to[rs_modnn(rs,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 141) index_of[lambda[i]] +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 142) s[r - i - 1])];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 144) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 145) discr_r = index_of[discr_r]; /* Index form */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 146) if (discr_r == nn) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 147) /* 2 lines below: B(x) <-- x*B(x) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 148) memmove (&b[1], b, nroots * sizeof (b[0]));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) b[0] = nn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 150) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 151) /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) t[0] = lambda[0];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 153) for (i = 0; i < nroots; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154) if (b[i] != nn) {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 155) t[i + 1] = lambda[i + 1] ^
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156) alpha_to[rs_modnn(rs, discr_r +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 157) b[i])];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 158) } else
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) t[i + 1] = lambda[i + 1];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 161) if (2 * el <= r + no_eras - 1) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 162) el = r + no_eras - el;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 163) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164) * 2 lines below: B(x) <-- inv(discr_r) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 165) * lambda(x)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 166) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) for (i = 0; i <= nroots; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) b[i] = (lambda[i] == 0) ? nn :
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) rs_modnn(rs, index_of[lambda[i]]
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) - discr_r + nn);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 173) /* 2 lines below: B(x) <-- x*B(x) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 174) memmove(&b[1], b, nroots * sizeof(b[0]));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 175) b[0] = nn;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 176) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 177) memcpy(lambda, t, (nroots + 1) * sizeof(t[0]));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 178) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 179) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 180)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 181) /* Convert lambda to index form and compute deg(lambda(x)) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 182) deg_lambda = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 183) for (i = 0; i < nroots + 1; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 184) lambda[i] = index_of[lambda[i]];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 185) if (lambda[i] != nn)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 186) deg_lambda = i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 187) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 188)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 189) if (deg_lambda == 0) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 190) /*
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 191) * deg(lambda) is zero even though the syndrome is non-zero
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 192) * => uncorrectable error detected
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 193) */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 194) return -EBADMSG;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 195) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 196)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 197) /* Find roots of error+erasure locator polynomial by Chien search */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 198) memcpy(®[1], &lambda[1], nroots * sizeof(reg[0]));
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 199) count = 0; /* Number of roots of lambda(x) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 200) for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 201) q = 1; /* lambda[0] is always 0 */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 202) for (j = deg_lambda; j > 0; j--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 203) if (reg[j] != nn) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 204) reg[j] = rs_modnn(rs, reg[j] + j);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 205) q ^= alpha_to[reg[j]];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 206) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 207) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 208) if (q != 0)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 209) continue; /* Not a root */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 210)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 211) if (k < pad) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 212) /* Impossible error location. Uncorrectable error. */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 213) return -EBADMSG;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 214) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 215)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 216) /* store root (index-form) and error location number */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 217) root[count] = i;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 218) loc[count] = k;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 219) /* If we've already found max possible roots,
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 220) * abort the search to save time
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 221) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 222) if (++count == deg_lambda)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 223) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 224) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 225) if (deg_lambda != count) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 226) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 227) * deg(lambda) unequal to number of roots => uncorrectable
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 228) * error detected
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 229) */
647cc9ece63fd (Ferdinand Blomqvist 2019-06-20 17:10:36 +0300 230) return -EBADMSG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 231) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 232) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 233) * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 234) * x**nroots). in index form. Also find deg(omega).
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 235) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 236) deg_omega = deg_lambda - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 237) for (i = 0; i <= deg_omega; i++) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 238) tmp = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 239) for (j = i; j >= 0; j--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 240) if ((s[i - j] != nn) && (lambda[j] != nn))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 241) tmp ^=
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 242) alpha_to[rs_modnn(rs, s[i - j] + lambda[j])];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 243) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 244) omega[i] = index_of[tmp];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 245) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 246)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 247) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 248) * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 249) * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 250) * Note: we reuse the buffer for b to store the correction pattern
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 251) */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 252) num_corrected = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 253) for (j = count - 1; j >= 0; j--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 254) num1 = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 255) for (i = deg_omega; i >= 0; i--) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 256) if (omega[i] != nn)
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 257) num1 ^= alpha_to[rs_modnn(rs, omega[i] +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 258) i * root[j])];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 259) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 260)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 261) if (num1 == 0) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 262) /* Nothing to correct at this position */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 263) b[j] = 0;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 264) continue;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 265) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 266)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 267) num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 268) den = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 269)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 270) /* lambda[i+1] for i even is the formal derivative
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 271) * lambda_pr of lambda[i] */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 272) for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 273) if (lambda[i + 1] != nn) {
03ead8427d65f (Thomas Gleixner 2005-11-07 11:15:37 +0000 274) den ^= alpha_to[rs_modnn(rs, lambda[i + 1] +
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 275) i * root[j])];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 276) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 277) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 278)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 279) b[j] = alpha_to[rs_modnn(rs, index_of[num1] +
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 280) index_of[num2] +
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 281) nn - index_of[den])];
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 282) num_corrected++;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 283) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 284)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 285) /*
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 286) * We compute the syndrome of the 'error' and check that it matches
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 287) * the syndrome of the received word
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 288) */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 289) for (i = 0; i < nroots; i++) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 290) tmp = 0;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 291) for (j = 0; j < count; j++) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 292) if (b[j] == 0)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 293) continue;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 294)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 295) k = (fcr + i) * prim * (nn-loc[j]-1);
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 296) tmp ^= alpha_to[rs_modnn(rs, index_of[b[j]] + k)];
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 297) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 298)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 299) if (tmp != alpha_to[s[i]])
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 300) return -EBADMSG;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 301) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 302)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 303) /*
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 304) * Store the error correction pattern, if a
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 305) * correction buffer is available
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 306) */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 307) if (corr && eras_pos) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 308) j = 0;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 309) for (i = 0; i < count; i++) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 310) if (b[i]) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 311) corr[j] = b[i];
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 312) eras_pos[j++] = loc[i] - pad;
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 313) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 314) }
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 315) } else if (data && par) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 316) /* Apply error to data and parity */
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 317) for (i = 0; i < count; i++) {
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 318) if (loc[i] < (nn - nroots))
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 319) data[loc[i] - pad] ^= b[i];
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 320) else
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 321) par[loc[i] - pad - len] ^= b[i];
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 322) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 323) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 324)
991305dee585d (Ferdinand Blomqvist 2019-06-20 17:10:39 +0300 325) return num_corrected;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 326) }
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags