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@kernel.org>
Link: https://lore.kernel.org/r/20230112080136.4929-9-jirislaby@kernel.org
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

1 files changed, 28 insertions, 24 deletions

diff --git a/drivers/tty/vt/vt.c b/drivers/tty/vt/vt.c
index 40d71cfdec32..f5d71f0ead59 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,