Skip to contentSkip to conversation

rslib: Several improvements

PATCH Superseded Zhang Boyang 2 participants 8 messages Jun 17, 2022 – Jun 19, 2022

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#1 lore raw

PATCH v2 1/5 rslib: Fix incorrect documentation of rs_modnn()

Previous documentation of rs_modnn() states simple arithmetic modulo return a wrong result for values >= (3 * rs->nn). However, that is not true. The rs_modnn() does the exactly same job as (x % rs->nn). This can be proved from following loop invariants:

  while (x >= rs->nn) {
    x -= rs->nn; // (1)
    x = (x >> rs->mm) + (x & rs->nn); // (2)
  }

Let x0 denote the value of x before assignment. At (1), it is obvious that x % nn == x0 % nn. At (2), because nn == ((1 << mm) - 1), we have

x0 % nn == x0 % nn
x0 % nn == (((x0 >> mm) << mm) + (x0 & nn)) % nn x0 % nn == ((x0 >> mm) * (nn + 1) + (x0 & nn)) % nn x0 % nn == ((x0 >> mm) * ((nn + 1) % nn) + (x0 & nn)) % nn
x0 % nn == ((x0 >> mm) * 1 + (x0 & nn)) % nn // let's assume nn > 1
x0 % nn == ((x0 >> mm) + (x0 & nn)) % nn
x0 % nn == x % nn

When the loop exits, it is obvious that 0 <= x < nn, so the return value must equal to (x % rs->nn).

---
 include/linux/rslib.h | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
include/linux/rslib.h +1 -2
index 238bb85243d3..507fa14c03b2 100644
@@ -116,8 +116,7 @@ void free_rs(struct rs_control *rs);
  *  rs->mm = number of bits per symbol
  *  rs->nn = (2^rs->mm) - 1
  *
- *  Simple arithmetic modulo would return a wrong result for values
- *  >= 3 * rs->nn
+ *  Calculate (x % rs->nn), without using a div instruction
 */
 static inline int rs_modnn(struct rs_codec *rs, int x)
 {
Signature · 1 line
2.30.2
#2 lore raw

PATCH v2 2/5 rslib: Fix obvious documentation mistakes

In reply to Zhang Boyang

This patch fixes some obvious documentation mistakes.

---
 include/linux/rslib.h           | 4 ++--
 lib/reed_solomon/reed_solomon.c | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)
include/linux/rslib.h +2 -2
index 507fa14c03b2..cd0b5a7a5698 100644
@@ -19,8 +19,8 @@
  *
  * @mm:		Bits per symbol
  * @nn:		Symbols per block (= (1<<mm)-1)
- * @alpha_to:	log lookup table
- * @index_of:	Antilog lookup table
+ * @alpha_to:	exp() lookup table
+ * @index_of:	log() lookup table
  * @genpoly:	Generator polynomial
  * @nroots:	Number of generator roots = number of parity symbols
  * @fcr:	First consecutive root, index form
lib/reed_solomon/reed_solomon.c +1 -1
index bbc01bad3053..9415899bf27c 100644
@@ -56,7 +56,7 @@ 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
  * @fcr:	first root of RS code generator polynomial, index form
Signature · 1 line
2.30.2
#3 lore raw

PATCH v2 3/5 rslib: Replace hard-coded 1 with alpha_to[0]

In reply to 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 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 9415899bf27c..da46026a60b8 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
#4 lore raw

PATCH v2 4/5 rslib: Improve the performance of encode_rs.c

In reply to Zhang Boyang

This patch enhances the performance of RS encoder by following points:

1) Avoid memmove(). The shifting operation done by memmove() can be merged into the calculation loop above.

2) Introduce rs_modnn_fast(). The original rs_modnn() contains a loop which may be slow. Since (fb + genpoly[...]) is always strictly less than (2 * rs->nn), we can use a ternary operator to do the same calculation. The new faster function is named rs_modnn_fast(). The new rs_modnn_fast(x) requires 0 <= x < 2*nn, in contrast, original rs_modnn(x) only requires x >= 0. To make things clear, the documentation of original rs_modnn() is also updated.

