home *** CD-ROM | disk | FTP | other *** search
/ ftp.cse.unsw.edu.au / 2014.06.ftp.cse.unsw.edu.au.tar / ftp.cse.unsw.edu.au / pub / doc / languages / C / ioccc / 1990 / jaw.hint < prev    next >
Encoding:
Text File  |  1992-10-18  |  7.2 KB  |  215 lines
  1. Best Entropy-reducer: <see below> Woods, Fox & Eggert
  2.  
  3.     James A. Woods                     jaw@riacs.edu
  4.     Research Institute for Advanced Computer Science
  5.     MS 230-5
  6.     NASA Ames Research Center
  7.     Moffett Field, CA 94131
  8.     USA
  9.  
  10.     Karl F. Fox                     karl@MorningStar.com
  11.     Morning Star Technologies, Inc.
  12.     1760 Zollinger Road
  13.     Columbus, OH 43221
  14.     USA
  15.  
  16.     Paul Eggert                     eggert@twinsun.com
  17.     Twin Sun Inc.
  18.     360 N. Sepulveda Blvd. #2055
  19.     El Segundo, CA 90245
  20.     USA
  21.  
  22.  
  23. Judges' comments:
  24.  
  25.     The program, in its base form, implements two useful utilities:
  26.  
  27.     atob - ascii to binary conversion
  28.     zcat - decompression filter
  29.  
  30.     To test the official C entry, one might try:
  31.  
  32.     echo "Quartz glyph jocks vend, fix, BMW." | compress | btoa | jaw
  33.  
  34.     which should apply the identity transformation to a minimal
  35.     holoalphabetic sentence.
  36.  
  37.     Included with this entry is a shell script (with comments edited down
  38.     to reduce it to 1530 bytes) which implements the complete
  39.     shark utility.  The script, shark.sh, contains a 'jaw.c' embedded
  40.     within it!
  41.  
  42.     The sender must have 'compress' and 'btoa'.  To send, try:
  43.  
  44.     sh shark.sh jaw.* > receive
  45.  
  46.     The resulting file, 'receive', unpacks the input files
  47.     even if the receiver lacks 'uncompress' and 'atob':
  48.  
  49.     mkdir test
  50.     cd test
  51.     sh ../receive
  52.     cmp ../jaw.c jaw.c
  53.     cmp ../jaw.hint jaw.hint
  54.  
  55. Selected notes from the authors:
  56.  
  57.                  ABSTRACT
  58.  
  59.            Minimal, Universal File Bundling
  60.      (or, Functional Obfuscation in a Self-Decoding Unix Shell Archive)
  61.  
  62.                James A. Woods
  63.            Universities Space Research Association
  64.               NASA Ames Research Center
  65.  
  66.  
  67.            "Use an algorithm, go to jail."
  68.                 [anon., circa 1988, pre-Morris worm era]
  69.  
  70.  
  71.       Myriad formats have been proposed for  network-mailable
  72.      data.  A major difficulty undermining the popularity of most
  73.      file/message bundlers  is  that  the  sender  assumes  prior
  74.      installation  of  the  computational  dual  of such bundling
  75.      software by the receiver.  Command shell archives  alleviate
  76.      this problem somewhat, but still require standardization for
  77.      the  function  of  data  compression  and  mail-transparency
  78.      encoding.  On Unix, these coding format quandaries are over-
  79.      come by planting a novel Trojan Horse in the archive  header
  80.      to perform negotiationless decoding.
  81.  
  82.       Specifically, we outline the development of an extraor-
  83.      dinarily   compact  portable  (un)bundler  to  (dis)assemble
  84.      data-compressed,  binary-to-ASCII-converted,   length-split,
  85.      and  checksummed  directory  structures  using standard Unix
  86.      tools.  Miniature versions of counterparts to  a  Lempel-Ziv
  87.      coder ('compress' or 'squeeze') and an efficient bit packet-
  88.      izer ('btoa') are compiled on-the-fly  at  mail  destination
  89.      sites  where  they may not already exist.  These are written
  90.      in purposefully obfuscated-C to  accompany  similarly-shrunk
  91.      shell command glue.  This resulting shell archiver is dubbed
  92.      'shark'.
  93.  
  94.        'Shark' procedure overhead consumes as  few  as  three
  95.      dozen  shell  lines  (or ~1100 bytes), commensurate with the
  96.      size of many Internet mail headers; it  amortizes  favorably
  97.      with  message  size.   'Shark' is portable across Unix vari-
  98.      ants, while the underlying technique is inherently  general-
  99.      izable to other encoding schemes.
  100.  
  101.       In   the   function-theoretic    sense    of    minimal
  102.      Chaitin/Kolmogorov complexity, and within a modified Shannon
  103.      model of communication, the 'shark' effort aims to construct
  104.      a  "shortest  program"  for  source  decoding in the Turing-
  105.      universal Unix environment.
  106.  
  107.      ----------------------------------------------
  108.  
  109.        Oh, the shark has pretty teeth, dear--
  110.        And he shows them pearly white
  111.        Just a jackknife has Macheath, dear--
  112.        And he keeps it out of sight.
  113.  
  114.             [Bertolt Brecht, Threepenny Opera]
  115.  
  116.      ----------------------------------------------
  117.  
  118.     We have ported this program to a wide variety of systems.  Among
  119.     these are:
  120.  
  121.     SunOS 4.1 / Sun Sparcstation 1 (using both 'cc' and 'gcc 1.37.1')
  122.     SunOS 4.0.3 / Sun 3
  123.     BSD 4.3 / VAX 8650
  124.     SEIUX / Sumitomo Electric Ustation/S
  125.     Sony NEWS-OS 3.3 / Sony NEWS (fairly vanilla 4.3BSD)
  126.     System V.? / Hitachi 2050
  127.     System V.? / NEC EWS 4800
  128.     UNIOS-B / Omron Luna
  129.     Dynix / Sequent Balance ('cc' for Natl. Semi. base + 'gcc 1.36')
  130.     Unicos / Cray 2
  131.  
  132.      We (the authors) feel this program is obfuscated for the
  133.      following reasons:
  134.  
  135.      (0) This is one of the few programs you'll see WHOSE VERY UTILITY
  136.      DEPENDS ON ITS OBFUSCATION!
  137.  
  138.      (1) The contest entry may be used to send its wonderful self to
  139.      anyone in the Unix world!  Virus writers need not apply...
  140.  
  141.      (2) The basic idea is twisted enough to be patentable, but is,
  142.      out of the kindness of our hearts (as well as to maintain
  143.      eligibility for the large IOCCC prize fund), dedicated to
  144.      the public domain.  Claude Shannon, meet Alan Turing.
  145.  
  146.      (3) Meta-obfuscation is via obfuscated description (see ABSTRACT).
  147.  
  148.      (4) "Literary" allusion.  Production code contains a reference to
  149.      self-reference, preserved at amazing cost for sheer perversity.
  150.  
  151.      (5) Many, many micro obfuscations below, honed over three years
  152.      time, in shell as well as C.  Ask about the 'tar' pit escape,
  153.      the argv[0] flip, Paul's &4294967295 portability hack, the
  154.      "void where prohibited by flaw" fix, the scanf() spacesaver,
  155.      shift shenanigans, signal madness, exit()ing stage left, and
  156.      source-to-source transformations galore.
  157.  
  158.      For extra credit:
  159.  
  160.     Construct 'sharkmail', to auto-split sharkives into mailable
  161.     segments and mail them.  Here's a simple one, which could be
  162.     extended to enable auto-reassembly with one shell cmd at the
  163.     far end.
  164.  
  165.      ------------------------ cut here for sharkmail -----------------------
  166.      #!/bin/sh
  167.      m=$1; shift
  168.      shark $* | split -800 - /tmp/shark$$
  169.      n=`ls /tmp/shark$$* | wc -l | sed 's/  *//'`
  170.      p=0
  171.      for f in `ls /tmp/shark$$*`
  172.      do
  173.      p=`expr $p + 1`
  174.      mail -s "bundle ($p of $n) from '`whoami`'" $m < $f
  175.      done
  176.      rm /tmp/shark$$*
  177.      ------------------------ end of sharkmail -----------------------------
  178.  
  179.  
  180. Shark history:
  181.  
  182.        May 1987: Karl Fox introduces 1023-byte zcat.c to USENET.
  183.          It's too late for the 4th IOCCC.
  184.  
  185.        May 21, 1987: James A. Woods extends idea to construct self
  186.          decompressing shar Trojan horse, utilizing 'cc', 'shar',
  187.          'zcat', & 'atob'; size: 2303 bytes.
  188.  
  189.        May 23, 1987: 'jaw' trims 250 bytes without much thought.
  190.  
  191.        June 2, 1987: 52 lines of shell, 1991 bytes, now made with 'tar',
  192.          short-circuit C-compile at far end, dual-use main.c,
  193.          portability mods. (jaw)
  194.  
  195.        Mar-May 1988: abortive run at 5th IOCCC.
  196.          jaw.c - 1529 bytes.  compile line: 152 bytes.
  197.          generated funny code with execvp() to invoke shell.
  198.  
  199.        Aug 29, 1988: production version, now at 1830 bytes.
  200.  
  201.        Jan 1990: Paul Eggert does tour-de-force shark re-engineering.
  202.  
  203.        May 24, 1990: collaboration yields 999-byte jaw.c core (see above)
  204.          and 1530-byte production shell code (w/comments).
  205.          Eggert comes through with lion's share of improvements.
  206.          7th IOCCC code now faster than the atob/zcat it replaces.
  207.  
  208.        May 1990: 'jaw' develops experimental replacement using
  209.          Dan Bernstein's high-compression 'squeeze'.
  210.  
  211.  
  212. To which we add:
  213.  
  214.        June 1990: 'shark' wins the IOCCC, finally!  :-)
  215.