Changeset 27422 in webkit for trunk/JavaScriptCore/pcre/pcre_exec.c

Timestamp:

Nov 4, 2007, 1:28:22 AM (18 years ago)

Author:

Darin Adler

Message:

Reviewed by Maciej.

• ​http://bugs.webkit.org/show_bug.cgi?id=15826 optimize opcode loop and case insensitive ASCII compares for a 30% speedup

SunSpider says it's 2.6% faster overall, 32.5% in the regular expression tests.

• pcre/pcre_internal.h: Added OP_ASCII_CHAR and OP_ASCII_LETTER_NC.

• pcre/pcre_compile.c: (find_fixedlength): Added cases for OP_ASCII_CHAR and OP_ASCII_LETTER_NC. Also added OP_NOT since there was no reason it should not be in here. (could_be_empty_branch): Ditto. (compile_branch): Streamlined all the single-character cases; there was a bit of duplicate code. Added cases for OP_ASCII_CHAR and OP_ASCII_LETTER_NC as needed. But in particular, compile to those opcodes when the single character match is ASCII. (find_firstassertedchar): Added cases for OP_ASCII_CHAR and OP_ASCII_LETTER_NC.

• pcre/pcre_exec.c: (match): Removed the "min", "minimize", and "op" fields from the matchframe, after I discovered that none of them needed to be saved and restored across recursive match calls. Also eliminated the ignored result field from the matchframe, since I discovered that rrc ("recursive result code") was already the exact same thing. Moved the handling of opcodes higher than OP_BRA into the default statement of the switch instead of doing them before the switch. This removes a branch from each iteration of the opcode interpreter, just as removal of "op" removed at least one store from each iteration. Last, but not least, add the OP_ASCII_CHAR and OP_ASCII_LETTER_NC functions. Neither can ever match a surrogate pair and the letter case can be handled efficiently.

File:

• trunk/JavaScriptCore/pcre/pcre_exec.c (modified) (88 diffs)

trunk/JavaScriptCore/pcre/pcre_exec.c

@@ -217 +217 @@
 
 
-#define RMATCH(num,rx,rb,rf,rg)\
+#define RMATCH(num, ra, rb, rc)\
   {\
   if (frame >= stackframes && frame + 1 < stackframesend)\
@@ -225 +225 @@
   frame->where = RMATCH_WHERE(num);\
   newframe->eptr = frame->eptr;\
-  newframe->ecode = rb;\
+  newframe->ecode = (ra);\
   newframe->offset_top = frame->offset_top;\
-  newframe->eptrb = rf;\
-  is_group_start = rg;\
+  newframe->eptrb = (rb);\
+  is_group_start = (rc);\
   ++rdepth;\
   newframe->prevframe = frame;\
@@ -235 +235 @@
   goto HEAP_RECURSE;\
 RRETURN_##num:\
+  --rdepth;\
   DPRINTF(("did a goto back to line %d\n", __LINE__));\
-  rx = result;\
-  --rdepth;\
   }
 
@@ -248 +247 @@
   if (frame != NULL)\
     {\
-    result = ra;\
+    rrc = (ra);\
     goto RRETURN_LABEL;\
     }\
   return ra;\
   }
-
 
 /* Structure for remembering the local variables in a private frame */
@@ -275 +273 @@
   const pcre_uchar *saved_eptr;
 
-  BOOL minimize;
-
   int repeat_othercase;
 
@@ -284 +280 @@
   int length;
   int max;
-  int min;
   int number;
   int offset;
-  int op;
   int save_offset1, save_offset2, save_offset3;
 
@@ -319 +313 @@
 same response.
 
-Performance note: It might be tempting to extract commonly used fields from the
-md structure (e.g. utf8, end_subject) into individual variables to improve
-performance. Tests using gcc on a SPARC disproved this; in the first case, it
-made performance worse.
-
 Arguments:
    eptr        pointer in subject
@@ -351 +340 @@
 BOOL prev_is_word;
 BOOL is_group_start = TRUE;
+int min;
+BOOL minimize = FALSE; /* Initialization not really needed, but some compilers think so. */
 
 /* When recursion is not being used, all "local" variables that have to be
@@ -365 +356 @@
 matchframe *frame = stackframes;
 matchframe *newframe;
-int result;
 frame->prevframe = NULL;            /* Marks the top level */
 
