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, 117 insertions, 0 deletions

diff --git a/test/parallel/test-buffer-indexof.js b/test/parallel/test-buffer-indexof.js
index 7fb862d919..0a20d2ce9a 100644
--- a/test/parallel/test-buffer-indexof.js
+++ b/test/parallel/test-buffer-indexof.js
@@ -282,3 +282,120 @@ assert.throws(function() {
 assert.throws(function() {
   b.indexOf([]);
 });
+
+// All code for handling encodings is shared between Buffer.indexOf and
+// Buffer.lastIndexOf, so only testing the separate lastIndexOf semantics.
+
+// Test lastIndexOf basic functionality; Buffer b contains 'abcdef'.
+// lastIndexOf string:
+assert.equal(b.lastIndexOf('a'), 0);
+assert.equal(b.lastIndexOf('a', 1), 0);
+assert.equal(b.lastIndexOf('b', 1), 1);
+assert.equal(b.lastIndexOf('c', 1), -1);
+assert.equal(b.lastIndexOf('a', -1), 0);
+assert.equal(b.lastIndexOf('a', -4), 0);
+assert.equal(b.lastIndexOf('a', -b.length), 0);
+assert.equal(b.lastIndexOf('a', -b.length - 1), -1);
+assert.equal(b.lastIndexOf('a', NaN), 0);
+assert.equal(b.lastIndexOf('a', -Infinity), -1);
+assert.equal(b.lastIndexOf('a', Infinity), 0);
+// lastIndexOf Buffer:
+assert.equal(b.lastIndexOf(buf_a), 0);
+assert.equal(b.lastIndexOf(buf_a, 1), 0);
+assert.equal(b.lastIndexOf(buf_a, -1), 0);
+assert.equal(b.lastIndexOf(buf_a, -4), 0);
+assert.equal(b.lastIndexOf(buf_a, -b.length), 0);
+assert.equal(b.lastIndexOf(buf_a, -b.length - 1), -1);
+assert.equal(b.lastIndexOf(buf_a, NaN), 0);
+assert.equal(b.lastIndexOf(buf_a, -Infinity), -1);
+assert.equal(b.lastIndexOf(buf_a, Infinity), 0);
+assert.equal(b.lastIndexOf(buf_bc), 1);
+assert.equal(b.lastIndexOf(buf_bc, 2), 1);
+assert.equal(b.lastIndexOf(buf_bc, -1), 1);
+assert.equal(b.lastIndexOf(buf_bc, -3), 1);
+assert.equal(b.lastIndexOf(buf_bc, -5), 1);
+assert.equal(b.lastIndexOf(buf_bc, -6), -1);
+assert.equal(b.lastIndexOf(buf_bc, NaN), 1);
+assert.equal(b.lastIndexOf(buf_bc, -Infinity), -1);
+assert.equal(b.lastIndexOf(buf_bc, Infinity), 1);
+assert.equal(b.lastIndexOf(buf_f), b.length - 1);
+assert.equal(b.lastIndexOf(buf_z), -1);
+assert.equal(b.lastIndexOf(buf_empty), -1);
+assert.equal(b.lastIndexOf(buf_empty, 1), -1);
+assert.equal(b.lastIndexOf(buf_empty, b.length + 1), -1);
+assert.equal(b.lastIndexOf(buf_empty, Infinity), -1);
+// lastIndexOf number:
+assert.equal(b.lastIndexOf(0x61), 0);
+assert.equal(b.lastIndexOf(0x61, 1), 0);
+assert.equal(b.lastIndexOf(0x61, -1), 0);
+assert.equal(b.lastIndexOf(0x61, -4), 0);
+assert.equal(b.lastIndexOf(0x61, -b.length), 0);
+assert.equal(b.lastIndexOf(0x61, -b.length - 1), -1);
+assert.equal(b.lastIndexOf(0x61, NaN), 0);
+assert.equal(b.lastIndexOf(0x61, -Infinity), -1);
+assert.equal(b.lastIndexOf(0x61, Infinity), 0);
+assert.equal(b.lastIndexOf(0x0), -1);
+
+// Test weird offset arguments.
+// Behaviour should match String.lastIndexOf:
+assert.equal(b.lastIndexOf('b', 0), -1);
+assert.equal(b.lastIndexOf('b', undefined), 1);
+assert.equal(b.lastIndexOf('b', null), -1);
+assert.equal(b.lastIndexOf('b', {}), 1);
+assert.equal(b.lastIndexOf('b', []), -1);
+assert.equal(b.lastIndexOf('b', [2]), 1);
+
+// Test lastIndexOf on a longer buffer:
+var bufferString = new Buffer('a man a plan a canal panama');
+assert.equal(15, bufferString.lastIndexOf('canal'));
+assert.equal(21, bufferString.lastIndexOf('panama'));
+assert.equal(0, bufferString.lastIndexOf('a man a plan a canal panama'));
+assert.equal(-1, bufferString.lastIndexOf('a man a plan a canal mexico'));
+assert.equal(13, bufferString.lastIndexOf('a '));
+assert.equal(13, bufferString.lastIndexOf('a ', 13));
+assert.equal(6, bufferString.lastIndexOf('a ', 12));
+assert.equal(0, bufferString.lastIndexOf('a ', 5));
+assert.equal(13, bufferString.lastIndexOf('a ', -1));
+assert.equal(0, bufferString.lastIndexOf('a ', -27));
+assert.equal(-1, bufferString.lastIndexOf('a ', -28));
+
+// The above tests test the LINEAR and SINGLE-CHAR strategies.
+// Now, we test the BOYER-MOORE-HORSPOOL strategy.
+// Test lastIndexOf on a long buffer w multiple matches:
+pattern = 'JABACABADABACABA';
+assert.equal(1535, longBufferString.lastIndexOf(pattern));
+assert.equal(1535, longBufferString.lastIndexOf(pattern, 1535));
+assert.equal(511, longBufferString.lastIndexOf(pattern, 1534));
+
+// Finally, give it a really long input to trigger fallback from BMH to
+// regular BOYER-MOORE (which has better worst-case complexity).
+
+// Generate a really long Thue-Morse sequence of 'yolo' and 'swag',
+// "yolo swag swag yolo swag yolo yolo swag" ..., goes on for about 5MB.
+// This is hard to search because it all looks similar, but never repeats.
+
+// countBits returns the number of bits in the binary reprsentation of n.
+function countBits(n) {
+  for (var count = 0; n > 0; count++) {
+    n = n & (n - 1); // remove top bit
+  }
+  return count;
+}
+var parts = [];
+for (var i = 0; i < 1000000; i++) {
+  parts.push((countBits(i) % 2 === 0) ? 'yolo' : 'swag');
+}
+var reallyLong = new Buffer(parts.join(' '));
+assert.equal('yolo swag swag yolo', reallyLong.slice(0, 19).toString());
+
+// Expensive reverse searches. Stress test lastIndexOf:
+pattern = reallyLong.slice(0, 100000);  // First 1/50th of the pattern.
+assert.equal(4751360, reallyLong.lastIndexOf(pattern));
+assert.equal(3932160, reallyLong.lastIndexOf(pattern, 4000000));
+assert.equal(2949120, reallyLong.lastIndexOf(pattern, 3000000));
+pattern = reallyLong.slice(100000, 200000);  // Second 1/50th.
+assert.equal(4728480, reallyLong.lastIndexOf(pattern));
+pattern = reallyLong.slice(0, 1000000);  // First 1/5th.
+assert.equal(3932160, reallyLong.lastIndexOf(pattern));
+pattern = reallyLong.slice(0, 2000000);  // first 2/5ths.
+assert.equal(0, reallyLong.lastIndexOf(pattern));