From: d8andjo@dtek.chalmers.se (Johan Andersson)
Newsgroups: rec.games.mud.lp
Subject: Coding style (Was Re: Gamedriver engineering)
Date: 13 Oct 92 14:31:54 GMT
	<14926@chalmers.se> <1992Oct13.040029.29654@rhrk.uni-kl.de>
Organization: Chalmers University of Technology, Sweden
In-reply-to: behrends@arctecws-12.dfki.uni-kl.de's message of 13 Oct 92 04:00:29 GMT


Oh well, I'm sorry to have to do this, for those of you not interested in
a lot of cryptic C-code, press 'n', or whatever you use.

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. And
as for 'variable names are selfexplanatory', first consider s, then 
consider l, d, r and i.

]        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?
        
]        ((char *)&offset)[0] = pc[1];
]        ((char *)&offset)[1] = pc[2];
]        ((char *)&break_adr)[0] = pc[3];
]        ((char *)&break_adr)[1] = pc[4];
]        *--break_sp = break_adr;
]        if ( ( i = EXTRACT_UCHAR(pc) >> 4 ) != 0xf )
]        {
]            if ( sp->type == T_NUMBER && !sp->u.number )
]            {
]                /* special case: uninitalized string */
]                s = ZERO_AS_STR_CASE_LABEL;
]            }
]            else if ( sp->type == T_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);
]            }
]        } 
]        else
]        {
]            if (sp->type != T_NUMBER) bad_arg(1, F_SWITCH);
]            s = sp->u.number;
]            i = (int)pc[0] &0xf ;
]        }
]
So far so good, the value of i is a slight mystery and s looks like some
form of searchvalue.

]        pop_stack();
]        end_tab = current_prog->program + break_adr;
]        if ( i >= 14 )
]        {
]            if ( i == 14 ) 
]            {
]                /* fastest switch format : lookup table */
]                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];
]                if ( s >= d && l + (s=(s-d)*sizeof(short)) < end_tab - 4 )
]                {
]                    ((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.


]        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.
]
]        for(;;) 
]        {
]            ((char *)&r)[0] = l[0];
]            ((char *)&r)[1] = l[1];
]            ((char *)&r)[2] = l[2];
]            ((char *)&r)[3] = l[3];
]            if (s < r)
]            {
]                if (d < 6) 
]                {
]                    if (!d) /* test for range */
]                    {
]                        ((char *)&offset)[0] = l[-2];
]                        ((char *)&offset)[1] = l[-1];
]                        
]                        /* F_BREAK is required to be > 1 */
]                        if (offset <= 1)
]                        {
]                            ((char *)&r)[0] = l[-6];
]                            ((char *)&r)[1] = l[-5];
]                            ((char *)&r)[2] = l[-4];
]                            ((char *)&r)[3] = l[-3];
]                            if (s >= r)
]                            {
]                                /* s is in the range */
]                                if (!offset)
]                                {
]                                    /* 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;
]                            }
]                        }
]                        /* use default address */
]                        ((char *)&offset)[0] = pc[5];
]                        ((char *)&offset)[1] = pc[6];
]                        break;
]                    } /* !d */
]                    d = 0;
]                } 
]                else 
]                {
]                    /* d >= 6 */
]                    l -= d;
]                    d >>= 1;
]                }
]            }
]            else if (s > r) 
]            {
]                if (d < 6)
]                {
]                    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...
]
]                    /* d >= 6 */
]                    l += d;
]                    while (l >= end_tab)
]                    {
]                        d >>= 1;
]                        if (d <= 3)
]                        {
]                            if (!d) 
]                                break;
]                            d = 0;
]                        }
]                        l -= d;
]                    }
]                    d >>= 1;
]                }
]
Variable names are selfexplanatory, right?

]            } 
]            else 
]            {
]                /* s == r */
]                ((char *)&offset)[0] = l[4];
]                ((char *)&offset)[1] = l[5];
]                if ( !l[-2] && !l[-1] ) 
]                {
]                    /* 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)
]                {
]                    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;
]            }
]        }
]        pc = current_prog->program + offset;
]        break;
]    }

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.

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

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?

/Johan

--
Johan Andersson           | "You don`t have conversations with microprocessors
Chalmers, Sweden          | you tell them what to do, and then you helplessly
Email:                    | watch the disaster when they take you literally."
d8andjo@dtek.chalmers.se  |	Sah`ot in David Brins "Startide Rising"