C is impractical on one's-complement machines
Norman Diamond
varying degrees, to write C code that "obeys" the standard (coming as
close to strictly conforming as might be practical) and produces identical
results on one's-complement machines as on two's-complement machines.
Perhaps our efforts have been wasted. Perhaps those who only concern
themselves with two's-complement machines have been correct.
It is surely possible to implement C on a one's-complement machine,
just as it is possible to implement C on a decimal or other strange
machine, by emulating the C machine model. However, this technique is
so inefficient that it is not really practical. I will guess that C
will never be genuinely implemented on a one's-complement machine.
Consider the following strictly conforming program. It always outputs
"No problem found." (Though of course it might output something else
when run on something other than a conforming implementation.)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
main() {
int i;
unsigned u;
signed char *scp;
size_t b;
union { int j; signed char sca[sizeof(int)]; } U;
u = 0;
scp = (void *) &i;
for (b = 0; b < sizeof(int); b++) *scp++ = -1;
if (memcmp((void *) &i, (void *) &u, sizeof(int)) != 0) {
if (i != u) {
/* This path will execute on two's-complement implementations. */
printf("No problem found.\n");
exit(EXIT_SUCCESS);
} else {
printf("Equal values have different representations.\n");
printf("Implementation violates ANSI 3.1.2.5 page 24 line 5.\n");
exit(EXIT_FAILURE);
}
}
/* memcmp indicated equality! Did the implementation hack *scp++ = -1
* to zero out the target int in the above code? Let's see if it can
* distinguish whether scp points to a signed char or into an int in
* the exact same location....
*/
scp = (signed char *) &U; /* points to U.sca */
for (b = 0; b < sizeof(int); b++) *scp++ = -1;
if (memcmp((void *) (signed char *) &U, (void *) &u, sizeof(int)) == 0) {
printf("A signed char didn't retain the value -1.\n");
printf("Implementation violates ANSI 2.2.4.2 page 14 lines 38-39.\n");
exit(EXIT_FAILURE);
}
scp = (void *) (int *) &U; /* points to U.j */
for (b = 0; b < sizeof(int); b++) *scp++ = -1;
if (memcmp((void *) (int *) &U, (void *) &u, sizeof(int)) != 0) {
if (U.j != u) {
if (memcmp((void *) (int *) &U, (void *) &i, sizeof(int)) != 0) {
if (U.j != i) {
printf("OK, the implementation hacked *scp++ = -1\n");
printf("to give different results for two int targets.\n");
printf("But we could do it to enough targets and they\n");
printf("would eventually run out of different results.\n");
exit(EXIT_FAILURE);
} else {
printf("Two equal ints have different representations.\n");
printf("Still violates ANSI 3.1.2.5 page 24 line 5.\n");
exit(EXIT_FAILURE);
}
} else {
printf("memcmp results of ==, !=, and == are inconsistent.\n");
exit(EXIT_FAILURE);
}
} else {
printf("Equal values have different representations.\n");
printf("Implementation violates ANSI 3.1.2.5 page 24 line 5.\n");
exit(EXIT_FAILURE);
}
}
/* Well, the implementation hacked *scp++ = -1 to zero out ints but not
* zero out signed chars at the same target locations. Congratulations.
* Though our strictly conforming program cannot output that fact.
*/
printf("No problem found.\n");
exit(EXIT_SUCCESS);
}
--
<< If this were the company's opinion, I would not be allowed to post it. >>
A program in conformance will not tend to stay in conformance, because even if
it doesn't change, the standard will. Force = program size * destruction.
Every technical corrigendum is met by an equally troublesome new defect report.
Peter Holzer
>A fair amount of effort has been taken by some disciplined people, to
>varying degrees, to write C code that "obeys" the standard (coming as
>close to strictly conforming as might be practical) and produces identical
>results on one's-complement machines as on two's-complement machines.
>Perhaps our efforts have been wasted. Perhaps those who only concern
>themselves with two's-complement machines have been correct.
>Consider the following strictly conforming program. It always outputs
>"No problem found." (Though of course it might output something else
>when run on something other than a conforming implementation.)
Assume CHAR_BITS == 8, sizeof (int) == 2.
>#include <stdio.h>
>#include <string.h>
>#include <stdlib.h>
>main() {
> int i;
> unsigned u;
> signed char *scp;
> size_t b;
> union { int j; signed char sca[sizeof(int)]; } U;
> u = 0;
u will be filled with zeroes here.
> scp = (void *) &i;
> for (b = 0; b < sizeof(int); b++) *scp++ = -1;
(signed char) -1 == (signed char) 0xFE on a one's complement machine,
so i will have the bit pattern 0xFEFE which is -0x101.
> if (memcmp((void *) &i, (void *) &u, sizeof(int)) != 0) {
The bit patterns are not identical, so we enter this branch.
> if (i != u) {
-257 is not equal to zero, so will will enter here as well.
> /* This path will execute on two's-complement implementations. */
> printf("No problem found.\n");
> exit(EXIT_SUCCESS);
Everything ok.
Of course you could change scp to be an unsigned char *, which would
give you the right bit pattern for -0. But suppose the implementation
does never produce -0 from normal operations. Does a variable
containing the bit pattern for -0 have to compare equal to zero in that
case? If not, both memcmp and i!= u will return non-zero, and the
program will still find no problem. There will be problems, however, if
-0 does have yield all 1-bits and still has to compare equal to 0.
Having never seen a one's complement machine I don't know how easy or
hard this is to avoid.
hp
--
| _ | Peter J. Holzer | Think of it |
| |_|_) | Technical University Vienna | as evolution |
| | | | Computer Science/Real-Time Systems | in action! |
| __/ | h...@vmars.tuwien.ac.at | Tony Rand |
John F Carr
sight of the real point. For any compiler, it is possible to write a
strictly conforming program that the compiler can not handle. Brute
force is the portable way to do this: write a program that is too big.
Even compilers without fixed size tables will run out of memory or disk
space.
If you don't believe the standard requires infinite compiler capacity I
can modify my compiler to reject all non-trivial programs on the grounds
that they exceed a limit and reject your compiler breaker program on that
basis. Example: the standard says a compiler must accept one program
with a switch with 257 cases. That doesn't mean that the compiler can't
reject all other programs with switch statements with multiple cases.
So I don't care much for weird programs designed only for standards
testing. Breaking compilers is only interesting when it exposes bugs
that might affect real programs.
If I'm maintaining a compiler and I get one bug report about excessive
precision loss in floating point calculations (legal) and another about
storing chars and reading a bad int from the same location (claimed to be
illegal), I'm going to look at the former.
--
John Carr (j...@athena.mit.edu)
Peter Montgomery
>
>Of course you could change scp to be an unsigned char *, which would
>give you the right bit pattern for -0. But suppose the implementation
>does never produce -0 from normal operations. Does a variable
>containing the bit pattern for -0 have to compare equal to zero in that
>case? If not, both memcmp and i!= u will return non-zero, and the
>program will still find no problem. There will be problems, however, if
>-0 does have yield all 1-bits and still has to compare equal to 0.
>Having never seen a one's complement machine I don't know how easy or
>hard this is to avoid.
I used the CDC 6400/7600 from 1972-1982. We used primarily
Fortran, and the Fortran compiler (FTN) treated +0 and -0 as equals
(except on a few points like the ISIGN intrinsic function and on output).
The Fortran compiler occasionally had to insert extra code
to check for -0 operands, such as testing the sign of I - J + 0
when testing whether I .GE. J (the difference I - J will be -0
precisely when I is -0 and J is +0, but the extra add of 0
ensures the final sum will not be -0).
Some used Wirth's Pascal compiler. This worked as Holzer
suggests, ensuring a -0 result is never produced. This required
adding 0 to a result for constructs like (in C notation)
double d;
int i, j;
i/4 (after using arithmetic right shift for the divide)
i*j (in case i = 0 and j < 0, for example)
(int)d (in case 0.0 > d > -1.0)
but not after i + j and i - j if i and j are known (by induction)
not to be -0. It is often possible to avoid the add of 0;
for example, if the expression is used only as a subscript
or in a comparison for equality.
Fortran lacked an unsigned type. When doing
bit operations on data, I sometimes wanted to distinguish
-0 (all bits set) from +0 (no bits set). I did this by testing
whether XOR(I, 1) .EQ. 1, where XOR is exclusive OR.
--
Peter L. Montgomery Internet: pmon...@math.orst.edu
Dept. of Mathematics, Oregon State Univ, Corvallis, OR 97331-4605 USA
My visiting professorship has ended. Interested in program optimization,
compilers, computer arithmetic, number theory. 17 yrs industrial experience.
Norman Diamond
In article <22ha5h$a...@email.tuwien.ac.at> h...@vmars.tuwien.ac.at (Peter Holzer) writes:
>dia...@jit.dec.com (Norman Diamond) writes:
>>[...]
>> signed char *scp;
>>[...]
>> for (b = 0; b < sizeof(int); b++) *scp++ = -1;
>(signed char) -1 == (signed char) 0xFE on a one's complement machine,
>so i will have the bit pattern 0xFEFE which is -0x101.
>[...]
>Of course you could change scp to be an unsigned char *, which would
>give you the right bit pattern for -0.
Argh! Yes, and your fix is correct; thank you.
>But suppose the implementation does never produce -0 from normal operations.
>Does a variable containing the bit pattern for -0 have to compare equal to
>zero in that case?
You mean that the hardware would do one's-complement arithmetic but the
hardware would always avoid generating a -0 and then the hardware's compare
instructions would make -0 compare unequal to +0? Interesting. So first,
let's check i+0 != u instead of the surprising i != u and still prove
that the implementation is non-conforming. Second, we can watch for the
answers to some relevant Defect Reports :-)
---------
pmon...@math.orst.edu (Peter Montgomery) mentioned that particular Fortran
and Pascal implementations on a particular one's-complement machine generated
extra code to change -0 to +0 after arithmetic operations. Yes, Fortran and
Pascal are only moderately inefficient in that respect. C would be a real
dog on such a machine, which was the point of my post.
---------
j...@athena.mit.edu (John F Carr) says that he would not try very hard to make
a C implementation conform on a one's-complement machine. I'm not sure what
his real message was. My posting suggested that perhaps we should abandon the
idea of conforming C implementations on one's-complement machines. Mr. Carr
said that he also would abandon the idea, but only in response to bug reports?
Christopher R. Volpe
|> In article <22ha5h$a...@email.tuwien.ac.at> h...@vmars.tuwien.ac.at
|> (Peter Holzer) writes:
|> >
|> >Of course you could change scp to be an unsigned char *, which would
|> >give you the right bit pattern for -0. But suppose the implementation
|> >does never produce -0 from normal operations. Does a variable
|> >containing the bit pattern for -0 have to compare equal to zero in that
I would imagine that whatever bit pattern you stick in, it had better
compare equal to SOMETHING between INT_MIN and INT_MAX, no? Or CHAR_MIN
and CHAR_MAX for signed chars, no? How about one big switch statement
enumerating all the possible values, without a default value? Such a
program, that prints out the same thing for each case, would be strictly
conforming, and would force "-0" to compare equal to something. If it
compares equal to anything non-zero, it violates the basic rules of
arithmetic, therefore it must compare equal to zero.
|> >case? If not, both memcmp and i!= u will return non-zero, and the
|> >program will still find no problem. There will be problems, however, if
|> >-0 does have yield all 1-bits and still has to compare equal to 0.
|> >Having never seen a one's complement machine I don't know how easy or
|> >hard this is to avoid.
|>
--
==================
Chris Volpe
G.E. Corporate R&D
vol...@crd.ge.com
Larry Jones
> It is surely possible to implement C on a one's-complement machine,
> just as it is possible to implement C on a decimal or other strange
> machine, by emulating the C machine model. However, this technique is
> so inefficient that it is not really practical. I will guess that C
> will never be genuinely implemented on a one's-complement machine.
I'm not following you, Norman. X3J11 went to a lot of trouble to ensure
that we DIDN'T make it overly difficult to implement C on a one's
complement machine. That's why all of the bit manipulation operators
are only well-defined when used with non-negative values. As far as I
know, the only extra effort you need to expend to implement C in such an
environment is that when you convert a signed integer to unsigned, you
have to add 1 to the result if the original value was negative; and you
have to make sure that you never generate -0.
> Consider the following strictly conforming program. It always outputs
> "No problem found." (Though of course it might output something else
> when run on something other than a conforming implementation.)
I don't believe the program is strictly conforming, nor do I think it
does what you want. Firstly, C's promise of a "pure binary numeration
system" excludes the sign bit -- as soon as you touch it, all bets are
off and you're in unspecified territory. This makes the program not
strictly conforming. Along those same lines, I don't believe that the
representation of -1 is required to be all bits set and, on a one's
complement machine it would not be, so your attempt to cobble up a -0 is
doomed to failure -- using an unsigned char pointer and ~0U would be
better, but I still don't think the results are meaningful.
----
Larry Jones, SDRC, 2000 Eastman Dr., Milford, OH 45150-2789 513-576-2070
larry...@sdrc.com
See if we can sell Mom and Dad into slavery for a star cruiser. -- Calvin
Joe Wright
the Standard wants to support? Which one(s)? Color me curious.
I seem to remember the Univac I was ones-complement (I could be wrong)
but I have never seen another one.
--
Joe Wright al...@wyvern.com "If you want it wRight"
Peter Holzer
>In article <22hmg2$o...@gaia.ucs.orst.edu>, pmon...@math.orst.edu (Peter Montgomery) writes:
>|> In article <22ha5h$a...@email.tuwien.ac.at> h...@vmars.tuwien.ac.at
>|> (Peter Holzer) writes:
>|> >
>|> >Of course you could change scp to be an unsigned char *, which would
>|> >give you the right bit pattern for -0. But suppose the implementation
>|> >does never produce -0 from normal operations. Does a variable
>|> >containing the bit pattern for -0 have to compare equal to zero in that
>I would imagine that whatever bit pattern you stick in, it had better
>compare equal to SOMETHING between INT_MIN and INT_MAX, no? Or CHAR_MIN
>and CHAR_MAX for signed chars, no? How about one big switch statement
>enumerating all the possible values, without a default value? Such a
>program, that prints out the same thing for each case, would be strictly
>conforming, and would force "-0" to compare equal to something. If it
>compares equal to anything non-zero, it violates the basic rules of
>arithmetic, therefore it must compare equal to zero.
I would hope so, but I am not sure about that. Unless I have overlooked
something, the standard does not define the semantics of the equality
operators for the arithmetic types at all.
Anyway, I think Norman's original argument is wrong, since the sentence
he constructed it from reads:
The range of nonnegative values of a signed integer type is a
subrange of the corresponding unsigned integer type, and the
representation of the same value in each type is the same.
IMHO, this means that the values (int)0 .. (int)INT_MAX must have the
same representation as (unsigned int)0 .. (unsigned int)INT_MAX (and
similarly for char, short, and long). It does not mean that there must
not be a second representation for (int)0 outside of that range.
So I think the following fragment could be used to test conformance to
this sentence:
unsigned int u
int i;
for (u = 0; u <= INT_MAX; u ++) {
i = u; /* or any other assignment to i which yields the same
* value
*/
if (i != *(int *)&u) printf ("problem\n");
if (u != *(unsigned int *)&i) printf ("problem\n");
}
If -0 must compare equal to 0, it must never be generated by signed
arithmetic, since that could be detected by the second if.
T. William Wells
: I seem to remember the Univac I was ones-complement (I could be wrong)
1100 series? Yes. Ones complement and a 36 bit word (meaning 9 bit
or larger bytes).