---
 include/linux/rslib.h        | 14 +++++++++++++-
 lib/reed_solomon/encode_rs.c | 21 ++++++++++-----------
 2 files changed, 23 insertions(+), 12 deletions(-)
include/linux/rslib.h +13 -1
index cd0b5a7a5698..44ec7c6f24b2 100644
@@ -110,7 +110,7 @@ void free_rs(struct rs_control *rs);
 /** modulo replacement for galois field arithmetics
  *
  *  @rs:	Pointer to the RS codec
- *  @x:		the value to reduce
+ *  @x:		x >= 0 ; the value to reduce
  *
  *  where
  *  rs->mm = number of bits per symbol
@@ -127,4 +127,16 @@ static inline int rs_modnn(struct rs_codec *rs, int x)
 	return x;
 }
 
+/** modulo replacement for galois field arithmetics
+ *
+ *  @rs:	Pointer to the RS codec
+ *  @x:		0 <= x < 2*nn ; the value to reduce
+ *
+ *  Same as rs_modnn(x), but faster, at the cost of limited value range of @x
+*/
+static inline int rs_modnn_fast(struct rs_codec *rs, int x)
+{
+	return x - rs->nn < 0 ? x : x - rs->nn;
+}
+
 #endif
lib/reed_solomon/encode_rs.c +10 -11
index 9112d46e869e..6e3847b17ad4 100644
@@ -27,19 +27,18 @@
 
 	for (i = 0; i < len; i++) {
 		fb = index_of[((((uint16_t) data[i])^invmsk) & msk) ^ par[0]];
-		/* feedback term is non-zero */
 		if (fb != nn) {
-			for (j = 1; j < nroots; j++) {
-				par[j] ^= alpha_to[rs_modnn(rs, fb +
-							 genpoly[nroots - j])];
-			}
-		}
-		/* Shift */
-		memmove(&par[0], &par[1], sizeof(uint16_t) * (nroots - 1));
-		if (fb != nn) {
-			par[nroots - 1] = alpha_to[rs_modnn(rs,
-							    fb + genpoly[0])];
+			/* feedback term is non-zero */
+			for (j = 1; j < nroots; j++)
+				par[j - 1] = par[j] ^ alpha_to[rs_modnn_fast(rs,
+						      fb +
+						      genpoly[nroots - j])];
+			par[nroots - 1] = alpha_to[rs_modnn_fast(rs,
+					  fb +
+					  genpoly[0])];
 		} else {
+			for (j = 1; j < nroots; j++)
+				par[j - 1] = par[j];
 			par[nroots - 1] = 0;
 		}
 	}
Signature · 1 line
2.30.2
#5 lore raw

Re: [PATCH v2 4/5] rslib: Improve the performance of encode_rs.c

Hi--

Quoted 20 lines · Zhang Boyang
---
 include/linux/rslib.h        | 14 +++++++++++++-
 lib/reed_solomon/encode_rs.c | 21 ++++++++++-----------
 2 files changed, 23 insertions(+), 12 deletions(-)
include/linux/rslib.h +1 -1
index cd0b5a7a5698..44ec7c6f24b2 100644
@@ -110,7 +110,7 @@ void free_rs(struct rs_control *rs);
 /** modulo replacement for galois field arithmetics
  *
  *  @rs:	Pointer to the RS codec
- *  @x:		the value to reduce
+ *  @x:		x >= 0 ; the value to reduce
  *
  *  where
  *  rs->mm = number of bits per symbol

include/linux/rslib.h static inline int rs_modnn(struct rs_codec *rs, int x) · line 130

Quoted 4 lines
include/linux/rslib.h +1 -0
@@ -127,4 +127,16 @@ static inline int rs_modnn(struct rs_codec *rs, int x)
 	return x;
 }
 
+/** modulo replacement for galois field arithmetics

/**
* rs_modnn_fast() - modulo replacement for galois field arithmetics

Quoted 12 lines
include/linux/rslib.h +11 -0
+ *
+ *  @rs:	Pointer to the RS codec
+ *  @x:		0 <= x < 2*nn ; the value to reduce
+ *
+ *  Same as rs_modnn(x), but faster, at the cost of limited value range of @x
+*/
+static inline int rs_modnn_fast(struct rs_codec *rs, int x)
+{
+	return x - rs->nn < 0 ? x : x - rs->nn;
+}
+
 #endif
