home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / sgrep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  65.5 KB  |  2,136 lines
  1. /* Copyright (c) 1994 Sun Wu, Udi Manber, Burra Gopal.  All Rights Reserved. */
  2. #include <stdio.h>
  3. #include <ctype.h>
  4. #include "agrep.h"
  5. #undef    MAXSYM
  6. #define MAXSYM  256
  7. #define MAXMEMBER 8192
  8. #define    CHARTYPE    unsigned char
  9. #undef    MaxError /* don't use agrep.h definition */
  10. #define MaxError 20
  11. #define MAXPATT 256
  12. #undef    MAXLINE
  13. #define MAXLINE 1024
  14. #undef    MAXNAME
  15. #define MAXNAME 256
  16. #undef    MaxCan    /* don't use agrep.h definition */
  17. #define MaxCan  2048
  18. #define BLOCKSIZE    16384
  19. #define MAX_SHIFT_2  4096
  20. #undef    ON
  21. #define ON      1
  22. #undef    OFF
  23. #define OFF    0
  24. #define LOG_ASCII 8
  25. #define LOG_DNA  3
  26. #define MAXMEMBER_1 65536
  27. #define LONG_EXAC  20
  28. #define LONG_APPX  24
  29. #define W_DELIM    128
  30. #include <sys/time.h>
  31.  
  32. extern int tuncompressible();
  33. extern int quick_tcompress();
  34. extern int quick_tuncompress();
  35.  
  36. extern int DELIMITER, OUTTAIL;
  37. extern int D_length, tc_D_length;
  38. extern unsigned char D_pattern[MaxDelimit], tc_D_pattern[MaxDelimit *2];
  39. extern int LIMITOUTPUT, INVERSE;
  40. extern int CurrentByteOffset;
  41. extern int BYTECOUNT;
  42. extern int CONSTANT, COUNT, FNAME, SILENT, FILENAMEONLY, prev_num_of_matched, num_of_matched;
  43. extern int DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  44.          p_size > 16  */
  45. extern WORDBOUND, WHOLELINE, NOUPPER;
  46. extern unsigned char CurrentFileName[],  Progname[]; 
  47. extern unsigned Mask[];
  48. extern unsigned endposition;
  49. extern int agrep_inlen;
  50. extern CHARTYPE *agrep_inbuffer;
  51. extern int agrep_initialfd;
  52. extern FILE *agrep_finalfp;
  53. extern int agrep_outpointer;
  54. extern int agrep_outlen;
  55. extern CHARTYPE * agrep_outbuffer;
  56.  
  57. extern int NEW_FILE, POST_FILTER;
  58.  
  59. extern int EXITONERROR;
  60. extern int errno;
  61. extern int TCOMPRESSED;
  62. extern int EASYSEARCH;
  63. extern char FREQ_FILE[MAX_LINE_LEN], HASH_FILE[MAX_LINE_LEN], STRING_FILE[MAX_LINE_LEN];
  64.  
  65. #if    MEASURE_TIMES
  66. /* timing variables */
  67. extern int OUTFILTER_ms;
  68. extern int FILTERALGO_ms;
  69. extern int INFILTER_ms;
  70. #endif    /*MEASURE_TIMES*/
  71.  
  72. unsigned char BSize;                /* log_c m   */
  73. unsigned char char_map[MAXSYM];
  74.  
  75. /* data area */
  76. int shift_1;
  77. CHARTYPE SHIFT[MAXSYM];
  78. CHARTYPE MEMBER[MAXMEMBER];
  79. CHARTYPE pat[MAXPATT];
  80. unsigned Hashmask;
  81. char MEMBER_1[MAXMEMBER_1];
  82. CHARTYPE TR[MAXSYM];
  83.  
  84. /*
  85.  * General idea behind output processing with delimiters, inverse, compression, etc.
  86.  * CAUTION: In compressed files, we can search ONLY for simple patterns or their ;,.
  87.  * Attempts to search for complex patterns / with errors might lead to spurious matches.
  88.  * 1. Once we find the match, go back and forward to get the delimiters that surround
  89.  *    the matched region.
  90.  * 2. If it is a compressed file, verify that the match is "real" (compressed files
  91.  *    can have pseudo matches hence this filtering step is required).
  92.  * 3. Increment num_of_matched.
  93.  * 4. Process some output options which print stuff before the matched region is
  94.  *    printed.
  95.  * 5. If there is compression, decomress and output the matched region. Otherwise
  96.  *    just output it as is. Remember, from step (1) we know the matched region.
  97.  * 6. If inverse is set, then we must keep track of the end of the last matched region
  98.  *    in the variable lastout. When there is a match, we must print everything from
  99.  *    lastout to the beginning of the current matched region (curtextbegin) and then
  100.  *    update lastout to point to the end of the current matched region (curtextend).
  101.  *    ALSO: if we exit from the main loops, we must output everything from the end
  102.  *    of the last matched region to the end of the input buffer.
  103.  * 7. Delimiter handling in complex patterns is different: there the search is done
  104.  *    for a boolean and of the delimiter pattern and the actual pattern.
  105.  */
  106.  
  107. /* skips over escaped characters */
  108. unsigned char *
  109. mystrchr(s, c)
  110. unsigned char *s;
  111. int c;
  112. {
  113.     unsigned char    *t = s;
  114.  
  115.     while (*t) {
  116.         if (*t == '\\') t++;
  117.         else if (c == *t) return t;
  118.         t ++;
  119.     }
  120.     return NULL;
  121. }
  122.  
  123. char_tr(pat, m)
  124. unsigned char *pat;
  125. int *m;
  126. {
  127.     int i;
  128.     unsigned char temp[MAXPATT];
  129.     for(i=0; i<MAXSYM; i++) TR[i] = i;
  130.     if(NOUPPER) {
  131.         for(i=0; i<MAXSYM; i++)
  132.             if (isupper(i)) TR[i] = TR[tolower(i)];
  133.         /* for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A'; */
  134.     }
  135.     /*
  136.     if(WORDBOUND) {
  137.         for(i=0; i<MAXSYM; i++) {
  138.             if(!isalnum(i)) TR[i] = W_DELIM;removed by Udi.
  139.             we don't use the trick of making the boundary W_delim anymore.
  140.             It's too buggy otherwise and it's not necessary.
  141.         }
  142.     }
  143.     removed by bg 11/8/94
  144.     */
  145.     if(WHOLELINE) {
  146.         memcpy(temp, pat, *m);
  147.         pat[0] = '\n';
  148.         memcpy(pat+1, temp, *m);
  149.         pat[*m+1] = '\n';
  150.         pat[*m+2] = 0;
  151.         *m = *m + 2;
  152.     }
  153. }
  154.  
  155. int
  156. sgrep(in_pat, in_m, fd, D, samepattern)
  157. CHARTYPE *in_pat;  
  158. int fd, in_m, D;
  159. {
  160.     CHARTYPE patbuf[MAXLINE];
  161.     CHARTYPE *pat = patbuf;
  162.     int m = in_m;
  163.     CHARTYPE *text; /* input text stream */
  164.     int offset = 2*MAXLINE;
  165.     int buf_end, num_read, i, start, end, residue = 0;
  166.     int first_time = 1;
  167.     CHARTYPE *oldpat = pat;
  168.     int k, j, oldm = m;
  169.     static CHARTYPE newpat[MAXLINE];    /* holds compressed version */
  170.     static int newm;
  171.     static struct timeval initt, finalt;
  172.     CHARTYPE *tempbuf;
  173.     int    oldCurrentByteOffset;
  174.  
  175.     strncpy(pat, in_pat, MAXLINE);
  176.     pat[MAXLINE-1] = '\0';
  177.  
  178. #define PROCESS_PATTERN \
  179.     if (!CONSTANT) {\
  180.         if( (pat[0] == '^') || (pat[0] == '$') ) pat[0] = '\n';\
  181.         if ((m>1) && (pat[m-2] != '\\') && ((pat[m-1] == '^') || (pat[m-1] == '$'))) pat[m-1] = '\n';\
  182.     }\
  183.     /* whether constant or not, interpret the escape character */\
  184.     for (k=0; k<m; k++) {\
  185.         if (pat[k] == '\\') {\
  186.             for (j=k; j<m; j++)\
  187.                 pat[j] = pat[j+1]; /* including '\0' */\
  188.             m--;\
  189.         }\
  190.     }\
  191.     char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */\
  192.     if(m >= MAXPATT) {\
  193.         fprintf(stderr, "%s: pattern too long (has > %d chars)\n", Progname, MAXPATT);\
  194.         if (!EXITONERROR) {\
  195.             errno = 2;\
  196.             return -1;\
  197.         }\
  198.         else exit(2);\
  199.     }\
  200.     if(D == 0) {\
  201.         if(m > LONG_EXAC) m_preprocess(pat);\
  202.         else prep_bm(pat, m);\
  203.     }\
  204.     else if (DNA) prep4(pat, m);\
  205.     else     if(m >= LONG_APPX) am_preprocess(pat);\
  206.     else {\
  207.         prep(pat, m, D);\
  208.         initmask(pat, Mask, m, 0, &endposition);\
  209.     }
  210.  
  211. #if    AGREP_POINTER
  212.     if (fd != -1) {
  213. #endif    /*AGREP_POINTER*/
  214.         alloc_buf(fd, &text, 2*BLOCKSIZE+2*MAXLINE+MAXPATT);
  215.         text[offset-1] = '\n';  /* initial case */
  216.         for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  217.         start = offset;   
  218.         if(WHOLELINE) {
  219.             start--;
  220.             CurrentByteOffset --;
  221.         }
  222.  
  223.         while( (num_read = fill_buf(fd, text+offset, 2*BLOCKSIZE)) > 0) 
  224.         {
  225.             buf_end = end = offset + num_read -1 ;
  226.             oldCurrentByteOffset = CurrentByteOffset;
  227.  
  228.             if (first_time) {
  229.                 if ((TCOMPRESSED == ON) && tuncompressible(text+offset, num_read)) {
  230.                     EASYSEARCH = text[offset+SIGNATURE_LEN-1];
  231.                     start += SIGNATURE_LEN;
  232.                     CurrentByteOffset += SIGNATURE_LEN;
  233.                     if (!EASYSEARCH) {
  234.                         fprintf(stderr, "not compressed for easy-search: can miss some matches in: %s\n", CurrentFileName);
  235.                     }
  236. #if    MEASURE_TIMES
  237.                     gettimeofday(&initt, NULL);
  238. #endif    /*MEASURE_TIMES*/
  239.                     if (samepattern || ((newm = quick_tcompress(FREQ_FILE, HASH_FILE, pat, m, newpat, MAXLINE-8, EASYSEARCH)) > 0)) {
  240.                         oldm = m;
  241.                         oldpat = pat;
  242.                         m = newm;
  243.                         pat = newpat;
  244.                     }
  245. #if    MEASURE_TIMES
  246.                     gettimeofday(&finalt, NULL);
  247.                     INFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  248. #endif    /*MEASURE_TIMES*/
  249.                 }
  250.                 else TCOMPRESSED = OFF;
  251.  
  252.                 PROCESS_PATTERN    /* must be AFTER we know that it is a compressed pattern... */
  253.  
  254.                 for(i=1; i<=m; i++) text[2*BLOCKSIZE+offset+i] = pat[m-1];
  255.                 /* to make sure the skip loop in bm() won't go out of bound in later iterations */
  256.                 first_time = 0;
  257.             }
  258.  
  259.                         if (!DELIMITER) {
  260.                                 while ((text[end]  != '\n') && (end > offset)) end--;
  261.                                 text[start-1] = '\n';
  262.                         }
  263.                         else {
  264.                                 unsigned char *newbuf = text + end + 1;
  265.                                 newbuf = backward_delimiter(newbuf, text+offset, D_pattern, D_length, OUTTAIL);        /* see agrep.c/'d' */
  266.                 if (newbuf < text+offset+D_length) newbuf = text + end + 1;
  267.                                 end = newbuf - text - 1;
  268.                                 memcpy(text+start-D_length, D_pattern, D_length);
  269.                         }
  270.             residue = buf_end - end + 1 ;
  271.  
  272.             /* SGREP_PROCESS */
  273.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  274.             if(D==0)  {
  275.                 if(m > LONG_EXAC) {
  276.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  277.                         free_buf(fd, text);
  278.                         return -1;
  279.                     }
  280.                 }
  281.                 else {
  282.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  283.                         free_buf(fd, text);
  284.                         return -1;
  285.                     }
  286.                 }
  287.             }
  288.             else {
  289.                 if(DNA) {
  290.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  291.                         free_buf(fd, text);
  292.                         return -1;
  293.                     }
  294.                 }
  295.                 else {
  296.                     if(m >= LONG_APPX) {
  297.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  298.                             free_buf(fd, text);
  299.                             return -1;
  300.                         }
  301.                     }
  302.                     else {
  303.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  304.                             free_buf(fd, text);
  305.                             return -1;
  306.                         }
  307.                     }
  308.                 }
  309.             }
  310.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {
  311.                 if (agrep_finalfp != NULL)
  312.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  313.                 else {
  314.                     int outindex;
  315.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  316.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  317.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  318.                     }
  319.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  320.                         OUTPUT_OVERFLOW;
  321.                         free_buf(fd, text);
  322.                         return -1;
  323.                     }
  324.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  325.                     agrep_outpointer += outindex;
  326.                 }
  327.                 free_buf(fd, text);
  328.                 NEW_FILE = OFF;
  329.                 return 0; 
  330.             }
  331.  
  332.             CurrentByteOffset = oldCurrentByteOffset + end - start + 1;    /* for a new iteration: avoid complicated calculations below */
  333.             start = offset - residue ;
  334.             if(start < MAXLINE) {
  335.                 start = MAXLINE; 
  336.             }
  337.             strncpy(text+start, text+end, residue);
  338.             start++;
  339.             if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) {
  340.                 free_buf(fd, text);
  341.                 return 0;    /* done */
  342.             }
  343.         } /* end of while(num_read = ...) */
  344.                 if (!DELIMITER) {
  345.                         text[start-1] = '\n';
  346.                         text[offset] = '\n';
  347.                 }
  348.                 else {
  349.                         if (start > D_length) memcpy(text+start-D_length, D_pattern, D_length);
  350.                         memcpy(text+offset, D_pattern, D_length);
  351.                 }
  352.                 end = start + residue;
  353.                 if(residue > 1) {
  354.             /* SGREP_PROCESS */
  355.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  356.             if(D==0)  {
  357.                 if(m > LONG_EXAC) {
  358.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  359.                         free_buf(fd, text);
  360.                         return -1;
  361.                     }
  362.                 }
  363.                 else {
  364.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  365.                         free_buf(fd, text);
  366.                         return -1;
  367.                     }
  368.                 }
  369.             }
  370.             else {
  371.                 if(DNA) {
  372.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  373.                         free_buf(fd, text);
  374.                         return -1;
  375.                     }
  376.                 }
  377.                 else {
  378.                     if(m >= LONG_APPX) {
  379.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  380.                             free_buf(fd, text);
  381.                             return -1;
  382.                         }
  383.                     }
  384.                     else {
  385.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  386.                             free_buf(fd, text);
  387.                             return -1;
  388.                         }
  389.                     }
  390.                 }
  391.             }
  392.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {
  393.                 if (agrep_finalfp != NULL)
  394.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  395.                 else {
  396.                     int outindex;
  397.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  398.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  399.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  400.                     }
  401.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  402.                         OUTPUT_OVERFLOW;
  403.                         free_buf(fd, text);
  404.                         return -1;
  405.                     }
  406.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  407.                     agrep_outpointer += outindex;
  408.                 }
  409.                 free_buf(fd, text);
  410.                 NEW_FILE = OFF;
  411.                 return 0; 
  412.             }
  413.                 }
  414.         free_buf(fd, text);
  415.         return 0;
  416. #if    AGREP_POINTER
  417.     }
  418.     else {    /* as if only one iteration of the while-loop and offset = 0 */
  419.         tempbuf = (CHARTYPE*)malloc(m);
  420.         text = (CHARTYPE *)agrep_inbuffer;
  421.         num_read = agrep_inlen;
  422.         start = 1;
  423.         buf_end = end = num_read - 1;
  424.         if (WHOLELINE) {
  425.             start --;
  426.             CurrentByteOffset --;
  427.         }
  428.  
  429.         if ((TCOMPRESSED == ON) && tuncompressible(text+1, num_read)) {
  430.             EASYSEARCH = text[offset+SIGNATURE_LEN-1];
  431.             start += SIGNATURE_LEN;
  432.             CurrentByteOffset += SIGNATURE_LEN;
  433.             if (!EASYSEARCH) {
  434.                 fprintf(stderr, "not compressed for easy-search: can miss some matches in: %s\n", CurrentFileName);
  435.             }
  436. #if    MEASURE_TIMES
  437.             gettimeofday(&initt, NULL);
  438. #endif    /*MEASURE_TIMES*/
  439.             if (samepattern || ((newm = quick_tcompress(FREQ_FILE, HASH_FILE, pat, m, newpat, MAXLINE-8, EASYSEARCH)) > 0)) {
  440.                 oldm = m;
  441.                 oldpat = pat;
  442.                 m = newm;
  443.                 pat = newpat;
  444.             }
  445. #if    MEASURE_TIMES
  446.             gettimeofday(&finalt, NULL);
  447.             INFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  448. #endif    /*MEASURE_TIMES*/
  449.         }
  450.         else TCOMPRESSED = OFF;
  451.  
  452.         PROCESS_PATTERN    /* must be after we know whether it is compressed or not */
  453.  
  454.         memcpy(tempbuf, text+end+1, m);    /* save portion being overwritten */
  455.         for(i=1; i<=m; i++) text[end+i] = pat[m-1];
  456.         /* to make sure the skip loop in bm() won't go out of bound in later iterations */
  457.  
  458.                         if (!DELIMITER)
  459.                                 while(text[end]  != '\n' && end > 1) end--;
  460.                         else {
  461.                                 unsigned char *newbuf = text + end + 1;
  462.                                 newbuf = backward_delimiter(newbuf, text, D_pattern, D_length, OUTTAIL);        /* see agrep.c/'d' */
  463.                 if (newbuf < text+offset+D_length) newbuf = text + end + 1;
  464.                                 end = newbuf - text - 1;
  465.                         }
  466.                         /* text[0] = text[end] = r_newline; : the user must ensure that the delimiter is there at text[0] and occurs somewhere before text[end ] */
  467.  
  468.             /* An exact copy of the above SGREP_PROCESS */
  469.             /* No harm in sending a few extra parameters even if they are unused: they are not accessed in monkey*()s */
  470.             if(D==0)  {
  471.                 if(m > LONG_EXAC) {
  472.                     if (-1 == monkey(pat, m, text+start, text+end, oldpat, oldm)) {
  473.                         free_buf(fd, text);
  474.                         memcpy(text+end+1, tempbuf, m); /* restore */
  475.                         free(tempbuf);
  476.                         return -1;
  477.                     }
  478.                 }
  479.                 else {
  480.                     if (-1 == bm(pat, m, text+start, text+end, oldpat, oldm)) {
  481.                         free_buf(fd, text);
  482.                         memcpy(text+end+1, tempbuf, m); /* restore */
  483.                         free(tempbuf);
  484.                         return -1;
  485.                     }
  486.                 }
  487.             }
  488.             else {
  489.                 if(DNA) {
  490.                     if (-1 == monkey4( pat, m, text+start, text+end, D , oldpat, oldm )) {
  491.                         free_buf(fd, text);
  492.                         memcpy(text+end+1, tempbuf, m); /* restore */
  493.                         free(tempbuf);
  494.                         return -1;
  495.                     }
  496.                 }
  497.                 else {
  498.                     if(m >= LONG_APPX) {
  499.                         if (-1 == a_monkey(pat, m, text+start, text+end, D, oldpat, oldm)) {
  500.                             free_buf(fd, text);
  501.                             memcpy(text+end+1, tempbuf, m); /* restore */
  502.                             free(tempbuf);
  503.                             return -1;
  504.                         }
  505.                     }
  506.                     else {
  507.                         if (-1 == agrep(pat, m, text+start, text+end, D, oldpat, oldm)) {
  508.                             free_buf(fd, text);
  509.                             memcpy(text+end+1, tempbuf, m); /* restore */
  510.                             free(tempbuf);
  511.                             return -1;
  512.                         }
  513.                     }
  514.                 }
  515.             }
  516.             if(FILENAMEONLY && (num_of_matched - prev_num_of_matched) && (NEW_FILE || !POST_FILTER)) {    /* externally set */
  517.                 if (agrep_finalfp != NULL)
  518.                     fprintf(agrep_finalfp, "%s\n", CurrentFileName);
  519.                 else {
  520.                     int outindex;
  521.                     for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  522.                             (CurrentFileName[outindex] != '\0'); outindex++) {
  523.                         agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  524.                     }
  525.                     if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+1>=agrep_outlen)) {
  526.                         OUTPUT_OVERFLOW;
  527.                         free_buf(fd, text);
  528.                         memcpy(text+end+1, tempbuf, m); /* restore */
  529.                         free(tempbuf);
  530.                         return -1;
  531.                     }
  532.                     else agrep_outbuffer[agrep_outpointer+outindex++] = '\n';
  533.                     agrep_outpointer += outindex;
  534.                 }
  535.                 free_buf(fd, text);
  536.                 NEW_FILE = OFF;
  537.             }
  538.  
  539.         memcpy(text+end+1, tempbuf, m); /* restore */
  540.         free(tempbuf);
  541.         return 0;
  542.     }
  543. #endif    /*AGREP_POINTER*/
  544. } /* end sgrep */
  545.  
  546. /* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  547. pat[m-1] such that the skip loop is guaranteed to terminated */
  548.  
  549. bm(pat, m, text, textend, oldpat, oldm)
  550. CHARTYPE *text, *textend, *pat, *oldpat;
  551. int m, oldm;
  552. {
  553.     register int shift;
  554.     register int  m1, j, d1; 
  555.     CHARTYPE *textbegin = text;
  556.     int newlen;
  557.     CHARTYPE *textstart;
  558.     CHARTYPE *curtextbegin;
  559.     CHARTYPE *curtextend;
  560.     struct timeval initt, finalt;
  561.     CHARTYPE *lastout = text;
  562.  
  563.     d1 = shift_1;    /* at least 1 */
  564.     m1 = m - 1;
  565.     shift = 0;       
  566.     while (text <= textend) {
  567.         textstart = text;
  568.         shift = SHIFT[*(text += shift)];
  569.         while(shift) {         
  570.             shift = SHIFT[*(text += shift)];
  571.             shift = SHIFT[*(text += shift)];
  572.             shift = SHIFT[*(text += shift)];
  573.         }
  574.         CurrentByteOffset += text - textstart;
  575.         j = 0;
  576.         while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  577.             if(++j == m)  break;       /* if statement can be saved, but for safty ... */
  578.         }
  579.         if (j == m ) { 
  580.             if(text > textend) return 0;
  581.             if(WORDBOUND) {
  582.                 if(isalnum(*(text+1))) goto CONT;    /* as if there was no match */
  583.                 if(isalnum(*(text-m))) goto CONT;    /* as if there was no match */
  584.                 /* changed by Udi 11/7/94 to avoid having to set TR[] to W_delim */
  585.             }
  586.  
  587.             if (TCOMPRESSED == ON) {
  588.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  589.                 if (!DELIMITER) {
  590.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  591.                     if (*curtextbegin == '\n') curtextbegin ++;
  592.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  593.                     if (*curtextend == '\n') curtextend ++;
  594.                 }
  595.                 else {
  596.                     curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  597.                     curtextend = forward_delimiter(text+1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  598.                 }
  599.             }
  600.             else {
  601.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  602.                 if (!DELIMITER) {
  603.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  604.                     if (*curtextbegin == '\n') curtextbegin ++;
  605.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  606.                     if (*curtextend == '\n') curtextend ++;
  607.                 }
  608.                 else {
  609.                     curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  610.                     curtextend = forward_delimiter(text+1, textend, D_pattern, D_length, OUTTAIL);
  611.                 }
  612.             }
  613.  
  614.             if (TCOMPRESSED == ON) {
  615. #if     MEASURE_TIMES
  616.                                 gettimeofday(&initt, NULL);
  617. #endif  /*MEASURE_TIMES*/
  618.                 if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text - curtextbegin + m, EASYSEARCH))
  619.                     goto CONT;    /* as if there was no match */
  620. #if     MEASURE_TIMES
  621.                                 gettimeofday(&finalt, NULL);
  622.                                 FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  623. #endif  /*MEASURE_TIMES*/
  624.             }
  625.  
  626.             textbegin = curtextend; /* (curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  627.             num_of_matched++;
  628.             if(FILENAMEONLY) return 0;
  629.             if(!COUNT) {
  630.                 if (!INVERSE) {
  631.                     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  632.                         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  633.                         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  634.                         if (agrep_finalfp != NULL)
  635.                             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  636.                         else {
  637.                             int outindex;
  638.                             if (prevstring[0] != '\0') {
  639.                                 if(agrep_outpointer + 1 >= agrep_outlen) {
  640.                                     OUTPUT_OVERFLOW;
  641.                                     return -1;
  642.                                 }
  643.                                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  644.                             }
  645.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  646.                                     (CurrentFileName[outindex] != '\0'); outindex++) {
  647.                                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  648.                             }
  649.                             if ((CurrentFileName[outindex] != '\0') || (outindex+agrep_outpointer+2>=agrep_outlen)) {
  650.                                 OUTPUT_OVERFLOW;
  651.                                 return -1;
  652.                             }
  653.                             else {
  654.                                 agrep_outbuffer[agrep_outpointer+outindex++] = ':';
  655.                                 agrep_outbuffer[agrep_outpointer+outindex++] = nextchar;
  656.                             }
  657.                             agrep_outpointer += outindex;
  658.                         }
  659.                         NEW_FILE = OFF;
  660.                     }
  661.  
  662.                     if(BYTECOUNT) {
  663.                         if (agrep_finalfp != NULL)
  664.                             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  665.                         else {
  666.                             char s[32];
  667.                             int  outindex;
  668.                             sprintf(s, "%d=", CurrentByteOffset);
  669.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  670.                                     (s[outindex] != '\0'); outindex++) {
  671.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  672.                             }
  673.                             if (s[outindex] != '\0') {
  674.                                 OUTPUT_OVERFLOW;
  675.                                 return -1;
  676.                             }
  677.                             agrep_outpointer += outindex;
  678.                         }
  679.                     }
  680.  
  681.                     CurrentByteOffset += textbegin - text;
  682.                     text = textbegin;
  683.  
  684.  
  685.                     if (TCOMPRESSED == ON) {
  686. #if    MEASURE_TIMES
  687.                         gettimeofday(&initt, NULL);
  688. #endif    /*MEASURE_TIMES*/
  689.                         if (agrep_finalfp != NULL)
  690.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  691.                         else {
  692.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  693.                                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  694.                                     OUTPUT_OVERFLOW;
  695.                                     return -1;
  696.                                 }
  697.                                 agrep_outpointer += newlen;
  698.                             }
  699.                         }
  700. #if    MEASURE_TIMES
  701.                         gettimeofday(&finalt, NULL);
  702.                         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  703. #endif    /*MEASURE_TIMES*/
  704.                     }
  705.                     else {
  706.                         if (agrep_finalfp != NULL) {
  707.                             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  708.                         }
  709.                         else {
  710.                             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  711.                                 OUTPUT_OVERFLOW;
  712.                                 return -1;
  713.                             }
  714.                             memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  715.                             agrep_outpointer += curtextend - curtextbegin;
  716.                         }
  717.                     }
  718.                 }
  719.                 else {    /* INVERSE */
  720.                     if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  721.                         if (agrep_finalfp != NULL)
  722.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  723.                         else {
  724.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  725.                                 if (newlen + agrep_outpointer >= agrep_outlen) {
  726.                                     OUTPUT_OVERFLOW;
  727.                                     return -1;
  728.                                 }
  729.                                 agrep_outpointer += newlen;
  730.                             }
  731.                         }
  732.                         lastout=textbegin;
  733.                         CurrentByteOffset += textbegin - text;
  734.                         text = textbegin;
  735.                     }
  736.                     else { /* NOT TCOMPRESSED */
  737.                         if (agrep_finalfp != NULL)
  738.                             fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  739.                         else {
  740.                             if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  741.                                 OUTPUT_OVERFLOW;
  742.                                 return -1;
  743.                             }
  744.                             memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  745.                             agrep_outpointer += (curtextbegin - lastout);
  746.                         }
  747.                         lastout=textbegin;
  748.                         CurrentByteOffset += textbegin - text;
  749.                         text = textbegin;
  750.                     } /* TCOMPRESSED */
  751.                 } /* INVERSE */
  752.             }
  753.             else {    /* COUNT */
  754.                 CurrentByteOffset += textbegin - text;
  755.                 text = textbegin;
  756.             }
  757.             if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  758.  
  759. CONT:
  760.             shift = 1;
  761.         }
  762.         else shift = d1;
  763.     }
  764.  
  765.     if (INVERSE && !COUNT && (lastout <= textend)) {
  766.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  767.             if (agrep_finalfp != NULL)
  768.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  769.             else {
  770.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  771.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  772.                         OUTPUT_OVERFLOW;
  773.                         return -1;
  774.                     }
  775.                     agrep_outpointer += newlen;
  776.                 }
  777.             }
  778.         }
  779.         else { /* NOT TCOMPRESSED */
  780.             if (agrep_finalfp != NULL)
  781.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  782.             else {
  783.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  784.                     OUTPUT_OVERFLOW;
  785.                     return -1;
  786.                 }
  787.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  788.                 agrep_outpointer += (textend - lastout + 1);
  789.             }
  790.         } /* TCOMPRESSED */
  791.     }
  792.  
  793.     return 0;
  794. }
  795.  
  796. /* initmask() initializes the mask table for the pattern                    */ 
  797. /* endposition is a mask for the endposition of the pattern                 */
  798. /* endposition will contain k mask bits if the pattern contains k fragments */
  799. initmask(pattern, Mask, m, D, endposition)
  800. CHARTYPE *pattern; 
  801. unsigned *Mask; 
  802. register int m, D; 
  803. unsigned *endposition;
  804. {
  805.     register unsigned Bit1, c;
  806.     register int i, j, frag_num;
  807.  
  808.     /* Bit1 = 1 << 31;*/    /* the first bit of Bit1 is 1, others 0.  */
  809.     Bit1 = (unsigned)0x80000000;
  810.     frag_num = D+1; 
  811.     *endposition = 0;
  812.     for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  813.     *endposition = *endposition >> (m - frag_num);
  814.     for(i = 0; i < m; i++) 
  815.         if (pattern[i] == '^' || pattern[i] == '$') {
  816.             pattern[i] = '\n'; 
  817.         }
  818.     for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  819.     for(i = 0; i < m; i++)     /* initialize the mask table */
  820.     {  
  821.         c = pattern[i];
  822.         for ( j = 0; j < m; j++)
  823.             if( c == pattern[j] )
  824.                 Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  825.     }
  826. }
  827.  
  828. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  829. CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  830. register int M, D;
  831. {
  832.     register int i, j, k, p, shift;
  833.     register unsigned m;
  834.     unsigned hash, b_size = 3;
  835.     m = M/(D+1);
  836.     p = M - m*(D+1);
  837.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  838.     for (i = M-1; i>=p ; i--) {
  839.         shift = (M-1-i)%m;
  840.         hash = Pattern[i];
  841.         if((int)(SHIFT[hash]) > (int)(shift)) SHIFT[hash] = shift;
  842.     }
  843. #ifdef DEBUG
  844.     for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  845.     printf("\n");
  846. #endif
  847.     shift_1 = m;
  848.     for(i=0; i<D+1; i++) {
  849.         j = M-1 - m*i;
  850.         for(k=1; k<m; k++) {
  851.             for(p=0; p<D+1; p++) 
  852.                 if(Pattern[j-k] == Pattern[M-1-m*p]) 
  853.                     if(k < shift_1) shift_1 = k;
  854.         }
  855.     }
  856. #ifdef DEBUG
  857.     printf("\nshift_1 = %d", shift_1);
  858. #endif
  859.     if(shift_1 == 0) shift_1 = 1;
  860.     for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  861.     if (m < 3) b_size = m;
  862.     for(i=0; i<D+1; i++) {
  863.         j = M-1 - m*i;
  864.         hash = 0;
  865.         for(k=0; k<b_size; k++) {
  866.             hash = (hash << 2) + Pattern[j-k];
  867.         }
  868. #ifdef DEBUG
  869.         printf(" hash = %d,", hash);
  870. #endif
  871.         MEMBER[hash] = 1;
  872.     }
  873. }
  874.  
  875. agrep( pat, M, text, textend, D, oldpat, oldM) 
  876. int M, D, oldM; 
  877. register CHARTYPE *text, *textend, *pat, *oldpat;
  878. {
  879.     register int i;
  880.     register int m = M/(D+1);
  881.     register CHARTYPE *textbegin;
  882.     CHARTYPE *textstart;
  883.     register int shift, HASH;
  884.     int  j=0, k, d1;
  885.     int  n, cdx;
  886.     int  Candidate[MaxCan][2], round, lastend=0;
  887.     unsigned R1[MaxError+1], R2[MaxError+1]; 
  888.     register unsigned int r1, endpos, c; 
  889.     unsigned currentpos;
  890.     unsigned Bit1;
  891.     unsigned r_newline;
  892.     int oldbyteoffset;
  893.     CHARTYPE *lastout = text;
  894.     int newlen;
  895.  
  896.     Candidate[0][0] = Candidate[0][1] = 0; 
  897.     d1 = shift_1;
  898.     cdx = 0;
  899.     if(m < 3) r1 = m;
  900.     else r1 = 3;
  901.     textbegin = text;
  902.     shift = m-1;
  903.     while (text < textend) {
  904.         textstart = text;
  905.         shift = SHIFT[*(text += shift)];
  906.         while(shift) {
  907.             shift = SHIFT[*(text += shift)];
  908.             shift = SHIFT[*(text += shift)];
  909.         }
  910.         CurrentByteOffset += text - textstart;
  911.         j = 1; 
  912.         HASH = *text;
  913.         while(j < r1) { 
  914.             HASH = (HASH << 2) + *(text-j);
  915.             j++; 
  916.         }
  917.         if (MEMBER[HASH]) { 
  918.             i = text - textbegin;
  919.             if((i - M - D - 10) > Candidate[cdx][1]) {     
  920.                 Candidate[++cdx][0] = i-M-D-2;
  921.                 Candidate[cdx][1] = i+M+D; 
  922.             }
  923.             else Candidate[cdx][1] = i+M+D;
  924.             shift = d1;
  925.         }
  926.         else shift = d1;
  927.     }
  928.  
  929.     CurrentByteOffset += (textbegin - text);
  930.     text = textbegin;
  931.     n = textend - textbegin;
  932.     r_newline = '\n';
  933.     /* for those candidate areas, find the D-error matches                     */
  934.     if(Candidate[1][0] < 0) Candidate[1][0] = 0;
  935.     endpos = endposition;                /* the mask table and the endposition */
  936.     /* Bit1 = (1 << 31); */
  937.     Bit1 = (unsigned)0x80000000;
  938.     oldbyteoffset = CurrentByteOffset;
  939.     for(round = 0; round <= cdx; round++)
  940.     {  
  941.         i = Candidate[round][0] ; 
  942.         if(Candidate[round][1] > n) Candidate[round][1] = n;
  943.         if(i < 0) i = 0;
  944.         CurrentByteOffset = oldbyteoffset+i;
  945.         R1[0] = R2[0] = ~0;
  946.         R1[1] = R2[1] = ~Bit1;
  947.         for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];
  948.         while (i < Candidate[round][1])                     
  949.         {  
  950.             c = text[i++];
  951.             CurrentByteOffset ++;
  952.             if(c == r_newline) {
  953.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  954.             }
  955.             r1 = Mask[c];
  956.             R1[0] = (R2[0] >> 1) | r1;
  957.             for(k=1; k<=D; k++)
  958.                 R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  959.             if((R1[D] & endpos) == 0) { 
  960.                 num_of_matched++;
  961.                 if(FILENAMEONLY) return 0; 
  962.                 currentpos = i;
  963.                 if(i <= lastend) {
  964.                     CurrentByteOffset += lastend - i;
  965.                     i = lastend;
  966.                 }
  967.                 else {
  968.                     int oldcurrentpos = currentpos;
  969.                     if (-1 == s_output(text, ¤tpos, textbegin, textend, &lastout, pat, M, oldpat, oldM)) return -1;
  970.                     CurrentByteOffset += currentpos - oldcurrentpos;
  971.                     i = currentpos; 
  972.                 }
  973.                 lastend = i;
  974.                 for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  975.                 if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  976.             }
  977.  
  978.             /* copying the code to save a few instructions.
  979.             you need to understand the shift-or algorithm
  980.             to figure this one... */
  981.  
  982.             c = text[i++];
  983.             CurrentByteOffset ++;
  984.             if(c == r_newline) {
  985.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  986.             }
  987.             r1 = Mask[c];
  988.             R2[0] = (R1[0] >> 1) | r1;
  989.             for(k = 1; k <= D; k++)
  990.                 R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  991.             if((R2[D] & endpos) == 0) { 
  992.                 currentpos = i;
  993.                 num_of_matched++;
  994.                 if(FILENAMEONLY) return 0; 
  995.                 if(i <= lastend) {
  996.                     CurrentByteOffset += lastend - i;
  997.                     i = lastend;
  998.                 }
  999.                 else {
  1000.                     int oldcurrentpos = currentpos;
  1001.                     if (-1 == s_output(text, ¤tpos, textbegin, textend, &lastout, pat, M, oldpat, oldM)) return -1;
  1002.                     CurrentByteOffset += currentpos - oldcurrentpos;
  1003.                     i = currentpos; 
  1004.                 }
  1005.                 lastend = i;
  1006.                 for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  1007.                 if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  1008.             }
  1009.         }
  1010.     }
  1011.  
  1012.  
  1013.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1014.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1015.             if (agrep_finalfp != NULL)
  1016.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1017.             else {
  1018.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1019.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1020.                         OUTPUT_OVERFLOW;
  1021.                         return -1;
  1022.                     }
  1023.                     agrep_outpointer += newlen;
  1024.                 }
  1025.             }
  1026.         }
  1027.         else { /* NOT TCOMPRESSED */
  1028.             if (agrep_finalfp != NULL)
  1029.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1030.             else {
  1031.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1032.                     OUTPUT_OVERFLOW;
  1033.                     return -1;
  1034.                 }
  1035.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1036.                 agrep_outpointer += (textend - lastout + 1);
  1037.             }
  1038.         } /* TCOMPRESSED */
  1039.     }
  1040.  
  1041.     return 0;
  1042. }
  1043.  
  1044. /* Don't update CurrentByteOffset here: done by caller */
  1045. s_output(text, i, textbegin, textend, lastout, pat, m, oldpat, oldm) 
  1046. int *i;    /* in, out */
  1047. int m, oldm; 
  1048. CHARTYPE *text, *textbegin, *textend, *pat, *oldpat;
  1049. CHARTYPE **lastout;    /* in, out */
  1050. {
  1051.     int newlen; 
  1052.     CHARTYPE *curtextbegin;
  1053.     CHARTYPE *curtextend;
  1054.     struct timeval initt, finalt;
  1055.  
  1056.     if(SILENT) return 0;
  1057.     if (TCOMPRESSED == ON) {
  1058.         if (!DELIMITER) {
  1059.             curtextbegin = text + *i; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1060.             if (*curtextbegin == '\n') curtextbegin ++;
  1061.             curtextend = text + *i /* + 1 agrep() has i++ */; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1062.             if (*curtextend == '\n') curtextend ++;
  1063.         }
  1064.         else {
  1065.             curtextbegin = backward_delimiter(text + *i, text, tc_D_pattern, tc_D_length, OUTTAIL);
  1066.             curtextend = forward_delimiter(text + *i /* + 1 agrep() has i++ */, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1067.         }
  1068.     }
  1069.     else {
  1070.         if (!DELIMITER) {
  1071.             curtextbegin = text + *i; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1072.             if (*curtextbegin == '\n') curtextbegin ++;
  1073.             curtextend = text + *i /* + 1 agrep() has i++ */; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1074.             if (*curtextend == '\n') curtextend ++;
  1075.         }
  1076.         else {
  1077.             curtextbegin = backward_delimiter(text + *i, text, D_pattern, D_length, OUTTAIL);
  1078.             curtextend = forward_delimiter(text + *i /* + 1 agrep() has i++ */, textend, D_pattern, D_length, OUTTAIL);
  1079.         }
  1080.     }
  1081.  
  1082.     if (TCOMPRESSED == ON) {
  1083. #if     MEASURE_TIMES
  1084.         gettimeofday(&initt, NULL);
  1085. #endif  /*MEASURE_TIMES*/
  1086.         if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text  + *i - curtextbegin + m, EASYSEARCH)) {
  1087.             num_of_matched --;
  1088.             return 0;
  1089.         }
  1090. #if     MEASURE_TIMES
  1091.         gettimeofday(&finalt, NULL);
  1092.         FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1093. #endif  /*MEASURE_TIMES*/
  1094.     }
  1095.  
  1096.     textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1097.     *i += textbegin - (text + *i);
  1098.     if(COUNT) return 0;
  1099.  
  1100.  
  1101.     if (INVERSE) {
  1102.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1103.             if (agrep_finalfp != NULL)
  1104.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, *lastout, curtextbegin - *lastout, agrep_finalfp, -1, EASYSEARCH);
  1105.             else {
  1106.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, *lastout, curtextbegin - *lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1107.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1108.                         OUTPUT_OVERFLOW;
  1109.                         return -1;
  1110.                     }
  1111.                     agrep_outpointer += newlen;
  1112.                 }
  1113.             }
  1114.             *lastout=textbegin;
  1115.             CurrentByteOffset += textbegin - text;
  1116.             text = textbegin;
  1117.         }
  1118.         else { /* NOT TCOMPRESSED */
  1119.             if (agrep_finalfp != NULL)
  1120.                 fwrite(*lastout, 1, curtextbegin-*lastout, agrep_finalfp);
  1121.             else {
  1122.                 if (curtextbegin - *lastout + agrep_outpointer >= agrep_outlen) {
  1123.                     OUTPUT_OVERFLOW;
  1124.                     return -1;
  1125.                 }
  1126.                 memcpy(agrep_outbuffer+agrep_outpointer, *lastout, curtextbegin-*lastout);
  1127.                 agrep_outpointer += (curtextbegin - *lastout);
  1128.             }
  1129.             *lastout=textbegin;
  1130.             CurrentByteOffset += textbegin - text;
  1131.             text = textbegin;
  1132.         } /* TCOMPRESSED */
  1133.         return 0;
  1134.     }
  1135.  
  1136.     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1137.         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1138.         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1139.         if (agrep_finalfp != NULL)
  1140.             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1141.         else {
  1142.             int outindex;
  1143.             if (prevstring[0] != '\0') {
  1144.                 if(agrep_outpointer + 1 >= agrep_outlen) {
  1145.                     OUTPUT_OVERFLOW;
  1146.                     return -1;
  1147.                 }
  1148.                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1149.             }
  1150.             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1151.                     (CurrentFileName[outindex] != '\0'); outindex++) {
  1152.                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1153.             }
  1154.             if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1155.                 OUTPUT_OVERFLOW;
  1156.                 return -1;
  1157.             }
  1158.             agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1159.             agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1160.             agrep_outpointer += outindex;
  1161.         }
  1162.         NEW_FILE = OFF;
  1163.     }
  1164.  
  1165.     if(BYTECOUNT) {
  1166.         if (agrep_finalfp != NULL)
  1167.             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1168.         else {
  1169.             char s[32];
  1170.             int  outindex;
  1171.             sprintf(s, "%d= ", CurrentByteOffset);
  1172.             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1173.                     (s[outindex] != '\0'); outindex++) {
  1174.                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1175.             }
  1176.             if (s[outindex] != '\0') {
  1177.                 OUTPUT_OVERFLOW;
  1178.                 return -1;
  1179.             }
  1180.             agrep_outpointer += outindex;
  1181.         }
  1182.     }
  1183.  
  1184.     if (TCOMPRESSED == ON) {
  1185. #if    MEASURE_TIMES
  1186.         gettimeofday(&initt, NULL);
  1187. #endif    /*MEASURE_TIMES*/
  1188.         if (agrep_finalfp != NULL) {
  1189.             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1190.         }
  1191.         else {
  1192.             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1193.                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1194.                     OUTPUT_OVERFLOW;
  1195.                     return -1;
  1196.                 }
  1197.                 agrep_outpointer += newlen;
  1198.             }
  1199.         }
  1200. #if    MEASURE_TIMES
  1201.         gettimeofday(&finalt, NULL);
  1202.         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1203. #endif    /*MEASURE_TIMES*/
  1204.     }
  1205.     else {
  1206.         if (agrep_finalfp != NULL) {
  1207.             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1208.         }
  1209.         else {
  1210.             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1211.                 OUTPUT_OVERFLOW;
  1212.                 return -1;
  1213.             }
  1214.             memcpy(agrep_outbuffer + agrep_outpointer, curtextbegin, curtextend - curtextbegin);
  1215.             agrep_outpointer += curtextend - curtextbegin;
  1216.         }
  1217.     }
  1218.     return 0;
  1219. }
  1220.  
  1221.  
  1222. prep_bm(Pattern, m)      
  1223. unsigned char *Pattern;
  1224. register m;
  1225. {
  1226.     int i;
  1227.     unsigned hash;
  1228.     unsigned char lastc;
  1229.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  1230.     for (i = m-1; i>=0; i--) {
  1231.         hash = TR[Pattern[i]];
  1232.         if((int)(SHIFT[hash]) >= (int)(m - 1)) SHIFT[hash] = m-1-i;
  1233.     }
  1234.     shift_1 = m-1;
  1235.     /* shift_1 records the previous occurrence of the last character of
  1236.     the pattern.  When we match this last character but do not have a match,
  1237.     we can shift until we reach the next occurrence from the right. */
  1238.     lastc = TR[Pattern[m-1]];
  1239.     for (i= m-2; i>=0; i--) {
  1240.         if(TR[Pattern[i]] == lastc )
  1241.         { 
  1242.             shift_1 = m-1 - i;  
  1243.             i = -1; 
  1244.         }
  1245.     }
  1246.     if(shift_1 == 0) shift_1 = 1; /* can never happen - Udi 11/7/94 */
  1247.     if(NOUPPER) for(i=0; i<MAXSYM; i++) {
  1248.         if (isupper(i)) SHIFT[i] = SHIFT[tolower(i)];
  1249.         /* SHIFT[i] = SHIFT[i +  'a' - 'A']; */
  1250.     }
  1251. #ifdef DEBUG
  1252.     for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); 
  1253.     printf("\n");
  1254.     for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); 
  1255.     printf("\n");
  1256. #endif
  1257. }
  1258.  
  1259. /* monkey uses two characters for delta_1 shifting */
  1260.  
  1261. CHARTYPE SHIFT_2[MAX_SHIFT_2];
  1262.  
  1263. monkey( pat, m, text, textend  ) 
  1264. register int m  ; 
  1265. register CHARTYPE *text, *textend, *pat;
  1266. {
  1267.     register unsigned hash;
  1268.     register CHARTYPE shift;
  1269.     register int  m1, j; 
  1270.     CHARTYPE *textbegin = text;
  1271.     CHARTYPE *textstart;
  1272.     int newlen;
  1273.     CHARTYPE *curtextbegin;
  1274.     CHARTYPE *curtextend;
  1275.     struct timeval initt, finalt;
  1276.     CHARTYPE *lastout = text;
  1277.  
  1278.     m1 = m - 1;
  1279.     text = text+m1;
  1280.     CurrentByteOffset += m1;
  1281.     while (text < textend) {
  1282.         textstart = text;
  1283.         hash = TR[*text];
  1284.         hash = (hash << 3) + TR[*(text-1)];
  1285.         shift = SHIFT_2[hash];
  1286.         while(shift) {
  1287.             text = text + shift;
  1288.             hash = (TR[*text] << 3) + TR[*(text-1)];
  1289.             shift = SHIFT_2[hash];
  1290.         }
  1291.         CurrentByteOffset += text - textstart;
  1292.         j = 0;
  1293.         while(TR[pat[m1 - j]] == TR[*(text - j)]) { 
  1294.             if(++j == m) break; 
  1295.         }
  1296.         if (j == m ) {
  1297.             if(text > textend) return 0; /* Udi: used to be >= for some reason */
  1298.             /* added by Udi 11/7/94 */
  1299.             if(WORDBOUND) {
  1300.                 if(isalnum(*(text+1))) goto CONT;    /* as if there was no match */
  1301.                 if(isalnum(*(text-m))) goto CONT;    /* as if there was no match */
  1302.                 /* changed by Udi 11/7/94 to avoid having to set TR[] to W_delim */
  1303.             }
  1304.  
  1305.             if (TCOMPRESSED == ON) {
  1306.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1307.                 if (!DELIMITER) {
  1308.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1309.                     if (*curtextbegin == '\n') curtextbegin ++;
  1310.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1311.                     if (*curtextend == '\n') curtextend ++;
  1312.                 }
  1313.                 else {
  1314.                     curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  1315.                     curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1316.                 }
  1317.             }
  1318.             else {
  1319.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1320.                 if (!DELIMITER) {
  1321.                     curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1322.                     if (*curtextbegin == '\n') curtextbegin ++;
  1323.                     curtextend = text+1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1324.                     if (*curtextend == '\n') curtextend ++;
  1325.                 }
  1326.                 else {
  1327.                     curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  1328.                     curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  1329.                 }
  1330.             }
  1331.  
  1332.             if (TCOMPRESSED == ON) {
  1333. #if     MEASURE_TIMES
  1334.                                 gettimeofday(&initt, NULL);
  1335. #endif  /*MEASURE_TIMES*/
  1336.                 if (-1 == exists_tcompressed_word(pat, m, curtextbegin, text - curtextbegin + m, EASYSEARCH))
  1337.                     goto CONT;    /* as if there was no match */
  1338. #if     MEASURE_TIMES
  1339.                                 gettimeofday(&finalt, NULL);
  1340.                                 FILTERALGO_ms +=  (finalt.tv_sec *1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1341. #endif  /*MEASURE_TIMES*/
  1342.             }
  1343.  
  1344.             textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1345.             num_of_matched++;
  1346.             if(FILENAMEONLY)  return 0;
  1347.             if (!COUNT) {
  1348.                 if (!INVERSE) {
  1349.                     if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1350.                         char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1351.                         char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1352.                         if (agrep_finalfp != NULL)
  1353.                             fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1354.                         else {
  1355.                             int outindex;
  1356.                             if (prevstring[0] != '\0') {
  1357.                                 if(agrep_outpointer + 1 >= agrep_outlen) {
  1358.                                     OUTPUT_OVERFLOW;
  1359.                                     return -1;
  1360.                                 }
  1361.                                 else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1362.                             }
  1363.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1364.                                     (CurrentFileName[outindex] != '\0'); outindex++) {
  1365.                                 agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1366.                             }
  1367.                             if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1368.                                 OUTPUT_OVERFLOW;
  1369.                                 return -1;
  1370.                             }
  1371.                             agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1372.                             agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1373.                             agrep_outpointer += outindex;
  1374.                         }
  1375.                         NEW_FILE = OFF;
  1376.                     }
  1377.  
  1378.                     if(BYTECOUNT) {
  1379.                         if (agrep_finalfp != NULL)
  1380.                             fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1381.                         else {
  1382.                             char s[32];
  1383.                             int  outindex;
  1384.                             sprintf(s, "%d= ", CurrentByteOffset);
  1385.                             for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1386.                                     (s[outindex] != '\0'); outindex++) {
  1387.                                 agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1388.                             }
  1389.                             if (s[outindex] != '\0') {
  1390.                                 OUTPUT_OVERFLOW;
  1391.                                 return -1;
  1392.                             }
  1393.                             agrep_outpointer += outindex;
  1394.                         }
  1395.                     }
  1396.  
  1397.                     CurrentByteOffset += textbegin - text;
  1398.                     text = textbegin;
  1399.  
  1400.  
  1401.                     if (TCOMPRESSED == ON) {
  1402. #if    MEASURE_TIMES
  1403.                         gettimeofday(&initt, NULL);
  1404. #endif    /*MEASURE_TIMES*/
  1405.                         if (agrep_finalfp != NULL)
  1406.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1407.                         else {
  1408.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1409.                                 if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1410.                                     OUTPUT_OVERFLOW;
  1411.                                     return -1;
  1412.                                 }
  1413.                                 agrep_outpointer += newlen;
  1414.                             }
  1415.                         }
  1416. #if    MEASURE_TIMES
  1417.                         gettimeofday(&finalt, NULL);
  1418.                         OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1419. #endif    /*MEASURE_TIMES*/
  1420.                     }
  1421.                     else {
  1422.                         if (agrep_finalfp != NULL) {
  1423.                             fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1424.                         }
  1425.                         else {
  1426.                             if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1427.                                 OUTPUT_OVERFLOW;
  1428.                                 return -1;
  1429.                             }
  1430.                             memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  1431.                             agrep_outpointer += curtextend - curtextbegin;
  1432.                         }
  1433.                     }
  1434.  
  1435.                 }
  1436.                 else {    /* INVERSE */
  1437.                     if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1438.                         if (agrep_finalfp != NULL)
  1439.                             newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  1440.                         else {
  1441.                             if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1442.                                 if (newlen + agrep_outpointer >= agrep_outlen) {
  1443.                                     OUTPUT_OVERFLOW;
  1444.                                     return -1;
  1445.                                 }
  1446.                                 agrep_outpointer += newlen;
  1447.                             }
  1448.                         }
  1449.                         lastout=textbegin;
  1450.                         CurrentByteOffset += textbegin - text;
  1451.                         text = textbegin;
  1452.                     }
  1453.                     else { /* NOT TCOMPRESSED */
  1454.                         if (agrep_finalfp != NULL)
  1455.                             fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  1456.                         else {
  1457.                             if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  1458.                                 OUTPUT_OVERFLOW;
  1459.                                 return -1;
  1460.                             }
  1461.                             memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  1462.                             agrep_outpointer += (curtextbegin - lastout);
  1463.                         }
  1464.                         lastout=textbegin;
  1465.                         CurrentByteOffset += textbegin - text;
  1466.                         text = textbegin;
  1467.                     } /* TCOMPRESSED */
  1468.                 } /* INVERSE */
  1469.             }
  1470.             else {    /* COUNT */
  1471.                 CurrentByteOffset += textbegin - text;
  1472.                 text = textbegin;
  1473.             }
  1474.  
  1475.             /* Counteract the ++ below */
  1476.             text --;
  1477.             CurrentByteOffset --;
  1478.             if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  1479.         }
  1480.     CONT:
  1481.         text++;
  1482.         CurrentByteOffset ++;
  1483.     }
  1484.  
  1485.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1486.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1487.             if (agrep_finalfp != NULL)
  1488.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1489.             else {
  1490.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1491.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1492.                         OUTPUT_OVERFLOW;
  1493.                         return -1;
  1494.                     }
  1495.                     agrep_outpointer += newlen;
  1496.                 }
  1497.             }
  1498.         }
  1499.         else { /* NOT TCOMPRESSED */
  1500.             if (agrep_finalfp != NULL)
  1501.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1502.             else {
  1503.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1504.                     OUTPUT_OVERFLOW;
  1505.                     return -1;
  1506.                 }
  1507.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1508.                 agrep_outpointer += (textend - lastout + 1);
  1509.             }
  1510.         } /* TCOMPRESSED */
  1511.     }
  1512.  
  1513.     return 0;
  1514. }
  1515.  
  1516. /* a_monkey() the approximate monkey move */
  1517.  
  1518. a_monkey( pat, m, text, textend, D ) 
  1519. register int m, D ; 
  1520. register CHARTYPE *text, *textend, *pat;
  1521. {
  1522.     register CHARTYPE *oldtext;
  1523.     CHARTYPE *curtextbegin;
  1524.     CHARTYPE *curtextend;
  1525.     register unsigned hash, i, hashmask, suffix_error; 
  1526.     register int  m1 = m-1-D, pos; 
  1527.     CHARTYPE *textbegin = text;
  1528.     CHARTYPE *textstart;
  1529.     CHARTYPE *lastout = text;
  1530.     int newlen;
  1531.  
  1532.     hashmask = Hashmask;
  1533.     oldtext  = text;
  1534.     while (text < textend) {
  1535.         textstart = text;
  1536.         text = text+m1;
  1537.         suffix_error = 0;
  1538.         while(suffix_error <= D) {
  1539.             hash = *text--;
  1540.             while(MEMBER_1[hash]) {
  1541.                 hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
  1542.             }
  1543.             suffix_error++;
  1544.         }
  1545.         CurrentByteOffset += text - textstart;
  1546.         if(text <= oldtext) {
  1547.             if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  1548.                 CurrentByteOffset += (oldtext+pos - text);
  1549.                 text = oldtext+pos;
  1550.                 if(text > textend) return 0;
  1551.  
  1552.                 /* Don't update CurrentByteOffset here: only before outputting properly */
  1553.                 if (TCOMPRESSED == ON) {
  1554.                     if (!DELIMITER) {
  1555.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1556.                         if (*curtextbegin == '\n') curtextbegin ++;
  1557.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1558.                         if (*curtextend == '\n') curtextend ++;
  1559.                     }
  1560.                     else {
  1561.                         curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  1562.                         curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1563.                     }
  1564.                 }
  1565.                 else {
  1566.                     if (!DELIMITER) {
  1567.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1568.                         if (*curtextbegin == '\n') curtextbegin ++;
  1569.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1570.                         if (*curtextend == '\n') curtextend ++;
  1571.                     }
  1572.                     else {
  1573.                         curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  1574.                         curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  1575.                     }
  1576.                 }
  1577.                 textbegin = curtextend; /* (curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1578.  
  1579.                 num_of_matched++;
  1580.                 if(FILENAMEONLY) return 0;
  1581.                 if(!COUNT) {
  1582.                     if (!INVERSE) {
  1583.                         if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1584.                             char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1585.                             char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1586.                             if (agrep_finalfp != NULL)
  1587.                                 fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1588.                             else {
  1589.                                 int outindex;
  1590.                                 if (prevstring[0] != '\0') {
  1591.                                     if(agrep_outpointer + 1 >= agrep_outlen) {
  1592.                                         OUTPUT_OVERFLOW;
  1593.                                         return -1;
  1594.                                     }
  1595.                                     else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1596.                                 }
  1597.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1598.                                         (CurrentFileName[outindex] != '\0'); outindex++) {
  1599.                                     agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1600.                                 }
  1601.                                 if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1602.                                     OUTPUT_OVERFLOW;
  1603.                                     return -1;
  1604.                                 }
  1605.                                 agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1606.                                 agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1607.                                 agrep_outpointer += outindex;
  1608.                             }
  1609.                             NEW_FILE = OFF;
  1610.                         }
  1611.  
  1612.                         if(BYTECOUNT) {
  1613.                             if (agrep_finalfp != NULL)
  1614.                                 fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1615.                             else {
  1616.                                 char s[32];
  1617.                                 int  outindex;
  1618.                                 sprintf(s, "%d= ", CurrentByteOffset);
  1619.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1620.                                         (s[outindex] != '\0'); outindex++) {
  1621.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1622.                                 }
  1623.                                 if (s[outindex] != '\0') {
  1624.                                     OUTPUT_OVERFLOW;
  1625.                                     return -1;
  1626.                                 }
  1627.                                 agrep_outpointer += outindex;
  1628.                             }
  1629.                         }
  1630.  
  1631.                         CurrentByteOffset += textbegin - text;
  1632.                         text = textbegin;
  1633.  
  1634.  
  1635.                         if (TCOMPRESSED == ON) {
  1636. #if    MEASURE_TIMES
  1637.                             gettimeofday(&initt, NULL);
  1638. #endif    /*MEASURE_TIMES*/
  1639.                             if (agrep_finalfp != NULL)
  1640.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1641.                             else {
  1642.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1643.                                     if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1644.                                         OUTPUT_OVERFLOW;
  1645.                                         return -1;
  1646.                                     }
  1647.                                     agrep_outpointer += newlen;
  1648.                                 }
  1649.                             }
  1650. #if    MEASURE_TIMES
  1651.                             gettimeofday(&finalt, NULL);
  1652.                             OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1653. #endif    /*MEASURE_TIMES*/
  1654.                         }
  1655.                         else {
  1656.                             if (agrep_finalfp != NULL) {
  1657.                                 fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  1658.                             }
  1659.                             else {
  1660.                                 if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  1661.                                     OUTPUT_OVERFLOW;
  1662.                                     return -1;
  1663.                                 }
  1664.                                 memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  1665.                                 agrep_outpointer += curtextend - curtextbegin;
  1666.                             }
  1667.                         }
  1668.  
  1669.                     }
  1670.                     else {    /* INVERSE */
  1671.                         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1672.                             if (agrep_finalfp != NULL)
  1673.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  1674.                             else {
  1675.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1676.                                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1677.                                         OUTPUT_OVERFLOW;
  1678.                                         return -1;
  1679.                                     }
  1680.                                     agrep_outpointer += newlen;
  1681.                                 }
  1682.                             }
  1683.                             lastout=textbegin;
  1684.                             CurrentByteOffset += textbegin - text;
  1685.                             text = textbegin;
  1686.                         }
  1687.                         else { /* NOT TCOMPRESSED */
  1688.                             if (agrep_finalfp != NULL)
  1689.                                 fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  1690.                             else {
  1691.                                 if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  1692.                                     OUTPUT_OVERFLOW;
  1693.                                     return -1;
  1694.                                 }
  1695.                                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  1696.                                 agrep_outpointer += (curtextbegin - lastout);
  1697.                             }
  1698.                             lastout=textbegin;
  1699.                             CurrentByteOffset += textbegin - text;
  1700.                             text = textbegin;
  1701.                         } /* TCOMPRESSED */
  1702.                     }
  1703.                 }
  1704.                 else {    /* COUNT */
  1705.                     CurrentByteOffset += textbegin - text;
  1706.                     text = textbegin;
  1707.                 }
  1708.                 if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  1709.             }
  1710.             else {
  1711.                 CurrentByteOffset += (oldtext + m - text);
  1712.                 text = oldtext + m;
  1713.             }
  1714.         }
  1715.         oldtext = text;
  1716.     }
  1717.  
  1718.     if (INVERSE && !COUNT && (lastout <= textend)) {
  1719.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  1720.             if (agrep_finalfp != NULL)
  1721.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  1722.             else {
  1723.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1724.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  1725.                         OUTPUT_OVERFLOW;
  1726.                         return -1;
  1727.                     }
  1728.                     agrep_outpointer += newlen;
  1729.                 }
  1730.             }
  1731.         }
  1732.         else { /* NOT TCOMPRESSED */
  1733.             if (agrep_finalfp != NULL)
  1734.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  1735.             else {
  1736.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  1737.                     OUTPUT_OVERFLOW;
  1738.                     return -1;
  1739.                 }
  1740.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  1741.                 agrep_outpointer += (textend - lastout + 1);
  1742.             }
  1743.         } /* TCOMPRESSED */
  1744.     }
  1745.  
  1746.     return 0;
  1747. }
  1748.  
  1749. am_preprocess(Pattern)
  1750. CHARTYPE *Pattern;
  1751. {
  1752.     int i, m;
  1753.     m = strlen(Pattern);
  1754.     for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
  1755.     for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
  1756.     for (i = m-1; i>=0; i--) {
  1757.         MEMBER_1[Pattern[i]] = 1;
  1758.     }
  1759.     for (i = m-1; i > 0; i--) {
  1760.         MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
  1761.     }
  1762. }
  1763.  
  1764.  
  1765. verify(m, n, D, pat, text)
  1766. register int m, n, D;
  1767. CHARTYPE *pat, *text;
  1768. {   
  1769.     int A[MAXPATT], B[MAXPATT];
  1770.     register int last = D;      
  1771.     register int cost = 0;  
  1772.     register int k, i, c;
  1773.     register int m1 = m+1;
  1774.     CHARTYPE *textend = text+n;
  1775.     CHARTYPE *textbegin = text;
  1776.  
  1777.     for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
  1778.     while (text < textend)
  1779.     {
  1780.         for (k = 1; k <= last; k++)
  1781.         {
  1782.             cost = B[k-1]+1; 
  1783.             if (pat[k-1] != *text)
  1784.             {   
  1785.                 if (B[k]+1 < cost) cost = B[k]+1; 
  1786.                 if (A[k-1]+1 < cost) cost = A[k-1]+1; 
  1787.             }
  1788.             else cost = cost -1; 
  1789.             A[k] = cost; 
  1790.         }
  1791.         if(pat[last] == *text++) { 
  1792.             A[last+1] = B[last]; 
  1793.             last++; 
  1794.         }
  1795.         if(A[last] < D) A[last+1] = A[last++]+1;
  1796.         while (A[last] > D) last = last - 1;
  1797.         if(last >= m) return(text - textbegin - 1);
  1798.         if(*text == '\n') {
  1799.             last = D;
  1800.             for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1801.         }
  1802.         for (k = 1; k <= last; k++)
  1803.         {
  1804.             cost = A[k-1]+1; 
  1805.             if (pat[k-1] != *text)
  1806.             {   
  1807.                 if (A[k]+1 < cost) cost = A[k]+1; 
  1808.                 if (B[k-1]+1 < cost) cost = B[k-1]+1; 
  1809.             }
  1810.             else cost = cost -1; 
  1811.             B[k] = cost;
  1812.         }
  1813.         if(pat[last] == *text++) { 
  1814.             B[last+1] = A[last]; 
  1815.             last++; 
  1816.         }
  1817.         if(B[last] < D) B[last+1] = B[last++]+1;
  1818.         while (B[last] > D) last = last -1;
  1819.         if(last >= m)   return(text - textbegin - 1);
  1820.         if(*text == '\n') {
  1821.             last = D;
  1822.             for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1823.         }
  1824.     }    
  1825.     return(0);
  1826. }
  1827.  
  1828. /* preprocessing for monkey()   */
  1829.  
  1830. m_preprocess(Pattern)
  1831. CHARTYPE *Pattern;
  1832. {
  1833.     int i, j, m;
  1834.     unsigned hash;
  1835.     m = strlen(Pattern);
  1836.     for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
  1837.     for (i = m-1; i>=1; i--) {
  1838.         hash = TR[Pattern[i]];
  1839.         hash = hash << 3;
  1840.         for (j = 0; j< MAXSYM; j++) {
  1841.             if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
  1842.         }
  1843.         hash = hash + TR[Pattern[i-1]];
  1844.         if((int)(SHIFT_2[hash]) >= (int)(m - 1)) SHIFT_2[hash] = m-1-i;
  1845.     }
  1846.     shift_1 = m-1;
  1847.     for (i= m-2; i>=0; i--) {
  1848.         if(TR[Pattern[i]] == TR[Pattern[m-1]] )
  1849.         { 
  1850.             shift_1 = m-1 - i;  
  1851.             i = -1; 
  1852.         }
  1853.     }
  1854.     if(shift_1 == 0) shift_1 = 1;
  1855.     SHIFT_2[0] = 0;
  1856. }
  1857.  
  1858. /* monkey4() the approximate monkey move */
  1859.  
  1860. char *MEMBER_D = NULL;
  1861.  
  1862. monkey4( pat, m, text, textend, D  ) 
  1863. register int m, D ; 
  1864. register unsigned char *text, *pat, *textend;
  1865. {
  1866.     register unsigned char *oldtext;
  1867.     register unsigned hash, hashmask, suffix_error; 
  1868.     register int m1=m-1-D, pos; 
  1869.     CHARTYPE *textbegin = text;
  1870.     CHARTYPE *textstart;
  1871.     CHARTYPE *curtextbegin;
  1872.     CHARTYPE *curtextend;
  1873.     CHARTYPE *lastout = text;
  1874.     int newlen;
  1875.  
  1876.     hashmask = Hashmask;
  1877.     oldtext = text ;
  1878.     while (text < textend) {
  1879.         textstart = text;
  1880.         text = text + m1;
  1881.         suffix_error = 0;
  1882.         while(suffix_error <= D) {
  1883.             hash = char_map[*text--];
  1884.             hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  1885.             while(MEMBER_D[hash]) {
  1886.                 hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  1887.             }
  1888.             suffix_error++;
  1889.         }
  1890.         CurrentByteOffset += text - textstart;
  1891.         if(text <= oldtext) {
  1892.             if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  1893.                 CurrentByteOffset += (oldtext+pos - text);
  1894.                 text = oldtext+pos;
  1895.                 if(text > textend) return 0;
  1896.  
  1897.                 if (TCOMPRESSED == ON) {
  1898.                     /* Don't update CurrentByteOffset here: only before outputting properly */
  1899.                     if (!DELIMITER) {
  1900.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1901.                         if (*curtextbegin == '\n') curtextbegin ++;
  1902.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1903.                         if (*curtextend == '\n') curtextend ++;
  1904.                     }
  1905.                     else {
  1906.                         curtextbegin = backward_delimiter(text, textbegin, tc_D_pattern, tc_D_length, OUTTAIL);
  1907.                         curtextend = forward_delimiter(text + 1, textend, tc_D_pattern, tc_D_length, OUTTAIL);
  1908.                     }
  1909.                 }
  1910.                 else {
  1911.                     /* Don't update CurrentByteOffset here: only before outputting properly */
  1912.                     if (!DELIMITER) {
  1913.                         curtextbegin = text; while((curtextbegin > textbegin) && (*(--curtextbegin) != '\n'));
  1914.                         if (*curtextbegin == '\n') curtextbegin ++;
  1915.                         curtextend = text + 1; while((curtextend < textend) && (*curtextend != '\n')) curtextend ++;
  1916.                         if (*curtextend == '\n') curtextend ++;
  1917.                     }
  1918.                     else {
  1919.                         curtextbegin = backward_delimiter(text, textbegin, D_pattern, D_length, OUTTAIL);
  1920.                         curtextend = forward_delimiter(text + 1, textend, D_pattern, D_length, OUTTAIL);
  1921.                     }
  1922.                 }
  1923.                 textbegin = curtextend; /*(curtextend - 1 > textbegin ? curtextend - 1 : curtextend); */
  1924.  
  1925.                 num_of_matched++;
  1926.                 if(FILENAMEONLY) return 0;
  1927.                 if(!COUNT) {
  1928.                     if (!INVERSE) {
  1929.                         if(FNAME && (NEW_FILE || !POST_FILTER)) {
  1930.                             char    nextchar = (POST_FILTER == ON)?'\n':' ';
  1931.                             char    *prevstring = (POST_FILTER == ON)?"\n":"";
  1932.                             if (agrep_finalfp != NULL)
  1933.                                 fprintf(agrep_finalfp, "%s%s:%c", prevstring, CurrentFileName, nextchar);
  1934.                             else {
  1935.                                 int outindex;
  1936.                                 if (prevstring[0] != '\0') {
  1937.                                     if(agrep_outpointer + 1 >= agrep_outlen) {
  1938.                                         OUTPUT_OVERFLOW;
  1939.                                         return -1;
  1940.                                     }
  1941.                                     else agrep_outbuffer[agrep_outpointer ++] = prevstring[0];
  1942.                                 }
  1943.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1944.                                         (CurrentFileName[outindex] != '\0'); outindex++) {
  1945.                                     agrep_outbuffer[agrep_outpointer+outindex] = CurrentFileName[outindex];
  1946.                                 }
  1947.                                 if ((CurrentFileName[outindex] != '\0') || (outindex + agrep_outpointer + 2 >= agrep_outlen)) {
  1948.                                     OUTPUT_OVERFLOW;
  1949.                                     return -1;
  1950.                                 }
  1951.                                 agrep_outbuffer[agrep_outpointer + outindex++] = ':';
  1952.                                 agrep_outbuffer[agrep_outpointer + outindex++] = nextchar;
  1953.                                 agrep_outpointer += outindex;
  1954.                             }
  1955.                             NEW_FILE = OFF;
  1956.                         }
  1957.  
  1958.                         if(BYTECOUNT) {
  1959.                             if (agrep_finalfp != NULL)
  1960.                                 fprintf(agrep_finalfp, "%d= ", CurrentByteOffset);
  1961.                             else {
  1962.                                 char s[32];
  1963.                                 int  outindex;
  1964.                                 sprintf(s, "%d= ", CurrentByteOffset);
  1965.                                 for(outindex=0; (outindex+agrep_outpointer<agrep_outlen) &&
  1966.                                         (s[outindex] != '\0'); outindex++) {
  1967.                                     agrep_outbuffer[agrep_outpointer+outindex] = s[outindex];
  1968.                                 }
  1969.                                 if (s[outindex] != '\0') {
  1970.                                     OUTPUT_OVERFLOW;
  1971.                                     return -1;
  1972.                                 }
  1973.                                 agrep_outpointer += outindex;
  1974.                             }
  1975.                         }
  1976.  
  1977.                         CurrentByteOffset += textbegin + 1 - text;
  1978.                         text = textbegin + 1;
  1979.  
  1980.  
  1981.                         if (TCOMPRESSED == ON) {
  1982. #if    MEASURE_TIMES
  1983.                             gettimeofday(&initt, NULL);
  1984. #endif    /*MEASURE_TIMES*/
  1985.                             if (agrep_finalfp != NULL)
  1986.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_finalfp, -1, EASYSEARCH);
  1987.                             else {
  1988.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, curtextbegin, curtextend-curtextbegin, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  1989.                                     if (agrep_outpointer + newlen + 1 >= agrep_outlen) {
  1990.                                         OUTPUT_OVERFLOW;
  1991.                                         return -1;
  1992.                                     }
  1993.                                     agrep_outpointer += newlen;
  1994.                                 }
  1995.                             }
  1996. #if    MEASURE_TIMES
  1997.                             gettimeofday(&finalt, NULL);
  1998.                             OUTFILTER_ms +=  (finalt.tv_sec*1000 + finalt.tv_usec/1000) - (initt.tv_sec*1000 + initt.tv_usec/1000);
  1999. #endif    /*MEASURE_TIMES*/
  2000.                         }
  2001.                         else {
  2002.                             if (agrep_finalfp != NULL) {
  2003.                                 fwrite(curtextbegin, 1, curtextend - curtextbegin, agrep_finalfp);
  2004.                             }
  2005.                             else {
  2006.                                 if (agrep_outpointer + curtextend - curtextbegin >= agrep_outlen) {
  2007.                                     OUTPUT_OVERFLOW;
  2008.                                     return -1;
  2009.                                 }
  2010.                                 memcpy(agrep_outbuffer+agrep_outpointer, curtextbegin, curtextend-curtextbegin);
  2011.                                 agrep_outpointer += curtextend - curtextbegin;
  2012.                             }
  2013.                         }
  2014.                     }
  2015.                     else {    /* INVERSE */
  2016.                         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  2017.                             if (agrep_finalfp != NULL)
  2018.                                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_finalfp, -1, EASYSEARCH);
  2019.                             else {
  2020.                                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, curtextbegin - lastout, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  2021.                                     if (newlen + agrep_outpointer >= agrep_outlen) {
  2022.                                         OUTPUT_OVERFLOW;
  2023.                                         return -1;
  2024.                                     }
  2025.                                     agrep_outpointer += newlen;
  2026.                                 }
  2027.                             }
  2028.                             lastout=textbegin;
  2029.                             CurrentByteOffset += textbegin + 1 - text;
  2030.                             text = textbegin + 1;
  2031.                         }
  2032.                         else { /* NOT TCOMPRESSED */
  2033.                             if (agrep_finalfp != NULL)
  2034.                                 fwrite(lastout, 1, curtextbegin-lastout, agrep_finalfp);
  2035.                             else {
  2036.                                 if (curtextbegin - lastout + agrep_outpointer >= agrep_outlen) {
  2037.                                     OUTPUT_OVERFLOW;
  2038.                                     return -1;
  2039.                                 }
  2040.                                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, curtextbegin-lastout);
  2041.                                 agrep_outpointer += (curtextbegin - lastout);
  2042.                             }
  2043.                             lastout=textbegin;
  2044.                             CurrentByteOffset += textbegin + 1 - text;
  2045.                             text = textbegin + 1;
  2046.                         } /* TCOMPRESSED */
  2047.                     }
  2048.                 }
  2049.                 else {    /* COUNT */
  2050.                     CurrentByteOffset += textbegin + 1 - text;
  2051.                     text = textbegin + 1 ;
  2052.                 }
  2053.                 if ((LIMITOUTPUT > 0) && (LIMITOUTPUT <= num_of_matched)) return 0;    /* done */
  2054.             }
  2055.             else { CurrentByteOffset += (oldtext + m - text); text = oldtext + m; }
  2056.         }
  2057.         oldtext = text; 
  2058.     }
  2059.  
  2060.     if (INVERSE && !COUNT && (lastout <= textend)) {
  2061.         if (TCOMPRESSED == ON) { /* INVERSE: Don't care about filtering time */
  2062.             if (agrep_finalfp != NULL)
  2063.                 newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_finalfp, -1, EASYSEARCH);
  2064.             else {
  2065.                 if ((newlen = quick_tuncompress(FREQ_FILE, STRING_FILE, lastout, textend - lastout + 1, agrep_outbuffer, agrep_outlen - agrep_outpointer, EASYSEARCH)) > 0) {
  2066.                     if (newlen + agrep_outpointer >= agrep_outlen) {
  2067.                         OUTPUT_OVERFLOW;
  2068.                         return -1;
  2069.                     }
  2070.                     agrep_outpointer += newlen;
  2071.                 }
  2072.             }
  2073.         }
  2074.         else { /* NOT TCOMPRESSED */
  2075.             if (agrep_finalfp != NULL)
  2076.                 fwrite(lastout, 1, textend-lastout + 1, agrep_finalfp);
  2077.             else {
  2078.                 if (textend - lastout + 1 + agrep_outpointer >= agrep_outlen) {
  2079.                     OUTPUT_OVERFLOW;
  2080.                     return -1;
  2081.                 }
  2082.                 memcpy(agrep_outbuffer+agrep_outpointer, lastout, textend-lastout + 1);
  2083.                 agrep_outpointer += (textend - lastout + 1);
  2084.             }
  2085.         } /* TCOMPRESSED */
  2086.     }
  2087.  
  2088.     return 0;
  2089. }
  2090.  
  2091. prep4(Pattern, m)
  2092. char *Pattern; 
  2093. int m;
  2094. {
  2095.     int i, j, k;
  2096.     unsigned hash;
  2097.  
  2098.     for(i=0; i< MAXSYM; i++) char_map[i] = 0;
  2099.     char_map['a'] = char_map['A'] = 4;
  2100.     char_map['g'] = char_map['g'] = 1;
  2101.     char_map['t'] = char_map['t'] = 2;
  2102.     char_map['c'] = char_map['c'] = 3;
  2103.     char_map['n'] = char_map['n'] = 5;
  2104.  
  2105.     BSize = blog(4, m);
  2106.     for (i = 1, Hashmask = 1 ; i<(int)(BSize*LOG_DNA); i++) Hashmask = (Hashmask << 1) + 1 ;
  2107.     if (MEMBER_D != NULL) free(MEMBER_D);
  2108.     MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
  2109. #ifdef DEBUG
  2110.     printf("BSize = %d", BSize);
  2111. #endif 
  2112.     for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
  2113.     for (j=0; j < (int)BSize; j++) {
  2114.         for(i=m-1; i >= j; i--) {
  2115.             hash = 0;
  2116.             for(k=0; k <= j; k++) 
  2117.                 hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
  2118. #ifdef DEBUG
  2119.             printf("< %d >, ", hash);
  2120. #endif
  2121.             MEMBER_D[hash] = 1;
  2122.         }
  2123.     }
  2124. }
  2125.  
  2126. blog(base, m )
  2127. int base, m;
  2128. {
  2129.     int i, exp;
  2130.     exp = base;
  2131.     m = m + m/2;
  2132.     for (i = 1; exp < m; i++) exp = exp * base;
  2133.     return(i);
  2134. }
  2135.  
  2136.