Re: [PATCH] mergesort: avoid left shift overflow

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Nov 16, 2021, 14:08 UTC
Message-ID: <nycvar.QRO.7.76.6.2111161505500.21127@tvgsbejvaqbjf.bet>
In-Reply-To: <5eabbe1c-4c0f-559a-da21-423afec89e7e@web.de>

Hi René,

On Tue, 16 Nov 2021, René Scharfe wrote:

Show 20 quoted lines

> Use size_t to match n when building the bitmask for checking whether a
> rank is occupied, instead of the default signed int.
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> Ugh, sorry. :(
>
>  mergesort.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/mergesort.c b/mergesort.c
> index 6216835566..bd9c6ef8ee 100644
> --- a/mergesort.c
> +++ b/mergesort.c
> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
>  		void *next = get_next_fn(list);
>  		if (next)
>  			set_next_fn(list, NULL);
> -		for (i = 0; n & (1 << i); i++)
> +		for (i = 0; n & ((size_t)1 << i); i++)

I was a bit concerned about the operator precedence (some of which I remember by heart, some not), but according to https://en.cppreference.com/w/c/language/operator_precedence the cast has a higher precedence than the shift operator.

I would have preferred an extra pair of parentheses around `(size_t)1` so that I (and other readers) do not have to remember or look up the operator precedence, but it _is_ correct.

Ciao, Dscho

Show 6 quoted lines

>  			list = llist_merge(ranks[i], list, get_next_fn,
>  					   set_next_fn, compare_fn);
>  		n++;
> --
> 2.33.1
>