From 102a0743326a03cd1a1202ceda21e175b7d3575c Mon Sep 17 00:00:00 2001
From: hc <hc@nodka.com>
Date: Tue, 20 Feb 2024 01:20:52 +0000
Subject: [PATCH] add new system file
---
kernel/lib/reed_solomon/decode_rs.c | 99 ++++++++++++++++++++++++++++++++++++-------------
1 files changed, 72 insertions(+), 27 deletions(-)
diff --git a/kernel/lib/reed_solomon/decode_rs.c b/kernel/lib/reed_solomon/decode_rs.c
index 121beb2..805de84 100644
--- a/kernel/lib/reed_solomon/decode_rs.c
+++ b/kernel/lib/reed_solomon/decode_rs.c
@@ -22,6 +22,7 @@
uint16_t *index_of = rs->index_of;
uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error;
int count = 0;
+ int num_corrected;
uint16_t msk = (uint16_t) rs->nn;
/*
@@ -39,7 +40,7 @@
/* Check length parameter for validity */
pad = nn - nroots - len;
- BUG_ON(pad < 0 || pad >= nn);
+ BUG_ON(pad < 0 || pad >= nn - nroots);
/* Does the caller provide the syndrome ? */
if (s != NULL) {
@@ -98,8 +99,7 @@
/* if syndrome is zero, data[] is a codeword and there are no
* errors to correct. So return data[] unmodified
*/
- count = 0;
- goto finish;
+ return 0;
}
decode:
@@ -185,6 +185,15 @@
if (lambda[i] != nn)
deg_lambda = i;
}
+
+ if (deg_lambda == 0) {
+ /*
+ * deg(lambda) is zero even though the syndrome is non-zero
+ * => uncorrectable error detected
+ */
+ return -EBADMSG;
+ }
+
/* Find roots of error+erasure locator polynomial by Chien search */
memcpy(®[1], &lambda[1], nroots * sizeof(reg[0]));
count = 0; /* Number of roots of lambda(x) */
@@ -198,6 +207,12 @@
}
if (q != 0)
continue; /* Not a root */
+
+ if (k < pad) {
+ /* Impossible error location. Uncorrectable error. */
+ return -EBADMSG;
+ }
+
/* store root (index-form) and error location number */
root[count] = i;
loc[count] = k;
@@ -212,8 +227,7 @@
* deg(lambda) unequal to number of roots => uncorrectable
* error detected
*/
- count = -EBADMSG;
- goto finish;
+ return -EBADMSG;
}
/*
* Compute err+eras evaluator poly omega(x) = s(x)*lambda(x) (modulo
@@ -233,7 +247,9 @@
/*
* Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
* inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
+ * Note: we reuse the buffer for b to store the correction pattern
*/
+ num_corrected = 0;
for (j = count - 1; j >= 0; j--) {
num1 = 0;
for (i = deg_omega; i >= 0; i--) {
@@ -241,6 +257,13 @@
num1 ^= alpha_to[rs_modnn(rs, omega[i] +
i * root[j])];
}
+
+ if (num1 == 0) {
+ /* Nothing to correct at this position */
+ b[j] = 0;
+ continue;
+ }
+
num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
den = 0;
@@ -252,30 +275,52 @@
i * root[j])];
}
}
- /* Apply error to data */
- if (num1 != 0 && loc[j] >= pad) {
- uint16_t cor = alpha_to[rs_modnn(rs,index_of[num1] +
- index_of[num2] +
- nn - index_of[den])];
- /* Store the error correction pattern, if a
- * correction buffer is available */
- if (corr) {
- corr[j] = cor;
- } else {
- /* If a data buffer is given and the
- * error is inside the message,
- * correct it */
- if (data && (loc[j] < (nn - nroots)))
- data[loc[j] - pad] ^= cor;
+
+ b[j] = alpha_to[rs_modnn(rs, index_of[num1] +
+ index_of[num2] +
+ nn - index_of[den])];
+ num_corrected++;
+ }
+
+ /*
+ * We compute the syndrome of the 'error' and check that it matches
+ * the syndrome of the received word
+ */
+ for (i = 0; i < nroots; i++) {
+ tmp = 0;
+ for (j = 0; j < count; j++) {
+ if (b[j] == 0)
+ continue;
+
+ k = (fcr + i) * prim * (nn-loc[j]-1);
+ tmp ^= alpha_to[rs_modnn(rs, index_of[b[j]] + k)];
+ }
+
+ if (tmp != alpha_to[s[i]])
+ return -EBADMSG;
+ }
+
+ /*
+ * Store the error correction pattern, if a
+ * correction buffer is available
+ */
+ if (corr && eras_pos) {
+ j = 0;
+ for (i = 0; i < count; i++) {
+ if (b[i]) {
+ corr[j] = b[i];
+ eras_pos[j++] = loc[i] - pad;
}
+ }
+ } else if (data && par) {
+ /* Apply error to data and parity */
+ for (i = 0; i < count; i++) {
+ if (loc[i] < (nn - nroots))
+ data[loc[i] - pad] ^= b[i];
+ else
+ par[loc[i] - pad - len] ^= b[i];
}
}
-finish:
- if (eras_pos != NULL) {
- for (i = 0; i < count; i++)
- eras_pos[i] = loc[i] - pad;
- }
- return count;
-
+ return num_corrected;
}
--
Gitblit v1.6.2