From: behrends@arctecws-12.dfki.uni-kl.de (Karl Reimer Behrends)
Subject: The mysteries of switch unraveled (Was: Re: Coding style)
Reply-To: behrends@dfki.uni-kl.de (Karl Reimer Behrends)
Organization: University of Kaiserslautern, Germany
Date: Wed, 14 Oct 1992 11:44:42 GMT

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

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:
> 
> > Now I really start wondering what's so difficult about the switch() code.
> > It can't be the code in interpret.c because every self-respecting programmer
> > should recognise binary search when he sees it.
> >
> > So it has to be the compiler part. But the use of heaps for priority
> > queues or sorting is (or should be) widely known - and that's by far
> > the most difficult part of it.
> >
> > 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?
> >
> > Even the variable names are selfexplanatory. So where's the hard stuff?
> >
> > I never suggested anybody at CD was incapable. What I wanted to say is
> > that Amylaar uses non-trivial code sometimes.
> >
> > However, I don't think your arguments concerning readability of Amylaar's
> > code are valid.
> >
> 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.
> 
> Lets take a look at the switch code in interpret.c Be warned, this is 230
> lines of code. If all this does is binary search, I'll eat my shoes.

Bon appetite. ;-)

> And
> as for 'variable names are selfexplanatory', first consider s, then 
> consider l, d, r and i.

