1/*
2  tre-filter.c: Histogram filter to quickly find regexp match candidates
3
4  This software is released under a BSD-style license.
5  See the file LICENSE for details and copyright.
6
7*/
8
9/* The idea of this filter is quite simple.  First, let's assume the
10   search pattern is a simple string.  In order for a substring of a
11   longer string to match the search pattern, it must have the same
12   numbers of different characters as the pattern, and those
13   characters must occur in the same order as they occur in pattern. */
14
15#ifdef HAVE_CONFIG_H
16#include <config.h>
17#endif /* HAVE_CONFIG_H */
18#include <stdio.h>
19#include "tre-internal.h"
20#include "tre-filter.h"
21
22int
23tre_filter_find(const unsigned char *str, size_t len, tre_filter_t *filter)
24{
25  unsigned short counts[256];
26  unsigned int i;
27  unsigned int window_len = filter->window_len;
28  tre_filter_profile_t *profile = filter->profile;
29  const unsigned char *str_orig = str;
30
31  DPRINT(("tre_filter_find: %.*s\n", len, str));
32
33  for (i = 0; i < elementsof(counts); i++)
34    counts[i] = 0;
35
36  i = 0;
37  while (*str && i < window_len && i < len)
38    {
39      counts[*str]++;
40      i++;
41      str++;
42      len--;
43    }
44
45  while (len > 0)
46    {
47      tre_filter_profile_t *p;
48      counts[*str]++;
49      counts[*(str - window_len)]--;
50
51      p = profile;
52      while (p->ch)
53	{
54	  if (counts[p->ch] < p->count)
55	    break;
56	  p++;
57	}
58      if (!p->ch)
59	{
60	  DPRINT(("Found possible match at %d\n",
61		  str - str_orig));
62	  return str - str_orig;
63	}
64      else
65	{
66	  DPRINT(("No match so far...\n"));
67	}
68      len--;
69      str++;
70    }
71  DPRINT(("This string cannot match.\n"));
72  return -1;
73}
74