home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / FREEZE-2.ZIP / lz.c < prev    next >
C/C++ Source or Header  |  1992-07-18  |  4KB  |  139 lines
  1. #include "freeze.h"
  2. #include "lz.h"
  3.  
  4. /*----------------------------------------------------------------------*/
  5. /*                                                                      */
  6. /*                          LZSS ENCODING                               */
  7. /*                                                                      */
  8. /*----------------------------------------------------------------------*/
  9.  
  10. uc_t    text_buf[N2 + F2 - 1];          /* cyclic buffer with an overlay */
  11. us_t    match_position, match_length;   /* current characteristics of a
  12.                         matched pattern */
  13. us_t    chain_length;                   /* max_chain_length ==
  14.                         CHAIN_THRESHOLD / greedy */
  15.  
  16.  
  17. /*      next[N+1..] is used as hash table,
  18.     the rest of next is a link down,
  19.     prev is a link up.
  20. */
  21.  
  22. hash_t             prev[N2 + 1];
  23.  
  24. #ifndef __XENIX__
  25. #ifdef __TURBOC__
  26. us_t huge * next = (us_t huge *) NULL;
  27. #else  /* __TURBOC__ */
  28. us_t next[array_size];       /* a VERY large array :-) */
  29. #endif /* __TURBOC__ */
  30. #else  /* __XENIX__ */
  31. #if parts == 2
  32. us_t next0[32768L], next1[8193];
  33. #else
  34. us_t next0[32768L], next1[32768L], next2[8193];
  35. #endif  /* parts */
  36.  
  37. /* A list of `next's parts */
  38.  
  39. us_t *next[parts] = {
  40. next0, next1
  41. #if parts != 2          /* was: parts > 2. Doesn't work on X286 cpp */
  42. ,next2
  43. #endif
  44. };
  45. #endif  /* __XENIX__ */
  46.  
  47. #ifdef GATHER_STAT
  48. long node_steps, node_matches;
  49. #endif  /* GATHER_STAT */
  50.  
  51. /* Initialize the data structures and allocate memory, if needed.
  52.     Although there is no more trees in the LZ algorithm
  53.     implementation, routine name is kept intact :-)
  54. */
  55.  
  56. void InitTree ()
  57. {
  58.     hash_t i;
  59. #ifdef GATHER_STAT
  60.     node_steps = node_matches = 0;
  61. #endif  /* GATHER_STAT */
  62.  
  63. #ifdef __TURBOC__
  64.     if (!next && (next = (us_t huge *) farmalloc(
  65.         (ul_t)array_size * sizeof(us_t))) == NULL) {
  66.  
  67.         fprintf(stderr, "Not enough memory (%luK wanted)\n",
  68.             (ul_t)array_size * sizeof(us_t) / 1024);
  69.         exit(3);
  70.     }
  71. #endif  /* __TURBOC__ */
  72.  
  73.     for (i = N2 + 1; i < array_size; i++ )
  74.         nextof(i) = NIL;
  75.     for (i = 0; i < sizeof(prev)/sizeof(*prev); i++ )
  76.         prev[i] = NIL;
  77.     chain_length = greedy ? CHAIN_THRESHOLD / greedy : 0;
  78. }
  79.  
  80. /* Get the longest (longer than `match_length' when entering in subroutine)
  81.     nearest match of the string beginning in text_buf[r]
  82.     to the cyclic buffer. Result (length & position) is returned
  83.     in correspondent global variables (`match_length' &
  84.     `match_position'). Unchanged `match_length' denotes failure.
  85. */
  86.  
  87. #ifndef FAST
  88. void get_next_match (r)
  89.     us_t r;
  90. {
  91.     register us_t p = r;
  92.     register int m;
  93.     register uc_t  *key FIX_SI, *pattern FIX_DI;
  94.     int     chain_count = chain_length;
  95. #ifdef GATHER_STAT
  96.     node_matches++;
  97. #endif
  98.     key = text_buf + r;
  99.     do {
  100.         do {
  101.             /* From ZIP 1.0 by J.-L. Gailly et al. */
  102.  
  103.             if ((p = nextof(p)) == NIL ||
  104.                 (greedy && !chain_count--))
  105.                 return;
  106.  
  107.             pattern = text_buf + p;
  108.  
  109.             MATCHING;
  110.  
  111.         } while NOT_YET;
  112.  
  113. #ifdef GATHER_STAT
  114.         node_steps++;
  115. #endif
  116.  
  117.         for (m = match_length;
  118.             ++m < F2 && key[m] == pattern[m]; );
  119.  
  120.         match_length = m;
  121.         match_position = ((r - p) & (N2 - 1)) - 1;
  122.     } while (m < F2);
  123.  
  124. /* There are two equal F-char sequences, the oldest one must be
  125.     deleted from the list.
  126. */
  127.  
  128.  
  129. #ifdef DEBUG
  130.     if (verbose)
  131.         fprintf(stderr, "Replacing node: %d -> %d\n", p, r);
  132. #endif
  133.     nextof(prev[p]) = nextof(p);
  134.     prev[nextof(p)] = prev[p];
  135.     prev[p] = NIL;  /* remove p, it is further than r */
  136.     return;
  137. }
  138. #endif
  139.