home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume35 / freeze / part01 / lz.c < prev    next >
C/C++ Source or Header  |  1993-02-21  |  4KB  |  154 lines
  1. #include "freeze.h"
  2. #include "lz.h"
  3.  
  4. /*----------------------------------------------------------------------*/
  5. /*                                                                      */
  6. /*                          LZSS ENCODING                               */
  7. /*                                                                      */
  8. /*----------------------------------------------------------------------*/
  9.  
  10. uc_t    text_buf[WINSIZE + LOOKAHEAD - 1];/* cyclic buffer with an overlay */
  11. int     match_position;                 /* current position of
  12.                         matched pattern */
  13. int     chain_length;                   /* max_chain_length ==
  14.                         CHAIN_THRESHOLD >> greedy */
  15.  
  16. /*      next[N+1..] is used as hash table,
  17.     the rest of next is a link down,
  18. */
  19.  
  20. hash_t hashtab[hash_size];      /* a VERY large array :-) */
  21. hash_t next[WINSIZE];
  22.  
  23. #ifdef GATHER_STAT
  24. long node_matches, node_compares, node_prolongations;
  25. #endif  /* GATHER_STAT */
  26.  
  27. /* Initialize the data structures and allocate memory, if needed.
  28.     Although there is no more trees in the LZ algorithm
  29.     implementation, routine name is kept intact :-)
  30. */
  31.  
  32. void InitTree ()
  33. {
  34.  
  35.     unsigned i = 0;
  36. #ifdef GATHER_STAT
  37.     node_matches = node_compares = node_prolongations = 0;
  38. #endif  /* GATHER_STAT */
  39.  
  40.     do {
  41.         hashtab[i] = 0;
  42.     } while (i++ != hash_size - 1);
  43.  
  44.     if (greedy >= 0)
  45.         chain_length = ((CHAIN_THRESHOLD - 1) >> greedy) + 1;
  46.     else
  47.         chain_length = LOOKAHEAD * 2;
  48. }
  49.  
  50. /* Get the longest (longer than `match_length' when entering in function)
  51.     nearest match of the string beginning in text_buf[r]
  52.     to the cyclic buffer. Result (length & position) is returned
  53.     as the result and in global variable
  54.     `match_position'). Unchanged `match_length' denotes failure and
  55.     `match_position' contains garbage !!
  56.     In order to achieve faster operation, `match_length' is shifted
  57.     down to LOOKAHEAD. Ideas of Andrew Cadach <kadach@isi.itfs.nsk.su>
  58.     have been used (lastbyte).
  59. */
  60.  
  61. int get_next_match (match_length, r)
  62.     register hash_t r; int match_length;
  63. {
  64.     register hash_t p = r & WINMASK;
  65.     register int m;
  66. #ifdef ALLOW_MISALIGN
  67.     register us_t lastbyte;
  68. #else
  69.     register uc_t lastbyte;
  70. #endif
  71.     register uc_t  *key FIX_SI, *pattern FIX_DI;
  72.     int     chain_count = chain_length;
  73.  
  74. #ifdef GATHER_STAT
  75.     node_matches++;
  76. #endif
  77.     key = text_buf + (r & WINMASK) + LOOKAHEAD;
  78.     r -= MAXDIST;           /* `r' is now a "barrier value" */
  79.  
  80.     for(;;) {
  81.         lastbyte = FETCH(key, match_length);
  82.         do {
  83.             if(chain_count <= 0)
  84.                 /* chain length exceeded, simple return */
  85.                 return match_length;
  86.  
  87.             pattern = text_buf + match_length + LOOKAHEAD;
  88.  
  89.             do {
  90.                 if ((p = next[p]) < r)
  91.                     return match_length;
  92.             } while (FETCH(pattern, p &= WINMASK) != lastbyte);
  93.  
  94.             chain_count--;  /* successful lastbyte match, cost = 1 */
  95.             pattern = text_buf + p + LOOKAHEAD;
  96.  
  97. #ifdef GATHER_STAT
  98.         node_compares++;
  99. #endif
  100.  
  101. #ifdef ALLOW_MISALIGN
  102.             for (m = -LOOKAHEAD;
  103.             *(unsigned*)&key[m] == *(unsigned*)&pattern[m] &&
  104.                 (m += sizeof(unsigned)) < 0;);
  105. #ifndef INT_16_BITS
  106.         /* Hope that sizeof(int) > 2 ==> sizeof(int) > sizeof(short) */
  107.             if (m < 0 && *(us_t*)&key[m] == *(us_t*)&pattern[m])
  108.                 m += sizeof(us_t);
  109. #endif
  110. #ifdef BIGSHORTS
  111.             while
  112. #else
  113.             if
  114. #endif
  115.                 (m < 0 && key[m] == pattern[m])
  116.                     ++m;
  117. #else
  118.             for (m = -LOOKAHEAD; key[m] == pattern[m] && ++m < 0;);
  119. #endif
  120.         } while (m < match_length);
  121.  
  122.         match_position = p;     /* remember new results */
  123.         if (m == 0)
  124.             return 0;
  125.         match_length = m;
  126.  
  127. #ifdef GATHER_STAT
  128.         node_prolongations++;
  129. #endif
  130.         chain_count -= 2;       /* yet another match found, cost = 2 */
  131.     }
  132. }
  133.  
  134. hash_t
  135. rehash(r)
  136. hash_t r;
  137. {
  138.   unsigned i = 0;
  139.   r += WINSIZE;
  140.   do {
  141.     /* process links; zero must remain zero */
  142.     if (next[i] && (next[i] += WINSIZE) > r) {
  143.         next[i] = 0;
  144.     }
  145.   } while(i++ != WINSIZE - 1);
  146.   i = 0;
  147.   do {
  148.     /* process the hash table itself; zero must remain zero */
  149.     if (hashtab[i] && (hashtab[i] += WINSIZE) > r)
  150.         hashtab[i] = 0;
  151.   } while (i++ != hash_size - 1);
  152.   return r;
  153. }
  154.