Advertisement
drankinatty

C filter wiretest data, dynamic arrays, structs

May 20th, 2015
425
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.85 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #if defined(__LP64__) || defined(_LP64)
  6. # define BUILD_64   1
  7. #endif
  8.  
  9. #ifdef BUILD_64
  10. # define BITS_PER_LONG 64
  11. #else
  12. # define BITS_PER_LONG 32
  13. #endif
  14.  
  15. #define LMAX 64
  16.  
  17. typedef struct {
  18.     unsigned short data;
  19.     char label[5];
  20. } wtest;
  21.  
  22. char **realloc_char (char **p, size_t *n);
  23. void free_cdp (char **p);
  24. char *binstr (unsigned long n, size_t sz);
  25.  
  26. int main (int argc, char **argv) {
  27.  
  28.     if (argc < 2 ) {
  29.         fprintf (stderr, "error: insufficient input, usage: %s <filename>\n", argv[0]);
  30.         return 1;
  31.     }
  32.  
  33.     char **array = NULL;        /* array of pointer to hold lines   */
  34.     char *ln = NULL;            /* NULL forces getline to allocate  */
  35.     size_t n = 0;               /* mem for ln (0 - getline decides) */
  36.     ssize_t nchr = 0;           /* number of chars actually read    */
  37.     size_t idx = 0;             /* index of lines read from file    */
  38.     size_t it = 0;              /* general loop iterator variable   */
  39.     size_t lmax = LMAX;         /* reallocation limit variable      */
  40.     FILE *fp = NULL;            /* file pointer for input file      */
  41.  
  42.     if (!(fp = fopen (argv[1], "r"))) { /* open file name given     */
  43.         fprintf (stderr, "error: file open failed '%s'.", argv[1]);
  44.         return 1;
  45.     }
  46.    
  47.     /* allocate LMAX pointers to char* for lines in file */
  48.     if (!(array = calloc (LMAX, sizeof *array))) {
  49.         fprintf (stderr, "error: memory allocation failed.");
  50.         return 1;
  51.     }
  52.  
  53.     /* read each line in file */
  54.     while ((nchr = getline (&ln, &n, fp)) != -1)
  55.     {
  56.         while (nchr > 0 && (ln[nchr-1] == '\n' || ln[nchr-1] == '\r'))
  57.             ln[--nchr] = 0;     /* strip newline or carriage return */
  58.        
  59.         if (!(array[idx] = strdup (ln))) { /* alloc/copy into array */
  60.             fprintf (stderr, "error: strdup line '%zu' failed. virtual memory exhausted.\n", idx);
  61.             return 1;
  62.         }
  63.        
  64.         idx++;              /* increment line index */
  65.  
  66.         if (idx == lmax)    /* realloc as required  */
  67.             array = realloc_char (array, &lmax);
  68.     }
  69.  
  70.     if (fp) fclose (fp);    /* read done close file */
  71.     if (ln) free (ln);      /* free line buffer mem */
  72.  
  73.     printf ("\nThe original contents of file '%s':\n\n", argv[1]);
  74.  
  75.     while (array[it])   /* note ability to iterate over only filled strings */
  76.         printf ("%s\n", array[it++]); /* calloc to inits pointers to NULL   */
  77.     printf ("\n");      /* alternative iteration is 'for (i=0; i<idx; i++)' */
  78.    
  79.     /*  optimize 14 bits, all bits on is hex 3FFF, or decimal 16383. Easy approach
  80.         is to read into array of struct containing bitfield to allow bitwise 'or'
  81.         of testbits to determine combination that equals 3FFF (have all bits on)
  82.     */
  83.    
  84.     wtest *test = NULL;     /* declare wtest ptr & allocate idx-1 elements  */
  85.     if (!(test = calloc (idx -1, sizeof *test))) {
  86.         fprintf (stderr, "error: memory allocation failed.");
  87.         return 1;
  88.     }
  89.  
  90.     it = 1;                 /* skip header line     */
  91.     while (array[it])       /* for each line        */
  92.     {
  93.         unsigned short sum = 0;
  94.         strncpy (test[it-1].label, array[it], 4);   /* copy data label  */
  95.         test[it-1].label[5] = 0;            /* null-terminate string    */
  96.         char *p = strrchr (array[it], 0);   /* start at end of string   */
  97.         unsigned char bit = 0;              /* simple shift counter     */
  98.        
  99.         while (p > array[it] + 4)   /* read in reverse for proper shift */
  100.         {
  101.             if (*p == '1') {        /* if '1', add (1 << bits) to sum   */
  102.                 sum += 1 << bit;
  103.                 bit++;
  104.             }
  105.             if (*p == '0') bit++;   /* if '0', just incread bit count   */
  106.             p--;                    /* decrement pointer, to next char  */
  107.         }
  108.         test[it-1].data = sum;  /* save sum in struct array */
  109.         it++;
  110.     }
  111.    
  112.     /* verify that struct array holds correct data values   */
  113.     printf ("\nThe bitfield sums for each test are:\n\n");
  114.    
  115.     for (it = 0; it < idx - 1; it++)    /* note (idx - 1)   */
  116.         printf (" %-8s  %4hu  %s\n", test[it].label,
  117.                 test[it].data,
  118.                 binstr(test[it].data, 14));
  119.    
  120.     /*  now to find which combination will turn all bits on, test each
  121.         permutation of size capable of turning all bits on. (this can
  122.         be sticky, because you don't know how many will be required so
  123.         you may end up tesing millions of permutations) Let's start by
  124.         elimination rows fully included in others and then adding rows
  125.         until we get to 3FFF.
  126.     */
  127.    
  128.     /* create an array to hold result rows/allocate idx pointers */
  129.     char **results = NULL;
  130.     if (!(results = calloc (idx, sizeof *results))) {
  131.         fprintf (stderr, "error: memory allocation failed.");
  132.         return 1;
  133.     }
  134.  
  135.     /* this is where work is still needed filtering out data with
  136.        the same bits that are included in other lines. One approach
  137.        is to compare the population of 1's lesser included situation
  138.        and keep the number with the greatest population. This would
  139.        further reduce the results to 5 (by tossing out 1) and may get
  140.        you all the way to 4, although I suspect more is needed
  141.     */
  142.     printf ("\nTesting for minimum elements with unsorted array:\n\n");
  143.     unsigned short sum = 0;
  144.     size_t ridx = 0;
  145.     size_t i = 0;
  146.     unsigned char dup = 0;
  147.     for (it = 0; it < idx - 1; it++)
  148.     {
  149.         dup = 0;
  150.         for (i = 0; i < it; i++) {
  151.             if (test[i].data == test[it].data)
  152.                 dup = 1;    /* duplicate value  */
  153.             if (test[i].data == (test[i].data | test[it].data))
  154.                 dup = 1;    /* duplicate bits   */
  155.         }
  156.         if (dup) continue;
  157.         printf (" ( %5hu | %5hu )  ", sum, test[it].data);
  158.         sum |= test[it].data;
  159.         printf (" sum: %s  (0x%04x)\n", binstr (sum, 14), sum);
  160.         results[ridx++] = strdup (array[it+1]);
  161.         if (sum == 0x3fff) break;
  162.     }
  163.    
  164.     printf ("\nA combination of the first '%zu' distinct rows test all values.\n\n", ridx);
  165.    
  166.     printf ("The unsorted distinct rows that test all values are:\n\n");
  167.     printf ("%s\n", array[0]);  /* print header row */
  168.     it = 0;
  169.     while (results[it])
  170.         printf ("%s\n", results[it++]);
  171.     printf ("\n");
  172.    
  173.     free_cdp (array);       /* free lines from file */
  174.     free_cdp (results);     /* free results array   */
  175.     free (test);            /* free array of struct */
  176.    
  177.     return 0;
  178. }
  179.  
  180. /** realloc an array of pointers to strings setting memory to 0.
  181.  *  reallocate an array of character arrays setting
  182.  *  newly allocated memory to 0 to allow iteration
  183.  */
  184. char **realloc_char (char **p, size_t *n)
  185. {
  186. #ifdef DEBUG
  187.     printf ("\n  reallocating %zu to %zu (size: %lu)\n", *n, *n * 2, 2 * *n * sizeof *p);
  188. #endif
  189.     char **tmp = realloc (p, 2 * *n * sizeof *p);
  190.     if (!tmp) {
  191.         fprintf (stderr, "Error: struct reallocation failure.\n");
  192.         exit (EXIT_FAILURE);
  193.     }
  194.     p = tmp;
  195.     memset (p + *n, 0, *n * sizeof *p); /* memset new ptrs 0 */
  196.     *n *= 2;
  197.  
  198.     return p;
  199. }
  200.  
  201. /* free double-char pointer allocation */
  202. void free_cdp (char **p)
  203. {
  204.     if (!p) return;
  205.     size_t i = 0;
  206.     while (p[i])
  207.         free (p[i++]);
  208.     free (p);
  209. }
  210.  
  211. /** returns pointer to binary representation of 'n' zero padded to 'sz'.
  212.  *  returns pointer to string contianing binary representation of
  213.  *  unsigned 64-bit (or less ) value zero padded to 'sz' digits.
  214.  */
  215. char *binstr (unsigned long n, size_t sz)
  216. {
  217.     static char s[BITS_PER_LONG + 1] = {0};
  218.     char *p = s + BITS_PER_LONG;
  219.     register size_t i;
  220.  
  221.     for (i = 0; i < sz; i++)
  222.         *(--p) = (n>>i & 1) ? '1' : '0';
  223.  
  224.     return p;
  225. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement