home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / c / u16pc.arc / U16.C < prev    next >
Encoding:
C/C++ Source or Header  |  1988-12-08  |  12.6 KB  |  503 lines
  1. /* This is an adaptation of the decompress part of the widespread net
  2.  * "compress" program. It is specifically designed for the IBM PC and
  3.  * clones and probably has to be compiled with the Microsoft C
  4.  * compiler (quick C won't do, it doesn't support the "huge" model).
  5.  *
  6.  * Parts written (other parts plagarized) by Tom Horsley
  7.  *   (tahorsley@ssd.harris.com)
  8.  *   Dec 1988.
  9.  */
  10. #include <stdio.h>
  11. #include <fcntl.h>
  12. #include <malloc.h>
  13.  
  14. /* Magic number stored in first two bytes.
  15.  */
  16. unsigned char magic_header[] = { "\037\235" }; /* 1F 9D */
  17.  
  18. /* Defines for third byte of header */
  19. #define BIT_MASK     0x1f    /* Max number of bits in codes */
  20. #define BLOCK_MASK   0x80    /* This bit set if should recognize CLEAR code */
  21.  
  22. /* Space to use for input file buffer.
  23.  */
  24. #define MAXBUF 4096
  25.  
  26. /* a codebuf struct is used to interface with the xcode() routine.
  27.  */
  28. struct codebuf {
  29.    void         (*codep)();
  30.    unsigned char * bufp;
  31. } cb;
  32.  
  33. /* a codesize struct is used for advancing from one size code to
  34.  * the next.
  35.  */
  36. struct codesize {
  37.    void         (*initp)(struct codebuf *);
  38.    int         n_bits;
  39.    long int     maxcode;
  40.    void         (*origp)();
  41. };
  42.  
  43. extern void init9(struct codebuf *);
  44. extern void init10(struct codebuf *);
  45. extern void init11(struct codebuf *);
  46. extern void init12(struct codebuf *);
  47. extern void init13(struct codebuf *);
  48. extern void init14(struct codebuf *);
  49. extern void init15(struct codebuf *);
  50. extern void init16(struct codebuf *);
  51. extern unsigned int xcode(struct codebuf *);
  52.  
  53. /* vartab tracks the variable size codes. For each size code the
  54.  * initialization routine, code size, largest code, and assembly state
  55.  * information is recorded.
  56.  *
  57.  * To advance to next sized code, read codes at current size while not
  58.  * at the original state, then call init routine for next size (and
  59.  * record initial state info).
  60.  */
  61. struct codesize vartab [] = {
  62.    { init9,  9,     0x1ffL,  0 },
  63.    { init10, 10, 0x3ffL,  0 },
  64.    { init11, 11, 0x7ffL,  0 },
  65.    { init12, 12, 0xfffL,  0 },
  66.    { init13, 13, 0x1fffL, 0 },
  67.    { init14, 14, 0x3fffL, 0 },
  68.    { init15, 15, 0x7fffL, 0 },
  69.    { init16, 16, 0x10000L, 0 }
  70. };
  71.  
  72. /* Record current entry in vartab.
  73.  */
  74. int curvartab = 0;
  75.  
  76. #ifdef DEBUG
  77. long bytes_out = 0;
  78. #endif
  79.  
  80.  
  81. /* buf is the input file buffer. Also used to store the initial help
  82.  * message you get with the -H option.
  83.  */
  84. unsigned char buf[MAXBUF] = "\
  85. u16 - 16 bit LZW uncompress for the IBM PC\n\
  86. u16 [-H] [files...]\n\
  87. \n\
  88. -H\tPrint this message and exit.\n\
  89. \n\
  90. Uncompresses each input file and writes result to stdout.  With no\n\
  91. input file specified, reads stdin.  Probably requires 270-280K of free\n\
  92. memory to run.\n\
  93. \n\
  94. Written for the IBM PC by tahorsley@ssd.harris.com (Tom Horsley).\n\
  95. \n\
  96. NOTE: this is kind of like zcat, but it does not try to stick any .Z's\n\
  97. on the ends of file names.\n"
  98. ;
  99.  
  100. /* Number of bytes of file data resident in buf.
  101.  */
  102. int          bufsize = 0;
  103.  
  104. /* Address of first byte in buffer past end of file
  105.  * (only set when the last buffer is read).
  106.  */
  107. char *          eofmark = NULL;
  108.  
  109. /* Address of byte near end of buffer (used to determine
  110.  * when to read additional data).
  111.  */
  112. char *          endbuf;
  113.  
  114.  
  115. /* Flag data read from file.
  116.  */
  117. int block_compress;
  118. int maxbits;
  119.  
  120. /* State variables controlling decompression
  121.  */
  122. #define FIRST  257   /* first free entry */
  123.  
  124. #define CLEAR  256   /* table clear output code */
  125.  
  126. int clear_flg = 0;
  127.  
  128. long free_ent = 0;
  129.  
  130. long maxcode;
  131.  
  132. #define FAR far
  133.  
  134. char FAR * de_stack;
  135.  
  136. /* tabprefix is the only real fly in the ointment, it needs to be a
  137.  * huge array, but could probably be changed to a couple of far arrays
  138.  * with the resulting additional complications in the tab_prefixof()
  139.  * macro.
  140.  */
  141. unsigned int huge * tabprefix;
  142.  
  143. unsigned char FAR * tabsuffix;
  144.  
  145. #define tab_prefixof(_i) tabprefix[_i]
  146.  
  147. #define tab_suffixof(_i) tabsuffix[_i]
  148.  
  149. long maxmaxcode = 65536L;
  150.  
  151. /* ReadBuf reads some data into the buffer following the data already
  152.  * in the buffer (if any). It tries to fill it up, and sets the end of
  153.  * file flag if it can't.
  154.  */
  155. void
  156. ReadBuf()
  157. {
  158.    int           cursize;
  159.    int           want;
  160.  
  161.    while ((eofmark == NULL) && ((want = MAXBUF - bufsize) > 0)) {
  162.       cursize = read(fileno(stdin), &buf[bufsize], want);
  163.       if (cursize < 0) {
  164.      perror("u16");
  165.      exit(1);
  166.       } else if (cursize == 0) {
  167.      eofmark = &buf[bufsize];
  168.       } else {
  169.      bufsize += cursize;
  170.       }
  171.    }
  172.    if (eofmark == NULL) {
  173.       endbuf = &buf[bufsize] - 32;
  174.    } else {
  175.       endbuf = eofmark;
  176.    }
  177. }
  178.  
  179. /* getcode deals with buffer filling, switching code size, and calling
  180.  * the assembler unpacking routines.
  181.  */
  182. long int
  183. getcode()
  184. {
  185.    int           leftover;
  186.  
  187.    if (cb.bufp >= endbuf) {
  188.       if (eofmark != NULL) {
  189.      return(-1L);
  190.       } else {
  191.      /* move the un-read data to the top of the buffer, then read
  192.       * some additional data.
  193.       */
  194.      leftover = &buf[bufsize] - cb.bufp;
  195.      memmove(&buf[0], cb.bufp, leftover);
  196.      cb.bufp = &buf[0];
  197.      bufsize = leftover;
  198.      ReadBuf();
  199.       }
  200.    }
  201.    if (clear_flg > 0 || free_ent > maxcode) {
  202.       /* If the next entry will be too big for the current code, or we
  203.        * have recieved a clear code then flush the current size code
  204.        * and advance to next size.
  205.        */
  206.       while (cb.codep != vartab[curvartab].origp) xcode(&cb);
  207.       if (cb.bufp >= endbuf) return(-1L);
  208.       if (clear_flg > 0) {
  209.      curvartab = 0;
  210.      clear_flg = 0;
  211.       } else {
  212.      ++curvartab;
  213.      if (curvartab > (16 - 9)) {
  214. #ifdef DEBUG
  215.         fputs("Attempt to overflow 16 bit codes.\n",stderr);
  216. #endif
  217.         curvartab = 16 - 9;
  218.      }
  219.       }
  220.       (*vartab[curvartab].initp)(&cb);
  221.       vartab[curvartab].origp = cb.codep;
  222.       maxcode = vartab[curvartab].maxcode;
  223. #ifdef DEBUG
  224.       fprintf(stderr,
  225.      "switching to %d bit codes, bytes_out = %ld, free_ent = %ld\n",
  226.      vartab[curvartab].n_bits,bytes_out, free_ent);
  227. #endif
  228.    }
  229.    return (long)(xcode(&cb));
  230. }
  231.  
  232. /* Decompress stdin to stdout.    This routine adapts to the codes in
  233.  * the file building the "string" table on-the-fly; requiring no table
  234.  * to be stored in the compressed file.
  235.  *
  236.  * This routine taken practically verbatim from the net compress
  237.  * program:
  238.  *
  239.  * $Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $
  240.  *
  241.  * compress.c - File compression ala IEEE Computer, June 1984.
  242.  *
  243.  * Authors:
  244.  *    Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
  245.  *    Jim McKie        (decvax!mcvax!jim)
  246.  *    Steve Davies    (decvax!vax135!petsd!peora!srd)
  247.  *    Ken Turkowski    (decvax!decwrl!turtlevax!ken)
  248.  *    James A. Woods    (decvax!ihnp4!ames!jaw)
  249.  *    Joe Orost        (decvax!vax135!petsd!joe)
  250.  */
  251. int
  252. decompress() {
  253.    register unsigned char FAR * stackp;
  254.    register int finchar;
  255.    register long code, oldcode, incode;
  256. #ifdef DEBUG
  257.    long stacksize = 0;
  258. #endif
  259.  
  260.    /* No buffering on stdin, we do all our own buffering.
  261.     */
  262.    setvbuf(stdin, NULL, _IONBF, 0);
  263.  
  264.    /* Operate in the binary file domain, don't want DOS screwing
  265.     * around with '\r''s.
  266.     */
  267.    setmode(fileno(stdin), O_BINARY);
  268.    setmode(fileno(stdout), O_BINARY);
  269.  
  270.    /* Read the iniital buffer worth of data and check magic numbers
  271.     * and flags.
  272.     */
  273.    ReadBuf();
  274.    if (bufsize < 3) {
  275.       fputs("u16: Missing file header.\n",stderr);
  276.       return 1;
  277.    }
  278.    if (memcmp(buf,magic_header,2) != 0) {
  279.       fputs("u16: Bad magic number.\n",stderr);
  280.       return 1;
  281.    }
  282.    block_compress = buf[2] & BLOCK_MASK;
  283.    maxbits = buf[2] & BIT_MASK;
  284.    if (maxbits > 16) {
  285.       fputs("u16: Cannot decompress, compressed with more than 16 bits.\n",
  286.      stderr);
  287.       return 1;
  288.    }
  289.  
  290.    /* Initialize the xcode routine to start reading 9 bit codes at the
  291.     * third byte of the initial buffer.
  292.     */
  293.    cb.bufp = &buf[3];
  294.    init9(&cb);
  295.    vartab[0].origp = cb.codep;
  296.    curvartab = 0;
  297.  
  298.    /*
  299.     * initialize the first 256 entries in the table.
  300.     */
  301.    maxcode = vartab[0].maxcode;
  302.    for ( code = 255; code >= 0; code-- ) {
  303.       tab_prefixof(code) = 0;
  304.       tab_suffixof(code) = (unsigned char)code;
  305.    }
  306.    free_ent = ((block_compress) ? FIRST : 256 );
  307.  
  308.    finchar = oldcode = getcode();
  309.    if(oldcode == -1)         /* EOF already? */
  310.       return;             /* Get out of here */
  311.    putchar((char)finchar );  /* first code must be 8 bits = char */
  312. #ifdef DEBUG
  313.    ++bytes_out;
  314. #endif
  315.    if(ferror(stdout)) {         /* Crash if can't write */
  316.       perror("u16");
  317.       exit(1);
  318.    }
  319.    stackp = de_stack;
  320.  
  321.    while ( (code = getcode()) > -1 ) {
  322.  
  323.       if ( (code == CLEAR) && block_compress ) {
  324. #ifdef DEBUG
  325.      fprintf(stderr,
  326.         "Input CLEAR code bytes_out = %ld, free_ent = %ld\n",
  327.         bytes_out, free_ent);
  328. #endif
  329.      for ( code = 255; code >= 0; code-- )
  330.         tab_prefixof(code) = 0;
  331.      clear_flg = 1;
  332.      free_ent = FIRST - 1;
  333.      if ( (code = getcode ()) == -1 )   /* O, untimely death! */
  334.         break;
  335.       }
  336.       incode = code;
  337.  
  338.       /* Special case for KwKwK string.
  339.        */
  340.       if ( code >= free_ent ) {
  341. #ifdef DEBUG
  342.      ++stacksize;
  343.      if (stacksize >= 65536L) {
  344.         fputs("stacksize overflow.\n",stderr);
  345.         exit(1);
  346.      }
  347. #endif
  348.      *stackp++ = finchar;
  349.      code = oldcode;
  350.       }
  351.  
  352.       /* Generate output characters in reverse order
  353.        */
  354.       while ( code >= 256 ) {
  355. #ifdef DEBUG
  356.      ++stacksize;
  357.      if (stacksize >= 65536L) {
  358.         fputs("stacksize overflow.\n",stderr);
  359.         exit(1);
  360.      }
  361.      if ((code < 0) || (code >= 65536L)) {
  362.         fprintf(stderr,"bad subscript, code = %ld\n",code);
  363.      }
  364. #endif
  365.      *stackp++ = tab_suffixof(code);
  366.      code = tab_prefixof(code);
  367.       }
  368. #ifdef DEBUG
  369.       ++stacksize;
  370.       if (stacksize >= 65536L) {
  371.      fputs("stacksize overflow.\n",stderr);
  372.      exit(1);
  373.       }
  374.       if ((code < 0) || (code >= 65536L)) {
  375.      fprintf(stderr,"bad subscript, code = %ld\n",code);
  376.       }
  377. #endif
  378.       *stackp++ = finchar = tab_suffixof(code);
  379. #ifdef DEBUG
  380.       if (stacksize > 65536L) {
  381.      fprintf(stderr,"stacksize reached %ld\n",stacksize);
  382.       }
  383. #endif
  384.  
  385.       /* And put them out in forward order
  386.        */
  387.       do {
  388.      putchar ( *--stackp );
  389. #ifdef DEBUG
  390.      ++bytes_out;
  391.      --stacksize;
  392. #endif
  393.       } while ( stackp > de_stack );
  394.  
  395. #ifdef DEBUG
  396.       if (stacksize != 0) {
  397.      fprintf(stderr,"stacksize = %ld, not empty!\n",stacksize);
  398.       }
  399. #endif
  400.  
  401.       /* Generate the new entry.
  402.        */
  403.       if ( (code=free_ent) < maxmaxcode ) {
  404. #ifdef DEBUG
  405.      if ((code < 0) || (code >= 65536L)) {
  406.         fprintf(stderr,"bad subscript, code = %ld\n",code);
  407.      }
  408. #endif
  409.      tab_prefixof(code) = (unsigned short)oldcode;
  410.      tab_suffixof(code) = finchar;
  411.      free_ent = code+1;
  412.       } 
  413.  
  414.       /* Remember previous code.
  415.        */
  416.       oldcode = incode;
  417.    }
  418.    fflush( stdout );
  419.    if(ferror(stdout)) {
  420.       perror("u16");
  421.       return 1;
  422.    }
  423.    return 0;
  424. }
  425.  
  426. /* 16 bit uncompress optimized for 8086 architecture.  The getcode
  427.  * routine is in 8086 assembler optimized for extracting the variable
  428.  * sized code rapidly.
  429.  */
  430. void
  431. main(argc, argv)
  432.    int           argc;
  433.    char *       argv[];
  434. {
  435.    int           errors = 0;
  436.  
  437.    /* Process options (only supports -H)
  438.     */
  439.    --argc;
  440.    ++argv;
  441.    while ((argc > 0) && (argv[0][0] == '-')) {
  442.       if (argv[0][1] == 'H') {
  443.      fputs(buf,stderr);
  444.      exit(0);
  445.       } else {
  446.      fputs("u16: unrecognized option ",stderr);
  447.      fputs(argv[0],stderr);
  448.      fputs("\n",stderr);
  449.      fputs("usage: u16 [-H] [files...]\n",stderr);
  450.      exit(1);
  451.       }
  452.       --argc;
  453.       ++argv;
  454.    }
  455.  
  456.    /* Allocate a large buffer for stdout (speeds up the program by a
  457.     * fair percentage).
  458.     */
  459.    setvbuf(stdout, NULL, _IOFBF, MAXBUF);
  460.  
  461.    /* Allocate space for tables
  462.     */
  463.    de_stack = (unsigned char FAR *)halloc(65536L, sizeof(unsigned char));
  464.    tabprefix = (unsigned int huge *)halloc(65536L, sizeof(unsigned int));
  465.    tabsuffix = (unsigned char FAR *)halloc(65536L, sizeof(unsigned char));
  466.    if ((de_stack == NULL) || (tabprefix == NULL) || (tabsuffix == NULL)) {
  467.       fputs("u16: out of memory.\n",stderr);
  468.       exit(1);
  469.    }
  470.  
  471.    if (argc == 0) {
  472.       /* Just decompress stdin
  473.        */
  474.       if (decompress()) {
  475.      ++errors;
  476.      fputs("u16: error decompressing stdin.\n",stderr);
  477.       }
  478.    } else {
  479.       while (argc > 0) {
  480.      if (freopen(argv[0], "r", stdin) == NULL) {
  481.         fputs("u16: cannot read ",stderr);
  482.         fputs(argv[0],stderr);
  483.         fputs("\n",stderr);
  484.         ++errors;
  485.      } else {
  486.         if (decompress()) {
  487.            fputs("u16: error in ",stderr);
  488.            fputs(argv[0],stderr);
  489.            fputs("\n",stderr);
  490.            ++errors;
  491.         }
  492.         fclose(stdin);
  493.      }
  494.      --argc;
  495.      ++argv;
  496.       }
  497.    }
  498. #ifdef DEBUG
  499.    fprintf(stderr,"Total bytes out = %ld\n",bytes_out);
  500. #endif
  501.    exit(errors);
  502. }
  503.