C filter wiretest data, dynamic arrays, structs

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#ifdef BUILD_64
# define BITS_PER_LONG 64
#else
# define BITS_PER_LONG 32
#endif

#define LMAX 64

typedef struct {
    unsigned short data;
    char label[5];
} wtest;

char **realloc_char (char **p, size_t *n);
void free_cdp (char **p);
char *binstr (unsigned long n, size_t sz);

int main (int argc, char **argv) {

    if (argc < 2 ) {
        fprintf (stderr, "error: insufficient input, usage: %s <filename>\n", argv[0]);
        return 1;
    }

    char **array = NULL;        /* array of pointer to hold lines   */
    char *ln = NULL;            /* NULL forces getline to allocate  */
    size_t n = 0;               /* mem for ln (0 - getline decides) */
    ssize_t nchr = 0;           /* number of chars actually read    */
    size_t idx = 0;             /* index of lines read from file    */
    size_t it = 0;              /* general loop iterator variable   */
    size_t lmax = LMAX;         /* reallocation limit variable      */
    FILE *fp = NULL;            /* file pointer for input file      */

    if (!(fp = fopen (argv[1], "r"))) { /* open file name given     */
        fprintf (stderr, "error: file open failed '%s'.", argv[1]);
        return 1;
    }

    /* allocate LMAX pointers to char* for lines in file */
    if (!(array = calloc (LMAX, sizeof *array))) {
        fprintf (stderr, "error: memory allocation failed.");
        return 1;
    }

    /* read each line in file */
    while ((nchr = getline (&ln, &n, fp)) != -1)
    {
        while (nchr > 0 && (ln[nchr-1] == '\n' || ln[nchr-1] == '\r'))
            ln[--nchr] = 0;     /* strip newline or carriage return */

        if (!(array[idx] = strdup (ln))) { /* alloc/copy into array */
            fprintf (stderr, "error: strdup line '%zu' failed. virtual memory exhausted.\n", idx);
            return 1;
        }

        idx++;              /* increment line index */

        if (idx == lmax)    /* realloc as required  */
            array = realloc_char (array, &lmax);
    }

    if (fp) fclose (fp);    /* read done close file */
    if (ln) free (ln);      /* free line buffer mem */

    printf ("\nThe original contents of file '%s':\n\n", argv[1]);

    while (array[it])   /* note ability to iterate over only filled strings */
        printf ("%s\n", array[it++]); /* calloc to inits pointers to NULL   */
    printf ("\n");      /* alternative iteration is 'for (i=0; i<idx; i++)' */

    /*  optimize 14 bits, all bits on is hex 3FFF, or decimal 16383. Easy approach
        is to read into array of struct containing bitfield to allow bitwise 'or'
        of testbits to determine combination that equals 3FFF (have all bits on)
    */

    wtest *test = NULL;     /* declare wtest ptr & allocate idx-1 elements  */
    if (!(test = calloc (idx -1, sizeof *test))) {
        fprintf (stderr, "error: memory allocation failed.");
        return 1;
    }

    it = 1;                 /* skip header line     */
    while (array[it])       /* for each line        */
    {
        unsigned short sum = 0;
        strncpy (test[it-1].label, array[it], 4);   /* copy data label  */
        test[it-1].label[5] = 0;            /* null-terminate string    */
        char *p = strrchr (array[it], 0);   /* start at end of string   */
        unsigned char bit = 0;              /* simple shift counter     */

        while (p > array[it] + 4)   /* read in reverse for proper shift */
        {
            if (*p == '1') {        /* if '1', add (1 << bits) to sum   */
                sum += 1 << bit;
                bit++;
            }
            if (*p == '0') bit++;   /* if '0', just incread bit count   */
            p--;                    /* decrement pointer, to next char  */
        }
        test[it-1].data = sum;  /* save sum in struct array */
        it++;
    }

    /* verify that struct array holds correct data values   */
    printf ("\nThe bitfield sums for each test are:\n\n");

    for (it = 0; it < idx - 1; it++)    /* note (idx - 1)   */
        printf (" %-8s  %4hu  %s\n", test[it].label,
                test[it].data,
                binstr(test[it].data, 14));

    /*  now to find which combination will turn all bits on, test each
        permutation of size capable of turning all bits on. (this can
        be sticky, because you don't know how many will be required so
        you may end up tesing millions of permutations) Let's start by
        elimination rows fully included in others and then adding rows
        until we get to 3FFF.
    */

    /* create an array to hold result rows/allocate idx pointers */
    char **results = NULL;
    if (!(results = calloc (idx, sizeof *results))) {
        fprintf (stderr, "error: memory allocation failed.");
        return 1;
    }

    /* this is where work is still needed filtering out data with
       the same bits that are included in other lines. One approach
       is to compare the population of 1's lesser included situation
       and keep the number with the greatest population. This would
       further reduce the results to 5 (by tossing out 1) and may get
       you all the way to 4, although I suspect more is needed
    */
    printf ("\nTesting for minimum elements with unsorted array:\n\n");
    unsigned short sum = 0;
    size_t ridx = 0;
    size_t i = 0;
    unsigned char dup = 0;
    for (it = 0; it < idx - 1; it++)
    {
        dup = 0;
        for (i = 0; i < it; i++) {
            if (test[i].data == test[it].data)
                dup = 1;    /* duplicate value  */
            if (test[i].data == (test[i].data | test[it].data))
                dup = 1;    /* duplicate bits   */
        }
        if (dup) continue;
        printf (" ( %5hu | %5hu )  ", sum, test[it].data);
        sum |= test[it].data;
        printf (" sum: %s  (0x%04x)\n", binstr (sum, 14), sum);
        results[ridx++] = strdup (array[it+1]);
        if (sum == 0x3fff) break;
    }

    printf ("\nA combination of the first '%zu' distinct rows test all values.\n\n", ridx);

    printf ("The unsorted distinct rows that test all values are:\n\n");
    printf ("%s\n", array[0]);  /* print header row */
    it = 0;
    while (results[it])
        printf ("%s\n", results[it++]);
    printf ("\n");

    free_cdp (array);       /* free lines from file */
    free_cdp (results);     /* free results array   */
    free (test);            /* free array of struct */

    return 0;
}

/** realloc an array of pointers to strings setting memory to 0.
 *  reallocate an array of character arrays setting
 *  newly allocated memory to 0 to allow iteration
 */
char **realloc_char (char **p, size_t *n)
{
#ifdef DEBUG
    printf ("\n  reallocating %zu to %zu (size: %lu)\n", *n, *n * 2, 2 * *n * sizeof *p);
#endif
    char **tmp = realloc (p, 2 * *n * sizeof *p);
    if (!tmp) {
        fprintf (stderr, "Error: struct reallocation failure.\n");
        exit (EXIT_FAILURE);
    }
    p = tmp;
    memset (p + *n, 0, *n * sizeof *p); /* memset new ptrs 0 */
    *n *= 2;

    return p;
}

/* free double-char pointer allocation */
void free_cdp (char **p)
{
    if (!p) return;
    size_t i = 0;
    while (p[i])
        free (p[i++]);
    free (p);
}

/** returns pointer to binary representation of 'n' zero padded to 'sz'.
 *  returns pointer to string contianing binary representation of
 *  unsigned 64-bit (or less ) value zero padded to 'sz' digits.
 */
char *binstr (unsigned long n, size_t sz)
{
    static char s[BITS_PER_LONG + 1] = {0};
    char *p = s + BITS_PER_LONG;
    register size_t i;

    for (i = 0; i < sz; i++)
        *(--p) = (n>>i & 1) ? '1' : '0';

    return p;
}