From: gusar@uniwa.uwa.edu.au (Sean A Reith)
Newsgroups: rec.games.mud.lp
Subject: Re: The mysteries of switch unraveled (unrot-13ed)
Date: 16 Oct 1992 13:02:13 +0800
Organization: The University of Westrn Australia
NNTP-Posting-Host: uniwa.uwa.edu.au

(If you think you've read this article before, your lying to yourself.)

behrends@arctecws-12.dfki.uni-kl.de (Karl Reimer Behrends) writes:

>Sigh. This is going to be long. If you're not interested in gamedrivers,
>simply skip it.

Welcome to "This is your code", hosted by Pinkfish and Lynscar.
(after an extremely long night....).

>In article <15014@chalmers.se>, d8andjo@dtek.chalmers.se (Johan Andersson) writes:
>> In article <1992Oct13.040029.29654@rhrk.uni-kl.de> behrends@arctecws-12.dfki.uni-kl.de (Karl Reimer Behrends) writes:
>> 
>> > The same applies for alists - they are so simple a concept that LISP
>> > programmers... ... The implementation again uses binary search and
>> > heapsort. So where's the problem?

Concept?  Sorry, must of missed the bit where Johan was complaining about the
concept...  I thought readablity was the issue...

>> > Even the variable names are selfexplanatory. So where's the hard stuff?

Missed them too (the self explanatory variables).

>> > I never suggested anybody at CD was incapable. What I wanted to say is
>> > that Amylaar uses non-trivial code sometimes.

As you seemed so fond of correcting Johans comments, I will correct yours, what
you meant to type was:
"... that Amylaar uses non-readable code most of the time."

>> > However, I don't think your arguments concerning readability of Amylaar's
>> > code are valid.

More comments on this later :)

>> Algorithms like heap/quicksort, hashing, binary search, alists, queues
>> and much else are trivial when you know the theory. It is not the
>> algorithms I and most others find hard to understand it is Joerns way of
>> coding them that we have problems with.

Hey, thats what I thought we were talking about...
Damn, stop _not_ quoting the bits that support your comments.  Makes it
really hard to agree with you.

>Now lets start with explaining how switch() works to get rid of this once and
>for ever. Just to avoid any misunderstandings, I may add that Amylaar didn't
>have a hand in it nor did he have to explain his code to me. All comments are
>by me and due to my own analysis of the code.

And it _only_ took you half an hour, considering it's such a trivial algorithm
it _must_ be readable code.
Btw, your comments _were_ helpful, much much much much more than the
uncommented source code...

First, the code rewritten using the [exact] same algorithm, you decide which
is more readable.

----- 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).
 */

/*
 * 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 */
  COPY_SHORT(&break_adr, pc+3); /* the offset to break to */
  *--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);
    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);
        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);
        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 -----

Before you say this is unrealistically overcommented, have a look at my
sprintf() code.

Back to your comments...

>> What is the use of off_tab, why (2^n-1)*6? In its original form the next to
>> last value was 4096*6, we changed it, were we wrong?
>
>Of course you weren't wrong. The reason for these values will become apparent
>later.

It's MUCH MUCH easier to understand code if the assumptions are stated first,
being forced to read the entire code to work out this out, is NON-USEFUL,
some people have better things to do.  Why obstificate?

>> So far so good, the value of i is a slight mystery and s looks like some
>> form of searchvalue.
>It doesn't "look like" some form of search value, it _is_ the argument to switch
>(slightly modified) and hence it _is_ the search value. Please don't play
  ^^^^^^^^^^^^^^^^^
laugh.  Yes and c = *s is just a string slightly modified.

>games here. If you don't know what s is, you have never worked on interpret.c.

Aha.  I agree totally, after a reasonable amount of work on interpret.c, 
a variable named s just shouts STRING, oops, I mean svalue, no no, I mean
svalue value, yeah that's it, or maybe it means socket?

>Now l = start of lookup table, d = lower end of range for which it is valid.

True, at the moment...  The meanings of d and r change whenever you blink too
fast.  Just to make life more ... interesting.

