lkml.org 
[lkml]   [2022]   [Jun]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[RFC PATCH] rslib: Replace hard-coded 1 with alpha_to[0]
Date
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(&reg[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
\
 
 \ /
  Last update: 2022-06-05 09:40    [W:0.069 / U:0.188 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site