[musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Gabriel Ravier]

The standard states that:

  > Unless explicitly stated otherwise, the functions described in
    this subclause order two wide characters the same way as two
    integers of the underlying integer type designated by `wchar_t`.
  > [...]
  > The `wcscmp` function returns an integer greater than, equal to,
    or less than zero, accordingly as the wide string pointed to by s1
    is greater than, equal to, or less than the wide string pointed to
    by s2.
  > The `wcsncmp` function returns an integer greater than, equal to,
    or less than zero, accordingly as the possibly null-terminated
    array pointed to by s1 is greater than, equal to, or less than the
    possibly null-terminated array pointed to by s2
  - N3047 (latest C draft as of the time of writing)

Yet a simple test program such as this:

    #include <wchar.h>
    #include <stdio.h>

    int main()
    {
        wchar_t str1[2] = { WCHAR_MAX, L'\0' };
        wchar_t str2[2] = { WCHAR_MIN, L'\0' };

        printf("%d\n", wcscmp(str1, str2));
        printf("%d\n", wcsncmp(str1, str2, 1));
    }

Will fail to run correctly according to this specification on musl (on
targets that have signed wchar_t), as it will print -1 instead of
1 (it should print 1, since WCHAR_MAX > WCHAR_MIN).

This appears to be due to the fact that musl uses a simple subtraction
to implement wcscmp and wcsncmp, which may result in an overflow.

This patch fixes this by replacing the subtraction with a little bit
of code that orders the characters correctly, returning -1 if the
character from the first string is smaller than the one from the
second, 0 if they are equal and 1 if the character from the first
string is larger than the one from the second
---
 src/string/wcscmp.c  | 2 +-
 src/string/wcsncmp.c | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/src/string/wcscmp.c b/src/string/wcscmp.c
index 26eeee70..286ec3ea 100644
--- a/src/string/wcscmp.c
+++ b/src/string/wcscmp.c
@@ -3,5 +3,5 @@
 int wcscmp(const wchar_t *l, const wchar_t *r)
 {
 	for (; *l==*r && *l && *r; l++, r++);
-	return *l - *r;
+	return *l < *r ? -1 : *l > *r;
 }
diff --git a/src/string/wcsncmp.c b/src/string/wcsncmp.c
index 4ab32a92..2b3558bf 100644
--- a/src/string/wcsncmp.c
+++ b/src/string/wcsncmp.c
@@ -3,5 +3,5 @@
 int wcsncmp(const wchar_t *l, const wchar_t *r, size_t n)
 {
 	for (; n && *l==*r && *l && *r; n--, l++, r++);
-	return n ? *l - *r : 0;
+	return n ? (*l < *r ? -1 : *l > *r) : 0;
 }
-- 
2.38.1

Re: [musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Markus Wichmann]

On Wed, Jan 04, 2023 at 04:07:19PM +0100, Gabriel Ravier wrote:
>  int wcscmp(const wchar_t *l, const wchar_t *r)
>  {
>  	for (; *l==*r && *l && *r; l++, r++);

I just noticed this line. Isn't the "&& *r" part superfluous? If r is a
prefix of l, then *r and *l will be unequal, and the loop will terminate
because of the first condition alone. (If l is a prefix of r, we need
the second condition to terminate the loop.)

> -	return *l - *r;
> +	return *l < *r ? -1 : *l > *r;
>  }

Ah, that old bug. The problem is that the difference between two 32-bit
values takes up 33 bits to save. I wonder if it would be worth it to
just cast the values to 64 bits, then dividing the result by two. You
know, like

return ((int64_t)*l - *r) >> 1;

Although that does presuppose that wchar_t is smaller than 64 bits,
which the proposed change does not require.

Ciao,
Markus

Re: [musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Markus Wichmann]

On Fri, Jan 06, 2023 at 10:20:10AM +0100, Markus Wichmann wrote:
> return ((int64_t)*l - *r) >> 1;

Wait, disregard that suggestion. It doesn't work when the difference
comes out at 1. Works for all other values, but if the difference is 1,
the shift makes it 0, and that means something different for these
functions.

