Velocity Reviews > Trap representations for unsigned integers

# Trap representations for unsigned integers

Army1987
Guest
Posts: n/a

 04-21-2007
If uMyInt_t is an unsigned integral type, is the following a
necessary and sufficient condition that uMyInt_t has no trap
representation?

(uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1

That is, I'm asking wheter it equals 0 whenever uMyInt_t has trap
representations, equals a nonzero value whenever uMyInt_t has no
trap representation, and never triggers undefined behaviour.

--
#include <stdio.h>
char s[]="\16Jsa ukenethr ,cto haCr\n";int main(void){*s*=5;*
s%=23;putchar(s[0][s]);return*s-14?main():!putchar(9[s+*s]);}

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a

 04-21-2007
Army1987 wrote:
> If uMyInt_t is an unsigned integral type, is the following a
> necessary and sufficient condition that uMyInt_t has no trap
> representation?
>
> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1

No. If uMyInt_t has padding bits, you will right-shift by a number
greater than (or equal to) the number of value bits, and for that the
behaviour is undefined.

Eric Sosman
Guest
Posts: n/a

 04-21-2007
Army1987 wrote:
> If uMyInt_t is an unsigned integral type, is the following a
> necessary and sufficient condition that uMyInt_t has no trap
> representation?
>
> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1
>
> That is, I'm asking wheter it equals 0 whenever uMyInt_t has trap
> representations, equals a nonzero value whenever uMyInt_t has no
> trap representation, and never triggers undefined behaviour.

I think there are at least two problems with this test.
First, if uMyInt_t has padding bits the shift count may be
too large and lead to undefined behavior ("may" because of
possible promotion to int or unsigned int). Second, the
presence of padding bits does not imply the existence of trap
representations: the extra bits may just be along for the ride.

The best way to detect padding bits may be to count the
number of 1's in (uMyInt_t)-1, or to compare the numeric value
of (uMyInt_t)-1 to the "expected" quantity. The first test is
easy at run time but difficult or impossible at preprocessing
time; the second has problems, too (what type should you use
to form the expected value?). I can think of no reliable way
to determine whether trap representations exist; if you find
there are no padding bits you can deduce that there are no
traps, but that's as far as I think you can get.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Army1987
Guest
Posts: n/a

 04-21-2007
"Harald van D?k" <(E-Mail Removed)> ha scritto nel messaggio
news:(E-Mail Removed) oups.com...
> Army1987 wrote:
>> If uMyInt_t is an unsigned integral type, is the following a
>> necessary and sufficient condition that uMyInt_t has no trap
>> representation?
>>
>> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1

>
> No. If uMyInt_t has padding bits, you will right-shift by a number
> greater than (or equal to) the number of value bits, and for that the
> behaviour is undefined.

Is

destruct. Get a real computer."), exit(1)),
/* On the DeathStation 9000 exit(1) activates self-destruction */
ceil(log2((uMyInt_t)(-1))) >= CHAR_BIT*sizeof(uMyInt_t) )

any better?

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a

 04-21-2007
Army1987 wrote:
> "Harald van D?k" <(E-Mail Removed)> ha scritto nel messaggio
> news:(E-Mail Removed) oups.com...
> > Army1987 wrote:
> >> If uMyInt_t is an unsigned integral type, is the following a
> >> necessary and sufficient condition that uMyInt_t has no trap
> >> representation?
> >>
> >> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1

> >
> > No. If uMyInt_t has padding bits, you will right-shift by a number
> > greater than (or equal to) the number of value bits, and for that the
> > behaviour is undefined.

>
> Is
>
> ( DBL_MAX >= (uMyInt_t)(-1) || (puts("Your DS9K is about to self-\
> destruct. Get a real computer."), exit(1)),
> /* On the DeathStation 9000 exit(1) activates self-destruction */
> ceil(log2((uMyInt_t)(-1))) >= CHAR_BIT*sizeof(uMyInt_t) )
>
> any better?

On the DS9K, DBL_MAX would be large enough, but CHAR_BIT *
sizeof(uMuInt_t) would give the wrong result because SIZE_MAX is too
small.

integer constant expression, so at this point there's no downside to
just writing a function.

Army1987
Guest
Posts: n/a

 04-21-2007
"Eric Sosman" <(E-Mail Removed)> ha scritto nel messaggio
news:(E-Mail Removed). ..
> Army1987 wrote:
>> If uMyInt_t is an unsigned integral type, is the following a
>> necessary and sufficient condition that uMyInt_t has no trap
>> representation?
>>
>> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1
>>
>> That is, I'm asking wheter it equals 0 whenever uMyInt_t has trap
>> representations, equals a nonzero value whenever uMyInt_t has no
>> trap representation, and never triggers undefined behaviour.

[snip] Second, the
> presence of padding bits does not imply the existence of trap
> representations: the extra bits may just be along for the ride.

So I'll replace "necessary and sufficient condition" with
"sufficient condition".

What I was thinking of is something like:

