Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Max value of typedef-ed type?

577 views
Skip to first unread message

Nikita The Spider

unread,
Dec 15, 2008, 11:13:59 AM12/15/08
to
Hi all,
I'm scraping many years of rust & barnacles off of my C skills, and
I'm stuck at my first knotty and interesting problem.

I'm writing some code that needs to be cross platform and it uses
several typdef-ed numeric types. For instance, a key_t could be typdef-
ed as an int, ulong, etc. I need to be able to figure out what the
maximum value is that can be stuffed into the key_t and other types.

I've read some of the other threads on this problem[1] and there seems
to be no straightforward solution. Can someone help me understand why
the code below not work? (Please ignore the dodgy assumption in the
printf() that long long is supported.)

#include <stdio.h>

typedef long foo_t; // This represents my unknown type

int main (int argc, char const *argv[])
{
foo_t test_value;
foo_t max = 127;
int found = 0;

while (!found) {
test_value = (max * 2) + 1;
if ( (test_value <= max) || (test_value != ((max * 2) + 1)))
// overflow!
found = 1;
else
max = test_value;
}

printf("max: %llu\n", (unsigned long long)max);

return 0;
}


[1] Some previous threads on the subject:
http://groups.google.com/group/comp.lang.c/browse_thread/thread/d6f967e56fa87617
http://groups.google.com/group/comp.lang.c/browse_thread/thread/84628b61f288bcb2

Thanks
Philip

Eric Sosman

unread,
Dec 15, 2008, 11:57:16 AM12/15/08
to
Nikita The Spider wrote:
> Hi all,
> I'm scraping many years of rust & barnacles off of my C skills, and
> I'm stuck at my first knotty and interesting problem.
>
> I'm writing some code that needs to be cross platform and it uses
> several typdef-ed numeric types. For instance, a key_t could be typdef-
> ed as an int, ulong, etc. I need to be able to figure out what the
> maximum value is that can be stuffed into the key_t and other types.

For unsigned integer types it's easy: `(key_t)-1' is the
maximum value. If you need to, you can test for unsignedness
with `if ( (key_t)-1 > 0 )'.

For signed integer types the method you've shown (try longer
and longer strings of 1-bits until the value turns negative) is
about the best you can do. It's not guaranteed to work, though,
since the C language does not define what happens when a signed
integer calculation overflows: There's no certainty you'll get a
useful result, or that your program won't just crash.

For floating-point types I know of no clean method. You can
keep doubling until you find a value that doesn't change when doubled;
this would presumably be an infinity -- but not all floating-point
implementations use IEEE-style synthetic infinities. You might
also watch for a sudden decrease in value as a tip-off that an
exponent has overflowed and wrapped around, but you're still risking
a crash upon overflow. Also, once you find the maximum exponent value
you're not done: You need to fill in the fraction digits (usually bits,
but even that isn't guaranteed and some systems use hexadecimal "hits"
in F-P fractions). If you need to, you can test for floatness with
`if( (key_t)1/2 > 0 )'.

For complex types it's easy: There's no such thing as a maximum
or minimum value, so you can just lie back in your hammock and
call for another imaginary daiquiri.

IMHO this is not a good question to ask at run-time. The answer
was in a sense "known" at compile time, when key_t was defined, and
it would be simpler all around if the knowledge had been preserved
by defining KEY_MAX and perhaps KEY_MIN at the same time. Another
thing to consider is your reason for wanting to know the maximum
value a key_t can hold: What are you going to do with that value
once you have it, and can your problem be rearranged so you don't
need the information? (Sometimes it can't, but it never hurts to
ask.)

--
Eric....@sun.com

Nate Eldredge

unread,
Dec 15, 2008, 11:58:40 AM12/15/08
to
Nikita The Spider <NikitaT...@gmail.com> writes:

> Hi all,
> I'm scraping many years of rust & barnacles off of my C skills, and
> I'm stuck at my first knotty and interesting problem.
>
> I'm writing some code that needs to be cross platform and it uses
> several typdef-ed numeric types. For instance, a key_t could be typdef-
> ed as an int, ulong, etc. I need to be able to figure out what the
> maximum value is that can be stuffed into the key_t and other types.

