Re: [Patch] faster fnmatch

[Ondrej Bilka]

I send new version according to your comments
On Fri, May 01, 2009 at 02:51:48PM +0200, Bruno Haible wrote:
>
> Hmm, well, users are expecting a speedup through your module always. If it
> some (not too rare) cases the glibc fnmatch is faster, it's difficult to
> convince people to use your function.
In most cases we are slower because I fallback to fnmatch. I added this for 
convience that you dont need check if pattern can be compiled. Now I added 
fnmatch_fallbacked to check this and if performance is concern you could call 
fnmatch manualy.

> 
> The general and hard case is the multibyte encoding case, where the encoding
> is something like GB18030, BIG5, or similar. Single-byte encodings may be
> worth optimizing for, because the C locale on glibc systems uses a single-byte
> encoding. Whether UTF-8 is worth special-casing, depends on the complexity.
>
I think I can process these encodings when encoding is stateless. 
I try my code, If I fail I know string doesnt contain pattern.
If I succeed I call fnmatch to check it isn't false positive. 
Also - in bracket is solved by replacing bracket by ? and checking false 
positives.

> > +struct _fnmatch_state;
> > +typedef struct _fnmatch_state fnmatch_state;
> 
> Is it really a "state", i.e. a data structure that is modified over and
> over again? I would have expected a compiled pattern data structure, that
> is created by fnmatch_compile and then left unchanged until fnmatch_free.
I named it state because it captures state of underlying NFA. Do you have 
better name?

