Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   "Jiri Slaby (SUSE)" <jirislaby@kernel.org>
To:     gregkh@linuxfoundation.org
Cc:     Kees Cook <keescook@chromium.org>, linux-serial@vger.kernel.org,
        linux-kernel@vger.kernel.org,
        "Jiri Slaby (SUSE)" <jirislaby@kernel.org>
Subject: [PATCH 09/11] tty: vt: separate array juggling to juggle_array()
Date:   Thu, 12 Jan 2023 09:01:34 +0100
Message-Id: <20230112080136.4929-9-jirislaby@kernel.org>
In-Reply-To: <20230112080136.4929-1-jirislaby@kernel.org>
References: <20230112080136.4929-1-jirislaby@kernel.org>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

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@kernel.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