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 <[email protected]>
---
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
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.
Signed-off-by: Zhang Boyang <[email protected]>
---
lib/reed_solomon/decode_rs.c | 4 ++--
lib/reed_solomon/reed_solomon.c | 4 ++--
2 files changed, 4 insertions(+), 4 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) {
--
2.30.2
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.
Signed-off-by: Zhang Boyang <[email protected]>
---
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(-)
diff --git a/include/linux/rslib.h b/include/linux/rslib.h
index 238bb85243d3..bd38e1285997 100644
--- a/include/linux/rslib.h
+++ b/include/linux/rslib.h
@@ -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);
diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomon.c
index bb4f44c8edba..8f25b539e3a5 100644
--- a/lib/reed_solomon/reed_solomon.c
+++ b/lib/reed_solomon/reed_solomon.c
@@ -56,9 +56,10 @@ static DEFINE_MUTEX(rslistlock);
/**
* codec_init - Initialize a Reed-Solomon codec
- * @symsize: symbol size, bits (1-8)
+ * @symsize: the symbol size (number of bits)
* @gfpoly: Field generator polynomial coefficients
* @gffunc: Field generator function
+ * @gfswab: Treat symbols as foreign endian, may be true only if symsize=16
* @fcr: first root of RS code generator polynomial, index form
* @prim: primitive element to generate polynomial roots
* @nroots: RS code generator polynomial degree (number of roots)
@@ -67,7 +68,8 @@ static DEFINE_MUTEX(rslistlock);
* Allocate a codec structure and the polynom arrays for faster
* en/decoding. Fill the arrays according to the given parameters.
*/
-static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
+static struct rs_codec *codec_init(int symsize,
+ int gfpoly, int (*gffunc)(int), bool gfswab,
int fcr, int prim, int nroots, gfp_t gfp)
{
int i, j, sr, root, iprim;
@@ -86,6 +88,7 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
rs->nroots = nroots;
rs->gfpoly = gfpoly;
rs->gffunc = gffunc;
+ rs->gfswab = gfswab;
/* Allocate the arrays */
rs->alpha_to = kmalloc_array(rs->nn + 1, sizeof(uint16_t), gfp);
@@ -105,13 +108,16 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
rs->alpha_to[rs->nn] = 0; /* alpha**-inf = 0 */
if (gfpoly) {
sr = 1;
+ sr = gfswab ? swab16(sr) : sr;
for (i = 0; i < rs->nn; i++) {
rs->index_of[sr] = i;
rs->alpha_to[i] = sr;
+ sr = gfswab ? swab16(sr) : sr;
sr <<= 1;
if (sr & (1 << symsize))
sr ^= gfpoly;
sr &= rs->nn;
+ sr = gfswab ? swab16(sr) : sr;
}
} else {
sr = gffunc(0);
@@ -204,6 +210,7 @@ EXPORT_SYMBOL_GPL(free_rs);
* @gffunc: pointer to function to generate the next field element,
* or the multiplicative identity element if given 0. Used
* instead of gfpoly if gfpoly is 0
+ * @gfswab: Treat symbols as foreign endian, may be true only if symsize=16
* @fcr: the first consecutive root of the rs code generator polynomial
* in index form
* @prim: primitive element to generate polynomial roots
@@ -211,8 +218,9 @@ EXPORT_SYMBOL_GPL(free_rs);
* @gfp: GFP_ flags for allocations
*/
static struct rs_control *init_rs_internal(int symsize, int gfpoly,
- int (*gffunc)(int), int fcr,
- int prim, int nroots, gfp_t gfp)
+ int (*gffunc)(int), bool gfswab,
+ int fcr, int prim, int nroots,
+ gfp_t gfp)
{
struct list_head *tmp;
struct rs_control *rs;
@@ -227,6 +235,8 @@ static struct rs_control *init_rs_internal(int symsize, int gfpoly,
return NULL;
if (nroots < 0 || nroots >= (1<<symsize))
return NULL;
+ if (gfswab && symsize != 16)
+ return NULL;
/*
* The decoder needs buffers in each control struct instance to
@@ -250,6 +260,8 @@ static struct rs_control *init_rs_internal(int symsize, int gfpoly,
continue;
if (gffunc != cd->gffunc)
continue;
+ if (gfswab != cd->gfswab)
+ continue;
if (fcr != cd->fcr)
continue;
if (prim != cd->prim)
@@ -263,7 +275,8 @@ static struct rs_control *init_rs_internal(int symsize, int gfpoly,
}
/* Create a new one */
- rs->codec = codec_init(symsize, gfpoly, gffunc, fcr, prim, nroots, gfp);
+ rs->codec = codec_init(symsize, gfpoly, gffunc, gfswab,
+ fcr, prim, nroots, gfp);
if (!rs->codec) {
kfree(rs);
rs = NULL;
@@ -288,10 +301,31 @@ static struct rs_control *init_rs_internal(int symsize, int gfpoly,
struct rs_control *init_rs_gfp(int symsize, int gfpoly, int fcr, int prim,
int nroots, gfp_t gfp)
{
- return init_rs_internal(symsize, gfpoly, NULL, fcr, prim, nroots, gfp);
+ return init_rs_internal(symsize, gfpoly, NULL, false,
+ fcr, prim, nroots, gfp);
}
EXPORT_SYMBOL_GPL(init_rs_gfp);
+/**
+ * init_rs16_gfp - 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)
+ * @gfp: Memory allocation flags.
+ */
+struct rs_control *init_rs16_gfp(int gfpoly, bool gfswab, int fcr, int prim,
+ int nroots, gfp_t gfp)
+{
+ return init_rs_internal(16, gfpoly, NULL, gfswab,
+ fcr, prim, nroots, gfp);
+}
+EXPORT_SYMBOL_GPL(init_rs16_gfp);
+
/**
* init_rs_non_canonical - Allocate rs control struct for fields with
* non-canonical representation
@@ -307,7 +341,7 @@ EXPORT_SYMBOL_GPL(init_rs_gfp);
struct rs_control *init_rs_non_canonical(int symsize, int (*gffunc)(int),
int fcr, int prim, int nroots)
{
- return init_rs_internal(symsize, 0, gffunc, fcr, prim, nroots,
+ return init_rs_internal(symsize, 0, gffunc, false, fcr, prim, nroots,
GFP_KERNEL);
}
EXPORT_SYMBOL_GPL(init_rs_non_canonical);
diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c
index d9d1c33aebda..f1eba21ed6d8 100644
--- a/lib/reed_solomon/test_rslib.c
+++ b/lib/reed_solomon/test_rslib.c
@@ -36,6 +36,7 @@ __param(int, bc, 1, "Test for correct behaviour beyond error correction capacity
struct 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;
--
2.30.2