1dc8f923eSThomas Gleixner // SPDX-License-Identifier: GPL-2.0 21da177e4SLinus Torvalds /* 31da177e4SLinus Torvalds * Generic Reed Solomon encoder / decoder library 41da177e4SLinus Torvalds * 51da177e4SLinus Torvalds * Copyright 2002, Phil Karn, KA9Q 61da177e4SLinus Torvalds * May be used under the terms of the GNU General Public License (GPL) 71da177e4SLinus Torvalds * 81da177e4SLinus Torvalds * Adaption to the kernel by Thomas Gleixner (tglx@linutronix.de) 91da177e4SLinus Torvalds * 103413e189SThomas Gleixner * Generic data width independent code which is included by the wrappers. 111da177e4SLinus Torvalds */ 121da177e4SLinus Torvalds { 1321633981SThomas Gleixner struct rs_codec *rs = rsc->codec; 141da177e4SLinus Torvalds int deg_lambda, el, deg_omega; 151da177e4SLinus Torvalds int i, j, r, k, pad; 161da177e4SLinus Torvalds int nn = rs->nn; 171da177e4SLinus Torvalds int nroots = rs->nroots; 181da177e4SLinus Torvalds int fcr = rs->fcr; 191da177e4SLinus Torvalds int prim = rs->prim; 201da177e4SLinus Torvalds int iprim = rs->iprim; 211da177e4SLinus Torvalds uint16_t *alpha_to = rs->alpha_to; 221da177e4SLinus Torvalds uint16_t *index_of = rs->index_of; 231da177e4SLinus Torvalds uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error; 241da177e4SLinus Torvalds int count = 0; 251da177e4SLinus Torvalds uint16_t msk = (uint16_t) rs->nn; 261da177e4SLinus Torvalds 2745888b40SThomas Gleixner /* 2845888b40SThomas Gleixner * The decoder buffers are in the rs control struct. They are 2945888b40SThomas Gleixner * arrays sized [nroots + 1] 3045888b40SThomas Gleixner */ 3145888b40SThomas Gleixner uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1); 3245888b40SThomas Gleixner uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1); 3345888b40SThomas Gleixner uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1); 3445888b40SThomas Gleixner uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1); 3545888b40SThomas Gleixner uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1); 3645888b40SThomas Gleixner uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1); 3745888b40SThomas Gleixner uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1); 3845888b40SThomas Gleixner uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1); 3945888b40SThomas Gleixner 401da177e4SLinus Torvalds /* Check length parameter for validity */ 411da177e4SLinus Torvalds pad = nn - nroots - len; 421dd7fdb1SJörn Engel BUG_ON(pad < 0 || pad >= nn); 431da177e4SLinus Torvalds 441da177e4SLinus Torvalds /* Does the caller provide the syndrome ? */ 451da177e4SLinus Torvalds if (s != NULL) 461da177e4SLinus Torvalds goto decode; 471da177e4SLinus Torvalds 481da177e4SLinus Torvalds /* form the syndromes; i.e., evaluate data(x) at roots of 491da177e4SLinus Torvalds * g(x) */ 501da177e4SLinus Torvalds for (i = 0; i < nroots; i++) 511da177e4SLinus Torvalds syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk; 521da177e4SLinus Torvalds 531da177e4SLinus Torvalds for (j = 1; j < len; j++) { 541da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 551da177e4SLinus Torvalds if (syn[i] == 0) { 561da177e4SLinus Torvalds syn[i] = (((uint16_t) data[j]) ^ 571da177e4SLinus Torvalds invmsk) & msk; 581da177e4SLinus Torvalds } else { 591da177e4SLinus Torvalds syn[i] = ((((uint16_t) data[j]) ^ 601da177e4SLinus Torvalds invmsk) & msk) ^ 611da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 621da177e4SLinus Torvalds (fcr + i) * prim)]; 631da177e4SLinus Torvalds } 641da177e4SLinus Torvalds } 651da177e4SLinus Torvalds } 661da177e4SLinus Torvalds 671da177e4SLinus Torvalds for (j = 0; j < nroots; j++) { 681da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 691da177e4SLinus Torvalds if (syn[i] == 0) { 701da177e4SLinus Torvalds syn[i] = ((uint16_t) par[j]) & msk; 711da177e4SLinus Torvalds } else { 721da177e4SLinus Torvalds syn[i] = (((uint16_t) par[j]) & msk) ^ 731da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 741da177e4SLinus Torvalds (fcr+i)*prim)]; 751da177e4SLinus Torvalds } 761da177e4SLinus Torvalds } 771da177e4SLinus Torvalds } 781da177e4SLinus Torvalds s = syn; 791da177e4SLinus Torvalds 801da177e4SLinus Torvalds /* Convert syndromes to index form, checking for nonzero condition */ 811da177e4SLinus Torvalds syn_error = 0; 821da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 831da177e4SLinus Torvalds syn_error |= s[i]; 841da177e4SLinus Torvalds s[i] = index_of[s[i]]; 851da177e4SLinus Torvalds } 861da177e4SLinus Torvalds 871da177e4SLinus Torvalds if (!syn_error) { 881da177e4SLinus Torvalds /* if syndrome is zero, data[] is a codeword and there are no 891da177e4SLinus Torvalds * errors to correct. So return data[] unmodified 901da177e4SLinus Torvalds */ 911da177e4SLinus Torvalds count = 0; 921da177e4SLinus Torvalds goto finish; 931da177e4SLinus Torvalds } 941da177e4SLinus Torvalds 951da177e4SLinus Torvalds decode: 961da177e4SLinus Torvalds memset(&lambda[1], 0, nroots * sizeof(lambda[0])); 971da177e4SLinus Torvalds lambda[0] = 1; 981da177e4SLinus Torvalds 991da177e4SLinus Torvalds if (no_eras > 0) { 1001da177e4SLinus Torvalds /* Init lambda to be the erasure locator polynomial */ 1011da177e4SLinus Torvalds lambda[1] = alpha_to[rs_modnn(rs, 1022034a42dSFerdinand Blomqvist prim * (nn - 1 - (eras_pos[0] + pad)))]; 1031da177e4SLinus Torvalds for (i = 1; i < no_eras; i++) { 1042034a42dSFerdinand Blomqvist u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad))); 1051da177e4SLinus Torvalds for (j = i + 1; j > 0; j--) { 1061da177e4SLinus Torvalds tmp = index_of[lambda[j - 1]]; 1071da177e4SLinus Torvalds if (tmp != nn) { 1081da177e4SLinus Torvalds lambda[j] ^= 1091da177e4SLinus Torvalds alpha_to[rs_modnn(rs, u + tmp)]; 1101da177e4SLinus Torvalds } 1111da177e4SLinus Torvalds } 1121da177e4SLinus Torvalds } 1131da177e4SLinus Torvalds } 1141da177e4SLinus Torvalds 1151da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) 1161da177e4SLinus Torvalds b[i] = index_of[lambda[i]]; 1171da177e4SLinus Torvalds 1181da177e4SLinus Torvalds /* 1191da177e4SLinus Torvalds * Begin Berlekamp-Massey algorithm to determine error+erasure 1201da177e4SLinus Torvalds * locator polynomial 1211da177e4SLinus Torvalds */ 1221da177e4SLinus Torvalds r = no_eras; 1231da177e4SLinus Torvalds el = no_eras; 1241da177e4SLinus Torvalds while (++r <= nroots) { /* r is the step number */ 1251da177e4SLinus Torvalds /* Compute discrepancy at the r-th step in poly-form */ 1261da177e4SLinus Torvalds discr_r = 0; 1271da177e4SLinus Torvalds for (i = 0; i < r; i++) { 1281da177e4SLinus Torvalds if ((lambda[i] != 0) && (s[r - i - 1] != nn)) { 1291da177e4SLinus Torvalds discr_r ^= 1301da177e4SLinus Torvalds alpha_to[rs_modnn(rs, 1311da177e4SLinus Torvalds index_of[lambda[i]] + 1321da177e4SLinus Torvalds s[r - i - 1])]; 1331da177e4SLinus Torvalds } 1341da177e4SLinus Torvalds } 1351da177e4SLinus Torvalds discr_r = index_of[discr_r]; /* Index form */ 1361da177e4SLinus Torvalds if (discr_r == nn) { 1371da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1381da177e4SLinus Torvalds memmove (&b[1], b, nroots * sizeof (b[0])); 1391da177e4SLinus Torvalds b[0] = nn; 1401da177e4SLinus Torvalds } else { 1411da177e4SLinus Torvalds /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */ 1421da177e4SLinus Torvalds t[0] = lambda[0]; 1431da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 1441da177e4SLinus Torvalds if (b[i] != nn) { 1451da177e4SLinus Torvalds t[i + 1] = lambda[i + 1] ^ 1461da177e4SLinus Torvalds alpha_to[rs_modnn(rs, discr_r + 1471da177e4SLinus Torvalds b[i])]; 1481da177e4SLinus Torvalds } else 1491da177e4SLinus Torvalds t[i + 1] = lambda[i + 1]; 1501da177e4SLinus Torvalds } 1511da177e4SLinus Torvalds if (2 * el <= r + no_eras - 1) { 1521da177e4SLinus Torvalds el = r + no_eras - el; 1531da177e4SLinus Torvalds /* 1541da177e4SLinus Torvalds * 2 lines below: B(x) <-- inv(discr_r) * 1551da177e4SLinus Torvalds * lambda(x) 1561da177e4SLinus Torvalds */ 1571da177e4SLinus Torvalds for (i = 0; i <= nroots; i++) { 1581da177e4SLinus Torvalds b[i] = (lambda[i] == 0) ? nn : 1591da177e4SLinus Torvalds rs_modnn(rs, index_of[lambda[i]] 1601da177e4SLinus Torvalds - discr_r + nn); 1611da177e4SLinus Torvalds } 1621da177e4SLinus Torvalds } else { 1631da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1641da177e4SLinus Torvalds memmove(&b[1], b, nroots * sizeof(b[0])); 1651da177e4SLinus Torvalds b[0] = nn; 1661da177e4SLinus Torvalds } 1671da177e4SLinus Torvalds memcpy(lambda, t, (nroots + 1) * sizeof(t[0])); 1681da177e4SLinus Torvalds } 1691da177e4SLinus Torvalds } 1701da177e4SLinus Torvalds 1711da177e4SLinus Torvalds /* Convert lambda to index form and compute deg(lambda(x)) */ 1721da177e4SLinus Torvalds deg_lambda = 0; 1731da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) { 1741da177e4SLinus Torvalds lambda[i] = index_of[lambda[i]]; 1751da177e4SLinus Torvalds if (lambda[i] != nn) 1761da177e4SLinus Torvalds deg_lambda = i; 1771da177e4SLinus Torvalds } 1781da177e4SLinus Torvalds /* Find roots of error+erasure locator polynomial by Chien search */ 1791da177e4SLinus Torvalds memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); 1801da177e4SLinus Torvalds count = 0; /* Number of roots of lambda(x) */ 1811da177e4SLinus Torvalds for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) { 1821da177e4SLinus Torvalds q = 1; /* lambda[0] is always 0 */ 1831da177e4SLinus Torvalds for (j = deg_lambda; j > 0; j--) { 1841da177e4SLinus Torvalds if (reg[j] != nn) { 1851da177e4SLinus Torvalds reg[j] = rs_modnn(rs, reg[j] + j); 1861da177e4SLinus Torvalds q ^= alpha_to[reg[j]]; 1871da177e4SLinus Torvalds } 1881da177e4SLinus Torvalds } 1891da177e4SLinus Torvalds if (q != 0) 1901da177e4SLinus Torvalds continue; /* Not a root */ 1911da177e4SLinus Torvalds /* store root (index-form) and error location number */ 1921da177e4SLinus Torvalds root[count] = i; 1931da177e4SLinus Torvalds loc[count] = k; 1941da177e4SLinus Torvalds /* If we've already found max possible roots, 1951da177e4SLinus Torvalds * abort the search to save time 1961da177e4SLinus Torvalds */ 1971da177e4SLinus Torvalds if (++count == deg_lambda) 1981da177e4SLinus Torvalds break; 1991da177e4SLinus Torvalds } 2001da177e4SLinus Torvalds if (deg_lambda != count) { 2011da177e4SLinus Torvalds /* 2021da177e4SLinus Torvalds * deg(lambda) unequal to number of roots => uncorrectable 2031da177e4SLinus Torvalds * error detected 2041da177e4SLinus Torvalds */ 205eb684507SJörn Engel count = -EBADMSG; 2061da177e4SLinus Torvalds goto finish; 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds /* 2091da177e4SLinus Torvalds * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 2101da177e4SLinus Torvalds * x**nroots). in index form. Also find deg(omega). 2111da177e4SLinus Torvalds */ 2121da177e4SLinus Torvalds deg_omega = deg_lambda - 1; 2131da177e4SLinus Torvalds for (i = 0; i <= deg_omega; i++) { 2141da177e4SLinus Torvalds tmp = 0; 2151da177e4SLinus Torvalds for (j = i; j >= 0; j--) { 2161da177e4SLinus Torvalds if ((s[i - j] != nn) && (lambda[j] != nn)) 2171da177e4SLinus Torvalds tmp ^= 2181da177e4SLinus Torvalds alpha_to[rs_modnn(rs, s[i - j] + lambda[j])]; 2191da177e4SLinus Torvalds } 2201da177e4SLinus Torvalds omega[i] = index_of[tmp]; 2211da177e4SLinus Torvalds } 2221da177e4SLinus Torvalds 2231da177e4SLinus Torvalds /* 2241da177e4SLinus Torvalds * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 2251da177e4SLinus Torvalds * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form 2261da177e4SLinus Torvalds */ 2271da177e4SLinus Torvalds for (j = count - 1; j >= 0; j--) { 2281da177e4SLinus Torvalds num1 = 0; 2291da177e4SLinus Torvalds for (i = deg_omega; i >= 0; i--) { 2301da177e4SLinus Torvalds if (omega[i] != nn) 2311da177e4SLinus Torvalds num1 ^= alpha_to[rs_modnn(rs, omega[i] + 2321da177e4SLinus Torvalds i * root[j])]; 2331da177e4SLinus Torvalds } 2341da177e4SLinus Torvalds num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)]; 2351da177e4SLinus Torvalds den = 0; 2361da177e4SLinus Torvalds 2371da177e4SLinus Torvalds /* lambda[i+1] for i even is the formal derivative 2381da177e4SLinus Torvalds * lambda_pr of lambda[i] */ 2391da177e4SLinus Torvalds for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) { 2401da177e4SLinus Torvalds if (lambda[i + 1] != nn) { 2411da177e4SLinus Torvalds den ^= alpha_to[rs_modnn(rs, lambda[i + 1] + 2421da177e4SLinus Torvalds i * root[j])]; 2431da177e4SLinus Torvalds } 2441da177e4SLinus Torvalds } 2451da177e4SLinus Torvalds /* Apply error to data */ 2461da177e4SLinus Torvalds if (num1 != 0 && loc[j] >= pad) { 2471da177e4SLinus Torvalds uint16_t cor = alpha_to[rs_modnn(rs,index_of[num1] + 2481da177e4SLinus Torvalds index_of[num2] + 2491da177e4SLinus Torvalds nn - index_of[den])]; 2501da177e4SLinus Torvalds /* Store the error correction pattern, if a 2511da177e4SLinus Torvalds * correction buffer is available */ 2521da177e4SLinus Torvalds if (corr) { 2531da177e4SLinus Torvalds corr[j] = cor; 2541da177e4SLinus Torvalds } else { 2551da177e4SLinus Torvalds /* If a data buffer is given and the 2561da177e4SLinus Torvalds * error is inside the message, 2571da177e4SLinus Torvalds * correct it */ 2581da177e4SLinus Torvalds if (data && (loc[j] < (nn - nroots))) 2591da177e4SLinus Torvalds data[loc[j] - pad] ^= cor; 2601da177e4SLinus Torvalds } 2611da177e4SLinus Torvalds } 2621da177e4SLinus Torvalds } 2631da177e4SLinus Torvalds 2641da177e4SLinus Torvalds finish: 2651da177e4SLinus Torvalds if (eras_pos != NULL) { 2661da177e4SLinus Torvalds for (i = 0; i < count; i++) 2671da177e4SLinus Torvalds eras_pos[i] = loc[i] - pad; 2681da177e4SLinus Torvalds } 2691da177e4SLinus Torvalds return count; 2701da177e4SLinus Torvalds 2711da177e4SLinus Torvalds } 272