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 /* Err+Eras Locator poly and syndrome poly The maximum value 251da177e4SLinus Torvalds * of nroots is 8. So the necessary stack size will be about 261da177e4SLinus Torvalds * 220 bytes max. 271da177e4SLinus Torvalds */ 281da177e4SLinus Torvalds uint16_t lambda[nroots + 1], syn[nroots]; 291da177e4SLinus Torvalds uint16_t b[nroots + 1], t[nroots + 1], omega[nroots + 1]; 301da177e4SLinus Torvalds uint16_t root[nroots], reg[nroots + 1], loc[nroots]; 311da177e4SLinus Torvalds int count = 0; 321da177e4SLinus Torvalds uint16_t msk = (uint16_t) rs->nn; 331da177e4SLinus Torvalds 341da177e4SLinus Torvalds /* Check length parameter for validity */ 351da177e4SLinus Torvalds pad = nn - nroots - len; 361dd7fdb1SJörn Engel BUG_ON(pad < 0 || pad >= nn); 371da177e4SLinus Torvalds 381da177e4SLinus Torvalds /* Does the caller provide the syndrome ? */ 391da177e4SLinus Torvalds if (s != NULL) 401da177e4SLinus Torvalds goto decode; 411da177e4SLinus Torvalds 421da177e4SLinus Torvalds /* form the syndromes; i.e., evaluate data(x) at roots of 431da177e4SLinus Torvalds * g(x) */ 441da177e4SLinus Torvalds for (i = 0; i < nroots; i++) 451da177e4SLinus Torvalds syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk; 461da177e4SLinus Torvalds 471da177e4SLinus Torvalds for (j = 1; j < len; j++) { 481da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 491da177e4SLinus Torvalds if (syn[i] == 0) { 501da177e4SLinus Torvalds syn[i] = (((uint16_t) data[j]) ^ 511da177e4SLinus Torvalds invmsk) & msk; 521da177e4SLinus Torvalds } else { 531da177e4SLinus Torvalds syn[i] = ((((uint16_t) data[j]) ^ 541da177e4SLinus Torvalds invmsk) & msk) ^ 551da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 561da177e4SLinus Torvalds (fcr + i) * prim)]; 571da177e4SLinus Torvalds } 581da177e4SLinus Torvalds } 591da177e4SLinus Torvalds } 601da177e4SLinus Torvalds 611da177e4SLinus Torvalds for (j = 0; j < nroots; j++) { 621da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 631da177e4SLinus Torvalds if (syn[i] == 0) { 641da177e4SLinus Torvalds syn[i] = ((uint16_t) par[j]) & msk; 651da177e4SLinus Torvalds } else { 661da177e4SLinus Torvalds syn[i] = (((uint16_t) par[j]) & msk) ^ 671da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 681da177e4SLinus Torvalds (fcr+i)*prim)]; 691da177e4SLinus Torvalds } 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds } 721da177e4SLinus Torvalds s = syn; 731da177e4SLinus Torvalds 741da177e4SLinus Torvalds /* Convert syndromes to index form, checking for nonzero condition */ 751da177e4SLinus Torvalds syn_error = 0; 761da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 771da177e4SLinus Torvalds syn_error |= s[i]; 781da177e4SLinus Torvalds s[i] = index_of[s[i]]; 791da177e4SLinus Torvalds } 801da177e4SLinus Torvalds 811da177e4SLinus Torvalds if (!syn_error) { 821da177e4SLinus Torvalds /* if syndrome is zero, data[] is a codeword and there are no 831da177e4SLinus Torvalds * errors to correct. So return data[] unmodified 841da177e4SLinus Torvalds */ 851da177e4SLinus Torvalds count = 0; 861da177e4SLinus Torvalds goto finish; 871da177e4SLinus Torvalds } 881da177e4SLinus Torvalds 891da177e4SLinus Torvalds decode: 901da177e4SLinus Torvalds memset(&lambda[1], 0, nroots * sizeof(lambda[0])); 911da177e4SLinus Torvalds lambda[0] = 1; 921da177e4SLinus Torvalds 931da177e4SLinus Torvalds if (no_eras > 0) { 941da177e4SLinus Torvalds /* Init lambda to be the erasure locator polynomial */ 951da177e4SLinus Torvalds lambda[1] = alpha_to[rs_modnn(rs, 961da177e4SLinus Torvalds prim * (nn - 1 - eras_pos[0]))]; 971da177e4SLinus Torvalds for (i = 1; i < no_eras; i++) { 981da177e4SLinus Torvalds u = rs_modnn(rs, prim * (nn - 1 - eras_pos[i])); 991da177e4SLinus Torvalds for (j = i + 1; j > 0; j--) { 1001da177e4SLinus Torvalds tmp = index_of[lambda[j - 1]]; 1011da177e4SLinus Torvalds if (tmp != nn) { 1021da177e4SLinus Torvalds lambda[j] ^= 1031da177e4SLinus Torvalds alpha_to[rs_modnn(rs, u + tmp)]; 1041da177e4SLinus Torvalds } 1051da177e4SLinus Torvalds } 1061da177e4SLinus Torvalds } 1071da177e4SLinus Torvalds } 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) 1101da177e4SLinus Torvalds b[i] = index_of[lambda[i]]; 1111da177e4SLinus Torvalds 1121da177e4SLinus Torvalds /* 1131da177e4SLinus Torvalds * Begin Berlekamp-Massey algorithm to determine error+erasure 1141da177e4SLinus Torvalds * locator polynomial 1151da177e4SLinus Torvalds */ 1161da177e4SLinus Torvalds r = no_eras; 1171da177e4SLinus Torvalds el = no_eras; 1181da177e4SLinus Torvalds while (++r <= nroots) { /* r is the step number */ 1191da177e4SLinus Torvalds /* Compute discrepancy at the r-th step in poly-form */ 1201da177e4SLinus Torvalds discr_r = 0; 1211da177e4SLinus Torvalds for (i = 0; i < r; i++) { 1221da177e4SLinus Torvalds if ((lambda[i] != 0) && (s[r - i - 1] != nn)) { 1231da177e4SLinus Torvalds discr_r ^= 1241da177e4SLinus Torvalds alpha_to[rs_modnn(rs, 1251da177e4SLinus Torvalds index_of[lambda[i]] + 1261da177e4SLinus Torvalds s[r - i - 1])]; 1271da177e4SLinus Torvalds } 1281da177e4SLinus Torvalds } 1291da177e4SLinus Torvalds discr_r = index_of[discr_r]; /* Index form */ 1301da177e4SLinus Torvalds if (discr_r == nn) { 1311da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1321da177e4SLinus Torvalds memmove (&b[1], b, nroots * sizeof (b[0])); 1331da177e4SLinus Torvalds b[0] = nn; 1341da177e4SLinus Torvalds } else { 1351da177e4SLinus Torvalds /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */ 1361da177e4SLinus Torvalds t[0] = lambda[0]; 1371da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 1381da177e4SLinus Torvalds if (b[i] != nn) { 1391da177e4SLinus Torvalds t[i + 1] = lambda[i + 1] ^ 1401da177e4SLinus Torvalds alpha_to[rs_modnn(rs, discr_r + 1411da177e4SLinus Torvalds b[i])]; 1421da177e4SLinus Torvalds } else 1431da177e4SLinus Torvalds t[i + 1] = lambda[i + 1]; 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds if (2 * el <= r + no_eras - 1) { 1461da177e4SLinus Torvalds el = r + no_eras - el; 1471da177e4SLinus Torvalds /* 1481da177e4SLinus Torvalds * 2 lines below: B(x) <-- inv(discr_r) * 1491da177e4SLinus Torvalds * lambda(x) 1501da177e4SLinus Torvalds */ 1511da177e4SLinus Torvalds for (i = 0; i <= nroots; i++) { 1521da177e4SLinus Torvalds b[i] = (lambda[i] == 0) ? nn : 1531da177e4SLinus Torvalds rs_modnn(rs, index_of[lambda[i]] 1541da177e4SLinus Torvalds - discr_r + nn); 1551da177e4SLinus Torvalds } 1561da177e4SLinus Torvalds } else { 1571da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1581da177e4SLinus Torvalds memmove(&b[1], b, nroots * sizeof(b[0])); 1591da177e4SLinus Torvalds b[0] = nn; 1601da177e4SLinus Torvalds } 1611da177e4SLinus Torvalds memcpy(lambda, t, (nroots + 1) * sizeof(t[0])); 1621da177e4SLinus Torvalds } 1631da177e4SLinus Torvalds } 1641da177e4SLinus Torvalds 1651da177e4SLinus Torvalds /* Convert lambda to index form and compute deg(lambda(x)) */ 1661da177e4SLinus Torvalds deg_lambda = 0; 1671da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) { 1681da177e4SLinus Torvalds lambda[i] = index_of[lambda[i]]; 1691da177e4SLinus Torvalds if (lambda[i] != nn) 1701da177e4SLinus Torvalds deg_lambda = i; 1711da177e4SLinus Torvalds } 1721da177e4SLinus Torvalds /* Find roots of error+erasure locator polynomial by Chien search */ 1731da177e4SLinus Torvalds memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); 1741da177e4SLinus Torvalds count = 0; /* Number of roots of lambda(x) */ 1751da177e4SLinus Torvalds for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) { 1761da177e4SLinus Torvalds q = 1; /* lambda[0] is always 0 */ 1771da177e4SLinus Torvalds for (j = deg_lambda; j > 0; j--) { 1781da177e4SLinus Torvalds if (reg[j] != nn) { 1791da177e4SLinus Torvalds reg[j] = rs_modnn(rs, reg[j] + j); 1801da177e4SLinus Torvalds q ^= alpha_to[reg[j]]; 1811da177e4SLinus Torvalds } 1821da177e4SLinus Torvalds } 1831da177e4SLinus Torvalds if (q != 0) 1841da177e4SLinus Torvalds continue; /* Not a root */ 1851da177e4SLinus Torvalds /* store root (index-form) and error location number */ 1861da177e4SLinus Torvalds root[count] = i; 1871da177e4SLinus Torvalds loc[count] = k; 1881da177e4SLinus Torvalds /* If we've already found max possible roots, 1891da177e4SLinus Torvalds * abort the search to save time 1901da177e4SLinus Torvalds */ 1911da177e4SLinus Torvalds if (++count == deg_lambda) 1921da177e4SLinus Torvalds break; 1931da177e4SLinus Torvalds } 1941da177e4SLinus Torvalds if (deg_lambda != count) { 1951da177e4SLinus Torvalds /* 1961da177e4SLinus Torvalds * deg(lambda) unequal to number of roots => uncorrectable 1971da177e4SLinus Torvalds * error detected 1981da177e4SLinus Torvalds */ 199eb684507SJörn Engel count = -EBADMSG; 2001da177e4SLinus Torvalds goto finish; 2011da177e4SLinus Torvalds } 2021da177e4SLinus Torvalds /* 2031da177e4SLinus Torvalds * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 2041da177e4SLinus Torvalds * x**nroots). in index form. Also find deg(omega). 2051da177e4SLinus Torvalds */ 2061da177e4SLinus Torvalds deg_omega = deg_lambda - 1; 2071da177e4SLinus Torvalds for (i = 0; i <= deg_omega; i++) { 2081da177e4SLinus Torvalds tmp = 0; 2091da177e4SLinus Torvalds for (j = i; j >= 0; j--) { 2101da177e4SLinus Torvalds if ((s[i - j] != nn) && (lambda[j] != nn)) 2111da177e4SLinus Torvalds tmp ^= 2121da177e4SLinus Torvalds alpha_to[rs_modnn(rs, s[i - j] + lambda[j])]; 2131da177e4SLinus Torvalds } 2141da177e4SLinus Torvalds omega[i] = index_of[tmp]; 2151da177e4SLinus Torvalds } 2161da177e4SLinus Torvalds 2171da177e4SLinus Torvalds /* 2181da177e4SLinus Torvalds * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 2191da177e4SLinus Torvalds * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form 2201da177e4SLinus Torvalds */ 2211da177e4SLinus Torvalds for (j = count - 1; j >= 0; j--) { 2221da177e4SLinus Torvalds num1 = 0; 2231da177e4SLinus Torvalds for (i = deg_omega; i >= 0; i--) { 2241da177e4SLinus Torvalds if (omega[i] != nn) 2251da177e4SLinus Torvalds num1 ^= alpha_to[rs_modnn(rs, omega[i] + 2261da177e4SLinus Torvalds i * root[j])]; 2271da177e4SLinus Torvalds } 2281da177e4SLinus Torvalds num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)]; 2291da177e4SLinus Torvalds den = 0; 2301da177e4SLinus Torvalds 2311da177e4SLinus Torvalds /* lambda[i+1] for i even is the formal derivative 2321da177e4SLinus Torvalds * lambda_pr of lambda[i] */ 2331da177e4SLinus Torvalds for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) { 2341da177e4SLinus Torvalds if (lambda[i + 1] != nn) { 2351da177e4SLinus Torvalds den ^= alpha_to[rs_modnn(rs, lambda[i + 1] + 2361da177e4SLinus Torvalds i * root[j])]; 2371da177e4SLinus Torvalds } 2381da177e4SLinus Torvalds } 2391da177e4SLinus Torvalds /* Apply error to data */ 2401da177e4SLinus Torvalds if (num1 != 0 && loc[j] >= pad) { 2411da177e4SLinus Torvalds uint16_t cor = alpha_to[rs_modnn(rs,index_of[num1] + 2421da177e4SLinus Torvalds index_of[num2] + 2431da177e4SLinus Torvalds nn - index_of[den])]; 2441da177e4SLinus Torvalds /* Store the error correction pattern, if a 2451da177e4SLinus Torvalds * correction buffer is available */ 2461da177e4SLinus Torvalds if (corr) { 2471da177e4SLinus Torvalds corr[j] = cor; 2481da177e4SLinus Torvalds } else { 2491da177e4SLinus Torvalds /* If a data buffer is given and the 2501da177e4SLinus Torvalds * error is inside the message, 2511da177e4SLinus Torvalds * correct it */ 2521da177e4SLinus Torvalds if (data && (loc[j] < (nn - nroots))) 2531da177e4SLinus Torvalds data[loc[j] - pad] ^= cor; 2541da177e4SLinus Torvalds } 2551da177e4SLinus Torvalds } 2561da177e4SLinus Torvalds } 2571da177e4SLinus Torvalds 2581da177e4SLinus Torvalds finish: 2591da177e4SLinus Torvalds if (eras_pos != NULL) { 2601da177e4SLinus Torvalds for (i = 0; i < count; i++) 2611da177e4SLinus Torvalds eras_pos[i] = loc[i] - pad; 2621da177e4SLinus Torvalds } 2631da177e4SLinus Torvalds return count; 2641da177e4SLinus Torvalds 2651da177e4SLinus Torvalds } 266