home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / sources / 2537 / boyermoo.c next >
Encoding:
C/C++ Source or Header  |  1992-11-17  |  9.7 KB  |  282 lines
  1. /* 
  2.  * Copyright 1990 Karl Lehenbauer, Mark Diekhans, 
  3.  *                Peter da Silva and Jordan Henderson.
  4.  *
  5.  * Permission to use, copy, modify, and distribute this
  6.  * software and its documentation for any purpose and without
  7.  * fee is hereby granted, provided that the above copyright
  8.  * notice appear in all copies.  Karl Lehenbauer, Mark Diekhans,
  9.  * Peter da Silva and Jordan Henderson make no representations
  10.  * about the suitability of this software for any purpose.
  11.  * It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. /*
  15.  * 
  16.  * Hacked to run under Sys V by karl, Sat Sep  8 09:25:55 CDT 1990
  17.  * 
  18.  * Hacked to have a separate routine to precompile the pattern delta table
  19.  * and such by karl, too
  20.  * 
  21.  * From: chris@mimsy.umd.edu (Chris Torek)
  22.  * Newsgroups: alt.sources
  23.  * Subject: [comp.lang.c] Re: strstr sources: a summary of responses
  24.  * Keywords: ANSI lib, strstr
  25.  * Message-ID: <1990Aug27.191251.21720@math.lsa.umich.edu>
  26.  * Date: 27 Aug 90 19:12:51 GMT
  27.  * Organization: University of Michigan, Department of Mathematics
  28.  * X-Original-Newsgroups: comp.lang.c
  29.  * 
  30.  * Archive-name: torek-boyer-moore/27-Aug-90
  31.  * Original-posting-by: chris@mimsy.umd.edu (Chris Torek)
  32.  * Original-subject: Re: strstr sources: a summary of responses
  33.  * Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)
  34.  * 
  35.  * In article <1158@umvlsi.ecs.umass.edu> srivasta@umvlsi.ecs.umass.edu
  36.  * (Manoj Srivastava) posts a Boyer-Moore based strstr() by John Lacey.
  37.  * 
  38.  * >And finally, an implementation of the Boyer-Moore algorithm. I
  39.  * >am not sure offhand, but while the worst case complexity remains
  40.  * >O(N+M), the avg case behavior is O(N/M) ???
  41.  * 
  42.  * (where N is the length of the string being searched and M is the length
  43.  * of the substring, aka pattern).  Yes, it is N/M.
  44.  * 
  45.  * Next, the code:
  46.  * 
  47.  * > strstr
  48.  *  [some stuff deleted]
  49.  * >int ch, d[SCHAR_MAX + 1];
  50.  *  [more stuff deleted]
  51.  * >      i += d[text[i]];
  52.  *  [still more deleted]
  53.  * 
  54.  * If `char' is signed, and a string containing a negative character value
  55.  * is passed to strstr(), this code can attempt to fetch, e.g., d[-40].  I
  56.  * found the code overly difficult to read, so I rewrote it.  I also wrote
  57.  * a long comment describing the algorithm.  This has been only lightly
  58.  * tested, but is simple enough that it should work.  Note that this
  59.  * version handles strings with embedded NULL characters as well.
  60.  * 
  61.  * 
  62.  */
  63.  
  64. #ifndef NOSCCSID
  65.         static char *sccs_id = "%M% %I% %H%";
  66. #endif
  67.  
  68. #ifdef M_XENIX
  69. # define XENIX
  70. # define XENIX286 1
  71. #endif
  72.  
  73. #if defined(XENIX) || defined(BSD)
  74. #  define CHAR_MAX 255
  75. #else
  76. #  include <limits.h>
  77. #endif
  78.  
  79. #if XENIX286
  80.   typedef int size_t;
  81. #endif
  82.  
  83. #include <sys/types.h>
  84. #include <stdio.h>
  85.  
  86. typedef char *PTR;              /* `char *' for old compilers */
  87. #define ckalloc malloc
  88. char *malloc();
  89.  
  90. struct compiled_search_struct {
  91.         size_t patlen;
  92.         size_t deltaspace[CHAR_MAX + 1];
  93. };
  94.  
  95. /*
  96.  * Boyer-Moore search: input is `text' (a string) and its length,
  97.  * and a `pattern' (another string) and its length.
  98.  *
  99.  * The linear setup cost of this function is approximately 256 + patlen.
  100.  * Afterwards, however, the average cost is O(textlen/patlen), and the
  101.  * worst case is O(textlen+patlen).
  102.  *
  103.  * The Boyer-Moore algorithm works by observing that, for each position
  104.  * in the text, if the character there does *not* occur somewhere in the
  105.  * search pattern, no comparisons including that character will match.
  106.  * That is, given the text "hello world..." and the pattern "goodbye", the
  107.  * `w' in `world' means that none of `hello w', `ello wo', `llo wor',
  108.  * `lo worl', `o world', ` world.', and `world..' can match.  In fact,
  109.  * exactly patlen strings are certain not to match.  We can discover this
  110.  * simply by looking at the patlen'th character.  Furthermore, even if
  111.  * the text character does occur, it may be that it rules out some number
  112.  * of other matches.  Again, we can discover this by doing the match
  113.  * `backwards'.
  114.  *
  115.  * We set up a table of deltas for each possible character, with
  116.  * delta[character] being patlen for characters not in the pattern,
  117.  * less for characters in the pattern, growing progressively smaller
  118.  * as we near the end of the pattern.  Matching then works as follows:
  119.  *
  120.  *       0         1         2         3
  121.  *       01234567890123456789012345678901234567
  122.  *      "Here is the string being searched into"        (text)
  123.  *       ------                                         (pos = [0..5])
  124.  *      "string"                                        (pat)
  125.  *      654321-                                         (deltas)
  126.  *
  127.  * (the delta for `-' will be derived below).
  128.  *
  129.  * Positions 0..5 end with `i', which is not the `g' we want.  `i' does
  130.  * appear in `string', but two characters before the end.  We skip
  131.  * forward so as to make the `i's match up:
  132.  *
  133.  *      "Here is the string being searched into"        (text)
  134.  *        "string"                                      (pos = [2..7])
  135.  *
  136.  * Next we find that ` ' and `g' do not match.  Since ` ' does not appear
  137.  * in the pattern at all, we can skip forward 6:
  138.  *
  139.  *      "Here is the string being searched into"        (text)
  140.  *              "string"                                (pos = [8..13])
  141.  *
  142.  * Comparing `t' vs `g', we again find no match, and so we obtain the
  143.  * delta for `t', which is 4.  We skip to position 17:
  144.  *
  145.  *      "Here is the string being searched into"        (text)
  146.  *                  "string"                            (pos = [12..17])
  147.  *
  148.  * It thus takes only four steps to move the search point forward to the
  149.  * match, in this case.
  150.  *
  151.  * If the pattern has a recurring character, we must set the delta for
  152.  * that character to the distance of the one closest to the end:
  153.  *
  154.  *      "befuddle the cat"      (text)
  155.  *      "fuddle"                (pos = [0..5])
  156.  *      654321-                 (delta)
  157.  *
  158.  * We want the next search to line the `d's up like this:
  159.  *
  160.  *      "befuddle the cat"      (text)
  161.  *        "fuddle"              (pos = [2..7])
  162.  *
  163.  * and not like this:
  164.  *
  165.  *      "befuddle the cat"      (text)
  166.  *         "fuddle"             (pos = [3..8])
  167.  *
  168.  * so we take the smaller delta for d, i.e., 2.
  169.  *
  170.  * The last task is computing the delta we have noted above as `-':
  171.  *
  172.  *      "candlesticks"          (text)
  173.  *      "hand"                  (pos = [0..3])
  174.  *      4321-                   (delta)
  175.  *
  176.  * Here the `d' in `hand' matches the `d' in `candlesticks', but the
  177.  * strings differ.  Since there are no other `d's in `hand', we know
  178.  * that none of (cand,andl,ndle,dles) can match, and thus we want this
  179.  * delta to be 4 (the length of the pattern).  But if we had, e.g.:
  180.  *
  181.  *      "candlesticks"          (text)
  182.  *      "deed"                  (pos = [0..3])
  183.  *      4321-                   (delta)
  184.  *
  185.  * then we should advance to line up the other `d':
  186.  *
  187.  *      "candlesticks"          (text)
  188.  *         "deed"               (pos = [3..6])
  189.  *
  190.  * As this suggests, the delta should be that for the `d' nearest the
  191.  * end, but not including the end.  This is easily managed by setting up
  192.  * a delta table as follows:
  193.  *
  194.  *      for int:c in [0..255] { delta[c] = patlen; };
  195.  *      for int:x in [0..patlen-1) { delta[pat[x]] = patlen - (x + 1); };
  196.  *
  197.  * delta[pat[patlen-1]] is never written, so the last letter inherits the
  198.  * delta from an earlier iteration or from the previous loop.
  199.  *
  200.  * NB: the nonsense with `deltaspace' below exists merely because gcc
  201.  * does a horrible job of common subexpression elimination (it does not
  202.  * notice that the array is at a constant stack address).
  203.  */
  204.  
  205. char *
  206. boyer_moore_search_compile(pat, patlen)
  207. char *pat;
  208. int patlen;
  209. {
  210.         register unsigned char *p, *t;
  211.         register size_t i, p1, j, *delta;
  212.         struct compiled_search_struct *cp;
  213.         int alloc_len;
  214.  
  215.         /* algorithm fails if pattern is empty */
  216.         if ((p1 = patlen) == 0)
  217.                 return (NULL);
  218.  
  219.         alloc_len = sizeof(struct compiled_search_struct) + patlen + 1;
  220.         cp = (struct compiled_search_struct *)ckalloc(alloc_len);
  221.  
  222.         strncpy((char *)cp+sizeof(struct compiled_search_struct), pat, patlen);
  223.         *((char *)cp+alloc_len-1) = '\0';
  224.  
  225.         /* set up deltas */
  226.         delta = cp->deltaspace;
  227.  
  228.         for (i = 0; i <= CHAR_MAX; i++)
  229.                 delta[i] = p1;
  230.  
  231.         for (p = (unsigned char *)pat, i = p1; --i > 0;)
  232.                 delta[*p++] = i;
  233.  
  234.         cp->patlen = patlen;
  235.         return((char*) cp);
  236. }
  237.  
  238.  
  239. char *
  240. boyer_moore_search_execute(text, textlen, compPtr, patLenP)
  241.         char     *text;
  242.         size_t    textlen;
  243.         char     *compPtr;
  244.         unsigned *patLenP;
  245. {
  246.         register unsigned char *p, *t;
  247.         struct compiled_search_struct *csp = 
  248.             (struct compiled_search_struct*) compPtr;
  249.         register size_t i, p1, j, *delta = csp->deltaspace;
  250.         char *pat;
  251.         size_t patlen;
  252.  
  253.         *patLenP = p1 = patlen = csp->patlen;
  254.         /* code below fails (whenever i is unsigned) if pattern too long */
  255.         if (p1 > textlen)
  256.                 return (NULL);
  257.  
  258.         pat = (char *)csp + sizeof(struct compiled_search_struct);
  259.         /*
  260.          * From now on, we want patlen - 1.
  261.          * In the loop below, p points to the end of the pattern,
  262.          * t points to the end of the text to be tested against the
  263.          * pattern, and i counts the amount of text remaining, not
  264.          * including the part to be tested.
  265.          */
  266.         p1--;
  267.         p = (unsigned char *)pat + p1;
  268.         t = (unsigned char *)text + p1;
  269.         i = textlen - patlen;
  270.         for (;;) {
  271.                 if (*p == *t && memcmp((PTR)(p - p1), (PTR)(t - p1), p1) == 0)
  272.                         return ((char *)t - p1);
  273.                 j = delta[*t];
  274.                 if (i < j)
  275.                         break;
  276.                 i -= j;
  277.                 t += j;
  278.         }
  279.         return (NULL);
  280. }
  281.  
  282.