rslib: RS decoder is severely broken
cover rslib: RS decoder is severely broken
The Reed_Solomon library used in the kernel is based on Phil Karn's fec library. When playing with this library I found a couple of bugs. It turn out that all of these bugs, and some additional flaws, are present in rslib.
The Reed-Solomon decoder has several bugs/flaws:
- Decoding of shortened codes is broken.
- The decoder sometimes fails silently, i.e. it announces success but returns a word that is not a codeword.
- The return value of the decoder is incoherent with respect to how fixed erasures are counted. If the word to be decoded is a codeword, then the decoder always returns zero even if some erasures are given. On the other hand, if the word to be decoded contains errors, then the number of erasures is always included in the count of corrected symbols. So the decoder handles erasures without symbol corruption inconsistently. This inconsistency probably doesn't affect anyone using the decoder, but it is inconsistent with the documentation.
- The error positions returned in eras_pos include all erasures, but the corrections are only set in the correction buffer if there actually is a symbol error. So if there are erasures without symbol corruption, then the correction buffer will contain errors (unless initialized to zero before calling the decoder) or some values will be unset (if the correction buffer is uninitialized).
- Assumes that the syndromes provided by callers are in index form. This is simply undocumented.
- When correcting data in-place the decoder does not correct errors in the parity. On the other hand, when returning the errors in correction buffers, errors in the parity are included.
This series provides a module with tests for rslib and fixes all the bugs/flaws. I am not sure that the provided self tests are written in the 'right way'. I just looked at other self tests in lib and implemented something similar.
The fixes are tested with the self tests. They should probably also be tested with drivers etc. that use rslib, but it is unclear to me how to do this.
I looked a bit on two of the drivers that use rslib:
drivers/mtd/nand/raw/cafe_nand.cdrivers/mtd/nand/raw/diskonchip.c
Both of them seem to do some additional error checking after calling decode_rs16. Maybe this is needed because of the bugs in the decoder?
Ferdinand Blomqvist (7):
rslib: Add tests for the encoder and decoder
rslib: Fix decoding of shortened codes
rslib: decode_rs: Fix length parameter check
rslib: decode_rs: code cleanup
rslib: Fix handling of of caller provided syndrome
rslib: Update documentation
rslib: Fix remaining decoder flaws
lib/Kconfig.debug | 12 + lib/reed_solomon/Makefile | 2 +- lib/reed_solomon/decode_rs.c | 112 +++++-- lib/reed_solomon/reed_solomon.c | 12 +- lib/reed_solomon/test_rslib.c | 519 ++++++++++++++++++++++++++++++++ 5 files changed, 622 insertions(+), 35 deletions(-) create mode 100644 lib/reed_solomon/test_rslib.c
Signature · 1 line
2.17.2
RFC PATCH 1/7 rslib: Add tests for the encoder and decoder
A Reed-Solomon code with minimum distance d can correct any error and erasure pattern that satisfies 2 * #error + #erasures < d. If the error correction capacity is exceeded, then correct decoding cannot be guaranteed. The decoder must, however, return a valid codeword or report failure.
There are two main tests:
- Check for correct behaviour up to the error correction capacity
- Check for correct behaviour beyond error corrupted capacity
Both tests are simple:
1. Generate random data
2. Encode data with the chosen code
3. Add errors and erasures to data
4. Decode the corrupted word
5. Check for correct behaviour
When testing up to capacity we test for:
- Correct decoding
- Correct return value (i.e. the number of corrected symbols)
- That the returned error positions are correct
There are two kinds of erasures; the erased symbol can be corrupted or not. When counting the number of corrected symbols, erasures without symbol corruption should not be counted. Similarly, the returned error positions should only include positions where a correction is necessary.
We run the up to capacity tests for three different interfaces of decode_rs:
- Use the correction buffers
- Use the correction buffers with syndromes provided by the caller
- Error correction in place (does not check the error positions)
When testing beyond capacity we test for silent failures. A silent failure is when the decoder returns success but the returned word is not a valid codeword.
There are a couple of options for the tests:
- Verbosity.
- Whether to test for correct behaviour beyond capacity. Default is to test beyond capacity.
- Whether to allow erasures without symbol corruption. Defaults to yes.
Note that the tests take a couple of minutes to complete.
--- lib/Kconfig.debug | 12 + lib/reed_solomon/Makefile | 2 +- lib/reed_solomon/test_rslib.c | 519 ++++++++++++++++++++++++++++++++++ 3 files changed, 532 insertions(+), 1 deletion(-) create mode 100644 lib/reed_solomon/test_rslib.c
lib/Kconfig.debug +12 -0
@@ -1726,6 +1726,18 @@ config RBTREE_TEST A benchmark measuring the performance of the rbtree library. Also includes rbtree invariant checks. +config REED_SOLOMON_TEST + tristate "Reed-Solomon library test" + depends on DEBUG_KERNEL || m + select REED_SOLOMON + select REED_SOLOMON_ENC16 + select REED_SOLOMON_DEC16 + help + This option enables the self-test function of rslib at boot, + or at module load time. + + If unsure, say N. + config INTERVAL_TREE_TEST tristate "Interval tree test" depends on DEBUG_KERNEL
lib/reed_solomon/Makefile +1 -1
@@ -3,4 +3,4 @@ # obj-$(CONFIG_REED_SOLOMON) += reed_solomon.o - +obj-$(CONFIG_REED_SOLOMON_TEST) += test_rslib.o
lib/reed_solomon/test_rslib.c new file +519 -0
519 lines not on this page · raw message
Signature · 1 line
2.17.2
Re: [RFC PATCH 1/7] rslib: Add tests for the encoder and decoder
Ferdinand,
On Sat, 30 Mar 2019, Ferdinand Blomqvist wrote:
Sorry for the horrible long delay. I'm just drowned in backlog.
....
Quoted 10 lines
There are a couple of options for the tests:
- Verbosity.
- Whether to test for correct behaviour beyond capacity. Default is to test beyond capacity.
- Whether to allow erasures without symbol corruption. Defaults to yes.
Note that the tests take a couple of minutes to complete.
Very well written changelog!
Quoted 16 lines
lib/reed_solomon/test_rslib.c new file +16
-0+/* List of codes to test */ +static struct etab Tab[] = { + {2 ,0x7 ,1 ,1 ,1 ,100000 }, + {3 ,0xb ,1 ,1 ,2 ,100000 }, + {3 ,0xb ,1 ,1 ,3 ,100000 }, + {3 ,0xb ,2 ,1 ,4 ,100000 }, + {4 ,0x13 ,1 ,1 ,4 ,10000 }, + {5 ,0x25 ,1 ,1 ,6 ,1000 }, + {6 ,0x43 ,3 ,1 ,8 ,100 }, + {7 ,0x89 ,1 ,1 ,10 ,100 }, + {8 ,0x11d ,1 ,1 ,32 ,100 }, + {8 ,0x187 ,112 ,11 ,32 ,100 }, +/* +* {9, 0x211, 1, 1, 32, 100 }, +* {10, 0x409, 1, 1, 32, 100 }, +* {11, 0x805, 1, 1, 32, 100 },
lib/reed_solomon/test_rslib.c line 70
Quoted 10 lines
lib/reed_solomon/test_rslib.c new file +10
-0+* {12, 0x1053 1, 1, 32, 50 }, +* {12, 0x1053 1, 1, 64, 50 }, +* {13, 0x201b 1, 1, 32, 20 }, +* {13, 0x201b 1, 1, 64, 20 }, +* {14, 0x4443 1, 1, 32, 10 }, +* {14, 0x4443 1, 1, 64, 10 }, +* {15, 0x8003 1, 1, 32, 5 }, +* {15, 0x8003 1, 1, 64, 5 }, +* {16, 0x1100 1, 1, 32, 5 }, +*/
I assume these are enabled later. We don't do that commented out stuff in general. If it's used later, then add it with a separate patch. If not just leave it alone.
Quoted 15 lines
lib/reed_solomon/test_rslib.c new file +15
-0+ {0, 0, 0, 0, 0, 0}, +}; + + +struct estat { + int dwrong; + int irv; + int wepos; + int nwords; +}; + +struct bcstat { + int rfail; + int rsuccess; + int noncw;
lib/reed_solomon/test_rslib.c line 95
Quoted 10 lines
lib/reed_solomon/test_rslib.c new file +10
-0+int nwords; +}; + +struct wspace { +uint16_t *c;/* sent codeword */ +uint16_t *r;/* received word */ +uint16_t *s;/* syndrome */ +uint16_t *corr;/* correction buffer */ +int *errlocs; +int *derrlocs;
Pet pieve comment. I generally prefer tabular layout of structs as it's simpler to follow
struct wspace {
uint16_t *c; /* sent codeword */
uint16_t *r; /* received word */
uint16_t *s; /* syndrome */
uint16_t *corr; /* correction buffer */
int *errlocs;
int *derrlocs;Hmm?
Review
Quoted 2 lines
(quoted diff) +2
-0+ +static double Pad[] = {0, 0.25, 0.5, 0.75, 1.0};
This is kernel code. You cannot use the FPU without special care. But for that use case doing so would be actually overkill.
lib/reed_solomon/test_rslib.c line 464
Quoted 2 lines
lib/reed_solomon/test_rslib.c new file +2
-0+for (i =0 ; i <ARRAY_SIZE (Pad); i++) { +int pad = Pad[i] * max_pad;
That can be simply expressed:
struct pad {
int mult;
int shift;
};static struct pad pad[] = {
{ 0, 0 },
{ 1, 2 },
{ 1, 1 },
{ 3, 2 },
{ 1, 0 },
}; for (i = 0; i < ARRAY_SIZE(pad); i++) {
int pad = (pad[i].mult * max_pad) >> pad[i].shift;Also note, that I got rid of the CamelCase name.
lib/reed_solomon/test_rslib.c line 104
Quoted 5 lines
lib/reed_solomon/test_rslib.c new file +5
-0+static struct wspace *alloc_ws (struct rs_codec *rs) +{ +int nn = rs->nn; +int nroots = rs->nroots; +struct wspace *ws;
Yet another pet pieve comment for readability. Order variables in reverse fir tree order.
int nroots = rs->nroots; struct wspace *ws; int nn = rs->nn;
Quoted 14 lines
lib/reed_solomon/test_rslib.c new file +14
-0+ ws =kzalloc (sizeof (*ws),GFP_KERNEL ); +if (!ws) +return NULL ; + + ws->c =kmalloc_array (2 * (nn + nroots), +sizeof (uint16_t ),GFP_KERNEL ); +if (!ws->c) + goto err; + + ws->r = ws->c + nn; + ws->s = ws->r + nn; + ws->corr = ws->s + nroots; + + ws->errlocs =kmalloc_array (nn + nroots,sizeof (int ),GFP_KERNEL );
lib/reed_solomon/test_rslib.c line 129
Quoted 10 lines
lib/reed_solomon/test_rslib.c new file +10
-0+if (!ws->c) + goto err; + + ws->derrlocs = ws->errlocs + nn; +return ws; + +err: +kfree (ws->errlocs); +kfree (ws->c); +kfree (ws);
If you move free_ws() above this function you can replace this kfree() sequence with
free_ws();
Review
Quoted 1 line
(quoted diff) +1
-0+ return NULL;
Just nitpicks, except for the FPU issue. Other than that this looks great.
Thanks,
tglx
RFC PATCH 2/7 rslib: Fix decoding of shortened codes
In reply to Ferdinand BlomqvistThe decoder is broken. It only works with full length codes.
--- lib/reed_solomon/decode_rs.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/reed_solomon/decode_rs.c +2 -2
@@ -99,9 +99,9 @@if (no_eras >0 ) {/* Init lambda to be the erasure locator polynomial */ lambda[1 ] = alpha_to[rs_modnn (rs, - prim * (nn -1 - eras_pos[0 ]))]; + prim * (nn -1 - (eras_pos[0 ] + pad)))];for (i =1 ; i < no_eras; i++) { - u =rs_modnn (rs, prim * (nn -1 - eras_pos[i])); + u =rs_modnn (rs, prim * (nn -1 - (eras_pos[i] + pad)));for (j = i +1 ; j >0 ; j--) { tmp = index_of[lambda[j -1 ]];if (tmp != nn) {
Signature · 1 line
2.17.2
Re: [RFC PATCH 2/7] rslib: Fix decoding of shortened codes
Ferdinand,
Quoted 1 line · Ferdinand Blomqvist
The decoder is broken. It only works with full length codes.
A short explanation what is missing and what is done to fix it would be appreciated.
Quoted 11 lines
Signed-off-by Ferdinand Blomqvist <[email protected]>--- lib/reed_solomon/decode_rs.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)lib/reed_solomon/decode_rs.c +0
-0@@ -99,9 +99,9 @@if (no_eras >0 ) {
lib/reed_solomon/decode_rs.c line 107
Quoted 10 lines
lib/reed_solomon/decode_rs.c +2
-2/* Init lambda to be the erasure locator polynomial */ lambda[1 ] = alpha_to[rs_modnn (rs, - prim * (nn -1 - eras_pos[0 ]))]; + prim * (nn -1 - (eras_pos[0 ] + pad)))];for (i =1 ; i < no_eras; i++) { - u =rs_modnn (rs, prim * (nn -1 - eras_pos[i])); + u =rs_modnn (rs, prim * (nn -1 - (eras_pos[i] + pad)));for (j = i +1 ; j >0 ; j--) { tmp = index_of[lambda[j -1 ]];if (tmp != nn) {
Code looks fine as is.
Thanks,
tglx
RFC PATCH 3/7 rslib: decode_rs: Fix length parameter check
In reply to Ferdinand BlomqvistThe length of the data load must be at least one. Or in other words, there must be room for at least 1 data and nroots parity symbols after shortening the RS code.
--- lib/reed_solomon/decode_rs.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
lib/reed_solomon/decode_rs.c +1 -1
@@ -39,7 +39,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 )
Signature · 1 line
2.17.2
Re: [RFC PATCH 3/7] rslib: decode_rs: Fix length parameter check
Quoted 3 lines · Ferdinand Blomqvist
The length of the data load must be at least one. Or in other words, there must be room for at least 1 data and nroots parity symbols after shortening the RS code.
Indeed!
RFC PATCH 4/7 rslib: decode_rs: code cleanup
In reply to Ferdinand BlomqvistNothing useful was done after the finish label when count is negative so return directly instead of jumping to finish.
--- lib/reed_solomon/decode_rs.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-)
lib/reed_solomon/decode_rs.c +2 -5
@@ -88,8 +88,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:
@@ -202,8 +201,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
@@ -261,7 +259,6 @@ } } -finish:if (eras_pos !=NULL ) {for (i =0 ; i < count; i++) eras_pos[i] = loc[i] - pad;
Signature · 1 line
2.17.2
Re: [RFC PATCH 4/7] rslib: decode_rs: code cleanup
Quoted 2 lines · Ferdinand Blomqvist
Nothing useful was done after the finish label when count is negative so return directly instead of jumping to finish.
Make sense.
Thanks,
tglx
RFC PATCH 5/7 rslib: Fix handling of of caller provided syndrome
In reply to Ferdinand BlomqvistCheck if the syndrome provided by the caller is zero, and act accordingly.
--- lib/reed_solomon/decode_rs.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)
lib/reed_solomon/decode_rs.c +10 -2
@@ -42,8 +42,16 @@BUG_ON (pad <0 || pad >= nn - nroots);/* Does the caller provide the syndrome ? */ -if (s !=NULL ) - goto decode; +if (s !=NULL ) { +for (i =0 ; i < nroots; i++) { +/* The syndrome is in index form, so nn represents zero */ +if (s[i] != nn) + goto decode; + } + +/* syndrome is zero, no errors to correct */ +return 0 ; + }/* form the syndromes; i.e., evaluate data(x) at roots of * g(x) */
Signature · 1 line
2.17.2
Re: [RFC PATCH 5/7] rslib: Fix handling of of caller provided syndrome
Quoted 2 lines · Ferdinand Blomqvist
Check if the syndrome provided by the caller is zero, and act accordingly.
Makes sense. IIRC I did not add that as the only caller doing this back then checked that at the call site. But yes for correctness sake this is a good change.
Thanks,
tglx
RFC PATCH 6/7 rslib: Update documentation
In reply to Ferdinand BlomqvistThe decoder returns the number of corrected symbols, not bits. The caller provided syndrome must be in index form.
--- lib/reed_solomon/reed_solomon.c | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-)
lib/reed_solomon/reed_solomon.c +8 -4
@@ -340,7 +340,8 @@ EXPORT_SYMBOL_GPL(encode_rs8);* @data: data field of a given type * @par: received parity data field * @len: data length -* @s: syndrome data field (if NULL, syndrome is calculated) +* @s: syndrome data field, must be in index form +* (if NULL, syndrome is calculated) * @no_eras: number of erasures * @eras_pos: position of erasures, can be NULL * @invmsk: invert data mask (will be xored on data, not on parity!)
@@ -354,7 +355,8 @@ EXPORT_SYMBOL_GPL(encode_rs8);* decoding, so the caller has to ensure that decoder invocations are * serialized. * -* Returns the number of corrected bits or -EBADMSG for uncorrectable errors. +* Returns the number of corrected symbols or -EBADMSG for uncorrectable +* errors. The count includes errors in the parity. */ int decode_rs8(struct rs_control *rsc, uint8_t *data, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
@@ -391,7 +393,8 @@ EXPORT_SYMBOL_GPL(encode_rs16);* @data: data field of a given type * @par: received parity data field * @len: data length -* @s: syndrome data field (if NULL, syndrome is calculated) +* @s: syndrome data field, must be in index form +* (if NULL, syndrome is calculated) * @no_eras: number of erasures * @eras_pos: position of erasures, can be NULL * @invmsk: invert data mask (will be xored on data, not on parity!)
@@ -403,7 +406,8 @@ EXPORT_SYMBOL_GPL(encode_rs16);* decoding, so the caller has to ensure that decoder invocations are * serialized. * -* Returns the number of corrected bits or -EBADMSG for uncorrectable errors. +* Returns the number of corrected symbols or -EBADMSG for uncorrectable +* errors. The count includes errors in the parity. */ int decode_rs16(struct rs_control *rsc, uint16_t *data, uint16_t *par, int len, uint16_t *s, int no_eras, int *eras_pos, uint16_t invmsk,
Signature · 1 line
2.17.2
Re: [RFC PATCH 6/7] rslib: Update documentation
Quoted 2 lines · Ferdinand Blomqvist
The decoder returns the number of corrected symbols, not bits. The caller provided syndrome must be in index form.
Right.
Thanks,
tglx
RFC PATCH 7/7 rslib: Fix remaining decoder flaws
In reply to Ferdinand BlomqvistThe decoder is flawed in the following ways:
- The decoder sometimes fails silently, i.e. it announces success but returns a word that is not a codeword.
- The return value of the decoder is incoherent with respect to how fixed erasures are counted. If the word to be decoded is a codeword, then the decoder always returns zero even if some erasures are given. On the other hand, if the word to be decoded contains errors, then the number of erasures is always included in the count of corrected symbols. So the decoder handles erasures without symbol corruption inconsistently. This inconsistency probably doesn't affect anyone using the decoder, but it is inconsistent with the documentation.
- The error positions returned in eras_pos include all erasures, but the corrections are only set in the correction buffer if there actually is a symbol error. So if there are erasures without symbol corruption, then the correction buffer will contain errors (unless initialized to zero before calling the decoder) or some values will be unset (if the correction buffer is uninitialized).
- When correcting data in-place the decoder does not correct errors in the parity. On the other hand, when returning the errors in correction buffers, errors in the parity are included.
The respective fixed are:
- The syndrome of a codeword is always zero, and the syndrome is linear, .i.e, S(x+e) = S(x) + S(e). So compute the syndrome for the error and check whether it equals the syndrome of the received word. If it does, then we have decoded to a valid codeword, otherwise we know that we have an uncorrectable error. Fortunately, some unrecoverable error conditions can be detected earlier in the decoding, which saves some processing power.
- Simply count and return the number of symbols actually corrected.
- Make sure to only return positions where symbols were corrected.
- Also fix errors in parity when correcting in-place. Another option would be to completely disregard errors in the parity, but then the interface makes it impossible to write tests that test for silent failures.
Other changes:
- Only fill the correction buffer and error position buffer if both of them are provided. Otherwise correct in place. Previously the error position buffer was always populated with the positions of the corrected errors, irrespective of whether a correction buffer was supplied or not. The rationale for this change is that there seems to be two use cases for the decoder; correct in-place or use the correction buffers. The caller does not need the positions of the corrected errors when in-place correction is used. If in-place correction is not used, then both the correction buffer and error position buffer need to be populated.
--- lib/reed_solomon/decode_rs.c | 87 +++++++++++++++++++++++++++--------- 1 file changed, 67 insertions(+), 20 deletions(-)
lib/reed_solomon/decode_rs.c +67 -20
@@ -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;/*
@@ -182,6 +183,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) */
@@ -195,6 +205,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;
@@ -229,7 +245,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--) {
@@ -237,6 +255,12 @@ num1 ^= alpha_to[rs_modnn (rs, omega[i] + i * root[j])]; } + +if (num1 ==0 ) { + b[j] =0 ; +continue ; + } + num2 = alpha_to[rs_modnn (rs, root[j] * (fcr -1 ) + nn)]; den =0 ;
@@ -248,29 +272,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' to 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 ; } -if (eras_pos !=NULL ) { -for (i =0 ; i < count; i++) - eras_pos[i] = loc[i] - pad; +/* +* 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]; + } } -return count; +return num_corrected; }
Signature · 1 line
2.17.2
Re: [RFC PATCH 7/7] rslib: Fix remaining decoder flaws
Quoted 1 line · Ferdinand Blomqvist
The decoder is flawed in the following ways:
...
Quoted 7 lines
- Also fix errors in parity when correcting in-place. Another option would be to completely disregard errors in the parity, but then the interface makes it impossible to write tests that test for silent failures.
Other changes:
Quoted 10 lines
- Only fill the correction buffer and error position buffer if both of them are provided. Otherwise correct in place. Previously the error position buffer was always populated with the positions of the corrected errors, irrespective of whether a correction buffer was supplied or not. The rationale for this change is that there seems to be two use cases for the decoder; correct in-place or use the correction buffers. The caller does not need the positions of the corrected errors when in-place correction is used. If in-place correction is not used, then both the correction buffer and error position buffer need to be populated.
Again. A perfect changelog! Very nice to read, informative and technically on the point.
Quoted 13 lines
lib/reed_solomon/decode_rs.c +1
-0@@ -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;/*
lib/reed_solomon/decode_rs.c line 192
Quoted 10 lines
lib/reed_solomon/decode_rs.c +7
-0@@ -182,6 +183,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 ;
Good catch. Now that I paged all that stuff back in it's obvious.
lib/reed_solomon/decode_rs.c line 211
Quoted 13 lines
lib/reed_solomon/decode_rs.c +6
-0+ } +/* 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) */ @@ -195,6 +205,12 @@ }if (q !=0 )continue ;/* Not a root */ + +if (k < pad) { +/* Impossible error location. Uncorrectable error. */ +return -EBADMSG ;
True.
Quoted 16 lines
lib/reed_solomon/decode_rs.c +4
-0+ } +/* store root (index-form) and error location number */ root[count] = i; loc[count] = k;@@ -229,7 +245,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--) {
lib/reed_solomon/decode_rs.c line 261
Quoted 7 lines
lib/reed_solomon/decode_rs.c +4
-0@@ -237,6 +255,12 @@ num1 ^= alpha_to[rs_modnn (rs, omega[i] + i * root[j])]; } + +if (num1 ==0 ) { + b[j] =0 ; +continue ;
A comment for this would be appreciated.
Quoted 19 lines
lib/reed_solomon/decode_rs.c +2
-10+ } + num2 = alpha_to[rs_modnn (rs, root[j] * (fcr -1 ) + nn)]; den =0 ;@@ -248,29 +272,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 {
lib/reed_solomon/decode_rs.c line 278
Quoted 10 lines
lib/reed_solomon/decode_rs.c +4
-6-/* 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])];
Way simpler indeed.
lib/reed_solomon/decode_rs.c line 283
Quoted 5 lines
lib/reed_solomon/decode_rs.c +5
-0+ num_corrected++; + } + +/* +* We compute the syndrome of the 'error' to and check that it matches
s/to// or s/to/too ?
Quoted 4 lines
lib/reed_solomon/decode_rs.c +4
-0+* the syndrome of the received word +*/ +for (i =0 ; i < nroots; i++) { + tmp =0 ;
lib/reed_solomon/decode_rs.c line 297
Quoted 10 lines
lib/reed_solomon/decode_rs.c +9
-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 ;
Interesting it never occured to me that this can actually happen.
Quoted 15 lines
lib/reed_solomon/decode_rs.c +10
-3} -if (eras_pos !=NULL ) { -for (i =0 ; i < count; i++) - eras_pos[i] = loc[i] - pad; +/* +* 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;
lib/reed_solomon/decode_rs.c line 319
Quoted 10 lines
lib/reed_solomon/decode_rs.c +10
-0+ } + } + }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]; + }
Aside of the fact that I had to wrap my brain around this crime I committed more than a decade ago, all of this was really a pleasure to review.
Thanks a lot for putting that effort in! I'm looking forward to V2 of that.
Thanks,
tglx
Re: [RFC PATCH 7/7] rslib: Fix remaining decoder flaws
Hi,
Quoted 5 lines · Thomas Gleixner
Quoted 1 line · Ferdinand Blomqvist
The decoder is flawed in the following ways:
...
Quoted 8 lines
Aside of the fact that I had to wrap my brain around this crime I committed more than a decade ago, all of this was really a pleasure to review.
Thanks a lot for putting that effort in! I'm looking forward to V2 of that.
Thanks,
tglx
Thanks for the review and comments! Will submit V2 shortly. Hopefully it addresses all concerns and suggestions in a satisfactory way.
Best,
Ferdinand
Ferdinand,
On Sat, 30 Mar 2019, Ferdinand Blomqvist wrote:
Thanks for providing that! I'm short of cycles to go through that right now, but will do in the foreseeable future. Feel free to remind me if I don't do so within two weeks.
Thanks,
tglx
Quoted 4 lines · Thomas Gleixner
Ferdinand,
On Sat, 30 Mar 2019, Ferdinand Blomqvist wrote:
Quoted 8 lines
Thanks for providing that! I'm short of cycles to go through that right now, but will do in the foreseeable future. Feel free to remind me if I don't do so within two weeks.
Thanks,
tglx
A gentle reminder.
Signature · 3 lines
Ferdinand Blomqvist ferdinand.blomqvist[at]gmail.com GPG key: 9EFB 7A2C 0432 4EC5 32BA FA61 CFE9 4164 93E8 B9E4
Quoted 10 lines · Ferdinand Blomqvist
Quoted 7 lines · Thomas Gleixner
Ferdinand,
On Sat, 30 Mar 2019, Ferdinand Blomqvist wrote:
Thanks for providing that! I'm short of cycles to go through that right now, but will do in the foreseeable future. Feel free to remind me if I don't do so within two weeks.
A gentle reminder.
Working through it. Need to page in all the details :(
Thanks,
tglx