home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / FREEZE-2.ZIP / lz.h < prev    next >
C/C++ Source or Header  |  1992-07-18  |  4KB  |  181 lines
  1. extern void InitTree();
  2.  
  3. #ifndef BITS
  4. #define BITS    14      /* for 16-bits machines */
  5. #endif
  6.  
  7. #if BITS < 13
  8. #undef BITS
  9. #define BITS    13      /* 1:1 hash */
  10. #endif
  11.  
  12. #if BITS > 16
  13. #undef BITS
  14. #define BITS    16      /* 128K hash table, if sizeof(us_t) == 2 */
  15. #endif
  16.  
  17. /* The following hash-function isn't optimal but it is very fast:
  18.  
  19.     HASH =      ((first + (second << LEN0) +
  20.             (third << LEN1)) & ((1L << BITS) - 1);
  21.  
  22.   The difference of LENs is no more than one bit.
  23. */
  24.  
  25. #define LEN0    ((BITS-8)/2)
  26. #define LEN1    (BITS-8)
  27.  
  28. #define NIL     N2
  29.  
  30. #if defined(M_XENIX) && !defined(M_I386) && (BITS > 14)
  31. #define __XENIX__
  32. #endif
  33.  
  34. /* `array_size' is the size of array `next', which contains
  35.     the heads of linked lists and the references to
  36.     next members of these lists.
  37. */
  38.  
  39. #define array_size      (N2 + 1 + (1L << BITS))
  40.  
  41. extern hash_t prev[];
  42. extern us_t      match_position, match_length, chain_length;
  43.  
  44. #ifndef __XENIX__
  45. #define nextof(i)       next[i]
  46.  
  47. #ifdef __TURBOC__
  48. extern us_t huge * next;
  49. #else   /* __TURBOC__ */
  50. extern us_t next[];
  51. #endif  /* __TURBOC__ */
  52.  
  53. #else   /* __XENIX__ */
  54.  
  55. /* We divide the array `next' in `parts' which fit into 286's segment */
  56. /* There may be 2 or 3 parts, because BITS <= 16 now */
  57.  
  58. #define parts (array_size/32768L + 1)
  59. #define nextof(i)       next[(i) >> 15][(i) & 0x7fff]
  60. #if parts == 2
  61. extern us_t next0[], next1[];
  62. #else
  63. extern us_t next0[], next1[], next2[];
  64. #endif  /* parts */
  65.  
  66. extern us_t *next[];
  67. #endif  /* __XENIX__ */
  68.  
  69. /* Some defines to eliminate function-call overhead */
  70.  
  71. /* Deleting of a node `n' from a linked list */
  72.  
  73. #define DeleteNode(n) \
  74. {\
  75.        nextof(prev[n]) = NIL;\
  76.        prev[n] = NIL;\
  77. }
  78.  
  79. /* Inserting of a node `r' into hashed linked list: `r' becomes
  80.     the head of list.
  81. */
  82.  
  83. #define InsertNode(r)\
  84. {\
  85.     register hash_t p; register us_t first_son;\
  86.     register uc_t  *key;\
  87.     key = &text_buf[r];\
  88.     p = N2 + 1 + (((hash_t)key[0] + ((hash_t)key[1] << LEN0) +\
  89.             ((hash_t)key[2] << LEN1)) & ((1L << BITS) - 1));\
  90.     first_son = nextof(p);\
  91.     nextof(r) = first_son;\
  92.     nextof(p) = r;\
  93.     prev[r] = p;\
  94.     prev[first_son] = r;\
  95. }
  96.  
  97. /* This routine inputs the char from stdin and does some other
  98.     actions depending of this char's presence.
  99. */
  100.  
  101. #define Next_Char(N,F)\
  102. if ((c = getchar()) != EOF) {\
  103.     text_buf[s] = c;\
  104.     if (s < F - 1)\
  105.         text_buf[s + N] = c;\
  106.     s = (s + 1) & (N - 1);\
  107.     r = (r + 1) & (N - 1);\
  108.     InsertNode(r);\
  109.     in_count++;\
  110. } else {\
  111.     s = (s + 1) & (N - 1);\
  112.     r = (r + 1) & (N - 1);\
  113.     if (--len) InsertNode(r);\
  114. }
  115.  
  116. #if defined(__GNUC__)
  117. #if defined(__i386__)
  118. /* Optimizer cannot allocate these registers correctly :( (v1.39) */
  119. #define FIX_SI  asm("si")
  120. #define FIX_DI  asm("di")
  121. #else
  122.  
  123. /* GNU-style register allocations for other processors are welcome! */
  124.  
  125. #define FIX_SI
  126. #define FIX_DI
  127. #endif
  128. #else
  129.  
  130. /* Dummy defines for non-GNU compilers */
  131.  
  132. #define FIX_SI
  133. #define FIX_DI
  134. #endif
  135.  
  136. #ifndef DO_INLINE
  137.  
  138. /* This statement is due to ideas of Boyer and Moore: */
  139. /* Is somewhere an optimizing compiler which can vectorize this? ;-) */
  140.  
  141. #define MATCHING for (m = match_length; m >= 0 && key[m] == pattern[m]; m--)
  142. #define NOT_YET (m >= 0)
  143.  
  144. #else
  145.  
  146. /* Hope this function will be intrinsic (Microsoft C).
  147.    Ideally this memcmp should be right-to-left, but this works
  148.    fast enough.
  149. */
  150. #define MATCHING m = memcmp(key, pattern, match_length + 1)
  151. #define NOT_YET (m != 0)
  152.  
  153. #endif
  154.  
  155. #define CHAIN_THRESHOLD (F2 * 3)
  156.  
  157. #ifdef  FAST
  158. /* Simple inline replacement for get_next_match; they match
  159. literally except return --> goto quote(leave)l. No obfuscations !! */
  160.  
  161. #ifdef __STDC__
  162. #define LEAVE(num) leave##num
  163. #else
  164. #define quote(x)x
  165. #define LEAVE(num) quote(leave)num
  166. #endif
  167.  
  168. #define Get_Next_Match(r,l) {register us_t p=r;register int m;\
  169. register uc_t *key FIX_SI, *pattern FIX_DI;int chain_count=chain_length;\
  170. key=text_buf+r;do{ do{ if((p=nextof(p))==NIL||(greedy &&\
  171. !chain_count--))goto LEAVE(l);pattern=text_buf+p;MATCHING;}while NOT_YET;\
  172. for(m=match_length;++m<F2&&key[m]==pattern[m];);\
  173. match_length=m;match_position=((r-p)&(N2-1))-1;}while(m<F2);\
  174. nextof(prev[p])=nextof(p);prev[nextof(p)]=prev[p];prev[p]=NIL;LEAVE(l):;}
  175.  
  176. #else
  177.  
  178. #define Get_Next_Match(r,l)     get_next_match(r)
  179.  
  180. #endif
  181.