Taking a test for a job

[ena8t8si]

Tomás said:

I would approach it with this attitude: The person who wrote the exam is
an absolute idiot, and it's my duty to show just how much of an idiot he
is.

Why?

Because most programming language exams are erroneous. You might even see
a question which has code that attemps to set all of an array's elements
to zero:

int *array[50];

memset( &array, 0, sizeof( int[50] ) );


You should give a very arrogant answer such as:


The programmer errorneously overlooked the fact that not all zero values
need be represented by all bits zero in memory; in particular: a null
pointer value, 0 for a float or double. Therefore, the above code
exhibits Undefined Behaviour.

Not to mention the fact that array has type int *[50], so &array has type
(int *[50])*. ...

You mean int *(*)[50].

 

[Richard Heathfield]

(e-mail address removed) said:

Not to mention the fact that array has type int *[50], so &array has type
(int *[50])*. ...

You mean int *(*)[50].

Possibly I do, yes. Personally, I shun such types, and so I lack easy
familiarity with them. For one thing, I can't see any particular benefit to
having an array of 50 pointers to int. If it were n pointers to int, that
would be a different matter.

 

[Tomás]

After adding the missing *, I don't think there is undefined behaviour
on any system just yet.

We're either writing portable C code, or non-portable C code. If you're
writing the latter, then you're on the wrong newsgroup.

The code sets all elements to all bits zero.

For unsigned char, char, and signed char, yes. For anything else, the
result is implementation-specific... and may result in Undefined
Behaviour on some platfroms.

If it's an invalid pointer value, there's not a problem until the
pointers are actually read.

Yes, but presumably, if one is setting pointer values to null, one
intends their value to be analysed at some point in the future (because
if this weren't the case, it would be pointless to set their value). When
the point comes to check for a null pointer:

if (!p)

The code is not guaranteed to work properly on all platforms.

(Sure, the code you've shown is then a
very bad idea, but don't claim UB when there isn't.)

I posted to a newsgroup which deals with the C language itself (not any
one of its particular implementations), therefore any and all code posted
here should be fully portable. If implementation-specific behaviour may
result in Undefined Behaviour, then it doesn't belong here either. The
following code is taboo for example:

for ( int i = 1; i; ++i );

If it's a valid
null pointer, the code is unnecessarily nonportable, but correct for
that implementation.

Yet non-portable nonetheless, because the Standard explicitly indicates
that a "zero value" need not necessarily be represented by all bits zero
(for certain types).

And if all bits zero is a valid pointer value,
but not a null pointer, and that special pointer value is needed, this
may even be a good way of getting it.

Not in portable code.

In C++, I'd use a template, however, in C, a macro would probably be the
way to go:

#define ZeroArray(array) for(unsigned long i = 0;\
i != sizeof(array) / sizeof(*array);\
++i) a = 0;


