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: <8bc8d977-5204-6f5b-8a1c-f2338c141993@rasmusvillemoes.dk>
Date:   Wed, 25 Aug 2021 11:29:12 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Sakari Ailus <sakari.ailus@...ux.intel.com>
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

On 25/08/2021 10.08, Sakari Ailus wrote:
> Hi Rasmus, Andy,
> 

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

Yes (provided num is tested at least for being non-zero first, but then
it's mostly free to check <= 1 instead), but in the vast majority of
cases the caller would pass a sane value of by, and an unconditional %=
would thus waste 100+ clock cycles for nothing.

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

Yes, as we almost always do array indexing in C... the math simply ends
up coming out more naturally that way in the majority of cases.

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

Well, Andy hasn't actually shown that it would be useful anywhere else.
I think I'd like to see another user. Just doing "move this helper to
lib/ because we can reuse choose-a-proper-swap-func and thus implement
this perhaps a tiny bit faster" without considering whether it's even
performance-critical in the sole user is not a good idea IMO.

Especially since it can affect code generation of the much more
important (at least, has many more users) sort() function - the
do_swap() function grows another user, so could make the compiler end up
choosing not to inline it anymore.

There's another slightly simpler way to implement rotate(), which might
end up having more users (though I can't find any currently): Add a
reverse() helper, then rotate() can be done as reverse(a, 0, n);
reverse(a, 0, k); reverse(a, k, n-k);. If my math is right, the current
suggested rotate() ends up doing n-gcd(n,k) swaps, while the
implementation in terms of a reverse() would do n-1 if either n or k is
odd, otherwise n, calls to swap().

Rasmus