Pointer indexing

Question

I am currently reading a book titled "Numerical Recipes in C". In this book, the author details how certain algorithms inherently work better if we had indices starting with 1 (I don't entirely follow his argument and that isn't the point of this post), but C always indexes its arrays starting with 0. In order to get around this, he suggests simply decrementing the pointer after allocation, e.g.:

float *a = malloc(size);
a--;

This, he says, will effectively give you a pointer that has an index starting with 1, which will then be free'd with:

free(a + 1);

As far as I'm aware, though, this is undefined behavior by the C standard. This is apparently a highly reputable book within the HPC community, so I don't want to simply disregard what he's saying, but simply decrementing a pointer outside of the allocated range seems highly sketchy to me. Is this "allowed" behavior in C? I have tested it out using both gcc and icc, and both of those results appear to indicate that I'm worrying over nothing, but I want to be absolutely positive.

Answer 1

You are right that code such as

float a = malloc(size);
a--;

yields undefined behavior, per the ANSI C standard, section 3.3.6:

Unless both the pointer operand and the result point to a member of the same array object, or one past the last member of the array object, the behavior is undefined

For code like this, the quality of the C code in the book (back when I used it in the late 1990s) wasn't considered very high.

The trouble with undefined behavior is that no matter what result the compiler produces, that result is by definition correct (even if it is highly destructive and unpredictable).
Fortunately, very few compilers make an effort to actually cause unexpected behavior for such cases and the typical malloc implementation on machines used for HPC has some bookkeeping data just before the address it returns, so the decrement would typically give you a pointer into that bookkeeping data. It is not a good idea to write there, but just creating the pointer is harmless on those systems.

Just be aware that the code could break when the runtime environment gets changed or when the code is ported to a different environment.

Answer 2

Officially, it's undefined behavior to have a pointer point outside the array (except for one past the end), even if it's never dereferenced.

In practice, if your processor has a flat memory model (as opposed to weird ones like x86-16), and if the compiler doesn't give you a runtime error or incorrect optimization if you create an invalid pointer, then the code will work just fine.

Answer 3

First, it's undefined behaviour. Some optimising compilers nowadays get very aggressive about undefined behaviour. For example, since a-- in this case is undefined behaviour, the compiler could decide to save an instruction and a processor cycle and not decrement a. Which is officially correct and legal.

Ignoring that, you might subtract 1, or 2, or 1980. For example if I have financial data for the years 1980 to 2013, I might subtract 1980. Now if we take float* a = malloc (size); there is surely some large constant k such that a - k is a null pointer. In that case, we really expect something to go wrong.

Now take a big struct, say a megabyte in size. Allocate a pointer p pointing to two structs. p - 1 might be a null pointer. p - 1 might wrap around (if a struct is a megabyte, and the malloc block is 900 KB from the start of address space). So it could be without any malice of the compiler that p - 1 > p. Things may get interesting.

Answer 4

...simply decrementing a pointer outside of the allocated range seems highly sketchy to me. Is this "allowed" behavior in C?

Allowed? Yes. Good idea? Not Usually.

C is a shorthand for assembly language, and in assembly language there are no pointers, just memory addresses. C's pointers are memory addresses that have a side behavior of incrementing or decrementing by the size of what they point to when subjected to arithmetic. This makes the following just fine from a syntax perspective:

double *p = (double *)0xdeadbeef;
--p;  // p == 0xdeadbee7, assuming sizeof(double) == 8.
double d = p[0];

Arrays aren't really a thing in C; they're just pointers to contiguous ranges of memory that behave like arrays. The [] operator is a shorthand for doing pointer arithmetic and dereferencing, so a[x] actually means *(a + x).

There are valid reasons to do the above, such as some I/O device having a couple of doubles mapped into 0xdeadbee7 and 0xdeadbeef. Very few programs would need to do that.

When you create the address of something, such as by using the & operator or calling malloc(), you want to keep the original pointer intact so you know that what it points to is actually something valid. Decrementing the pointer means that some bit of errant code could try to dereference it, getting erroneous results, clobbering something or, depending on your environment, committing a segmentation violation. This is especially true with malloc(), because you've put the burden on whoever's calling free() to remember to pass the original value and not some altered version that will cause all heck to break loose.

If you need 1-based arrays in C, you can do it safely at the expense of allocating one additional element that will never be used:

double *array_create(size_t size) {
    // Wasting one element, so don't allow it to be full-sized
    assert(size < SIZE_MAX);
    return malloc((size+1) * sizeof(double));
}

inline double array_index(double *array, size_t index) {
    assert(array != NULL);
    assert(index >= 1);  // This is a 1-based array
    return array[index];
}

Note that this doesn't do anything to protect against exceeding the upper bound, but that's easy enough to handle.

---

Addendum:

Some chapter and verse from the C99 draft (sorry, that's all I can link to):

§6.5.2.1.1 says that the second ("other") expression used with the subscript operator is of integer type. -1 is an integer, and that makes p[-1] valid and therefore also makes the pointer &(p[-1]) valid. This does not imply that accessing memory at that location would produce defined behavior, but the pointer is still a valid pointer.

§6.5.2.2 says that the array subscript operator evaluates to the equivalent of adding the element number to the pointer, therefore p[-1] is equivalent to *(p + (-1)). Still valid, but may not produce desirable behavior.

§6.5.6.8 says (emphasis mine):

When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand.

...if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist.

This means that the results of pointer arithmetic have to point at an element in an array. It does not say that the arithmetic has to be done all at once. Therefore:

double a[20];

// This points to element 9 of a; behavior is defined.
double d = a[-1 + 10];

double *p = a - 1;  // This is just a pointer.  No dereferencing.

double e = p[0];   // Does not point at any element of a; behavior is undefined.
double f = p[1];   // Points at element 0 of a; behavior is defined.

Do I recommend doing things this way? I don't, and my answer explains why.