> 
> > +#include <stdint.h>
> > +
> > +#define  _GNU_SOURCE
> 
> "#define GNU_SOURCE" has no effect after a system include file such as 
> <stdint.h>
> was already included. Also, "#define _GNU_SOURCE" has no effect on Solaris.
> For this reason, gnulib has a module 'extensions' which does the right thing
> (and which you're already using).
I copied this from fnmatch source. If I dont define FNM_EXTMATCH and so is 
undefined. How do it correctly?

> > +  uint32_t hash[8];
> 
> For better portability, write (UCHAR_MAX / 32) + 1 instead of 8.
Ok but 16b char(if this exist) could make table too big.

diff --git a/MODULES.html.sh b/MODULES.html.sh
index 06afa2d..03d308e 100755
--- a/MODULES.html.sh
+++ b/MODULES.html.sh
@@ -61,6 +61,7 @@ fenv
 float
 fmtmsg
 fnmatch
+fnmatchcomp
 ftw
 glob
 grp
@@ -418,6 +419,7 @@ fmodf
 fmodl
 fmtmsg
 fnmatch
+fnmatchcomp
 fopen
 fork
 fpathconf
diff --git a/lib/fnmatchcomp.c b/lib/fnmatchcomp.c
new file mode 100644
index 0000000..2709e02
--- /dev/null
+++ b/lib/fnmatchcomp.c
@@ -0,0 +1,526 @@
+  /* Copyright (C) 2009
+     Ondrej Bilka < address@hidden >
+
+     This program is free software: you can redistribute it and/or modif y
+     it under the terms of the GNU General Public License as published by
+     the Free Software Foundation; either version 3 of the License, or
+     (at your option) any later version.
+
+     This program is distributed in the hope that it will be useful,
+     but WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+     GNU General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with this program. If not, see < http://      www.gnu.org/licenses/ 
> . */
+
+#include <stdint.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <nl_types.h>
+#include <langinfo.h>
+#include <locale.h>
+#include <ctype.h>
+
+#define  _GNU_SOURCE
+#include <fnmatch.h>
+#include "fnmatchcomp.h"
+
+#define  UINT4 uint32_t
+#define  UINT2 uint16_t
+#define  CHARSPERINT (sizeof (UINT4)/sizeof(char))
+#define  STREQ(a, b) (strcmp(a, b) == 0)
+#define  MAX_PATTERN_SIZE (2*sizeof (bracket_pattern))
+#define  NULTEST(...) if (__builtin_expect(!(__VA_ARGS__),0)) return NULL;
+#define  NULTEST2(...) if (__builtin_expect(!(__VA_ARGS__),0)) return -1;
+typedef struct
+{
+  char tp;
+  char chr;
+} chr_pattern;
+typedef struct
+{
+  char tp;
+  char chars[CHARSPERINT];
+  short sizerest;
+  short charno;
+} star_pattern;
+typedef struct
+{
+  char tp;
+} end_pattern;
+typedef struct
+{
+  char tp;
+} endstar_pattern;
+typedef struct
+{
+  char tp;
+  char flags;
+  char *chars;
+  int sizerest;
+  uint32_t hash[(UCHAR_MAX / 32) + 1];
+} bracket_pattern;
+typedef struct
+{
+  char tp;
+} begindot_pattern;
+typedef struct
+{
+  char tp;
+} slashend_pattern;
+typedef struct
+{
+  char tp;
+  char *ptr;
+  char *prefix;
+  int flags;
+} fallback_pattern;
+typedef struct
+{
+  char tp;
+  void *states;
+} fold_pattern;
+typedef struct
+{
+  char tp;
+  void *states;
+  fallback_pattern *fallback;
+} checkneeded_pattern;
+
+typedef star_pattern starslash_pattern;
+enum PATTERNS
+{
+  PATTERN_chr,
+  PATTERN_star,
+  PATTERN_starslash,
+  PATTERN_end,
+  PATTERN_endstar,
+  PATTERN_bracket,
+  PATTERN_begindot,
+  PATTERN_slashend,
+  PATTERN_fallback,
+  PATTERN_fold,
+  PATTERN_checkneeded
+};
+union _patterns
+{
+  chr_pattern chr;
+  star_pattern star;
+  starslash_pattern starslash;
+  end_pattern end;
+  endstar_pattern endstar;
+  bracket_pattern bracket;
+  begindot_pattern begindot;
+  fallback_pattern fallback;
+  fold_pattern fold;
+  checkneeded_pattern checkneeded;
+};
+typedef union _patterns patterns;
+static void freepatterns (patterns * p);
+
+struct states
+{
+  patterns *p;
+  struct states *next;
+};
+struct _fnmatch_state
+{
+  struct states *states;
+  int flags;
+  int *refcount;
+  patterns *start;
+};
+
+int fnmatch_fallbacked(fnmatch_state * s){
+       return (s->states->p.tp == PATTERN_fallback);
+}
+static int
+ascii_compatible_encoding (const char *c)
+{
+  if (MB_CUR_MAX == 1 || STREQ (c, "UTF-8"))
+    return 0;
+  if (STREQ (c, "BIG5") || STREQ (c, "GB18030"))
+    return 1;
+  return 2;
+}
+
+static void
+strfold (const char *str, char *buf)
+{
+  while (*str)
+    *buf++ = tolower (*str++);
+  *buf = 0;
+}
+
+static fnmatch_state *
+initfnmatchstate ()
+{
+  fnmatch_state *st;
+  NULTEST (st = (fnmatch_state *) malloc (sizeof (fnmatch_state)));
+  NULTEST (st->states = malloc (sizeof (struct states)));
+  st->states->next = NULL;
+  NULTEST (st->refcount = malloc (sizeof (int)));
+  *st->refcount = 1;
+  return st;
+}
+
+static fnmatch_state *
+fnmatch_fallback (const char *str, int flags)
+{
+  fnmatch_state *st;
+  NULTEST (st = initfnmatchstate ());
+  NULTEST (st->start = st->states->p = malloc (sizeof (fallback_pattern)));
+  st->states->p->fallback.tp = PATTERN_fallback;
+  NULTEST (st->states->p->fallback.ptr = strdup (str));
+  st->states->p->fallback.flags = flags;
+  NULTEST (st->states->p->fallback.prefix = strdup (""));
+  return st;
+}
+
+static fnmatch_state *
+fold_fallback (fnmatch_state * s)
+{
+  fnmatch_state *st;
+  NULTEST (s);
+  NULTEST (st = initfnmatchstate ());
+  NULTEST (st->start = st->states->p = malloc (sizeof (fold_pattern)));
+  st->states->p->fold.tp = PATTERN_fold;
+  st->states->p->fold.states = (void *) s;
+  return st;
+}
+
+static fnmatch_state *
+checkneeded_fallback (fnmatch_state * s, fnmatch_state * fb)
+{
+  NULTEST (s);
+  NULTEST (fb);
+  fnmatch_state *st;
+  NULTEST (st = initfnmatchstate ());
+  NULTEST (st->start = st->states->p = malloc (sizeof (checkneeded_pattern)));
+  st->states->p->checkneeded.tp = PATTERN_checkneeded;
+  st->states->p->checkneeded.states = (void *) s;
+  st->states->p->checkneeded.fallback = (void *) fb;
+  return st;
+}
+
+static int
+parse_bracket (const char *str, patterns * pat, int flags)
+{
+  char *chr, lastbyte;
+  int mlen;
+  const char *s = str;
+  int i;
+  pat->bracket.tp = PATTERN_bracket;
+  if (*s == '!' || (getenv ("POSIXLY_CORRECT") != NULL && *s == '^'))
+    {
+      pat->bracket.flags = 1;
+      s++;
+    }
+
+  if (!pat->bracket.chars)
+    {
+      if (!(pat->bracket.chars = malloc (2 * strlen (s) + 2)))
+        return -3;
+    }
+  chr = pat->bracket.chars;
+  do
+    {
+      if (*s == 0 || *s == '-')
+        pat->bracket.flags = 5;
+      if (*s == '['
+          && (*(s + 1) == ':' || *(s + 1) == '=' || *(s + 1) == '.'))
+        return -1;
+      mlen = mblen (s, MB_CUR_MAX);
+      lastbyte = s[mlen - 1];
+      pat->bracket.hash[lastbyte / 32] |= 1 << (lastbyte % 32);
+      memcpy (chr, s, mlen);
+      s += mlen;
+      chr += mlen + 1;
+    }
+  while (*s && *s != ']');
+  *chr = 0;
+  if (pat->bracket.flags == 5)
+    {                           /* bracket is too complicated to process here
+                                   we replace it with ? and when we match 
entire pattern
+                                   we call fnmatch it wasn't false positive */
+      *pat->bracket.chars = 0;
+      for (i = 0; i < 8; i++)
+        pat->bracket.hash[i] = 0;
+    }
+  return s - str;
+}
+
+#define  NEXTPATTERN(type) pat->chr.tp = PATTERN_##type; pat = (patterns 
*)(((void *) pat)+sizeof (type##_pattern));
+#define  FALLBACK freepatterns(ret); free(ret);
+#define  BRACTEST(...) if ((__VA_ARGS__) == -3)  {FALLBACK; return NULL; }
+fnmatch_state *
+fnmatch_compile (const char *str, int flags)
+{
+  const char *s;
+  patterns *pat, *ret;
+  int i, pass;
+  int size = 0, patsize;
+  int checkneeded = 0;
+  char *codeset = nl_langinfo (CODESET);
+  char *buf;
+  if (ascii_compatible_encoding (codeset) == 1)
+    checkneeded = 1;
+  if (ascii_compatible_encoding (codeset) == 2)
+    {
+      return fnmatch_fallback (str, flags);
+    }
+  if (flags & FNM_CASEFOLD)
+    {
+      if (MB_CUR_MAX != 1)
+        return fnmatch_fallback (str, flags);
+      NULTEST (buf = malloc (2 * strlen (str)));
+      strfold (str, buf);
+      fnmatch_state *st =
+        fold_fallback (fnmatch_compile (buf, flags & (!FNM_CASEFOLD)));
+      NULTEST (st);
+      free (buf);
+      if (((fnmatch_state *) st->start->fold.states)->start->chr.tp
+          == PATTERN_fallback)
+        {
+          fnmatch_free (st);
+          return fnmatch_fallback (str, flags);
+        }
+      return st;
+    }
+
+  ret = (patterns *) calloc (1, strlen (str) * MAX_PATTERN_SIZE);
+
+  for (pass = 0; pass < 2; pass++)
+    {
+      /* two passes in first we compute values we use in second to optimize
+       */
+      patsize = size;
+      size = 0;
+      pat = ret;
+      if (flags & FNM_PERIOD && *str != '.')
+        {
+        NEXTPATTERN (begindot)}
+      for (s = str; *s; s++)
+        {
+          if (flags & FNM_EXTMATCH && *(s + 1) == '(' &&
+              (*s == '*' || *s == '+' || *s == '@' || *s == '!'))
+            {
+              FALLBACK;
+              return fnmatch_fallback (str, flags);
+            }
+          switch (*s)
+            {
+            case '*':
+              while (*(s + 1) == '?')
+                {
+                  BRACTEST (parse_bracket ("!", pat, flags));
+                  size++;
+                  pat->bracket.sizerest = patsize - size;
+                  NEXTPATTERN (bracket);
+                  s++;
+                }
+              if (*(s + 1))
+                {
+                  if (pass)
+                    {
+                      patterns *tmppat = pat;
+                      pat->star.sizerest = patsize - size;
+                      NEXTPATTERN (star);
+                      for (i = 0; pat->chr.tp == PATTERN_chr && pat->chr.chr
+                           && i < CHARSPERINT; i++)
+                        {
+                          tmppat->star.chars[i] = pat->chr.chr;
+                          NEXTPATTERN (chr);
+                        }
+                      if (i == 3)
+                        i = 2;
+                      tmppat->star.charno = i;
+                      pat = tmppat;
+                    }
+                  if (flags & FNM_PATHNAME)
+                    {
+                      NEXTPATTERN (starslash);
+                    }
+                  else
+                    {
+                      NEXTPATTERN (star);
+                    }
+                }
+              else
+                {
+                  NEXTPATTERN (endstar);
+                }
+              break;
+            case '?':
+              BRACTEST (parse_bracket ("!", pat, flags));
+              size++;
+              pat->bracket.sizerest = patsize - size;
+              NEXTPATTERN (bracket);
+              break;
+            case '[':
+              {
+                int siz = parse_bracket (s + 1, pat, flags);
+                BRACTEST (siz);
+                if (siz < 0)
+                  {
+                    FALLBACK;
+                    return fnmatch_fallback (str, flags);
+                  }
+                size++;
+                s += siz + 1;
+                pat->bracket.sizerest = patsize - size;
+                if (pat->bracket.flags == 5)
+                  checkneeded = 1;
+                NEXTPATTERN (bracket);
+              }
+              break;
+            default:
+              if (*s == '\\' && (!(flags & FNM_NOESCAPE)))
+                s++;
+              pat->chr.chr = *s;
+              size++;
+              NEXTPATTERN (chr);
+              if (*s == '/' && (flags & FNM_PERIOD) && (flags & FNM_PATHNAME)
+                  && *(s + 1) != '.')
+                {
+                NEXTPATTERN (begindot)}
+
+              break;
+            }
+        }
+    }
+  if (flags & FNM_LEADING_DIR)
+    {
+    NEXTPATTERN (slashend) NEXTPATTERN (endstar)}
+  else
+    {
+    NEXTPATTERN (end)}
+
+  fnmatch_state *st;
+  NULTEST (st = initfnmatchstate ());
+  st->states->p = ret;
+  st->start = ret;
+  if (checkneeded)
+    st = checkneeded_fallback (st, fnmatch_fallback (str, flags));
+  return st;
+}
+
+#undef NEXTPATTERN
+#define  NEXTPATTERN(type) p = (patterns *)(((void *) p)+sizeof 
(type##_pattern));
+
+static inline int
+fnmatch2_internal (const patterns * p, const char *str, int len)
+{
+#include "fnmatchcomp_loop.h"
+}
+
+int
+fnmatch_exec (const fnmatch_state * p, const char *str)
+{
+  const struct states *s;
+  int len = strlen (str);
+  for (s = p->states; s; s = s->next)
+    {
+      int ret = fnmatch2_internal (s->p, str, len);
+      if (ret <= 0)
+        return ret;
+    }
+  return FNM_NOMATCH;
+}
+
+#define  FNMATCH_PREFIX
+static int
+fnmatch2_prefix_internal (patterns * p, const char *str, int len,
+                          fnmatch_state * ret)
+{
+#include "fnmatchcomp_loop.h"
+}
+
+fnmatch_state *
+fnmatch_prefix (const fnmatch_state * p, const char *str)
+{
+  struct states *s;
+  int len = strlen (str);
+  fnmatch_state *ret;
+  NULTEST (ret = (fnmatch_state *) malloc (sizeof (fnmatch_state)));
+  memcpy ((void *) ret, (void *) p, sizeof (fnmatch_state));
+  ret->states = NULL;
+  (*ret->refcount)++;
+  for (s = p->states; s; s = s->next)
+    {
+      fnmatch2_prefix_internal (s->p, str, len, ret);
+    }
+  return ret;
+}
+
+static void
+freepatterns (patterns * p)
+{
+#define  SKIPPATTERN(type) case PATTERN_##type: NEXTPATTERN(type); break;
+  while (p->chr.tp != PATTERN_end && p->chr.tp != PATTERN_endstar)
+    {
+      switch (p->chr.tp)
+        {
+        case PATTERN_chr:
+          if (!p->chr.chr)
+            return;
+          NEXTPATTERN (chr);
+          break;
+          SKIPPATTERN (star);
+          SKIPPATTERN (starslash);
+          SKIPPATTERN (end);
+          SKIPPATTERN (endstar);
+        case PATTERN_bracket:
+          free (p->bracket.chars);
+          NEXTPATTERN (bracket);
+          break;
+          SKIPPATTERN (begindot);
+          SKIPPATTERN (slashend);
+        case PATTERN_fallback:
+          free (p->fallback.ptr);
+          return;
+        case PATTERN_fold:
+          return;
+        case PATTERN_checkneeded:
+          fnmatch_free ((fnmatch_state *) p->checkneeded.fallback);
+          return;
+        }
+    }
+
+}
+
+void
+fnmatch_free (fnmatch_state * s)
+{
+  struct states *st, *st2;
+  for (st = s->states; st;)
+    {
+      if (st->p->chr.tp == PATTERN_fallback)
+        {
+          free (st->p->fallback.prefix);
+        }
+      if (st->p->chr.tp == PATTERN_fold)
+        {
+          fnmatch_free ((fnmatch_state *) st->p->fold.states);
+        }
+      if (st->p->chr.tp == PATTERN_checkneeded)
+        {
+          fnmatch_free ((fnmatch_state *) st->p->checkneeded.states);
+        }
+
+      st2 = st->next;
+      free (st);
+      st = st2;
+    }
+  (*s->refcount)--;
+  if (!*s->refcount)
+    {
+      free (s->refcount);
+      freepatterns (s->start);
+      free (s->start);
+    }
+  free (s);
+}
diff --git a/lib/fnmatchcomp.h b/lib/fnmatchcomp.h
new file mode 100644
index 0000000..1cfce8c
--- /dev/null
+++ b/lib/fnmatchcomp.h
@@ -0,0 +1,41 @@
+  /* Copyright (C) 2009
+     Ondrej Bilka < address@hidden >
+
+     This program is free software: you can redistribute it and/or modif y
+     it under the terms of the GNU General Public License as published by
+     the Free Software Foundation; either version 3 of the License, or
+     (at your option) any later version.
+
+     This program is distributed in the hope that it will be useful,
+     but WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+     GNU General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with this program. If not, see < http://      www.gnu.org/licenses/ 
> . */
+
+struct _fnmatch_state;
+typedef struct _fnmatch_state fnmatch_state;
+
+  /* compile pattern */
+fnmatch_state *fnmatch_compile (const char *pattern, int flags);
+
+  /* add prefix to matched strings.
+     suppose you want match foo againist /home/foo, /home/bar/foo,
+     /home/bar/bar
+     fnmatch_state* s = fnmatch_compile("foo", 0);
+     fnmatch_state* home = fnmatch_prefix(s, "/home");
+     fnmatch_state* bar = fnmatch_prefix(home, "/bar");
+     fnmatch_exec(home, "/foo");
+     fnmatch_exec(bar, "/foo");
+     fnmatch_exec(bar, "/bar");
+   */
+fnmatch_state *fnmatch_prefix (const fnmatch_state * pattern,
+                               const char *prefix);
+
+int fnmatch_exec (const fnmatch_state * pattern, const char *string);
+
+void fnmatch_free (fnmatch_state * pattern);
+
+/*For some encodings we decide just call fnmatch. In that cases you can gain 
some performance by checking fnmatch_fallbacked and if returns 1 call fnmatch 
yourself*/
+int fnmatch_fallbacked(fnmatch_state *pattern);
diff --git a/lib/fnmatchcomp_loop.h b/lib/fnmatchcomp_loop.h
new file mode 100644
index 0000000..c189047
--- /dev/null
+++ b/lib/fnmatchcomp_loop.h
@@ -0,0 +1,196 @@
+  /* Copyright (C) 2009
+     Ondrej Bilka < address@hidden >
+
+     This program is free software: you can redistribute it and/or modif y
+     it under the terms of the GNU General Public License as published by
+     the Free Software Foundation; either version 3 of the License, or
+     (at your option) any later version.
+
+     This program is distributed in the hope that it will be useful,
+     but WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+     GNU General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with this program. If not, see < http://      www.gnu.org/licenses/ 
> . */
+
+const char *s = str, *chars;
+int i, len2;
+int sizerest, charno;
+char *buf;
+patterns *pat;
+while (1)
+  {
+#ifndef FNMATCH_PREFIX
+#undef ADDSTATE
+#define  ADDSTATE
+#else
+    struct states *state;
+#undef ADDSTATE
+#define  ADDSTATE state = calloc(1, sizeof (struct states)); \
+  state->next = ret->states; \
+  ret->states = state; \
+  state->p = p;
+    if (!*s)
+      {
+        ADDSTATE;
+        return 0;
+      }
+#endif
+    switch (p->chr.tp)
+      {
+      case PATTERN_chr:
+        if (*s != p->chr.chr)
+          return FNM_NOMATCH;
+        NEXTPATTERN (chr);
+        s++;
+        break;
+      case PATTERN_starslash:
+#undef SLASHTEST
+#define  SLASHTEST if (str[i] == '/') return FNM_NOMATCH;
+#include "fnmatchcomp_star.h"
+        break;
+      case PATTERN_star:
+#undef SLASHTEST
+#define  SLASHTEST
+#include "fnmatchcomp_star.h"
+        break;
+
+      case PATTERN_end:
+        return (*s) ? FNM_NOMATCH : 0;
+        break;
+      case PATTERN_slashend:
+        if (*s == '/' || *s == 0)
+          {
+            NEXTPATTERN (slashend);
+          }
+        break;
+      case PATTERN_endstar:
+        ADDSTATE;
+        return 0;
+        break;
+      case PATTERN_bracket:
+        {
+          int mat;
+          int mlen, mlen2;
+          unsigned char lastbyte;
+          chars = p->bracket.chars;
+          if (MB_CUR_MAX == 1)
+            {
+              mlen = 1;
+              lastbyte = s[mlen - 1];
+              mat = (p->bracket.hash[lastbyte / 32] &
+                     (1 << (lastbyte % 32))) ? 1 : 0;
+            }
+          else
+            {
+              mlen = mblen (s, MB_CUR_MAX);
+              mat = 1;
+              if (mlen < 0)
+                return FNM_NOMATCH;
+              lastbyte = s[mlen - 1];
+              if (!(p->bracket.hash[lastbyte / 32] & (1 << (lastbyte % 32))))
+                {
+                  mat = 0;
+                  goto match;
+                }
+              while (*chars)
+                {
+                  mlen2 = strlen (chars);
+                  if (!strncmp (chars, s, mlen) && mlen == mlen2)
+                    goto match;
+                  chars += mlen2 + 1;
+                }
+              mat = 0;
+            }
+        match:
+          if (mat ^ (p->bracket.flags & 1))
+            {
+              if (p->bracket.flags & 2 && *s == '/')
+                return FNM_NOMATCH;
+              s += mlen;
+              if (len - (str - s) < p->bracket.sizerest)
+                return FNM_NOMATCH;
+            }
+          else
+            {
+              return FNM_NOMATCH;
+            }
+          NEXTPATTERN (bracket);
+        }
+        break;
+      case PATTERN_begindot:
+        if (*s == '.')
+          return FNM_NOMATCH;
+        NEXTPATTERN (begindot);
+        break;
+      case PATTERN_fallback:
+
+        len2 = strlen (p->fallback.prefix) + len;
+        NULTEST2 (buf =
+                  (len2 <= 1000) ? alloca (len2 + 1) : malloc (len2 + 1));
+        strcpy (buf, p->fallback.prefix);
+        strcat (buf, s);
+#ifndef FNMATCH_PREFIX
+        {
+          int ret = fnmatch (p->fallback.ptr, buf, p->fallback.flags);
+          if (len > 1000)
+            free (buf);
+          return ret;
+        }
+#else
+        patterns *pat2 = malloc (sizeof (fallback_pattern));
+        NULTEST2 (pat2);
+        memcpy (pat2, p, sizeof (fallback_pattern));
+        NULTEST2 (pat2->fallback.prefix = strdup (buf));
+        p = (patterns *) pat2;
+        ADDSTATE;
+        return FNM_NOMATCH;
+#endif
+        if (len > 1000)
+          free (buf);
+        break;
+
+      case PATTERN_fold:
+        NULTEST2 (buf = (len <= 1000) ? alloca (len + 1) : malloc (len + 1));
+        strfold (str, buf);
+#ifndef FNMATCH_PREFIX
+        return fnmatch_exec ((fnmatch_state *) p->fold.states, buf);
+#else
+        NULTEST2 (pat2 = malloc (sizeof (fallback_pattern)));
+        pat2->fold.tp = PATTERN_fold;
+        NULTEST2 (pat2->fold.states =
+                  (void *)
+                  fold_fallback (fnmatch_prefix (p->fold.states, buf)));
+        p = (patterns *) pat2;
+        ADDSTATE;
+        if (len > 1000)
+          free (buf);
+        return FNM_NOMATCH;
+#endif
+        break;
+      case PATTERN_checkneeded:
+#ifndef FNMATCH_PREFIX
+        {
+          int ret = fnmatch_exec ((fnmatch_state *) p->checkneeded.states, s);
+          if (ret > 0)
+            return FNM_NOMATCH;
+          if (ret < 0)
+            return ret;
+          return fnmatch_exec ((fnmatch_state *) p->checkneeded.fallback, s);
+        }
+#else
+        NULTEST2 (pat2 = malloc (sizeof (checkneeded_pattern)));
+        pat2->checkneeded.tp = PATTERN_checkneeded;
+        NULTEST2 (pat2->checkneeded.states = (void *)
+                  fnmatch_prefix ((fnmatch_state *) p->checkneeded.states,
+                                  s));
+        NULTEST2 (pat2->checkneeded.fallback =
+                  (void *) fnmatch_prefix ((fnmatch_state *) p->
+                                           checkneeded.fallback, s));
+        ADDSTATE;
+        return FNM_NOMATCH;
+#endif
+        break;
+      }
+  }
diff --git a/lib/fnmatchcomp_star.h b/lib/fnmatchcomp_star.h
new file mode 100644
index 0000000..33dc5f7
--- /dev/null
+++ b/lib/fnmatchcomp_star.h
@@ -0,0 +1,65 @@
+  /* Copyright (C) 2009
+     Ondrej Bilka < address@hidden >
+
+     This program is free software: you can redistribute it and/or modif y
+     it under the terms of the GNU General Public License as published by
+     the Free Software Foundation; either version 3 of the License, or
+     (at your option) any later version.
+
+     This program is distributed in the hope that it will be useful,
+     but WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+     GNU General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with this program. If not, see < http://      www.gnu.org/licenses/ 
> . */
+
+#ifndef FNMATCH_PREFIX
+sizerest = p->star.sizerest;
+chars = p->star.chars;
+charno = p->star.charno;
+NEXTPATTERN (star);
+for (i = 0; i < charno; i++)
+  {
+    NEXTPATTERN (chr);
+  }
+
+switch (charno)
+  {
+  case 0:
+    for (i = s - str; i < len - sizerest; i++)
+      {
+        if (!fnmatch2_internal (p, str + i, len - i))
+          return 0;
+        SLASHTEST;
+      }
+    break;
+#define  CASEN(type, no) \
+  case no:\
+  for (i = s-str; i <= len-sizerest; i++)  {\
+  if ((*((type*)(str+i)) == *(type *) chars)\
+  && !fnmatch2_internal(p, str+i+no, len-i-no)) return 0; \
+  SLASHTEST \
+  } \
+  break;
+    CASEN (char, 1);
+    CASEN (UINT2, 2);
+  case 3:
+    CASEN (UINT4, 4);
+  }
+
+return FNM_NOMATCH;
+#else
+pat = p;
+NEXTPATTERN (star);
+for (i = s - str; i < len; i++)
+  {
+    fnmatch2_prefix_internal (p, str + i, len - i, ret);
+    SLASHTEST;
+  }
+
+p = pat;
+ADDSTATE;
+return FNM_NOMATCH;
+#endif
+break;
diff --git a/modules/fnmatchcomp b/modules/fnmatchcomp
new file mode 100644
index 0000000..c89b1e7
--- /dev/null
+++ b/modules/fnmatchcomp
@@ -0,0 +1,34 @@
+Description:
+ Allows you to compile fnmatch pattern. You can add to this pattern prefix
+ which will be added as prefix of any string you will match with this pattern
+
+Files:
+lib/fnmatchcomp.c
+lib/fnmatchcomp.h
+lib/fnmatchcomp_loop.h
+lib/fnmatchcomp_star.h
+
+Depends-on:
+fnmatch
+extensions
+alloca
+stdbool
+wchar
+wctype
+memchr
+memcmp
+mbsrtowcs
+mbsinit
+
+configure.ac:
+
+Makefile.am:
+
+Include:
+<fnmatchcomp.h>
+
+License:
+LGPLv2+
+
+Maintainer:
+Ondrej Bilka