On Thu, 12 Jan 2023, Jiri Slaby (SUSE) wrote:
> 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@xxxxxxxxxx>
> ---
> 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);
top? Should be t I think.
> + vc_uniscr_clear_lines(vc, t, nr);
> + } else {
> + juggle_array(&uni_lines[top], size, nr);
Ditto.
> + vc_uniscr_clear_lines(vc, b - nr, nr);
> }
> -
> - vc_uniscr_clear_lines(vc, clear, nr);
> }
>
> static void vc_uniscr_copy_area(u32 **dst_lines,
>
--
i.
