home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c019 / 3.ddi / AR001 / SLIDE.C < prev   
Encoding:
C/C++ Source or Header  |  1990-04-23  |  6.7 KB  |  276 lines
  1. /***********************************************************
  2.     slide.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include "ar.h"
  5. #include <stdlib.h>
  6. #include <string.h>  /* memmove() */
  7.  
  8. #define PERCOLATE  1
  9.  
  10. #define NIL        0
  11. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  12.  
  13. typedef short  node;
  14.  
  15. static uchar *text, *childcount;
  16. static node pos, matchpos, avail,
  17.     *position, *parent, *prev, *next = NULL;
  18. static int remainder, matchlen;
  19.  
  20. #if MAXMATCH <= (UCHAR_MAX + 1)
  21.     static uchar *level;
  22. #else
  23.     static ushort *level;
  24. #endif
  25.  
  26. static void init_slide(void)
  27. {
  28.     node i;
  29.  
  30.     if (next == NULL) {
  31.         level      = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  32.         childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  33.         #if PERCOLATE
  34.           position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  35.         #else
  36.           position = malloc(DICSIZ * sizeof(*position));
  37.         #endif
  38.         parent     = malloc(DICSIZ * 2 * sizeof(*parent));
  39.         prev       = malloc(DICSIZ * 2 * sizeof(*prev));
  40.         next       = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  41.         if (next == NULL) error("Out of memory.");
  42.     }
  43.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  44.         level[i] = 1;
  45.         #if PERCOLATE
  46.             position[i] = NIL;  /* sentinel */
  47.         #endif
  48.     }
  49.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  50.     avail = 1;
  51.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  52.     next[DICSIZ - 1] = NIL;
  53.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  54. }
  55.  
  56. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  57.  
  58. node child(node q, uchar c)
  59.     /* q's child for character c (NIL if not found) */
  60. {
  61.     node r;
  62.  
  63.     r = next[HASH(q, c)];
  64.     parent[NIL] = q;  /* sentinel */
  65.     while (parent[r] != q) r = next[r];
  66.     return r;
  67. }
  68.  
  69. void makechild(node q, uchar c, node r)
  70.     /* Let r be q's child for character c. */
  71. {
  72.     node h, t;
  73.  
  74.     h = HASH(q, c);
  75.     t = next[h];  next[h] = r;  next[r] = t;
  76.     prev[t] = r;  prev[r] = h;
  77.     parent[r] = q;  childcount[q]++;
  78. }
  79.  
  80. void split(node old)
  81. {
  82.     node new, t;
  83.  
  84.     new = avail;  avail = next[new];  childcount[new] = 0;
  85.     t = prev[old];  prev[new] = t;  next[t] = new;
  86.     t = next[old];  next[new] = t;  prev[t] = new;
  87.     parent[new] = parent[old];
  88.     level[new] = matchlen;
  89.     position[new] = pos;
  90.     makechild(new, text[matchpos + matchlen], old);
  91.     makechild(new, text[pos + matchlen], pos);
  92. }
  93.  
  94. static void insert_node(void)
  95. {
  96.     node q, r, j, t;
  97.     uchar c, *t1, *t2;
  98.  
  99.     if (matchlen >= 4) {
  100.         matchlen--;
  101.         r = (matchpos + 1) | DICSIZ;
  102.         while ((q = parent[r]) == NIL) r = next[r];
  103.         while (level[q] >= matchlen) {
  104.             r = q;  q = parent[q];
  105.         }
  106.         #if PERCOLATE
  107.             t = q;
  108.             while (position[t] < 0) {
  109.                 position[t] = pos;  t = parent[t];
  110.             }
  111.             if (t < DICSIZ) position[t] = -pos;
  112.         #else
  113.             t = q;
  114.             while (t < DICSIZ) {
  115.                 position[t] = pos;  t = parent[t];
  116.             }
  117.         #endif
  118.     } else {
  119.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  120.         if ((r = child(q, c)) == NIL) {
  121.             makechild(q, c, pos);  matchlen = 1;
  122.             return;
  123.         }
  124.         matchlen = 2;
  125.     }
  126.     for ( ; ; ) {
  127.         if (r >= DICSIZ) {
  128.             j = MAXMATCH;  matchpos = r;
  129.         } else {
  130.             j = level[r];
  131.             matchpos = position[r];
  132.             if (matchpos < 0) matchpos = -matchpos;
  133.         }
  134.         if (matchpos >= pos) matchpos -= DICSIZ;
  135.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  136.         while (matchlen < j) {
  137.             if (*t1 != *t2) {  split(r);  return;  }
  138.             matchlen++;  t1++;  t2++;
  139.         }
  140.         if (matchlen == MAXMATCH) break;
  141.         position[r] = pos;
  142.         q = r;
  143.         if ((r = child(q, *t1)) == NIL) {
  144.             makechild(q, *t1, pos);  return;
  145.         }
  146.         matchlen++;
  147.     }
  148.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  149.     t = next[r];  next[pos] = t;  prev[t] = pos;
  150.     parent[pos] = q;  parent[r] = NIL;
  151.     next[r] = pos;  /* special use of next[] */
  152. }
  153.  
  154. static void delete_node(void)
  155. {
  156.     #if PERCOLATE
  157.         node q, r, s, t, u;
  158.     #else
  159.         node r, s, t, u;
  160.     #endif
  161.  
  162.     if (parent[pos] == NIL) return;
  163.     r = prev[pos];  s = next[pos];
  164.     next[r] = s;  prev[s] = r;
  165.     r = parent[pos];  parent[pos] = NIL;
  166.     if (r >= DICSIZ || --childcount[r] > 1) return;
  167.     t = position[r];
  168.     #if PERCOLATE
  169.         if (t < 0) t = -t;
  170.     #endif
  171.     if (t >= pos) t -= DICSIZ;
  172.     #if PERCOLATE
  173.         s = t;  q = parent[r];
  174.         while ((u = position[q]) < 0) {
  175.             u = -u;  if (u >= pos) u -= DICSIZ;
  176.             if (u > s) s = u;
  177.             position[q] = (s | DICSIZ);  q = parent[q];
  178.         }
  179.         if (q < DICSIZ) {
  180.             if (u >= pos) u -= DICSIZ;
  181.             if (u > s) s = u;
  182.             position[q] = -(s | DICSIZ);
  183.         }
  184.     #endif
  185.     s = child(r, text[t + level[r]]);
  186.     t = prev[s];  u = next[s];
  187.     next[t] = u;  prev[u] = t;
  188.     t = prev[r];  next[t] = s;  prev[s] = t;
  189.     t = next[r];  prev[t] = s;  next[s] = t;
  190.     parent[s] = parent[r];  parent[r] = NIL;
  191.     next[r] = avail;  avail = r;
  192. }
  193.  
  194. void get_next_match(void)
  195. {
  196.     int n;
  197.  
  198.     remainder--;
  199.     if (++pos == DICSIZ * 2) {
  200.         memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
  201.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
  202.         remainder += n;  pos = DICSIZ;  putc('.', stderr);
  203.     }
  204.     delete_node();  insert_node();
  205. }
  206.  
  207. void encode(void)
  208. {
  209.     int lastmatchlen;
  210.     node lastmatchpos;
  211.  
  212.     text = malloc(DICSIZ * 2 + MAXMATCH);
  213.     if (text == NULL) error("Out of memory.");
  214.     init_slide();  encode_start();
  215.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
  216.     putc('.', stderr);
  217.     matchlen = 0;
  218.     pos = DICSIZ;  insert_node();
  219.     if (matchlen > remainder) matchlen = remainder;
  220.     while (remainder > 0 && ! unpackable) {
  221.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  222.         get_next_match();
  223.         if (matchlen > remainder) matchlen = remainder;
  224.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
  225.             output(text[pos - 1], 0);
  226.         else {
  227.             output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  228.                    (pos - lastmatchpos - 2) & (DICSIZ - 1));
  229.             while (--lastmatchlen > 0)
  230.                 get_next_match();
  231.             if (matchlen > remainder) matchlen = remainder;
  232.         }
  233.     }
  234.     encode_end();  free(text);
  235. }
  236.  
  237. void decode(void)
  238. {
  239.     int i, j, k, r, c;
  240.     unsigned long count;
  241.  
  242.     text = malloc(DICSIZ);
  243.     if (text == NULL) error("Out of memory.");
  244.     decode_start();
  245.     count = 0;  r = 0;
  246.     while (count < origsize) {
  247.         c = decode_c();
  248.         if (c <= UCHAR_MAX) {
  249.             text[r++] = c;
  250.             if (r == DICSIZ) {
  251.                 if (outfile != stdout) putc('.', stderr);
  252.                 fwrite_crc(text, DICSIZ, outfile);
  253.                 r = 0;
  254.             }
  255.             count++;
  256.         } else {
  257.             j = c - (UCHAR_MAX + 1 - THRESHOLD);  count += j;
  258.             i = (r - decode_p() - 1) & (DICSIZ - 1);
  259.             for (k = 0; k < j; k++) {
  260.                 c = text[(i + k) & (DICSIZ - 1)];
  261.                 text[r++] = c;
  262.                 if (r == DICSIZ) {
  263.                     if (outfile != stdout) putc('.', stderr);
  264.                     fwrite_crc(text, DICSIZ, outfile);
  265.                     r = 0;
  266.                 }
  267.             }
  268.         }
  269.     }
  270.     if (r != 0) {
  271.         fwrite_crc(text, r, outfile);
  272.         if (outfile != stdout) putc('.', stderr);
  273.     }
  274.     free(text);
  275. }
  276.