I don't think there is going to be a portable way to do this.

If the type is known to be unsigned, (foo_t)-1 will be its maximum
possible value (6.3.1.3 (2)). But I can't think of an approach that
will work in general if the type could be signed. If it might be
floating point, worse yet.

The best approach would be to define an appropriate macro when the
typedef is made. E.g.

#include <limits.h>

#if defined(FOO_IS_INT)
typedef int foo_t;
#define FOO_MAX INT_MAX
#elif defined(FOO_IS_ULONG)
typedef unsigned long foo_t;
#define FOO_MAX ULONG_MAX
#elif ...
/*...*/
#endif

On the other hand, why do you need this information? There might be
some other way to get to whatever the goal is.

> I've read some of the other threads on this problem[1] and there seems
> to be no straightforward solution. Can someone help me understand why
> the code below not work? (Please ignore the dodgy assumption in the
> printf() that long long is supported.)
>
> #include <stdio.h>
>
> typedef long foo_t; // This represents my unknown type
>
> int main (int argc, char const *argv[])
> {
> foo_t test_value;
> foo_t max = 127;
> int found = 0;
>
> while (!found) {
> test_value = (max * 2) + 1;
> if ( (test_value <= max) || (test_value != ((max * 2) + 1)))
> // overflow!

I think a big concern here is that overflow in signed arithmetic is
allowed to have ill effects. It could trap, for example. You also
can't be sure that the machine is two's complement; if it uses a
sign-magnitude representation or something else, this won't work.

Keith Thompson

unread,
Dec 15, 2008, 12:48:54 PM12/15/08
to
Eric Sosman <Eric....@sun.com> writes:
> Nikita The Spider wrote:
>> Hi all,
>> I'm scraping many years of rust & barnacles off of my C skills, and
>> I'm stuck at my first knotty and interesting problem.
>> I'm writing some code that needs to be cross platform and it uses
>> several typdef-ed numeric types. For instance, a key_t could be typdef-
>> ed as an int, ulong, etc. I need to be able to figure out what the
>> maximum value is that can be stuffed into the key_t and other types.
>
> For unsigned integer types it's easy: `(key_t)-1' is the
> maximum value. If you need to, you can test for unsignedness
> with `if ( (key_t)-1 > 0 )'.
>
> For signed integer types the method you've shown (try longer
> and longer strings of 1-bits until the value turns negative) is
> about the best you can do. It's not guaranteed to work, though,
> since the C language does not define what happens when a signed
> integer calculation overflows: There's no certainty you'll get a
> useful result, or that your program won't just crash.

Another method that's likely to work in most implementations is to use
sizeof (key_t) * CHAR_BIT, under the assumption that key_t has exactly
(sizeof (key_t) * CHAR_BIT - 1) value bits and no trap
representations. There's probably a fairly simple expression using
left shift operators that computes this without risking overflow, but
I'm too lazy to work it out.

This will fail if key_t's representation includes padding bits.

> For floating-point types I know of no clean method. You can
> keep doubling until you find a value that doesn't change when doubled;
> this would presumably be an infinity -- but not all floating-point
> implementations use IEEE-style synthetic infinities. You might
> also watch for a sudden decrease in value as a tip-off that an
> exponent has overflowed and wrapped around, but you're still risking
> a crash upon overflow.

[...]

I don't know of any floating-point implementation where the exponent
quietly wraps around on overflow.

> you're not done: You need to fill in the fraction digits (usually bits,
> but even that isn't guaranteed and some systems use hexadecimal "hits"
> in F-P fractions). If you need to, you can test for floatness with
> `if( (key_t)1/2 > 0 )'.
>
> For complex types it's easy: There's no such thing as a maximum
> or minimum value, so you can just lie back in your hammock and
> call for another imaginary daiquiri.

Which you can mix with a real daiquiri to construct a comlex daiquiri.

> IMHO this is not a good question to ask at run-time. The answer
> was in a sense "known" at compile time, when key_t was defined, and
> it would be simpler all around if the knowledge had been preserved
> by defining KEY_MAX and perhaps KEY_MIN at the same time.

[...]

Agreed.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Eric Sosman

unread,
Dec 15, 2008, 1:08:28 PM12/15/08
to
Keith Thompson wrote:
> Eric Sosman <Eric....@sun.com> writes:
>> [...]

>> For floating-point types I know of no clean method. You can
>> keep doubling until you find a value that doesn't change when doubled;
>> this would presumably be an infinity -- but not all floating-point
>> implementations use IEEE-style synthetic infinities. You might
>> also watch for a sudden decrease in value as a tip-off that an
>> exponent has overflowed and wrapped around, but you're still risking
>> a crash upon overflow.
> [...]
>
> I don't know of any floating-point implementation where the exponent
> quietly wraps around on overflow.

My (hazy) recollection of the IBM S/360 is that exponent overflow
produced a too-small exponent and a hardware-generated trap, but that
the system could run in a mode where the trap was suppressed and all
you got was the too-small result. My (unfounded) supposition is that
this capability is probably still present in the 360's descendants,
including today's zSeries systems.

The VAX was another system whose floating-point had no infinities,
but I did almost no floating-point work on VAX and can't remember what
it did on overflow. VAXen may be scarce nowadays, but the Alpha CPU
that succeeded them has a sort of hybrid floating-point that supports
both IEEE numbers and some of the VAX numbers. If you're using VAX-
style numbers on an Alpha they can't overflow to infinity (no such
thing), but again I can't recall exactly what they *do* do.

Anyhow, the main point was that trying to find the maximum value
of a floating-point type can be a beastly business, fraught with non-
portabilities.

--
Eric....@sun.com

Nikita The Spider

unread,
Dec 15, 2008, 1:35:04 PM12/15/08
to
On Dec 15, 11:57 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
> Nikita The Spider wrote:
> > Hi all,
> > I'm scraping many years of rust & barnacles off of my C skills, and
> > I'm stuck at my first knotty and interesting problem.
>
> > I'm writing some code that needs to be cross platform and it uses
> > several typdef-ed numeric types. For instance, a key_t could be typdef-
> > ed as an int, ulong, etc. I need to be able to figure out what the
> > maximum value is that can be stuffed into the key_t and other types.
>
>      For unsigned integer types it's easy: `(key_t)-1' is the
> maximum value.  If you need to, you can test for unsignedness
> with `if ( (key_t)-1 > 0 )'.
>
>      For signed integer types the method you've shown (try longer
> and longer strings of 1-bits until the value turns negative) is
> about the best you can do.  It's not guaranteed to work, though,
> since the C language does not define what happens when a signed
> integer calculation overflows: There's no certainty you'll get a
> useful result, or that your program won't just crash.
>
>      For floating-point types I know of no clean method.

I should have said that I'm willing to make the assumption that my
types are limited to integers (int, long, long long, possibly signed).

>      IMHO this is not a good question to ask at run-time.  The answer
> was in a sense "known" at compile time, when key_t was defined, and
> it would be simpler all around if the knowledge had been preserved
> by defining KEY_MAX and perhaps KEY_MIN at the same time.

Heartily agreed, and I intend to raise that issue in my discussion
with the authors of <sys/ipc.h>!

> Another
> thing to consider is your reason for wanting to know the maximum
> value a key_t can hold: What are you going to do with that value
> once you have it, and can your problem be rearranged so you don't
> need the information?  (Sometimes it can't, but it never hurts to
> ask.)

A fair question. I'm writing (in C) an extension for Python. The
extension will be downloaded by the end-user (a Python programmer) as
C source that she compiles onto her machine into a library that the
Python interpreter can talk to. The extension should compile on
anything that supports SysV IPC. (I've got a similar extension for
POSIX IPC.) It's incumbent upon me as the extension developer to
expose to Python the limits the Python caller must obey, so if she
passes a value of, say, 999999 for a key I can raise a "Sorry that's
too big" error.

I'd like to know the maximum (or minimum) of uid_t, gid_t, mode_t and
key_t. I'd also like to know the maximum value that a semaphore can
hold. It's #defined as SEMVMX on some systems, but on others it is
configurable and not in a header file at all (which is a different
problem entirely that may require multiple daiquiri to solve). I'd at
least like to restrict it to the maximum that the type can hold.

Thanks
Philip

Nikita The Spider

unread,
Dec 15, 2008, 1:38:21 PM12/15/08
to
On Dec 15, 11:58 am, Nate Eldredge <n...@vulcan.lan> wrote:

See my response to Eric S. who raised a lot of the same excellent
points that you did.


> > I've read some of the other threads on this problem[1] and there seems
> > to be no straightforward solution. Can someone help me understand why
> > the code below not work? (Please ignore the dodgy assumption in the
> > printf() that long long is supported.)
>
> > #include <stdio.h>
>
> > typedef long foo_t;   // This represents my unknown type
>
> > int main (int argc, char const *argv[])
> > {
> >     foo_t test_value;
> >     foo_t max = 127;
> >     int found = 0;
>
> >     while (!found) {
> >         test_value = (max * 2) + 1;
> >         if ( (test_value <= max) || (test_value != ((max * 2) + 1)))
> >             // overflow!
>
> I think a big concern here is that overflow in signed arithmetic is
> allowed to have ill effects.  It could trap, for example.  You also
> can't be sure that the machine is two's complement; if it uses a
> sign-magnitude representation or something else, this won't work.

I suspected that my code was two's complement-specific. I guess the
problem in sign-magnitude representation would be that this:


(test_value <= max) || (test_value != ((max * 2) + 1))

would never become true?

Thanks
Philip

Nikita The Spider

unread,
Dec 15, 2008, 1:43:41 PM12/15/08
to
On Dec 15, 12:48 pm, Keith Thompson <ks...@mib.org> wrote:

I like the suggestion but I'm not sure I follow you on the last point.
Do you mean padding inserted by the compiler or an assumption by other
code that uses key_t that the top N bits are padding-only? If it is
the former I don't see the problem, and if it is the latter I don't
see how the code author could assume that without providing a
KEY_T_MAX definition.

Cheers
Philip

Nate Eldredge

unread,
Dec 15, 2008, 3:16:54 PM12/15/08
to
Nikita The Spider <NikitaT...@gmail.com> writes:

> On Dec 15, 11:57 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
>> Another
>> thing to consider is your reason for wanting to know the maximum
>> value a key_t can hold: What are you going to do with that value
>> once you have it, and can your problem be rearranged so you don't
>> need the information?  (Sometimes it can't, but it never hurts to
>> ask.)
>
> A fair question. I'm writing (in C) an extension for Python. The
> extension will be downloaded by the end-user (a Python programmer) as
> C source that she compiles onto her machine into a library that the
> Python interpreter can talk to. The extension should compile on
> anything that supports SysV IPC. (I've got a similar extension for
> POSIX IPC.) It's incumbent upon me as the extension developer to
> expose to Python the limits the Python caller must obey, so if she
> passes a value of, say, 999999 for a key I can raise a "Sorry that's
> too big" error.

Perhaps something like the following would work.

key_t set_key(python_int_t n) {
key_t k = n;
if ((n != k) || (n >= 0 && k < 0) || (n < 0 && k >= 0))
error("Sorry, too big!");
return k;
}

The comparison `n != k' should cause `k' to be promoted to python_int_t
(which is presumably bigger; if not then there is no problem anyway).
This would check whether the value of `n' fits into `k'. It
might fail if one of the two is unsigned and the other is negative,
hence the rest of the test.

Keith Thompson

unread,
Dec 15, 2008, 3:58:25 PM12/15/08
to
Nikita The Spider <NikitaT...@gmail.com> writes:
> On Dec 15, 12:48 pm, Keith Thompson <ks...@mib.org> wrote:
[...]

>> Another method that's likely to work in most implementations is to use
>> sizeof (key_t) * CHAR_BIT, under the assumption that key_t has exactly
>> (sizeof (key_t) * CHAR_BIT - 1) value bits and no trap
>> representations.  There's probably a fairly simple expression using
>> left shift operators that computes this without risking overflow, but
>> I'm too lazy to work it out.
>>
>> This will fail if key_t's representation includes padding bits.
>
> I like the suggestion but I'm not sure I follow you on the last point.
> Do you mean padding inserted by the compiler or an assumption by other
> code that uses key_t that the top N bits are padding-only? If it is
> the former I don't see the problem, and if it is the latter I don't
> see how the code author could assume that without providing a
> KEY_T_MAX definition.

C allows padding bits within the representation of an integer type.
For example, it's legal for sizeof(int)*CHAR_BIT to be 32, but for it
to have say, 1 sign bit, 23 value bits, and 8 padding bits. Padding
bits do not affect the value of an object, though they might affect
whether it's a trap representation or not. Given this representation,
INT_MAX == 2**23-1; just looking at the size would imply INT_MAX ==
2**31-1.

You're unlikely to run into this kind of thing in real life.

Keith Thompson

unread,
Dec 15, 2008, 4:34:43 PM12/15/08
to
Nikita The Spider <NikitaT...@gmail.com> writes:
> On Dec 15, 11:57 am, Eric Sosman <Eric.Sos...@sun.com> wrote:
[...]

>> Another
>> thing to consider is your reason for wanting to know the maximum
>> value a key_t can hold: What are you going to do with that value
>> once you have it, and can your problem be rearranged so you don't
>> need the information?  (Sometimes it can't, but it never hurts to
>> ask.)
>
> A fair question. I'm writing (in C) an extension for Python. The
> extension will be downloaded by the end-user (a Python programmer) as
> C source that she compiles onto her machine into a library that the
> Python interpreter can talk to. The extension should compile on
> anything that supports SysV IPC. (I've got a similar extension for
> POSIX IPC.) It's incumbent upon me as the extension developer to
> expose to Python the limits the Python caller must obey, so if she
> passes a value of, say, 999999 for a key I can raise a "Sorry that's
> too big" error.
>
> I'd like to know the maximum (or minimum) of uid_t, gid_t, mode_t and
> key_t. I'd also like to know the maximum value that a semaphore can
> hold. It's #defined as SEMVMX on some systems, but on others it is
> configurable and not in a header file at all (which is a different
> problem entirely that may require multiple daiquiri to solve). I'd at
> least like to restrict it to the maximum that the type can hold.

I think what you're looking for is the maximum *meaningful* value of
these types rather than the maximum representable value, and that's
not really a C question.

As for the maximum representable value, if you're willing to restrict
the set of systems on which this will work, you might get away with
something like this:

switch (sizeof (key_t) * CHAR_BIT) {
case 8: return 0x7f;
case 16: return 0x7fff;
case 32: return 0x7fffffff;
case 64: return 0x7fffffffffffffff;
default: /* fatal error */
}

(Note the phrase "something like"; I haven't tested this, and I don't
guarantee that it's correct.)

Eric Sosman

unread,
Dec 15, 2008, 5:06:43 PM12/15/08
to

<topicality level="marginal">

The first four types you mention aren't really "values" in the
sense of "quantities" that can be too large, too small, or just
right, but something more like "codes." They are numbers in the
same way your telephone number is a number: They're really just
arbitrary symbols expressed in numeric form for ease of generation
and of manipulation. You can't determine the validity of a uid_t
by making range comparisons or other arithmetic calculations: You've
got to look the thing up in some kind of roster or directory. That
raises some doubt (in my mind, anyhow) about the utility of performing
the range check in the first place: It just doesn't tell you much.

True, mode_t exposes a little more internal structure and isn't
quite as arbitrary as the others. But still, magnitude checks aren't
the way to discover whether a particular mode_t value makes sense.
For example, 0400 and 0666 are perfectly reasonable mode_t's, yet
0477 (which lies between them) is silly.

The semaphore maximum is another type of beast, because the
value really does count somthing, to wit, the excess of posts over
waits. I don't know what to recommend for that one, I'm afraid.

Since these are POSIX-specified types, you might have more luck
in a POSIX-oriented newsgroup like comp.unix.programmer. For example,
you might be able to find guarantees that some of these types are
unsigned, in which case the maximum (if you still feel it's useful)
is easily obtained. Or maybe you'll find guarantees about behavior
of signed integer overflow, which would ease the calculation for
signed types.

</topicality>

--
Eric....@sun.com

Peter Nilsson

unread,
Dec 15, 2008, 7:08:29 PM12/15/08
to
Eric Sosman <Eric.Sos...@sun.com> wrote:
> Nikita The Spider wrote:
> > ...I need to be able to figure out what the maximum

> > value is that can be stuffed into the key_t and other
> > types.
>
>      For unsigned integer types it's easy: `(key_t)-1'
> is the maximum value.  If you need to, you can test for
> unsignedness with `if ( (key_t)-1 > 0 )'.
>
>      For signed integer types the method you've shown
> (try longer and longer strings of 1-bits until the value
> turns negative) is about the best you can do.

Arguably best is the following, courtesy of Lawrence Kirby.

unsigned long value;
key_t tmp;

value = -1;
while ((tmp = value) < 0 || tmp != value)
value >>= 1;

/* value is now maximum of key_t */

> It's not guaranteed to work, though, since the C language
> does not define what happens when a signed integer
> calculation overflows: There's no certainty you'll get a
> useful result, or that your program won't just crash.

<snip>

The earlier code isn't maximally portable C99 since C99
introduced an implementation-defined signal in the case
of conversion to a signed integer of a value not in range.

--
Peter

Mark L Pappin

unread,
Dec 15, 2008, 8:57:21 PM12/15/08
to
Keith Thompson <ks...@mib.org> writes:
> Eric Sosman <Eric....@sun.com> writes:
>> Nikita The Spider wrote:
>>> I need to be able to figure out what the maximum value is that can
>>> be stuffed into the key_t and other types.

>> For floating-point types I know of no clean method. You can keep
>> doubling [...] You might also watch for a sudden decrease in value


>> as a tip-off that an exponent has overflowed and wrapped around,

> I don't know of any floating-point implementation where the exponent


> quietly wraps around on overflow.

At least one compiler for tiny[0] 8-bit microcontrollers did[1] in its
software-emulated FP code.

mlp

[0] down to tens of bytes of RAM and small hundreds of bytes of ROM
[1] as of 12 months ago when I was employed by the compiler vendor, FP
values were in IEEE-754 format but every bitpattern was treated as a
valid normalized value - no Inf, NaN, etc.

Nikita The Spider

unread,
Dec 15, 2008, 11:10:55 PM12/15/08
to
On Dec 15, 4:34 pm, Keith Thompson <ks...@mib.org> wrote:

Well yes, I'd much prefer to know the max meaningful value for key_t &
friends. But that's an implementation-specific opinion, and apparently
systems like to keep their opinions to themselves, judging by the lack
of definitions for KEY_T_MAX, UID_T_MAX, etc. in limits.h or sem.h. In
the absence of hints from the system, I have to assume that all (non-
negative) values are potentially meaningful and not preclude their
representation by my type choices.

To put it another way, my code just schleps values from Python to C
API calls and vice versa. It's up to the user to make sense of them,
but I don't want to mangle them in transit. My code also needs to warn
callers about out-of-range values since Python code doesn't have
access to sizeof() and so forth.

Thanks for the explanation about padding bits, BTW, and the sample
code below.


>
> As for the maximum representable value, if you're willing to restrict
> the set of systems on which this will work, you might get away with
> something like this:
>
>     switch (sizeof (key_t) * CHAR_BIT) {
>         case 8:  return 0x7f;
>         case 16: return 0x7fff;
>         case 32: return 0x7fffffff;
>         case 64: return 0x7fffffffffffffff;
>         default: /* fatal error */
>     }
>
> (Note the phrase "something like"; I haven't tested this, and I don't
> guarantee that it's correct.)


Cheers
Philip

Nikita The Spider

unread,
Dec 15, 2008, 11:36:21 PM12/15/08
to
On Dec 15, 5:06 pm, Eric Sosman <Eric.Sos...@sun.com> wrote:
> Nikita The Spider wrote:

It's true that I can't determine whether or not a value passed to me
is valid by a simple range check, but certain ranges are definitely
*in*valid. I want to alert users of my code if they attempt to use
values that I know cannot possibly be valid.

It's also true that the max semaphore value is a biggie because a
programmer is unlikely to care what the maximum gid is that he can
invent, he may well care about how many shared resources a semaphore
can represent. Fortunately that's #defined sometimes and I might be
able to wheedle it out of sysctl on other (usually BSD-ish) systems.


Thanks
Philip

Message has been deleted
0 new messages