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]

Date:   Wed, 25 Aug 2021 11:08:32 +0300
From:   Sakari Ailus <sakari.ailus@...ux.intel.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Mauro Carvalho Chehab <mchehab+huawei@...nel.org>,
        linux-media@...r.kernel.org, linux-kernel@...r.kernel.org,
        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

Hi Rasmus, Andy,

On Wed, Aug 25, 2021 at 09:05:19AM +0200, Rasmus Villemoes wrote:
> 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;"

The latter could be done unconditionally.

> 
> > + * @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.

Now that I think about it, they can be just removed. In that case end
refers to the element following end, rather than the last element.

> 
> > +	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).

I don't know, I wrote this to fix a bug in the ipu3-cio2 driver. ;-) The
hardware, and so the arguments, were static. Nice to see it would be useful
elsewhere almost as-is.

> 
> 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();
>   }
> }

Makes sense to add something like that.

After addressing the comments, for patches from 1 to 3:

Acked-by: Sakari Ailus <sakari.ailus@...ux.intel.com>

-- 
Kind regards,

Sakari Ailus