1990 IOCCC dds BASIC interpreter (unscrambled) 
Author Message
 1990 IOCCC dds BASIC interpreter (unscrambled)

Some of you may remember the 1990 international obfuscated c code competition,
here is an extract from the rules to explain what it is to those of you who
either don't remember, have never come across it before or don't want to
remeber it ;-)

        Obfuscate:  tr.v.  -cated, -cating, -cates.  1. a.  To render obscure.
                b.  To darken.  2. To confuse:  his emotions obfuscated his
                judgment.  [LLat. obfuscare, to darken : ob(intensive) +
                Lat. fuscare, to darken < fuscus, dark.] -obfuscation n.
                obfuscatory adj.

GOALS OF THE CONTEST:

    * To write the most Obscure/Obfuscated C program under the rules below.
    * To show what should NOT be done in C programs.
    * To provide a safe forum for poor C code.  :-)


BASIC language interpreter.  I was looking around for a simple language
to play around with one day, and decided that this may be a good starting
point as well as an interesting exercise of my understanding of the C
language.  Anyhow, I took the original code, which is immediately below,
and annotated it.  I thought some other people may be interested in the
final outcome, so I have included the results of my labour
(well it didn't take that long!) after the original.

I am posting this with the permission of Diomidis, who has asked me to
point out that this is NOT his normal coding style. It may also
interest some of you to know that the translation from an
understandable version of the code to the winning entry was partially
done by some special sed scripts.  Diomidis' original code is somewhat
different to my interpretation in that I have not left any of the
original #defines in the code.

Enjoy!

Pete.

---- Original winning entry ----

#define O(b,f,u,s,c,a)b(){int o=f();switch(*p++){X u:_ o s b();X c:_ o a b();default:p--;_ o;}}
#define t(e,d,_,C)X e:f=fopen(B+d,_);C;fclose(f)
#define U(y,z)while(p=Q(s,y))*p++=z,*p=' '
#define N for(i=0;i<11*R;i++)m[i]&&
#define I "%d %s\n",i,m[i]
#define X ;break;case
#define _ return
#define R 999
typedef char*A;int*C,E[R],L[R],M[R],P[R],l,i,j;char B[R],F[2];A m[12*R],malloc
(),p,q,x,y,z,s,d,f,fopen();A Q(s,o)A s,o;{for(x=s;*x;x++){for(y=x,z=o;*z&&*y==
*z;y++)z++;if(z>o&&!*z)_ x;}_        0;}main(){m[11*R]="E";while(puts("Ok"),gets(B)
)switch(*B){X'R':C=E;l=1;for(i=0;i<R;P[i++]=0);while(l){while(!(s=m[l]))l++;if
(!Q(s,"\"")){U("<>",'#');U("<=",'$');U(">=",'!');}d=B;while(*F=*s){*s=='"'&&j
++;if(j&1||!Q(" \t",F))*d++=*s;s++;}*d--=j=0;if(B[1]!='=')switch(*B){X'E':l=-1
X'R':B[2]!='M'&&(l=*--C)X'I':B[1]=='N'?gets(p=B),P[*d]=S():(*(q=Q(B,"TH"))=0,p
=B+2,S()&&(p=q+4,l=S()-1))X'P':B[5]=='"'?*d=0,puts(B+6):(p=B+5,printf("%d\n",S
()))X'G':p=B+4,B[2]=='S'&&(*C++=l,p++),l=S()-1 X'F':*(q=Q(B,"TO"))=0;p=B+5;P[i
=B[3]]=S();p=q+2;M[i]=S();L[i]=l X'N':++P[*d]<=M[*d]&&(l=L[*d]);}else p=B+2,P[
*B]=S();l++;}X'L':N printf(I)X'N':N free(m[i]),m[i]=0   X'B':_ 0 t('S',5,"w",N
fprintf(f,I))t('O',4,"r",while(fgets(B,R,f))(*Q(B,"\n")=0,G()))X 0:default:G()
;}_ 0;}G(){l=atoi(B);m[l]&&free(m[l]);(p=Q(B," "))?strcpy(m[l]=malloc(strlen(p
)),p+1):(m[l]=0,0);}O(S,J,'=',==,'#',!=)O(J,K,'<',<,'>',>)O(K,V,'$',<=,'!',>=)
O(V,W,'+',+,'-',-)O(W,Y,'*',*,'/',/)Y(){int o;_*p=='-'?p++,-Y():*p>='0'&&*p<=
'9'?strtol(p,&p,0):*p=='('?p++,o=S(),p++,o:P[*p++];}

---- My interpretation of the above ----

/*
 * DDS BASIC Interpreter V1.0(a)
 *

 * for the 1990 international obfuscated c code competition.

 *
 *      Notes
 *
 *  -   Please Note that I use 4 space tabstops, so for optimum readability
 *      I suggest you change you editor/file browser to use these too.
 *
 * [1]  The ;break; results from a #define from the original code:
 *              #define X ;break;case   used to save space.
 * [2]  The reason for the strange precedence of < > and <= >=
 *              is that there was a single #define statement for all the
 *              S(), J(), K(), V() and W() routines to save space.
 *
 * The following were "fairly" normal space savers and do not give rise
 * to any strange consequences.
 *
 * [3]  The fopen... fclose sequence was also #defined
 * [4]  The for() statments here were also partially #defined
 * [5]  This format statement was #defined
 *
 * I shall not mention the other defines as they are ordinary space
 * saving devices.
 */

typedef char * A;

int* C,                 /* line number stack pointer used for GOSUB's */
        E[999],         /* line number stack used for GOSUB's */

        /* the following two arrays are for FOR loops only */
        L[999],         /* line number start of FOR loop store */
        M[999],         /* loop termination constant values */

        P[999],         /* contains integer variable values */

        l,                      /* current line no of program */
        i,                      /* used as for loop counter for LIST, NEW and SAVE */
        j;                      /* boolean to indicate if line contains a string */

char B[999],    /* temporary input buffer and execution buffer */
         F[2];          /* used for stripping out spaces and tabs */

A m[12*999],    /* array of ptrs to lines of code */
        malloc(),
        p,                      /* used by S() for expression parsing */
        q,                      /* used to help find second token in IF and FOR statements */
        x,                      /* used as temp var in Q() */
        y,                      /* used as temp var in Q() */
        z,                      /* used as temp var in Q() */
        s,                      /* points to the current line being executed as loaded in */
        d,                      /* used to point to last char on current line */
        f,                      /* holds file descriptor of currently loaded file */
        fopen();

/*
 * this routine (originally called strstr) searches for string 'o' in
 * string 's' and returns a ptr to the first occurence of the string or
 * zero if not found
 */
A Q(s,o)
A s,o;
{
        for(x=s; *x; x++)
        {
                /* do search */
                for(y=x,z=o; *z && *y == *z; y++)
                        z++;

                /* return ptr if we found one */
                if(z > o && !*z)
                        return x;
        }

        /* otherwise return null */
        return  0;

Quote:
} /* end of Q */

main()
{
        /*
         * initialise the very last possible line to END so
         * we never die if we try to run an empty program
         */
        m[11*999]="E";

        /* output prompt and get a command */
        while(puts("Ok"),gets(B))

                /* interpret the command */
                switch(*B)
                {
                ;break;         /* [1] */

                /*
                 * interpret away :-)
                 */
                case'R':        /* RUN */
                        C=E;    /* initialise stack pointer */
                        l=1;    /* initialise line counter */

                        /* initialise variables */
                        for(i=0; i<999; P[i++]=0);

                        while(l)
                        {
                                /* get next non null line and assign it to s */
                                while(!(s=m[l]))
                                        l++;

                                /*
                                 * check for expression with two letter operators
                                 * in current line, and convert to a single letter operator
                                 * to allow easier parsing later
                                 */
                                if (!Q(s,"\""))
                                {
                                        /* not equals */
                                        while(p=Q(s,"<>"))
                                                *p++='#',*p=' ';                /* convert to # */

                                        /* less than or equals */
                                        while(p=Q(s,"<="))
                                                *p++='$',*p=' ';                /* convert to $ */

                                        /* greater than or equals */
                                        while(p=Q(s,">="))
                                                *p++='!',*p=' ';                /* convert to ! */
                                }

                                /* assign d to start of temp buffer B */
                                d=B;

                                /*
                                 * strip out all the spaces and tabs for this line
                                 * moving the line from s to the temp buffer B ready
                                 * for execution
                                 */
                                while(*F = *s)
                                {
                                        /*
                                         * if its a string then set j
                                         * Note how the code after the && is only executed
                                         * if the code before it is true!  This is used a lot
                                         * as a space saving 'if' statement.
                                         */
                                        *s=='"'
                                                && j++;

                                        /*
                                         * if j == 1 then we have a string and we must get
                                         * d to point to the end of it so assign *s to *d
                                         * otherwise if the char is not a space or tab then
                                         * copy it too
                                         * Note all strings go to end of line
                                         */
                                        if (j&1||!Q(" \t",F))
                                                *d++ = *s;

                                        /* get next char */
                                        s++;
                                }

                                /*
                                 * d points to the last char of line here
                                 * so set that to null and point d to the previous
                                 * char on the line, so eg for a NEXT statement d
                                 * will point to the count variable.
                                 * For a PRINT, it will point to the last ", so
                                 * it is set to null later.
                                 * Note j is reset here too
                                 */
                                *d-- = j = 0;

                                /* check we are not doing a straight assignment */
                                if(B[1] != '=')
                                        switch(*B)      /* no so execute line */
                                        {
                                        ;break;         /* [1] */

                                        /* E... => END */
                                        case'E':
                                                l = -1;
                                                break;

                                        /* R.M => REM  otherwise its a RETURN */
                                        case'R':
                                                B[2] != 'M'
                                                        /* Not a REM, must be RETURN */
                                                        && (l = *--C);  /* pop line off stack */
                                                break;

                                        /* I... => IF or INPUT */
                                        case'I':
                                                B[1]=='N'
                                                ?
                                                        /* INPUT */
                                                        gets(p=B),      /* read it in */
                                                        P[*d]=S()
                                                :
                                                        /* must be IF so find the THEN */
                                                        (*(q=Q(B,"TH"))=0,

                                                        p=B+2,  /* get to end of THEN */

                                                        /* evaluate expression in IF */
                                                        S()
                                                                /* it's true so jump */
                                                                && (p=q+4,              /* move p to line number str */
                                                                        l=S()-1)        /* update line no */
                                                        );
                                                break;

                                        /* P...." => PRINT */
                                        case'P':
                                                B[5]=='"'
                                                ?
                                                        /* print a string */
                                                        *d=0,           /* clear out the final " */
                                                        puts(B+6)       /* do the print */
                                                :
                                                        /* print a number */
                                                        (p=B+5,printf("%d\n",S()));
                                                break;

                                        /*
                                         * G.S => GOSUB otherwise its a goto
                                         * Note how the code after the && is only executed
                                         * if the code before it is true!
                                         */
                                        case'G':
                                                p=B+4,  /* presume a GOTO make p point to new line */

                                                B[2]=='S'
                                                        /* actually a GOSUB! */
                                                        && (*C++=l /* store current line on stack */,
                                                        p++),   /* in counter to get line no */

                                                l=S()-1;        /* set new line no */
                                                break;

                                        /* F... => FOR */
                                        case'F':

                                                /* lets find the TO */
                                                *(q=Q(B,"TO"))=0;

                                                /* get the variable name */
                                                p=B+5;

                                                /*
                                                 * get the counter var and initialise it
                                                 * to the start value, assign i the ascii val
                                                 * of the var, this gives us a FOR nesting
                                                 * capability of 26!
                                                 */
                                                P[i=B[3]]=S();

                                                /* get value after TO */
                                                p=q+2;
                                                M[i]=S();

                                                /* store current line no */
                                                L[i]=l;
                                                break;

                                        /* N... => NEXT */
                                        case'N':
                                                /* inc count and check if we have finished the loop */
                                                ++P[*d]<=M[*d]
                                                        /* not finished so goto start of FOR */
                                                        &&(l=L[*d]);
                                        }
                                else
                                        /* do assignment here */
                                        p=B+2,
                                        P[*B]=S();

                                /* get next line */
                                l++;
                        }
                        ;break;         /* [1] */

                case'L':        /* LIST [4] */
                        for(i=0; i<11*999; i++)
                                m[i]
                                        /* only print if we have a line there! */
                                        && printf("%d %s\n",i,m[i]);  /* [5] */
                        break;

                case'N':        /* NEW [4] */
                        for(i=0; i<11*999; i++)
                                m[i]
                                        /* only delete if we have a line there! */
                                        && free(m[i]),m[i]=0;
                        break;

                case'B':        /* BYE */
                        return 0 ;
                        break;

                /*
                 * this is the "save a program to a file" code, note that this
                 * interpreter presumes that you have typed "SAVE fname" or at least
                 * "Sxxx fname" :-)
                 */
                case 'S':       /* SAVE [4] */

                        /* [3] */
                        f=fopen(B+5,"w");     /* open file for writing */

                        /* output the lines */
                        for(i=0; i<11*999; i++)
                                m[i]
                                        /* only save if we have a line there! */
                                        && fprintf(f,"%d %s\n",i,m[i]);               /* [5] */

                        fclose(f);
                        break;

                /*
                 * this is the "load a prgram from a file into memory" code,
                 * note that this interpreter presumes that you have typed
                 * "OLD fname" or at least "Oxx fname" :-)
                 */
                case 'O':       /* OLD */

                        /* [3] */
                        f=fopen(B+4,"r");     /* open the source file */

                        /* read it in */
                        while(fgets(B,999,f))
                                (*Q(B,"\n")=0,G());           /* insert lines into memory */

                        fclose(f);
                        break;

                case 0:         /* anything else */
                default:
                        G();
                }
        return 0;

Quote:
} /* end of main */

/*
 * this routine (originally called enterline) inserts a new line into
 * the line buffer, the line inserted is currently held in the temporary
 * input buffer named B
 */
G()
{
        /* get the line number */
        l=atoi(B);

        /* clear out any previous incarnation of that line */
        m[l] && free(m[l]);

        /* do we have a valid line ? */
        (p=Q(B," "))
        ?
                /* copy the string into a newly created buffer */
                strcpy(m[l]=malloc(strlen(p)),p+1)
        :
                /* null out this line, ie empty */
                (m[l]=0,0);

Quote:
} /* end of G */

/*
 * This routine causes all the routines below it to be called in turn
 * until no further expressions are found, the order of cascading gives
 * rise to operator precedence.
 * Together these routines form the expression parser.
 * This technique is called recusive descent parsing.
 *
 * S() does equivalence and non equivalence expressions
 */
S()
{
int o=J();      /* call J */

        switch(*p++)
        {
                ;break;         /* [1] */
        case '=':                                       /* IF equivalence */
                return o == S();                /* return boolean */
                ;break;         /* [1] */
        case '#':                                       /* IF non equivalence */
                return o != S();                /* return boolean */
        default:
                p--;
        return o;
        }

Quote:
} /* end of S */

/*
 * J() handles less than and greater than expressions
 * higher precedence than S() expressions
 */
J()
{
int o=K();      /* call K */

        switch(*p++)
        {
                ;break;         /* [1] */
        case '<':                                    /* less than */
                return o < J();                      /* return boolean */
                ;break;         /* [1] */
        case '>':                                    /* greater than */
                return o > J();                      /* return boolean */
        default:
                p--;
                return o;
        }

Quote:
} /* end of J */

/*
 * K() handles less than or equal to and greater than or equal to expressions
 * higher precedence than J() expressions [2].
 */
K()
{
int o=V();      /* call V */

        switch(*p++)
        {
                ;break;         /* [1] */
        case '$':                                       /* less than or equal */
                return o <= K();             /* return boolean */
                ;break;         /* [1] */
        case '!':                                       /* greater than or equal to */
                return o >= K();             /* return boolean */
        default:
                p--;
                return o;
        }

Quote:
} /* end of K */

/*
 * V() handles addition and subtraction
 * higher precedence than K() expressions
 */
V()
{
int o=W();      /* call W */

        switch(*p++)
        {
                ;break;         /* [1] */
        case '+':
                return o + V();                 /* return added value */
                ;break;         /* [1] */
        case '-':
                return o - V();                 /* return subtracted value */
        default:
                p--;
                return o;
        }

Quote:
} /* end of V */

/*
 * W() handles multiplication and division
 * higher precedence than V() expressions
 */
W()
{
int o=Y();      /* call Y */

        switch(*p++)
        {
                ;break;         /* [1] */
        case '*':
                return o * W();                 /* return multiplied value */
                ;break;         /* [1] */
        case '/':
                return o / W();                 /* return divided value */
        default:
                p--;
                return o;
        }

Quote:
} /* end of W */

/*
 * this routine (originally called basic) does the nitty gritty work of
 * handling the lowest level of an expression, whether it be a number,
 * variable or another expression nested in brackets
 */
Y()
{
int o;

        return *p=='-'          /* are we after a negation? */
        ?
                p++,
                -Y()                            /* negate return value */
        :
                *p>='0' && *p<='9'
                ?
                        /* number, so return its value */
                        strtol(p,&p,0)      /* return value */
                :
                        *p=='('
                        ?
                                p++,            /* skip a start bracket if we have one */
                                o=S(),          /* evaluate the expression */
                                p++,            /* skip an end bracket if we have one */
                                o                       /* set return value! */
                        :
                                /* no further expressions just a var */
                                P[*p++];        /* set return value! */

Quote:
} /* end of Y */

--

      -w---------    Pyramid Technology U.K.       Peter Ruczynski    
    ---www-------    Pyramid House                 #include <std/disclaimer.h>

-------wwwwwww---    Hants GU14 7PL     England.   Wot no funny comment :-)



Sun, 02 Jan 1994 18:23:21 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. ioccc sources 1990 1991

2. BASIC to C translator wanted (or BASIC interpreter)

3. Copy of ISO/IEC 9899:1990

4. Freestanding implementations in ISO/EIC 9899:1990

5. 1990 International Obfuscated C Code Contest winners 1 of 2

6. 1990 International Obfuscated C Code Contest Winners

7. Repost of International Obfuscated C Code Contest Rules for 1990

8. Call for Papers - Summer 1990 USENIX, Anaheim, CA

9. 1990 International Obfuscated C Code Contest winners 2 of 2

10. reference: AT&T long-distance snafu in 1990

11. basic interpreter in C

12. basic interpreter written in std C

 

 
Powered by phpBB® Forum Software