From: reith_s@cs.uwa.oz.au (Sean A Reith)
Subject: interpret.c switch code rewritten...
Organization: Dept. Computer Science, University of Western Australia.
Date: Fri, 16 Oct 1992 15:45:24 GMT

( Failed to post this twice from my other account...  Anyway, here it is. )

gusar@uniwa.uwa.edu.au (Sean A Reith) writes:

Noticed a blinding error as I read through our article, blame it on the
time we wrote it...  Note this code is _untestested_, so typos may (and did)
exist.  (this is just a copy of the rewrite David and I did in responce
to the gamedriver thread, hit 'n' now unless you want that code).

Note that any credit for this code belongs to Amylaar, we basically just
changed the way it reads.  (We made a couple of minor changes, but don't
mention the war.)

>----- START OF CODE (the non-RLE version) -----

>/*
> * Switch interpreting code.
> * Uses a binary search which assumes the table size is 2^n-1,
> * so that we can use shift-lefts and shift-rights for speed.
> * Note: The actual table size is irrelevant (it handles 'padding' at the end).
> */

[ more #defines would have avoided this problem...  Better late than never. ]

/*
 * Switches have 7bytes of leading guff...
 * The first is the table type (and size as a power of 2).
 * The next two give the address of the start of the table.
 * The next two, the address to break to.
 * The last two, the 'default' address.
 */
#define TABLE_OFF	1
#define BREAK_OFF	3
#define DEFAULT_OFF	5

>/*
> * The size of each table entry.
> * The first four bytes are the value of the entry,
> * The last two are offsets, though some entries are paired, (for lookup
> *   tables, and ranges.  In paired entries, the first offset indicates
> *   type (and the fact that the entries are paired...).
> * eg (for range or lookup entry pair):
> *  <   4  > < 2> <   4  > < 2> bytes
> * +-------- ----+-------- ----+
> * | lower  |type| upper  |offs|
> * +-------- ----+-------- ----+
> * Type:
> *   0 : Offset is to lookup table.
> *   1 : The entry is the lower edge of a range.
> */
>#define ENTRY_SIZE 6
>#define LOOKUP_TABLE	0
>#define RANGE			1

>/*
> * Offsets in ranges/lookup tables.
> *   L_* is from the lower of the pair.
> *   U_* is from the upper of the pair.
> */
>#define L_TYPE		4
>#define L_OFFSET	10
>#define L_LOWER		0
>#define L_UPPER		6
>#define U_TYPE		-2
>#define U_OFFSET	4
>#define U_LOWER		-6
>#define U_UPPER		0

>/*
> * To make the copies clearer...
> * (And still handle machines that don't like non-word boundary word accesses)
> */
>#define COPY_SHORT(DST, SRC) bcopy((char *)(SRC), (char *)(DST), 2)
>#define COPY_LONG(DST, SRC) bcopy((char *)(SRC), (char *)(DST), 4)

>  extern char* findstring PROT((char*));
>  unsigned short offset,break_adr;
>  int win_width, /* the size of the next window width (middle of the middle) */
>      search_val,
>      mid_val, /* the value of the table at the current middle */
>      range_start; /* lower end of table values */
>  char *tab_mid, /* the table middle */
>       tab_size,
>       *end_tab; /* the top of the table */
>  /*
>   * Table of the initial window sizes.
>   * Each value is 2^n-1 * the size of each entry.
>   */
>  static short win_size[] = {
>       0*ENTRY_SIZE,    1*ENTRY_SIZE,    3*ENTRY_SIZE,    7*ENTRY_SIZE,
>      15*ENTRY_SIZE,   31*ENTRY_SIZE,   63*ENTRY_SIZE,  127*ENTRY_SIZE,
>     255*ENTRY_SIZE,  511*ENTRY_SIZE, 1023*ENTRY_SIZE, 2047*ENTRY_SIZE,
>    4095*ENTRY_SIZE, 8191*ENTRY_SIZE
>  };

>  COPY_SHORT(&offset, pc); /* set offset to the start of the table */

[ OOPS!  This should be: ]

  COPY_SHORT(&offset, pc+TABLE_OFF); /* set offset to start of table */

>  COPY_SHORT(&break_adr, pc+3); /* the offset to break to */

[ Better as: ]

  COPY_SHORT(&break_adr, pc+BREAK_OFF); /* extract the break address */

>  *--break_sp = break_adr;
>  /*
>   * If all the top four bits are set, then switching on a int
>   * (the lower 4 store the table size),
>   * otherwise the top 4 bits _are_ the table size
>   * (and switching on a string).
>   */
>  if ((tab_size = (EXTRACT_UCHAR(pc) >> 4)) != 0xf) { /* == string */
>    if (sp->type == T_NUMBER && !sp->u.number) {
>      /* special case: uninitalized string */
>      search_val = ZERO_AS_STR_CASE_LABEL;
>    } else if (sp->type == T_STRING) {
>      /* make it a shared string, so we can compare pointers */
>      switch(sp->string_type) {
>        case STRING_SHARED:
>          search_val = (int)sp->u.string;
>          break;
>        default:
>          search_val = (int)findstring(sp->u.string);
>          break;
>      }
>    } else {
>      bad_arg(1, F_SWITCH);
>    }
>  } else { /* == int */
>    if (sp->type != T_NUMBER) bad_arg(1, F_SWITCH);
>    search_val = sp->u.number;
>    tab_size = (int)pc[0] & 0xf ; /* the lower four bits store size of table */
>  }
>  pop_stack();
>  end_tab = current_prog->program + break_adr;
>  /* high table values indicate different switch formats */
>  if (tab_size > 14)
>     fatal("unsupported switch table format.\n");
>  if (tab_size == 14) { /* entire switch is a lookup table */
>    char *tab_start;

>    /* fastest switch format : lookup table */
>    tab_start = current_prog->program + offset;
>    COPY_LONG(&range_start, end_tab-4);
>    /*
>     * If the search_val is in the table, then
>     *   make search_val the offset into the lookup table
>     *   (the ENTRY_SIZE is 4 for lookup tables)
>     */
>    if (search_val >= range_start
>        && (tab_start + (search_val = (search_val - range_start)*sizeof(short)))
>            < (end_tab - 4)) { 
>      COPY_SHORT(&offset, tab_start+search_val);
>      if (offset) {
>        pc = current_prog->program + offset;
>        break;
>      }
>    }
>    /* default */
>    COPY_SHORT(&offset, pc+5);

[ Better as: ]

    COPY_SHORT(&offset, pc+DEFAULT_OFF);

>    pc = current_prog->program + offset;
>    break;
>  } 
>  tab_mid = current_prog->program + offset + win_size[tab_size];
>  win_width = (win_size[tab_size]+ENTRY_SIZE) >> 1;
>  if (win_width == ENTRY_SIZE/2) 
>    win_width = 0;
>  for(;;) {
>    COPY_LONG(&mid_val, tab_mid);
>    if (search_val < mid_val) {
>      if (win_width < ENTRY_SIZE) { /* leaf */
>        COPY_SHORT(&offset, tab_mid+U_TYPE);
>        /* F_BREAK is required to be > 1 */
>        if (offset <= 1) { /* special type */
>          COPY_LONG(&range_start, tab_mid+U_LOWER);
>          if (search_val >= range_start) {
>            /* search_val is in the range */
>            if (offset == LOOKUP_TABLE) {
>              /* range with lookup table */
>              /* get start of lookup table (from offset in pair) */
>              COPY_SHORT(&offset, tab_mid+U_OFFSET);
>              /* offset in lookup table of search_val */
>              tab_mid = current_prog->program + offset
>                        + (search_val - range_start) * sizeof(short);
>              COPY_SHORT(&offset, tab_mid); /* value out of lookup table */
>              break;
>            }
>            /* else RANGE */
>            COPY_SHORT(&offset, tab_mid+U_OFFSET);
>            break;
>          }
>        }
>        /* use default address */
>        COPY_SHORT(&offset, pc+5);

[ Better as: ]

        COPY_SHORT(&offset, pc+DEFAULT_OFF);

>        break;
>      } else { /* win_width >= ENTRY_SIZE */
>        /* move window lower */
>        tab_mid -= win_width;
>        win_width >>= 1;
>      }
>    } else if (search_val > mid_val) {
>      if (win_width < ENTRY_SIZE) { /* leaf */
>        COPY_SHORT(&offset, tab_mid+L_TYPE);
>        if (offset <= 1) {
>          COPY_LONG(&range_start, tab_mid+L_UPPER);
>          if (search_val <= range_start) {
>            /* search_val is in the range */
>            if (offset == LOOKUP_TABLE) {
>              /* range with lookup table */
>              COPY_SHORT(&offset, tab_mid+L_OFFSET);
>              tab_mid = current_prog->program + offset
>                        + (search_val - range_start) * sizeof(short);
>              COPY_SHORT(&offset, tab_mid);
>              break;
>            }
>            /* else RANGE */
>            COPY_SHORT(&offset, tab_mid+L_OFFSET);
>            break;
>          }
>        }
>        /* use default address */
>        COPY_SHORT(&offset, pc+5);

[ Better as: ]

        COPY_SHORT(&offset, pc+DEFAULT_OFF);

>        break;
>      } else { /* win_width >= ENTRY_SIZE */
>        /* move window higher */
>        tab_mid += win_width;
>        win_width >>= 1;
>        /*
>         * The actual table size can be smaller than the assumed table size,
>         * if so, adjust tab_mid lower as appropriate.
>         */
>        while (tab_mid >= end_tab) {
>          if (win_width <= ENTRY_SIZE/2) {
>            win_width = 0;
>            break;
>          }
>          tab_mid -= win_width;
>          win_width >>= 1;
>        }
>      }
>    } else { /* search_val == mid_val */
>      /* Found a match */
>      COPY_SHORT(&offset, tab_mid+U_OFFSET);
>      /* if upper end of lookup table, do indexing */
>      if (!tab_mid[U_TYPE] && !tab_mid[U_TYPE+1]) {
>        /* end of range with lookup table */
>        COPY_LONG(&range_start, tab_mid+U_LOWER);
>        tab_mid = current_prog->program + offset
>                  + (search_val - range_start) * sizeof(short);
>        COPY_SHORT(&offset, tab_mid);
>      }
>      /* lower end of a range or lookup table */
>      if (offset <= 1) {
>        if (offset == LOOKUP_TABLE) {
>          /* start of range with lookup table */
>          COPY_SHORT(&offset, tab_mid+L_OFFSET);
>          tab_mid = current_prog->program + offset;
>          COPY_SHORT(&offset, tab_mid);
>        } else {
>          COPY_SHORT(&offset, tab_mid+L_OFFSET);
>        }
>      }
>      break;
>    }
>  }
>  /* perform the jump */
>  pc = current_prog->program + offset;

>----- END OF CODE -----

Enjoy, be free,
Sean.
-- 
Sean A Reith                         | gusar@uniwa.uwa.edu.au
C programmer and net.addict at large | sean@gu.uwa.edu.au
Obquote:                             | reith_s@kultarr.cs.uwa.edu.au
 "I have a cunning Plan" - Baldrick  | sean@his.own.really.fast.machine (RSN)