(Entirely off-topic here, but if anyone's curious, here's the C++ way:


template<class T, unsigned long len>
void ZeroArray( T (&array)[len] )
{
const T * const p_last = array + (len - 1);

for ( T *p = array; ; ++p )
{
*p = T();

if ( p == p_last ) return;
}
}


-Tomás

 

[Guest]

We're either writing portable C code, or non-portable C code. If you're
writing the latter, then you're on the wrong newsgroup.

You were talking about exams. Exams aren't necessarily only about
portable C code. (Also, see below for more.)

For unsigned char, char, and signed char, yes. For anything else, the
result is implementation-specific... and may result in Undefined
Behaviour on some platfroms.

The code sets all elements to all bits zero (which may or may not be a
valid representation of any value, 0 or otherwise), regardless of its
type. If you have reason to believe otherwise, please explain.

Yes, but presumably, if one is setting pointer values to null,

The code doesn't necessarily set pointer values to null. You're
assuming that's the intent.

one
intends their value to be analysed at some point in the future (because
if this weren't the case, it would be pointless to set their value). When
the point comes to check for a null pointer:

if (!p)

The code is not guaranteed to work properly on all platforms.

Right, that's what I said. What you said is that there's UB even when
no such check is ever made.

I posted to a newsgroup which deals with the C language itself (not any
one of its particular implementations), therefore any and all code posted
here should be fully portable. If implementation-specific behaviour may
result in Undefined Behaviour, then it doesn't belong here either. The
following code is taboo for example:

for ( int i = 1; i; ++i );

This newsgroup, to the best of my knowledge, is not only for strictly
conforming C code, but, exactly what you said, for the C language (as
defined by the C standard). The standard defines the behaviour for more
than strictly conforming code: it also defines the behaviour of code on
some implementations even when it may be undefined on others. If I'm
wrong here, I'd appreciate a correction from any of the more regular
users here though.

Yet non-portable nonetheless, because the Standard explicitly indicates
that a "zero value" need not necessarily be represented by all bits zero
(for certain types).

Nit: in the normative text states that all bits zero is a valid
representation of 0 for any integer type, and that other than what the
standard guarantees, the representation of types in unspecified, but
only explicitly states all bits zero may not be a valid representation
of 0 for some types in a non-normative footnote.

And if all bits zero is a valid pointer value,
but not a null pointer, and that special pointer value is needed, this
may even be a good way of getting it.

Not in portable code.
Obviously.

In C++, I'd use a template, however, in C, a macro would probably be the
way to go:

#define ZeroArray(array) for(unsigned long i = 0;\
i != sizeof(array) / sizeof(*array);\
++i) a = 0;

I wouldn't even make it a macro. Such a simple for loop, as long as
it's formatted properly, is clear enough. I'd use a pointer instead of
an index, but that's just personal preference.

 

[Tomás]

The code doesn't necessarily set pointer values to null. You're
assuming that's the intent.

Exactly. I was demonstarting how a not-so-good-programmer may blindly
presume that the zero value for a double is all bits zero, or that a null
pointer value is all bits zero. Such a programmer may then go on to use
memset to set each element of an array to zero. (but in reality, they're
setting each element to all bits zero -- which may or may not represent
the value 0 for that given type).

Such code is non-portable.

Right, that's what I said. What you said is that there's UB even when
no such check is ever made.

I may have been over-zealous with my language, but I was implying that it
would be UB because, naturally, you only set a variable's value if you're
going to read it again. Only a brain amputee would do the following:

void SomeFunc()
{
int k = 3;

/* Thirty-five lines of code here */

/* Now the last line: */

k = 2;
}

Why set k's value if you're never going to use it?

Nit: in the normative text states that all bits zero is a valid
representation of 0 for any integer type

Nit: but only for the value representation bits. There may be an extra
bit which doesn't take part in the representation of the variable's
value. Such a bit would be used for trapping. In such cases, you can't
use memset to set it to zero. The following code is non-portable:

void SetToZero( unsigned * const p )
{
memset( p, 0, sizeof(*p) );
}

#define ZeroArray(array) for(unsigned long i = 0;\
i != sizeof(array) / sizeof(*array);\
++i) a = 0;

I wouldn't even make it a macro. Such a simple for loop, as long as
it's formatted properly, is clear enough. I'd use a pointer instead of
an index, but that's just personal preference.

I too would use a pointer... but I don't see how that would be possible
when writing the macro. How would we determine the type of the pointer
variable? I think we'd need a "typeof" operator:

#define ZeroArray(array) \
{ \
const typeof(*array) * const p_last; \
\
for( typeof(*array) *p = array; ;++p ) \
{\
*p = 0;\
if (p == p_last) break;\
}\
}


-Tomás

 

[Rod Pemberton]

We're either writing portable C code, or non-portable C code. If you're
writing the latter, then you're on the wrong newsgroup.

False. I'd say 40% or more of the standard is non-portable. Some examples:

bitshifts
unions
enums
any function that uses file i/o (fopen/fclose,fread,ftell,fprintf).
printf (uses file i/o-all xxprintf variants except sprintf)
representation of null pointers, floats, integers
setjmp,jmpto,jmpbuf
time functions
signal
system
argv,argc
choice of character set
declaration of main, other than required two
whitespace or not in preprocessor directives

etc...
etc...


Rod Pemberton

 

[Guest]

I may have been over-zealous with my language, but I was implying that it
would be UB because, naturally, you only set a variable's value if you're
going to read it again. Only a brain amputee would do the following:

void SomeFunc()
{
int k = 3;

/* Thirty-five lines of code here */

/* Now the last line: */

k = 2;
}

