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