Subject: bug#17070: [PATCH] grep: optimization of DFA by reuse of multi-byte buffers in non-UTF8 locales

From: Norihiro Tanaka <[email-masked]>
Date: Sun, 30 Mar 2014 20:14:21 +0900

I added further improvement to previous patch.

If dfaexec() runs in non-UTF8 locales, length and wide character
representation are checked for all characters of a line in a input
string.  However, if matched early in the line, results for remaining
characters are wasted.

The new patch doesn't reuse both `mblen_buf' and `inputwcs' but stops
using them, and checks multibyte characters on demand.  It enables to
accomplish to speed-up for matched early and reduce required memories.

Norihiro
From 6de4137bf8c5c237cc35c2eecf6fe149db478bcf Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Wed, 26 Mar 2014 22:14:19 +0900
Subject: [PATCH 1/2] grep: optimization of DFA by reuse of multi-byte buffers
 in non-UTF8 locales

* src/dfa.c (struct dfa): New members `mblen_buf', `nmblen_buf',
`inputwcs', `ninputwcs', `mb_follows' and `mb_match_lens'.
(SKIP_REMAINS_MB_IF_INITIAL_STATE): Use them instead of global variables.
(match_anychar): Use them instead of global variables.
(match_mb_charset): Use them instead of global variables.
(check_matching_with_multibyte_ops): Use it instead of new allocation.
(transit_state_consume_1char): Use them instead of global variables.
(transit_state): Use them instead of global variables.
(prepare_wc_buf): Use them instead of global variables.
(dfaexec): Initializations of new members.
(free_mbdata): Memory Deallocations for new members.
---
 src/dfa.c | 133 ++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 68 insertions(+), 65 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index b22fe97..adfe450 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -436,6 +436,30 @@ struct dfa
   struct dfamust *musts;        /* List of strings, at least one of which
                                    is known to appear in any r.e. matching
                                    the dfa.  */
+  unsigned char *mblen_buf;     /* Correspond to the input buffer in dfaexec.
+                                   Each element stores the number of remaining
+                                   bytes of the corresponding multibyte
+                                   character in the input string.  A element's
+                                   value is 0 if the corresponding character is
+                                   single-byte.
+                                   e.g., input : 'a', <mb(0)>, <mb(1)>, <mb(2)>
+                                   mblen_buf   :  0,       3,       2,       1
+                                 */
+  size_t nmblen_buf;            /* Length of the mblen buffer currently
+                                   allocated.  */
+  wchar_t *inputwcs;            /* Wide character representation of the input
+                                   string in dfaexec.
+                                   The length of this array is the same as
+                                   the length of input string (char array).
+                                   inputstring[i] is a single-byte char,
+                                   or the first byte of a multibyte char;
+                                   inputwcs[i] is the codepoint.  */
+  size_t ninputwcs;             /* Length of the input wide characters
+                                   currently allocated.  */
+  position_set *mb_follows;     /* Follow set added by ANYCHAR and/or MBCSET
+                                   on demand.  */
+  int *mb_match_lens;           /* Array of length reduced by ANYCHAR and/or
+                                   MBCSET.  */
 };
 
 /* Some macros for user access to dfa internals.  */
@@ -877,22 +901,6 @@ static int cur_mb_len = 1;      /* Length of the multibyte representation of
 static mbstate_t mbs;           /* mbstate for mbrtowc.  */
 static wchar_t wctok;           /* Wide character representation of the current
                                    multibyte character.  */
-static unsigned char *mblen_buf;/* Correspond to the input buffer in dfaexec.
-                                   Each element stores the number of remaining
-                                   bytes of the corresponding multibyte
-                                   character in the input string.  A element's
-                                   value is 0 if the corresponding character is
-                                   single-byte.
-                                   e.g., input : 'a', <mb(0)>, <mb(1)>, <mb(2)>
-                                   mblen_buf   :  0,       3,       2,       1
-                                 */
-static wchar_t *inputwcs;       /* Wide character representation of the input
-                                   string in dfaexec.
-                                   The length of this array is the same as
-                                   the length of input string (char array).
-                                   inputstring[i] is a single-byte char,
-                                   or the first byte of a multibyte char;
-                                   inputwcs[i] is the codepoint.  */
 static unsigned char const *buf_begin;  /* reference to begin in dfaexec.  */
 static unsigned char const *buf_end;    /* reference to end in dfaexec.  */
 
@@ -2960,14 +2968,12 @@ build_state_zero (struct dfa *d)
 #define SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p)		\
   if (s == 0)						\
     {							\
-      while (inputwcs[p - buf_begin] == 0		\
-            && mblen_buf[p - buf_begin] > 0		\
+      while (d->inputwcs[p - buf_begin] == 0		\
+            && d->mblen_buf[p - buf_begin] > 0		\
             && (unsigned char const *) p < buf_end)	\
         ++p;						\
       if ((char *) p >= end)				\
         {						\
-          free (mblen_buf);				\
-          free (inputwcs);				\
           *end = saved_end;				\
           return NULL;					\
         }						\
@@ -3061,8 +3067,8 @@ match_anychar (struct dfa *d, state_num s, position pos, size_t idx)
   wchar_t wc;
   int mbclen;
 
-  wc = inputwcs[idx];
-  mbclen = (mblen_buf[idx] == 0) ? 1 : mblen_buf[idx];
+  wc = d->inputwcs[idx];
+  mbclen = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3103,7 +3109,7 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   int context;
   wchar_t wc;                   /* Current referring character.  */
 
-  wc = inputwcs[idx];
+  wc = d->inputwcs[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3124,7 +3130,7 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   /* Assign the current referring operator to work_mbc.  */
   work_mbc = &(d->mbcsets[(d->multibyte_prop[pos.index]) >> 2]);
   match = !work_mbc->invert;
-  match_len = (mblen_buf[idx] == 0) ? 1 : mblen_buf[idx];
+  match_len = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Match in range 0-255?  */
   if (wc < NOTCHAR && work_mbc->cset != -1
@@ -3202,7 +3208,7 @@ check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
   size_t i;
   int *rarray;
 
-  MALLOC (rarray, d->states[s].mbps.nelem);
+  rarray = d->mb_match_lens;
   for (i = 0; i < d->states[s].mbps.nelem; ++i)
     {
       position pos = d->states[s].mbps.elems[i];
@@ -3232,7 +3238,7 @@ check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
 static status_transit_state
 transit_state_consume_1char (struct dfa *d, state_num s,
                              unsigned char const **pp,
-                             int *match_lens, int *mbclen, position_set * pps)
+                             int *match_lens, int *mbclen)
 {
   size_t i, j;
   int k;
@@ -3242,7 +3248,7 @@ transit_state_consume_1char (struct dfa *d, state_num s,
 
   /* Calculate the length of the (single/multi byte) character
      to which p points.  */
-  *mbclen = (mblen_buf[*pp - buf_begin] == 0) ? 1 : mblen_buf[*pp - buf_begin];
+  *mbclen = (d->mblen_buf[*pp - buf_begin] == 0) ? 1 : d->mblen_buf[*pp - buf_begin];
 
   /* Calculate the state which can be reached from the state 's' by
      consuming '*mbclen' single bytes from the buffer.  */
@@ -3252,8 +3258,8 @@ transit_state_consume_1char (struct dfa *d, state_num s,
       s2 = s1;
       rs = transit_state_singlebyte (d, s2, (*pp)++, &s1);
     }
-  /* Copy the positions contained by 's1' to the set 'pps'.  */
-  copy (&(d->states[s1].elems), pps);
+  /* Copy the positions contained by 's1' to the set 'd->mb_follows'.  */
+  copy (&(d->states[s1].elems), d->mb_follows);
 
   /* Check (input) match_lens, and initialize if it is NULL.  */
   if (match_lens == NULL && d->states[s].mbps.nelem != 0)
@@ -3268,12 +3274,10 @@ transit_state_consume_1char (struct dfa *d, state_num s,
       if (work_mbls[i] == *mbclen)
         for (j = 0; j < d->follows[d->states[s].mbps.elems[i].index].nelem;
              j++)
-          insert (d->follows[d->states[s].mbps.elems[i].index].elems[j], pps);
+          insert (d->follows[d->states[s].mbps.elems[i].index].elems[j],
+            d->mb_follows);
     }
 
-  if (match_lens == NULL && work_mbls != NULL)
-    free (work_mbls);
-
   /* FIXME: this return value is always ignored.  */
   return rs;
 }
@@ -3290,7 +3294,6 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
   size_t i, j;
   int *match_lens = NULL;
   size_t nelem = d->states[s].mbps.nelem;       /* Just a alias.  */
-  position_set follows;
   unsigned char const *p1 = *pp;
   wchar_t wc;
 
@@ -3321,26 +3324,25 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
       if (rs == TRANSIT_STATE_DONE)
         ++*pp;
 
-      free (match_lens);
       return s1;
     }
 
   /* This state has some operators which can match a multibyte character.  */
-  alloc_position_set (&follows, d->nleaves);
+  d->mb_follows->nelem = 0;
 
   /* 'maxlen' may be longer than the length of a character, because it may
      not be a character but a (multi character) collating element.
      We enumerate all of the positions which 's' can reach by consuming
      'maxlen' bytes.  */
-  transit_state_consume_1char (d, s, pp, match_lens, &mbclen, &follows);
+  transit_state_consume_1char (d, s, pp, match_lens, &mbclen);
 
-  wc = inputwcs[*pp - mbclen - buf_begin];
-  s1 = state_index (d, &follows, wchar_context (wc));
+  wc = d->inputwcs[*pp - mbclen - buf_begin];
+  s1 = state_index (d, d->mb_follows, wchar_context (wc));
   realloc_trans_if_necessary (d, s1);
 
   while (*pp - p1 < maxlen)
     {
-      transit_state_consume_1char (d, s1, pp, NULL, &mbclen, &follows);
+      transit_state_consume_1char (d, s1, pp, NULL, &mbclen);
 
       for (i = 0; i < nelem; i++)
         {
@@ -3348,15 +3350,13 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
             for (j = 0;
                  j < d->follows[d->states[s1].mbps.elems[i].index].nelem; j++)
               insert (d->follows[d->states[s1].mbps.elems[i].index].elems[j],
-                      &follows);
+                      d->mb_follows);
         }
 
-      wc = inputwcs[*pp - mbclen - buf_begin];
-      s1 = state_index (d, &follows, wchar_context (wc));
+      wc = d->inputwcs[*pp - mbclen - buf_begin];
+      s1 = state_index (d, d->mb_follows, wchar_context (wc));
       realloc_trans_if_necessary (d, s1);
     }
-  free (match_lens);
-  free (follows.elems);
   return s1;
 }
 
@@ -3375,21 +3375,21 @@ prepare_wc_buf (struct dfa *d, const char *begin, const char *end)
 
   for (i = 0; i < ilim; i++)
     {
-      size_t nbytes = mbs_to_wchar (d, inputwcs + i, begin + i, ilim - i, &mbs);
-      mblen_buf[i] = nbytes - (nbytes == 1);
+      size_t nbytes = mbs_to_wchar (d, d->inputwcs + i, begin + i, ilim - i, &mbs);
+      d->mblen_buf[i] = nbytes - (nbytes == 1);
       if (begin[i] == eol)
         break;
       while (--nbytes != 0)
         {
           i++;
-          mblen_buf[i] = nbytes;
-          inputwcs[i] = 0;
+          d->mblen_buf[i] = nbytes;
+          d->inputwcs[i] = 0;
         }
     }
 
   buf_end = (unsigned char *) (begin + i);
-  mblen_buf[i] = 0;
-  inputwcs[i] = 0;              /* sentinel */
+  d->mblen_buf[i] = 0;
+  d->inputwcs[i] = 0;              /* sentinel */
 #endif /* MBS_SUPPORT */
 }
 
@@ -3427,10 +3427,18 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
   if (d->mb_cur_max > 1)
     {
-      MALLOC (mblen_buf, end - begin + 2);
-      MALLOC (inputwcs, end - begin + 2);
+      static bool mb_alloc = false;
+      REALLOC_IF_NECESSARY (d->mblen_buf, d->nmblen_buf, end - begin + 2);
+      REALLOC_IF_NECESSARY (d->inputwcs, d->ninputwcs, end - begin + 2);
       memset (&mbs, 0, sizeof (mbstate_t));
       prepare_wc_buf (d, (const char *) p, end);
+      if (!mb_alloc)
+        {
+          MALLOC (d->mb_match_lens, d->nleaves);
+          MALLOC (d->mb_follows, 1);
+          alloc_position_set (d->mb_follows, d->nleaves);
+          mb_alloc = true;
+        }
     }
 
   for (;;)
@@ -3457,8 +3465,6 @@ dfaexec (struct dfa *d, char const *begin, char *end,
               if (backref)
                 {
                   *backref = 1;
-                  free (mblen_buf);
-                  free (inputwcs);
                   *end = saved_end;
                   return (char *) p;
                 }
@@ -3491,11 +3497,6 @@ dfaexec (struct dfa *d, char const *begin, char *end,
             {
               if (backref)
                 *backref = (d->states[s].backref != 0);
-              if (d->mb_cur_max > 1)
-                {
-                  free (mblen_buf);
-                  free (inputwcs);
-                }
               *end = saved_end;
               return (char *) p;
             }
@@ -3526,11 +3527,6 @@ dfaexec (struct dfa *d, char const *begin, char *end,
       /* Check if we've run off the end of the buffer.  */
       if ((char *) p > end)
         {
-          if (d->mb_cur_max > 1)
-            {
-              free (mblen_buf);
-              free (inputwcs);
-            }
           *end = saved_end;
           return NULL;
         }
@@ -3581,6 +3577,13 @@ free_mbdata (struct dfa *d)
   free (d->mbcsets);
   d->mbcsets = NULL;
   d->nmbcsets = 0;
+
+  free (d->mblen_buf);
+  free (d->inputwcs);
+  if (d->mb_follows != NULL)
+    free (d->mb_follows->elems);
+  free (d->mb_follows);
+  free (d->mb_match_lens);
 }
 
 /* Initialize the components of a dfa that the other routines don't
-- 
1.9.1

From d936d818d8f5735f15e67b3b5f0f3df3d7e7b5e1 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sat, 29 Mar 2014 20:59:53 +0900
Subject: [PATCH 2/2] grep: speed-up of DFA by checking multibyte characters on
 demand

If dfaexec() runs in non-UTF8 locales, length and wide character
representation are checked for all characters of a line in a input
string.  However, if matched early in the line, results for remaining
characters are wasted.

This patch checks multibyte characters on demand.  It enables to
accomplish to speed-up for matched early and reduce required memories.

* src/dfa.c (struct dfa): Remove members.
(buf_begin, buf_end): No longer they are used.  Remove them.
(SKIP_REMAINS_MB_IF_INITIAL_STATE): Now, the content of the macro is
extended in dfaexec().
(transit_state_singlebyte): sem check is removed.
(match_anychar): Doesn't use `mblen_buf and' `inputwcs'.
(match_mb_charset): Doesn't use `mblen_buf and' `inputwcs'.
(check_matching_with_multibyte_ops): Modify arguments.
(transit_state_consume_1char): Modify arguments.
(transit_state): Doesn't use `mblen_buf and' `inputwcs'.
(prepare_wc_buf): Remove it.
(dfaexec): Doesn't use `mblen_buf and' `inputwcs'.
---
 src/dfa.c | 212 ++++++++++++++++++--------------------------------------------
 1 file changed, 62 insertions(+), 150 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index adfe450..8146700 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -436,26 +436,6 @@ struct dfa
   struct dfamust *musts;        /* List of strings, at least one of which
                                    is known to appear in any r.e. matching
                                    the dfa.  */
-  unsigned char *mblen_buf;     /* Correspond to the input buffer in dfaexec.
-                                   Each element stores the number of remaining
-                                   bytes of the corresponding multibyte
-                                   character in the input string.  A element's
-                                   value is 0 if the corresponding character is
-                                   single-byte.
-                                   e.g., input : 'a', <mb(0)>, <mb(1)>, <mb(2)>
-                                   mblen_buf   :  0,       3,       2,       1
-                                 */
-  size_t nmblen_buf;            /* Length of the mblen buffer currently
-                                   allocated.  */
-  wchar_t *inputwcs;            /* Wide character representation of the input
-                                   string in dfaexec.
-                                   The length of this array is the same as
-                                   the length of input string (char array).
-                                   inputstring[i] is a single-byte char,
-                                   or the first byte of a multibyte char;
-                                   inputwcs[i] is the codepoint.  */
-  size_t ninputwcs;             /* Length of the input wide characters
-                                   currently allocated.  */
   position_set *mb_follows;     /* Follow set added by ANYCHAR and/or MBCSET
                                    on demand.  */
   int *mb_match_lens;           /* Array of length reduced by ANYCHAR and/or
@@ -901,8 +881,6 @@ static int cur_mb_len = 1;      /* Length of the multibyte representation of
 static mbstate_t mbs;           /* mbstate for mbrtowc.  */
 static wchar_t wctok;           /* Wide character representation of the current
                                    multibyte character.  */
-static unsigned char const *buf_begin;  /* reference to begin in dfaexec.  */
-static unsigned char const *buf_end;    /* reference to end in dfaexec.  */

 #if MBS_SUPPORT
@@ -2958,27 +2936,6 @@ build_state_zero (struct dfa *d)
 
 /* Multibyte character handling sub-routines for dfaexec.  */
 
-/* The initial state may encounter a byte which is not a single byte character
-   nor the first byte of a multibyte character.  But it is incorrect for the
-   initial state to accept such a byte.  For example, in Shift JIS the regular
-   expression "\\" accepts the codepoint 0x5c, but should not accept the second
-   byte of the codepoint 0x815c.  Then the initial state must skip the bytes
-   that are not a single byte character nor the first byte of a multibyte
-   character.  */
-#define SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p)		\
-  if (s == 0)						\
-    {							\
-      while (d->inputwcs[p - buf_begin] == 0		\
-            && d->mblen_buf[p - buf_begin] > 0		\
-            && (unsigned char const *) p < buf_end)	\
-        ++p;						\
-      if ((char *) p >= end)				\
-        {						\
-          *end = saved_end;				\
-          return NULL;					\
-        }						\
-    }
-
 static void
 realloc_trans_if_necessary (struct dfa *d, state_num new_state)
 {
@@ -3035,14 +2992,7 @@ transit_state_singlebyte (struct dfa *d, state_num s, unsigned char const *p,
             works = 0;
         }
       else if (works < 0)
-        {
-          if (p == buf_end)
-            {
-              /* At the moment, it must not happen.  */
-              abort ();
-            }
-          works = 0;
-        }
+        works = 0;
       else if (d->fails[works])
         {
           works = d->fails[works][*p];
@@ -3057,18 +3007,13 @@ transit_state_singlebyte (struct dfa *d, state_num s, unsigned char const *p,
   return rval;
 }
 
-/* Match a "." against the current context.  buf_begin[IDX] is the
-   current position.  Return the length of the match, in bytes.
-   POS is the position of the ".".  */
+/* Match a "." against the current context.  Return the length of the
+   match, in bytes.  POS is the position of the ".".  */
 static int
-match_anychar (struct dfa *d, state_num s, position pos, size_t idx)
+match_anychar (struct dfa *d, state_num s, position pos,
+               wchar_t wc, size_t mbclen)
 {
   int context;
-  wchar_t wc;
-  int mbclen;
-
-  wc = d->inputwcs[idx];
-  mbclen = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3090,16 +3035,14 @@ match_anychar (struct dfa *d, state_num s, position pos, size_t idx)
 }
 
 /* Match a bracket expression against the current context.
-   buf_begin[IDX] is the current position.
    Return the length of the match, in bytes.
    POS is the position of the bracket expression.  */
 static int
-match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
+match_mb_charset (struct dfa *d, state_num s, position pos,
+                  char const *p, wchar_t wc, size_t match_len)
 {
   size_t i;
   int match;               /* Matching succeeded.  */
-  int match_len;           /* Length of the character (or collating element)
-                              with which this operator matches.  */
   int op_len;              /* Length of the operator.  */
   char buffer[128];
 
@@ -3107,9 +3050,6 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   struct mb_char_classes *work_mbc;
 
   int context;
-  wchar_t wc;                   /* Current referring character.  */
-
-  wc = d->inputwcs[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3130,7 +3070,6 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   /* Assign the current referring operator to work_mbc.  */
   work_mbc = &(d->mbcsets[(d->multibyte_prop[pos.index]) >> 2]);
   match = !work_mbc->invert;
-  match_len = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Match in range 0-255?  */
   if (wc < NOTCHAR && work_mbc->cset != -1
@@ -3144,14 +3083,14 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
         goto charset_matched;
     }
 
-  strncpy (buffer, (char const *) buf_begin + idx, match_len);
+  strncpy (buffer, p, match_len);
   buffer[match_len] = '\0';
 
   /* match with an equivalence class?  */
   for (i = 0; i < work_mbc->nequivs; i++)
     {
       op_len = strlen (work_mbc->equivs[i]);
-      strncpy (buffer, (char const *) buf_begin + idx, op_len);
+      strncpy (buffer, p, op_len);
       buffer[op_len] = '\0';
       if (strcoll (work_mbc->equivs[i], buffer) == 0)
         {
@@ -3164,7 +3103,7 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   for (i = 0; i < work_mbc->ncoll_elems; i++)
     {
       op_len = strlen (work_mbc->coll_elems[i]);
-      strncpy (buffer, (char const *) buf_begin + idx, op_len);
+      strncpy (buffer, p, op_len);
       buffer[op_len] = '\0';
 
       if (strcoll (work_mbc->coll_elems[i], buffer) == 0)
@@ -3198,12 +3137,10 @@ charset_matched:
    array which corresponds to 'd->states[s].mbps.elem'; each element of the
    array contains the number of bytes with which the element can match.
 
-   'idx' is the index from buf_begin, and it is the current position
-   in the buffer.
-
    The caller MUST free the array which this function return.  */
 static int *
-check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
+check_matching_with_multibyte_ops (struct dfa *d, state_num s,
+                                   char const *p, wchar_t wc, size_t mbclen)
 {
   size_t i;
   int *rarray;
@@ -3215,10 +3152,10 @@ check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
       switch (d->tokens[pos.index])
         {
         case ANYCHAR:
-          rarray[i] = match_anychar (d, s, pos, idx);
+          rarray[i] = match_anychar (d, s, pos, wc, mbclen);
           break;
         case MBCSET:
-          rarray[i] = match_mb_charset (d, s, pos, idx);
+          rarray[i] = match_mb_charset (d, s, pos, p, wc, mbclen);
           break;
         default:
           break;                /* cannot happen.  */
@@ -3238,22 +3175,22 @@ check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
 static status_transit_state
 transit_state_consume_1char (struct dfa *d, state_num s,
                              unsigned char const **pp,
-                             int *match_lens, int *mbclen)
+                             wchar_t wc, size_t mbclen,
+                             int *match_lens)
 {
   size_t i, j;
   int k;
   state_num s1, s2;
-  int *work_mbls;
   status_transit_state rs = TRANSIT_STATE_DONE;
 
-  /* Calculate the length of the (single/multi byte) character
-     to which p points.  */
-  *mbclen = (d->mblen_buf[*pp - buf_begin] == 0) ? 1 : d->mblen_buf[*pp - buf_begin];
+  /* Check (input) match_lens, and initialize if it is NULL.  */
+  if (match_lens == NULL && d->states[s].mbps.nelem != 0)
+    match_lens = check_matching_with_multibyte_ops (d, s, (char const *) *pp, wc, mbclen);
 
   /* Calculate the state which can be reached from the state 's' by
-     consuming '*mbclen' single bytes from the buffer.  */
+     consuming 'mbclen' single bytes from the buffer.  */
   s1 = s;
-  for (k = 0; k < *mbclen; k++)
+  for (k = 0; k < mbclen; k++)
     {
       s2 = s1;
       rs = transit_state_singlebyte (d, s2, (*pp)++, &s1);
@@ -3261,17 +3198,11 @@ transit_state_consume_1char (struct dfa *d, state_num s,
   /* Copy the positions contained by 's1' to the set 'd->mb_follows'.  */
   copy (&(d->states[s1].elems), d->mb_follows);
 
-  /* Check (input) match_lens, and initialize if it is NULL.  */
-  if (match_lens == NULL && d->states[s].mbps.nelem != 0)
-    work_mbls = check_matching_with_multibyte_ops (d, s, *pp - buf_begin);
-  else
-    work_mbls = match_lens;
-
   /* Add all of the positions which can be reached from 's' by consuming
      a single character.  */
   for (i = 0; i < d->states[s].mbps.nelem; i++)
     {
-      if (work_mbls[i] == *mbclen)
+      if (match_lens[i] == mbclen)
         for (j = 0; j < d->follows[d->states[s].mbps.elems[i].index].nelem;
              j++)
           insert (d->follows[d->states[s].mbps.elems[i].index].elems[j],
@@ -3286,7 +3217,8 @@ transit_state_consume_1char (struct dfa *d, state_num s,
    buffer.  This function is for some operator which can match with a multi-
    byte character or a collating element (which may be multi characters).  */
 static state_num
-transit_state (struct dfa *d, state_num s, unsigned char const **pp)
+transit_state (struct dfa *d, state_num s, unsigned char const **pp,
+               unsigned char const *end)
 {
   state_num s1;
   int mbclen;  /* The length of current input multibyte character.  */
@@ -3302,7 +3234,8 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
        We check whether each of them can match or not.  */
     {
       /* Note: caller must free the return value of this function.  */
-      match_lens = check_matching_with_multibyte_ops (d, s, *pp - buf_begin);
+      mbclen = mbs_to_wchar (d, &wc, (char const *) *pp, end - *pp, &mbs);
+      match_lens = check_matching_with_multibyte_ops (d, s, (char const *) *pp, wc, mbclen);
 
       for (i = 0; i < nelem; i++)
         /* Search the operator which match the longest string,
@@ -3334,15 +3267,15 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
      not be a character but a (multi character) collating element.
      We enumerate all of the positions which 's' can reach by consuming
      'maxlen' bytes.  */
-  transit_state_consume_1char (d, s, pp, match_lens, &mbclen);
+  transit_state_consume_1char (d, s, pp, wc, mbclen, match_lens);
 
-  wc = d->inputwcs[*pp - mbclen - buf_begin];
   s1 = state_index (d, d->mb_follows, wchar_context (wc));
   realloc_trans_if_necessary (d, s1);
 
   while (*pp - p1 < maxlen)
     {
-      transit_state_consume_1char (d, s1, pp, NULL, &mbclen);
+      mbclen = mbs_to_wchar (d, &wc, (char const *) *pp, end - *pp, &mbs);
+      transit_state_consume_1char (d, s1, pp, wc, mbclen, NULL);
 
       for (i = 0; i < nelem; i++)
         {
@@ -3353,46 +3286,12 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
                       d->mb_follows);
         }
 
-      wc = d->inputwcs[*pp - mbclen - buf_begin];
       s1 = state_index (d, d->mb_follows, wchar_context (wc));
       realloc_trans_if_necessary (d, s1);
     }
   return s1;
 }
 
-
-/* Initialize mblen_buf and inputwcs with data from the next line.  */
-
-static void
-prepare_wc_buf (struct dfa *d, const char *begin, const char *end)
-{
-#if MBS_SUPPORT
-  unsigned char eol = eolbyte;
-  size_t i;
-  size_t ilim = end - begin + 1;
-
-  buf_begin = (unsigned char *) begin;
-
-  for (i = 0; i < ilim; i++)
-    {
-      size_t nbytes = mbs_to_wchar (d, d->inputwcs + i, begin + i, ilim - i, &mbs);
-      d->mblen_buf[i] = nbytes - (nbytes == 1);
-      if (begin[i] == eol)
-        break;
-      while (--nbytes != 0)
-        {
-          i++;
-          d->mblen_buf[i] = nbytes;
-          d->inputwcs[i] = 0;
-        }
-    }
-
-  buf_end = (unsigned char *) (begin + i);
-  d->mblen_buf[i] = 0;
-  d->inputwcs[i] = 0;              /* sentinel */
-#endif /* MBS_SUPPORT */
-}
-
 /* Search through a buffer looking for a match to the given struct dfa.
    Find the first occurrence of a string matching the regexp in the
    buffer, and the shortest possible version thereof.  Return a pointer to
@@ -3410,7 +3309,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
          int allow_nl, size_t *count, int *backref)
 {
   state_num s, s1;              /* Current state.  */
-  unsigned char const *p;       /* Current input character.  */
+  unsigned char const *p, *mbp; /* Current input character.  */
   state_num **trans, *t;        /* Copy of d->trans so it can be optimized
                                    into a register.  */
   unsigned char eol = eolbyte;  /* Likewise for eolbyte.  */
@@ -3420,7 +3319,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
     build_state_zero (d);
 
   s = s1 = 0;
-  p = (unsigned char const *) begin;
+  p = mbp = (unsigned char const *) begin;
   trans = d->trans;
   saved_end = *(unsigned char *) end;
   *end = eol;
@@ -3428,10 +3327,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
   if (d->mb_cur_max > 1)
     {
       static bool mb_alloc = false;
-      REALLOC_IF_NECESSARY (d->mblen_buf, d->nmblen_buf, end - begin + 2);
-      REALLOC_IF_NECESSARY (d->inputwcs, d->ninputwcs, end - begin + 2);
       memset (&mbs, 0, sizeof (mbstate_t));
-      prepare_wc_buf (d, (const char *) p, end);
       if (!mb_alloc)
         {
           MALLOC (d->mb_match_lens, d->nleaves);
@@ -3447,10 +3343,32 @@ dfaexec (struct dfa *d, char const *begin, char *end,
         {
           while ((t = trans[s]) != NULL)
             {
-              if (p > buf_end)
-                break;
               s1 = s;
-              SKIP_REMAINS_MB_IF_INITIAL_STATE (s, p);
+
+              if (s == 0)
+                {
+                  /* The initial state may encounter a byte which is not
+                     a single byte character nor the first byte of a
+                     multibyte character.  But it is incorrect for the
+                     initial state to accept such a byte.  For example,
+                     in Shift JIS the regular expression "\\" accepts
+                     the codepoint 0x5c, but should not accept the second
+                     byte of the codepoint 0x815c.  Then the initial
+                     state must skip the bytes that are not a single
+                     byte character nor the first byte of a multibyte
+                     character.  */
+                  wchar_t wc;
+                  while (mbp < p)
+                    mbp += mbs_to_wchar (d, &wc, (char const *) mbp,
+                                         end - (char const *) mbp, &mbs);
+                  p = mbp;
+
+                  if ((char *) p >= end)
+                    {
+                      *end = saved_end;
+                      return NULL;
+                    }
+                }
 
               if (d->states[s].mbps.nelem == 0)
                 {
@@ -3471,7 +3389,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
               /* Can match with a multibyte character (and multi character
                  collating element).  Transition table might be updated.  */
-              s = transit_state (d, s, &p);
+              s = transit_state (d, s, &p, (unsigned char *) end);
+              mbp = p;
               trans = d->trans;
             }
         }
@@ -3506,7 +3425,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
             {
               /* Can match with a multibyte character (and multicharacter
                  collating element).  Transition table might be updated.  */
-              s = transit_state (d, s, &p);
+              s = transit_state (d, s, &p, (unsigned char *) end);
+              mbp = p;
               trans = d->trans;
             }
           else
@@ -3515,14 +3435,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
         }
 
       /* If the previous character was a newline, count it.  */
-      if ((char *) p <= end && p[-1] == eol)
-        {
-          if (count)
-            ++*count;
-
-          if (d->mb_cur_max > 1)
-            prepare_wc_buf (d, (const char *) p, end);
-        }
+      if ((char *) p <= end && p[-1] == eol && count)
+        ++*count;
 
       /* Check if we've run off the end of the buffer.  */
       if ((char *) p > end)
@@ -3578,8 +3492,6 @@ free_mbdata (struct dfa *d)
   d->mbcsets = NULL;
   d->nmbcsets = 0;
 
-  free (d->mblen_buf);
-  free (d->inputwcs);
   if (d->mb_follows != NULL)
     free (d->mb_follows->elems);
   free (d->mb_follows);
-- 
1.9.1