#include <string.h>
unsigned char randchar();
/* Get a random integer from 0 to UCHAR_MAX */

unsigned long longrand()
{
unsigned long result;
if (NO_TRAP(unsigned long)) {
int i;
unsigned char res[sizeof result];
for (i=0; i<sizeof result; i++)
res[i] = randchar();
memcpy(&result, res, sizeof result);
} else {
/* invent something else */
}
return result;
}

I would still be able to use the algorithm with the right result (a
uniformly distributed random integer from 0 to UINT_MAX) if there
are padding bits but they are ignored.

Army1987
Guest
Posts: n/a

 04-21-2007
"Harald van D?k" <(E-Mail Removed)> ha scritto nel messaggio
news:(E-Mail Removed) oups.com...
> Army1987 wrote:

>> Is
>>
>> ( DBL_MAX >= (uMyInt_t)(-1) || (puts("Your DS9K is about to self-\
>> destruct. Get a real computer."), exit(1)),
>> /* On the DeathStation 9000 exit(1) activates self-destruction */
>> ceil(log2((uMyInt_t)(-1))) >= CHAR_BIT*sizeof(uMyInt_t) )
>>
>> any better?

>
> On the DS9K, DBL_MAX would be large enough, but CHAR_BIT *
> sizeof(uMuInt_t) would give the wrong result because SIZE_MAX is too
> small.

On C99 I might use (uintmax_t)CHAR_BIT*sizeof(uMyInt_t)...

> integer constant expression, so at this point there's no downside to
> just writing a function.

I was thinking of using a macro, so I could write
to do that with a function.

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a

 04-21-2007
Army1987 wrote:
> "Eric Sosman" <(E-Mail Removed)> ha scritto nel messaggio
> news:(E-Mail Removed). ..
> > Army1987 wrote:
> >> If uMyInt_t is an unsigned integral type, is the following a
> >> necessary and sufficient condition that uMyInt_t has no trap
> >> representation?
> >>
> >> (uMyInt_t)(-1) >> CHAR_BIT*sizeof(uMyInt_t)-1
> >>
> >> That is, I'm asking wheter it equals 0 whenever uMyInt_t has trap
> >> representations, equals a nonzero value whenever uMyInt_t has no
> >> trap representation, and never triggers undefined behaviour.

>
> [snip] Second, the
> > presence of padding bits does not imply the existence of trap
> > representations: the extra bits may just be along for the ride.

>
> So I'll replace "necessary and sufficient condition" with
> "sufficient condition".
>
> What I was thinking of is something like:
>
> #include <string.h>
> unsigned char randchar();
> /* Get a random integer from 0 to UCHAR_MAX */
>
> unsigned long longrand()
> {
> unsigned long result;
> if (NO_TRAP(unsigned long)) {
> int i;
> unsigned char res[sizeof result];
> for (i=0; i<sizeof result; i++)
> res[i] = randchar();
> memcpy(&result, res, sizeof result);
> } else {
> /* invent something else */
> }
> return result;
> }
>
> I would still be able to use the algorithm with the right result (a
> uniformly distributed random integer from 0 to UINT_MAX) if there
> are padding bits but they are ignored.

Why not

unsigned long result = randchar();
if ((unsigned long) -1 > UCHAR_MAX)
{
size_t i;
for (i = sizeof result - 1; i != 0; i--)
result = (result << CHAR_BIT) | randchar();
}

It works regardless of any padding bits.

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a

 04-21-2007
Army1987 wrote:
> "Harald van D?k" <(E-Mail Removed)> ha scritto nel messaggio
> news:(E-Mail Removed) oups.com...
> > Army1987 wrote:

>
> >> Is
> >>
> >> ( DBL_MAX >= (uMyInt_t)(-1) || (puts("Your DS9K is about to self-\
> >> destruct. Get a real computer."), exit(1)),
> >> /* On the DeathStation 9000 exit(1) activates self-destruction */
> >> ceil(log2((uMyInt_t)(-1))) >= CHAR_BIT*sizeof(uMyInt_t) )
> >>
> >> any better?

> >
> > On the DS9K, DBL_MAX would be large enough, but CHAR_BIT *
> > sizeof(uMuInt_t) would give the wrong result because SIZE_MAX is too
> > small.

> On C99 I might use (uintmax_t)CHAR_BIT*sizeof(uMyInt_t)...

And on C90, you can use a cast to unsigned long.

> > Seriously though, your current expression is already no longer an
> > integer constant expression, so at this point there's no downside to
> > just writing a function.

>
> I was thinking of using a macro, so I could write
> to do that with a function.

You could do

#define NO_PADDING(type) (count_bits((type) -1) == sizeof(type))

where count_bits accepts an unsigned long / uintmax_t.

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?=
Guest
Posts: n/a

 04-21-2007
Harald van Dĳk wrote:
> You could do
>
> #define NO_PADDING(type) (count_bits((type) -1) == sizeof(type))

.... == sizeof(type) * CHAR_BIT