home *** CD-ROM | disk | FTP | other *** search
/ DOS/V Power Report 1997 December / VPR9712A.ISO / OLS / OS2 / LHA2P205 / LHA2P205.LZH / lha2-2.05pre / source.lzh / src / slide.c < prev    next >
C/C++ Source or Header  |  1995-10-13  |  10KB  |  520 lines
  1. /*
  2.  * slide.c --- sliding dictionary with percolating update
  3.  *   Copyright (C) 1988-1992, Haruyasu YOSHIZAKI
  4.  *
  5.  * $Log$
  6.  */
  7.  
  8.  
  9. #include <sys/types.h>
  10. #include <stdio.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <limits.h>
  14. #include <time.h>
  15. #include "typedef.h"
  16. #include "port2.h"
  17. #include "lh.h"
  18. #include "header.h"
  19. #include "slidehuf.h"
  20. #include "intrface.h"
  21. #include "errmes.h"
  22.  
  23.  
  24. #define PERCOLATE  1
  25. #define NIL        0
  26. #define HASH(p, c) ((p) + ((c) << hash1) + hash2)
  27.  
  28.  
  29. node *next = NULL;
  30. int unpackable;
  31. ulong origsize, compsize;
  32. ushort dicbit;
  33. ushort maxmatch;
  34. ulong count;
  35. uchar *use_ptr;
  36. ushort loc;
  37. uchar text[TEXT_SIZE];
  38.  
  39.  
  40. static struct encode_option encode_define[2] =
  41. {
  42.   /* lh1 */
  43.   {output_dyn, encode_start_fix, encode_end_dyn},
  44.   /* lh4, 5 */
  45.   {output_st1, encode_start_st1, encode_end_st1}
  46. };
  47. static struct decode_option decode_define[7] =
  48. {
  49.   /* lh1 */
  50.   {decode_c_dyn, decode_p_st0, decode_start_fix},
  51.   /* lh2 */
  52.   {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  53.   /* lh3 */
  54.   {decode_c_st0, decode_p_st0, decode_start_st0},
  55.   /* lh4 */
  56.   {decode_c_st1, decode_p_st1, decode_start_st1},
  57.   /* lh5 */
  58.   {decode_c_st1, decode_p_st1, decode_start_st1},
  59.   /* lzs */
  60.   {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  61.   /* lz5 */
  62.   {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  63. };
  64. static struct encode_option encode_set;
  65. static struct decode_option decode_set;
  66. static node pos, matchpos, avail, *position, *parent, *prev;
  67. static int remainder, matchlen;
  68. static uchar *level, *childcount;
  69. static ushort dicsiz, max_hash_val, hash1, hash2;
  70.  
  71.  
  72. int
  73. encode_alloc(int method)
  74. {
  75.   if(method == 1)
  76.     {
  77.       encode_set = encode_define[0];
  78.       maxmatch = 60;
  79.       dicbit = 12;
  80.     }
  81.   else
  82.     {
  83.       encode_set = encode_define[1];
  84.       maxmatch = MAXMATCH;
  85.       dicbit = method + 8;
  86.     }
  87.  
  88.   while(1)
  89.     {
  90.       dicsiz = 1U << dicbit;
  91.       max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  92.       level = malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  93.       childcount = malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  94. #if PERCOLATE
  95.       position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  96. #else
  97.       position = (node *)malloc(dicsiz * sizeof(*position));
  98. #endif
  99.       parent = (node *)malloc(dicsiz * 2 * sizeof(*parent));
  100.       prev = (node *)malloc(dicsiz * 2 * sizeof(*prev));
  101.       next = (node *)malloc((max_hash_val + 1) * sizeof(*next));
  102.       if(next == NULL || method > 1 && alloc_buf() == NULL)
  103.     {
  104.       if(next)
  105.         free(next);
  106.       if(prev)
  107.         free(prev);
  108.       if(parent)
  109.         free(parent);
  110.       if(position)
  111.         free(position);
  112.       if(childcount)
  113.         free(childcount);
  114.       if(level)
  115.         free(level);
  116.     }
  117.       else
  118.     break;
  119.       if(--dicbit < 12 )
  120.     error(MEMOVRERR, NULL);
  121.     }
  122.  
  123.   memset(level, 0, (dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  124.   memset(childcount , 0, (dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  125. #if PERCOLATE
  126.   memset(position, 0, (dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  127. #else
  128.   memset(position, 0, dicsiz * sizeof(*position));
  129. #endif
  130.   memset(parent, 0, dicsiz * 2 * sizeof(*parent));
  131.   memset(prev, 0, dicsiz * 2 * sizeof(*prev));
  132.   memset(next, 0, (max_hash_val + 1) * sizeof(*next));
  133.  
  134.   if(method == 5)
  135.     method = dicbit - 8;
  136.  
  137.   return method;
  138. }
  139.  
  140.  
  141. static void
  142. init_slide(void)
  143. {
  144.   node i;
  145.  
  146.   for(i = dicsiz; i <= dicsiz + UCHAR_MAX; i++)
  147.     {
  148.       level[i] = 1;
  149. #if PERCOLATE
  150.       position[i] = NIL;    /* sentinel */
  151. #endif
  152.     }
  153.   for(i = dicsiz; i < dicsiz * 2; i++)
  154.     parent[i] = NIL;
  155.   avail = 1;
  156.   for(i = 1; i < dicsiz - 1; i++)
  157.     next[i] = i + 1;
  158.   next[dicsiz - 1] = NIL;
  159.   for(i = dicsiz * 2; i <= max_hash_val; i++)
  160.     next[i] = NIL;
  161.   hash1 = dicbit - 9;
  162.   hash2 = dicsiz * 2;
  163. }
  164.  
  165.  
  166. static node
  167. child(node q, uchar c)
  168. /* q's child for character c (NIL if not found) */
  169. {
  170.   node r;
  171.  
  172.   r = next[HASH(q, c)];
  173.   parent[NIL] = q;        /* sentinel */
  174.   while(parent[r] != q)
  175.     r = next[r];
  176.  
  177.   return r;
  178. }
  179.  
  180.  
  181. static void
  182. makechild(node q, uchar c, node r)
  183. /* Let r be q's child for character c. */
  184. {
  185.   node h, t;
  186.  
  187.   h = HASH(q, c);
  188.   t = next[h];
  189.   next[h] = r;
  190.   next[r] = t;
  191.   prev[t] = r;
  192.   prev[r] = h;
  193.   parent[r] = q;
  194.   childcount[q]++;
  195. }
  196.  
  197.  
  198. static void
  199. split(node old)
  200. {
  201.   node new, t;
  202.  
  203.   new = avail;
  204.   avail = next[new];
  205.   childcount[new] = 0;
  206.   t = prev[old];
  207.   prev[new] = t;
  208.   next[t] = new;
  209.   t = next[old];
  210.   next[new] = t;
  211.   prev[t] = new;
  212.   parent[new] = parent[old];
  213.   level[new] = matchlen;
  214.   position[new] = pos;
  215.   makechild(new, text[matchpos + matchlen], old);
  216.   makechild(new, text[pos + matchlen], pos);
  217. }
  218.  
  219.  
  220. static void
  221. insert_node(void)
  222. {
  223.   node q, r, j, t;
  224.   uchar c, *t1, *t2;
  225.  
  226.   if(matchlen >= 4)
  227.     {
  228.       matchlen--;
  229.       r = (uint)(matchpos + 1) | (uint)dicsiz;
  230.       while((q = parent[r]) == NIL)
  231.     r = next[r];
  232.       while(level[q] >= matchlen)
  233.     {
  234.       r = q;
  235.       q = parent[q];
  236.     }
  237. #if PERCOLATE
  238.       t = q;
  239.       while(position[t] < 0)
  240.     {
  241.       position[t] = pos;
  242.       t = parent[t];
  243.     }
  244.       if(t < dicsiz)
  245.     position[t] = (uint)pos | 0x8000;
  246. #else
  247.       t = q;
  248.       while(t < dicsiz)
  249.     {
  250.       position[t] = pos;
  251.       t = parent[t];
  252.     }
  253. #endif
  254.     }
  255.   else
  256.     {
  257.       q = text[pos] + dicsiz;
  258.       c = text[pos + 1];
  259.       if((r = child(q, c)) == NIL)
  260.     {
  261.       makechild(q, c, pos);
  262.       matchlen = 1;
  263.       return;
  264.     }
  265.       matchlen = 2;
  266.     }
  267.   for(;;)
  268.     {
  269.       if(r >= dicsiz)
  270.     {
  271.       j = maxmatch;
  272.       matchpos = r;
  273.     }
  274.       else
  275.     {
  276.       j = level[r];
  277.       matchpos = (uint)position[r] & 0x7fff;
  278.     }
  279.       if(matchpos >= pos)
  280.     matchpos -= dicsiz;
  281.       t1 = &text[pos + matchlen];
  282.       t2 = &text[matchpos + matchlen];
  283.       while(matchlen < j)
  284.     {
  285.       if(*t1 != *t2)
  286.         {
  287.           split(r);
  288.           return;
  289.         }
  290.       matchlen++;
  291.       t1++;
  292.       t2++;
  293.     }
  294.       if(matchlen == maxmatch)
  295.     break;
  296.       position[r] = pos;
  297.       q = r;
  298.       if((r = child(q, *t1)) == NIL)
  299.     {
  300.       makechild(q, *t1, pos);
  301.       return;
  302.     }
  303.       matchlen++;
  304.     }
  305.   t = prev[r];
  306.   prev[pos] = t;
  307.   next[t] = pos;
  308.   t = next[r];
  309.   next[pos] = t;
  310.   prev[t] = pos;
  311.   parent[pos] = q;
  312.   parent[r] = NIL;
  313.   next[r] = pos;        /* special use of next[] */
  314. }
  315.  
  316.  
  317. #ifdef __API16__
  318. #pragma optimize("awgelzc", off)
  319. #endif
  320. static void
  321. delete_node(void)
  322. {
  323. #if PERCOLATE
  324.   node q, r, s, t, u;
  325. #else
  326.   node r, s, t, u;
  327. #endif
  328.  
  329.   if(parent[pos] == NIL)
  330.     return;
  331.   r = prev[pos];
  332.   s = next[pos];
  333.   next[r] = s;
  334.   prev[s] = r;
  335.   r = parent[pos];
  336.   parent[pos] = NIL;
  337.   if(r >= dicsiz || --childcount[r] > 1)
  338.     return;
  339.  
  340. #if PERCOLATE
  341.   t = (uint)position[r] & 0x7fff;
  342. #else
  343.   t = position[r];
  344. #endif
  345.  
  346.   if(t >= pos)
  347.     t -= dicsiz;
  348.  
  349. #if PERCOLATE
  350.   s = t;
  351.   q = parent[r];
  352.   while((u = position[q]) < 0)
  353.     {
  354.       u = (uint)u & 0x7fff;
  355.       if(u >= pos)
  356.     u -= dicsiz;
  357.       if(u > s)
  358.     s = u;
  359.       position[q] = ((uint)s | (uint)dicsiz);
  360.       q = parent[q];
  361.     }
  362.   if(q < dicsiz)
  363.     {
  364.       if(u >= pos)
  365.     u -= dicsiz;
  366.       if(u > s)
  367.     s = u;
  368.       position[q] = ((uint)s | (uint)dicsiz) | 0x8000;
  369.     }
  370. #endif
  371.  
  372.   s = child(r, text[t + level[r]]);
  373.   t = prev[s];
  374.   u = next[s];
  375.   next[t] = u;
  376.   prev[u] = t;
  377.   t = prev[r];
  378.   next[t] = s;
  379.   prev[s] = t;
  380.   t = next[r];
  381.   prev[t] = s;
  382.   next[s] = t;
  383.   parent[s] = parent[r];
  384.   parent[r] = NIL;
  385.   next[r] = avail;
  386.   avail = r;
  387. }
  388. #ifdef __API16__
  389. #pragma optimize("awgelzc", on)
  390. #endif
  391.  
  392.  
  393. void
  394. get_next_match(hword *crc)
  395. {
  396.   int n;
  397.  
  398.   remainder--;
  399.   if(++pos == dicsiz * 2)
  400.     {
  401.       memmove(&text[0], &text[dicsiz], dicsiz + maxmatch);
  402.       n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile, crc);
  403.       remainder += n;
  404.       pos = dicsiz;
  405.     }
  406.   delete_node();
  407.   insert_node();
  408. }
  409.  
  410.  
  411. hword
  412. encode(struct interfacing *interface)
  413. {
  414.   int lastmatchlen, dicsiz1;
  415.   node lastmatchpos;
  416.   hword crc = 0;
  417.  
  418.   infile = interface -> infile;
  419.   outfile = interface -> outfile;
  420.   origsize = interface -> original;
  421.   compsize = count = 0;
  422.   unpackable = 0;
  423.   init_slide();
  424.   encode_set.encode_start();
  425.   dicsiz1 = dicsiz - 1;
  426.   pos = dicsiz + maxmatch;
  427.   memset(&text[pos], ' ', dicsiz);
  428.   remainder = fread_crc(&text[pos], dicsiz, infile, &crc);
  429.   matchlen = 0;
  430.   insert_node();
  431.   if(matchlen > remainder)
  432.     matchlen = remainder;
  433.   while(remainder > 0 && ! unpackable)
  434.     {
  435.       lastmatchlen = matchlen;
  436.       lastmatchpos = matchpos;
  437.       get_next_match(&crc);
  438.       if(matchlen > remainder)
  439.     matchlen = remainder;
  440.       if(matchlen > lastmatchlen || lastmatchlen < THRESHOLD)
  441.     {
  442.       encode_set.output(text[pos - 1], 0);
  443.     }
  444.       else
  445.     {
  446.       encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  447.                 (uint)(pos - lastmatchpos - 2) & (uint)dicsiz1);
  448.       while(--lastmatchlen > 0)
  449.         {
  450.           get_next_match(&crc);
  451.         }
  452.       if(matchlen > remainder)
  453.         matchlen = remainder;
  454.     }
  455.     }
  456.   encode_set.encode_end();
  457.   interface -> packed = compsize;
  458.  
  459.   return crc;
  460. }
  461.  
  462.  
  463. hword
  464. decode(struct interfacing *interface)
  465. {
  466.   int i, j, k, c, dicsiz1, offset;
  467.   hword crc = 0;
  468.  
  469.   infile = interface -> infile;
  470.   outfile = interface -> outfile;
  471.   dicbit = interface -> dicbit;
  472.   origsize = interface -> original;
  473.   compsize = interface -> packed;
  474.   use_ptr = interface -> internal; /* for display usage */
  475.   decode_set = decode_define[interface -> method - 1];
  476.   dicsiz = 1U << dicbit;
  477.   if(text == NULL)
  478.     error(MEMOVRERR, NULL);
  479.   memset(text, ' ', dicsiz);
  480.   decode_set.decode_start();
  481.   dicsiz1 = dicsiz - 1;
  482.   offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
  483.   count = 0;
  484.   loc = 0;
  485.   while(count < origsize)
  486.     {
  487.       c = decode_set.decode_c();
  488.       if(c <= UCHAR_MAX)
  489.     {
  490.       text[loc++] = c;
  491.       if(loc == dicsiz)
  492.         {
  493.           fwrite_crc(text, dicsiz, outfile, &crc);
  494.           loc = 0;
  495.         }
  496.       count++;
  497.     }
  498.       else
  499.     {
  500.       j = c - offset;
  501.       i = (uint)(loc - decode_set.decode_p() - 1) & (uint)dicsiz1;
  502.       count += j;
  503.       for(k = 0; k < j; k++)
  504.         {
  505.           c = text[(uint)(i + k) & (uint)dicsiz1];
  506.           text[loc++] = c;
  507.           if(loc == dicsiz)
  508.         {
  509.           fwrite_crc(text, dicsiz, outfile, &crc);
  510.           loc = 0;
  511.         }
  512.         }
  513.     }
  514.     }
  515.   if(loc != 0)
  516.     fwrite_crc(text, loc, outfile, &crc);
  517.  
  518.   return crc;
  519. }
  520.