rslib: Several improvements
Hello,
I made several improvements to reed-solomon library. Please have a look. :)
Thanks!
Best Regards,
Zhang Boyang
===
Changes in [PATCH v2]:
Added more patches. Removed init_rs16(), since init_rs_non_canonical() can do the same job.
Changes in [PATCH v1]:
Added init_rs16().
[RFC PATCH]:
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
@@ -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
PATCH v2 2/5 rslib: Fix obvious documentation mistakes
In reply to Zhang BoyangThis 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
@@ -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
@@ -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
PATCH v2 3/5 rslib: Replace hard-coded 1 with alpha_to[0]
In reply to Zhang BoyangCurrently 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
@@ -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);
lib/reed_solomon/reed_solomon.c +2 -2
@@ -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
PATCH v2 4/5 rslib: Improve the performance of encode_rs.c
In reply to Zhang BoyangThis 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
@@ -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
@@ -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
Re: [PATCH v2 4/5] rslib: Improve the performance of encode_rs.c
Hi--
Quoted 20 lines · Zhang Boyang
Signed-off-by Zhang Boyang <[email protected]>--- 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@@ -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
PATCH v2 5/5 rslib: Fix integer overflow on large fcr or prim
In reply to Zhang BoyangCurrent 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
@@ -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
@@ -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
@@ -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
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
Signed-off-by Zhang Boyang <[email protected]>--- 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
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