home *** CD-ROM | disk | FTP | other *** search
/ Hall of Fame / HallofFameCDROM.cdr / proglc / zoo141_c.lzh / LZC.C < prev    next >
C/C++ Source or Header  |  1987-02-07  |  8KB  |  303 lines
  1. #include "options.h"
  2. /*
  3. Lempel-Ziv compression.  Mostly based on Tom Pfau's assembly language
  4. code. 
  5.  
  6. The contents of this file are hereby released to the public domain.
  7.  
  8.                                     -- Rahul Dhesi  1986/12/31
  9. */
  10.  
  11. #include <stdio.h>            /* just to define NULL */
  12. #include "various.h"
  13. #include "zoofns.h"           /* function definitions */
  14. /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
  15. #include "zoomem.h"
  16. #include "debug.h"
  17. #include "assert.h"
  18. /* lzconst.h contains constants for lzd() and lzc() */
  19. #include "lzconst.h"
  20.  
  21. /* interval at which to check ratio */
  22. #define CHECKGAP 4000
  23. #define NEXT_USE  1
  24. #define FIRST_USE 2
  25. #define FOUND 0
  26.  
  27. struct   tabentry {
  28.    int first;
  29.    int next;
  30.    char z_ch;
  31. };
  32.  
  33. void init_ctab();
  34. void wr_ccode();
  35. int rd_cch();
  36. int lukup_ccode();
  37. void ad_ccode();
  38. void check_ratio();
  39. void flush_c();
  40. extern char *out_buf_adr;
  41. extern char *in_buf_adr;
  42. extern char memflag;                    /* memory allocated? */
  43. struct tabentry *table;                 /* this table also used by lzd.c */
  44. static unsigned int free_code;
  45. static int nbits;
  46. static unsigned int max_code;
  47. static unsigned int bitsout;
  48. static int bit_interval;
  49. static unsigned int bytesin, ratio, ratflag;
  50. static unsigned int in_offset, in_size;
  51. static unsigned int bit_offset;
  52. static int in_han, out_han;
  53.  
  54. int lzc(input_handle, output_handle)
  55. int input_handle, output_handle;
  56. {
  57.    int nextch, prefix_code, k;
  58.    int status;
  59.    int where;
  60.  
  61.    in_han = input_handle;
  62.    out_han = output_handle;
  63.  
  64.    bit_offset = in_offset = in_size = 0;
  65.  
  66.    if (memflag == 0) {
  67.      table = (struct tabentry *) emalloc((MAXMAX+10) * sizeof(struct tabentry));
  68.      memflag++;
  69.    }
  70.  
  71.  
  72.    init_ctab();
  73.    wr_ccode(CLEAR);
  74.    nextch = rd_cch();
  75.    if (nextch == EOF) {                  /* note real EOF, not Z_EOF */
  76.       wr_ccode (Z_EOF);
  77.       return (0);                         /* normal return from compress */
  78.    }
  79.  
  80.    /* compression loop begins here with nextch holding the next input char */
  81. loop1:
  82.    if (ratflag != 0)
  83.       check_ratio();
  84.    nextch &= 0xff;                       /* turn character to code */
  85.    assert(nextch < 256);
  86. loop2:
  87.    prefix_code = nextch;
  88.    nextch = rd_cch();
  89.    if (nextch == EOF) {                  /* note real EOF, not Z_EOF */
  90.       wr_ccode (prefix_code);
  91.       wr_ccode (Z_EOF);
  92.       if (bit_offset != 0)
  93.          flush_c ((int) (bit_offset / 8 + 1));
  94.       return (0);                         /* normal return from compress */
  95.    }
  96.    nextch &= 0xff;                        /* force to 8 bits */
  97.    assert(nextch < 256);
  98.  
  99.    k = nextch;
  100.    status = lukup_ccode (prefix_code, nextch, &where);
  101.    if (status == FOUND) {
  102.       nextch = where;                     /* where found */
  103.       goto loop2;
  104.    }
  105.    assert(status == FIRST_USE || status == NEXT_USE);
  106.  
  107.    /* reach here with status = FIRST_USE or NEXT_USE */
  108.    ad_ccode (status, nextch, where);
  109.  
  110.    wr_ccode (prefix_code);
  111.    nextch = k;
  112.  
  113.    if (free_code <= max_code)
  114.       goto loop1;
  115.    assert(nbits >= 9 && nbits <= MAXBITS);
  116.    if (nbits >= MAXBITS) {
  117.    /* To continue using table after it is full, remove next two lines */
  118.       wr_ccode (CLEAR);
  119.       init_ctab();
  120.  
  121.       goto loop1;
  122.    }
  123.  
  124.    nbits++;
  125.    assert(nbits >= 9 && nbits <= MAXBITS);
  126.    max_code = max_code << 1;
  127.    goto loop1;
  128. } /* end lzc() */
  129.  
  130. void wr_ccode (code)
  131. int code;
  132. {
  133.    unsigned int ofs_inbyte, hibits;
  134.    int byte_offset;
  135.  
  136. #ifdef DEBUG
  137. if (code == CLEAR)
  138.    printf(" CLEAR\n");
  139. #endif
  140.  
  141.    assert(nbits >= 9 && nbits <= MAXBITS);
  142.    bitsout += nbits;                /* total number of bits written */
  143.    bit_interval -= nbits;
  144.    if (bit_interval < 0)
  145.       ratflag = 1;                  /* time to check ratio */
  146.  
  147.    byte_offset = bit_offset / 8;
  148.    ofs_inbyte = bit_offset % 8;     /* offset within byte */
  149.    bit_offset += nbits;             /* allowing for new code */
  150.  
  151.    if (byte_offset >= OUTBUFSIZ - 4) {
  152.       flush_c (byte_offset);
  153.       bit_offset = ofs_inbyte + nbits;
  154.       out_buf_adr[0] = out_buf_adr [byte_offset];
  155.       byte_offset = 0;
  156.    }
  157.  
  158.    code = code & 0xffff;            /* force to 16 bits */
  159.  
  160.    if (ofs_inbyte == 0)
  161.       out_buf_adr[byte_offset]  = code & 0xff;
  162.    else
  163.       out_buf_adr[byte_offset] |= (code << ofs_inbyte) & 0xff;
  164.  
  165.    hibits = ((unsigned int) code) >> (8 - ofs_inbyte);
  166.    out_buf_adr[byte_offset+1] = hibits & 0xff;
  167.    out_buf_adr[byte_offset+2] = (((unsigned int) hibits) >> 8) & 0xff;
  168.  
  169.    assert(nbits >= 9 && nbits <= MAXBITS);
  170. } /* end wr_ccode() */
  171.  
  172. void init_ctab()
  173. {
  174.    int i;
  175.    bytesin = bitsout = ratio = ratflag = 0;
  176.    bit_interval = CHECKGAP;
  177.    nbits = 9;
  178.    max_code = 512;
  179. #ifdef COMMENT
  180.    for (i = 0; i < 256; i++) {
  181. #endif
  182.    for (i = 0; i < MAXMAX+1; i++) {
  183.       table[i].z_ch = table[i].first = table[i].next = -1;
  184.    }
  185. #ifdef COMMENT
  186.    /*DEBUG*/ table[MAXMAX].first   = table[MAXMAX].next = -1;
  187.    /*DEBUG*/ table[MAXMAX-1].first = table[MAXMAX-1].next = -1;
  188. #endif
  189.    free_code = FIRST_FREE;
  190. } /* end init_ctab() */
  191.  
  192. int rd_cch()
  193. {
  194.    int count;
  195.    bytesin++;
  196.    if (in_offset == in_size) {
  197.       count = read (in_han, in_buf_adr, INBUFSIZ);
  198.       if (count == -1)
  199.          prterror ('f', "Error reading input file during compression.\n");
  200.       addbfcrc (in_buf_adr, count);
  201.       if (count == 0) {
  202.          debug((printf("\nEOF on input\n")))
  203.          return (EOF);              /* real EOF, not Z_EOF */
  204.       }
  205.       in_size = count;
  206.       debug((printf("\ninput %d chars\n", count)))
  207.       in_offset = 0;
  208.    }
  209.    in_offset++;
  210.    return (in_buf_adr[in_offset-1] & 0xff);
  211. } /* end rd_cch () */
  212.  
  213. void check_ratio()
  214. {
  215. #ifdef COMMENT
  216.    int rat;
  217.    if (bitsout > 16383) {     /* avoid overflow */
  218.       bitsout /= 4;
  219.       bytesin /= 4;
  220.    }
  221.    rat = (2 * bitsout) / bytesin;
  222.    if (1.1 * rat < ratio) {
  223.       printf("#");
  224.       wr_ccode (CLEAR);
  225.       init_ctab();
  226.       bit_interval = CHECKGAP;
  227.       bitsout = 0;
  228.       bytesin = 0;
  229.       ratio = 0;
  230.    } else
  231.       ratio = ((ratio << 2) + ((2 * bitsout) / bytesin)) / 5;
  232. #else
  233.    bit_interval = CHECKGAP;
  234.    bitsout = 0;
  235.    bytesin = 0;
  236. #endif
  237. } /* end check_ratio() */
  238.  
  239. void ad_ccode (status, ch, index)
  240. int status, index, ch;
  241. {
  242.    assert(status == FIRST_USE || status == NEXT_USE);
  243. #ifdef COMMENT
  244.    if (free_code >= MAXMAX)      /* to fix apparent bug in original */
  245.       return;
  246. #endif
  247. #ifdef COMMENT
  248.    if (status == NEXT_USE)
  249.       table[index].next = free_code;
  250.    else                 /* else must be FIRST_USE */
  251.       table[index].first = free_code;
  252. #endif
  253.    if (status == NEXT_USE)
  254.       table[index].next = (free_code >= MAXMAX ? -1 : free_code);
  255.    else                 /* else must be FIRST_USE */
  256.       table[index].first = (free_code >= MAXMAX ? -1 : free_code);
  257.  
  258. #ifdef COMMENT
  259.    if (free_code < MAXMAX) {
  260. #endif
  261.    if (free_code <= MAXMAX) {
  262.       table[free_code].first = table[free_code].next = -1;
  263.       table[free_code].z_ch = ch & 0xff;
  264.       free_code++;
  265.    }
  266. } /* end ad_ccode() */
  267.  
  268. int lukup_ccode (index, ch, where)
  269. int index;                        /* where to start looking */
  270. int ch;                             /* char to look for */
  271. int *where;                       /* last entry looked at */
  272. {
  273.    *where = index;
  274.    index = table[index].first;
  275.    if (index == -1) {
  276.       return (FIRST_USE);           /* not found, first use */
  277.    } else {
  278.       while (1) {
  279.          if ((table[index].z_ch & 0xff) == (ch & 0xff)) {
  280.             *where = index;
  281.             return (FOUND);
  282.          }
  283.          *where = index;
  284.          index = table[index].next;
  285.          if (index == -1) {
  286.             return (NEXT_USE);
  287.          }
  288.       } /* end while */
  289.    } /* end else */
  290. } /* end lukup_ccode() */
  291.  
  292. void flush_c (count)
  293. int count;
  294. {
  295.    int status;
  296. #ifdef DEBUG
  297. printf(" <flushed %d bytes> ", count);
  298. #endif
  299.    status = write (out_han, out_buf_adr, count);
  300.    if (status == -1)
  301.       prterror ('f', "Error writing during compression.\n");
  302. }
  303.