Why set k's value if you're never going to use it?

Possibly to verify the pointers are not used until they are set
properly, when debugging is done on a system which aborts when an all
bits zero pointer value is used. Not applicable to your SomeFunc
example, and not applicable to most systems, just a random thought. In
most cases, you're right, there's no reason.

Nit: but only for the value representation bits. There may be an extra
bit which doesn't take part in the representation of the variable's
value. Such a bit would be used for trapping. In such cases, you can't
use memset to set it to zero. The following code is non-portable:

void SetToZero( unsigned * const p )
{
memset( p, 0, sizeof(*p) );
}

6.2.6.2#5:

The values of any padding bits are unspeciï¬ed.45) A valid (non-trap)
object representation of a signed integer type where the sign bit is
zero is a valid object representation of the corresponding unsigned
type, and shall represent the same value. *For any integer type, the
object representation where all the bits are zero shall be a
representation of the value zero in that type.*

(This was changed with C99 TC2.)

#define ZeroArray(array) for(unsigned long i = 0;\
i != sizeof(array) / sizeof(*array);\
++i) a = 0;

I wouldn't even make it a macro. Such a simple for loop, as long as
it's formatted properly, is clear enough. I'd use a pointer instead of
an index, but that's just personal preference.

I too would use a pointer... but I don't see how that would be possible
when writing the macro. How would we determine the type of the pointer
variable? I think we'd need a "typeof" operator:

Again, I wouldn't even use a macro, but when you do, good point.

 

[Tomás]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

*For any integer type, the
object representation where all the bits are zero shall be a
representation of the value zero in that type.*

