ndeql.c

   1 #include <errno.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <time.h>
   6
   7 #define RD_BLOCK_SZ 4096
   8
   9 #define RAND   '?'
  10 #define NEXT   '='
  11 #define DEC    '-'
  12 #define INC    '_'
  13 #define BEGIN  '\\'
  14 #define END    '/'
  15 #define GROW   '!'
  16 #define INPUT  '&'
  17 #define OUTPUT '*'
  18
  19 #define MAKE_ARRAY(arr, arr_sz_var) {                   \
  20     arr = malloc(arr_sz_var * sizeof *arr);             \
  21     if (!arr)                                           \
  22       return errno;                                     \
  23   }
  24
  25 #define GROW_ARRAY(arr, arr_sz) {                       \
  26     arr_sz *= 2;                                        \
  27     arr = realloc(arr, arr_sz * sizeof *arr);           \
  28     if (!arr)                                           \
  29       return errno;                                     \
  30   }
  31
  32 char *vars;
  33 size_t vars_num;
  34 size_t vars_storage_sz;
  35
  36 /*
  37  * queue is implemented as a circularized array with continuously
  38  * advancing head/tail pointers. queue_head shall point to the first
  39  * position at which a `real' value is stored, queue_tail shall point
  40  * to the first position past queue_head at which a `real' value is
  41  * not stored
  42  */
  43 char *queue;
  44 char *queue_head;
  45 char *queue_tail;
  46 size_t queue_storage_sz;
  47 size_t queue_elem_num;
  48
  49 /*
  50  * the program source is slurped entirely into this array so that
  51  * BEGIN/END jumping may work correctly, though perhaps in the future
  52  * an option may be added to do this through fseek() calls instead
  53  */
  54 char *prog;
  55 size_t prog_storage_sz;
  56 size_t prog_len;
  57
  58 /*
  59  * begin and end points are stored, interleaved, in an array (A[2k] a
  60  * begin, A[2k+1] its matching end) for faster lookup than a linear
  61  * search (about half of the time). jump_pair_num * 2 >
  62  * jump_storage_sz is the condition that must be avoided
  63  *
  64  * TODO: it now seems clear that this should be reversed, so that the
  65  * ends are in monotonic order, with the begins unordered
  66  */
  67 const char **jumps;
  68 size_t jump_storage_sz;
  69 size_t jump_pair_num;
  70
  71 /* program handling */
  72 int read_in(FILE * input)
  73 {
  74   int read_bytes;
  75   char *c_prog;
  76
  77   prog_storage_sz = RD_BLOCK_SZ;
  78   MAKE_ARRAY(prog, prog_storage_sz);
  79   c_prog = prog;
  80
  81   while ((read_bytes =
  82           fread(c_prog, sizeof *prog, RD_BLOCK_SZ, input)) == RD_BLOCK_SZ) {
  83     prog_storage_sz += RD_BLOCK_SZ;
  84     prog_len = prog_storage_sz;
  85     prog = realloc(prog, prog_storage_sz * sizeof *prog);
  86     if (!prog)
  87       return errno;
  88     c_prog = prog + (prog_storage_sz - RD_BLOCK_SZ);
  89   }
  90
  91   prog_len += read_bytes;
  92   *(prog + prog_len) = '\0';
  93
  94   return 0;
  95 }
  96
  97 int build_jump_list(void)
  98 {
  99   const char *pc = prog;
 100
 101   /*
 102    * a stack for where the next end gets stored, so
 103    * ends_storage_stack[ends_num - 1 - 2] is a pointer to within
 104    * jumps that should be filled by a pointer to within prog that
 105    * matches a begin that is two matching levels away from the current
 106    * context
 107    */
 108   const char ***ends_storage_stack;
 109   size_t ends_num = 0;
 110   size_t ends_storage_sz = 4;
 111
 112   int lineno = 0;
 113   int charpos = 0;
 114
 115   MAKE_ARRAY(ends_storage_stack, ends_storage_sz);
 116
 117   jump_pair_num = 0;
 118   jump_storage_sz = 8;
 119   MAKE_ARRAY(jumps, jump_storage_sz);
 120
 121   while (*pc != '\0') {
 122     if (*pc == BEGIN) {
 123       if (ends_num + 1 >= ends_storage_sz) {
 124         GROW_ARRAY(ends_storage_stack, ends_storage_sz);
 125       }
 126
 127       if (2 * (jump_pair_num + 1) >= jump_storage_sz) {
 128         GROW_ARRAY(jumps, jump_storage_sz);
 129       }
 130
 131       /*
 132        * store this point as a begin, and record the spot at which to
 133        * fill in the matching end
 134        */
 135       *(ends_storage_stack + ends_num) = jumps + (2 * jump_pair_num) + 1;
 136       *(jumps + 2 * jump_pair_num) = pc;
 137       ends_num++;
 138       jump_pair_num++;
 139     } else if (*pc == END) {
 140       if (ends_num <= 0) {
 141         fprintf(stderr, "Unmatched %c at line %d, char %d\n", END, lineno,
 142                 charpos);
 143         return -1;
 144       }
 145
 146       if (2 * (jump_pair_num + 1) >= jump_storage_sz) {
 147         GROW_ARRAY(jumps, jump_storage_sz);
 148       }
 149
 150       /*
 151        * store this point as an end in the correct point in the jump
 152        * list, which was precomputed when the begin was seen
 153        */
 154       **(ends_storage_stack + ends_num - 1) = pc;
 155       ends_num--;
 156     } else if (*pc == '\n') {
 157       lineno++;
 158       charpos = 0;
 159     } else {
 160       charpos++;
 161     }
 162     pc++;
 163   }
 164
 165   if (ends_num != 0) {
 166     fprintf(stderr, "%lu unmatched %c detected", (unsigned long)ends_num,
 167             BEGIN);
 168     return -1;
 169   }
 170
 171   return 0;
 172 }
 173
 174 const char *matching_end_for(const char *begin)
 175 {
 176   size_t cur_jump;
 177   size_t search_incr;
 178   int diff;
 179
 180   /*
 181    * quick checks that allow range to be a little sloppy
 182    */
 183   if (jumps[(2 * 0) + 0] == begin)
 184     return jumps[(2 * 0) + 1];
 185   if (jumps[(2 * jump_pair_num) + 0] == begin)
 186     return jumps[(2 * jump_pair_num) + 1];
 187
 188   /*
 189    * binary search, since it is known that begins are laid out in
 190    * increasing order in jump list
 191    */
 192   cur_jump = jump_pair_num / 2;
 193   search_incr = jump_pair_num / 4;
 194
 195   while (search_incr >= 0) {
 196     diff = (int)(jumps[(2 * cur_jump) + 0] - begin);
 197     if (search_incr == 0 || diff == 0)
 198       return jumps[(2 * cur_jump) + 1];
 199     else if (diff < 0)
 200       cur_jump += search_incr;
 201     else
 202       cur_jump -= search_incr;
 203
 204     search_incr /= 2;
 205   }
 206
 207   return NULL;
 208 }
 209
 210 const char *matching_begin_for(const char *end)
 211 {
 212   size_t cur_jump = 0;
 213
 214   /*
 215    * ends are completely unordered, so nothing for it but linear
 216    */
 217   while (cur_jump < jump_pair_num) {
 218     if (jumps[(2 * cur_jump) + 1] == end)
 219       break;
 220     cur_jump++;
 221   }
 222   return jumps[(2 * cur_jump) + 0];
 223
 224 }
 225
 226 /* queue handling */
 227 int enqueue(const char c)
 228 {
 229   queue_elem_num++;
 230
 231   /*
 232    * store value and advance tail pointer, wrapping if needed
 233    */
 234   *queue_tail = c;
 235   if (queue_tail - queue + 1 == queue_storage_sz)
 236     queue_tail = queue;
 237   else
 238     queue_tail++;
 239
 240   /*
 241    * resize the buffer if needed
 242    */
 243   if (queue_elem_num == queue_storage_sz) {
 244
 245     queue_storage_sz *= 2;
 246
 247     if (queue_head == queue) {
 248       /*
 249        * in the easy case, re-use existing memory
 250        */
 251       queue = realloc(queue, queue_storage_sz * sizeof *queue);
 252       if (!queue)
 253         return errno;
 254       queue_head = queue;
 255       queue_tail = queue + queue_elem_num;
 256     } else {
 257       /*
 258        * in the non-trivial case, neatly re-arrange everything to a
 259        * new buffer.
 260        */
 261       char *new_queue;
 262
 263       MAKE_ARRAY(new_queue, queue_storage_sz);
 264
 265       memcpy(new_queue, queue_head, queue_elem_num - (queue_head - queue));
 266       memcpy(new_queue, queue, queue_head - queue);
 267       queue_head = queue = new_queue;
 268       queue_tail = queue_head + queue_elem_num;
 269     }
 270   }
 271
 272   return 0;
 273 }
 274
 275 char dequeue(void)
 276 {
 277   char to_ret = *queue_head;
 278
 279   queue_elem_num--;
 280
 281   if (queue_head - queue + 1 == queue_storage_sz)
 282     queue_head = queue;
 283   else
 284     queue_head++;
 285
 286   return to_ret;
 287 }
 288
 289 /* var handling */
 290 char *sel_var(void)
 291 {
 292   return vars + (rand() % vars_num);
 293 }
 294
 295 /* instruction handling */
 296 int execute(void)
 297 {
 298   const char *pc = prog;
 299   char *tvar;
 300   int c;
 301   int ret = 0;
 302
 303   while (*pc != '\0') {
 304     switch (*pc) {
 305     case RAND:
 306       if (vars_num >= vars_storage_sz) {
 307         GROW_ARRAY(vars, vars_storage_sz);
 308       }
 309       vars_num++;
 310       vars[vars_num - 1] = 0;
 311       break;
 312     case NEXT:
 313       tvar = sel_var();
 314       if ((ret = enqueue(*tvar)) != 0)
 315         return ret;
 316       *tvar = dequeue();
 317       break;
 318     case DEC:
 319       tvar = sel_var();
 320       if (*tvar == -128)
 321         *tvar = 127;
 322       else
 323         (*tvar)--;
 324       break;
 325     case INC:
 326       tvar = sel_var();
 327       if (*tvar == 127)
 328         *tvar = -128;
 329       else
 330         (*tvar)++;
 331       break;
 332     case BEGIN:
 333
 334 #ifdef LESS_PROBLEMATIC
 335       c = 0;
 336       {
 337         size_t varidx = 0;
 338
 339         while (c == 0 && varidx < vars_num)
 340           c = vars[varidx++] != 0;
 341       }
 342       if (c == 0)
 343         pc = matching_end_for(pc);
 344 #else
 345       tvar = sel_var();
 346       if (*tvar == 0)
 347         pc = matching_end_for(pc);
 348 #endif
 349
 350       break;
 351     case END:
 352       /*
 353        * this `- 1' may be an error from a faulty reading of the spec
 354        */
 355       pc = matching_begin_for(pc) - 1;
 356       break;
 357     case GROW:
 358       if ((ret = enqueue(0)) != 0)
 359         return ret;
 360       break;
 361     case INPUT:
 362       c = getchar();
 363       if (c == EOF)
 364         ret = enqueue(0);
 365       else
 366         ret = enqueue((char)c);
 367       if (ret != 0)
 368         return ret;
 369       break;
 370     case OUTPUT:
 371       tvar = sel_var();
 372       putchar(*tvar);
 373       if ((ret = enqueue(*tvar)) != 0)
 374         return ret;
 375       *tvar = dequeue();
 376       break;
 377     }
 378
 379     pc++;
 380   }
 381
 382   return 0;
 383 }
 384
 385 int main(int argc, char **argv)
 386 {
 387   FILE *input;
 388
 389   if (argc != 2) {
 390     fprintf(stderr, "Usage: %s INPUT_FILE\n", argv[0]);
 391     return -1;
 392   }
 393
 394   srand(time(NULL));
 395
 396   vars_num = 3;
 397   vars_storage_sz = 16;
 398   if (!(vars = calloc(vars_storage_sz, sizeof *vars))) {
 399     perror("Could not initialize internal state");
 400     return ENOMEM;
 401   }
 402
 403   queue_storage_sz = 128;
 404   queue_elem_num = 0;
 405   if (!
 406       (queue_head = queue_tail = queue =
 407        malloc(queue_storage_sz * sizeof *queue))) {
 408     perror("Could not initialize internal state");
 409     return ENOMEM;
 410   }
 411
 412   jump_storage_sz = 2;
 413   jump_pair_num = 0;
 414   if (!(jumps = malloc(jump_storage_sz * sizeof *jumps))) {
 415     perror("Could not initialize internal state");
 416     return ENOMEM;
 417   }
 418
 419   if (!(input = fopen(argv[1], "r"))) {
 420     perror("Could not open input file");
 421     return errno;
 422   }
 423
 424   if (read_in(input) != 0) {
 425     perror("Could not fully read input file");
 426 #ifdef EFBIG
 427     return EFBIG;
 428 #else
 429     return 1;
 430 #endif
 431   }
 432
 433   if (build_jump_list() != 0) {
 434     /*
 435      * if errno is set, library error, otherwise syntax error
 436      */
 437     if (errno != 0) {
 438       perror("Could not initialize jump list");
 439       return errno;
 440     }
 441 #ifdef EINVAL
 442     return EINVAL;
 443 #else
 444     return 2;
 445 #endif
 446   }
 447
 448   if (execute() != 0) {
 449     perror("Error during execution");
 450     return errno;
 451   }
 452
 453   return 0;
 454 }