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; 25991305deSFerdinand Blomqvist int num_corrected; 261da177e4SLinus Torvalds uint16_t msk = (uint16_t) rs->nn; 271da177e4SLinus Torvalds 2845888b40SThomas Gleixner /* 2945888b40SThomas Gleixner * The decoder buffers are in the rs control struct. They are 3045888b40SThomas Gleixner * arrays sized [nroots + 1] 3145888b40SThomas Gleixner */ 3245888b40SThomas Gleixner uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1); 3345888b40SThomas Gleixner uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1); 3445888b40SThomas Gleixner uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1); 3545888b40SThomas Gleixner uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1); 3645888b40SThomas Gleixner uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1); 3745888b40SThomas Gleixner uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1); 3845888b40SThomas Gleixner uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1); 3945888b40SThomas Gleixner uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1); 4045888b40SThomas Gleixner 411da177e4SLinus Torvalds /* Check length parameter for validity */ 421da177e4SLinus Torvalds pad = nn - nroots - len; 43a343536fSFerdinand Blomqvist BUG_ON(pad < 0 || pad >= nn - nroots); 441da177e4SLinus Torvalds 451da177e4SLinus Torvalds /* Does the caller provide the syndrome ? */ 46ef4d6a85SFerdinand Blomqvist if (s != NULL) { 47ef4d6a85SFerdinand Blomqvist for (i = 0; i < nroots; i++) { 48ef4d6a85SFerdinand Blomqvist /* The syndrome is in index form, 49ef4d6a85SFerdinand Blomqvist * so nn represents zero 50ef4d6a85SFerdinand Blomqvist */ 51ef4d6a85SFerdinand Blomqvist if (s[i] != nn) 521da177e4SLinus Torvalds goto decode; 53ef4d6a85SFerdinand Blomqvist } 54ef4d6a85SFerdinand Blomqvist 55ef4d6a85SFerdinand Blomqvist /* syndrome is zero, no errors to correct */ 56ef4d6a85SFerdinand Blomqvist return 0; 57ef4d6a85SFerdinand Blomqvist } 581da177e4SLinus Torvalds 591da177e4SLinus Torvalds /* form the syndromes; i.e., evaluate data(x) at roots of 601da177e4SLinus Torvalds * g(x) */ 611da177e4SLinus Torvalds for (i = 0; i < nroots; i++) 621da177e4SLinus Torvalds syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk; 631da177e4SLinus Torvalds 641da177e4SLinus Torvalds for (j = 1; j < len; j++) { 651da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 661da177e4SLinus Torvalds if (syn[i] == 0) { 671da177e4SLinus Torvalds syn[i] = (((uint16_t) data[j]) ^ 681da177e4SLinus Torvalds invmsk) & msk; 691da177e4SLinus Torvalds } else { 701da177e4SLinus Torvalds syn[i] = ((((uint16_t) data[j]) ^ 711da177e4SLinus Torvalds invmsk) & msk) ^ 721da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 731da177e4SLinus Torvalds (fcr + i) * prim)]; 741da177e4SLinus Torvalds } 751da177e4SLinus Torvalds } 761da177e4SLinus Torvalds } 771da177e4SLinus Torvalds 781da177e4SLinus Torvalds for (j = 0; j < nroots; j++) { 791da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 801da177e4SLinus Torvalds if (syn[i] == 0) { 811da177e4SLinus Torvalds syn[i] = ((uint16_t) par[j]) & msk; 821da177e4SLinus Torvalds } else { 831da177e4SLinus Torvalds syn[i] = (((uint16_t) par[j]) & msk) ^ 841da177e4SLinus Torvalds alpha_to[rs_modnn(rs, index_of[syn[i]] + 851da177e4SLinus Torvalds (fcr+i)*prim)]; 861da177e4SLinus Torvalds } 871da177e4SLinus Torvalds } 881da177e4SLinus Torvalds } 891da177e4SLinus Torvalds s = syn; 901da177e4SLinus Torvalds 911da177e4SLinus Torvalds /* Convert syndromes to index form, checking for nonzero condition */ 921da177e4SLinus Torvalds syn_error = 0; 931da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 941da177e4SLinus Torvalds syn_error |= s[i]; 951da177e4SLinus Torvalds s[i] = index_of[s[i]]; 961da177e4SLinus Torvalds } 971da177e4SLinus Torvalds 981da177e4SLinus Torvalds if (!syn_error) { 991da177e4SLinus Torvalds /* if syndrome is zero, data[] is a codeword and there are no 1001da177e4SLinus Torvalds * errors to correct. So return data[] unmodified 1011da177e4SLinus Torvalds */ 102647cc9ecSFerdinand Blomqvist return 0; 1031da177e4SLinus Torvalds } 1041da177e4SLinus Torvalds 1051da177e4SLinus Torvalds decode: 1061da177e4SLinus Torvalds memset(&lambda[1], 0, nroots * sizeof(lambda[0])); 1071da177e4SLinus Torvalds lambda[0] = 1; 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds if (no_eras > 0) { 1101da177e4SLinus Torvalds /* Init lambda to be the erasure locator polynomial */ 1111da177e4SLinus Torvalds lambda[1] = alpha_to[rs_modnn(rs, 1122034a42dSFerdinand Blomqvist prim * (nn - 1 - (eras_pos[0] + pad)))]; 1131da177e4SLinus Torvalds for (i = 1; i < no_eras; i++) { 1142034a42dSFerdinand Blomqvist u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad))); 1151da177e4SLinus Torvalds for (j = i + 1; j > 0; j--) { 1161da177e4SLinus Torvalds tmp = index_of[lambda[j - 1]]; 1171da177e4SLinus Torvalds if (tmp != nn) { 1181da177e4SLinus Torvalds lambda[j] ^= 1191da177e4SLinus Torvalds alpha_to[rs_modnn(rs, u + tmp)]; 1201da177e4SLinus Torvalds } 1211da177e4SLinus Torvalds } 1221da177e4SLinus Torvalds } 1231da177e4SLinus Torvalds } 1241da177e4SLinus Torvalds 1251da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) 1261da177e4SLinus Torvalds b[i] = index_of[lambda[i]]; 1271da177e4SLinus Torvalds 1281da177e4SLinus Torvalds /* 1291da177e4SLinus Torvalds * Begin Berlekamp-Massey algorithm to determine error+erasure 1301da177e4SLinus Torvalds * locator polynomial 1311da177e4SLinus Torvalds */ 1321da177e4SLinus Torvalds r = no_eras; 1331da177e4SLinus Torvalds el = no_eras; 1341da177e4SLinus Torvalds while (++r <= nroots) { /* r is the step number */ 1351da177e4SLinus Torvalds /* Compute discrepancy at the r-th step in poly-form */ 1361da177e4SLinus Torvalds discr_r = 0; 1371da177e4SLinus Torvalds for (i = 0; i < r; i++) { 1381da177e4SLinus Torvalds if ((lambda[i] != 0) && (s[r - i - 1] != nn)) { 1391da177e4SLinus Torvalds discr_r ^= 1401da177e4SLinus Torvalds alpha_to[rs_modnn(rs, 1411da177e4SLinus Torvalds index_of[lambda[i]] + 1421da177e4SLinus Torvalds s[r - i - 1])]; 1431da177e4SLinus Torvalds } 1441da177e4SLinus Torvalds } 1451da177e4SLinus Torvalds discr_r = index_of[discr_r]; /* Index form */ 1461da177e4SLinus Torvalds if (discr_r == nn) { 1471da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1481da177e4SLinus Torvalds memmove (&b[1], b, nroots * sizeof (b[0])); 1491da177e4SLinus Torvalds b[0] = nn; 1501da177e4SLinus Torvalds } else { 1511da177e4SLinus Torvalds /* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */ 1521da177e4SLinus Torvalds t[0] = lambda[0]; 1531da177e4SLinus Torvalds for (i = 0; i < nroots; i++) { 1541da177e4SLinus Torvalds if (b[i] != nn) { 1551da177e4SLinus Torvalds t[i + 1] = lambda[i + 1] ^ 1561da177e4SLinus Torvalds alpha_to[rs_modnn(rs, discr_r + 1571da177e4SLinus Torvalds b[i])]; 1581da177e4SLinus Torvalds } else 1591da177e4SLinus Torvalds t[i + 1] = lambda[i + 1]; 1601da177e4SLinus Torvalds } 1611da177e4SLinus Torvalds if (2 * el <= r + no_eras - 1) { 1621da177e4SLinus Torvalds el = r + no_eras - el; 1631da177e4SLinus Torvalds /* 1641da177e4SLinus Torvalds * 2 lines below: B(x) <-- inv(discr_r) * 1651da177e4SLinus Torvalds * lambda(x) 1661da177e4SLinus Torvalds */ 1671da177e4SLinus Torvalds for (i = 0; i <= nroots; i++) { 1681da177e4SLinus Torvalds b[i] = (lambda[i] == 0) ? nn : 1691da177e4SLinus Torvalds rs_modnn(rs, index_of[lambda[i]] 1701da177e4SLinus Torvalds - discr_r + nn); 1711da177e4SLinus Torvalds } 1721da177e4SLinus Torvalds } else { 1731da177e4SLinus Torvalds /* 2 lines below: B(x) <-- x*B(x) */ 1741da177e4SLinus Torvalds memmove(&b[1], b, nroots * sizeof(b[0])); 1751da177e4SLinus Torvalds b[0] = nn; 1761da177e4SLinus Torvalds } 1771da177e4SLinus Torvalds memcpy(lambda, t, (nroots + 1) * sizeof(t[0])); 1781da177e4SLinus Torvalds } 1791da177e4SLinus Torvalds } 1801da177e4SLinus Torvalds 1811da177e4SLinus Torvalds /* Convert lambda to index form and compute deg(lambda(x)) */ 1821da177e4SLinus Torvalds deg_lambda = 0; 1831da177e4SLinus Torvalds for (i = 0; i < nroots + 1; i++) { 1841da177e4SLinus Torvalds lambda[i] = index_of[lambda[i]]; 1851da177e4SLinus Torvalds if (lambda[i] != nn) 1861da177e4SLinus Torvalds deg_lambda = i; 1871da177e4SLinus Torvalds } 188991305deSFerdinand Blomqvist 189991305deSFerdinand Blomqvist if (deg_lambda == 0) { 190991305deSFerdinand Blomqvist /* 191991305deSFerdinand Blomqvist * deg(lambda) is zero even though the syndrome is non-zero 192991305deSFerdinand Blomqvist * => uncorrectable error detected 193991305deSFerdinand Blomqvist */ 194991305deSFerdinand Blomqvist return -EBADMSG; 195991305deSFerdinand Blomqvist } 196991305deSFerdinand Blomqvist 1971da177e4SLinus Torvalds /* Find roots of error+erasure locator polynomial by Chien search */ 1981da177e4SLinus Torvalds memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); 1991da177e4SLinus Torvalds count = 0; /* Number of roots of lambda(x) */ 2001da177e4SLinus Torvalds for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) { 2011da177e4SLinus Torvalds q = 1; /* lambda[0] is always 0 */ 2021da177e4SLinus Torvalds for (j = deg_lambda; j > 0; j--) { 2031da177e4SLinus Torvalds if (reg[j] != nn) { 2041da177e4SLinus Torvalds reg[j] = rs_modnn(rs, reg[j] + j); 2051da177e4SLinus Torvalds q ^= alpha_to[reg[j]]; 2061da177e4SLinus Torvalds } 2071da177e4SLinus Torvalds } 2081da177e4SLinus Torvalds if (q != 0) 2091da177e4SLinus Torvalds continue; /* Not a root */ 210991305deSFerdinand Blomqvist 211991305deSFerdinand Blomqvist if (k < pad) { 212991305deSFerdinand Blomqvist /* Impossible error location. Uncorrectable error. */ 213991305deSFerdinand Blomqvist return -EBADMSG; 214991305deSFerdinand Blomqvist } 215991305deSFerdinand Blomqvist 2161da177e4SLinus Torvalds /* store root (index-form) and error location number */ 2171da177e4SLinus Torvalds root[count] = i; 2181da177e4SLinus Torvalds loc[count] = k; 2191da177e4SLinus Torvalds /* If we've already found max possible roots, 2201da177e4SLinus Torvalds * abort the search to save time 2211da177e4SLinus Torvalds */ 2221da177e4SLinus Torvalds if (++count == deg_lambda) 2231da177e4SLinus Torvalds break; 2241da177e4SLinus Torvalds } 2251da177e4SLinus Torvalds if (deg_lambda != count) { 2261da177e4SLinus Torvalds /* 2271da177e4SLinus Torvalds * deg(lambda) unequal to number of roots => uncorrectable 2281da177e4SLinus Torvalds * error detected 2291da177e4SLinus Torvalds */ 230647cc9ecSFerdinand Blomqvist return -EBADMSG; 2311da177e4SLinus Torvalds } 2321da177e4SLinus Torvalds /* 2331da177e4SLinus Torvalds * Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo 2341da177e4SLinus Torvalds * x**nroots). in index form. Also find deg(omega). 2351da177e4SLinus Torvalds */ 2361da177e4SLinus Torvalds deg_omega = deg_lambda - 1; 2371da177e4SLinus Torvalds for (i = 0; i <= deg_omega; i++) { 2381da177e4SLinus Torvalds tmp = 0; 2391da177e4SLinus Torvalds for (j = i; j >= 0; j--) { 2401da177e4SLinus Torvalds if ((s[i - j] != nn) && (lambda[j] != nn)) 2411da177e4SLinus Torvalds tmp ^= 2421da177e4SLinus Torvalds alpha_to[rs_modnn(rs, s[i - j] + lambda[j])]; 2431da177e4SLinus Torvalds } 2441da177e4SLinus Torvalds omega[i] = index_of[tmp]; 2451da177e4SLinus Torvalds } 2461da177e4SLinus Torvalds 2471da177e4SLinus Torvalds /* 2481da177e4SLinus Torvalds * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = 2491da177e4SLinus Torvalds * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form 250991305deSFerdinand Blomqvist * Note: we reuse the buffer for b to store the correction pattern 2511da177e4SLinus Torvalds */ 252991305deSFerdinand Blomqvist num_corrected = 0; 2531da177e4SLinus Torvalds for (j = count - 1; j >= 0; j--) { 2541da177e4SLinus Torvalds num1 = 0; 2551da177e4SLinus Torvalds for (i = deg_omega; i >= 0; i--) { 2561da177e4SLinus Torvalds if (omega[i] != nn) 2571da177e4SLinus Torvalds num1 ^= alpha_to[rs_modnn(rs, omega[i] + 2581da177e4SLinus Torvalds i * root[j])]; 2591da177e4SLinus Torvalds } 260991305deSFerdinand Blomqvist 261991305deSFerdinand Blomqvist if (num1 == 0) { 262991305deSFerdinand Blomqvist /* Nothing to correct at this position */ 263991305deSFerdinand Blomqvist b[j] = 0; 264991305deSFerdinand Blomqvist continue; 265991305deSFerdinand Blomqvist } 266991305deSFerdinand Blomqvist 2671da177e4SLinus Torvalds num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)]; 2681da177e4SLinus Torvalds den = 0; 2691da177e4SLinus Torvalds 2701da177e4SLinus Torvalds /* lambda[i+1] for i even is the formal derivative 2711da177e4SLinus Torvalds * lambda_pr of lambda[i] */ 2721da177e4SLinus Torvalds for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) { 2731da177e4SLinus Torvalds if (lambda[i + 1] != nn) { 2741da177e4SLinus Torvalds den ^= alpha_to[rs_modnn(rs, lambda[i + 1] + 2751da177e4SLinus Torvalds i * root[j])]; 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds } 278991305deSFerdinand Blomqvist 279991305deSFerdinand Blomqvist b[j] = alpha_to[rs_modnn(rs, index_of[num1] + 2801da177e4SLinus Torvalds index_of[num2] + 2811da177e4SLinus Torvalds nn - index_of[den])]; 282991305deSFerdinand Blomqvist num_corrected++; 2831da177e4SLinus Torvalds } 284991305deSFerdinand Blomqvist 285991305deSFerdinand Blomqvist /* 286991305deSFerdinand Blomqvist * We compute the syndrome of the 'error' and check that it matches 287991305deSFerdinand Blomqvist * the syndrome of the received word 288991305deSFerdinand Blomqvist */ 289991305deSFerdinand Blomqvist for (i = 0; i < nroots; i++) { 290991305deSFerdinand Blomqvist tmp = 0; 291991305deSFerdinand Blomqvist for (j = 0; j < count; j++) { 292991305deSFerdinand Blomqvist if (b[j] == 0) 293991305deSFerdinand Blomqvist continue; 294991305deSFerdinand Blomqvist 295991305deSFerdinand Blomqvist k = (fcr + i) * prim * (nn-loc[j]-1); 296991305deSFerdinand Blomqvist tmp ^= alpha_to[rs_modnn(rs, index_of[b[j]] + k)]; 297991305deSFerdinand Blomqvist } 298991305deSFerdinand Blomqvist 299991305deSFerdinand Blomqvist if (tmp != alpha_to[s[i]]) 300991305deSFerdinand Blomqvist return -EBADMSG; 301991305deSFerdinand Blomqvist } 302991305deSFerdinand Blomqvist 303991305deSFerdinand Blomqvist /* 304991305deSFerdinand Blomqvist * Store the error correction pattern, if a 305991305deSFerdinand Blomqvist * correction buffer is available 306991305deSFerdinand Blomqvist */ 307991305deSFerdinand Blomqvist if (corr && eras_pos) { 308991305deSFerdinand Blomqvist j = 0; 309991305deSFerdinand Blomqvist for (i = 0; i < count; i++) { 310991305deSFerdinand Blomqvist if (b[i]) { 311991305deSFerdinand Blomqvist corr[j] = b[i]; 312991305deSFerdinand Blomqvist eras_pos[j++] = loc[i] - pad; 313991305deSFerdinand Blomqvist } 314991305deSFerdinand Blomqvist } 315991305deSFerdinand Blomqvist } else if (data && par) { 316991305deSFerdinand Blomqvist /* Apply error to data and parity */ 317991305deSFerdinand Blomqvist for (i = 0; i < count; i++) { 318991305deSFerdinand Blomqvist if (loc[i] < (nn - nroots)) 319991305deSFerdinand Blomqvist data[loc[i] - pad] ^= b[i]; 320991305deSFerdinand Blomqvist else 321991305deSFerdinand Blomqvist par[loc[i] - pad - len] ^= b[i]; 3221da177e4SLinus Torvalds } 3231da177e4SLinus Torvalds } 3241da177e4SLinus Torvalds 325991305deSFerdinand Blomqvist return num_corrected; 3261da177e4SLinus Torvalds } 327