some tricky questions

[Mark McIntyre]

Here is the definition of "pure binary representation" provided by the
Standard as a footnote in 6.2.6.1:

While i don't dispute the text, I should point out that footnotes are
not normative.

Then I suspect you would be able to provide at least one such
implementation?
x86.

How do shifts work on that implementation?

Same as anywhere else. The standard requires them to do what you
expect, but this need not map onto the actual order of bits in memory.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Robert Gamble]

While i don't dispute the text, I should point out that footnotes are
not normative.


x86.

Are you referring to BCD? If so, such a representation is not
compatible with the Standard, if not you should be more specific.

Same as anywhere else. The standard requires them to do what you
expect, but this need not map onto the actual order of bits in memory.

Well obviously the implementation can store the information however it
pleases as long as it appears "as-if" it conformed to the Standard and
a s.c. program must not be able to tell the difference. In the
example presented by Army1987 the assumption was that the program was
able to tell the difference.

Robert Gamble

 

[Mark McIntyre]

Are you referring to BCD? If so, such a representation is not
compatible with the Standard, if not you should be more specific.

I was thinking of endianness. If you copy a long into an array of
unsigned chars, the bits are not in the 'right' order.

Well obviously the implementation can store the information however it
pleases as long as it appears "as-if"

Agreed. This was kinda the point.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Keith Thompson]

On Mon, 04 Jun 2007 02:42:39 -0000, in comp.lang.c , Robert Gamble


Same as anywhere else. The standard requires them to do what you
expect, but this need not map onto the actual order of bits in memory.

I'm not convinced that the "actual order of bits in memory" is even
meaningful. On systems that don't address bits directly, there may be
no such concept, except perhaps one defined by convention for
documentation purposes.

 

[Eric Sosman]

Keith Thompson wrote On 06/04/07 16:03,:

]

How do shifts work on that implementation?

Same as anywhere else. The standard requires them to do what you
expect, but this need not map onto the actual order of bits in memory.

I'm not convinced that the "actual order of bits in memory" is even
meaningful. On systems that don't address bits directly, there may be
no such concept, except perhaps one defined by convention for
documentation purposes.

Agreed. Here's a thought experiment I've suggested
before; perhaps it's a good time to drag it out again.

In the pursuit of ever greater density and ever lower
power consumption, somebody builds a base-four computer
using four-state instead of two-state devices. Integers
on this machine are represented in quartal instead of in
binary, with four-quit bytes, eight-quit shorts, and so on.

However, the manufacturer decided that introducing the
world's first quartal computer would scare off too many
buyers; they'd shake their heads and say "It's too weird
for me" and buy the binary competition. So even though the
machine uses four-state devices the documentation is careful
to conceal this fact: it says (with its fingers crossed)
that the machine operates in binary and (with a straight
face) describes the order of individual bits within various
integer sizes. Since the 1's bit and the 2's bit are in
fact just different aspects of the value of one single quit
this description is largely fantasy, but it's not the first
time a computer manufacturer has lied to you, is it?

Surprisingly enough, I happen to know (by means I am not
at liberty to divulge) that the machine you are using right
at this very moment is a quartal wonder masquerading as a
plain vanilla binary machine. Ask the manufacturer and you'll
get a flat-out denial, but I Happen To Know. On your machine,
the 1's bit and the 2's bit are not neighbors, neither is to
the left or right of the other -- they are in the exact same
place.

With this long-winded setup out of the way, here comes
the experiment itself: Can you devise a C program to test
whether I'm right or wrong about the nature of your machine?
If you cannot, I submit that if C cannot even tell whether
individual bits exist as separable entities, it cannot begin
to tell how these un-isolatable entities are arranged.

 

[Old Wolf]

It is 'e' - 'a', which nothing requires to be four. It could be
anything from CHAR_MIN - CHAR_MAX to -1 included, and it could be
anything from 1 to CHAR_MAX - CHAR_MIN included.

Why do you pick those particular ranges?
Suppose CHAR_MIN is -128, 'e' is -100 and 'a' is 50.
(Then the behaviour is undefined).

Not all the world uses ASCII.

Do you know of any character set that has ever been
used in a conforming implementation where 'e' - 'a'
was not 4?

 

[Walter Roberson]

Do you know of any character set that has ever been
used in a conforming implementation where 'e' - 'a'
was not 4?

