Messages in this thread Patch in this message | | | From | Zhang Boyang <> | Subject | [RFC PATCH] rslib: Replace hard-coded 1 with alpha_to[0] | Date | Sun, 5 Jun 2022 15:38:57 +0800 |
| |
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.
Signed-off-by: Zhang Boyang <zhangboyang.id@gmail.com> --- 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(-)
diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c index 805de84ae83d..6c1d53d1b702 100644 --- a/lib/reed_solomon/decode_rs.c +++ b/lib/reed_solomon/decode_rs.c @@ -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); diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c index bbc01bad3053..bb4f44c8edba 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -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) { diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c index d9d1c33aebda..1c7fefcc89f2 100644 --- a/lib/reed_solomon/test_rslib.c +++ b/lib/reed_solomon/test_rslib.c @@ -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; -- 2.30.2
| |