Skip to contentSkip to conversation

rslib: Replace hard-coded 1 with alpha_to[0]

RFC PATCH New Zhang Boyang 1 participant 3 messages Jun 5, 2022 – Jun 6, 2022

lore
Share & tools
lore
#0 lore raw

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
index 805de84ae83d..6c1d53d1b702 100644
@@ -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);
lib/reed_solomon/reed_solomon.c +2 -2
index bbc01bad3053..bb4f44c8edba 100644
@@ -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
index d9d1c33aebda..1c7fefcc89f2 100644
@@ -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
#1 lore raw

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
index 805de84ae83d..6c1d53d1b702 100644
@@ -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);
lib/reed_solomon/reed_solomon.c +2 -2
index bbc01bad3053..bb4f44c8edba 100644
@@ -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
#2 lore raw

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
index 238bb85243d3..bd38e1285997 100644
@@ -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
index d9d1c33aebda..f1eba21ed6d8 100644
@@ -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;
 
Signature · 1 line
2.30.2