linux-kernel - Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an array of elements

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: <4078b7a3-2ec2-ba87-d23c-b8daed7386fe@rasmusvillemoes.dk>
Date:   Wed, 25 Aug 2021 09:05:19 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Mauro Carvalho Chehab <mchehab+huawei@...nel.org>,
        Sakari Ailus <sakari.ailus@...ux.intel.com>,
        linux-media@...r.kernel.org, linux-kernel@...r.kernel.org
Cc:     Yong Zhi <yong.zhi@...el.com>, Bingbu Cao <bingbu.cao@...el.com>,
        Dan Scally <djrscally@...il.com>,
        Tianshu Qiu <tian.shu.qiu@...el.com>,
        Mauro Carvalho Chehab <mchehab@...nel.org>
Subject: Re: [PATCH v1 2/3] lib/sort: Introduce rotate() to circular shift an
 array of elements

On 24/08/2021 15.33, Andy Shevchenko wrote:
> In some cases we want to circular shift an array of elements.
> Introduce rotate() helper for that.
> 
> Signed-off-by: Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
> ---
>  include/linux/sort.h |  3 +++
>  lib/sort.c           | 61 ++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 64 insertions(+)
> 
> diff --git a/include/linux/sort.h b/include/linux/sort.h
> index b5898725fe9d..c881acb12ffc 100644
> --- a/include/linux/sort.h
> +++ b/include/linux/sort.h
> @@ -13,4 +13,7 @@ void sort(void *base, size_t num, size_t size,
>  	  cmp_func_t cmp_func,
>  	  swap_func_t swap_func);
>  
> +void rotate(void *base, size_t num, size_t size, size_t by,
> +	    swap_func_t swap_func);
> +
>  #endif
> diff --git a/lib/sort.c b/lib/sort.c
> index d9b2f5b73620..b9243f8db34b 100644
> --- a/lib/sort.c
> +++ b/lib/sort.c
> @@ -14,6 +14,7 @@
>  
>  #include <linux/types.h>
>  #include <linux/export.h>
> +#include <linux/minmax.h>
>  #include <linux/sort.h>
>  
>  /**
> @@ -275,3 +276,63 @@ void sort(void *base, size_t num, size_t size,
>  	return sort_r(base, num, size, _CMP_WRAPPER, swap_func, cmp_func);
>  }
>  EXPORT_SYMBOL(sort);
> +
> +/**
> + * rotate - rotate an array of elements by a number of elements
> + * @base: pointer to data to sort

sort?

> + * @num: number of elements
> + * @size: size of each element
> + * @by: number of elements to rotate by

Perhaps add (0 <= @by < @num) or something like that, and/or start the
implementation with "if (num <= 1) return; if (by >= num) by %= num;"

> + * @swap_func: pointer to swap function or NULL
> + *
> + * Helper function to advance all the elements of a circular buffer by
> + * @by positions.
> + */
> +void rotate(void *base, size_t num, size_t size, size_t by,
> +	    swap_func_t swap_func)
> +{
> +	struct {
> +		size_t begin, end;
> +	} arr[2] = {
> +		{ .begin = 0, .end = by - 1 },
> +		{ .begin = by, .end = num - 1 },
> +	};

I see you just copied-and-adapted, but I think the code would be much
easier to read without all those plus/minus ones all over.

> +	swap_func = choose_swap_func(swap_func, base, size);
> +
> +#define CHUNK_SIZE(a) ((a)->end - (a)->begin + 1)
> +
> +	/* Loop as long as we have out-of-place entries */
> +	while (CHUNK_SIZE(&arr[0]) && CHUNK_SIZE(&arr[1])) {
> +		size_t size0, i;
> +
> +		/*
> +		 * Find the number of entries that can be arranged on this
> +		 * iteration.
> +		 */
> +		size0 = min(CHUNK_SIZE(&arr[0]), CHUNK_SIZE(&arr[1]));
> +
> +		/* Swap the entries in two parts of the array */
> +		for (i = 0; i < size0; i++) {
> +			void *a = base + size * (arr[0].begin + i);
> +			void *b = base + size * (arr[1].begin + i);
> +
> +			do_swap(a, b, size, swap_func);
> +		}
> +
> +		if (CHUNK_SIZE(&arr[0]) > CHUNK_SIZE(&arr[1])) {
> +			/* The end of the first array remains unarranged */
> +			arr[0].begin += size0;
> +		} else {
> +			/*
> +			 * The first array is fully arranged so we proceed
> +			 * handling the next one.
> +			 */
> +			arr[0].begin = arr[1].begin;
> +			arr[0].end = arr[1].begin + size0 - 1;
> +			arr[1].begin += size0;
> +		}
> +	}

Perhaps add a small self-test, it's not at all obvious how this works
(perhaps it's some standard CS101 algorithm for rotating in-place, I
don't know, but even then an implementation can have off-by-ones and
corner cases).

for (len = 1; len < 15; ++len) {
  for (by = 0; by <= len; ++by) {
    for (i = 0; i < len; ++i)
      arr[i] = i;
    rotate(arr, len, sizeof(int), by);
    for (i = 0; i < len; ++i)
      if (arr[i] != (i + by) % len)
        error();
  }
}

Rasmus