buffer: add Buffer.prototype.lastIndexOf()

* Remove unnecessary templating from SearchString

  SearchString used to have separate PatternChar and SubjectChar template type
  arguments, apparently to support things like searching for an 8-bit string
  inside a 16-bit string or vice versa. However, SearchString is only used from
  node_buffer.cc, where PatternChar and SubjectChar are always the same. Since
  this is extra complexity that's unused and untested (simplifying to a single
  Char template argument still compiles and didn't break any unit tests), I
  removed it.

* Use Boyer-Hoore[-Horspool] for both indexOf and lastIndexOf

  Add test cases for lastIndexOf. Test the fallback from BMH to
  Boyer-Moore, which looks like it was totally untested before.

* Extra bounds checks in node_buffer.cc

* Extra asserts in string_search.h

* Buffer.lastIndexOf: clean up, enforce consistency w/ String.lastIndexOf

* Polyfill memrchr(3) for non-GNU systems

PR-URL: https://github.com/nodejs/node/pull/4846
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Trevor Norris <trev.norris@gmail.com>

1 files changed, 185 insertions, 181 deletions

diff --git a/src/string_search.h b/src/string_search.h
index 2a2790b2cc6..bf246702d7e 100644
--- a/src/string_search.h
+++ b/src/string_search.h
@@ -21,60 +21,35 @@ T Max(T a, T b) {
 
 static const uint32_t kMaxOneByteCharCodeU = 0xff;
 
-
-static inline size_t NonOneByteStart(const uint16_t* chars, size_t length) {
-  const uint16_t* limit = chars + length;
-  const uint16_t* start = chars;
-  while (chars < limit) {
-    if (*chars > kMaxOneByteCharCodeU)
-      return static_cast<size_t>(chars - start);
-    ++chars;
-  }
-  return static_cast<size_t>(chars - start);
-}
-
-
-static inline bool IsOneByte(const uint16_t* chars, size_t length) {
-  return NonOneByteStart(chars, length) >= length;
-}
-
-
 template <typename T>
 class Vector {
  public:
-  Vector(T* data, size_t length) : start_(data), length_(length) {
+  Vector(T* data, size_t length, bool isForward)
+      : start_(data), length_(length), is_forward_(isForward) {
     ASSERT(length > 0 && data != nullptr);
   }
 
-  // Returns the length of the vector.
+  // Returns the start of the memory range.
+  // For vector v this is NOT necessarily &v[0], see forward().
+  const T* start() const { return start_; }
+
+  // Returns the length of the vector, in characters.
   size_t length() const { return length_; }
 
-  T* start() const { return start_; }
+  // Returns true if the Vector is front-to-back, false if back-to-front.
+  // In the latter case, v[0] corresponds to the *end* of the memory range.
+  size_t forward() const { return is_forward_; }
 
   // Access individual vector elements - checks bounds in debug mode.
   T& operator[](size_t index) const {
     ASSERT(0 <= index && index < length_);
-    return start_[index];
-  }
-
-  const T& at(size_t index) const { return operator[](index); }
-
-  bool operator==(const Vector<T>& other) const {
-    if (length_ != other.length_)
-      return false;
-    if (start_ == other.start_)
-      return true;
-    for (size_t i = 0; i < length_; ++i) {
-      if (start_[i] != other.start_[i]) {
-        return false;
-      }
-    }
-    return true;
+    return start_[is_forward_ ? index : (length_ - index - 1)];
   }
 
  private:
   T* start_;
   size_t length_;
+  bool is_forward_;
 };
 
 
@@ -114,31 +89,17 @@ class StringSearchBase {
   // Table used temporarily while building the BoyerMoore good suffix
   // shift table.
   static int kSuffixTable[kBMMaxShift + 1];
-
-  static inline bool IsOneByteString(Vector<const uint8_t> string) {
-    return true;
-  }
-
-  static inline bool IsOneByteString(Vector<const uint16_t> string) {
-    return IsOneByte(string.start(), string.length());
-  }
 };
 
-template <typename PatternChar, typename SubjectChar>
+template <typename Char>
 class StringSearch : private StringSearchBase {
  public:
-  explicit StringSearch(Vector<const PatternChar> pattern)
+  explicit StringSearch(Vector<const Char> pattern)
       : pattern_(pattern), start_(0) {
     if (pattern.length() >= kBMMaxShift) {
       start_ = pattern.length() - kBMMaxShift;
     }
 
-    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
-      if (!IsOneByteString(pattern_)) {
-        strategy_ = &FailSearch;
-        return;
-      }
-    }
     size_t pattern_length = pattern_.length();
     CHECK_GT(pattern_length, 0);
     if (pattern_length < kBMMinPatternLength) {
@@ -152,12 +113,12 @@ class StringSearch : private StringSearchBase {
     strategy_ = &InitialSearch;
   }
 
-  size_t Search(Vector<const SubjectChar> subject, size_t index) {
+  size_t Search(Vector<const Char> subject, size_t index) {
     return strategy_(this, subject, index);
   }
 
   static inline int AlphabetSize() {
-    if (sizeof(PatternChar) == 1) {
+    if (sizeof(Char) == 1) {
       // Latin1 needle.
       return kLatin1AlphabetSize;
     } else {
@@ -165,42 +126,42 @@ class StringSearch : private StringSearchBase {
       return kUC16AlphabetSize;
     }
 
-    static_assert(sizeof(PatternChar) == sizeof(uint8_t) ||
-                      sizeof(PatternChar) == sizeof(uint16_t),
-                  "sizeof(PatternChar) == sizeof(uint16_t) || sizeof(uint8_t)");
+    static_assert(sizeof(Char) == sizeof(uint8_t) ||
+                  sizeof(Char) == sizeof(uint16_t),
+                  "sizeof(Char) == sizeof(uint16_t) || sizeof(uint8_t)");
   }
 
  private:
   typedef size_t (*SearchFunction)(  // NOLINT - it's not a cast!
-      StringSearch<PatternChar, SubjectChar>*,
-      Vector<const SubjectChar>,
+      StringSearch<Char>*,
+      Vector<const Char>,
       size_t);
 
-  static size_t FailSearch(StringSearch<PatternChar, SubjectChar>*,
-                           Vector<const SubjectChar> subject,
+  static size_t FailSearch(StringSearch<Char>*,
+                           Vector<const Char> subject,
                            size_t) {
     return subject.length();
   }
 
-  static size_t SingleCharSearch(StringSearch<PatternChar, SubjectChar>* search,
-                                 Vector<const SubjectChar> subject,
+  static size_t SingleCharSearch(StringSearch<Char>* search,
+                                 Vector<const Char> subject,
                                  size_t start_index);
 
-  static size_t LinearSearch(StringSearch<PatternChar, SubjectChar>* search,
-                             Vector<const SubjectChar> subject,
+  static size_t LinearSearch(StringSearch<Char>* search,
+                             Vector<const Char> subject,
                              size_t start_index);
 
-  static size_t InitialSearch(StringSearch<PatternChar, SubjectChar>* search,
-                              Vector<const SubjectChar> subject,
+  static size_t InitialSearch(StringSearch<Char>* search,
+                              Vector<const Char> subject,
                               size_t start_index);
 
   static size_t BoyerMooreHorspoolSearch(
-      StringSearch<PatternChar, SubjectChar>* search,
-      Vector<const SubjectChar> subject,
+      StringSearch<Char>* search,
+      Vector<const Char> subject,
       size_t start_index);
 
-  static size_t BoyerMooreSearch(StringSearch<PatternChar, SubjectChar>* search,
-                                 Vector<const SubjectChar> subject,
+  static size_t BoyerMooreSearch(StringSearch<Char>* search,
+                                 Vector<const Char> subject,
                                  size_t start_index);
 
   void PopulateBoyerMooreHorspoolTable();
@@ -214,16 +175,10 @@ class StringSearch : private StringSearchBase {
   }
 
   static inline int CharOccurrence(int* bad_char_occurrence,
-                                   SubjectChar char_code) {
-    if (sizeof(SubjectChar) == 1) {
+                                   Char char_code) {
+    if (sizeof(Char) == 1) {
       return bad_char_occurrence[static_cast<int>(char_code)];
     }
-    if (sizeof(PatternChar) == 1) {
-      if (exceedsOneByte(char_code)) {
-        return -1;
-      }
-      return bad_char_occurrence[static_cast<unsigned int>(char_code)];
-    }
     // Both pattern and subject are UC16. Reduce character to equivalence class.
     int equiv_class = char_code % kUC16AlphabetSize;
     return bad_char_occurrence[equiv_class];
@@ -250,7 +205,7 @@ class StringSearch : private StringSearchBase {
   }
 
   // The pattern to search for.
-  Vector<const PatternChar> pattern_;
+  Vector<const Char> pattern_;
   // Pointer to implementation of the search.
   SearchFunction strategy_;
   // Cache value of Max(0, pattern_length() - kBMMaxShift)
@@ -274,111 +229,138 @@ inline uint8_t GetHighestValueByte(uint16_t character) {
 inline uint8_t GetHighestValueByte(uint8_t character) { return character; }
 
 
-template <typename PatternChar, typename SubjectChar>
-inline size_t FindFirstCharacter(Vector<const PatternChar> pattern,
-                              Vector<const SubjectChar> subject, size_t index) {
-  const PatternChar pattern_first_char = pattern[0];
+// Searches for a byte value in a memory buffer, back to front.
+// Uses memrchr(3) on systems which support it, for speed.
+// Falls back to a vanilla for loop on non-GNU systems such as Windows.
+inline const void* MemrchrFill(const void* haystack, uint8_t needle,
+                               size_t haystack_len) {
+#ifdef _GNU_SOURCE
+  return memrchr(haystack, needle, haystack_len);
+#else
+  const uint8_t* haystack8 = static_cast<const uint8_t*>(haystack);
+  for (size_t i = haystack_len - 1; i != static_cast<size_t>(-1); i--) {
+    if (haystack8[i] == needle) {
+      return haystack8 + i;
+    }
+  }
+  return nullptr;
+#endif
+}
+
+
+// Finds the first occurence of *two-byte* character pattern[0] in the string
+// `subject`. Does not check that the whole pattern matches.
+template <typename Char>
+inline size_t FindFirstCharacter(Vector<const Char> pattern,
+                              Vector<const Char> subject, size_t index) {
+  const Char pattern_first_char = pattern[0];
   const size_t max_n = (subject.length() - pattern.length() + 1);
 
+  // For speed, search for the more `rare` of the two bytes in pattern[0]
+  // using memchr / memrchr (which are much faster than a simple for loop).
   const uint8_t search_byte = GetHighestValueByte(pattern_first_char);
-  const SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char);
   size_t pos = index;
   do {
-    const SubjectChar* char_pos = reinterpret_cast<const SubjectChar*>(
-        memchr(subject.start() + pos, search_byte,
-               (max_n - pos) * sizeof(SubjectChar)));
+    size_t bytes_to_search;
+    const void* void_pos;
+    if (subject.forward()) {
+      // Assert that bytes_to_search won't overflow
+      CHECK_LE(pos, max_n);
+      CHECK_LE(max_n - pos, SIZE_MAX / sizeof(Char));
+      bytes_to_search = (max_n - pos) * sizeof(Char);
+      void_pos = memchr(subject.start() + pos, search_byte, bytes_to_search);
+    } else {
+      CHECK_LE(pos, subject.length());
+      CHECK_LE(subject.length() - pos, SIZE_MAX / sizeof(Char));
+      bytes_to_search = (subject.length() - pos) * sizeof(Char);
+      void_pos = MemrchrFill(subject.start(), search_byte, bytes_to_search);
+    }
+    const Char* char_pos = static_cast<const Char*>(void_pos);
     if (char_pos == nullptr)
       return subject.length();
-    char_pos = AlignDown(char_pos, sizeof(SubjectChar));
-    pos = static_cast<size_t>(char_pos - subject.start());
-    if (subject[pos] == search_char)
+
+    // Then, for each match, verify that the full two bytes match pattern[0].
+    char_pos = AlignDown(char_pos, sizeof(Char));
+    size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
+    pos = subject.forward() ? raw_pos : (subject.length() - raw_pos - 1);
+    if (subject[pos] == pattern_first_char) {
+      // Match found, hooray.
       return pos;
+    }
+    // Search byte matched, but the other byte of pattern[0] didn't. Keep going.
   } while (++pos < max_n);
 
   return subject.length();
 }
 
 
+// Finds the first occurance of the byte pattern[0] in string `subject`.
+// Does not verify that the whole pattern matches.
 template <>
 inline size_t FindFirstCharacter(Vector<const uint8_t> pattern,
                                  Vector<const uint8_t> subject,
                                  size_t index) {
   const uint8_t pattern_first_char = pattern[0];
+  const size_t subj_len = subject.length();
   const size_t max_n = (subject.length() - pattern.length() + 1);
 
-  const uint8_t* char_pos = reinterpret_cast<const uint8_t*>(
-      memchr(subject.start() + index, pattern_first_char, max_n - index));
-  if (char_pos == nullptr)
-    return subject.length();
-  return static_cast<size_t>(char_pos - subject.start());
+  const void* pos;
+  if (subject.forward()) {
+    pos = memchr(subject.start() + index, pattern_first_char, max_n - index);
+  } else {
+    pos = MemrchrFill(subject.start(), pattern_first_char, subj_len - index);
+  }
+  const uint8_t* char_pos = static_cast<const uint8_t*>(pos);
+  if (char_pos == nullptr) {
+    return subj_len;
+  }
+
+  size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
+  return subject.forward() ? raw_pos : (subj_len - raw_pos - 1);
 }
 
 //---------------------------------------------------------------------
 // Single Character Pattern Search Strategy
 //---------------------------------------------------------------------
 
-template <typename PatternChar, typename SubjectChar>
-size_t StringSearch<PatternChar, SubjectChar>::SingleCharSearch(
-    StringSearch<PatternChar, SubjectChar>* search,
-    Vector<const SubjectChar> subject,
+template <typename Char>
+size_t StringSearch<Char>::SingleCharSearch(
+    StringSearch<Char>* search,
+    Vector<const Char> subject,
     size_t index) {
   CHECK_EQ(1, search->pattern_.length());
-  PatternChar pattern_first_char = search->pattern_[0];
-
-  if (sizeof(SubjectChar) == 1 && sizeof(PatternChar) == 1) {
-    return FindFirstCharacter(search->pattern_, subject, index);
-  } else {
-    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
-      if (exceedsOneByte(pattern_first_char)) {
-        return -1;
-      }
-    }
-    return FindFirstCharacter(search->pattern_, subject, index);
-  }
+  return FindFirstCharacter(search->pattern_, subject, index);
 }
 
 //---------------------------------------------------------------------
 // Linear Search Strategy
 //---------------------------------------------------------------------
 
-template <typename PatternChar, typename SubjectChar>
-inline bool CharCompare(const PatternChar* pattern,
-                        const SubjectChar* subject,
-                        size_t length) {
-  ASSERT_GT(length, 0);
-  size_t pos = 0;
-  do {
-    if (pattern[pos] != subject[pos]) {
-      return false;
-    }
-    pos++;
-  } while (pos < length);
-  return true;
-}
-
 // Simple linear search for short patterns. Never bails out.
-template <typename PatternChar, typename SubjectChar>
-size_t StringSearch<PatternChar, SubjectChar>::LinearSearch(
-    StringSearch<PatternChar, SubjectChar>* search,
-    Vector<const SubjectChar> subject,
+template <typename Char>
+size_t StringSearch<Char>::LinearSearch(
+    StringSearch<Char>* search,
+    Vector<const Char> subject,
     size_t index) {
-  Vector<const PatternChar> pattern = search->pattern_;
+  Vector<const Char> pattern = search->pattern_;
   CHECK_GT(pattern.length(), 1);
   const size_t pattern_length = pattern.length();
-  size_t i = index;
   const size_t n = subject.length() - pattern_length;
-  while (i <= n) {
+  for (size_t i = index; i <= n; i++) {
     i = FindFirstCharacter(pattern, subject, i);
     if (i == subject.length())
       return subject.length();
     ASSERT_LE(i, n);
-    i++;
 
-    // Loop extracted to separate function to allow using return to do
-    // a deeper break.
-    if (CharCompare(pattern.start() + 1, subject.start() + i,
-                    pattern_length - 1)) {
-      return i - 1;
+    bool matches = true;
+    for (size_t j = 1; j < pattern_length; j++) {
+      if (pattern[j] != subject[i + j]) {
+        matches = false;
+        break;
+      }
+    }
+    if (matches) {
+      return i;
     }
   }
   return subject.length();
@@ -388,12 +370,12 @@ size_t StringSearch<PatternChar, SubjectChar>::LinearSearch(
 // Boyer-Moore string search
 //---------------------------------------------------------------------
 
-template <typename PatternChar, typename SubjectChar>
-size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
-    StringSearch<PatternChar, SubjectChar>* search,
-    Vector<const SubjectChar> subject,
+template <typename Char>
+size_t StringSearch<Char>::BoyerMooreSearch(
+    StringSearch<Char>* search,
+    Vector<const Char> subject,
     size_t start_index) {
-  Vector<const PatternChar> pattern = search->pattern_;
+  Vector<const Char> pattern = search->pattern_;
   const size_t subject_length = subject.length();
   const size_t pattern_length = pattern.length();
   // Only preprocess at most kBMMaxShift last characters of pattern.
@@ -402,7 +384,7 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
   int* bad_char_occurence = search->bad_char_table();
   int* good_suffix_shift = search->good_suffix_shift_table();
 
-  PatternChar last_char = pattern[pattern_length - 1];
+  Char last_char = pattern[pattern_length - 1];
   size_t index = start_index;
   // Continue search from i.
   while (index <= subject_length - pattern_length) {
@@ -426,7 +408,7 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
       // Fall back on BMH shift.
       index += pattern_length - 1 -
                CharOccurrence(bad_char_occurence,
-                              static_cast<SubjectChar>(last_char));
+                              static_cast<Char>(last_char));
     } else {
       int gs_shift = good_suffix_shift[j + 1];
       int bc_occ = CharOccurrence(bad_char_occurence, c);
@@ -441,10 +423,10 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
   return subject.length();
 }
 
-template <typename PatternChar, typename SubjectChar>
-void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() {
+template <typename Char>
+void StringSearch<Char>::PopulateBoyerMooreTable() {
   const size_t pattern_length = pattern_.length();
-  const PatternChar* pattern = pattern_.start();
+  Vector<const Char> pattern = pattern_;
   // Only look at the last kBMMaxShift characters of pattern (from start_
   // to pattern_length).
   const size_t start = start_;
@@ -467,12 +449,12 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() {
   }
 
   // Find suffixes.
-  PatternChar last_char = pattern[pattern_length - 1];
+  Char last_char = pattern_[pattern_length - 1];
   size_t suffix = pattern_length + 1;
   {
     size_t i = pattern_length;
     while (i > start) {
-      PatternChar c = pattern[i - 1];
+      Char c = pattern[i - 1];
       while (suffix <= pattern_length && c != pattern[suffix - 1]) {
         if (static_cast<size_t>(shift_table[suffix]) == length) {
           shift_table[suffix] = suffix - i;
@@ -511,22 +493,22 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() {
 // Boyer-Moore-Horspool string search.
 //---------------------------------------------------------------------
 
-template <typename PatternChar, typename SubjectChar>
-size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch(
-    StringSearch<PatternChar, SubjectChar>* search,
-    Vector<const SubjectChar> subject,
+template <typename Char>
+size_t StringSearch<Char>::BoyerMooreHorspoolSearch(
+    StringSearch<Char>* search,
+    Vector<const Char> subject,
     size_t start_index) {
-  Vector<const PatternChar> pattern = search->pattern_;
+  Vector<const Char> pattern = search->pattern_;
   const size_t subject_length = subject.length();
   const size_t pattern_length = pattern.length();
   int* char_occurrences = search->bad_char_table();
   int64_t badness = -pattern_length;
 
   // How bad we are doing without a good-suffix table.
-  PatternChar last_char = pattern[pattern_length - 1];
+  Char last_char = pattern[pattern_length - 1];
   int last_char_shift =
       pattern_length - 1 -
-      CharOccurrence(char_occurrences, static_cast<SubjectChar>(last_char));
+      CharOccurrence(char_occurrences, static_cast<Char>(last_char));
 
   // Perform search
   size_t index = start_index;  // No matches found prior to this index.
@@ -564,8 +546,8 @@ size_t StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch(
   return subject.length();
 }
 
-template <typename PatternChar, typename SubjectChar>
-void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() {
+template <typename Char>
+void StringSearch<Char>::PopulateBoyerMooreHorspoolTable() {
   const size_t pattern_length = pattern_.length();
 
   int* bad_char_occurrence = bad_char_table();
@@ -585,8 +567,8 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() {
     }
   }
   for (size_t i = start; i < pattern_length - 1; i++) {
-    PatternChar c = pattern_[i];
-    int bucket = (sizeof(PatternChar) == 1) ? c : c % AlphabetSize();
+    Char c = pattern_[i];
+    int bucket = (sizeof(Char) == 1) ? c : c % AlphabetSize();
     bad_char_occurrence[bucket] = i;
   }
 }
@@ -597,12 +579,12 @@ void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() {
 
 // Simple linear search for short patterns, which bails out if the string
 // isn't found very early in the subject. Upgrades to BoyerMooreHorspool.
-template <typename PatternChar, typename SubjectChar>
-size_t StringSearch<PatternChar, SubjectChar>::InitialSearch(
-    StringSearch<PatternChar, SubjectChar>* search,
-    Vector<const SubjectChar> subject,
+template <typename Char>
+size_t StringSearch<Char>::InitialSearch(
+    StringSearch<Char>* search,
+    Vector<const Char> subject,
     size_t index) {
-  Vector<const PatternChar> pattern = search->pattern_;
+  Vector<const Char> pattern = search->pattern_;
   const size_t pattern_length = pattern.length();
   // Badness is a count of how much work we have done.  When we have
   // done enough work we decide it's probably worth switching to a better
@@ -642,11 +624,11 @@ size_t StringSearch<PatternChar, SubjectChar>::InitialSearch(
 // If searching multiple times for the same pattern, a search
 // object should be constructed once and the Search function then called
 // for each search.
-template <typename SubjectChar, typename PatternChar>
-size_t SearchString(Vector<const SubjectChar> subject,
-                    Vector<const PatternChar> pattern,
+template <typename Char>
+size_t SearchString(Vector<const Char> subject,
+                    Vector<const Char> pattern,
                     size_t start_index) {
-  StringSearch<PatternChar, SubjectChar> search(pattern);
+  StringSearch<Char> search(pattern);
   return search.Search(subject, start_index);
 }
 }
@@ -655,16 +637,38 @@ size_t SearchString(Vector<const SubjectChar> subject,
 namespace node {
 using node::stringsearch::Vector;
 
-template <typename SubjectChar, typename PatternChar>
-size_t SearchString(const SubjectChar* haystack,
+template <typename Char>
+size_t SearchString(const Char* haystack,
                     size_t haystack_length,
-                    const PatternChar* needle,
+                    const Char* needle,
                     size_t needle_length,
-                    size_t start_index) {
-  return node::stringsearch::SearchString(
-      Vector<const SubjectChar>(haystack, haystack_length),
-      Vector<const PatternChar>(needle, needle_length),
-      start_index);
+                    size_t start_index,
+                    bool is_forward) {
+  // To do a reverse search (lastIndexOf instead of indexOf) without redundant
+  // code, create two vectors that are reversed views into the input strings.
+  // For example, v_needle[0] would return the *last* character of the needle.
+  // So we're searching for the first instance of rev(needle) in rev(haystack)
+  Vector<const Char> v_needle = Vector<const Char>(
+      needle, needle_length, is_forward);
+  Vector<const Char> v_haystack = Vector<const Char>(
+      haystack, haystack_length, is_forward);
+  ASSERT(haystack_length >= needle_length);
+  size_t diff = haystack_length - needle_length;
+  size_t relative_start_index;
+  if (is_forward) {
+    relative_start_index = start_index;
+  } else if (diff < start_index) {
+    relative_start_index = 0;
+  } else {
+    relative_start_index = diff - start_index;
+  }
+  size_t pos = node::stringsearch::SearchString(
+      v_haystack, v_needle, relative_start_index);
+  if (pos == haystack_length) {
+    // not found
+    return pos;
+  }
+  return is_forward ? pos : (haystack_length - needle_length - pos);
 }
 }  // namespace node