rslib: Replace hard-coded 1 with alpha_to[0]
RFC PATCH 1/1 rslib: Replace hard-coded 1 with alpha_to[0]
Comments for RFC:
Hello,
I found problems in rslib when I specify `gffunc' as myfunc(x) = bswap_16(gffunc(x)). This patch fixes these problems, please refer to commit message below for details. Since I'm not experienced with GF fields, so I would like to invite people to review my patch.
If not using init_rs_non_canonical(), the change is trivial because alpha_to[0] is always 1. So this patch should introduce no regression and safe to merge.
The modifications to `test_rslib.c' are not intended to commit, just for showing the idea and a small self-test. It will be removed if this patch is going to be merged.
The reason I want to use this `gffunc' is because I'm going to implement Reed-Solomon for BTRFS filesystem. As on-disk-format is little endian, the code of file system must deal with little-endian reed solomon symbols on big-endian machines. One possible approach is to do bswap_16 on every symbol when encoding/decoding, which is not very good. Another approach is to bswap_16 the GF field, so no additional bswap_16 when encoding/decoding is required. This will expose the above problem because gffunc(0) is 0x0100 instead of 0x0001 in that field.
Thanks!
Best Regards,
Zhang Boyang
===
Currently the rslib allows customizing the finite field by the `gffunc' parameter of init_rs_non_canonical(). However, there are several places in rslib use hard-coded 1 instead of alpha_to[0], leading errors if gffunc(0) != 1. This patch fixes the problem. One of such gffunc might be gffunc'(x) = bswap_16(gffunc(x)). This is useful to implement foreign-endian RS coder for 16 bit symbols.
--- lib/reed_solomon/decode_rs.c | 4 ++-- lib/reed_solomon/reed_solomon.c | 4 ++-- lib/reed_solomon/test_rslib.c | 23 ++++++++++++++++++++--- 3 files changed, 24 insertions(+), 7 deletions(-)
lib/reed_solomon/decode_rs.c +2 -2
@@ -104,7 +104,7 @@ decode:memset (&lambda[1 ],0 , nroots *sizeof (lambda[0 ])); - lambda[0 ] =1 ; + lambda[0 ] = alpha_to[0 ];if (no_eras >0 ) {/* Init lambda to be the erasure locator polynomial */
@@ -198,7 +198,7 @@memcpy (®[1 ], &lambda[1 ], nroots *sizeof (reg[0 ])); count =0 ;/* Number of roots of lambda(x) */ for (i =1 , k = iprim -1 ; i <= nn; i++, k =rs_modnn (rs, k + iprim)) { - q =1 ;/* lambda[0] is always 0 */ + q = alpha_to[0 ];/* lambda[0] is always 0 */ for (j = deg_lambda; j >0 ; j--) {if (reg[j] != nn) { reg[j] =rs_modnn (rs, reg[j] + j);
lib/reed_solomon/reed_solomon.c +2 -2
@@ -131,9 +131,9 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int), rs->iprim = iprim / prim;/* Form RS code generator polynomial from its roots */ - rs->genpoly[0 ] =1 ; + rs->genpoly[0 ] = rs->alpha_to[0 ];for (i =0 , root = fcr * prim; i < nroots; i++, root += prim) { - rs->genpoly[i +1 ] =1 ; + rs->genpoly[i +1 ] = rs->alpha_to[0 ];/* Multiply rs->genpoly[] by @**(root + x) */ for (j = i; j >0 ; j--) {if (rs->genpoly[j] !=0 ) {
lib/reed_solomon/test_rslib.c +20 -3
@@ -42,9 +42,11 @@ struct etab {int ntrials; }; +#define RS16_GFPOLY 0x1002d +/* List of codes to test */ static struct etab Tab[] = { - {2 ,0x7 ,1 ,1 ,1 ,100000 }, +/*{2, 0x7, 1, 1, 1, 100000 }, {3, 0xb, 1, 1, 2, 100000 }, {3, 0xb, 1, 1, 3, 100000 }, {3, 0xb, 2, 1, 4, 100000 },
@@ -54,7 +56,8 @@ static struct etab Tab[] = {{7, 0x89, 1, 1, 14, 500 }, {8, 0x11d, 1, 1, 30, 100 }, {8, 0x187, 112, 11, 32, 100 }, - {9, 0x211, 1, 1, 33, 80 }, +{9, 0x211, 1, 1, 33, 80 },*/ + {16,RS16_GFPOLY,1, 1, 33, 100 }, {0, 0, 0, 0, 0, 0}, };
@@ -439,6 +442,19 @@ static int exercise_rs_bc(struct rs_control *rs, struct wspace *ws,return stat.noncw; } + +static int gf_mul (int x) +{ +//printk("x=%04x\n", x); + x =be16_to_cpu (x); +if (x ==0 ) +return cpu_to_be16 (1 ); + x <<=1 ; +if (x &0x10000 ) + x ^=RS16_GFPOLY ; + x &=0xFFFF ; +return cpu_to_be16 (x); +}static int run_exercise (struct etab *e) {int nn = (1 << e->symsize) -1 ;
@@ -450,7 +466,8 @@ static int run_exercise(struct etab *e)struct wspace *ws;int i; - rsc =init_rs (e->symsize, e->genpoly, e->fcs, e->prim, e->nroots); +//rsc = init_rs(e->symsize, e->genpoly, e->fcs, e->prim, e->nroots); + rsc =init_rs_non_canonical (e->symsize, gf_mul, e->fcs, e->prim, e->nroots);if (!rsc)return retval;
Signature · 1 line
2.30.2
PATCH 1/2 rslib: Replace hard-coded 1 with alpha_to[0]
Currently the rslib allows customizing the finite field by the `gffunc' parameter of init_rs_non_canonical(). However, there are several places in rslib use hard-coded 1 instead of alpha_to[0], leading to errors if gffunc(0) != 1. This patch fixes the problem. One of such `gffunc' might be gffunc'(x) = swab16(gffunc(swab16(x))), as gffunc'(0) = swab16(1). This special gffunc'(x) is useful when implementing RS coder for 16 bit foreign-endian symbols.
--- lib/reed_solomon/decode_rs.c | 4 ++-- lib/reed_solomon/reed_solomon.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-)
lib/reed_solomon/decode_rs.c +2 -2
@@ -104,7 +104,7 @@ decode:memset (&lambda[1 ],0 , nroots *sizeof (lambda[0 ])); - lambda[0 ] =1 ; + lambda[0 ] = alpha_to[0 ];if (no_eras >0 ) {/* Init lambda to be the erasure locator polynomial */
@@ -198,7 +198,7 @@memcpy (®[1 ], &lambda[1 ], nroots *sizeof (reg[0 ])); count =0 ;/* Number of roots of lambda(x) */ for (i =1 , k = iprim -1 ; i <= nn; i++, k =rs_modnn (rs, k + iprim)) { - q =1 ;/* lambda[0] is always 0 */ + q = alpha_to[0 ];/* lambda[0] is always 0 */ for (j = deg_lambda; j >0 ; j--) {if (reg[j] != nn) { reg[j] =rs_modnn (rs, reg[j] + j);
lib/reed_solomon/reed_solomon.c +2 -2
@@ -131,9 +131,9 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int), rs->iprim = iprim / prim;/* Form RS code generator polynomial from its roots */ - rs->genpoly[0 ] =1 ; + rs->genpoly[0 ] = rs->alpha_to[0 ];for (i =0 , root = fcr * prim; i < nroots; i++, root += prim) { - rs->genpoly[i +1 ] =1 ; + rs->genpoly[i +1 ] = rs->alpha_to[0 ];/* Multiply rs->genpoly[] by @**(root + x) */ for (j = i; j >0 ; j--) {if (rs->genpoly[j] !=0 ) {
Signature · 1 line
2.30.2
PATCH 2/2 rslib: Introduce init_rs16()
This patch introduces init_rs16(). This function creates a RS coder for exactly 16 bit symbols and it provides a special parameter bool gfswab' which indicates whether to treat symbols as foreign endian. If gfswab' is true, the coder will act as if all reads/writes to symbols is byte-swapped. This is useful, for example, when a big-endian machine want to decode symbols generated on a little-endian machine.
--- include/linux/rslib.h | 24 +++++++++++++++++ lib/reed_solomon/reed_solomon.c | 48 ++++++++++++++++++++++++++++----- lib/reed_solomon/test_rslib.c | 31 ++++++++++++--------- 3 files changed, 84 insertions(+), 19 deletions(-)
include/linux/rslib.h +24 -0
@@ -28,6 +28,7 @@* @iprim: prim-th root of 1, index form * @gfpoly: The primitive generator polynominal * @gffunc: Function to generate the field, if non-canonical representation +* @gfswab: Treat symbols as foreign endian, may be true only if mm = 16 * @users: Users of this structure * @list: List entry for the rs codec list */
@@ -43,6 +44,7 @@ struct rs_codec {int iprim;int gfpoly;int (*gffunc)(int ); +bool gfswab;int users;struct list_head list; };
@@ -101,6 +103,28 @@ static inline struct rs_control *init_rs(int symsize, int gfpoly, int fcr,return init_rs_gfp (symsize, gfpoly, fcr, prim, nroots,GFP_KERNEL ); } +struct rs_control *init_rs16_gfp (int gfpoly,bool gfswab,int fcr,int prim, +int nroots,gfp_t gfp); + +/** +* init_rs16 - Allocate rs control struct for 16 bit symbols +* @gfpoly: the extended Galois field generator polynomial coefficients, +* with the 0th coefficient in the low order bit. The polynomial +* must be primitive; +* @gfswab: Treat symbols as foreign endian +* @fcr: the first consecutive root of the rs code generator polynomial +* in index form +* @prim: primitive element to generate polynomial roots +* @nroots: RS code generator polynomial degree (number of roots) +* +* Allocations use GFP_KERNEL. +*/ +static inline struct rs_control *init_rs16 (int gfpoly,bool gfswab,int fcr, +int prim,int nroots) +{ +return init_rs16_gfp (gfpoly, gfswab, fcr, prim, nroots,GFP_KERNEL ); +} +struct rs_control *init_rs_non_canonical (int symsize,int (*func)(int ),int fcr,int prim,int nroots);
lib/reed_solomon/reed_solomon.c +41 -7
126 lines not on this page · raw message
lib/reed_solomon/test_rslib.c +19 -12
@@ -36,6 +36,7 @@ __param(int, bc, 1, "Test for correct behaviour beyond error correction capacitystruct etab {int symsize;int genpoly; +bool byteswap;int fcs;int prim;int nroots;
@@ -44,17 +45,18 @@ struct etab {/* 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 ,1000 }, - {7 ,0x89 ,1 ,1 ,14 ,500 }, - {8 ,0x11d ,1 ,1 ,30 ,100 }, - {8 ,0x187 ,112 ,11 ,32 ,100 }, - {9 ,0x211 ,1 ,1 ,33 ,80 }, + {2 ,0x7 , false,1 ,1 ,1 ,100000 }, + {3 ,0xb , false,1 ,1 ,2 ,100000 }, + {3 ,0xb , false,1 ,1 ,3 ,100000 }, + {3 ,0xb , false,2 ,1 ,4 ,100000 }, + {4 ,0x13 , false,1 ,1 ,4 ,10000 }, + {5 ,0x25 , false,1 ,1 ,6 ,1000 }, + {6 ,0x43 , false,3 ,1 ,8 ,1000 }, + {7 ,0x89 , false,1 ,1 ,14 ,500 }, + {8 ,0x11d , false,1 ,1 ,30 ,100 }, + {8 ,0x187 , false,112 ,11 ,32 ,100 }, + {9 ,0x211 , false,1 ,1 ,33 ,80 }, + {16 ,0x1002d , true,1 ,1 ,33 ,5 }, {0 ,0 ,0 ,0 ,0 ,0 }, };
@@ -450,7 +452,12 @@ static int run_exercise(struct etab *e)struct wspace *ws;int i; - rsc =init_rs (e->symsize, e->genpoly, e->fcs, e->prim, e->nroots); +if (e->symsize !=16 ) + rsc =init_rs (e->symsize, e->genpoly, + e->fcs, e->prim, e->nroots); +else + rsc =init_rs16 (e->genpoly, e->byteswap, + e->fcs, e->prim, e->nroots);if (!rsc)return retval;
Signature · 1 line
2.30.2