ptrdiff_t maximum

[John Kelly]

It may not be pleasing or sneaky, but it does work under C90.

That's a start. But I want C99 too.

6.3.1.3 Signed and unsigned integers

3 Otherwise, the new type is signed and the value cannot be
represented in it; either the result is implementation-defined
or an implementation-defined signal is raised.

So when the value assigned to new, which is signed (ptrdiff_t), cannot
be represented, a signal may be raised. Uh-oh, the UB boogeyman!

Let's look again,

for (max = 32767; (new = 2ul * max + 1) > max

and think about what 6.3.1.8 says

... integer promotions are performed on both operands. Then the
following rules are applied to the promoted operands:

(a) If both operands have the same type, then no further conversion is needed.

Not true. 2ul is unsigned, max (ptrdiff_t) is signed.

(b) Otherwise, if both operands have signed integer types or both have unsigned
integer types, the operand with the type of lesser integer conversion rank is
converted to the type of the operand with greater rank.

Not true. Same as above.

(c) Otherwise, if the operand that has unsigned integer type has rank greater or
equal to the rank of the type of the other operand, then the operand with
signed integer type is converted to the type of the operand with unsigned
integer type.

Possibly false. Rank of (ptrdiff_t) may be greater than 2ul.

(d) Otherwise, if the type of the operand with signed integer type can represent
all of the values of the type of the operand with unsigned integer type, then
the operand with unsigned integer type is converted to the type of the
operand with signed integer type.

Possibly false. Rank of (ptrdiff_t) may be less than 2ul.

(e) Otherwise, both operands are converted to the unsigned integer type
corresponding to the type of the operand with signed integer type.

The (e) catch-all has the same effect as (c). 2ul is already unsigned
and max is converted to unsigned. So with (c) or (e), both operands are
sure to become unsigned. Thus the "l" in "2ul" is redundant. It can be
reduced to 2u. That is enough to ensure (c) or (e).

OK. But the UB boogeyman is still lurking in:

(new = 2u * max + 1)

because "new" is signed (ptrdiff_t), and we're back to 6.3.1.3

Otherwise, the new type is signed and the value cannot be represented
in it ... an implementation-defined signal is raised.

Oops. Hmmm. We could assign to a different variable which is unsigned,
but we have no way of knowing what rank to choose for it, since we don't
know the rank of (ptrdiff_t). Chicken and egg problem.

If we could just pretend that (ptrdiff_t) is unsigned, the boogeyman
would go away. Hmmm. I never tried casting the lhs of an assignment
before. Wonder if it works?

Wait for it ...

 

[John Kelly]

If we could just pretend that (ptrdiff_t) is unsigned, the boogeyman
would go away. Hmmm. I never tried casting the lhs of an assignment
before. Wonder if it works?

Wait for it ...

Here it comes ... the no Boogeyman solution, with test output ...







# include <stdio.h>
# include <stddef.h>

int
main (void)
{
ptrdiff_t last, next;

printf ("\n");
printf (" last");
printf (" next");
printf (" double");
printf ("\n\n");
for (last = 32767; {
(unsigned) next = 2u * last + 1;
printf ("%22lld %22lld %32f\n", (long long) last, (long long) next,
(double) next);
if (next > 0)
last = next;
else
break;
}
printf ("\n%22lld\n%22llx\n\n", (long long) last, (long long) last);
return 0;
}

 

[Seebs]

(unsigned) next = 2u * last + 1;

I wonder what this cast is intended to accomplish.

-s

 

[John Kelly]

Here it comes ... the no Boogeyman solution, with test output ...

Oops. Forgot to compile it under C99 ...

gcc -Wall -Werror -O2 -std=c99 -o dh dh.c
dh.c: In function 'ptrdiff_max_':
dh.c:181: error: lvalue required as left operand of assignment
make: *** [dh] Error 1

So much for the C99 solution ...

 

[Keith Thompson]

If we could just pretend that (ptrdiff_t) is unsigned, the boogeyman
would go away. Hmmm. I never tried casting the lhs of an assignment
before. Wonder if it works?

Wait for it ...

Here it comes ... the no Boogeyman solution, with test output ... [snip]
(unsigned) next = 2u * last + 1;

[snip]

If you didn't get a diagnostic on that line, there's something seriously
wrong with your compiler. ``(unsigned) next'' is not a modifiable
lvalue.

Whatever you were trying to do, there's a better way to do it.

 

[Keith Thompson]

Here it comes ... the no Boogeyman solution, with test output ...

Oops. Forgot to compile it under C99 ...

gcc -Wall -Werror -O2 -std=c99 -o dh dh.c
dh.c: In function 'ptrdiff_max_':
dh.c:181: error: lvalue required as left operand of assignment
make: *** [dh] Error 1

So much for the C99 solution ...

What did you compile it under? It's no more legal in C90 than in C99
<OT>or in C++</OT>.

 

[John Kelly]

Oops. Forgot to compile it under C99 ...

gcc -Wall -Werror -O2 -std=c99 -o dh dh.c
dh.c: In function 'ptrdiff_max_':
dh.c:181: error: lvalue required as left operand of assignment
make: *** [dh] Error 1

So much for the C99 solution ...

What did you compile it under? It's no more legal in C90 than in C99
<OT>or in C++</OT>.

gcc 3.3 on Interix. No complaints with

-Wall -Werror -O2

But then I moved it over to linux and discovered that bird won't fly.

 

[Ben Bacarisse]

That's a start. But I want C99 too.

There is no problem in C99. If you don't have PTRDIFF_MAX, you don't
have C99. The code Peter posted is there to solve a problem in C90 that
does not exist in C99.

If you try anything similar in C99 you risk the risk of a signal being
raised so there is no point in try to make the above 100% portable to
C99 implementations.

<snip>

 

[John Kelly]

Oops. Forgot to compile it under C99 ...

gcc -Wall -Werror -O2 -std=c99 -o dh dh.c
dh.c: In function 'ptrdiff_max_':
dh.c:181: error: lvalue required as left operand of assignment
make: *** [dh] Error 1

So much for the C99 solution ...

Let's start over.

for (max = 32767; (new = 2ul * max + 1) > max

The problem with this approach is, the test and the assignment are
jammed together.

To avoid UB, the test must be separated from the assignment. That way,
we can do the test using only unsigned values, which never evoke UB.

Then, if we pass the test, we can do the assignment, knowing that the
value is not out of range. Goodbye UB Boogeyman!

last = 32767;
while (last < last * 2u + 2) {
last = last * 2u + 1;
}

Wow. Such a simple thing is so hard to discover in C. I wonder if go
is easier.

Here is the full test code, in case anyone else in interested in this.



# include <stdio.h>
# include <stddef.h>

int
main (void)
{
ptrdiff_t last, next;

printf ("\n");
printf (" last");
printf (" next");
printf (" double");
printf ("\n\n");

last = 32767;
while (last < last * 2u + 2) {
next = last * 2u + 1;
printf ("%22lld %22lld %32f\n", (long long) last,
(long long) next, (double) next);
last = next;
}
printf ("\n%22lld\n%22llx\n\n", (long long) last, (long long) last);

last = 32767;
while (last < last * 2u + 2) {
last = last * 2u + 1;
}

return 0;
}

 

[John Kelly]

There is no problem in C99. If you don't have PTRDIFF_MAX, you don't
have C99. The code Peter posted is there to solve a problem in C90 that
does not exist in C99.

I understand that. Nevertheless, I still want a universal solution that
compiles without #ifdefs.

If you try anything similar in C99 you risk the risk of a signal being
raised so there is no point in try to make the above 100% portable to
C99 implementations.

I had to deconstruct and reconstruct Peter's suggested code, but that's
sometimes what programmers have to do.

I just posted the new solution. It compiles with c89 or c99, and there
is no UB.

 

[John Kelly]

Let's start over.

for (max = 32767; (new = 2ul * max + 1) > max

The problem with this approach is, the test and the assignment are
jammed together.

To avoid UB, the test must be separated from the assignment. That way,
we can do the test using only unsigned values, which never evoke UB.

Then, if we pass the test, we can do the assignment, knowing that the
value is not out of range. Goodbye UB Boogeyman!

last = 32767;
while (last < last * 2u + 2) {
last = last * 2u + 1;
}

And one more thing ...

Since we prove the assignment will be in range, the "u" in the "2u" is
not needed a second time. So reduced to its simplest possible terms, we
can succinctly say:


last = 32767;
while (last < last * 2u + 2) {
last = last * 2 + 1;
}

 

[Ben Bacarisse]

And one more thing ...

Since we prove the assignment will be in range, the "u" in the "2u" is
not needed a second time. So reduced to its simplest possible terms, we
can succinctly say:


last = 32767;
while (last < last * 2u + 2) {
last = last * 2 + 1;
}

What happens if ptrdiff_t is wider than unsigned int? Peter used 2ul
for a C90 solution because in C90 ptrdiff_t can't be wider than the
signed version of unsigned long.

 

[John Kelly]

What happens if ptrdiff_t is wider than unsigned int?

The compiler must promote all operands to the largest among them.

6.3.1.8 Usual arithmetic conversions

Otherwise, if the operand that has unsigned integer type has rank
greater or equal to the rank of the type of the other operand, then
the operand with signed integer type is converted to the type of the
operand with unsigned integer type.

That will be false, so we continue ...

Otherwise, both operands are converted to the unsigned integer type
corresponding to the type of the operand with signed integer type.

So both get converted to unsigned, equal to the size of ptrdiff_t.

Thus, it's not necessary to predetermine and force a certain size. The
compiler will handle it for you. The key is to specify 'u' so that each
operand is converted to unsigned.

 

[Ben Bacarisse]

The compiler must promote all operands to the largest among them.

Which is ptrdiff_t -- a signed type that can overflow giving undefined
behaviour. You posted the above to avoid UB by using unsigned
arithmetic.

That will be false, so we continue ...
Yup...


So both get converted to unsigned, equal to the size of ptrdiff_t.

No. You missed out the paragraph that applies to this case. I don't
think you can have missed it -- its right there between the one that you
say does not apply and the one that you say does. Are just having a
laugh? Here it is for those following along (are there any?):

| Otherwise, if the type of the operand with signed integer type can
| represent all of the values of the type of the operand with unsigned
| integer type, then the operand with unsigned integer type is converted
| to the type of the operand with signed integer type.

Thus, it's not necessary to predetermine and force a certain size. The
compiler will handle it for you. The key is to specify 'u' so that each
operand is converted to unsigned.

Nope. Try it on an implementation that (a) has ptrdiff_t wider than
unsigned and (b) signals an error on integer overflow and you'll see.

 

[John Kelly]

Which is ptrdiff_t -- a signed type that can overflow giving undefined
behaviour. You posted the above to avoid UB by using unsigned
arithmetic.
Right.



No. You missed out the paragraph that applies to this case. I don't
think you can have missed it -- its right there between the one that you
say does not apply and the one that you say does.

I read it, but too quickly.

Are just having a laugh?
No.


Here it is for those following along (are there any?):

| Otherwise, if the type of the operand with signed integer type can
| represent all of the values of the type of the operand with unsigned
| integer type, then the operand with unsigned integer type is converted
| to the type of the operand with signed integer type.


Nope. Try it on an implementation that (a) has ptrdiff_t wider than
unsigned and (b) signals an error on integer overflow and you'll see.

I thought I had all cases covered, but now I see you're right. I need
to think again. Perhaps

(last < last * 2llu + 2)

Though that's a hard coded hack, which I was trying to avoid. I was
looking for a universal method of finding the maximum value for any
signed type, not just ptrdiff_t, without UB. But as you point out, I
haven't found it yet.

If only there was a way to make the compiler omit this step:

| Otherwise, if the type of the operand with signed integer type can
| represent all of the values of the type of the operand with unsigned
| integer type, then the operand with unsigned integer type is converted
| to the type of the operand with signed integer type.

But ATM, I can't think of any.

 

[John Kelly]

John Kelly <[email protected]> wrote:

I thought I had all cases covered, but now I see you're right. I need
to think again. Perhaps

(last < last * 2llu + 2)

Though that's a hard coded hack, which I was trying to avoid. I was
looking for a universal method of finding the maximum value for any
signed type, not just ptrdiff_t, without UB. But as you point out, I
haven't found it yet.

If only there was a way to make the compiler omit this step:



But ATM, I can't think of any.

static ptrdiff_t
ptrdiff_max_ (void)
{
ptrdiff_t last = 32767;

while (last < (unsigned) last * 2u + 2u) {
last = last * 2 + 1;
}
return last;
}


Until now, I thought the (unsigned) cast was unnecessary. But as Ben
pointed out, I misread a step in the standard. I think this new version
satisfies the universal property I'm looking for.


step (a)

If both operands have the same type, then no further conversion is needed.

or step (b)

Otherwise, if both operands have signed integer types or both have
unsigned integer types, the operand with the type of lesser integer
conversion rank is converted to the type of the operand with greater
rank.

should always be true for

(unsigned) last * 2u + 2u

 

[Ben Bacarisse]

static ptrdiff_t
ptrdiff_max_ (void)
{
ptrdiff_t last = 32767;

while (last < (unsigned) last * 2u + 2u) {
last = last * 2 + 1;
}
return last;
}


Until now, I thought the (unsigned) cast was unnecessary. But as Ben
pointed out, I misread a step in the standard. I think this new version
satisfies the universal property I'm looking for.

With the above (and the right headers) this:

int main(void)
{
ptrdiff_t pd = ptrdiff_max_();
printf("%td %td\n", pd, 2 * pd);
return 0;
}

prints

2147483647 4294967294

on my machine, neither of which is anywhere close to PTRDIFF_MAX.

<snip>

 

[John Kelly]

With the above (and the right headers) this:

int main(void)
{
ptrdiff_t pd = ptrdiff_max_();
printf("%td %td\n", pd, 2 * pd);
return 0;
}

prints

2147483647 4294967294

on my machine, neither of which is anywhere close to PTRDIFF_MAX.

OK. Another thinko.

Apparently the (unsigned) cast means (int) and truncates the size of
ptrdiff_t. I suppose (unsigned long long) would work but that's the
same hack as 2llu.

I was looking for a dynamic way of treating ptrdiff_t type as unsigned,
but maybe that's not possible with C.

 

[Seebs]

Apparently the (unsigned) cast means (int) and truncates the size of
ptrdiff_t. I suppose (unsigned long long) would work but that's the
same hack as 2llu.

Yes. "(unsigned)" is a synonym for "(unsigned int)".

I was looking for a dynamic way of treating ptrdiff_t type as unsigned,
but maybe that's not possible with C.

Not particularly. And even "(unsigned long long)" might not work, because
nothing prevents a future system from having ptrdiff_t larger than long
long.

On the other hand, the question is probably moot, as so far as I can tell,
none of this ever comes up in real test cases without doing something more
exciting sooner.

-s

 

[John Kelly]

#include <stdio.h>
#include <stddef.h>
#include <limits.h>

int main()
{
printf("ptrdiff_t maximum %ld\n",
(long)(~(1UL<<(sizeof(ptrdiff_t)*CHAR_BIT-1))));
}

Works for ptrdiff_t, but not for a short.

Here's another try at the elusive universal solution for the maximum
value of any signed type. You expand the macro with the types you're
interested in. It takes two arguments: the type, and a symbolic_name
for the type. Calling a function named symbolic_name_max_ returns the
type's maximum positive value.



# include <limits.h>
# include <stddef.h>
# include <stdio.h>

# define MAX_SIGNED_BITS(type) (sizeof (type) * CHAR_BIT - 1)

# define MAX_SIGNED(type, name) \
\
type \
name ## _max_ (void)\
{ \
type last; \
int tn, bits = MAX_SIGNED_BITS(type); \
for (last = 1, tn = 1; tn < bits; tn++) { \
last = last * 2 + 1; \
} \
return last; \
}

MAX_SIGNED (short, short);
MAX_SIGNED (ptrdiff_t, ptrdiff_t);
MAX_SIGNED (long long, long_long);

int
main (void)
{
short const short_max = short_max_ ();
ptrdiff_t const ptrdiff_t_max = ptrdiff_t_max_ ();
long long const long_long_max = long_long_max_ ();

printf ("short_max = %d\n", short_max);
printf ("ptrdiff_t_max = %d\n", ptrdiff_t_max);
printf ("long_long_max = %lld\n", long_long_max);

return 0;
}