home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / lha100bt.zip / lha-1.00 / src / slide.c < prev    next >
C/C++ Source or Header  |  1992-04-04  |  9KB  |  390 lines
  1. /***********************************************************
  2.     slide.c -- sliding dictionary with percolating update
  3. ***********************************************************/
  4. #include "lharc.h"
  5. #include "slidehuf.h"
  6. #include "intrface.h"
  7.  
  8. #define PERCOLATE  1
  9. #define NIL        0
  10.  
  11. node *next = NULL;
  12. int unpackable;
  13. unsigned long origsize, compsize;
  14. unsigned short dicbit;
  15. unsigned short maxmatch;
  16. unsigned long count;
  17. unsigned short loc;
  18. unsigned char *text;
  19. int prev_char;
  20.  
  21. static unsigned long encoded_origsize;
  22.  
  23. static struct encode_option encode_define[2] = {
  24. #if defined(__STDC__) || defined(AIX)
  25. /* lh1 */
  26.     {(void(*)())output_dyn,
  27.      (void(*)())encode_start_fix,
  28.      (void(*)())encode_end_dyn},
  29. /* lh4, 5 */
  30.     {(void(*)())output_st1,
  31.     (void(*)())encode_start_st1,
  32.     (void(*)())encode_end_st1}
  33. #else
  34. /* lh1 */
  35.     {(int(*)())output_dyn,
  36.      (int(*)())encode_start_fix,
  37.      (int(*)())encode_end_dyn},
  38. /* lh4, 5 */
  39.     {(int(*)())output_st1,
  40.     (int(*)())encode_start_st1,
  41.     (int(*)())encode_end_st1}
  42. #endif
  43. };
  44.  
  45. static struct decode_option decode_define[7] = {
  46. /* lh1 */
  47.     {decode_c_dyn, decode_p_st0, decode_start_fix},
  48. /* lh2 */
  49.     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  50. /* lh3 */
  51.     {decode_c_st0, decode_p_st0, decode_start_st0},
  52. /* lh4 */
  53.     {decode_c_st1, decode_p_st1, decode_start_st1},
  54. /* lh5 */
  55.     {decode_c_st1, decode_p_st1, decode_start_st1},
  56. /* lzs */
  57.     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  58. /* lz5 */
  59.     {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  60. };
  61.  
  62. static struct encode_option encode_set;
  63. static struct decode_option decode_set;
  64.  
  65. static node pos, matchpos, avail,
  66.         *position, *parent, *prev;
  67. static int remainder, matchlen;
  68. static unsigned char *level, *childcount;
  69. static unsigned short dicsiz;
  70. static unsigned short max_hash_val;
  71. static unsigned short hash1, hash2;
  72.  
  73. int encode_alloc(method)
  74. int method;
  75. {
  76.   if (method == 1) {
  77.     encode_set = encode_define[0];
  78.     maxmatch = 60;
  79.     dicbit = 12;
  80.   } else {
  81.     encode_set = encode_define[1];
  82.     maxmatch = MAXMATCH;
  83.     dicbit = 13;
  84.   }
  85.   while (1) {
  86.     dicsiz = 1 << dicbit;
  87.     max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  88.     text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
  89.     level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  90.     childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  91. #if PERCOLATE
  92.     position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  93. #else
  94.     position = (node *)malloc(dicsiz * sizeof(*position));
  95. #endif
  96.     parent     = (node *)malloc(dicsiz * 2 * sizeof(*parent));
  97.     prev       = (node *)malloc(dicsiz * 2 * sizeof(*prev));
  98.     next       = (node *)malloc((max_hash_val + 1) * sizeof(*next));
  99.     if (next == NULL || 
  100.     method > 1 && alloc_buf() == NULL) {
  101.       if (next) free(next);
  102.       if (prev) free(prev);
  103.       if (parent) free(parent);
  104.       if (position) free(position);
  105.       if (childcount) free(childcount);
  106.       if (level) free(level);
  107.       if (text) free(text);
  108.     } else {
  109.       break;
  110.     }
  111.     if (--dicbit < 12 )
  112.       /* error(MEMOVRERR, NULL); */
  113.       exit( 207 );
  114.   }
  115.   if (method == 5)
  116.     method = dicbit - 8;
  117.   return method;
  118. }
  119.  
  120. static void init_slide(void)
  121. {
  122.     node i;
  123.  
  124.     for (i = dicsiz; i <= dicsiz + UCHAR_MAX; i++) {
  125.         level[i] = 1;
  126. #if PERCOLATE
  127.             position[i] = NIL;  /* sentinel */
  128. #endif
  129.     }
  130.     for (i = dicsiz; i < dicsiz * 2; i++) parent[i] = NIL;
  131.     avail = 1;
  132.     for (i = 1; i < dicsiz - 1; i++) next[i] = i + 1;
  133.     next[dicsiz - 1] = NIL;
  134.     for (i = dicsiz * 2; i <= max_hash_val; i++) next[i] = NIL;
  135.     hash1 = dicbit - 9;
  136.     hash2 = dicsiz * 2;
  137. }
  138.  
  139. #define HASH(p, c) ((p) + ((c) << hash1) + hash2)
  140.  
  141. static /* inline */ node child(q, c)
  142.     /* q's child for character c (NIL if not found) */
  143. node q;
  144. unsigned char c;
  145. {
  146.     node r;
  147.  
  148.     r = next[HASH(q, c)];
  149.     parent[NIL] = q;  /* sentinel */
  150.     while (parent[r] != q) r = next[r];
  151.     return r;
  152. }
  153.  
  154. static /* inline */ void makechild(q, c, r)
  155.     /* Let r be q's child for character c. */
  156. node q;
  157. unsigned char c;
  158. node r;
  159. {
  160.     node h, t;
  161.  
  162.     h = HASH(q, c);
  163.     t = next[h];  next[h] = r;  next[r] = t;
  164.     prev[t] = r;  prev[r] = h;
  165.     parent[r] = q;  childcount[q]++;
  166. }
  167.  
  168. static /*inline*/ void split(old)
  169. node old;
  170. {
  171.     node new, t;
  172.  
  173.     new = avail;  avail = next[new];  childcount[new] = 0;
  174.     t = prev[old];  prev[new] = t;  next[t] = new;
  175.     t = next[old];  next[new] = t;  prev[t] = new;
  176.     parent[new] = parent[old];
  177.     level[new] = matchlen;
  178.     position[new] = pos;
  179.     makechild(new, text[matchpos + matchlen], old);
  180.     makechild(new, text[pos + matchlen], pos);
  181. }
  182.  
  183. static void insert_node(void)
  184. {
  185.     node q, r, j, t;
  186.     unsigned char c, *t1, *t2;
  187.  
  188.     if (matchlen >= 4) {
  189.         matchlen--;
  190.         r = (matchpos + 1) | dicsiz;
  191.         while ((q = parent[r]) == NIL) r = next[r];
  192.         while (level[q] >= matchlen) {
  193.             r = q;  q = parent[q];
  194.         }
  195. #if PERCOLATE
  196.             t = q;
  197.             while (position[t] < 0) {
  198.                 position[t] = pos;  t = parent[t];
  199.             }
  200.             if (t < dicsiz) position[t] = pos | SHRT_MIN;
  201. #else
  202.             t = q;
  203.             while (t < dicsiz) {
  204.                 position[t] = pos;  t = parent[t];
  205.             }
  206. #endif
  207.     } else {
  208.         q = text[pos] + dicsiz;  c = text[pos + 1];
  209.         if ((r = child(q, c)) == NIL) {
  210.             makechild(q, c, pos);  matchlen = 1;
  211.             return;
  212.         }
  213.         matchlen = 2;
  214.     }
  215.     for ( ; ; ) {
  216.         if (r >= dicsiz) {
  217.             j = maxmatch;  matchpos = r;
  218.         } else {
  219.             j = level[r];
  220.             matchpos = position[r] & SHRT_MAX;
  221.         }
  222.         if (matchpos >= pos) matchpos -= dicsiz;
  223.         t1 = &text[pos + matchlen];  t2 = &text[matchpos + matchlen];
  224.         while (matchlen < j) {
  225.             if (*t1 != *t2) {  split(r);  return;  }
  226.             matchlen++;  t1++;  t2++;
  227.         }
  228.         if (matchlen == maxmatch) break;
  229.         position[r] = pos;
  230.         q = r;
  231.         if ((r = child(q, *t1)) == NIL) {
  232.             makechild(q, *t1, pos);  return;
  233.         }
  234.         matchlen++;
  235.     }
  236.     t = prev[r];  prev[pos] = t;  next[t] = pos;
  237.     t = next[r];  next[pos] = t;  prev[t] = pos;
  238.     parent[pos] = q;  parent[r] = NIL;
  239.     next[r] = pos;  /* special use of next[] */
  240. }
  241.  
  242. static void delete_node(void)
  243. {
  244. #if PERCOLATE
  245.         node q, r, s, t, u;
  246. #else
  247.         node r, s, t, u;
  248. #endif
  249.  
  250.     if (parent[pos] == NIL) return;
  251.     r = prev[pos];  s = next[pos];
  252.     next[r] = s;  prev[s] = r;
  253.     r = parent[pos];  parent[pos] = NIL;
  254.     if (r >= dicsiz || --childcount[r] > 1) return;
  255. #if PERCOLATE
  256.         t = position[r] & SHRT_MAX;
  257. #else
  258.         t = position[r];
  259. #endif
  260.     if (t >= pos) t -= dicsiz;
  261. #if PERCOLATE
  262.         s = t;  q = parent[r];
  263.         while ((u = position[q]) < 0) {
  264.             u &= SHRT_MAX;  if (u >= pos) u -= dicsiz;
  265.             if (u > s) s = u;
  266.             position[q] = (s | dicsiz);  q = parent[q];
  267.         }
  268.         if (q < dicsiz) {
  269.             if (u >= pos) u -= dicsiz;
  270.             if (u > s) s = u;
  271.             position[q] = (s | dicsiz) | SHRT_MIN;
  272.         }
  273. #endif
  274.     s = child(r, text[t + level[r]]);
  275.     t = prev[s];  u = next[s];
  276.     next[t] = u;  prev[u] = t;
  277.     t = prev[r];  next[t] = s;  prev[s] = t;
  278.     t = next[r];  prev[t] = s;  next[s] = t;
  279.     parent[s] = parent[r];  parent[r] = NIL;
  280.     next[r] = avail;  avail = r;
  281. }
  282.  
  283. /* static */void get_next_match(void)
  284. {
  285.     int n;
  286.  
  287.     remainder--;
  288.     if (++pos == dicsiz * 2) {
  289.         bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
  290.         n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
  291.         encoded_origsize += n;
  292.         remainder += n;  pos = dicsiz;
  293.     }
  294.     delete_node();  insert_node();
  295. }
  296.  
  297. void encode(interface)
  298. struct interfacing *interface;
  299. {
  300.     int lastmatchlen, dicsiz1;
  301.     node lastmatchpos;
  302.  
  303.     infile = interface -> infile;
  304.     outfile = interface -> outfile;
  305.     origsize = interface -> original;
  306.     compsize = count = 0L;
  307.     crc = unpackable = 0;
  308.     init_slide();  encode_set.encode_start();
  309.     dicsiz1 = dicsiz - 1;
  310.     pos = dicsiz + maxmatch;
  311.     memset(&text[pos], ' ', dicsiz);
  312.     remainder = fread_crc(&text[pos], dicsiz, infile);
  313.     encoded_origsize = remainder;
  314.     matchlen = 0;
  315.     insert_node();
  316.     while (remainder > 0 && ! unpackable) {
  317.         lastmatchlen = matchlen;  lastmatchpos = matchpos;
  318.         get_next_match();
  319.         if (matchlen > remainder) matchlen = remainder;
  320.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  321.             encode_set.output(text[pos - 1], 0);
  322.             count++;
  323.         } else {
  324.             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  325.                    (pos - lastmatchpos - 2) & dicsiz1);
  326.             while (--lastmatchlen > 0) {
  327.                 get_next_match();
  328.                 count++;
  329.             }
  330.             if (matchlen > remainder) matchlen = remainder;
  331.         }
  332.     }
  333.     encode_set.encode_end();
  334.     interface -> packed = compsize;
  335.     interface -> original = encoded_origsize;
  336. }
  337.  
  338. void decode(interface)
  339. struct interfacing *interface;
  340. {
  341.     int i, j, k, c, dicsiz1, offset;
  342.  
  343.     infile = interface -> infile;
  344.     outfile = interface -> outfile;
  345.     dicbit = interface -> dicbit;
  346.     origsize = interface -> original;
  347.     compsize = interface -> packed;
  348.     decode_set = decode_define[interface -> method - 1];
  349.     crc = 0;
  350.     prev_char = -1;
  351.     dicsiz = 1 << dicbit;
  352.     text = (unsigned char *)malloc(dicsiz);
  353.     if (text == NULL)
  354.         /* error(MEMOVRERR, NULL); */
  355.         exit( errno );
  356.     memset(text, ' ', dicsiz);
  357.     decode_set.decode_start();
  358.     dicsiz1 = dicsiz - 1;
  359.     offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
  360.     count = 0;  loc = 0;
  361.     while (count < origsize) {
  362.         c = decode_set.decode_c();
  363.         if (c <= UCHAR_MAX) {
  364.             text[loc++] = c;
  365.             if (loc == dicsiz) {
  366.                 fwrite_crc(text, dicsiz, outfile);
  367.                 loc = 0;
  368.             }
  369.             count++;
  370.         } else {
  371.             j = c - offset;
  372.             i = (loc - decode_set.decode_p() - 1) & dicsiz1;
  373.             count += j;
  374.             for (k = 0; k < j; k++) {
  375.                 c = text[(i + k) & dicsiz1];
  376.                 text[loc++] = c;
  377.                 if (loc == dicsiz) {
  378.                     fwrite_crc(text, dicsiz, outfile);
  379.                     loc = 0;
  380.                 }
  381.             }
  382.         }
  383.     }
  384.     if (loc != 0) {
  385.         fwrite_crc(text, loc, outfile);
  386.     }
  387.     free(text);
  388. }
  389.  
  390.