472,328 Members | 1,051 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,328 software developers and data experts.

Trap representations for unsigned integers

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]);}
Apr 21 '07 #1
17 1477
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.

Apr 21 '07 #2
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
es*****@acm-dot-org.invalid
Apr 21 '07 #3
"Harald van D?k" <tr*****@gmail.comha scritto nel messaggio
news:11**********************@b58g2000hsg.googlegr 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?
Apr 21 '07 #4
Army1987 wrote:
"Harald van D?k" <tr*****@gmail.comha scritto nel messaggio
news:11**********************@b58g2000hsg.googlegr 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. :)

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.

Apr 21 '07 #5
"Eric Sosman" <es*****@acm-dot-org.invalidha scritto nel messaggio
news:Cc******************************@comcast.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

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.
Apr 21 '07 #6
"Harald van D?k" <tr*****@gmail.comha scritto nel messaggio
news:11**********************@l77g2000hsb.googlegr 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)...

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
NO_PADDING(size_t), NO_PADDING(unsigned int), etc. There's no way
to do that with a function.
Apr 21 '07 #7
Army1987 wrote:
"Eric Sosman" <es*****@acm-dot-org.invalidha scritto nel messaggio
news:Cc******************************@comcast.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

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.

Apr 21 '07 #8
Army1987 wrote:
"Harald van D?k" <tr*****@gmail.comha scritto nel messaggio
news:11**********************@l77g2000hsb.googlegr 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
NO_PADDING(size_t), NO_PADDING(unsigned int), etc. There's no way
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.

Apr 21 '07 #9
Harald van Dijk wrote:
You could do

#define NO_PADDING(type) (count_bits((type) -1) == sizeof(type))
.... == sizeof(type) * CHAR_BIT

Apr 21 '07 #10
"Harald van D?k" <tr*****@gmail.comha scritto nel messaggio
news:11**********************@e65g2000hsc.googlegr oups.com...
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.
I hadn't thought of that before... (Mathematically x << y << z << t
is equivalent to x << (y+z+t), but I hadn't thought to the fact
that the former might be valid C even when the latter may be UB.)
Thanks.
Apr 21 '07 #11
Harald van Dijk <true...@gmail.comwrote:
unsigned char randchar();

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.
True, but it may call randchar() more times than needed
on a hypothetical implementation where there are LOTS
of padding bits.

unsigned long m = -1, result = randchar();
while ((m = m >(CHAR_BIT - 1) >1) != 0)
result = (result << CHAR_BIT) | randchar();

--
Peter

Apr 23 '07 #12

"Peter Nilsson" <ai***@acay.com.auha scritto nel messaggio
news:11**********************@e65g2000hsc.googlegr oups.com...
>Harald van D?k <true...@gmail.comwrote:
unsigned char randchar();

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.

True, but it may call randchar() more times than needed
on a hypothetical implementation where there are LOTS
of padding bits.

unsigned long m = -1, result = randchar();
while ((m = m >(CHAR_BIT - 1) >1) != 0)
result = (result << CHAR_BIT) | randchar();
Or something more readable:

#include <limits.h>
#if __STDC_VERSION__ >= 199901L
#include <stdint.h>
#else
#define uintmax_t unsigned long
#endif

int count_bits(uintmax_t n)
{
int result = 1;
while (n/=2)
result++;
return result;
}

#define PADDING(t) ( CHAR_BIT*sizeof(t) - count_bits((t)(-1)) )

unsigned long longrand()
{
size_t i;
unsigned long result = 0;
size_t bytes = sizeof result - PADDING(unsigned long)/CHAR_BIT;
for (i=0; i<bytes; i++) {
result <<= CHAR_BIT;
result |= randchar();
}
return result;
}

(Did I get this right?)

Apr 24 '07 #13
"Army1987" <pl********@for.itwrites:
[...]
#include <limits.h>
#if __STDC_VERSION__ >= 199901L
#include <stdint.h>
#else
#define uintmax_t unsigned long
#endif
Why are you using #define rather than typedef?

The test for __STDC_VERSION__ *should* work, but unfortunately in real
life it may not be reliable. The __STDC_VERSION__ macro typically
tells you whether the compiler claims to support C99; this may or may
not tell you whether the <stdint.hheader exists. You can also get a
false negative, if the compiler doesn't claim to support C99, but it
supports unsigned long long as an extension. (Most such compilers
support a mode in which they conform to C90 without supporting
C99-specific features; the trick is to make sure the compiler is
actually invoked in such a mode.)

A conditional #include would be handy here:

#if header_exists <stdint.h>
#include <stdint.h>
#else
typedef unsigned long uintmax_t
#endif

but, alas, that doesn't exist.

Configuration systems like GNU autoconf can be helpful, but the
details are off-topic.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Apr 24 '07 #14
Peter Nilsson wrote:
>
Harald van Dijk <true...@gmail.comwrote:
unsigned char randchar();
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.

True, but it may call randchar() more times than needed
on a hypothetical implementation where there are LOTS
of padding bits.

unsigned long m = -1, result = randchar();
while ((m = m >(CHAR_BIT - 1) >1) != 0)
result = (result << CHAR_BIT) | randchar();
(result << CHAR_BIT) is undefined if sizeof(result) equals one.

