<?
/*

    De Gan filter, one-way-hash filter.

    overview: large scale, small footprint one-way-hash filter.

    this is: In order to have hashed datasets around 40M requires 75M in a bloom filter. 
        with the De Gan filter, this can be accomplished in about 20M.

example usage to create dictionary hashes:
###########################
$dfilt = _init_filter();
$f = fopen("/usr/share/dict/words", "r");
$words = explode("\n",fread($f, filesize("/usr/share/dict/words") ));
fclose($f);
while(list($key,$val)=each($words)){
    $dfilt = insert(trim($val), $dfilt);
}
// do a couple checks
echo check("dog", $dfilt); // should return 1
echo "\n";
echo check("zzzz", $dfilt); // should return 0
echo "\n";
datasave($dfilt, "wordsfilter.asc"); // save it
###########################

*/
define("FILTERSIZE", 50); // be careful to not set this lower than 5. Higher values get big fast

$codes = "abcdefghijklmnopqrstuvwxyz";// not a good idea to change these

function datasave($array, $filename) {
                $serialised = serialize($array);
                $f = fopen($filename, "w+");
                if (!$f)  {
                        echo "\nCould not open $filename!";
                        return;
                }
                $size = fwrite($f, $serialised);
                fclose($f);
}

function &dataload($filename) {
                if (file_exists($filename) ) {
                        $f = fopen($filename, "r");
                        $serialised = fread($f, filesize($filename) );
                        fclose($f);
                        if ($serialised < 0) {
                                return null;
                        }
                        return unserialize($serialised);
                }
                return null;
}

// initialize filter
function _init_filter(){
    for($a=0;$a<FILTERSIZE;$a++){
        $df .= "0";
    }
    for($a=0;$a<FILTERSIZE;$a++){
        $deganfilter[$a] = array_fill(0, FILTERSIZE, $df);
    }
  return $deganfilter;
}

// returns our point
function _vec($num, $size=FILTERSIZE, $p=""){
    global $codes;
    $n1 =  @unpack("N", $num);
    while(list($key,$val)=@each($n1)){
        $vec1 = $vec1 ^ $val;
    }
    if($p == ""){
        $rvec = ($vec1 % $size);
    }else{
        $r = ($vec1 % strlen($codes));
        $rvec = $codes{$r};
    }
    return $rvec;    
}

// returns hash points.
function _hash_item($item){
    $ret[0] = _vec(crc32($item), FILTERSIZE); // crc used for mult
    $ret[1] = _vec(md5($item));   // md5 used for X
    $ret[2] = _vec(sha1($item));  // sha1 used for Y
    $ret[3] = _vec(crc32($item), FILTERSIZE, "alpha"); // alphaval
  return $ret;
}

function isupper($c){
    return (ord($c) >= 65 && ord($c) <= 90);
}
function islower($c){
    return (ord($c) >= 97 && ord($c) <= 122);
}

function isalpha($c){
    return (isupper($c) || islower($c));
}

// explode codedstring into array
function explodecs($str){
    for($a=0;$a<strlen($str);$a++){
        $t = $str{$a};
        if(isupper($t)){
            $r .= $t;
        }else{
            $r .= $t;
            $ret[] = $r;
            $r = "";
        }
    }
    return $ret;
}

// insert a point into the hash
function csinsert($codedstring, $at, $val){
    $cs = explodecs($codedstring);
    $csval = $cs[$at];
    if($csval == "" || $val == ""){return $codedstring;}
    if($csval == "0"){ 
        $cs[$at] = $val;
        $back = implode("",$cs);
        return $back; 
    }
    for($a=0;$a<strlen($csval);$a++){
        $t[] = $csval{$a};
    }
    while(list(,$v)=each($t)){
        if(strtolower($v) == $val){ // dup
            return $codedstring;
        }else{
            $ret .= strtoupper($v);
        }
    }
    $ret .= $val;
    $cs[$at] = $ret;
    return implode("",$cs);
}// end function

// check value against the hash
function cscheck($codedstring, $at, $val){
    if($val == ""){ return false; }
    $cs = explodecs($codedstring);
    $ch = $cs[$at];
    for($a=0;$a<strlen($ch);$a++){
        $t[] = $ch{$a};
    }
    while(list(,$v)=each($t)){
        if(strtolower($v) == strtolower($val)){ // dup
            return true;
        }
    }
  return false;    
}

// insert
function insert($item, $filter){
    if(trim($item)==""){ return $filter; }
    $h = _hash_item($item);
    $h1 = $filter[$h[1]][$h[2]];
    $h2 = $filter[$h[2]][$h[1]];
    
    $filter[$h[1]][$h[2]] = csinsert($h1, $h[0], $h[3]);
    $filter[$h[2]][$h[1]] = csinsert($h2, $h[0], $h[3]);

    return $filter;
}

// check a value against the hash
function check($item, $filter){
    if(trim($item)==""){ return false; }
    reset($filter);
    $h = _hash_item($item);
    $h1 = $filter[$h[1]][$h[2]];
    $h2 = $filter[$h[2]][$h[1]];
    
    if( cscheck($filter[$h[1]][$h[2]], $h[0], $h[3]) && cscheck($filter[$h[2]][$h[1]], $h[0], $h[3])  ){
        return true;
    }//fi
    return false;
}


?>