(I wasn't aware of this... I'll go check if it's the same for C++ aswell).

So... with regard to integer types, if the value representation bits are
all zero, then the trapping bits must be all zero too.

So that implies that the following functions all work as expected:

void SetToZero( char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsinged char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( int const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( signed char const * p ) { memset(p, 0, sizeof(*p)); }

However, the following may not work as expected, because of the possibility
of "trapping bits":

void SetToMaxValue( unsigned long * const p )
{
memset( p, UCHAR_MAX, sizeof(*p) );
}


-Tomás

 

[Guest]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:


(I wasn't aware of this... I'll go check if it's the same for C++ aswell).

So... with regard to integer types, if the value representation bits are
all zero, then the trapping bits must be all zero too.

Not necessarily. All bits zero must be a valid representation of 0, but
it need not be the only one (unless there's something I'm missing, of
course).

So that implies that the following functions all work as expected:

void SetToZero( char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsinged char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( int const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( signed char const * p ) { memset(p, 0, sizeof(*p)); }

Assuming you switch the * and const, then yes.

However, the following may not work as expected, because of the possibility
of "trapping bits":

void SetToMaxValue( unsigned long * const p )
{
memset( p, UCHAR_MAX, sizeof(*p) );
}

Indeed. There is only a guarantee for all bits zero, not any other bit
pattern.

 

[Ben Pfaff]

So that implies that the following functions all work as expected:

void SetToZero( char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsinged char const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( int const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( unsigned long const * p ) { memset(p, 0, sizeof(*p)); }
void SetToZero( signed char const * p ) { memset(p, 0, sizeof(*p)); }

However, the following may not work as expected, because of the possibility
of "trapping bits":

void SetToMaxValue( unsigned long * const p )
{
memset( p, UCHAR_MAX, sizeof(*p) );
}

Yes and yes.

But why are the parameter types in the former cases "pointer to
const T"? And why does it change to "const pointer to T" in the
latter case? Are these just typos or are you trying to make a
point?

 

[Tomás]

=?utf-8?B?SGFyYWxkIHZhbiBExLNr?= posted:

Not necessarily. All bits zero must be a valid representation of 0,
but it need not be the only one (unless there's something I'm missing,
of course).

It's funny... just when you think you've thought of everything, someone
points out something that you've overlooked! Let's take an example:
An integer type which has 20 bits overall, but only 16 of them are
value representation bits. The Standard guarantees that the following
object bit-pattern MUST represent the number zero:

0000 0000 0000 0000 0000

Although there may be another way of representing the number zero for a
given integer type, we're still guaranteed that the bit-pattern displayed
above is perfectly legitimate for zero.

Assuming you switch the * and const, then yes.

A typographical error, I can assure you!

Indeed. There is only a guarantee for all bits zero, not any other bit
pattern.

While we're on the topic, I just want to make sure of something.

If we have a positive integer value which can be represented accurately
in both the signed and unsigned form of an integer type, then must they
have the same object bit-pattern? (Or maybe just the same value
representation bit-pattern?). What I mean is, is the following code okay:

unsigned ConvertToUnsigned( int const val )
{
if ( val >= 0 ) /* Make sure it's positive */
{
const unsigned * const p = (const unsigned*)&val;

return *p;
}

...
}

int ConvertToSigned( unsigned const val )
{
unsigned const max_positive_signed_val = INT_MAX;

if ( val <= max_positive_signed_val ) /* Make sure within range */
{
const int * const p = (const int*)&val;

return *p;
}

...
}

The code above acts on the assumption that a given number will be stored
identically in a signed and unsigned type (assuming the actual number is
within range of both types).

Does the Standard also guarantee that one of three systems must be used
for storing negative numbers:

Sign-magnitude
One's complement
Two's complement

Or does it leave the door wide open?

-Tomás

 

[Tomás]

Ben Pfaff posted:

But why are the parameter types in the former cases "pointer to
const T"? And why does it change to "const pointer to T" in the
latter case? Are these just typos or are you trying to make a
point?

Typo's I can assure you! I wrote one line with haste, then copy-pasted it
several times.


-Tomás

 

[Guest]

If we have a positive integer value which can be represented accurately
in both the signed and unsigned form of an integer type, then must they
have the same object bit-pattern? (Or maybe just the same value
representation bit-pattern?).

The representation for (nonnegative) signed values must be valid for
unsigned as well, but a quick search doesn't give me a guarantee for
the reverse.

What I mean is, is the following code okay:

[...]

The code above acts on the assumption that a given number will be stored
identically in a signed and unsigned type (assuming the actual number is
within range of both types).

6.2.6.2#5 again:
"The values of any padding bits are unspeciï¬ed.45) A valid (non-trap)
object representation
of a signed integer type where the sign bit is zero is a valid object
representation of the
corresponding unsigned type, and shall represent the same value. For
any integer type,
the object representation where all the bits are zero shall be a
representation of the value
zero in that type."

The way I see it, this says that using 20-bit ints, with the padding
bits shown as the leftmost four:

#include <string.h>
int main(void) {
signed a = 0; /* can store 0001 0000 0000 0000 0000 */
unsigned b = 0; /* can store 1111 0000 0000 0000 0000 */
if(0) {
memcpy(&a, &b, sizeof(int));
return a; /* no guarantee that 1111 0000 0000 0000 0000 is a
valid bit pattern for signed int */
} else {
memcpy(&b, &a, sizeof(int));
return b; /* guaranteed that 0001 0000 0000 0000 0000 must be a
valid bit pattern representing 0 for unsigned int */
}
}

I do hope I'm reading this incorrectly though, or that the guarantee
does exist elsewhere.

Does the Standard also guarantee that one of three systems must be used
for storing negative numbers:

Sign-magnitude
One's complement
Two's complement

Or does it leave the door wide open?

It must be one of those three (6.2.6.2#2).

 

[pete]

Tomás wrote:

It must be one of those three (6.2.6.2#2).

In C99, it must be one of those three.
In C89, the door is open for any system with a sign bit.

 

[Keith Thompson]

As always, Keith stating the obvious and known in an ignorant and useless
manner. If I wanted a response to my question from the generic AI populace,
I would've asked there. But, I didn't. I wanted a response from someone
who was extremely interested in AI (i.e., PHD) and upto date (i.e., new
PHD). In other words, the individual who posted here.

So use e-mail.

Don't bother replying; I'm done with this thread.

 

[Malcolm]

False. I'd say 40% or more of the standard is non-portable. Some
examples:

bitshifts
unions
enums
any function that uses file i/o (fopen/fclose,fread,ftell,fprintf).
printf (uses file i/o-all xxprintf variants except sprintf)
representation of null pointers, floats, integers
setjmp,jmpto,jmpbuf
time functions
signal
system
argv,argc
choice of character set
declaration of main, other than required two
whitespace or not in preprocessor directives

Two issues here.
Some of these things don't appear on non-hosted implementations, or, sadly,
on some popular platforms like MS Windows, where I have never been able to
catch stderr from a Windowing mode program.

The other issue is that it is quite easy to use C's ability to give you
direct access to the computer's memory in a non-portable way. For instance
unions can be abused to provide a breakup of 32 bit integers into two 16 bit
integers, which is fine until the endianness of the platform changes.

 

[spibou]

Sorry if this is off-topic but can someone explain to me what a
"trapping bit" is ?

Cheers
Spiros Bousbouras

 

[Tomás]

posted:

Sorry if this is off-topic but can someone explain to me what a
"trapping bit" is ?

Cheers
Spiros Bousbouras

Take an unsigned 16-Bit integer:

0000 0000 0000 0000


Each bit has one of two possible values, one or zero. We have 16 of them.
The amount of unique combinations is: 65 536 (that's 2 to the power of
16).

If we use this unsigned 16-Bit integer to store a number, we can store
numbers in the following range:

0 to 65 535 inclusive.


However, it's possible to have a 18-Bit unsigned integer, except that
only 16 of the bits are used for value representation. The other two bits
are used for "trapping".

Trapping is where the system tests for an invalid value.

Here's our sample 18-Bit unsigned integer which has only 16-Bit value
representation bits:

00 0000 0000 0000 0000


The particular platform we're working on may decide that the trapping
bits must be 11 in order for the number to be valid. So when you do the
following:

unsigned k = 5;

Then it looks like so in memory:

11 0000 0000 0000 0101


Why have trapping bits? Because you can detect when a variable contains
garbage, as in the following:

int main(void) { unsigned k; }

"k" was never initialised, so all of its 18 bits can have any value.
Using trapping bits however, the system can detect whether it contains
garbage or a legitimate value.

It's usually only any use for debugging... and would only really work
properly if all relevent memory was set to zero before hand, because
there's a 1 in 4 chance that the trapping bits will be okay even when the
variable was never initialised.

The following is undefined behaviour because of the possibility of
trapping bits:

unsigned a;

unsigned b = a;


Thankfully though, we're guaranteed that "unsigned char" has no trapping
bits. Therefore, the following is okay:

unsigned char a;

unsigned char b = a;


And we can also safely access any sequence of memory as if it were an
array of unsigned chars. For example:

double array[45];

unsigned char *p = (unsigned char*)(array + 6);

unsigned char c = *p; /* No problem */


However, the following may cause Undefined Behaviour because of the
possibility of trapping bits:

double array[45];

unsigned int *p = (unsigned int*)(array + 6);

unsigned int k = *p; /* Bad idea! */


-Tomás

 

[osmium]

I would approach it with this attitude: The person who wrote the exam is
an absolute idiot, and it's my duty to show just how much of an idiot he
is.

You want fries with that?

 

[Keith Thompson]

Sorry if this is off-topic but can someone explain to me what a
"trapping bit" is ?

It may or may not be off-topic for the newsgroup. It certainly seems
to be off-topic for the thread; as far as I can tell, nobody has
mentioned "trapping bits". If you want to ask a new question, please
start a new thread rather than posting a followup on an existing one.

C does not define anything called a "trapping bit".

A "padding bit" is a bit in the representation of an integer type that
doesn't contribute to the value. For an unsigned integer type, the
bits are divided into value bits and (zero or more) padding bits; a
signed integer type as, in addition to that, a single sign bit. Most
implementations don't have paddig bits, but the standard allows them.

(This is distinct from the padding that's allowed between structure
members, or after the last member of a structure.)

Padding bits are defined only for integer types; for other types (such
as pointer and floating-point types), the standard doesn't specify
enough about their representation to make the concept necessary.
There may well be bits within, for example, a floating-point
representation that don't contribute to its value, but the standard
doesn't care about this.

A "trap representation" is a representation (bit pattern) for a given
type that doesn't represent a value of the type. Accessing a trap
representation invokes undefined behavior. For an integer type, a
trap representation might be determined by a particular set of values
for the padding bits. On the other hand, a type might have padding
bits but no trap representations; the values of any padding bits might
just be quietly ignored.