Issue 6446 - Ignore emulated selectors if unchanged

lib/hash.js

+/*
+ * This file is part of Adblock Plus <https://adblockplus.org/>,
+ * Copyright (C) 2006-present eyeo GmbH
+ *
+ * Adblock Plus is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
+ * published by the Free Software Foundation.
+ *
+ * Adblock Plus is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** @module hash */
+
+"use strict";
+
+// This is an implementation of the SuperFastHash algorithm.
+// See http://www.azillionmonkeys.com/qed/hash.html
+function SuperFastHash(message)

[Manish Jethani, 2018/03/07 16:03:22]

This hash function is 4 times as fast as MD5 on Node.js. It's used by Google
Chrome internally for non-crypto hashes, we should adopt in our code as well.

[kzar, 2018/03/19 20:49:31]

Cool, but please add some unit tests.

[Sebastian Noack, 2018/03/19 21:13:11]

I'd rather not add this hash function. It just mitigates the memory usage, but
doesn't remove any complexity (actually it does the opposite).

I'm not even sure how much of an optimization it is. We trade in some memory
usage in case of emulated filters vs. additional cpu cycles and a fair amount of
additional code to be loaded/parsed for each document no matter what.

[Manish Jethani, 2018/03/20 11:54:22]

Yeah, I have to agree with Sebastian that it's not making sense for our use
case. There are only a handful of emulated selectors right now, we can just
compare the strings as in my initial patch.

[Manish Jethani, 2018/03/20 11:57:43]

Also one more thing: I'm beginning to think that this should all be done on the
Core side, so if addSelectors is called at all then the selectors have
definitely changed (or Core doesn't care if they haven't changed, either way).

[Manish Jethani, 2018/03/21 16:20:12]

By now I am convinced that this will have to be taken care of on the Core side.
We already have to keep the selectors updated because of the use of style sheets
instead of the style attribute, as well as some optimizations, and we get to
know for free if any selectors have changed.

This patch for example:

https://codereview.adblockplus.org/29728690/

So I'm closing this now.

+{
+  let {length} = message;
+
+  if (length == 0)
+    return 0;
+
+  let index = 0;
+
+  let nextUint8 = () => message[index++];
+  let nextUint16 = () => nextUint8() | nextUint8() << 8;
+
+  let digest = length;
+
+  for (let n = length >> 2; n > 0; n--)
+  {
+    digest = digest + nextUint16() >>> 0;
+    digest ^= digest << 16 >>> 0 ^ nextUint16() << 11;
+    digest = digest + (digest >>> 11) >>> 0;
+  }
+
+  switch (length & 3)
+  {
+    case 3:
+      digest = digest + nextUint16() >>> 0;
+      digest ^= digest << 16 >>> 0;
+      digest ^= nextUint8() << 18;
+      digest = digest + (digest >>> 11) >>> 0;
+      break;
+    case 2:
+      digest = digest + nextUint16() >>> 0;
+      digest ^= digest << 11 >>> 0;
+      digest = digest + (digest >>> 17) >>> 0;
+      break;
+    case 1:
+      digest = digest + nextUint8() >>> 0;
+      digest ^= digest << 10 >>> 0;
+      digest = digest + (digest >>> 1) >>> 0;
+  }
+
+  digest ^= digest << 3 >>> 0;
+  digest = digest + (digest >>> 5) >>> 0;
+  digest ^= digest << 4 >>> 0;
+  digest = digest + (digest >>> 17) >>> 0;
+  digest ^= digest << 25 >>> 0;
+  digest = digest + (digest >>> 6) >>> 0;
+
+  return digest;
+}
+
+/**
+ * Calculates the digest for a message.
+ *
+ * The hashing algorithm used is "SuperFastHash"
+ * (see http://www.azillionmonkeys.com/qed/hash.html). If no encoding is
+ * specified, the return value is a 32-bit unsigned integer.
+ *
+ * @param {number[]} message The message. This must be an array-like object of
+ *        "bytes" (i.e. only the lowest 8 bits are relevant). In order to hash
+ *        a string, it must be converted into UTF-8 or some other 8-bit
+ *        encoding first.
+ * @param {Object} [options]
+ * @param {string} [options.encoding] The encoding of the digest. This may be
+ *        set to "hex". If no encoding is specified, the preferred default
+ *        encoding for the hashing algorithm is used.
+ * @return {number|string} The digest.
+ */
+function hash(message, {encoding} = {})
+{
+  let digest = SuperFastHash(message);
+
+  if (encoding == "hex")
+    return digest.toString(16);
+
+  return digest;
+}
+
+exports.hash = hash;