test_degenerate_switch.c

/* 
 * A silly little test program involving switches, loops, and gotos.
 * It's designed to emulate the kind of spaghetti-goto code produced by
 * PyPy for its bytecode interpretation loop.
 *
 * This program takes a string as command-line argument, counts the number
 * of zeros in the string, checks for the presence of the digits 1 through 4,
 * and prints its findings to stdout.  Example:
 *
 *   $> js test_degenerate_switch.js 00203
 *   6 CHARACTERS
 *   3 ZEROS
 *   THERE WAS NO 1
 *   THERE WAS A 2
 *   THERE WAS A 3
 *   THERE WAS NO 4
 *
 * It does this in a very silly way, essentially by treating the input string
 * as 'bytecode' and dispatching to a different target based on each character
 * in the string in turn.
 *
 * The resulting javascript generated by emscripten contains a "degenerate"
 * switch statement, that dispatches on the character to set a flag variable,
 * then checks each case of the flag variable using an if-else chain.
 * Structurally is looks something like this:
 *
 *   LOOP: while (1) {
 *     switch (input[i]) {
 *       case '0':
 *         flag = 1;
 *         break LOOP;
 *         break;
 *       case '1':
 *         flag = 2;
 *         break LOOP;
 *         break;
 *       ...etc...
 *     }
 *     i++;
 *   }
 *   if (flag == 1) {
 *     ...code for case 1...
 *   } else if (flag == 2) {
 *     ...code for case 2...
 *   }
 *
 * If the switch contained many cases, the resulting code would be very
 * inefficient.  It should be possible to fold the cases into the body of
 * the switch statement and avoid the second level of dispatch, like so:
 *
 *   LOOP: while (1) {
 *     switch (input[i]) {
 *       case '0':
 *         ...inline code for case 1...
 *         break LOOP;
 *         break;
 *       case '1':
 *         ...inline code for case 2...
 *         break LOOP;
 *         break;
 *       ...etc...
 *     }
 *     i++;
 *   }
 *
 */

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

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

  // Current position in the input string.
  int i=0;
  // Count of all 0 digits seen in the input.
  int c0=0;
  // Whether we have seen the digits 1 through 4.
  int b1=0, b2=0, b3=0, b4=0;

  char* digits;
  digits = argc[1];

  blockSWITCH:
    // Dispatch to handler code based on the current character in the string.
    switch (digits[i]) {
      case '0':
        goto block0;
      case '1':
        goto block1;
      case '2':
        goto block2;
      case '3':
        goto block3;
      case '4':
        goto block4;
      default:
        goto blockFINISH;
    }

  // If there's a '0', count all instances in the run in a tight loop.
  // When done, re-join the other branches at a block prior to the dispatcher.
  // This prevents some simplication of the looping structure.
  block0:
    while (1) {
      if (digits[i] != '0') {
        i--;
        goto blockNEXT;
      }
      c0++;
      i++;
    }

  // If there's a one, flag it and branch directly back to the start.
  // This prevents all branches from having a common jump target,
  // which would allow simplifaction of the looping structure.
  block1:
    b1 = 1;
    i++;
    goto blockSWITCH;

  // For other digits, just flag them and jump to common continuation point.
  block2:
    b2 = 1;
    goto blockNEXT;

  block3:
    b3 = 1;
    goto blockNEXT;

  block4:
    b4 = 1;
    goto blockNEXT;

  // Increment position and jump back to the dispatcher.
  blockNEXT:
    i++;
    goto blockSWITCH;

  // When done, print our findings to stdout.
  blockFINISH:
    printf("%d CHARCTERS\n", i);
    printf("%d ZEROS\n", c0);
    if (b1) printf("THERE WAS A 1\n"); else printf("THERE WAS NO 1\n");
    if (b2) printf("THERE WAS A 2\n"); else printf("THERE WAS NO 2\n");
    if (b3) printf("THERE WAS A 3\n"); else printf("THERE WAS NO 3\n");
    if (b4) printf("THERE WAS A 4\n"); else printf("THERE WAS NO 4\n");
    return 0;
}