@@ -409 +399 @@
 for (;;)
   {
-  frame->op = *frame->ecode;
-  frame->minimize = FALSE;
-
-  /* Opening capturing bracket. If there is space in the offset vector, save
-  the current subject position in the working slot at the top of the vector. We
-  mustn't change the current values of the data slot, because they may be set
-  from a previous iteration of this group, and be referred to by a reference
-  inside the group.
-
-  If the bracket fails to match, we need to restore this value and also the
-  values of the final offsets, in case they were set by a previous iteration of
-  the same bracket.
-
-  If there isn't enough space in the offset vector, treat this as if it were a
-  non-capturing bracket. Don't worry about setting the flag for the error case
-  here; that is handled in the code for KET. */
-
-  if (frame->op > OP_BRA)
-    {
-    frame->number = frame->op - OP_BRA;
-
-    /* For extended extraction brackets (large number), we have to fish out the
-    number from a dummy opcode at the start. */
-
-    if (frame->number > EXTRACT_BASIC_MAX)
-      frame->number = GET2(frame->ecode, 2+LINK_SIZE);
-    frame->offset = frame->number << 1;
-
-#ifdef DEBUG
-    printf("start bracket %d subject=", frame->number);
-    pchars(frame->eptr, 16, TRUE, md);
-    printf("\n");
-#endif
-
-    if (frame->offset < md->offset_max)
-      {
-      frame->save_offset1 = md->offset_vector[frame->offset];
-      frame->save_offset2 = md->offset_vector[frame->offset+1];
-      frame->save_offset3 = md->offset_vector[md->offset_end - frame->number];
-
-      DPRINTF(("saving %d %d %d\n", frame->save_offset1, frame->save_offset2, frame->save_offset3));
-      md->offset_vector[md->offset_end - frame->number] = frame->eptr - md->start_subject;
-
-      do
-        {
-        RMATCH(1, rrc, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
-        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-        frame->ecode += GET(frame->ecode, 1);
-        }
-      while (*frame->ecode == OP_ALT);
-
-      DPRINTF(("bracket %d failed\n", frame->number));
-
-      md->offset_vector[frame->offset] = frame->save_offset1;
-      md->offset_vector[frame->offset+1] = frame->save_offset2;
-      md->offset_vector[md->offset_end - frame->number] = frame->save_offset3;
-
-      RRETURN(MATCH_NOMATCH);
-      }
-
-    /* Insufficient room for saving captured contents */
-
-    else frame->op = OP_BRA;
-    }
-
-  /* Other types of node can be handled by a switch */
-
-  switch(frame->op)
+  switch (*frame->ecode)
     {
     case OP_BRA:     /* Non-capturing bracket: optimized */
+    NON_CAPTURING_BRACKET:
     DPRINTF(("start bracket 0\n"));
     do
       {
-      RMATCH(2, rrc, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
+      RMATCH(2, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
       frame->ecode += GET(frame->ecode, 1);
@@ -506 +430 @@
     do
       {
-      RMATCH(6, rrc, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
+      RMATCH(6, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
       if (rrc == MATCH_MATCH) break;
       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
@@ -527 +451 @@
     do
       {
-      RMATCH(7, rrc, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
+      RMATCH(7, frame->ecode + 1 + LINK_SIZE, NULL, match_isgroup);
       if (rrc == MATCH_MATCH) RRETURN(MATCH_NOMATCH);
       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
@@ -551 +475 @@
       do
         {
-        RMATCH(9, rrc, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
+        RMATCH(9, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
         if (rrc == MATCH_MATCH) break;
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
@@ -589 +513 @@
       if (*frame->ecode == OP_KETRMIN)
         {
-        RMATCH(10, rrc, frame->ecode + 1 + LINK_SIZE, frame->eptrb, 0);
+        RMATCH(10, frame->ecode + 1 + LINK_SIZE, frame->eptrb, 0);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-        RMATCH(11, rrc, frame->prev, frame->eptrb, match_isgroup);
+        RMATCH(11, frame->prev, frame->eptrb, match_isgroup);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
         }
       else  /* OP_KETRMAX */
         {
-        RMATCH(12, rrc, frame->prev, frame->eptrb, match_isgroup);
+        RMATCH(12, frame->prev, frame->eptrb, match_isgroup);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-        RMATCH(13, rrc, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
+        RMATCH(13, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
         }
@@ -620 +544 @@
       {
       frame->next = frame->ecode+1;
-      RMATCH(14, rrc, frame->next, frame->eptrb, match_isgroup);
+      RMATCH(14, frame->next, frame->eptrb, match_isgroup);
       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
       do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
@@ -631 +555 @@
       frame->next = frame->ecode+1;
       do frame->next += GET(frame->next,1); while (*frame->next == OP_ALT);
-      RMATCH(15, rrc, frame->next + 1+LINK_SIZE, frame->eptrb, match_isgroup);
+      RMATCH(15, frame->next + 1+LINK_SIZE, frame->eptrb, match_isgroup);
       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
       frame->ecode++;
@@ -712 +636 @@
       if (*frame->ecode == OP_KETRMIN)
         {
-        RMATCH(16, rrc, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
+        RMATCH(16, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-        RMATCH(17, rrc, frame->prev, frame->eptrb, match_isgroup);
+        RMATCH(17, frame->prev, frame->eptrb, match_isgroup);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
         }
       else  /* OP_KETRMAX */
         {
-        RMATCH(18, rrc, frame->prev, frame->eptrb, match_isgroup);
+        RMATCH(18, frame->prev, frame->eptrb, match_isgroup);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-        RMATCH(19, rrc, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
+        RMATCH(19, frame->ecode + 1+LINK_SIZE, frame->eptrb, 0);
         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
         }
@@ -904 +828 @@
         case OP_CRMINQUERY:
         c = *frame->ecode++ - OP_CRSTAR;
-        frame->minimize = (c & 1) != 0;
-        frame->min = rep_min[c];                 /* Pick up values from tables; */
+        minimize = (c & 1) != 0;
+        min = rep_min[c];                 /* Pick up values from tables; */
         frame->max = rep_max[c];                 /* zero for max => infinity */
         if (frame->max == 0) frame->max = INT_MAX;
@@ -912 +836 @@
         case OP_CRRANGE:
         case OP_CRMINRANGE:
-        frame->minimize = (*frame->ecode == OP_CRMINRANGE);
-        frame->min = GET2(frame->ecode, 1);
+        minimize = (*frame->ecode == OP_CRMINRANGE);
+        min = GET2(frame->ecode, 1);
         frame->max = GET2(frame->ecode, 3);
         if (frame->max == 0) frame->max = INT_MAX;
@@ -932 +856 @@
       /* First, ensure the minimum number of matches are present. */
 
-      for (i = 1; i <= frame->min; i++)
+      for (i = 1; i <= min; i++)
         {
         if (!match_ref(frame->offset, frame->eptr, frame->length, md)) RRETURN(MATCH_NOMATCH);
@@ -941 +865 @@
       They are not both allowed to be zero. */
 
-      if (frame->min == frame->max) continue;
+      if (min == frame->max) continue;
 
       /* If minimizing, keep trying and advancing the pointer */
 
-      if (frame->minimize)
-        {
-        for (frame->fi = frame->min;; frame->fi++)
-          {
-          RMATCH(20, rrc, frame->ecode, frame->eptrb, 0);
+      if (minimize)
+        {
+        for (frame->fi = min;; frame->fi++)
+          {
+          RMATCH(20, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           if (frame->fi >= frame->max || !match_ref(frame->offset, frame->eptr, frame->length, md))
@@ -963 +887 @@
         {
         frame->pp = frame->eptr;
-        for (i = frame->min; i < frame->max; i++)
+        for (i = min; i < frame->max; i++)
           {
           if (!match_ref(frame->offset, frame->eptr, frame->length, md)) break;
@@ -970 +894 @@
         while (frame->eptr >= frame->pp)
           {
-          RMATCH(21, rrc, frame->ecode, frame->eptrb, 0);
+          RMATCH(21, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           frame->eptr -= frame->length;
@@ -1007 +931 @@
         case OP_CRMINQUERY:
         c = *frame->ecode++ - OP_CRSTAR;
-        frame->minimize = (c & 1) != 0;
-        frame->min = rep_min[c];                 /* Pick up values from tables; */
+        minimize = (c & 1) != 0;
+        min = rep_min[c];                 /* Pick up values from tables; */
         frame->max = rep_max[c];                 /* zero for max => infinity */
         if (frame->max == 0) frame->max = INT_MAX;
@@ -1015 +939 @@
         case OP_CRRANGE:
         case OP_CRMINRANGE:
-        frame->minimize = (*frame->ecode == OP_CRMINRANGE);
-        frame->min = GET2(frame->ecode, 1);
+        minimize = (*frame->ecode == OP_CRMINRANGE);
+        min = GET2(frame->ecode, 1);
         frame->max = GET2(frame->ecode, 3);
         if (frame->max == 0) frame->max = INT_MAX;
@@ -1023 +947 @@
 
         default:               /* No repeat follows */
-        frame->min = frame->max = 1;
+        min = frame->max = 1;
         break;
         }
@@ -1030 +954 @@
 
         {
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1036 +960 @@
           if (c > 255)
             {
-            if (frame->op == OP_CLASS) RRETURN(MATCH_NOMATCH);
+            if (frame->data[-1] == OP_CLASS) RRETURN(MATCH_NOMATCH);
             }
           else
@@ -1048 +972 @@
       need to recurse. */
 
-      if (frame->min == frame->max) continue;
+      if (min == frame->max) continue;
 
       /* If minimizing, keep testing the rest of the expression and advancing
       the pointer while it matches the class. */
 
-      if (frame->minimize)
-        {
-          {
-          for (frame->fi = frame->min;; frame->fi++)
-            {
-            RMATCH(22, rrc, frame->ecode, frame->eptrb, 0);
+      if (minimize)
+        {
+          {
+          for (frame->fi = min;; frame->fi++)
+            {
+            RMATCH(22, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1064 +988 @@
             if (c > 255)
               {
-              if (frame->op == OP_CLASS) RRETURN(MATCH_NOMATCH);
+              if (frame->data[-1] == OP_CLASS) RRETURN(MATCH_NOMATCH);
               }
             else
@@ -1082 +1006 @@
 
           {
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1089 +1013 @@
             if (c > 255)
               {
-              if (frame->op == OP_CLASS) break;
+              if (frame->data[-1] == OP_CLASS) break;
               }
             else
@@ -1099 +1023 @@
           for (;;)
             {
-            RMATCH(24, rrc, frame->ecode, frame->eptrb, 0);
+            RMATCH(24, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
@@ -1128 +1052 @@
         case OP_CRMINQUERY:
         c = *frame->ecode++ - OP_CRSTAR;
-        frame->minimize = (c & 1) != 0;
-        frame->min = rep_min[c];                 /* Pick up values from tables; */
+        minimize = (c & 1) != 0;
+        min = rep_min[c];                 /* Pick up values from tables; */
         frame->max = rep_max[c];                 /* zero for max => infinity */
         if (frame->max == 0) frame->max = INT_MAX;
@@ -1136 +1060 @@
         case OP_CRRANGE:
         case OP_CRMINRANGE:
-        frame->minimize = (*frame->ecode == OP_CRMINRANGE);
-        frame->min = GET2(frame->ecode, 1);
+        minimize = (*frame->ecode == OP_CRMINRANGE);
+        min = GET2(frame->ecode, 1);
         frame->max = GET2(frame->ecode, 3);
         if (frame->max == 0) frame->max = INT_MAX;
@@ -1144 +1068 @@
 
         default:               /* No repeat follows */
-        frame->min = frame->max = 1;
+        min = frame->max = 1;
         break;
         }
@@ -1150 +1074 @@
       /* First, ensure the minimum number of matches are present. */
 
-      for (i = 1; i <= frame->min; i++)
+      for (i = 1; i <= min; i++)
         {
         if (frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1160 +1084 @@
       need to recurse. */
 
-      if (frame->min == frame->max) continue;
+      if (min == frame->max) continue;
 
       /* If minimizing, keep testing the rest of the expression and advancing
       the pointer while it matches the class. */
 
-      if (frame->minimize)
-        {
-        for (frame->fi = frame->min;; frame->fi++)
-          {
-          RMATCH(26, rrc, frame->ecode, frame->eptrb, 0);
+      if (minimize)
+        {
+        for (frame->fi = min;; frame->fi++)
+          {
+          RMATCH(26, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1183 +1107 @@
         {
         frame->pp = frame->eptr;
-        for (i = frame->min; i < frame->max; i++)
+        for (i = min; i < frame->max; i++)
           {
           int len = 1;
@@ -1193 +1117 @@
         for(;;)
           {
-          RMATCH(27, rrc, frame->ecode, frame->eptrb, 0);
+          RMATCH(27, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
@@ -1277 +1201 @@
     break;
 
+    /* Match a single ASCII character. */
+
+    case OP_ASCII_CHAR:
+    if (md->end_subject == frame->eptr)
+      RRETURN(MATCH_NOMATCH);
+    if (*frame->eptr != frame->ecode[1])
+      RRETURN(MATCH_NOMATCH);
+    ++frame->eptr;
+    frame->ecode += 2;
+    break;
+
+    /* Match one of two cases of an ASCII character. */
+
+    case OP_ASCII_LETTER_NC:
+    if (md->end_subject == frame->eptr)
+      RRETURN(MATCH_NOMATCH);
+    if ((*frame->eptr | 0x20) != frame->ecode[1])
+      RRETURN(MATCH_NOMATCH);
+    ++frame->eptr;
+    frame->ecode += 2;
+    break;
+
     /* Match a single character repeatedly; different opcodes share code. */
 
     case OP_EXACT:
-    frame->min = frame->max = GET2(frame->ecode, 1);
+    min = frame->max = GET2(frame->ecode, 1);
+    minimize = FALSE;
     frame->ecode += 3;
     goto REPEATCHAR;
@@ -1286 +1233 @@
     case OP_UPTO:
     case OP_MINUPTO:
-    frame->min = 0;
+    min = 0;
     frame->max = GET2(frame->ecode, 1);
-    frame->minimize = *frame->ecode == OP_MINUPTO;
+    minimize = *frame->ecode == OP_MINUPTO;
     frame->ecode += 3;
     goto REPEATCHAR;
@@ -1299 +1246 @@
     case OP_MINQUERY:
     c = *frame->ecode++ - OP_STAR;
-    frame->minimize = (c & 1) != 0;
-    frame->min = rep_min[c];                 /* Pick up values from tables; */
+    minimize = (c & 1) != 0;
+    min = rep_min[c];                 /* Pick up values from tables; */
     frame->max = rep_max[c];                 /* zero for max => infinity */
     if (frame->max == 0) frame->max = INT_MAX;
@@ -1313 +1260 @@
       GETUTF8CHARLEN(frame->fc, frame->ecode, frame->length);
       {
-      if (frame->min * (frame->fc > 0xFFFF ? 2 : 1) > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
+      if (min * (frame->fc > 0xFFFF ? 2 : 1) > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
       frame->ecode += frame->length;
 
@@ -1320 +1267 @@
         int othercase = md->caseless ? _pcre_ucp_othercase(frame->fc) : -1;
 
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (*frame->eptr != frame->fc && *frame->eptr != othercase) RRETURN(MATCH_NOMATCH);
@@ -1326 +1273 @@
           }
 
-        if (frame->min == frame->max) continue;
-
-        if (frame->minimize)
+        if (min == frame->max) continue;
+
+        if (minimize)
           {
           frame->repeat_othercase = othercase;
-          for (frame->fi = frame->min;; frame->fi++)
-            {
-            RMATCH(28, rrc, frame->ecode, frame->eptrb, 0);
+          for (frame->fi = min;; frame->fi++)
+            {
+            RMATCH(28, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1344 +1291 @@
           {
           frame->pp = frame->eptr;
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             if (frame->eptr >= md->end_subject) break;
@@ -1352 +1299 @@
           while (frame->eptr >= frame->pp)
            {
-           RMATCH(29, rrc, frame->ecode, frame->eptrb, 0);
+           RMATCH(29, frame->ecode, frame->eptrb, 0);
            if (rrc != MATCH_NOMATCH) RRETURN(rrc);
            --frame->eptr;
@@ -1364 +1311 @@
         /* No case on surrogate pairs, so no need to bother with "othercase". */
 
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           int nc;
@@ -1372 +1319 @@
           }
 
-        if (frame->min == frame->max) continue;
-
-        if (frame->minimize)
-          {
-          for (frame->fi = frame->min;; frame->fi++)
+        if (min == frame->max) continue;
+
+        if (minimize)
+          {
+          for (frame->fi = min;; frame->fi++)
             {
             int nc;
-            RMATCH(30, rrc, frame->ecode, frame->eptrb, 0);
+            RMATCH(30, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1391 +1338 @@
           {
           frame->pp = frame->eptr;
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int nc;
@@ -1401 +1348 @@
           while (frame->eptr >= frame->pp)
            {
-           RMATCH(31, rrc, frame->ecode, frame->eptrb, 0);
+           RMATCH(31, frame->ecode, frame->eptrb, 0);
            if (rrc != MATCH_NOMATCH) RRETURN(rrc);
            frame->eptr -= 2;
@@ -1439 +1386 @@
 
     case OP_NOTEXACT:
-    frame->min = frame->max = GET2(frame->ecode, 1);
+    min = frame->max = GET2(frame->ecode, 1);
+    minimize = FALSE;
     frame->ecode += 3;
     goto REPEATNOTCHAR;
@@ -1445 +1393 @@
     case OP_NOTUPTO:
     case OP_NOTMINUPTO:
-    frame->min = 0;
+    min = 0;
     frame->max = GET2(frame->ecode, 1);
-    frame->minimize = *frame->ecode == OP_NOTMINUPTO;
+    minimize = *frame->ecode == OP_NOTMINUPTO;
     frame->ecode += 3;
     goto REPEATNOTCHAR;
@@ -1458 +1406 @@
     case OP_NOTMINQUERY:
     c = *frame->ecode++ - OP_NOTSTAR;
-    frame->minimize = (c & 1) != 0;
-    frame->min = rep_min[c];                 /* Pick up values from tables; */
+    minimize = (c & 1) != 0;
+    min = rep_min[c];                 /* Pick up values from tables; */
     frame->max = rep_max[c];                 /* zero for max => infinity */
     if (frame->max == 0) frame->max = INT_MAX;
@@ -1468 +1416 @@
 
     REPEATNOTCHAR:
-    if (frame->min > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
+    if (min > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
     frame->fc = *frame->ecode++;
 
@@ -1479 +1427 @@
     characters and work backwards. */
 
-    DPRINTF(("negative matching %c{%d,%d}\n", frame->fc, frame->min, frame->max));
+    DPRINTF(("negative matching %c{%d,%d}\n", frame->fc, min, frame->max));
 
     if (md->caseless)
@@ -1487 +1435 @@
         {
         register int d;
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           GETCHARINC(d, frame->eptr);
@@ -1495 +1443 @@
         }
 
-      if (frame->min == frame->max) continue;
-
-      if (frame->minimize)
+      if (min == frame->max) continue;
+
+      if (minimize)
         {
           {
           register int d;
-          for (frame->fi = frame->min;; frame->fi++)
-            {
-            RMATCH(38, rrc, frame->ecode, frame->eptrb, 0);
+          for (frame->fi = min;; frame->fi++)
+            {
+            RMATCH(38, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             GETCHARINC(d, frame->eptr);
@@ -1522 +1470 @@
           {
           register int d;
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1533 +1481 @@
           for(;;)
             {
-            RMATCH(40, rrc, frame->ecode, frame->eptrb, 0);
+            RMATCH(40, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
@@ -1551 +1499 @@
         {
         register int d;
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           GETCHARINC(d, frame->eptr);
@@ -1558 +1506 @@
         }
 
-      if (frame->min == frame->max) continue;
-
-      if (frame->minimize)
+      if (min == frame->max) continue;
+
+      if (minimize)
         {
           {
           register int d;
-          for (frame->fi = frame->min;; frame->fi++)
-            {
-            RMATCH(42, rrc, frame->ecode, frame->eptrb, 0);
+          for (frame->fi = min;; frame->fi++)
+            {
+            RMATCH(42, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             GETCHARINC(d, frame->eptr);
@@ -1584 +1532 @@
           {
           register int d;
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1594 +1542 @@
           for(;;)
             {
-            RMATCH(44, rrc, frame->ecode, frame->eptrb, 0);
+            RMATCH(44, frame->ecode, frame->eptrb, 0);
             if (rrc != MATCH_NOMATCH) RRETURN(rrc);
             if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
@@ -1611 +1559 @@
 
     case OP_TYPEEXACT:
-    frame->min = frame->max = GET2(frame->ecode, 1);
-    frame->minimize = TRUE;
+    min = frame->max = GET2(frame->ecode, 1);
+    minimize = TRUE;
     frame->ecode += 3;
     goto REPEATTYPE;
@@ -1618 +1566 @@
     case OP_TYPEUPTO:
     case OP_TYPEMINUPTO:
-    frame->min = 0;
+    min = 0;
     frame->max = GET2(frame->ecode, 1);
-    frame->minimize = *frame->ecode == OP_TYPEMINUPTO;
+    minimize = *frame->ecode == OP_TYPEMINUPTO;
     frame->ecode += 3;
     goto REPEATTYPE;
@@ -1631 +1579 @@
     case OP_TYPEMINQUERY:
     c = *frame->ecode++ - OP_TYPESTAR;
-    frame->minimize = (c & 1) != 0;
-    frame->min = rep_min[c];                 /* Pick up values from tables; */
+    minimize = (c & 1) != 0;
+    min = rep_min[c];                 /* Pick up values from tables; */
     frame->max = rep_max[c];                 /* zero for max => infinity */
     if (frame->max == 0) frame->max = INT_MAX;
@@ -1651 +1599 @@
     and single-bytes. */
 
-    if (frame->min > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
-    if (frame->min > 0)
+    if (min > md->end_subject - frame->eptr) RRETURN(MATCH_NOMATCH);
+    if (min > 0)
       {
       switch(frame->ctype)
         {
         case OP_ANY:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject || IS_NEWLINE(*frame->eptr))
@@ -1667 +1615 @@
 
         case OP_NOT_DIGIT:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1677 +1625 @@
 
         case OP_DIGIT:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject ||
@@ -1687 +1635 @@
 
         case OP_NOT_WHITESPACE:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject ||
@@ -1697 +1645 @@
 
         case OP_WHITESPACE:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject ||
@@ -1707 +1655 @@
 
         case OP_NOT_WORDCHAR:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject ||
@@ -1717 +1665 @@
 
         case OP_WORDCHAR:
-        for (i = 1; i <= frame->min; i++)
+        for (i = 1; i <= min; i++)
           {
           if (frame->eptr >= md->end_subject ||
@@ -1733 +1681 @@
     /* If min = max, continue at the same level without recursing */
 
-    if (frame->min == frame->max) continue;
+    if (min == frame->max) continue;
 
     /* If minimizing, we have to test the rest of the pattern before each
-    subsequent match. Again, separate the UTF-8 case for speed, and also
-    separate the UCP cases. */
-
-    if (frame->minimize)
-      {
-        {
-        for (frame->fi = frame->min;; frame->fi++)
-          {
-          RMATCH(48, rrc, frame->ecode, frame->eptrb, 0);
+    subsequent match. */
+
+    if (minimize)
+      {
+        {
+        for (frame->fi = min;; frame->fi++)
+          {
+          RMATCH(48, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           if (frame->fi >= frame->max || frame->eptr >= md->end_subject) RRETURN(MATCH_NOMATCH);
@@ -1794 +1741 @@
 
     /* If maximizing it is worth using inline code for speed, doing the type
-    test once at the start (i.e. keep it out of the loop). Again, keep the
-    UTF-8 and UCP stuff separate. */
+    test once at the start (i.e. keep it out of the loop). */
 
     else
@@ -1813 +1759 @@
             {
               {
-              for (i = frame->min; i < frame->max; i++)
+              for (i = min; i < frame->max; i++)
                 {
                 if (frame->eptr >= md->end_subject || IS_NEWLINE(*frame->eptr)) break;
@@ -1827 +1773 @@
             {
               {
-              for (i = frame->min; i < frame->max; i++)
+              for (i = min; i < frame->max; i++)
                 {
                 if (frame->eptr >= md->end_subject || IS_NEWLINE(*frame->eptr)) break;
@@ -1838 +1784 @@
 
           case OP_NOT_DIGIT:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1849 +1795 @@
 
           case OP_DIGIT:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1860 +1806 @@
 
           case OP_NOT_WHITESPACE:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1871 +1817 @@
 
           case OP_WHITESPACE:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1882 +1828 @@
 
           case OP_NOT_WORDCHAR:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1893 +1839 @@
 
           case OP_WORDCHAR:
-          for (i = frame->min; i < frame->max; i++)
+          for (i = min; i < frame->max; i++)
             {
             int len = 1;
@@ -1911 +1857 @@
         for(;;)
           {
-          RMATCH(52, rrc, frame->ecode, frame->eptrb, 0);
+          RMATCH(52, frame->ecode, frame->eptrb, 0);
           if (rrc != MATCH_NOMATCH) RRETURN(rrc);
           if (frame->eptr-- == frame->pp) break;        /* Stop if tried at original pos */
@@ -1923 +1869 @@
       }
     /* Control never gets here */
+
+    default:
+      /* Opening capturing bracket. If there is space in the offset vector, save
+      the current subject position in the working slot at the top of the vector. We
+      mustn't change the current values of the data slot, because they may be set
+      from a previous iteration of this group, and be referred to by a reference
+      inside the group.
+
+      If the bracket fails to match, we need to restore this value and also the
+      values of the final offsets, in case they were set by a previous iteration of
+      the same bracket.
+
+      If there isn't enough space in the offset vector, treat this as if it were a
+      non-capturing bracket. Don't worry about setting the flag for the error case
+      here; that is handled in the code for KET. */
+
+      if (*frame->ecode > OP_BRA)
+        {
+        frame->number = *frame->ecode - OP_BRA;
+
+        /* For extended extraction brackets (large number), we have to fish out the
+        number from a dummy opcode at the start. */
+
+        if (frame->number > EXTRACT_BASIC_MAX)
+          frame->number = GET2(frame->ecode, 2+LINK_SIZE);
+        frame->offset = frame->number << 1;
+
+#ifdef DEBUG
+        printf("start bracket %d subject=", frame->number);
+        pchars(frame->eptr, 16, TRUE, md);
+        printf("\n");
+#endif
+
+        if (frame->offset < md->offset_max)
+          {
+          frame->save_offset1 = md->offset_vector[frame->offset];
+          frame->save_offset2 = md->offset_vector[frame->offset+1];
+          frame->save_offset3 = md->offset_vector[md->offset_end - frame->number];
+
+          DPRINTF(("saving %d %d %d\n", frame->save_offset1, frame->save_offset2, frame->save_offset3));
+          md->offset_vector[md->offset_end - frame->number] = frame->eptr - md->start_subject;
+
+          do
+            {
+            RMATCH(1, frame->ecode + 1 + LINK_SIZE, frame->eptrb, match_isgroup);
+            if (rrc != MATCH_NOMATCH) RRETURN(rrc);
+            frame->ecode += GET(frame->ecode, 1);
+            }
+          while (*frame->ecode == OP_ALT);
+
+          DPRINTF(("bracket %d failed\n", frame->number));
+
+          md->offset_vector[frame->offset] = frame->save_offset1;
+          md->offset_vector[frame->offset+1] = frame->save_offset2;
+          md->offset_vector[md->offset_end - frame->number] = frame->save_offset3;
+
+          RRETURN(MATCH_NOMATCH);
+          }
+
+        /* Insufficient room for saving captured contents */
+
+        goto NON_CAPTURING_BRACKET;
+        }
 
     /* There's been some horrible disaster. Since all codes > OP_BRA are
@@ -1929 +1938 @@
     in the code above or the OP_xxx definitions. */
 
-    default:
     DPRINTF(("Unknown opcode %d\n", *frame->ecode));
     RRETURN(JS_REGEXP_ERROR_INTERNAL);