--
pete
Apr 28 '07 #15
"pete" <pf*****@mindspring.comha scritto nel messaggio
news:46***********@mindspring.com...
Peter Nilsson wrote:
>>
Harald van Dijk <true...@gmail.comwrote:
unsigned char randchar();

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.

True, but it may call randchar() more times than needed
on a hypothetical implementation where there are LOTS
of padding bits.

unsigned long m = -1, result = randchar();
while ((m = m >(CHAR_BIT - 1) >1) != 0)
result = (result << CHAR_BIT) | randchar();

(result << CHAR_BIT) is undefined if sizeof(result) equals one.
if sizeof result is 1, then m is UCHAR_MAX, and
m >(CHAR_BIT - 1) >1 is 0.
So the body loop is never done then.
(I still wonder why uns_var >value_bits and uns_var << value_bits
are undefined. uns_var * 2**value_bits modulo 2**value_bits is 0,
and so is floor(uns_var / 2**value_bits). That's what
uns_var >value_bits-1 >1 and uns_var << value_bits-1 << 1 do.
Maybe I'll post that to comp.std.c.)
Apr 28 '07 #16
Army1987 wrote, On 28/04/07 10:28:

<snip>
(I still wonder why uns_var >value_bits and uns_var << value_bits
are undefined. uns_var * 2**value_bits modulo 2**value_bits is 0,
and so is floor(uns_var / 2**value_bits). That's what
uns_var >value_bits-1 >1 and uns_var << value_bits-1 << 1 do.
Maybe I'll post that to comp.std.c.)
The most probable reason for it being undefined is because the way
processors will treat it if you use assembler instructions to do it varies.
--
Flash Gordon
Apr 28 '07 #17
"Army1987" <please....@for.itwrote:
"Peter Nilsson" <a...@acay.com.au:
unsigned char randchar();
unsigned long m = -1, result = randchar();
while ((m = m >(CHAR_BIT - 1) >1) != 0)
result = (result << CHAR_BIT) | randchar();

Or something more readable:
But less correct. ;-)
#include <limits.h>
<snip>
#define PADDING(t) ( CHAR_BIT*sizeof(t) - count_bits((t)(-1)))
Why are people so hung up on calculating the number of
padding bits?
unsigned long longrand()
{
size_t i;
unsigned long result = 0;
size_t bytes = sizeof result - PADDING(unsigned long)
/CHAR_BIT;
for (i=0; i<bytes; i++) {
result <<= CHAR_BIT;
result |= randchar();
}
return result;

}

(Did I get this right?)
No. If unsigned long is exactly 1 byte (ergo unpadded),
then the left shifting of result by CHAR_BIT bits invokes
undefined behaviour.

--
Peter

Apr 29 '07 #18

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

96
by: John Harrison | last post by:
I knew that unsigned integral data types were the cause of scads of mostly spurious warning messages, but I didn't realise that they were a security...
8
by: Rade | last post by:
Following a discussion on another thread here... I have tried to understand what is actually standardized in C++ regarding the representing of...
49
by: Neil Zanella | last post by:
Hello, Often I happen to be dealing with nonnegative integers and since I know I won't need negative numbers here I declare them as unsigned...
11
by: pemo | last post by:
Ambiguous? I have a student who's asked me to explain the following std text (esp. the footnote). 6.2.6.1.5 Certain object representations...
10
by: pemo | last post by:
As far as I understand it, a trap representation means something like - an uninitialised automatic variable might /implicitly/ hold a bit-pattern...
24
by: hammer1234 | last post by:
Hi I am wondering if there is a way of using the underlying bit representations of floats. I am interested in creating a violation in MISRA...
24
by: Lane Straatman | last post by:
I'm trying to think of what one-third looks like when represented by two's complement. What is its length? I'm not schur. It would be a DWORD in...
10
by: Richard Tobin | last post by:
May all-bits-zero be a trap representation for a pointer? What if I calloc() space for a structure containing pointers? -- Richard --...
11
by: vippstar | last post by:
Hello Let's assume CHAR_BIT == 8, sizeof (int) == 4 and INT_MAX == 32767 (that'd mean int has 32 bits, of which only the 15 are value bits) ...
0
by: tammygombez | last post by:
Hey fellow JavaFX developers, I'm currently working on a project that involves using a ComboBox in JavaFX, and I've run into a bit of an issue....
0
by: tammygombez | last post by:
Hey everyone! I've been researching gaming laptops lately, and I must say, they can get pretty expensive. However, I've come across some great...
0
better678
by: better678 | last post by:
Question: Discuss your understanding of the Java platform. Is the statement "Java is interpreted" correct? Answer: Java is an object-oriented...
0
by: teenabhardwaj | last post by:
How would one discover a valid source for learning news, comfort, and help for engineering designs? Covering through piles of books takes a lot of...
0
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and...
0
by: CD Tom | last post by:
This happens in runtime 2013 and 2016. When a report is run and then closed a toolbar shows up and the only way to get it to go away is to right...
0
by: Naresh1 | last post by:
What is WebLogic Admin Training? WebLogic Admin Training is a specialized program designed to equip individuals with the skills and knowledge...
0
by: antdb | last post by:
Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was...
0
by: Matthew3360 | last post by:
Hi there. I have been struggling to find out how to use a variable as my location in my header redirect function. Here is my code. ...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.