home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / AR002.LZH / ENCODE.C < prev    next >
C/C++ Source or Header  |  1990-08-13  |  6KB  |  236 lines
  1. /***********************************************************
  2.     encode.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. #define NIL        0
  10. #define MAX_HASH_VAL (3 * DICSIZ + (DICSIZ / 512 + 1) * UCHAR_MAX)
  11.  
  12. typedef short node;
  13.  
  14. static uchar *text, *childcount;
  15. static node pos, matchpos, avail,
  16.     *position, *parent, *prev, *next = NULL;
  17. static int remainder, matchlen;
  18.  
  19. #if MAXMATCH <= (UCHAR_MAX + 1)
  20.     static uchar *level;
  21. #else
  22.     static ushort *level;
  23. #endif
  24.  
  25. static void allocate_memory(void)
  26. {
  27.     if (next != NULL) return;
  28.     text = malloc(DICSIZ * 2 + MAXMATCH);
  29.     level      = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*level));
  30.     childcount = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*childcount));
  31.     #if PERCOLATE
  32.       position = malloc((DICSIZ + UCHAR_MAX + 1) * sizeof(*position));
  33.     #else
  34.       position = malloc(DICSIZ * sizeof(*position));
  35.     #endif
  36.     parent     = malloc(DICSIZ * 2 * sizeof(*parent));
  37.     prev       = malloc(DICSIZ * 2 * sizeof(*prev));
  38.     next       = malloc((MAX_HASH_VAL + 1) * sizeof(*next));
  39.     if (next == NULL) error("Out of memory.");
  40. }
  41.  
  42. static void init_slide(void)
  43. {
  44.     node i;
  45.  
  46.     for (i = DICSIZ; i <= DICSIZ + UCHAR_MAX; i++) {
  47.         level[i] = 1;
  48.         #if PERCOLATE
  49.             position[i] = NIL;  /* sentinel */
  50.         #endif
  51.     }
  52.     for (i = DICSIZ; i < DICSIZ * 2; i++) parent[i] = NIL;
  53.     avail = 1;
  54.     for (i = 1; i < DICSIZ - 1; i++) next[i] = i + 1;
  55.     next[DICSIZ - 1] = NIL;
  56.     for (i = DICSIZ * 2; i <= MAX_HASH_VAL; i++) next[i] = NIL;
  57. }
  58.  
  59. #define HASH(p, c) ((p) + ((c) << (DICBIT - 9)) + DICSIZ * 2)
  60.  
  61. static node child(node q, uchar c)
  62.     /* q's child for character c (NIL if not found) */
  63. {
  64.     node r;
  65.  
  66.     r = next[HASH(q, c)];
  67.     parent[NIL] = q;  /* sentinel */
  68.     while (parent[r] != q) r = next[r];
  69.     return r;
  70. }
  71.  
  72. static void makechild(node q, uchar c, node r)
  73.     /* Let r be q's child for character c. */
  74. {
  75.     node h, t;
  76.  
  77.     h = HASH(q, c);
  78.     t = next[h];  next[h] = r;  next[r] = t;
  79.     prev[t] = r;  prev[r] = h;
  80.     parent[r] = q;  childcount[q]++;
  81. }
  82.  
  83. void split(node old)
  84. {
  85.     node new, t;
  86.  
  87.     new = avail;  avail = next[new];  childcount[new] = 0;
  88.     t = prev[old];  prev[new] = t;  next[t] = new;
  89.     t = next[old];  next[new] = t;  prev[t] = new;
  90.     parent[new] = parent[old];
  91.     level[new] = matchlen;
  92.     position[new] = pos;
  93.     makechild(new, text[matchpos + matchlen], old);
  94.     makechild(new, text[pos + matchlen], pos);
  95. }
  96.  
  97. static void insert_node(void)
  98. {
  99.     node q, r, j, t;
  100.     uchar c, *t1, *t2;
  101.  
  102.     if (matchlen >= 4) {
  103.         matchlen--;
  104.         r = (matchpos + 1) | DICSIZ;
  105.         while ((q = parent[r]) == NIL) r = next[r];
  106.         while (level[q] >= matchlen) {
  107.             r = q;  q = parent[q];
  108.         }
  109.         #if PERCOLATE
  110.             t = q;
  111.             while (position[t] < 0) {
  112.                 position[t] = pos;  t = parent[t];
  113.             }
  114.             if (t < DICSIZ) position[t] = pos | PERC_FLAG;
  115.         #else
  116.             t = q;
  117.             while (t < DICSIZ) {
  118.                 position[t] = pos;  t = parent[t];
  119.             }
  120.         #endif
  121.     } else {
  122.         q = text[pos] + DICSIZ;  c = text[pos + 1];
  123.         if ((r = child(q, c)) == NIL) {
  124.             makechild(q, c, pos);  matchlen = 1;
  125.             return;
  126.         }
  127.         matchlen = 2;
  128.     }
  129.     for ( ; ; ) {
  130.         if (r >= DICSIZ) {
  131.             j = MAXMATCH;  matchpos = r;
  132.         } else {
  133.             j = level[r];
  134.             matchpos = position[r] & ~PERC_FLAG;
  135.         }
  136.         if (matchpos >= pos) matchpos -= DICSIZ;
  137.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  138.         while (matchlen < j) {
  139.             if (*t1 != *t2) {  split(r);  return;  }
  140.             matchlen++;  t1++;  t2++;
  141.         }
  142.         if (matchlen >= MAXMATCH) break;
  143.         position[r] = pos;
  144.         q = r;
  145.         if ((r = child(q, *t1)) == NIL) {
  146.             makechild(q, *t1, pos);  return;
  147.         }
  148.         matchlen++;
  149.     }
  150.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  151.     t = next[r];  next[pos] = t;  prev[t] = pos;
  152.     parent[pos] = q;  parent[r] = NIL;
  153.     next[r] = pos;  /* special use of next[] */
  154. }
  155.  
  156. static void delete_node(void)
  157. {
  158.     #if PERCOLATE
  159.         node q, r, s, t, u;
  160.     #else
  161.         node r, s, t, u;
  162.     #endif
  163.  
  164.     if (parent[pos] == NIL) return;
  165.     r = prev[pos];  s = next[pos];
  166.     next[r] = s;  prev[s] = r;
  167.     r = parent[pos];  parent[pos] = NIL;
  168.     if (r >= DICSIZ || --childcount[r] > 1) return;
  169.     #if PERCOLATE
  170.         t = position[r] & ~PERC_FLAG;
  171.     #else
  172.         t = position[r];
  173.     #endif
  174.     if (t >= pos) t -= DICSIZ;
  175.     #if PERCOLATE
  176.         s = t;  q = parent[r];
  177.         while ((u = position[q]) & PERC_FLAG) {
  178.             u &= ~PERC_FLAG;  if (u >= pos) u -= DICSIZ;
  179.             if (u > s) s = u;
  180.             position[q] = (s | DICSIZ);  q = parent[q];
  181.         }
  182.         if (q < DICSIZ) {
  183.             if (u >= pos) u -= DICSIZ;
  184.             if (u > s) s = u;
  185.             position[q] = s | DICSIZ | PERC_FLAG;
  186.         }
  187.     #endif
  188.     s = child(r, text[t + level[r]]);
  189.     t = prev[s];  u = next[s];
  190.     next[t] = u;  prev[u] = t;
  191.     t = prev[r];  next[t] = s;  prev[s] = t;
  192.     t = next[r];  prev[t] = s;  next[s] = t;
  193.     parent[s] = parent[r];  parent[r] = NIL;
  194.     next[r] = avail;  avail = r;
  195. }
  196.  
  197. static void get_next_match(void)
  198. {
  199.     int n;
  200.  
  201.     remainder--;
  202.     if (++pos == DICSIZ * 2) {
  203.         memmove(&text[0], &text[DICSIZ], DICSIZ + MAXMATCH);
  204.         n = fread_crc(&text[DICSIZ + MAXMATCH], DICSIZ, infile);
  205.         remainder += n;  pos = DICSIZ;  putc('.', stderr);
  206.     }
  207.     delete_node();  insert_node();
  208. }
  209.  
  210. void encode(void)
  211. {
  212.     int lastmatchlen;
  213.     node lastmatchpos;
  214.  
  215.     allocate_memory();  init_slide();  huf_encode_start();
  216.     remainder = fread_crc(&text[DICSIZ], DICSIZ + MAXMATCH, infile);
  217.     putc('.', stderr);
  218.     matchlen = 0;
  219.     pos = DICSIZ;  insert_node();
  220.     if (matchlen > remainder) matchlen = remainder;
  221.     while (remainder > 0 && ! unpackable) {
  222.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  223.         get_next_match();
  224.         if (matchlen > remainder) matchlen = remainder;
  225.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
  226.             output(text[pos - 1], 0);
  227.         else {
  228.             output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  229.                    (pos - lastmatchpos - 2) & (DICSIZ - 1));
  230.             while (--lastmatchlen > 0) get_next_match();
  231.             if (matchlen > remainder) matchlen = remainder;
  232.         }
  233.     }
  234.     huf_encode_end();
  235. }
  236.