home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume25 / freeze / part02 / lz.h < prev    next >
C/C++ Source or Header  |  1991-11-04  |  4KB  |  190 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 > 21
  13. #undef BITS
  14. #define BITS    21      /* 4 MB hash table, if sizeof(u_short) == 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(I_286) && (BITS > 14)
  31. #define __XENIX__
  32. #if BITS > 18
  33. #undef BITS
  34. #define BITS 18
  35. #endif
  36. #endif
  37.  
  38. /* `array_size' is the size of array `next', which contains
  39.     the heads of linked lists and the references to
  40.     next members of these lists.
  41. */
  42.  
  43. #define array_size      (N2 + 1 + (1L << BITS))
  44.  
  45. extern hash_t prev[];
  46.  
  47. #ifndef __XENIX__
  48. #define nextof(i)       next[i]
  49.  
  50. #ifdef __TURBOC__
  51. extern u_short huge * next;
  52. #else   /* __TURBOC__ */
  53. extern u_short next[];
  54. #endif  /* __TURBOC__ */
  55.  
  56. #else   /* __XENIX__ */
  57.  
  58. /* We divide the array `next' in `parts' which fit into 286's segment */
  59.  
  60. #define parts (array_size/32768 + 1)
  61. #define nextof(i)       next[(i) >> 15][(i) & 0x7fff]
  62. #if parts == 2
  63. extern u_short next0[], next1[];
  64. #else
  65. #    if parts == 3
  66. extern u_short next0[], next1[], next2[];
  67. #       else
  68. #        if parts == 5
  69. extern u_short next0[], next1[], next2[], next3[], next4[];
  70. #        else
  71. extern u_short next0[], next1[], next2[], next3[], next4[],
  72.     next5[], next6[], next7[], next8[];
  73. #        endif
  74. #    endif
  75. #endif  /* parts */
  76.  
  77. extern u_short *next[];
  78. #endif  /* __XENIX__ */
  79.  
  80. /* Some defines to eliminate function-call overhead */
  81.  
  82. /* Deleting of a node `n' from a linked list */
  83.  
  84. #define DeleteNode(n) \
  85. {\
  86.        nextof(prev[n]) = NIL;\
  87.        prev[n] = NIL;\
  88. }
  89.  
  90. /* Inserting of a node `r' into hashed linked list: `r' becomes
  91.     the head of list.
  92. */
  93.  
  94. #define InsertNode(r)\
  95. {\
  96.     register hash_t p; register u_short first_son;\
  97.     register uchar  *key;\
  98.     key = &text_buf[r];\
  99.     p = N2 + 1 + (((hash_t)key[0] + ((hash_t)key[1] << LEN0) +\
  100.             ((hash_t)key[2] << LEN1)) & ((1L << BITS) - 1));\
  101.     first_son = nextof(p);\
  102.     nextof(r) = first_son;\
  103.     nextof(p) = r;\
  104.     prev[r] = p;\
  105.     prev[first_son] = r;\
  106. }
  107.  
  108. /* This routine inputs the char from stdin and does some other
  109.     actions depending of this char's presence.
  110. */
  111.  
  112. #define Next_Char(N,F)\
  113. if ((c = getchar()) != EOF) {\
  114.     text_buf[s] = c;\
  115.     if (s < F - 1)\
  116.         text_buf[s + N] = c;\
  117.     s = (s + 1) & (N - 1);\
  118.     r = (r + 1) & (N - 1);\
  119.     InsertNode(r);\
  120.     in_count++;\
  121. } else {\
  122.     s = (s + 1) & (N - 1);\
  123.     r = (r + 1) & (N - 1);\
  124.     if (--len) InsertNode(r);\
  125. }
  126.  
  127. #if defined(__GNUC__)
  128. #if defined(__i386__)
  129. /* Optimizer cannot allocate these registers correctly :( (v1.39) */
  130. #define FIX_SI  asm("si")
  131. #define FIX_DI  asm("di")
  132. #else
  133.  
  134. /* GNU-style register allocations for other processors are welcome! */
  135.  
  136. #define FIX_SI
  137. #define FIX_DI
  138. #endif
  139. #else
  140.  
  141. /* Dummy defines for non-GNU compilers */
  142.  
  143. #define FIX_SI
  144. #define FIX_DI
  145. #endif
  146.  
  147. #ifndef DO_INLINE
  148.  
  149. /* This statement is due to ideas of Boyer and Moore: */
  150. /* Is somewhere an optimizing compiler which can vectorize this? ;-) */
  151.  
  152. #define MATCHING for (m = match_length; m >= 0 && key[m] == pattern[m]; m--)
  153. #define NOT_YET (m >= 0)
  154.  
  155. #else
  156.  
  157. /* Hope this function will be intrinsic (Microsoft C).
  158.    Ideally this memcmp should be right-to-left, but this works
  159.    fast enough.
  160. */
  161. #define MATCHING m = memcmp(key, pattern, match_length + 1)
  162. #define NOT_YET (m != 0)
  163.  
  164. #endif
  165.  
  166. #ifdef  FAST
  167. /* Simple inline replacement for get_next_match; they match
  168. literally except return --> goto quote(leave)l. No obfuscations !! */
  169.  
  170. #ifdef __STDC__
  171. #define LEAVE(num) leave##num
  172. #else
  173. #define LEAVE(num) leave/**/num
  174. #endif
  175.  
  176. #define Get_Next_Match(r,l) {register u_short p=r;register int m;\
  177. register uchar *key FIX_SI, *pattern FIX_DI;key=text_buf+r;\
  178. match_length=0;do{ do{ if((p=nextof(p))==NIL)goto LEAVE(l);\
  179. pattern=text_buf+p;MATCHING;}while NOT_YET;\
  180. for(m=match_length;++m<F2&&key[m]==pattern[m];);   \
  181. match_length=m;match_position=((r-p)&(N2-1))-1;}while(m<F2);\
  182. nextof(prev[p])=nextof(p);prev[nextof(p)]=prev[p];prev[p]=NIL;   \
  183. LEAVE(l):;}
  184.  
  185. #else
  186.  
  187. #define Get_Next_Match(r,l)     get_next_match(r)
  188.  
  189. #endif
  190.