Max value of typedef-ed type?

[Nikita The Spider]

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

 

[Nate Eldredge]

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.

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

 

[Keith Thompson]

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.

 

[Nikita The Spider]

     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

 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]

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.

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]

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.

Cheers
Philip

 

[Nate Eldredge]

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]

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]

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

 

[Peter Nilsson]

     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.

 

[Mark L Pappin]

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]

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.

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]

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

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

 

[S M Ryan]

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.

Perhaps something like

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

static long long maxsigned[] = {
[sizeof(char)] = SCHAR_MAX,
[sizeof(int)] = INT_MAX,
[sizeof(short int)] = SHRT_MAX,
[sizeof(long int)] = LONG_MAX,
[sizeof(long long int)] = LLONG_MAX,
};

int main(int argc,char **argv) {
typedef short int t1;
typedef long int t2;
printf("t1 max = %lld\nt2 max = %lld\n",
maxsigned[sizeof(t1)],
maxsigned[sizeof(t2)]);
return 0;
}