Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
3  
what C standard do you refer? I ask because per my recollection, "Numerical Recipes in C" has been published in 1990s, in ancient times of K&R and maybe ANSI C –  gnat Jul 8 at 12:54
2  
Related SO question: stackoverflow.com/questions/10473573/… –  dan04 Jul 8 at 13:20
3  
"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." Never assume that because your compiler allows it, the C language allows it. Unless, of course, you're fine with your code breaking in the future. –  Doval Jul 8 at 14:42
5  
Without wishing to be snarky, "Numerical Recipies" is generally considered a useful, quick and dirty book, not a paradigm of either software development or numerical analysis. Check out the Wikipedia article on "Numerical Recipies" for a summary of some of the criticisms. –  Charles E. Grant Jul 8 at 16:48
1  
As an aside, here's why we index from zero: cs.utexas.edu/~EWD/ewd08xx/EWD831.PDF –  Russell Borogove Jul 8 at 17:15

4 Answers 4

up vote 14 down vote accepted

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.

share|improve this answer
3  
Exactly, it is possible on a multi-bank architecture that malloc could give you the 0th address in a bank and the decrementing it can cause a CPU trap with an underflow for one. –  Vality Jul 8 at 16:31
    
I disagree that that is "fortunate". I think it would be much better if compilers emitted code that immediately crashed whenever you invoked undefined behavior. –  David Conrad Jul 8 at 20:04
4  
@DavidConrad: Then C isn't the language for you. Much of the undefined behavior in C can't be easily detected or only with a severe performance hit. –  Bart van Ingen Schenau Jul 8 at 20:16
    
I was thinking of adding "with a compiler switch". Obviously you wouldn't want that for optimized code. But, you're right, and that's why I gave up writing C ten years ago. –  David Conrad Jul 8 at 20:19
    
@BartvanIngenSchenau depending on what you mean by 'severe performance hit' there is symbolic execution for C (for example clang+klee) as well as sanatizers (asan, tsan, ubsan, valgrind etc.) which tend to be very useful for debugging. –  Maciej Piechotka Jul 8 at 20:28

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.

share|improve this answer
1  
That makes sense. Unfortunately, that's two too many if's for my liking. –  wolfPack88 Jul 8 at 13:33
2  
The last point is IMHO the most problematic. Since compilers these times don't just let happen whatever the platform "naturally" does in case of UB, but optimizers are aggressively exploiting it, I wouldn't play with it so lightly. –  Matteo Italia Jul 8 at 22:15

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.

share|improve this answer

...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.

share|improve this answer
6  
-1 A definition of 'allowed' which includes code the C standard declares as generating undefined results is not a useful one. –  Pete Kirkham Jul 8 at 14:01
    
Others have pointed out that it's undefined behaviour, so you shouldn't say that it's "allowed". However, the suggestion to allocate an extra unused element 0 is good. –  200_success Jul 8 at 14:36
    
This is really not right, please at least note that this is forbidden by the C standard. –  Vality Jul 8 at 16:32
    
@PeteKirkham: I disagree. See the addendum to my answer. –  Blrfl Jul 8 at 16:34
2  
@Blrfl 6.5.6 of the ISO C11 standard states in the case of adding an integer to a pointer: "If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behaviour is undefined." –  Vality Jul 8 at 17:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.