14

From this post in SO, it is clear that C supports negative indices.

  1. Why support such a potential memory violation in a program?

  2. Shouldn't the compiler throw a Negative Index warning at least? (am using GCC)

  3. Or is this calculation done in runtime?

EDIT 1: Can anybody hint at its uses?

EDIT 2: for 3.) Using counters of loops in [] of arrays/pointers indicates Run-time Calculation of Indices.

Community
  • 1
  • 1
boxed__l
  • 1,334
  • 1
  • 10
  • 24
  • 3
    You can legitimately take the address of the Nth element of an array and then negatively index down to -N. – Hot Licks Aug 11 '13 at 14:20
  • 1
    @ 1) : to avoid negative indexing you can use unsigned types as an index, which also has the nice property of _failing fast_. – wildplasser Aug 11 '13 at 14:29
  • 3
    @wildplasser: No, they won't fail any faster. On typical implementations, adding `SIZE_MAX` to a pointer (which has UB) has the same effect as adding `-1` to that pointer. – R.. GitHub STOP HELPING ICE Aug 11 '13 at 14:57
  • 1
    Yes, they _do_ fail faster: a negative index could corrupt memory silently, while an index of `(unsigned) (~0)` will immediately cause an out-of-bounds violation. – wildplasser Aug 11 '13 at 15:01
  • If `unsigned` and `size_t` are the same size, `x[-1]` and `x[(unsigned) ~0]` typically have the same effect in common implementations. If `size_t` is wider than `unsigned` (which is not uncommon in “64-bit” implementations) there is typically a difference; the former is usually just before the array, and the latter is a great distance away. However, one should generally avoid `int` or `unsigned` for indices and prefer `ptrdiff_t`. When using `ptrdiff_t`, there is typically no difference. – Eric Postpischil Aug 11 '13 at 17:40
  • @EricPostpischil: I realise that if `void *` and the unsigned index variable have the same size (such as in the case of (`void*` and `size_t`), the pointer arithmetic (though formally undefined) will be performed using _effectively_ modulo `1u<< sizeof (void*)`. I guess this is the point that @R.. tries to make (but he implicitely assumes that the index variable and the pointer have the same size) – wildplasser Aug 11 '13 at 21:52
  • possible duplicate of [Negative array indexes in C?](http://stackoverflow.com/questions/3473675/negative-array-indexes-in-c) – m0nhawk Apr 10 '15 at 13:59

8 Answers8

21

The calculation is done at runtime.

Negative indices don't necessarily have to cause a violation, and have their uses.

For example, let's say you have a pointer that is currently pointing to the 10th element in an array. Now, if you need to access the 8th element without changing the pointer, you can do that easily by using a negative index of -2.

char data[] = "01234567890123456789";
char* ptr = &data[9];
char c = ptr[-2]; // 7
Ziffusion
  • 8,779
  • 4
  • 29
  • 57
  • Hey to access the 8th element wouldn't i use `*(data+7)`? – boxed__l Aug 11 '13 at 14:30
  • 1
    It's just an example. In some scenarios, data may not be available. Let's say you pass ptr as an argument to other functions. Inside the functions, you may have use for negative indices to access prior elements like this. In any case, this is just an example. Just saying that there are legitimate uses for a negative index. – Ziffusion Aug 11 '13 at 14:40
11

Here is an example of use.

An Infinite Impulse Response filter is calculated partially from recent previous output values. Typically, there will be some array of input values and an array where output values are to be placed. If the current output element is yi, then yi may be calculated as yi = a0•xi + a1•xi–1 +a2•yi–1 +a3•yi–2.

A natural way to write code for this is something like:

void IIR(float *x, float *y, size_t n)
{
    for (i = 0; i < n; ++i)
        y[i] = a0*x[i] + a1*x[i-1] + a2*y[i-1] + a3*y[i-2];
}

Observe that when i is zero, y[i-1] and y[i-2] have negative indices. In this case, the caller is responsible for creating an array, setting the initial two elements to “starter values” for the output (often either zero or values held over from a previous buffer), and passing a pointer to where the first new value is to be written. Thus, this routine, IRR, normally receives a pointer into the middle of an array and uses negative indices to address some elements.

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
9

Why support such a potential memory violation in a program?

Because it follows the pointer arithmetic, and may be useful in certain case.

Shouldn't the compiler throw a Negative Index warning at least? (am using GCC)

The same reason the compiler won't warn you when you access array[10] when the array has only 10 elements. Because it leaves that work to the programmers.

Or is this calculation done in runtime?

Yes, the calculation is done in runtime.

Yu Hao
  • 119,891
  • 44
  • 235
  • 294
5

Elaborating on Taymon's answer:

float arr[10];
float *p = &arr[2];

p[-2]

is now perfectly OK. I haven't seen a good use of negative indices, but why should the standard exclude it if it is in general undecidable whether you are pointing outside of a valid range.

user1666959
  • 1,805
  • 12
  • 11
  • " I haven't seen a good use of negative indices" - in [this tutorial](http://www.youtube.com/watch?v=PjjDMe5r5Zk) the hash function takes into account the current **and** the previous character in the string, the code contains `hash += data * p[-1]` (or something like this). –  Aug 11 '13 at 16:08
  • The emphasis should have been on 'good use'. Naturally, one can switch between the two styles of always passing the 0th element and using a variable of type 'size_t' to index and passing the nth element and using negative indices. By good use I was hoping for something where the negative index has a nice interpretation ie it exposes something interesting in the algorithm being implemented. Here is a decidable criteria: if I find any use of negative indices in the original TeX source or the Standford GraphBase (any published code by Knuth) I'll change the claim :). – user1666959 Aug 12 '13 at 04:30
4

Array subscripts are just syntactic sugar for dereferencing of pointers to arbitrary places in memory. The compiler can't warn you about negative indexes because it doesn't know at compile time where a pointer will be pointing to. Any given pointer arithmetic expression might or might not result in a valid address for memory access.

Taymon
  • 24,950
  • 9
  • 62
  • 84
  • 2
    If you're doing something like `a[i]` then of course it's done at runtime. The compiler cannot know the value of `i` at compile time because it will be different each time the code is executed. – Taymon Aug 11 '13 at 14:24
  • 12
    You should change "Arrays are just syntactic sugar for pointers" because arrays and pointers are quite different. "Array-subscripts `[]` are just syntactic sugar..." would be better. – Kninnug Aug 11 '13 at 14:36
4

OP: Why support ... a potential memory violation?

It has potential uses, for as OP says it is a potential violation and not certain memory violation. C is about allowing users to do many things, include all the rope they need to hang themselves.

OP: ... throw a Negative Index warning ...

If concerned, use unsigned index or better yet, use size_t.

OP ... calculation done in runtime?

Yes, quite often as in a[i], where i is not a constant.

OP: hint at its uses?

Example: one is processing a point in an array of points (Pt) and want to determine if the mid-point is a candidate for removal as it is co-incident. Assume the calling function has already determined that the Mid is neither the first nor last point.

static int IsCoincident(Pt *Mid) {
  Pt *Left = &Mid[-1];   // fixed negative index
  Pt *Right = &Mid[+1]; 
  return foo(Left, Mid, Right);
}
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

a[b] does the same thing as *(a+b). Since the latter allows the negative b, so does the former.

dragonroot
  • 5,653
  • 3
  • 38
  • 63
0

Example of using negative array indices.

I use negative indices to check message protocols. For example, one protocol format looks like:

<nnn/message/f>

or, equally valid:

<nnn/message>

The parameter f is optional and must be a single character if supplied.

If I want to get to the value of character f, I first get a pointer to the > character:

char * end_ptr = strchr(msg, '>');
char f_char = '1';  /* default value */

Now I check if f is supplied and extract it (here is where the negative array index is used):

if (end_ptr[-2] == '/')
{
    f_char = end_ptr[-1];
}

Note that I've left out error checking and other code that is not relevant to this example.

NZD
  • 1,780
  • 2
  • 20
  • 29