Making Fatal Hidden Assumptions

Now responding to the basic article:

In article snipped-for-privacy@maineline.net writes: ... > #define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)

It does not allow for larger sizeof(int) (as it does not allow for other values of CHAR_BIT). When sizeof(int) > 4 it will only show whether there is a zero byte in the low order four bytes. When sizeof(int) < 4 it will give false positives. Both constants have to be changed when sizeof(int) != 4. Moreover, it will not work on

It is false on the Cray 1 and its derivatives. See another article by me where I show that it may give wrong answers.

Yeah, my world-view doesn't allow individual objects to occupy half the address space or more. I'm comfortable with that restriction, but I can accept that there may be others that aren't. They're wrong, of course :-)

Yes, very hard indeed. Partition your object or use a machine with bigger addresses. Doesn't seem like a good enough reason to me to break a very useful abstraction.

Posit: you've got N bits to play with, both for addresses and integers. You need to be able to form a ptrdiff_t, which is a signed quantity, to compute d = anobject.a[i] - anobject.a[j], for any indices i,j within the range of the array. The range of signed quantities is just less than half that of unsigned. That range must therefore define how large any individual object can be. I.e., half of your address space. Neat, huh?

Yeah, yeah, for any complicated problem there's an answer that is simple, neat and wrong.

Right, "illegal" probably isn't the best word to describe undefined behavior. An implementation is required to diagnose syntax errors and constraint violations; it's specifically *not* required to diagnose undefined behavior (though it's allowed to do so).

Ok, you can do that if you like. If you can manage to avoid undefined behavior altogether, your code is likely to work on *any* system with a conforming C implementation; if not, it may break when ported to some exotic system.

For example, code that makes certain seemingly reasonable assumptions about pointer representations will fail on Cray vector systems. I've run into such code myself; the corrected code was actually simpler and cleaner.

If you write code that depends on undefined behavior, *and* there's a real advantage in doing so on some particular set of platforms, *and* you don't mind that your code could fail on other platforms, then that's a perfectly legitimate choice. (If you post such code here in comp.lang.c, you can expect us to point out the undefined behavior; some of us might possibly be overly enthusiastic in pointing it out.)

All bets don't *need* to be off if you're able to stick to what the C standard actually guarantees.

Probably, since NULL has been given the guarantee that it's unique in some sense. In an embedded environment, or assembly language, the construct could of course produce NULL (for whatever value you pick for NULL), and NULL would not be special. I don't know that insisting on the existence of a unique and special NULL pointer value is one of the standard's crowning achievements, either. It's convenient for lots of things, but it's just not the way simple hardware works, particularly at the limits.

Sure, in the ptrdiff sense that I mentioned before. I.e., (a - 1) - (a + 0) < 0 (indeed, identically -1)

Go nuts. If your address space is larger than your integer range, (as, is the case for I32LP64 machines), your compiler might have to make sure that it performs the difference calculation to sufficient precision.

I still feel comfortable about this failing to work for objects larger than half the address space, or even for objects larger than the range of an int. That's IMO, a much less uncomfortable restriction than the one that the standard seems to have stipulated, which is that the simple and obvious pointer arithmetic that you've used in your examples works in some situations and doesn't work in others. (Remember: it's all good if those array references are in a function that was itself passed (&foo[n], for n>=1) as the argument.)

Cheers,

I can easily imagine a program that needs to manipulate a very large data set (for a scientific simulation, perhaps). For a data set that won't fit into memory all at once, loading as much of it as possible can significantly improve performance.

Your "very useful abstraction" is not something that has *ever* been guaranteed by any C standard or reference manual.

The standard explicitly allows for the possibility that pointer subtraction within a single object might overflow (if so, it invokes undefined behavior). Or, given that C99 requires 64-bit integer types, making ptrdiff_t larger should avoid the problem for any current systems (I don't expect to see full 64-bit address spaces for a long time).

The standard is full of compromises. Not everyone likes all of them.

Same for gcc4 on MacOS X. However this slight permutation of your program (only the comparison line has changed):

#include

#define SIZE (50*1000000L) typedef struct { char a [SIZE]; } bigstruct;

static bigstruct bigarray [8];

int main(void) { printf("%lx\n", (unsigned long) &bigarray [0]); printf("%lx\n", (unsigned long) &bigarray [9]); printf("%lx\n", (unsigned long) &bigarray [-1]); if (&bigarray [-1] - & bigarray [0] < 0) printf ("Everything is fine\n"); else printf ("The C Standard is right: &bigarray [-1] is broken\n"); return 0; }

produces:

So what we see is that (a) pointer comparisons use direct unsigned integer comparison, instead of checking the sign of the pointer difference---since pointer comparisons only make sense in the context of an indivdual object, I'd argue that the compiler is doing the wrong thing here, and the comparison should instead have been done in the context of a pointer difference; and (b) your printf string about "&bigarray[-1] is broken" is wrong, since that's not what the code showed at all. What it showed is that &bigarray[-1] could be formed, that &bigarray[0] was one element to the right of it, and that hell did not freeze over (nor was any trap taken), since you did not attempt to access any memory there.

Cheers,

The Cray blood-line starting at least with "Little Character" (prototype for the 160) was 1's complement, implemented with subtraction as the basis of arithmetic (the so-called 'adder pyramid'). Even the CDC

Nor did he have truck with integrated circuits until absolutely necessary.

Michael Grigoni Cybertheque Museum

How exactly do you get from NULL (more precisely, a null pointer value) being "unique in some sense" to a guarantee that &a[-1], which doesn't point to any object, is unequal to NULL?

The standard guarantees that a null pointer "is guaranteed to compare unequal to a pointer to any object or function". &a[-1] is not a pointer to any object or function, so the standard doesn't guarantee that &a[-1] != NULL.

Plausibly, if a null pointer is represented as all-bits-zero, and pointer arithmetic works like integer arithmetic, an object of size N could easily happen to be allocated at address N; then pointer arithmetic could yield a null pointer value. (In standard C, this is one of the infinitely many possible results of undefined behavior.)

What restrictions would you be willing to impose, and/or what code would you be willing to break, in order to make such a guarantee?

Most jokes contain at least a kernel of truth.

Yeah, me to. Still do, regularly, on processors that will never have a C compiler. C is as close to a universal assembler as we've got at the moment. It doesn't stick it's neck out too far, although a more deliberately designed universal assembler would be a really good thing. (It's on my list of things to do...)

If you actually *want* a higher level language, there are better ones to chose from than C.

While the data are consistent with this conclusion, there are other ways to arrive at the same output. But this is certainly allowed.

It is perhaps worth pointing out that in Ancient C (as in "whatever Dennis' compiler did"), before the "unsigned" keyword even existed, the way you got unsigned arithmetic and comparisons was to use "char *". That is:

int a, b; char *c, *d; ... if (a rkcsr!) */ if (c < d) /* unsigned compare */ ...