Issue 4067 - Make filter "keys" generated for element hiding filters numeric

lib/filterListener.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2016 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
@@ skipping 196 matching lines @@
     defaultMatcher.remove(filter);
   else if (filter instanceof ElemHideBase)
   {
     if (filter instanceof CSSPropertyFilter)
       CSSRules.remove(filter);
     else
       ElemHide.remove(filter);
   }
 }
 
+const primes = [101, 109, 131, 149, 163, 179, 193, 211, 229, 241];
+
+function addFilters(filters)
+{
+  // We add filters using pseudo-random ordering. Reason is that ElemHide will
+  // assign consecutive filter IDs that might be visible to the website. The
+  // randomization makes sure that no conclusion can be made about the actual
+  // filters applying there. We have ten prime numbers to use as iteration step,
+  // any of those can be chosen as long as the array length isn't divisible by
+  // it.
+  let len = filters.length;
+  if (!len)
+    return;
+
+  let current = (Math.random() * len) | 0;
+  let step;
+  do
+  {
+    step = primes[(Math.random() * primes.length) | 0];
+  } while (len % step == 0);
+
+  for (let i = 0; i < len; i++, current = (current + step) % len)

[kzar, 2016/05/24 12:36:49]

I didn't intuitively understand that this should work, so I tried it out on a
piece of paper. Unless I'm missing something it's not working right, I keep
getting the filters back in sequential order, just starting from a random index?

Take this example:

selectors: ["a", "b", "c", "d", "e", "f"]
len: 6
prime: 61
current: 3

3                  = 3
(3 + 61) % 6       = 4
(4 + 61) % 6       = 5
(5 + 61) % 6       = 0
(0 + 61) % 6       = 1
(1 + 61) % 6       = 2

[Wladimir Palant, 2016/05/24 12:49:50]

That's because 61%6 happens to be 1. On the other hand, 47%6 is 5 so with this
prime you will get reverse order (3, 2, 1, 0, 5, 4). Either way, this is only an
issue if the array length is smaller than the prime used which shouldn't
normally be the case - our filter lists are considerably larger than the primes
used here.

So e.g. with len 7 and prime 3 you get (3, 6, 2, 5, 1, 4, 0).

[kzar, 2016/05/24 12:57:45]

Acknowledged.

+    addFilter(filters[current]);
+}
+
 function onSubscriptionAdded(subscription)
 {
   FilterListener.setDirty(1);
 
   if (!subscription.disabled)
   {
     subscription.filters.forEach(addFilter);
     flushElemHide();
   }
 }
@@ skipping 89 matching lines @@
 
 function onLoad()
 {
   isDirty = 0;
 
   defaultMatcher.clear();
   ElemHide.clear();
   CSSRules.clear();
   for (let subscription of FilterStorage.subscriptions)
     if (!subscription.disabled)
-      subscription.filters.forEach(addFilter);
+      addFilters(subscription.filters);
   flushElemHide();
 }
 
 function onSave()
 {
   isDirty = 0;
 }