Re: [PATCH] mergesort: avoid left shift overflow

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 17, 2021, 09:19 UTC
Message-ID: <xmqqr1bf2l83.fsf@gitster.g>
In-Reply-To: <nycvar.QRO.7.76.6.2111161505500.21127@tvgsbejvaqbjf.bet>

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

Show 19 quoted lines

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

Interesting.

I do not quite see the need for it myself, but if we wanted to, we can smoke them out with this, I think.

	$ cat >contrib/coccinelle/cast.cocci <<-\EOF
	@@
	type T;
	expression V, C;
	@@
	-(T) V << C
	+((T) V) << C
	EOF
	$ make contrib/coccinelle/cast.cocci.patch
	$ git apply --stat contrib/coccinelle/cast.cocci.patch
         compat/mingw.c     |    2 +-
         compat/mingw.c     |    2 +-
         ewah/bitmap.c      |    2 +-
         ewah/ewok_rlw.h    |    6 +++---
         ewah/ewah_bitmap.c |    8 ++++----
         ewah/ewok_rlw.h    |    6 +++---
         ppc/sha1.c         |    2 +-
         wrapper.c          |    2 +-
         8 files changed, 15 insertions(+), 15 deletions(-)