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