Re: [PATCH 09/11] tty: vt: separate array juggling to juggle_array()

[Ilpo Järvinen]

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.