Reed-Solomon Code: Update no_eras to the actual number of errors
RFC v2 1/1 Reed-Solomon Code: Update no_eras to the actual number of errors
Corr and eras_pos are updated to actual correction pattern and erasure positions, but no_eras is not.
When this library is used to recover lost bytes, we normally memset the lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost byte is zero, b[i] is zero too. Without correct no_eras, users won't be able to determine the valid length of corr and eras_pos.
--- drivers/md/dm-verity-fec.c | 2 +- include/linux/rslib.h | 4 ++-- lib/reed_solomon/decode_rs.c | 20 ++++++++++++++------ lib/reed_solomon/reed_solomon.c | 4 ++-- lib/reed_solomon/test_rslib.c | 18 ++++++++++++------ 5 files changed, 31 insertions(+), 17 deletions(-)
drivers/md/dm-verity-fec.c +1 -1
@@ -50,7 +50,7 @@ static int fec_decode_rs8(struct dm_verity *v, struct dm_verity_fec_io *fio,for (i =0 ; i < v->fec->roots; i++) par[i] = fec[i]; -return decode_rs8 (fio->rs, data, par, v->fec->rsn,NULL , neras, +return decode_rs8 (fio->rs, data, par, v->fec->rsn,NULL , &neras, fio->erasures,0 ,NULL ); }
include/linux/rslib.h +2 -2
@@ -64,7 +64,7 @@ int encode_rs8(struct rs_control *rs, uint8_t *data, int len, uint16_t *par,#endif #ifdef CONFIG_REED_SOLOMON_DEC8 int decode_rs8 (struct rs_control *rs,uint8_t *data,uint16_t *par,int len, -uint16_t *s,int no_eras,int *eras_pos,uint16_t invmsk, +uint16_t *s,int *no_eras,int *eras_pos,uint16_t invmsk,uint16_t *corr);#endif
@@ -75,7 +75,7 @@ int encode_rs16(struct rs_control *rs, uint16_t *data, int len, uint16_t *par,#endif #ifdef CONFIG_REED_SOLOMON_DEC16 int decode_rs16 (struct rs_control *rs,uint16_t *data,uint16_t *par,int len, -uint16_t *s,int no_eras,int *eras_pos,uint16_t invmsk, +uint16_t *s,int *no_eras,int *eras_pos,uint16_t invmsk,uint16_t *corr);#endif
lib/reed_solomon/decode_rs.c +14 -6
@@ -24,6 +24,7 @@int count =0 ;int num_corrected;uint16_t msk = (uint16_t ) rs->nn; +int no_eras_local = no_eras ? *no_eras :0 ;/* * The decoder buffers are in the rs control struct. They are
@@ -106,11 +107,11 @@memset (&lambda[1 ],0 , nroots *sizeof (lambda[0 ])); lambda[0 ] =1 ; -if (no_eras >0 ) { +if (no_eras_local >0 ) {/* Init lambda to be the erasure locator polynomial */ lambda[1 ] = alpha_to[rs_modnn (rs, prim * (nn -1 - (eras_pos[0 ] + pad)))]; -for (i =1 ; i < no_eras; i++) { +for (i =1 ; i < no_eras_local; 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 ]];
@@ -129,8 +130,8 @@* Begin Berlekamp-Massey algorithm to determine error+erasure * locator polynomial */ - r = no_eras; - el = no_eras; + r = no_eras_local; + el = no_eras_local;while (++r <= nroots) {/* r is the step number */ /* Compute discrepancy at the r-th step in poly-form */ discr_r =0 ;
@@ -158,8 +159,8 @@ }else t[i +1 ] = lambda[i +1 ]; } -if (2 * el <= r + no_eras -1 ) { - el = r + no_eras - el; +if (2 * el <= r + no_eras_local -1 ) { + el = r + no_eras_local - el;/* * 2 lines below: B(x) <-- inv(discr_r) * * lambda(x)
@@ -312,14 +313,21 @@ eras_pos[j++] = loc[i] - pad; } } +if (no_eras) + *no_eras = j; }else if (data && par) {/* Apply error to data and parity */ + j =0 ;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]; +if (b[i]) + j++; } +if (no_eras) + *no_eras = j; }return num_corrected;
lib/reed_solomon/reed_solomon.c +2 -2
@@ -359,7 +359,7 @@ EXPORT_SYMBOL_GPL(encode_rs8);* 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, +uint16_t *s,int *no_eras,int *eras_pos,uint16_t invmsk,uint16_t *corr) {#include "decode_rs.c"
@@ -410,7 +410,7 @@ EXPORT_SYMBOL_GPL(encode_rs16);* 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, +uint16_t *s,int *no_eras,int *eras_pos,uint16_t invmsk,uint16_t *corr) {#include "decode_rs.c"
lib/reed_solomon/test_rslib.c +12 -6
@@ -258,7 +258,7 @@ static void compute_syndrome(struct rs_control *rsc, uint16_t *data,/* Test up to error correction capacity */ static void test_uc (struct rs_control *rs,int len,int errs, -int eras,int trials,struct estat *stat, +int *eras,int trials,struct estat *stat,struct wspace *ws,int method) {int dlen = len - rs->codec->nroots;
@@ -327,8 +327,11 @@ static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,pr_info (" %s\n" , desc[method]);for (errs =0 ; errs <= nroots /2 ; errs++) -for (eras =0 ; eras <= nroots -2 * errs; eras++) -test_uc (rs, len, errs, eras, trials, &stat, ws, method); +for (eras =0 ; eras <= nroots -2 * errs; eras++) { +int no_eras = ers; + +test_uc (rs, len, errs, &no_eras, trials, &stat, ws, method); + }if (v >=V_CSUMMARY ) { pr_info(" Decodes wrong: %d / %d\n",
@@ -364,7 +367,7 @@ static int exercise_rs(struct rs_control *rs, struct wspace *ws,/* Tests for correct behaviour beyond error correction capacity */ static void test_bc (struct rs_control *rs,int len,int errs, -int eras,int trials,struct bcstat *stat, +int *eras,int trials,struct bcstat *stat,struct wspace *ws) {int nroots = rs->codec->nroots;
@@ -420,8 +423,11 @@ static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws, eras =0 ; cutoff = nroots <= len - errs ? nroots : len - errs; -for (; eras <= cutoff; eras++) -test_bc (rs, len, errs, eras, trials, &stat, ws); +for (; eras <= cutoff; eras++) { +int no_eras = eras; + +test_bc (rs, len, errs, &no_eras, trials, &stat, ws); + } }if (v >=V_CSUMMARY ) {
Signature · 1 line
2.25.1
Hi!
Quoted 9 lines · Aiden Leong
Corr and
eras_posare updated to actual correction pattern and erasure positions, butno_erasis not.When this library is used to recover lost bytes, we normally memset the lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost byte is zero, b[i] is zero too. Without correct
no_eras, users won't be able to determine the valid length of corr anderas_pos.Signed-off-by Aiden Leong <[email protected]>
I'm not sure I understand what you try to do. decode_rs* already returns the number of errors correted (or something negative upon failure). So your last statment is false. The lengt of corr and eras_pos is returned by the function. So this change is unnecessary. More comments inline.
Quoted 50 lines
lib/reed_solomon/decode_rs.c +7
-6@@ -24,6 +24,7 @@int count =0 ;int num_corrected;uint16_t msk = (uint16_t ) rs->nn; +int no_eras_local = no_eras ? *no_eras :0 ;/* * The decoder buffers are in the rs control struct. They are @@ -106,11 +107,11 @@memset (&lambda[1 ],0 , nroots *sizeof (lambda[0 ])); lambda[0 ] =1 ; -if (no_eras >0 ) { +if (no_eras_local >0 ) {/* Init lambda to be the erasure locator polynomial */ lambda[1 ] = alpha_to[rs_modnn (rs, prim * (nn -1 - (eras_pos[0 ] + pad)))]; -for (i =1 ; i < no_eras; i++) { +for (i =1 ; i < no_eras_local; 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 ]];@@ -129,8 +130,8 @@* Begin Berlekamp-Massey algorithm to determine error+erasure * locator polynomial */ - r = no_eras; - el = no_eras; + r = no_eras_local; + el = no_eras_local;while (++r <= nroots) {/* r is the step number */ /* Compute discrepancy at the r-th step in poly-form */ discr_r =0 ;@@ -158,8 +159,8 @@ }else t[i +1 ] = lambda[i +1 ]; } -if (2 * el <= r + no_eras -1 ) { - el = r + no_eras - el; +if (2 * el <= r + no_eras_local -1 ) { + el = r + no_eras_local - el;/* * 2 lines below: B(x) <-- inv(discr_r) * * lambda(x)
lib/reed_solomon/decode_rs.c line 317
Quoted 5 lines
lib/reed_solomon/decode_rs.c +2
-0@@ -312,14 +313,21 @@ eras_pos[j++] = loc[i] - pad; } } +if (no_eras) + *no_eras = j;
At this point j will be equal to num_corrected. So why return this information in no_eras, when it is already returned by the function?
lib/reed_solomon/decode_rs.c line 330
Quoted 13 lines
lib/reed_solomon/decode_rs.c +5
-0}else if (data && par) {/* Apply error to data and parity */ + j =0 ;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]; +if (b[i]) + j++; } +if (no_eras) + *no_eras = j;
Same as above.
Quoted 2 lines
2.25.1
Best,
Ferdinand
Signature · 3 lines
Ferdinand Blomqvist ferdinand.blomqvist[at]gmail.com GPG key: 9EFB 7A2C 0432 4EC5 32BA FA61 CFE9 4164 93E8 B9E4
Hi,
You are right. I forgot the return value is number of errors rather than status code.
Sorry to bother you.
Quoted 98 lines · Ferdinand Blomqvist
Hi!
Quoted 9 lines · Aiden Leong
Corr and
eras_posare updated to actual correction pattern and erasure positions, butno_erasis not.When this library is used to recover lost bytes, we normally memset the lost trunk of bytes to zero as a placeholder. Unfortunately, if the lost byte is zero, b[i] is zero too. Without correct
no_eras, users won't be able to determine the valid length of corr anderas_pos.Signed-off-by Aiden Leong <[email protected]>I'm not sure I understand what you try to do. decode_rs* already returns the number of errors correted (or something negative upon failure). So your last statment is false. The lengt of corr and
eras_posis returned by the function. So this change is unnecessary. More comments inline.Quoted 50 lines
lib/reed_solomon/decode_rs.c +5
-4@@ -24,6 +24,7 @@ int count = 0; int num_corrected; uint16_t msk = (uint16_t) rs->nn; + int no_eras_local = no_eras ? *no_eras : 0; /** The decoder buffers are in the rs control struct. They are @@ -106,11 +107,11 @@ memset(&lambda[1], 0, nroots * sizeof(lambda[0])); lambda[0] = 1; - if (no_eras > 0) { + if (no_eras_local > 0) { /* Init lambda to be the erasure locator polynomial */ lambda[1] = alpha_to[rs_modnn(rs, prim * (nn - 1 - (eras_pos[0] + pad)))]; - for (i = 1; i < no_eras; i++) { + for (i = 1; i < no_eras_local; 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]];@@ -129,8 +130,8 @@* Begin Berlekamp-Massey algorithm to determine error+erasure * locator polynomial */ - r = no_eras; - el = no_eras; + r = no_eras_local; + el = no_eras_local;while (++r <= nroots) { /* r is the step number */ /* Compute discrepancy at the r-th step in poly-form */
discr_r= 0;lib/reed_solomon/decode_rs.c +2
-2@@ -158,8 +159,8 @@ } else t[i + 1] = lambda[i + 1]; } - if (2 * el <= r + no_eras - 1) { - el = r + no_eras - el; + if (2 * el <= r + no_eras_local - 1) { + el = r + no_eras_local - el; /** 2 lines below: B(x) <-- inv(discr_r) * * lambda(x) lib/reed_solomon/decode_rs.c line 317
Quoted 5 lines
lib/reed_solomon/decode_rs.c +2
-0@@ -312,14 +313,21 @@ eras_pos[j++] = loc[i] - pad; } } + if (no_eras) + *no_eras = j;At this point j will be equal to
num_corrected. So why return this information inno_eras, when it is already returned by the function?Quoted 6 lines
lib/reed_solomon/decode_rs.c +1
-0} else if (data && par) { /* Apply error to data and parity */ + j = 0; for (i = 0; i < count; i++) { if (loc[i] < (nn - nroots)) data[loc[i] - pad] ^= b[i];Quoted 7 lines
else
par[loc[i] - pad - len] ^= b[i];
+ if (b[i])
+ j++;
}
+ if (no_eras)
+*no_eras= j;Same as above.
Quoted 2 lines
2.25.1
Best,
Ferdinand
kernel test robot
build bot[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use as documented in https://git-scm.com/docs/git-format-patch]
Hi Aiden,
[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on dm/for-next]
[also build test ERROR on linux/master linus/master v5.8-rc3 next-20200629] [If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/Aiden-Leong/Reed-Solomon-Code-Update-no_eras-to-the-actual-number-of-errors/20200625-153849 base: https://git.kernel.org/pub/scm/linux/kernel/git/device-mapper/linux-dm.git for-next config: sh-allyesconfig (attached as .config) compiler: sh4-linux-gcc (GCC) 9.3.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-9.3.0 make.cross ARCH=sh
If you fix the issue, kindly add following tag as appropriate
All errors (new ones prefixed by >>):
lib/reed_solomon/test_rslib.c: In function 'test_uc':
lib/reed_solomon/test_rslib.c:275:41: warning: passing argument 5 of 'get_rcw_we' makes integer from pointer without a cast [-Wint-conversion]
275 | nerrs = get_rcw_we(rs, ws, len, errs, eras);
| ^~~~
| |
| int *
lib/reed_solomon/test_rslib.c:152:27: note: expected 'int' but argument is of type 'int *'
152 | int len, int errs, int eras)
| ~~~~^~~~
lib/reed_solomon/test_rslib.c: In function 'ex_rs_helper':
>> lib/reed_solomon/test_rslib.c:331:18: error: 'ers' undeclared (first use in this function); did you mean 'eras'?
331 | int no_eras = ers;
| ^~~
| eras
lib/reed_solomon/test_rslib.c:331:18: note: each undeclared identifier is reported only once for each function it appears in
lib/reed_solomon/test_rslib.c: In function 'test_bc':
lib/reed_solomon/test_rslib.c:381:33: warning: passing argument 5 of 'get_rcw_we' makes integer from pointer without a cast [-Wint-conversion]
381 | get_rcw_we(rs, ws, len, errs, eras);
| ^~~~
| |
| int * lib/reed_solomon/test_rslib.c:152:27: note: expected 'int' but argument is of type 'int *'
152 | int len, int errs, int eras)
| ~~~~^~~~
vim +331 lib/reed_solomon/test_rslib.c
312
313 static int ex_rs_helper(struct rs_control *rs, struct wspace *ws,
314 int len, int trials, int method)
315 {
316 static const char * const desc[] = {
317 "Testing correction buffer interface...",
318 "Testing with caller provided syndrome...",
319 "Testing in-place interface..."
320 };
321
322 struct estat stat = {0, 0, 0, 0};
323 int nroots = rs->codec->nroots;
324 int errs, eras, retval;
325
326 if (v >= V_PROGRESS)
327 pr_info(" %s\n", desc[method]);
328
329 for (errs = 0; errs <= nroots / 2; errs++)
330 for (eras = 0; eras <= nroots - 2 * errs; eras++) {
> 331 int no_eras = ers;
332
333 test_uc(rs, len, errs, &no_eras, trials, &stat, ws, method);
334 }
335
336 if (v >= V_CSUMMARY) {
337 pr_info(" Decodes wrong: %d / %d\n",
338 stat.dwrong, stat.nwords);
339 pr_info(" Wrong return value: %d / %d\n",
340 stat.irv, stat.nwords);
341 if (method != IN_PLACE)
342 pr_info(" Wrong error position: %d\n", stat.wepos);
343 }
344
345 retval = stat.dwrong + stat.wepos + stat.irv;
346 if (retval && v >= V_PROGRESS)
347 pr_warn(" FAIL: %d decoding failures!\n", retval);
348
349 return retval;
350 }
351
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org