Portability of array indexing types

A while ago, Serg approached me regarding a bug and a patch that was supposed to solve the problem (I just didn't write the post until now).

To explain the situation, I construct a similar setup, but simplify the issue significantly to demonstrate what the problem is, why the patch really solves the problem, and what the real solution is.

Suppose that we have a structure defined in the following manner and a function that is used to find a substring in a larger string. (Now, don't start complaining that I should use strstr(3) instead. It is true, but this is just an example and the real fulltext search does a lot more than this.)

typedef struct match {
  unsigned int beg;
  unsigned int end;
} match;

match find_substr(char const *str, char const *substr);

The match structure hold the positions of the beginning and the end of the substring found, and since the position is guaranteed to be positive, it is declared as unsigned.

Inside the fulltext search code, we have something that looks like this, which is used to decide if this is the beginning of a word or just something that is inside a word:

if (... && !isalnum(p0[m[1].beg - 1])) {
  /*
    Do something if the character before the first one that matched is
    not a word character.
  */
}

Now, when running on a 64-bit machine... and under certain circumstances... MySQL BUG#11392 was triggered. After some investigations, the following patch was committed which proved to solve the problem (I've highlighted the changed part of the line):

- if (... && !isalnum(p0[m[1].beg - 1])) {
+ if (... && !isalnum(*(p0 + m[1].beg - 1))) {

Everybody who's a little familiar with C knows that ptr[expr] is just another way to write *(ptr + expr), so this could should not really change anything at all and could therefore not fix the bug. Right?

Wrong.

The expression ptr[expr] is equivalent to the expression *(ptr + (expr)), and please note the additional parentheses around the expression. This seems to be quite obvious, but please bear with me for a little while more.

The special quirk on the compiler of this 64-bit machine is that pointers are of size 8 (bytes), while sizeof(unsigned int) is 4. (I can't know for sure why the compiler is implemented this way, but my guess is that it is so that each of the sizes 1, 2, 4, and 8 (bytes) can be represented with a basic type in C89. Remember that long long does not exist in C89.)

While doing the searching, the start position of the match ended up at (unsigned) zero. For machines where the size of a pointer is the same as the size of an unsigned int (and where negative integers are represented using two-complement numbers, but as far as I know that is ubiquitous), p0[0U-1] == *(p0 + (0U - 1)) == *(p0 + UINT_MAX) == p0[-1], so all is well (in this case, *(p0 - 1) was a valid memory location).

However, for this 64 bit machine where the pointers are 64 bits instead of 32 while the unsigned int is 32 bits, the addition before the patch ends up very far away into the array (in this case far out of the allocated memory), so there were a segmentation fault. However, for the patched code we have *(p0 + 0U - 1) == *((p0 + 0U) - 1) == *(p0 - 1), so it works even on this machine with this compiler.

So, the basic problem is that an unsigned integral type is used to index the array, and that integral type is smaller than the size of the pointer. In that case, it is important in what order the computations are made. Since the natural approach is to use array index notation, we need to find a type for beg that is good for this use on any machine, so what to pick? We need a signed integral type, since we need to ensure that -1 really becomes -1 and does not cause a wraparound as unsigned arithmetics do. We also need it to be large enough to move backwards and forwards from any position in an object to any other position in an object.

The immediate candidate for this is ptrdiff_t, which is supposed to be able to represent the difference between two pointers. So what does the standard say regarding this? Well... not much actually. From 7.1.7 (the TC3 draft is available as ISO/IEC 9899:TC3 on www.open-std.org), we have:

ptrdiff_t [...] is the signed integer type of the result of subtracting two pointers

So that seems to be all well and good, however, from 6.5.6 §9, we have (emphasis is mine):

When two pointers are subtracted [...] the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h>; header. If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i-j provided the value fits in an object of type ptrdiff_t.

So, in essence, the type ptrdiff_t is a signed integral type that might be able to represent the difference between two pointer, so we cannot rely on ptrdiff_t. This leaves size_t, which is an unsigned integral type large enough to hold the size of any object. Now, it seems strange that I advocate using an unsigned type when I pointed out a problem with it above, but the problem is that the wraparound caused by using an unsigned integer that is smaller than the pointer size caused the problem. So, if sizeof(X*) == sizeof(size_t), all will work as expected.

Now, as usual when it comes to standard issues, there are some caveats. For machines with segmented memory (like 80486, but there are others), the compilers have different of memory types and hence different kinds of pointers. For example __far,__near, and __huge. So, to illustrate the problem, we assume we have a 16-bit machine with 8-bit segment number and the pointers are __far pointers, i.e., each pointer is the address within the segment plus a segment address. This means that sizeof(void*) == 3. For this memory model, it is usually the case that any object defined has to fit within a single segment and may not border two segments. This means that sizeof(size_t) == 2. Since sizeof(size_t) is less than sizeof(void*), we have the same problem again.

So, what is the moral of the story? Well... if you need to have a type to represent an index into an array, use size_t and make sure that sizeof(size_t) == sizeof(void*).

If sizeof(size_t) < sizeof(void*), you have three (not necessarily exclusive) options:

• Scream and curse
• Pick a signed integral type strictly larger than size_t. It will be horribly inefficient, but it will work
• Make sure that any expression used for array indexing never become negative by expanding the array indexing manually as was done in the patch above.