[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <20220617144624.158973-2-zhangboyang.id@gmail.com>
Date: Fri, 17 Jun 2022 22:46:20 +0800
From: Zhang Boyang <zhangboyang.id@...il.com>
To: linux-kernel@...r.kernel.org
Cc: Ferdinand Blomqvist <ferdinand.blomqvist@...il.com>,
Thomas Gleixner <tglx@...utronix.de>,
Kees Cook <keescook@...omium.org>,
Ivan Djelic <ivan.djelic@...rot.com>,
Boris Brezillon <boris.brezillon@...tlin.com>,
Miquel Raynal <miquel.raynal@...tlin.com>,
Zhang Boyang <zhangboyang.id@...il.com>
Subject: [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).
Signed-off-by: Zhang Boyang <zhangboyang.id@...il.com>
---
include/linux/rslib.h | 3 +--
1 file changed, 1 insertion(+), 2 deletions(-)
diff --git a/include/linux/rslib.h b/include/linux/rslib.h
index 238bb85243d3..507fa14c03b2 100644
--- a/include/linux/rslib.h
+++ b/include/linux/rslib.h
@@ -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)
{
--
2.30.2
Powered by blists - more mailing lists