>> Ok, the comment gives a hint of what i is. There are different switch table
>> formats, i denotes them. The role of d, end_tab, l and how the 
>> interpretation of the value of s changes within the third 'if' is somewhat
>> understandable.
>Strike out the "somewhat". So far the code shouldn't pose any problems to an
>experienced programmer like you.

Underline the "somewhat", make it into a huge neon sign.
(Appologies if you just forgot the smilie :)

>> What does 'd' stand for? There are 14 entries in off_tab and 'i'
>> can at this point have values 0 - 13, that is probably a hint.
>> 
>> Following is what I consider an extremely lucid example of totally
>> unreadable code. Note that we have decompacted the original, adding newlines
>> and spaces at numerous places. That some form of search is being done I
>> understand. I will accept your word that the algorithm used is binary search.
>> I do not accept that it is obvious.
>Then I'll make it obvious for you. How I arrive at my conclusions I'll
>explain at the end of this article.

BUT THE BLOODY CODE SHOULD.

>This is not what you would call 'classic' binary search, but it is binary search
>all the same. This should also make the values in off_tab clear if we know the
                                                                 ^^^^^^^^^^
Psionic powers are low at 04:00.

>table to consist of chunks six bytes long, four for the value and two for the
>corresponding offset to be added to the program counter.

>> This is the part I love most...
>I too, it's so easy to understand... really.

Yes I agree, it's a really trivial algorithm ... skillfully obscured.

>Nothing complicated, actually.

No.....

[and later...]
>actually. Took me less than half an hour to analyze switch. Any experienced

Complex code must be a real bummer.

>What's difficult about that? Having an offset added to a pointer which is
>divided by 2 everytime you go round the loop indicates binary search. Having
>comparisons for s < r and s > r corroborates this. Then its easy to derive
>the meaning of l and d. The way the switch table is constructed should be
>obvious by that time. Finding out how flow of control runs is easy now. Done.

Especially the offset finding at -2 and +4.  Thank goodness he didn't comment
it, be no challenge at all.

>The only reason this code appears to be strange is the way the table is coded.

s/the table/it/

>> There are more examples, if you think this is fun we can look at the
>> expression handling in lex.c or we could dig up the alist code.
>
>Sigh. I don't think it's that much fun, but if you really need more help, just
>call me. I'll be happy to help out.

ucbvax.berkeley.edu
/pub/games/lpmud/driver.interpreted.tar.Z

Nice of you to volunteer, must have lots of free time (1/2 hour per 200 lines,
now what does that work out to...).

>> My point is that this code can be written in a much more readable way
>> without losing efficiency or functionality. I know that I write code
>> less readable than some others, the old parse_command is a good example of
>> that. But I acknowledge this as a fault and try to improve my style of
>> coding. I'm not saying I'm succeeding :-)
>>
>> Joern and yourself do not accept even the principal fault. Your argument
>> seem to be that if a piece of code is to be efficient it must by definition
>> be hard to read, i.e. 'If it was hard to write, it should be hard to read'.
>
>Sorry. No. First of all I pride myself on writing very readable code. You haven't
>yet seen any code by me. Concerning Amylaar's code, it isn't that hard to read,
>actually. Took me less than half an hour to analyze switch. Any experienced

So your code is readable like Amylaar's?  Bonus.

>programmer should be able to perform this feat without difficulties.
>Only muttering "Oh god, it's been written by Amylaar" won't take you much
>further, though, which you seem to have done.

Yeah, bummer we don't have a kill file for code.

>> May one assume that it is because Joern find such trivial algorithms as 
>> those used, difficult to implement, i.e. hard to write, and might that
>> be the reason we find his code hard to read?
>
>I don't think so. But he's concerned about getting reasonable upper bounds on
>the execution time. Thus his algorithms aren't always the most trivial.

The algorithm was trivial (as you said yourself), our version is just as quick
(it's pretty much the same code), and a hell of a lot more
readable == maintainable.  It doesn't insert NOPs for comment lines.

>				Reimer Behrends

Enjoy, be free,
Sean and DDT.
Pink fish forever.
-- 
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)