| [ Team LiB ] |
|
12.10 Restructuring Arrays12.10.1 ProblemArrays contain information in their structure. Knowing how many dimensions an array has can help in understanding the underlying data. You need a way to hide dimensional information about arrays. 12.10.2 SolutionDisguising the nature of arrays is different from obfuscating a variable. What is important in this case is the order of elements in the array, not the elements themselves. Array elements can be obfuscated using any standard variable obfuscation, but arrays themselves should be restructured as well. Arrays can be restructured in four ways:
In this recipe, an API will be developed for splitting, folding, flattening, and merging arrays. 12.10.3 Discussion
The first step in developing the API for restructuring arrays is to define a new data type that will represent an array, rather than using the normal C convention for arrays. This array type will hide the management of the array restructuring from the programmer. typedef enum {
SPC_ARRAY_SPLIT, SPC_ARRAY_MERGE, SPC_ARRAY_FOLD, SPC_ARRAY_FLAT
} spc_array_type;
typedef struct {
spc_array_type type;
int sz_elem;
int num_elem;
int split;
unsigned char data[1];
} spc_array_t;
Four functions—spc_array_split( ), spc_array_merge( ), spc_array_fold( ), and spc_array_flat( )—are provided for creating arrays. The spc_array_get( ) function retrieves an element from an array, and the spc_array_set( ) function sets an element in the array. Use spc_array_free( ) to destroy an array. #include <stdlib.h>
#include <limits.h>
/* Create a split array of num_elem elements, each of size sz_elem */
spc_array_t *spc_array_split(int sz_elem, int num_elem) {
double size;
spc_array_t *a;
size = (((double)sz_elem * (double)num_elem) / 2) + (double)sizeof(spc_array_t);
if (size > (double)INT_MAX) return 0;
if (!(a = (spc_array_t *)calloc((size_t)size, 1))) return 0;
a->type = SPC_ARRAY_SPLIT;
a->sz_elem = sz_elem;
a->num_elem = num_elem;
a->split = 2; /* array is split into 2 arrays */
return a;
}
/* Create two merged arrays with num_first elements in array 1 and num_second
* elements in array 2
*/
spc_array_t *spc_array_merge(int sz_elem, int num_first, int num_second) {
double size;
spc_array_t *a;
size = (((double)num_first + (double)num_second) * (double)sz_elem) +
(double)sizeof(spc_array_t);
if (!num_first || size > (double)INT_MAX) return 0;
if (!(a = (spc_array_t *)calloc((size_t)size, 1))) return 0;
a->type = SPC_ARRAY_MERGE;
a->sz_elem = sz_elem;
a->num_elem = num_first + num_second;
a->split = num_first / num_second;
if (!a->split) a->split = (num_second / num_first) * -1;
return a;
}
/* Create an array folded 'layers' times, with num_elem elements */
spc_array_t *spc_array_fold(int sz_elem, int num_elem, int layers) {
double size = (sz_elem * num_elem) + sizeof(spc_array_t);
spc_array_t *a;
size = ((double)sz_elem * (double)num_elem) + (double)sizeof(spc_array_t);
if (size > (double)INT_MAX) return 0;
if (!(a = (spc_array_t *)calloc((size_t)size, 1))) return 0;
a->type = SPC_ARRAY_FOLD;
a->sz_elem = sz_elem;
a->num_elem = num_elem;
a->split = layers;
return a;
}
/* Create a flattened array of num_dimen dimensions with num_elem elements per
* dimension, flattened to a single dimension
*/
spc_array_t *spc_array_flat(int sz_elem, int num_elem, int num_dimen) {
double size;
spc_array_t *a;
size = ((double)sz_elem * (double)num_elem * (double)num_dimen) +
(double)sizeof(spc_array_t);
if (size > (double)INT_MAX) return 0;
if (!(a = (spc_array_t *)calloc((size_t)size, 1))) return 0;
a->type = SPC_ARRAY_FLAT;
a->sz_elem = sz_elem;
a->num_elem = num_elem * num_dimen;
a->split = num_dimen;
return a;
}
/* return the real index of element 'idx' in array 'subarray' */
static int array_index(spc_array_t *a, int subarray, int idx) {
int index = -1, num_row, diff;
num_row = a->num_elem / a->split;
switch (a->type) {
case SPC_ARRAY_SPLIT:
if (idx % a->split) index = idx / a->split;
else index = (a->num_elem / a->split) + (idx / a->split);
break;
case SPC_ARRAY_MERGE:
/* a->split = = size diff between array 1 and 2 */
if (a->split < 0) {
subarray = !subarray;
diff = a->split * -1;
} else diff = a->split;
if (!subarray) index = idx + idx / diff;
else index = diff + (idx * (diff + 1));
break;
case SPC_ARRAY_FOLD:
index = (idx / num_row) + (a->split * (idx % num_row) );
break;
case SPC_ARRAY_FLAT:
index = subarray + (a->split * (idx % num_row));
break;
}
return (index >= a->num_elem ? -1 : index);
}
/* Get a pointer to element 'idx' in array 'subarray' */
void *spc_array_get(spc_array_t *a, int subarray, int idx) {
int index;
if (!a || (index = array_index(a, subarray, idx)) = = -1) return 0;
return (void *)(a->data + (a->sz_elem * index));
}
/* Set element 'idx' in array 'subarray' to the data pointed to by 'src' --
* note that the sz_elem used to initialize the array is used here to copy
* the correct amount of data.
*/
int spc_array_set(spc_array_t *a, int subarray, int idx, void *src) {
int index;
if (!a || !src || (index = array_index(a, subarray, idx)) = = -1)
return 0;
memcpy(a->data + (a->sz_elem * index), src, a->sz_elem);
return 1;
}
/* Free an spc_array_t, including its table of elements */
int spc_array_free(spc_array_t *a) {
if (a) free(a);
return !!a;
}
The function spc_array_split( ) creates a two-dimensional array that is accessed as if it were an array of a single dimension; all odd-numbered elements are stored in the first half of the array, and all even-numbered elements are stored in the second half. For example, an array of five elements with indices numbered zero through four is conceptually broken up into two arrays where the second and fourth elements are stored in the first array, and the first, third, and fifth elements are stored in the second array. The two conceptual arrays are actually stored contiguously in memory. The effect is a simple reordering of the elements as illustrated in Figure 12-1. Figure 12-1. Memory representation of split arrays The function spc_array_merge( ) creates a single-dimensional array whose elements are indexed as if they were two separate arrays; the elements are referenced by an array number (0 or 1) and an index into that array. The ratio of the size between the two arrays is used to determine the placement of each element, so that the arrays are stored in memory as illustrated in Figure 12-2. Figure 12-2. Memory representation of merged arrays Folded arrays created using the spc_array_fold( ) function become multidimensional arrays, similar to the two-dimensional arrays created with spc_array_split( ). Each array element is referenced by an index as if it were in a single-dimensional array. The number of dimensions chosen determines the ordering of the elements. The memory representation of folded arrays is illustrated in Figure 12-3. Figure 12-3. Memory representation of folded arrays The spc_array_flat( ) function stores multiple arrays or a multidimensional array as a single-dimensional array with each element referenced by an array number and an index into that array. The first element of each array is stored, followed by the second element of each array, and so forth until the end of the arrays are reached. Note that not all arrays need be the same size for this to work correctly, as long as the space reserved for the one-dimensional array contains NULL entries for the unused elements. The memory representation of flat arrays is illustrated in Figure 12-4. Figure 12-4. Memory representation of flat arrays The following example demonstrates how to create, initialize, and iterate through each type of array: #include <stdio.h>
int main(int argc, char *argv[ ]) {
int i, j, *p, val;
spc_array_t *a_split, *a_merge, *a_flat, *a_fold;
/* Split arrays */
a_split = spc_array_split(sizeof(int), 8);
for (i = 0; i < a_split->num_elem; i++) {
val = i * 10;
printf("%#.8X ", val);
spc_array_set(a_split, 0, i, &val);
}
putchar('\n');
for (i = 0; i < a_split->num_elem; i++) {
if (!(p = (int *)spc_array_get(a_split, 0, i))) break;
printf("%#.8X ", *p);
}
putchar('\n');
/* Merged arrays */
a_merge = spc_array_merge(sizeof(int), 4, 8);
for (i = 0; i < 4; i++) {
val = (i * 12) / 3;
printf("%#.8X ", val);
spc_array_set(a_merge, 0, i, &val);
}
putchar('\n');
for (i = 0; i < 8; i++) {
val = (i * 2) + 10;
printf("%#.8X ", val);
spc_array_set(a_merge, 1, i, &val);
}
putchar('\n');
for (i = 0; i < 4; i++) {
if (!(p = (int *)spc_array_get(a_merge, 0, i))) break;
printf("%#.8X ", *p);
}
putchar('\n');
for (i = 0; i < 8; i++) {
if (!(p = (int *)spc_array_get(a_merge, 1, i))) break;
printf("%#.8X ", *p);
}
putchar('\n');
/* Folded arrays */
a_fold = spc_array_fold(sizeof(int), 32, 4);
for (i = 0; i < a_fold->num_elem; i++) {
val = ((i * 3) + 2) % 256;
printf("%#.2X ", val);
spc_array_set(a_fold, 0, i, &val);
}
putchar('\n');
for (i = 0; i < a_fold->num_elem; i++) {
if (!(p = (int *)spc_array_get(a_fold, 0, i))) break;
printf("%#.2X ", *p);
}
putchar('\n');
/* Flat arrays */
a_flat = spc_array_flat(sizeof(int), 6, 4);
for (i = 0; i < 4; i++) {
printf("Dimension %d: ", i);
for (j = 0; j < 6; j++) {
val = (i * j) << 2;
printf("%#.8X ", val);
spc_array_set(a_flat, i, j, &val);
}
putchar('\n');
}
for (i = 0; i < 4; i++) {
printf("Dimension %d: ", i );
for (j = 0; j < 6; j++) {
if (!(p = spc_array_get(a_flat, i, j))) break;
printf("%#.8X ", *p);
}
putchar('\n');
}
return 0;
}
 |
| [ Team LiB ] |
|
