home *** CD-ROM | disk | FTP | other *** search
/ Inside Multimedia 1995 July / IMM0795.ISO / share / os2 / zoo21_32 / source / encode.c < prev    next >
C/C++ Source or Header  |  1993-12-17  |  8KB  |  317 lines
  1. /*$Source: /usr/home/dhesi/zoo/RCS/encode.c,v $*/
  2. /*$Id: encode.c,v 1.41 91/07/09 01:39:47 dhesi Exp $*/
  3.  
  4. /*
  5. Adapted from "ar" archiver written by Haruhiko Okumura.
  6. */
  7.  
  8. #include "options.h"
  9. #include "zoo.h"
  10. #include "ar.h"
  11. #include "lzh.h"
  12.  
  13. extern void prterror();
  14. extern char *out_buf_adr;
  15.  
  16. #include <assert.h>
  17.  
  18. #ifdef ANSI_HDRS
  19. # include <stdlib.h>
  20. # include <string.h>
  21. #endif
  22.  
  23. #include "errors.i"
  24.  
  25. FILE *lzh_infile;
  26. FILE *lzh_outfile;
  27.  
  28. /*
  29. sliding dictionary with percolating update
  30. */
  31.  
  32. #define PERCOLATE  1
  33. #define NIL        0
  34. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  35.  
  36. typedef short node;
  37.  
  38. static uchar *text, *childcount;
  39. static node pos, matchpos, avail,
  40.     *position, *parent, *prev, *next = NULL;
  41. static int remainder, matchlen;
  42.  
  43. #if MAXMATCH <= (UCHAR_MAX + 1)
  44.     static uchar *level;
  45. # define T_LEVEL  uchar *
  46. #else
  47.     static ushort *level;
  48. # define T_LEVEL  ushort *
  49. #endif
  50.  
  51. static void allocate_memory()
  52. {
  53.     if (next != NULL) return;
  54.     /* text = (uchar *) malloc(DICSIZ * 2 + MAXMATCH); */
  55.     text = (uchar *) out_buf_adr; /* reuse I/O buffer used elsewhere */
  56.     level      = (T_LEVEL) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  57.     childcount = (uchar *)malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  58. #ifdef PERCOLATE
  59.       position = (node *) malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  60. #else
  61.       position = (node *) malloc(DICSIZ * sizeof(*position));
  62. #endif
  63.     parent     = (node *) malloc(DICSIZ * 2 * sizeof(*parent));
  64.     prev       = (node *) malloc(DICSIZ * 2 * sizeof(*prev));
  65.     next       = (node *) malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  66.     if (next == NULL) prterror('f', no_memory);
  67. }
  68.  
  69. static void init_slide()
  70. {
  71.     node i;
  72.  
  73.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  74.         level[i] = 1;
  75. #ifdef PERCOLATE
  76.             position[i] = NIL;  /* sentinel */
  77. #endif
  78.     }
  79.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  80.     avail = 1;
  81.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  82.     next[DICSIZ - 1] = NIL;
  83.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  84. }
  85.  
  86. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  87.  
  88. static node child(q, c)
  89. node q;
  90. uchar c;
  91.     /* q's child for character c (NIL if not found) */
  92. {
  93.     node r;
  94.  
  95.     r = next[HASH(q, c)];
  96.     parent[NIL] = q;  /* sentinel */
  97.     while (parent[r] != q) r = next[r];
  98.     return r;
  99. }
  100.  
  101. static void makechild(q, c, r)
  102. node q;
  103. uchar c;
  104. node r;
  105.     /* Let r be q's child for character c. */
  106. {
  107.     node h, t;
  108.  
  109.     h = HASH(q, c);
  110.     t = next[h];  next[h] = r;  next[r] = t;
  111.     prev[t] = r;  prev[r] = h;
  112.     parent[r] = q;  childcount[q]++;
  113. }
  114.  
  115. void split(old)
  116. node old;
  117. {
  118.     node new, t;
  119.  
  120.     new = avail;  avail = next[new];  childcount[new] = 0;
  121.     t = prev[old];  prev[new] = t;  next[t] = new;
  122.     t = next[old];  next[new] = t;  prev[t] = new;
  123.     parent[new] = parent[old];
  124.     level[new] = matchlen;
  125.     position[new] = pos;
  126.     makechild(new, text[matchpos + matchlen], old);
  127.     makechild(new, text[pos + matchlen], pos);
  128. }
  129.  
  130. static void insert_node()
  131. {
  132.     node q, r, j, t;
  133.     uchar c, *t1, *t2;
  134.  
  135.     if (matchlen >= 4) {
  136.         matchlen--;
  137.         r = (matchpos + 1) | DICSIZ;
  138.         while ((q = parent[r]) == NIL) r = next[r];
  139.         while (level[q] >= matchlen) {
  140.             r = q;  q = parent[q];
  141.         }
  142. #ifdef PERCOLATE
  143.             t = q;
  144.             while (position[t] < 0) {
  145.                 position[t] = pos;  t = parent[t];
  146.             }
  147.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  148. #else
  149.             t = q;
  150.             while (t < DICSIZ) {
  151.                 position[t] = pos;  t = parent[t];
  152.             }
  153. #endif
  154.     } else {
  155.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  156.         if ((r = child(q, c)) == NIL) {
  157.             makechild(q, c, pos);  matchlen = 1;
  158.             return;
  159.         }
  160.         matchlen = 2;
  161.     }
  162.     for ( ; ; ) {
  163.         if (r >= DICSIZ) {
  164.             j = MAXMATCH;  matchpos = r;
  165.         } else {
  166.             j = level[r];
  167.             matchpos = position[r] & ~PERC_FLAG;
  168.         }
  169.         if (matchpos >= pos) matchpos -= DICSIZ;
  170.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  171.         while (matchlen < j) {
  172.             if (*t1 != *t2) {  split(r);  return;  }
  173.             matchlen++;  t1++;  t2++;
  174.         }
  175.         if (matchlen >= MAXMATCH) break;
  176.         position[r] = pos;
  177.         q = r;
  178.         if ((r = child(q, *t1)) == NIL) {
  179.             makechild(q, *t1, pos);  return;
  180.         }
  181.         matchlen++;
  182.     }
  183.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  184.     t = next[r];  next[pos] = t;  prev[t] = pos;
  185.     parent[pos] = q;  parent[r] = NIL;
  186.     next[r] = pos;  /* special use of next[] */
  187. }
  188.  
  189. static void delete_node()
  190. {
  191. #ifdef PERCOLATE
  192.         node q, r, s, t, u;
  193. #else
  194.         node r, s, t, u;
  195. #endif
  196.  
  197.     if (parent[pos] == NIL) return;
  198.     r = prev[pos];  s = next[pos];
  199.     next[r] = s;  prev[s] = r;
  200.     r = parent[pos];  parent[pos] = NIL;
  201.     if (r >= DICSIZ || --childcount[r] > 1) return;
  202. #ifdef PERCOLATE
  203.         t = position[r] & ~PERC_FLAG;
  204. #else
  205.         t = position[r];
  206. #endif
  207.     if (t >= pos) t -= DICSIZ;
  208. #ifdef PERCOLATE
  209.         s = t;  q = parent[r];
  210.         while ((u = position[q]) & PERC_FLAG) {
  211.             u &= ~PERC_FLAG;  if (u >= pos) u -= DICSIZ;
  212.             if (u > s) s = u;
  213.             position[q] = (s | DICSIZ);  q = parent[q];
  214.         }
  215.         if (q < DICSIZ) {
  216.             if (u >= pos) u -= DICSIZ;
  217.             if (u > s) s = u;
  218.             position[q] = s | DICSIZ | PERC_FLAG;
  219.         }
  220. #endif
  221.     s = child(r, text[t + level[r]]);
  222.     t = prev[s];  u = next[s];
  223.     next[t] = u;  prev[u] = t;
  224.     t = prev[r];  next[t] = s;  prev[s] = t;
  225.     t = next[r];  prev[t] = s;  next[s] = t;
  226.     parent[s] = parent[r];  parent[r] = NIL;
  227.     next[r] = avail;  avail = r;
  228. }
  229.  
  230. static void get_next_match()
  231. {
  232.     int n;
  233.  
  234.     remainder--;
  235.     if (++pos == DICSIZ * 2) {
  236. #ifdef CHECK_BREAK
  237.         check_break();
  238. #endif
  239.         (void) MOVE_LEFT((char *) &text[0], (char *) &text[DICSIZ], DICSIZ + MAXMATCH);
  240.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, lzh_infile);
  241.         remainder += n;  pos = DICSIZ;
  242. #ifdef SHOW_DOTS
  243.         (void) putc('.', stderr);
  244.         (void) fflush(stderr);
  245. #endif
  246.     }
  247.     delete_node();  insert_node();
  248. }
  249.  
  250. /* read from infile, compress, write to outfile */
  251. void encode(infile, outfile)
  252. FILE *infile;
  253. FILE *outfile;
  254. {
  255.     int lastmatchlen;
  256.     node lastmatchpos;
  257.  
  258.     /* make input/output files visible to other functions */
  259.     lzh_infile = infile;
  260.     lzh_outfile = outfile;
  261.  
  262.     allocate_memory();  init_slide();  huf_encode_start();
  263.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, lzh_infile);
  264. #ifdef SHOW_DOTS
  265.     (void) putc('.', stderr);
  266.     (void) fflush(stderr);
  267. #endif
  268.     matchlen = 0;
  269.     pos = DICSIZ;  insert_node();
  270.     if (matchlen > remainder) matchlen = remainder;
  271.     while (remainder > 0 && ! unpackable) {
  272.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  273.         get_next_match();
  274.         if (matchlen > remainder) matchlen = remainder;
  275.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  276. #if 0
  277.             d1log("%c", text[pos-1]);
  278. #endif
  279.             output(text[pos - 1], 0);
  280.         } else {
  281. #if 0
  282.         (void) putc('.', stderr); (void) fflush(stderr);
  283. #endif
  284.  
  285. #if 0
  286.             {
  287.                 int i;
  288.                 d1log("\nlastmatchlen=%d, pos=%d, lastmatchpos=%d",
  289.                             lastmatchlen, pos, lastmatchpos);
  290.                 d1log("\n[%d: ", (int) lastmatchlen);
  291.                 for (i = 0;  i < lastmatchlen;  i++)
  292.                     d1log("%c", text[lastmatchpos + i]);
  293.                 d1log("]\n");
  294.             }
  295. #endif
  296.  
  297.             output((uint) (lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD)),
  298.                    (uint) ((pos - lastmatchpos - 2) & (DICSIZ - 1)));
  299.             while (--lastmatchlen > 0) get_next_match();
  300.             if (matchlen > remainder) matchlen = remainder;
  301.         }
  302.     }
  303.     huf_encode_end();
  304. }
  305.  
  306. #ifdef NEED_MEMMOVE
  307. /* like memmove, but for moving stuff LEFT (downwards in memory) only!! */
  308. void move_left(dest, src, len)
  309. char *dest;
  310. char *src;
  311. int len;
  312. {
  313.     while (len-- > 0)
  314.         *dest++ = *src++;
  315. }
  316. #endif /* NEED_MEMMOVE */
  317.