extension/lib/mode-hints/bloomfilter.coffee

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