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