RegExp: Add support for table-based character class

src/interpreter-irregexp.cc

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 15 matching lines @@
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 // A simple interpreter for the Irregexp byte code.
 
 
 #include "v8.h"
 #include "unicode.h"
 #include "utils.h"
 #include "ast.h"
 #include "bytecodes-irregexp.h"
+#include "interpreter-irregexp.h"
 #include "jsregexp.h"
-#include "interpreter-irregexp.h"
+#include "regexp-macro-assembler.h"
 
 namespace v8 {
 namespace internal {
 
 
 typedef unibrow::Mapping<unibrow::Ecma262Canonicalize> Canonicalize;
 
 static bool BackRefMatchesNoCase(Canonicalize* interp_canonicalize,
                                  int from,
                                  int current,
@@ skipping 394 matching lines @@
         uint32_t c = (insn >> BYTECODE_SHIFT);
         uint32_t minus = Load16Aligned(pc + 4);
         uint32_t mask = Load16Aligned(pc + 6);
         if (c != ((current_char - minus) & mask)) {
           pc = code_base + Load32Aligned(pc + 8);
         } else {
           pc += BC_MINUS_AND_CHECK_NOT_CHAR_LENGTH;
         }
         break;
       }
+      BYTECODE(CHECK_CHAR_IN_RANGE) {
+        uint32_t from = Load16Aligned(pc + 4);
+        uint32_t to = Load16Aligned(pc + 6);
+        if (from <= current_char && current_char <= to) {
+          pc = code_base + Load32Aligned(pc + 8);
+        } else {
+          pc += BC_CHECK_CHAR_IN_RANGE_LENGTH;
+        }
+        break;
+      }
+      BYTECODE(CHECK_CHAR_NOT_IN_RANGE) {
+        uint32_t from = Load16Aligned(pc + 4);
+        uint32_t to = Load16Aligned(pc + 6);
+        if (from > current_char || current_char > to) {
+          pc = code_base + Load32Aligned(pc + 8);
+        } else {
+          pc += BC_CHECK_CHAR_NOT_IN_RANGE_LENGTH;
+        }
+        break;
+      }
+      BYTECODE(CHECK_BIT_IN_TABLE) {
+        int mask = RegExpMacroAssembler::kTableMask;
+        byte b = pc[8 + ((current_char & mask) >> kBitsPerByteLog2)];

[ulan, 2012/03/27 11:02:43]

I think the compiler will take care of optimizing division
and modulo operations with constant powers of 2.
So there is no need for (>>) and (&).

If you use the "conventional" bit ordering (see the comment in
regexp-macro-assembler-irregexp.cc) then this code can be simplified as follows:

const int kTableStart = 8;
int index = current_char & mask;
int byte_index = index / kBitsPerByte;
int bit_index = index % kBitsPerByte;
int bit = (pc[kTableStart + byte_index] >> bit_index) & 1;
if (bit != 0) ...

[Erik Corry, 2012/03/28 09:40:26]

No, the compiler can only do this optimization for unsigned variables.  I don't
use unsigned much because it causes warnings (comparing signed with unsigned)
and bugs (-1 compares greater than all other numbers).

On Linux (this is compiler dependent) the result of % can also be negative so it
is not as fast as &.
I switched to the opposite bit ordering.

+        int bit = (current_char & (kBitsPerByte - 1));
+        if ((b & (1 << (kBitsPerByte - 1 - bit))) != 0) {
+          pc = code_base + Load32Aligned(pc + 4);
+        } else {
+          pc += BC_CHECK_BIT_IN_TABLE_LENGTH;
+        }
+        break;
+      }
       BYTECODE(CHECK_LT) {
         uint32_t limit = (insn >> BYTECODE_SHIFT);
         if (current_char < limit) {
           pc = code_base + Load32Aligned(pc + 4);
         } else {
           pc += BC_CHECK_LT_LENGTH;
         }
         break;
       }
       BYTECODE(CHECK_GT) {
@@ skipping 19 matching lines @@
           pc += BC_CHECK_REGISTER_GE_LENGTH;
         }
         break;
       BYTECODE(CHECK_REGISTER_EQ_POS)
         if (registers[insn >> BYTECODE_SHIFT] == current) {
           pc = code_base + Load32Aligned(pc + 4);
         } else {
           pc += BC_CHECK_REGISTER_EQ_POS_LENGTH;
         }
         break;
-      BYTECODE(LOOKUP_MAP1) {
-        // Look up character in a bitmap.  If we find a 0, then jump to the
-        // location at pc + 8.  Otherwise fall through!
-        int index = current_char - (insn >> BYTECODE_SHIFT);
-        byte map = code_base[Load32Aligned(pc + 4) + (index >> 3)];
-        map = ((map >> (index & 7)) & 1);
-        if (map == 0) {
-          pc = code_base + Load32Aligned(pc + 8);
-        } else {
-          pc += BC_LOOKUP_MAP1_LENGTH;
-        }
-        break;
-      }
-      BYTECODE(LOOKUP_MAP2) {
-        // Look up character in a half-nibble map.  If we find 00, then jump to
-        // the location at pc + 8.   If we find 01 then jump to location at
-        // pc + 11, etc.
-        int index = (current_char - (insn >> BYTECODE_SHIFT)) << 1;
-        byte map = code_base[Load32Aligned(pc + 3) + (index >> 3)];
-        map = ((map >> (index & 7)) & 3);
-        if (map < 2) {
-          if (map == 0) {
-            pc = code_base + Load32Aligned(pc + 8);
-          } else {
-            pc = code_base + Load32Aligned(pc + 12);
-          }
-        } else {
-          if (map == 2) {
-            pc = code_base + Load32Aligned(pc + 16);
-          } else {
-            pc = code_base + Load32Aligned(pc + 20);
-          }
-        }
-        break;
-      }
-      BYTECODE(LOOKUP_MAP8) {
-        // Look up character in a byte map.  Use the byte as an index into a
-        // table that follows this instruction immediately.
-        int index = current_char - (insn >> BYTECODE_SHIFT);
-        byte map = code_base[Load32Aligned(pc + 4) + index];
-        const byte* new_pc = code_base + Load32Aligned(pc + 8) + (map << 2);
-        pc = code_base + Load32Aligned(new_pc);
-        break;
-      }
-      BYTECODE(LOOKUP_HI_MAP8) {
-        // Look up high byte of this character in a byte map.  Use the byte as
-        // an index into a table that follows this instruction immediately.
-        int index = (current_char >> 8) - (insn >> BYTECODE_SHIFT);
-        byte map = code_base[Load32Aligned(pc + 4) + index];
-        const byte* new_pc = code_base + Load32Aligned(pc + 8) + (map << 2);
-        pc = code_base + Load32Aligned(new_pc);
-        break;
-      }
       BYTECODE(CHECK_NOT_REGS_EQUAL)
         if (registers[insn >> BYTECODE_SHIFT] ==
             registers[Load32Aligned(pc + 4)]) {
           pc += BC_CHECK_NOT_REGS_EQUAL_LENGTH;
         } else {
           pc = code_base + Load32Aligned(pc + 8);
         }
         break;
       BYTECODE(CHECK_NOT_BACK_REF) {
         int from = registers[insn >> BYTECODE_SHIFT];
@@ skipping 99 matching lines @@
     return RawMatch(isolate,
                     code_base,
                     subject_vector,
                     registers,
                     start_position,
                     previous_char);
   }
 }
 
 } }  // namespace v8::internal