wfMD5BloomFilter.php — Wordfence Security – Firewall, Malware Scan, and Login Security 7.3.2

wordfence / lib / wfMD5BloomFilter.php

wordfence / lib Last commit date

wfMD5BloomFilter.php

133 lines

1	<?php
2	/*
3	Copyright (c) 2012, Da Xue
4	All rights reserved.
5
6	Redistribution and use in source and binary forms, with or without
7	modification, are permitted provided that the following conditions are met:
8	1. Redistributions of source code must retain the above copyright
9	notice, this list of conditions and the following disclaimer.
10	2. Redistributions in binary form must reproduce the above copyright
11	notice, this list of conditions and the following disclaimer in the
12	documentation and/or other materials provided with the distribution.
13	3. The name of the author nor the names of its contributors may be used
14	to endorse or promote products derived from this software without
15	specific prior written permission.
16
17	THIS SOFTWARE IS PROVIDED BY DA XUE ''AS IS'' AND ANY
18	EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19	WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20	DISCLAIMED. IN NO EVENT SHALL DA XUE BE LIABLE FOR ANY
21	DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23	LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24	ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26	SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/
28
29	/* https://github.com/dsx724/php-bloom-filter */
30
31	// Modified for PHP 5.2 compatibility and to support serialization.
32
33	class wfMD5BloomFilter {
34	private static function merge($bf1,$bf2,$bfout,$union = false){
35	if ($bf1->m != $bf2->m) throw new Exception('Unable to merge due to vector difference.');
36	if ($bf1->k != $bf2->k) throw new Exception('Unable to merge due to hash count difference.');
37	$length = strlen($bfout->bit_array);
38	if ($union){
39	$bfout->bit_array = $bf1->bit_array \| $bf2->bit_array;
40	$bfout->n = $bf1->n + $bf2->n;
41	} else {
42	$bfout->bit_array = $bf1->bit_array & $bf2->bit_array;
43	$bfout->n = abs($bf1->n - $bf2->n);
44	}
45	}
46	public static function createFromProbability($n, $p){
47	if ($p <= 0 \|\| $p >= 1) throw new Exception('Invalid false positive rate requested.');
48	if ($n <= 0) throw new Exception('Invalid capacity requested.');
49	$k = floor(log(1/$p,2));
50	$m = pow(2,ceil(log(-$n*log($p)/pow(log(2),2),2))); //approximate estimator method
51	return new self($m,$k);
52	}
53	public static function getUnion($bf1,$bf2){
54	$bf = new self($bf1->m,$bf1->k,$bf1->hash);
55	self::merge($bf1,$bf2,$bf,true);
56	return $bf;
57	}
58	public static function getIntersection($bf1,$bf2){
59	$bf = new self($bf1->m,$bf1->k,$bf1->hash);
60	self::merge($bf1,$bf2,$bf,false);
61	return $bf;
62	}
63	private $n = 0; // # of entries
64	private $m; // # of bits in array
65	private $k; // # of hash functions
66	private $k2;
67	private $mask;
68	private $bit_array; // data structure
69	public function __construct($m, $k){
70	if ($m < 8) throw new Exception('The bit array length must be at least 8 bits.');
71	if (($m & ($m - 1)) !== 0) throw new Exception('The bit array length must be power of 2.');
72	if ($m > 65536) throw new Exception('The maximum data structure size is 8KB.');
73	if ($k > 8) throw new Exception('The maximum bits to set is 8.');
74	$this->m = $m;
75	$this->k = $k;
76	$this->k2 = $k * 2;
77	$address_bits = (int)log($m,2);
78	$this->mask = (1 << $address_bits) - 8;
79	$this->bit_array = (binary)(str_repeat("\0",$this->getArraySize(true)));
80	}
81	public function __sleep() {
82	return array('n', 'm', 'k', 'k2', 'mask', 'bit_array');
83	}
84	public function calculateProbability($n = 0){
85	return pow(1-pow(1-1/$this->m,$this->k*($n ? $n : $this->n)),$this->k);
86	}
87	public function calculateCapacity($p){
88	return floor($this->mlog(2)/log($p,1-pow(1-1/$this->m,$this->mlog(2))));
89	}
90	public function getElementCount(){
91	return $this->n;
92	}
93	public function getArraySize($bytes = false){
94	return $this->m >> ($bytes ? 3 : 0);
95	}
96	public function getHashCount(){
97	return $this->k;
98	}
99	public function getInfo($p = null){
100	$units = array('','K','M','G','T','P','E','Z','Y');
101	$M = $this->getArraySize(true);
102	$magnitude = intval(floor(log($M,1024)));
103	$unit = $units[$magnitude];
104	$M /= pow(1024,$magnitude);
105	return 'Allocated '.$this->getArraySize().' bits ('.$M.' '.$unit.'Bytes)'.PHP_EOL.
106	'Using '.$this->getHashCount(). ' (16b) hashes'.PHP_EOL.
107	'Contains '.$this->getElementCount().' elements'.PHP_EOL.
108	(isset($p) ? 'Capacity of '.number_format($this->calculateCapacity($p)).' (p='.$p.')'.PHP_EOL : '');
109	}
110	public function add($key){
111	$hash = md5($key,true);
112	for ($index = 0; $index < $this->k2; $index++){
113	$hash_sub = (ord($hash[$index++]) << 8) \| ord($hash[$index]);
114	$word = ($hash_sub & $this->mask) >> 3;
115	$this->bit_array[$word] = $this->bit_array[$word] \| chr(1 << ($hash_sub & 7));
116	}
117	$this->n++;
118	}
119	public function contains($key){
120	$hash = md5($key,true);
121	for ($index = 0; $index < $this->k2; $index++){
122	$hash_sub = (ord($hash[$index++]) << 8) \| ord($hash[$index]);
123	if ((ord($this->bit_array[($hash_sub & $this->mask) >> 3]) & (1 << ($hash_sub & 7))) === 0) return false;
124	}
125	return true;
126	}
127	public function unionWith($bf){
128	self::merge($this,$bf,$this,true);
129	}
130	public function intersectWith($bf){
131	self::merge($this,$bf,$this,false);
132	}
133	}