Never seen one myself, but I seem to recall reading of some
systems that used a Gray Code alphabet -- but I don't have any
clue as to whether a conforming implementation was every built
for those (possibly mythical) machines.

 

[Dave Vandervies]

Keith Thompson wrote On 06/04/07 16:03,:

Agreed. Here's a thought experiment I've suggested
before; perhaps it's a good time to drag it out again.

In the pursuit of ever greater density and ever lower
power consumption, somebody builds a base-four computer
using four-state instead of two-state devices. Integers
on this machine are represented in quartal instead of in
binary, with four-quit bytes, eight-quit shorts, and so on.

However, the manufacturer decided that introducing the
world's first quartal computer would scare off too many
buyers; they'd shake their heads and say "It's too weird
for me" and buy the binary competition. So even though the
machine uses four-state devices the documentation is careful
to conceal this fact: it says (with its fingers crossed)
that the machine operates in binary and (with a straight
face) describes the order of individual bits within various
integer sizes. Since the 1's bit and the 2's bit are in
fact just different aspects of the value of one single quit
this description is largely fantasy, but it's not the first
time a computer manufacturer has lied to you, is it?

Surprisingly enough, I happen to know (by means I am not
at liberty to divulge) that the machine you are using right
at this very moment is a quartal wonder masquerading as a
plain vanilla binary machine. Ask the manufacturer and you'll
get a flat-out denial, but I Happen To Know. On your machine,
the 1's bit and the 2's bit are not neighbors, neither is to
the left or right of the other -- they are in the exact same
place.

With this long-winded setup out of the way, here comes
the experiment itself: Can you devise a C program to test
whether I'm right or wrong about the nature of your machine?
If you cannot, I submit that if C cannot even tell whether
individual bits exist as separable entities, it cannot begin
to tell how these un-isolatable entities are arranged.

Run this program, and while it's running expose the system to a convenient
source of cosmic rays.
Wait for the cosmic rays to introduce memory errors, observe the pattern
of the errors, and look for pairs of bits whose errors are correlated.
If the cosmic ray affects the state of a quit, two bits will be affected,
and you would expect to see both of those flip often enough to notice
a pattern.