Signature · 1 line
~Randy
#6 lore raw

PATCH v2 5/5 rslib: Fix integer overflow on large fcr or prim

In reply to Zhang Boyang

Current rslib support symsize up to 16, so the max value of rs->nn can be 0xFFFF. Since fcr <= nn, prim <= nn, multiplications on them can overflow easily, e.g. fcr*root[j], fcr*prim.

This patch fixes these problems by introducing rs_modnn_mul(a, b). This function is same as rs_modnn(a*b) but it will avoid overflow when calculating a*b. It requires 0 <= a <= nn && 0 <= b <= nn, because it use uint32_t to do the multiplication internally, so there will be no overflow as long as 0 <= a <= nn <= 0xFFFF && 0 <= b <= nn <= 0xFFFF. In fact, if we use unsigned int' everywhere, there is no need to have rs_modnn_mul(). But the unsigned int' approach has poor scalability and it may bring us to the mess of signed and unsigned integers.

With rs_modnn(), the intermediate result is now restricted to [0, nn). This enables us to use rs_modnn_fast(a+b) to replace rs_modnn(a+b), as long as 0 <= a+b < 2*nn. The most common case is one addend in [0, nn] and the other addend in [0, nn). The examples of values in [0, nn] are fcr, prim, indexes taken from rs->index_of[0...nn], etc. The examples of values in [0, nn) are results from rs_modnn(), indexes taken from rs->index_of[1...nn], etc.

Since the roots of RS generator polynomial, i.e. (fcr+i)*prim%nn, is often used. It's now precomputed into rs->genroot[], to avoid writing rs_modnn_mul(rs, rs_modnn_fast(rs, fcr + i), prim) everywhere.

The algorithm of searching for rs->iprim is also changed. Instead of searching for (1+what*nn)%prim == 0, then iprim = (1+what*nn)/prim, it now searches for iprim*prim%nn == 1 directly.

A new test case is also added to test_rslib.c to ensure correctness.

---
 include/linux/rslib.h           | 22 ++++++++++++
 lib/reed_solomon/decode_rs.c    | 60 +++++++++++++++++++--------------
 lib/reed_solomon/reed_solomon.c | 30 ++++++++++++-----
 lib/reed_solomon/test_rslib.c   |  8 ++---
 4 files changed, 82 insertions(+), 38 deletions(-)
include/linux/rslib.h +22 -0
index 44ec7c6f24b2..29abfb2de257 100644
@@ -22,6 +22,7 @@
  * @alpha_to:	exp() lookup table
  * @index_of:	log() lookup table
  * @genpoly:	Generator polynomial
+ * @genroot:	Roots of generator polynomial, index form
  * @nroots:	Number of generator roots = number of parity symbols
  * @fcr:	First consecutive root, index form
  * @prim:	Primitive element, index form
@@ -37,6 +38,7 @@ struct rs_codec {
 	uint16_t	*alpha_to;
 	uint16_t	*index_of;
 	uint16_t	*genpoly;
+	uint16_t	*genroot;
 	int		nroots;
 	int		fcr;
 	int		prim;
@@ -127,6 +129,26 @@ static inline int rs_modnn(struct rs_codec *rs, int x)
 	return x;
 }
 
