#include <stdio.h> 
#include "minwise.h"

/* k-wise indepedent hashing function 
	from [2^n] to [2^r] with 2^-e  L1 Form */

kwHashFunction::kwHashFunction(int n_, int r_, int k_, int e_){
	n=n_;r=r_;k=k_;e=e_;

	//compute m according to the following formula
	//a K=2^k*r-wise independent distribution on N=2^n*r bit
	// with epsilon E=2^-e 
	// according to Th.3 Page 11 on Alon,Goldreich,et al 92
	// m=2*ceil(K/2+log2(1/E)+log(1+(K-1)*log(N+1))) 
 	// i.e m= K+ 2log(KlogN/2E)=2^k*r + 2*(k+log2(r)+log2(n+logr)-1+e) 
	m=(r<<k)+ 2*(k+e-1 + LOG2C(r)+LOG2C(n+LOG2C(r)));

#ifdef DEBUG
	printf("2^%d-wise 2^-%d away h: [2^%d]->[2^%d] constructed using %d"
	       " LFSR\n",k,e,n,r,m); 
#endif
	lfsr=new LFSR(m);
}

kwHashFunction::~kwHashFunction(){
	delete lfsr;
}

void kwHashFunction::hash(INTTYPE h,char *buf){
	lfsr->getBits(h*r,r,buf);
}

INTTYPE kwHashFunction::hash(INTTYPE h){
	char *buf=new char[r+1];
	INTTYPE result=0;
	lfsr->getBits(h*r,r,buf);
	for(int i=0;i<r;i++){
		result=(result<<1);
		result|=buf[i];
	}
#ifdef DEBUG
//	printf("h:%d->%d\n",h,result);
#endif
	return result;
}