tools/rules_optimize/rules_optimize.c

   1 /**
   2  * Author......: Jens Steube <jens.steube@gmail.com>
   3  * License.....: MIT
   4  */
   5
   6 #include <stdlib.h>
   7 #include <stdio.h>
   8 #include <string.h>
   9 #include <inttypes.h>
  10 #include <strings.h>
  11 #include <stdlib.h>
  12
  13 #define MIN_FUNCTIONS 1
  14 #define MAX_FUNCTIONS 5
  15
  16 int max_len = 0;
  17
  18 #include "cpu_rules.h"
  19
  20 typedef struct
  21 {
  22   char rule_buf[BLOCK_SIZE];
  23   int  rule_len;
  24
  25 } rule_t;
  26
  27 static int cmp (const void *p1, const void *p2)
  28 {
  29   rule_t *r1 = (rule_t *) p1;
  30   rule_t *r2 = (rule_t *) p2;
  31
  32   return r1->rule_len - r2->rule_len;
  33 }
  34
  35 int process_block (int o[BLOCK_SIZE], char *block_ptr[BLOCK_SIZE], int block_cnt, char *word_buf, char final_buf[BLOCK_SIZE], int final_len, char rule_buf[BLOCK_SIZE])
  36 {
  37   int last_o = o[0];
  38
  39   for (int i = 1; i < block_cnt; i++)
  40   {
  41     if (o[i] < last_o) return (0);
  42   }
  43
  44   memset (rule_buf, 0, BLOCK_SIZE);
  45
  46   strcat (rule_buf, block_ptr[o[0]]);
  47
  48   int i;
  49
  50   for (i = 1; i < block_cnt; i++)
  51   {
  52     strcat (rule_buf, " ");
  53
  54     strcat (rule_buf, block_ptr[o[i]]);
  55   }
  56
  57   char out_buf[BLOCK_SIZE];
  58
  59   memset (out_buf, 0, sizeof (out_buf));
  60
  61   int out_len = apply_rule_cpu (rule_buf, strlen (rule_buf), word_buf, strlen (word_buf), out_buf);
  62
  63   if (out_len == final_len)
  64   {
  65     if (memcmp (final_buf, out_buf, out_len) == 0) return (1);
  66   }
  67
  68   return 0;
  69 }
  70
  71 int next_permutation (int *o, int *p, int k)
  72 {
  73   p[k]--;
  74
  75   int j = k % 2 * p[k];
  76
  77   int tmp = o[j];
  78
  79   o[j] = o[k];
  80
  81   o[k] = tmp;
  82
  83   for (k = 1; p[k] == 0; k++) p[k] = k;
  84
  85   return k;
  86 }
  87
  88 int main ()
  89 {
  90   FILE *fp = stdin;
  91
  92   char line_buf[BUFSIZ];
  93
  94   while (!feof (fp))
  95   {
  96     /*
  97      * line
  98      */
  99
 100     char *line_ptr = fgets (line_buf, BUFSIZ, fp);
 101
 102     if (line_ptr == NULL) continue;
 103
 104     int line_len = strlen (line_ptr);
 105
 106     if (line_len && line_ptr[line_len - 1] == '\n') line_len--;
 107     if (line_len && line_ptr[line_len - 1] == '\r') line_len--;
 108
 109     line_ptr[line_len] = 0;
 110
 111     /*
 112      * split
 113      */
 114
 115     char *word_buf = line_ptr;
 116
 117     char *sep = strchr (line_ptr, ':');
 118
 119     if (sep == NULL) continue;
 120
 121     *sep = 0;
 122
 123     int word_len = sep - word_buf;
 124
 125     if (strstr (word_buf, "$HEX[")) continue; // not yet supported
 126
 127     char *rule_buf = sep + 1;
 128
 129     if (strchr (rule_buf, ':')) continue; // another one? ignore line
 130
 131     /*
 132      * final
 133      */
 134
 135     char final_buf[BLOCK_SIZE];
 136
 137     memset (final_buf, 0, sizeof (final_buf));
 138
 139     int final_len = apply_rule_cpu (rule_buf, strlen (rule_buf), word_buf, strlen (word_buf), final_buf);
 140
 141     if (final_len < 0) continue;
 142
 143     if ((final_len == word_len) && (memcmp (word_buf, final_buf, final_len)) == 0) continue;
 144
 145     /*
 146      * split into blocks
 147      */
 148
 149     char *block_ptr[BLOCK_SIZE];
 150     int   block_cnt = 0;
 151
 152     char *ptr = rule_buf;
 153
 154     for (char *next = NULL; (next = strchr (ptr, ' ')) != NULL; ptr = next + 1)
 155     {
 156       if (next[1] == ' ') next++;
 157
 158       *next = 0;
 159
 160       block_ptr[block_cnt] = ptr;
 161
 162       block_cnt++;
 163     }
 164
 165     block_ptr[block_cnt] = ptr;
 166
 167     block_cnt++;
 168
 169     if (block_cnt < MIN_FUNCTIONS) continue; // to many
 170     if (block_cnt > MAX_FUNCTIONS) continue; // to many
 171
 172     /*
 173      * permute blocks, this where the real work starts..
 174      */
 175
 176     int o[BLOCK_SIZE];
 177     int p[BLOCK_SIZE];
 178
 179     for (int i = 0; i < block_cnt + 1; i++)
 180     {
 181       o[i] = i;
 182       p[i] = i;
 183     }
 184
 185     int k = 1;
 186
 187     rule_t *rules_buf = (rule_t *) calloc (120 * MAX_FUNCTIONS, sizeof (rule_t)); // 5! = 120, so its guaranteed
 188     int     rules_cnt = 0;
 189
 190     char rule_out_buf[BLOCK_SIZE];
 191
 192     for (int i0 = 0, i1 = 1; i0 < block_cnt; i0++, i1++)
 193     {
 194       if (process_block (o, block_ptr, i1, word_buf, final_buf, final_len, rule_out_buf) == 1)
 195       {
 196         memcpy (rules_buf[rules_cnt].rule_buf, rule_out_buf, BLOCK_SIZE);
 197
 198         rules_buf[rules_cnt].rule_len = i1;
 199
 200         rules_cnt++;
 201       }
 202     }
 203
 204     if (block_cnt >= 2)
 205     {
 206       while ((k = next_permutation (o, p, k)) != block_cnt)
 207       {
 208         for (int i0 = 0, i1 = 1; i0 < block_cnt; i0++, i1++)
 209         {
 210           if (process_block (o, block_ptr, i1, word_buf, final_buf, final_len, rule_out_buf) == 1)
 211           {
 212             memcpy (rules_buf[rules_cnt].rule_buf, rule_out_buf, BLOCK_SIZE);
 213
 214             rules_buf[rules_cnt].rule_len = i1;
 215
 216             rules_cnt++;
 217           }
 218         }
 219       }
 220
 221       for (int i0 = 0, i1 = 1; i0 < block_cnt; i0++, i1++)
 222       {
 223         if (process_block (o, block_ptr, i1, word_buf, final_buf, final_len, rule_out_buf) == 1)
 224         {
 225           memcpy (rules_buf[rules_cnt].rule_buf, rule_out_buf, BLOCK_SIZE);
 226
 227           rules_buf[rules_cnt].rule_len = i1;
 228
 229           rules_cnt++;
 230         }
 231       }
 232     }
 233
 234     /**
 235      * sort and output the ones with the less length
 236      */
 237
 238     qsort (rules_buf, rules_cnt, sizeof (rule_t), cmp);
 239
 240     int first_len = rules_buf[0].rule_len;
 241
 242     for (int i = 0; i < rules_cnt; i++)
 243     {
 244       rule_t *rule_buf = &rules_buf[i];
 245
 246       if (rule_buf->rule_len > first_len) break;
 247
 248       puts (rule_buf->rule_buf);
 249     }
 250
 251     free (rules_buf);
 252   }
 253
 254   return 0;
 255 }