NetNews Usenet Archive 1992 #20

home *** CD-ROM | disk | FTP | other *** search

/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / sources / misc / 3919 < prev next >

Wrap

Text File | 1992-09-10 | 54.9 KB | 1,504 lines

Newsgroups: comp.sources.misc Path: sparky!kent From: chongo@toad.com (Landon Curt Noll) Subject: v32i028: ioccc.1992 - 1992 International Obfuscated C Code Contest winners, Part01/05 Message-ID: <csm-v32i028=ioccc.1992.103926@sparky.IMD.Sterling.COM> Followup-To: comp.sources.d X-Md4-Signature: fced55eeed9eefb316aacae723a465d0 Keywords: ioccc Sender: kent@sparky.imd.sterling.com (Kent Landfield) Reply-To: chongo@hoptoad.UUCP (Landon C. Noll) Organization: Nebula Consultants in San Francisco Date: Thu, 10 Sep 1992 15:40:38 GMT Approved: kent@sparky.imd.sterling.com Lines: 1488 Submitted-by: chongo@toad.com (Landon Curt Noll) Posting-number: Volume 32, Issue 28 Archive-name: ioccc.1992/part01 Environment: C Enclosed is the first of a 5 part shar file containing the winners of the 1992 International Obfuscated C Code Contest. First, we congratulate the winners for doing a fine job. Their efforts and feedback have resulted another good year for the contest. Second, the 1993 contest will not open until early March 1993. The rules are expected to be very similar to the 1992 rules, though the input format will change slightly. Please wait for the 1993 rules to be posted before submitting 1993 entries. Third, an International Obfuscated Perl contest is being considered. Larry Wall and Landon Curt Noll plan to formulate the contest rules (and a contest name) sometime this year. Watch comp.lang.perl for details. Send contest ideas (but not entries!) to chongo@toad.com. Last, we would like to make an apology to the 1992 winners and to the net for the delay in posting of these results. The poster of this article (chongo) went on vacation, held extended discussions with several of the contest winners and attempted to deal with one entry that appears to conflict with US export regulations. If you find problems with some of the contest entries, or find typos in our notes, please send ->PATCH FILES OR COMPLETE FILES<- containing the corrections to: judges@toad.com -or- ...!{sun,uunet,utzoo,pyramid}!hoptoad!judges chongo <Landon Curt Noll> /\cc/\ hoptoad!chongo Larry Bassel {uunet,ucbvax,cbosgd}|sun!lab p.s. previous winners are available on ftp.uu.net via anonymous ftp under the directory ~/pub/ioccc. Any 'patches' to the 1992 winners will be deposited there in a few months. =-= Send comments, questions, bugs to: judges@toad.com -or- ...!{sun,uunet,utzoo,pyramid}!hoptoad!judges You are strongly encouraged to read the new contest rules before sending any entries. The rules, and sometimes the contest Email address itself, change over time. A valid entry one year may be rejected in a later year due to changes in the rules. The typical start date for a contest is early March. The typical end date for a contest is early May. The contest rules are posted to comp.unix.wizards, comp.lang.c, misc.misc, alt.sources and comp.sources.d. If you do not have access to these groups, or if you missed the early March posting, you may request a copy from the judges, via Email, at the address above. ---- Cut Here and unpack ---- #! /bin/sh # This is a shell archive. Remove anything before this line, then feed it # into a shell via "sh file" or similar. To overwrite existing files, # type "sh file -c". # Contents: 1992 1992/buzzard.2.design 1992/gson.c 1992/guidelines # Wrapped by kent@sparky on Thu Sep 10 10:21:20 1992 PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin ; export PATH echo If this archive is complete, you will see the following message: echo ' "shar: End of archive 1 (of 5)."' if test ! -d '1992' ; then echo shar: Creating directory \"'1992'\" mkdir '1992' fi if test -f '1992/buzzard.2.design' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'1992/buzzard.2.design'\" else echo shar: Extracting \"'1992/buzzard.2.design'\" $25773 characters$ sed "s/^X//" >'1992/buzzard.2.design' <<'END_OF_FILE' X FIRST & THIRD X almost FORTH X X FORTH is a language mostly familiar to users of "small" machines. XFORTH programs are small because they are interpreted--a function Xcall in FORTH takes two bytes. FORTH is an extendable language-- Xbuilt-in primitives are indistinguishable from user-defined X_words_. FORTH interpreters are small because much of the system Xcan be coded in FORTH--only a small number of primitives need to Xbe implemented. Some FORTH interpreters can also compile defined Xwords into machine code, resulting in a fast system. X X FIRST is an incredibly small language which is sufficient for Xdefining the language THIRD, which is mostly like FORTH. There are Xsome differences, and THIRD is probably just enough like FORTH for Xthose differences to be disturbing to regular FORTH users. X X The only existing FIRST interpreter is written in obfuscated C, Xand rings in at under 800 bytes of source code, although through Xdeletion of whitespace and unobfuscation it can be brought to about X650 bytes. X X This document FIRST defines the FIRST environment and primitives, Xwith relevent design decision explanations. It secondly documents Xthe general strategies we will use to implement THIRD. The THIRD Xsection demonstrates how the complete THIRD system is built up Xusing FIRST. X X XSection 1: FIRST X X XEnvironment X X FIRST implements a virtual machine. The machine has three chunks Xof memory: "main memory", "the stack", and "string storage". When Xthe virtual machine wishes to do random memory accesses, they come Xout of main memory--it cannot access the stack or string storage. X X The stack is simply a standard LIFO data structure that is used Ximplicitly by most of the FIRST primitives. The stack is made up Xof ints, whatever size they are on the host machine. X X String storage is used to store the names of built-in and defined Xprimitives. Separate storage is used for these because it allows Xthe C code to use C string operations, reducing C source code size. X X Main memory is a large array of ints. When we speak of Xaddresses, we actually mean indices into main memory. Main memory Xis used for two things, primarily: the return stack and the dictionary. X X The return stack is a LIFO data structure, independent of Xthe abovementioned "the stack", which is used by FIRST to keep Xtrack of function call return addresses. X X The dictionary is a list of words. Each word contains a header Xand a data field. In the header is the address of the previous word, Xan index into the string storage indicating where the name of this Xword is stored, and a "code pointer". The code pointer is simply Xan integer which names which "machine-language-primitive" implements Xthis instruction. For example, for defined words the code pointer Xnames the "run some code" primitive, which pushes the current program Xcounter onto the return stack and sets the counter to the address of Xthe data field for this word. X X There are several important pointers into main memory. There is Xa pointer to the most recently defined word, which is used to start Xsearches back through memory when compiling words. There is a pointer Xto the top of the return stack. There is a pointer to the current Xend of the dictionary, used while compiling. X X For the last two pointers, namely the return stack pointer and Xthe dictionary pointer, there is an important distinction: the pointers Xthemselves are stored in main memory (in FIRST's main memory). This Xis critical, because it means FIRST programs can get at them without Xany further primitives needing to be defined. X X XInstructions X X There are two kinds of FIRST instructions, normal instructions and Ximmediate instructions. Immediate instructions do something significant Xwhen they are used. Normal instructions compile a pointer to their Xexecutable part onto the end of the dictionary. As we will see, this Xmeans that by default FIRST simply compiles things. X X Integer Operations XSymbol Name Function X - binary minus pop top 2 elements of stack, subtract, push X * multiply pop top 2 elements of stack, multiply, push X / divide pop top 2 elements of stack, divide, push X <0 less than 0 pop top element of stack, push 1 if < 0 else 0 X XNote that we can synthesize addition and negation from binary minus, Xbut we cannot synthesize a time efficient divide or multiply from it. X<0 is synthesizable, but only nonportably. X X Memory Operations XSymbol Name Function X @ fetch pop top of stack, treat as address to push contents of X ! store top of stack is address, 2nd is value; store to memory X and pop both off the stack X X Input/Output Operations XName Function Xecho output top of stack through C's putchar() Xkey push C's getchar() onto top of stack X_read read a space-delimited word, find it in the X dictionary, and compile a pointer to X that word's code pointer onto the X current end of the dictionary X XAlthough _read could be synthesized from key, we need _read to be able Xto compile words to be able to start any syntheses. X X Execution Operations XName Function Xexit leave the current function: pop the return stack X into the program counter X X Immediate (compilation) Operations XSymbol Name Function X : define read in the next space-delimited word, add it to X the end of our string storage, and generate X a header for the new word so that when it X is typed it compiles a pointer to itself X so that it can be executed. Ximmediate immediate when used immediately after a name following a ':', X makes the word being defined run whenever X it is typed. X X: cannot be synthesized, because we could not synthesize anything. Ximmediate has to be an immediate operation, so it could not be Xsynthesized unless by default operations were immediate; but that Xwould preclude our being able to do any useful compilation. X X Stack Operations XName Function Xpick pop top of stack, use as index into stack and copy up X that element X XIf the data stack were stored in main memory, we could synthesize pick; Xbut putting the stack and stack pointer in main memory would significantly Xincrease the C source code size. X X There are three more primitives, but they are "internal only"-- Xthey have no names and no dictionary entries. The first is X"pushint". It takes the next integer out of the instruction stream Xand pushes it on the stack. This could be synthesized, but probably Xnot without using integer constants. It is generated by _read when Xthe input is not a known word. The second is "compile me". When Xthis instruction is executed, a pointer to the word's data field is Xappended to the dictionary. The third is "run me"--the word's data Xfield is taken to be a stream of pointers to words, and is executed. X X One last note about the environment: FIRST builds a very small Xword internally that it executes as its main loop. This word calls X_read and then calls itself. Each time it calls itself, it uses Xup a word on the return stack, so it will eventually trash things. XThis is discussed some more in section 2. X X XHere's a handy summary of all the FIRST words: X X - * / binary integer operations on the stack X <0 is top of stack less than 0? X @ ! read from or write to memory X echo key output or input one character X _read read a word from input and compile a pointer to it X exit stop running the current function X : compile the header of a definition X immediate modify the header to create an immediate word X X Here is a sample FIRST program. I'm assuming you're using Xthe ASCII character set. FIRST does not depend upon ASCII, but Xsince FIRST has no syntax for character constants, one normally has Xto use decimal values. This can be gotten around using getchar, though. XOh. One other odd thing. FIRST initially builds its symbol table Xby calling : several times, so it needs to get the names of the base Xsymbols as its first 13 words of input. You could even name them Xdifferently if you wanted. X These FIRST programs have FORTH comments in them: they are contained Xinside parentheses. FIRST programs cannot have FORTH comments; but I need Xsome device to indicate what's going on. (THIRD programs are an entirely Xdifferent subject.) X X ( Our first line gives the symbols for the built-ins ) X: immediate _read @ ! - * / <0 exit echo key _pick X X ( now we define a simple word that will print out a couple characters ) X X: L ( define a word named 'L' ) X 108 echo ( output an ascii 'l' ) X exit X X: hello ( define a word named 'hello') X 72 echo ( output an ascii 'H' ) X 101 echo ( output an ascii 'e' ) X 111 ( push ascii 'o' onto the stack ) X L L ( output two ascii 'l's ) X echo ( output the 'o' we pushed on the stack before ) X 10 echo ( print a newline ) X exit ( stop running this routine ) X X: test immediate ( define a word named 'test' that runs whenever typed ) X hello ( call hello ) X exit X Xtest X X( The result of running this program should be: XHello X) X X XSection 2: Motivating THIRD X X What is missing from FIRST? There are a large number of Ximportant primitives that aren't implemented, but which are Xeasy to implement. drop , which throws away the top of the Xstack, can be implemented as { 0 * + } -- that is, multiply Xthe top of the stack by 0 (which turns the top of the stack Xinto a 0), and then add the top two elements of the stack. X X dup , which copies the top of the stack, can be easily Ximplemented using temporary storage locations. Conveniently, XFIRST leaves memory locations 3, 4, and 5 unused. So we can Ximplement dup by writing the top of stack into 3, and then Xreading it out twice: { 3 ! 3 @ 3 @ }. X X we will never use the FIRST primitive 'pick' in building THIRD, Xjust to show that it can be done; 'pick' is only provided because Xpick itself cannot be built out of the rest of FIRST's building Xblocks. X X So, instead of worrying about stack primitives and the Xlike, what else is missing from FIRST? We get recursion, but Xno control flow--no conditional operations. We cannot at the Xmoment write a looping routine which terminates. X X Another glaring dissimilarity between FIRST and FORTH is Xthat there is no "command mode"--you cannot be outside of a X: definition and issue some straight commands to be executed. XAlso, as we noted above, we cannot do comments. X X FORTH also provides a system for defining new data types, Xusing the words [in one version of FORTH] <builds and does> . XWe would like to implement these words as well. X X As the highest priority thing, we will build control flow Xstructures first. Once we have control structures, we can Xwrite recursive routines that terminate, and we are ready to Xtackle tasks like parsing, and the building of a command mode. X X By the way, location 0 holds the dictionary pointer, location X1 holds the return stack pointer, and location 2 should always Xbe 0--it's a fake dictionary entry that means "pushint". X X XSection 3: Building THIRD X X In this section, I'm going to keep my conversation X indented to this depth, rather than using fake comments-- X because we'll have real comments eventually. X X The first thing we have to do is give the symbols for our X built-ins. X X: immediate _read @ ! - * / < exit echo key _pick X X Next we want to be mildly self commenting, so we define X the word 'r' to push the *address of the return stack X pointer* onto the stack--NOT the value of the return X stack pointer. (In fact, when we run r, the value of X the return stack pointer is temporarily changed.) X X: r 1 exit X X Next, we're currently executing a short loop that contains X _read and recursion, which is slowly blowing up the return X stack. So let's define a new word, from which you can X never return. What it does is drops the top value off X the return stack, calls _read, then calls itself. Because X it kills the top of the return stack, it can recurse X indefinitely. X X: ] X r @ Get the value of the return stack pointer X 1 - Subtract one X r ! Store it back into the return stack pointer X _read Read and compile one word X ] Start over X X Notice that we don't need to exit, since we never come X back. Also, it's possible that an immediate word may X get run during _read, and that _read will never return! X X Now let's get compile running. X X: main immediate ] Xmain X X Next off, I'm going to do this the easy but non-portable X way, and put some character constant definitions in. X I wanted them at the top of the file, but that would have X burned too much of the return stack. X X: '"' 34 exit X: ')' 41 exit X: '\n' 10 exit X: 'space' 32 exit X: '0' 48 exit X: '-' 45 exit X X: cr '\n' echo exit X X Next, we want to define some temporary variables for X locations 3, 4, and 5, since this'll make our code look X clearer. X: _x 3 @ exit X: _x! 3 ! exit X: _y 4 @ exit X: _y! 4 ! exit X X Ok. Now, we want to make THIRD look vaguely like FORTH, X so we're going to define ';'. What ; ought to do is X terminate a compilation, and turn control over to the X command-mode handler. We don't have one, so all we want X ';' to do for now is compile 'exit' at the end of the X current word. To do this we'll need several other words. X X Swap by writing out the top two elements into temps, and X then reading them back in the other order. X: swap _x! _y! _x _y exit X Take another look and make sure you see why that works, X since it LOOKS like I'm reading them back in the same X order--in fact, it not only looks like it, but I AM! X X Addition might be nice to have. To add, we need to X negate the top element of the stack, and then subtract. X To negate, we subtract from 0. X: + X 0 swap - X - X exit X X Create a copy of the top of stack X: dup _x! _x _x exit X X Get a mnemonic name for our dictionary pointer--we need X to compile stuff, so it goes through this. X: h 0 exit X X We're going to need to advance that pointer, so let's X make a generic pointer-advancing function. X Given a pointer to a memory location, increment the value X at that memory location. X: inc X dup @ Get another copy of the address, and get the value X so now we have value, address on top of stack. X 1 + Add one to the value X swap Swap to put the address on top of the stack X ! exit Write it to memory X X , is a standard FORTH word. It should write the top of X stack into the dictionary, and advance the pointer X: , X h @ Get the value of the dictionary pointer X ! Write the top of stack there X h inc And increment the dictionary pointer X exit X X ' is a standard FORTH word. It should push the address X of the word that follows it onto the stack. We could X do this by making ' immediate, but then it'd need to X parse the next word. Instead, we compile the next word X as normal. When ' is executed, the top of the return X stack will point into the instruction stream immediately X after the ' . We push the word there, and advance the X return stack pointer so that we don't execute it. X: ' X r @ Get the address of the top of return stack X We currently have a pointer to the top of return stack X @ Get the value from there X We currently have a pointer to the instruction stream X dup Get another copy of it--the bottom copy will stick X around until the end of this word X 1 + Increment the pointer, pointing to the NEXT instruction X r @ ! Write it back onto the top of the return stack X We currently have our first copy of the old pointer X to the instruction stream X @ Get the value there--the address of the "next word" X exit X X Now we're set. ; should be an immediate word that pushes X the address of exit onto the stack, then writes it out. X: ; immediate X ' exit Get the address of exit X , Compile it X exit And we should return X X Now let's test out ; by defining a useful word: X: drop 0 * + ; X X Since we have 'inc', we ought to make 'dec': X: dec dup @ 1 - swap ! ; X X Our next goal, now that we have ;, is to implement X if-then. To do this, we'll need to play fast and X loose with the return stack, so let's make some X words to save us some effort. X X First we want a word that pops off the top of the normal X stack and pushes it on top of the return stack. We'll X call this 'tor', for TO-Return-stack. It sounds easy, X but when tor is running, there's an extra value on the X return stack--tor's return address! So we have to pop X that off first... We better just bite the bullet and X code it out--but we can't really break it into smaller X words, because that'll trash the return stack. X: tor X r @ @ Get the value off the top of the return stack X swap Bring the value to be pushed to the top of stack X r @ ! Write it over the current top of return stack X r @ 1 + r ! Increment the return stack pointer--but can't use inc X r @ ! Store our return address back on the return stack X; X X Next we want the opposite routine, which pops the top X of the return stack, and puts it on the normal stack. X: fromr X r @ @ Save old value X r @ 1 - r ! Decrement pointer X r @ @ Get value that we want off X swap Bring return address to top X r @ ! Store it and return X; X X Now, if we have a routine that's recursing, and we X want to be polite about the return stack, right before X we recurse we can run { fromr drop } so the stack won't X blow up. This means, though, that the first time we X enter this recursive routine, we blow our *real* return X address--so when we're done, we'll return up two levels. X To save a little, we make 'tail' mean { fromr drop }; X however, it's more complex since there's a new value on X top of the return stack. X: tail fromr fromr drop tor ; X X Now, we want to do 'if'. To do this, we need to convert X values to boolean values. The next few words set this X up. X X minus gives us unary negation. X: minus 0 swap - ; X X If top of stack is boolean, bnot gives us inverse X: bnot 1 swap - ; X X To compare two numbers, subtract and compare to 0. X: < - <0 ; X X logical turns the top of stack into either 0 or 1. X: logical X dup Get two copies of it X 0 < 1 if < 0, 0 otherwise X swap minus Swap number back up, and take negative X 0 < 1 if original was > 0, 0 otherwise X + Add them up--has to be 0 or 1! X; X X not returns 1 if top of stack is 0, and 0 otherwise X: not logical bnot ; X X We can test equality by subtracting and comparing to 0. X: = - not ; X X Just to show how you compute a branch: Suppose you've X compiled a call to branch, and immediately after it is X an integer constant with the offset of how far to branch. X To branch, we use the return stack to read the offset, and X add that on to the top of the return stack, and return. X: branch X r @ Address of top of return stack X @ Our return address X @ Value from there: the branch offset X r @ @ Our return address again X + The address we want to execute at X r @ ! Store it back onto the return stack X; X X For conditional branches, we want to branch by a certain X amount if true, otherwise we want to skip over the branch X offset constant--that is, branch by one. Assuming that X the top of the stack is the branch offset, and the second X on the stack is 1 if we should branch, and 0 if not, the X following computes the correct branch offset. X: computebranch 1 - * 1 + ; X X Branch if the value on top of the stack is 0. X: notbranch X not X r @ @ @ Get the branch offset X computebranch Adjust as necessary X r @ @ + Calculate the new address X r @ ! Store it X; X X here is a standard FORTH word which returns a pointer to X the current dictionary address--that is, the value of X the dictionary pointer. X: here h @ ; X X We're ALL SET to compile if...else...then constructs! X Here's what we do. When we get 'if', we compile a call X to notbranch, and then compile a dummy offset, because X we don't know where the 'then' will be. On the *stack* X we leave the address where we compiled the dummy offset. X 'then' will calculate the offset and fill it in for us. X: if immediate X ' notbranch , Compile notbranch X here Save the current dictionary address X 0 , Compile a dummy value X; X X then expects the address to fixup to be on the stack. X: then immediate X dup Make another copy of the address X here Find the current location, where to branch to X swap - Calculate the difference between them X swap ! Bring the address to the top, and store it. X; X X Now that we can do if...then statements, we can do X some parsing! Let's introduce real FORTH comments. X find-) will scan the input until it finds a ), and X exit. X: find-) X key Read in a character X ')' = Compare it to close parentheses X not if If it's not equal X tail find-) repeat (popping R stack) X then Otherwise branch here and exit X; X X: ( immediate X find-) X; X X( we should be able to do FORTH-style comments now ) X X( now that we've got comments, we can comment the rest of the code X in a legitimate [self parsing] fashion. Note that you can't X nest parentheses... ) X X: else immediate X ' branch , ( compile a definite branch ) X here ( push the backpatching address ) X 0 , ( compile a dummy offset for branch ) X swap ( bring old backpatch address to top ) X dup here swap - ( calculate the offset from old address ) X swap ! ( put the address on top and store it ) X; X X: over _x! _y! _y _x _y ; X X: add X _x! ( save the pointer in a temp variable ) X _x @ ( get the value pointed to ) X + ( add the incremement from on top of the stack ) X _x ! ( and save it ) X; X X: allot h add ; X X: maybebranch X logical ( force the TOS to be 0 or 1 ) X r @ @ @ ( load the branch offset ) X computebranch ( calculate the condition offset [either TOS or 1]) X r @ @ + ( add it to the return address ) X r @ ! ( store it to our return address and return ) X; X X: mod _x! _y! ( get x then y off of stack ) X _y _y _x / _x * ( y - y / x * x ) X - X; X X: printnum X dup X 10 mod '0' + X swap 10 / dup X if X printnum X echo X else X drop X echo X then X; X X: . X dup 0 < X if X '-' echo minus X then X printnum X 'space' echo X; X X: debugprint dup . cr ; X X( the following routine takes a pointer to a string, and prints it, X except for the trailing quote. returns a pointer to the next word X after the trailing quote ) X X: _print X dup 1 + X swap @ X dup '"' = X if X drop exit X then X echo X tail _print X; X X: print _print ; X X ( print the next thing from the instruction stream ) X: immprint X r @ @ X print X r @ ! X; X X: find-" X key dup , X '"' = X if X exit X then X tail find-" X; X X: " immediate X key drop X ' immprint , X find-" X; X X: do immediate X ' swap , ( compile 'swap' to swap the limit and start ) X ' tor , ( compile to push the limit onto the return stack ) X ' tor , ( compile to push the start on the return stack ) X here ( save this address so we can branch back to it ) X; X X: i r @ 1 - @ ; X: j r @ 3 - @ ; X X: > swap < ; X: <= 1 + < ; X: >= swap <= ; X X: inci X r @ 1 - ( get the pointer to i ) X inc ( add one to it ) X r @ 1 - @ ( find the value again ) X r @ 2 - @ ( find the limit value ) X <= X if X r @ @ @ r @ @ + r @ ! exit ( branch ) X then X fromr 1 + X fromr drop X fromr drop X tor X; X X: loop immediate ' inci @ here - , ; X X: loopexit X X fromr drop ( pop off our return address ) X fromr drop ( pop off i ) X fromr drop ( pop off the limit of i ) X; ( and return to the caller's caller routine ) X X: execute X 8 ! X ' exit 9 ! X 8 tor X; X X: :: ; ( :: is going to be a word that does ':' at runtime ) X X: fix-:: immediate 3 ' :: ! ; Xfix-:: X X ( Override old definition of ':' with a new one that invokes ] ) X: : immediate :: ] ; X X: command X here 5 ! ( store dict pointer in temp variable ) X _read ( compile a word ) X ( if we get control back: ) X here 5 @ X = if X tail command ( we didn't compile anything ) X then X here 1 - h ! ( decrement the dictionary pointer ) X here 5 @ ( get the original value ) X = if X here @ ( get the word that was compiled ) X execute ( and run it ) X else X here @ ( else it was an integer constant, so push it ) X here 1 - h ! ( and decrement the dictionary pointer again ) X then X tail command X; X X: make-immediate ( make a word just compiled immediate ) X here 1 - ( back up a word in the dictionary ) X dup dup ( save the pointer to here ) X h ! ( store as the current dictionary pointer ) X @ ( get the run-time code pointer ) X swap ( get the dict pointer again ) X 1 - ( point to the compile-time code pointer ) X ! ( write run-time code pointer on compile-time pointer ) X; X X: <build immediate X make-immediate ( make the word compiled so far immediate ) X ' :: , ( compile '::', so we read next word ) X 2 , ( compile 'pushint' ) X here 0 , ( write out a 0 but save address for does> ) X ' , , ( compile a push that address onto dictionary ) X; X X: does> immediate X ' command , ( jump back into command mode at runtime ) X here swap ! ( backpatch the build> to point to here ) X 2 , ( compile run-code primitive so we look like a word ) X ' fromr , ( compile fromr, which leaves var address on stack ) X; X X X: _dump ( dump out the definition of a word, sort of ) X dup " (" . " , " X dup @ ( save the pointer and get the contents ) X dup ' exit X = if X " ;)" cr exit X then X . " ), " X 1 + X tail _dump X; X X: dump _dump ; X X: # . cr ; X X: var <build , does> ; X: constant <build , does> @ ; X: array <build allot does> + ; X X: [ immediate command ; X: _welcome " Welcome to THIRD. XOk. X" ; X X: ; immediate ' exit , command exit X X[ X X_welcome X END_OF_FILE if test 25773 -ne `wc -c <'1992/buzzard.2.design'`; then echo shar: \"'1992/buzzard.2.design'\" unpacked with wrong size! fi # end of '1992/buzzard.2.design' fi if test -f '1992/gson.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'1992/gson.c'\" else echo shar: Extracting \"'1992/gson.c'\" $1513 characters$ sed "s/^X//" >'1992/gson.c' <<'END_OF_FILE' X#include <stdio.h> X Xlong a X[4],b[ X4],c[4] X,d[0400],e=1; Xtypedef struct f{long g X,h,i[4] ,j;struct f*k;}f;f g,* Xl[4096 ]; char h[256],*m,k=3; X long n (o, p,q)long*o,*p,*q;{ X long r =4,s,i=0;for(;r--;s=i^ X *o^*p, i=i&*p|(i|*p)&~*o++,*q X ++=s,p ++);return i;}t(i,p)long*p X ;{*c=d [i],n(a,c,b),n(p,b,p);}u(j)f*j;{j->h X =(j->g =j->i[0]|j->i[1]|j->i[2]|j->i[3])&4095;}v( Xj,s)f* j; {int i; for(j->k->k&&v(j->k, ' '),fseek( Xstdin, j->j, 0);i=getchar(),putchar(i-'\n'?i:s),i- X'\n';);}w(o,r,j,x,p)f*o,*j;long p;{f q;int Xs,i=o->h;q.k=o;r>i?j=l[r=i]:r<i&& X(s=r&~i)?(s|=s>>1, s|=s X>>2,s|=s>>4,s X|=s>>8 X,j=l[r X=((r&i X |s)&~(s>>1))-1&i]):0;--x;for X (;x&&!(p&i);p>>=1);for(;!x&&j;n(o->i,j->i,q. X i),u(&q),q.g||(q.j=j->j,v(&q,'\n')),j=j->k);for(;x;j=x X ?j->k:0){for(;!j&&((r=(r&i)-1&i)-i&&(r&p)?2:(x=0));j=l[r]);! X x||(j->g&~o->g)||n (o->i,j->i,q.i)||( X u(&q), q.j=j ->j,q.g?w(&q X ,r,j->k,x ,p):v(&q, X '\n')); }}y(){f X j;char *z,*p; Xfor(;m ? j.j= Xftell( stdin) X,7,(m= gets(m ))||w( X&g,315 *13,l[ 4095] X ,k,64* 64)&0: 0;n(g X .i,j.i, b)||(u (&j),j. X k=l[j.h],l[j.h]= &j,y())){for(z= p=h;*z&&( X d[*z++]||(p=0)););for(z=p?n(j.i ,j.i,j.i)+h:""; X *z;t(*z++,j.i));}}main(o,p)char** p; {for(;m = *++p;)for(;*m- X'-'?*m:(k= -atoi(m))&0;d[*m]||(d[*m ]=e,e<<=1),t(*m++,g.i)); u(& X g),m=h X ,y();} END_OF_FILE if test 1513 -ne `wc -c <'1992/gson.c'`; then echo shar: \"'1992/gson.c'\" unpacked with wrong size! fi # end of '1992/gson.c' fi if test -f '1992/guidelines' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'1992/guidelines'\" else echo shar: Extracting \"'1992/guidelines'\" $22215 characters$ sed "s/^X//" >'1992/guidelines' <<'END_OF_FILE' X9th International Obfuscated C Code Contest Guidelines, Hints and Comments X X XABOUT THIS FILE: X X This file is intended to help people who wish to submit entries to X the International Obfuscated C Code Contest (IOCCC for short). X X This is not the IOCCC rules, though it does contain comments about X them. The guidelines should be viewed as hints and suggestions. X Entries that violate the guidelines but remain within the rules are X allowed. Even so, you are safer if you remain within the guidelines. X X You should read the current IOCCC rules, prior to submitting entries. X The rules are typically sent out with these guidelines. X X XWHAT IS NEW IN 1992: X X The size rules are different this year. There is a more relaxed X rule to encourage formatting styles beyond rectangular blobs of C X code. The build file (how to compile) has been expanded as well. X See the rules, and OUR LIKES AND DISLIKES for details. X X The entry format is better (for us anyway). The program mkentry.c X provides a convenient way to form an entry. See ENTRY FORMAT. X X The original entry source, build and resulting binary should be X treated as read-only. There is a provision to allow entries to X modify these files indirectly. See ENTRY FORMAT. X X This year, we are experimenting with a new category of programs: X X clients. X client entries should be as portable as possible. X See OUR LIKES AND DISLIKES. X X XHINTS AND SUGGESTIONS: X X You are encouraged to examine the winners of previous contests. See X FOR MORE INFORMATION for details on how to get previous winners. X X Keep in mind that rules change from year to year, so some winning entries X may not be valid entries this year. What was unique and novel one year X might be 'old' the next year. X X An entry is usually examined in a number of ways. We typically apply X a number of tests to an entry: X X * look at the original source X * If it is ANSI, convert tri-graphs to ASCII X * C pre-process the source ignoring '#include' lines X * C pre-process the source ignoring '#define' and '#include' lines X * run it through a C beautifier X * examine the algorithm X * lint it X * compile it X * execute it X X You should consider how your entry looks in each of the above tests. X You should ask yourself if your entry remains obscure after it has been X 'cleaned up' by the C pre-processor and a C beautifier. X X Your entry need not do well under all, or in most tests. In certain X cases, a test is not important. Entries that compete for the X 'strangest/most creative source layout' need not do as well as X others in terms of their algorithm. On the other hand, given X two such entries, we are more inclined to pick the entry that X does something interesting when you run it. X X We try to avoid limiting creativity in our rules. As such, we leave X the contest open for creative rule interpretation. As in real life X programming, interpreting a requirements document or a customer request X is important. For this reason, we often award 'worst abuse of the X rules' to an entry that illustrates this point in an ironic way. X X If you do plan to abuse the rules, we suggest that you let us know X in the remarks section. Please note that an invitation to abuse X is not an invitation to break. We are strict when it comes to the X 3217 byte size limit. Also, abusing the entry format tends to X annoy more than amuse. X X We do realize that there are holes in the rules, and invite entries X to attempt to exploit them. We will award 'worst abuse of the rules' X and then plug the hole next year. Even so, we will attempt to use X the smallest plug needed, if not smaller. :-) X X Check out your program and be sure that it works. We sometimes make X the effort to debug an entry that has a slight problem, particularly X in or near the final round. On the other hand, we have seen some X of the best entries fall down because they didn't work. X X We tend to look down on a prime number printer, that claims that X 16 is a prime number. If you do have a bug, you are better off X documenting it. Noting "this entry sometimes prints the 4th power X of a prime by mistake" would save the above entry. And sometimes, X a strange bug/feature can even help the entry! Of course, a correctly X working entry is best. X X XOUR LIKES AND DISLIKES: X X Doing masses of #defines to obscure the source has become 'old'. We X tend to 'see thru' masses of #defines due to our pre-processor tests X that we apply. Simply abusing #defines or -Dfoo=bar won't go as far X as a program that is more well rounded in confusion. X X Many ANSI C compilers dislike the following code, and so do we: X X #define d define X #d foo <-- don't expect this to turn into #define foo X X int i; X j; <-- don't use such implicit type declarations X int k; X X We suggest that you use ANSI C compilers if possible. If you must X use non-ANSI C, such as K&R C, try to avoid areas that give ANSI C X compilers problems. X X Small programs are best when they are short, obscure and concise. X While such programs are not as complex as other winners, they do X serve a useful purpose. They are often the only program that people X attempt to completely understand. For this reason, we look for X programs that are compact, and are instructional. X X One line programs should be short one line programs, say around 80 X bytes long. Getting close to 160 bytes is a bit too long for one liners X in our books. X X We tend to dislike programs that: X X * are very hardware specific X * are very OS or Un*x version specific X (index/strchr differences are ok, but socket/streams specific X code is likely not to be) X * dump core or have compiler warnings X (it is ok only if you warn us in the 'remark' header item) X * won't compile under both BSD or SYS V Un*x X * abusing the build file to get around the size limit X * obfuscate by excessive use of ANSI tri-graphs X * are longer than they need to be X * are similar to previous winners X * are identical to previous losers :-) X X Unless you are cramped for space, or unless you are entering the X 'best one liner' category, we suggest that you format your program X in a more creative way than simply forming excessively long lines. X X The build file should not be used to try and get around the size X limit. It is one thing to make use of a several -D's to help out, X but it is quite another to use 200+ bytes of -D's in order to X try and squeeze the source under the size limit. You should feel X free to make use of the build file space, but you are better off X if you show some amount of restraint. X X We allowed whitespace, and in certain cases ; { or } do not impact X your program size (up to a certain point), because we want to get X away from source that is simply a compact blob of characters. X X Given two versions of the same program, one that is a compact blob X of code, and the other that is formatted more like a typical C X program, we tend to favor the second version. Of course, a third X version of the same program that is formatted in an interesting X and/or obfuscated way, would definitely win over the first two! X X We suggest that you avoid trying for the 'smallest self-replicating' X program. We are amazed at the many different sizes that claim X to be the smallest. There is nothing wrong with self-replicating X programs. In fact, a number of winners have been self-replicating. X You might want to avoid the claim of 'smallest', lest we (or others) X know of a smaller one! X X X client entries should be as portable as possible. Entries that X adapt to a wide collection of environments will be favored. Don't X depend on a particular type of display. For example, don't depend X on color or a given size. Don't require backing store. X X X client entries should avoid using X related libraries and X software that is not in wide spread use. We ask that such X client X entries restrict themselves to only the low level Xlib and the X Athena widget set (libX11.a, libXaw.a, libXmu.a and libXt.a). X Don't use M*tif, Xv*ew, or OpenL*ok toolkits, since not everyone X has them. Avoid depending on a particular window manager. Not X everyone has X11r5, and some people are stuck back in X11r3 (or X earlier), so try to target X11r4 without requiring X11r4. Better X yet, try to make your entry run on all version 11 X Window Systems. X X X client entries should not to depend on particular items on X .Xdefaults. If you must do so, be sure to note the required lines X in the ---remark--- section. Better yet, give an xrdb -merge X command as part of the build. X X We like programs that: X X * are as concise and small as they need to be X * do something at least quasi-interesting X * pass lint without complaint (not a requirement, but it is nice) X * are portable X * are unique or novel in their obfuscation style X * MAKE USE OF A NUMBER OF DIFFERENT TYPES OF OBFUSCATION X * make us laugh and/or throw up :-) X X Some types of programs can't excel in some areas. Of course, your X program doesn't have to excel in all areas, but doing well in several X areas really does help. X X We freely admit that interesting, creative or humorous comments in X the ---remark--- section helps your chance of winning. If you had to X read of many twisted entries, you too would enjoy a good laugh or two. X We think the readers of the contest winners do as well. X X Be creative! X X XENTRY FORMAT: X X In order to help us process the many entries, we must request your X assistance by formatting your entries in a certain way. This format, X in addition, allows us to quickly separate information about the X author from the program itself. (see JUDGING PROCESS) X X We have provided the program, mkentry, as an example of how to X format entries. You should be aware of the following warning that X is found in mkentry.c: X X This program attempts to implement the IOCCC rules. Every X attempt has been made to make sure that this program produces X an entry that conforms to the contest rules. In all cases, X where this program differs from the contest rules, the X contest rules will be used. Be sure to check with the X contest rules before submitting an entry. X X You are not required to use mkentry. It is convenient, however, X as it attempts to uuencode the needed files, and attempt to check X the entry against the size rules. X X If you have any suggestions, comments, fixes or complaints about X the mkentry.c program, please send Email to the judges. (see below) X X The following is a sample entry: X X---entry--- Xrule: 1992 Xtitle: chonglab Xentry: 0 Xdate: Mon Feb 17 13:58:57 1992 Xhost: Un*x v6, pdp11/45 X 2.9BSD, pdp11/70 X---remark--- X This is a non-obfuscated obfuscated C program. X X It is likely not to win a prize. But what do you expect from X a short example! (yes, Hello world progs have become old too) X---author--- Xname: Landon Curt Noll Xorg: IOCCC Judging Group Xaddr: Toad Hall X San Francisco, CA 94101 X USA Xemail: chongo@toad.com Xanon: n X---author--- Xname: Larry Bassel Xorg: IOCCC Judging Group Xaddr: Toad Hall X San Francisco, CA 94101 X USA Xemail: hoptoad!sun!lab X lab@sun.com Xanon: n X---info--- Xbegin 444 info.file XM2&$A("!792!G;W0@>6]U('1O(&QO;VLA"@I4:&%T('1H870@:7,L(&ES+@I4 XM:&%T('1H870@:7,@;F]T+`H@("`@:7,@;F]T('1H870@=&AA="!N;W0@:7,N XM"E1H870@:7,L('1H870@=&AA="!I<R!N;W0L(&ES(0H*"0DM+2!C:&]N9V\@ X%,3DW-`H@ X` Xend X---build--- Xbegin 444 build X28V,@<')O9RYC("UO('!R;V<* X` Xend X---program--- Xbegin 444 prog.c XC;6%I;B@I>W!R:6YT9B@B2&5L;&\L('=O<FQD(5QN(BD[?0H` X` Xend X---end--- X X Where build uudecodes into: X Xcc prog.c -o prog X X and prog.c uudecodes into: X Xmain(){printf("Hello, world!\n");} X X Typically the build file should assume that the source is prog.c X and will compile into prog. If an entry wins, we will rename X its source and binary to avoid filename collision. By tradition, X we use the name of the entry's title, followed by an optional X digit in case of name conflicts. X X If the above entry somehow won the 'least likely to win' award, X we would use chonglab.c and chonglab. X X If your entry depends on, or requires that your build, source X and/or binary files be a particular name, please say so in the X ---remark--- section. If this case applies, it would be be helpful X if you did one of the following: X X * Tell us how to change the filename(s) in your entry. X X * Have the build file make copies of the files. For example: X X cc prog.c -o special_name need special binary X X or rm -f special_src.c need special source X cp prog.c special_src.c X cc special_src.c -o special_name X X or rm -f special_build need special build X tail +4 build > special_build X sh < special_build X X * Assume that we will use the entry title. Send us a version of X your build/program files that uses the name convention. You X should uuencode these files in ---data--- sections. X X If your entry needs to modify its source, info or binary files, X please say so in the ---remark--- section. You should try to avoid X touching your original build, source and binary files. You should X arrange to make copies of the files you intend to modify. This X will allow people to re-generate your entry from scratch. X X Remember that your entry may be built without a build file. We X typically incorporate the build lines into a Makefile. If the X build file must exist, say so in the ---remark--- section. X X If your entry needs special info files, you should uuencode them X into ---info--- sections. In the case of multiple info files, X use multiple ---info--- sections. If no info files are needed, X then skip the ---info--- section. X X Info files are intended to be input, or detailed information that X does not fit well into the ---remark--- section. For example, an X entry that implements a compiler might want to provide some sample X programs for the user to compile. An entry might want to include a X lengthly design document, that might not be appropriate for a X 'hints' file. X X Info files should be used only to supplement your entry. For X example, info files may provide sample input or detailed X information about your entry. Because they are supplemental, X the entry should not require them exist. X X In some cases, your info files might be renamed to avoid name X conflicts. If info files should not be renamed for some reason, X say so in the ---remark--- section. X X Info files must uudecode into the current directory. If they X absolutely must be renamed, or moved into a sub-directory, say X so in the ---remark--- section. X X XJUDGING PROCESS: X X Entries are judged by Larry Bassel and Landon Curt Noll. X X Entries are unpacked into individual directories. The Email message X is unpacked into individual files, each containing: X X ---entry--- section X all ---author--- sections X all ---info--- sections X ---build--- section X ---program--- section X any other text, including the Email message headers X X Prior to judging, the 'any other text' file is scanned to be sure X it does not contain useful information (or in case the entry was X malformed and did not unpack correctly). Information from the X ---author--- sections are not read until the judging process is X complete, and then only from entries that have won an award. X X The above process helps keep us biased for/against any one particular X individual. We are usually kept in the dark as much as you are X until the final awards are given. We like the surprise of finding X out in the end, who won and where they were from. X X We attempt to keep all entries anonymous, unless they win an award. X Because the main 'prize' of winning is being announced, we make all X attempts to send non-winners into oblivion. We remove all non-winning X files, and shred all related paper. By tradition, we do not even X reveal the number of entries that we received. (for the curious, X we do indicate the volume of paper consumed when presenting the IOCCC X winners at talks) X X After the Usenix announcement, we attempt to send Email to the X authors of the winning entries. One reason we do this is to give X the authors a chance to comment on the way we have presented their X entry. They are given the chance to correct mistakes, typos. We X often accept their suggestions/comments about our remarks as well. X This is done prior to posting the winners to the wide world. X X Judging consists of a number of elimination rounds. During a round, X the collection of entries are divided into two roughly equal piles; X the pile that advances on to the next round, and the pile that does X not. We also re-examine the entries that were eliminated in the X previous round. Thus, an entry gets at least two readings. X X A reading consists of a number of actions: X X * reading the ---entry--- section X * reading the uudecoded ---build--- section X * reading the uudecoded ---program--- section X * reading the uudecoded ---info--- section(s), if any X * passing the source thru the C pre-processor X shipping over any #include files X * performing a number of C beautify/cleanup edits on the source X * passing the beautified source thru the C pre-processor X shipping over any #include files X X In later rounds, other actions are performed: X X * linting the source X * compiling/building the source X * running the program X * performing misc tests on the source and binary X X Until we reduce the stack of entries down to about 25 entries, entries X are judged on an individual basis. An entry is set aside because it X does not, in our opinion, meet the standard established by the round. X When the number of entries thins to about 25 entries, we begin to form X award categories. Entries begin to compete with each other for awards. X An entry often will compete in several categories. X X The actual award category list will vary depending on the types of entries X we receive. A typical category list might be: X X * best small one line program X * best small program X * strangest/most creative source layout X * most useful obfuscated program X * best game that is obfuscated X * most creatively obfuscated program X * most deceptive C code X * best X client (see OUR LIKES AND DISLIKES) X * best abuse of ANSI C X * worst abuse of the rules X * <anything else so strange that it deserves an award> X X We do not limit ourselves to this list. For example, a few entries are so X good/bad that they are declared winners at the start of the final round. X We will invent awards categories for them, if necessary. X X In the final round process, we perform the difficult tasks of X reducing the remaining entries (typically about 25) down to 8 or 10 X winners. Often we are confident that the entries that make it into X the final round are definitely better than the ones that do not X make it. The selection of the winners out of the final round, is X less clear cut. X X Sometimes a final round entry good enough to win, but is beat out X by a similar, but slightly better entry. For this reason, it is X sometimes worthwhile to re-enter an entry that failed to win on a X previous year. There have been winners that lost in a previous X year. Of course, in those cases, improving on the entry made X the difference! X X More often that not, we select a small entry (usually one line), a X strange/creative layout entry, and an entry that abuses the contest X rules in some way. X X In the end, we traditionally pick one entry as 'best'. Sometimes such X an entry simply far exceeds any of the other entry. More often, the X 'best' is picked because it does well in a number of categories. X X XANNOUNCEMENT OF WINNERS: X X The first announcement, occurs at a Summer Usenix conference. By X tradition, this is done during the latter part of the UUNET/IOCCC BOF, X just prior to the Berkeley BSD, and BSDI BOF. X X Winning entries will be posted in late June to the following groups: X X comp.lang.c comp.unix.wizards alt.sources X X In addition, pointers to these postings are posted to the following X X comp.sources.d alt.sources.d misc.misc X comp.sources.misc X X Winning entries will be deposited into the uunet archives. See X below for details. X X Often, winning entries are published in magazines such as "The C Users X Journal". Winners have appeared in books ("The New Hackers Dictionary") X and on T-Shirts. X X Last, but not least, winners receive international fame and flames! :-) X X XFOR MORE INFORMATION: X X You may contact the judges by sending Email to the following address: X X ...!{apple,pyramid,sun,uunet}!hoptoad!judges (not the address for X judges@toad.com submitting entries) X X Questions and comments about the contest are welcome. X X One may obtain a copy of the current rules, guidelines or mkentry X program as well. To stream line these common requests, we request X that you use the following subjects when making such requests: X X subject to request X ------- ---------- X send rules to obtain the current IOCCC rules X send guidelines to obtain the current IOCCC guidelines X send mkentry to obtain the current IOCCC mkentry program X send allinfo to obtain the current IOCCC rules,guidelines,mkentry X X One may also obtain the above items, we well as winners of previous X contests, via anonymous ftp from: X X host: ftp.uu.net (137.39.1.9) X user: anonymous X pass: yourname@yourhost X dir: pub/ioccc X X Often, contest rules, guidelines and winners are available from X archive sites. Check comp.sources.unix archives, for example. X You may also request previous winners by Email, using the judges X Email address, though we ask that you do this as a last resort. X X Xchongo <Landon Curt Noll> /\cc/\ hoptoad!chongo XLarry Bassel {uunet,ucbvax,cbosgd}|sun!lab END_OF_FILE if test 22215 -ne `wc -c <'1992/guidelines'`; then echo shar: \"'1992/guidelines'\" unpacked with wrong size! fi # end of '1992/guidelines' fi echo shar: End of archive 1 $of 5$. cp /dev/null ark1isdone MISSING="" for I in 1 2 3 4 5 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 5 archives. rm -f ark[1-9]isdone else echo You still must unpack the following archives: echo " " ${MISSING} fi exit 0 exit 0 # Just in case...