Casting ArraysI shall begin this tale at its end. This will be about a particular programming problem in C, one that you've likely encountered if you've ever dealt with dynamically allocated arrays.
Here's the situation: You've just allocated a pointer to a linear or one-dimensional array of integers. It's something like ptr=(int *)malloc(ARRAYSIZE). Later in the program, a function will treat this array as a 2-D array with dimensions of 100 by 200. The function is declared as void func1(int array[][200]).
How do you pass the pointer you got from malloc() to the function and keep all C compilers happy? Certainly, this will require a cast operation, but how do you construct it?
As promised, here's the answer:
func1((int(*)[200])foo);
I will happily admit that when the above solution was presented to me I found it to be less than obvious. Not only was I confused by the nested elements in the cast operation, I was further thrown by the explanation that was given by the solution's provider: The above cast will work because func1() is expecting a pointer to an array of 200 integers.
On the surface, that seems wrong. The routine func1 is expecting a pointer to a 2-D array of integers, not a 1-D array of 200 integers--or so I thought. The solution required an investigation into how C treats arrays, as well as how to interpret cast operations.
The First Wrong Answer
This problem arose when I was working with the BYTEmark program (see "BYTE's New Benchmarks," March BYTE). Many of the routines in the BYTEmark program worked with varying numbers of arrays. In other words, although a particular routine--say, func1()--would operate on a single 100 by 200 array of integers, the caller of func1() would have allocated space for three or four such arrays.
The allocation would, of course, have taken place via malloc(). It would be up to the caller of func1() to determine the offset into the buffer to the start of each 2-D array and pass the properly adjusted pointer to func1(). Hence the problem: Coercing a pointer to an integer (a sequential buffer of integers, to be precise) into something I could pass to a function expecting a 2-D array of integers.
The first wrong answer was to simply do it. After all, you can pass a pointer in place of a reference to a 1-D array. For example, I could easily pass ptr (as defined earlier) into a function defined as follows:
void func1(int array[]);
However, for the original case--func1() expecting a 2-D array--simply calling func1() with ptr as the argument worked for only some compilers. For example, Watcom C/C++ had no problem with it. But the Metrowerks Code Warrior compiler for the Mac refused it. Several discussions with the engineers at Metrowerks left me with the feeling that it wasn't Metrowerks' problem. I would have to come up with a workaround.
The Unused Answer
There is a related problem, one whose solution leads to the solution to the original problem. The related problem is this: How do you write a routine that manipulates a 2-D array of indeterminate size? That is, at compile time, we don't know how many rows and columns will be in the array--the algorithms handling the array are such that the dimensions are determined at run time. (We're keeping things down to only 2-D arrays; astute readers will be able to extend this to multidimensional arrays.)
Consider how a C compiler "sees" a 2-D array. At one level, the array is just a contiguous set of memory locations. But at a higher level, the compiler has to understand that members of the array are accessed via two indexes. So, to reference an element of the array, the compiler needs to know the array's dimensions.
That turns out to be only partly true. To allocate space for the array, the compiler does need to know both dimensions (as well as the data type). But to reference an item in the array, the compiler need know only how many columns are in the array.
For example, consider a byte array with dimensions of [2][3]. The offset to element [i][j] can be calculated by i*3+j. The compiler doesn't need the size of the first subscript.
Thus, you can manipulate 2-D arrays of indeterminate size. Where you would have written array[i][j], you simply write *(&array[0][0]+i*COLS+j). (COLS represents the number of columns.) The expression &array[0][0] returns the address of the first element of the array; the rest of the expression calculates the proper offset.
The catch is, this is not generally efficient. Consider the case where either i or COLS in the above equation is a power of two. In that case, you'd want to turn the multiplication into a shift operation. Also, if you had access to the machine's registers, you might want to keep COLS inside a register to reduce a load-multiply operation to simply a multiply operation. This is what a compiler would do as part of its optimization process. The upshot: A compiler is better at optimizing array access than you're ever likely to be.
In any case, this technique solves the original problem. Once you've allocated enough space for 100 by 200 integers using malloc(), you pass that to func1(), which is now defined as void func1(int *array). Of course, inside func1(), you'll have to handle all array subscripting manually. But, as described above, it's likely to produce slower code.
The Wrong Answer That Worked
After all, what was func1() really working with but a pointer. In terms of size, a pointer to a 1-D array was as large as a pointer to a 2-D, 3-D, 4-D, or whatever-dimensional array. I knew that, but I just couldn't get C to believe me.
The first answer that worked was to make use of the union declaration. I handled it through a typedef:
typedef struct {
union {
int *ptr;
int (*aptr)[COLS];
} p;
} tp;
This lets you call the function without the extra level of indirection:
tp locptr;
... locptr.p.ptr=(int *)malloc(ARRAYSIZE); ... func1(locptr.p.aptr); ...
It's also--in one sense, at least--wrong. The expression (*aptr)[ROWS][COLS] defines a pointer to a 2-D array. As it turns out, this is what you would pass to a function that expects a 3-D array.
If you find that confusing, don't be alarmed--I did, as well. Given an array defined as int matrix[2][3], I originally thought that the expression matrix (with no subscripts) was understood by the C compiler to be a pointer to an integer--in this case, the first integer in the array. The compiler simply used the subscripts to calculate proper offsets from that pointer. Not so; matrix is treated as a pointer to two elements, each element being an array of three integers. Thus, matrix is a pointer to an array of integers (that array being the first row). Another way of saying the same thing--matrix is a pointer to a pointer to an integer.
As a result, the expression matrix[0] (specifying only the first index) is valid: It returns a pointer that references the first element of the first row of matrix. So, *matrix[0] will retrieve the same value as would matrix[0][0]. Similarly, matrix[1] will return a pointer to the first element of the second row of the array, and so on.
Now that we know how C "sees" arrays, we can derive a more correct way of using the union declaration to solve the problem:
typedef struct {
union {
int *ptr;
int (*aptr)[ROWS][COLS];
} p;
} tp;
This got the job done, and compilers happily accept it. In use, though, it's bulky, as the following call shows:
tp locptr; ... locptr.p.ptr=(int *)malloc(ARRAYSIZE); ... func1(*(locptr.p.aptr)); ...
In some ways, using the union declaration to coerce a pointer to a buffer to a 2-D array reference is quite flexible. You can load up the union structure with multiple pointers to arrays of different dimensions, if you wish. This would let you reference a single array as a 1-D, 2-D, or 3-D array (although offhand I can't think of an algorithm that would need that capability). However, this is not very elegant, and it betrays a lack of understanding of how to use the C cast operator.
The Last Right Answer
Knowing what we now know, we need to cast ptr--declared as a pointer to an int--into a pointer to an array of int. We already know what the answer is (reread the beginning of the article if you've forgotten), and because deciphering a complex cast can be difficult, we'll reverse-engineer what we already know works. The cast expression is (int(*)[200])matrix.
To understand a complex cast operation, you use the right-left rule: Start with the identifier, look right, and then look left. Continue this recursively to "work your way out" of the expression. As you work your way out, evaluate () (identifies a function) and [] (identifies an array) at a higher preference than * (identifies a pointer).
So, for the cast given above, because there is no identifier, start with the innermost (*) -- it's a pointer -- look right -- it's a pointer to an array -- look left -- it's a pointer to an array of integers -- and you're done.
I'm embarrassed to say that the last right answer was not the one that made its way into the first version of the BYTEmark benchmarks. The current release of the benchmarks uses the union trick instead. Still, it's often the case that a not-so-right answer to a problem can work, lead to a deeper understanding of what is actually going on, and ultimately provide the last right answer.
BIBLIOGRAPHY
Anderson, Paul, and Gail Anderson. Advanced C Tips and Techniques. Indianapolis, IN: Hayden Books, 1988.
ACKNOWLEDGMENT
I wish to thank James Janney, who gave me the last right answer.
Copyright © 1994-1995