home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1994 March / Source_Code_CD-ROM_Walnut_Creek_March_1994.iso / compsrcs / unix / volume26 / agrep201 / part03 < prev    next >
Encoding:
Text File  |  1992-05-08  |  56.2 KB  |  1,776 lines
  1. Newsgroups: comp.sources.unix
  2. From: sw@cs.arizona.edu (Sun Wu)
  3. Subject: v26i023: agrep - very fast grep with approximate pattern matching, Part03/03
  4. Sender: unix-sources-moderator@pa.dec.com
  5. Approved: vixie@pa.dec.com
  6.  
  7. Submitted-By: sw@cs.arizona.edu (Sun Wu)
  8. Posting-Number: Volume 26, Issue 23
  9. Archive-Name: agrep-2.01/part03
  10.  
  11. #! /bin/sh
  12. # This is a shell archive.  Remove anything before this line, then unpack
  13. # it by saving it into a file and typing "sh file".  To overwrite existing
  14. # files, type "sh file -c".  You can also feed this as standard input via
  15. # unshar, or by typing "sh <file", e.g..  If this archive is complete, you
  16. # will see the following message at the end:
  17. #        "End of archive 3 (of 3)."
  18. # Contents:  main.c sgrep.c
  19. # Wrapped by sw@optima on Sun Feb 23 13:44:16 1992
  20. PATH=/bin:/usr/bin:/usr/ucb ; export PATH
  21. if test -f 'main.c' -a "${1}" != "-c" ; then 
  22.   echo shar: Will not clobber existing file \"'main.c'\"
  23. else
  24. echo shar: Extracting \"'main.c'\" \(35404 characters\)
  25. sed "s/^X//" >'main.c' <<'END_OF_FILE'
  26. X/* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  27. X#include "agrep.h"
  28. X#include "checkfile.h"
  29. X
  30. unsigned Mask[MAXSYM];
  31. unsigned Init1, NO_ERR_MASK, Init[MaxError];
  32. unsigned Bit[WORD+1];
  33. CHAR buffer[BlockSize+Maxline+1];
  34. unsigned Next[MaxNext], Next1[MaxNext];
  35. unsigned wildmask, endposition, D_endpos; 
  36. int  REGEX, RE_ERR, FNAME, WHOLELINE, SIMPLEPATTERN;
  37. int  COUNT, HEAD, TAIL, LINENUM, INVERSE, I, S, DD, AND, SGREP, JUMP; 
  38. int  Num_Pat, PSIZE, num_of_matched, SILENT, BESTMATCH, NOUPPER;
  39. int  NOMATCH, TRUNCATE, FIRST_IN_RE, FIRSTOUTPUT;
  40. int  WORDBOUND, DELIMITER, D_length;
  41. int  EATFIRST, OUTTAIL;
  42. int  FILEOUT;
  43. int  DNA = 0;
  44. int  APPROX = 0;
  45. int  PAT_FILE = 0;
  46. int  CONSTANT = 0;
  47. int total_line = 0; /* used in mgrep */
  48. X                                     
  49. CHAR **Textfiles;     /* array of filenames to be searched */
  50. CHAR old_D_pat[MaxDelimit] = "\n";  /* to hold original D_pattern */
  51. CHAR CurrentFileName[MAXNAME]; 
  52. CHAR Progname[MAXNAME]; 
  53. CHAR D_pattern[MaxDelimit] = "\n; "; /* string which delimits records --
  54. X                                        defaults to newline */   
  55. int  NOFILENAME = 0,  /* Boolean flag, set for -h option */
  56. X     FILENAMEONLY = 0,/* Boolean flag, set for -l option */
  57. X     Numfiles = 0;    /* indicates how many files in Textfiles */
  58. extern int init();
  59. int table[WORD][WORD];
  60. X
  61. initial_value()
  62. X{
  63. X   int i; 
  64. X
  65. X   JUMP = REGEX = FNAME = BESTMATCH = NOUPPER = 0;
  66. X   COUNT = LINENUM = WHOLELINE = SGREP = 0;
  67. X   EATFIRST = INVERSE = AND = TRUNCATE = OUTTAIL = 0; 
  68. X   FIRST_IN_RE = NOMATCH = FIRSTOUTPUT = ON;
  69. X   I = DD = S = 1;
  70. X   HEAD = TAIL = ON;
  71. X   D_length = 2;
  72. X   SILENT = Num_Pat = PSIZE = SIMPLEPATTERN = num_of_matched = 0 ;
  73. X   WORDBOUND = DELIMITER = RE_ERR = 0;
  74. X   Bit[WORD] = 1;
  75. X   for (i = WORD - 1; i > 0  ; i--)  Bit[i] = Bit[i+1] << 1; 
  76. X   for (i=0; i< MAXSYM; i++) Mask[i] = 0;
  77. X}
  78. X
  79. compute_next(M, Next, Next1)
  80. int M; unsigned *Next, *Next1;
  81. X{
  82. X  int i, j=0, n,  k, temp;
  83. X  int mid, pp;
  84. X  int MM, base;
  85. X  unsigned V[WORD];
  86. X   
  87. X  base = WORD - M;
  88. X  temp = Bit[base]; Bit[base] = 0;
  89. X  for (i=0; i<WORD; i++) V[i] = 0;
  90. X  for (i=1; i<M; i++)
  91. X  {  
  92. X      j=0;
  93. X      while (table[i][j] > 0 && j < 10) {
  94. X            V[i] = V[i] | Bit[base + table[i][j++]];
  95. X      }
  96. X  }
  97. X  Bit[base]=temp;
  98. X  if(M <= SHORTREG)
  99. X  {
  100. X    k = exponen(M);
  101. X    pp = 2*k;
  102. X    for(i=k; i<pp ; i++)
  103. X    {   n = i;
  104. X        Next[i]= (k>>1);
  105. X        for(j=M; j>=1; j--)
  106. X        {
  107. X           if(n & Bit[WORD]) Next[i] = Next[i] | V[j];
  108. X           n = (n>>1);
  109. X        }
  110. X    }      
  111. X    return;
  112. X  }
  113. X  if(M > MAXREG) fprintf(stderr, "%s: regular expression too long\n", Progname);
  114. X  MM = M;
  115. X  if(M & 1) M=M+1;
  116. X  k = exponen(M/2);
  117. X  pp = 2*k;
  118. X  mid = MM/2;
  119. X  for(i=k; i<pp ; i++)
  120. X  {     n = i;
  121. X        Next[i]= (Bit[base]>>1);
  122. X        for(j=MM; j>mid ; j--)
  123. X        {
  124. X           if(n & Bit[WORD]) Next[i] = Next[i] | V[j-mid];
  125. X           n = (n>>1);
  126. X        }
  127. X        n=i-k;
  128. X        Next1[i-k] = 0;
  129. X        for(j = 0; j<mid; j++)
  130. X        {
  131. X           if(n & Bit[WORD]) Next1[i-k] = Next1[i-k] | V[MM-j];
  132. X           n = (n>>1);
  133. X        }
  134. X  }      
  135. X  return;
  136. X}
  137. X  
  138. exponen(m)
  139. int m;
  140. X{ int i, ex;
  141. X  ex= 1;
  142. X  for (i=0; i<m; i++) ex= ex*2;
  143. X  return(ex);
  144. X}
  145. X
  146. re1(Text, M, D)
  147. int Text, M, D;
  148. X{
  149. X  register unsigned i, c, r0, r1, r2, r3, CMask, Newline, Init0, r_NO_ERR; 
  150. X  register unsigned end;
  151. X  register unsigned hh, LL=0, k;  /* Lower part */
  152. X  int  FIRST_TIME=ON, num_read , j=0, base;
  153. X  unsigned A[MaxRerror+1], B[MaxRerror+1];
  154. X  unsigned Next[MaxNext], Next1[MaxNext];
  155. X  CHAR buffer[BlockSize+Maxline+1];
  156. X  int FIRST_LOOP = 1;
  157. X   
  158. X  r_NO_ERR = NO_ERR_MASK;
  159. X  if(M > 30) {
  160. X     fprintf(stderr, "%s: regular expression too long\n", Progname);
  161. X     exit(2);
  162. X  }
  163. X  base = WORD - M;
  164. X  hh = M/2;
  165. X  for(i=WORD, j=0; j < hh ; i--, j++) LL = LL | Bit[i];
  166. X  if(FIRST_IN_RE) compute_next(M, Next, Next1); 
  167. X                                   /*SUN: try: change to memory allocation */
  168. X  FIRST_IN_RE = 0;
  169. X  Newline = '\n';
  170. X  Init[0] = Bit[base];
  171. X  if(HEAD) Init[0] = Init[0] | Bit[base+1];
  172. X  for(i=1; i<= D; i++) Init[i] = Init[i-1] | Next[Init[i-1]>>hh] | Next1[Init[i-1]&LL];
  173. X  Init1 = Init[0] | 1; 
  174. X  Init0 = Init[0];
  175. X  r2 = r3 = Init[0];
  176. X  for(k=0; k<= D; k++) { A[k] = B[k] = Init[k]; }
  177. X  if ( D == 0 )
  178. X  {
  179. X    while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  180. X    {
  181. X      i=Maxline; end = num_read + Maxline;
  182. X      if((num_read < BlockSize) && buffer[end-1] != '\n') buffer[end] = '\n';
  183. X      if(FIRST_LOOP) {         /* if first time in the loop add a newline */
  184. X        buffer[i-1] = '\n';  /* in front the  text.  */
  185. X    i--;
  186. X        FIRST_LOOP = 0;
  187. X      }
  188. X      while ( i < end )
  189. X      {
  190. X        c = buffer[i++];
  191. X        CMask = Mask[c];
  192. X        if(c != Newline)
  193. X        {  if(CMask != 0) {  
  194. X              r1 = Init1 & r3;
  195. X              r2 = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) | r1;
  196. X           }
  197. X       else  {
  198. X              r2 = r3 & Init1; 
  199. X           }
  200. X        }
  201. X        else {  j++; 
  202. X              r1 = Init1 & r3;            /* match against endofline */
  203. X              r2 = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) | r1;
  204. X              if(TAIL) r2 = (Next[r2>>hh] | Next1[r2&LL]) | r2;                                        /* epsilon move */
  205. X              if(( r2 & 1 ) ^ INVERSE) {
  206. X                   if(FILENAMEONLY) {
  207. X                          num_of_matched++;
  208. X                          printf("%s\n", CurrentFileName);
  209. X                          return;
  210. X                   } 
  211. X                   r_output(buffer, i-1, end, j);
  212. X              }
  213. X              r3 = Init0;
  214. X              r2 = (Next[r3>>hh] | Next1[r3&LL]) & CMask | Init0;  
  215. X                                               /* match begin of line */
  216. X        }
  217. X        c = buffer[i++];
  218. X        CMask = Mask[c];
  219. X        if(c != Newline)
  220. X        {  if(CMask != 0) {  
  221. X              r1 = Init1 & r2;
  222. X              r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  223. X           }
  224. X       else   r3 = r2 & Init1; 
  225. X        } /* if(NOT Newline) */
  226. X        else {  j++;
  227. X              r1 = Init1 & r2;            /* match against endofline */
  228. X              r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  229. X              if(TAIL) r3 = ( Next[r3>>hh] | Next1[r3&LL] ) | r3; 
  230. X                                           /* epsilon move */
  231. X              if(( r3 & 1 ) ^ INVERSE) {
  232. X                   if(FILENAMEONLY) {
  233. X                          num_of_matched++;
  234. X                          printf("%s\n", CurrentFileName);
  235. X                          return;
  236. X                   } 
  237. X                   r_output(buffer, i-1, end, j);
  238. X              }
  239. X              r2 = Init0;
  240. X              r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | Init0; 
  241. X                   /* match begin of line */
  242. X        }
  243. X      } /* while i < end ... */
  244. X      strncpy(buffer, buffer+num_read, Maxline);
  245. X    } /* end while read()... */
  246. X  return;
  247. X  } /*  end if (D == 0) */
  248. X  while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  249. X  {
  250. X    i=Maxline; end = Maxline + num_read;
  251. X    if((num_read < BlockSize) && buffer[end-1] != '\n') buffer[end] = '\n';
  252. X    if(FIRST_TIME) {         /* if first time in the loop add a newline */
  253. X        buffer[i-1] = '\n';  /* in front the  text.  */
  254. X    i--;
  255. X        FIRST_TIME = 0;
  256. X    }
  257. X    while (i < end )
  258. X    {
  259. X        c = buffer[i];
  260. X        CMask = Mask[c];
  261. X        if(c !=  Newline)
  262. X        {
  263. X           if(CMask != 0) {  
  264. X              r2 = B[0];
  265. X              r1 = Init1 & r2;
  266. X              A[0] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  267. X              r3 = B[1];
  268. X              r1 = Init1 & r3;
  269. X              r0 = r2 | A[0];     /* A[0] | B[0] */
  270. X              A[1] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       (( r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  271. X                     if(D == 1) goto Nextchar;
  272. X              r2 = B[2];
  273. X              r1 = Init1 & r2;
  274. X              r0 = r3 | A[1];
  275. X              A[2] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) |                                       ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  276. X                     if(D == 2) goto Nextchar;
  277. X              r3 = B[3];
  278. X              r1 = Init1 & r3;
  279. X              r0 = r2 | A[2];
  280. X              A[3] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  281. X                     if(D == 3) goto Nextchar;
  282. X              r2 = B[4];
  283. X              r1 = Init1 & r2;
  284. X              r0 = r3 | A[3];
  285. X              A[4] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) |                                        ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  286. X                     if(D == 4)  goto Nextchar;
  287. X           }  /* if(CMask) */
  288. X       else  {
  289. X              r2 = B[0];
  290. X              A[0] = r2 & Init1; 
  291. X              r3 = B[1];
  292. X              r1 = Init1 & r3;
  293. X              r0 = r2 | A[0];
  294. X              A[1] = ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  295. X                   if(D == 1) goto Nextchar;
  296. X              r2 = B[2];
  297. X              r1 = Init1 & r2;
  298. X              r0 = r3 | A[1];
  299. X              A[2] = ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  300. X                   if(D == 2) goto Nextchar;
  301. X              r3 = B[3];
  302. X              r1 = Init1 & r3;
  303. X              r0 = r2 | A[2];
  304. X              A[3] = ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  305. X                   if(D == 3) goto Nextchar;
  306. X              r2 = B[4];
  307. X              r1 = Init1 & r2;
  308. X              r0 = r3 | A[3];
  309. X              A[4] = ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  310. X                   if(D == 4) goto Nextchar;
  311. X           }
  312. X        }
  313. X        else {  j++;
  314. X              r1 = Init1 & B[D];            /* match against endofline */
  315. X              A[D] = ((Next[B[D]>>hh] | Next1[B[D]&LL]) & CMask) | r1;
  316. X              if(TAIL) A[D] = ( Next[A[D]>>hh] | Next1[A[D]&LL] ) | A[D]; 
  317. X                                           /* epsilon move */
  318. X              if(( A[D] & 1 ) ^ INVERSE) {
  319. X                   if(FILENAMEONLY) {
  320. X                          num_of_matched++;
  321. X                          printf("%s\n", CurrentFileName);
  322. X                          return;
  323. X                   } 
  324. X                   r_output(buffer, i, end, j);
  325. X              }
  326. X              for(k=0; k<=D; k++)  B[k] = Init[0];
  327. X              r1 = Init1 & B[0];
  328. X              A[0] = (( Next[B[0]>>hh] | Next1[B[0]&LL]) & CMask) | r1;
  329. X              for(k=1; k<=D; k++) {
  330. X                   r3 = B[k];
  331. X                   r1 = Init1 & r3;
  332. X                   r2 = A[k-1] | B[k-1];
  333. X                   A[k] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       ((B[k-1] | Next[r2>>hh] | Next1[r2&LL]) & r_NO_ERR) | r1;
  334. X              }
  335. X        }
  336. Nextchar: i=i+1;
  337. X        c = buffer[i];
  338. X        CMask = Mask[c];
  339. X        if(c != Newline)
  340. X        {
  341. X           if(CMask != 0) {  
  342. X              r2 = A[0];
  343. X              r1 = Init1 & r2;
  344. X              B[0] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  345. X              r3 = A[1];
  346. X              r1 = Init1 & r3;
  347. X              r0 = B[0] | r2;
  348. X              B[1] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       ((r2 | Next[r0>>hh] | Next1[r0&LL]) & r_NO_ERR) | r1 ;  
  349. X                     if(D == 1) goto Nextchar1;
  350. X              r2 = A[2];
  351. X              r1 = Init1 & r2;
  352. X              r0 = B[1] | r3;
  353. X              B[2] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) |                                   ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  354. X                     if(D == 2) goto Nextchar1;
  355. X              r3 = A[3];
  356. X              r1 = Init1 & r3;
  357. X              r0 = B[2] | r2;
  358. X              B[3] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  359. X                     if(D == 3) goto Nextchar1;
  360. X              r2 = A[4];
  361. X              r1 = Init1 & r2;
  362. X              r0 = B[3] | r3;
  363. X              B[4] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) |                                       ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  364. X                     if(D == 4)   goto Nextchar1;
  365. X           }  /* if(CMask) */
  366. X       else  {
  367. X              r2 = A[0];
  368. X              B[0] = r2 & Init1; 
  369. X              r3 = A[1];
  370. X              r1 = Init1 & r3;
  371. X              r0 = B[0] | r2;
  372. X              B[1] = ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  373. X                   if(D == 1) goto Nextchar1;
  374. X              r2 = A[2];
  375. X              r1 = Init1 & r2;
  376. X              r0 = B[1] | r3;
  377. X              B[2] = ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  378. X                   if(D == 2) goto Nextchar1;
  379. X              r3 = A[3];
  380. X              r1 = Init1 & r3;
  381. X              r0 = B[2] | r2;
  382. X              B[3] = ((r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  383. X                   if(D == 3) goto Nextchar1;
  384. X              r2 = A[4];
  385. X              r1 = Init1 & r2;
  386. X              r0 = B[3] | r3;
  387. X              B[4] = ((r3 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  388. X                   if(D == 4) goto Nextchar1;
  389. X           }
  390. X        } /* if(NOT Newline) */
  391. X        else {  j++;
  392. X              r1 = Init1 & A[D];            /* match against endofline */
  393. X              B[D] = ((Next[A[D]>>hh] | Next1[A[D]&LL]) & CMask) | r1;
  394. X              if(TAIL) B[D] = ( Next[B[D]>>hh] | Next1[B[D]&LL] ) | B[D]; 
  395. X                                           /* epsilon move */
  396. X              if(( B[D] & 1 ) ^ INVERSE) {
  397. X                   if(FILENAMEONLY) {
  398. X                          num_of_matched++;
  399. X                          printf("%s\n", CurrentFileName);
  400. X                          return;
  401. X                   } 
  402. X                   r_output(buffer, i, end, j);
  403. X              }
  404. X              for(k=0; k<=D; k++) A[k] = Init0; 
  405. X              r1 = Init1 & A[0];
  406. X              B[0] = ((Next[A[0]>>hh] | Next1[A[0]&LL]) & CMask) | r1;
  407. X              for(k=1; k<=D; k++) {
  408. X                   r3 = A[k];
  409. X                   r1 = Init1 & r3;
  410. X                   r2 = A[k-1] | B[k-1];
  411. X                   B[k] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       ((A[k-1] | Next[r2>>hh] | Next1[r2&LL]) & r_NO_ERR) | r1;
  412. X              }
  413. X        }
  414. Nextchar1: i=i+1;
  415. X    } /* while */
  416. X    strncpy(buffer, buffer+num_read, Maxline);
  417. X  } /* while */
  418. X  return;
  419. X} /* re1 */
  420. X
  421. re(Text, M, D)
  422. int Text, M, D;
  423. X{
  424. X  register unsigned i, c, r1, r2, r3, CMask, k, Newline, Init0, Init1, end; 
  425. X  register unsigned r_even, r_odd, r_NO_ERR ;
  426. X  unsigned RMask[MAXSYM];
  427. X  unsigned A[MaxRerror+1], B[MaxRerror+1];
  428. X  int num_read, j=0, bp, lasti, base, ResidueSize; 
  429. X  int FIRST_TIME; /* Flag */ 
  430. X  base = WORD - M;
  431. X  k = 2*exponen(M);
  432. X  if(FIRST_IN_RE) {
  433. X         compute_next(M, Next, Next1); 
  434. X         FIRST_IN_RE = 0;    }
  435. X  for(i=0; i< MAXSYM; i++) RMask[i] = Mask[i];
  436. X  r_NO_ERR = NO_ERR_MASK;
  437. X  Newline = '\n';
  438. X  lasti = Maxline;
  439. X  Init0 = Init[0] = Bit[base];
  440. X  if(HEAD) Init0  = Init[0] = Init0 | Bit[base+1] ;
  441. X  for(i=1; i<= D; i++) Init[i] = Init[i-1] | Next[Init[i-1]]; /* can be out? */
  442. X  Init1 = Init0 | 1; 
  443. X  r2 = r3 = Init0;
  444. X  for(k=0; k<= D; k++) { A[k] = B[k] = Init[0]; }  /* can be out? */
  445. X  FIRST_TIME = ON;
  446. X  if ( D == 0 )
  447. X  {
  448. X    while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  449. X    {
  450. X      i=Maxline; end = Maxline + num_read ;
  451. X      if((num_read < BlockSize)&&buffer[end-1] != '\n') buffer[end] = '\n';
  452. X      if(FIRST_TIME) {
  453. X         buffer[i-1] = '\n';
  454. X     i--;
  455. X         FIRST_TIME = 0;
  456. X      }
  457. X      while (i < end) 
  458. X      {              
  459. X        c = buffer[i++];
  460. X        CMask = RMask[c];
  461. X        if(c != Newline)
  462. X        {  
  463. X              r1 = Init1 & r3;
  464. X              r2 = (Next[r3] & CMask) | r1;
  465. X        }
  466. X        else {  
  467. X              r1 = Init1 & r3;            /* match against '\n' */
  468. X              r2 = Next[r3] & CMask | r1;
  469. X              j++;
  470. X              if(TAIL) r2 = Next[r2] | r2 ;   /* epsilon move */
  471. X              if(( r2 & 1) ^ INVERSE) {
  472. X                   if(FILENAMEONLY) {
  473. X                          num_of_matched++;
  474. X                          printf("%s\n", CurrentFileName);
  475. X                          return;
  476. X                   } 
  477. X                   r_output(buffer, i-1, end, j);
  478. X              }
  479. X              lasti = i - 1;
  480. X              r3 = Init0;
  481. X              r2 = (Next[r3] & CMask) | Init0;
  482. X        }
  483. X        c = buffer[i++];   
  484. X        CMask = RMask[c];
  485. X        if(c != Newline)
  486. X        {
  487. X              r1 = Init1 & r2;
  488. X              r3 = (Next[r2] & CMask) | r1;
  489. X        }
  490. X        else {  j++;
  491. X              r1 = Init1 & r2;            /* match against endofline */
  492. X              r3 = Next[r2] & CMask | r1;
  493. X              if(TAIL) r3 = Next[r3] | r3;
  494. X              if(( r3 & 1) ^ INVERSE) {
  495. X                   if(FILENAMEONLY) {
  496. X                          num_of_matched++;
  497. X                          printf("%s\n", CurrentFileName);
  498. X                          return;
  499. X                   } 
  500. X                   r_output(buffer, i-1, end, j);
  501. X              }
  502. X              lasti = i - 1;
  503. X              r2 = Init0; 
  504. X              r3 = (Next[r2] & CMask) | Init0;  /* match the newline */
  505. X        }
  506. X      } /* while */
  507. X      ResidueSize = Maxline + num_read - lasti;
  508. X      if(ResidueSize > Maxline) {
  509. X           ResidueSize = Maxline;  }
  510. X      strncpy(buffer+Maxline-ResidueSize, buffer+lasti, ResidueSize);
  511. X      lasti = Maxline - ResidueSize;
  512. X    } /* while */
  513. X  return;
  514. X  } /* end if(D==0) */
  515. X  while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  516. X  {
  517. X    i=Maxline; end = Maxline+num_read;
  518. X    if((num_read < BlockSize) && buffer[end-1] != '\n') buffer[end] = '\n';
  519. X    if(FIRST_TIME) {
  520. X        buffer[i-1] = '\n';
  521. X    i--;
  522. X        FIRST_TIME = 0;
  523. X    }
  524. X    while (i < end)
  525. X    {   c = buffer[i++];
  526. X        CMask = RMask[c];
  527. X        if (c != Newline)
  528. X        {  
  529. X              r_even = B[0];
  530. X              r1 = Init1 & r_even;
  531. X              A[0] = (Next[r_even] & CMask) | r1;
  532. X              r_odd = B[1];
  533. X              r1 = Init1 & r_odd;
  534. X              r2 = (r_even | Next[r_even|A[0]]) &r_NO_ERR;
  535. X              A[1] = (Next[r_odd] & CMask) | r2 | r1 ;  
  536. X                     if(D == 1) goto Nextchar;
  537. X              r_even = B[2];
  538. X              r1 = Init1 & r_even;
  539. X              r2 = (r_odd | Next[r_odd|A[1]]) &r_NO_ERR;
  540. X              A[2] = (Next[r_even] & CMask) | r2 | r1 ;  
  541. X                     if(D == 2) goto Nextchar;
  542. X              r_odd = B[3];
  543. X              r1 = Init1 & r_odd;
  544. X              r2 = (r_even | Next[r_even|A[2]]) &r_NO_ERR;
  545. X              A[3] = (Next[r_odd] & CMask) | r2 | r1 ;  
  546. X                     if(D == 3) goto Nextchar;
  547. X              r_even = B[4];
  548. X              r1 = Init1 & r_even;
  549. X              r2 = (r_odd | Next[r_odd|A[3]]) &r_NO_ERR;
  550. X              A[4] = (Next[r_even] & CMask) | r2 | r1 ;  
  551. X              goto Nextchar;
  552. X        } /* if NOT Newline */
  553. X        else {  j++;
  554. X              r1 = Init1 & B[D];               /* match endofline */
  555. X              A[D] = (Next[B[D]] & CMask) | r1;
  556. X              if(TAIL) A[D] = Next[A[D]] | A[D];
  557. X              if((A[D] & 1) ^ INVERSE )  {
  558. X                   if(FILENAMEONLY) {
  559. X                          num_of_matched++;    
  560. X                          printf("%s\n", CurrentFileName);
  561. X                          return;
  562. X                   }  
  563. X                   r_output(buffer, i-1, end, j);
  564. X              }
  565. X              for(k=0; k<= D; k++) { A[k] = B[k] = Init[k]; }
  566. X              r1 = Init1 & B[0]; 
  567. X              A[0] = (Next[B[0]] & CMask) | r1;
  568. X              for(k=1; k<= D; k++) {
  569. X                    r1 = Init1 & B[k];
  570. X                    r2 = (B[k-1] | Next[A[k-1]|B[k-1]]) &r_NO_ERR;
  571. X                    A[k] = (Next[B[k]] & CMask) | r1 | r2;
  572. X              }
  573. X        }
  574. Nextchar: 
  575. X        c = buffer[i];
  576. X        CMask = RMask[c];
  577. X        if(c != Newline)
  578. X        { 
  579. X              r1 = Init1 & A[0];
  580. X              B[0] = (Next[A[0]] & CMask) | r1;
  581. X              r1 = Init1 & A[1];
  582. X              B[1] = (Next[A[1]] & CMask) |                                                          ((A[0] | Next[A[0] | B[0]]) & r_NO_ERR) | r1 ;  
  583. X                     if(D == 1) goto Nextchar1;
  584. X              r1 = Init1 & A[2];
  585. X              B[2] = (Next[A[2]] & CMask) | ((A[1] | Next[A[1] | B[1]]) &r_NO_ERR) | r1 ;  
  586. X                     if(D == 2) goto Nextchar1;
  587. X              r1 = Init1 & A[3];
  588. X              B[3] = (Next[A[3]] & CMask) | ((A[2] | Next[A[2] | B[2]])&r_NO_ERR) | r1 ;  
  589. X                     if(D == 3) goto Nextchar1;
  590. X              r1 = Init1 & A[4];
  591. X              B[4] = (Next[A[4]] & CMask) | ((A[3] | Next[A[3] | B[3]])&r_NO_ERR) | r1 ;  
  592. X              goto Nextchar1;
  593. X        } /* if(NOT Newline) */
  594. X        else {  j++;
  595. X              r1 = Init1 & A[D];               /* match endofline */
  596. X              B[D] = (Next[A[D]] & CMask) | r1;
  597. X              if(TAIL) B[D] = Next[B[D]] | B[D];
  598. X              if((B[D] & 1) ^ INVERSE )  {
  599. X                   if(FILENAMEONLY) {
  600. X                          num_of_matched++;
  601. X                          printf("%s\n", CurrentFileName);
  602. X                          return;
  603. X                   } 
  604. X                   r_output(buffer, i, end, j);
  605. X              }
  606. X              for(k=0; k<= D; k++) { A[k] = B[k] = Init[k]; }
  607. X              r1 = Init1 & A[0]; 
  608. X              B[0] = (Next[A[0]] & CMask) | r1;
  609. X              for(k=1; k<= D; k++) {
  610. X                    r1 = Init1 & A[k];
  611. X                    r2 = (A[k-1] | Next[A[k-1]|B[k-1]])&r_NO_ERR;
  612. X                    B[k] = (Next[A[k]] & CMask) | r1 | r2;
  613. X              }
  614. X        }
  615. Nextchar1: i++;
  616. X    } /* while i < end */
  617. X    strncpy(buffer, buffer+num_read, Maxline);
  618. X  } /* while  read() */
  619. X  return;
  620. X} /* re */
  621. X
  622. X
  623. r_output (buffer, i, end, j) 
  624. int i, end, j; 
  625. CHAR *buffer;
  626. X{
  627. int bp;
  628. X      if(i >= end) return;
  629. X      num_of_matched++;
  630. X      if(COUNT)  return; 
  631. X      if(FNAME) printf("%s: ", CurrentFileName);
  632. X      bp = i-1;
  633. X      while ((buffer[bp] != '\n') && (bp > 0)) bp--;
  634. X      if(LINENUM) printf("%d: ", j); 
  635. X      if(buffer[bp] != '\n') bp = Maxline-1;
  636. X      bp++; 
  637. X      while (bp <= i ) putchar(buffer[bp++]);
  638. X}
  639. X
  640. main(argc, argv)
  641. int argc; char *argv[];
  642. X{
  643. X  int N, M, D=0, fp, fd, i, j; 
  644. X  char c;
  645. X  int filetype;
  646. X  unsigned char Pattern[MAXPAT], OldPattern[MAXPAT], temp[MAXPAT];
  647. X  
  648. X  initial_value();
  649. X  strcpy(Progname, argv[0]);
  650. X  if (argc < 2) usage();
  651. X  Pattern[0] = '\0';
  652. X  while(--argc > 0 && (*++argv)[0] == '-') {
  653. X     c = *(argv[0]+1); 
  654. X     switch(c) {
  655. X       case 'c' : COUNT = ON;    /* output the # of matched */
  656. X                  break;
  657. X       case 's' : SILENT = ON;   /* silent mode  */
  658. X                  break;
  659. X       case 'p' : I = 0;         /* insertion cost is 0 */
  660. X                  break; 
  661. X       case 'x' : WHOLELINE = ON;  /* match the whole line */
  662. X          if(WORDBOUND) {
  663. X            fprintf(stderr, "%s: illegal option combination\n", Progname);
  664. X            exit(2);
  665. X          }
  666. X                  break;
  667. X       case 'L' : break;
  668. X       case 'd' : DELIMITER = ON;  /* user defines delimiter */
  669. X                  if(argc <= 1) usage();
  670. X                  if (argv[0][2] == '\0') {/* space after -d option */
  671. X                    argv++;
  672. X                    if ((D_length = strlen(argv[0])) > MaxDelimit) {
  673. X                      fprintf(stderr, "%s: delimiter pattern too long\n", Progname);
  674. X                      exit(2);
  675. X                    }
  676. X                    D_pattern[0] = '<';
  677. X                    strcpy(D_pattern+1, argv[0]);
  678. X                    argc--;
  679. X                  } else {
  680. X                    if ((D_length = strlen(argv[0]+2)) > MaxDelimit) {
  681. X                      fprintf(stderr, "%s: delimiter pattern too long\n", Progname);
  682. X                      exit(2);
  683. X                    }
  684. X                    D_pattern[0] = '<';
  685. X                    strcpy(D_pattern+1, argv[0]+2);
  686. X                  } /* else */
  687. X                  strcat(D_pattern, ">; ");
  688. X                  D_length++;   /* to count ';' as one */
  689. X                  break;
  690. X       case 'e' : argc--;
  691. X          if(argc == 0) {
  692. X            fprintf(stderr, "%s: the pattern should immediately follow the -e option\n", Progname);
  693. X            usage();
  694. X          }
  695. X          if((++argv)[0][0] == '-') {
  696. X                       Pattern[0] = '\\';
  697. X                       strcat(Pattern, (argv)[0]);
  698. X                  }
  699. X                  else strcat(Pattern, argv[0]);
  700. X                  break;
  701. X       case 'f' : PAT_FILE = ON;
  702. X          argv++;
  703. X          argc--;
  704. X          if((fp = open(argv[0], 0)) < 0) {
  705. X            fprintf(stderr, "%s: Can't open pattern file %s\n", Progname, argv[0]);
  706. X            exit(2);
  707. X          }
  708. X          break;
  709. X       case 'h' : NOFILENAME = ON;
  710. X                  break;
  711. X       case 'i' : NOUPPER = ON;
  712. X                  break;
  713. X       case 'k' : argc--;
  714. X          if(argc == 0) {
  715. X            fprintf(stderr, "%s: the pattern should immediately follow the -k option\n", Progname);
  716. X            usage();
  717. X          }
  718. X          CONSTANT = ON;
  719. X          argv++;
  720. X          strcat(Pattern, argv[0]);
  721. X          if(argc > 1 && argv[1][0] == '-') {
  722. X            fprintf(stderr, "%s: -k should be the last option in the command\n", Progname);
  723. X            exit(2);
  724. X          }
  725. X          break;
  726. X       case 'l' : FILENAMEONLY = ON;
  727. X                  break;
  728. X       case 'n' : LINENUM = ON;  /* output prefixed by line no*/
  729. X                  break;
  730. X       case 'v' : INVERSE = ON;  /* output no-matched lines */
  731. X                  break;
  732. X       case 't' : OUTTAIL = ON;  /* output from tail of delimiter */
  733. X                  break;
  734. X       case 'B' : BESTMATCH = ON;
  735. X                  break;
  736. X       case 'w' : WORDBOUND = ON;/* match to words */
  737. X          if(WHOLELINE) {
  738. X            fprintf(stderr, "%s: illegal option combination\n", Progname);
  739. X            exit(2);
  740. X          }
  741. X                  break;
  742. X       case 'I' : I = atoi(argv[0]+2);  /* Insertion Cost */
  743. X              JUMP = ON;
  744. X                  break;
  745. X       case 'S' : S = atoi(argv[0]+2);  /* Substitution Cost */
  746. X                  JUMP = ON;
  747. X                  break;
  748. X       case 'D' : DD = atoi(argv[0]+2); /* Deletion Cost */
  749. X                  JUMP = ON;
  750. X                  break;
  751. X       case 'G' : FILEOUT = ON; 
  752. X          COUNT = ON;
  753. X          break;
  754. X       default  : if (isdigit(c)) {
  755. X            APPROX = ON;
  756. X                    D = atoi(argv[0]+1);
  757. X                    if (D > MaxError) {
  758. X                      fprintf(stderr,"%s: the maximum number of errors is %d \n", Progname, MaxError);
  759. X                      exit(2);
  760. X                    }
  761. X                  } else {
  762. X                    fprintf(stderr, "%s: illegal option  -%c\n",Progname, c);
  763. X            usage();
  764. X                  }
  765. X       } /* switch(c) */
  766. X  } /* while (--argc > 0 && (*++argv)[0] == '-') */
  767. X
  768. X  if (FILENAMEONLY && NOFILENAME) {
  769. X    fprintf(stderr, "%s: -h and -l options are mutually exclusive\n",Progname);
  770. X  }
  771. X  if (COUNT && (FILENAMEONLY || NOFILENAME)) {
  772. X      FILENAMEONLY = OFF; 
  773. X      if(!FILEOUT) NOFILENAME = OFF;
  774. X  }
  775. X  if (!(PAT_FILE) && Pattern[0] == '\0') { /* Pattern not set with -e option */
  776. X    if (argc == 0) usage();
  777. X    strcpy(Pattern, *argv); 
  778. X    argc--;
  779. X    argv++;
  780. X  }
  781. X  Numfiles = 0;  
  782. X  fd = 3; /* make sure it's not 0 */
  783. X  if (argc == 0)  /* check Pattern against stdin */
  784. X    fd = 0;
  785. X  else {
  786. X    if (!(Textfiles = (CHAR **)malloc(argc * sizeof(CHAR *) ))) {
  787. X      fprintf(stderr, "%s: malloc failure (you probably don't have enough memory)\n", Progname);
  788. X      exit(2);
  789. X    }
  790. X    while (argc--)  { /* one or more filenames on command line -- put
  791. X                          the valid filenames in a array of strings */    
  792. X/*
  793. X      if ((filetype = check_file(*argv)) != ISASCIIFILE) {
  794. X    if(filetype == NOSUCHFILE) fprintf(stderr,"%s: %s: no such file or directory\n",Progname,*argv);
  795. X        argv++;
  796. X*/
  797. X      
  798. X      if ((filetype = check_file(*argv)) == NOSUCHFILE) {
  799. X    if(filetype == NOSUCHFILE) fprintf(stderr,"%s: %s: no such file or directory\n",Progname,*argv);
  800. X        argv++;
  801. X      } else { /* file is ascii*/
  802. X        if (!(Textfiles[Numfiles] = (CHAR *)malloc((strlen(*argv)+1)))) {
  803. X          fprintf(stderr, "%s: malloc failure (you probably don't have enough memory)\n", Progname);
  804. X          exit(2);
  805. X        }
  806. X        strcpy(Textfiles[Numfiles++], *argv++);
  807. X       } /* else */
  808. X     } /* while (argc--) */
  809. X  } /* else */
  810. X  checksg(Pattern, D);       /* check if the pattern is simple */
  811. X  strcpy(OldPattern, Pattern);
  812. X  if (SGREP == 0) {
  813. X      preprocess(D_pattern, Pattern);
  814. X      strcpy(old_D_pat, D_pattern);
  815. X      M = maskgen(Pattern, D);
  816. X  }
  817. X  else M = strlen(OldPattern);
  818. X  if (PAT_FILE)  prepf(fp);
  819. X  if (Numfiles > 1) FNAME = ON;
  820. X  if (NOFILENAME) FNAME = 0;
  821. X  num_of_matched = 0;
  822. X  compat(); /* check compatibility between options */
  823. X  if (fd == 0) {
  824. X    if(FILENAMEONLY) {
  825. X       fprintf(stderr, "%s: -l option is not compatible with standard input\n", Progname);
  826. X       exit(2);  
  827. X    }
  828. X    if(PAT_FILE) mgrep(fd);
  829. X    else {
  830. X        if(SGREP) sgrep(OldPattern, strlen(OldPattern), fd, D);
  831. X       else      bitap(old_D_pat, Pattern, fd, M, D);
  832. X    }
  833. X    if (COUNT) {
  834. X    if(INVERSE && PAT_FILE) printf("%d\n", total_line-num_of_matched);
  835. X    else printf("%d\n", num_of_matched);
  836. X    }
  837. X  } 
  838. X  else {
  839. X    for (i = 0; i < Numfiles; i++, close(fd), num_of_matched = 0) {
  840. X          strcpy(CurrentFileName, Textfiles[i]);
  841. X          if ((fd = open(Textfiles[i], 0)) <= 0) {
  842. X            fprintf(stderr, "%s: can't open file %s\n",Progname, Textfiles[i]);
  843. X          } 
  844. X    else { 
  845. X             if(PAT_FILE) mgrep(fd);
  846. X             else {
  847. X                     if(SGREP) sgrep(OldPattern, strlen(OldPattern), fd, D);
  848. X                     else      bitap(old_D_pat, Pattern, fd, M, D);
  849. X            }
  850. X            if (num_of_matched) NOMATCH = OFF;
  851. X            if (COUNT && !FILEOUT) {
  852. X            if(INVERSE && PAT_FILE) {
  853. X                     if(FNAME) printf("%s: %d\n", CurrentFileName, total_line - num_of_matched);
  854. X                else printf("%d\n", total_line - num_of_matched);
  855. X            }
  856. X            else {
  857. X                     if(FNAME) printf("%s: %d\n", CurrentFileName, num_of_matched);
  858. X                else printf("%d\n", num_of_matched);
  859. X            }
  860. X            }  /* if COUNT */
  861. X        if(FILEOUT && num_of_matched) {
  862. X            file_out(CurrentFileName);
  863. X        }
  864. X          } /* else */
  865. X    }  /* for i < Numfiles */
  866. X    if(NOMATCH && BESTMATCH) {
  867. X    if(WORDBOUND || WHOLELINE || LINENUM || INVERSE) { 
  868. X        SGREP = 0;    
  869. X              preprocess(D_pattern, Pattern);
  870. X              strcpy(old_D_pat, D_pattern);
  871. X              M = maskgen(Pattern, D);
  872. X    }
  873. X    COUNT=ON; D=1;
  874. X    while(D<M && D<=MaxError && num_of_matched == 0) {
  875. X            for (i = 0; i < Numfiles; i++, close(fd)) {
  876. X                  strcpy(CurrentFileName, Textfiles[i]);
  877. X                  if ((fd = open(Textfiles[i], 0)) > 0) {
  878. X                     if(PAT_FILE) mgrep(fd);
  879. X                     else {
  880. X                                 if(SGREP) sgrep(OldPattern,strlen(OldPattern),fd,D);
  881. X                                 else bitap(old_D_pat,Pattern,fd,M,D);
  882. X                      }
  883. X            } 
  884. X           }  /* for i < Numfiles */
  885. X        D++;
  886. X    } /* while */
  887. X    if(num_of_matched > 0) {
  888. X        D--; COUNT = 0;
  889. X        if(D==1) fprintf(stderr, "best match has 1 error, ");
  890. X        else fprintf(stderr, "best match has %d errors, ", D);
  891. X        fflush(stderr);
  892. X        if(num_of_matched == 1) fprintf(stderr,"there is 1 match, output it? (y/n)");
  893. X        else fprintf(stderr,"there are %d matches, output them? (y/n)", num_of_matched);
  894. X        scanf("%c",&c);
  895. X        if(c != 'y') goto CONT;
  896. X            for (i = 0; i < Numfiles; i++, close(fd)) {
  897. X                  strcpy(CurrentFileName, Textfiles[i]);
  898. X                  if ((fd = open(Textfiles[i], 0)) > 0) {
  899. X                     if(PAT_FILE) mgrep(fd);
  900. X                     else {
  901. X                                 if(SGREP) sgrep(OldPattern,strlen(OldPattern),fd,D);
  902. X                                 else bitap(old_D_pat,Pattern,fd,M,D);
  903. X                }
  904. X                  } 
  905. X           }  /* for i < Numfiles */
  906. X        NOMATCH = 0;
  907. X    }
  908. X   }
  909. X }
  910. CONT:
  911. X if(EATFIRST) {
  912. X      printf("\n");
  913. X      EATFIRST = OFF;
  914. X }
  915. X if(NOMATCH) exit(1);
  916. X exit(0);
  917. X} /* end of main() */
  918. X
  919. X       
  920. file_out(fname)
  921. char *fname;
  922. X{
  923. int num_read;
  924. int fd;
  925. int i, len;
  926. CHAR buf[4097];
  927. X    if(FNAME) {
  928. X        len = strlen(fname);
  929. X        putchar('\n');
  930. X        for(i=0; i< len; i++) putchar(':');
  931. X        putchar('\n');
  932. X        printf("%s\n", CurrentFileName);
  933. X        len = strlen(fname);
  934. X        for(i=0; i< len; i++) putchar(':');
  935. X        putchar('\n');
  936. X        fflush(stdout);
  937. X    }
  938. X    fd = open(fname, 0);
  939. X    while((num_read = read(fd, buf, 4096)) > 0) 
  940. X        write(1, buf, num_read);
  941. X}
  942. X
  943. X
  944. usage()
  945. X{
  946. X        fprintf(stderr, "usage: %s [-#cdehiklnpstvwxBDGIS] [-f patternfile] pattern [files]\n", Progname); 
  947. X     printf("\n");    
  948. X    fprintf(stderr, "summary of frequently used options:\n");
  949. X    fprintf(stderr, "-#: find matches with at most # errors\n");
  950. X    fprintf(stderr, "-c: output the number of matched records\n");
  951. X    fprintf(stderr, "-d: define record delimiter\n");
  952. X    fprintf(stderr, "-h: do not output file names\n");
  953. X    fprintf(stderr, "-i: case-insensitive search, e.g., 'a' = 'A'\n");
  954. X    fprintf(stderr, "-l: output the names of files that contain a match\n");
  955. X    fprintf(stderr, "-n: output record prefixed by record number\n");
  956. X    fprintf(stderr, "-v: output those records containing no matches\n");
  957. X    fprintf(stderr, "-w: pattern has to match as a word, e.g., 'win' will not match 'wind'\n");
  958. X    fprintf(stderr, "-B: best match mode. find the closest matches to the pattern\n"); 
  959. X    fprintf(stderr, "-G: output the files that contain a match\n");
  960. X     printf("\n");    
  961. X
  962. X        exit(2);
  963. X}
  964. X
  965. checksg(Pattern, D) 
  966. CHAR *Pattern; int D;
  967. X{                          
  968. X  char c;
  969. X  int i, m;
  970. X  m = strlen(Pattern);
  971. X  if(!(PAT_FILE) && m <= D) {
  972. X      fprintf(stderr, "%s: size of pattern must be greater than number of errors\n", Progname);
  973. X      exit(2);
  974. X  }
  975. X  SIMPLEPATTERN = ON;
  976. X  for (i=0; i < m; i++) 
  977. X  {
  978. X      switch(Pattern[i])
  979. X      {
  980. X         case ';' : SIMPLEPATTERN = OFF; break;
  981. X         case ',' : SIMPLEPATTERN = OFF; break;
  982. X         case '.' : SIMPLEPATTERN = OFF; break;
  983. X         case '*' : SIMPLEPATTERN = OFF; break;
  984. X         case '-' : SIMPLEPATTERN = OFF; break;
  985. X         case '[' : SIMPLEPATTERN = OFF; break;
  986. X         case ']' : SIMPLEPATTERN = OFF; break;
  987. X         case '(' : SIMPLEPATTERN = OFF; break;
  988. X         case ')' : SIMPLEPATTERN = OFF; break;
  989. X         case '<' : SIMPLEPATTERN = OFF; break;
  990. X         case '>' : SIMPLEPATTERN = OFF; break;
  991. X         case '^' : if(D > 0) SIMPLEPATTERN = OFF; 
  992. X            break;
  993. X         case '$' : if(D > 0) SIMPLEPATTERN = OFF; 
  994. X            break;
  995. X         case '|' : SIMPLEPATTERN = OFF; break;
  996. X         case '#' : SIMPLEPATTERN = OFF; break;
  997. X         case '\\' : SIMPLEPATTERN = OFF; break;
  998. X         default  : break;
  999. X      }
  1000. X  }
  1001. X  if (CONSTANT) SIMPLEPATTERN = ON;
  1002. X  if (SIMPLEPATTERN == OFF) return;
  1003. X  if (NOUPPER && D) return;     
  1004. X  if (JUMP == ON) return;
  1005. X  if (I == 0) return;
  1006. X  if (LINENUM) return;
  1007. X  if (DELIMITER) return;   
  1008. X  if (INVERSE) return;
  1009. X  if (WORDBOUND && D > 0) return;  
  1010. X  if (WHOLELINE && D > 0) return;  
  1011. X  if (SILENT) return;     /* REMINDER: to be removed */
  1012. X  SGREP = ON;
  1013. X  if(m >= 16) DNA = ON;
  1014. X  for(i=0; i<m; i++) {
  1015. X    c = Pattern[i];
  1016. X    if(c == 'a' || c == 'c' || c == 't' || c == 'g' ) ;
  1017. X    else DNA = OFF;
  1018. X  }
  1019. X  return;
  1020. X}
  1021. X
  1022. output (buffer, i1, i2, j)  
  1023. register CHAR *buffer; int i1, i2, j;
  1024. X{
  1025. register CHAR *bp, *outend;
  1026. X    if(i1 > i2) return;
  1027. X        num_of_matched++;
  1028. X        if(COUNT)  return;
  1029. X        if(SILENT) return;
  1030. X    if(OUTTAIL) {
  1031. X              i1 = i1 + D_length;
  1032. X              i2 = i2 + D_length;
  1033. X        }
  1034. X        if(DELIMITER) j = j+1;
  1035. X        if(FIRSTOUTPUT) {
  1036. X           if (buffer[i1] == '\n')  {
  1037. X               i1++;
  1038. X               EATFIRST = ON;
  1039. X           }
  1040. X           FIRSTOUTPUT = 0;
  1041. X        }
  1042. X        if(TRUNCATE) {
  1043. X           fprintf(stderr, "WARNING!!!  some lines have been truncated in output record #%d\n", num_of_matched-1);
  1044. X        }
  1045. X        while(buffer[i1] == '\n' && i1 <= i2) {
  1046. X       printf("\n");
  1047. X           i1++;
  1048. X        }
  1049. X        if(FNAME == ON) printf("%s: ", CurrentFileName);
  1050. X        if(LINENUM) printf("%d: ", j-1); 
  1051. X    bp = buffer + i1;
  1052. X    outend = buffer + i2;
  1053. X    while(bp <= outend) putchar(*bp++);
  1054. X}
  1055. X
  1056. X/* end of main.c */
  1057. END_OF_FILE
  1058. if test 35404 -ne `wc -c <'main.c'`; then
  1059.     echo shar: \"'main.c'\" unpacked with wrong size!
  1060. fi
  1061. # end of 'main.c'
  1062. fi
  1063. if test -f 'sgrep.c' -a "${1}" != "-c" ; then 
  1064.   echo shar: Will not clobber existing file \"'sgrep.c'\"
  1065. else
  1066. echo shar: Extracting \"'sgrep.c'\" \(18635 characters\)
  1067. sed "s/^X//" >'sgrep.c' <<'END_OF_FILE'
  1068. X/* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  1069. X#include <stdio.h>
  1070. X#define MAXSYM  256
  1071. X#define MAXMEMBER 8192
  1072. X#define    CHARTYPE    unsigned char
  1073. X#define MaxError 20
  1074. X#define MAXPATT 256
  1075. X#define MAXLINE 1024
  1076. X#define MaxCan  2048
  1077. X#define BLOCKSIZE    8192
  1078. X#define MAX_SHIFT_2  4096
  1079. X#define ON      1
  1080. X#define LOG_ASCII 8
  1081. X#define LOG_DNA  3
  1082. X#define MAXMEMBER_1 65536
  1083. X#define LONG_EXAC  20
  1084. X#define LONG_APPX  24
  1085. X#define W_DELIM    2
  1086. X
  1087. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  1088. extern DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  1089. X         p_size > 16  */
  1090. extern WORDBOUND, WHOLELINE, NOUPPER;
  1091. extern unsigned char CurrentFileName[],  Progname[]; 
  1092. extern unsigned Mask[];
  1093. extern unsigned endposition;
  1094. X
  1095. unsigned char BSize;                /* log_c m   */
  1096. unsigned char char_map[MAXSYM];
  1097. X    
  1098. X
  1099. X/* data area */
  1100. int shift_1;
  1101. CHARTYPE SHIFT[MAXSYM];
  1102. CHARTYPE MEMBER[MAXMEMBER];
  1103. CHARTYPE pat[MAXPATT];
  1104. unsigned Hashmask;
  1105. char MEMBER_1[MAXMEMBER_1];
  1106. CHARTYPE TR[MAXSYM];
  1107. X
  1108. char_tr(pat, m)
  1109. X    unsigned char *pat;
  1110. X    int *m;
  1111. X{
  1112. int i;
  1113. unsigned char temp[MAXPATT];
  1114. X    for(i=0; i<MAXSYM; i++) TR[i] = i;
  1115. X    if(NOUPPER) {
  1116. X        for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A';
  1117. X    }
  1118. X    if(WORDBOUND) { /* SUN: To be added to be more complete */
  1119. X        TR['\n'] = TR['\t'] = TR[' '] = TR[','] = TR[';'] = TR[':'] = 
  1120. X            TR['!'] = TR['"'] = TR['?'] = TR['<'] = TR['>'] = 
  1121. X        TR['='] = TR['['] = TR[']'] = TR['\''] =
  1122. X            TR['('] = TR[')'] = TR['$'] = TR['/'] = TR['\\'] = W_DELIM;
  1123. X    }
  1124. X    if(WHOLELINE) {
  1125. X        memcpy(temp, pat, *m);
  1126. X        pat[0] = '\n';
  1127. X        memcpy(pat+1, temp, *m);
  1128. X        pat[*m+1] = '\n';
  1129. X        pat[*m+2] = 0;
  1130. X        *m = *m + 2;
  1131. X    }
  1132. X}
  1133. X
  1134. sgrep(pat, m, fd, D)
  1135. CHARTYPE *pat;  int fd, m, D;
  1136. X{ 
  1137. X    CHARTYPE text[BLOCKSIZE+2*MAXLINE+MAXPATT]; /* input text stream */
  1138. X    int offset = 2*MAXLINE;
  1139. X    int buf_end, num_read, i, start, end, residue = 0;
  1140. X    if(pat[0] == '^' || pat[0] == '$') pat[0] = '\n';
  1141. X    if(pat[m-1] == '^' || pat[m-1] == '$') pat[m-1] = '\n';
  1142. X    char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */
  1143. X    text[offset-1] = '\n';  /* initial case */
  1144. X    for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  1145. X    start = offset;   
  1146. X    if(WHOLELINE) start--;
  1147. X    if(m >= MAXPATT) {
  1148. X         fprintf(stderr, "%s: pattern too long\n", Progname);
  1149. X         exit(2);
  1150. X    }
  1151. X    if(D == 0) {
  1152. X    if(m > LONG_EXAC) m_preprocess(pat);
  1153. X    else prep_bm(pat, m);
  1154. X    }
  1155. X    else if (DNA) prep4(pat, m);
  1156. X     else     if(m >= LONG_APPX) am_preprocess(pat);
  1157. X        else {
  1158. X            prep(pat, m, D);
  1159. X            initmask(pat, Mask, m, 0, &endposition); 
  1160. X        }
  1161. X    for(i=1; i<=m; i++) text[BLOCKSIZE+offset+i] = pat[m-1];
  1162. X        /* to make sure the skip loop in bm() won't go out of bound */
  1163. X    while( (num_read = read(fd, text+offset, BLOCKSIZE)) > 0) 
  1164. X    {
  1165. X       buf_end = end = offset + num_read -1 ;
  1166. X       if(num_read < BLOCKSIZE) if(text[end] != '\n') text[++end] = '\n';
  1167. X       while(text[end]  != '\n' && end > offset) end--;
  1168. X       residue = buf_end - end + 1 ;
  1169. X       text[start-1] = '\n';
  1170. X       if(D==0)  {
  1171. X        if(m > LONG_EXAC) monkey(pat, m, text+start, text+end);
  1172. X        else bm(pat, m, text+start, text+end);
  1173. X       }
  1174. X       else {
  1175. X        if(DNA) monkey4( pat, m, text+start, text+end, D  );
  1176. X        else {
  1177. X          if(m >= LONG_APPX) a_monkey(pat, m, text+start, text+end, D);
  1178. X          else       agrep(pat, m, text+start, text+end, D);
  1179. X        }
  1180. X       }
  1181. X       if(FILENAMEONLY && num_of_matched) {
  1182. X            printf("%s\n", CurrentFileName);
  1183. X            return; }
  1184. X       start = offset - residue ;
  1185. X       if(start < MAXLINE) {
  1186. X            start = MAXLINE; 
  1187. X       }
  1188. X       strncpy(text+start, text+end, residue);
  1189. X       start++;
  1190. X    } /* end of while(num_read = ... */
  1191. X    return;
  1192. X} /* end sgrep */
  1193. X
  1194. X/* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  1195. pat[m-1] such that the skip loop is guaranteed to terminated */
  1196. X
  1197. bm(pat, m, text, textend)
  1198. X    CHARTYPE *text, *textend, *pat;  int m;
  1199. X{
  1200. register int shift;
  1201. register int  m1, j, d1; 
  1202. X
  1203. X/*
  1204. printf("%d\t", textend - text);
  1205. printf("%c, %c", *text, *textend);
  1206. X*/
  1207. X
  1208. d1 = shift_1;    /* at least 1 */
  1209. m1 = m - 1;
  1210. shift = 0;       
  1211. while (text <= textend) {
  1212. X    shift = SHIFT[*(text += shift)];
  1213. X    while(shift) {          
  1214. X        shift = SHIFT[*(text += shift)];
  1215. X        shift = SHIFT[*(text += shift)];
  1216. X        shift = SHIFT[*(text += shift)];
  1217. X    }
  1218. X        j = 0;
  1219. X        while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  1220. X            if(++j == m)  break;       /* if statement can be
  1221. X                            saved, but for safty ... */
  1222. X        }
  1223. X            if (j == m ) { 
  1224. X            if(text > textend) return;
  1225. X            if(WORDBOUND) {
  1226. X                if(TR[*(text+1)] != W_DELIM) goto CONT;
  1227. X                if(TR[*(text-m)] != W_DELIM) goto CONT;
  1228. X            }
  1229. X            num_of_matched++;
  1230. X            if(FILENAMEONLY) return;
  1231. X            if(!(COUNT)) {
  1232. X                if(FNAME) printf("%s: ", CurrentFileName);
  1233. X                while(*(--text) != '\n');
  1234. X                while(*(++text) != '\n') putchar(*(text));
  1235. X                putchar(*text);
  1236. X            }
  1237. X            else { while(*text != '\n') text++; } 
  1238. CONT:
  1239. X            shift = 1;
  1240. X                }
  1241. X        else shift = d1;
  1242. X  }
  1243. return;
  1244. X}
  1245. X
  1246. X  
  1247. X/* initmask() initializes the mask table for the pattern                    */ 
  1248. X/* endposition is a mask for the endposition of the pattern                 */
  1249. X/* endposition will contain k mask bits if the pattern contains k fragments */
  1250. initmask(pattern, Mask, m, D, endposition)
  1251. CHARTYPE *pattern; unsigned *Mask; register int m, D; unsigned *endposition;
  1252. X{
  1253. X  register unsigned Bit1, c;
  1254. X  register int i, j, frag_num;
  1255. X
  1256. X  Bit1 = 1 << 31;    /* the first bit of Bit1 is 1, others 0.  */
  1257. X  frag_num = D+1; *endposition = 0;
  1258. X  for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  1259. X  *endposition = *endposition >> (m - frag_num);
  1260. X  for(i = 0; i < m; i++) 
  1261. X          if (pattern[i] == '^' || pattern[i] == '$') {
  1262. X              pattern[i] = '\n'; 
  1263. X          }
  1264. X  for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  1265. X  for(i = 0; i < m; i++)     /* initialize the mask table */
  1266. X  {  c = pattern[i];
  1267. X     for ( j = 0; j < m; j++)
  1268. X           if( c == pattern[j] )
  1269. X               Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  1270. X  }
  1271. X}
  1272. X
  1273. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  1274. X    CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  1275. X    register int M, D;
  1276. X{
  1277. register int i, j, k, p, shift;
  1278. register unsigned m;
  1279. unsigned hash, b_size = 3;
  1280. X    m = M/(D+1);
  1281. X    p = M - m*(D+1);
  1282. X    for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  1283. X    for (i = M-1; i>=p ; i--) {
  1284. X        shift = (M-1-i)%m;
  1285. X        hash = Pattern[i];
  1286. X        if(SHIFT[hash] > shift) SHIFT[hash] = shift;
  1287. X    }
  1288. X#ifdef DEBUG
  1289. X    for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  1290. X    printf("\n");
  1291. X#endif
  1292. X    shift_1 = m;
  1293. X    for(i=0; i<D+1; i++) {
  1294. X        j = M-1 - m*i;
  1295. X        for(k=1; k<m; k++) {
  1296. X            for(p=0; p<D+1; p++) 
  1297. X                if(Pattern[j-k] == Pattern[M-1-m*p]) 
  1298. X                    if(k < shift_1) shift_1 = k;
  1299. X        }
  1300. X    }
  1301. X#ifdef DEBUG
  1302. X    printf("\nshift_1 = %d", shift_1);
  1303. X#endif
  1304. X    if(shift_1 == 0) shift_1 = 1;
  1305. X    for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  1306. X    if (m < 3) b_size = m;
  1307. X    for(i=0; i<D+1; i++) {
  1308. X        j = M-1 - m*i;
  1309. X        hash = 0;
  1310. X        for(k=0; k<b_size; k++) {
  1311. X            hash = (hash << 2) + Pattern[j-k];
  1312. X        }
  1313. X#ifdef DEBUG
  1314. X    printf(" hash = %d,", hash);
  1315. X#endif
  1316. X        MEMBER[hash] = 1;
  1317. X    }
  1318. X}
  1319. X
  1320. X
  1321. agrep( pat, M, text, textend, D ) 
  1322. int M, D ; register CHARTYPE *text, *textend, *pat;
  1323. X{
  1324. X  register int i;
  1325. X  register int m = M/(D+1);
  1326. X  register CHARTYPE *textstart;
  1327. X  register int shift, HASH;
  1328. X  int  j=0, k, m1, d1;
  1329. X  int  n, cdx;
  1330. X  int  Candidate[MaxCan][2], round, lastend=0;
  1331. X  unsigned R1[MaxError+1], R2[MaxError+1]; 
  1332. X  register unsigned int r1, endpos, c; 
  1333. X  unsigned currentpos;
  1334. X  unsigned Bit1;
  1335. X  unsigned r_newline;
  1336. X
  1337. X  Candidate[0][0] = Candidate[0][1] = 0; 
  1338. X  d1 = shift_1;
  1339. X  cdx = 0;
  1340. X  if(m < 3) r1 = m;
  1341. X  else r1 = 3;
  1342. X  textstart = text;
  1343. X  shift = m-1;
  1344. X  while (text < textend) {
  1345. X    shift = SHIFT[*(text += shift)];
  1346. X    while(shift) {
  1347. X        shift = SHIFT[*(text += shift)];
  1348. X        shift = SHIFT[*(text += shift)];
  1349. X    }
  1350. X        j = 1; HASH = *text;
  1351. X        while(j < r1) { HASH = (HASH << 2) + *(text-j);
  1352. X                j++; }
  1353. X            if (MEMBER[HASH]) { 
  1354. X            i = text - textstart;
  1355. X                         if((i - M - D - 10) > Candidate[cdx][1]) {     
  1356. X                Candidate[++cdx][0] = i-M-D-2;
  1357. X                              Candidate[cdx][1] = i+M+D; }
  1358. X                         else Candidate[cdx][1] = i+M+D;
  1359. X            shift = d1;
  1360. X                }
  1361. X        else shift = d1;
  1362. X  }
  1363. X
  1364. X
  1365. X  text = textstart;
  1366. X  n = textend - textstart;
  1367. X  r_newline = '\n';
  1368. X  /* for those candidate areas, find the D-error matches                     */
  1369. X  if(Candidate[1][0] < 0) Candidate[1][0] = 0;
  1370. X  endpos = endposition;                /* the mask table and the endposition */
  1371. X  Bit1 = (1 << 31);
  1372. X  for(round = 0; round <= cdx; round++)
  1373. X  {  i = Candidate[round][0] ; 
  1374. X     if(Candidate[round][1] > n) Candidate[round][1] = n;
  1375. X     if(i < 0) i = 0;
  1376. X#ifdef DEBUG
  1377. X     printf("round: %d, start=%d, end=%d, ", round, i, Candidate[round][1]);
  1378. X#endif
  1379. X     R1[0] = R2[0] = ~0;
  1380. X     R1[1] = R2[1] = ~Bit1;
  1381. X     for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];
  1382. X     while (i < Candidate[round][1])                     
  1383. X     {  
  1384. X        c = text[i++];
  1385. X            if(c == r_newline) {
  1386. X               for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  1387. X            }
  1388. X            r1 = Mask[c];
  1389. X            R1[0] = (R2[0] >> 1) | r1;
  1390. X            for(k=1; k<=D; k++)
  1391. X                R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  1392. X            if((R1[D] & endpos) == 0) { 
  1393. X                                    num_of_matched++;
  1394. X                                    if(FILENAMEONLY) { return; }
  1395. X                                    currentpos = i;
  1396. X                                    if(i <= lastend) i = lastend;
  1397. X                                    else {
  1398. X                                       s_output(text, ¤tpos); 
  1399. X                                       i = currentpos; 
  1400. X                                    }
  1401. X                                    lastend = i;
  1402. X                                    for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  1403. X                                  }
  1404. X            c = text[i++];
  1405. X            if(c == r_newline) {
  1406. X                for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  1407. X            }
  1408. X            r1 = Mask[c];
  1409. X            R2[0] = (R1[0] >> 1) | r1;
  1410. X            for(k = 1; k <= D; k++)
  1411. X                R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  1412. X            if((R2[D] & endpos) == 0) { currentpos = i;
  1413. X                                    num_of_matched++;
  1414. X                                    if(FILENAMEONLY) { return; }
  1415. X                                    if(i <= lastend) i = lastend;
  1416. X                                    else {
  1417. X                                       s_output(text, ¤tpos); 
  1418. X                                       i = currentpos; 
  1419. X                                    }
  1420. X                                    lastend = i;
  1421. X                                    for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  1422. X                                  }
  1423. X     }
  1424. X  }
  1425. X  return;
  1426. X}
  1427. X
  1428. s_output (text, i) 
  1429. int *i; CHARTYPE *text;
  1430. X{
  1431. int kk, bp;
  1432. X        if(SILENT) return;
  1433. X        if(COUNT) {
  1434. X        while(text[*i] != '\n') *i = *i + 1; 
  1435. X        return;
  1436. X    }
  1437. X        if(FNAME == ON) printf("%s: ", CurrentFileName);
  1438. X        bp = *i;
  1439. X        while(text[--bp] != '\n');
  1440. X        while(text[++bp] != '\n') putchar(text[bp]);
  1441. X        putchar('\n');
  1442. X        *i = bp;
  1443. X}
  1444. X
  1445. X
  1446. prep_bm(Pattern, m)      
  1447. X    unsigned char *Pattern;
  1448. X    register m;
  1449. X{
  1450. int i, j;
  1451. unsigned hash;
  1452. unsigned char lastc;
  1453. X    for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  1454. X    for (i = m-1; i>=0; i--) {
  1455. X        hash = TR[Pattern[i]];
  1456. X        if(SHIFT[hash] >= m - 1) SHIFT[hash] = m-1-i;
  1457. X    }
  1458. X    shift_1 = m-1;
  1459. X    lastc = TR[Pattern[m-1]];
  1460. X    for (i= m-2; i>=0; i--) {
  1461. X        if(TR[Pattern[i]] == lastc )
  1462. X            { shift_1 = m-1 - i;  i = -1; }
  1463. X    }
  1464. X    if(shift_1 == 0) shift_1 = 1;
  1465. X    if(NOUPPER) for(i='A'; i<='Z'; i++) SHIFT[i] = SHIFT[i +  'a' - 'A'];
  1466. X#ifdef DEBUG
  1467. X    for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  1468. X    for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  1469. X#endif
  1470. X}
  1471. X
  1472. X
  1473. X/* a_monkey() the approximate monkey move */
  1474. X
  1475. a_monkey( pat, m, text, textend, D ) 
  1476. register int m, D ; register CHARTYPE *text, *textend, *pat;
  1477. X{
  1478. register CHARTYPE *oldtext;
  1479. register unsigned hash, i, hashmask, suffix_error; 
  1480. register int  m1 = m-1-D, j, pos; 
  1481. X
  1482. X      hashmask = Hashmask;
  1483. X      oldtext  = text;
  1484. X      while (text < textend) {
  1485. X             text = text+m1;
  1486. X             suffix_error = 0;
  1487. X             while(suffix_error <= D) {
  1488. X            hash = *text--;
  1489. X            while(MEMBER_1[hash]) {
  1490. X                      hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
  1491. X            }
  1492. X            suffix_error++;
  1493. X             }
  1494. X             if(text <= oldtext) {
  1495. X                   if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  1496. X                text = oldtext+pos;
  1497. X                if(text > textend) return;
  1498. X                num_of_matched++;
  1499. X                if(FILENAMEONLY) return;
  1500. X                if(!(COUNT)) {
  1501. X                    if(FNAME) printf("%s: ", CurrentFileName);
  1502. X                    while(*(--text) != '\n');
  1503. X                     while(*(++text) != '\n') putchar(*text);
  1504. X                        printf("\n");
  1505. X                }
  1506. X                else {
  1507. X                    while(*text != '\n') text++;
  1508. X                }
  1509. X               }
  1510. X               else { 
  1511. X                    text = oldtext + m;
  1512. X               }
  1513. X             }
  1514. X             oldtext = text; 
  1515. X      }
  1516. X}
  1517. X
  1518. X/* monkey uses two characters for delta_1 shifting */
  1519. X
  1520. CHARTYPE SHIFT_2[MAX_SHIFT_2];
  1521. X
  1522. monkey( pat, m, text, textend  ) 
  1523. register int m  ; register CHARTYPE *text, *textend, *pat;
  1524. X{
  1525. register unsigned hash, i; 
  1526. register CHARTYPE shift;
  1527. register int  m1, j; 
  1528. register unsigned r_newline;
  1529. X
  1530. r_newline = '\n';
  1531. X
  1532. X  m1 = m - 1;
  1533. X  text = text+m1;
  1534. X  while (text < textend) {
  1535. X    hash = *text;
  1536. X    hash = (hash << 3) + *(text-1);
  1537. X    shift = SHIFT_2[hash];
  1538. X    while(shift) {
  1539. X        text = text + shift;
  1540. X        hash = (*text << 3) + *(text-1);
  1541. X        shift = SHIFT_2[hash];
  1542. X    }
  1543. X    j = 0;
  1544. X    while(TR[pat[m1 - j]] == TR[*(text - j)]) { if(++j == m) break; }
  1545. X    if (j == m ) { 
  1546. X        if(text >= textend) return;
  1547. X                num_of_matched++;
  1548. X                if(FILENAMEONLY)  return;
  1549. X            if(COUNT) {
  1550. X              while (*text != r_newline) text++;
  1551. X              text--;
  1552. X        }
  1553. X        else {
  1554. X              if(FNAME) printf("%s: ", CurrentFileName);
  1555. X                          while(*(--text) != r_newline);
  1556. X                          while(*(++text) != r_newline) putchar(*text);
  1557. X              printf("\n");
  1558. X              text--;
  1559. X        }
  1560. X        }
  1561. X    text++;
  1562. X  }
  1563. X}
  1564. X 
  1565. am_preprocess(Pattern)
  1566. CHARTYPE *Pattern;
  1567. X{
  1568. int i, j, m;
  1569. unsigned hash;
  1570. X    m = strlen(Pattern);
  1571. X    for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
  1572. X    for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
  1573. X    for (i = m-1; i>=0; i--) {
  1574. X        MEMBER_1[Pattern[i]] = 1;
  1575. X        }
  1576. X    for (i = m-1; i > 0; i--) {
  1577. X           MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
  1578. X    }
  1579. X}
  1580. X
  1581. X
  1582. verify(m, n, D, pat, text)
  1583. register int m, n, D;
  1584. CHARTYPE *pat, *text;
  1585. X{   
  1586. X    int A[MAXPATT], B[MAXPATT];
  1587. X    register int last = D;      
  1588. X    register int cost = 0;  
  1589. X    register int k, i, c;
  1590. X    register int m1 = m+1;
  1591. X    CHARTYPE *textend = text+n;
  1592. X    CHARTYPE *textbegin = text;
  1593. X
  1594. X   for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
  1595. X   while (text < textend)
  1596. X   {
  1597. X       for (k = 1; k <= last; k++)
  1598. X       {
  1599. X           cost = B[k-1]+1; 
  1600. X           if (pat[k-1] != *text)
  1601. X           {   if (B[k]+1 < cost) cost = B[k]+1; 
  1602. X               if (A[k-1]+1 < cost) cost = A[k-1]+1; }
  1603. X           else cost = cost -1; 
  1604. X           A[k] = cost; 
  1605. X       }
  1606. X       if(pat[last] == *text++) { A[last+1] = B[last]; last++; }
  1607. X       if(A[last] < D) A[last+1] = A[last++]+1;
  1608. X       while (A[last] > D) last = last - 1;
  1609. X       if(last >= m) return(text - textbegin - 1);
  1610. X       if(*text == '\n') {
  1611. X            last = D;
  1612. X        for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1613. X       }
  1614. X       for (k = 1; k <= last; k++)
  1615. X       {
  1616. X           cost = A[k-1]+1; 
  1617. X           if (pat[k-1] != *text)
  1618. X           {   if (A[k]+1 < cost) cost = A[k]+1; 
  1619. X               if (B[k-1]+1 < cost) cost = B[k-1]+1; }
  1620. X           else cost = cost -1; 
  1621. X           B[k] = cost;
  1622. X       }
  1623. X       if(pat[last] == *text++) { B[last+1] = A[last]; last++; }
  1624. X       if(B[last] < D) B[last+1] = B[last++]+1;
  1625. X       while (B[last] > D) last = last -1;
  1626. X       if(last >= m)   return(text - textbegin - 1);
  1627. X       if(*text == '\n') {
  1628. X            last = D;
  1629. X        for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  1630. X       }
  1631. X   }    
  1632. X   return(0);
  1633. X}
  1634. X
  1635. X/* preprocessing for monkey()   */
  1636. X
  1637. m_preprocess(Pattern)
  1638. CHARTYPE *Pattern;
  1639. X{
  1640. int i, j, m;
  1641. unsigned hash;
  1642. X    m = strlen(Pattern);
  1643. X    for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
  1644. X    for (i = m-1; i>=1; i--) {
  1645. X        hash = Pattern[i];
  1646. X        hash = hash << 3;
  1647. X        for (j = 0; j< MAXSYM; j++) {
  1648. X            if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
  1649. X        }
  1650. X        hash = hash + Pattern[i-1];
  1651. X        if(SHIFT_2[hash] >= m - 1) SHIFT_2[hash] = m-1-i;
  1652. X    }
  1653. X    shift_1 = m-1;
  1654. X    for (i= m-2; i>=0; i--) {
  1655. X        if(Pattern[i] == Pattern[m-1] )
  1656. X            { shift_1 = m-1 - i;  i = -1; }
  1657. X    }
  1658. X    if(shift_1 == 0) shift_1 = 1;
  1659. X    SHIFT_2[0] = 0;
  1660. X}
  1661. X
  1662. X/* monkey4() the approximate monkey move */
  1663. X
  1664. char *MEMBER_D;
  1665. X
  1666. monkey4( pat, m, text, textend, D  ) 
  1667. register int m, D ; register unsigned char *text, *pat, *textend;
  1668. X{
  1669. register unsigned char *oldtext;
  1670. register unsigned hash, i, hashmask, suffix_error; 
  1671. register int m1=m-1-D, j, pos; 
  1672. X
  1673. X  hashmask = Hashmask;
  1674. X  oldtext = text ;
  1675. X  while (text < textend) {
  1676. X     text = text + m1;
  1677. X     suffix_error = 0;
  1678. X     while(suffix_error <= D) {
  1679. X    hash = char_map[*text--];
  1680. X    hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  1681. X    while(MEMBER_D[hash]) {
  1682. X          hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  1683. X    }
  1684. X    suffix_error++;
  1685. X     }
  1686. X     if(text <= oldtext) {
  1687. X                   if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  1688. X                text = oldtext+pos;
  1689. X                if(text > textend) return;
  1690. X                num_of_matched++;
  1691. X                if(FILENAMEONLY) return;
  1692. X                if(!(COUNT)) {
  1693. X                    if(FNAME) printf("%s:", CurrentFileName);
  1694. X                    while(*(--text) != '\n');
  1695. X                     while(*(++text) != '\n') putchar(*text);
  1696. X                        printf("\n");
  1697. X                    text++;
  1698. X                }
  1699. X                else {
  1700. X                    while(*text != '\n') text++;
  1701. X                    text++;
  1702. X                }
  1703. X               }
  1704. X               else text = oldtext + m;
  1705. X     }
  1706. X     oldtext = text; 
  1707. X  }
  1708. X}
  1709. X 
  1710. prep4(Pattern, m)
  1711. char *Pattern; int m;
  1712. X{
  1713. int i, j, k;
  1714. unsigned hash;
  1715. X
  1716. for(i=0; i< MAXSYM; i++) char_map[i] = 0;
  1717. char_map['a'] = char_map['A'] = 4;
  1718. char_map['g'] = char_map['g'] = 1;
  1719. char_map['t'] = char_map['t'] = 2;
  1720. char_map['c'] = char_map['c'] = 3;
  1721. char_map['n'] = char_map['n'] = 5;
  1722. X
  1723. X    BSize = blog(4, m);
  1724. X    for (i = 1, Hashmask = 1 ; i<BSize*LOG_DNA; i++) Hashmask = (Hashmask << 1) + 1 ;
  1725. X    MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
  1726. X#ifdef DEBUG
  1727. X    printf("BSize = %d", BSize);
  1728. X#endif 
  1729. X    for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
  1730. X    for (j=0; j < BSize; j++) {
  1731. X            for(i=m-1; i >= j; i--) {
  1732. X               hash = 0;
  1733. X           for(k=0; k <= j; k++) 
  1734. X          hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
  1735. X#ifdef DEBUG
  1736. X           printf("< %d >, ", hash);
  1737. X#endif
  1738. X           MEMBER_D[hash] = 1;
  1739. X            }
  1740. X        }
  1741. X}
  1742. X
  1743. blog(base, m )
  1744. int base, m;
  1745. X{
  1746. int i, exp;
  1747. X    exp = base;
  1748. X        m = m + m/2;
  1749. X    for (i = 1; exp < m; i++) exp = exp * base;
  1750. X    return(i);
  1751. X}
  1752. X
  1753. END_OF_FILE
  1754. if test 18635 -ne `wc -c <'sgrep.c'`; then
  1755.     echo shar: \"'sgrep.c'\" unpacked with wrong size!
  1756. fi
  1757. # end of 'sgrep.c'
  1758. fi
  1759. echo shar: End of archive 3 \(of 3\).
  1760. cp /dev/null ark3isdone
  1761. MISSING=""
  1762. for I in 1 2 3 ; do
  1763.     if test ! -f ark${I}isdone ; then
  1764.     MISSING="${MISSING} ${I}"
  1765.     fi
  1766. done
  1767. if test "${MISSING}" = "" ; then
  1768.     echo You have unpacked all 3 archives.
  1769.     rm -f ark[1-9]isdone
  1770. else
  1771.     echo You still need to unpack the following archives:
  1772.     echo "        " ${MISSING}
  1773. fi
  1774. ##  End of shell archive.
  1775. exit 0
  1776.