extension/packages/mode-hints/bloomfilter.coffee

   1 { getPref
   2 , setPref } = require 'prefs'
   3
   4 `
   5 (function(exports) {
   6   exports.BloomFilter = BloomFilter;
   7   exports.fnv_1a = fnv_1a;
   8   exports.fnv_1a_b = fnv_1a_b;
   9
  10   var typedArrays = typeof ArrayBuffer !== "undefined";
  11
  12   // Creates a new bloom filter.  If *m* is an array-like object, with a length
  13   // property, then the bloom filter is loaded with data from the array, where
  14   // each element is a 32-bit integer.  Otherwise, *m* should specify the
  15   // number of bits.  *k* specifies the number of hashing functions.
  16   function BloomFilter(m, k) {
  17     var a;
  18     if (typeof m !== "number") a = m, m = a.length * 32;
  19
  20     this.m = m;
  21     this.k = k;
  22     var n = Math.ceil(m / 32),
  23         i = -1;
  24
  25     if (typedArrays) {
  26       var kbytes = 1 << Math.ceil(Math.log(Math.ceil(Math.log(m) / Math.LN2 / 8)) / Math.LN2),
  27           array = kbytes === 1 ? Uint8Array : kbytes === 2 ? Uint16Array : Uint32Array,
  28           kbuffer = new ArrayBuffer(kbytes * k),
  29           buckets = this.buckets = new Int32Array(n);
  30       if (a) while (++i < n) buckets[i] = a[i];
  31       this._locations = new array(kbuffer);
  32     } else {
  33       var buckets = this.buckets = [];
  34       if (a) while (++i < n) buckets[i] = a[i];
  35       else while (++i < n) buckets[i] = 0;
  36       this._locations = [];
  37     }
  38   }
  39
  40   // See http://willwhim.wordpress.com/2011/09/03/producing-n-hash-functions-by-hashing-only-once/
  41   BloomFilter.prototype.locations = function(v) {
  42     var k = this.k,
  43         m = this.m,
  44         r = this._locations,
  45         a = fnv_1a(v),
  46         b = fnv_1a_b(a),
  47         i = -1,
  48         x = a % m;
  49     while (++i < k) {
  50       r[i] = x < 0 ? (x + m) : x;
  51       x = (x + b) % m;
  52     }
  53     return r;
  54   };
  55
  56   BloomFilter.prototype.add = function(v) {
  57     var l = this.locations(v + ""),
  58         i = -1,
  59         k = this.k,
  60         buckets = this.buckets;
  61     while (++i < k) buckets[Math.floor(l[i] / 32)] |= 1 << (l[i] % 32);
  62   };
  63
  64   BloomFilter.prototype.test = function(v) {
  65     var l = this.locations(v + ""),
  66         i = -1,
  67         k = this.k,
  68         b,
  69         buckets = this.buckets;
  70     while (++i < k) {
  71       b = l[i];
  72       if ((buckets[Math.floor(b / 32)] & (1 << (b % 32))) === 0) {
  73         return false;
  74       }
  75     }
  76     return true;
  77   };
  78
  79   // Estimated cardinality.
  80   BloomFilter.prototype.size = function() {
  81     var buckets = this.buckets,
  82         bits = 0;
  83     for (var i = 0, n = buckets.length; i < n; ++i) bits += popcnt(buckets[i]);
  84     return -this.m * Math.log(1 - bits / this.m) / this.k;
  85   };
  86
  87   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
  88   function popcnt(v) {
  89     v -= (v >> 1) & 0x55555555;
  90     v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  91     return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
  92   }
  93
  94   // Fowler/Noll/Vo hashing.
  95   function fnv_1a(v) {
  96     var n = v.length,
  97         a = 2166136261,
  98         c,
  99         d,
 100         i = -1;
 101     while (++i < n) {
 102       c = v.charCodeAt(i);
 103       if (d = c & 0xff000000) {
 104         a ^= d >> 24;
 105         a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);
 106       }
 107       if (d = c & 0xff0000) {
 108         a ^= d >> 16;
 109         a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);
 110       }
 111       if (d = c & 0xff00) {
 112         a ^= d >> 8;
 113         a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);
 114       }
 115       a ^= c & 0xff;
 116       a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);
 117     }
 118     // From http://home.comcast.net/~bretm/hash/6.html
 119     a += a << 13;
 120     a ^= a >> 7;
 121     a += a << 3;
 122     a ^= a >> 17;
 123     a += a << 5;
 124     return a & 0xffffffff;
 125   }
 126
 127   // One additional iteration of FNV, given a hash.
 128   function fnv_1a_b(a) {
 129     a += (a << 1) + (a << 4) + (a << 7) + (a << 8) + (a << 24);
 130     a += a << 13;
 131     a ^= a >> 7;
 132     a += a << 3;
 133     a ^= a >> 17;
 134     a += a << 5;
 135     return a & 0xffffffff;
 136   }
 137 })(typeof exports !== "undefined" ? exports : this);
 138 `
 139
 140 class DummyBloomFilter
 141   save: ->
 142   add: ->
 143   test: ->
 144   size: ->
 145   popcnt: ->
 146
 147 class SerializableBloomFilter extends exports.BloomFilter
 148   constructor: (@prefName, m, k) ->
 149     if data = getPref(@prefName)
 150       super(JSON.parse(data), k)
 151     else
 152       super(m, k)
 153
 154   save: ->
 155     data = JSON.stringify([].slice.call(@buckets))
 156     setPref(@prefName, data)
 157
 158
 159 exports.SerializableBloomFilter = SerializableBloomFilter
 160 exports.DummyBloomFilter = DummyBloomFilter