home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / ARCHIVERS / lha208src.lzh / LHA / SRC / slide.c < prev    next >
Text File  |  1994-02-14  |  11KB  |  441 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 struct encode_option encode_define[2] = {
  22. #ifdef __STDC__
  23.     /* lh1 */
  24.     {(void(*)())output_dyn,
  25.      (void(*)())encode_start_fix,
  26.      (void(*)())encode_end_dyn},
  27.     /* lh4, 5 */
  28.     {(void(*)())output_st1,
  29.      (void(*)())encode_start_st1,
  30.      (void(*)())encode_end_st1}
  31. #else
  32.     /* lh1 */
  33.     {(int(*)())output_dyn,
  34.      (int(*)())encode_start_fix,
  35.      (int(*)())encode_end_dyn},
  36.     /* lh4, 5 */
  37.     {(int(*)())output_st1,
  38.      (int(*)())encode_start_st1,
  39.      (int(*)())encode_end_st1}
  40. #endif
  41. };
  42.  
  43. static struct decode_option decode_define[7] = {
  44.     /* lh1 */
  45.     {decode_c_dyn, decode_p_st0, decode_start_fix},
  46.     /* lh2 */
  47.     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  48.     /* lh3 */
  49.     {decode_c_st0, decode_p_st0, decode_start_st0},
  50.     /* lh4 */
  51.     {decode_c_st1, decode_p_st1, decode_start_st1},
  52.     /* lh5 */
  53.     {decode_c_st1, decode_p_st1, decode_start_st1},
  54.     /* lzs */
  55.     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  56.     /* lz5 */
  57.     {decode_c_lz5, decode_p_lz5, decode_start_lz5}
  58. };
  59.  
  60. static struct encode_option encode_set;
  61. static struct decode_option decode_set;
  62.  
  63. static node pos, matchpos, avail,
  64. *position, *parent, *prev;
  65. static int remainder, matchlen;
  66. static unsigned char *level, *childcount;
  67. static unsigned short dicsiz;
  68. static unsigned short max_hash_val;
  69. static unsigned short hash1, hash2;
  70.  
  71. int encode_alloc(method)
  72. int method;
  73. {
  74.     if (method == 1) {
  75.         encode_set = encode_define[0];
  76.         maxmatch = 60;
  77.         dicbit = 12;
  78.     } 
  79.     else {
  80.         encode_set = encode_define[1];
  81.         maxmatch = MAXMATCH;
  82.         dicbit = 13;
  83.     }
  84.     while (1) {
  85.         dicsiz = 1 << dicbit;
  86.         max_hash_val = 3 * dicsiz + (dicsiz / 512 + 1) * UCHAR_MAX;
  87.         text = (unsigned char *)malloc(dicsiz * 2 + maxmatch);
  88.         level = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*level));
  89.         childcount = (unsigned char *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*childcount));
  90. #if PERCOLATE
  91.         position = (node *)malloc((dicsiz + UCHAR_MAX + 1) * sizeof(*position));
  92. #else
  93.         position = (node *)malloc(dicsiz * sizeof(*position));
  94. #endif
  95.         parent     = (node *)malloc(dicsiz * 2 * sizeof(*parent));
  96.         prev       = (node *)malloc(dicsiz * 2 * sizeof(*prev));
  97.         next       = (node *)malloc((max_hash_val + 1) * sizeof(*next));
  98.         if (next == NULL || 
  99.             method > 1 && alloc_buf() == NULL) {
  100.             if (next) free(next);
  101.             if (prev) free(prev);
  102.             if (parent) free(parent);
  103.             if (position) free(position);
  104.             if (childcount) free(childcount);
  105.             if (level) free(level);
  106.             if (text) free(text);
  107.         } 
  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()
  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];  
  164.     next[h] = r;  
  165.     next[r] = t;
  166.     prev[t] = r;  
  167.     prev[r] = h;
  168.     parent[r] = q;  
  169.     childcount[q]++;
  170. }
  171.  
  172. static /*inline*/ void split(old)
  173. node old;
  174. {
  175.     node new, t;
  176.  
  177.     new = avail;  
  178.     avail = next[new];  
  179.     childcount[new] = 0;
  180.     t = prev[old];  
  181.     prev[new] = t;  
  182.     next[t] = new;
  183.     t = next[old];  
  184.     next[new] = t;  
  185.     prev[t] = new;
  186.     parent[new] = parent[old];
  187.     level[new] = matchlen;
  188.     position[new] = pos;
  189.     makechild(new, text[matchpos + matchlen], old);
  190.     makechild(new, text[pos + matchlen], pos);
  191. }
  192.  
  193. static void insert_node()
  194. {
  195.     node q, r, j, t;
  196.     unsigned char c, *t1, *t2;
  197.  
  198.     if (matchlen >= 4) {
  199.         matchlen--;
  200.         r = (matchpos + 1) | dicsiz;
  201.         while ((q = parent[r]) == NIL) r = next[r];
  202.         while (level[q] >= matchlen) {
  203.             r = q;  
  204.             q = parent[q];
  205.         }
  206. #if PERCOLATE
  207.         t = q;
  208.         while (position[t] < 0) {
  209.             position[t] = pos;  
  210.             t = parent[t];
  211.         }
  212.         if (t < dicsiz) position[t] = pos | SHRT_MIN;
  213. #else
  214.         t = q;
  215.         while (t < dicsiz) {
  216.             position[t] = pos;  
  217.             t = parent[t];
  218.         }
  219. #endif
  220.     } 
  221.     else {
  222.         q = text[pos] + dicsiz;  
  223.         c = text[pos + 1];
  224.         if ((r = child(q, c)) == NIL) {
  225.             makechild(q, c, pos);  
  226.             matchlen = 1;
  227.             return;
  228.         }
  229.         matchlen = 2;
  230.     }
  231.     for ( ; ; ) {
  232.         if (r >= dicsiz) {
  233.             j = maxmatch;  
  234.             matchpos = r;
  235.         } 
  236.         else {
  237.             j = level[r];
  238.             matchpos = position[r] & SHRT_MAX;
  239.         }
  240.         if (matchpos >= pos) matchpos -= dicsiz;
  241.         t1 = &text[pos + matchlen];  
  242.         t2 = &text[matchpos + matchlen];
  243.         while (matchlen < j) {
  244.             if (*t1 != *t2) {  
  245.                 split(r);  
  246.                 return;  
  247.             }
  248.             matchlen++;  
  249.             t1++;  
  250.             t2++;
  251.         }
  252.         if (matchlen == maxmatch) break;
  253.         position[r] = pos;
  254.         q = r;
  255.         if ((r = child(q, *t1)) == NIL) {
  256.             makechild(q, *t1, pos);  
  257.             return;
  258.         }
  259.         matchlen++;
  260.     }
  261.     t = prev[r];  
  262.     prev[pos] = t;  
  263.     next[t] = pos;
  264.     t = next[r];  
  265.     next[pos] = t;  
  266.     prev[t] = pos;
  267.     parent[pos] = q;  
  268.     parent[r] = NIL;
  269.     next[r] = pos;  /* special use of next[] */
  270. }
  271.  
  272.  
  273. static void delete_node()
  274. {
  275. #if PERCOLATE
  276.     node q, r, s, t, u;
  277. #else
  278.     node r, s, t, u;
  279. #endif
  280.  
  281.     if (parent[pos] == NIL) return;
  282.     r = prev[pos];  
  283.     s = next[pos];
  284.     next[r] = s;  
  285.     prev[s] = r;
  286.     r = parent[pos];  
  287.     parent[pos] = NIL;
  288.     if (r >= dicsiz || --childcount[r] > 1) return;
  289. #if PERCOLATE
  290.     t = position[r] & SHRT_MAX;
  291. #else
  292.     t = position[r];
  293. #endif
  294.     if (t >= pos) t -= dicsiz;
  295. #if PERCOLATE
  296.     s = t;  
  297.     q = parent[r];
  298.     while ((u = position[q]) < 0) {
  299.         u &= SHRT_MAX;  
  300.         if (u >= pos) u -= dicsiz;
  301.         if (u > s) s = u;
  302.         position[q] = (s | dicsiz);  
  303.         q = parent[q];
  304.     }
  305.     if (q < dicsiz) {
  306.         if (u >= pos) u -= dicsiz;
  307.         if (u > s) s = u;
  308.         position[q] = (s | dicsiz) | SHRT_MIN;
  309.     }
  310. #endif
  311.     s = child(r, text[t + level[r]]);
  312.     t = prev[s];  
  313.     u = next[s];
  314.     next[t] = u;  
  315.     prev[u] = t;
  316.     t = prev[r];  
  317.     next[t] = s;  
  318.     prev[s] = t;
  319.     t = next[r];  
  320.     prev[t] = s;  
  321.     next[s] = t;
  322.     parent[s] = parent[r];  
  323.     parent[r] = NIL;
  324.     next[r] = avail;  
  325.     avail = r;
  326. }
  327.  
  328. /* static */void get_next_match()
  329. {
  330.     int n;
  331.  
  332.     remainder--;
  333.     if (++pos == dicsiz * 2) {
  334.         bcopy(&text[dicsiz], &text[0], dicsiz + maxmatch);
  335.         n = fread_crc(&text[dicsiz + maxmatch], dicsiz, infile);
  336.         origsize += n;
  337.         remainder += n;  
  338.         pos = dicsiz;
  339.     }
  340.     delete_node();  
  341.     insert_node();
  342. }
  343.  
  344. void encode(interface)
  345. struct interfacing *interface;
  346. {
  347.     int lastmatchlen, dicsiz1;
  348.     node lastmatchpos;
  349.  
  350.     infile = interface -> infile;
  351.     outfile = interface -> outfile;
  352.     compsize = count = 0L;
  353.     mcrc = unpackable = 0;
  354.     init_slide();  
  355.     encode_set.encode_start();
  356.     dicsiz1 = dicsiz - 1;
  357.     pos = dicsiz + maxmatch;
  358.     memset(&text[pos], ' ', dicsiz);
  359.     remainder = fread_crc(&text[pos], dicsiz, infile);
  360.     origsize = remainder;
  361.     matchlen = 0;
  362.     insert_node();
  363.     while (remainder > 0 && ! unpackable) {
  364.         lastmatchlen = matchlen;  
  365.         lastmatchpos = matchpos;
  366.         get_next_match();
  367.         if (matchlen > remainder) matchlen = remainder;
  368.         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
  369.             encode_set.output(text[pos - 1], 0);
  370.             count++;
  371.         } 
  372.         else {
  373.             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
  374.             (pos - lastmatchpos - 2) & dicsiz1);
  375.             while (--lastmatchlen > 0) {
  376.                 get_next_match();
  377.                 count++;
  378.             }
  379.             if (matchlen > remainder) matchlen = remainder;
  380.         }
  381.     }
  382.     encode_set.encode_end();
  383.     interface -> packed = compsize;
  384.     interface -> original = origsize;
  385. }
  386.  
  387. void decode(interface)
  388. struct interfacing *interface;
  389. {
  390.     int i, j, k, c, dicsiz1, offset;
  391.  
  392.     infile = interface -> infile;
  393.     outfile = interface -> outfile;
  394.     dicbit = interface -> dicbit;
  395.     origsize = interface -> original;
  396.     compsize = interface -> packed;
  397.     decode_set = decode_define[interface -> method - 1];
  398.     mcrc = 0;
  399.     prev_char = -1;
  400.     dicsiz = 1 << dicbit;
  401.     text = (unsigned char *)malloc(dicsiz);
  402.     if (text == NULL)
  403.         /* error(MEMOVRERR, NULL); */
  404.         exit( errno );
  405.     memset(text, ' ', dicsiz);
  406.     decode_set.decode_start();
  407.     dicsiz1 = dicsiz - 1;
  408.     offset = (interface -> method == 6) ? 0x100 - 2 : 0x100 - 3;
  409.     count = 0;  
  410.     loc = 0;
  411.     while (count < origsize) {
  412.         c = decode_set.decode_c();
  413.         if (c <= UCHAR_MAX) {
  414.             text[loc++] = c;
  415.             if (loc == dicsiz) {
  416.                 fwrite_crc(text, dicsiz, outfile);
  417.                 loc = 0;
  418.             }
  419.             count++;
  420.         } 
  421.         else {
  422.             j = c - offset;
  423.             i = (loc - decode_set.decode_p() - 1) & dicsiz1;
  424.             count += j;
  425.             for (k = 0; k < j; k++) {
  426.                 c = text[(i + k) & dicsiz1];
  427.                 text[loc++] = c;
  428.                 if (loc == dicsiz) {
  429.                     fwrite_crc(text, dicsiz, outfile);
  430.                     loc = 0;
  431.                 }
  432.             }
  433.         }
  434.     }
  435.     if (loc != 0) {
  436.         fwrite_crc(text, loc, outfile);
  437.     }
  438.     free(text);
  439. }
  440.  
  441.