+/** modulo replacement for galois field arithmetics
+ *
+ *  @rs:	Pointer to the RS codec
+ *  @a:		0 <= a <= nn ; a*b is the value to reduce
+ *  @b:		0 <= b <= nn ; a*b is the value to reduce
+ *
+ *  Same as rs_modnn(a*b), but avoid interger overflow when calculating a*b
+*/
+static inline int rs_modnn_mul(struct rs_codec *rs, int a, int b)
+{
+	/* nn <= 0xFFFF, so (a * b) will not overflow uint32_t */
+	uint32_t x = (uint32_t)a * (uint32_t)b;
+	uint32_t nn = (uint32_t)rs->nn;
+	while (x >= nn) {
+		x -= nn;
+		x = (x >> rs->mm) + (x & nn);
+	}
+	return (int)x;
+}
+
 /** modulo replacement for galois field arithmetics
  *
  *  @rs:	Pointer to the RS codec
lib/reed_solomon/decode_rs.c +34 -26

146 lines not on this page · raw message

lib/reed_solomon/reed_solomon.c +22 -8
index da46026a60b8..2c86e4dfcbaa 100644
@@ -100,6 +100,10 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
 	if(rs->genpoly == NULL)
 		goto err;
 
+	rs->genroot = kmalloc_array(rs->nroots, sizeof(uint16_t), gfp);
+	if(rs->genroot == NULL)
+		goto err;
+
 	/* Generate Galois field lookup tables */
 	rs->index_of[0] = rs->nn;	/* log(zero) = -inf */
 	rs->alpha_to[rs->nn] = 0;	/* alpha**-inf = 0 */
@@ -126,26 +130,34 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
 		goto err;
 
 	/* Find prim-th root of 1, used in decoding */
-	for(iprim = 1; (iprim % prim) != 0; iprim += rs->nn);
+	for (iprim = 1; rs_modnn_mul(rs, iprim, prim) != 1; iprim++);
 	/* prim-th root of 1, index form */
-	rs->iprim = iprim / prim;
+	rs->iprim = iprim;
+
+	/* Precompute generator polynomial roots */
+	root = rs_modnn_mul(rs, fcr, prim);
+	for (i = 0; i < nroots; i++) {
+		rs->genroot[i] = root; /*  = (fcr + i) * prim % nn  */
+		root = rs_modnn_fast(rs, root + prim);
+	}
 
 	/* Form RS code generator polynomial from its roots */
 	rs->genpoly[0] = rs->alpha_to[0];
