home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume2 / bm < prev    next >
Internet Message Format  |  1986-11-30  |  25KB
  1. From: Peter Bain <decvax!watmath!wateng!pdbain>
  2. Subject: bm version 1.1
  3. Newsgroups: mod.sources
  4. Approved: john@genrad.UUCP
  5.  
  6. Mod.sources:  Volume 2, Issue 14
  7. Submitted by: Peter Bain <decvax!watmath!wateng!pdbain>
  8.  
  9.  
  10. This is an fgrep-like Boyer-Moore program called "bm"
  11. which is much faster than the bgrep program posted recently (see below).
  12. I have found that for 99% of the cases bm is entirely sufficient.
  13.  
  14.         */bin/time bgrep Zurich /usr/dict/words
  15.         Zurich
  16.                38.7 real         7.3 user         1.1 sys  
  17.         */bin/time bm Zurich /usr/dict/words 
  18.         Zurich
  19.                 5.2 real         0.9 user         0.5 sys  
  20.         script done on Thu Jul  4 10:09:56 1985
  21.  
  22. 1. Bug fixes from release 1.0:
  23.     - incorrect operation of -x with -c, -s, -l. Fixed.
  24.     - major bug, which was acute with piped input: lines containing
  25.     matches were mangled or missed entirely. Fixed.
  26.     - Some sites were having trouble with externs and #include files
  27.     (the systems at Waterloo run 4.2, and we have not found this,
  28.     but I have changed thing to make everyone happy.
  29.     - Some compilers don't like line 36 of Search.c. I have
  30.     added alternate code (line 39) against this possibility
  31.  
  32.     One site reported abnormally high system time. Installers may want to
  33.     play around with MAXBUFF to optimize.
  34.  
  35. 2. Added features:
  36.     -e: take next argument as a pattern, even if it starts with a '-'
  37.     -h: do not print file names.
  38.  
  39. 3. Why bm is always case-sensitive.
  40.     95% of the time I use a pattern matcher, I know the pattern exactly.
  41.     If not, I use grep. I didn't consider the speed penalty worth it.
  42.  
  43. -------------- snip snip snip -----------------------------------------
  44. : This is a shar archive.    Extract with sh, not csh.
  45. : The rest of this file will extract:
  46. : bm.h bm.c Execute.c Extern.h GetPatFile.c Global.c MakeDesc.c MakeSkip.c MatchFound.c MkDescVec.c MoveResidue.c PrintLine.c PutUsage.c Search.c Makefile README bm.p
  47. echo Extracting bm.h
  48. sed 's/^X//' > bm.h << 'e-o-f'
  49. X#define FIRSTCHAR ' '
  50. X#define MAXCHAR 0377
  51. X#define MAXBUFF 8192
  52. X#define MAXSIZE 100
  53. X#define MAXPATS 100 /* max number of patterns */
  54. X#define min(x,y) (x) < (y) ? (x) : (y)
  55. X#define max(x,y) (x) > (y) ? (x) : (y)
  56. Xstruct PattDesc {
  57. X    int *Skip1, *Skip2; /* pointers to skip tables */
  58. X    char *Pattern;
  59. X    int PatLen; /* pattern length */
  60. X    char *Start;
  61. X    /* starting position of search (at beginning of pattern) */
  62. X    int Success; /* true when pattern found */
  63. X};
  64. e-o-f
  65. echo Extracting bm.c
  66. sed 's/^X//' > bm.c << 'e-o-f'
  67. X#include <stdio.h>
  68. X#include <sys/file.h>
  69. X#include <strings.h>
  70. X#include "bm.h"
  71. X#include "Extern.h"
  72. Xmain(argc,argv)
  73. Xint argc;
  74. Xchar *argv[];
  75. X{
  76. X    /* test driver for grep based on Boyer-Moore algorithm */
  77. X    char BigBuff[MAXBUFF + 2];
  78. X    /*
  79. X    * We leave one extra character at the beginning and end of the buffer,
  80. X    * but don't tell Execute about it. This is so when someone is
  81. X    * scanning the buffer and scans past the end (or beginning)
  82. X    * we are still technically in the buffer (picky, but there ARE
  83. X    * machines which would complain)
  84. X    */
  85. X    int ret = 1, /* return code from Execute */
  86. X        NFiles,
  87. X        NPats; /* number of patterns to search for */
  88. X    char i,
  89. X        *FlagPtr,
  90. X        **OptPtr; /* used to scan command line */
  91. X    int TextFile /* file to search */;
  92. X    struct PattDesc *DescVec[MAXPATS];
  93. X
  94. X    --argc;
  95. X    OptPtr = argv + 1;
  96. X    while ( argc && **OptPtr == '-') {
  97. X        FlagPtr = *OptPtr + 1;
  98. X        while (*FlagPtr) {
  99. X            switch (*FlagPtr) {
  100. X                case 'c': cFlag = 1; break;
  101. X                case 'e': eFlag = 1;
  102. X                    /* get the patterns from next arg */
  103. X                    NPats = MkDescVec(DescVec,*++OptPtr);
  104. X                    --argc;
  105. X                    break;
  106. X                case 'f': fFlag = 1; 
  107. X                    /* read the patterns from a file */
  108. X                    NPats = GetPatFile(*++OptPtr,DescVec);
  109. X                    --argc;
  110. X                    break;
  111. X                case 'l': lFlag = 1; break;
  112. X                case 'n': nFlag = 1; break;
  113. X                case 's': sFlag = 1; break;
  114. X                case 'x': xFlag = 1; break;
  115. X                case 'h': hFlag = 1; break;
  116. X                default:
  117. X                    fprintf(stderr,
  118. X                    "bm: invalid option: -%c \n",
  119. X                    *FlagPtr);
  120. X                    PutUsage();
  121. X                    exit(2);
  122. X            } /* switch */
  123. X            ++FlagPtr;
  124. X        } /* while */
  125. X        ++OptPtr; --argc;
  126. X    } /* while */
  127. X    /* OptPtr now points to patterns */
  128. X    if (!fFlag && !eFlag) {
  129. X        if (!argc) {
  130. X            fprintf(stderr,"bm: no pattern specified\n");
  131. X            PutUsage();
  132. X            exit(2);
  133. X        } else
  134. X            NPats = MkDescVec(DescVec,*OptPtr);
  135. X        ++OptPtr; --argc;
  136. X    }
  137. X    /* OptPtr now points to first file */
  138. X    NFiles = argc;
  139. X    if (!NFiles)
  140. X        ret &= Execute(DescVec,NPats,0,BigBuff+1);
  141. X    else while (argc--) {
  142. X        if ((NFiles > 1) || lFlag) FileName = *OptPtr;
  143. X        if ((TextFile = open(*OptPtr,O_RDONLY,0)) < 0) {
  144. X            fprintf(stderr,"bm: can't open %s\n",*OptPtr);
  145. X            exit(2);
  146. X        } /* if */
  147. X        ret &= Execute(DescVec,NPats,TextFile,BigBuff+1);
  148. X        if (sFlag && !ret)
  149. X            exit(0);
  150. X        ++OptPtr;
  151. X        close(TextFile);
  152. X    } /* while */
  153. X    if (cFlag) printf("%d\n",MatchCount);
  154. X    exit(ret);
  155. X} /* main */
  156. e-o-f
  157. echo Extracting Execute.c
  158. sed 's/^X//' > Execute.c << 'e-o-f'
  159. X#include <stdio.h>
  160. X#include "bm.h"
  161. X#include "Extern.h"
  162. XExecute(DescVec, NPats, TextFile, Buffer)
  163. Xstruct PattDesc *DescVec[]; /* pointers to status vectors for the different
  164. X    * patterns, including skip tables, position in buffer, etc. */
  165. Xint NPats; /* number of patterns */
  166. Xchar Buffer[]; /* holds text from file */
  167. Xint TextFile; /* file to search */
  168. X{
  169. X    int NRead, /* number of chars read from file */
  170. X        NWanted, /* number of chars wanted */
  171. X        NAvail, /* number of chars actually read */
  172. X        BuffSize, /* number of chars in buffer */
  173. X        BuffPos, /* offset of first char in Buffer in TextFile */
  174. X        BuffEx, /* flag to indicate that buffer has been searched */
  175. X        ResSize,
  176. X        /* number of characters in the last, incomplete line */
  177. X        Found, /* flag indicates whether pattern found
  178. X        * completely and all matches printed */
  179. X        Valid; /* was the match "valid", i.e. if -x used,
  180. X        * did the whole line match? */
  181. X    char *BuffEnd; /* pointer to last char of last complete line */
  182. X
  183. X    /* misc working variables */
  184. X    int i;
  185. X
  186. X    /* initialize */
  187. X    ResSize = 0;
  188. X    Found = 0;
  189. X    BuffPos = 0;
  190. X    for (i=0; i < NPats; i++) {
  191. X        DescVec[i] -> Success = 0;
  192. X        DescVec[i] -> Start = Buffer;
  193. X    } /* for */
  194. X    /* now do the searching */
  195. X    do {
  196. X        /* first, read a bufferfull and set up the variables */
  197. X        NWanted = MAXBUFF - ResSize; NRead = 0;
  198. X        do {
  199. X            NAvail =
  200. X               read(TextFile,Buffer + ResSize + NRead, NWanted);
  201. X            if (NAvail == -1) {
  202. X                fprintf(stderr,
  203. X                  "bm: error reading from input file\n");
  204. X                exit(2);
  205. X            } /* if */
  206. X            NRead += NAvail; NWanted -= NAvail;
  207. X        } while (NAvail && NWanted);
  208. X        BuffEx = 0;
  209. X        BuffSize = ResSize + NRead;
  210. X        BuffEnd = Buffer + BuffSize - 1;
  211. X        /* locate the end of the last complete line */
  212. X        while (*BuffEnd != '\n' && BuffEnd >= Buffer)
  213. X            --BuffEnd;
  214. X        if (BuffEnd < Buffer)
  215. X            BuffEnd = Buffer + BuffSize - 1;
  216. X        while (!BuffEx) { /* work through one buffer full */
  217. X            BuffEx = 1; /* set it provisionally, then clear
  218. X            * it if we find the buffer non-empty */
  219. X            for (i=0; i< NPats; i++) {
  220. X                if (!DescVec[i]->Success)
  221. X                /* if the pattern  has not been found */
  222. X                    DescVec[i]-> Success =
  223. X                    Search(DescVec[i]->Pattern,
  224. X                    DescVec[i]->PatLen, Buffer, BuffEnd,
  225. X                    DescVec[i]->Skip1, DescVec[i]->Skip2,
  226. X                    DescVec[i]);
  227. X                if (DescVec[i]->Success){
  228. X                /* if a match occurred */
  229. X                    BuffEx = 0;
  230. X                    Valid = MatchFound(DescVec[i],BuffPos,
  231. X                    Buffer, BuffEnd);
  232. X                    Found |= Valid;
  233. X                    if ((sFlag || lFlag) && Found)
  234. X                        return(0);
  235. X                } /* if */
  236. X            } /* for */
  237. X        } /* while */
  238. X        if(NRead) {
  239. X            ResSize = MoveResidue(DescVec,NPats,Buffer,BuffEnd);
  240. X            BuffPos += BuffSize - ResSize;
  241. X        } /* if */
  242. X    } while (NRead);
  243. X    return(!Found);
  244. X} /* Execute */
  245. e-o-f
  246. echo Extracting Extern.h
  247. sed 's/^X//' > Extern.h << 'e-o-f'
  248. X/* global flags for bm */
  249. Xextern int    cFlag, /* true if we want only a count of matching lines */
  250. X    eFlag, /* indicates that next argument is the pattern */
  251. X    fFlag, /* true if the patterns arew to come from a file */
  252. X    lFlag, /* true if we want a list of files containing the pattern */
  253. X    nFlag, /* true if we want the character offset of the pattern */
  254. X    sFlag, /* true if we want silent mode */
  255. X    xFlag, /* true if we want only lines which match entirely */
  256. X    hFlag, /* true if we want no filenames in output */
  257. X
  258. X    MatchCount; /* count of number of times a search string was found
  259. X    * in the text */
  260. Xextern char *FileName;
  261. e-o-f
  262. echo Extracting GetPatFile.c
  263. sed 's/^X//' > GetPatFile.c << 'e-o-f'
  264. X#include <stdio.h>
  265. X#include <sys/types.h>
  266. X#include <sys/stat.h>
  267. X#include "bm.h"
  268. Xint
  269. XGetPatFile(PatFile, DescVec)
  270. Xchar *PatFile;
  271. Xstruct PattDesc *DescVec[];
  272. X/* read patterns from a file and set up a pattern descriptor vector */
  273. X{
  274. X    extern char *malloc();
  275. X    FILE *PFile;
  276. X    struct stat StatBuff;
  277. X    int PatSize; /* the number of chars in all the patterns */
  278. X    char *PatBuff; /* hold the patterns */
  279. X    if (!(PFile = fopen(PatFile,"r"))) {
  280. X        fprintf(stderr,"bm: can't open pattern file %s\n",PatFile);
  281. X        exit(2);
  282. X    } /* if */
  283. X    /* find out how big the patterns are */
  284. X    if (fstat(fileno(PFile),&StatBuff) == -1) {
  285. X        fprintf(stderr,"bm: can't fstat %s\n",PatFile);
  286. X        exit(2);
  287. X    } /* if */
  288. X    PatSize = StatBuff.st_size;
  289. X    if (!PatSize) {
  290. X        fprintf(stderr,"bm: pattern file is empty\n");
  291. X        exit(2);
  292. X    } /* if */
  293. X    if (!(PatBuff = malloc(PatSize))) {
  294. X           fprintf(stderr,"bm: insufficient memory to store patterns\n");
  295. X        exit(2);
  296. X    } /* if */
  297. X    fread(PatBuff,1,PatSize,PFile); /* get the patterns */
  298. X    /* make sure the patterns are null-terminated. We can't have
  299. X    * nulls in the patterns */
  300. X    if (PatBuff[PatSize-1] == '\n')
  301. X        PatBuff[PatSize-1] = '\0';
  302. X    else
  303. X        PatBuff[PatSize] = '\0';
  304. X    return(MkDescVec(DescVec,PatBuff));
  305. X} /* GetPatFile */
  306. e-o-f
  307. echo Extracting Global.c
  308. sed 's/^X//' > Global.c << 'e-o-f'
  309. X/* global flags for bm */
  310. Xint    cFlag=0, /* true if we want only a count of matching lines */
  311. X    eFlag=0, /* indicates that next argument is the pattern */
  312. X    fFlag=0, /* true if the patterns are to come from a file */
  313. X    lFlag=0, /* true if we want a list of files containing the pattern */
  314. X    nFlag=0, /* true if we want the character offset of the pattern */
  315. X    sFlag=0, /* true if we want silent mode */
  316. X    xFlag=0, /* true if we want only lines which match entirely */
  317. X    hFlag=0, /* true if we want no filenames in output */
  318. X
  319. X    MatchCount=0; /* count of number of times a search string was found
  320. X    * in the text */
  321. Xchar *FileName = 0;
  322. e-o-f
  323. echo Extracting MakeDesc.c
  324. sed 's/^X//' > MakeDesc.c << 'e-o-f'
  325. X#include <stdio.h>
  326. X#include "bm.h"
  327. X#include "Extern.h"
  328. Xextern char * malloc();
  329. X/* makes a pattern descriptor */
  330. Xstruct PattDesc *MakeDesc(Pattern)
  331. Xchar *Pattern;
  332. X{
  333. X    struct PattDesc *Desc;
  334. X    Desc = (struct PattDesc *) malloc(sizeof(struct PattDesc));
  335. X    if (!(Desc->Skip1 = (int *) malloc( sizeof(int) * (MAXCHAR + 1)))){
  336. X        fprintf(stderr,"bm: can't allocate space\n");
  337. X        exit(2);
  338. X    } /* if */
  339. X    if (!(Desc->Skip2 = (int *) malloc(sizeof(int) * strlen(Pattern)))){
  340. X        fprintf(stderr,"bm: can't allocate space\n");
  341. X        exit(2);
  342. X    } /* if */
  343. X    Desc->Pattern=Pattern;
  344. X    Desc->PatLen = strlen(Desc->Pattern);
  345. X    MakeSkip(Desc->Pattern,Desc->Skip1,
  346. X    Desc->Skip2,Desc->PatLen);
  347. X    return(Desc);
  348. X} /* main */
  349. e-o-f
  350. echo Extracting MakeSkip.c
  351. sed 's/^X//' > MakeSkip.c << 'e-o-f'
  352. X#include "bm.h"
  353. Xextern char *malloc();
  354. X
  355. XMakeSkip(Pattern,Skip1,Skip2,PatLen)
  356. Xchar Pattern[];
  357. Xint Skip1[], Skip2[];
  358. Xint PatLen;
  359. X/* generate the skip tables for Boyer-Moore string search algorithm.
  360. X* Skip1 is the skip depending on the character which failed to match
  361. X* the pattern, and Skip2 is the skip depending on how far we got into
  362. X* the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  363. X{
  364. X    int *BackTrack; /* backtracking table for t when building skip2 */
  365. X    int c; /* general purpose constant */
  366. X    int j,k,t,tp; /* indices into Skip's and BackTrack */
  367. X
  368. X    if (!(BackTrack = (int *) malloc(PatLen * (sizeof (int))))){
  369. X        fprintf("bm: can't allocate space\n");
  370. X        exit(2);
  371. X    } /* if */
  372. X    for (c=0; c<=MAXCHAR; ++c)
  373. X        Skip1[c] = PatLen;
  374. X    for (k=0;k<PatLen;k++) {
  375. X        Skip1[Pattern[k]] = PatLen - k - 1;
  376. X        Skip2[k] = 2 * PatLen - k - 1;
  377. X    } /* for */
  378. X    for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  379. X        BackTrack[j] = t;
  380. X        while (t<PatLen && Pattern[j] != Pattern[t]) {
  381. X            Skip2[t] = min(Skip2[t], PatLen - j - 1);
  382. X            t = BackTrack[t];
  383. X        } /* while */
  384. X    } /* for */
  385. X    for (k=0;k<=t;++k)
  386. X        Skip2[k] = min(Skip2[k],PatLen+t-k);
  387. X    tp=BackTrack[t];
  388. X    while(tp<PatLen) {
  389. X        while(t<PatLen) {
  390. X            Skip2[t] = min(Skip2[t],tp-t+PatLen);
  391. X            ++t;
  392. X        } /* while */
  393. X        tp = BackTrack[tp];
  394. X    } /* while */
  395. X    cfree(BackTrack);
  396. X} /* MakeSkip */
  397. e-o-f
  398. echo Extracting MatchFound.c
  399. sed 's/^X//' > MatchFound.c << 'e-o-f'
  400. X#include <stdio.h>
  401. X#include "bm.h"
  402. X#include "Extern.h"
  403. XMatchFound(Desc, BuffPos, Buffer, BuffEnd)
  404. Xstruct PattDesc *Desc; /* state info about search for one string */
  405. Xint BuffPos; /* offset of first char of buffer into the file being searched */
  406. Xchar *Buffer, /* pointer to the first character in the buffer */
  407. X    *BuffEnd; /* pointer to the last character in the buffer */
  408. X{
  409. X    char *MLineBegin, *MLineEnd;
  410. X    Desc->Success = 0;
  411. X    /* Start points to first character after a successful match */
  412. X    MLineBegin = MLineEnd = Desc->Start - 1;
  413. X    while(MLineBegin >=Buffer && *MLineBegin != '\n') --MLineBegin;
  414. X    ++MLineBegin;
  415. X    while( MLineEnd <= BuffEnd && *MLineEnd != '\n') ++MLineEnd;
  416. X    if (MLineEnd > BuffEnd) --MLineEnd;
  417. X    /* fixed 25jun85 pdbain. suppress multiple matches of the same
  418. X    * pattern on one line */
  419. X    Desc->Start = MLineEnd + 1;
  420. X    /* check if exact match */
  421. X    if (xFlag && !( Desc->PatLen == (*MLineEnd != '\n' ? ((MLineEnd -
  422. X    MLineBegin) + 1) : (MLineEnd - MLineBegin))))
  423. X        return(0); /* failure */
  424. X    if (sFlag) return(1);
  425. X    if (cFlag) {
  426. X        ++MatchCount;
  427. X        return(1);
  428. X    } /* if */
  429. X    PrintLine(BuffPos+(Desc->Start-Buffer),MLineBegin,MLineEnd);
  430. X    return(1);
  431. X} /* MatchFound */
  432. e-o-f
  433. echo Extracting MkDescVec.c
  434. sed 's/^X//' > MkDescVec.c << 'e-o-f'
  435. X#include "bm.h"
  436. X#include <strings.h>
  437. X/* scan a newline-separated string of patterns and set up the
  438. X* vector of descriptors, one pattern descriptor per pattern. 
  439. X* Return the number of patterns */
  440. Xint
  441. XMkDescVec(DescVec, Pats)
  442. Xstruct PattDesc *DescVec[];
  443. Xchar *Pats;
  444. X{
  445. X    int NPats = 0;
  446. X    char *EndPat;
  447. X    extern struct PattDesc *MakeDesc();
  448. X    while (*Pats && (EndPat = index(Pats,'\n')) && NPats < MAXPATS) {
  449. X        *EndPat = '\0';
  450. X        DescVec[NPats] = MakeDesc(Pats);
  451. X        Pats = EndPat + 1;
  452. X        ++NPats;
  453. X    } /* while */
  454. X    if (*Pats && NPats < MAXPATS) {
  455. X        DescVec[NPats] = MakeDesc(Pats);
  456. X        ++NPats;
  457. X    } /* if */
  458. X    return(NPats);
  459. X} /* MkDescVec */
  460. e-o-f
  461. echo Extracting MoveResidue.c
  462. sed 's/^X//' > MoveResidue.c << 'e-o-f'
  463. X#include "bm.h"
  464. X/* Moves the text which has not been completely searched at the end of
  465. X* the buffer to the beginning of the buffer
  466. X* and returns number of bytes moved */
  467. Xint MoveResidue(DescVec, NPats,Buffer, BuffEnd)
  468. Xstruct PattDesc *DescVec[];
  469. Xint NPats;
  470. Xchar *Buffer, *BuffEnd;
  471. X{
  472. X    char *FirstStart, *f, *t, *Residue;
  473. X    int ResSize, i;
  474. X    FirstStart = BuffEnd;
  475. X    /* find the earliest point which has not been
  476. X    * completely searched */
  477. X    for (i=0; i < NPats; i++) {
  478. X        FirstStart = 
  479. X            min(FirstStart, DescVec[i]-> Start );
  480. X    } /* for */
  481. X    /* now scan to the beginning of the line containing the
  482. X    * unsearched text */
  483. X    for (Residue = FirstStart; *Residue != '\n' &&
  484. X    Residue >= Buffer; Residue--);
  485. X    if (Residue < Buffer)
  486. X        Residue = FirstStart;
  487. X    else ++Residue;
  488. X    ResSize = (BuffEnd - Residue + 1);
  489. X    /* now move the residue to the beginning of
  490. X    * the file */
  491. X    t = Buffer; f = Residue;
  492. X    for(i=ResSize;i;--i)
  493. X        *t++ = *f++;
  494. X    /* now fix the status vectors */
  495. X    for (i=0; i < NPats; i++) {
  496. X        DescVec[i]->Start -= (Residue - Buffer);
  497. X    } /* for */
  498. X    return(ResSize);
  499. X} /* MoveResidue */
  500. e-o-f
  501. echo Extracting PrintLine.c
  502. sed 's/^X//' > PrintLine.c << 'e-o-f'
  503. X#include <stdio.h>
  504. X#include <strings.h>
  505. X#include "Extern.h"
  506. XPrintLine(OffSet,LineStart,LineEnd)
  507. Xint OffSet; /* offset of LineStart from beginning of file */
  508. Xchar *LineStart,
  509. X    *LineEnd;
  510. X{
  511. X    char OffStr[80];
  512. X    if (lFlag) {
  513. X        if (strlen(FileName) > 76) {
  514. X            fprintf(stderr,"bm: filename too long\n");
  515. X            exit(2);
  516. X        } /* if */
  517. X        sprintf(OffStr,"%s\n",FileName);
  518. X        write(1,OffStr,strlen(OffStr));
  519. X        return;
  520. X    } /* if */
  521. X    if (FileName && !hFlag) {
  522. X        if (strlen(FileName) > 76) {
  523. X            fprintf(stderr,"bm: filename too long\n");
  524. X            exit(2);
  525. X        } /* if */
  526. X        sprintf(OffStr,"%s:",FileName);
  527. X        write(1,OffStr,strlen(OffStr));
  528. X    } /* if */
  529. X    if (nFlag) {
  530. X        sprintf(OffStr,"%d: ",OffSet);
  531. X        write(1,OffStr,strlen(OffStr));
  532. X    } /* if */
  533. X    write(1,LineStart,LineEnd-LineStart+1); 
  534. X    if (*LineEnd != '\n') write (1,"\n",1);
  535. X} /* PrintLine */
  536. e-o-f
  537. echo Extracting PutUsage.c
  538. sed 's/^X//' > PutUsage.c << 'e-o-f'
  539. X#include <stdio.h>
  540. XPutUsage()
  541. X{
  542. X    fprintf(stderr,
  543. X    "bm: search for a given string or strings in a file or files\n");
  544. X    fprintf(stderr,
  545. X    "synopsis: bm [option]* [string(s)] [file]*\n");
  546. X    fprintf(stderr,
  547. X    "options:\n");
  548. X    fprintf(stderr,
  549. X    "-c print only a count of matching lines \n");
  550. X    fprintf(stderr,
  551. X    "-e Take next argument as the pattern\n");
  552. X    fprintf(stderr,
  553. X    "-f PFile read patterns from a file PFile\n");
  554. X    fprintf(stderr,
  555. X    "-h Do not print file names\n");
  556. X    fprintf(stderr,
  557. X    "-l print a list of files containing the pattern(s) \n");
  558. X    fprintf(stderr,
  559. X    "-n print the character offset of the pattern(s) \n");
  560. X    fprintf(stderr,
  561. X    "-s silent mode. Return only success (0) or failure (1)\n");
  562. X    fprintf(stderr,
  563. X    "-x print only lines which match entirely \n");
  564. X} /*PutUsage */
  565. e-o-f
  566. echo Extracting Search.c
  567. sed 's/^X//' > Search.c << 'e-o-f'
  568. X#include "bm.h"
  569. X#include "Extern.h"
  570. Xint Search(Pattern,PatLen,Buffer, EndBuff, Skip1, Skip2, Desc)
  571. Xchar Pattern[];
  572. Xint PatLen;
  573. Xchar Buffer[];
  574. Xchar *EndBuff;
  575. Xint Skip1[], Skip2[];
  576. Xstruct PattDesc *Desc;
  577. X{
  578. X    register char *k, /* indexes text */
  579. X        *j, /* indexes Pattern */
  580. X        *PatBegin; /* register pointing to char
  581. X        * before beginning of Pattern */
  582. X    register int Skip; /* skip distance */
  583. X    char *PatEnd,
  584. X    *BuffEnd; /* pointers to last char in Pattern and Buffer */
  585. X    BuffEnd = EndBuff;
  586. X    PatBegin = Pattern - 1;
  587. X    PatEnd = Pattern + PatLen - 1;
  588. X
  589. X    k = Desc->Start;
  590. X    Skip = PatLen-1;
  591. X    while ( Skip <= (BuffEnd - k) ) {
  592. X        j = PatEnd;
  593. X        k = k + Skip;
  594. X        while (j > PatBegin && *j == *k) {
  595. X            --j; --k;
  596. X        } /* while */
  597. X        if (j< Pattern) {
  598. X            /* found it. Start next search
  599. X            * just after the pattern */
  600. X            Desc -> Start = k + 1 + Desc->PatLen;
  601. X            return(1);
  602. X        } /* if */
  603. X        Skip = max(Skip1[*(unsigned char *)k],Skip2[j-Pattern]);
  604. X    } /* while */
  605. X    Desc->Start = k;
  606. X    return(0);
  607. X} /* Search */
  608. e-o-f
  609. echo Extracting Makefile
  610. sed 's/^X//' > Makefile << 'e-o-f'
  611. XCCFLAGS =  -O
  612. XSOURCES =  bm.h bm.c Execute.c Extern.h\
  613. X    GetPatFile.c Global.c MakeDesc.c MakeSkip.c \
  614. X    MatchFound.c \
  615. X    MkDescVec.c MoveResidue.c PrintLine.c PutUsage.c Search.c
  616. XOBJECTS = bm.o Execute.o \
  617. X    GetPatFile.o Global.o MakeDesc.o MakeSkip.o \
  618. X    MatchFound.o \
  619. X    MkDescVec.o MoveResidue.o Search.o PrintLine.o PutUsage.o
  620. XBASEFILES = $(SOURCES) Makefile README bm.p
  621. Xbm: $(OBJECTS)
  622. X    cc -o bm $(CCFLAGS) $(OBJECTS)
  623. Xinstall: bm
  624. X    rm /usr/public/bm
  625. X    cp bm /usr/public/bm
  626. X    rm /usr/src/public/bm/*
  627. X    cp $(BASEFILES) /usr/src/public/bm
  628. Xshar:
  629. X    /usr/public/shar $(BASEFILES) >bm.shar
  630. Xman: /usr/man/manp/bm.p
  631. X/usr/man/manp/bm.p: bm.p
  632. X    rm -f /usr/man/manp/bm.p
  633. X    cp bm.p /usr/man/manp/bm.p
  634. X    man bm > /dev/null
  635. Xbm.o: bm.c bm.h Extern.h
  636. X    cc -c $(CCFLAGS) bm.c
  637. XPutUsage.o: PutUsage.c bm.h 
  638. X    cc -c $(CCFLAGS) PutUsage.c
  639. XMakeSkip.o: MakeSkip.c bm.h 
  640. X    cc -c $(CCFLAGS) MakeSkip.c
  641. XSearch.o: Search.c bm.h Extern.h
  642. X    cc -c $(CCFLAGS) Search.c
  643. XExecute.o: Execute.c bm.h 
  644. X    cc -c $(CCFLAGS) Execute.c
  645. XMoveResidue.o: MoveResidue.c bm.h Extern.h
  646. X    cc -c $(CCFLAGS) MoveResidue.c
  647. XMatchFound.o: MatchFound.c bm.h Extern.h
  648. X    cc -c $(CCFLAGS) MatchFound.c
  649. XPrintLine.o: PrintLine.c Extern.h
  650. X    cc -c $(CCFLAGS) PrintLine.c
  651. XMkDescVec.o: MkDescVec.c bm.h
  652. X    cc -c $(CCFLAGS) MkDescVec.c
  653. XGetPatFile.o: GetPatFile.c bm.h
  654. X    cc -c $(CCFLAGS) GetPatFile.c
  655. XMakeDesc.o: MakeDesc.c bm.h
  656. X    cc -c $(CCFLAGS) MakeDesc.c
  657. XGlobal.o: Global.c
  658. X    cc -c $(CCFLAGS) Global.c
  659. Xlisting:
  660. X    print -i3 $(BASEFILES)
  661. e-o-f
  662. echo Extracting README
  663. sed 's/^X//' > README << 'e-o-f'
  664. XBm is a fast pattern matching utility, intended to be almost
  665. Xidentical in functionality to fgrep (ugh!) but much faster. It uses
  666. Xthe Boyer-Moore algorithm, as described in the papers listed below:
  667. X
  668. XD.E. Knuth, J.H. Morris, V.R. Pratt,"Fast Pattern Matching in Strings", 
  669. XSIAM J. Comput., 6(2), June  1977, 323-350, 
  670. X
  671. XZ. Galil,
  672. X"On Improving the Worst Case Running Time of the Boyer-Moore String
  673. XMatching Algorithm", 
  674. XCACM, 22(9), Sept. 1979, ACM, 
  675. X
  676. XR.S. Boyer, J.S. Moore,"A Fast String Searching Algorithm", CACM, 20(10), 
  677. XOct. 1977, 762-772, 
  678. X
  679. XG. de V. Smit,"A Comparison of Three String Matching Algorithms", 
  680. XSoftware - Practice and Experience, vol. 12,  1982, 57-66, 
  681. X
  682. XThe files are:
  683. XExecute.c: search a file for the patterns
  684. XExtern.h: declarations of externs
  685. XGetPatFile.c: read in patterns from a file and set up a vector of
  686. X    pattern descriptors
  687. XGlobal.c: global variables (complement to Extern.h)
  688. XMakeDesc.c: create a pattern descriptor for one pattern, including
  689. X    skip tables, etc.
  690. XMakeSkip.c: make the skip tables for one pattern
  691. XMakefile: you can figure this one out for yourself
  692. XMatchFound.c: what to do when you actually FIND a pattern - print it,
  693. X    update flags, etc.
  694. XMkDescVec.c: make a vector of pattern descriptors, given a string
  695. X    of newline-separated patterns
  696. XMoveResidue.c: when you come to the end of the buffer, move the
  697. X    unsearched "residue" to the beginning and start again
  698. XPrintLine.c: print the appropriate stuff after finding a match
  699. XPutUsage.c: mini-man page.
  700. XREADME: this file
  701. XSearch.c: the guts. Implements B-M algorithm given a pattern, skip
  702. X    tables for the pattern, and a buffer to search
  703. Xbm.c: mainline. mostly interpreting the command line and tidying
  704. X    up at the end. Calls Execute for each file.
  705. Xbm.h: constants
  706. Xbm.p: man page
  707. e-o-f
  708. echo Extracting bm.p
  709. sed 's/^X//' > bm.p << 'e-o-f'
  710. X.TH BM PUBLIC "8 July 1985"
  711. X.UC 4
  712. X.SH NAME
  713. Xbm \- search a file for a string
  714. X.SH SYNOPSIS
  715. X.B /usr/public/bm
  716. X[ option ] ...
  717. X[ strings ]
  718. X[ file ]
  719. X.SH DESCRIPTION
  720. X.I Bm
  721. Xsearches the input
  722. X.I files
  723. X(standard input default) for lines matching a string.
  724. XNormally, each line found is copied to the standard output.
  725. XIt is blindingly fast.
  726. X.I Bm
  727. Xstrings are fixed sequences of characters:
  728. Xthere are no wildcards, repetitions, or other features
  729. Xof regular expressions.
  730. XBm is also case sensitive.
  731. XThe following options are recognized.
  732. X.TP
  733. X.B \-x
  734. X(Exact) only lines matched in their entirety are printed
  735. X.TP
  736. X.B \-l
  737. XThe names of files with matching lines are listed (once) separated by newlines.
  738. X.TP
  739. X.B \-c
  740. XOnly a count of the number of matches
  741. Xis printed
  742. X.TP
  743. X.B \-e "string"
  744. XThe string is the next argument after the
  745. X.B \-e
  746. Xflag. This allows strings beginning with '-'.
  747. X.TP
  748. X.B \-h
  749. XNo filenames are printed, even if multiple files are searched.
  750. X.TP
  751. X.B \-n
  752. XEach line is preceded by the number
  753. Xof characters from the beginning of the file
  754. Xto the match.
  755. X.TP
  756. X.B \-s
  757. XSilent mode.  Nothing is printed (except error messages).
  758. XThis is useful for checking the error status.
  759. X.TP
  760. X.BI \-f " file"
  761. XThe string list
  762. Xis taken from the
  763. X.I file.
  764. X.LP
  765. XUnless the
  766. X.B \-h
  767. Xoption is specified
  768. Xthe file name is shown if there is more than one input file.
  769. XCare should be taken when using the characters $ * [ ^ | ( ) and \\ in the
  770. X.I strings
  771. X(listed on the command line)
  772. Xas they are also meaningful to the Shell.  It is safest to enclose the entire
  773. X.I expression
  774. Xargument in single quotes \' \'.
  775. X.LP
  776. X.I Bm
  777. Xsearches for lines that contain one of the (newline-separated)
  778. X.I strings,
  779. Xusing
  780. Xthe Boyer-Moore algorithm.
  781. XIt is far superior in terms of speed to the grep (egrep, fgrep)
  782. Xfamily of pattern matchers for fixed-pattern searching,
  783. Xand its speed increases with pattern length.
  784. X.SH "SEE ALSO"
  785. Xgrep(1)
  786. X.SH DIAGNOSTICS
  787. XExit status is 0 if any matches are found,
  788. X1 if none, 2 for syntax errors or inaccessible files.
  789. X.SH AUTHOR
  790. XPeter Bain (pdbain@wateng), with modifications suggested by John Gilmore
  791. X.SH BUGS
  792. XOnly 100 patterns are allowed.
  793. X.LP
  794. XPatterns may not contain newlines.
  795. X.LP
  796. XIf a line (delimited by newlines, and the beginning and end of the file)
  797. Xis longer than 8000 charcters (e.g. in a core dump),
  798. Xit will not be completely printed.
  799. X.LP
  800. XIf multiple patterns are specified, the order of the ouput lines is not
  801. Xnecessarily the same as the order of the input lines.
  802. X.LP
  803. XA line will be printed once for each different string on that line.
  804. X.LP
  805. XThe algorithm cannot count lines.
  806. X.LP
  807. XThe
  808. X.B -n
  809. Xand
  810. X.B -c
  811. Xwork differently from fgrep.
  812. X.LP
  813. XThe
  814. X.B -v,
  815. X.B -i,
  816. Xand
  817. X.B -b
  818. Xare not available.
  819. e-o-f
  820. exit 0
  821.  
  822.