Err. My fault, I'm afraid. The 'selfexplanatory' was meant to belong to the
compiler part of switch() but somehow I managed to screw it up when editing it.
Sorry. *blush*

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.

]        extern char* findstring PROT((char*));
]        unsigned short offset,break_adr;
]        int d,s,r;
]        char *l,*end_tab;
]        static short off_tab[] = { 0*6,1*6,3*6,7*6,15*6,31*6,63*6,127*6,255*6,
]                                   511*6,1023*6,2047*6,4095*6,8191*6 };
]
> 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.

]        ((char *)&offset)[0] = pc[1];
]        ((char *)&offset)[1] = pc[2];
Find the offset relative to the current program counter where the switch table
lies. Please note that this kludgy style of copying a short (and later ints)
is due to the compiler codes not being word aligned. Actually, even this of
storing numbers > 255 hasn't been invented by Amylaar but by Lars. See F_NUMBER
or the F_JUMP family in interpret.c for examples.
]        ((char *)&break_adr)[0] = pc[3];
]        ((char *)&break_adr)[1] = pc[4];
]        *--break_sp = break_adr;
Get the address where to jump when encountering a break and push it on the break
stack.
]        if ( ( i = EXTRACT_UCHAR(pc) >> 4 ) != 0xf )
The more significant 4 bits of this byte define whether switching is done on
numbers or strings. First consider strings (in this case, these bits also
hold information on the switch table).
]        {
]            if ( sp->type == T_NUMBER && !sp->u.number )
]            {
]                /* special case: uninitalized string */
]                s = ZERO_AS_STR_CASE_LABEL;
If there's a zero on the stack we will need a special value for it since this
will lead to conflicts with the null pointer otherwise.
]            }
]            else if ( sp->type == T_STRING )
]            {
We will be comparing pointers to shared strings (all string constants are
shared) instead of the strings itself, therefore make s a pointer to a shared
string or 0 if no such shared string exists (see find_string()).
]                switch(sp->string_type) 
]                {
]                case STRING_SHARED:
]                    s = (int)sp->u.string;
]                    break;
]                default:
]                    s = (int)findstring(sp->u.string);
]                    break;
]                }
]            } 
]            else
]            {
]                bad_arg(1, F_SWITCH);
Give an error because there's a type mismatch.
]            }
]        } 
]        else
Switch on numbers:
]        {
]            if (sp->type != T_NUMBER) bad_arg(1, F_SWITCH);
]            s = sp->u.number;
]            i = (int)pc[0] &0xf ;
Get the switch table info from the least significant four bits this time.
]        }
]
> 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
games here. If you don't know what s is, you have never worked on interpret.c.
]        pop_stack();
]        end_tab = current_prog->program + break_adr;
The end of the switch table lies right in front of the code where break continues.
]        if ( i >= 14 )
]        {
]            if ( i == 14 ) 
]            {
]                /* fastest switch format : lookup table */
However, the compiler currently doesn't support it.
]                l = current_prog->program + offset;
]                ((char *)&d)[0] = end_tab[-4];
]                ((char *)&d)[1] = end_tab[-3];
]                ((char *)&d)[2] = end_tab[-2];
]                ((char *)&d)[3] = end_tab[-1];
Now l = start of lookup table, d = lower end of range for which it is valid.
]                if ( s >= d && l + (s=(s-d)*sizeof(short)) < end_tab - 4 )
]                {
Index into the table and perform the jump:
]                    ((char *)&offset)[0] = l[s];
]                    ((char *)&offset)[1] = l[s+1];
]                    if (offset)
]                    {
]                        pc = current_prog->program + offset;
]                        break;
]                    }
]                }
]                /* default */
]                ((char *)&offset)[0] = pc[5];
]                ((char *)&offset)[1] = pc[6];
]                pc = current_prog->program + offset;
]                break;
]            } 
]            else
]                fatal("unsupported switch table format.\n");
]        }
]
> 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.
]        l = current_prog->program + offset + off_tab[i];
]        d = (off_tab[i]+6) >> 1;
]        if (d == 3) 
]            d = 0;
]
> 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.
Let me first explain the variant of binary search used here: We will assume first
that the size of the table is of the form 2^n-1 for some nonnegative integer n.
Then the middle entry of the array lies exactly at index 2^(n-1)-1 - no rounding
necessary. By adding/subtracting half the size of either of the halves we will
arrive at the exact centre of the left right half of the array - and so on.
This is due to the fact that an array with 2^n-1 entries can be considered to
be a perfect binary tree with 2^n-1 nodes, 2^(n-1) of them being leaves.
We will see that the value of l will follow the path from the root (being entry
2^(n-1)-1 of the array) down to a leaf as in searching a binary tree until
a match is found or the search ends unsuccessful. d on the other hand will
always contain the offset to the middle of the left or right part of the
remaining range to be searched. And to avoid wasting space by having exactly
2^n-1 entries in the table, we will think of the area beyond the right edge to
consist of virtual cells with a value +infinity greater than all other values.
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
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.
I may add that I think the underlying algorithm is much nicer than classical
binary search and yet needs exactly the same number of comparisons in the worst
case.
]
]        for(;;) 
]        {
]            ((char *)&r)[0] = l[0];
]            ((char *)&r)[1] = l[1];
]            ((char *)&r)[2] = l[2];
]            ((char *)&r)[3] = l[3];
r now has the value pointed to by l, i.e. the middle entry of the table.
]            if (s < r)
]            {
]                if (d < 6) 
]                {
We've arrived at a leaf.
The following test for !d is superfluous since d is set to 0 anyway for the
next walk round the loop. This may be considered a bug, although not a harmful
one - uses just some CPU cycles.
]                    if (!d) /* test for range */
]                    {
We now check whether the leaf needs to be combined with an adjoining one
to make up a range as for example in case 10..20:
]                        ((char *)&offset)[0] = l[-2];
]                        ((char *)&offset)[1] = l[-1];
]                        
]                        /* F_BREAK is required to be > 1 */
More precisely, the instruction preceding the switch table is a break and thus
F_BREAK has to be > 1 if you get off the left hand side.
]                        if (offset <= 1)
]                        {
If offset == 1 it is a range, if offset == 0 use a lookup table (the latter one
isn't yet supported by the compiler).
]                            ((char *)&r)[0] = l[-6];
]                            ((char *)&r)[1] = l[-5];
]                            ((char *)&r)[2] = l[-4];
]                            ((char *)&r)[3] = l[-3];
Having already tested the upper bound, we'll now check the lower bound of the
range.
]                            if (s >= r)
]                            {
]                                /* s is in the range */
]                                if (!offset)
]                                {
offset == 0 denotes a lookup table.
]                                    /* range with lookup table */
]                                    ((char *)&offset)[0] = l[4];
]                                    ((char *)&offset)[1] = l[5];
]                                    l = current_prog->program + offset +
]                                        (s-r) * sizeof(short);
]                                    ((char *)&offset)[0] = l[0];
]                                    ((char *)&offset)[1] = l[1];
]                                    break;
]                                }
]                                ((char *)&offset)[0] = l[4];
]                                ((char *)&offset)[1] = l[5];
]                                break;
]                            }
]                        }
If all cases fail, goto default:
]                        /* use default address */
]                        ((char *)&offset)[0] = pc[5];
]                        ((char *)&offset)[1] = pc[6];
]                        break;
]                    } /* !d */
]                    d = 0;
]                } 
]                else 
]                {
]                    /* d >= 6 */
Now consider the left half. Move the pointer and half the offset.
]                    l -= d;
]                    d >>= 1;
]                }
]            }
]            else if (s > r) 
]            {
Now we're off to the right.
]                if (d < 6)
]                {
Again arrived at a leaf.
]                    if (!d)  /* test for range */
]                    {
]                        ((char *)&offset)[0] = l[4];
]                        ((char *)&offset)[1] = l[5];
]                        if (offset <= 1) 
]                        {
]                            ((char *)&r)[0] = l[6];
]                            ((char *)&r)[1] = l[7];
]                            ((char *)&r)[2] = l[8];
]                            ((char *)&r)[3] = l[9];
]                            if (s <= r) 
]                            {
]                                /* s is in the range */
]                                if (!offset) 
]                                {
]                                    /* range with lookup table */
]                                    ((char *)&offset)[0] = l[10];
]                                    ((char *)&offset)[1] = l[11];
]                                    l = current_prog->program + offset +
]                                        (s-r) * sizeof(short);
]                                    ((char *)&offset)[0] = l[0];
]                                    ((char *)&offset)[1] = l[1];
]                                    break;
]                                }
]                                ((char *)&offset)[0] = l[10];
]                                ((char *)&offset)[1] = l[11];
]                                break;
]                            }
]                        }
]                        /* use default address */
]                        ((char *)&offset)[0] = pc[5];
]                        ((char *)&offset)[1] = pc[6];
]                        break;
]                    } /* !d */
]                    d = 0;
]                } 
]                else 
]                {

> This is the part I love most...
I too, it's so easy to understand... really.
]
]                    /* d >= 6 */
]                    l += d;
Move l into the right part. Then:
While l is beyond the right edge of the table it is considered to point to
+infinity, thus we will always move left. Since this is likely to happen several
times in a row we speed things up by putting it in a loop. However, a break
after d = 0 would make it even faster.
]                    while (l >= end_tab)
]                    {
]                        d >>= 1;
]                        if (d <= 3)
]                        {
]                            if (!d) 
]                                break;
]                            d = 0;
]                        }
]                        l -= d;
]                    }
And don't forget to divide d by 2.
]                    d >>= 1;
]                }
]
Nothing complicated, actually.
]            } 
]            else 
]            {
]                /* s == r */
Found.
]                ((char *)&offset)[0] = l[4];
]                ((char *)&offset)[1] = l[5];
If single element or at the right end of the range, we're finished.
Else some more work has to be done.
]                if ( !l[-2] && !l[-1] ) 
]                {
Lookup table, index into it.
]                    /* end of range with lookup table */
]                    ((char *)&r)[0] = l[-6];
]                    ((char *)&r)[1] = l[-5];
]                    ((char *)&r)[2] = l[-4];
]                    ((char *)&r)[3] = l[-3];
]                    l = current_prog->program + offset + (s-r)*sizeof(short);
]                    ((char *)&offset)[0] = l[0];
]                    ((char *)&offset)[1] = l[1];
]                }
]                if (offset <= 1)
]                {
Value is left boundary of either a range or a lookup table. Find the correct
offset.
]                    if (!offset)
]                    {
]                        /* start of range with lookup table */
]                        ((char *)&offset)[0] = l[10];
]                        ((char *)&offset)[1] = l[11];
]                        l = current_prog->program + offset;
]                        ((char *)&offset)[0] = l[0];
]                        ((char *)&offset)[1] = l[1];
]                    } 
]                    else 
]                    {
]                        ((char *)&offset)[0] = l[10];
]                        ((char *)&offset)[1] = l[11];
]                    }
]                }
]                break;
]            }
]        }
Perform the jump:
]        pc = current_prog->program + offset;

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.
The only reason this code appears to be strange is the way the table is coded.
Replace this in your mind with an array of structs and everything gets much
easier.

> 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.

> 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
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.

> 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.

				Reimer Behrends
Newsgroups: rec.games.mud.lp,alt.mud.lp,rec.games.mud.misc