-	for (i = 0, root = fcr * prim; i < nroots; i++, root += prim) {
+	for (i = 0; i < nroots; i++) {
+		root = rs->genroot[i];
 		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) {
-				rs->genpoly[j] = rs->genpoly[j -1] ^
-					rs->alpha_to[rs_modnn(rs,
+				rs->genpoly[j] = rs->genpoly[j - 1] ^
+					rs->alpha_to[rs_modnn_fast(rs,
 					rs->index_of[rs->genpoly[j]] + root)];
 			} else
 				rs->genpoly[j] = rs->genpoly[j - 1];
 		}
 		/* rs->genpoly[0] can never be zero */
 		rs->genpoly[0] =
-			rs->alpha_to[rs_modnn(rs,
+			rs->alpha_to[rs_modnn_fast(rs,
 				rs->index_of[rs->genpoly[0]] + root)];
 	}
 	/* convert rs->genpoly[] to index form for quicker encoding */
@@ -157,6 +169,7 @@ static struct rs_codec *codec_init(int symsize, int gfpoly, int (*gffunc)(int),
 	return rs;
 
 err:
+	kfree(rs->genroot);
 	kfree(rs->genpoly);
 	kfree(rs->index_of);
 	kfree(rs->alpha_to);
@@ -188,6 +201,7 @@ void free_rs(struct rs_control *rs)
 		kfree(cd->alpha_to);
 		kfree(cd->index_of);
 		kfree(cd->genpoly);
+		kfree(cd->genroot);
 		kfree(cd);
 	}
 	mutex_unlock(&rslistlock);
@@ -340,7 +354,7 @@ EXPORT_SYMBOL_GPL(encode_rs8);
  *  @data:	data field of a given type
  *  @par:	received parity data field
  *  @len:	data length
- *  @s: 	syndrome data field, must be in index form
+ *  @s: 	syndrome data field, must be in index form, 0 <= index <= nn
  *		(if NULL, syndrome is calculated)
  *  @no_eras:	number of erasures
  *  @eras_pos:	position of erasures, can be NULL
@@ -393,7 +407,7 @@ EXPORT_SYMBOL_GPL(encode_rs16);
  *  @data:	data field of a given type
  *  @par:	received parity data field
  *  @len:	data length
- *  @s: 	syndrome data field, must be in index form
+ *  @s: 	syndrome data field, must be in index form, 0 <= index <= nn
  *		(if NULL, syndrome is calculated)
  *  @no_eras:	number of erasures
  *  @eras_pos:	position of erasures, can be NULL
lib/reed_solomon/test_rslib.c +4 -4
index d9d1c33aebda..a03c7249f920 100644
@@ -55,6 +55,7 @@ static struct etab Tab[] = {
 	{8,	0x11d,	1,	1,	30,	100	},
 	{8,	0x187,	112,	11,	32,	100	},
 	{9,	0x211,	1,	1,	33,	80	},
+	{16,  0x1ffed,	65534,	65534,	50,	5	},
 	{0, 0, 0, 0, 0, 0},
 };
 
@@ -232,9 +233,8 @@ static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
 	struct rs_codec *rs = rsc->codec;
 	uint16_t *alpha_to = rs->alpha_to;
 	uint16_t *index_of = rs->index_of;
+	uint16_t *genroot = rs->genroot;
 	int nroots = rs->nroots;
-	int prim = rs->prim;
-	int fcr = rs->fcr;
 	int i, j;
 
 	/* Calculating syndrome */
@@ -245,8 +245,8 @@ static void compute_syndrome(struct rs_control *rsc, uint16_t *data,
 				syn[i] = data[j];
 			} else {
 				syn[i] = data[j] ^
-					alpha_to[rs_modnn(rs, index_of[syn[i]]
-						+ (fcr + i) * prim)];
+					alpha_to[rs_modnn_fast(rs,
+						index_of[syn[i]] + genroot[i])];
 			}
 		}
 	}
Signature · 1 line
2.30.2
#7 lore raw

Re: [PATCH v2 5/5] rslib: Fix integer overflow on large fcr or prim

Hi--

Somehow some of the kernel-doc notation in these files has been entered incorrectly and you are propagating that mistake... Please see below for more.

Quoted 14 lines · Zhang Boyang
---
 include/linux/rslib.h           | 22 ++++++++++++
 lib/reed_solomon/decode_rs.c    | 60 +++++++++++++++++++--------------
 lib/reed_solomon/reed_solomon.c | 30 ++++++++++++-----
 lib/reed_solomon/test_rslib.c   |  8 ++---
 4 files changed, 82 insertions(+), 38 deletions(-)
include/linux/rslib.h +0 -0
index 44ec7c6f24b2..29abfb2de257 100644

include/linux/rslib.h static inline int rs_modnn(struct rs_codec *rs, int x) · line 132

Quoted 4 lines
include/linux/rslib.h +1 -0
@@ -127,6 +129,26 @@ static inline int rs_modnn(struct rs_codec *rs, int x)
 	return x;
 }
 
+/** modulo replacement for galois field arithmetics

/**
* rs_modnn_mul() - modulo replacement for galois field arithmetics

include/linux/rslib.h static inline int rs_modnn(struct rs_codec *rs, int x) · line 138

Quoted 6 lines
include/linux/rslib.h +6 -0
+ *
+ *  @rs:	Pointer to the RS codec
+ *  @a:		0 <= a <= nn ; a*b is the value to reduce
+ *  @b:		0 <= b <= nn ; a*b is the value to reduce
+ *
+ *  Same as rs_modnn(a*b), but avoid interger overflow when calculating a*b

integer a * b

Quoted 4 lines
include/linux/rslib.h +4 -0
+*/
+static inline int rs_modnn_mul(struct rs_codec *rs, int a, int b)
+{
+	/* nn <= 0xFFFF, so (a * b) will not overflow uint32_t */

include/linux/rslib.h static inline int rs_modnn(struct rs_codec *rs, int x) · line 152

Quoted 10 lines
include/linux/rslib.h +9 -0
+	uint32_t x = (uint32_t)a * (uint32_t)b;
+	uint32_t nn = (uint32_t)rs->nn;
+	while (x >= nn) {
+		x -= nn;
+		x = (x >> rs->mm) + (x & nn);
+	}
+	return (int)x;
+}
+
 /** modulo replacement for galois field arithmetics

/**
* rs_modnn() - modulo replacement for galois field arithmetics

Quoted 2 lines
include/linux/rslib.h +0 -0
  *
  *  @rs:	Pointer to the RS codec
Signature · 1 line
~Randy