linux-kernel - [PATCH 09/11] tty: vt: separate array juggling to juggle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20230112080136.4929-9-jirislaby@kernel.org>
Date:   Thu, 12 Jan 2023 09:01:34 +0100
From:   "Jiri Slaby (SUSE)" <jirislaby@...nel.org>
To:     gregkh@...uxfoundation.org
Cc:     Kees Cook <keescook@...omium.org>, linux-serial@...r.kernel.org,
        linux-kernel@...r.kernel.org,
        "Jiri Slaby (SUSE)" <jirislaby@...nel.org>
Subject: [PATCH 09/11] tty: vt: separate array juggling to juggle_array()

The algorithm used for scrolling is the array juggling. It has
complexity O(N) and space complexity O(1). I.e. quite fast w/o
requirements for temporary storage.

Move the algorithm to a separate function so it is obvious what it is.
It is almost generic (except the array type), so if anyone else wants
array rotation, feel free to make it generic and move it to include/.

And rename all the variables from i, j, k, sz, d, and so on to something
saner.

Signed-off-by: Jiri Slaby (SUSE) <jirislaby@...nel.org>
---
 drivers/tty/vt/vt.c | 52 ++++++++++++++++++++++++---------------------
 1 file changed, 28 insertions(+), 24 deletions(-)

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 74db07b32abe..7cda18b7ee3d 100644
--- a/drivers/tty/vt/vt.c
+++ b/drivers/tty/vt/vt.c
@@ -398,40 +398,44 @@ static void vc_uniscr_clear_lines(struct vc_data *vc, unsigned int y,
 			memset32(vc->vc_uni_lines[y++], ' ', vc->vc_cols);
 }
 
+/* juggling array rotation algorithm (complexity O(N), size complexity O(1)) */
+static void juggle_array(u32 **array, unsigned int size, unsigned int nr)
+{
+	unsigned int gcd_idx;
+
+	for (gcd_idx = 0; gcd_idx < gcd(nr, size); gcd_idx++) {
+		u32 *gcd_idx_val = array[gcd_idx];
+		unsigned int dst_idx = gcd_idx;
+
+		while (1) {
+			unsigned int src_idx = (dst_idx + nr) % size;
+			if (src_idx == gcd_idx)
+				break;
+
+			array[dst_idx] = array[src_idx];
+			dst_idx = src_idx;
+		}
+
+		array[dst_idx] = gcd_idx_val;
+	}
+}
+
 static void vc_uniscr_scroll(struct vc_data *vc, unsigned int t, unsigned int b,
 			     enum con_scroll dir, unsigned int nr)
 {
 	u32 **uni_lines = vc->vc_uni_lines;
-	unsigned int i, j, k, sz, d, clear;
+	unsigned int size = b - t;
 
 	if (!uni_lines)
 		return;
 
-	sz = b - t;
-	clear = b - nr;
-	d = nr;
-
 	if (dir == SM_DOWN) {
-		clear = t;
-		d = sz - nr;
-	}
-
-	for (i = 0; i < gcd(d, sz); i++) {
-		u32 *tmp = uni_lines[t + i];
-		j = i;
-		while (1) {
-			k = j + d;
-			if (k >= sz)
-				k -= sz;
-			if (k == i)
-				break;
-			uni_lines[t + j] = uni_lines[t + k];
-			j = k;
-		}
-		uni_lines[t + j] = tmp;
+		juggle_array(&uni_lines[top], size, size - nr);
+		vc_uniscr_clear_lines(vc, t, nr);
+	} else {
+		juggle_array(&uni_lines[top], size, nr);
+		vc_uniscr_clear_lines(vc, b - nr, nr);
 	}
-
-	vc_uniscr_clear_lines(vc, clear, nr);
 }
 
 static void vc_uniscr_copy_area(u32 **dst_lines,
-- 
2.39.0