* Optimized the bad-char table of Boyer-Moore

src/runtime.cc

 // Copyright 2006-2008 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 947 matching lines @@
 static const int kBMMaxShift = 0xff;
 // Reduce alphabet to this size.
 static const int kBMAlphabetSize = 0x100;
 // For patterns below this length, the skip length of Boyer-Moore is too short
 // to compensate for the algorithmic overhead compared to simple brute force.
 static const int kBMMinPatternLength = 5;
 
 // Holds the two buffers used by Boyer-Moore string search's Good Suffix
 // shift. Only allows the last kBMMaxShift characters of the needle
 // to be indexed.
-class BMGoodSuffixBuffers: public AllStatic {
+class BMGoodSuffixBuffers {
  public:
   BMGoodSuffixBuffers() {}
   inline void init(int needle_length) {
     ASSERT(needle_length > 1);
     int start = needle_length < kBMMaxShift ? 0 : needle_length - kBMMaxShift;
     int len = needle_length - start;
     biased_suffixes_ = suffixes_ - start;
     biased_good_suffix_shift_ = good_suffix_shift_ - start;
     for (int i = 0; i <= len; i++) {
       good_suffix_shift_[i] = len;
@@ skipping 19 matching lines @@
 static int bad_char_occurence[kBMAlphabetSize];
 static BMGoodSuffixBuffers bmgs_buffers;
 
 // Compute the bad-char table for Boyer-Moore in the static buffer.
 template <typename pchar>
 static void BoyerMoorePopulateBadCharTable(Vector<const pchar> pattern,
                                           int start) {
   // Run forwards to populate bad_char_table, so that *last* instance
   // of character equivalence class is the one registered.
   // Notice: Doesn't include the last character.
-  for (int i = 0; i < kBMAlphabetSize; i++) {
-    bad_char_occurence[i] = start - 1;
+  int table_size = (sizeof(pchar) == 1) ? String::kMaxAsciiCharCode + 1
+                                        : kBMAlphabetSize;
+  if (start == 0) {  // All patterns less than kBMMaxShift in length.
+    memset(bad_char_occurence, -1, table_size * sizeof(*bad_char_occurence));
+  } else {
+    for (int i = 0; i < table_size; i++) {
+      bad_char_occurence[i] = start - 1;
+    }
   }
   for (int i = start; i < pattern.length() - 1; i++) {
     pchar c = pattern[i];
-    int bucket = c % kBMAlphabetSize;
+    int bucket = (sizeof(pchar) ==1) ? c : c % kBMAlphabetSize;
     bad_char_occurence[bucket] = i;
   }
 }
 
 template <typename pchar>
 static void BoyerMoorePopulateGoodSuffixTable(Vector<const pchar> pattern,
                                               int start) {
   int m = pattern.length();
   int len = m - start;
   // Compute Good Suffix tables.
@@ skipping 34 matching lines @@
       if (bmgs_buffers.shift(i) == len) {
         bmgs_buffers.shift(i) = suffix - start;
       }
       if (i == suffix) {
         suffix = bmgs_buffers.suffix(suffix);
       }
     }
   }
 }
 
+template <typename schar, typename pchar>
+static inline int CharOccurence(int char_code) {
+  if (sizeof(schar) == 1) {
+    return bad_char_occurence[char_code];
+  }
+  if (sizeof(pchar) == 1) {
+    if (char_code > String::kMaxAsciiCharCode) {
+      return -1;
+    }
+    return bad_char_occurence[char_code];
+  }
+  return bad_char_occurence[char_code % kBMAlphabetSize];
+}
 
 // Restricted simplified Boyer-Moore string matching. Restricts tables to a
 // suffix of long pattern strings and handles only equivalence classes
 // of the full alphabet. This allows us to ensure that tables take only
 // a fixed amount of space.
 template <typename schar, typename pchar>
 static int BoyerMooreSimplified(Vector<const schar> subject,
                                 Vector<const pchar> pattern,
                                 int start_index,
                                 bool& complete) {
   int n = subject.length();
   int m = pattern.length();
   // Only preprocess at most kBMMaxShift last characters of pattern.
   int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
 
   BoyerMoorePopulateBadCharTable(pattern, start);
 
   int badness = -m;  // How bad we are doing without a good-suffix table.
   int idx;  // No matches found prior to this index.
   pchar last_char = pattern[m - 1];
   // Perform search
   for (idx = start_index; idx <= n - m;) {
     int j = m - 1;
     int c;
     while (last_char != (c = subject[idx + j])) {
-      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
+      int bc_occ = CharOccurence<schar, pchar>(c);
       int shift = j - bc_occ;
       idx += shift;
       badness += 1 - shift;  // at most zero, so badness cannot increase.
       if (idx > n - m) {
         complete = true;
         return -1;
       }
     }
     j--;
     while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
     if (j < 0) {
       complete = true;
       return idx;
     } else {
-      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
+      int bc_occ = CharOccurence<schar, pchar>(c);
       int shift = bc_occ < j ? j - bc_occ : 1;
       idx += shift;
       // Badness increases by the number of characters we have
       // checked, and decreases by the number of characters we
       // can skip by shifting. It's a measure of how we are doing
       // compared to reading each character exactly once.
       badness += (m - j) - shift;
       if (badness > 0) {
         complete = false;
         return idx;
@@ skipping 15 matching lines @@
   int start = m < kBMMaxShift ? 0 : m - kBMMaxShift;
 
   // Build the Good Suffix table and continue searching.
   BoyerMoorePopulateGoodSuffixTable(pattern, start);
   pchar last_char = pattern[m - 1];
   // Continue search from i.
   do {
     int j = m - 1;
     schar c;
     while (last_char != (c = subject[idx + j])) {
-      int shift = j - bad_char_occurence[c % kBMAlphabetSize];
+      int shift = j - CharOccurence<schar, pchar>(c);
       idx += shift;
       if (idx > n - m) {
         return -1;
       }
     }
     while (j >= 0 && pattern[j] == (c = subject[idx + j])) j--;
     if (j < 0) {
       return idx;
     } else if (j < start) {
       // we have matched more than our tables allow us to be smart about.
       idx += 1;
     } else {
       int gs_shift = bmgs_buffers.shift(j + 1);       // Good suffix shift.
-      int bc_occ = bad_char_occurence[c % kBMAlphabetSize];
+      int bc_occ = CharOccurence<schar, pchar>(c);
       int shift = j - bc_occ;                         // Bad-char shift.
       shift = (gs_shift > shift) ? gs_shift : shift;
       idx += shift;
     }
   } while (idx <= n - m);
 
   return -1;
 }
 
 
@@ skipping 4234 matching lines @@
 
 void Runtime::PerformGC(Object* result) {
   Failure* failure = Failure::cast(result);
   // Try to do a garbage collection; ignore it if it fails. The C
   // entry stub will throw an out-of-memory exception in that case.
   Heap::CollectGarbage(failure->requested(), failure->allocation_space());
 }
 
 
 } }  // namespace v8::internal