home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume9 / fastgrep / part01 < prev    next >
Text File  |  1987-06-15  |  57KB  |  1,746 lines
  1. Path: seismo!uunet!rs
  2. From: rs@uunet.UU.NET (Rich Salz)
  3. Newsgroups: comp.sources.unix
  4. Subject: v09i061:  Fastest grep around, Part01/02
  5. Message-ID: <365@uunet.UU.NET>
  6. Date: 16 Jun 87 23:35:08 GMT
  7. Organization: UUNET Communications Services, Arlington, VA
  8. Lines: 1735
  9. Approved: rs@uunet.uu.net
  10.  
  11. Submitted by: James A. Woods <ames!aurora!jaw>
  12. Mod.sources: Volume 9, Issue 61
  13. Archive-name: fastgrep/Part01
  14.  
  15. [  This is the latest posting of the Woods/Spencer super-fast grep.
  16.    It was announced in net.sources a few weeks ago.  You will probably
  17.    want to replace all your other greps with this one.  (Greps?)
  18.    When you unpak this, take careful not of the last few lines of the
  19.    script -- they make some "8-bit kanji" files.  --r$  ]
  20.  
  21. # To unbundle, sh this file
  22. echo Makefile 1>&2
  23. cat > Makefile <<'End of Makefile'
  24. # optional items for ENV:
  25. # -I.            use regexp.h in current directory, not /usr/include.
  26. # -DEGREPOLD=path    location of std egrep (normally /usr/bin/egrep).
  27. # -DGREPOLD=path    location of std grep (normally /bin/grep).
  28. # -DFGREPOLD=path    location of std fgrep (normally /usr/bin/fgrep).
  29. # -Dstrrchr=rindex, -Dstrchr=index    for troglodytes.
  30. # -DSLOWSYS        invoke xread() for system time quirk on PDP, others? 
  31. # -DNOKANJI        default is for Japanese Unix.  undef only for raw
  32. #             parity-marked search capability, not standard w/grep.
  33. # -DCHINESE        for systems using EUC Chinese2 codes
  34.  
  35. ENV= -I.
  36.  
  37. # warning:  do not overwrite existing [ef]?grep family with $BIN path choice
  38. BIN= /usr/local
  39.  
  40. # optional items for OBJ:
  41. # misc.o        for V7 or BSD 4.2 systems w/no getopt(3) or string(3)
  42. #              also contains xread() per above.
  43. # regexp.o        if Henry Spencer's regexp(3) is not installed
  44. #            V8 people -- your regexp.h won't do
  45.  
  46. OBJ= regexp.o
  47.  
  48. CFLAGS= -O $(ENV) 
  49. #CFLAGS= -O -i $(ENV)    uncomment this line for PDP-11
  50.  
  51. regexp:    ; make -f Makefile.regexp r; make egrep
  52.  
  53. egrep:    egrep.o regerror.o
  54.     cc $(CFLAGS) egrep.o regerror.o -o egrep $(OBJ)
  55.     rm -f grep fgrep
  56.     ln egrep grep
  57.     ln egrep fgrep
  58.  
  59. install: 
  60.     rm -f $(BIN)/*grep
  61.     strip egrep
  62.     mv egrep $(BIN)
  63.     ln $(BIN)/egrep $(BIN)/grep
  64.     ln $(BIN)/egrep $(BIN)/fgrep
  65.  
  66. clean:
  67.     rm *.o ./egrep ./grep ./fgrep ./try
  68. End of Makefile
  69. echo README.FIRST 1>&2
  70. cat > README.FIRST <<'End of README.FIRST'
  71. here is the fast 'grep/egrep' package sent to comp.sources and u. c. berkeley.
  72. included are the prerequisite routines developed by henry spencer of
  73. univ. of toronto -- these are also part of the comp.sources archive.
  74.  
  75. i've already updated spencer's care package to incorporate three fixes
  76. which have appeared in the same forum.
  77.  
  78. the makefiles are configured for bsd 4.3 and sys5 unix.
  79. they assume that the spencer regexp() is not already in a system library --
  80. read the makefile comments if this is not the case.
  81.  
  82. for stock 4.3 sites, apply the diff 'diff.egrep.y.bsd' to the existing
  83. source in /usr/src/usr.bin/egrep.y and re-make.  this adds full support
  84. for the -i option.  the procedure is then:
  85.  
  86.     make
  87.     sh eg.shell    # amusement
  88.     make install
  89.     
  90. ames!jaw
  91. End of README.FIRST
  92. echo README.kanji.mods 1>&2
  93. cat > README.kanji.mods <<'End of README.kanji.mods'
  94.      Three areas must be addressed to provide full Kanji compatibility.
  95. Only #1 (for the non-regular expression case) has been implemented
  96. directly in our grep/egrep-compatible Boyer-Moore-based code.
  97.  
  98.     (1) false middle match
  99.  
  100.        (a) meta-free Kanji
  101.        (b) Kanji regexprs
  102.  
  103. Kanji 16-bit "EUC" data codes (see Jung/Kalash, "Yunikkusu wa Nihongo o
  104. Hanasemasu", p. 209, Atlanta Usenix, 1986) have the upper bit on in both
  105. bytes, so as to allow intermixing of ASCII while preserving end-of-string
  106. detection.  'grep' must beware of matching two Kanji byte pairs in
  107. the interior of two unrelated Kanji characters.  e.g.
  108.  
  109.     text:         a (k1 k2) b (k3 k4) (k5 k6)
  110.     pattern:                   (k4   k5)    
  111.  
  112. is a bad match, given ascii bytes 'a' and 'b', and Kanji characters
  113. (k1 k2), (k3 k4), and (k5 k6).  The solution for Kanji grep using
  114. the traditional algorithm might be to anchor the pattern only at
  115. Kanji pair boundaries while scanning forward.
  116.  
  117. Boyer-Moore methods cannot afford this.  So we allow false matches, then
  118. scan backwards for legality (the first ascii byte in the text occurring
  119. before the candidate match disambiguates).  Another appealing method,
  120. for "layered" processing via regexp(3), is to convert the meta-free
  121. Kanji to '(^|[^\000-\177])k1k2', assuming Henry Spencer's code is
  122. "8-bit clean".  Case (b) (e.g. regexprs like 'k1k2.*k3k4') is similar,
  123. though syntax translation may be more difficult.
  124.  
  125.     (2) closures
  126.  
  127.      Eight-bit egrep '(k1k2)*' [where the '*' may be '+' or '?'], would
  128. wrongly apply the closure to the previous byte instead of the byte pair.
  129. One solution (without touching the existing 'regexp(3)' or 'e?grep' source)
  130. is to simply parenthesize reg exprs 'k1k2*' -> '(k1k2)*'.
  131. [only works with egrep syntax, so should occur after the grep->egrep
  132. expr xlation].
  133.  
  134.     (3) character classes
  135.  
  136.        (a) easy case:  [k1k2k3k4k5k6]
  137.  
  138.                -- just map to (k1k2|k3k4|k5k6).
  139.  
  140.        (b) hard:  ranges [k1k2-k3k4]
  141.  
  142. fail for byte-oriented char class code.
  143. Kanji interpretation (how do ideograms collate?) is also problematic.
  144. Translation to egrep '.*((k1k2)|(k1k2++)...|(k3k4)).*', where '++'
  145. denotes "16-bit successor" is conceivable, but farfetched.
  146.  
  147.      Now, translations (1) and (2) may be done [messily] w/o touching
  148. Spencer's code, while (3) could be farmed out to standard Kanji egrep via the
  149. process exec mechanism already established (see pep4grep.doc[123]).
  150. But if (3) were done this way (invoking exec()), then the other cases might
  151. also be done without recourse to the above xlations [just match "regmust"
  152. first, then pass false drops to the Japan Unix std.]  However, r.e.'s handled
  153. in such a manner would make hybrid Boyer-Moore slow for small files, except for
  154. systems running MACH.  We could have ad hoc file size vs. exec() tradeoff
  155. detectors control things for Kanji (it's already done for Anglo exprs), but
  156. previous success has hinged upon having the regexp(3) layer compatible with the
  157. r.e. style of the coarser egrep utility.
  158.  
  159.      Thus we take the easy way out and make fast grep only apply to simple
  160. non-r.e. Kanji.  The very best approach remains modification of proprietary
  161. Kanji egrep to incorporate Boyer-Moore directly, by doing Boyer-Moore on the
  162. buffers first before rescanning with the Kanji r.e. machine.  Someday.
  163.  
  164. -- James A. Woods (ames!jaw)
  165.  
  166. Postscript:  The several articles in the special issue of UNIX Review
  167. (March 1987) have delineated the bewildering variety of codesets
  168. (shifted JIS, HP 15/16, many EUC flavors, etc.).  A late addition to
  169. [ef]?grep Kanji support is capability for intermixed Katakana (SS2).
  170. Full testing on real Kanji files has not been done.  Comments are welcome.
  171. End of README.kanji.mods
  172. echo diff.egrep.y.bsd 1>&2
  173. cat > diff.egrep.y.bsd <<'End of diff.egrep.y.bsd'
  174. 19a20
  175. > #include <ctype.h>
  176. 27a29
  177. > char cmap[256];
  178. 51a54
  179. > int     iflag;
  180. 425a429
  181. >     register int i;
  182. 426a431,433
  183. >     for ( i = 0; i < 256; i++ )
  184. >         cmap[i] = (char) i;
  185. > 
  186. 454a462,467
  187. >         case 'i':
  188. >             iflag++;
  189. >             for ( i = 'A'; i <= 'Z'; i++ )
  190. >                 cmap[i] = (char) tolower ( i );
  191. >             continue;
  192. > 
  193. 483a497,502
  194. >     if ( iflag ) {
  195. >         register char *s;
  196. >         for ( s = input; *s != '\0'; s++ )
  197. >             if ( isupper ( (int)(*s) ) )
  198. >                 *s = (char) tolower ( (int)(*s) );
  199. >     }
  200. 508a528
  201. >     register char *cmapr = cmap;
  202. 544c564
  203. <         cstat = gotofn[cstat][*p&0377]; /* all input chars made positive */
  204. ---
  205. >         cstat = gotofn[cstat][cmapr[*(unsigned char *)p]]; 
  206. End of diff.egrep.y.bsd
  207. echo eg.shell 1>&2
  208. cat > eg.shell <<'End of eg.shell'
  209. DICT=/usr/dict/words    
  210.  
  211. echo "   testing MARK OF ZORRO: time ./egrep astrian $DICT"
  212. time ./egrep astrian $DICT
  213. echo ""
  214. echo "   testing ... AND VICTIM: time /usr/bin/egrep astrian $DICT" 
  215. time /usr/bin/egrep astrian $DICT
  216. echo ""
  217. echo "   testing A CAPITAL IDEA: time egrep -i zurich $DICT"
  218. time ./egrep -i zurich $DICT
  219. echo ""
  220. echo "   testing HOAGY CARMICHAEL: time egrep 'hoe.*g' $DICT"
  221. time ./egrep 'hoe.*g' $DICT
  222. echo ""
  223. echo "   testing NE PLUS ULTRA: grep '+=' egrep.c"
  224. ./grep '+=' ./egrep.c
  225. echo ""
  226. echo "   testing THE JAMES FILES: grep -l 'James'"
  227. ./grep -l James *
  228. echo ""
  229. echo "   testing CLEVER HANS EFFECT: egrep -c count < $DICT"
  230. ./egrep -c count < $DICT
  231. echo ""
  232. echo "   testing NUMBER OF THE BEAST: egrep -n '^[sS]atan$' $DICT"
  233. time ./egrep -n '^[sS]atan$' $DICT
  234. echo ""
  235. echo "   testing STATUS BACK BABY: grep -s 'my.*baby' $DICT"
  236. if ./grep -s 'my.*baby' $DICT
  237. then echo SOMETHING IS WRONG
  238. else echo status OK 
  239. fi
  240. echo ""
  241. echo "   testing PARALLEL FIFTHS: time egrep 'Ae|Ze|Oe|Qe|Xe' $DICT"
  242. time ./egrep 'Ae|Qe|Oe|Xe|Ze' $DICT
  243. echo ""
  244. echo "   testing TEE FOR TWO:  tee < eg.shell | ./egrep TWO"
  245. echo "   (or, short blocks go home)"
  246. tee < eg.shell | ./egrep TWO 
  247. echo ""
  248. echo "   testing HARD-TO-RHYME COLORS:"
  249. echo "        (echo orange; echo silver; echo purple) > colors"
  250. echo "        time ./fgrep -f colors $DICT > /dev/null"
  251. (echo orange; echo silver; echo purple) > colors
  252. time ./fgrep -f colors $DICT > /dev/null
  253. rm colors
  254. echo ""
  255. echo "   testing FAKE KANJI: ./egrep -f kanjipat.fake kanji.fake.test" 
  256. ./egrep -f kanjipat.fake kanji.fake.test | tr -d '\216'
  257. echo ""
  258. echo "   testing NOTHING: ./egrep '' egrep.c" 
  259. ./egrep '' $DICT
  260. echo ""
  261. echo "   testing SPEAK OF THE DEVIL (torture test courtesy Scott Anderson):" 
  262. echo "   or, WIN ALL 32 WITHOUT LAZY EVALUATION" 
  263. echo './egrep "' 'M[ou]'"'"'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]"' egad
  264. cat > egad << 'Egad'
  265. 1)  Muammar Qaddafi
  266. 2)  Mo'ammar Gadhafi
  267. 3)  Muammar Kaddafi
  268. 4)  Muammar Qadhafi
  269. 5)  Moammar El Kadhafi
  270. 6)  Muammar Gadafi
  271. 7)  Mu'ammar al-Qadafi
  272. 8)  Moamer El Kazzafi
  273. 9)  Moamar al-Gaddafi
  274. 10) Mu'ammar Al Qathafi
  275. 11) Muammar Al Qathafi
  276. 12) Mo'ammar el-Gadhafi
  277. 13) Moamar El Kadhafi
  278. 14) Muammar al-Qadhafi
  279. 15) Mu'ammar al-Qadhdhafi
  280. 16) Mu'ammar Qadafi
  281. 17) Moamar Gaddafi
  282. 18) Mu'ammar Qadhdhafi
  283. 19) Muammar Khaddafi
  284. 20) Muammar al-Khaddafi
  285. 21) Mu'amar al-Kadafi
  286. 22) Muammar Ghaddafy
  287. 23) Muammar Ghadafi
  288. 24) Muammar Ghaddafi
  289. 25) Muamar Kaddafi
  290. 26) Muammar Quathafi
  291. 27) Muammar Gheddafi
  292. 28) Muamar Al-Kaddafi
  293. 29) Moammar Khadafy
  294. 30) Moammar Qudhafi
  295. 31) Mu'ammar al-Qaddafi
  296. 32) Mulazim Awwal Mu'ammar Muhammad Abu Minyar al-Qadhafi
  297. Egad
  298. # there are subtle reasons why this odd command is not directly applied
  299. # to a "here document"
  300. time ./egrep "M[ou]'?am+[ae]r .*([AEae]l[- ])?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]" egad
  301. rm egad
  302. End of eg.shell
  303. echo egrep.c 1>&2
  304. cat > egrep.c <<'End of egrep.c'
  305.  
  306. /*
  307.      Hybrid Boyer/Moore/Gosper-assisted 'grep/egrep/fgrep' search, with delta0
  308.      table as in original paper (CACM, October, 1977).  No delta1 or delta2.
  309.      According to experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of
  310.      minimal practical value.  However, to improve for worst case input,
  311.      integrating the improved Galil strategies (Apostolico/Giancarlo, SIAM. J.
  312.      Comput., Feb. 1986) deserves consideration.
  313.  
  314.      Method:     extract longest metacharacter-free string from expression.
  315.         this is done using a side-effect from henry spencer's regcomp().
  316.         use boyer-moore to match such, then pass submatching lines
  317.         to either regexp() or standard 'egrep', depending on certain
  318.         criteria within execstrategy() below.  [this tradeoff is due
  319.         to the general slowness of the regexp() nondeterministic
  320.         machine on complex expressions, as well as the startup time
  321.         of standard 'egrep' on short files.]  alternatively, one may
  322.         change the vendor-supplied 'egrep' automaton to include
  323.         boyer-moore directly.  see accompanying writeup for discussion
  324.         of kanji expression treatment.
  325.  
  326.         late addition:  apply trickbag for fast match of simple
  327.         alternations (sublinear, in common low-cardinality cases).
  328.         trap fgrep into this lair.
  329.  
  330.         gnu additions:  -f, newline as |, \< and \> [in regexec()], more
  331.                 comments.  inspire better dfa exec() strategy.
  332.                 serious testing and help with special cases.
  333.  
  334.      Algorithm amalgam summary:
  335.  
  336.         dfa e?grep         (aho/thompson)
  337.         ndfa regexp()         (spencer/aho)
  338.         bmg            (boyer/moore/gosper)
  339.         "superimposed" bmg       (jaw)
  340.         fgrep            (aho/corrasick)
  341.  
  342.         sorry, but the knuth/morris/pratt machine, horspool's
  343.         "frequentist" code, and the rabin/karp matcher, however cute,
  344.         just don't cut it for this production.
  345.  
  346.      James A. Woods                Copyright (c) 1986
  347.      NASA Ames Research Center
  348. */
  349. #include <stdio.h>
  350. #include <ctype.h>
  351. #include <sys/types.h>
  352. #include <sys/stat.h>
  353. #include <regexp.h>        /* must be henry spencer's version */
  354.  
  355. #define    MIN(A, B)    ((A) > (B) ? (B) : (A))
  356.  
  357. #ifdef    SLOWSYS
  358. #define read    xread
  359. #endif
  360. /*
  361.  * define existing [ef]?grep program locations below for use by execvp().
  362.  * [execlp() would be used were it not for the possibility of
  363.  * installation-dependent recursion.] 
  364.  */
  365. #ifndef EGREPSTD
  366. #define    EGREPSTD    "/usr/bin/egrep"
  367. #endif
  368. #ifndef GREPSTD
  369. #define    GREPSTD        "/bin/grep"
  370. #endif
  371. #ifndef FGREPSTD
  372. #define    FGREPSTD    "/usr/bin/fgrep"
  373. #endif
  374.  
  375. #define BUFSIZE    8192        /* make higher for cray */
  376. #define PATSIZE 6000
  377. #define LARGE     BUFSIZE + PATSIZE
  378.  
  379. #define ALTSIZE    100        /* generous? */
  380. #define NALT    7        /* tied to scanf() size in alternate() */
  381. #define NMUSH    6        /* loosely relates to expected alt length */
  382.  
  383. #define    FIRSTFEW    10    /* Always do FIRSTFEW matches with regexec() */
  384. #define    PUNTPERCENT    5    /* After FIRSTFEW, if PUNTPERCENT of the input
  385.                  * was processed by regexp(), exec std egrep. */
  386. #define NL    '\n'
  387. #define    EOS    '\0'
  388. #define    NONASCII    0200    /* Bit mask for Kanji non-ascii chars */
  389. #define META    "\n^$.[]()?+*|\\"    /* egrep meta-characters */
  390. #define SS2    '\216'        /* EUC Katakana (or Chinese2) prefix */
  391. #define SS3    '\217'        /* EUC Kanji2 (or Chinese3) prefix */
  392.  
  393. extern char *optarg;
  394. extern int optind;
  395. char *progname;
  396.  
  397. int cflag, iflag, eflag, fflag, lflag, nflag;    /* SVID flags */
  398. int sflag, hflag;        /* v7, v8, bsd */
  399.  
  400. int firstflag;            /* Stop at first match */
  401. int grepflag;            /* Called as "grep" */
  402. int fgrepflag;            /* Called as "fgrep" */
  403. int altflag;            /* Simple alternation in pattern */
  404. int boyonly;            /* No regexp needed -- all simple */
  405. int flushflag;
  406. int grepold, egrepold, fgrepold;
  407.  
  408. int nalt;            /* Number of alternatives */
  409. int nsuccess;            /* 1 for match, 2 for error */
  410. int altmin;            /* Minimum length of all the alternate
  411.                  * strings */
  412. int firstfile;            /* argv index of first file argument */
  413. long nmatch;            /* Number of matches in this file */
  414. long incount, counted;        /* Amount of input consumed */
  415. long rxcount;            /* Bytes of input processed by regexec() */
  416. int boyfound;            /* accumulated partial matches (tripped by
  417.                  * FIRSTFEW) */
  418. int prevmatch;            /* next three lines aid fast -n */
  419. long nline, prevnline;
  420. char *prevloc;
  421.  
  422. regexp *rspencer;
  423. char *pattern;
  424. char *patboy;            /* Pattern for simple Boyer-Moore */
  425. char *patfile;            /* Filename containing pattern(s) */
  426.  
  427. int delta0[256];        /* Boyer-Moore algorithm core */
  428. char cmap[256];            /* Usually 0-255, but if -i, maps upper to
  429.                  * lower case */
  430. char str[BUFSIZE + 2];
  431. int nleftover;
  432. char linetemp[BUFSIZE];
  433. char altpat[NALT][ALTSIZE];    /* alternation component storage */
  434. int altlen[NALT];
  435. short altset[NMUSH + 1][256];
  436. char preamble[200];        /* match prefix (filename, line no.) */
  437.  
  438. int fd;
  439. char *
  440. strchr(), *strrchr(), *strcpy(), *strncpy(), *strpbrk(), *sprintf(), *malloc();
  441. char *
  442. grepxlat(), *fold(), *pfile(), *alternate(), *isolate();
  443. char **args;
  444.  
  445. main(argc, argv)
  446.     int argc;
  447.     char *argv[];
  448. {
  449.     int c;
  450.     int errflag = 0;
  451.  
  452.     args = argv;
  453.  
  454.     if ((progname = strrchr(argv[0], '/')) != 0)
  455.         progname++;
  456.     else
  457.         progname = argv[0];
  458.     if (strcmp(progname, "grep") == 0)
  459.         grepflag++;
  460.     if (strcmp(progname, "fgrep") == 0)
  461.         fgrepflag++;
  462.  
  463.     while ((c = getopt(argc, argv, "bchie:f:lnsvwxy1")) != EOF) {
  464.         switch (c) {
  465.  
  466.         case 'f':
  467.             fflag++;
  468.             patfile = optarg;
  469.             continue;
  470.         case 'b':
  471.         case 'v':
  472.             egrepold++;    /* boyer-moore of little help here */
  473.             continue;
  474.         case 'c':
  475.             cflag++;
  476.             continue;
  477.         case 'e':
  478.             eflag++;
  479.             pattern = optarg;
  480.             continue;
  481.         case 'h':
  482.             hflag++;
  483.             continue;
  484.         case '1':    /* Stop at very first match */
  485.             firstflag++;    /* spead freaks only */
  486.             continue;
  487.         case 'i':
  488.             iflag++;
  489.             continue;
  490.         case 'l':
  491.             lflag++;
  492.             continue;
  493.         case 'n':
  494.             nflag++;
  495.             continue;
  496.         case 's':
  497.             sflag++;
  498.             continue;
  499.         case 'w':
  500.         case 'y':
  501.             if (!grepflag)
  502.                 errflag++;
  503.             grepold++;
  504.             continue;
  505.         case 'x':    /* needs more work, like -b above */
  506.             if (!fgrepflag)
  507.                 errflag++;
  508.             fgrepold++;
  509.             continue;
  510.         case '?':
  511.             errflag++;
  512.         }
  513.     }
  514.     if (errflag || ((argc <= optind) && !fflag && !eflag)) {
  515.         if (grepflag)
  516. oops("usage: grep [-bcihlnsvwy] [-e] pattern [file ...]");
  517.         else if (fgrepflag)
  518. oops("usage: fgrep [-bcilnv] {-f patfile | [-e] strings} [file ...]");
  519.         else        /* encourage SVID options, though we provide
  520.                  * others */
  521. oops("usage: egrep [-bcilnv] {-f patfile | [-e] pattern} [file ...]");
  522.     }
  523.     if (fflag)
  524.         pattern = pfile(patfile);
  525.     else if (!eflag)
  526.         pattern = argv[optind++];
  527.  
  528.     if ((argc - optind) <= 1)    /* Filename invisible given < 2 files */
  529.         hflag++;
  530.     if (pattern[0] == EOS)
  531.         oops("empty expression");
  532.     /*
  533.      * 'grep/egrep' merger -- "old" grep is called to handle: tagged
  534.      * exprs \( \), word matches \< and \>, -w and -y options, char
  535.      * classes with '-' at end (egrep bug?), and patterns beginning with
  536.      * an asterisk (don't ask why). otherwise, characters meaningful to
  537.      * 'egrep' but not to 'grep' are escaped; the entire expr is then
  538.      * passed to 'egrep'. 
  539.      */
  540.     if (grepflag && !grepold) {
  541.         if (strindex(pattern, "\\(") >= 0 ||
  542.             strindex(pattern, "\\<") >= 0 ||
  543.             strindex(pattern, "\\>") >= 0 ||
  544.             strindex(pattern, "-]") >= 0 ||
  545.             pattern[0] == '*')    /* grep bug */
  546.             grepold++;
  547.         else
  548.             pattern = grepxlat(pattern);
  549.     }
  550.     if (grepold || egrepold || fgrepold)
  551.         kernighan(argv);
  552.  
  553.     if (iflag)
  554.         strcpy(pattern, fold(pattern));
  555.     /*
  556.      * If the pattern is a plain string, just run boyer-moore. If it
  557.      * consists of meta-free alternatives, run "superimposed" bmg.
  558.      * Otherwise, find best string, and compile pattern for regexec(). 
  559.      */
  560.     if (strpbrk(pattern, META) == NULL) {    /* do boyer-moore only */
  561.         boyonly++;
  562.         patboy = pattern;
  563.     } else {
  564.         if ((patboy = alternate(pattern)) != NULL)
  565.             boyonly++;
  566.         else {
  567.             if ((patboy = isolate(pattern)) == NULL)
  568.                 kernighan(argv);    /* expr too involved */
  569. #ifndef NOKANJI
  570.             for (c = 0; pattern[c] != EOS; c++)
  571.                 if (pattern[c] & NONASCII)    /* kanji + meta */
  572.                     kernighan(argv);
  573. #endif
  574.             if ((rspencer = regcomp(pattern)) == NULL)
  575.                 oops("regcomp failure");
  576.         }
  577.     }
  578.     gosper(patboy);        /* "pre-conditioning is wonderful"
  579.                  * -- v. strassen */
  580.  
  581.     if ((firstfile = optind) >= argc) {
  582.         /* Grep standard input */
  583.         if (lflag)    /* We don't know its name! */
  584.             exit(1);
  585.         egsecute((char *) NULL);
  586.     } else {
  587.         while (optind < argc) {
  588.             egsecute(argv[optind]);
  589.             optind++;
  590.             if (firstflag && (nsuccess == 1))
  591.                 break;
  592.         }
  593.     }
  594.     exit((nsuccess == 2) ? 2 : (nsuccess == 0));
  595. }
  596.  
  597. char *
  598. pfile(pfname)            /* absorb expression from file */
  599.     char *pfname;
  600. {
  601.     FILE *pf;
  602.     struct stat patstat;
  603.     static char *pat;
  604.  
  605.     if ((pf = fopen(pfname, "r")) == NULL)
  606.         oops("can't read pattern file");
  607.     if (fstat(fileno(pf), &patstat) != 0)
  608.         oops("can't stat pattern file");
  609.     if (patstat.st_size > PATSIZE) {
  610.         if (fgrepflag) {    /* defer to unix version */
  611.             fgrepold++;
  612.             return "dummy";
  613.         } else
  614.             oops("pattern file too big");
  615.     }
  616.     if ((pat = malloc((unsigned) patstat.st_size + 1)) == NULL)
  617.         oops("out of memory to read pattern file");
  618.     if (patstat.st_size !=
  619.         fread(pat, sizeof(char), patstat.st_size + 1, pf))
  620.         oops("error reading pattern file");
  621.     (void) fclose(pf);
  622.  
  623.     pat[patstat.st_size] = EOS;
  624.     if (pat[patstat.st_size - 1] == NL)    /* NOP for egrep; helps grep */
  625.         pat[patstat.st_size - 1] = EOS;
  626.  
  627.     if (nlcount(pat, &pat[patstat.st_size]) > NALT) {
  628.         if (fgrepflag)
  629.             fgrepold++;    /* "what's it all about, alfie?" */
  630.         else
  631.             egrepold++;
  632.     }
  633.     return (pat);
  634. }
  635.  
  636. egsecute(file)
  637.     char *file;
  638. {
  639.     if (file == NULL)
  640.         fd = 0;
  641.     else if ((fd = open(file, 0)) <= 0) {
  642.         fprintf(stderr, "%s: can't open %s\n", progname, file);
  643.         nsuccess = 2;
  644.         return;
  645.     }
  646.     chimaera(file, patboy);
  647.  
  648.     if (!boyonly && !flushflag && file != NULL)
  649.         flushmatches();
  650.     if (file != NULL)
  651.         close(fd);
  652. }
  653.  
  654. chimaera(file, pat)        /* "reach out and boyer-moore search someone" */
  655.     char *file, *pat;    /* -- soon-to-be-popular bumper sticker */
  656. {
  657.     register char *k, *strend, *s;
  658.     register int j, count;
  659.     register int *deltazero = delta0;
  660.     int patlen = altmin;
  661.     char *t;
  662.     char *gotamatch(), *kanji(), *linesave(), *submatch();
  663.  
  664.     nleftover = boyfound = flushflag = 0;
  665.     nline = 1L;
  666.     prevmatch = 0;
  667.     nmatch = counted = rxcount = 0L;
  668.  
  669.     while ((count = read(fd, str + nleftover, BUFSIZE - nleftover)) > 0) {
  670.  
  671.         counted += count;
  672.         strend = linesave(str, count);
  673.  
  674.         for (k = str + patlen - 1; k < strend;) {
  675.             /*
  676.              * for a large class of patterns, upwards of 80% of
  677.              * match time is spent on the next line.  we beat
  678.              * existing microcode (vax 'matchc') this way. 
  679.              */
  680.             while ((k += deltazero[*(unsigned char *) k]) < strend);
  681.             if (k < (str + LARGE))
  682.                 break;
  683.             k -= LARGE;
  684.  
  685.             if (altflag) {
  686.                 /*
  687.                  * Parallel Boyer-Moore.  Check whether each
  688.                  * of the previous <altmin> chars COULD be
  689.                  * from one of the alternative strings. 
  690.                  */
  691.                 s = k - 1;
  692.                 j = altmin;
  693.                 while (altset[--j][(unsigned char)
  694.                          cmap[*(unsigned char *) s--]]);
  695.                 /*
  696.                  * quick test fails. in this life, compare
  697.                  * 'em all.  but, a "reverse trie" would
  698.                  * attenuate worst case (linear w/delta2?). 
  699.                  */
  700.                 if (--j < 0) {
  701.                     count = nalt - 1;
  702.                     do {
  703.                         s = k;
  704.                         j = altlen[count];
  705.                         t = altpat[count];
  706.  
  707.                         while
  708.                             (cmap[*(unsigned char *) s--]
  709.                              == t[--j]);
  710.                         if (j < 0)
  711.                             break;
  712.                     }
  713.                     while (count--);
  714.                 }
  715.             } else {
  716.                 /* One string -- check it */
  717.                 j = patlen - 1;
  718.                 s = k - 1;
  719.                 while (cmap[*(unsigned char *) s--] == pat[--j]);
  720.             }
  721.             /*
  722.              * delta-less shortcut for literati. short shrift for
  723.              * genetic engineers? 
  724.              */
  725.             if (j >= 0) {
  726.                 k++;    /* no match; restart next char */
  727.                 continue;
  728.             }
  729.             k = submatch(file, pat, str, strend, k, count);
  730.             if (k == NULL)
  731.                 return;
  732.         }
  733.         if (nflag) {
  734.             if (prevmatch)
  735.                 nline = prevnline + nlcount(prevloc, k);
  736.             else
  737.                 nline = nline + nlcount(str, k);
  738.             prevmatch = 0;
  739.         }
  740.         strncpy(str, linetemp, nleftover);
  741.     }
  742.     if (cflag) {
  743.         /* Bug from old grep: -c overrides -h.  We fix the bug. */
  744.         if (!hflag)
  745.             printf("%s:", file);
  746.         printf("%ld\n", nmatch);
  747.     }
  748. }
  749.  
  750. char *
  751. linesave(str, count)        /* accumulate partial line at end of buffer */
  752.     char str[];
  753.     register int count;
  754. {
  755.     register int j;
  756.  
  757.     count += nleftover;
  758.     if (count != BUFSIZE && fd != 0)
  759.         str[count++] = NL;    /* insurance for broken last line */
  760.     str[count] = EOS;
  761.     for (j = count - 1; str[j] != NL && j >= 0;)
  762.         j--;
  763.     /*
  764.      * break up these lines: long line (> BUFSIZE), last line of file, or
  765.      * short return from read(), as from tee(1) input 
  766.      */
  767.     if (j < 0 && (count == (BUFSIZE - nleftover))) {
  768.         str[count++] = NL;
  769.         str[count] = EOS;
  770.         linetemp[0] = EOS;
  771.         nleftover = 0;
  772.         return (str + count);
  773.     } else {
  774.         nleftover = count - j - 1;
  775.         strncpy(linetemp, str + j + 1, nleftover);
  776.         return (str + j);
  777.     }
  778. }
  779.  
  780. /*
  781.  * Process partial match. First check for mis-aligned Kanji, then match line
  782.  * against full compiled r.e. if statistics do not warrant handing off to
  783.  * standard egrep. 
  784.  */
  785. char *
  786. submatch(file, pat, str, strend, k, altindex)
  787.     char file[], pat[], str[];
  788.     register char *strend, *k;
  789.     int altindex;
  790. {
  791.     register char *s;
  792.     char *t, c;
  793.  
  794.     t = k;
  795.     s = ((altflag) ? k - altlen[altindex] + 1 : k - altmin + 1);
  796. #ifndef NOKANJI
  797.     c = ((altflag) ? altpat[altindex][0] : pat[0]);
  798.     if (c & NONASCII)
  799.         if ((s = kanji(str, s, k)) == NULL)
  800.             return (++k);    /* reject false kanji */
  801. #endif
  802.     do;
  803.     while (*s != NL && --s >= str);
  804.     k = s + 1;        /* now at line start */
  805.  
  806.     if (boyonly)
  807.         return (gotamatch(file, k));
  808.  
  809.     incount = counted - (strend - k);
  810.     if (boyfound++ == FIRSTFEW)
  811.         execstrategy(file);
  812.  
  813.     s = t;
  814.     do
  815.         rxcount++;
  816.     while (*s++ != NL);
  817.     *--s = EOS;
  818.     /*
  819.      * "quick henry -- the flit" (after theodor geisel) 
  820.      */
  821.     if (regexec(rspencer, ((iflag) ? fold(k) : k)) == 1) {
  822.         *s = NL;
  823.         if (gotamatch(file, k) == NULL)
  824.             return (NULL);
  825.     }
  826.     *s = NL;
  827.     return (s + 1);
  828. }
  829.  
  830. /*
  831.  * EUC code disambiguation -- scan backwards to first 7-bit code, while
  832.  * counting intervening 8-bit codes.  If odd, reject unaligned Kanji pattern. 
  833.  * SS2/3 checks are for intermixed Japanase Katakana or Kanji2. 
  834.  */
  835. char *
  836. kanji(str, s, k)
  837.     register char *str, *s, *k;
  838. {
  839.     register int j = 0;
  840.  
  841.     for (s--; s >= str; s--) {
  842.         if (*s == SS2 || *s == SS3 || (*s & NONASCII) == 0)
  843.             break;
  844.         j++;
  845.     }
  846. #ifndef CHINESE
  847.     if (*s == SS2)
  848.         j -= 1;
  849. #endif  CHINESE
  850.     return ((j & 01) ? NULL : k);
  851. }
  852.  
  853. /*
  854.  * Compute "Boyer-Moore" delta table -- put skip distance in delta0[c] 
  855.  */
  856. gosper(pattern)
  857.     char *pattern;        /* ... HAKMEM lives ... */
  858. {
  859.     register int i, j;
  860.     unsigned char c;
  861.  
  862.     /* Make one-string case look like simple alternatives case */
  863.     if (!altflag) {
  864.         nalt = 1;
  865.         altmin = altlen[0] = strlen(pattern);
  866.         strcpy(altpat[0], pattern);
  867.     }
  868.     /* For chars that aren't in any string, skip by string length. */
  869.     for (j = 0; j < 256; j++) {
  870.         delta0[j] = altmin;
  871.         cmap[j] = j;    /* Sneak in initialization of cmap */
  872.     }
  873.  
  874.     /* For chars in a string, skip distance from char to end of string. */
  875.     /* (If char appears more than once, skip minimum distance.) */
  876.     for (i = 0; i < nalt; i++)
  877.         for (j = 0; j < altlen[i] - 1; j++) {
  878.             c = altpat[i][j];
  879.             delta0[c] = MIN(delta0[c], altlen[i] - j - 1);
  880.             if (iflag && islower((int) c))
  881.                 delta0[toupper((int) c)] = delta0[c];
  882.         }
  883.  
  884.     /* For last char of each string, fall out of search loop. */
  885.     for (i = 0; i < nalt; i++) {
  886.         c = altpat[i][altlen[i] - 1];
  887.         delta0[c] = LARGE;
  888.         if (iflag && islower((int) c))
  889.             delta0[toupper((int) c)] = LARGE;
  890.     }
  891.     if (iflag)
  892.         for (j = 'A'; j <= 'Z'; j++)
  893.             cmap[j] = tolower((int) j);
  894. }
  895.  
  896. /*
  897.  * Print, count, or stop on full match. Result is either the location for
  898.  * continued search, or NULL to stop. 
  899.  */
  900. char *
  901. gotamatch(file, s)
  902.     register char *file, *s;
  903. {
  904.     char *savematch();
  905.     int squirrel = 0;    /* nonzero to squirrel away FIRSTFEW matches */
  906.  
  907.     nmatch++;
  908.     nsuccess = 1;
  909.     if (!boyonly && boyfound <= FIRSTFEW && file != NULL)
  910.         squirrel = 1;
  911.  
  912.     if (sflag)
  913.         return (NULL);    /* -s usurps all flags (unlike some versions) */
  914.     if (cflag) {        /* -c overrides -l, we guess */
  915.         do;
  916.         while (*s++ != NL);
  917.     } else if (lflag) {
  918.         puts(file);
  919.         return (NULL);
  920.     } else {
  921.         if (!hflag)
  922.             if (!squirrel)
  923.                 printf("%s:", file);
  924.             else
  925.                 sprintf(preamble, "%s:", file);
  926.         if (nflag) {
  927.             if (prevmatch)
  928.                 prevnline = prevnline + nlcount(prevloc, s);
  929.             else
  930.                 prevnline = nline + nlcount(str, s);
  931.             prevmatch = 1;
  932.  
  933.             if (!squirrel)
  934.                 printf("%ld:", prevnline);
  935.             else
  936.                 sprintf(preamble + strlen(preamble),
  937.                     "%ld:", prevnline);
  938.         }
  939.         if (!squirrel) {
  940.             do
  941.                 putchar(*s);
  942.             while (*s++ != NL);
  943.         } else
  944.             s = savematch(s);
  945.  
  946.         if (nflag)
  947.             prevloc = s - 1;
  948.     }
  949.     return ((firstflag && !cflag) ? NULL : s);
  950. }
  951.  
  952. char *
  953. fold(line)
  954.     char *line;
  955. {
  956.     static char fline[BUFSIZE];
  957.     register char *s, *t = fline;
  958.  
  959.     for (s = line; *s != EOS; s++)
  960.         *t++ = (isupper((int) *s) ? (char) tolower((int) *s) : *s);
  961.     *t = EOS;
  962.     return (fline);
  963. }
  964.  
  965. strindex(s, t)            /* the easy way, as in K&P, p. 192 */
  966.     char *s, *t;
  967. {
  968.     int i, n;
  969.  
  970.     n = strlen(t);
  971.     for (i = 0; s[i] != '\0'; i++)
  972.         if (strncmp(s + i, t, n) == 0)
  973.             return (i);
  974.     return (-1);
  975. }
  976.  
  977. char *
  978. grepxlat(pattern)        /* grep pattern meta conversion */
  979.     char *pattern;
  980. {
  981.     register char *p, *s;
  982.     static char newpat[BUFSIZE];
  983.  
  984.     for (s = newpat, p = pattern; *p != EOS;) {
  985.         if (*p == '\\') {    /* skip escapes ... */
  986.             *s++ = *p++;
  987.             if (*p)
  988.                 *s++ = *p++;
  989.         } else if (*p == '[') {    /* ... and char classes */
  990.             while (*p != EOS && *p != ']')
  991.                 *s++ = *p++;
  992.         } else if (strchr("+?|()", *p) != NULL) {
  993.             *s++ = '\\';    /* insert protection */
  994.             *s++ = *p++;
  995.         } else
  996.             *s++ = *p++;
  997.     }
  998.     *s = EOS;
  999.     return (newpat);
  1000. }
  1001.  
  1002. /*
  1003.  * Test for simple alternation.  Result is NULL if it's not so simple, or is
  1004.  * a pointer to the first string if it is. Warning:  sscanf size is a
  1005.  * fixpoint, beyond which the speedup linearity starts to break down.  In the
  1006.  * wake of the elegant aho/corrasick "trie"-based fgrep, generalizing
  1007.  * altpat[] to arbitrary size is not useful. 
  1008.  */
  1009. char *
  1010. alternate(regexpr)
  1011.     char *regexpr;
  1012. {
  1013.     register i, j, min;
  1014.     unsigned char c;
  1015.     char oflow[100];
  1016.  
  1017.     if (fgrepflag && strchr(regexpr, '|'))
  1018.         return (NULL);
  1019.  
  1020.     i = strlen(regexpr);
  1021.     for (j = 0; j < i; j++)
  1022.         if (regexpr[j] == NL)
  1023.             regexpr[j] = '|';
  1024.  
  1025.     if (!fgrepflag) {
  1026.         if (strchr(regexpr, '|') == NULL || regexpr[0] == '|')
  1027.             return (NULL);
  1028.         if (strpbrk(regexpr, "^$.[]()?+*\\") != NULL
  1029.             || strindex(regexpr, "||") >= 0)
  1030.             return (NULL);
  1031.     }
  1032.     oflow[0] = EOS;
  1033.     nalt = sscanf(regexpr, "%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]|%[^|]",
  1034.               altpat[0], altpat[1], altpat[2], altpat[3], altpat[4], altpat[5], altpat[6], oflow);
  1035.  
  1036.     if (nalt < 1 || oflow[0] != EOS)
  1037.         return (NULL);
  1038.  
  1039.     altmin = NMUSH;
  1040.     for (j = 0; j < nalt; j++) {
  1041.         min = altlen[j] = strlen(altpat[j]);
  1042.         if (min > ALTSIZE)
  1043.             return (NULL);
  1044.         altmin = MIN(altmin, min);
  1045.     }
  1046.     if (nalt > 1) {        /* build superimposed "pre-match" sets per
  1047.                  * char */
  1048.         altflag++;
  1049.         for (j = 0; j < nalt; j++)
  1050.             for (i = 0; i < altmin; i++) {
  1051.                 c = altpat[j][altlen[j] - altmin + i];
  1052.                 altset[i + 1][c] = 1;    /* offset for sentinel */
  1053.             }
  1054.     }
  1055.     return (altpat[0]);
  1056. }
  1057.  
  1058. /*
  1059.  * Grapple with the dfa (std egrep) vs. ndfa (regexp) tradeoff. Criteria to
  1060.  * determine whether to use dfa-based egrep:  We do FIRSTFEW matches with
  1061.  * regexec().  Otherwise, if Boyer-Moore up to now matched more than
  1062.  * PUNTPERCENT of the input, and there is sufficient bulk remaining to
  1063.  * justify justify a process exec, do old *grep, presuming that its greater
  1064.  * speed at regular expressions will pay us back over this volume.  At
  1065.  * FIRSTFEW, dump the saved matches collected by savematch(). They are saved
  1066.  * so that a "PUNT" can "rewind" to ignore them.  Stdin is problematic,
  1067.  * since it's hard to rewind. 
  1068.  */
  1069.  
  1070. #define CTHRESH    50000
  1071.  
  1072. execstrategy(file)
  1073.     char *file;
  1074. {
  1075.     struct stat stbuf;
  1076.     int pctmatch;
  1077.     long cremain;
  1078.  
  1079.     pctmatch = (100 * rxcount) / incount;
  1080.     if (!grepflag && pctmatch > PUNTPERCENT && file != NULL) {
  1081.         fstat(fd, &stbuf);
  1082.         cremain = stbuf.st_size - incount;
  1083.         if (cremain > CTHRESH)
  1084.             kernighan(args);
  1085.     }
  1086.     if (file != NULL)
  1087.         flushmatches();
  1088. }
  1089.  
  1090. nlcount(bstart, bstop)        /* flail interval to totalize newlines. */
  1091.     char *bstart, *bstop;
  1092. {
  1093.     register char *s = bstart;
  1094.     register char *t = bstop;
  1095.     register int count = 0;
  1096.  
  1097.     do {            /* loop unroll for older architectures */
  1098.         if (*t == NL)    /* ... ask ames!jaw for sample code */
  1099.             count++;
  1100.     } while (t-- > s);
  1101.  
  1102.     return (count);
  1103. }
  1104.  
  1105. char *
  1106. isolate(regexpr)        /* isolate longest metacharacter-free string */
  1107.     char *regexpr;
  1108. {
  1109.     char *dummyexpr;
  1110.  
  1111.     /*
  1112.      * We add (.)* because Henry's regcomp only figures regmust if it
  1113.      * sees a leading * pattern.  Foo! 
  1114.      */
  1115.     dummyexpr = malloc((unsigned) strlen(regexpr) + 5);
  1116.     sprintf(dummyexpr, "(.)*%s", regexpr);
  1117.     if ((rspencer = regcomp(dummyexpr)) == NULL)
  1118.         kernighan(args);
  1119.     return (rspencer->regmust);
  1120. }
  1121.  
  1122. char *matches[FIRSTFEW];
  1123. static int mcount = 0;
  1124.  
  1125. char *
  1126. savematch(s)            /* horde matches during statistics gathering */
  1127.     register char *s;
  1128. {
  1129.     char *p;
  1130.     char *start = s;
  1131.     int msize = 0;
  1132.     int psize = strlen(preamble);
  1133.  
  1134.     while (*s++ != NL)
  1135.         msize++;
  1136.     *--s = EOS;
  1137.  
  1138.     p = malloc((unsigned) msize + 1 + psize);
  1139.     strcpy(p, preamble);
  1140.     strcpy(p + psize, start);
  1141.     matches[mcount++] = p;
  1142.  
  1143.     preamble[0] = 0;
  1144.     *s = NL;
  1145.     return (s);
  1146. }
  1147.  
  1148. flushmatches()
  1149. {
  1150.     int n;
  1151.  
  1152.     flushflag = 1;
  1153.     for (n = 0; n < mcount; n++)
  1154.         printf("%s\n", matches[n]);
  1155.     mcount = 0;
  1156. }
  1157.  
  1158. oops(message)
  1159.     char *message;
  1160. {
  1161.     fprintf(stderr, "%s: %s\n", progname, message);
  1162.     exit(2);
  1163. }
  1164.  
  1165. kernighan(args)            /* "let others do the hard part ..." */
  1166.     char *args[];
  1167. {
  1168.     /*
  1169.      * We may have already run grep on some of the files; remove them
  1170.      * from the arg list we pass on.  Note that we can't delete them
  1171.      * totally because the number of file names affects the output
  1172.      * (automatic -h). 
  1173.      */
  1174.     /* better would be fork/exec per punted file -- jaw */
  1175.  
  1176.     while (firstfile && optind > firstfile)
  1177.         args[firstfile++] = "/dev/null";
  1178.  
  1179.     fflush(stdout);
  1180.  
  1181.     if (grepflag)
  1182.         execvp(GREPSTD, args), oops("can't exec old 'grep'");
  1183.     else if (fgrepflag)
  1184.         execvp(FGREPSTD, args), oops("can't exec old 'fgrep'");
  1185.     else
  1186.         execvp(EGREPSTD, args), oops("can't exec old 'egrep'");
  1187. }
  1188. End of egrep.c
  1189. echo k.pat 1>&2
  1190. cat > k.pat <<'End of k.pat'
  1191. buffy|q|XY
  1192. End of k.pat
  1193. echo k.test 1>&2
  1194. cat > k.test <<'End of k.test'
  1195. WXY--this line should *not* print--
  1196. abXY--this line should print, but *not* the previous line--
  1197. XWXY--this line should print--
  1198. XYcd--this line also--
  1199. q--this line too--
  1200. ZWWXYembedded Katakana, unaligned Kanji
  1201. ZWXYembedded Katakana
  1202. End of k.test
  1203. echo pep4grep.doc1 1>&2
  1204. cat > pep4grep.doc1 <<'End of pep4grep.doc1'
  1205. >From postnews Tue Mar 18 18:04:08 1986
  1206. Subject: More Pep for Boyer-Moore Grep (part 1 of 2)
  1207. Newsgroups: net.unix
  1208.  
  1209. #  The chief defect of Henry King
  1210.    Was chewing little bits of string.
  1211.  
  1212.     -- Hilaire Belloc, Cautionary Tales [1907]
  1213.  
  1214. #  Attempt the end, and never stand to doubt
  1215.    Nothing's so hard but search will find it out.
  1216.  
  1217.     -- Robert Herrick, Hesperides [1648]
  1218.  
  1219.      The world does not need another 'grep' variant.  And so, what is this
  1220. we offer?  On the surface, the exact same 'egrep' actually, but underneath,
  1221. a swift Boyer-Moore hybrid, in C, which can beat assembler versions utilizing
  1222. microcoded string search instructions.  The offering, designed in the
  1223. Kernighanian sense to utilize the existing 'egrep' when it must, also
  1224. makes use of Mr. Henry Spencer's regexp(3) functions in an unusual way.
  1225. For the edification of those without on-line access to system source code,
  1226. the vendor-supplied 'egrep' is left in a pristine state.
  1227.  
  1228.      With code now wending its way to mod.sources, we obtain the following
  1229. results.  Times (in seconds) are all measured on a VAX 11/750 system running
  1230. BSD 4.2 on Fujitsu Eagles, although our 'egrep' has been run on the Sun 2,
  1231. V7 Unix/PDP 11, Vaxen configured with System V, and, for added effect, the
  1232. NASA Ames Cray 2.
  1233.  
  1234.             200K bytes       user   sys    notes
  1235.  
  1236.   (new) egrep  astrian /usr/dict/words     0.4    0.5    implementation by "jaw"
  1237.     match      "           "         0.5    0.5    VAX-only (Waterloo)
  1238.     bm      "           "         1.1    0.6    Peter Bain's version 2
  1239.   (old) egrep     "           "      5.6    1.7    standard    
  1240.  
  1241. [note:  the output here is the single word "Zoroastrian".]
  1242.  
  1243.      Aha, you quip -- this is all very fine for the 99 and 44/100's percent
  1244. metacharacter-free world, but what about timing for shorter strings, character
  1245. folding, as well as for the more interesting universe of extended regular 
  1246. expressions?  Samples forthwith.  (Egrep below refers to the new one, times for
  1247. the /usr/bin code being about the same as above on most any pattern.)
  1248.  
  1249.     egrep      zurich        0.4  0.5    0 words output
  1250.     egrep -i zuRich      0.4  0.5    1 
  1251.     egrep -i zeus          0.6  0.6    1
  1252.     egrep -i zen          0.7  0.6    11
  1253.     bm      zen          2.2  0.6    10
  1254.     egrep      ZZ          0.8  0.6    0
  1255.     bm      ZZ          3.0  0.7    0
  1256.     egrep -c Z          1.5  0.6    19
  1257.     bm -c      Z          5.9  0.7    19
  1258.  
  1259. Admittedly, most people (or programs) don't search for single characters,
  1260. where Boyer-Moore is a bit slow, but it's important for the layered regular
  1261. expression approach described herein.  We might point out from the above that
  1262. the popular "fold" option crippled by 'bm' costs little; it's only a slight
  1263. adjustment of the precomputed "delta" table as well as a single character
  1264. array reference in a secondary loop.  Why has Bain claimed complexity for this?
  1265. Also, the times show that the inner loop chosen for our code (modeled after
  1266. the original speedup done by Boyer-Moore for the PDP 10) consistently betters
  1267. the "blindingly fast" version by a factor of two to three.  The tipoff was
  1268. from previous paper studies (esp. Horspool, see header notes in code) noting
  1269. that the algorithm should, when implemented efficiently, best typical microcode.
  1270. Now it does. 
  1271.  
  1272.     while ( (k += delta0 ( *k )) < strend )
  1273.         ;        /* over 80% of time spent here */
  1274.  
  1275. is the key (modulo precomputation tricks), and takes but three or four
  1276. instructions on most machines.
  1277.  
  1278.      Basic method for regular expressions:
  1279.  
  1280.     (1) isolate the longest metacharacter-free pattern string via the
  1281.         "regmust" field provided by H. Spencer's regcomp() routine.
  1282.  
  1283.         (Non-kosher, but worth not re-inventing the wheel.
  1284.         v8 folks just might have to reverse-engineer Spencer's
  1285.         reverse-engineering to provide equivalent functionality.
  1286.         You see, there are many more sites running his code than v8.
  1287.         Besides, we enjoy using regexpr technology on itself.
  1288.  
  1289.     (2) for "short" input, submatching lines are passed to regexec().
  1290.  
  1291.     (3) for "long" input, start up a standard 'egrep' process via
  1292.         popen() or equivalent.  Why not just use regexec()?  Unfortunately
  1293.         for our application, Spencer's otherwise admirable finite-state
  1294.         automaton exhibits poor performance for complex expressions.
  1295.         Setting a threshold on input length, though not perfect, helps.
  1296.         If pipes on Unix were free, we'd use this way exclusively.
  1297.         Until then, we buy happiness for those who might
  1298.  
  1299.             egrep stuff /usr/spool/news/net/unix/*
  1300.  
  1301.         or on other directories full of short files.
  1302.  
  1303. [note: the details of (3) have changed in the re-release -- see pep4grep.doc3]
  1304.  
  1305. So,
  1306.     [new] egrep -i 'hoe.*g' words        1.2  1.1
  1307.                          {shoestring,Shoenberg}
  1308.     [new] egrep '(a|b).*zz.*[od]$'    words     1.5  1.1
  1309.                          {blizzard,buzzword,palazzo}
  1310.     [old] egrep                 6.3  1.4
  1311. but,
  1312.     {new,old} egrep -c 'first|second'    similar times (no isolate)
  1313.  
  1314. Again, we stress that given the different nature of the simulations of the two
  1315. nondeterministic reg. expr. state-machines (one functionless), cases can be
  1316. "cooked" to show things in a bad light, so a hybrid is warranted.
  1317. We can generally do better incorporating the Boyer-Moore algorithm directly
  1318. into the AT&T code.  For the last example, the abstraction
  1319.  
  1320.     (egrep first words &; egrep second words) | sort -u | wc
  1321.  
  1322. ideally would work better on a parallel machine, but if you're expecting
  1323. something as amazing in this draft as, say, Morwen B. Thistlethwaite's 52-move
  1324. Rubik's Cube solution, you're in the wrong place.
  1325.  
  1326. [note: but see pep4grep.doc3 -- now [ef]?grep handles some parallelism fast]
  1327.  
  1328.      About options -- the SVID ones are supported (-c, -l, bonus -i for BSD),
  1329. and -s and -h works as for BSD and v8.  Note: the 'egrep' here just hands off
  1330. patterns to the old code for things like -n, -b, -v, and multiple patterns.
  1331. As a bone to throw to the enemies of the cat-v school, there is a -1 flag
  1332. (halt after printing first match), but we don't talk about it much.
  1333. Multiple patterns can done ala 'bm' but laziness in the presence of lack of
  1334. knowledge of where 'fgrep' wins has prevailed for version 1.
  1335.  
  1336.      Personally I feel that adapting ("internationalizing") the 'egrep' effort
  1337. for two-byte Kanji is FAR more important than tweeking options or tradeoffs,
  1338. so for you large-alphabet Boyer-Moore algorithm specialists, send ideas
  1339. this way.
  1340.      
  1341.      Further historical/philosophical comments follow in the sequel.
  1342.  
  1343.      James A. Woods (ames!jaw)
  1344.      NASA Ames Research Center
  1345.  
  1346. End of pep4grep.doc1
  1347. echo pep4grep.doc2 1>&2
  1348. cat > pep4grep.doc2 <<'End of pep4grep.doc2'
  1349. >From postnews Tue Mar 18 18:05:22 1986
  1350. Subject: More Pep for Boyer-Moore Grep (part 2 of 2)
  1351. Newsgroups: net.unix
  1352.  
  1353. #  "Gratiano speaks an infinite deal of nothing, more than any man in all
  1354.    of Venice.  His reasons are as two grains of wheat hid in two bushels of
  1355.    chaff:  you shall seek all day ere you find them, they are not worth
  1356.    the search."  -- Shakespeare, Merchant of Venice
  1357.  
  1358. ... or, part 2, "Reach out and Boyer-Moore Egrep Someone"
  1359.  
  1360.      Maybe you never use 'grep'.  Then ignore this.  But if you do, why not
  1361. use the best algorithm?  Serious addicts know that for unstructured yet
  1362. stable text, B-trees are used for speed, or something like Lesk's nifty
  1363. (and unavailable) 'grab' suite for inverted files are ways to go.  Barring file
  1364. inversion daemons for netnews and other ephemera, we are limited to the
  1365. present improvements.
  1366.  
  1367.      Proper skeptics should question why a nearly I/O-bound program (but
  1368. not for any CPU with less than the power of several VAX MIPS, alas) should
  1369. be made more so.  The question was posed in B & M's classic 1978 CACM
  1370. paper -- the answer then was to free up more CPU cycles for timesharing.
  1371. Now, our motivations are more mundane (we won't have desktop 5 MIP machines
  1372. for another year), but not only that, we've discovered that the Cray 2's
  1373. standard 'egrep' is also very anemic, performing 8-12 times as worse as ours
  1374. on simple patterns.  For shame, especially since hearing of the rumor that
  1375. certain group theorists have a search application ready for testing.
  1376. Boyer-Moore could fill in until a Cray vectorizing C compiler shows up.
  1377. Sheer speed for machines whose filesystems are cached in memory is nice too.
  1378.  
  1379.      A quick-and-dirty rundown of the debts to which the new hybrid pays
  1380. now follows.
  1381.  
  1382.     Thompson, K. T. (CACM, November 1968):
  1383.         Regular Expression Search Algorithm.  As usual, obvious
  1384.         once you understand it.  The current 'egrep'.  Still
  1385.         useful as a base.  Abstracted by Aho/Ullman as Algorithm
  1386.         9.1 in Design and Analysis of Computer Algorithms.
  1387.  
  1388.     Boyer/Moore:
  1389.         Not quite pre-Unix.  Oh well.  Modern designers should
  1390.         know better now, if they want their stuff to get out there.
  1391.         By the way, I haven't used delta2 (or 1) since the O(mn) case
  1392.         case doesn't come up too often.  Sure Knuth stood on his head
  1393.         to better the linearity, but his proof had a bug in it until
  1394.         the 1980 SIAM J. Comput. retraction.  Would you want to code
  1395.         something that even Knuth trips up on?
  1396.  
  1397.          Now to assuage nagging feelings that geneticists might want
  1398.         to search entire libraries of 9000-unit nucleotide protein
  1399.         sequences for ((AGCA|TTGCA).*TGC)|AGCT)?T?A+ or some nonsense
  1400.         which MIGHT be nonlinear, you would want delta2.  So convince
  1401.         someone to do the Galil/Apostolico/Giancarlo 2n comparison
  1402.         worst case stuff.  See egrep.c for reference.
  1403.         
  1404.     Gosper, W. (HAKMEM 1972):
  1405.         Gosper didn't get around to the Thompson-like machine until
  1406.         1972 with HAKMEM.  His PDP 10 code is nevertheless valiant.
  1407.         He is also (barely) credited with conceiving the backwards
  1408.         match idea independently.  Where is he now?
  1409.         
  1410.     Morris/Pratt:
  1411.         Nice guys, but for this purpose, has-beens.
  1412.         Neat to see a hacker's triumph bury some theory.
  1413.  
  1414.     Horspool (Software Practice & Experience, 1980):
  1415.         Now here's a Canadian after the heart of things
  1416.         (perfect hashing, text compression, NP-complete
  1417.         code generation probs., etc.)  Did some Amdahl
  1418.         timings to show that delta2 is not so hot.
  1419.         Knows about Search For Least Frequent Character First,
  1420.         which is useful for short patterns. 
  1421.  
  1422.     {,e,f}grep man page:
  1423.         The laughable bugnote "but we do not know a single algorithm
  1424.         that spans a wide enough range of space-time tradeoffs"
  1425.         certainly presumes that there is no such thing as switching
  1426.         logic.  How the 'grep' family got into a multiple-version
  1427.         mess is probably a Guy Harris story; 'egrep' looks like the
  1428.         winner, as its functionality is pretty much a superset of
  1429.         the other two.  The K & P teaser (p. 105) offers hope for
  1430.         unification, but we see no difference with extant V8 code.
  1431.  
  1432.      "Not cited in the text" -- the sexy randomized Karp/Rabin string searcher
  1433. (Sedgewick, Algorithms, or Karp's Turing Award Lecture), and the ribald classic
  1434. Time Warps, String Edits, and Macromolecules -- The Theory and Practice
  1435. of Sequence Comparison (Kruskal & Sankoff).  Inquire within.
  1436. Thanks for your patience,
  1437.  
  1438.      James A. Woods (ames!jaw)
  1439.      NASA Ames Research Center
  1440.  
  1441. P.S.
  1442.      Current applications for Boyer-Moore code include modification of 
  1443. 'fastfind' for true speed, as well as substring search for 'grab', both
  1444. benefiting from BM-style search thru incrementally-compressed files/indices.
  1445.  
  1446. End of pep4grep.doc2
  1447. echo pep4grep.doc3 1>&2
  1448. cat > pep4grep.doc3 <<'End of pep4grep.doc3'
  1449. Subject: Get Hep to Kanji-Ready Five-Algorithm [ef]?grep
  1450.  
  1451. #  "I need very little,
  1452.       and of that little,
  1453.          I need very little."  -- St. Francis of Assisi
  1454.  
  1455.      Hybrid blitz 'egrep', whose urquell is a veritable chimaera of at least
  1456. five string search techniques, is now further tuned.
  1457.  
  1458.      Posted to USENET (and the mod.sources archive) some months ago, our
  1459. implementation of "plug-compatible" egrep.c has been extended to support:
  1460.  
  1461.     transparent 'grep' expression translation, to bring the speed of
  1462.     hyper-'egrep' to bear upon searches specified via the less capable
  1463.     'grep' syntax.
  1464.  
  1465.     interception of 'fgrep' for alternations of low (<= 7) cardinality,
  1466.     using a novel method of Boyer-Moore table superimposition and
  1467.     pre-computation magic.  the resulting speedup applies also to simple
  1468.     metacharacter-free 'egrep'-style alternations.
  1469.  
  1470.     (the above two improvements are made invisible by linking the
  1471.     grep/egrep/fgrep triumvirate.)
  1472.  
  1473.     a revised strategy of fallback to standard 'egrep' for hard
  1474.     cases, which eliminates costly popen() plumbing in favor of a
  1475.     statistically-based re-exec() dynamic.
  1476.  
  1477.     more complete application of fast match to standard options,
  1478.     including -n line numbering.
  1479.  
  1480.     preparation for Kanji pattern input, based upon parity-marked EUC
  1481.     codes.  new egrep.c is "eight-bit clean".  the fast algorithms
  1482.     unfortunately currently apply only to meta-free patterns and
  1483.     simple alternations; full Kanji regular expression treatment
  1484.     remains problematic.  however, the new code will pass difficult
  1485.     input through to [ef]?grep utilities in the UNIX Japan standard
  1486.     substrate.
  1487.  
  1488.      Kanji capability is perhaps the most important addition, as the
  1489. number of UNIX systems in the Orient proliferate, providing a "new market"
  1490. for Boyer-Moore-style search.  However, actual search efficacy remains
  1491. unknown until the Gaijin author gains feedback from JUNET or points beyond.
  1492. For all we know, Nippon text search utilities may already incorporate
  1493. the methods.  Tests conducted so far have been with artificial Kanji files.
  1494.  
  1495.      In case you are w(o|a)ndering, be reminded that no vendor source
  1496. changes are required to use the code.  It is configured as a turbo-charged
  1497. "front-end" to the existing section one commands, though it is (barely)
  1498. conceivable to adapt things, at a loss in worst-case efficiency, for
  1499. (heaven forfend!) non-Unix systems running C.  And, since we do not offer
  1500. a minimalist grep, do not expect it to run well on minimalist UNIX clones.
  1501.  
  1502.      Below appears a brief timing run on Webster's 2nd wordlist.  Notes
  1503. on implementation changes since original release follow in the next message.
  1504. If you want to skip the rest, fine.  The easy instructions -- download
  1505. from comp.sources [or 'anonymous' ftp of egrep.shar.Z from ames-aurora.arpa
  1506. for the (im)patient], and run:
  1507.  
  1508.     make
  1509.     sh eg.shell    # regression test amusement
  1510.     make install
  1511.  
  1512. after perusing README.FIRST.  Though the bundle in ~ftp/pub at NASA Ames
  1513. Research Center contains prerequisite support from Univ. of Toronto's
  1514. Henry Spencer, we are not re-posting regcomp()/regexec() to comp.sources.
  1515. John Gilmore of the GNU project has a modified regexec(), but it is not
  1516. mandatory for running the new egrep.
  1517.  
  1518.      Contrary to popular belief, old egrep is not I/O bound for large
  1519. large files on most machines.  The new version is.  One sample:
  1520.  
  1521.     time egrep 'u.*nix' /usr/dict/web2    (2.5 MB)
  1522.       (yielding {Coturnix, Pseudophoenix, [Tt]urnix}), shows
  1523.  
  1524.                 user     sys      real     (load ave. < 1)
  1525.  
  1526.     VAX 11/750, 4.3 BSD, Fujitsu Eagles
  1527.        (new)    6.8      3.8       11
  1528.        (old)       70.0      5.5       87
  1529.  
  1530.     Sun 3/160, 3.2 OS, Eagle on SMD
  1531.        (new)    1.7      2.2        5
  1532.        (old)       14.7      1.5       16
  1533.  
  1534.     Cray 2, Sys 5, no disk striping
  1535.        (new)        .93      .11        1
  1536.        (old)       8.07      .21        8
  1537.  
  1538. notes:  New egrep was actually run with -i option, but not old egrep.
  1539. Also, fumbling for three-character residue is not [ef]?grep's forte,
  1540. so the example is conservative.
  1541.  
  1542. Sun 3 has higher sys time for some unknown reason (a guess:  VAX 4.3 kernel
  1543. handles read() calls with oddsize buffers differently?).  Cray 2 reportedly
  1544. does disk I/O at 5-10 megabytes per second, but the architecture/compiler
  1545. is bad at byte addressing -- no cache, no vectors here.  Unfair comparison:
  1546. new egrep on Sun beats old egrep on Cray 2, even with fast Cray I/O!
  1547.  
  1548. Speculation:  the code might be useful on the Macintosh II, even if the Unix
  1549. filesystem (Sys 5?) were to waste 3/4 of the 1 MB/sec SCSI disk bandwidth.
  1550. Mac 2 testers please forward info to ames!jaw.
  1551.  
  1552.      Another metric is inner loop efficiency:
  1553.  
  1554.                 # instructions
  1555.     VAX Berkeley cc            5
  1556.     Sun 68020 3.2 cc        6
  1557.     Stallman's GNU 68020 cc        4
  1558.     MIPS R2000            6
  1559.     Cray 2                   25
  1560.  
  1561. Thanks goes to mips!dce (David Elliott) for his testing time, as well as
  1562. to RMS for two-upping Sun's C compiler.
  1563.  
  1564.      Of course, if you have a Connection Machine dedicated to running their
  1565. admirable full-text keyworder on "in-core" text, you won't need [ef]?grep at
  1566. all.  And, for unindexed text on fine-grained parallel machines, reg. expr.
  1567. search algorithms can be made to run with a lower time bound (see the Hillis
  1568. book).  But if your files are on disk, even a specialized search chip won't help
  1569. once things become I/O or bus limited.  For this reason, vectorization on a
  1570. Cray(ette) would be a bust, though Cray buffs may write the author for other
  1571. scalar speedup ideas...
  1572.  
  1573. [continued]
  1574. End of pep4grep.doc3
  1575. echo pep4grep.doc4 1>&2
  1576. cat > pep4grep.doc4 <<'End of pep4grep.doc4'
  1577. #  How long a time lies in one little word! -- Shakespeare, Richard II, I, iii
  1578.  
  1579. #  Fine words butter no parsnips. -- Southern proverb
  1580.  
  1581.         [ef]?grep Implementation Changes
  1582.  
  1583. 'grep' r.e. translation:
  1584.  
  1585.      To buy speed for the novice 'grep' user who deigns not to learn the
  1586. extended 'egrep' syntax, we translate 'grep' r.e.'s to the 'egrep' superset.
  1587. It is straightforward enough to surround search patterns meaningful to
  1588. 'egrep' but not to 'grep'.  Odd cases include the -w option, not implemented
  1589. in standard 'egrep', the defunct -y option, and "tagged expressions", which
  1590. are done via an exec() of /bin/grep.  Tagged exprs, like
  1591.  
  1592.     grep '\(....\).*\1' /usr/dict/words
  1593.  
  1594. which outputs chaff like "beriberi", "couscous", "hodgepodge", and
  1595. "lightweight", are weird.  The irregularity these exprs lend coupled with
  1596. a low complexity/utility ratio kept them from being part of 'egrep'.
  1597. But for this feature, old 'grep' code could be thrown away.
  1598.  
  1599. 'fgrep' improvement / (partial) unification:
  1600.  
  1601.      In the new release, we trap low-complexity disjunctions such as
  1602.  
  1603.         egrep 'boyer|moore' file
  1604. or
  1605.         fgrep 'boyer\n
  1606.         moore' file
  1607.  
  1608. (or with "-f patfile" in place of the pattern) with a method to superimpose
  1609. the non-terminals within the Boyer/Moore table.  When scanning text backwards,
  1610. other programming tricks short-circuit some tests against the pattern.
  1611. Sparing further details, which might make for a more formal writeup, it
  1612. suffices to say that although worst-case complexity here is O(Rn) with string
  1613. length 'n', and R == r.e. size, average-case for text is still sublinear.  E.g.
  1614.  
  1615.     egrep 'silver|orange|purple'      # hard-to-rhyme color test in eg.shell
  1616.  
  1617. looks at ~55000 chars in /usr/dict/words, whereas (three) separate invocations
  1618. of egrep on the individual color words make the code look at ~40000 bytes per
  1619. word.  Aho/Corrasick's 'fgrep', in contrast, must look at all 200KB in the
  1620. dictionary.  The elegant "trie" construction within "fgrep" excels, however,
  1621. for medium/large R.  An equally ambitious "reverse trie", supplementing our
  1622. extant "alternation mush", would attenuate worst-case behavior while preserving
  1623. low R speedup.  We save the addition for another day.
  1624.  
  1625.      Since the syntax for [ef]grep is similar, we thought of making egrep
  1626. hand off to fgrep for sufficiently large metacharacter-free R, as there is no
  1627. strong reason to make the user conscious of the separate algorithms.  Certain
  1628. technicalities prevent this.  For one, we are not willing to invent an 'egrep'
  1629. option to inform the code to interpret a file of (say a hundred) word
  1630. alternatives containing some innocent metacharacter, that it is literal
  1631. 'fgrep' input, rather than a closure-containing 'egrep' pattern which would
  1632. otherwise make egrep explode.  More work could be done here.
  1633.  
  1634.      Our motivation?  Is this not all overblown?  Perhaps, but now you can
  1635. build a simple fast "NSA filter", or search for the seven dwarfs at leisure.
  1636. Besides, the final nail needed to be driven into 'bm/match', which tried
  1637. to do parallel match, but actually shuffled things out of order during its
  1638. simplistic block-based scheme.  These programs, part of source archive also,
  1639. are now historical curiosities.
  1640.  
  1641. Kanji egrep:
  1642.  
  1643.      Copious notes are in README.kanji.mods.  The March 1987 Unix Review
  1644. was indispensable for pointing out the embedded "SS2" Katakana pitfalls.
  1645. The modularity of our code as a semi-dependent filter was necessary for this
  1646. exploration, as we have no access to AT&T/Unisoft Kanji code.  Again, JUNET
  1647. or Sigma project people -- please respond with grep war stories or usage notes.
  1648.  
  1649. Worst-case r.e. handling:
  1650.  
  1651.      The first code release elaborately called upon a function mcilroy()
  1652. to pipe partial match output to old egrep for tough expressions, whose
  1653. backtracking might swamp regexp().  Some details of the DFA/NDFA tradeoff
  1654. were discussed in pep4grep.doc[12].  Due largely to feedback from John Gilmore
  1655. of the GNU project, the strategy was revised.  egrep.c function kernighan()
  1656. ("let others do the hard part") now usurps calls to costly popen() by invoking
  1657. exec() on old egrep when necessary.  Rough partial match statistics gathered
  1658. on the fly determine the handoff.  You may revise the time reported previously
  1659. for
  1660.     egrep 'hoe.*g' /usr/dict/words
  1661.  
  1662. from 1.2 user, 1.1 sys seconds (VAX 11/750, 4.3BSD, Fuji disks) to 0.8u, 0.4s.
  1663. For those public-spirited souls who really want to build a PD egrep out of
  1664. what we offer, sans fallback from regexp() to an AT&T /usr/bin/egrep, the
  1665. slippery test "egrep 'g+h+o' /usr/dict/words" will prove enlightening.
  1666.  
  1667. Faster -n option:
  1668.  
  1669.      By popular demand.  Though Boyer/Moore techniques subvert line numbering,
  1670. we've made it faster with brute force (loop unrolling helps VAXEN, but not
  1671. CRISPS).  Timing tests for this and other options appear in the eg.shell script.
  1672.  
  1673. Not so fast:
  1674.  
  1675.     -v, -b, -w, various r.e.'s with no rexexp() "residue"
  1676.  
  1677. (you'll still have to use the layered "grep host /etc/hosts | grep -w host"
  1678. for speed.)
  1679.  
  1680. Other contra-indications for new [ef]?grep:
  1681.  
  1682.     Monster patterns
  1683.  
  1684.      The amazing expressions output by /usr/lib/calendar still beg for
  1685. the lazy evaluation technique rolled into edition 8 egrep by Prof. Aho of
  1686. Princeton.  Hinted at on p. 105 in Kernighan & Pike, lazy evaluation reduces
  1687. standard egrep r.e. compile time.  Here the possible O(R**2) machine
  1688. construction cost is eliminated to amortize complexity at run-time and 
  1689. shifted to such only if a bad match actually happens.  Whew!  Fortunately,
  1690. this is not so important for simple r.e. fare, where H. Spencer's regexp()
  1691. works well, but it certainly helps calendar(1).
  1692.  
  1693.      The catch with lazy eval. is that it slows down simple matching (15-20%
  1694. for /usr/dict/words on VAX), so it hasn't been adopted by System V egrep.
  1695. Note that our egrep, deferring to the underlying one in /usr/bin, doesn't
  1696. care much about these hideous beasts -- it just doesn't do better on them.
  1697. However, [ef]?grep does well by the Kadhafi matcher (eg.shell, again).
  1698.  
  1699.     Long lines, small alphabets
  1700.  
  1701.      Finally, a comment on one rapidly burgeoning application area
  1702. where new egrep should not be blindly proscribed -- genome sequencing.
  1703. Though line limits have been raised (to 8192 byte buffers), much of
  1704. GENBANK has no newlines.  The code would need modification for scanning
  1705. freestyle.  Also, locating ACGT sequences with the current "superimposed BMG"
  1706. over a 4-letter alphabet might actually be worse, but the global homology
  1707. crowd probably uses a >20 letter protein alphabet (for other reasons).
  1708. At any rate, genetic string search generally relies on more sophisticated
  1709. methods such as dynamic programming ala Sankoff/Kruskal.
  1710.  
  1711.      On the other hand, large alphabets such as Kanji probably help
  1712. performance.  As do parallel transfer disks, MACH file mapping, ...
  1713. Your suggestions welcome.
  1714.  
  1715.      James A. Woods (ames!jaw)
  1716.      NASA Ames Research Center
  1717.  
  1718. P.S.  Preserving author credit, [ef]?grep may be redistributed as you wish.
  1719. End of pep4grep.doc4
  1720. echo regerror.c 1>&2
  1721. cat > regerror.c <<'End of regerror.c'
  1722. #include <stdio.h>
  1723.  
  1724. void
  1725. regerror(s)
  1726. char *s;
  1727. {
  1728. #ifdef ERRAVAIL
  1729.     error("regexp: %s", s);
  1730. #else
  1731. /*
  1732.     fprintf(stderr, "regexp(3): %s\n", s);
  1733.     exit(1);
  1734. */
  1735.     return;      /* let std. egrep handle errors */
  1736. #endif
  1737.     /* NOTREACHED */
  1738. }
  1739. End of regerror.c
  1740. cat k.test | tr W '\200' | tr X '\201' | tr Y '\202' | tr Z '\216' > kanji.fake.test
  1741. cat k.pat | tr X '\201' | tr Y '\202' > kanjipat.fake
  1742. rm k.test k.pat
  1743. -- 
  1744. Rich $alz            rsalz@pineapple.bbn.com
  1745. Cronus Project, BBN Labs    "Anger is an energy"
  1746.