NetNews Usenet Archive 1992 #20

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

/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / comp / lang / c / 13354 < prev next >

Wrap

Internet Message Format | 1992-09-08 | 60.4 KB

Xref: sparky comp.lang.c:13354 comp.sources.d:1252 comp.unix.wizards:3852 alt.sources:2022 misc.misc:3277 Path: sparky!uunet!cis.ohio-state.edu!ucbvax!hoptoad!chongo From: chongo@hoptoad.uucp (Landon C. Noll) Newsgroups: comp.lang.c,comp.sources.d,comp.unix.wizards,alt.sources,misc.misc Subject: 1992 International Obfuscated C Code Contest winners, 3 of 4 Keywords: ioccc Message-ID: <34850@hoptoad.uucp> Date: 9 Sep 92 01:41:50 GMT Expires: 28 Nov 92 00:00:00 GMT Reply-To: chongo@hoptoad.UUCP (Landon C. Noll) Organization: Nebula Consultants in San Francisco Lines: 1737 Submitted-by: chongo@toad.com (Landon Curt Noll) # # 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. # Archive-name: ioccc.1992/part03 ---- Cut Here and unpack ---- #!/bin/sh # This is part 03 of ioccc.1992 if touch 2>&1 | fgrep 'amc' > /dev/null then TOUCH=touch else TOUCH=true fi # ============= 1992/buzzard.2.design ============== echo "x - extracting 1992/buzzard.2.design (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/buzzard.2.design && 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 SHAR_EOF $TOUCH -am 0908155392 1992/buzzard.2.design && chmod 0444 1992/buzzard.2.design || echo "restore of 1992/buzzard.2.design failed" set `wc -c 1992/buzzard.2.design`;Wc_c=$1 if test "$Wc_c" != "25773"; then echo original size 25773, current size $Wc_c fi # ============= 1992/buzzard.2.hint ============== echo "x - extracting 1992/buzzard.2.hint (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/buzzard.2.hint && XBest Language Tool: <sean@stat.tamu.edu> Sean Barrett X X Sean Barrett X Software Construction Company X 430 Southwest Parkway, #1906 X College Station, TX 77840 X USA X X Direct bounced email to <jon@stat.tamu.edu>. X XJudges' comments: X X First: X make first X X Second: X echo help | cat third help.th - | first X cat third demo5.th | first X X Third: X cat third help.th - | first X X Wait until Ok is printed and the type: X 2 3 + . cr <-- yes you should really type the 2 letters: cr X X Forth: X Sorry, this is third! X X XSelected notes from the author: X X What it does: X X first implements a relatively primitive stack machine. How X primitive? It supplies 13 visible primitives: 3 arithmetic, X 1 comparison, 2 memory-access, 2 character I/O, 3 primitives X for defining new words, 1 tokenizing, and 1 special stack X operation. (There are also three internal operations for X the stack machine: 'push this integer', 'call this code', X and 'compile a call to this code'.) X X It is very difficult to accomplish anything with this set X of primitives, but they do have an interesting property. X X This--what this interesting property is, or in other words X what first is good for--is the major obfuscation; there are X also minor source obfuscations, as well as some design tricks X that are effectively obfuscations. Details on the obfuscations X are below, and the interesting property is discussed much X further down. X X X How to run it: X X first expects you to first enter the names of the 13 primitives, X separated by whitespace--it doesn't care what you name them, but X if all the names aren't unique, you won't be able to use some of X them. After this you may type any sequence of valid first input. X Valid first input is defined as any sequence of whitespace-delimited X tokens which consist of primitives, new words you've defined, and X integers (as parsed by "%d"). Invalid input behaves unpredictably, X but gives no warning messages. A sample program, demo1.1st, is X included, but it only works on ASCII systems. X X Do not expect to be able to do anything interesting with first. X X To do something interesting, you need to feed first the file X third first. In unix, you can do X X % cat third help.th - | first X X to do this. Hopefully most operating systems will provide a X way to do this. It may take some time for this to complete X (I seem to remember it taking several minutes on an 8086 PC); X THIRD will prompt you when it is finished. The file third has X not been obfuscated, due to sheer kindness on the author's part. X X For more information on what you can do once you've piped X THIRD into first, type 'help' and consult FORTH manuals for X further reference. Six sample THIRD programs are included X in the files demo[1-6].th. buzzard.2.README has more X information. X X Keep in mind that you are still running first, and X are for the most part limited by first's tokenizer X (notably, unknown words will attempt to be parsed as X integers.) It is possible to build a new parser that X parses by hand, reading a single character at a time; X however, such a parser cannot easily use the existing X dictionary, and so would have to implement its own, X thus requiring reimplementing all of first and third X a second time--I did not care to tackle this project. X X X Compiling: X X first is reasonably portable. You may need to adjust the X size of the buffers on smaller machines; m[] needs to be X at least 2000 long, though. X X I say first is portable mainly because it uses native types. X Unlike FORTH, which traditionally allows byte and multi-byte X operations, all operations are performed on C 'int's. That X means first code is only as portable as the same code would X be in C. As in C, the result of dividing -1 by 2 is machine X (or rather compiler) dependent. X X How is first obfuscated? X X first is obfuscated in several ways. Some minor obfuscations X like &w[&m[1]][s] for s+m[w+1] were in the original source X but are no longer because, apparently, ANSI doesn't allow it X (gcc -ansi -pedantic doesn't mind it, though.) X Other related obfuscations are still present. The top of the X stack is cached in a variable, which increases performance X massively if the compiler can figure out to keep it in a register; X it also obfuscates the code. (Unfortunately, the top of stack X is a global variable and neither gcc nor most bundled compilers X seem to register allocate it.) X X More significant are the design obfuscations. m[0] is the X "dictionary pointer", used when compiling words, and m[1] is X the return stack index. Both are used as integer offsets into X m. Both are kept in m, instead of as separate pointers, X because they are then accessible to first programs, which is a X crucial property of first. Similarly the way words are stored X in the dictionary is not obvious, so it can be difficult to X follow exactly what the compiler words are doing. X X Assuming you've waded through all that, you still have X to penetrate the most significant obfuscation. Traditionally, X the question is whether a reader can answer the question "what X will this do when I run it". A reader who has deciphered first X to this point may think they know the answer to this question, X but they may not know the answer to the more important question, X "what will this program do when given the right input?" FORTH X afficianados, and especially FORTH implementors, may recognize X the similarity of the internal compiler format to many FORTH X interal representations, and, being aware that FORTH interpreters X can often by self-compiling, may be suspicious that this program X can compile FORTH, or a significant subset of it, or at least be X capable of doing so if fed the right input. Of course, the name X "THIRD" should be a dead giveaway, if the name "first" wasn't. X (These numbers were largely chosed because they were five letters X long, like "FORTH", and would not require truncation to five X letters, which would be a dead giveaway. Besides, THIRD represents X a step backwards, in more ways than one.) X X X What exactly is first, then? X X first is a tiny interpreter which implements a sufficient X pseudo-subset of FORTH to allow it to bootstrap a relatively X complete version of FORTH (based loosely on forth79), which X I call THIRD. Complete relative to what, I'm not sure. X X I believe first is close to the smallest amount of code possible X to get this effect *using forth-style primitives*, and still have X some efficiency (it is possible to get by without multiplication X if you have addition, obviously). In the design file, design, X I give a justification for why each primitive in first was included. X X THIRD is sorta slow, because first has so few primitives that X many things that are primitives in FORTH (like swap) take a X significant amount of time in THIRD. X X When you get the 'Ok.' message from third, try out some sample X FORTH code (first has no way of knowing if keyboard input is X waiting, so it can't actually prompt you in a normal way. It X only prints 'Ok.' after you define a word). X X 2 3 + . cr ( add 2 and 3, and print it and a newline.) X X and THIRD responds X X 5 X X Now try: X X : test 11 1 do i . loop cr ; X test X X and THIRD responds X X 1 2 3 4 5 6 7 8 9 10 X X X When in THIRD, you can see how much space you're currently X using by typing X X here . X X The number THIRD replies is the number of machine words (ints) X that the dictionary (the first code) takes up, plus the X 512 ints for the return stack. If you compile the basic X THIRD system without the help word (strings take up one X int per character in the string!), you should find that X you're using around 1000 ints (plus the return stack). X X Thus THIRD gives you a relatively complete FORTH system in X less than 700 chars of C source + about 1000 ints of X memory--and it's portable too (you could copy over the X THIRD memory dump to another machine, in theory). If the X above numbers seem to you to be mixing apples and oranges X (C source and compiled THIRD code), note that you should X in theory be able to stick the compiled THIRD code into X the C source. X X X Software Construction Company gets credit for rekindling X my interest in FORTH and thus indirectly inspiring me X to write this program. SHAR_EOF $TOUCH -am 0908160292 1992/buzzard.2.hint && chmod 0444 1992/buzzard.2.hint || echo "restore of 1992/buzzard.2.hint failed" set `wc -c 1992/buzzard.2.hint`;Wc_c=$1 if test "$Wc_c" != "8915"; then echo original size 8915, current size $Wc_c fi # ============= 1992/buzzard.2.orig.c ============== echo "x - extracting 1992/buzzard.2.orig.c (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/buzzard.2.orig.c && X#define c 0 [m] ++ [m] = X#define z;break;case X Xchar s[5000]; Xint m[20000]={32},L=1,I,T[500],*S=T,t=64,w,f; X Xa(x) X{ X c L; X L= *m-1; X c t; X c x; X scanf("%s",s+t); X t+=strlen(s+t)+1; X} X Xr(x) X{ X switch(x++[m]){ X z 5: for(w=scanf("%s",s)<1?exit(0):L;strcmp(s,&w[&m[1]][s]);w=m[w]); X w-1 ? r(w+2) : (c 2,c atoi(s)) X z 12: I=1[m]--[m] X z 15: f=S[-f] X z 1: c x X z 9: f *=* S-- X z 7: m[f]= *S--; X f= *S-- X z 0: *++S=f; X f=I++[m] X z 8: f= *S --- f X z 2: m[++1[m]]=I; X I=x X z 11: f=0>f X z 4: *m-=2;c 2 X z 6: f=f[m] X z 10: f= *S--/f X z 3: a(1); X c 2 X z 13: putchar(f); X f= *S-- X z 14: *++S=f; X f=getchar(); X } X} X Xmain() X{ X a(3); X a(4); X a(1); X w= *m; X c 5; X c 2; X I= *m; X c w; X c I-1; X for(w=6;w<16;) X a(1),c w++; X m[1]= *m; X for(*m+=512;;r(m[I++])); X} SHAR_EOF $TOUCH -am 0817110092 1992/buzzard.2.orig.c && chmod 0444 1992/buzzard.2.orig.c || echo "restore of 1992/buzzard.2.orig.c failed" set `wc -c 1992/buzzard.2.orig.c`;Wc_c=$1 if test "$Wc_c" != "794"; then echo original size 794, current size $Wc_c fi # ============= 1992/demo1.1st ============== echo "x - extracting 1992/demo1.1st (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo1.1st && X: immediate _read @ ! - * / <0 exit echo key _pick X X: show echo echo echo echo exit X: all show show show show echo exit X X: doit immediate X 10 33 100 108 114 111 87 X 32 111 108 108 101 72 X all Xexit X Xdoit SHAR_EOF $TOUCH -am 0817110092 1992/demo1.1st && chmod 0444 1992/demo1.1st || echo "restore of 1992/demo1.1st failed" set `wc -c 1992/demo1.1st`;Wc_c=$1 if test "$Wc_c" != "212"; then echo original size 212, current size $Wc_c fi # ============= 1992/demo1.th ============== echo "x - extracting 1992/demo1.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo1.th && X: demo1 " Hello world! X" ; X Xdemo1 SHAR_EOF $TOUCH -am 0817110092 1992/demo1.th && chmod 0444 1992/demo1.th || echo "restore of 1992/demo1.th failed" set `wc -c 1992/demo1.th`;Wc_c=$1 if test "$Wc_c" != "34"; then echo original size 34, current size $Wc_c fi # ============= 1992/demo2.th ============== echo "x - extracting 1992/demo2.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo2.th && X: demo2 X X 10 0 ( iterate from 0 stopping before 10 ) X do X i . ( print the loop counter ) X loop X cr ( add a newline ) X; X Xdemo2 SHAR_EOF $TOUCH -am 0817110092 1992/demo2.th && chmod 0444 1992/demo2.th || echo "restore of 1992/demo2.th failed" set `wc -c 1992/demo2.th`;Wc_c=$1 if test "$Wc_c" != "135"; then echo original size 135, current size $Wc_c fi # ============= 1992/demo3.th ============== echo "x - extracting 1992/demo3.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo3.th && X: printfour X X dup ( save the number on top of the stack ) X 4 = ( compare it to four ) X if X " forth " ( output a string for it ) X drop ( and delete the saved value ) X else X . X endif X; X X: demo3 10 0 do i printfour loop cr ; X Xdemo3 SHAR_EOF $TOUCH -am 0817110092 1992/demo3.th && chmod 0444 1992/demo3.th || echo "restore of 1992/demo3.th failed" set `wc -c 1992/demo3.th`;Wc_c=$1 if test "$Wc_c" != "245"; then echo original size 245, current size $Wc_c fi # ============= 1992/demo4.th ============== echo "x - extracting 1992/demo4.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo4.th && X( compute factorial recursively ) X( take x as input, return x! and x as output ) X X: fact-help X X dup if X 1 - ( leave x-1 on top ) X fact-help ( leave x-1, [x-1]! ) X 1 + ( leave x, [x-1]!, x ) X swap over swap ( leave [x-1]!, x, x ) X * ( into x!, x ) X swap ( into x, x! ) X else X 1 swap X then X; X X: fact X X fact-help X drop X X; X X: demo4 X " 4 factorial is: " 4 fact . cr X " 6 factorial is: " 6 fact . cr X; X Xdemo4 SHAR_EOF $TOUCH -am 0817110092 1992/demo4.th && chmod 0444 1992/demo4.th || echo "restore of 1992/demo4.th failed" set `wc -c 1992/demo4.th`;Wc_c=$1 if test "$Wc_c" != "439"; then echo original size 439, current size $Wc_c fi # ============= 1992/demo5.th ============== echo "x - extracting 1992/demo5.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo5.th && X( recursive factorial. given x on top, followed by ) X( an "accumulator" containing the product except for x! ) X X: fact-help2 X X dup if X swap over swap X * X swap 1 - X fact-help2 X then X; X X: fact X X 1 swap X fact-help2 X drop X; X X: demo5 X X " The factorial of 3 is: " 3 fact . cr X " The factorial of 5 is: " 5 fact . cr X; X Xdemo5 SHAR_EOF $TOUCH -am 0817110092 1992/demo5.th && chmod 0444 1992/demo5.th || echo "restore of 1992/demo5.th failed" set `wc -c 1992/demo5.th`;Wc_c=$1 if test "$Wc_c" != "339"; then echo original size 339, current size $Wc_c fi # ============= 1992/demo6.th ============== echo "x - extracting 1992/demo6.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/demo6.th && X: foobar X 2 X [ 2 , ( '[' turns the compiler off, allowing us to execute code ) X 1 1 1 + + , ( and we compile in-line a 2 and a three ) X ( the '2' means 'push the number following this' ) X ] X + . cr X; X Xfoobar X X: 'foobar ' foobar ; ( ' can only be run inside the compiler ) X ( ' leaves the address of the following word X on the stack ) X X'foobar . cr X X'foobar dump SHAR_EOF $TOUCH -am 0817110092 1992/demo6.th && chmod 0444 1992/demo6.th || echo "restore of 1992/demo6.th failed" set `wc -c 1992/demo6.th`;Wc_c=$1 if test "$Wc_c" != "388"; then echo original size 388, current size $Wc_c fi # ============= 1992/gson.c ============== echo "x - extracting 1992/gson.c (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/gson.c && 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();} SHAR_EOF $TOUCH -am 0817110092 1992/gson.c && chmod 0444 1992/gson.c || echo "restore of 1992/gson.c failed" set `wc -c 1992/gson.c`;Wc_c=$1 if test "$Wc_c" != "1513"; then echo original size 1513, current size $Wc_c fi # ============= 1992/gson.hint ============== echo "x - extracting 1992/gson.hint (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/gson.hint && XMost Humorous Output: <gson@niksula.hut.fi> Andreas Gustafsson X X Andreas Gustafsson X Helsinki University of Technology X Arentikuja 1 D 305 (home address) X 00410 Helsinki X FINLAND X X XJudges' comments: X X To make: X make ag X X Determine where your system dictionary is located. You may find X it located in one of the following places: X X /usr/dict/words X /usr/share/lib/spell/words X /usr/ucblib/dict/words X /dev/null <-- for machines with nothing to say X X Then using the proper dictionary: X X ag free software foundation < /usr/dict/words X ag obfuscated c contest < /usr/dict/words X ag unix international < /usr/dict/words X ag george bush < /usr/dict/words X ag bill clinton < /usr/dict/words X ag ross perot < /usr/dict/words X ag paul e tsongas < /usr/dict/words X X Recently some newspapers printed amusing anagrams of one of the X names listed above. Run this program to find the anagrams they X weren't allowed to print! X X XSelected notes from the author: X X The name of the game: X X AG is short for either Anagram Generator or simply AnaGram. X It might also be construed to mean Alphabet Game, and by pure X coincidence it happens to be the author's initials. X X X What it does: X X AG takes one or more words as arguments, and tries to find X anagrams of those words, i.e. words or sentences containing X exactly the same letters. X X X How to use it: X X To run AG, you need a dictionary file consisting of distinct words X in the natural language of your choice, one word on each line. If X your machine doesn't have one already, you can make your own X dictionary by concatenating a few hundred of your favourite Usenet X articles and piping them through the following obfuscated shell X script: X X #!/bin/sh X z=a-z];tr [A-Z\] \[$z|sed s/[\^$z[\^$z*/_/g|tr _ \\012|grep ..|sort -u X X Using articles from alt.folklore.computers is likely to make X a more professional-looking dictionary than rec.arts.erotica. X X AG must be run with the dictionary file as standard input. X X Because anagrams consisting of just a few words are generally more X meaningful than those consisting of dozens of very short words, the X number of words in the anagrams is limited to 3 by default. This X limit can be changed using a numeric command line option, as in X "ag -4 international obfuscated c code contest </usr/dict/words". X X Bugs: X X - There is no error checking X - Standard input must be seekable, so you can't pipe the dictionary X into AG. X - The input sentence and each line in the dictionary may contain X at most 32 distinct letters, and each letter may occur at most 15 X times. X - Words in the dictionary may be at most 255 bytes long X - AG cannot handle characters that sign-extend to negative values X - Although AG works on both 16-bit and 32-bit machines, X the size of the problems it can solve is severely limited X on machines that limit the stack size to 64k or less. X X X Obfuscatory notes: X X As you can see, AG takes advantage of the new '92 whitespace rules to X achieve a clear, readable, self-documenting layout. The identifiers X have been chosen in a way appropriate for an alphabet game, and common X sources of bugs such as goto statements and malloc/free have been X eliminated. As AG also refrains from abusing the preprocessor, it X doesn't really have much to offer in terms of "surface obfuscation". X Instead, it tries to achieve both its speed and its obscurity through a X careful choice of algorithms. Some of the finer points of those X algorithms are outlined in the rot-13 encoded spoiler below. X X How it works: (ROT13 to read) X X Urer sbyybjf n qrfpevcgvba bs fbzr bs gur qngn fgehpgherf naq X nytbevguzf hfrq ol NT. Vg vf ol ab zrnaf pbzcyrgr, ohg vg znl uryc X lbh trg na vqrn nobhg gur trareny cevapvcyrf. X X -- X X Vagreanyyl, NT ercerfragf jbeqf naq fragraprf nf neenlf bs 32 X 4-ovg vagrtre ryrzragf. Rnpu ryrzrag ercerfragf gur ahzore bs X gvzrf n yrggre bpphef va gur jbeq/fragrapr. Gurer ner 32 ryrzragf X orpnhfr 32 vf n pbairavrag cbjre bs gjb ynetre guna gur ahzore bs X yrggref va zbfg jrfgrea nycunorgf, naq gur ryrzragf ner 4 ovgf X rnpu orpnhfr gur fnzr yrggre vf hayvxryl gb bpphe zber guna 15 X gvzrf va n cenpgvpny nantenz trarengvba ceboyrz. X X Gurfr 32*4-ovg neenlf ner npghnyyl fgberq va zrzbel va n X "ovg-genafcbfrq" sbezng, nf neenlf bs sbhe "ybat" inyhrf. Vg vf X nffhzrq gung n "ybat" vf ng yrnfg 32 ovgf. Gur svefg 4-ovg yrggre X pbhag vf sbezrq ol gur yrnfg fvtavsvpnag (2^0) ovg va rnpu bs gur X sbhe ybatf, gur arkg bar vf sbezrq ol gur 2^1 ovgf, rgp. X X Guvf fgbentr sbezng znxrf vg cbffvoyr gb nqq be fhogenpg gjb fhpu X irpgbef bs 32 4-ovg inyhrf va cnenyyry ol fvzhyngvat n frg bs 32 X ovanel shyy nqqref va fbsgjner hfvat ovgjvfr ybtvpny bcrengvbaf. X R.t., nyy gur YFO:f bs gur erfhyg ner sbezrq va cnenyyry ol gnxvat X gur rkpyhfvir BE bs gur YFO:f va rnpu fhzznaq, naq 32 pneel ovgf X ner sbezrq va cnenyyry va n fvzvyne jnl hfvat n ybtvpny NAQ. X Guhf, 32 vaqrcraqrag 4-ovg nqqvgvbaf pna or cresbezrq ol whfg sbhe X vgrengvbaf bs n ybbc pbagnvavat fbzr 32-ovg ovgjvfr ybtvpny X bcrengvbaf, ohg ab nevguzrgvp bcrengvbaf bgure guna gubfr vzcyvrq X ol neenl vaqrkvat. X X Fhogenpgvba jbexf fvzvyneyl, naq va snpg NT bayl vzcyrzragf X fhogenpgvba qverpgyl, unaqyvat nqqvgvba ol zrnaf bs gur vqragvgl X n+o = n-(0-o). X X Va nqqvgvba gb guvf 32*4-ovg ercerfragngvba, NT nyfb sbezf n fb-pnyyrq X "fvtangher" gung vf gur ovgjvfr BE bs gur sbhe ybatf, juvpu vf X rdhvinyrag gb fnlvat gung gur fvtangher bs n jbeq pbagnvaf n ybtvpny 1 X va gur ovg cbfvgvbaf pbeerfcbaqvat gb yrggref bppheevat ng yrnfg bapr X va gung jbeq. X X Gur svefg guvat NT qbrf vf gb pbafgehpg n ybbxhc gnoyr bs 256 X ybatf, bar sbe rnpu 8-ovg punenpgre inyhr. Gur ragel sbe n X punenpgre jvyy or mreb vs gung punenpgre qbrfa'g nccrne va gur X fragrapr tvira ba gur pbzznaq yvar, be vg jvyy unir n fvatyr ovg X frg vs gur punenpgre qbrf nccrne va gur fragrapr. Ol nqqvat X gbtrgure gur ovg znfxf sbe nyy gur yrggref va gur vachg fragrapr X hfvat gur genafcbfr nqqvgvba zrgubq qrfpevorq nobir, NT sbezf gur X 32*4 ovg neenl ercerfragngvba bs gur vachg fragrapr. X X Gur arkg npgvba cresbezrq vf ernqvat gur qvpgvbanel. Gubfr jbeqf gung X pbagnva yrggref abg va gur vachg fragrapr ner vzzrqvngryl qvfpneqrq. X Jbeqf pbagnvavat gur evtug yrggref ohg va rkprffvir ahzoref ner X ryvzvangrq va n frcnengr purpx vaibyivat gur 32*4 ovg neenl. X X Gur erznvavat jbeqf, juvpu jvyy or ersreerq gb nf "pnaqvqngr jbeqf", X ner fgberq va 32*4-ovg ercerfragngvba, gbtrgure jvgu gurve fvtangherf X naq bssfrgf vagb gur qvpgvbanel svyr fb gung gur cynva-grkg irefvba bs X n jbeq pna yngre or sbhaq sbe cevagvat. Guvf vasbezngvba vf xrcg va n X ybpny "fgehpg" va gur qvpgvbanel-ernqvat shapgvba, naq zrzbel vf X nyybpngrq sbe rnpu pnaqvqngr jbeq fvzcyl ol znxvat nabgure erphefvir X pnyy gb gung shapgvba. X X Rnpu fgehpg fb nyybpngrq vf yvaxrq vagb n svkrq-fvmr unfu gnoyr bs X 4096 ragevrf vaqrkrq ol gur 12 ybj ovgf bs gur jbeq'f fvtangher. X Jura gur qvpgvbanel-ernqvat shapgvba rapbhagref raq-bs-svyr, nyy gur X pnaqvqngr jbeqf unir orra fgberq va arfgrq npgvingvba erpbeqf ba gur X fgnpx, npprffvoyr guebhtu gur unfu gnoyr. X X Trarengvat gur nantenzf vf gura qbar ol genirefvat gur unfu gnoyr naq X fhogenpgvat gur yrggref bs rnpu jbeq va gur unfu gnoyr sebz gur X "pheerag fragrapr", juvpu vavgvnyyl vf gur fragrapr tvira ba gur X pbzznaq yvar. X X Gur fhogenpgvba vf cresbezrq va cnenyyry ba gur 4-ovg yrggre pbhagf X nf qrfpevorq nobir, naq vs nyy 32 erfhygf ner mreb, na nantenz unf X orra sbhaq. Vs gur erfhyg vf artngvir sbe bar be zber bs gur yrggref X (nf vaqvpngrq ol bar be zber "1" va n irpgbe bs 32 obeebj ovgf X erghearq ol gur fhogenpgvba ebhgvar), gur jbeq qvq abg zngpu gur X pheerag fragrapr naq vf vtaberq. Svanyyl, vs gur erfhyg pbagnvarq X bayl abaartngvir yrggre pbhagf, jr unir sbhaq n cnegvny nantenz: X n jbeq pbagnvavat fbzr, ohg abg nyy, bs gur yrggref va gur pheerag X fragrapr. Va guvf pnfr jr erphefviryl gel gb svaq na nantenz bs gur X erznvavat yrggref. Gur qrcgu bs gur erphefvba vf yvzvgrq gb gur X znkvzhz ahzore bs jbeqf va gur nantenz, nf fcrpvsvrq ol gur hfre. X X Jura gur qrrcrfg erphefvba yriry unf orra ernpurq, na bcgvzvmngvba pna X or nccyvrq: orpnhfr ab shegure erphefvba jvyy or qbar, gurer vf ab X arrq gb ybbx sbe cnegvny nantenzf, naq gurersber NT bayl arrqf gb X purpx sbe jbeqf gung pbagnva rknpgyl gur fnzr yrggref nf gur pheerag X fragrapr. Gubfr jbeqf pna or sbhaq fvzcyl ol vaqrkvat gur unfu gnoyr X jvgu gur fvtangher bs gur pheerag fragrapr. X X Rira jura abg ba gur qrrcrfg erphefvba yriry, NT trarenyyl nibvqf X rknzvavat nyy gur ragevrf bs gur unfu gnoyr. Gur vqrn vf gung jr ner X abg vagrerfgrq va unfu ohpxrgf jubfr jbeqf pbagnva nal yrggref abg X va gur pheerag fragrapr; gurfr ohpxrgf ner rknpgyl gubfr jubfr vaqrk X unf n ybtvpny bar va n ovg cbfvgvba jurer gur fvtangher bs gur pheerag X fragrapr unf n mreb. Chg nabgure jnl, jr jnag gb ybbc guebhtu bayl X gubfr unfu ohpxrg vaqvprf "v" gung pbagnva mrebrf va nyy gur ovg X cbfvgvbaf jurer gur fvtangher "f" bs gur pheerag fragrapr pbagnvaf X n mreb; guvf pna or rkcerffrq va P nf (v & ~f == 0). X X Vg vf cbffvoyr gb ybbc guebhtu nyy fhpu ahzoref va na rssvpvrag jnl ol X gnxvat nqinagntr bs pregnva cebcregvrf bs ovanel nevguzrgvp: ol X sbepvat gur ovgf pbeerfcbaqvat gb mrebrf va "f" gb barf, jr pna znxr X gur pneevrf trarengrq va vaperzragvat "v" cebcntngr fgenvtug npebff X gubfr ovgf gung fubhyq erznva mreb. Sbe rknzcyr, gur sbyybjvat X cebtenz cevagf nyy gubfr 16-ovg vagrtref gung pbagnva mrebrf va nyy X rira ovg cbfvgvbaf: X X znva(){vag v=0,f=0kNNNN;qb{cevags("%04k\g",v);}juvyr(v=((v|~f)+1)&f);} X X NT hfrf n fvzvyne zrgubq ohg jbexf va gur bccbfvgr qverpgvba, svaqvat X gur arkg ybjre inyhr jvgu mrebrf va tvira ovg cbfvgvbaf ol cebcntngvat X obeebjf npebff gubfr ovgf. Fbzr nqqvgvbany nqwhfgzragf ner znqr X gb gur unfu gnoyr vaqrk jura vavgvngvat n erphefvir frnepu, hfvat X fvzvyne ovg-gjvqqyvat grpuavdhrf. X X Jurarire na nantenz unf orra sbhaq, vg vf cevagrq ol genirefvat n X yvaxrq yvfg sbezrq ol fgehpgf va gur npgvingvba erpbeqf bs gur X erphefvir vaibpngvbaf bs gur frnepu shapgvba, frrxvat gb gur ortvaavat X bs gur jbeq zngpurq ol gung vaibpngvba, naq pbclvat gur punenpgref bs X gur jbeq qverpgyl sebz fgnaqneq vachg gb fgnaqneq bhgchg. SHAR_EOF $TOUCH -am 0908160292 1992/gson.hint && chmod 0444 1992/gson.hint || echo "restore of 1992/gson.hint failed" set `wc -c 1992/gson.hint`;Wc_c=$1 if test "$Wc_c" != "10891"; then echo original size 10891, current size $Wc_c fi # ============= 1992/help.th ============== echo "x - extracting 1992/help.th (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/help.th && X: help key ( flush the carriage return form the input buffer ) X X" The following are the standard known words; words marked with (*) are Ximmediate words, which cannot be used from command mode, but only in Xword definitions. Words marked by (**) declare new words, so are always Xfollowed by the new word. X X ! @ fetch, store X + - * / mod standard arithmetic operations X = < > <= >= standard comparison operations X X not boolean not of top of stack X logical turn top of stack into 0 or 1 X X dup over duplicate the top of stack or second of stack X swap drop reverse top two elements or drop topmost X X inc dec increment/decrement the value at address from stack X add add a value from 2nd of stack into address from top X X echo key output character from, or input to, top of stack X . # print out number on top of stack without/with cr X cr print a carriage return X X[more]" key X" (**) var declare variable with initial value taken from stack X(**) constant declare constant with initial value taken from stack X(**) array declare an array with size taken from stack X X(*) if...else...then FORTH branching construct X(*) do...loop FORTH looping construct X i j loop values (not variables) X X print print the string pointed to on screen X X(*)(**) : declare a new THIRD word X(*) <build does> declare a data types compile-time and run-time X(*) ; terminate a word definition X X[more]" key X" Advanced words: X here current location in dictionary X h pointer into dictionary X r pointer to return stack X fromr tor pop a value from or to the return stack X X , write the top of stack to dictionary X ' store the address of the following word on the stack X allot leave space on the dictionary X X :: compile a ':' header X [ switch into command mode X ] continue doing : definitions X" ; SHAR_EOF $TOUCH -am 0817110092 1992/help.th && chmod 0444 1992/help.th || echo "restore of 1992/help.th failed" set `wc -c 1992/help.th`;Wc_c=$1 if test "$Wc_c" != "1774"; then echo original size 1774, current size $Wc_c fi # ============= 1992/imc.c ============== echo "x - extracting 1992/imc.c (Text)" sed 's/^X//' << 'SHAR_EOF' > 1992/imc.c && X#include <stdio.h> X#include <malloc.h> X#define ext(a) (exit(a),0) X#define I " .:\';+<?F7RQ&%#*" X#define a "%s?\n" X#define n "0?\n" X#define C double X#define o char X#define l long X#define L sscanf X#define i stderr X#define e stdout X#define r ext (1) X#define s(O,B) L(++J,O,&B)!=1&&c>++q&&L(v[q],O,&B)!=1&&--q X#define F(U,S,C,A) t=0,*++J&&(t=L(J,U,&C,&A)),(!t&&c>++q&&!(t=L(v[q],U,\ X &C,&A)))?--q:(t<2&&c>++q&&!(t=L(v[q],S,&A))&&--q X#define T(E) (s("%d",E),E||(fputs(n,i),r)) X#define d(C,c) (F("%lg,%lg","%lg",C,c))) X#define O (F("%d,%d","%d",N,U),(N&&U)||(fputs(n,i),r))) X#define D (s("%lg",f)) X#define E putc X C X G=0, X R X =0,Q,H X ,M,P,z,S X =0,x=0 X , f=0;l b,j=0, k X =128,K=1,V,B=0,Y,m=128,p=0,N X =768,U=768,h[]={0x59A66A95,256 X ,192,1,6912,1,0,0},t,A=0,W=0,Z=63,X=23 X ;o*J,_;main(c,v)l c;o**v;{l q=1;for(;;q< X c ?(((J=v[q])[0]&&J[0]<48&&J++,((_= *J)<99|| X _/2== '2'||(_-1)/3=='\"'||_==107||_/05*2==','||_ X >0x074)?( fprintf(i,a,v[q]),r):_>0152?(_/4>27?(_&1?( X O,Z=N,X=U): (W++,N=Z,U=X)):_&1?T(K):T(k)):_>103?(d(G, X R ),j=1):_&1? d(S,x):D,q++),q--,main(c-q,v+q)):A==0?(A= X 1,f||(f=N/4.),b=(((N-1)&017)<8),q=(((N+7)>>3)+b)*U,(J=malloc(q) X )||(perror("malloc"),r),S-=(N/2)/f,x+=(U/2)/f):A==1?(B<U?(A=2,V X = 0,Q=x-B/f,j ||(R=Q),W&&E('\n',e),E(46,i)):(W&&E('\n', X e),E('\n',i ),h[1]=N,h[2]=U,h[4]=q,W||(fwrite(h,1,32, X e),fwrite (J,1,q,e)),free(J),ext(0))):A==2?(V<N?(j? X (H=V/f +S,M=Q):(G=V/f+S,H=M=0),Y=0,A=03):((m&0x80 X ) ||(m=0x80,p++),b&&(J[p++]=0),A=1,B++)):((Y X <k&&(P=H*H)+(z=M*M)<4.)?(M=2*H*M+R,H=P-z X +G,Y++):(W&&E(I[0x0f*(Y&K)/K],e),Y&K?J X [p]&=~m:(J[p]|=m),(m>>=1)||/*/ X (m=128,u--),A==6?ext(1):B<u X . e=3,l=2*c*/( m X =0x80, X p++),V++ X ,A=0x2 X ) X )); X } SHAR_EOF $TOUCH -am 0817110392 1992/imc.c && chmod 0444 1992/imc.c || echo "restore of 1992/imc.c failed" set `wc -c 1992/imc.c`;Wc_c=$1 if test "$Wc_c" != "1965"; then echo original size 1965, current size $Wc_c fi echo "End of part 3, continue with part 4" exit 0 -- For a good prime, call: 391581 * 2^216193 - 1