--------
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int main(void)
{
unsigned seed=(unsigned)time(0);
int *big_array=malloc(128 * sizeof *big_array);
size_t big_arr_size=128;
size_t i,j;
void *t;

if(!big_array)
{
puts("Can't allocate memory, giving up");
return EXIT_FAILURE;
}

while(t=realloc(big_array,size*2*sizeof *big_array)
{
size*=2;
big_array=t;
}

srand(seed);
for(i=0;i<size;i++)
{
big_array=rand();
}

while(1)
{
srand(seed);
for(i=0;i<size;i++)
{
int expected=rand();
if(big_array!=expected)
{
printf("%lu: Expected %d, got %d\n",i,expected,big_array);
printf("Bytes:\nExpected: ");
for(j=0;j<sizeof expected;j++)
printf(" %x",(unsigned)(((unsigned char *)&expected)[j]));
printf("\nGot: ");
for(j=0;j<sizeof big_array;j++)
printf(" %x",(unsigned)(((unsigned char *)&(big_array))[j]));
puts("");
big_array=expected;
}
}
}
/*not reached*/
}
--------

(I should add, for those who haven't realized it by this point, that I'm
not entirely serious here; this makes the assumption that the execution
environment WILL FAIL to conform to the C standard and attempts to
gain information from that failure, and will be broken by hardware or
software that attempts to detect and correct for, or reliably trap on,
these failures.)


dave

--
Dave Vandervies (e-mail address removed)

I sense some Perl coming on. --Mike Andrews and Steve VanDevender

Be sure to [...] have someone nearby if a particularly in the scary
severe attack requires restraint or sedation. devil monastery

 

[Chris Torek]

Why do you pick those particular ranges?
Suppose CHAR_MIN is -128, 'e' is -100 and 'a' is 50. ...

This is not allowed. CHAR_MIN can be negative but 'e' must be
positive, as must all the characters that are part of the "C
alphabet". (More specifically, any "member of the required source
character set" must be result in a positive value when stored in
a plain "char". Some reasonable assumptions like INT_MAX >= CHAR_MAX
then give you "all character constants for required-source-set
characters are positive". Note that while '\0' is a character
constant, the NUL it makes it is not a member of the "required
source set".)

Given that 'e' and 'a' are both positive, and hence both in
[1..CHAR_MAX], it seems that the subtraction must produce a value
between CHAR_MAX - 1 (at the high end, where 'e' is CHAR_MAX and
'a' is 1) and 1 - CHAR_MAX (at the low end, where 'e' is 1 and 'a'
is CHAR_MAX). Of course the latter would be negative.

Do you know of any character set that has ever been
used in a conforming implementation where 'e' - 'a'
was not 4?

(I do not, myself. But I only know about ASCII, EBCDIC, Fieldata,
and Unicode. Fieldata cannot be used for C as it lacks too many
required symbols. Interestingly, on 8-bit EBCDIC machines, plain
"char" is necessarily unsigned, since '9' is 0xf9.)

 

[David Thompson]

Thankfully you are wrong about this, see 9899:1999 section 6.2.6.2.

Unless the actual standard differs from n1124.pdf, it says:
If there are N value bits, each bit shall represent a different
power of 2 between 1 and 2^(N?1), [...]
Nowhere does it says anything about how are these ordered.

Concur. Except the '?' should be minus (looks like en-dash,
but my AcroRd 5 pasting to my notepad gives hyphen).

Maybe on the DS9K this is decided randomly at program startup.

But that would violate that requirement that writing out data to a
binary file and reading it back in by at least the same program must
work. Unless some very magic swizzling is done, or unless binary I/O
just always fails -- which is conforming, but not in the spirit of the
DS9k which is NOT to fail in the sorts of ways programs usually cope
with but to 'work' in the most unhelpful or useless possible way.

I think it could be decided randomly when a program is _built_, in
particular no later than link time or equivalent -- i.e. the end of
t.p.8. Or if not that, derived as a nonrandom but counterintuitive
function -- such as MD5-trunc -- of all the (preprocessed) t.u.s.

- formerly david.thompson1 || achar(64) || worldnet.att.net

 

[Richard Bos]

Unless the actual standard differs from n1124.pdf, it says:
If there are N value bits, each bit shall represent a different
power of 2 between 1 and 2^(N?1), [...]
Nowhere does it says anything about how are these ordered.

Concur. Except the '?' should be minus (looks like en-dash,
but my AcroRd 5 pasting to my notepad gives hyphen).

Maybe on the DS9K this is decided randomly at program startup.

But that would violate that requirement that writing out data to a
binary file and reading it back in by at least the same program must
work.

I cannot find that requirement. The only thing I can see that is
somewhere in that area is the requirement, in 7.19.3#5, that "The file
may be subsequently reopened, by the same or another program execution,
and its contents reclaimed or modified". It doesn't state that this
contents must be the same as before; and given that a file can be
altered, possibly even while it is being written[1], or indeed a whole
new file written under the same name, I don't think this requirement can
be made.

Richard

[1] by two programs simultaneously; I don't think that this is forbidden

by the Standard, although of course most OSes do forbid it.

 

[Army1987]

Unless the actual standard differs from n1124.pdf, it says:
If there are N value bits, each bit shall represent a different
power of 2 between 1 and 2^(N?1), [...]
Nowhere does it says anything about how are these ordered.

Concur. Except the '?' should be minus (looks like en-dash,
but my AcroRd 5 pasting to my notepad gives hyphen).

Maybe on the DS9K this is decided randomly at program startup.

But that would violate that requirement that writing out data to a
binary file and reading it back in by at least the same program must
work.

I cannot find that requirement. The only thing I can see that is
somewhere in that area is the requirement, in 7.19.3#5, that "The file
may be subsequently reopened, by the same or another program execution,
and its contents reclaimed or modified". It doesn't state that this
contents must be the same as before; and given that a file can be
altered, possibly even while it is being written[1], or indeed a whole
new file written under the same name, I don't think this requirement can
be made.

7.19.2:
A binary stream is an ordered sequence of characters that can transparently record
internal data. Data read in from a binary stream shall compare equal to the data that were
earlier written out to that stream, under the same implementation. Such a stream may,
however, hav e an implementation-defined number of null characters appended to the end
of the stream.
"Under the same implementation"... not even "under the same
program"... But still, we know that the representation of a null
pointer changes from a compile to another
(http://dialspace.dial.pipex.com/prod/dialspace/town/green/gfd34/art/bloopers.html)
so it must be more magic than we can imagine...