Ciao,
Markus

Re: [musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Rich Felker]

On Fri, Jan 06, 2023 at 10:20:10AM +0100, Markus Wichmann wrote:
> On Wed, Jan 04, 2023 at 04:07:19PM +0100, Gabriel Ravier wrote:
> >  int wcscmp(const wchar_t *l, const wchar_t *r)
> >  {
> >  	for (; *l==*r && *l && *r; l++, r++);
> 
> I just noticed this line. Isn't the "&& *r" part superfluous? If r is a
> prefix of l, then *r and *l will be unequal, and the loop will terminate
> because of the first condition alone. (If l is a prefix of r, we need
> the second condition to terminate the loop.)

Yes, but I would assume the compiler would make the same optimization
anyway. The original motivation here may have just been writing it
symmetrically in l and r.

> > -	return *l - *r;
> > +	return *l < *r ? -1 : *l > *r;
> >  }
> 
> Ah, that old bug. The problem is that the difference between two 32-bit
> values takes up 33 bits to save. I wonder if it would be worth it to
> just cast the values to 64 bits, then dividing the result by two. You
> know, like
> 
> return ((int64_t)*l - *r) >> 1;
> 
> Although that does presuppose that wchar_t is smaller than 64 bits,
> which the proposed change does not require.

As you noted later this doesn't work but I think the core flaw here is
not the same as the classic bug. Rather, I probably had a wrong
initial assumption that the function was intended only to work for
valid wide character values of wchar_t not arbitrary integers that fit
in wchar_t arrays. In that case they would be 21-bit and the
difference would never overflow.

Rich

Re: [musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Markus Wichmann]

Hi all,

I thought a bit more about it. It would be possible to compress the
information we need somewhat like this:

int64_t d = (int64_t)*l - *r;
return (d >> 1) | (d & INT_MAX);

The idea is that I need bit 31 of the output to equal bit 32 of the
difference, and bits 0-30 of the output need to be nonzero exactly if
bits 0-31 of the difference were nonzero. So it's one big disjunction.

So I managed to find a branchless function. Not sure if it is actually
worth it to implement it. The branching version is easier to understand
and apparently gives better machine code on i386 and x86_64 (from just
eyeballing it). It is not even implemented with branches on those
architectures. And it is a micro-optimization, anyway.

Ciao,
Markus

Re: [musl] [PATCH] fix return value of wcs{,n}cmp for near-limits signed wchar_t values

[Gabriel Ravier]

On 1/6/23 17:57, Markus Wichmann wrote:
> Hi all,
>
> I thought a bit more about it. It would be possible to compress the
> information we need somewhat like this:
>
> int64_t d = (int64_t)*l - *r;
> return (d >> 1) | (d & INT_MAX);
>
> The idea is that I need bit 31 of the output to equal bit 32 of the
> difference, and bits 0-30 of the output need to be nonzero exactly if
> bits 0-31 of the difference were nonzero. So it's one big disjunction.
>
> So I managed to find a branchless function. Not sure if it is actually
> worth it to implement it. The branching version is easier to understand
> and apparently gives better machine code on i386 and x86_64 (from just
> eyeballing it). It is not even implemented with branches on those
> architectures. And it is a micro-optimization, anyway.
>
> Ciao,
> Markus

If you really want branchless machine code I think that could be 
obtained from just doing something like `return (a > b) - (a < b)` (on a 
good compiler) but I didn't use that because I didn't know if it would 
even be faster and it seemed a little confusing.

Now I've looked into it a bit more and after a quick benchmark at 
(https://quick-bench.com/q/0D4dWdFpDnMGu-BJNYmLQfBLVeo) it appears like 
all the options are roughly equal: the biggest difference I could find 
between all the different methods was that on Clang my second method was 
~30% faster than my first one... but it then becomes slightly slower 
than the others when compiled on GCC. So personally I would stay on the 
first version as it seems the simplest and the other alternatives aren't 
particularly faster.